Memory Requirements of Java Bytecode Verification on Limited Devices
Karsten Klohs, Uwe Kastens
University of Paderborn, Germany
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 significant amounts
of memory.
Keywords: Proof Carrying Code, Bytecode Verification, Limited Devices, Java Card