Method and system for tamperproofing software

• US 20060031686A1
• Filed: 07/27/2005
• Published: 02/09/2006
• Est. Priority Date: 09/03/1999
• Status: Active Grant

• Current Assignee: Purdue Research Foundation (The Trustees of Purdue University (d/b/a Purdue University))
• Original Assignee: Purdue Research Foundation (The Trustees of Purdue University (d/b/a Purdue University))
• Inventors: Atallah, Mikhail J., Chang, Hoi
• Granted Patent: US 7,757,097 B2
• Time in Patent Office: Days
• US Class Current: 713/190
• CPC Class Codes: G06F 12/1408 by using cryptography for digital transmission H04L9/00

Abstract

Method of protecting host application code comprising a plurality of code blocks. The method includes steps of preprocessing the host application code; obfuscating the host application code; installing guards in the host application code to protect client blocks; randomly rearranging the code blocks of the host application code; linking the rearranged host application code with other resources to produce a binary executable image; and patching the binary executable image with data values to be used by the guard. The method can be used to install a plurality of guards to form a distributed network of guards that cooperatively protect the host application code and the other guards in the network. The installation of the guards can be performed automatically using a guard formation graph; and guard formation graph customization parameters. The obfuscation step can include control flow graph merging, cloning, and data-aliasing.

Claims

1. Method of protecting host application code comprising a plurality of code blocks, the method comprising:

preprocessing the host application code;

obfuscating the host application code;

installing a guard in the host application code to protect a client block, the client block being at least one code block;

randomly rearranging the code blocks of the host application code without rearranging the code blocks that have already been protected;

linking the rearranged host application code with other resources to produce a binary executable image; and

patching the binary executable image with data values to be used by the guard.

2. The method of claim 1, wherein the preprocessing step comprises

building a combined control flow graph for the host application code;

and

replacing instructions within the host application code containing high-level semantics with groups of simpler instructions that perform the equivalent function.

3. The method of claim 1, wherein the step of obfuscating the host application code occurs prior to the step of installing a guard;

and a second step of obfuscating the host application code occurs following the step of installing a guard to obfuscate at least one of the host application and the guard.

4. The method of claim 1, wherein the step of installing a guard further comprises:

using a plurality of guards;

saving a guard template for each guard to be installed; and

installing the plurality of guards to form a distributed network of guards that cooperatively protect the host application code and each other.

5. The method of claim 1, wherein the step of installing a guard comprises:

using a plurality of guards;

selecting the client blocks to be protected by the guards;

dividing each client block into sub-blocks;

rearranging the sub-blocks of each client block in a randomized order;

forming a contiguous code block from the rearranged sub-blocks of each client block;

assigning each of the plurality of guards to protect at least one code block;

selecting a guard template for each guard to be installed; and

installing each of the plurality of guards in a selected code block of the plurality of code blocks, the selected code block not being protected by a previously installed guard.

6. The method of claim 5, wherein the step of installing a plurality of guards is

performed automatically using a guard formation graph;

a first guard formation graph customization parameter, and a second guard formation graph customization parameter;

the guard formation graph including a plurality of client nodes, at least one client node being a root node;

the first guard formation graph customization parameter specifying the number of brigade nodes protecting each root node; and

the second guard formation graph customization parameter specifying the number of additional brigade nodes to be added to the guard formation graph.

7. The method of claim 4, wherein the step of patching the binary executable image comprises:

deriving one or more checksum constants for each client block in the binary executable image; and

patching each checksum constant into the appropriate location in the binary executable image.

8. The method of claim 7, wherein the step of patching each checksum constant comprises:

for at least one checksum constant, creating a functional algorithm which evaluates to the value of the checksum constant;

executing the functional algorithm; and

patching the result of the functional algorithm into the appropriate location in the binary executable image.

9. The method of claim 1, wherein installing a guard comprises:

mapping parameters in a guard template to variables and values in the host application code to create guard code,

installing the guard code in the host application code;

selecting an expression in the host application code to be modified by the guard;

inserting a conditional identity function into the selected expression in the host application code, the conditional identity function including checksum variables and corresponding constant values;

rewriting the selected expression to conceal the checksum variables;

marking the corresponding constant values to be derived from the checksum variables; and

saving a sequence of operations for deriving the corresponding constant values from the checksum variables.

10. The method of claim 9, wherein patching the binary executable image comprises:

