Runtime monitoring and verification of systems with hidden information

This paper describes a technique for runtime monitoring (RM) and runtime verification (RV) of systems with invisible events and data artifacts. Our approach combines well-known hidden markov model (HMM) techniques for learning and subsequent identification of hidden artifacts, with runtime monitoring of probabilistic formal specifications. The proposed approach entails a process in which the end-user first develops and validates deterministic formal specification assertions, s/he then identifies hidden artifacts in those assertions. Those artifacts induce the state set of the identifying HMM. HMM parameters are learned using standard frequency analysis techniques. In the verification or monitoring phase, the system emits visible events and data symbols, used by the HMM to deduce invisible events and data symbols, and sequences thereof; both types of symbols are then used by a probabilistic formal specification assertion to monitor or verify the system.     

Are the Logical Foundations of Verifying Compiler Prototypes Matching user Expectations?

The verifying compiler (VC) project proposals suggest that mainstream software developers are its targeted end-users. Like other software engineering efforts, the VC project success depends on appropriate end-user consultation. Industrial use of program assertions for the purpose of run-time assertion checking (RAC) is becoming commonplace. A likely next step on the path to VC adoption is the use of assertions in extended static checking (ESC), a fully automated form of static program verification (SPV). Unfortunately, all current VC prototypes supporting SPV, adopt a semantics which is unsound relative to the standard run-time interpretation of assertions. In this article, we report on the results of a survey in which we asked industrial developers what logical semantics they want program assertions to have, and whether consistency across RAC and SPV tools is important. Survey results indicate that developers are in favor of a semantics for assertions that is compatible with their current use in RAC.     

Data structures and program correctness: Bridging the gap

An assertion language for data structures is presented, leading to the following results: formal semantics of operations on data structures are given in terms of the weakest precondition formula for assignment statements; input/output specifications for data-structure manipulating algorithms can be stated with precision; there is a clear relationship between the output specification and intermediate assertions; and knowledge about standard types of data structures can be schematized. These ideas are illustrated on an algorithm to reverse the arcs on a one-way linked list, and on a threaded tree example.     

An Aspect-Oriented Approach to Modular Behavioral Specification

Behavioral interface specification languages, such as Java Modeling Language (JML), can be used to specify the behavior of program modules. We have developed a behavioral interface specification language Moxa, an extension of JML. Moxa provides a new modularization mechanism called assertion aspect that can capture the crosscutting properties among assertions. In this paper, we briefly explain the notion of assertion aspects and the design of Moxa, and then we show an example specification. By comparing the specification to its JML counterpart, we show that the use of assertion aspects clarifies the large, complex specification and greatly simplifies each assertion in the specification.     

On the Role of OpenMath in Interactive Mathematical Documents

The standard OpenMath is an enabling technology for creating an integrated computer environment in which software packages for computer algebra and for proof checking can be combined. Here we demonstrate how OpenMath can be employed for generating interactive mathematical documents containing primality proofs. Our case study takes place within a browser; once a prime number is specified, a document appears summarizing the proof in a number of assertions. By clicking an assertion regarding the truth of an arithmetic equality, a computer algebra calculation is invoked verifying the equality. By clicking an assertion regarding a specific mathematical lemma called Pocklington’s Criterion, a verification of the corresponding formal proof is carried out by a proof checker. Moreover, the whole document is structured in such a way that it can be easily translated to a formal proof object. OpenMath supports the interaction between the document as it appears in the browser and the mathematical software packages. This paper begins with an introduction to OpenMath and a brief comparison with MathML.     

Integrating a formal method into a software engineering process with UML and Java

