Scalable reachability analysis via automated dynamic netlist-based hint generation

While SAT-based algorithms have largely displaced BDD-based verification techniques due to their typically higher scalability, there are classes of problems for which BDD-based reachability analysis is the only existing method for an automated solution. Nonetheless, reachability engines require a high degree of tuning to perform well on challenging benchmarks. In addition to clever partitioning and scheduling techniques, the use of hints has been proposed to decompose an otherwise breadth-first fixedpoint computation into a series of underapproximate computations, requiring a larger number of (pre-)image iterations though often significantly reducing peak BDD size and thus resource requirements. In this paper, we introduce a novel approach to boost the scalability of reachability computation: automated netlist-based hint generation. Experiments confirm that this approach can yield significant resource reductions; often over an order of magnitude on complex problems compared to reachability analysis without hints, and even compared to SAT-based proof techniques.     

Dynamic and Formal Verification of Embedded Systems: A Comparative Survey

Embedded Systems, by their nature, constitute a meeting point for communities with extremely different background. In particular, the high demands for quality and reliability for embedded systems have led to complementary quality assurance efforts: hardware engineers have developed techniques for dynamic verification in terms of co-simulation, which, in particular, addresses the different nature of hardware and software components. Thus these techniques are tailored for the transactional level, which comprises dedicated models for the hardware and the software parts. On the other hand, there is a bulk of work on formal verification techniques, which typically address higher levels of abstraction. These techniques are exhaustive in the sense that they cover all the infinite possible paths of their models, however at the price of neglecting many of the low-level aspects treated by co-simulation. It is the goal of this paper to increase the mutual understanding between these communities and to animate research at this exciting borderline.     

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.     

Automated assumption generation for compositional verification

We describe a method for computing a minimum-state automaton to act as an intermediate assertion in assume-guarantee reasoning, using a sampling approach and a Boolean satisfiability solver. For a set of synthetic benchmarks intended to mimic common situations in hardware verification, this is shown to be significantly more effective than earlier approximate methods based on Angluin’s L* algorithm. For many of these benchmarks, this method also outperforms BDD-based model checking and interpolation-based model checking. We also demonstrate how domain knowledge can be incorporated into our algorithm to improve its performance.     

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.     

基于软件的RFID系统设计仿真验证方法

为构建RFID技术研究及产品研发的测试环境,对RFID系统设计的验证测试技术与方法进行研究,提出了RFID系统映射建模仿真方法,开发了基于S／C模型与多线程的RFID系统设计的软硬件综合验证测试平台。     

Distributed Symbolic Bounded Property Checking

In this paper we describe an algorithm for distributed, BDD-based bounded property checking and its implementation in the verification tool SymC. The distributed algorithm verifies larger models and returns results faster than the sequential version.The core algorithm distributes partitions of the state set to computation nodes after reaching a threshold size. The nodes proceed with image computation on the nodes asynchronously. The main scalability problem of this scheme is the overlap of state set partitions. We present static and dynamic overlap reduction techniques.     

Bisimulation Minimization and Symbolic Model Checking

State space minimization techniques are crucial for combating state explosion. A variety of explicit-state verification tools use bisimulation minimization to check equivalence between systems, to minimize components before composition, or to reduce a state space prior to model checking. Experimental results on bisimulation minimization in symbolic model checking contexts, however, are mixed. This paper explores bisimulation minimization as an optimization in symbolic model checking of invariance properties. We consider three bisimulation minimization algorithms. From each, we produce a BDD-based model checker for invariant properties and compare this model checker to a conventional one based on backwards reachability. Our comparisons, both theoretical and experimental, suggest that bisimulation minimization is not viable in the context of invariance verification, because performing the minimization requires as many, if not more, computational resources as model checking the unminimized system through backwards reachability.     

Verification and analysis of domain-specific models of physical characteristics in embedded control software

ContextA considerable portion of the software systems today are adopted in the embedded control domain. Embedded control software deals with controlling a physical system, and as such models of physical characteristics become part of the embedded control software.ObjectiveDue to the evolution of system properties and increasing complexity, faults can be left undetected in these models of physical characteristics. Therefore, their accuracy must be verified at runtime. Traditional runtime verification techniques that are based on states/events in software execution are inadequate in this case. The behavior suggested by models of physical characteristics cannot be mapped to behavioral properties of software. Moreover, implementation in a general-purpose programming language makes these models hard to locate and verify. Therefore, this paper proposes a novel approach to perform runtime verification of models of physical characteristics in embedded control software.MethodThe development of an approach for runtime verification of models of physical characteristics and the application of the approach to two industrial case studies from the printing systems domain.ResultsThis paper presents a novel approach to specify models of physical characteristics using a domain-specific language, to define monitors that detect inconsistencies by exploiting redundancy in these models, and to realize these monitors using an aspect-oriented approach. We complement runtime verification with static analysis to verify the composition of domain-specific models with the control software written in a general-purpose language.ConclusionsThe presented approach enables runtime verification of implemented models of physical characteristics to detect inconsistencies in these models, as well as broken hardware components and wear and tear of hardware in the physical system. The application of declarative aspect-oriented techniques to realize runtime verification monitors increases modularity and provides the ability to statically verify this realization. The complementary static and runtime verification techniques increase the reliability of embedded control software.     

