Practical Obfuscating Programs

Barak et al. gave a first formalization of obfuscation, describing an obfuscator O as an efficient, probabilistic "compiler" that takes in input a program P and produces a new program O (P ) that has the same functionality as P but is unintelligible. This mean that any result an obfuscated program can compute is actually computable given only an input/output access (called oracle access) to the program P: we call such results trivial results. On the basis of this informal definition, they suggest a formal definition of obfuscation based on oracle access to programs and show that no obfuscator can exist according to this definition. They also try to relax the definition and show that, even with a restriction to some common classes of programs, there exists no obfuscator.

In this work, we show that their definition is inaccurate and lacks a fundamental property, that we formalize by the notion of oracle programs. Oracle programs are an abstract notion which basically refers to perfectly obfuscated programs. We suggest a new definition of obfuscation based on these oracle programs and show that such obfuscators do not exist either. Considering the actual implementations of "obfuscators", we define a new kind of obfuscators, t-obfuscators. These are obfuscators that hide non trivial results at least for time t. By restricting the t-requirement to deobfuscation (that is outputting an intelligible program when fed with an obfuscated program in input), we show that such obfuscators do exist. Practical t-obfuscation methods are presented at the end of this paper: we focus more specifically on code protection techniques in a malware context.

Based on the fact that a malware may fulfill its action in an amount of time which may be far larger than the analysis time of any automated detection program, these obfuscation methods can be considered as efficient enough to greatly thwart automated analysis and put check on any antivirus software.