Optimizing symbolic model checking for statecharts

被引：18

作者：

Chan, W

Anderson, RJ

Beame, P

Jones, DH

Notkin, D

Warner, WE

机构：

[1] Univ Washington, Dept Comp Sci & Engn, Seattle, WA 98195 USA

[2] Boeing Co, Seattle, WA 98124 USA

来源：

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING | 2001年 / 27卷 / 02期

基金：

美国国家科学基金会;

关键词：

formal verification; symbolic model checking; binary decision diagrams; requirements specifications; statecharts; RSML; TCAS II; partitioned transition relation; automatic abstraction; fault tolerance; avionic systems;

D O I：

10.1109/32.908961

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

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 model 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.

引用

页码：170 / 190

页数：21

共 41 条

[11]

CABODI G, 1994, PR IEEE COMP DESIGN, P230, DOI 10.1109/ICCD.1994.331895

[12]

Cabodi G, 1997, DES AUT CON, P728, DOI 10.1145/266021.266355

[13]

CABODI G, 1996, P INT C COMP AID DES, P10

[14]

Chan W., 1999, Proceedings of the 1999 International Conference on Software Engineering (IEEE Cat. No.99CB37002), P142, DOI 10.1109/ICSE.1999.841003

[15]

Chan W., 1998, Software Engineering Notes, V23, P102, DOI 10.1145/271775.271798

[16] Model checking large software specifications [J].

Chan, W ;

Anderson, RJ ;

Beame, P ;

Burns, S ;

Modugno, F ;

Notkin, D ;

Reese, JD .

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, 1998, 24 (07) :498-520

[17]

CHANG J, 1994, P 4 IRV SOFTW S APR

[18]

Clarke E.M., 1981, LECT NOTES COMPUTER, P52, DOI [DOI 10.1007/BFB0025774, 10.1137/0201010]

[19] MODEL CHECKING AND ABSTRACTION [J].

CLARKE, EM ;

GRUMBERG, O ;

LONG, DE .

ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS, 1994, 16 (05) :1512-1542

[20] Exploiting symmetry in temporal logic model checking [J].

Clarke, EM ;

Enders, R ;

Filkorn, T ;

Jha, S .

FORMAL METHODS IN SYSTEM DESIGN, 1996, 9 (1-2) :77-104

← 1 2 3 4 5 →