>
 

This is a classic control-flow transformation that removes structured flow.

Flattening is useful as a precursor to other transformations. For example, our AntiBranchAnalysis transformation flattens a function prior to replacing direct branches by calls to a branch function since this creates more opportunities for encoding. Also, the Merge transformation can optionally flatten functions before merging them, thus more thoroughly mixing their code.

 

Diversity

There are several sources of diversity:  

Dispatch

These are the four kinds of block dispatch we currently support, and what a reursive factorial function looks like after transformation:  

Conditional Branches

If the --FlattenConditionalKinds=flag is set, there will be no explicit conditional tests in the code. Rather, they will be transformed into an assembly code snippet (x86 only, at this point) that does the comparison, extracts the flag register, and then the address to jump to will be computed based on the individual flags set. Similar encodings are availablef for the the Merge and the Virtualize transformations.  

Options

OptionArgumentsDescription
--Transform Flatten Flatten a function using Chenxi Wang's algorithm
--FlattenDispatch switch, goto, indirect, call, * Dispatch method. Comma-separated list. Default=switch.
  • switch = dispatch by while(1) {switch (next) {blocks}}
  • goto = dispatch by {labl1: block1; goto block2;}
  • indirect = dispatch by goto* (jtab[next])
  • call = each block is outlined into its own function
  • * = select a dispatch method at random.
--FlattenObfuscateNext BOOLSPEC Whether the dispatch variable should be obfuscated with opaque expressions or not. Default=false.
--FlattenDumpBlocks BOOLSPEC Print the linearized blocks. Default=false.
--FlattenOpaqueStructs list, array, * Type of opaque predicate to use. Traditionally, for this transformation, array is used. Default=array.
  • list = Generate opaque expressions using linked lists
  • array = Generate opaque expressions using arrays
  • * = Same as list,array
--FlattenSplitBasicBlocks BOOLSPEC If true, then basic blocks (sequences of assignment and call statements without intervening branches) will be split up into indiviual blocks. If false, they will be kept intact. Default=false.
--FlattenRandomizeBlocks BOOLSPEC If true, then basic block sequences will be randomized. Default=false.
--FlattenTrace bool Print a message before each block gets executed. Useful for debugging. Default=false.
--FlattenConditionalKinds branch, compute, flag Ways to transform conditional branches. Default=branch.
  • branch = Use normal branches, such as if (a>b) goto L1 else goto L2
  • compute = Compute the branch, such as x=(a>b); goto *(expression over x)
  • flag = Compute the branch from the values of the flag register, such as asm("cmp a b;pushf;pop"); goto *(expression over flag register)
--FlattenImplicitFlowNext bool Insert implicit flow between the computation of a an address and the subsequent indirect jump or call. This applies to call and indirect transformations only. Default=false.
--FlattenImplicitFlow S-Expression The type of implicit flow to insert. See --AntiTaintAnalysisImplicitFlow for a description. Default=none.
 

Examples

Flatten
Flatten fib in test1.c using each of the dispatch methods.
tigress --Verbosity=1  \
   --Transform=Flatten --Functions=fib --FlattenDispatch=dispatch \
   --Transform=CleanUp --CleanUpKinds=annotations \
   --out=c-files/... test1.c 
gcc -Wno-builtin-requires-header -fgnu89-inline -o bin-files/... c-files/...
sw id go
shout.c shout.c shout.c

Flatten ⇒ Flatten
Flatten fib in test1.c using two levels of flattening.
tigress --Verbosity=1  \
   --Transform=Flatten --Functions=fib --FlattenDispatch=dispatch1 \
   --Transform=Flatten --Functions=fib --FlattenDispatch=dispatch2 \
   --Transform=CleanUp --CleanUpKinds=annotations \
   --out=c-files/... test1.c 
gcc -Wno-builtin-requires-header -fgnu89-inline -o bin-files/.. c-files/..
sw go id
sw shout.c shout.c shout.c
go shout.c shout.c shout.c
id shout.c shout.c shout.c

Flatten
Flatten all functions with switch dispatch and opaque expressions.
tigress --Verbosity=1  \
   --Transform=InitEntropy --Functions=main \
   --Transform=InitOpaque --Functions=main --InitOpaqueCount=2 --InitOpaqueStructs=list,array \
   --Transform=Flatten --Functions=fib,fac --FlattenObfuscateNext=true --FlattenDispatch=switch \
   --Transform=CleanUp --CleanUpKinds=annotations \
   --out=gen/flatten_switch_opaque.c test1.c 
test1.cflatten_switch_opaque.sh.txtflatten_switch_opaque.c
Flatten ⇒ Merge
Flatten fac and fib and then merge them into fac_fib.
tigress --Verbosity=1  \
   --Transform=InitEntropy --Functions=main \
   --Transform=InitOpaque --Functions=main --InitOpaqueCount=2 --InitOpaqueStructs=list,array \
   --Transform=Flatten --Functions=fac,fib --FlattenObfuscateNext=true --FlattenDispatch=switch \
   --Transform=Merge --Functions=fac,fib \
   --Transform=CleanUp --CleanUpKinds=annotations \
   --out=gen/flatten-merge.c test1.c 
test1.cflatten-merge.sh.txtflatten-merge.c
 

Issues

 

Acknowledgments

Saumya Debray and Babak Yadegari suggested the --FlattenConditionalKinds=flag transformation.

 

References