This paper shows how reactive systems can be modelled and analysed using finite-state machines and temporal logic, and how model checking tools can be used to verify crucial properties of safety-critical systems. The paper also provides an introduction into the algorithms and data structures used to model check very large finite-state systems.
There will be assignments to practice the use of two different model checkers, and a test will assess the theoretical aspects of temporal logic and model checking algorithms. During a final assignment, students will have the opportunity to build their own model checker.
Having completed this paper, students will be able to specify the behaviour of reactive systems using finite-state machines and temporal logic. They will be able to use model checkers to check whether crucial properties are satisfied, and understand the way how model checkers work.
This paper contributes to the capabilities 1, 2, 4, 5, 6, 8, and 9 of the Software Engineering Graduate Profile.
COMP235 Logic and Computation and
60 points at 300 level in Computer Science
Students entering this paper are expected to know about propositional logic and finite-state machines. The final assignment requires Java programming skills.
COMP552 Model Checking
- Dr. Robi Malik
Phone: +64 7 838 4796
Official Timetable Information
Students are expected to spend about twelve hours per week on this paper: two hours in lectures, four hours reading and thinking, and six hours on the assignments.
Bérard, M. Bidoit, A. Finkel, F. Laroussinie, A. Petit, L. Petrucci, Ph. Schnoebelen, Systems and Software Verification, Springer, 2001.
Michael Huth, Mark Ryan, Logic in Computer Science, 2nd edition, Cambridge University Press, 2004.
The Linux computers in Computing
Laboratory 6 (R G.18) can be used for the assignments.
This paper is fully internally assessed. There will be three computer-based assignments, each using a different model checking environment. An in-class test will assess competency in the theoretic aspects of model checking.
Internal assessment/final examination ratio 1:0
||Due ||Mon 24 Mar ||Weight 30%|
||Due ||Mon 14 Apr ||*|
||Held ||Fri 16 May ||Weight 30%|
||Due ||Mon 9 Jun ||Weight 40%|
*Assignment 2 is optional for COMP452 students. If it is submitted, the COMP552 grading schedule (Assignment 1 worth 20%, Assignment 2 worth 20%, Test worth 30% Assignment 3 worth 30%) will be applied in cases where it improves the final grade.
Numerical marks will be used to grade assignments and tests, with detailed schedules provided with each assessment item. The weighted total of marks over all assessment items will determine the final grade based on the
University grading schedule.
An overall mark of 50% is required for a pass.
Assignment submission deadlines are firm. Late submissions will not be accepted.
Assignment submission requirements will vary depending on the nature of the assignments, and specific instructions will be provided with each assignment. There will be electronic submissions through Moodle, plus paper components to be placed in a drop-in box.
Marked assignments and tests will usually be returned to students during the supervised lab following the submission deadline.
Class attendance is expected. The course notes provided are not comprehensive, additional material will be covered in class. You are responsible for all material covered in class.
Follow this link for Academic Integrity information and this link for detailed explanation of How to prevent plagiarism in Computer Science assessment items.
Follow this link for information on Performance Impairment.
Student Concerns and Complaints
Follow this link for Student Concerns and Complaints information.
Application for Extension
Follow this link for information on applying for an Extension.
Review of Grade
Follow this link for information on applying for a Review of Grade.
Your attention is drawn to the following regulations and policies, which are published in the University Calendar: