Symbolic model checking of extended finite state machines with linear constraints over integer variables
✍ Scribed by Takashi Takenaka; Kozo Okano; Teruo Higashino; Kenichi Taniguchi
- Publisher
- John Wiley and Sons
- Year
- 2006
- Tongue
- English
- Weight
- 338 KB
- Volume
- 37
- Category
- Article
- ISSN
- 0882-1666
No coin nor oath required. For personal study only.
✦ Synopsis
Abstract
We propose a symbolic model checking algorithm for a class of extended finite state machines equipped with integer variables (FSM/int). An FSM/int has several constraints on variable assignments, such as a variable of FSM/int keeps its value until the control visits at the definition transition and new value is fed via external input. Our model checking algorithm verifies whether an FSM/int satisfies a property described in CTL‐like expressions over integer variables. We have implemented a model checker, and verified that blackjack dealer circuits and a packet multiplex protocol satisfy some designated properties. We have found that the verification of systems with 100 states and 10 integer variables can be carried out in a few seconds in most cases (in the worst case, a few minutes). © 2006 Wiley Periodicals, Inc. Syst Comp Jpn, 37(6): 64–72, 2006; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/scj.20264