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
--InitEntropyDebug BOOLSPEC Keep the expected value of each entropy variable in a temporary alongside it, so a wrong value can be recognised at runtime. The option existed but was undocumented before version 4.1.

It is implied by --InitEntropyTrace=use and --InitEntropyTrace=check, which cannot report a wrong value without the expected one to compare against. Note that the expected value is a cleartext copy of what the entropy is supposed to be, so this is a debugging aid rather than something to ship. Default=FALSE.
--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: 


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.