Extended BDDs: Trading of canonicity for structure in verification algorithms

We present an extension to binary decision diagrams (BDDs) that exploits the information contained in the structure of a given circuit to produce a compact,semicanonical, representation. The resulting XBDDs (extended BDDs) retain many of the advantages of BDDs, while at the same time allowing one to deal with larger circuits.We propose algorithms for verification of combinational circuits based on XBDDs that overcome the exponential growth in the number of nodes in the BDDs for some specific circuits such as the multipliers. While the approach remains cpu-time intensive, we believe it is the first to exactly verify the most difficult (median) output of a 16-bit multiplier. Experimental results are presented to support our claim that the XBDD approach is the best for multiplier verification.     

Polynomial-Size Binary Decision Diagrams for the Exactly Half-<Emphasis Type="Italic">d</Emphasis>-Hyperclique Problem Reading Each Input Bit Twice

A binary decision diagram (BDD) is a graph-based data structure representing Boolean functions; ℓ-BDDs are BDDs with an additional restriction that each input bit can be tested at most ℓ times. A d-uniform hypergraph H on N vertices is an exactly half-d-hyperclique if N/2 of its vertices form a hyperclique and the remaining vertices are isolated. Wegener [J. ACM 35(2), 461–471 (1988)] conjectured that there is no polynomial-size (d−1)-BDD for the Exactly half-d-hyperclique problem. We refute this conjecture by constructing polynomial-size (syntactic) 2-BDDs for the Exactly half-d-hyperclique problem for every d≥2. Institute for Theoretical Computer Science (ITI) is supported by Ministry of Education of Czech Republic as projects LN00A056 and 1M0545.     

The Theory of Zero-Suppressed BDDs and the Number of Knight's Tours

Zero-suppressed binary decision diagrams (ZBDDs) have been introduced by Minato [14–17] who presents applications for cube set representations, fault simulation, timing analysis and the n-queens problem. Here the structural properties of ZBDDs are worked out and a generic synthesis algorithm is presented and analyzed. It is proved that ZBDDs can be at most by a factor n + 1 smaller or larger than ordered BDDs (OBDDs) for the same function on n variables. Using ZBDDs the best known upper bound on the number of knight's tours on an 8 × 8 chessboard is improved significantly.     

Using XBDDs and ZBDDs in points‐to analysis

Binary decision diagrams (BDDs) have recently become widely accepted as a space‐efficient method of representing relations in points‐to or reference analyses. When BDDs are used to represent relations, each element of a domain is assigned a bit pattern to represent it, but not every bit pattern represents an element. The circuit design, model checking, and verification communities have achieved significant reductions in BDD sizes using several techniques to reduce the overhead of these don't‐care bit patterns. We adapt these techniques to BDD‐based program analysis, and we study their effect on the BDD size in this context. Specifically, we compare the effectiveness of Coudert and Madre's restrict operation and the use of zero‐suppressed BDDs (ZBDDs) to represent relations. Using don't‐care BDDs (XBDDs) and ZBDDs to reduce the size of the relations allows a compiler or other software analysis tools to analyze larger programs with greater precision. Our experimental evaluation considers both context‐insensitive and context‐sensitive program analyses. We also provide a metric that can be used to estimate whether ZBDDs will be more compact than BDDs for a given analysis. Copyright © 2008 John Wiley & Sons, Ltd.     

Cultural algorithm for minimization of binary decision diagram and its application in crosstalk fault detection

The binary decision diagrams (BDDs) can give canonical representation to Boolean functions; they have wide applications in the design and verification of digital systems. A new method based on cultural algorithms for minimizing the size of BDDs is presented in this paper. First of all, the coding of an individual representing a BDDs is given, and the fitness of an individual is defined. The population is built by a set of the individuals. Second, the implementations based on cultural algorithms for the minimization of BDDs, i.e., the designs of belief space and population space, and the designs of acceptance function and influence function, are given in detail. Third, the fault detection approaches using BDDs for digital circuits are studied. A new method for the detection of crosstalk faults by using BDDs is presented. Experimental results on a number of digital circuits show that the BDDs with small number of nodes can be obtained by the method proposed in this paper, and all test vectors of a fault in digital circuits can also be produced.     

An Improved Hierarchy Result for Partitioned BDDs

