Tamper resistant software encoding

• US 6,594,761 B1
• Filed: 06/09/1999
• Issued: 07/15/2003
• Est. Priority Date: 06/09/1999
• Status: Expired due to Term

• Current Assignee: Irdeto B.V. (MultiChoice Group Ltd.)
• Original Assignee: Cloakware Incorporated (MultiChoice Group Ltd.)
• Inventors: Johnson, Harold J., Chow, Stanley T., Gu, Yuan
• Primary Examiner(s): Peeso, Thomas R.
• Application Number:
  US09/329,117
• Time in Patent Office: 1,497 Days
• Field of Search: 713/165, 713/166, 713/187, 713/189, 713/190, 713/194, 713/200, 713/201
• US Class Current: 713/190
• CPC Class Codes: G06F 21/14 against software analysis or reverse engineering, e.g. by obfuscation
• CPC Class Codes: G06F 2211/007 Encryption, En-/decode, En-/decipher, En-/decypher, Scramble, (De-)compress
• CPC Class Codes: H04L 2209/16 Obfuscation or hiding, e.g. involving white box

Abstract

The present invention relates generally to computer software, and more specifically, to a method and system of making computer software resistant to tampering and reverse-engineering. “Tampering ” occurs when an attacker makes unauthorized changes to a computer software program such as overcoming password access, copy protection or timeout algorithms. Broadly speaking, the method of the invention is to increase the tamper-resistance and obscurity of computer software code by transforming the data flow of the computer software so that the observable operation is dissociated from the intent of the original software code. This way, the attacker can not understand and decode the data flow by observing the execution of the code. A number of techniques for performing the invention are given, including encoding software arguments using polynomials, prime number residues, converting variables to new sets of boolean variables, and defining variables on a new n-dimensional vector space.

Claims

1. A method of increasing the tamper-resistance and obscurity of computer software code comprising the steps of:

encoding said computer software code into a domain which does not have a corresponding semantic structure, to increase the tamper-resistance and obscurity of said computer software code by;

transforming the domains of individual operations in said software code, and of the data used by and computed by said individual operations in said software code, so that each individual operation, together with the data which it uses and the data which it computes, occupies a different data domain from the data domains of such operations and data in the original software code, and so that the original of said operations and the original of said data may not be readily deducible from the transformed versions of said operations and the transformed versions of said data.

2. A method as claimed in claim 1 wherein said steps of encoding and transforming comprise the step of:

dispersing the definition of an argument into a plurality of locations, to dissociate the observable operation of said computer software code from said computer software code while being executed.

3. A method as claimed in claim 2, further comprising the subsequent step of:

moving selected individual instructions to new locations permitted by their data flow and control flow dependencies.

4. A method as claimed in claim 3, wherein said step of dispersing comprises:

redefining an argument using one of the following techniques;

residue coding;

bit-explosion;

bit-residue;

or

custom base coding.

5. A method as claimed in claim 1 wherein said steps of encoding and transforming comprise the step of:

encoding said computer software code such that minor changes will result in nonsensical operation when the encoded software is executed, without causing the encoded software to immediately fail.

6. A method as claimed in claim 5 further comprising the step of:

adding code to said computer software code to allow variables to have a broader range of values without causing out of range errors.

7. A method as claimed in claim 6, wherein said steps of encoding and adding code comprise the step of:

redefining an argument using one of the following techniques;

polynomial coding;

residue coding;

bit-explosion;

bit-residue;

or custom base coding.

8. A method as claimed in claim 1 wherein said steps of encoding and transforming comprise the steps of:

defining a first variable in said computer software code in terms of a second variable in said computer software code, so that modification of said second variable modifies the value of said first variable.

9. A method as claimed in claim 1 wherein said steps of encoding and transforming comprise the steps of:

defining a plurality of variables in terms of one another, so that modification of any one of said variables will alter the definition of all of said plurality of variables.

10. A method as claimed in claim 9, wherein said step of defining comprises:

redefining an argument using one of the following techniques;

polynomial coding;

residue coding;

bit-explosion;

bit-residue;

or

custom base coding.