Are BDDs still alive within sequential verification?

This work proposes a fully BDD-based approach based on: mixing forward and backward traversals, dovetailing approximate and exact methods, adopting guided and partitioned searches, and using conjunctive decompositions and generalized-cofactor-based BDD simplifications. The method is exact, i.e., it does not produce false negatives or positives, and reaps relevant performance enhancements from an appropriate tradeoff among the component methodologies.The resulting verification strategy is able, on one hand, to improve standard BDD-based algorithms, and, on the other hand, to compete with SAT-based tools on a broader range of circuit sizes.We experimentally compare our approach with three state-of-the-art freely available techniques. The first and second ones are SAT-based strategies, i.e., bounded model checking implemented within the NuSMV and the VIS tools (using Chaff as SAT engine). The third one is a BDD-based methodology, i.e., approximate reachability dont cares model checking implemented within the VIS tool. Results show interesting improvements in terms of both efficiency and power. They demonstrate how BDDs are able to accomplish larger verification tasks and to efficiently deal with high sequential depths.     

Haifa verification conference 2007

This special section contains a selection of contributions originally presented at the Third Haifa Verification Conference (HVC’07). The scope of this conference covers all types of verification of both hardware and software systems. While there is widespread agreement on the importance of verification, it is clear that different systems require different approaches. Several distinct fields of research have developed, devoted to either software or hardware, or to a particular verification approach such as formal or testing/simulation. Each of these paradigms has an extensive publication history and its own dedicated conference. Yet there is much to be gained from sharing knowledge and experience. HVC’s goal is to serve as a venue for researchers from all fields of verification, enabling them to exchange ideas and learn from one another. It is our hope that by gathering these experts together in one conference, we are fostering the emergence of new trends that combine ideas and insights from different domains.     

Formal verification of hardware correctness: introduction andsurvey of current research

Formal verification techniques are analyzed, focusing on two key points: suitable representation systems and mechanizable proofs. Different approaches to hardware verification are first examined, and formal verification and automated synthesis are compared to show how they cooperate in producing zero-defect designs. The different techniques are evaluated. Cross fertilization with software verification techniques is discussed     

System-on-a-chip cosimulation and compilation

Complex consumer products with multiple functions on a single chip demand new design and verification methods for interfunctioning hardware and software components. The authors' new techniques address this need     

On software verification for sensor nodes

We consider software written for networked, wireless sensor nodes, and specialize software verification techniques for standard C programs in order to locate programming errors in sensor applications before the software's deployment on motes. Ensuring the reliability of sensor applications is challenging: low-level, interrupt-driven code runs without memory protection in dynamic environments. The difficulties lie with (i) being able to automatically extract standard C models out of the particular flavours of embedded C used in sensor programming solutions, and (ii) decreasing the resulting program's state space to a degree that allows practical verification times.We contribute a platform-dependent, OS-independent software verification tool for OS-wide programs written in MSP430 embedded C with asynchronous hardware interrupts. Our tool automatically translates the program into standard C by modelling the MCU's memory map and direct memory access. To emulate the existence of hardware interrupts, calls to hardware interrupt handlers are added, and their occurrence is minimized with a double strategy: a partial-order reduction technique, and a supplementary reachability check to reduce overapproximation. This decreases the program's state space, while preserving program semantics. Safety specifications are written as C assertions embedded in the code. The resulting sequential program is then passed to CBMC, a bounded software verifier for sequential ANSI C. Besides standard errors (e.g., out-of-bounds arrays, null-pointer dereferences), this tool chain is able to verify application-specific assertions, including low-level assertions upon the state of the registers and peripherals.Verification for wireless sensor network applications is an emerging field of research; thus, as a final note, we survey current research on the topic.     

Automatic synthesis and verification of real-time embedded software for mobile and ubiquitous systems