We describe how CSP-OZ, a formal method combining the process algebra CSP with the specification language Object-Z, can be integrated into an object-oriented software engineering process employing the UML as a modelling and Java as an implementation language. The benefit of this integration lies in the rigour of the formal method, which improves the precision of the constructed models and opens up the possibility of (1) verifying properties of models in the early design phases, and (2) checking adherence of implementations to models. The envisaged application area of our approach is the design of distributed reactive systems. To this end, we propose a specific UML profile for reactive systems. The profile contains facilities for modelling components, their interfaces and interconnections via synchronous/broadcast communication, and the overall architecture of a system. The integration with the formal method proceeds by generating a significant part of the CSP-OZ specification from the initially developed UML model. The formal specification is on the one hand the starting point for verifying properties of the model, for instance by using the FDR model checker. On the other hand, it is the basis for generating contracts for the final implementation. Contracts are written in the Java Modeling Language (JML) complemented by CSP_jassda, an assertion language for specifying orderings between method invocations. A set of tools for runtime checking can be used to supervise the adherence of the final Java implementation to the generated contracts. This research was partially supported by the DFG project ForMooS (grants OL 98/3-2 and WE 2290/5-1). C. B. Jones     

Simulating the behavior of software modules by trace rewriting

The trace assertion method is a module interface specification method based on the finite state machine model. To support this method, we plan to develop a specification simulation tool, a trace simulator, that symbolically interprets trace assertions of trace specifications and simulates the externally observable behavior of the modules specified. We first present the trace assertion method. Then we formally define trace rewriting systems and show how trace rewriting, a technique similar to term rewriting, can be applied to implement trace simulation     

Verifying Communication Protocols Using Live Sequence Chart Specifications

The need for a formal verification process in System on Chip (SoC) design and Intellectual Property (IP) integration has been recognized and investigated significantly in the past. A major drawback is the lack of a suitable specification language against which definitive and efficient verification of inter-core communication can be performed to prove compliance of an IP block against the protocol specification. Previous research has yielded positive results of verifying systems against the graphical language of Live Sequence Charts (LSCs) but has identified key limitations of the process that arise from the lack of support for important constructs of LSCs such as Kleene stars, subcharts, and hierarchical charts. In this paper we further investigate the use of LSCs as a specification language and show how it can be formally translated to automata suitable for input to a model checker for automatic verification of the system under test. We present the translation for subcharts, Kleene stars, and hierarchical charts that are essential for protocol specification and have not been translated to automata before. Further, we successfully translate the BVCI protocol (point to point communication protocol) specification from LSC to an automaton and present a case study of verifying models using the resulting automaton.     

System-level design language standard needed

The combination of SystemVerilog, SystemC, and the property specification language (PSL) promises a powerful and flexible foundation for design. Together, these standards address clear needs for emerging software-rich designs; critical capabilities for these standards include advanced verification features such as solvers and constrained random testing. This combination of standards brings powerful assertion capabilities that, with PSL, provide a bridge to formal verification and the ability to apply assertions across multiple design languages.     

Model variables: cleanly supporting abstraction in design by contract

In design by contract (DBC), assertions are typically written using program variables and query methods. The lack of separation between program code and assertions is confusing, because readers do not know what code is intended for use in the program and what code is only intended for specification purposes. This lack of separation also creates a potential runtime performance penalty, even when runtime assertion checks are disabled, due to both the increased memory footprint of the program and the execution of code maintaining that part of the program's state intended for use in specifications. To solve these problems, we present a new way of writing and checking DBC assertions without directly referring to concrete program states, using ‘model’, i.e. specification‐only, variables and methods. The use of model variables and methods does not incur the problems mentioned above, but it also allow one to write more easily assertions that are abstract, concise, and independent of representation details, and hence more readable and maintainable. We implemented these features in the runtime assertion checker for the Java Modeling Language (JML), but the approach could also be implemented in other DBC tools. Copyright © 2005 John Wiley & Sons, Ltd.     

Executing Formal Specifications with Concurrent Constraint Programming

