A Graph Game Model for Software Tamper Protection
We present a probabilistic program-transformation algorithm to render a given program tamper-resistant. In addition, we suggest a model to estimate the required effort for an attack. We make some engineering assumptions about local indistinguishability on
- PDF / 489,797 Bytes
- 16 Pages / 430 x 660 pts Page_size
- 60 Downloads / 198 Views
Abstract. We present a probabilistic program-transformation algorithm to render a given program tamper-resistant. In addition, we suggest a model to estimate the required effort for an attack. We make some engineering assumptions about local indistinguishability on the transformed program and model an attacker’s steps as making a walk on the program flow graph. The goal of the attacker is to learn what has been inserted by the transformation, in which case he wins. Our heuristic estimate counts the number of steps of his walk on the graph. Our model is somewhat simplified, but we believe both the constructions and models can be made more realistic in the future.
1
Introduction
In this paper, we consider the problem of protecting a complex program against tampering. The results of [3,11] mean that we cannot hope to solve this in general, namely in a model involving worst-case programs and polynomial-time adversaries. Hence it is natural to ask for practical solutions in some natural model with limited attacks. Here the hard problem is in building an appropriate model. A careful look at well known attacks (see overview in Section 3) and effects of program-transformation tools on local program properties (e.g., how homogeneous the code looks over 50 lines of assembly code) allows us to propose a security model of various protection schemes, based on some assumptions. Our overall approach is as follows. First, we take a given program P and convert this into another program P , where we inject new code that modifies the control and data flow graphs by adding nodes and edges. The goal of the attacker is to find the new additions, and we would grant the attacker victory if he does this reliably. Thus, we specify a formal model by defining a game where the attacker’s moves correspond to various attempts to break the protection, and the attacker’s victory corresponds to a break. In the present state of software protection, models based on complexity theory offer mainly negative results [3,11], with a handful of positive results that essentially formalize hashbased comparisons [12,18]. Motivated by an assortment of heuristic techniques for tamper protection, we give a simplified model, which captures realistic scenarios and allows quantitative analysis of tamper-resistance. Our model makes
Computer Science Department, Boston University. [email protected]. Part of this work was done during internships at Microsoft Research (Redmond, WA). Microsoft Research (Redmond, WA). [email protected] Microsoft Research (Redmond, WA and Bangalore, India). [email protected]
T. Furon et al. (Eds.): IH 2007, LNCS 4567, pp. 80–95, 2007. c Springer-Verlag Berlin Heidelberg 2007
A Graph Game Model for Software Tamper Protection
81
engineering assumptions about local indistinguishability of small code fragments and provides a lower bound on the attack effort required. An adversary who tries to reverse-engineer and eventually “crack” the program is typically equipped with some software tools that allow him to analyze the static s
Data Loading...
