Software Specification and Verification, Fall 2014

This is an introductory course on formal software specification and verification, covering various formalisms, methods, and tools for specifying the properties of a software program and for verifying that the program meets its specification. Its goal is to acquaint the students with fundamentals of formal software verification and to prepare them for conducting research in the area. We will focus on deductive (theorem proving) methods. A separate, complementary course entitled “Automatic Verification” covers algorithmic (model checking) methods.

• 01/08: solutions to homework assignments: HW#1, HW#2, HW#3.
• 01/02: old exams.
• 12/25: slides for the B-Method available.
• 12/24: slides for Temporal Verification available.
• 12/24: slides for the Owicki-Gries Method and for UNITY available.
• 12/18: HW#5 due on 2015/01/08.
• 12/18: slides for Z available.
• 11/24: HW#4 due on 11/27.
• 11/24: HW#3.
• 11/13: slides for Hoare Logic (II): Procedures available.
• 11/01: slides for Soundness and Completeness of Hoare Logic revised.
• 10/30: slides for Predicate Transformers available.
• 10/30: slides for Soundness and Completeness of Hoare Logic available.
• 10/16: slides for Hoare Logic (I) and two notes available.
• 10/10: HW#2 due on 10/23.
• 10/10: HW#1 due on 10/16.
• 10/09: slides and a note for Logical Proofs in Coq available.
• 09/26: slides for First-Order Logic available.
• 09/18: HW#0 due on 09/25.
• 09/17: slides for Course Introduction and Propositional Logic and a note on Natural Deduction available.
• 09/17: this website is the sole source of all up to date course information and syllabus; there will be no separate PDF version.

Yih-Kuen Tsay (蔡益坤), Room 1108, Management II, 3366-1189, Xtsay@im.ntu.edu.twX (between the enclosing pair of X's)

Thursday 1:20-2:50PM and 5:00-6:00PM, Room 204, College of Management, Building I
Note: when the class is small enough, we will meet in Room 1108, Management Building II.

Wednesday 1:30-2:00PM (Room 1108, Management II) or by appointment

Computer Programming and Discrete Mathematics

Class Notes and Selected Readings

We shall seek to strike a balance between depth and breadth, covering both the foundations and some of the more successful formalisms, techniques, and tools. Below is a tentative list of topics and their schedule:

• Introduction (.5 week: 09/18a)
  [slides]
• Propositional and First-Order Logics (2.5 weeks: 09/18b, 09/25, 10/02)
  [slides:Propositional Logic, First-Order Logic; notes: Natural Deduction]
• Logical Proofs in the Coq Proof Assistant (1 week: 10/09)
  [slides; Tactics for Natural Deduction in Coq]
• Verification of Sequential Programs: Hoare Logic (2 weeks: 10/16, 10/23)
  [slides:Hoare Logic, Soundess and Completeness; notes: Rules of Hoare Logic, Proofs with Hoare Logic]
• Predicate Transformers and Program Derivation (1 week: 10/30)
  [slides]
• Procedures (+ Object Orientation) (1 week: 11/06)
  [slides]
• Program Verification Tools: Coq, Why, and Frama-C (2 weeks: 11/13, 11/20)
  [slides: Why, Frama-C]
• Data Refinement + Formal Methods: Z and B (2 weeks: 11/27, 12/04)
  [slides: Z, B]
• Concurrent, Reactive Systems: Owicki-Gries Method, UNITY, Linear Temporal Logic (2 weeks: 12/11, 12/18)
  [slides:Owicki-Gries, UNITY, Temporal Verification]
• Selected Topic: Modular/Compositional Reasoning (1 week: 12/25)
  [slides]
• Final (2015/01/08)
• Selected Topic: Separation Logic (1 week: 2015/01/15)

Homework Assignments 15%, Final 35%, Term Paper/Report 40%, Participation 10%.

1. Logic for Computer Science: Foundations of Automatic Theorem Proving, J.H. Gallier, Harper & Row Publishers, 1985. (Note: click on the link to author's free download site.)
2. Proof Theory and Automated Deduction, J. Goubault-Larrecq and I. Mackie, Kluwer Academic Publishers, 1997.
3. Logic in Computer Science: Modelling and Reasoning about Systems, M. Huth and M. Ryan, Cambridge University Press, 2004.
4. Foundations for Programming Languages, J.C. Mitchell, The MIT Press, 1996.
5. Formal Syntax and Semantics of Programming Languages, K. Slonneger and B.L. Kurtz, Addison-Wesley, 1995.
6. Verification of Sequential and Concurrent Programs, 2nd Edition, K.R. Apt and E.-R. Olderog, Springer-Verlag, 1997.
7. The Science of Programming, D. Gries, Springer-Verlag, 1981.
8. Predicate Calculus and Program Semantics, E.W. Dijkstra and C.S. Scholten, Springer-Verlag, 1990.
9. Programming from Specifications, 2nd Edition, C. Morgan, 1994.
10. Software Foundations, B.C. Pierce, C. Casinghino, M. Greenberg, V. Sjöberg, and B. Yorgey. (Note: click on the link to authors' free download site.)
11. Certified Programming with Dependent Types , A. Chilipala. (Note: click on the link to author's free download site.)
12. The Z Notation: A Reference Manual, 2nd Edition, J.M. Spivey, 1992. (Note: click on the link to author's free download site.)
13. Software Engineering with B, J.B. Wordsworth, Addison-Wesley, 1996.
14. Modeling in Event-B: System and Software Engineering, J.-R. Abrial, Cambridge University Press, 2010.
15. The Temporal Logic of Reactive and Concurrent Systems: Specification, Z. Manna and A. Pnueli, Springer-Verlag, 1992.
16. Temporal Verification of Reactive Systems: Safety, Z. Manna and A. Pnueli, Springer, 1995.
17. Temporal Verification of Reactive Systems: Progress, Z. Manna and A. Pnueli, Book Draft, 1996. (Note: click on the link to authors' free download site.)
18. Specifying Systems: The TLA+ Language and Tools for Hardware and Software Engineers, L. Lamport, Addison-Wesley, 2003.
19. Parallel Program Design: A Foundation, K.M. Chandy and J. Misra, Addison-Wesley, 1988.
20. A Discipline of Multiprogramming: Programming Theory for Distributed Applications, J. Misra, Springer, 2001
21. Beauty Is Our Business: A Birthday Salute to Edsger W. Dijkstra, Edited by W.H.J. Feijen, A.J.M. van Gasteren, D. Gries, and J. Misra, Springer-Verlag, 1990
22. The Formal Methods Page: http://formalmethods.wikia.com/wiki/Formal_methods, J. Bowen. (Note: this Web portal provides links to numerous formal methods and tools.)