Model checking JAVA programs using JAVA PathFinder

This paper describes a translator called Java PathFinder (Jpf), which translates from Java to Promela, the modeling language of the Spin model checker. Jpf translates a given Java program into a Promela model, which then can be model checked using Spin. The Java program may contain assertions, which are translated into similar assertions in the Promela model. The Spin model checker will then look for deadlocks and violations of any stated assertions. Jpf generates a Promela model with the same state space characteristics as the Java program. Hence, the Java program must have a finite and tractable state space. This work should be seen in a broader attempt to make formal methods applicable within NASA’s areas such as space, aviation, and robotics. The work is a continuation of an effort to formally analyze, using Spin, a multi-threaded operating system for the Deep-Space 1 space craft, and of previous work in applying existing model checkers and theorem provers to real applications.     

Using SPIN for automated debugging of infinite executions of Java programs

This paper presents an approach for the automated debugging of reactive and concurrent Java programs, combining model checking and runtime monitoring. Runtime monitoring is used to transform the Java execution traces into the input for the model checker, the purpose of which is twofold. First, it checks these execution traces against properties written in linear temporal logic (LTL), which represent desirable or undesirable behaviors. Second, it produces several execution traces for a single Java program by generating test inputs and exploring different schedulings in multithreaded programs. As state explosion is the main drawback to model checking, we propose two abstraction approaches to reduce the memory requirements when storing Java states. We also present the formal framework to clarify which kinds of LTL safety and liveness formulas can be correctly analysed with each abstraction for both finite and infinite program executions. A major advantage of our approach comes from the model checker, which stores the trace of each failed execution, allowing the programmer to replay these executions to locate the bugs. Our current implementation, the tool TJT, uses Spin as the model checker and the Java Debug Interface (JDI) for runtime monitoring. TJT is presented as an Eclipse plug-in and it has been successfully applied to debug complex public Java programs.     

Java过程蓝图

1 引言计算机应用正进入网络时代,Java是一种广泛使用的网络编程语言,被称之为网络上的“世界语”。Java作为一种程序设计语言不仅具有简单、面向对象、分布式、解释执行、鲁棒、安全、平台无关、可移植、高性能、多线程以及动态性等特点,更重要的是它支持以网络为中心的新型计算模式——Java计算模式,从而使Ja-     

Uppaal到PVS的时间自动机翻译器

Uppaal是一种对实时系统模型进行建模和验证的工具,PVS（Prototype Verification System）是开发和分析形式化规格说明的原型证明系统。介绍了Uppaal2PVS翻译器的设计与实现,给出了一种将用Uppaal生成的时间自动机规格说明翻译成PVS文件的方法,从而将模型检查问题转换成了定理证明问题,解决了潜在的状态空间爆炸问题。最后给出了一个实例。     

Multimedia Authoring with Hierarchical Timed Stream Petri Nets and Java

The expected benefits of modeling documents using a formal technique are twofold. First, the document's model can be checked against logical errors and unsatisfied timing constraints. Second, the same model can serve as reference for implementation purposes. In this context, the paper discusses a methodology for multimedia document design and implementation on heterogeneous and distributed platforms. The design trajectory starts with document modeling in Hierarchical Timed Stream Petri Nets, goes on with model checking against design errors, and continues with automatic translation of HTSPN models into a Java application. A tool prototype supports the methodology with a document editor, a simulator and a HTSPN to Java generator. Its use is exemplified on a guided tour of Florianopolis City, Brazil.     

Cobol到Java翻译中的数据类型转换方法

将Cobol代码迁移到新的平台，如Java是减轻Cobol代码维护负担的一个有效方法．怎样将Cobol数据平滑迁移到新平台则是必须解决的基本问题之一．以前的大部分研究工作都直接将Cob01数据映射到现代程序设计语言中的基本数据类型，比如int，float等．但是，这种简单映射并不能保持原来的Cobol语义，从而导致目标码并不能与原来的代码运行一致．首先利用数据抽象技术对Cobol数据进行初步建模，在此基础上进一步提出了一个纯Java的功能等价的封装方法，可以有效地将Cobol数据描述映射到Java类型系统．该方法已经在一个Cobol2Java翻译系统——C2J翻译器中得到实现，并且应用于一个近400万行的真实银行商用系统．实验结果表明，此方法可以在保持功能等价的情况下，将Cobol数据无需手工干预地迁移到Java平台．     

SPI演算规范的建模、实现验证研究

针对安全协议安全属性是否满足，缺乏有效性能评价方法的现状，大都使用SPI演算或相近的进程代数方法进行建模。利用这种方法不仅能够有效地形式化描述安全协议，并且能够对安全协议进行多方面的系统评价，但基本上没有说明怎么样寻找设计合适的验证工具，验证其安全属性实现的正确性。本文引入基于SPI演算的验证工具SPRITE来保证建模过程正确性，并设计给出实现映射的具体方法。本方法通过对典型的WOO-LAM单向认证协议予以说明，最后SPRITE产生的具体JAVA代码，给出了安全协议的安全属性，使形式化描述的协议的安全属性是否满足更接近于人的理解而不仅只是机器的解释。     

The KeY tool

