Memory Requirements of Java Bytecode Verification on Limited Devices

Bytecode verification forms the corner stone of the Java security model that ensures the integrity of the runtime environment even in the presence of untrusted code. Limited devices, like Java smart cards, lack the necessary amount of memory to verify the type-safety of Java bytecode on their own. Proof carrying code techniques compute, outside the device, tamper-proof certificates which simplify bytecode verification and pass them along with the code. Rose has developed such an approach for a small subset of the Java bytecode language. In this paper, we extend this approach to real world Java software and develop a precise model of the memory requirements on the device. We use a variant of interval graphs to model liveness of memory regions in the checking step. Based on this model, memory-optimal checking strategies are computed outside the device and attached to the certificate. The underlying type system of the bytecode verifier has been augmented with multi-dimensional arrays and recognizes references to uninitialized Java objects. Our detailed measurements, based on real world Java libraries, demonstrate that the approach offers a substantial improvement in size of certificate over the similar approach taken by the KVM verifier. Worst case memory consumption on the device is examined as well and it turns out that the refinements based on our model save a significant amount of memory