Graph-Based Tamper Resistance Modeling For Software Protection
Implementation of graph-based tamper resistance modeling for software protection is described. In one implementation, paths of execution of a program are modeled as a graph having nodes and edges. A tamper resistance tool receives an input program code corresponding to the program and generates a tamper-resistant program code using integrity checks. Values for the integrity checks are computed during program execution and are compared to pre-computed values to determine whether a section of the program has been tempered with. Values of the integrity checks may be accessed at any point in time during execution of the program.
1 . A method comprising:
accessing a graph, wherein the graph models paths of execution associated with a program, and further wherein the graph includes a plurality of nodes and one or more edges;
inserting one or more checking edges into the graph, wherein the one or more checking edges are associated with selected nodes in the plurality of nodes, and further wherein the one or more checking edges are associated with one or more integrity checks; and
registering tampering with the program based upon detection of one or more failed integrity checks.
2 . The method of claim 1 wherein accessing further comprises randomizing a sub graph including a plurality of sub nodes and one or more sub edges into the plurality of nodes and the one or more edges in the graph.
3 . The method of claim 2 , wherein randomizing includes one or more of:
adding one or more chaff sub nodes into the sub graph;
clustering two or more sub nodes into a node.
4 . The method of claim 1 wherein accessing comprises creating the graph based on the program.
5 . The method of claim 1 , wherein inserting includes coupling one of the plurality of nodes with at least one of the one or more checking edges.
6 . The method of claim 1 , wherein registering includes detecting at least one of the one or more failed integrity checks after the one or more failed integrity checks have been calculated.
7 . The method of claim 1 , further comprising estimating a minimum attack time required to break protection of the program based on a number of integrity checks associated with the program.
8 . The method of claim 1 , further comprising determining that one of the one or more integrity checks has failed if a hash value of variables computed in the program at runtime in association with the integrity check does not exactly match a pre-computed hash value of the variables associated with the integrity check.
9 . A computer-readable medium having a set of computer-readable instructions residing thereon that, when executed, perform acts comprising:
implementing execution of a program as a walk through a graph of the program, wherein the graph includes one or more nodes associated with integrity checks;
accessing a status of integrity checks coupled with at least one node of the one or more nodes; and
indicating that the program has been compromised when the status of the integrity checks indicates tampering with the program.
10 . The computer-readable medium of claim 9 , further comprising computer executable instructions that, when executed, perform acts comprising:
executing integrity checks associated with one node of the one or more nodes as execution of the program traverses the one node.
11 . The computer-readable medium of claim 9 , further comprising computer executable instructions that, when executed, perform acts comprising:
estimating a total number of actions to be executed by an attacker to defeat security features of the program as being one of:
a super-linear function of a number of integrity checks associated with the program;
a polynomial function of a number of integrity checks associated with the program.
12 . The computer-readable medium of claim 9 , further comprising computer executable instructions that, when executed, perform acts comprising:
executing an integrity check by computing a hash value of a current program state at runtime and comparing the hash value with a pre-computed hash value; and
returning a false value for the status of the integrity check when the hash value of the current program state at runtime fails to match the pre-computed hash value, wherein the false value indicates tampering with the program.
13 . The computer-readable medium of claim 9 , further comprising computer executable instructions that, when executed, perform acts comprising:
indicating that the program has been compromised by one of:
terminating the execution of the program;
degrading the execution of the program;
unreliably performing the execution of the program;
displaying an error message.
14 . A computing device comprising:
a memory;
one or more processors operatively coupled to the memory;
a check generator configured to insert a plurality of checking edges in a graphical model of a program, wherein the graphical model includes a plurality of nodes and edges, and further wherein each checking edge is associated with one or more integrity checks;
a node modifier configured to couple one or more of the plurality of nodes with a subset of the checking edges; and
a tampering identifier configured to perform acts comprising:
determining a status of the integrity checks associated with one or more checking edges; and
regulating execution of the program depending upon the status of the integrity checks.
15 . The computing device of claim 14 , wherein the node modifier is configured to couple nodes to checking edges with which the nodes are not associated.
16 . The computing device of claim 14 , wherein the tampering identifier is configured to determine the status of an integrity check by comparing a pre-computed hash value of variables in the program against a hash value of the variables in the program computed at runtime.
17 . The computing device of claim 16 , wherein the tampering identifier is configured to return a false status for an integrity check when the pre-computed hash value of variables in the program fails to match the hash value of the variables in the program computed at runtime.
18 . The computing device of claim 14 , wherein the tampering identifier is configured to regulate execution of the program when at least a subset of the integrity checks fail.
19 . The computing device of claim 14 further comprising a graphical model generator configured to generate the graphical model of the program.
20 . The computing device of claim 14 , further comprising a randomizer configured to randomize the plurality of nodes and edges by at least one of:
inserting chaff nodes into the graphical model;
inserting chaff edges into the graphical model;
clustering two or more nodes in the graphical model into a super node.