BDD-based software verification

In software model checking, most successful symbolic approaches use predicates as representation of the state space, and SMT solvers for computations on the state space; BDDs are often used as auxiliary data structure. Although BDDs are applied with great success in hardware verification, BDD representations of software state spaces were not yet thoroughly investigated, mainly because not all operations that are needed in software verification are efficiently supported by BDDs. We evaluate the use of a pure BDD representation of integer values, and focus on a particular class of programs: event-condition-action (ECA) programs with limited operations. A symbolic representation using BDDs seems appropriate for ECA programs under certain conditions. We configure a program analysis based on BDDs and experimentally compare it to four approaches to verify reachability properties of ECA programs: an explicit-value analysis, a symbolic bounded-loops analysis, a predicate-abstraction analysis, and a predicate-impact analysis. The results show that BDDs are efficient for a restricted class of programs, which yields the insight that BDDs could be used selectively for variables that are restricted to certain program operations (according to the variable’s domain type), even in general software model checking. We show that even a naive portfolio approach, in which after a pre-analysis either a BDD-based analysis or a predicate-impact analysis is performed, outperforms all above-mentioned analyses.     

一种基于LTL性质的面向对象并发程序切片方法

为了缩减程序验证的状态空间,针对面向对象程序的并发机制,定义了程序中存在的依赖关系,提出一种从待验证的线性时序逻辑(LTL)性质中提取出切片准则对程序进行切片的方法。切片后的程序与原程序对待验证的LTL性质具有相同的可满足性,而其对应的状态转换图中的状态个数明显减少。     

State-space caching revisited

State-space caching is a verification technique for finite-state concurrent systems. It performs an exhaustive exploration of the state space of the system being checked while storing only all states of just one execution sequence plus as many other previously visited states as available memory allows. So far, this technique has been of little practical significance: it allows one to reduce memory usage by only twoo to three times, before an unacceptable blow-up of the run-time overhead sets in. The explosion of the run-time requirements is due to redundant multiple explorations of unstored parts of the state space. Indeed, almost all states in the state space of concurrent systems are typically reached several times during the search.In this paper, we present a method to tackle the main cause of this prohibitive state matching: the exploration of all possible interleavings of concurrent executions of the system which all lead to the same state. Then, we show that, in many cases, with this method, most reachable states are visited only once during state-space exploration. This enables one not to store most of the states that have already been visited without incurring too much redundant explorations of parts of the state space, and makes therefore state-space caching a much more attractive verification method. As an example, we were able to competely explore a state space of 250,000 states while storing simultaneously no more than 500 states and with only a three-fold increas of the run-time requirements.     

基于事件集的反应系统模型的验证

在总结前人工作的基础上,提出了一种有效检测并发或反应系统的动态行为模型中违反安全属性的方法,目的是减少为检测违反安全属性所需检测的状态数量,验证过程包括构造一个由所有独立状态图组成的全局状态空间图,并遍历这个全局状态空间图中的状态以便检测安全协议。首先读待验证的安全属性和可能会违反这些属性的相关事件集,构造全局状态空间图只考虑相关事件产生的状态转换。使用该方法验证了"火车道口"系统,减少了59%的搜索空间。     

A new approach for the verification of cache coherence protocols

We introduce a cache protocol verification technique based on a symbolic state expansion procedure. A global Finite State Machine (FSM) model characterizing the protocol behavior is built and protocol verification becomes equivalent to finding whether or not the global FSM may enter erroneous states. In order to reduce the complexity of the state expansion process, all the caches in the same state are grouped into an equivalence class and the number of caches in the class is symbolically represented by a repetition constructor. This symbolic representation is partly justified by the symmetry and homogeneity of cache-based systems. However, the key idea behind the representation is to exploit a unique property of cache coherence protocols: the fact that protocol correctness is not dependent on the exact number of cached copies. Rather, symbolic states only need to keep track of whether the caches have 0, 1, or multiple copies. The resulting symbolic state expansion process only takes a few steps and verifies the protocol for any system size. Therefore, it is more efficient and reliable than current approaches. The verification procedure is first applied to the verification of five existing protocols under the assumption of atomic protocol transitions. A simple snooping protocol on a split-transaction shared bus is also verified to illustrate the extension of our approach to protocols with nonatomic transitions     