generating the marked corresponding constant values using the saved sequence of operations and the checksum variables; and

inserting the generated corresponding constant values at the appropriate insertion points in the binary executable image, such that, during execution of the binary executable image, the checksums are compared with the generated corresponding constant values to detect modification and initiate defensive action.

13. The method of claim 1, wherein the obfuscating step further comprises:

selecting a potential block having a plurality of unmerged predecessor blocks and a single successor block;

creating a clone block for the potential block, the clone block having functionally equivalent code to the potential block;

updating a subset of the plurality of predecessor blocks to direct control flow to the clone block instead of the potential block; and

rewriting the code of the clone block to recast the clone block to have a different look than the potential block.

14. The method of claim 1, wherein the obfuscating step further comprises:

selecting a potential block having a plurality of unmerged predecessor blocks and a single successor block;

creating a clone block for the potential block, the clone block having functionally equivalent code to the potential block;

updating a subset of the plurality of predecessor blocks to direct control flow to one of the clone block and the potential block based on a randomized condition; and

rewriting the code of the clone block to recast the clone block to have a different look than the potential block.

15. The method of claim 1, wherein the obfuscating step further comprises:

selecting an aliasing constant in the host application code;

assigning an assigned variable to the aliasing constant;

substituting a mathematical expression using the assigned variable for at least one occurrence of the aliasing constant, the mathematical expression evaluating to the assigned variable;

computing the value of the assigned variable necessary for the mathematical expression to evaluate to the value of the aliasing constant; and

initializing the assigned variable to the necessary value in the code prior to the mathematical expression such that the assigned variable will have the necessary value when used in the mathematical expression.

16. The method of claim 1, further comprising embedding at least one watermark into the host application code.

17. The method of claim 16, further comprising protecting the embedded watermark with at least one guard.

18. The method of claim 1, further comprising embedding a plurality of watermarks in the host application code using a sequence of byte strings created by the steps of:

creating a common prefix, the common prefix being common to all watermarks in the host application code;

then performing the following steps for each watermark,

creating a unique field, the unique field being different for each watermark;

computing the combined length of the watermark plus the unique field;

encrypting the value of the combined length of the watermark plus the unique field;

creating a first string comprising the unique field appended to the watermark;

encrypting the first string;

creating a second string comprising the common prefix, the unique field, the encrypted combined length, and the encrypted first string; and

embedding the second string in the host application code.

20. The method of claim 1, further comprising:

attaching a digital signature of the binary executable image and any encrypted customization parameters used in the installation process to the binary executable image.

11. The method of claim I, wherein the obfuscating step comprises:

identifying a set of candidate blocks having the same program instructions in the same order with possibly conflicting parameter values;

selecting candidate blocks that do not share a predecessor block with any other candidate block of the set of candidate blocks, and are not a predecessor of itself or of any other candidate block of the set of candidate blocks;

for each candidate block that has no predecessor block, creating an empty code block as the predecessor block of that candidate block;

merging the set of candidate blocks into a merged block;

updating control flow instructions in the predecessor blocks of each of the candidate blocks to direct control flow to the merged block;

identifying each conflicting set of values in the set of candidate blocks, including any successor flow value that directs control flow from the merged block to the appropriate successor block for each candidate block of the set of candidate blocks;

assigning an assigned variable to each conflicting set of values;

pre-computing the set of conflicting values for each assigned variable; and

initializing each assigned variable in the host application code to contain the appropriate value from the set of conflicting values before use of the assigned variable by the merged block.

12. The method of claim 11, wherein the initializing each assigned variable step comprises:

for each candidate block, determining an appropriate value for each assigned variable, the appropriate value being one of the values from the conflicting set of values for the assigned variable; and

for each assigned variable and each candidate block, installing a computation that will evaluate to the appropriate value for the assigned variable before the assigned variable is used in the merged block.

19. The method of claim I, further comprising:

removing symbol tables from the binary executable image.

21. Method of coordinating the installation of a guard network to protect host code, the guard network being formed by a plurality of guards, the protection being specified by the portions of the host code and the guard network that is to be protected by each guard of the plurality of guards, and how each guard of the plurality of guards is to perform the protection, the method of coordinating the installation of the guard network comprising:

selecting a next guard of the plurality of guards to be installed in the guard network such that the next guard protects host code only, protects other guards that have already been installed, or protects host code and other guards that have already been installed; and

installing the next guard.