Generate Entropy

Some transformations need a source of randomness during execution. For this reason, we can insert statements that collect random values, preferably from variables that are input dependent.

We support two basic ways to collect entropy. You can insert statements within your program that collect values from (hopefully) input-dependent variables. Or, you can spin up a background thread that intermittently does so automatically. Regardless, the randomness we collect is of low quality, but good enough for our purposes.

At a minimum, you should issue the --Transform=InitEntropy transformation, since this creates the variables that hold the entropy. You should issue as many --Transform=UpdateEntropy as you can, making sure you collect entropy from variables that are truly input dependent.

OptionArgumentsDescription
--Transform InitEntropy Add initialization of the entropy variables.
--InitEntropyKinds thread, vars, * Comma-separated list of the kinds of entropy generation to add. Default=thread,var.
  • thread = Generate a background thread to update the entropy
  • vars = Update the entropy from input-dependent variables found in the program
  • * = Same as thread,vars
--InitEntropyThreadName string The name of the generated background thread Default=entropyThread.
--InitEntropyThreadSleep INTSPEC How long the background thread will sleep after having updated the entropy, in nanoseconds Default=1000.
--InitEntropyTrace update, use, check Trace entropy values as they are generated during execution. This used to be a boolean, but from version 4.0, it can take on multiple values. Default=NONE.
  • update = Print the generated structure
  • use = Print every generation of an entropy value
  • check = Print only if an entropy value is wrong
--InitEntropyObfuscate BOOLSPEC Apply some light obfuscation on top of the entropy-generating expression. Default=FALSE.

OptionArgumentsDescription
--Transform UpdateEntropy Add updates to the entropy variables.
--UpdateEntropyTrace update, use, check Trace entropy values as they are updated during execution. This used to be a boolean, but from version 4.0, it can take on multiple values. Default=NONE.
  • update = Print the generated structure
  • use = Print every generation of an entropy value
  • check = Print only if an entropy value is wrong
--UpdateEntropyObfuscate BOOLSPEC Apply some light obfuscation on top of the entropy-generating expression. Default=FALSE.
--UpdateEntropyKinds thread, vars, annotations, * Comma-separated list of the kinds of entropy generation to add. Default=thread,var.
  • thread = Generate a background thread to update the entropy.
  • vars = Update the entropy from input-dependent variables found in the program.
  • annotations = Indicate in the source code which variables should be added to the entropy, such as: ENTROPY_VARIABLE(x).
  • * = Same as thread,vars
--UpdateEntropyVars IDENTSPEC Add to the entropy variables from these variables. Default=*.
 

Examples

The command below initializes the entropy variables in main, and then collects randomness from variables x,y,z in function inputData, from variable packet in function acceptNetworkPacket, and from all variables in function random. It also spins up a background thread from the tigress_init function. The thread function is called ENTROPYTHREAD, and it sleeps for 1000000 nanoseconds between updates. 

tigress --Seed=0 --Verbosity=1 --Environment=... \
    --Transform=InitEntropy \
       --InitEntropyThreadName=ENTROPYTHREAD \
       --InitEntropyThreadSleep=1000000\
       --InitEntropyKinds=vars,thread \
       --InitEntropyTrace=true \
    --Transform=UpdateEntropy \
       --Functions=inputData \
       --UpdateEntropyKinds=vars \
       --UpdateEntropyTrace=true \
       --UpdateEntropyVars=x,y,z \
    --Transform=UpdateEntropy \
       --Functions=acceptNetworkPacket \
       --UpdateEntropyKinds=vars \
       --UpdateEntropyTrace=true \
       --UpdateEntropyVars=packet \
    --Transform=UpdateEntropy \
       --Functions=random \
       --UpdateEntropyKinds=vars \
       --UpdateEntropyTrace=true \
       --UpdateEntropyVars=p\* \
    --Transform=UpdateEntropy \
       --Functions=tigress_init \
       --UpdateEntropyKinds=thread \
 

Source code annotations

Instead of using --UpdateEntropyVars you can use annotations in the source code to directly indicate which variables should contribute to entropy calculation: 

#include "tigress.h"

int foo (int x) {
  ...
  ENTROPY_VARIABLE(x);
  float f = x + 10;
  ENTROPY_VARIABLE(f);
  ...
}

You should place these annotations in locations where the variable depends on input. Here's the Tigress command: 

tigress ... \
   --Transform=InitEntropy \
       --Functions=main \
       --InitEntropyKinds=annotations \
    --Transform=UpdateEntropy \
       --Functions=foo \
       --UpdateEntropyKinds=annotations \
 

References

The idea of using threads and CPU performance counters to generate random numbers was first introduced by Adrian Colesa, Radu Tudoran, and Sebastian Banescu in Software Random Number Generation Based on Race Conditions. Our implementation isn't as advanced at theirs since it only uses X86's rdtsc counter. Unfortunately, other counters are not available from user mode.