When are Opaque Predicates Useful?

Opaque predicates are a commonly used technique in program obfuscation, intended to add complexity to control flow and to insert dummy code or watermarks. However, there are many attacks known to detect opaque predicates and remove dummy code. We survey these attacks and argue that many types of programs cannot be securely obfuscated using opaque predicates. In particular we explain that most previous works on control flow obfuscation have introduced predicates that are easily distinguished from naturally occurring predicates in code, and hence easily removed by an attacker. We state two conditions that are necessary for a program to be suitable for control flow obfuscation. We give an integrated approach to control flow obfuscation that simultaneously obfuscates real predicates and introduces opaque predicates. The opaque predicates are indistinguishable from the obfuscated real predicates in the program. If an attacker applies the usual approaches (both static and dynamic) to identify and remove opaque predicates then they are likely to remove critical functionality and introduce errors. We have implemented our obfuscator in LLVM. We provide an analysis of the performance of the resulting obfuscated code.