NOVEMBER 2009 | VOL. 52 | NO. 11 | Moshe Y. Vardi, Editor-in-Chief
The 2007 ACM A.M. Turing Award was awarded to Edmund M. Clarke, E. Allen Emerson, and Joseph Sifakis for their foundational work in model checking, a verification technology that uses algorithms to determine whether an abstract model satisfies a formal specification expressed as a temporal logic (TL) formula. Model checking has become a highly successful field, with applications in hardware and software verification, including VLSI circuits, communication protocols, software device drivers, real-time embedded systems, and security algorithms.
The development of model checking has been driven by the need to address the state explosion problem, which arises when the number of possible states in a system becomes too large to handle explicitly. Over the past 28 years, significant progress has been made in this area, leading to the creation of new logics for specification, verification algorithms, and theoretical results. Model checking tools have revolutionized the verification process, enabling engineers to design complex systems with high assurance of correctness.
Key contributions include the use of temporal logic to specify correct system behavior, the development of efficient search procedures to find counterexamples, and the introduction of symbolic model checking using ordered binary decision diagrams (OBDDs). These advancements have made it possible to verify systems with an extremely large number of states, including those with infinite state spaces.
Despite these achievements, the state explosion problem remains a significant challenge. Future research directions include developing new abstraction techniques, combining model checking with static analysis, and exploring compositional verification methods to handle large and complex systems more efficiently. The authors also discuss the importance of requirements specification, building faithful executable models, and scalable verification methods, emphasizing the need for further theoretical and practical advancements in the field.The 2007 ACM A.M. Turing Award was awarded to Edmund M. Clarke, E. Allen Emerson, and Joseph Sifakis for their foundational work in model checking, a verification technology that uses algorithms to determine whether an abstract model satisfies a formal specification expressed as a temporal logic (TL) formula. Model checking has become a highly successful field, with applications in hardware and software verification, including VLSI circuits, communication protocols, software device drivers, real-time embedded systems, and security algorithms.
The development of model checking has been driven by the need to address the state explosion problem, which arises when the number of possible states in a system becomes too large to handle explicitly. Over the past 28 years, significant progress has been made in this area, leading to the creation of new logics for specification, verification algorithms, and theoretical results. Model checking tools have revolutionized the verification process, enabling engineers to design complex systems with high assurance of correctness.
Key contributions include the use of temporal logic to specify correct system behavior, the development of efficient search procedures to find counterexamples, and the introduction of symbolic model checking using ordered binary decision diagrams (OBDDs). These advancements have made it possible to verify systems with an extremely large number of states, including those with infinite state spaces.
Despite these achievements, the state explosion problem remains a significant challenge. Future research directions include developing new abstraction techniques, combining model checking with static analysis, and exploring compositional verification methods to handle large and complex systems more efficiently. The authors also discuss the importance of requirements specification, building faithful executable models, and scalable verification methods, emphasizing the need for further theoretical and practical advancements in the field.