Java Bytecode Verification: Algorithms and Formalizations

Bytecode verification is a crucial security component for Java applets, on the Web and on embedded devices such as smart cards. This paper reviews the various bytecode verification algorithms that have been proposed, recasts them in a common framework of dataflow analysis, and surveys the use of proof assistants to specify bytecode verification and prove its correctness. This revised version was published online in August 2006 with corrections to the Cover Date.     

Kleene Algebra and Bytecode Verification

Most standard approaches to the static analysis of programs, such as the popular worklist method, are first-order methods that inductively annotate program points with abstract values. In [6] we introduced a second-order approach based on Kleene algebra. In this approach, the primary objects of interest are not the abstract data values, but the transfer functions that manipulate them. These elements form a left-handed Kleene algebra. The dataflow labeling is not achieved by inductively labeling the program with abstract values, but rather by computing the star (Kleene closure) of a matrix of transfer functions. In this paper we show how this general framework applies to the problem of Java bytecode verification. We show how to specify transfer functions arising in Java bytecode verification in such a way that the Kleene algebra operations (join, composition, star) can be computed efficiently. We also give a hybrid dataflow analysis algorithm that computes the closure of a matrix on a cutset of the control flow graph, thereby avoiding the recalculation of dataflow information when there are cycles in the graph. This method could potentially improve the performance over the standard worklist algorithm when a small cutset can be found.     

基于混合模式的Java卡字节码优化器

Java卡是一种基于Java语言的智能卡。因为智能卡的空间和处理器速度的约束,一个应用程序在Java卡上运行时面临的最大问题是存储空间的不足和对程序执行时间的严格限制。因此,对下载到卡中的字节码进行优化是十分必要的。本文提出了一种综合使用扩展指令集和分段压缩算法的Java卡字节码优化器的设计方案,通过对字节码文件的优化,可得到占用空间较少且没有降低执行速率的字节码文件。     

Tool-Assisted Specification and Verification of Typed Low-Level Languages

Bytecode verification is one of the key security functions of several architectures for mobile and embedded code, including Java, Java Card, and .NET. Over the past few years, its formal correctness has been studied extensively by academia and industry, using general-purpose theorem provers. The objective of our work is to facilitate such endeavors by providing a dedicated environment for establishing the correctness of bytecode verification within a proof assistant. The environment, called Jakarta, exploits a methodology that casts the correctness of bytecode verification relatively to a defensive virtual machine that performs checks at run-time and to an offensive one that does not; it can be summarized as stating that the two machines coincide on programs that pass bytecode verification. Such a methodology has been used successfully to prove the correctness of the Java Card bytecode verifier and may potentially be applied to many similar problems. One definite advantage of the methodology is that it is amenable to automation. Indeed, Jakarta automates the construction of an offensive virtual machine and a bytecode verifier from a defensive machine, and the proofs of correctness of the bytecode verifier. We illustrate the principles of Jakarta on a simple low-level language extended with subroutines and discuss its usefulness to proving the correctness of the Java Card platform.     

Exploring the Interaction between Java's Implicitly Thrown Exceptions and Instruction Scheduling

The frequent occurrence of implicitly thrown exceptions poses one of the challenges present in a Java compiler. Not only do these implicitly thrown exceptions directly affect the performance by requiring explicit checks, they also indirectly impact the performance by restricting code movement in order to satisfy the precise exception model in Java. In particular, instruction scheduling is one transformation that is restricted by implicitly thrown exceptions due to the heavy reliance on reordering instructions to exploit maximum hardware performance. The goal of this study is two-fold: first, investigate the degree to which implicitly thrown exceptions in Java hinder instruction scheduling, and second, find new techniques for allowing more efficient execution of Java programs containing implicitly thrown exceptions. Experimental results show that with aggressive scheduling techniques, such as superblock scheduling, the negative performance impact can be greatly reduced.     

一种新的Java智能卡上字节码校验算法

Java智能卡上的字节码校验是保障Java卡安全的重要手段。但是,由于Java智能卡本身的空间和运算器的限制,传统的字节码校验算法无法在Java智能卡上实现。为了解决此问题,本文在分析了现有方法的特点和不足的基础上提出了一种基于有向分枝图和缓存策略的字节码校验算法。效率分析和实践表明,该算法是一种可以在Java智能卡上实现
现的高效算法。     

一种精确程序最坏执行时间分析方法

