Tamper-proof annotations, by construction

Dynamic compilation often comes at the price of reduced code quality, because there is not enough time available to perform expensive optimizations. One solution to this problem has been the addition of annotations by the code producer that enable a dynamic code generator on the code consumer's side to shortcut certain analysis and optimization steps. However, code annotation often creates a new problem, in that most such annotations are unsafe-if they become corrupted during transit, then the safety of the target system is in jeopardy.In order to provide safety and to guard against potentially malicious actions, mobile programs are verified by the code recipient. Such verification is needed even when a mobile program originated in a "safe" language such as Java, because the transmission might have been corrupted by an adversary. The advanced optimizations expressed in annotations typically cannot be verified in this manner without repeating the expensive analysis that they were intended to circumvent in the first place.In this paper, we describe a way of encoding mobile programs in a manner that makes it impossible to represent illegal programs in the first place. In such an inherently safe format, any given bit-sequence of sufficient length is guaranteed to map back to a legal program in the original encoding domain, which in our prototype is Java. Hence, any incoming program that meets Java's well-formedness criteria is guaranteed to be legal and no code verification is necessary.Interestingly, our method also enables the tamper-proof transport of annotations along with the program. In our current implementation, we are able to perform escape analysis at the code producer's side and can encode the results of this analysis in a manner that cannot be falsified in transit. Moreover, adding these annotations increases encoding density since it reduces the number of valid choices that need to be represented, so that the addition of the annotations comes at almost no space cost