Tamper resistant software encoding

• US 6,842,862 B2
• Filed: 01/10/2003
• Issued: 01/11/2005
• 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: Gu, Yuan, Johnson, Harold J., Chow, Stanley T.
• Primary Examiner(s): Peeso, Thomas R.
• Application Number:
  US10/340,410
• Publication Number:
  US 20030221121A1
• Time in Patent Office: 732 Days
• Field of Search: 713/190, 713/189, 713/194, 713/200, 713/201, 713/165, 713/166, 713/187
• 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:

transforming the data flow of said computer software code to dissociate the observable operation of the transformed said computer software code from the intent of the original software code;

thereby rendering said computer software code resistant to tampering, yet still executable in the same environments as the unprotected form of said computer software code.

2. The method of claim 1, wherein said step of transforming comprises the steps of:

producing new software code which depends critically on constraints, so any modification results in erroneous operation.

3. The method of claim 1, wherein said step of transforming comprises:

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.

4. The method of claim 1 wherein said step of transforming comprises the step of:

transforming a system of equations that define the data flow of at least part of said computer software code, to a new and coordinated system of equations that dissociate the observable operation of the transformed said computer software code from the original intent, and to render it resistant to tampering.

5. The method of claim 4 wherein said step of encoding comprises

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

6. The method of claim 5, further comprising the subsequent step of:

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

7. The method of claim 6, wherein said step of dispersing comprises:

redefining a variable using a technique selected from the group of;

residue coding;

bit-explosion;

bit-residue; and

custom base coding.

8. The method of claim 4 wherein said step of encoding comprises:

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. The method of claim 8 wherein said step of encoding comprises:

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

10. The method of claim 9, wherein said step of defining comprises:

redefining a variable using a technique selected from the group of;

polynomial coding;

residue coding;

bit-explosion;

bit-residue; and

custom base coding.

11. The method of claim 8, wherein said step of transforming comprises the step of:

minimizing the appearance of the data in their original form.

12. The method at claim 4 wherein said step of transforming comprises the step of:

transforming a system of equations that define the data flow in at least part at said computer software code, to a new and coordinated system of equations, which act as a plan, for the dissociation of the observable operation of the transformed said computer software code from the original intent, and to render it resistant to tampering.

13. The method of claim 12, wherein said step of transforming comprises the steps of:

analysing a system of equations that define the data flow in at least part of said computer software code; and

developing a new and coordinated system of equations that dissociate the observable operation of the transformed said computer software code from the original intent and to render it resistant to tampering;

followed by the step of transforming said system of equations in accordance with said new and coordinated system of equations.

14. The method of claim 13, further comprising the step of:

optimizing said transformed system of equations.

15. The method of claim 12, wherein said stop of transforming comprises the steps of:

first assigning new codings to said system of equations;

followed by the step of performing changes to said system of equations to affect said new codings.

16. The method of claim 4 wherein said step of transforming comprises the step of:

transforming a system of equations that define the data flow of at least part of said computer software code, in view of all graph-wide constraints, to a new and coordinated system of equations that dissociate the observable operation of the transformed said computer software code from the original intent, and to render it resistant to tampering.

17. The method of claim 16 wherein said step of transforming comprises the step of:

randomly varying arguments within bounds that will not cause a failure, whereby small modifications will cause nonsensical computations without immediate failure.

18. The method of claim 16 where said step of transforming further comprises the step of:

proposing a new and coordinated system of equations that dissociate the observable operation of the transformed said computer software code form the original intent, and to render it resistant to tampering;

traversing said at least part of the data flow graph of said computer software code to collect constraints on said new and coordinated system of equations; and

replacing said original system of equations with said proposed new and coordinated system of equations.

19. The method of claim 16 wherein said step of transforming comprises the steps of:

traversing at least part of the data flow graph of said computer software code to identify a system of equations that define said data flow;

proposing a new and coordinated system of equations that dissociate the observable operation of the transformed said computer software code from the original intent, and to render it resistant to tampering;

traversing said at least part of the data flow graph of said computer software code to identify mismatches between said original system of equations and said proposed new and coordinated system of equations; and

responding to a determination that there are no mismatches by;

traversing said at least part of the data flow graph of said computer software code to replace said original system or equations with said proposed new and coordinated system of equations.

20. The method of claim 19, further comprising the step of:

responding to a determination that mismatches exist by;

re-coding said proposed new and coordinated system or equations to eliminate said mismatches.

21. The method of claim 16 wherein said step of transforming comprises 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.

22. The method of claim 21 wherein said step of transforming further comprises the step of:

determining where said transformed computer software code would trap and modifying code to perform nonsensical operation rather than trapping.

23. The method of claim 21, wherein said step of encoding comprises the step of:

defining an individual variable in said computer software code as a plurality of new variables.

24. The method of claim 23 wherein said step of encoding comprises:

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.

25. The method of claim 24 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.

26. The method of claim 25 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.

27. The method of claim 23, wherein said step or encoding comprises:

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

28. The method of claim 27, further comprising the step of:

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

29. The method of claim 28, further comprising the step of:

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

30. The method of claim 29, where step of responding comprises 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.

31. The method of claim 21, wherein said step of encoding comprises the step of:

defining many variables or constants in said software code as many new equations, where each new variable depends on all old variables.

32. The method of claim 31 wherein said step of encoding comprises:

generating and storing a set of relatively prime factors; and

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

33. The method of claim 32, further comprising the steps of:

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.

34. The method of claim 33 wherein said step of transposing comprises selecting a block of SSA code and transposing said block at SSA code into a corresponding set of residual code by calculating residues based on said set of relatively prime factors.

35. The method of claim 32 wherein said step of encoding comprises:

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

36. The method of claim 35 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.

37. The method of claim 32 wherein said step of encoding comprises:

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.

38. The method of claim 37 wherein said stop of selecting comprises selecting values of constants in said new polynomial equations to invert the sense of an arithmetic operation in said polynomial equation.

39. The method of claim 38 wherein:

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

said slop 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.

40. The method of claim 21, wherein said step of encoding comprises the step of:

defining many variables or constants in said software code as one now variable.

41. The method of claim 40, further comprising the step of:

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

42. The method of claim 21, 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 set of n-boolean variables with said corresponding table lookup.

44. The method of claim 21 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.

45. The method of claim 44, wherein said steps of encoding and adding code comprise:

redefining a variable using a technique selected from the group of;

polynomial coding;

residue coding;

bit-explosion;

bit-residue; and

custom base coding.

43. The method of claim wherein said step of encoding comprises the step of:

modifying selected expressions in said computer software code to allow a broader range of values for variables so that certain operations on the variables will execute without errors, some of the lime, without causing the encoded software to immediately fail.