System and method for cloaking software

• US 6,192,475 B1
• Filed: 03/25/1998
• Issued: 02/20/2001
• Est. Priority Date: 03/31/1997
• Status: Expired due to Term

• Current Assignee: Cloakworks Incorporated
• Original Assignee: Cloakworks Incorporated
• Inventors: Wallace, David R.
• Primary Examiner(s): Peeso, Thomas R.
• Assistant Examiner(s): JACK, TODD M
• Application Number:
  US09/048,138
• Time in Patent Office: 1,063 Days
• Field of Search: 713/187, 713/190, 713/189, 713/193, 705/55
• US Class Current: 713/190
• CPC Class Codes: G06F 21/14 against software analysis or reverse engineering, e.g. by obfuscation

Abstract

A system and method for rewriting software into a protected form, called cloaked software, such that this cloaked form is protected from analysis or reverse engineering while at the same time the cloaked software is executable. Further, said cloaked software may be set up so that it requires a correct key or keys to be supplied, when it is to be run, for it to execute correctly. Cloaking modifies the basic operations within the software so that the logical connections or data flow among the program operations is no longer visible. In fact, cloaking makes the correct dataflow among operations dependent on a complex interrelated set of addressing operations within the cloaked program. These addressing operations are designed so that their analysis is equivalent to a computationally intractable NP-complete problem. This situation prevents reverse-engineering and unauthorized tampering. Further, these interrelated addressing operations may be set up to use a key or keys in a way that is integral to their operation. This makes the key or keys necessary for correct program operation in such a way that removing the program'"'"'s need for the keys requires the solution of an NP-complete problem.

Claims

1. A method for utilizing a data processor to protect a software program, comprising:

a) inputting said program;

b) analyzing said program to gather symbol information on one or more original variables used within said program;

c) using said symbol information to compute cloaked variables, with new addressing expressions, corresponding to one or more of said original variables, such that said cloaked variables use dynamic addressing, which changes at runtime, rather than fixed constant addressing;

d) replacing a plurality of said original variables by said cloaked variables, updating said program and thereby creating a protected program;

e) outputting said protected program;

whereby it becomes difficult to determine when two variables refer to the same or different actual memory locations in said protected program and whereby the flow of values through said protected program becomes hidden.

2. A method according to claim 1 further comprising:

a) augmenting said program with a plurality of key variables including program code to initialize said key variables with a plurality of key values;

b) incorporating said key variables into the computation of said new addressing expressions for said cloaked variables;

whereby said protected program cannot run properly without correct said key values being provided.

3. A method according to claim 1 further comprising:

a) augmenting said program with code to gather system identification values at the time said program is running;

b) augmenting said program with code to place said identification values into a plurality of identification variables;

c) incorporating said identification variables into computation of said new addressing expressions for said cloaked variables;

whereby said protected program cannot run properly without correct said identification values being provided.

4. A method according to claim 1 wherein c) further comprises:

a) reading said symbol information;

b) replacing a plurality of said original variables by said cloaked variables such that given any two said cloaked variables with conflicting lifetimes where the difference of the addressing expressions for two said cloaked variables is formed into a different matrix, said difference matrix having only non-zero solutions within the operation of said program;

whereby it is assured that no two of said cloaked variables, in fact, do not conflict during the operation of said program.

5. A method according to claim 1 wherein c) further comprises:

a) reading said symbol information;

b) replacing a plurality of said original variables by said cloaked variables such that given any two said cloaked variables within the same lifetime where the difference of the addressing expressions for two said cloaked variables is formed into a masking matrix, said masking matrix derivable, via a series of simple matrix row operations, from a matrix with each row clearly of zero value, based on the relationship among addressing and induction variables in the program;

whereby two said original variables that both, before cloaking, used to refer obviously to the same storage location, now appear, after replacement with said cloaked variables, to refer to different storage locations.

6. A method for utilizing a data processor to protect a software program, comprising:

a) inputting said program;

b) analyzing said program to gather symbol information on one or more original variables used within said program;

c) using said symbol information to compute cloaked variables, with new addressing expressions, corresponding to one or more of said original variables, such that said cloaked variables use dynamic addressing, which changes at run-time, rather than fixed constant addressing;

d) replacing a plurality of said original variables by said cloaked variables, updating said program and thereby creating a protected program;

e) outputting said protected program;

whereby it becomes difficult to determine when two variables refer to the same or different actual memory locations in said protected program and whereby the flow of values through said protected program becomes hidden wherein c) further comprises

f) analyzing a plurality of lifetimes of said original variables used in said program and forming a lifetime conflict graph;

g) coloring each of a plurality of lifetimes of said conflict graph with a color matrix that is computed using a means such that the matrix corresponding to the difference of the corresponding said color matrices for two said lifetimes that conflict, has no zero solution;

h) using said symbol information, forming a plurality of equations representing relations among variable addressing expressions, including induction variable addressing expressions;

i) forming a masking matrix for each of said lifetimes and for each color within a single said lifetime, by writing a plurality of said equations as matrix rows, combining said rows into a matrix and applying random row operations to said matrix, forming a masking matrix, and then adding said masking matrix to said color matrix for said single lifetime, forming the reference matrix for said reference;