KeY is a tool that provides facilities for formal specification and verification of programs within a commercial platform for UML based software development. Using the KeY tool, formal methods and object-oriented development techniques are applied in an integrated manner. Formal specification is performed using the Object Constraint Language (OCL), which is part of the UML standard. KeY provides support for the authoring and formal analysis of OCL constraints. The target language of KeY based development is Java Card DL, a proper subset of Java for smart card applications and embedded systems. KeY uses a dynamic logic for Java Card DL to express proof obligations, and provides a state-of-the-art theorem prover for interactive and automated verification. Apart from its integration into UML based software development, a characteristic feature of KeY is that formal specification and verification can be introduced incrementally.     

Model Checking Programs

The majority of work carried out in the formal methods community throughout the last three decades has (for good reasons) been devoted to special languages designed to make it easier to experiment with mechanized formal methods such as theorem provers, proof checkers and model checkers. In this paper we will attempt to give convincing arguments for why we believe it is time for the formal methods community to shift some of its attention towards the analysis of programs written in modern programming languages. In keeping with this philosophy we have developed a verification and testing environment for Java, called Java PathFinder (JPF), which integrates model checking, program analysis and testing. Part of this work has consisted of building a new Java Virtual Machine that interprets Java bytecode. JPF uses state compression to handle big states, and partial order and symmetry reduction, slicing, abstraction, and runtime analysis techniques to reduce the state space. JPF has been applied to a real-time avionics operating system developed at Honeywell, illustrating an intricate error, and to a model of a spacecraft controller, illustrating the combination of abstraction, runtime analysis, and slicing with model checking.     

Formalization and Analysis of Class Loading in Java

Since Java security relies on the type-safety of the JVM, many formal approaches have been taken in order to prove the soundness of the JVM. This paper presents a new formalization of the JVM and proves its soundness. It is the first model to employ dynamic linking and bytecode verification to analyze the loading constraint scheme of Java2. The key concept required for proving the soundness of the new model is augmented value typing, which is defined from ordinary value typing combined with the loading constraint scheme. In proving the soundness of the model, it is shown that there are some problems inside the current reference implementation of the JVM with respect to our model. We also analyze the findClass scheme, newly introduced in Java2. The same analysis also shows why applets cannot exploit the type-spoofing vulnerability reported by Saraswat, which led to the introduction of the loading constraint scheme.     

Lightweight extraction of object models from bytecode

A program's object model captures the essence of its design. For some programs, no object model was developed during design; for others, an object model exists but may be out-of-sync with the code. This paper describes a tool that automatically extracts an object model from the class-files of a Java program. Unlike existing tools, it handles container classes by inferring the types of elements stored in a container and eliding the container itself. This feature is crucial for obtaining models that show the structure of the abstract state and bear some relation to conceptual models. Although the tool performs only a simple, heuristic analysis that is almost entirely local, the resulting object model is surprisingly accurate. The paper explains what object models are and why they are useful; describes the analysis, its assumptions, and limitations; evaluates the tool for accuracy, and illustrates its use on a suite of sample programs     

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     

Worst‐case execution time analysis for a Java processor

In this paper, we propose a solution for a worst‐case execution time (WCET) analyzable Java system: a combination of a time‐predictable Java processor and a tool that performs WCET analysis at Java bytecode level. We present a Java processor, called JOP, designed for time‐predictable execution of real‐time tasks. The execution time of bytecodes, the instructions of the Java virtual machine, is known to cycle accuracy for JOP. Therefore, JOP simplifies the low‐level WCET analysis. A method cache, which fills whole Java methods into the cache, simplifies cache analysis. The WCET analysis tool is based on integer linear programming. The tool performs the low‐level analysis at the bytecode level and integrates the method cache analysis. An integrated data‐flow analysis performs receiver‐type analysis for dynamic method dispatches and loop‐bound analysis. Furthermore, a model checking approach to WCET analysis is presented where the method cache can be exactly simulated. The combination of the time‐predictable Java processor and the WCET analysis tool is evaluated with standard WCET benchmarks and three real‐time applications. The WCET friendly architecture of JOP and the integrated method cache analysis yield tight WCET bounds. Comparing the exact, but expensive, model checking‐based analysis of the method cache with the static approach demonstrates that the static approximation of the method cache is sufficiently tight for practical purposes. Copyright © 2010 John Wiley & Sons, Ltd.     

Model interoperability via Model Driven Development

Among the factors that contribute to the inherent complexity of the software development process is the gap between the design and the formal analysis domains. Software design is often considered a human oriented task while the analysis phase draws on formal representation and mathematical foundations. An example of this dichotomy is the use of UML for the software design phase and Petri Nets for the analysis; a separation of concerns that leads to the creation of heterogeneous models. Although UML is widely accepted as a language that can be used to model the structural and behavioural aspects of a system, its lack of mathematical foundations is seen as a serious impediment to rigorous analysis. Petri Nets on the other hand have a strong mathematical basis that are well suited for formal analysis; they lack however the appeal and the ease-of-use of UML. A pressing concern for software developers is how to bridge the gap between these domains and allow for model interoperability and the integration of different toolsets across them, and thus reduce the complexity of the software development process. The aim of this paper is to present a Model Driven Development (MDD) model transformation which supports a seamless transition between UML and Petri Nets. This is achieved by model interoperability from UML Sequence Diagrams to Petri Nets and supported by tool integration. The model transformation framework allows a software system to be designed in terms of UML Sequence Diagrams and subjected to formal analysis by taking advantage of the strong mathematical framework of Petri Nets. The behaviour of a Personal Area Network will be used to illustrate the proposed approach and to highlight model interoperability and tool integration through the design, the transformation and the analysis phases.