Task structures as a basis for modeling knowledge-based systems

Recently, there has been an increasing interest in improving the reliability and quality of AI systems. As a result, a number of approaches to knowledge-based systems modeling have been proposed. However, these approaches are limited in formally verifying the intended functionality and behavior of a knowledge-based system. In this article, we proposed a formal treatment to task structures to formally specify and verify knowledge-based systems modeled using these structures. The specification of a knowledge-based system modeled using task structures has two components: a model specification that describes static properties of the system, and a process specification that characterizes dynamic properties of the system. The static properties of a system are described by two models: a model about domain objects (domain model), and a model about the problem-solving states (state model). The dynamic properties of the system are characterized by (1) using the notion of state transition to explicitly describe what the functionality of a task is, and (2) specifying the sequence of tasks and interactions between tasks (i.e., behavior of a system) using task state expressions (TSE). The task structure extended with the proposed formalism not only provides a basis for detailed functional decomposition with procedure abstraction embedded in, but also facilitates the verification of the intended functionality and behavior of a knowledge-based system. © 1997 John Wiley & Sons, Inc.     

Exact Acceleration of Real-Time Model Checking

Different time scales do often occur in real-time systems, e.g., a polling real-time system samples the environment many times per second, whereas the environment may only change a few times per second. When these systems are modeled as (networks of) timed automata, the validation using symbolic model checking techniques can significantly be slowed down by unnecessary fragmentation of the symbolic state space. This paper introduces a syntactical adjustment to a subset of timed automata that addresses this fragmentation problem and that can speed-up forward symbolic reachability analysis in a significant way. We prove that this syntactical adjustment does not alter reachability properties and that it indeed is effective. We illustrate our exact acceleration technique with run-time data obtained with the model checkers Uppaal and Kronos. Moreover, we demonstrate that automated application of our exact acceleration technique can significantly speed-up the verification of the run-time behavior of LEGO Mindstorms programs.     

LORETO: a tool for reducing state explosion in verification of LOTOS programs

LOTOS is a formal specification language for concurrent and distributed systems. Basic LOTOS is the version of LOTOS without value‐passing. A widely used approach to the verification of temporal properties is model checking. Often, in this approach the formal specification is translated into a labeled transition system on which formulae expressing properties are checked. A problem with this verification technique is state explosion: concurrent systems are often represented by automata with a prohibitive number of states. In this paper we show how, given a set ρ of actions, it is possible to automatically obtain for a Basic LOTOS program a reduced transition system to which only the arcs labeled by actions in ρ belong. The set ρ of actions plays a fundamental role in conjunction with a temporal logic defined by the authors in a previous paper: selective mu‐calculus. The reduced system with respect to ρ preserves the truth value of all selective mu‐calculus formulae with actions from the set ρ. We act at both syntactic and semantic levels. From a syntactic point of view, we define a set of transformation rules obtaining a smaller program. On the semantic side, we define a non‐standard semantics which dynamically reduces the transition system during generation. We present a tool implementing both the syntactic and the semantic reduction. Copyright © 1999 John Wiley & Sons, Ltd.     

Counting Paths: Nondeterminism as Linear Algebra

Nondeterminism is considered to be ignorance about the actual state transition sequence performed during a computation. The number of distinct potential paths from state i to j forms a matrix [nij]. The behavior of a nondeterministic program is defined to be this multiplicity matrix of the state transitions. The standard programming constructs have behaviors defined in terms of the behaviors of their constituents using matrix addition and multiplication only. The spectral radius of the matrix assigned to an iterating component characterizes its convergence. The spectral radius is shown to be either 0 or else ? 1. The program converges iff the spectral radius is zero, diverges deterministically iff the spectral radius is one, and has a proper nondeterministic divergence iff the spectral radius exceeds one. If the machine has an infinite number of states the characterization of convergence is given graph theoretically. The spectral radii of synchronous and interleaved parallel noncommunicating systems are easily computed in terms of the spectral radii of the components.     

Using heuristic search for finding deadlocks in concurrent systems

