A tag is a random value associated with each coprocessor instruction by the translator. It can be thought of as an identifier but since the current implementation uses byte valued tags, it is not a unique identifier except maybe for very simple applications. When an instruction is executed, its tag is stored along with the result value in the destination register. In the case of instructions without a destination register, the tag is stored in an alternate location, in the heap for the store instruction, or on the stack for the push instruction. Space is reserved to store a tag for each memory location in the coprocessor (registers, heap, stack) and every time the virtual machine stores the result of an instruction, it automatically stores its tag too.

At each location where the value in a register is used by an instruction, the translator identifies the instruction(s) that (may) have computed this value using a well known data flow analysis called reaching definitions. The list of the tags for these instructions is encoded by the translator so that the coprocessor can check that one of the expected tags is present in the register before proceeding.

The coprocessor instruction words are 64 bit long. Opcodes, register numbers, and tags are byte values^[3] so the typical binary operation has room for three expected tag values. Two are used for the left operand and one for the right operand. If the reaching definition analysis shows that the value in a source register may have been computed by more instructions than that, special join instructions are inserted^[4] to check tags and reduce the number of tags reaching the binary operation.

The sample code below mixes Java control flow with coprocessor VM instructions. Tags are shown in square brackets. The value before the opcode is the instruction tag and those after each source register are the expected tags:

[162] VM_ADD R3 R2 [244, 153] R1 [181]
if (predicate) {
[12] VM_LDI R4 1
} else {
[120] VM_LDI R4 -1
}
[124] VM_ADD R2 R4 [12, 120] R3 [162] 

There are two valid streams of VM instructions for this fragment of code, depending on the boolean value of the predicate: (162, 12, 124), or (162, 120, 124). If any of the instructions 162, 12, 120 is removed, it is highly unlikely that the tags for R3 and R4 will match what instruction 124 expects.

Another advantage of tags is that a good part of the instruction word is now random so that the probability that two instructions that perform the same operation on the same source and destination registers have the same instruction word is extremely low. After they are ciphered, virtually all instructions are different, whether they are semantically the same or not.

With tag checking, it becomes possible to link two otherwise unrelated computations by adding a special instruction called a mutual check. This instruction changes the tags of two registers provided they both have the expected tags on entry. If such an instruction is inserted at the end of two computations to link the registers that hold their respective results, it is then impossible to remove or tamper with one computation without losing the result of the other one.

Using mutual checks, it is possible to add new secured instructions to the application that cannot be removed because they are linked to one of the original secured instructions. These instructions can be used to perform integrity checks while the program is running. Call protection is one kind of integrity check that can be implemented semi automatically by the translator. It consists in performing a handshake between the call site of a method and the called method. It can be pictured as :

These extra values are passed on the coprocessor stack or in one of its registers. The value themselves are meaningless ^[5], only the tags are important. If the handshake instructions are linked to other secured instructions inside the caller and the callee, it becomes impossible to remove an existing call or add a new call to the method.

Because Java supports virtual method calls and interfaces, the case where a single method implementation is secured by itself is rare. In practice, call protection applies to groups of methods and call sites connected by the following relationships:

In Java, all the methods in a group share a common signature and name. For each group, the translator derives two sets of tags, the caller set and the callee set, from this common signature, name, and the secret key used to cipher instructions. Then code is inserted in the calling methods to :

And code is inserted in the called methods to:

The callee tag is not set nor checked if the called method raises an exception because this would require the generation of a try/catch block at each secured call site.

To be completed.