Encode Data

Encode integer variables so that they have a non-standard data representation. The goal is for a variable's real value (and the values of intermediate expressions used to compute it) to never be revealed, until it is printed or otherwise escapes the program. For example, an integer variable v could be replaced with: 

v' = a*v + b

where a is a random odd integer and b a random integer. For example, given this program 

int main () {
  int arg1 = ...
  int arg2 = ...
  int a = arg1;
  int b = arg2;
  int x = a*b;
  printf("x=%i\n",x);
}

Tigress might produce the following: 

a = 1789355803 * arg1 + 1391591831;
b = 1789355803 * arg2 + 1391591831;
x = ((3537017619 * (a * b) - 3670706997 * a) - 3670706997 * b) + 3171898074;
printf("x=%i\n", -757949677 * x - 3670706997);

 

Usage

A typical invokation of this transformation lists a collection of local variables and formal parameters, and global variables: 

   --Transform=EncodeData \
      --GlobalVariables='g1,g2' \
      --LocalVariables='fun1:L1,L2;fun2:L3' \
      --EncodeDataCodecs=poly1

These variables should all be integers, pointers to integers, arrays of integers, or combinations of these. In the example above, g1 may be an int, L1 an int*, L2 an array of ints, and L3 an array of pointers to ints.

If you want the return value of a function fun1 to be encoded, specify it this way: 

   --Transform=EncodeData \
      --LocalVariables='fun1:return' \
      --EncodeDataCodecs=poly1

OptionArgumentsDescription
--Transform EncodeData Replace integer variables with a different encoding. Use --GlobalVariables and --LocalVariables to specify the variables that should be transformed. In addition to the variables specifed, any other variables that are related through aliasing will be transformed. Only integer variables, arrays of integers, and pointers to integers are currently supported. Avoid structs, since our alias analysis algorithm conflates all fields.
--EncodeDataCodecs poly1, xor, xorfloat, add, rnc, poly_xor, xor_poly, poly_rnc, xor_rnc, * Comma-separated list of the kinds of codecs that may be used. Only poly1 currently makes sense; avoid the others. Default=poly1.
  • poly1 = Linear transformation of the form a*x+b.
  • xor = Exclusive-or with a constant.
  • xorfloat = Exclusive-or with a constant on floating point values.
  • add = Add a constant and promote to next largest integer type. Will fail for the largest integer type.
  • rnc = Residue Number Coding
  • poly_xor = First encode with poly1, then with xor
  • xor_poly = First encode with xor, then with poly1
  • poly_rnc = First encode with poly1, then with rnc
  • xor_rnc = First encode with xor, then with rnc
  • * = All options
--EncodeDataDebug pointsToGraph, aliasConstraints, aliasProgress, aliasDebug, aliasTypes, mayAliasRelationships, traceUpdates Debugging options. Default=NONE.
  • pointsToGraph = Print the alias graph.
  • aliasConstraints = Print alias constraints.
  • aliasProgress = Print progress of the alias computation.
  • aliasDebug = Print alias debugging information
  • aliasTypes = Print alias type information
  • mayAliasRelationships = Print may alias relationships
  • traceUpdates = Trace how functions are transformed
--EncodeDataOptimize Simplify expressions. Default=true.
--EncodeDataTrace Trace execution of encoded data. Default=false.
--EncodeDataNumberOfPieces INTSPEC Number of pieces in which to break up a value. Only applies to codecs that split values, such as rnc. Default=2.
--EncodeDataStorage struct, split How variabls split into multiple pieces should be stored. Default=struct.
  • struct = Store pieces in a struct.
  • split = Store pieces in individual variables. Only partially implemented.
 

Issues

If you ask Tigress to encode a variable x, then all variables related to x through aliasing must also be encoded. In cases where our alias analysis algorithm isn't precise enough, encoding will fail at transformation time. For large programs, the alias analysis routine may take a very long time.

 

References

This transformation is based on ideas from several Cloakware/IRDETO papers and patents: