论有穷状态验证方法的局限性

程序有穷状态验证方法是介于程序验证和程序测试之间的一种方法，一方面它如同程序验证一样可以证明某程序具有某些要求的性质，或找出反例证明该程序不具有所要求的性质。另一方面它又不像程序验证那样复杂，要求验证人员具有较高的形式化推理的专业理论和数学水平。但是，现有的有穷状态验证方法有很大的局限性，它要求所论证的性质是有穷自动机所接受的事件序列的集合，或等价地说该性质能表示成为正则表达式。众所周知，有穷自动机所能接受的语言类，按Chomsky字的集合的分类是很小的类。本文讨论了这种局限性，井尝试突破只能使用有穷自动机的限制，提出了一种新的验证方法——有穷路径验证法。在这种方法中，所论证的性质表示可以推广到使用任何一类自动机。作为代价，描写系统的模型限制是无环的。对于有环的描写系统的模型，本文提出了一种称之为“有穷路径测试”的方法。同一般的程序测试一样，用这种方法通过测试不能正面地验证程序的正确性，可是如果通不过测试，则能帮你发现反例，找出程序的错误。与一般的程序测试不同的是这里的测试是相对于模型的路径，而不执行实际的程序。     

Proving the shalls

Incomplete, inaccurate, ambiguous, and vola-tile requirements have plagued the software industry since its inception. The convergence of model-based development and formal methods offers developers of safety-critical systems a powerful new approach to the early validation of requirements. This paper describes an exercise conducted to determine if formal methods could be used to validate system requirements early in the lifecycle at reasonable cost. Several hundred functional and safety requirements for the mode logic of a typical flight guidance system were captured as natural language “shall” statements. A formal model of the mode logic was written in the RSML^−e language and translated into the NuSMV model checker and the PVS theorem prover using translators developed as part of the project. Each “shall” statement was manually translated into a NuSMV or PVS property and proven using these tools. Numerous errors were found in both the original requirements and the RSML^−e model. This demonstrates that formal models can be written for realistic systems and that formal analysis tools have matured to the point where they can be effectively used to find errors before implementation. This project was partially funded by the NASA Langley Research Center under contract NCC1-01001 of the Aviation Safety Program.     

Finding feasible abstract counter-examples

A strength of model checking is its ability to automate the detection of subtle system errors and produce traces that exhibit those errors. Given the high-computational cost of model checking most researchers advocate the use of aggressive property-preserving abstractions. Unfortunately, the more aggressively a system is abstracted the more infeasible behavior it will have. Thus, while abstraction enables efficient model checking it also threatens the usefulness of model checking as a defect detection tool, since it may be difficult to determine whether a counter-example is feasible and hence worth developer time to analyze.We have explored several strategies for addressing this problem by extending an explicit-state model checker, Java PathFinder (JPF), to search for and analyze counter-examples in the presence of abstractions. We demonstrate that these techniques effectively preserve the defect detection ability of model checking in the presence of aggressive abstraction by applying them to check properties of several abstracted multi-threaded Java programs. These new capabilities are not specific to JPF and can be easily adapted to other model checking frameworks; we describe how this was done for the Bandera toolset.     

软件模型代数性质的程序化验证

软件模型代数的思想是通过引入进程代数来对软件体系结构进行建模。它将构件解释为变量,将连接子抽象为代数运算,并针对软件的特性建立了软件体系结构代数模型。在代数模型的基础上,讨论分析获得一系列能指导软件演化的代数性质。但是,上述研究都只对模型的代数性质进行了理论证明,实际上并无程序能够证明这些代数性质的正确性,同时也未给出这些性质的应用方法,使其缺乏可操作性。采用程序化验证的方法对代数性质进行了验证,并对这些性质的应用算法进行了研究,进一步丰富了软件的建模理论,也使得软件演化从理论研究转化为实际应用成为可能。     

Memory model sensitive bytecode verification

