Tamper resistant software-control flow encoding

• US 6,779,114 B1
• Filed: 08/19/1999
• Issued: 08/17/2004
• Est. Priority Date: 08/19/1999
• Status: Expired due to Fees

• Current Assignee: Cloakware Incorporated (MultiChoice Group Ltd.)
• Original Assignee: Cloakware Incorporated (MultiChoice Group Ltd.)
• Inventors: Johnson, Harold J., Chow, Stanley T., Gu, Yuan
• Primary Examiner(s): Barrón, Gilberto
• Assistant Examiner(s): Gurshman, Grigory
• Application Number:
  US09/377,312
• Time in Patent Office: 1,825 Days
• Field of Search: 713/189, 713/194, 713/190
• US Class Current: 713/189
• CPC Class Codes: G06F 21/14 against software analysis or reverse engineering, e.g. by obfuscation

Abstract

The present invention relates to a method and system of making computer software resistant to tampering and reverse-engineering. “Tampering” refers to making unauthorized changes to software, such as bypassing password checks, which are of benefit to the tamperer or of detriment to the provider or vendor of the software. Thus, tampering does not denote arbitrary destructive changes, such as causing the software to fail completely. Broadly speaking, the method of the invention is to increase the tamper-resistance and obscurity of software so that the observable operation of the transformed software is dissociated from the intent of the original code, and so that the functionality of the software is extremely fragile when modified: any modification will, with high probability, produce persistently nonsensical behaviour. These effects are achieved by converting the control-flow of the software into data-driven form, and increasing the complexity of the control-flow by orders of magnitude.

Claims

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

transforming a control flow of said computer software code from a semantic structure related to an original source code for said computer software code, into a control flow which does not have a corresponding semantic structure by;

re-sorting said source code instructions into lumps;

placing non-deterministic branches at the exit point(s) of each said lump to indicate the legitimate emulation sequences for the represented code, including dummy variables with fake-robust references; and

renaming the virtual registers (VRs) in each lump to effect lump to lump control transfers;

dissociating the observable operation of the transformed computer software code from that of the original software code and increasing the tamper-resistance and obscurity of said computer software code.

2. The method as claimed in claim 1, wherein said semantically exposed form code comprises static single assignment form or equivalent form exposing definition-use chains and definition merges.

3. The method as claimed in claim 2, wherein said step of re-sorting comprises the step of:

randomizing the positions of said instructions in said semantically exposed form within their containing routines;

arbitrarily selecting contiguous straight line sequences of code, or pieces, from said computer software code, which may include overlapping pieces; and

grouping the said pieces into lumps comprising multiple, arbitrarily selected pieces.

4. The method as claimed in claim 3 wherein said step of randomizing comprises the step of:

randomizing the positions of said instructions in said semantically exposed form within their containing routines, within the limits imposed by their dependency relationships, including randomizations across basic block and branch boundaries, to scatter instructions among the pieces to be selected thereafter.

5. The method as claimed in claim 4 wherein prior to said step of placing, performing the steps of:

creating a renaming map for each lump, which maps the virtual registers used in the original code onto the VRs to be used in the new code for the lumps;

assigning sets of roles for the lumps, and adding sufficient entry points and/or exit points so that it is possible to completely set up the various data contexts for each lump using only φ

-assignments or using only VR-to-VR transfers; and

assigning a tag for each lump, each lump entry point, and each lump exit point, so that all of the tag assignments are unique within a routine group.

6. A method as claimed in claim 5 wherein said step of placing comprises:

placing non-deterministic branches at the exit point(s) of each lump to indicate the legitimate emulation sequences for the represented code; and

creating dummy variables with fake-robust references.

7. A method as claimed in claim 6 wherein said step of re-naming comprises:

tabulating lump to lump control transfers;

generating new basic blocks for all lumps, including their instructions, including one basic block for the lump itself, which contains code for the computations of the pieces in the lump; and

renaming the VRs in each lump to use the new VRs defined by the renaming maps rather than the old ones, and inserting the code to transfer VRs among lumps according to the VR switching tables.

8. The method as claimed in claim 7 wherein said step of generating further comprises the steps of:

responding to a lump having multiple lump entry points, by generating one basic block for each entry point; and

responding to a lump having multiple lump exit points, by generating one basic block for each exit point.

9. A method as claimed in claim 8 wherein said step of renaming comprises:

renaming the VRs in each lump to use the new VRs defined by the renaming maps rather than the old ones, and inserting the code to transfer VRs among lumps according to the VR switching tables, by adding φ

-assignments.

10. A method as claimed in claim 9 wherein prior to the step of compiling said simplified intermediate code into object code, performing the steps of:

performing data flow encoding on code in lumps; and

