How bytecode verification checks execution states

A virtual machine can receive instructions that ask it to add two values when only one value is available, read a local slot that has never been assigned, or return a value of the wrong category. Discovering those mistakes during execution is possible, but a verifier can reject some of them before the program begins running.

bytecode verification works with descriptions of possible execution states. It follows the instructions and their control-flow connections without choosing a concrete input and running the program to completion. At each reachable instruction, it asks whether the incoming description meets that instruction's contract.

The description leaves information out deliberately. A verifier may need to know that two values are integers without knowing whether they are two and three. It can then check addition across many possible executions using the same category description. The guarantee remains limited to the properties represented in its model.

A small machine with explicit instruction contracts

Consider a hypothetical machine with an operand stack and two local slots. Its values have two categories: integer and reference. Write those categories as I and R in the example. A local slot can also be unusable, meaning the analysis has not established that an instruction may read it as a particular category.

The stack is ordered. Its top value is the one removed first by a pop operation. Describe an empty stack as an empty sequence and a stack holding an integer followed by a reference as the sequence I, R, with R on top. A verifier's stack description records categories and positions, rather than the actual integer or referenced object.

Define pushInt to add an integer-category value to the stack and pushRef to add a reference-category value. Define addInt to require two integers at the top, remove them, and push one integer result. A returnInt instruction requires the stack state specified by the method's integer-return contract.

A store instruction removes the top value and records its category in a selected local slot. A load instruction requires that the selected slot be usable with the expected category, then places that category on the stack. The verifier checks the state before the instruction applies its transition. A plausible result after an instruction cannot repair a missing required input before it.

These rules describe our example machine. A production verifier has its own instruction set, type relations, entry conditions, and exceptional control-flow rules. The example isolates the checking process; a particular virtual machine needs its own complete rules.

Propagate abstract interpretation through both branches

Suppose a method starts with an integer argument in its first local slot and an empty operand stack. Loading that argument produces an integer on the stack. Define branchIfZero to consume an integer and send control to one of two successor instructions, according to its value.

Here the verifier records the integer category without recording the integer itself. It therefore propagates the outgoing state to both successors. It does not predict which branch a future caller will take, and it does not need a sample input to perform the check.

On one path, pushInt places an integer on the stack. On the other, a different pushInt does the same. If both paths then reach the same returnInt instruction, the incoming descriptions agree on the needed category. The two concrete integers can differ while the relevant abstract state remains the same.

This is a form of abstract interpretation. The related topic examines analyses whose state summaries keep expanding and the approximation choices that make them converge. Our small verifier uses a limited category model; it need not introduce a widening rule merely because it analyzes branches or a loop.

The recorded states must cover every execution included in the verification claim. If both branches are possible under the entry conditions, discarding one because an example input did not take it would leave that path unverified. A conclusion drawn from the remaining path would then be too strong for the method as a whole.

Where operand stack types must agree at a join

Now change the branch example. Let the first path arrive at a shared instruction with one integer on its stack. Let the second path arrive with an empty stack. The shared instruction cannot receive one consistent stack-height description under our stipulated join rule. The verifier rejects this join.

The conflicting heights already prevent a valid join, regardless of the values involved. A future instruction that expects one operand would find it available on one incoming path and absent on the other. Averaging the stack heights or choosing the state of whichever path was examined first would conceal the incompatible execution state.

A second mismatch occurs when both paths carry one value, but one carries I and the other R. In this example's strict stack-category model, those states cannot be joined into a value that addInt may treat as an integer. The rule rejects the incompatible categories. A richer verifier could represent other type relationships, but its later instruction checks would still need to justify the operation.

It helps to compare operand stack types with the compiler value identities used in static single assignment. That related representation makes path-dependent value selection explicit at control-flow joins. Choosing which definition supplies a value and proving that an instruction may use its category are different questions, even though both require careful handling of incoming paths.

Local slots need a conservative rule too. Suppose one branch stores an integer in the second slot and the other leaves that slot unusable. The joined state cannot authorize an integer load from it on every incoming path. Our model retains an unusable description for that slot until later instructions establish an appropriate category.

Revisit instructions when incoming states change

The verifier can organize its analysis with a worklist of instructions whose incoming states need processing. It begins with the method's defined entry state. Processing an instruction checks its requirements, computes its outgoing state, and proposes that state to each successor.

