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: the value is held as its residues modulo several pairwise-coprime moduli n_i, plus a fresh random multiple of each, so equal values do not encode equally. Correct at every integer type from version 4.1.0 (before that it silently computed wrong values at unsigned short, unsigned int, long and unsigned long).

    Range limitation. The codec is exact only while the value being reconstructed stays below half the product of its moduli. A single operation on in-range values always satisfies this, so ordinary arithmetic is correct. It is not guaranteed for a value that keeps growing, because the limit applies to the running value and not to the type: a variable ACCUMULATED in a loop (a counter, a running total, a repeated product) eventually passes it, after which the obfuscated program silently computes a different answer from the original. Large multiplications reach the limit fastest, since a product of two w-bit values is 2w bits wide. Prefer poly1 or xor for such variables -- both are exact for every value of every integer type, because they are bijections modulo 2^w and so wrap exactly as C does. Tracked as tigress_issues#183.

  • 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.

The count also decides whether rnc can encode a 64-bit value on a target without 128-bit integers (--Allow128BitInts=false). Its usual decode reconstructs through the product of all the moduli, which must exceed the type's range and so exceeds 64 bits; the narrow alternative (Garner's mixed-radix reconstruction) needs an unsigned type and at least 3 pieces, because a digit step costs twice the width of one modulus. With 2 pieces on a 64-bit value and no 128-bit integers available, rnc reports that it cannot encode the value. From version 4.1.0 Default=2.
--EncodeDataIndividualVariables BOOLSPEC Whether to split a variable into individual pieces or keep the pieces in a struct. Default=false.
--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: