Proceedings of ISP RAS

Program obfuscation as obstruction of program static analysis.

K.S. Ivanov, V.A. Zakharov.


By obfuscation we mean any efficient semantic-preserving transformation of computer programs aimed at bringing a program into such a form, which impedes the understanding of its algorithm and data structures or prevents the extracting of some valuable information from the plaintext of a program. Some results obtained recently testify that it is very much uneasy to develop a provably secure program obfuscator unless a capability of an adversary is restricted weakly. But in many practical cases when program re-engineering activity is restricted only to the application of available static analysis algorithms an acceptable security of obfuscation can be achieved by guaranteeing the obfuscated programs to obstruct completely some definite static analysis technique. This approach to designing program obfuscators is commonly used now though no rigorous study of its efficiency and security is made so far. In this paper we give a preliminary framework for studying formally program obfuscators as tools for the obstruction of program static analysis. We present a criterion which provides a way of estimating the actual efficiency of static analysis obstruction and demonstrate with example of two typical static analysis algorithms (Andersen’s points-to analysis algorithm and Binkley-Horwitz-Reps slicing algorithm) how to use our approach in practice.


Proceedings of the Institute for System Programming, vol. 6 (in Russian), 2004, Стр. 137-156.

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

Full text of the paper in pdf (in Russian) Back to the contents of the volume