Linear Temporal Logic Symbolic Model Checking

We are seeing an increased push in the use of formal verification techniques in safety-critical software and hardware in practice. Formal verification has been successfully used to verify systems such as air traffic control, airplane separation assurance, autopilot, CPU designs, life-support systems, medical equipment (such as devices which administer radiation), and many other systems which ensure human safety. This survey provides a perspective on the formal verification technique of linear temporal logic (LTL) symbolic model checking, from its history and evolution leading up to the state-of-the-art. We unify research from 1977 to 2009, providing a complete end-to-end analysis embracing a users’ perspective by applying each step to a real-life aerospace example. We include an in-depth examination of the algorithms underlying the symbolic model-checking procedure, show proofs of important theorems, and point to directions of ongoing research. The primary focus is on model checking using LTL specifications, though other approaches are briefly discussed and compared to using LTL.