Modern cars require powerful multi- and manycore hardware platforms to fulfill the demands of upcoming computationally intensive advanced driver assistance systems. This leads to a distributed hardware/software architecture that poses an unbearable system complexity to designers. Additionally, the strict requirements of new functional safety standards make it extremely difficult to rapidly and comprehensively close the development-evaluation-debug cycle. To overcome these complications, virtual platform technology is a promising approach that provides full hardware/software visibility, controllability and adequate simulation speed at electronic system level. However, for highly heterogeneous systems, such as modern cars, this technology lacks the capability to capture and integrate interactions of multiple subsystems beyond the hardware/software domain. To bridge this gap, this work presents multiple methods to facilitate the integration of virtual platforms into complex heterogeneous multi-domain vehicular simulation systems via the Functional Mock-Up Interface (FMI), the de facto co-simulation standard for automotive. The presented approaches significantly increase the depth of functional safety testing, as holistic car simulation covers cross-domain interactions of its subsystems.

This paper describes a method to generate a computational model for formal verification of hardware-dependent software in embedded systems. The computational model of the combined HW/SW system is a program netlist (PN) consisting of instruction cells connected in a directed acyclic graph that compactly represents all execution paths of the software. The model can be easily integrated into SAT-based verification environments such as those based on Bounded Model Checking (BMC). The proposed construction of the model, however, allows for an efficient reasoning of the SAT solver over entire execution paths. We demonstrate the efficiency of our approach by presenting experimental results from the formal verification of an industrial LIN (Local Interconnect Network) bus node, implemented as a software driver on a 32-bit RISC machine.

In formal verification, proof logging is a technique for automatically reviewing the reasoning steps of a proof engine by a separate tool. This is useful for enhancing the confidence in the prover's result, especially in the case of a positive answer when no counterexample exists. Mature proof logging techniques exist for single-theory provers. SMT solvers, however, combine several theories so that developing an unified proof logging technique is more challenging. This paper proposes an approach for logging the proofs of the SMT solver STABLE which is a prover combining SAT and computer algebra engines. We show how to translate the SAT proofs into algebraic forms (polynomials) and how to check the combined Boolean and word-level proofs using a separate computer algebra engine.

A new methodology for formal system verification of System-on-Chip (SoC) designs is proposed. It does not only ensure correctness of the system-level models but also of the concrete implementation at the Register-Transfer-Level (RTL). For each SoC module at the RTL an abstract description is obtained by path predicate abstraction. Since this leads to time-abstract system models the main challenge is to deal with the concurrency between the individual RTL components. We propose a compositional scheme describing the communication between SoC modules independently of their individual processing speed. The composed abstract system is modeled as an asynchronous composition and can be verified using the SPIN model checker. We demonstrate the practical feasibility of our approach by a comprehensive case study based on Infineon's FPI Bus.

Ensuring functional correctness of hardware and software is a bottleneck in every design process of Embedded Systems. This paper proposes an approach to formally verify low-level software in conjunction with the hardware. The proposed approach is based on Interval Property Checking (IPC) that has proved successful on large industrial hardware designs. In this paper, IPC is extended by a specific abstraction technique that makes it tractable for hardware/software co-verification on realistic industrial designs. In the proposed methodology sets of finite state sequences of the system are abstracted by interval properties. This allows us to handle long sequences of state transitions in the hardware as they occur when running programs. We demonstrate the feasibility of our approach using the example of an industrial LIN software running on a public domain microprocessor platform.

This paper presents a new SMT solver, STABLE, for formulas of the quantifier-free logic over fixed-sized bit vectors (QF-BV). The heart of STABLE is a computer-algebra-based engine which provides algorithms for simplifying arithmetic problems of an SMT instance prior to bit-blasting. As the primary application domain for STABLE we target an SMT-based property checking flow for System-on-Chip (SoC) designs. When verifying industrial data path modules we frequently encounter custom-designed arithmetic components specified at the logic level of the hardware description language being used. This results in SMT problems where arithmetic parts may include non-arithmetic constraints. STABLE includes a new technique for extracting arithmetic bit-level information for these non-arithmetic constraints. Thus, our algebraic engine can solve subproblems related to the entire arithmetic design component. STABLE was successfully evaluated in comparison with other state-of-the-art SMT solvers on a large collection of SMT formulas describing verification problems of industrial data path designs that include multiplication. In contrast to the other solvers STABLE was able to solve instances with bit-widths of up to 64 bits.

This paper proposes enhancements to SAT-based property checking with the goal to increase the spectrum of applications where a proof of unbounded validity of a safety property can be provided. For this purpose, invariants are computed by reachability analysis on an abstract model. The main idea of the paper consists in a BDD-based analysis of k-step-induction on the abstract model and its use to guide a step-wise refinement process of the initial abstraction. The property is then proven on a bounded model of the original design using the computed invariant. The new approach has been applied to formally verify industrial SoC modules. In our experiments, we consider particularly difficult verification tasks occurring in the context of protocol compliance verification using generic, transaction-style verification IPs. In our experiments, numerous properties are proven which either required substantial manual interaction in previous approaches, or cannot be proven at all by other methods available to us.