We have implemented a technique for execution of formal, model-based specifications. The specifications we can execute are written at a level of abstraction that is close to that used in nonexecutable specifications. The specification abstractions supported by our execution technique include using quantified assertions to directly construct post-state values, and indirect definitions of post-state values (definitions that do not use equality). Our approach is based on translating specifications to the concurrent constraint programming language AKL. While there are, of course, expressible assertions that are not executable, our technique is amenable to any formal specification language based on a finite number of intrinsic types and pre- and postcondition assertions.     

Jass — Java with Assertions

Design by Contract, proposed by Meyer for the programming language Eiffel, is a technique that allows run-time checks of specification violation and their treatment during program execution. Jass, Java with assertions, is a Design by Contract extension for Java allowing to annotate Java programs with specifications in the form of assertions. The Jass tool is a pre-compiler that translates annotated into pure Java programs in which compliance with the specification is dynamically tested. Besides the standard Design by Contract features known from classical program verification (e.g. pre- and postconditions, invariants), Jass additionally supports refinement, i.e. subtyping, checks and the novel concept of trace assertions. Trace assertions are used to monitor the dynamic behaviour of objects in time.     

A practical approach to programming with assertions

Embedded assertions have been recognized as a potentially powerful tool for automatic runtime detection of software faults during debugging, testing, maintenance and even production versions of software systems. Yet despite the richness of the notations and the maturity of the techniques and tools that have been developed for programming with assertions, assertions are a development tool that has seen little widespread use in practice. The main reasons seem to be that (1) previous assertion processing tools did not integrate easily with existing programming environments, and (2) it is not well understood what kinds of assertions are most effective at detecting software faults. This paper describes experience using an assertion processing tool that was built to address the concerns of ease-of-use and effectiveness. The tool is called APP, an Annotation PreProcessor for C programs developed in UNIX-based development environments, APP has been used in the development of a variety of software systems over the past five years. Based-on this experience, the paper presents a classification of the assertions that were most effective at detecting faults. While the assertions that are described guard against many common kinds of faults and errors, the very commonness of such faults demonstrates the need for an explicit, high-level, automatically checkable specification of required behavior. It is hoped that the classification presented in this paper will prove to be a useful first step in developing a method of programming with assertions     

An automatic ABV methodology enabling PSL assertions across SLD flow for SOCs modeled in SystemC

Property specification languages and ABV (assertion-based verification) driven by simulation are being recognized by many as essential for verification of today’s increasingly complex designs. In addition, there are few mature approaches that concentrate on improving assertion integration with high-level designs modeled in SystemC. This paper discusses the issues faced within SystemC environments to incorporate PSL (property specification language) assertions. It also proposes an automatic solution that enhances SOC (system on chip) SLD (system level design) flow with PSL assertions embedded into SystemC designs.     

Theorem Proving Guided Development of Formal Assertions in a Resource-Constrained Scheduler for High-Level Synthesis

This paper presents a formal specification and a proof of correctness for the widely-used Force-Directed List Scheduling (FDLS) algorithm for resource-constrained scheduling of data flow graphs in high-level synthesis systems. The proof effort is conducted using a higher-order logic theorem prover. During the proof effort many interesting properties of the FDLS algorithm are discovered. These properties are formally stated and proved in a higher-order logic theorem proving environment. These properties constitute a detailed set of formal assertions and invariants that should hold at various steps in the FDLS algorithm. They are then inserted as programming assertions in the implementation of the FDLS algorithm in a production-strength high-level synthesis system. When turned on, the programming assertions (1) certify whether a specific run of the FDLS algorithm produced correct schedules and, (2) in the event of failure, help discover and isolate programming errors in the FDLS implementation.We present a detailed example and several experiments to demonstrate the effectiveness of these assertions in discovering and isolating errors. Based on this experience, we discuss the role of the formal theorem proving exercise in developing a useful set of assertions for embedding in the scheduler code and argue that in the absence of such a formal proof checking effort, discovering such a useful set of assertions would have been an arduous if not impossible task.     

A top-down methodology for microprocessor validation

