Directed model checking with distance-preserving abstractions

In directed model checking, the traversal of the state space is guided by an estimate of the distance from the current state to the nearest error state. This paper presents a distance-preserving abstraction for concurrent systems that allows one to compute an interesting estimate of the error distance without hitting the state explosion problem. Our experiments show a dramatic reduction both in the number of states explored by the model checker and in the total runtime.     

Verifying data refinements using a model checker

In this paper, we consider how refinements between state-based specifications (e.g., written in Z) can be checked by use of a model checker. Specifically, we are interested in the verification of downward and upward simulations which are the standard approach to verifying refinements in state-based notations. We show how downward and upward simulations can be checked using existing temporal logic model checkers.In particular, we show how the branching time temporal logic CTL can be used to encode the standard simulation conditions. We do this for both a blocking, or guarded, interpretation of operations (often used when specifying reactive systems) as well as the more common non-blocking interpretation of operations used in many state-based specification languages (for modelling sequential systems). The approach is general enough to use with any state-based specification language, and we illustrate how refinements between Z specifications can be checked using the SAL CTL model checker using a small example.     

Model checking action system refinements

Action systems provide a formal approach to modelling parallel and reactive systems. They have a well established theory of refinement supported by simulation-based proof rules. This paper introduces an automatic approach for verifying action system refinements utilising standard CTL model checking. To do this, we encode each of the simulation conditions as a simulation machine, a Kripke structure on which the proof obligation can be discharged by checking that an associated CTL property holds. This procedure transforms each simulation condition into a model checking problem. Each simulation condition can then be model checked in isolation, or, if desired, together with the other simulation conditions by combining the simulation machines and the CTL properties.     

A universal relation data model with semantic abstractions

Two important features of modern database models are support for complex data structures and support for high-level data retrieval and update. The first issue has been studied by the development of various semantic data models; the second issue has been studied through universal relation data models. How the advantages of these two approaches can be combined is presently examined. A new data model that incorporates standard concepts from semantic data models such as entities, aggregations, and ISA hierarchies is introduced. It is then shown how nonnavigational queries and updates can be interpreted in this model. The main contribution is to demonstrate how universal relation techniques can be extended to a more powerful data model. Moreover, the semantic constructs of the model allow one to eliminate many of the limitations of previous universal relation models     

Bayesian model checking for multivariate outcome data

Bayesian models are increasingly used to analyze complex multivariate outcome data. However, diagnostics for such models have not been well developed. We present a diagnostic method of evaluating the fit of Bayesian models for multivariate data based on posterior predictive model checking (PPMC), a technique in which observed data are compared to replicated data generated from model predictions. Most previous work on PPMC has focused on the use of test quantities that are scalar summaries of the data and parameters. However, scalar summaries are unlikely to capture the rich features of multivariate data. We introduce the use of dissimilarity measures for checking Bayesian models for multivariate outcome data. This method has the advantage of checking the fit of the model to the complete data vectors or vector summaries with reduced dimension, providing a comprehensive picture of model fit. An application with longitudinal binary data illustrates the methods.     

Formal analysis for robust anti-SPIT protection using model checking

Anti-SPIT policies counter the SPam over Internet Telephony (SPIT) by distinguishing bots launching unsolicited bulks of VoIP calls from human beings. We propose an Anti-SPIT Policy Management mechanism (aSPM) that detects spam calls and prevents VoIP session establishment by the Session Initiation Protocol (SIP). The SPIN model checker is used to formally model and analyze the robustness of the aSPM mechanism in execution scenarios with parallel SIP sessions. In case of a possible design flaw, the model checker provides a trace of the caught unexpected behavior (counterexample), that can be used for the revision of the mechanism’s design. Our SPIN model is parameterized, based on measurements from experiments with VoIP users. Non-determinism plays a key role in representing all possible anti-SPIT policy decisions, in terms of the SIP messages that may be exchanged. The model checking results provide evidence for the timeliness of the parallel SIP sessions, the absence of deadlocks or livelocks, and the fairness for the VoIP service users. These findings ensure robust anti-SPIT protection, meaning that the aSPM mechanism operates as expected, despite the occurrence of random SPIT calls and communication error messages. To the best of our knowledge, this is the first analysis for exhaustively searching security policy flaws, due to complex interactions between anti-SPIT measures and the SIP protocol services.     

On model checking multiple hybrid views

Many applications, for instance the MS .NET Global Assembly Cache (GAC), are naturally expressed as 3-valued models where an additional third truth value models uncertainty or under-specification. An example of under-specification is that a component in a GAC may or may not have a main method. Models described in this manner can then be analyzed to refute or verify properties about the concrete systems they intend to model. This approach to system validation traditionally considers only one model at a time, even though this model may evolve if subjected to analysis. Many applications, however, benefit from or require the simultaneous consideration of multiple models of systems. We mention here requirements from different stake holders, and data drawn from federated databases.     

E-process design and assurance using model checking

Trust in e-commerce is difficult to establish and maintain. Almost daily, news headlines cover some incident, causing users to question e-commerce systems' trustworthiness. Strong e-process design and implementation is the first line of defense against errors, fraud and hacking. Minimizing program faults in business operations is critical for an e-business's survival. Carefully designed and implemented code can handle most expected situations, so these e-processes often function well within their defined boundaries, but guaranteeing correct processing under all circumstances is extremely difficult, if not impossible. Hidden flaws and errors, triggered only under unexpected, hard-to-anticipate scenarios, lead to subtle mistakes and even catastrophic failures. The authors use an online ticket sales example to illustrate the potential of model checking (an advanced formal method) for economically finding certain flaws. Model checking is a powerful verification method that determines whether a system model satisfies certain specifications under all circumstances. It can locate subtle but critical flaws that conventional design and assurance methods, such as testing and simulation, often miss     

