ACM Transactions on Embedded Computing Systems · 2010 · 91 citations · 68 references
ComputingComputer EngineeringComputer ScienceEmbedded SystemsFormal MethodsSystems ModelingAbstract InterpretationModel CheckingVerificationAbstractionState Space ExplorationState-space AbstractionState-space StructureSymbolic Model Checking
The interest of industries in model checking software for microcontrollers is increasing. However, there are currently no appropriate tools that can be applied by embedded systems developers for the direct verification of software for microcontrollers without the need for manual modeling. This article describes a new approach to model checking software for microcontrollers, which verifies the assembly code of the software. The state space is built using a tailored simulator, which abstracts from time, handles nondeterminism, and creates an overapproximation of the behavior shown by the real microcontroller. Within this simulator, we apply abstraction techniques to tackle the state-explosion problem. In our approach, we combine different formal methods, namely, model checking, static analysis, and abstract interpretation. We also combine explicit and symbolic model checking techniques. This article presents a case study using several programs to demonstrate the efficiency of the applied abstraction techniques and to show the applicability of this approach.
68
E. M. Clarke, Orna Grümberg, D. Long · 1996 · 6.9K citations
Patrick Cousot, Radhia Cousot · 1977 · 6.2K citations
Depth-First Search and Linear Graph Algorithms
Robert E. Tarjan · SIAM Journal on Computing · 1972 · 6K citations
The temporal logic of programs
Amir Pnueli · 1977 · 5.7K citations