Java语言的动态特性使程序的最坏执行时间分析较悲观和难以预测,提出一种精确最坏执行时间分析方法,在高层分析中,引入一种标记方法,对带有标记的Java类文件进行反编译提取控制流程,得到每一个基本块中的Java 字节码指令的最坏情况下的执行次数,在底层分析中,建立结合流水线和高级缓存影响的时间模型,得到每条指令所对应的执行时间,最后结合高层分析和底层分析的结果得到程序的最坏情况下的执行时间。实验表明,该方法可以使对实时Java 程序的最坏情况执行时间预测更加安全和精确。     

Improving the Decompilation of Java Bytecode to Prolog by Partial Evaluation

The interpretative approach to compilation allows compiling programs by partially evaluating an interpreter w.r.t. a source program. This approach, though very attractive in principle, has not been widely applied in practice mainly because of the difficulty in finding a partial evaluation strategy which always obtain “quality” compiled programs. In spite of this, in recent work we have performed a proof of concept of that, at least for some examples, this approach can be applied to decompile Java bytecode into Prolog. This allows applying existing advanced tools for analysis of logic programs in order to verify Java bytecode. However, successful partial evaluation of an interpreter for (a realistic subset of) Java bytecode is a rather challenging problem. The aim of this work is to improve the performance of the decompilation process above in two respects. First, we would like to obtain quality decompiled programs, i.e., simple and small. We refer to this as the effectiveness of the decompilation. Second, we would like the decompilation process to be as efficient as possible, both in terms of time and memory usage, in order to scale up in practice. We refer to this as the efficiency of the decompilation. With this aim, we propose several techniques for improving the partial evaluation strategy. We argue that our experimental results show that we are able to improve significantly the efficiency and effectiveness of the decompilation process.     

Completeness of a Bytecode Verifier and a Certifying Java-to-JVM Compiler

During an attempt to prove that the Java-to-JVM compiler generates code that is accepted by the bytecode verifier, we found examples of legal Java programs that are rejected by the verifier. We propose therefore to restrict the rules of definite assignment for the try-finally statement as well as for the labeled statement so that the example programs are no longer allowed. Then we can prove, using the framework of Abstract State Machines, that each program from the slightly restricted Java language is accepted by the Bytecode Verifier. In the proof we use a new notion of bytecode type assignment without subroutine call stacks. This revised version was published online in August 2006 with corrections to the Cover Date.     

API文档缺陷自动检测和修复方法

在为了完善应用程序编程接口（application programming interface,API）文档,提出了基于程序静态分析和自然语言处理的自动检测和修复API文档缺陷的方法。该方法能够自动检测和修复API文档缺陷。实验中缺陷检测结果的准确率和召回率分别达到74.6%和81.4%,能够较为准确地检测到Java API的文档缺陷。在进一步的实验中还对API文档的修复功能进行了评估,结果表明生成的文档正确且简洁,可以有效地修复API文档缺陷。     

A Type System for the Java Bytecode Language and Verifier

The Java Virtual Machine executes bytecode programs that may have been sent from other, possibly untrusted, locations on the network. Since the transmitted code may be written by a malicious party or corrupted during network transmission, the Java Virtual Machine contains a bytecode verifier to check the code for type errors before it is run. As illustrated by reported attacks on Java run-time systems, the verifier is essential for system security. However, no formal specification of the bytecode verifier exists in the Java Virtual Machine Specification published by Sun. In this paper, we develop such a specification in the form of a type system for a subset of the bytecode language. The subset includes classes, interfaces, constructors, methods, exceptions, and bytecode subroutines. We also present a type checking algorithm and prototype bytecode verifier implementation, and we conclude by discussing other applications of this work. For example, we show how to extend our formal system to check other program properties, such as the correct use of object locks. This revised version was published online in August 2006 with corrections to the Cover Date.     

JVM Bytecode Verification Without Dataflow Analysis

Bytecode verification algorithms are traditionally based on dataflow analysis. We present an alternative algorithm that first restructures the bytecode and then infers a type signature for each method in a manner typical of functional programming languages. We also give an operational semantics to an algebra of structured bytecode and thereby prove both that restructuring preserves semantics and that our type inference is sound.     

基于Java的编译原理课程案例教学方法初探

针对编译原理教学实际,在分析和修改工业级开源编译器实现代码的基础上,提出一个基于Java的编译原理课程案例教学过程,结合Java这种日益普及的面向对象程序设计语言,这种教学过程在编译原理课程教学方面取得良好效果。