Software Tamper Resistance: Obstructing Static Analysis of Programs

Authors:Wang, Chenxi, Department of Computer ScienceUniversity of Virginia Hill, Jonathan, Department of Computer ScienceUniversity of Virginia Knight, John, Department of Computer ScienceUniversity of Virginia Davidson, Jack, Department of Computer ScienceUniversity of Virginia

Reliable execution of software on untrustworthy platforms is a difficult problem. On the one hand, the underlying system services cannot be relied upon to provide execution assurance, while on the other hand, the effect of a tampered execution can be disastrous -- consider intrusion detection programs. What is needed, in this case, is tamper resistant software. Code obfuscation has been an area of development, in part, to enhance software tamper resistance. However, most obfuscation techniques are ad hoc, without the support of sound theoretical basis or provable results. In this paper, we address one aspect of software protection by obstructing static analysis of programs. Our techniques are based, fundamentally, on the difficulty of resolving aliases in programs. The presence of aliases has been proven to greatly restrict the precision of static data-flow analysis. Meanwhile, effective alias detection has been shown to be NP-Hard. While this represents a significant hurdle for code optimization, it provides a theoretical basis for structuring tamper-resistant programs -- systematic introduction of nontrivial aliases transforms programs to a form that yields data flow information very slowly and/or with little precision. Precise alias analysis relies on the collection of static control flow information. We further hinder the analysis by a systematic "break-down" of the program control-flow; transforming high level control transfers to indirect addressing through aliased pointers. By doing so, we have made the basic control-flow analysis into a general alias analysis problem, and the data-flow analysis and control-flow analysis are made co-dependent. We present a theoretical result which shows that a precise analysis of the transformed program, in the general case, is NP-hard and demonstrate the applicability of our techniques with empirical results.

All rights reserved (no additional license for public reuse)
Source Citation:

Wang, Chenxi, Jonathan Hill, John Knight, and Jack Davidson. "Software Tamper Resistance: Obstructing Static Analysis of Programs." University of Virginia Dept. of Computer Science Tech Report (2000).

University of Virginia, Department of Computer Science
Published Date: