Summary form only given. We briefly present a rule-based framework, called EAGLE, shown to be capable of defining and implementing finite trace monitoring logics, including future and past time temporal logic, extended regular expressions, real-time and metric temporal logics (MTL), interval logics, forms of quantified temporal logics, and so on. In this paper we focus on a linear temporal logic (LTL) specialisation of EAGLE. For an initial formula of size m, we establish upper bounds of O(m/sup 2/2/sup m/logm) and O(m/sup 4/2/sup 2m/log/sup 2/m) for the space and time complexity, respectively, of single step evaluation over an input trace. EAGLE has been successfully used, in both LTL and metric LTL forms, to test a real-time controller of an experimental NASA planetary rover.

Abstract In the course of our work in developing formal specifications for components of the Java Virtual Machine (JVM), we have uncovered subtle bugs in the bytecode verifier of Sun's Java 2 SDK 1.2. These bugs, which lead to type safety violations, relate to the naming of reference types. Under certain circumstances, these names can be spoofed through delegating class loaders. These flaws expose some inaccuracies and ambiguities in the JVM specification. We propose several solutions to all of these bugs. In particular, we propose a general solution that makes use of subtype loading constraints. Such constraints complement the equality loading constraints introduced in the Java 2 Platform, and are posted by the bytecode verifier when checking assignment compatibility of class types. By posting constraints instead of resolving and loading classes, the bytecode verifier in our solution has a cleaner interface with the rest of the JVM, and allows lazier loading. We sketch some excerpts of our mathematical formalization of this approach and of its type safety results. Copyright © 2001 John Wiley & Sons, Ltd.

The Java Virtual Machine (JVM) has a novel and powerful mechanism to support lazy, dynamic class loading according to user-definable policies. Class loading directly impacts type safety, on which the security of Java applications is based. Conceptual bugs in the loading mechanism were found in earlier versions of the JVM that lead to type violations. A deeper understanding of the class loading mechanism, through such means as formal analysis, will improve our confidence that no additional bugs are present.The work presented in this paper provides a formal specification of (the relevant aspects of) class loading in the JVM and proves its type safety. Our approach to proving type safety is different from the usual ones since classes are dynamically loaded and full type information may not be statically available. In addition, we propose an improvement in the interaction between class loading and bytecode verification, which is cleaner and enables lazier loading.

A methodology for the design and development of data-parallel applications and components is presented. Data-parallelism is a well understood form of parallel computation, yet developing simple applications can involve substantial efforts to express the problem in low level notations. We describe a process of software development for data-parallel applications starting from high level specifications, generating repeated refinements of designs to match different architectural models and performance constraints, enabling a development activity with cost benefit analysis. Primary issues are algorithm choice, correctness, and efficiency, followed by data decomposition, load balancing, and message passing coordination. Development of a data-parallel multitarget tracking application is used as a case study, showing the progression from high to low level refinements. We conclude by describing tool support for the process.

This paper gives a mathematical specification the Java Virtual Machine (JVM) bytecode verifier. The specification is an axiomatic description of the verifier that makes precise subtle aspects of the JVM semantics and the verifier. We focus on the use of data flow analysis to verify type-correctness and the use of typing contexts to insure global type consistency in the context of an arbitrary strategy for dynamic class loading. The specification types interfaces with sufficient accuracy to eliminate run-time type checks. Our approach is to specify a generic dataflow architecture and formalize the JVM verifier as an instance of this architecture. The emphasis in this paper is on readability of the specification and mathematical clarity. The specification given is consistent with the descriptions in the Lindholm's and Yellin's The Java^TM Virtual Machine Specification. It less committed to certain implementation choices than Sun's version 1.1 implementation. In particular, the specific...

For certain structural testing criteria a significant proportion of tests instances are infeasible in the sense the semantics of the program implies that test data cannot be constructed that meet the test requirement. This paper describes the design and prototype implementation of a structural testing system that uses a theorem prover to determine feasibility of testing requirements and to optimize the number of test cases required to achieve test coverage. Using this approach, we were able to accurately and efficiently determine path feasibility for moderately-sized program units of production code written in a subset of Ada. On these problems, the computer solutions were obtained much faster and with greater accuracy than manual analysis. The paper describes how we formalize test criteria as control flow graph path expressions; how the criteria are mapped to logic formulas; and how we control the complexity of the inference task. It describes the limitations of the system and proposals for its improvement as well as other applications of the analysis.

An automated verification system, Reacto-Verifier (RVF) developed for supporting the design of reliable reactive systems is described. In order to make the formal verification of large and/or complex systems tractable, RVF is enhanced by a knowledge-base manager, a proof manager, and a dependency maintenance procedure. The knowledge base manager supports a flexible use of a large set of axioms and rules derived from the domain theory of the specification language. The proof manager helps handle verification failure and supports off-line development of proofs. The dependency maintenance procedure permits the user to trace the history of a derivation and supports efficient addition and/or retraction of assumptions. RVF can be used both for batch-style automated verification, and for incremental development of verified programs.>