One of the great challenges of complexity theory is the problem of analyzing the dependence of the complexity of Boolean functions on the resources nondeterminism and randomness. So far this problem could be solved only for very few models of computation. For so-called partitioned binary decision diagrams , which are a restricted variant of nondeterministic read-once branching programs, Bollig and Wegener have proven an astonishing hierarchy result which shows that the smallest possible decrease of the available amount of nondeterminism may incur an exponential blow-up of the branching program size. They have shown that k -partitioned BDDs which may nondeterministically choose between k alternative subprograms may be exponentially larger than (k+1) -partitioned BDDs for the same function if k = o(( log n / log log n) ^1/2 ) , where n is the input size. In this paper an improved hierarchy result is established which still works if the number of nondeterministic decisions is O((n/ log ^1+ε n) ^1/4 ) , where ε > 0 is an arbitrary small constant. Received November 25, 1999.     

Symbolic Protocol Verification with Queue BDDs

Symbolic verification based on Binary Decision Diagrams (BDDs) has proven to be a powerful technique for ensuring the correctness of digital hardware. In contrast, BDDs have not caught on as widely for software verification, partly because the data types used in software are more complicated than those used in hardware. In this work, we propose an extension of BDDs for dealing with dynamic data structures. Specifically, we focus on queues, since they are commonly used in modeling communication protocols. We introduce Queue BDDs (QBDDs), which include all the power of BDDs while also providing an efficient representation of queue contents. Experimental results show that QBDDs are well-suited for the verification of communication protocols.     

Generating BDDs for symbolic model checking in CCS

Summary Finite transition systems can easily be represented by binary decision diagrams (BDDs) through the characteristic function of the transition relation. Burch et al. have shown how model checking of a powerful version of the -calculus can be performed on such BDDs. In this paper we show how a BDD can be generated from elementary finite transition systems given as BDDs by applying the CCS operations of parallel composition, restriction, and relabelling. The resulting BDDs only grow linearly in the number of parallel components. This way bisimilarity checking can be performed for processes out of the reach of conventional process algebra tools. Reinhard Enders graduated from the Technical University in Munich with a Diploma in mathematics and computer science in 1978. From 1977 to 1984 he was employed by Siemens, working in computer linguistics and expert systems. From 1984 to 1988 he worked at ECRC on Prolog extensions. In Autmn 1988 he joined Siemens and is developping the constraint extension of a new Prolog product. Thomas Filkorn received the computer science degree and the Ph.D. degree, both from the Technical University of Munich. Since 1992 he works at Siemens' Corporate Research and Development on symbolic algorithms and methods for the verification of finite state systems. Dirk Taubner received his Ph.D. in informatics at the Technical University of Munich in 1988. He investigated which sublanguages of process algebra could be represented finitely by automata and Petri nets. From 1989 through 91 he worked at Siemens' Corporate Research and Development where he led a project on computer-aided verification of parallel processes. This paper presents part of the work of that project. Currently he works on commercial software engineering for a software consulting company.     

Modeling and simulation of circuits with shared structurally synthesized BDDs

Modeling and simulation are critical tools for the analysis of testability and verification of digital circuits. BDDs are a well-known model for manipulating Boolean functions. However, the traditional BDDs mainly address modeling the function of the digital circuits, and not the structural aspects that are important for testability analysis. We propose a new type of BDD in the form of Shared Structurally Synthesized BDD (S³BDD) for representing the structure and simulating the faults in digital circuits. The paper presents a method for synthesis of S³BDDs, offers a formula for calculating the minimal size of the model, and proposes a method for parallel pattern simulation with S³BDDs We demonstrate a considerable increase in the speed-up of simulation of digital circuits using S³BDDs.     

Probabilistic symbolic model checking with PRISM: a hybrid approach

In this paper we present efficient symbolic techniques for probabilistic model checking. These have been implemented in PRISM, a tool for the analysis of probabilistic models such as discrete-time Markov chains, continuous-time Markov chains and Markov decision processes using specifications in the probabilistic temporal logics PCTL and CSL. Motivated by the success of model checkers such as SMV which use BDDs (binary decision diagrams), we have developed an implementation of PCTL and CSL model checking based on MTBDDs (multi-terminal BDDs) and BDDs. Existing work in this direction has been hindered by the generally poor performance of MTBDD-based numerical computation, which is often substantially slower than explicit methods using sparse matrices. The focus of this paper is a novel hybrid technique which combines aspects of symbolic and explicit approaches to overcome these performance problems. For typical examples, we achieve a dramatic improvement over the purely symbolic approach. In addition, thanks to the compact model representation using MTBDDs, we can verify systems an order of magnitude larger than with sparse matrices, while almost matching or even beating them for speed.     

