Symbolic model checking provides partially effective verification procedures that can handle systems with an infinite state space. So-called "acceleration techniques" enhance the convergence of fixpoint computations by computing the transitive closure of some transitions. In this paper we develop a new framework for symbolic model checking with accelerations. We also propose and analyze new symbolic algorithms using accelerations to compute reachability sets. Context. The development of model checking techniques [19] for infinite-state systems is now an active field of research. These techniques allow considering models like pushdown systems [13] , channel systems [1, 14] , counter systems [8, 31, 38] , and many other versatile families of models. Such models are very expressive and often lead to undecidable verification problems. This did not deter several research teams from developing powerful innovative model checkers for infinite-state systems. For example, tools for checking reachability properties of counter systems are ALV [6], BRAIN [37], LASH [33], TREX [3] , and our own FAST [8] . For infinite-state systems, model checking must be "symbolic" since one manipulates (symbolic representations of) potentially infinite sets of configurations. The most popular symbolic representations are based on regular languages: these are quite expressive and automata-theoretical data structures provide efficient algorithms performing set-theoretical operations as well as preand post-image computations. With these ingredients, it becomes possible to launch a fixpoint computation for forward or backward reachability sets, as exemplified in [32] . The problem of convergence. When dealing with infinite-state systems, a naive fixpoint computation procedure for reachability sets, in the style of Procedure 1 (section 3.2), has very little chance to terminate: convergence in a finite number of steps can only occur if the system under study is uniformly bounded (see section 3.2). To make fixpoint Flat Acceleration in Symbolic Model Checking 475 computations converge more frequently, so-called "acceleration techniques" have been developed. These techniques can compute subsets of the reachability set that are not uniformly bounded. This can be done, for example, by replacing a control loop "x:=x+1; y:=y-1" by its transitive closure "k:=random int(); x:=x+k; y:=y-k". Currently, many different acceleration techniques for different families of systems exist [1, 2, 12, 14, 26, 38] . Some of them have been implemented [3, 8, 33] and promising case-studies have been reported [1, 2, 3, 8, 9] . Acceleration shares some similarities with the widening techniques used in abstract interpretation [22] but also exhibits some clear differences: acceleration aims at exact computation for some given control structures, while widening mostly ignores control structures and usually trades exactness for termination. A field in need of foundations. The existing acceleration results usually amount to a (sometimes difficult) theorem stating that the transitive closure of an action, or of a sequence of actions, can be effectively computed. The difficulty of these results usually lies in finding the precise conditions on the action and on the set of initial states that yield effectiveness. How to use acceleration results is not really known: the theorems and algorithms for computing reachability sets with acceleration methods do not exist in general! With some tools, e.g., LASH, the user has to choose which loops to accelerate and how to mix the outcomes with more standard symbolic computation; in other cases, e.g., with TREX, some default strategy is implemented outside of any theoretical framework and without discussions about its efficiency or completeness. We propose the first theoretical framework for symbolic model checking with acceleration. We distinguish three natural levels for accelerations ( "loop", "flat", and "global"), depending on which sequences of transitions can be computed: transitive closure of cycles (resp. of length 1) for flat (resp. loop) acceleration; or any regular set of sequences for global acceleration. These levels can account for most acceleration results on specific systems (pushdown systems, channel systems, counter systems, . . . ). For each level we give a symbolic algorithm with acceleration computing reachability sets and we characterize the conditions necessary for its termination. Flat acceleration is the most interesting level. As a matter of fact, loop acceleration is not sufficient for many of the example systems we have analyzed with our tool FAST. Furthermore, the majority of existing acceleration results stated at the loop acceleration level may be extended to the level of flat acceleration. At the other end of the spectrum, global acceleration is always sufficient but it occurs very rarely in practice and is essentially restricted to particular subclasses (e.g., pushdown systems, reversal-bounded counter systems [31] or particular subclasses of Petri nets). (2) We develop new concepts for the algorithmic study of flat acceleration. The notions of flattenings and of flattable systems provide the required bridge between flat acceleration and the effective computation of the reachability set. We propose new symbolic procedures and analyze them rigorously. We show Procedure REACH2 terminates iff it is applied to a flattable (rather than flat) system, which is the first completeness result on symbolic model checking with acceleration. We remark that most of the case studies we analyzed in earlier works with FAST are flattable but not flat, underlining the relevance of this concept.
REF present an overall framework for various classes of systems that can be treated by exact acceleration.
Flat acceleration in symbolic model checking
In ATVA'2005. LNCS 3707
Computer Science