If a successor has no recorded incoming state, the proposal becomes its initial description. If it already has one, the verifier applies the join rule. When that joined description changes, the successor is placed on the worklist so its instruction and outgoing transitions can be reconsidered.

A loop can introduce an incoming state after its header has already been examined. A branch near the end of a method can send a state back to an instruction examined earlier. The header's first incoming description may need revision when that back edge is processed. The verifier must account for that additional incoming path before treating the description as stable.

For a simple loop, suppose the stack is empty at its header. The body loads an integer local, adds an integer constant, stores the result back in the same slot, and jumps to the header with an empty stack. The local still has category I and the stack shape is unchanged. Repeating the abstract transition can then leave the recorded header state unchanged, even though concrete integer values may keep changing.

Stabilization means the worklist has no new relevant state changes to propagate. It does not mean the program has completed an execution. Our limited state descriptions may stabilize because the analysis has already captured every category change it represents. The exact numerical history of the loop is absent from those descriptions.

A conservative result can reject a usable program

Conservative path merging can discard distinctions that the verifier would need for a more precise conclusion. If its category model cannot express a distinction needed to prove an operation safe, it may reject the operation rather than assume the distinction will work out favorably during execution.

For example, a method might rely on a relationship between a branch condition and a value selected later. A coarse analysis that records only broad categories may lose that relationship at a join. The program might behave appropriately for all relevant inputs, yet the stipulated verifier may lack the information necessary to establish the required instruction state.

Accepted methods meet the checked invariants under the model's assumptions and boundary. Rejection does not by itself show that every rejected method would fail during a concrete execution. It can also mean that the checking rules could not establish the required property.

A change to those rules needs a reason that preserves the guarantee. Allowing an incompatible state through merely because a sample run succeeded would replace a check over possible paths with an observation of one path. The original question about all reachable instruction states would remain unanswered.

Accepted bytecode can still compute the wrong answer

Consider instructions that push the integers two and three, add them, and return the integer result. Their stack transitions meet the contracts of our machine. If the intended task was to multiply those inputs, the result is still wrong for that task. The verifier has established category and stack compatibility, not the application's intended arithmetic.

An endless loop can also satisfy the selected structural rules. A method can repeatedly store an integer local and jump back with the same valid stack shape. Its abstract state can stabilize while the concrete program continues running. Passing this verifier does not prove termination.

Both examples satisfy the selected instruction-state rules while leaving a different correctness question unresolved. The first asks whether reachable instructions receive permitted execution states. General correctness would also need a specification of the desired behavior and a justified relationship between the program and that specification.

bytecode verification does not authenticate who supplied the program either. A structurally acceptable method can come from an untrusted source. Checking an executable's origin or integrity requires a different boundary and different evidence from the stack-state analysis described here.

Keep runtime and external boundaries visible

The verifier's contract also determines what remains to be checked during execution. Knowing that a value is a reference does not establish every property of the object it names. An operation can have further runtime preconditions that our two-category model does not represent.

For calls to external code, the declared interface establishes a further checking boundary. A verifier may reason from a declared interface to establish the categories consumed and produced by a call. That does not prove every action performed inside the called code. External effects and the validity of the interface assumptions need their own treatment.

A machine can also run out of resources while executing otherwise accepted instructions. The selected state invariants say nothing about how much memory or execution time will be available. The model should not be credited with preventing failures that it does not represent.

A Lenovo IdeaPad 15.6-inch FHD touch laptop is listed with an Intel Core i5-1334U, 16GB DDR4 memory, and a 512GB SSD. Those are host-computer characteristics. They do not identify the verification rules used by a virtual machine or prove that a particular program was checked before execution.

The ASUS Vivobook 14 FHD laptop listing gives another physical host example. It identifies an Intel Core 5 120U and 16GB DDR4 memory. A hardware listing cannot supply evidence about compatible branch joins, permitted stack categories, or what external operations an installed runtime allows.

Report the result with the scope of the checks that produced it. Follow the abstract states from the defined entry through every reachable successor, check the instruction contracts, and revisit joins until the descriptions stabilize. A passing result then supports the selected execution-state invariants, while purpose, termination, external behavior, and runtime resource availability remain separate questions.