Modern concurrent programming languages like C# and Java have a programming language level memory model, which captures the set of all allowed behaviors of programs on any implementation platform—uni- or multi-processor. Such a memory model is typically weaker than Sequential Consistency and allows reordering of operations within a program thread. Therefore, programs verified correct by assuming Sequential Consistency (that is, each thread proceeds in program order) may not behave correctly on certain platforms! One solution to this problem is to develop program checkers which are memory model sensitive. In this paper, we develop a bytecode level invariant checker for the programming language C#. Our checker identifies program states which are reached only because the C# memory model is more relaxed than Sequential Consistency. It employs partial order reduction strategies to speed up the search. These strategies are different from standard partial order reduction methods since our search also considers execution traces containing bytecode re-orderings. Furthermore, our checker identifies (a) operation re-orderings which cause undesirable states to be reached, and (b) simple program modifications—by inserting memory barrier operations—which prevent such undesirable re-orderings. A preliminary version of this paper appeared as (Huynh and Roychoudhury, in: Formal Methods Symposium, 2006). The conference paper is available from . This work was done when the first author was a Research Assistant at National University of Singapore.     

Efficient SAT-based bounded model checking for software verification

This paper discusses our methodology for formal analysis and automatic verification of software programs. It is applicable to a large subset of the C programming language that includes pointer arithmetic and bounded recursion. We consider reachability properties, in particular whether certain assertions or basic blocks are reachable in the source code, or whether certain standard property violations can occur. We perform this analysis via a translation to a Boolean circuit representation based on modeling basic blocks. The program is then analyzed by a back-end SAT-based bounded model checker, where each unrolling is mapped to one step in a block-wise execution of the program.     

Inductive assertions and operational semantics

This paper shows how classic inductive assertions can be used in conjunction with a formal operational semantics to prove partial correctness properties of programs. The method imposes only the proof obligations that would be produced by a verification condition generator – but does not require the definition of a verification condition generator. All that is required is a theorem prover, a formal operational semantics, and the object program with appropriate assertions at user-selected cut points. The verification conditions are generated in the course of the theorem-proving process by straightforward symbolic evaluation of the formal operational semantics. The technique is demonstrated by proving the partial correctness of simple bytecode programs with respect to a preexisting operational model of the Java Virtual Machine.     

The formal-CAFE methodology and model checking patterns in the specification of e-commerce systems

Electronic commerce is an important application that has evolved significantly recently. However, electronic commerce systems are complex and difficult to be correctly designed. Guaranteeing the correctness of an e-commerce system is not an easy task due to the great amount of scenarios where errors occur, many of them very subtle. In this work we presents a methodology that uses formal-method techniques, specifically symbolic model checking, to design electronic commerce applications and to automatically verify them. Also, a model checking pattern hierarchy has been developed—it specifies patterns to construct and verify the formal model of e-commerce systems. We consider this research the first step to the development of a framework, which will integrate the methodology, an e-commerce specification language based on business rules, and a model checker. Adriano Pereira received the B.S. and M.S. degrees in computer science in 2000 and 2002, respectively, and he is currently pursuing the Ph.D. degree in computer science from the Federal University of Minas Gerais, Belo Horizonte, Brazil. His current interests are on performance analysis and modeling of e-business and distributed systems, and formal methods. Mark Song received the B.S., M.S. and Ph.D. degrees in computer science from the Federal University of Minas Gerais, Belo Horizonte, Brazil. His current interests are on distributed systems and formal methods – especially BMC (Bounded Model Checking). Gustavo Franco received the B.S. and M.S. degrees in computer science in 2001 and 2004, respectively, from the Federal University of Minas Gerais, Belo Horizonte, Brazil. His research was on modeling the user behavior of e-business and distributed systems, and formal methods. Actually his current interests are on software engeneering and project management of IT projects.     

A framework for the design and verification of software measurement methods

At the core of any engineering discipline is the use of measures, based on ISO standards or on widely recognized conventions, for the development and analysis of the artifacts produced by engineers. In the software domain, many alternatives have been proposed to measure the same attributes, but there is no consensus on a framework for how to analyze or choose among these measures. Furthermore, there is often not even a consensus on the characteristics of the attributes to be measured.In this paper, a framework is proposed for a software measurement life cycle with a particular focus on the design phase of a software measure. The framework includes definitions of the verification criteria that can be used to understand the stages of software measurement design. This framework also integrates the different perspectives of existing measurement approaches. In addition to inputs from the software measurement literature the framework integrates the concepts and vocabulary of metrology. This metrological approach provides a clear definition of the concepts, as well as the activities and products, related to measurement. The aim is to give an integrated view, involving the practical side and the theoretical side, as well as the basic underlying concepts of measurement.     