Currently available application frameworks that target the automatic design of real-time embedded software are poor in integrating functional and non-functional requirements for mobile and ubiquitous systems. In this work, we present the internal architecture and design flow of a newly proposed framework called Verifiable Embedded Real-Time Application Framework (VERTAF), which integrates three techniques namely software component-based reuse, formal synthesis, and formal verification. Component reuse is based on a formal unified modeling language (UML) real-time embedded object model. Formal synthesis employs quasi-static and quasi-dynamic scheduling with multi-layer portable efficient code generation, which can output either real-time operating systems (RTOS)-specific application code or automatically generated real-time executive with application code. Formal verification integrates a model checker kernel from state graph manipulators (SGM), by adapting it for embedded software. The proposed architecture for VERTAF is component-based which allows plug-and-play for the scheduler and the verifier. The architecture is also easily extensible because reusable hardware and software design components can be added. Application examples developed using VERTAF demonstrate significantly reduced relative design effort as compared to design without VERTAF, which also shows how high-level reuse of software components combined with automatic synthesis and verification increases design productivity.     

基于安全风险的RTL级硬件木马验证研究

信息时代使得信息安全变得日益重要。攻击方为了获取想要的信息,除了使用软件方面的手段,如病毒、蠕虫、软件木马等,也使用硬件手段来威胁设备、系统和数据的安全,如在芯片中植入硬件木马等。如果将硬件木马植入信息处理的核心--处理器,那将风险更高、危害更大。然而,硬件木马位于信息系统底层核心的层面,难以被检测和发现出来。硬件木马是国内外学术界研究的热点课题,尤其是在设计阶段结合源代码的硬件木马检测问题,是新问题,也是有实际需要的问题。在上述背景下,围绕源代码中硬件木马的检测和验证展开了研究。基于硬件木马危害结果属性,在学术上提出基于安全风险的模型和验证规则,给出相应的描述形式,从理论上说明安全验证规则在减少验证盲目性、缩小可疑代码范围、提高评估效率的作用,实验表明,基于安全风险规则的验证,可以避免验证的盲目性和测试空间向量膨胀的问题,有效验证疑似硬件木马的存在和危害,对源代码安全评估是有一定效果的。     

Object-oriented techniques in hardware design

We focus on using object-oriented techniques to improve the hardware design process. The advantages of these techniques for hardware design include: improved modifiability and maintainability of models; easy component instantiation with different parameters; quick composition of new components; the ability to identify and reuse common components; the ability to tailor general-purpose components to more specialized components; support of dynamic object creation and destruction; and the possibility of employing existing software synthesis and verification techniques. We illustrate the application of object-oriented techniques using a load-store, reduced instruction-set processor that contains a local memory. The instruction set consists of 22 instructions, which require one or two 16-bit words. Arithmetic is performed in two's complement. We use C++ to demonstrate the usefulness of object-oriented techniques, not to provide arguments for or against its use in hardware modeling and design     

基于软硬件协同形式验证的固件漏洞分析技术

为了系统高效地分析固件中潜在的安全隐患,提出了一种基于行为时序逻辑 TLA 的软硬件协同形式验证方法。通过对固件工作过程中的软硬件交互机制进行形式建模分析,在动态调整攻击模型的基础上,发现了固件更新过程中存在的安全漏洞,并通过实验证实了该漏洞的存在,从而证明了形式验证方法的可靠性。     

量子程序验证

量子硬件设计与制造技术的飞速发展使得人们开始预言大于一百个量子比特的特定用途的量子计算机有望在5-10年内实现.可以想见,到那时候,量子软件的开发将变成真正发挥这些计算机能力的关键.然而,由于量子信息的不可克隆性和纠缠的非局域作用等量子特征,如何设计正确高效的量子程序和量子通信协议将是一个富有挑战性的课题.形式化验证方法,特别是模型检测技术,已经在经典软件设计和系统建模方面被证明行之有效,因此量子软件的形式化验证也开始受到越来越多的关注.本文从量子顺序程序验证和量子通信协议验证两方面,对近年来国内外学者,特别是两位作者所在的研究组在该研究领域取得的一些成果进行了系统的总结.最后,对未来可能的研究方向和面临的挑战进行了简单展望.     

Copilot: monitoring embedded systems

Runtime verification (RV) is a natural fit for ultra-critical systems that require correct software behavior. Due to the low reliability of commodity hardware and the adversity of operational environments, it is common in ultra-critical systems to replicate processing units (and their hosted software) and incorporate fault-tolerant algorithms to compare the outputs, even if the software is considered to be fault-free. In this paper, we investigate the use of software monitoring in distributed fault-tolerant systems and the implementation of fault-tolerance mechanisms using RV techniques. We describe the Copilot language and compiler that generates monitors for distributed real-time systems, and we discuss two case-studies in which Copilot-generated monitors were used to detect onboard software and hardware faults and monitor air-ground data link messaging protocols.