Bogus Predicates Obfuscation Algorithm

Authors

Ashok Purushotham (ashok@cs.arizona.edu)
Rathna Prabhu Rajendran (prabhu@cs.arizona.edu)

Description

This is an algorithm that implements simple boolean identities and adds them to the user's code. Our aim is to embed opaquely true constructs which must be stealthy. So we have selected some constructs based on algebraic properties and known facts in mathematics. For example, we know for all x,y in I, (7y2 - 1) is not equal to x2. A list of all the available constructs is maintained. At runtime, whenever we encounter a conditional expression, we randomly select one among these to append to the current expression. Since the expression that we add is opaquely true, but the reverse engineer has to try out many inputs to find that this added expression is indeed opaquely true,if he is not aware of mathematical properties.

Example

Here is an example of the original method and its transformation on applying Bogus Predicates Algorithm:

        main(){             main(){
          int a=10;           int a=10;
          int b=20;           int b=20;  
          if (a<30)            int c;
             b=a+99;          if (a<30 && c(c+1)%2 == 0)
        }                       b=a+99;
                            }
    

The original byte code in a conditional expression was:

        iload_1
        bipush 7
        if_icmpne 29
    

The new added byte code as a result of our algorithm is:

        iload_1
        bipush 7
        if_icmpne 29
        iload_3
        dup
        iconst_1
        iadd
        imul
        iconst_2
        irem
        iconst_0
        if_icmpne 29
    

Configuration

There are no extra configuration parameters necessary to run this obfuscator.

References