Encode Branches

The goal of these transformations is to make it harder for automatic analysis tools (such as disassemblers) to determine the target of branches.


Branch Functions

This transformation implements a simplistic version of Linn and Debray's branch functions. We doen't use perfect hash tables, as suggested in Linn and Debray's paper, since this is hard to do as a source-to-source transformation. Rather, we simply pass the offset to jump to as an argument to the branch function.

The generated code looks like this, where the call to the branch function bf actually results in a direct jump to lab2: 

void bf(unsigned long offset) {
  __asm__  volatile   ("addq  %0, 8(%%rbp)": : "r" (offset));
}

int main() {
   bf((unsigned long)(&& lab2) - (unsigned long)(&& lab3));
   lab3: 
       __asm__  volatile   (".byte 0x76,0x9b,0x8e,0x1b,0x4d":);
   ...
   lab2: ...;
}

A function can be flattened prior to direct jumps being encoded. This creates more direct jumps and hence more opportunities to apply the transformation. Prior to version 4.0.12 this only applied to branch functions, and not the other encoding variants.

Before branches can be replaced by calls to a branch function, at least one such function needs to be constructed, using the --Transform=InitBranchFuns transformation.

The branch function is not obfuscated and hence trivial to find. It's therefore a good idea to merge it with other functions in the program.

OptionArgumentsDescription
--Transform InitBranchFuns Initialize so that branch functions can be insered at a later time.
--InitBranchFunsOpaqueStructs Deprecated spelling of --InitBranchFunsOpaqueInvariantKinds Kept for compatibility. Replace --InitBranchFunsOpaqueStructs=list,array with --InitBranchFunsOpaqueInvariantKinds=structure_state. Replace --InitBranchFunsOpaqueStructs=env with --InitBranchFunsOpaqueInvariantKinds=environment. The input kind was removed in 4.1. Default=The kinds specified at InitOpaque..
--InitBranchFunsOpaqueInvariantKinds identity, modular, mba, structure_state, scalar_state, environment, plugin, * Comma-separated list of the kinds of opaque invariant branch functions may draw from, named by the hardness family they rest on. Constrained to the kinds set up by --InitOpaqueInvariantKinds. From version 4.1 Default=The kinds specified at InitOpaque..
  • identity = Universally-true arithmetic identities.
  • modular = Residue and modular-arithmetic facts.
  • mba = Mixed boolean-arithmetic.
  • structure_state = A data structure that maintains an invariant as the program runs and is then queried structurally. Replaces pre-4.1 list and array.
  • scalar_state = Evolving scalar state.
  • environment = Opaque expressions from entropy. Requires --InitEntropy. Replaces env.
  • plugin = Invariants supplied by a user plugin.
  • * = Same as identity,modular,mba,structure_state,scalar_state,environment,plugin
--InitBranchFunsOpaqueInvariantResilience trivial, local, global, interprocedural, inter_process, * Comma-separated list of the resilience levels branch functions may draw from -- the scope of analysis an attacker must run to decide the invariant. Constrained to the levels set up by --InitOpaqueInvariantResilience. From version 4.1 Default=The levels specified at InitOpaque..
  • trivial = One expression decides it, AND a stock compiler at -O2 folds it to a constant.
  • local = One expression decides it, but -O2 does not fold it.
  • global = Deciding it needs analysis of the whole procedure.
  • interprocedural = Deciding it needs whole-program analysis.
  • inter_process = Deciding it needs reasoning about concurrent interleavings. Reserved -- no invariant is at this level yet.
  • * = Every level, trivial included.
--InitBranchFunsOpaqueMaxSize INTSPEC The largest number of sub-opaques one opaque may be composed of. See --AddOpaqueMaxSize. From version 4.1 Default=The value set by --InitOpaqueMaxSize..
--InitBranchFunsOpaqueSelect (Deity mode only.) Comma-separated list of exact invariant names to draw from, bypassing the kind and resilience selection entirely. Names come from --InitOpaqueList. Silently inert unless the deity key is supplied with --DeityMode. The named invariants must have been set up by InitOpaque, so pair this with a permissive --InitOpaqueInvariantKinds/--InitOpaqueInvariantResilience. From version 4.1 Default=none.
--InitBranchFunsCount INTSPEC How many branch functions to add.
--InitBranchFunsObfuscate BOOLSPEC Whether to obfuscate the branch function. Default=false.
--InitBranchFunsName STRING Name of generated branch functions. If more than one, an "_number" is appended. Default=_bf.

