Internal state of the HAVEGE generator and Unpredictability

The internal state of a pseudo-random number generator

On a pseudo-random number generator, at any step in the computation, one can define its internal state as the values of internal variables and tables. This internal state determines the future behavior of the generator and the sequence of numbers that it will generate.

The internal state of the HAVEGE generator

At any moment, one can also define the internal state of the HAVEGE generator as the content of its internal variables (the Walk table, the values of pointers, the values in the RESULT table) and the values of all the volatile hardware states in the processor (branch predictors, instruction and data caches, ...), on the system bus and on the memory system that determines the execution time of the sequences of instructions in HAVEGE.

Unpredictability and particularly irreproducibility is associated with this non-conventional internal state:

If one was able to capture the internal state of the HAVEGE generator at a given point then he/she would be (theoretically) able to replicate the generated sequence from this point until the next occurrence of an interruption or until a new external event on the system bus or the memory system.

Capturing the internal state on the fly is unfeasible:
However, collecting the internal state of the HAVEGE generator is unfeasible at user-level. The user itself cannot collect and reestablish the internal state. For instance, to indirectly determine that a particular cache block was present, one has to access it, but then other internal states are modified (similar to Heisenberg's criteria).

Following the internal state is unfeasible:
Another possible mean to reproduce the sequence would be to set the internal state of the generator in a known state at the beginning of execution. Then, one can try to follow the sequence of instructions through only monitoring external events to the process.
The internal state at the initiation of the generator depends on many parameters such as the exact date of launching (cycle accurate), the exact contents
of the disk, their response time (cycle accurate), the memory content, etc.
Moreover to follow the internal state, one has also to be able to monitor every external events, but also internal events during the initiliazation phase.

An analysis of the internal state of HAVEGE on an UltraSparc II

We describe below part of the volatile information that belongs to the internal state of the HAVEGE generator on an UltraSparc II workstation. A very similar analysis can be done for the other processors.

L1 Data cache From the HAVEGE generator, each of the 512 32-byte cache lines of the L1 data cache can be considered as in one of seven possible states. Either it maps one of the two possible 32-byte blocks A0 or A1 from the Walk table or it maps a block irrelevant from HAVEGE. If it maps a relevant block then it maps only one or or both the 16-byte subblocks. That is, the L1 cache is in one of 7**512 possible states.

L1 instruction cache

The inner loop body in the self modifying walk (just) fits in the L1 instruction cache. The L1 instruction cache is two-way set-associative and branch prediction is embedded in the instructioncache. It features 256 sets.

Only two instruction blocks I0 and I1 from the main HAVEGE loop are mapped onto a given sets of the instruction cache. A LRU replacement policy is implemented on the instruction cache. Therefore, from the HAVEGE perspective, each set has 7 different possible states, B being an instruction block independent from the HAVEGE algorithm: (I0, I1), (I1, I0), ( B, I0), (B, I1), (I0, B), (I1, B) and (B, B). Then from HAVEGE perspective, the instruction cache can be in at least different states 256**7.

On the UltraSparc II, the instruction cache also handles the branch prediction for both targets and directions. For targets, from the HAVEGE perspective, two states are visible: either the target is correct or it is not. For the Ultrasparc II, the main loop in HAVEGE2.0 features 11 iterations, each of these iterations features 21 conditional branches and 2 calls to HardClock. From the HAVEGE perspective, the target prediction generator features at least 2**253 different states. A 2-bit counter is associated with each conditional branch, therefore from the HAVEGE perspective, the branch predictor can be at least in 4**231 different states.

Summary

Considering only the two memorization structures above, it appears that the internal state of the HAVEGE generator includes thousands of binary internal volatile hardware states. A significant fraction of these states are destructed (modified) on each interruption. Each of these states influences the self modifying walks in HAVEGE.

Moreover, many other volatile hardware states (pipeline states, buffer contents and status, L2 caches, etc.) are part of the HAVEGE internal state. Some of the volatile hardware states touched by an operating system interrupt that are part of the internal HAVEGE state are correlated. For instance when an instruction block is evicted then its associated branch prediction information is also evicted, moreover the next instruction block has also a high probability to be also evicted. Nevertheless, there is little correlation between the blocks evicted from the data cache, and the blocks evicted from the instruction cache.