An approach to the obfuscation of control-flow of sequential computer programs.

Authors

Chow S., Gu Y., Johnson H., Zakharov V.A.

Abstract

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 $\pi$, we implant $I$ into $\pi$ by applying semantics-preserving transformations and using $K$ as a key. This yields as its result an obfuscated program $\pi_{I,K}$, such that a detection of some property $\cal{P}$ of $\pi_{I,K}$, which is essential for comprehending the program, gives a solution to $I$. Varying instances $I$, we obtain a family $\Pi_C$ of obfuscated programs such that the problem of checking $\cal{P}$ for $\Pi_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.

Text of article

Keywords

program obfuscation, equivalent transformations, PSPACE-completeness

Edition

Proceedings of the First "Information Security Conference", Malaga, Spain, 2001, серия Lecture Notes in Computer Science, 2001, v. 2200, pp. 144-155.

Research Group

Theoretical Computer Science

All publications during 2001

All publications