simplifying said intermediate code.

14. The method as claimed in claim 1, wherein said step of transforming further comprises:

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

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

15. The method as claimed in claim 14, wherein said step of re-ordering comprises the step of:

randomly re-ordering code instructions within said replicated subsequences of instructions within constraints of operability.

16. The method as claimed in claim 15, wherein said constraints include data constraints.

17. The method as claimed in claim 15, wherein said constraints include condition constraints.

18. The method as claimed in claim 15, wherein said constraints include dominator constraints.

19. The method as claimed in claim 15, wherein said constraints include post-dominator constraints.

20. The method as claimed in claim 15, wherein said constraints include non-trapping unaliased early copying constraints.

21. The method as claimed in claim 15, wherein said constraints include non-trapping unaliased late copying constraints.

22. The method as claimed in claim 1, wherein said fake-robust control transfers are combined, so that changing individual steps in control flow is infeasible.

23. The method as claimed in claim 1, wherein said step of adding fake-robust control transfers is performed using fault resistant programming techniques.

24. The method as claimed in claim 1 wherein said step of transforming is performed on said computer software code in successive phases.

25. The method as claimed in claim 24 wherein said successive phases are managed using a phase control file.

26. The method as claimed in claim 1, wherein said step of transforming comprises the steps of:

analysing a portion of the graph that defines the control flow in at least part of said computer software code;

developing a set of control flow modifications including re-sorting instructions, placing non-deterministic branches and renaming VRs; and

modifying said control flow in at least part of said computer software code in accordance with said set of control flow modifications.

27. The method as claimed in claim 26, further comprising the step of:

optimizing said set of modified code.

28. The method as claimed in claim 1, wherein said step of transforming comprises the step of:

replicating subsequences of instructions within said computer software code into a plurality of locations.

29. A method as claimed in claim 28, wherein said step of replicating comprises the steps of:

dispersing subsequences of instructions within said computer software code into a plurality of locations;

merging multiple dispersed subsequences into single blocks of code;

selecting said subsequences of instructions from merged blocks of code for either functionally effective or decoy execution, as needed, to separate the observable operation of resulting code from the intent of the original computer software code during execution.

30. The method as claimed in claim 28, further comprising the step of:

re-ordering code instructions within said replicated subsequences of instructions.

31. A method as claimed in claim 1, further comprising the step of:

protecting the data-flow of the resulting code using a data-flow obscuring and/or tamper-proofing technology, to obscure and tamper-proof said computer software code comprehensively.

32. A method as claimed in claim 1 wherein said step of converting comprises the step of:

obscuring the control flow of said computer software code using branch indexing via scalar functions, pervasive induced fragility to tampering and probabilistic deterioration under tampering, to increase the tamper-resistance of said computer software code.

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

means for transforming a control flow of said computer software code from a semantic structure related to an original source code for said computer software code, into a control flow which does not have a corresponding semantic structure, including;

means for re-sorting assignments in said computer software code without changing the semantic operation of said computer software code;

means for copying multiple different segments of said computer software code into new segments; and

means for adding fake-robust control transfers to said new segments, to increase the tamper-resistance of said computer software code;

dissociating the observable operation of the transformed computer software code from that of the original software code and increasing the tamper-resistance and obscurity of said computer software code.

12. A computer readable memory medium, storing computer software code for increasing the tamper-resistance and obscurity of a targeted software program, said computer software code executable to perform the steps of:

transforming said targeted software program by encoding a control flow of said targeted software program from a semantic structure related to an original source code for said targeted software program, into a control flow which does not have a corresponding semantic structure, by;

re-sorting assignments in said targeted software program without changing the semantic operation of said targeted software program;

copying multiple different segments of said targeted software program into new segments; and

adding fake-robust control transfers to said new segments, to increase the tamper-resistance of said targeted software program;

dissociating the observable operation of the transformed targeted software program from that of the original targeted software program and increasing the tamper-resistance and obscurity of said targeted software program.

13. A computer data signal embodied in a carrier wave, said computer data signal comprising a set of machine executable code operable to increase the tamper-resistance and obscurity of a targeted software program, said machine executable code executable to perform the steps of:

transforming said targeted software program by encoding a control flow of said targeted software program from a semantic structure related to an original source code for said targeted software program, into a control flow which does not have a corresponding;

semantic structure, by;

re-sorting assignments in said targeted software program without changing the semantic operation of said targeted software program;

copying multiple different segments of said targeted software program into new segments; and

adding fake-robust control transfers to said new segments, to increase the tamper-resistance of said targeted software program;

dissociating the observable operation of the transformed targeted software program from that of the original targeted software program and increasing the tamper-resistance and obscurity of said targeted software program.