INFS 780 Theoretical Foundations of System Security

Professor Ravi Sandhu

Fall 2003, Tuesday 4:30pm - 7:10pm, Innovation 136

This is a new course. It is mathematically VERY demanding. Doctoral students pursuing the Information Security track should take this course. The course is also appropriate for any Graduate Student interested in learning computer science theory that applies to many areas of Information Technology.

INFS 780 will be a prerequisite for IT 862 in Spring 2004. IT 862 will assume knowledge of the theory taught in INFS 780.

Note to doctoral students: This course is required for students in the new Information Security and Assurance track.

Important Notice:

  • 12/16/03: Examination 2 has been received from ALL students.
  • 11/30/03: Examination 2 has been posted here.  Due on 12/15/03.  Clarifications will be posted on the examination page.
  • 10/08/03: Examination 1 has been posted here.  Due on 10/21/03 in class.  Clarifications will be posted on the examination page.
  • 9/21/03: Examination questions will be posted AFTER the review session on 10/7/03.  This overrides the announcement made in the 9/16/03 lecture.
  • Please do not sign up for this course unless you have
    • completed INFS 501 or equivalent
    • are mathematically inclined
    • willing to work hard and study independently
  • This is a tough course with high expectations of the students. Be prepared to be self-reliant and don't let yourself get surprised. Do not expect help or hand-holding outside the lectures. Students have to handle the mathematics by themselves.
  • Look forward to an exciting course!

Course Prerequisites:    

  • Must be familiar with Discrete mathematics and Formal notation (such as INFS 501).
  • There are NO exceptions to these prerequisites. SORRY!

Schedule of Classes:

  • 8/26/03: Sipser, Chapter 1 Regular Languages (Read Chapter 0 of Sipser prior to first lecture)
  • 9/2/03: Sipser, Chapter 1 Regular Languages. Chapter 3 Church-Turing Thesis
  • 9/9/03: Sipser, Chapter 3 Church-Turing Thesis.  Chapter 4 Decidability. 
  • 9/16/03: Sipser, Chapter 5 Reducibility
  • 9/23/03: no lecture
  • 9/30/03: Sipser, Chapter 7 Time Complexity
  • 10/7/03: Sipser, Chapter 7 Time Complexity.  REVIEW.
  • 10/14/03: Examination 1 (Take-home) posted on 10/8/03 here, due on 10/21/03 in class.
  • 10/21/03: Huth-Ryan, Chapter 1 Propositional Logic
  • 10/28/03: Huth-Ryan, Chapter 2 Predicate Logic
  • 11/4/03: no lecture
  • 11/11/03: Huth-Ryan, Chapter 2 Predicate Logic
  • 11/18/03: Huth-Ryan, Chapter 3 Model Checking
  • 11/25/03: Huth-Ryan, Chapter 3 Model Checking
  • 12/4/03: Huth-Ryan, Chapter 4 Program Verification.  REVIEW.
  • 12/11/03: Examination 2 (Take-home) posted on 11/30/03 here, due on 12/15/03.

Grading Policy:

  • Grades will be based on the 2 examinations with equal weightage.

Course Structure and Textbooks:    

  • The course covers material from 2 textbooks as follows.
    • Lectures on the theory of computation (roughly 50% of the course).
      Textbook: Introduction to the Theory of Computation, Michael Sipser, PWS Publishing 1997.
    • Lectures on logic (roughly 50% of the course).
      Textbook: Logic in Computer Science, Michael Huth and Mark Ryan, Cambridge University Press, 2000.