Bytecode Verification by Model Checking

Java bytecode verification is traditionally performed by using dataflow analysis. We investigate an alternative based on reducing bytecode verification to model checking. First, we analyze the complexity and scalability of this approach. We show experimentally that, despite an exponential worst-case time complexity, model checking type-correct bytecode using an explicit-state on-the-fly model checker is feasible in practice, and we give a theoretical account why this is the case. Second, we formalize our approach using Isabelle/HOL and prove its correctness. In doing so we build on the formalization of the Java Virtual Machine and dataflow analysis framework of Pusch and Nipkow and extend it to a more general framework for reasoning about model-checking-based analysis. Overall, our work constitutes the first comprehensive investigation of the theory and practice of bytecode verification by model checking. 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 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.     

Provably correct control flow graphs from Java bytecode programs with exceptions

We present an algorithm for extracting control flow graphs from Java bytecode that captures normal as well as exceptional control flow. We prove its correctness, in the sense that the behaviour of the extracted control flow graph is a sound over-approximation of the behaviour of the original program. This makes control flow graphs suitable for performing various static analyses, such as model checking of temporal safety properties. Analysing exceptional control flow for Java bytecode is difficult because of the stack-based nature of the language. We therefore develop the extraction in two stages. In the first, we abstract away from the complications arising from exceptional flows, and relativize the extraction on an oracle that is able to look into the stack and predict the exceptions that can be raised at each instruction. This idealized algorithm provides a specification for concrete extraction algorithms, which have to provide a suitable implementation for the oracle. We prove correctness of the idealized algorithm by means of behavioural simulation. In the second stage, we develop a concrete extraction algorithm that consists of two phases. In the first phase, the program is transformed into a BIR program, a stack-less intermediate representation of Java bytecode, from which the control flow graph is extracted in the second phase. We use this intermediate format because it provides the information needed to implement the oracle, and since it gives rise to more compact graphs. We show that the behaviour of the control flow graph extracted via the intermediate representation is a sound over-approximation of the behaviour of the graph extracted by the direct, idealized algorithm, and thus of the original program. The concrete extraction algorithm is implemented as the ConFlEx tool. A number of test cases are performed to evaluate the efficiency of the algorithm.     

Verified Bytecode Subroutines

Bytecode subroutines are a major complication for Java bytecode verification: They are difficult to fit into the dataflow analysis that the JVM specification suggests. Hence, subroutines are left out or are restricted in most formalizations of the bytecode verifier. We examine the problems that occur with subroutines and give an overview of the most prominent solutions in the literature. Using the theorem prover Isabelle/HOL, we have extended our substantial formalization of the JVM and the bytecode verifier with its proof of correctness by the most general solution for bytecode subroutines. This revised version was published online in August 2006 with corrections to the Cover Date.     

基于缓存策略的Java卡字节码校验

作为一种不可靠的可下载Java程序， Java卡的字节码校验是安全的嵌入式系统所不可缺少的一个部分。由于Java卡本身的空间和运算器的限制，传统的字节码校验并不可取。采用非易失性存储器作为主存， RAM中的一部分空间作为缓存器，并且给出一种相应的Cache调度策略算法，尝试实现一种在卡上的Java卡的字节码校验算法，并且证明了该算法具有较好的可移植性和实现性。     

Checking secure information flow in Java bytecode by code transformation and standard bytecode verification

A method is presented for checking secure information flow in Java bytecode, assuming a multilevel security policy that assigns security levels to the objects. The method exploits the type‐level abstract interpretation of standard bytecode verification to detect illegal information flows. We define an algorithm transforming the original code into another code in such a way that a typing error detected by the Verifier on the transformed code corresponds to a possible illicit information flow in the original code. We present a prototype tool that implements the method and we show an example of application. Copyright © 2004 John Wiley & Sons, Ltd.     

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.     

Lightweight Bytecode Verification

In this paper, we provide a theoretical foundation for and improvements to the existing bytecode verification technology, a critical component of the Java security model, for mobile code used with the Java “micro edition” (J2ME), which is intended for embedded computing devices. In Java, remotely loaded “bytecode” class files are required to be bytecode verified before execution, that is, to undergo a static type analysis that protects the platform's Java run-time system from so-called type confusion attacks such as pointer manipulation. The data flow analysis that performs the verification, however, is beyond the capacity of most embedded devices because of the memory requirements that the typical algorithm will need. We propose to take a proof-carrying code approach to data flow analysis in defining an alternative technique called “lightweight analysis” that uses the notion of a “certificate” to reanalyze a previously analyzed data flow problem, even on poorly resourced platforms. We formally prove that the technique provides the same guarantees as standard bytecode safety verification analysis, in particular that it is “tamper proof” in the sense that the guarantees provided by the analysis cannot be broken by crafting a “false” certificate or by altering the analyzed code. We show how the Java bytecode verifier fits into this framework for an important subset of the Java Virtual Machine; we also show how the resulting “lightweight bytecode verification” technique generalizes and simulates the J2ME verifier (to be expected as Sun's J2ME “K-Virtual machine” verifier was directly based on an early version of this work), as well as Leroy's “on-card bytecode verifier,” which is specifically targeted for Java Cards.     

Bytecode verification on Java smart cards

