Instruction Ordering Obfuscation

Author

Kamlesh Kantilal (kamlesh@cs.arizona.edu)

Description

This algorithm tries to reorder the instructions within each basic block of a method. The algorithm is as follows. First it creates a list of expression trees within each block. This expression trees are obtained by using the ExprTree class which resides in sandmark.util.exprtree. Next it creates a dependency graph for the expression trees within each block. An expression tree is dependent on another expression tree if there is a WAW, WAR or RAW hazard. Once the dependency graph is obtained it writes out the instruction by doing a topological sort of the nodes in the dependency graph. When there are more than one choices it tries to output the last instruction in the original order first thereby reordering the code.

Example

The original byte code before applying the obfuscation The reordered byte code as a result of applying the obfuscation
0 bipush 100
2 istore 1
3 sipush 10000
6 istore 2
7 lconst 1
8 lstore 3
9 ldc2_w #2
12 lstore 5
14 ldc2_w #4
17 dstore 7
19 bipush 24
21 iload 2
22 imul
23 istore 1
24 iconst 3
25 iload 1
26 imul
27 i2l
28 lload 3
29 lmul
30 l2i
31 istore 2
32 return
0 ldc2_w #4
3 dstore 7
5 ldc2_w #2
8 lstore 5
10 lconst 1
11 lstore 3
12 sipush 10000
15 istore 2
16 bipush 100
18 istore 1
19 bipush 24
21 iload 2
22 imul
23 istore 1
24 iconst 3
25 iload 1
26 imul
27 i2l
28 lload 3
29 lmul
30 l2i
31 istore 2
32 return

Configuration

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

References