Model checking is a formal technique for proving the correctness of a system with respect to a desired behavior. This is accomplished by checking whether a structure representing the system (typically a labeled transition system) satisfies a temporal logic formula describing the expected behavior. Model checking has a number of advantages over traditional approaches that are based on simulation and testing: it is completely automatic and when the verification fails it returns a counterexample that can be used to pinpoint the source of the error. Nevertheless, model checking techniques often fail because of the state explosion problem: transition systems grow exponentially with the number of components. The aim of this paper is to attack the state explosion problem that may arise when looking for deadlocks in concurrent systems described through the calculus of communicating systems. We propose to use heuristics-based techniques, namely the A* algorithm, both to guide the search without constructing the complete transition system, and to provide minimal counterexamples. We have realized a prototype tool to evaluate the methodology. Experiments we have conducted on processes of different size show the benefit from using our technique against building the whole state space, or applying some other methods.     

Deductive Model Checking

We present an extension of classical tableau-based model checking procedures to the case of infinite-state systems, using deductive methods in an incremental construction of the behavior graph. Logical formulas are used to represent infinite sets of states in an abstraction of this graph, which is repeatedly refined in the search for a counterexample computation, ruling out large portions of the graph before they are expanded to the state-level. This can lead to large savings, even in the case of finite-state systems. Only local conditions need to be checked at each step, and previously proven properties can be used to further constrain the search. Although the resulting method is not always automatic, it provides a flexible, general and complete framework that can integrate a diverse number of other verification tools.     

State space reduction by non-standard semantics for deadlock analysis

In recent years many techniques have been developed for automatically verifying concurrent systems and most of them are based on the representation of the concurrent system by means of a transition system. State explosion is one of the most serious problems of this approach: often the prohibitive number of states renders the verification inefficient and, in some cases, impossible.

We propose a method for reducing the state space of the transition system corresponding to a CCS process that suites deadlock analysis. The reduced transition system is generated by means of a non-standard operational semantics containing a set of rules which are, in some sense, an abstraction, preserving deadlock freeness, of the inference rules of the standard semantics. Our method does not build the standard transition system, but directly generates an abstract system with a fewer number of states, so saving memory space. We characterize a class of processes whose abstract transition system is not exponential in the number of parallel components.     

Syntactic reductions for efficient deadlock analysis

A well‐known problem in the verification of concurrent systems based on model checking is state explosion: concurrent systems are often represented by automata with a prohibitive number of states. A reduction technique to reduce state explosion in deadlock checking is presented. The method is based on an automatic syntactic simplification of a calculus of communicating systems (CCS) specification, which keeps the parts of the program structure that may lead to a deadlock and deletes the other parts. Copyright © 2002 John Wiley & Sons, Ltd.     

Termination of nondeterministic quantum programs

We define a language-independent model of nondeterministic quantum programs in which a quantum program consists of a finite set of quantum processes. These processes are represented by quantum Markov chains over the common state space, which formalize the quantum mechanical behaviors of the machine. An execution of a nondeterministic quantum program is modeled by a sequence of actions of individual processes, and at each step of an execution a process is chosen nondeterministically to perform the next action. This execution model formalize the users’ behavior of calling the processes in the classical world. Applying the model to a quantum walk as an instance of physically realizable systems, we describe an execution step by step. A characterization of reachable space and a characterization of diverging states of a nondeterministic quantum program are presented. We establish a zero-one law for termination probability of the states in the reachable space. A combination of these results leads to a necessary and sufficient condition for termination of nondeterministic quantum programs. Based on this condition, an algorithm is found for checking termination of nondeterministic quantum programs within a fixed finite-dimensional state space.     

基于约束依赖图的并发程序模型检测工具

