What is an "opaque predicate"?

Question

I saw the term of opaque predicates several times in obfuscation papers. As far as I understand it, it refers to predicates that are hard to evaluate in an automated manner. Placing it at strategical points of the program (jmp, test, ...) can mislead the analysis of a program by automatic tools.

My definition is lacking of precision and, moreover, I have no idea on how to estimate the opacity of such a predicate (its efficiency). So, can somebody give a proper definition and maybe a few examples ?

Answer 1

The answers already in this thread are good ones. In a nutshell, an opaque predicate is "something that a program analysis might miss, if the program analysis is not sophisticated enough". Denis' example was based on the inverse of constant propagation, and served as an anti-checksum mechanism. Joxean's SetErrorMode example was an environment-based opaque predicate that was used for dynamic anti-emulation. Two of Ange's answers were also dynamic anti-emulation; based upon the environment, and based upon uncommon platform features. Ange's other example was more like an anti-disassembly trick via indirect addressing.

In the academic literature, an opaque predicate is referred to as a branch that always executes in one direction, which is known to the creator of the program, and which is unknown a priori to the analyzer. The notion of "hardness" of an opaque predicate is deliberately omitted from this definition. Academic predicates are often based upon number-theoretic constructions, aliasing relationships, recursive data structures; basically anything that is commonly understood by program analysis researchers to cause problems for a program analysis tool.

My favorite researcher Mila Dalla Preda has shown that the ability for an abstract interpreter to break a given category of opaque predicate is related to the "completeness" of the domain with respect to the property tested by the predicate. She demonstrates by using mod-k-based opaque predicates, and elicits a family of domains that are complete (i.e. incur no abstract precision loss) for mod-k with respect to common transformers (addition, multiplication, etc). Then she explores the use of obscure theoretical constructions such as completeness refinement to automatically construct a domain for breaking a certain category of predicate. See this paper for more details.

Answer 2

An opaque predicate is an obfuscated condition, that, followed with a conditional operation, will make the analysis harder, and in some cases impossible until code is actually executed until that condition is evaluated.

This is used to disrupt static analysis (outcome is unpredictable) or emulation (to tell the difference between a real machine and an emulated environment).

They can rely on executions conditions, CPU features, API calls, and documented or not.

Examples

initial values

As values of registers are neither null nor completely random on process start, they can be relied on to create tests that look random but are actually deterministic:

example:

<EntryPoint>:
   jnz <InvalidPath>
   <ValidPath>

1. flags register is always 246 at EntryPoint
   • ZF is always set
2. as a consequence, jnz will never be taken.

checksum

1. compute a checksum of some piece of code or data
   • preferably something not present before runtime
2. xor with expected_result ^ jump_target
3. blindly use the result to jump somewhere

thus, it might be impossible to tell in advance what the next instructions will be.

mathematic functions

1. implement an asymptotic function in FPU
   • FPU is more likely to be unsupported or wrongly emulated/analysed than standard instructions
2. implement enough iteration to guarantee the result
   • many iterations might make an emulator run out of cycles
3. use the final result in a test, as a jump target, etc...

Answer 3

Not necessarily the predicate must be hard to evaluate. An opaque predicate is a condition which the result is known in advance by the programmer and that cannot be resolved statically (by a compiler, for example) and must be resolved dynamically.

An example I noticed in malware some years ago:

  SetErrorMode(100);
  if ( SetErrorMode(1024) == 100 )
    // Valid Path
  else
    // Invalid Path

Without executing the program (or knowing how the Win32 API SetErrorMode works) there is no way to determine which of the paths the program will take. However, as SetErrorMode returns the last previous code set, the programmer knows before executing this piece of code that the 1st path is the only valid one.

Answer 4

Sort of it also can be found in malicious obfuscated JavaScript code:

001     vz = 1;
002     var1 = 49;
003     var2 = var1;
004     if (var1 == var2){
005       document.location = "http://path.to.malicious.website";
006     }

here You see attempt in line 001-004 declare vars and conditions, that meaningless, and present to change obfuscated code hash and to complicate automatic analysis.

p.s. this is very simple examples, for more complicated samples of opaque predicate in JS see DefenceCode blog post