11. A method as claimed in claim 1 wherein said steps of encoding and transforming comprise the steps of:

responding to a line of code defining a polynomial equation by;

redefining each variable in said polynomial equation by a new polynomial equation; and

selecting random values of constants in said new polynomial equations.

12. A method as claimed in claim 11 wherein said step of selecting comprises selecting values of constants in said new polynomial equations to invert the sense of an arithmetic operation in said polynomial equation.

13. A method as claimed in claim 12 wherein:

said step of redefining comprises redefining each variable in said polynomial equation by a new first order polynomial equation; and

said step of selecting comprises selecting values of constants in said new first order polynomial equations to invert the sense of an arithmetic operation in said first order polynomial equation.

14. A method as claimed in claim 1 wherein said steps of encoding and transforming comprise the steps of:

generating and storing a set of relatively prime factors;

transposing said computer software program by calculating residues based on said set of relatively prime factors;

calculating a corresponding set of execution constants which may be used to execute said encoded computer software program; and

storing said set of execution constants with said encoded computer software program.

15. A method as claimed in claim 14 wherein said step of transposing comprises selecting a block of SSA code and transposing said block of SSA code into a corresponding set of residual code by calculating residues based on said set of relatively prime factors.

16. A method as claimed in claim 1, wherein said steps of encoding and transforming comprise the step of:

defining an n-bit variable as a corresponding set of n-boolean variables.

17. A method as claimed in claim 16, further comprising the step of:

adding lines of code to invert selected ones of said corresponding set of n-boolean variables.

18. A method as claimed in claim 17, further comprising the step of:

responding to the data flow of said computer software code having a reasonably small number of inputs and being acyclic, by replacing said corresponding set of n-boolean variables with a table lookup.

19. A method as claimed in claim 1 wherein said steps of encoding and transforming comprise the step of:

mapping a set of n-variables into a new n-dimensional, custom coordinate space.

20. A method as claimed in claim 19 wherein said step of mapping comprises:

mapping a set of n-independent variables into a new n-dimensional coordinate space defining a rotation of said set of n-independent variables from the original coordinate space.

21. A method as claimed in claim 1, wherein said steps of encoding and transforming comprise the step of:

encoding intermediate computer software code into tamper-resistant intermediate computer software code having a domain which does not have a corresponding semantic structure, to increase the tamper-resistance and obscurity of said computer software code; and

further comprising;

a prior step of compiling said computer software program from source code into a corresponding set of intermediate computer software code; and

a subsequent step of compiling said tamper-resistant intermediate computer software code into said tamper-resistant computer software object code.

22. A method as claimed in claim 1 wherein said steps of encoding and transforming comprise the step of:

encoding arguments in said computer software code into a domain which does not have a corresponding high level semantic structure, to increase the tamper-resistance and obscurity of said computer software code.

23. A computer readable memory medium, storing computer software code executable to perform the steps of:

compiling said computer software program from source code into a corresponding set of intermediate computer software code;

encoding said intermediate computer software code into tamper-resistant intermediate computer software code having a domain which does not have a corresponding semantic structure, to increase the tamper-resistance and obscurity of said computer software code; and

compiling said tamper-resistant intermediate computer software code into tamper-resistant computer software object code.

24. A computer data signal embodied in a carrier wave, said computer data signal comprising a set of machine executable code being executable by a computer to perform the steps of:

compiling said computer software program from source code into a corresponding set of intermediate computer software code;

encoding said intermediate computer software code into tamper-resistant intermediate computer software code having a domain which does not have a corresponding semantic structure, to increase the tamper-resistance and obscurity of said computer software code; and

compiling said tamper-resistant intermediate computer software code into tamper-resistant computer software object code.

25. An apparatus for increasing the tamper-resistance and obscurity of computer software code, comprising:

front end compiler means for compiling said computer software program from source code into a corresponding set of intermediate computer software code;

encoding means for encoding said intermediate computer software code into tamper-resistant intermediate computer software code having a domain which does not have a corresponding semantic structure, to increase the tamper-resistance and obscurity of said computer software code; and

back end compiler means for compiling said tamper-resistant intermediate computer software code into tamper-resistant computer software object code.