Search

One of the appreciated features of the synchronous dataflow approach is that a program defines a perfectly deterministic behavior. But the use of the delay primitive leads to undefined values at the first cycle; thus a dataflow program is really deterministic only if it can be shown that such undefined values do not affect the behavior of the system.This paper presents aninitialization analysisthat guarantees the deterministic behavior of programs. This property being undecidable in general, the paper proposes a safe approximation of the property, precise enough for most dataflow programs. This analysis is aone-bitanalysis - expressions are either initialized or uninitialized - and is defined as an inference-type system with subtyping constraints. This analysis has been implemented in theLucid Synchronecompiler and in a newScade-Lustreprototype compiler at Esterel Technologies. The analysis gives very good results in practice. [ABSTRACT FROM AUTHOR]

Reasoning about program heap, especially if it involves handling unbounded, dynamically heap-allocated data structures such as linked lists and arrays, is challenging. Furthermore, sound analysis that precisely models heap becomes significantly more challenging in the presence of low-level pointer manipulation that is prevalent in systems software. The reachability predicate has already proved to be useful for reasoning about the heap in type-safe languages where memory is manipulated by dereferencing object fields. In this paper, we present a memory model suitable for reasoning about low-level pointer operations that is accompanied by a formalization of the reachability predicate in the presence of internal pointers and pointer arithmetic. We have designed an annotation language for C programs that makes use of the new predicate. This language enables us to specify properties of many interesting data structures present in the Windows kernel. We present our experience with a prototype verifier on a set of illustrative C benchmarks. [ABSTRACT FROM AUTHOR]

The openness of modern IT systems and their permanent change make it challenging to keep these systems secure. A combination of regression and security testing called security regression testing, which ensures that changes made to a system do not harm its security, are therefore of high significance and the interest in such approaches has steadily increased. In this article we present a systematic classification of available security regression testing approaches based on a solid study of background and related work to sketch which parts of the research area seem to be well understood and evaluated, and which ones require further research. For this purpose we extract approaches relevant to security regression testing from computer science digital libraries based on a rigorous search and selection strategy. Then, we provide a classification of these according to security regression approach criteria: abstraction level, security issue, regression testing techniques, and tool support, as well as evaluation criteria, for instance evaluated system, maturity of the system, and evaluation measures. From the resulting classification we derive observations with regard to the abstraction level, regression testing techniques, tool support as well as evaluation, and finally identify several potential directions of future research. [ABSTRACT FROM AUTHOR]

The community of software testing and that of protocol testing are traditionally disjoint. It is seldom the case that protocol testing experts present papers at the large software testing conferences and vice versa. This raises the question about the peculiarities of protocol testing with respect to general software testing. Here we will examine those peculiarities and the consequences in terms of specific methodology developed for protocol testing. [ABSTRACT FROM AUTHOR]

This paper is concerned with the problem of checking. by means of testing. that a software component satisfies a specification of temporal safety properties. Checking that an actual observed behavior conforms to the specification is performed by a test oracle, which can be either a human tester or a software module. We present a technique for automatically generating test oracles from specifications of temporal safety properties in a metric temporal logic. The logic can express quantitative timing properties. and can also express properties of data values by means of a quantification construct. The generated oracle works online in the sense that checking is performed simultaneously with observation. The technique has been implemented and used in case studies at Volvo Technical Development Corporation. [ABSTRACT FROM AUTHOR]

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 in- variants. 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. [ABSTRACT FROM AUTHOR]

This paper presents a scalable method for parallel symbolic on-the-fly model checking in a distributed memory environment. Our method combines a scheme for on-the-fly model checking for safety properties with a scheme for scalable reachability analysis. We suggest an efficient, BDD-based algorithm for a distributed construction of a counterexample. The extra memory requirement for counterexample generation is evenly distributed among the processes by a memory balancing procedure. At no point during computation does the memory of a single process contain all the data. This enhances scalability. Collaboration between the parallel processes during counterexample generation reduces memory utilization for the backward step. We implemented our method on a standard, loosely-connected environment of workstations, using a high-performance model checker. Our initial performance evaluation, carried out on several large circuits, shows that our method can check models that are too large to fit in the memory of a single node. Our on-the-fly approach may find counterexamples even when the model is too large to fit in the memory of the parallel system. [ABSTRACT FROM AUTHOR]

The semantics of modelling languages are not always specified in a precise and formal way, and their rather complex underlying models make it a non-trivial exercise to reuse them in newly developed tools. We report on experiments with a virtual machine-based approach for state space generation. The virtual machine’s (VM) byte-code language is straightforwardly implementable, facilitates reuse and makes it an adequate target for translation of higher-level languages like the SPIN model checker’s P romela, or even C. As added value, it provides efficiently executable operational semantics for modelling languages. Several tools have been built around the VM implementation we developed, to evaluate the benefits of the proposed approach. [ABSTRACT FROM AUTHOR]

For model-based development to be a success in practice, it needs to have a convincing added-value associated with its use. Our goal is to provide such added-value by developing tool-support for the analysis of UML models against difficult system requirements. Towards this goal, we describe a UML verification framework supporting the construction of automated requirements analysis tools for UML diagrams. The framework is connected to industrial CASE tools using XMI and allows convenient access to this data and to the human user. As a particular example, we present plugins for verifying models defined using the security extension UMLsec of UML. The verification framework allows advanced users of the UMLsec approach to themselves implement verification routines for the constraints of self-defined stereotypes. In particular, we focus on an analysis plug-in that utilizes the model-checker Spin to verify security properties of cryptography-based systems. [ABSTRACT FROM AUTHOR]

UML-RT is achieving increasing popularity as a modeling language for real-time applications. Unfortunately UML-RT is not formally well defined and it is not well suited for supporting the specification stage: e.g., it does not provide native constructs to represent time and non-determinism. UML+ is an extension of UML that is formally well defined and suitable for expressing the specifications of real-time systems (e.g., the properties of a UML+ model can be formally verified). However, UML+ does not support design and development. This article addresses the translation of UML+ into UML-RT, thus posing the basis for a development framework where UML+ and UML-RT are used together, in order to remove each other’s limitations. Specifications are written using UML+, they are automatically verified by means of formal methods, and are then converted – through a semi-automatic process – in an equivalent UML-RT model that becomes the starting point for the implementation. [ABSTRACT FROM AUTHOR]

Insight into the global structure of a state space is of great help in the analysis of the underlying process. We advocate the use of visualization for this purpose and present a method to visualize the structure of very large state spaces with millions of nodes. The method uses a clustering based on an equivalence relation to obtain a simplified representation, which is used as a backbone for the display of the entire state space. With this visualization we are able to answer questions about the global structure of a state space that cannot easily be answered by conventional methods. We show this by presenting a number of visualizations of real-world protocols . [ABSTRACT FROM AUTHOR]

Today’s development processes employ a variety of notations and tools, e.g., the Unified Modeling Language UML, the Standard Description Language SDL, requirements databases, design tools, code generators, model checkers, etc. For better process support, the employed tools may be organized within a tool suite or integration platform, e.g., Rational Rose or Eclipse. While these tool-integration platforms usually provide GUI adaption mechanisms and functional adaption via application programming interfaces, they frequently do not provide appropriate means for data integration at the meta-model level. Thus, overlapping and redundant data from different “integrated” tools may easily become inconsistent and unusable. We propose two design patterns that provide a flexible basis for the integration of different tool data at the meta-model level. To achieve consistency between meta-models, we describe rule-based mechanisms providing generic solutions for managing overlapping and redundant data. The proposed mechanisms are widely used within the Fujaba Tool Suite. We report about our implementation and application experiences . [ABSTRACT FROM AUTHOR]

The ability to generate counterexamples for failing properties is often cited as one of the strengths of model checking. However, it is often difficult to interpret long error traces in which many variables appear. Besides, a traditional error trace presents only one possible behavior of the system causing the failure, with no further annotation. Our objective is to identify some structure in the error trace to make debugging easier. We present an enhanced error trace as an alternation of fated (forced) and free segments. The fated segments show unavoidable progress toward the error while the free segments show choices that, if avoided, may have prevented the error. Hence, the demarcation into segments tends to highlight critical events. The segmentation of a trace raises the questions of whether the fated segment should indeed be inevitable and whether the free segments are critical in causing the error. Addressing these questions may help the user to better analyze the failure of the property. [ABSTRACT FROM AUTHOR]

The i-protocol, an optimized sliding-window protocol for GNU uucp, first came to our attention in 1995 when we used the Concurrency Factory's local model checker to detect, locate, and correct a non-trivial livelock in version 1.04 of the protocol. Since then, we have conducted a systematic case study on the protocol using four verification tools, viz. Cospan, Munp, Spin, and XMC, each of which supports some form of explicit-state model checking. Our results show that although the i-protocol is inherently complex - the size of its state space grows exponentially in the window size and it deploys several sophisticated optimizations aimed at minimizing control-message and retransmission overhead - it is nonetheless amenable to a number of general-purpose abstraction techniques whose application can significantly reduce the size of the protocol's state space. [ABSTRACT FROM AUTHOR]

We present an approach for analyzing cryptographic protocols that are subject to attack from an active intruder who takes advantage of knowledge of the protocol rules. The approach uses a form of type system in which types are communication steps and typing constraints characterize all the messages available to the intruder. This reduces verification of authentication and secrecy properties to a typing problem in our type system. We present the typing rules, prove soundness of a type inference algorithm, and establish the correctness of the typing rules with respect to the protocol execution and intruder actions. The protocol specifications used in the approach can be automatically extracted from the conventional, informal cryptographic protocol notation commonly found in the literature. To validate the approach, we implement our algorithm in a tool called DYMNA, which is a practical and efficient environment for the specification and analysis of cryptographic protocols. [ABSTRACT FROM AUTHOR]