Efficient Reachability Analysis of Hierarchic Reactive Machines

Rajeev Alur, Radu Grosu, and Michael McDougall

Hierarchical state machines is a popular visual formalism for software specifications. To apply automated analysis to such specifications, the traditional approach is to compile them to existing model checkers. Aimed at exploiting the modular structure more effectively, our approach is to develop algorithms that work directly on the hierarchical structure. First, we report on an implementation of a visual hierarchical language with modular features such as nested modes, variable scoping, mode reuse, exceptions, group transitions, and history. Then, we identify a variety of heuristics to exploit these modular features during reachability analysis. We report on an enumerative as well as a symbolic checker, and case studies.

Proceedings of the 12th International Conference on Computer-Aided Verification (CAV'00), LNCS 1855, Springer, pp. 280--295, 2000.