Model Checking

Embedded software control many of the safety-critical systems that we deal with in everyday life: for instance, modern cars are equipped with software to automatically change gears; pacemakers come with a software controller to regulate heart beat; aircrafts have flight control software, and so on. Typically, these (software) controllers have to make decisions based on inputs coming from multiple interacting components. As the size and the number of interacting components increase, the design and verification of controllers becomes increasingly complex.Model checking is a field of research that addresses this challenge by making use of mathematical models in the design and verification of controllers. The main idea is to look at the system as a mathematical model - commonly used models are extensions of finite-state machines. Design requirements on the controller then get translated to suitable questions on these mathematical models.The goal of this course is to understand some of the techniques and tools used in the process of model-checking.INTENDED AUDIENCE : This course would be relevant to CSE/EE/ECE/IT students. It would also cater to engineers in the industry who are looking forward to rigorous design and testing methods.PREREQUISITES : Familiarity with basic algorithms and finite-state machines preferableINDUSTRY SUPPORT : NIL

Week 1: Modeling systems as Finite-state machines
Week 2: Using the model-checker NuSMV
Week 3: Linear-time properties for verification
Week 4: Regular properties – automata over finite words
Week 5: Omega-regular properties – automata over infinite words
Week 6: Model checking omega-regular properties
Week 7: Linear Temporal Logic (LTL)
Week 8: Algorithms for LTL
Week 9: Computation Tree Logic (CTL)
Week 10: Algorithms for CTL
Week 11: Binary Decision Diagrams (BDDs)
Week 12: Models with timing constraints – timed automataRegular properties – automata over finite words