How to design opaque predicates?

Question

Opaque predicate are used to disrupt automatic analysis of the binary code by reaching the limits of what can do an analyzer.

Can somebody give an example (or a few examples) of an opaque predicate found in a real-life case ? And, what are the methods used to build new opaque predicates ?

Answer 1

One opaque predicate I found in a malware sample years ago:

SetErrorMode(1024);
if ( SetErrorMode(0) == 0 )
  SayHiToEmulator();
DoRealStuff();

As for the other question, how to build new opaque predicates, I think it depends on the kind of analyser you want to disrupt. It's different to disrupt a static code analyser designed to find bugs than disrupting an emulator designed to mimic the environment where a malware should run in.

But, let's say that you want to disrupt malware emulators: you can build a list of APIs from the most common libraries (kernel32.dll, advapi32.dll, user32.dll, etc...), create a batch of proves where you execute those APIs changing the arguments and checking the return values and generated exceptions, if any, and save the results. Then check the results of such APIs and find candidates: For example, a return value related to the input to such APIs is a good candidate for an opaque predicate. Specific conditions (exceptions or return values) that only happen rarely and with certain specific inputs are even better. Just some ideas...

Answer 2

Manufacturing Cheap, Resilient, and Stealthy Opaque Constructs, ACM Principles of Programming Languages (POPL'98), January 1998.

The article has 300+ citations. The paper is a good text on the topic of opaque predicates, then follow-up on the citations to look for newer articles that refer to it.

Link: Manufacturing Cheap, Resilient, and Stealthy Opaque Constructs

Answer 3

I do not know any real-life opaque predicate. But there is a very constructive predicate obfuscator in the paper Limits of Static Analysis for Malware Detection. It is proved to be NP-hard for precise static analysis.