支持模型驱动开发的软构件形式化描述方法

针对模型驱动的软件开发(MDSD)中语义特性保持的描述和验证等问题,基于类型范畴理论的形式化框架和进程代数理论,提出了一种软件结构模型的形式化描述方法。在此基础上对模型转换前后构件规范之间应满足的语义约束进行了深入的分析和探讨,从图表结构、端口与配置约束、外部行为以及可替换性等四个方面对特性约束保持的问题进行了描述,并建立了相应的判定标准。该方法能为模型之间转换规则的定义提供指导,并为模型转换的效果分析和正确性验证提供依据。应用研究表明,该方法使得构件模型的语义描述能力显著增强,可作为已有软件建模方法的一个有效补充。     

基于Uppaal的实时系统AADL数据流模型的转换与验证

体系结构分析设计语言AADL是一种可支持软硬件一体化建模及同一模型多元分析的形式化与图形化建模语言。采用时间自动机形式化模型检验方法对AADL模型中的数据流进行转换和验证。考虑到单一数据流与混合数据流的差异性,分别设计了数据流到时间自动机模型的转换规则,并通过时间自动机网络实现数据流的综合分析。设计开发了自动化模型转换的插件AADLToUppaal Plug-in,将其嵌入到OSTATE工具中,使用时间自动机建模与验证工具Uppaal对转换得到的时间自动机进行模拟和验证,等价地验证所设计的AADL模型数据流时延是否满足系统实时性要求。仿真实验结果表明,所设计的数据流模型转换方法能有效地将AADL模型转换到时间自动机模型,并能在Uppaal中正确地分析原模型的数据流时延特性。     

Symmetry reductions for model checking of concurrent dynamic software

Symmetry reduction techniques exploit symmetries that occur during the execution of a system in order to minimize its state space for efficient verification of temporal logic properties. This paper presents a framework for concisely defining and evaluating symmetry reductions currently used in software model checking, involving heap objects and processes. An on-the-fly state space exploration algorithm combining both techniques will also be presented. Second, the relation between symmetry and partial-order reductions is investigated, showing how ones strengths can be used to compensate for the others weaknesses. The symmetry reductions presented here were implemented in the dSPIN model-checking tool. We also performed a number of experiments that show significant progress in reducing the cost of finite-state software verification.     

面向源代码的软件模型检测及其实现

模型检测应用于检测软件可靠性具有重要意义.介绍了一种基于谓词抽象和反例引导抽象求精技术对源程序进行建模和验证的模型检测方法,并结合自行研发的Jchecker工具详细介绍了该软件模型检测技术的运作过程和关键算法.     

Development of a verified Erlang program for resource locking

In this paper, we describe a tool to verify Erlang programs and show, by means of an industrial case study, how this tool is used. The tool includes a number of components, including a translation component, a state space generation component and a model checking component. To verify properties of the code, the tool first translates the Erlang code into a process algebraic specification. The outcome of the translation is made more efficient by taking advantage of the fact that software written in Erlang builds upon software design patterns such as client–server behaviours. A labelled transition system is constructed from the specification by use of the CRL toolset. The resulting labelled transition system is model checked against a set of properties formulated in the -calculus using the Caesar/Aldébaran toolset.As a case study we focus on a simplified resource manager modelled on a real implementation in the control software of the AXD 301 ATM switch. Some of the key properties we verified for the program are mutual exclusion and non-starvation. Since the toolset supports only the regular alternation-free -calculus, some ingenuity is needed for checking the liveness property non-starvation. The case study has been refined step by step to provide more functionality, with each step motivated by a corresponding formal verification using model checking .     

Organisational change through influence

Influence is a phenomenon underpinning many types of interactions in both human and artificial organisations, and has a significant impact on the operation of the organisation. If influence can be examined at the organisational level, instead of at the level of the agents involved, engineers can better understand an organisation’s robustness to structural, behavioural and population changes. In this paper we present the Model of Organisational Change using Agents (MOChA) as a means to formally specify, check and simulate organisations using agents, particularly with a view to determining the impact of influence on the operation of an organisation. This formalisation of influence is not specific to our model, and is relevant and adaptable to any organisational model in which explicit relationships among roles of agents are formed.     

