Result: Verified Java Bytecode Verification

The bytecode verifier is an important part of Java's security architecture. This thesis presents a fully formal, executable, and machine checked specification of a representative subset of the Java Virtual Machine and its bytecode verifier together with a proof that the bytecode verifier is safe. The specification consists of an abstract framework for bytecode verification which is instantiated step by step with increasingly expressive type systems covering all of the interesting and complex properties of Java bytecode verification: classes, objects, inheritance, virtual methods, exception handling, constructors, object initialization, bytecode subroutines, and arrays. The instantiation yields two executable verified bytecode verifiers: the iterative data flow algorithm of the standard Java platform and also a lightweight bytecode verifier for resource-constrained devices such as smart cards. All specifications and proofs have been carried out in the interactive theorem prover Isabelle/HOL. Large parts of the proofs are written in the human-readable proof language Isabelle/Isar making it possible to understand and reproduce the reasoning independently of the theorem prover. All formal proofs in this thesis are machine checked and generated directly from Isabelle sources.
Der Bytecode Verifier ist ein essentieller Bestandteil der Sicherheitsarchiktektur der Programmierplattform Java. Die Dissertation präsentiert eine formale, ausführbare Spezifikation des Bytecode Verifiers sowie den Beweis, dass dieser korrekt ist. Die Formalisierung im Theorembeweiser Isabelle besteht aus einem abstrakten Framework für Bytecode-Verifikation, das mit zunehmend ausdrucksstarken Typsystemen instantiiert wird. Diese decken sämtliche interessanten Eigenschaften der Java-Plattform ab: Klassen, Objekte, virtuelle Methoden, Vererbung, Ausnahmebehandlung, Konstruktoren, Objekt-Initialisierung, Subroutinen und Felder. Die Formalisierung liefert zwei ausführbare verifizierte Bytecode Verifier: den iterativen Standard-Algorithmus sowie einen Lightweight Bytecode Verifier für Geräte mit eingeschränkten Ressourcen.