Acceleration is a technique for summarising loops by computing a closed-form representation of the loop behaviour. The closed form can be turned into an accelerator, which is a code snippet that skips over intermediate states of the loop to the end of the loop in a single step. Program analysers rely on invariant generation techniques to reason about loops. The state-of-the-art invariant generation techniques, in practice, often struggle to find concise loop invariants, and, instead, degrade into unrolling loops, which is ineffective for non-trivial programs. In this paper, we evaluate experimentally whether loop accelerators enable existing program analysis algorithm to discover loop invariants more reliably and more efficiently. This paper is the first comprehensive study on the synergies between acceleration and invariant generation. We report our experience with a collection of safe and unsafe programs drawn from the Software Verification Competition and the literature.

This paper reports for the first time, the use of a hardware-software combined bounded model checking approach for hardware-software mixed implementations of power management logic. We report significant performance gains as compared to our earlier attempt of extracting a finite quotient transition system from the control software.

Formal methods have gained acceptance in the hardware field through a pragmatic approach that has succeeded in providing systematic, scalable, highly automated, and cost effective treatments for certain stereotypical problems of practical importance. By identifying stereotypical problems, the effort required to develop effective formal methods has been amortized over many applications. We suggest that formal methods can achieve similar industrial success in selected software applications by following the same principles. As an illustration, we examine approaches to the stereotypical problem of interpreter correctness in the presence of timing differences between the specification and implementation interpreters. In hardware, this corresponds to the problem of verifying microprogrammed, pipelined, or superscalar processors, but it has wider applications to any system-hardware or software-that can be considered as an interpreter.

The effectiveness of hardware verification techniques has increased markedly in the past decade. As hardware verification techniques become increasingly powerful the idea of transitioning verification technology to industry can be taken seriously. Nevertheless, powerful decision procedures that can completely automate the verification of certain types of hardware, whether they are BDD based model-checkers or automatic microprocessor verification tools, cannot be adequate on their own for industrial hardware verification. However, a high-level, general-purpose theorem prover with specific capabilities can provide an overall framework in which these tools can be embedded and in which they can then be effectively used for industrial hardware verification.

In a strongly typed system supporting user defined data abstractions, the designer of a data abstraction ought to be careful in choosing the operations for the abstraction. If the operation set chosen is not expressive enough, it might be impossible or inconvenient to implement certain useful functions on the values of the data abstraction. In this paper, we characterize the expressive power of the operation set by defining two properties for data abstractions - expressive completeness and expressive richness. The operation set of an expressively complete data abstraction is adequate enough to implement all computable functions on its values. An expressively rich data abstraction is expressively complete with an operation set that is rich enough to conveniently extract from a value, all relevant information required to reconstruct the value from scratch. Practical applications of the properties of expressiveness introduced are also discussed.