j) transforming each reference matrix into an array variable reference which is said cloaked variable with said new addressing expression.

7. A method according to claim 6, wherein g) said conflict graph comprises:

k) assigning a color matrix to an uncolored node or lifetime, not yet so colored, by choosing a color matrix not represented among the color matrices already assigned to neighbors of said uncolored node;

if a previously used color matrix is not among said color matrices already assigned to said neighbors, then assigning said previous used color matrix to said uncolored node;

otherwise deriving a new color matrix to assign to said uncolored node;

l) deriving said new color matrix, when required in step a) above, by choosing an arbitrary matrix if this is the first of said new color matrices;

otherwise deriving subsequent color matrices by adding a new separation matrix to the previous color matrix;

m) deriving said new separation matrix, when required in step b) above, by deriving a matrix by means such that said new separation matrix has no zero solution within said program and such that the sum of said new separation matrix with any plurality of separation matrices previously derived in this step is a matrix, also with no zero solution within said program.

8. A method according to claim 7, wherein m) further comprises:

n) deriving a plurality of inequality constraints from said derived program, creating a constraint island;

o) choosing a lattice whose points do not meet said constraint island and that further said lattice is chosen so that the corresponding points, with the same lattice coefficients, of the previously chosen lattices fall within a convex region that also does not meet said constraint island;

p) forming said lattice'"'"'s vector generators into column vectors which are combined together to form a partial matrix which is further combined with rows corresponding to said constraints from step n) to form the separation matrix.

9. A method for utilizing a data processor to create matrices, called separation matrices, that do not have zero solutions within certain regions of an application program, comprising the steps of:

a) analyzing said application program to derive a plurality of inequality constraints for a particular region of said program, creating a constraint island;

b) choosing a lattice whose points do not meet said constraint island;

c) forming said lattice'"'"'s vector generators into column vectors which are combined together to form a partial matrix which is further combined with rows corresponding to said constraints from step a) to form the separation matrix;

whereby the separation matrix does not have a zero solution within said region of said application program.

a) a means of augmenting said program with a plurality of key variables including program code to initialize said key variables with a plurality of key values;

b) a means of incorporating these said key variables into the computation of said new addressing expressions for said cloaked variables;

whereby said protected program cannot run properly without the correct said key values being provided.

10. A method according to claim 9 wherein a means is provided to select a series of separation matrices such that the componentwise sum of a plurality of matrices from said series is a matrix which is again a separation matrix.

11. A method for utilizing a data processor to create matrices, called masking matrices, that only have zero solutions within certain regions of an application program, comprising the steps of:

a) analyzing said application program to derive a plurality ot equality constrants for a particular region of said program, including, but not limited to, induction variable relations;

b) forming said equality constraints into rows to form a matrix;

c) applying random row operations to said matrix to form the masking matrix;

whereby the masking matrix has only a zero solution within said region of said application program.

12. An apparatus for modifying a software application program to put it into a protected form, comprising:

a) a means of inputting said program;

b) a means of analyzing said program to gather symbol information on a plurality of original variables used within said program;

c) a means of using said symbol information to compute cloaked variables, with new addressing expressions, corresponding to a plurality of said original variables using a means such that said cloaked variables use dynamic addressing, which changes at run-tine, rather than fixed constant addressing;

d) a means of replacing a plurality of said original variables by said cloaked variables, updating said program and thereby creating a protected program;

e) a means of outputting said protected program;

whereby it becomes difficult to determine when two variables refer to the same or different actual memory locations in said protected program and whereby the flow of values through said protected program becomes hidden.

13. An apparatus according to claim 12 further including:

a) a means of augmenting said program with a plurality of key variables including program code to initialize said key variables with a plurality of key values;

b) a means of incorporating these said key variables into the computation of said new addressing expressions for said cloaked variables;

whereby said protected program cannot run properly without the correct said key values being provided.

15. An apparatus according to claim 12 wherein the means c) comprises:

a) a means of reading said symbol information;

b) a means of replacing a plurality of said original variables by said cloaked variables such that given any two said cloaked variables with conflicting lifetimes where we have formed the difference of the addressing expressions for two said cloaked variables into a difference matrix, this said difference matrix has only non-zero solutions within the constraints of said program;

whereby we are assured that two said cloaked variables, in fact, do not conflict during the operation of said program.

16. An apparatus according to claim 12 wherein the means c) comprises:

a) a means of reading said symbol information;

b) a means of replacing a plurality of said original variables by said cloaked variables such that given any two said cloaked variables within the same lifetime where we have formed the difference of the addressing expressions for two said cloaked variables into a masking matrix, this said masking matrix is derivable, via a series of simple matrix row operations, from a matrix with each row clearly of zero value, based on the relationship among addressing and induction variables in the program;

whereby two said original variables that both, before cloaking, used to refer obviously to the same storage location, now appear, after replacement with said cloaked variables, to refer to different storage locations.

14. An apparatus for modifying a software application program to put it into a protected form, comprising:

a) a means of inputting said program;

b) a means of analyzing said program to gather symbol information on a plurality of original variables used within said program;