A Case for Compressing Traces with BDDs

Instruction-level traces are widely used for program and hardware analysis. However, program traces for just a few seconds of execution are enormous, up to several terabytes in size, uncompressed. Specialized compression can shrink traces to a few gigabytes, but trace analyzers typically stream the decompressed trace through the analysis engine. Thus, the complexity of analysis depends on the decompressed trace size (even though the decompressed trace is never stored to disk). This makes many global or interactive analyses infeasible. This paper presents a method to compress program traces using binary decision diagrams (BDDs). BDDs intrinsically support operations common to many desirable program analyses and these analyses operate directly on the BDD. Thus, they are often polynomial in the size of the compressed representation. The paper presents mechanisms to represent a variety of trace data using BDDs and shows that BDDs can store, in 1 GB of RAM, the entire data-dependence graph of traces with over 1 billion instructions. This allows rapid computation of global analyses such as heap-object liveness and dynamic slicing     

Efficient BDDs for bounded arithmetic constraints

Symbolic model checkers use BDDs to represent arithmetic constraints over bounded integer variables. The size of such BDDs can in the worst case be exponential in the number and size (in bits) of the integer variables. In this paper we show how to construct linear-sized BDDs for linear integer arithmetic constraints. We present basic constructions for atomic equality and inequality constraints and generalize our complexity results for arbitrary linear arithmetic formulas. We also present three alternative ways of handling out-of-bounds transitions and discuss heterogeneous bounds on integer variables. We experimentally compare our approach to other BDD-based symbolic model checkers and demonstrate that the algorithms presented in this paper can be used to improve their performance significantly.     

Free binary decision diagrams for the computation of EAR n

Free binary decision diagrams (FBDDs) are graph-based data structures representing Boolean functions with the constraint (additional to binary decision diagram) that each variable is tested at most once during the computation. The function EAR_n is the following Boolean function defined for n × n Boolean matrices: EAR_n(M) = 1 iff the matrix M contains two equal adjacent rows. We prove that each FBDD computing EAR_n has size at least and we present a construction of such diagrams of size approximately .     

Real Numbers and BDDs

We present a proposal for representing large vectors of real numbers using binary decision diagrams (BDDs). If the vectors contain structured data, the necessary size may be reduced significantly compared to an explicit representation of the numbers. We are able to prove a nontrivial upper bound for this size for a rather theoretical example: tables approximating linear functions.     

Exploiting interleaving semantics in symbolic state-space generation

Symbolic techniques based on Binary Decision Diagrams (BDDs) are widely employed for reasoning about temporal properties of hardware circuits and synchronous controllers. However, they often perform poorly when dealing with the huge state spaces underlying systems based on interleaving semantics, such as communications protocols and distributed software, which are composed of independently acting subsystems that communicate via shared events. This article shows that the efficiency of state-space exploration techniques using decision diagrams can be drastically improved by exploiting the interleaving semantics underlying many event-based and component-based system models. A new algorithm for symbolically generating state spaces is presented that (i) encodes a model’s state vectors with Multi–valued Decision Diagrams (MDDs) rather than flattening them into BDDs and (ii) partitions the model’s Kronecker–consistent next–state function by event and subsystem, thus enabling multiple lightweight next–state transformations rather than a single heavyweight one. Together, this paves the way for a novel iteration order, called saturation, which replaces the breadth–first search order of traditional algorithms. The resulting saturation algorithm is implemented in the tool SMART, and experimental studies show that it is often several orders of magnitude better in terms of time efficiency, final memory consumption, and peak memory consumption than existing symbolic algorithms.     

Partial-Order Reduction in Symbolic State-Space Exploration

