In computer programming, an opaque predicate is a predicate—an expression that evaluates to either "true" or "false"—for which the outcome is known by the programmer a priori, but which, for a variety of reasons, still needs to be evaluated at run time
Opaque predicates appears to have been first used by Christian Collberg & Clark Thomborson back in 1997 source. The technique is discussed in their paper A Taxonomy of Obfuscating Transformations.
The real challenge when designing control-altering transformations is to make them not only cheap, but also resistant to attack from deobfuscators. To achieve this, many transformations rely on the existence of opaque variables and opaque predicates. Informally, a variable V is opaque if it has some property q which is known a priori to the obfuscator, but which is difficult for the deobfuscator to deduce. Similarly, a predicate P (a boolean expression) is opaque if a deobfuscator can deduce its outcome only with great diffculty, while this outcome is well known to the obfuscator.
opaque predicates are the major building block in the design of transformations that obfuscate control flow. In fact, the quality of most control transformations is directly dependent on the quality of such predicates.
Opaque predicates are used to perform code obfuscation by injecting superfluous branches into the program. Superfluous branches are the gateways for junk bytes or unreachable code to inconspicuously mingle with authentic code instructions.
Fundamentally, opaque predicates inject superfluous nbranches (a.k.a dead branches), or branches that are never taken during program runtime, into the disassembly. An opaque predicate injects a superfluous branch by syntactically disguising an unconditional branch as a conditional branch. This disguise is enabled by an invariant expression that always evaluates to true or false. The eventual disguised conditional branch is composed of an unconditional branch and a superfluous branch. A simple opaque predicate in x86 assembly is demonstrated below:
xor eax, eax
jz always_jump
The disguised JZ instruction will always jump to the label ”always jump” because prior to the jump the zero flag is always set by the XOR instruction. Here, the invariant expression evaluates to true. The disguised JZ instruction is composed of a unconditional branch whose target address is the ”always jump” label (true branch) and a superfluous branch whose target address is the location immediately following the JZ instruction (false branch)
There are two types of damage that can result from opaque predicates: code bloat or disassembly desynchronization.
Repo for Heuristic Approach to Detect Opaque Predicates that Disrupt Static Disassembly. A sample set of ELF binaries also exists.
- Seeing through obfuscation: interactive detection and removal of opaque predicates
- Man-At-The-End Obfuscation Lecture
- Opaque Predicates Detection by Abstract Interpretation: Slides & Thesis
- Analysis of obfuscation transformations on binary code
- Code Obfuscation 102+(2*a+3)%2 Code Obfuscation 102+(2*a+3)%2
- Code Obfuscation
- Surreptitious Software, Chapter 4
- Reversing: Secrets of Reverse Engineering, Chapter 10
- Practical Binary Analysis, Chapter 12
- Practical Reverse Engineering: x86, x64, ARM, Windows Kernel, Reversing Tools, and Obfuscation, Chapter 5