模型检测是一种基于状态空间搜索的自动化验证方法,可以有效地提升程序的质量.然而,由于并发程序中线程调度的不确定性以及数据同步的复杂性,对该类程序验证时存在更为严重的状态空间爆炸问题.目前,大多采用基于独立性分析的偏序约简技术缩小并发程序探索空间.针对粗糙的独立性分析会显著增加需探索的等价类路径问题,开发了一款可细化线程迁移依赖性分析的并发程序模型检测工具CDG4CPV.首先,构造了待验证可达性性质对应的规约自动机;随后,根据线程迁移边的类型和共享变量访问信息构建约束依赖图;最后,利用约束依赖图剪裁控制流图在展开过程中的独立可执行分支.在SV-COMP 2022竞赛的并发程序数据集上进行了对比实验,并对工具的效率进行比较分析.实验结果表明,该工具可以有效地提升并发程序模型检测的效率.特别是,与基于BDD的程序分析算法相比,该工具可使探索状态数目平均减少91.38%,使时间和空间开销分别平均降低86.25%和69.80%.     

An approximation algorithm for box abstraction of transition systems on real state spaces

Predicate abstraction is a powerful technique for extracting finite-state models from infinite-state systems such as computer software, and is applied to verification of safety properties. Predicate abstraction is also applied to verification of dynamical systems on real state spaces such as hybrid dynamical systems. In this paper, we propose a fast algorithm for computing entire abstract state spaces of transition systems on real state spaces. The method is based on the box abstraction of state spaces, and requires a relatively smaller number of reachability checks and Boolean operations. We also propose a fast method for computing the set of boxes that intersect a given convex polyhedron. This computation is a part of the proposed state-space generation algorithm. Effectiveness of the algorithm is evaluated by the computation time and by the difference of the approximated state space from the exact state space.     

Verification of infinite-state dynamic systems using approximatequotient transition systems

This paper deals with computational methods for verifying properties of labeled infinite-state transition systems using quotient transition system (QTS). A QTS is a conservative approximation to the infinite-state transition system based on a finite partition of the infinite state space. For universal specifications, positive verification for a QTS implies the specification is true for the infinite-state transition system. We introduce the approximate QTS or AQTS. The paper presents a sufficient condition for an AQTS to be a bisimulation of the infinite state transition system. An AQTS bisimulation is essentially equivalent to the infinite-state system for the purposes of verification. It is well known, however, that finite-state bisimulations do not exist for most hybrid systems of practical interest. Therefore, the use of the AQTS for verification of universal specifications is proposed and illustrated with an example. This approach has been implemented in a tool for computer-aided verification of a general class of hybrid systems     

Safety property verification using sequential SAT and bounded model checking

Model checkers verify properties of safety- or business-critical systems. The main idea behind model checking is to convert a design's verification into a problem of checking key design properties expressed as a set of temporal logic formulas. The graph representing the design's state space then becomes the basis for testing these formulas' satisfiability (SAT). This divide-and-conquer approach provides an overall test for design correctness. We describe a method for checking safety properties using sequential SAT. SSAT can efficiently prove true properties by harnessing the power of bounded model checking (BMC) using SAT, but without the need for a pre-computed correctness threshold. Using a standard set of benchmarks, we conducted experiments to compare the runtime behavior of SSAT with BMC and binary decision diagrams (BDDs).     

An object-oriented implementation of concurrent and hierarchical state machines

ContextState machine diagrams are a powerful means to describe the behavior of reactive systems. Unfortunately, the implementation of state machines is difficult, because state machine concepts, like states, events and transitions, are not directly supported in commonly used programming languages. Most of the implementation approaches known so far have one or more serious drawbacks: they are difficult to understand and maintain, lack in performance, depend on the properties of a specific programming language or do not implement the more advanced state machine features like hierarchy, concurrency or history.ObjectiveThis paper proposes and examines an approach to implement state machines, where both states and events are objects. Because the reaction of the state machine depends on two objects (state and event), a method known as double-dispatch is used to invoke the transition between the states. The aim of this work is to explore this approach in detail.MethodTo prove the usefulness of the proposed approach, an example was implemented with the proposed approach as well as with other commonly known approaches. The implementation strategies are then compared with each other with respect to run-time, code size, maintainability and portability.ResultsThe presented approach executes fast but needs slightly more memory than other approaches. It supports hierarchy, concurrency and history, is human authorable, easy to understand and easy to modify. Because of its pure object-oriented nature depending only on inheritance and late binding, it is extensible and can be implemented with a wide variety of programming languages.ConclusionThe results show that the presented approach is a useful way to implement state machines, even on small micro-controllers.