c) a means of using said symbol information to compute cloaked variables, with new addressing expressions, corresponding to a plurality of said original variables using a means such that said cloaked variables use dynamic addressing, which changes at run-time, rather than fixed constant addressing;

d) a means of replacing a plurality of said original variables by said cloaked variables, updating said program and thereby creating a protected program;

e) a means of outputting said protected program;

whereby it becomes difficult to determine when two variables refer to the same or different actual memory locations in said protected program and whereby the flow of values through said protected program becomes hidden;

f) a means of augmenting said program with code to gather system identification values at the time said program is running;

g) a means of augmenting said program with code to place said identification values into a plurality of identification variables;

h) a means of incorporating these said identification variables into the computation of said new addressing expressions for said cloaked variables;

whereby said protected program cannot run properly without the correct said identification values being provided.

17. An apparatus for modifying a software application program to put it into a protected form, comprising:

a) a means of inputting said program;

b) a means of analyzing said program to gather symbol information on a plurality of original variables used within said program;

c) a means of using said symbol information to compute cloaked variables, with new addressing expressions, corresponding to a plurality of said original variables using a means such that said cloaked variables use dynamic addressing, which changes at run-time, rather than fixed constant addressing;

d) a means of replacing a plurality of said original variables bv said cloaked variables, updating said program and thereby creating a protected program;

e) a means of outputting said protected program;

whereby it becomes difficult to determine when two variables refer to the same or different actual memory locations in said protected program and whereby the flow of values through said protected program becomes hidden;

wherein the means c) of computing said cloaked variables with said new addressing expressions, corresponding to a plurality of said original variables comprises;

f) a means of analyzing a plurality of lifetimes of said original variables used in said program and forming a lifetime conflict graph;

g) a means of coloring each of a plurality of lifetimes of said conflict graph with a color matrix that is computed using a means such that the matrix corresponding to the difference of the corresponding said color matrices for two said lifetimes that conflict, has no zero solution;

h) a means of using said symbol information, forming a plurality of equations representing relations among variable addressing expressions, including induction variable addressing expressions;

i) a means of forming a masking matrix for each lifetime and for each reference within a single lifetime, by writing a plurality of said equations as matrix rows, combining said rows into a matrix and applying random row operations to said matrix, forming a masking matrix, and then adding said masking matrix to said color matrix for said single lifetime, forming the reference matrix for said reference;

j) a means of transforming each reference matrix into an array variable reference which is said cloaked variable with said new addressing expression.

18. An apparatus according to claim 17, wherein the means b) of coloring lifetimes of said conflict graph comprises:

a) a means of assigning a color matrix to an uncolored node or lifetime, not yet so colored, by choosing a color matrix not represented among the color matrices already assigned to neighbors of said uncolored node;

if a previously used color matrix is not among said color matrices already assigned to said neighbors, then assigning said previously used color matrix to said uncolored node;

otherwise deriving a new color matrix to assign to said uncolored node;

b) a means of deriving said new color matrix, when required in step a) above, by choosing an arbitrary matrix if this is the first of said new color matrices;

otherwise deriving subsequent color matrices by adding a new separation matrix to the previous color matrix;

c) a means of deriving said new separation matrix, when required in step b) above, by deriving a matrix by means such that said new separation matrix has no zero solution within said program and such that the sum of said new separation matrix with any plurality of separation matrices previously derived in this step is a matrix, also with no zero solution within said program.

19. An apparatus according to claim 18, wherein the means c) of deriving said new separation matrix comprises:

a) a means of deriving a plurality of inequality constraints from said derived program, creating a constraint island;

b) a means of choosing a lattice whose points do not meet said constraint island and that further said lattice is chosen so that the corresponding points, with the same lattice coefficients, of the previously chosen lattices fall within a convex region that also does not meet said constraint island;

c) a means of forming said lattice'"'"'s vector generators into column vectors which are combined together to form a partial matrix which is further combined with rows corresponding to said constraints from step a) to form the separation matrix.

20. An apparatus to create matrices, called separation matrices, that do not have zero solutions within certain regions of an application program, comprising:

a) a means of analyzing said application program to derive a plurality of inequality constraints for a particular region of said program, creating a constraint island;

b) a means of choosing a lattice whose points do not meet said constraint island,

c) a means of forming said lattice'"'"'s vector generators into column vectors which are combined together to form a partial matrix which is further combined with rows corresponding to said constraints from step a) to form the separation matrix;

whereby the separation matrix does not have a zero solution within the operation of said application program.

21. An apparatus according to claim 20, wherein a means is provided to select a series of separation matrices such that the componentwise sum of a plurality of matrices from said series is a matrix which is again a separation matrix.

22. An apparatus to create matrices, called masking matrices, that only have zero solutions within certain regions of an application program, comprising:

a) a means of analyzing said application program to derive a plurality of equality constraints for a particular region of said program, including, but not limited to, induction variable relations;

b) a means of forming said equality constraints into rows to form a matrix;

c) a means of applying random row operations to said matrix to form the masking matrix;

whereby the masking matrix has only a zero solution within the operation of said application program.