Title :
Optimizing symbolic model checking for statecharts
Author :
Chan, William ; Anderson, Richard J. ; Beame, Paul ; Jones, David H. ; Notkin, David ; Warner, William E.
Author_Institution :
Dept. of Comput. Sci. & Eng., Washington Univ., Seattle, WA, USA
fDate :
2/1/2001 12:00:00 AM
Abstract :
Symbolic model checking based on binary decision diagrams is a powerful formal verification technique for reactive systems. In this paper, we present various optimizations for improving the time and space efficiency of symbolic modal checking for systems specified as statecharts. We used these techniques in our analyses of the models of a collision avoidance system and a fault-tolerant electrical power distribution (EPD) system, both used on commercial aircraft. The techniques together reduce the time and space requirements by orders of magnitude, making feasible some analysis that was previously intractable. We also elaborate on the results of verifying the EPD model. The analysis disclosed subtle modeling and logical flaws not found by simulation
Keywords :
aerospace computing; aircraft; binary decision diagrams; collision avoidance; fault tolerant computing; formal verification; binary decision diagrams; collision avoidance system; commercial aircraft; fault-tolerant electrical power distribution system; formal verification; reactive systems; space efficiency; statecharts; symbolic model checking optimization; time efficiency; Aerospace electronics; Aircraft; Binary decision diagrams; Boolean functions; Collision avoidance; Data structures; Formal verification; Hardware; Power distribution; Power system modeling;
Journal_Title :
Software Engineering, IEEE Transactions on