A major challenge in today's functional verification is the lack of a formal specification with which to compare the RTL model. We propose a novel top-down verification approach that allows specification of a design above the RTL. From this specification, it is possible to automatically generate assertion models and RTL reference models. We also demonstrate that symbolic simulation and equivalence checking can be applied to verify an RTL design against its specification.     

Checking JML specifications using an extensible software model checking framework

The use of assertions to express correctness properties of programs is growing in practice. Assertions provide a form of lightweight checkable specification that can be very effective in finding defects in programs and in guiding developers to the cause of a problem. A wide variety of assertion languages and associated validation techniques have been developed, but run-time monitoring is commonly thought to be the only practical solution. In this paper, we describe how specifications written in the Java Modeling Language (JML), a general purpose behavioral specification and assertional language for Java, can be validated using a customized model checker built on top of the Bogor model checking framework. Our experience illustrates the need for customized state-space representations and reduction strategies in model checking frameworks in order to effectively check the kind of strong behavioral specifications that can be written in JML. We discuss the advantages and tradeoffs of model checking relative to other specification validation techniques and present data that suggest that the cost of model checking strong specifications is practical for several real programs. This is an extended version of the paper Checking Strong Specifications Using An Extensible Model Checking Framework that appeared in Proceedings of the 10th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, TACAS 2004. This work was supported in part by the U.S. Army Research Office (DAAD190110564), by DARPA/IXO’s PCES program (AFRL Contract F33615-00-C-3044), by NSF (CCR-0306607) by Lockheed Martin, and by Rockwell-Collins.     

On simulation-based probabilistic model checking of mixed-analog circuits

In this paper, we consider verifying properties of mixed-signal circuits, i.e., circuits for which there is an interaction between analog (continuous) and digital (discrete) values. We use a simulation-based approach that consists of evaluating the property on a representative subset of behaviors and answering the question of whether the circuit satisfies the property with a probability greater than or equal to some threshold. We propose a logic adapted to the specification of properties of mixed-signal circuits in the temporal domain as well as in the frequency domain. We also demonstrate the applicability of the method on different models of Δ–Σ modulators for which previous formal verification attempts were too conservative and required excessive computation time.     

Property-directed incremental invariant generation

A fundamental method of analyzing a system such as a program or a circuit is invariance analysis, in which one proves that an assertion holds on all reachable states. Typically, the proof is performed via induction; however, an assertion, while invariant, may not be inductive (provable via induction). Invariant generation procedures construct auxiliary inductive assertions for strengthening the assertion to be inductive. We describe a general method of generating invariants that is incremental and property-directed. Rather than generating one large auxiliary inductive assertion, our method generates many simple assertions, each of which is inductive relative to those generated before it. Incremental generation is amenable to parallelization. Our method is also property-directed in that it generates inductive assertions that are relevant for strengthening the given assertion. We describe two instances of our method: a procedure for generating clausal invariants of finite-state systems and a procedure for generating affine inequalities of numerical infinite-state systems. We provide evidence that our method scales to checking safety properties of some large finite-state systems.     

An assertion-based verification methodology for system-level design

In this paper, we integrate an assertion-based verification methodology with our object-oriented system-level synthesis methodology to address the problem of HW/SW co-verification. In this direction a system-level assertion language is defined. The system-level assertions can be used to monitor the current state of system or flow of transactions. These assertions are automatically converted to “monitor hardware” or “monitor software” during the system-level synthesis process depending on their type and also synthesis style of their corresponding functions. The synthesized assertions are functionally equivalent to their original system-level assertions, and hence, can be reused to verify the system after HW/SW synthesis and also at run-time after system manufacturing. This way, not only system-level assertions are reused in lower-levels of abstraction, but also run-time verification of system is provided. In this paper, we describe the system-level assertion language and explain the corresponding synthesis method in our object-oriented system-level synthesis methodology; however the concept can be applied to any system-level design methodology with modifications to assertion types and synthesis method.