Improved reachability analysis of large finite state machines

Abstract

BDD-based symbolic traversals are the state-of-the-art technique for reachability analysis of Finite State Machines. They are currently limited to medium-small circuits for two reasons: peak BDD size during image computation and BDD explosion for representing state sets. Starting from these limits, this paper presents an optimized traversal technique particularly oriented to the exact exploration of the state space of large machines. This is possible thanks to: 1) temporary simplification of a Finite State Machine by removing some of its state elements, 2) a divide-and-conquer approach based on state set decomposition. An effective use of secondary memory allows us to store relevant portions of BDDs and to regularize access to memory, resulting in less page faults. Experimental results show that this approach is particularly effective on the larger ISCAS'89 and ISCAS'89-addendum'93 circuits.