X86 Branch Obfuscations

We implement two standard branch obfuscations used by many packers: 

      push target
      call lab
      ret
lab:
      ret

and 

      push target
      ret


NOP sleds

The --AntiBranchAnalysisKinds=goto2nopSled switch turns this code 

      goto L
      ...
   L:

into this code 

      goto *(R+expression)
      ...
    R: 
      nop
      nop
      ...
      nop
    L:

The expression is opaque such that the branch falls somewhere within the nop sled. The intention is to combine this transformation with input-dependent opaque predicates so that the actual jump address will be random and input dependent: 

tigress --Input=... \
        --Transform=InitOpaque 
           --InitOpaqueKind=Input \
        --Transform=AntiBranchAnalysis \
            --AntiBranchAnalysisKinds=goto2nopSled \
            --AntiBranchAnalysisOpaqueStructs=Input

The current nop-sled is trivial, consisting of random lists of x86 bytes that have no effect: 

   cmc
   std
   cld
   nop
   stc
   cmc
   clc
   stc
   wait
   ...

OptionArgumentsDescription
--Transform AntiBranchAnalysis Replace branches with other constructs.
--AntiBranchAnalysisKinds branchFuns, goto2call, goto2push, goto2push2, goto2nopSled, * Comma-separated list of the kinds of constructs branches can be replaced with. Default=branchFuns.
  • branchFuns = Generate calls to branch functions. --Transform=InitBranchFuns must be given prior to this transform
  • goto2call = Replace goto L with push L; call lab; ret; lab: ret
  • goto2push = Replace goto L with push L; ret
  • goto2push2 = Replace goto L with push L; leal; jmp
  • goto2nopSled = Replace goto L with goto *p where p is the address of a sequence of nop:s that eventually lead to L
  • * = Same as branchFuns,goto2call,goto2push
--AntiBranchAnalysisOpaqueStructs Deprecated spelling of --AntiBranchAnalysisOpaqueInvariantKinds Kept for compatibility. Replace --AntiBranchAnalysisOpaqueStructs=list,array with --AntiBranchAnalysisOpaqueInvariantKinds=structure_state. Replace --AntiBranchAnalysisOpaqueStructs=env with --AntiBranchAnalysisOpaqueInvariantKinds=environment. The input kind was removed in 4.1. Default=The kinds specified at InitOpaque..
--AntiBranchAnalysisObfuscateBranchFunCall BOOLSPEC Obfuscate the body of the branch function. Default=false.
--AntiBranchAnalysisBranchFunFlatten BOOLSPEC Flatten before replacing jumps. This opens up more opportunities for replacing unconditional branches. From version 4.0.12 this is obsolete. Use --AntiBranchAnalysisFlatten instead. Default=false.
--AntiBranchAnalysisFlatten BOOLSPEC Flatten before replacing jumps. This opens up more opportunities for replacing unconditional branches. Default=false.
--AntiBranchAnalysisBranchFunAddressOffset integer The offset (in bytes) of the return address on the stack, for branch functions. May differ based on operating system, word size, and compiler. Default=8 on x86_64, 0 on Arm.
--AntiBranchAnalysisFraction FRACSPEC How many unconditional branches should be encoded. Default=%100.
--AntiBranchAnalysisOpaqueInvariantKinds identity, modular, mba, structure_state, scalar_state, environment, plugin, * Comma-separated list of the kinds of opaque invariant the NOP sled may draw from, named by the hardness family they rest on. Constrained to the kinds set up by --InitOpaqueInvariantKinds. From version 4.1 Default=The kinds specified at InitOpaque..
  • identity = Universally-true arithmetic identities.
  • modular = Residue and modular-arithmetic facts.
  • mba = Mixed boolean-arithmetic.
  • structure_state = A data structure that maintains an invariant as the program runs and is then queried structurally. Replaces pre-4.1 list and array.
  • scalar_state = Evolving scalar state.
  • environment = Opaque expressions from entropy. Requires --InitEntropy. Replaces env.
  • plugin = Invariants supplied by a user plugin.
  • * = Same as identity,modular,mba,structure_state,scalar_state,environment,plugin