In this paper we describe a practical methodology to formally verify highly optimized, industrial multipliers. We define a multiplier description language which abstracts from low-level optimizations and which can model a wide range of common implementations at a structural and arithmetic level. The correctness of the created model is established by bit level transformations matching the model against a standard multiplication specification. The model is also translated into a gate netlist to be compared with the full-custom implementation of the multiplier by standard equivalence checking. The advantage of this approach is that we use a high level language to provide the correlation between structure and bit level arithmetic. This compares favorably with other approaches that have to spend considerable effort on extracting this information from highly optimized implementations. Our approach is easily portable and proved applicable to a wide variety of state-of-the-art industrial designs.

Arithmetic bit-level (ABL) normalization has been proven a viable approach to formal property checking of datapath designs. It is applicable where arithmetic components and sub-components can be identified at the register-transfer (RT) level of the design and the property. This paper extends the applicability of ABL normalization to cases where some of the arithmetic components are custom-designed entities, e.g., specified using Boolean equations or gates. We transform these entities into ABL building blocks using Reed-Muller expressions as an intermediate representation. We show how Boolean logic expressed in Reed-Muller form can be automatically transformed into ABL components so that such logic blocks can be treated together with the remaining ABL components in a subsequent normalization run. The approach is evaluated on a number of industrial designs generated by a commercial arithmetic module generator.

We propose a methodology to formally prove protocol compliance for communication blocks in System-on-Chip (SoC) designs. In this methodology, a set of operational properties is specified with respect to the states of a central finite state machine (FSM). This central FSM is called main FSM and controls the overall behavior of the design. In order to prove a set of compliance properties, we developed an approach that combines property checking on a bounded circuit model with an approximate reachability analysis. The property checker determines whether a property is valid for an arbitrary state of the design regardless of its reachability. In order to avoid false negatives, reachability constraints are added to the property, which are generated by an approximate FSM traversal algorithm. We show how the existence of a main FSM can be exploited systematically in the reachability analysis and how to partition both the transition relation and the state space such that the computational complexity is reduced drastically. This makes formal verification of protocol compliance tractable even for large designs with several thousand state variables. Our approach has been applied successfully to verify several industrial designs.

We propose a normalization technique for verifying arithmetic circuits in a bounded model-checking environment. Our technique operates on the arithmetic bit-level (ABL) description of the arithmetic circuit parts and property. The ABL description can easily be provided by the front-end of a register transfer level property checker. The proposed normalization greatly simplifies the SAT instances to be solved for arithmetic circuit verification. Our approach has been successfully applied to verify the integer pipeline of an industrial microprocessor with advanced DSP capabilities.

We propose a normalization technique for verifying arithmetic circuits in a bounded model checking environment. Our technique operates on the arithmetic bit level (ABL) description of the arithmetic circuit parts and the property. The ABL description can easily be provided by the front-end of an RTL property checker. The proposed normalization greatly simplifies the SAT instances to be solved for arithmetic circuit verification. Our approach has been applied successfully to verify the integer pipeline of an industrial microprocessor with advanced DSP capabilities.

In bounded model checking (BMC)-based verification flows lack of reachability constraints often leads to false negatives. At present, it is daily practice of a verification engineer to identify the missing reachability constraints by manually inspecting the design code and by analyzing counterexamples. This, unfortunately, requires a lot of effort and is prone to errors. We propose an algorithm to determine reachability constraints automatically. The proposed approach applies to a design style where the operation of the design is controlled by a main FSM which can easily be extracted from the RTL description of the circuit. The algorithm decomposes and analyzes the state space of the circuit by considering transitions of the main FSM. Experimental results show that the proposed method can considerably reduce the manual work of verification engineers.

We propose a new arithmetic reasoning calculus to speed up a SAT solver based on the Davis Putnam Longman Loveland (DPLL) procedure. It is based on an arithmetic bit level description of the arithmetic circuit parts and the property. This description can easily be provided by the front-end of an RTL property checker. The calculus yields significant speedup and more robustness on hard SAT instances derived from the formal verification of arithmetic circuits.

This paper discusses a "structural" technique for traversing the state space of a finite state machine (FSM) and its application to equivalence checking of sequential circuits. The key ingredient to a state-space traversal is a data structure to represent state sets. In structural FSM, traversal-state sets are represented noncanonically and implicitly as gate netlists. First, we present an exact algorithm, which is based on an iterative expansion of the FSM into time frames and a network-decomposition procedure serving the same purpose as an existential quantification operation. Then, we discuss approximative algorithms for the application of structural FSM traversal to sequential equivalence checking. We theoretically analyze the properties of the exact as well as the approximative algorithms. Finally, we give details on the implementation of a sequential equivalence checker and present experimental results that demonstrate the effectiveness of the proposed approach for equivalence checking of optimized and retimed circuits.