Encode Arithmetic

Replace integer arithmetic with more complex expressions, encoded with Mixed Boolean Expressions (MBA). For example, the following identities can be used to encode integer addition: 

x + y = x - ¬ y - 1
      = (x ⊕ y) + 2·(x ∧ y) 
      = (x ∨ y) + (x ∧ y) 
      = 2·(x ∨ y) - (x ⊕ y)

For example, Tigress might replace 

z = x + y + w

with 

z = (((x ^ y) + ((x & y) << 1)) | w) + 
    (((x ^ y) + ((x & y) << 1)) & w);

Here's a LigerLabs video that discusses this transformation:

OptionArgumentsDescription
--Transform EncodeArithmetic Replace integer arithmetic with more complex expressions.
--EncodeArithmeticKinds builtin, plugins Specify the types to encode. Currently, only integer is available. From version 3.3.3. Default=builtin.
  • builtin = Use Tigress' built-in MBA patterns
  • plugins = Use plugin MBA expressions
--EncodeArithmeticMaxLevel INTSPEC How deep to recurse into expressions. Default=1.
--EncodeArithmeticMaxTransforms INTSPEC How many transformations to perform on each expression. Default=1.
--EncodeArithmeticRepeatTimes INTSPEC How many times to repeat the rewriting process. Equivalent to calling EncodeArithmetic multiple times. From Version 3.3 Default=1.
--EncodeArithmeticDumpFileName string Name of Json file onto which we dump transformed expression. The actual file will be function-name_number_fileName.json. From version 3.3.2. Default=100.
 

Splitting Encoded Expressions

There are two parts to attacking an MBA expression: first you have to find the expression, and then you have to decode it (i.e. turn it back into something resembling it's original form). You can split up expressions to make them more diffiult to locate in the code (both statically and dynamically).

OptionArgumentsDescription
--EncodeArithmeticMaxSplit INTSPEC How many pieces in which to split the transformed expression. From Version 3.3 Default=1.
--EncodeArithmeticAddImplicitFlow BOOLSPEC Add implicit flow to the pieces split out from an encoded expression. You need to set --EncodeArithmeticMaxSplit=value greater than zero for this to take effect. From Version 3.3 Default=false.
--EncodeArithmeticImplicitFlow S-Expression The type of implicit flow to insert. See --AntiTaintAnalysisImplicitFlow for a description. Default=none.
--EncodeArithmeticAddOpaques BOOLSPEC Add opaque predicates to the pieces split out from an encoded expression. You need to set --EncodeArithmeticMaxSplit=value greater than zero for this to take effect. From Version 3.3 Default=false.
 

Diversity

For each operator, there are many possible encodings, and at transformation time, these are selected from randomly.

 

Debugging and Attacking (From version 3.3.2

There have been many recent papers on attacking MBA expressions. To facilitate such attacks you can dump all the transformed expressions onto a Json file for further processing. Simply set --EncodeArithmeticDumpFileName=filename.json.

 

References

Currently, the identities are taken from the book Hacker's Delight.