--AntiBranchAnalysisOpaqueInvariantResilience trivial, local, global, interprocedural, inter_process, * Comma-separated list of the resilience levels the NOP sled may draw from -- the scope of analysis an attacker must run to decide the invariant. Constrained to the levels set up by --InitOpaqueInvariantResilience. From version 4.1 Default=The levels specified at InitOpaque..
  • trivial = One expression decides it, AND a stock compiler at -O2 folds it to a constant.
  • local = One expression decides it, but -O2 does not fold it.
  • global = Deciding it needs analysis of the whole procedure.
  • interprocedural = Deciding it needs whole-program analysis.
  • inter_process = Deciding it needs reasoning about concurrent interleavings. Reserved -- no invariant is at this level yet.
  • * = Every level, trivial included.
--AntiBranchAnalysisOpaqueMaxSize INTSPEC The largest number of sub-opaques one opaque may be composed of. See --AddOpaqueMaxSize. From version 4.1 Default=The value set by --InitOpaqueMaxSize..
--AntiBranchAnalysisOpaqueSelect (Deity mode only.) Comma-separated list of exact invariant names to draw from, bypassing the kind and resilience selection entirely. Names come from --InitOpaqueList. Silently inert unless the deity key is supplied with --DeityMode. The named invariants must have been set up by InitOpaque, so pair this with a permissive --InitOpaqueInvariantKinds/--InitOpaqueInvariantResilience. From version 4.1 Default=none.
 

Issues

This transformation has many issues, and should only be used with great care:

  • It appears as goto2push and goto2call will often cause clang to generate the wrong code.

    1

    gcc 4.6 appears to do the right thing.

    2

    gcc 4.8 appears to occasionally hang when compiling our generated code.

    The issue is that the generated inline assembly code contains jumps. Newer versions of gcc have an asm goto construct which ought to help with this. Clang lacks this feature.
  • Make sure you set the --Environment=... option appropriately if you are going to use goto2push and goto2call and test the generated code thoroughly. goto2push and goto2call are turned off by default.
  • Running this transformation on the same function twice seems to occasionally break.
  • The NOP sled currently uses only trivial instructions that do not modify registers. Eventually, we'll get around to implementing a nop-generator (similar to MetaSploit's) that also allows more complex instructions.
  • In versions prior to 4.0.12 if there were not goto:s in a function, the Branch Functions transformation would just silently fail. Now an error is generated instead.
  • Branch Functions on code like this that jumps around to labels within in switch statement seems to inexplicably fail, at least on Arm: 
    void switch_() {
   puts("switch: ");
   goto lab7;
   switch (1) {
   lab1:
   lab2:
   lab3:
     printf(", SUCCESS-2");
     goto lab5;
   lab4:
   case 1: 
   case 2: 
   case 3: 
      lab5:
      lab6:
     printf(", SUCCESS-3");
     goto lab10;
   lab7:
   default:
      lab8:
      printf("SUCCESS-1");
      goto lab2;
   };
   lab9:
   lab10:
   lab11:
      puts(", SUCCESS-4");
      goto lab13;
   lab12:
      printf("FAILURE");
   lab13:;
}

 

References

The Branch Function transformation implements a simplistic version of Linn and Debray's Obfuscation of Executable Code to Improve Resistance to Static Disassembly, Linn and Debray's algorithm replaces direct jumps with calls to a special branch function which sets the return address to the target of the original branch, and then returns.

There are many attacks published on branch functions, including Static Disassembly of Obfuscated Binaries by Christopher Kruegel, William Robertson, Fredrik Valeur and Giovanni Vigna, and Deobfuscation: Reverse engineering obfuscated code by Sharath Udupah, Saumya Debray, and Matias Madou.

Kevin A. Roundy and Barton P. Miller's survey paper Binary-code obfuscations in prevalent packer tools is a good source of information on techniques used by current obfuscation tools.