Automated traceability analysis for UML model refinements

During iterative, UML-based software development, various UML diagrams, modeling the same system at different levels of abstraction are developed. These models must remain consistent when changes are performed. In this context, we refine the notion of impact analysis and distinguish horizontal impact analysis–that focuses on changes and impacts at one level of abstraction–from vertical impact analysis–that focuses on changes at one level of abstraction and their impacts on another level. Vertical impact analysis requires that some traceability links be established between model elements at the two levels of abstraction. We propose a traceability analysis approach for UML 2.0 class diagrams which is based on a careful formalization of changes to those models, refinements which are composed of those changes, and traceability links corresponding to refinements. We show how actual refinements and corresponding traceability links are formalized using the OCL. Tool support and a case study are also described.     

Minimal data dependence abstractions for loop transformations: Extended version

Many abstractions of program dependences have already been proposed, such as the Dependence Distance, the Dependence Direction Vector, the Dependence Level or the Dependence Cone. These different abstractions have different precisions. Theminimal abstraction associated to a transformation is the abstraction that contains the minimal amount of information necessary to decide when such a transformation is legal. Minimal abstractions for loop reordering and unimodular transformations are presented. As an example, the dependence cone, which approximates dependences by a convex cone of the dependence distance vectors, is the minimal abstraction for unimodular transformations. It also contains enough information for legally applying all loop reordering transformations and finding the same set of valid mono- and multi-dimensional linear schedules as the dependence distance set.     

Programming by successive refinement of data abstractions

The Model Programming Language implements a form of data abstraction that has been used in a large programming project, the Demos Operating System. The use of the abstraction mechanism suggests a particular programming style that has evolved over an extensive period of gaining experience with the language. The programming style and Model's approach to data abstraction are both documented here using an example designed to illustrate several of the more important issues. The goal of the paper is to demonstrate a programming style and an approach to data abstraction in a programming language that has proved useful in a significant systems programming application.     

On decidability of LTL model checking for process rewrite systems

We establish a decidability boundary of the model checking problem for infinite-state systems defined by Process Rewrite Systems (PRS) or weakly extended Process Rewrite Systems (wPRS), and properties described by basic fragments of action-based Linear Temporal Logic (LTL) with both future and past operators. It is known that the problem for general LTL properties is decidable for Petri nets and for pushdown processes, while it is undecidable for PA processes.We show that the problem is decidable for wPRS if we consider properties defined by LTL formulae with only modalities strict eventually, strict always, and their past counterparts. Moreover, we show that the problem remains undecidable for PA processes even with respect to the LTL fragment with the only modality until or the fragment with modalities next and infinitely often.     

Debugging programs that use macro-oriented data abstractions

Enhanced C (EC) is a set-oriented, extensible, C-like language. EC uses data abstractions to define new types. These data abstractions, called clusters, are macro-like devices that perform substitution on the typed syntax tree. Debugging programs that use clusters raise problems that are not encountered in ordinary programming languages. At compile time there is a need to determine and report whether the macro expansion will result in a legal program before this expansion actually takes place. At run-time the problems are how to account for replaced statements and how to handle variables whose types have been established by the clusters, variables that disappear, or variables whose names have been changed. This article presents these problems and their solutions as implemented by the EC compiler and the EC symbolic debugger. Similar debugging problems appear in other languages: The need to handle variables at run time is common to all languages that support data abstraction even if the abstractions are procedure oriented; also, a mild form of the problem of the replaced statement appears in inline procedure substitution of Ada. The solutions developed for the EC debugger apply to these cases as well.     

Analysing a stream authentication protocol using model checking

In this paper, we consider how one can analyse a stream authentication protocol using model checking techniques. In particular, we will be focusing on the Timed Efficient Stream Loss-tolerant Authentication Protocol, TESLA. This protocol differs from the standard class of authentication protocols previously analysed using model checking techniques in the following interesting way: an unbounded stream of messages is broadcast by a sender, making use of an unbounded stream of keys; the authentication of the n-th message in the stream is achieved on receipt of the n+1-th message. We show that, despite the infinite nature of the protocol, it is possible to build a finite model that correctly captures its behaviour.     

Role updating in information systems using model checking

The role-based access control (RBAC) has significantly simplified the management of users and permissions in information systems. In dynamic environments, systems are constantly undergoing changes, and accordingly, the associated configurations need to be updated in order to reflect the systems’ security evolutions. However, such updating process is generally complicated as the resulting system state is expected to meet necessary constraints. This paper presents an approach for assisting administrators to make a desirable update, in light of changes in RBAC systems. We propose a formalization of the update approach, investigate its properties, and develop an updating algorithm based on model checking techniques. Our experimental results demonstrate the effectiveness of the proposed approach.     

Scaling model checking of dataraces using dynamic information

Dataraces in multithreaded programs often indicate severe bugs and can cause unexpected behaviors when different thread interleavings are executed. Because dataraces are a cause for concern, many works have dealt with the problem of detecting them. Works based on dynamic techniques either report errors only for dataraces that occur in the current interleaving, which limits their usefulness, or produce many spurious dataraces. Works based on model checking search exhaustively for dataraces and thus can reveal even those that occur in rarely executed paths. However, the applicability of model checking is limited because the large number of thread interleavings in realistic multithreaded programs causes state space explosion. In this work, we combine the two techniques in a hybrid scheme which overcomes these difficulties and enjoys the advantages of both worlds. Our hybrid technique succeeds in providing thread interleavings that prove the existence of dataraces in realistic programs. The programs we experimented with cannot be checked using either an ordinary industrial strength model checker or bounded model checking.