NOVEMBER 2009 | Edmund M. Clarke, E. Allen Emerson, and Joseph Sifakis
The 2007 ACM A.M. Turing Award was given to Edmund M. Clarke, E. Allen Emerson, and Joseph Sifakis for their foundational work in model checking, a method for algorithmic verification of system correctness. Their research established the field of model checking, which uses temporal logic (TL) to verify whether a system's behavior satisfies a formal specification. Model checking provides an algorithmic way to determine if an abstract model—such as a hardware or software design—meets a formal specification. If a property does not hold, the method identifies a counterexample execution that shows the source of the problem.
The development of model checking has been driven by the need to address the state explosion problem, which arises when the number of states in a system becomes too large to handle. Over the past 28 years, significant progress has been made in this area, leading to the widespread use of model checking in industry for verifying complex systems such as VLSI circuits, communication protocols, and real-time embedded systems.
Clarke, Emerson, and Sifakis have made substantial contributions to the field, including the development of new logics for specification, verification algorithms, and theoretical results. Their work has led to the creation of model checking tools that enable engineers to design complex systems with a high degree of assurance regarding their correctness. These tools have had a significant impact on the hardware and software industries, and their research continues to be central to the success of the field.
The paper discusses the evolution of model checking, the challenges of the state explosion problem, and the development of techniques such as symbolic model checking, partial order reduction, and bounded model checking. It also highlights the importance of expressiveness in model checking and the need for efficient algorithms that can handle large state spaces. The authors emphasize the importance of abstraction and refinement techniques in managing the complexity of large systems.
The paper concludes with a discussion of the future of model checking, including the need for further research in areas such as software model checking, real-time and hybrid systems, and the integration of model checking with theorem proving. The authors also highlight the importance of developing scalable verification methods and the need for further research in compositional verification techniques.The 2007 ACM A.M. Turing Award was given to Edmund M. Clarke, E. Allen Emerson, and Joseph Sifakis for their foundational work in model checking, a method for algorithmic verification of system correctness. Their research established the field of model checking, which uses temporal logic (TL) to verify whether a system's behavior satisfies a formal specification. Model checking provides an algorithmic way to determine if an abstract model—such as a hardware or software design—meets a formal specification. If a property does not hold, the method identifies a counterexample execution that shows the source of the problem.
The development of model checking has been driven by the need to address the state explosion problem, which arises when the number of states in a system becomes too large to handle. Over the past 28 years, significant progress has been made in this area, leading to the widespread use of model checking in industry for verifying complex systems such as VLSI circuits, communication protocols, and real-time embedded systems.
Clarke, Emerson, and Sifakis have made substantial contributions to the field, including the development of new logics for specification, verification algorithms, and theoretical results. Their work has led to the creation of model checking tools that enable engineers to design complex systems with a high degree of assurance regarding their correctness. These tools have had a significant impact on the hardware and software industries, and their research continues to be central to the success of the field.
The paper discusses the evolution of model checking, the challenges of the state explosion problem, and the development of techniques such as symbolic model checking, partial order reduction, and bounded model checking. It also highlights the importance of expressiveness in model checking and the need for efficient algorithms that can handle large state spaces. The authors emphasize the importance of abstraction and refinement techniques in managing the complexity of large systems.
The paper concludes with a discussion of the future of model checking, including the need for further research in areas such as software model checking, real-time and hybrid systems, and the integration of model checking with theorem proving. The authors also highlight the importance of developing scalable verification methods and the need for further research in compositional verification techniques.