This article presents a novel approach to the problem of bytecode verification for Java Card applets. By relying on prior off‐card bytecode transformations, we simplify the bytecode verifier and reduce its memory requirements to the point where it can be embedded on a smart card, thus increasing significantly the security of post‐issuance downloading of applets on Java Cards. This article describes the on‐card verification algorithm and the off‐card code transformations, and evaluates experimentally their impact on applet code size. Copyright © 2002 John Wiley & Sons, Ltd.     

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

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

A Space-Aware Bytecode Verifier for Java Cards

The bytecode verification is a key point of the security chain of the Java Platform. This feature is optional in many embedded devices since the memory requirements of the verification process are too high. In this paper we propose a verification algorithm that remarkably reduces the use of the memory by performing the verification during multiple specialized passes. The algorithm reduces the type encoding space by operating on different abstractions of the domain of types. The results of the experiments show that this bytecode verification can be performed directly on small memory systems.     

一种使用CFT的Java卡内字节码校验算法

Java卡字节码校验是构成Java卡安全体系结构的重要组成部分.而传统的Java卡字节码校验由于Java智能卡资源的限制,无法在卡内进行.本文通过对控制流程图和类型推导的分析,提出了基于控制流程树的Java卡卡外翻译过程和卡内校验器算法,详细描述了CFT迁移机理并对于基于CFT的Java卡内字节码校验算法和可行性进行了分析与实践.     

Formal Translation of Bytecode into BoogiePL

Many modern program verifiers translate the program to be verified and its specification into a simple intermediate representation and then compute verification conditions on this representation. Using an intermediate language improves the interoperability of tools and facilitates the computation of small verification conditions. Even though the translation into an intermediate representation is critical for the soundness of a verifier, this step has not been formally verified. In this paper, we formalize the translation of a small subset of Java bytecode into an imperative intermediate language similar to BoogiePL. We prove soundness of the translation by showing that each bytecode method whose BoogiePL translation can be verified, can also be verified in a logic that operates directly on bytecode.     

Instruction-level security typing by abstract interpretation

We present a method based on abstract interpretation to check secure information flow in programs with dynamic structures where input and output channels are associated with security levels. In the concrete operational semantics each value is annotated by a security level dynamically taking into account both the explicit and the implicit information flows. We define a collecting semantics which associates with each program point the set of concrete states of the machine when the point is reached. The abstract domains are obtained from the concrete ones by keeping the security levels and forgetting the actual values. Using this framework, we define an abstract semantics, called instruction-level security typing, that allows us to certify a larger set of programs with respect to the typing approaches to check secure information flow. An efficient implementation is shown, operating a fixpoint iteration similar to that of the Java bytecode verification. This work was partially supported by the Italian COFIN 2004 project “AIDA: Abstract Interpretation Design and Application”.     

PicoJava: a direct execution engine for Java bytecode

Key to the central promise inherent in Java technology-“write once, run anywhere”-is the fact that Java programs run on the Java virtual machine, insulating them from any contact with the underlying hardware. Consequently, Java programs must execute indirectly through a translation layer built into the Java virtual machine. Translation essentially converts Java virtual machine instructions (called bytecodes) into corresponding machine-specific binary instructions. Bytecode is a single image of a program that will execute identically (in principle) on any system equipped with a JVM. The first step toward the development of a new class of Java processors was the creation of the bytecode execution engine itself, called the picoJava core. PicoJava directly executes Java bytecode instructions and provides hardware support for other essential functions of the JVM. Executing bytecode instructions in hardware eliminates the need for dynamic translation, thus extending the useful range of Java bytecode programs to embedded environments. By the end of 1998, Java processors like Sun's microJava 701 should be available for evaluation from several licensees of the picoJava core technology     

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.     

Flow-sensitive, context-sensitive, and object-sensitive information flow control based on program dependence graphs

Information flow control (IFC) checks whether a program can leak secret data to public ports, or whether critical computations can be influenced from outside. But many IFC analyses are imprecise, as they are flow-insensitive, context-insensitive, or object-insensitive; resulting in false alarms. We argue that IFC must better exploit modern program analysis technology, and present an approach based on program dependence graphs (PDG). PDGs have been developed over the last 20 years as a standard device to represent information flow in a program, and today can handle realistic programs. In particular, our dependence graph generator for full Java bytecode is used as the basis for an IFC implementation which is more precise and needs less annotations than traditional approaches. We explain PDGs for sequential and multi-threaded programs, and explain precision gains due to flow-, context-, and object-sensitivity. We then augment PDGs with a lattice of security levels and introduce the flow equations for IFC. We describe algorithms for flow computation in detail and prove their correctness. We then extend flow equations to handle declassification, and prove that our algorithm respects monotonicity of release. Finally, examples demonstrate that our implementation can check realistic sequential programs in full Java bytecode.     

Verified bytecode verification and type-certifying compilation

This article presents a type certifying compiler for a subset of Java and proves the type correctness of the bytecode it generates in the proof assistant Isabelle. The proof is performed by defining a type compiler that emits a type certificate and by showing a correspondence between bytecode and the certificate which entails well-typing. The basis for this work is an extensive formalization of the Java bytecode type system, which is first presented in an abstract, lattice-theoretic setting and then instantiated to Java types.