A verification tool for ERLANG

This paper presents an overview of the main results of the project Verification of ERLANG Programs , which is funded by the Swedish Business Development Agency (NUTEK) and by Ericsson within the ASTEC (Advanced Software TEChnology) initiative. Its main outcome is the ERLANG Verification Tool (EVT), a theorem prover which assists in obtaining proofs that ERLANG applications satisfy their correctness requirements formulated as behavioural properties in a modal logic with recursion. We give a summary of the verification framework as supported by EVT, discuss reasoning principles essential for successful proofs such as inductive and compositional reasoning, and an efficient treatment of side-effect-free code. The experiences of applying the tool in an industrial case study are summarised, and an approach for supporting verification in the presence of program libraries is outlined.EVT is essentially a classical proof assistant, or theorem-proving tool, requiring users to intervene in the proof process at crucial steps such as stating program invariants. However, the tool offers considerable support for automatic proof discovery through higher-level tactics tailored to the particular task of the verification of ERLANG programs. In addition, a graphical interface permits easy navigation through proof tableaux, proof reuse, and meaningful feedback about the current proof state, to assist users in taking informed proof decisions.     

Embedded software verification in hardware–software codesign

Concurrent Embedded Real-Time Software (CERTS) is intrinsically different from traditional, sequential, independent, and temporally unconstrained software. The verification of software is more complex than hardware due to inherent flexibilities (dynamic behavior) that incur a multitude of possible system states. The verification of CERTS is all the more difficult due to its concurrency and embeddedness. The work presented here shows how the complexity of CERTS verification can be reduced significantly through answering common engineering questions such as when, where, and how one must verify embedded software. First, a new Schedule-Verify-Map strategy is proposed to answer the when question. Second, verification under system concurrency is proposed to answer the where question. Finally, a complete symbolic model checking procedure is proposed for CERTS verification. Several application examples illustrate the usefulness of our technique in increasing verification scalability.     

The software model checker Blast

Blast is an automatic verification tool for checking temporal safety properties of C programs. Given a C program and a temporal safety property, Blast either statically proves that the program satisfies the safety property, or provides an execution path that exhibits a violation of the property (or, since the problem is undecidable, does not terminate). Blast constructs, explores, and refines abstractions of the program state space based on lazy predicate abstraction and interpolation-based predicate discovery. This paper gives an introduction to Blast and demonstrates, through two case studies, how it can be applied to program verification and test-case generation. In the first case study, we use Blast to statically prove memory safety for C programs. We use CCured, a type-based memory-safety analyzer, to annotate a program with run-time assertions that check for safe memory operations. Then, we use Blast to remove as many of the run-time checks as possible (by proving that these checks never fail), and to generate execution scenarios that violate the assertions for the remaining run-time checks. In our second case study, we use Blast to automatically generate test suites that guarantee full coverage with respect to a given predicate. Given a C program and a target predicate p, Blast determines the program locations q for which there exists a program execution that reaches q with p true, and automatically generates a set of test vectors that cause such executions. Our experiments show that Blast can provide automated, precise, and scalable analysis for C programs.     

Program verification with interacting analysis plugins

In this paper we propose and argue for a modular framework for interprocedural program analysis, where multiple program analysis tools are combined in order to exploit the particular advantages of each. This allows for “plugging together” such tools as required by each verification task and makes it easy to integrate new analyses. Our framework automates the sharing of information between plugins using a first order logic with transitive closure, in a way inspired by the open product of Cortesi et al. We describe a prototype implementation of our framework, which performs static assertion checking on a simple language for heap-manipulating programs. This implementation includes plugins for three existing approaches—predicate abstraction, 3-valued shape analysis and a decidable pointer analysis—and for a simple type system. We demonstrate through a detailed example the increase in precision that our approach can provide. Finally we discuss the design decisions we have taken, in particular the tradeoffs involved in the choice of language by which the plugins communicate, and identify some future directions for our work. R. Lazic, R. Nagarajan and J. C. P. Woodcock