Software Model Checking: The VeriSoft Approach

Verification by state-space exploration, also often referred to as model checking, is an effective method for analyzing the correctness of concurrent reactive systems (for instance, communication protocols). Unfortunately, traditional model checking is restricted to the verification of properties of models, i.e., abstractions, of concurrent systems.We discuss in this paper how model checking can be extended to analyze arbitrary software, such as implementations of communication protocols written in programming languages like C or C++. We then introduce a search technique that is suitable for exploring the state spaces of such systems. This algorithm has been implemented in VeriSoft, a tool for systematically exploring the state spaces of systems composed of several concurrent processes executing arbitrary code.During the past five years, VeriSoft has been applied successfully for analyzing several software products developed in Lucent Technologies, and has also been licensed to hundreds of users in industry and academia. We discuss applications, strengths and limitations of VeriSoft, and compare it to other approaches to software model checking, analysis and testing.     

Symbolic Model Checking of Software

Model checking is a popular formal verification technique for both software and hardware. The verification of concurrent software predominantly employs explicit-state model checkers, such as SPIN, that use partial-order reduction as a main technique to deal with large state spaces efficiently. In the hardware domain, the introduction of symbolic model checking has been considered a breakthrough, allowing the verification of systems clearly out-of-reach of any explicit-state model checker.This paper introduces ImProviso, a new algorithm for model checking of software that efficiently combines the advantages of partial-order reduction with symbolic exploration. IMPROVISO uses implicit BDD representations for both the state space and the transition relation together with a new implicit in-stack proviso for efficient partial-order reduction. The new approach is inspired by the Twophase partial-order reduction algorithm for explicit-state model checking.Initial experimental results show that the proposed algorithm improves the existing symbolic model checking approach and can be used to tackle problems that are not tractable using explicit-state methods.     

Transactions for Software Model Checking

This paper presents a software model checking algorithm that combats state explosion by decomposing each thread's execution into a sequence of transactions that execute atomically. Our algorithm infers transactions using the theory of reduction, and supports both left and right movers, thus yielding larger transactions and fewer context switches than previous methods. Our approach uses access predicates to support a wide variety of synchronization mechanisms. In addition, we automatically infer these predicates for programs that use lock-based synchronization.     

Parallel Assignments in Software Model Checking

In this paper we investigate how formal software verification systems can be improved by utilising parallel assignment in weakest precondition computations.We begin with an introduction to modern software verification systems. Specifically, we review the method in which software abstractions are built using counterexample-guided abstraction refinement (CEGAR). The classical NP-complete parallel assignment problem is first posed, and then an additional restriction is added to create a special case in which the problem is tractable with an O(n²) algorithm. The parallel assignment problem is then discussed in the context of weakest precondition computations. In this special situation where statements can be assumed to execute truly concurrently, we show that any sequence of simple assignment statements without function calls can be transformed into an equivalent parallel assignment block.Results of compressing assignment statements into a parallel form with this algorithm are presented for a wide variety of software applications. The proposed algorithms were implemented in the ComFoRT reasoning framework [J. Ivers and N. Sharygina. Overview of ComFoRT: A model checking reasoning framework. Technical Report CMU/SEI-2004-TN-018, Carnegie Mellon Software Engineering Institute, 2004] and used to measure the improvement in the verification of real software systems. This improvement in time proved to be significant for many classes of software.     

一种基于模型检查的嵌入式软件验证方法

嵌入式软件广泛应用于不同领域,如消费电子、工业控制、汽车电子、移动通信等。嵌入式软件的可靠性保证十分关键。嵌入式软件中常见的错误包括状态机错误、时序错误、栈溢出／存储溢出等,在开发过程中对嵌入式软件进行验证十分重要。     

Interface Grammars for Modular Software Model Checking

Verification techniques relying on state enumeration (e.g., model checking) face two important challenges: the state-space explosion, an exponential increase in the state space as the number of components increases; and environment generation, modeling components that are either not available for analysis, or that cannot be handled by the verification tool in use. We propose a semi-automated approach for attacking these problems. In our approach, interfaces for the components not under analysis are specified using a specification language based on grammars. Specifically, an interface grammar for a component specifies the sequences of method invocations that are allowed by that component. We have built an compiler that takes the interface grammar for a component as input and generates a stub for that component. The stub thus generated can be used to replace that component during state space exploration, either to moderate state space explosion, or to provide an executable environment for the component under verification. We conducted a case study by writing an interface grammar for the Enterprise JavaBeans (EJB) persistence interface, and using the resulting stub to check EJB clients using the JPF model checker. Our results show that EJB clients can be verified efficiently with JPF using our approach.     

模型检测在软件测试中的应用

随着计算机软硬件系统日益复杂,如何保证其正确性和可靠性成为日益紧迫的问题。在为此提出的诸多理论和方法中,模型检测（model checking）以其简洁明了和自动化程度高而引人注目。具体介绍了模型检测的一些理论,同时将它应用于具体的软件程序,运用模型检测方法对软件进行测试。从而证明了模型检测方法与测试结合对于软件可靠性和正确性所起的巨大作用。     

Space-Reduction Strategies for Model Checking Dynamic Software

