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

Volume

27

Issue

2

fYear

2001

fDate

2/1/2001 12:00:00 AM

Firstpage

170

Lastpage

190

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;

fLanguage

English

Journal_Title

Software Engineering, IEEE Transactions on

Publisher

ieee

ISSN

0098-5589

Type

jour

DOI

10.1109/32.908961

Filename

908961