Gedanken zur Java Bytecode Verifikation

Michael Franz, University of California, Irvine

Der von Sun vorgegebene, auf Datenflussanalyse beruhende,
Verifikationsalgorithmus für Java-Bytecode hat eine Komplexität, die
im schlimmsten Fall quadratisch mit der Codelänge wächst. Wir zeigen,
wie solche Programme mit worst-case Verifikationskomplexität
aussehen. Mit einem nur wenige Kilobyte langen Java Classfile (welches
ein vollkommen "legales" Programm enthält, welches am Ende als
"korrekt" verifiziert wird) kann man so die Virtual Machine auf einer
High-End Workstation fuer mehrere Stunden beschäftigt halten.

Desweiteren stellen wir einen alternativen Verifikationsalgorithmus
vor, welcher stattdessen Verifikation über den Umweg von
SSA-Konstruktion betreibt. Nicht nur ist unser Algorithmus effizienter
als der Standard-Verifikator, sondern das "Beiprodukt" SSA kann direkt
für einen nachfolgenden just-in-time Compilationsschritt verwendet
werden.