Effective model-checking of modern object-oriented software systems requires providing support for program features such as dynamically created threads, heap-allocated objects and garbage collection. These features have often proven problematic to treat using many previous model-checking frameworks that do not provide sophisticated heap representations and optimizations.In this paper, we define a flexible framework for combined heap and thread symmetry reductions in explicit-state model checking that can be tuned to trade run-time overhead for precision. In addition, we describe various strategies for duplication-reducing state-space encodings for object-oriented heap structures. We have implemented these techniques in Bogor (our extensible software model-checking framework), and we present empirical data to support the effectiveness of these memory reductions on a collection of realistic examples and to demonstrate that they improve upon previous approaches. These techniques, formalized in a group theoretic framework, can be applied to any non-deterministic heap object diagram.     

Preface of the special issue on Model Checking of Software

Software Model Checking consists of a broad collection of techniques to tackle the complexity and the diversity in the use of software in safety-critical systems. The contributions in this special issue address some of the core problems in software model checking. The articles are based on papers selected from the 2013 SPIN Symposium on Model Checking of Software, an annual forum for practitioners and researchers interested in symbolic and state space-based techniques for the validation and analysis of software systems.     

一种软件模型检测方法及其原型系统

Microsoft Research.Zin项目

MOPS:an Infrastructure for Examining Security Properties of Software

程序分析技术 2005

基于符号模型检测方法的应对规划系统 2006

>>更多...     

基于模型检验的软件安全静态分析研究

软件安全静态分析是检测软件安全漏洞的一种手段。本文在总结现有的软件安全静态分析方法的基础上，将在硬件设计领域得到成功应用的模型检验方法引入到软件产品的检验中，给出了一种基于自动机理论的检测软件安全的模型检验方法，阐述了其原理和工作流程，并用实例进行了验证说明。     

模型检测在软件测试中的应用研究

以测试为基础的模型或规格是产生测试用例的一种很有潜力技术。在这种方法中,先要建立一个系统的规格或模型,再由规格或模型产生测试用例。文章对结合模型检测来进行测试的方法进行了研究,从整体上对测试进行考虑,不仅包含了对系统所希望具有的功能进行测试,还包括了对系统不应具有的功能进行测试。通过这种方法,我们可以进一步保证系统的正确性和可靠,大大降低人力和资源的开销,为进一步优化测试奠定了基础。     

Specification and Generation of Environment for Model Checking of Software Components

Model checking of isolated software components is inherently not possible because a component does not form a complete program with an explicit starting point. To overcome this obstacle, it is typically necessary to create an environment of the component which is the intended subject to model checking. We present our approach to automated environment generation that is based on behavior protocols [Plasil, F., and S. Visnovsky, Behavior Protocols for Software Components, IEEE Transactions on Software Engineering, 28(2002)]; to our knowledge, this is the only environment generator designed for model checking of software components. We compare it with the approach taken in the Bandera Environment Generator tool [Tkachuk, O., M. B. Dwyer and C. S. Pasareanu, Automated Environment Generation for Software Model Checking, 18th IEEE International Conference on Automated Software Engineering (ASE03), p. 116, 2003], designed for model checking of sets of Java classes.     

Model Checking

Die Gewährleistung der korrekten Funktionsweise von Hard- und Software ist ein entscheidender Faktor bei der heutigen Systementwicklung. Dies trifft ganz besonders auf das Gebiet der sog. sicherheitskritischen Systeme zu, bei dem ein Systemversagen Menschenleben gefährden kann.     

软件安全建模与检测

为有效表示和检测软件中存在的安全缺陷和隐患,提出了一种软件安全建模与检测技术--层次融合安全建模与检测技术.该技术采用多点建模技术,通过结合抽象建模、应用建模和数据建模等机制来实现对安全特征的描述.此外该技术利用表示层、应用层等不同抽象层次的建模信息,通过自动机与模型合成技术来构建安全特征模型.最后结合基于应用切片技术对软件中的安全缺陷与隐患进行检测.该技术克服了常规安全建模与检测中存在的缺点,可以有效表示和检测各种安全特征,提高了安全模型的表达力、复用性和适用性,降低了安全检测的复杂度.     

Open-Source Model Checking

We present GMC², a software model checker for GCC, the open-source compiler from the Free Software Foundation (FSF). GMC², which is part of the GMC static-analysis and model-checking tool suite for GCC under development at SUNY Stony Brook, can be seen as an extension of Monte Carlo model checking to the setting of concurrent, procedural programming languages. Monte Carlo model checking is a newly developed technique that utilizes the theory of geometric random variables, statistical hypothesis testing, and random sampling of lassos in Büchi automata to realize a one- sided error, randomized algorithm for LTL model checking. To handle the function call/return mechanisms inherent in procedural languages such as C/C++, the version of Monte Carlo model checking implemented in GMC² is optimized for pushdown-automaton models. Our experimental results demonstrate that this approach yields an efficient and scalable software model checker for GCC.     

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.     

Model Checking Programs

The majority of work carried out in the formal methods community throughout the last three decades has (for good reasons) been devoted to special languages designed to make it easier to experiment with mechanized formal methods such as theorem provers, proof checkers and model checkers. In this paper we will attempt to give convincing arguments for why we believe it is time for the formal methods community to shift some of its attention towards the analysis of programs written in modern programming languages. In keeping with this philosophy we have developed a verification and testing environment for Java, called Java PathFinder (JPF), which integrates model checking, program analysis and testing. Part of this work has consisted of building a new Java Virtual Machine that interprets Java bytecode. JPF uses state compression to handle big states, and partial order and symmetry reduction, slicing, abstraction, and runtime analysis techniques to reduce the state space. JPF has been applied to a real-time avionics operating system developed at Honeywell, illustrating an intricate error, and to a model of a spacecraft controller, illustrating the combination of abstraction, runtime analysis, and slicing with model checking.