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: grade report corrected.
• 2024/01/07: grade report available (corrected 01/08); please send requests/inquiries, if any, to the instructor by 2PM 01/08 (Mon.).
• 12/20: the final is due 5:30PM.
• 12/13: slides for Compositional Reasoning available.
• 12/12: solutions to homework assignments: HW#3, HW#4, HW#5,HW#6.
• 12/06: HW#7 for exercise (not counted toward grade).
• 12/06: slides for UNITY and Temporal Verification available.
• 11/30: You may submit up to three proposals for the term project by the deadline.
• 11/29: Term Project: proposal due 12/15 and final results due 12/29.
• 11/29: old exams.
• 11/29: slides for the Owicki-Gries Method available.
• 11/29: HW#6 due on 12/06.
• 11/21: slides and examples for Using Frama-C available.
• 11/08: HW#5 due on 11/22.
• 11/08: slides for Frama-C and ACSL available.
• 10/31: slides for Hoare Logic (II): Procedures available.
• 10/22: slides for Predicate Transformers available.
• 10/22: HW#4 due on 11/01.
• 10/16: slides for Soundness and Completeness of Hoare Logic available.
• 10/11: slides for Hoare Logic (I) and two notes available.
• 10/09: solutions to homework assignments: HW#1, HW#2.
• 09/27: HW#3 due on 10/11.
• 09/18: slides and a note for Coq available.
• 09/15: HW#2 due on 09/27.
• 09/08: HW#1 due on 09/20.
• 09/07: classroom changed again to Room 203, Management Building 1.
• 09/06: classroom changed to Room 204, Management Building 2.
• 09/06: HW#0 due on 09/13.
• 09/06: slides for Course Introduction, Propositional Logic, and First-Order Logic and a note on Natural Deduction available.
• 09/03: this wiki site created to complement the NTU COOL site for this course.

Yih-Kuen Tsay (蔡益坤), NTU IM Dept., 3366-1189, Xtsay@ntu.edu.twX (between the enclosing pair of X's)

Wednesday 2:20-5:20PM, Room 203, Management Building 1

Tuesday 1:30~2:00PM, Wednesday 1:30~2:00PM, or by appointment, Room 1108, Management Building 2.

There is no TA for this course.

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: Reasoning about Programs (.5 week: 09/06a) [slides]
• Fundamentals: Propositional and First-Order Logics (2.5 weeks: 09/06b, 09/13, 09/20) [slides:Propositional Logic, First-Order Logic; notes: Natural Deduction]
• Verification Tools: Coq (2 weeks: 09/27, 10/04) [slides; notes:Tactics for Natural Deduction in Coq]
• Sequential Programs: Hoare Logic (I) (2 weeks: 10/11, 10/18) [slides:Hoare Logic, Soundess and Completeness; notes: Rules of Hoare Logic, Proofs with Hoare Logic]
• Predicate Transformers (1 week: 10/25) [slides]
• Procedures: Hoare Logic (II) (1 week: 11/01) [slides]
• Verification Tools: Frama-C + Plugins (2 weeks: 11/08, 11/22) [slides: Frama-C and ACSL, Using Frama-C; examples:Frama-C Examples]
• Concurrent, Reactive Systems: Owicki-Gries Method (1 week: 11/29) [slides]
• Concurrent, Reactive Systems: UNITY and Linear Temporal Logic (1 week: 12/06) [slides: UNITY,Temporal Verification]
• Selected Topics: Modular/Compositional Reasoning (1 week: 12/13) [slides]
• Final Exam (2023/12/20)

Homework Assignments 20%, Participation 10%, Final Exam 40%, Term Paper/Report 30%.

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. The Coq Proof Assistant: https://coq.inria.fr.
5. Interactive Theorem Proving and Program Development, Y. Bertot and P. Castéran, Springer, 2004.
6. 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.)
7. Certified Programming with Dependent Types , A. Chilipala. (Note: click on the link to author's free download site.)
8. Foundations for Programming Languages, J.C. Mitchell, The MIT Press, 1996.
9. Formal Syntax and Semantics of Programming Languages, K. Slonneger and B.L. Kurtz, Addison-Wesley, 1995.
10. Verification of Sequential and Concurrent Programs, Third Edition, K.R. Apt, F.S. de Boer, and E.-R. Olderog, Springer, 2009.
11. The Science of Programming, D. Gries, Springer-Verlag, 1981.
12. Predicate Calculus and Program Semantics, E.W. Dijkstra and C.S. Scholten, Springer-Verlag, 1990.
13. Programming from Specifications, 2nd Edition, C. Morgan, Prentice Hall, 1994.
14. Frama-C: https://www.frama-c.com.
15. Introduction to C program proof with Frama-C and its WP plugin, Allan Blanchard, 2020.
16. ACSL Mini-Tutorial, Virgile Prevosto.
17. The Z Notation: A Reference Manual, 2nd Edition, J.M. Spivey, 1992. (Note: click on the link to author's free download site.)
18. Software Engineering with B, J.B. Wordsworth, Addison-Wesley, 1996.
19. Modeling in Event-B: System and Software Engineering, J.-R. Abrial, Cambridge University Press, 2010.
20. The Temporal Logic of Reactive and Concurrent Systems: Specification, Z. Manna and A. Pnueli, Springer-Verlag, 1992.
21. Temporal Verification of Reactive Systems: Safety, Z. Manna and A. Pnueli, Springer, 1995.
22. Temporal Verification of Reactive Systems: Progress, Z. Manna and A. Pnueli, Book Draft, 1996. (Note: click on the link to authors' free download site.)
23. Specifying Systems: The TLA+ Language and Tools for Hardware and Software Engineers, L. Lamport, Addison-Wesley, 2003.
24. Parallel Program Design: A Foundation, K.M. Chandy and J. Misra, Addison-Wesley, 1988.
25. A Discipline of Multiprogramming: Programming Theory for Distributed Applications, J. Misra, Springer, 2001
26. 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
27. 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.)