An Approach to the Obfuscation of Control-Flow of Sequential Computer Programs

摘要

In this paper we present a straightforward approach to the obfuscation of sequential program control-flow in order to design tamper-resistant software. The principal idea of our technique is as follows: Let I be an instance of a hard combinatorial problem C, whose solution K is known. Then, given a source program π, we implant I into π by applying semantics-preserving transformations and using K as a key. This yields as its result an obfuscated program π_(I,K), such that a detection of some property p of π_(I,K), which is essential for comprehending the program, gives a solution to I. Varying instances I, we obtain a family Π_C of obfuscated programs such that the problem of checking P for Π_C is at least as hard as C. We show how this technique works by taking for C the acceptance problem for linear bounded Turing machines, which is known to be PSPACE-complete.