State-space explosion is a fundamental obstacle in the formal verification of designs and protocols. Several techniques for combating this problem have emerged in the past few years, among which two are significant: partial-order reduction and symbolic state-space search. In asynchronous systems, interleavings of independent concurrent events are equivalent, and only a representative interleaving needs to be explored to verify local properties. Partial-order methods exploit this redundancy and visit only a subset of the reachable states. Symbolic techniques, on the other hand, capture the transition relation of a system and the set of reachable states as boolean functions. In many cases, these functions can be represented compactly using binary decision diagrams (BDDs). Traditionally, the two techniques have been practiced by two different schools—partial-order methods with enumerative depth-first search for the analysis of asynchronous network protocols, and symbolic breadth-first search for the analysis of synchronous hardware designs. We combine both approaches and develop a method for using partial-order reduction techniques in symbolic BDD-based invariant checking. We present theoretical results to prove the correctness of the method, and experimental results to demonstrate its efficacy.     

Zero-suppressed BDDs and their applications

In many real-life problems, we are often faced with manipulating sets of combinations. In this article, we study a special type of ordered binary decision diagram (OBDD), called zero-suppressed BDDs (ZBDDs). This data structure represents sets of combinations more efficiently than using original OBDDs. We discuss the basic data structures and algorithms for manipulating ZBDDs in contrast with the original OBDDs. We also present some practical applications of ZBDDs, such as solving combinatorial problems with unate cube set algebra, logic synthesis methods, Petri net processing, etc. We show that a ZBDD is a useful option in OBDD techniques, suitable for a part of the practical applications. Published online: 15 May 2001     

Binary Decision Diagrams and neural networks

This paper describes a neural network approach that gives an estimation method for the space complexity of Binary Decision Diagrams (BDDs). A model has been developed to predict the complexity of digital circuits. The formal core of the developed neural network model (NNM) is a unique matrix for the complexity estimation over a set of BDDs derived from Boolean logic expressions with a given number of variables and Sum of Products (SOP) terms. Experimental results show good correlation between the theoretical results and those predicted by the NNM, which will give insights to the complexity of Very Large Scale Integration (VLSI)/Computer Aided Design (CAD) designs. The proposed model is capable of predicting the maximum BDD complexity (MaxBC) and the number of product terms (NPT) in the Boolean function that corresponds to the minimum BDD complexity (MinBC). This model provides an alternative way to predict the complexity of digital VLSI circuits.

A rewriting approach to binary decision diagrams

Binary decision diagrams (BDDs) provide an established technique for propositional formula manipulation. In this paper, we present the basic BDD theory by means of standard rewriting techniques. Since a BDD is a DAG instead of a tree we need a notion of shared rewriting and develop appropriate theory. A rewriting system is presented by which canonical reduced ordered BDDs (ROBDDs) can be obtained and for which uniqueness of ROBDD representation is proved. Next, an alternative rewriting system is presented, suitable for actually computing ROBDDs from formulas. For this rewriting system a layerwise strategy is defined, and it is proved that when replacing the classical apply-algorithm by layerwise rewriting, roughly the same complexity bound is reached as in the classical algorithm. Moreover, a layerwise innermost strategy is defined and it is proved that the full classical algorithm for computing ROBDDs can be replaced by layerwise innermost rewriting without essentially affecting the complexity. Finally a lazy strategy is proposed sometimes performing much better than the traditional algorithm.     

Memory optimization in function and set manipulation with BDDs

Binary Decision Diagrams (BDDs) are the state-of-the-art technique for many synthesis, verification and testing problems in CAD for VLSI. Many researchers proposed optimized BDD—based representations, but in many complex applications the (working) memory required is still too much. Virtual memory is no alternative solution, because if the working set size for a program is large and memory accesses are random, an extremely large number of page faults significantly modifies the performance of the software. This paper proposes a solution to this problem for a specific application, namely BDD—based exploration of large state spaces, an issue often found in CAD for VLSI. Our ‘divide—and—conquer’ approach for reachability analysis is based on decomposition of state sets carried out at different levels and on an effective use of mass memory. As a result, we are able to explore the state space of large Finite State Machines. At the same time, the technique we develop is orthogonal to a variety of symbolic techniques and graph manipulation procedures and it allows reducing complexity of very common operations. Experimental results, on well known synchronous benchmarks usually used in the field of CAD for VLSI, show that this approach is particularly effective on larger problems as decomposition decreases the amount of working memory, avoids page faulting and makes the overall process more efficient. © 1998 John Wiley & Sons, Ltd.