US6779114B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Tamper resistant software-control flow encoding
Assignee: Cloakware Corp
•
Filing: 1999-08-19
•
Granted: 2004-08-17
•
Expires: 2019-08-19
Abstract
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.
Inventors
- 👤 Stanley T. Chow
- 👤 Harold J. Johnson
- 👤 Yuan Gu
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 17:36
CPC Classifications
G; G06; G06F; G06F21/00; G06F21/10; G06F21/12; G06F21/14
Claims Analysis
Total Claims: 36
Claim 1
Independent Claim
132 words
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.
Claim 2
Independent Claim
132 words
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.
Claim 3
Dependent Claim
28 words
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.
Claim 4
Dependent Claim
64 words
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.
Claim 5
Dependent Claim
57 words
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.
Claim 6
Dependent Claim
116 words
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.
Claim 7
Dependent Claim
40 words
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.
Claim 8
Dependent Claim
86 words
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.
Claim 9
Dependent Claim
54 words
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.
Claim 10
Dependent Claim
52 words
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.
Claim 11
Dependent Claim
38 words
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.
Claim 12
Independent Claim
133 words
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.
Claim 13
Independent Claim
133 words
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.
Claim 14
Dependent Claim
149 words
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.
Claim 15
Dependent Claim
149 words
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.
Claim 16
Dependent Claim
161 words
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.
Claim 17
Dependent Claim
161 words
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.
Claim 18
Dependent Claim
57 words
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.
Claim 19
Dependent Claim
31 words
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.
Claim 20
Dependent Claim
14 words
The method as claimed in claim 15 , wherein said constraints include data constraints.
Claim 21
Dependent Claim
14 words
The method as claimed in claim 15 , wherein said constraints include condition constraints.
Claim 22
Dependent Claim
14 words
The method as claimed in claim 15 , wherein said constraints include dominator constraints.
Claim 23
Dependent Claim
14 words
The method as claimed in claim 15 , wherein said constraints include post-dominator constraints.
Claim 24
Dependent Claim
17 words
The method as claimed in claim 15 , wherein said constraints include non-trapping unaliased early copying constraints.
Claim 25
Dependent Claim
17 words
The method as claimed in claim 15 , wherein said constraints include non-trapping unaliased late copying constraints.
Claim 26
Dependent Claim
25 words
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.
Claim 27
Dependent Claim
23 words
The method as claimed in claim 1 , wherein said step of adding fake-robust control transfers is performed using fault resistant programming techniques.
Claim 28
Dependent Claim
22 words
The method as claimed in claim 1 wherein said step of transforming is performed on said computer software code in successive phases.
Claim 29
Dependent Claim
18 words
The method as claimed in claim 24 wherein said successive phases are managed using a phase control file.
Claim 30
Dependent Claim
76 words
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.
Claim 31
Dependent Claim
19 words
The method as claimed in claim 26 , further comprising the step of: optimizing said set of modified code.
Claim 32
Dependent Claim
31 words
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.
Claim 33
Dependent Claim
78 words
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.
Claim 34
Dependent Claim
22 words
The method as claimed in claim 28 , further comprising the step of: re-ordering code instructions within said replicated subsequences of instructions.
Claim 35
Dependent Claim
36 words
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.
Claim 36
Dependent Claim
50 words
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.
References Cited (Backward Citations)
US5123045A
Cited
EP0735468A2
Cited
US5659754A
Cited
WO1997004394A1
Cited
US5768596A
Cited
US5892899A
Cited
US6192475B1
Cited
WO1999001815A1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2007-08-17 | 2008-02-16 | 2008-08-17 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2011-08-17 | 2012-02-16 | 2012-08-17 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2015-08-17 | 2016-02-16 | 2016-08-17 | $7700.00 | Window Closed / Lapsed |