Technique for producing through watermarking highly tamper-resistant executable code and resulting “watermarked” code so formed

• US 7,051,208 B2
• Filed: 10/21/2004
• Issued: 05/23/2006
• Est. Priority Date: 03/14/2000
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Venkatesan, Ramarathnam, Vazirani, Vijay
• Primary Examiner(s): Barron, Gilberto
• Assistant Examiner(s): Kim, Jung W.
• Application Number:
  US10/970,425
• Publication Number:
  US 20050144458A1
• Time in Patent Office: 579 Days
• Field of Search: 713/176, 713/179, 713/189, 713/190, 713/194
• US Class Current: 713/176
• CPC Class Codes: G06F 21/14 against software analysis or reverse engineering, e.g. by obfuscation
• CPC Class Codes: G06F 21/16 Program or content traceability, e.g. by watermarking

Abstract

Apparatus and an accompanying method, for forming and embedding a highly tamper-resistant cryptographic identifier, i.e., a watermark, within non-marked executable code, e.g., an application program, to generate a “watermarked” version of that code. Specifically, the watermark, containing, e.g., a relatively large number of separate executable routines, is tightly integrated into a flow pattern of non-marked executable code, e.g., an application program, through randomly establishing additional control flows in the executable code and inserting a selected one of the routines along each such flow. Since the flow pattern of the watermark is highly intertwined with the flow pattern of the non-marked code, the watermark is effectively impossible to either remove from the code and/or circumvent. The routines are added in such a manner that the flow pattern of resulting watermarked code is not substantially different from that of the non-marked code, thus frustrating third party detection of the watermark using, e.g., standard flow analysis tools. To enhance tamper-resistance of the watermarked code, each such routine can provide a pre-defined function such that if that routine were to be removed from the marked code by, e.g., a third party adversary, then the marked code will prematurely terminate its execution.

Claims

1. Apparatus for forming an identifier for an input object and for securely marking the input object with the identifier so as to yield a marked object, apparatus comprising:

means for storing computer executable instructions therein;

means for performing acts, in response to the stored executable instructions, the acts comprising;

generating a flow representation for the input object, the representation having a plurality of nodes, said nodes representing pre-defined first operations performed by the input object, and connections among the nodes signifying associated flow among the pre-defined first operations performed by the input object;

randomly selecting first and second nodes from the plurality of nodes in the representation so as to form a pre-defined number of nodal pairs, each of said pairs having one of the first nodes and a corresponding one of the second nodes;

for each of the nodal pairs, forming an executable procedure associated with each of the nodal pairs by establishing flow between the first and second nodes in said each nodal pair and inserting, in the flow so established, a selected one of a plurality of different pre-defined second operations so as to collectively define the marked object, whereby the marked object implements the pre-defined first operations and a plurality of selected ones of the pre-defined second operations, each of which has been randomly spliced into flow of the input object, wherein the identifier collectively comprises all ones which differ within the plurality of pre-defined second operations, and execution flow associated therewith and involving the nodal pairs;

inserting a pre-defined number of separate links and designations for selected ones of the procedures into the flow representation so as to yield a combined flow representation; and

converting, in response to said input executable code and executable code for said selected ones of the procedures, said combined flow representation into output executable code, said output executable code being the marked code;

wherein;

the input object comprises a software object which comprises, input executable code, at least one instruction in the input executable code being associated with a corresponding one of the pre-defined first operations, and executable code for a corresponding executable procedure being associated with each selected one of the pre-defined second operations;

the input executable code comprises first and second portions thereof and the flow representation comprises first and second separate flow representations for the first and second portions of the input executable code, respectively;

the first portion of the input executable code comprises at least a pre-defined portion of a non-marked application program; and

the second portion of the input executable code comprises a remaining portion of the non-marked application program or pre-defined executable security code.

2. Apparatus in claim 1 wherein the means for performing acts, in response to the stored instructions, inserts executable code for a selected one procedure in noncontiguous locations in the input executable code.

3. Apparatus in claim 1 wherein the means for performing acts, in response to the stored instructions, selects a procedure from a pre-defined library of stored routines wherein said procedure is one of the stored routines.

4. Apparatus in claim 1 wherein each of the inserted procedures implements, when executed, a pit-defined function such that if any of said inserted procedures is removed from the marked code, the marked code, when subsequently executed, will terminate its execution.

5. Apparatus in claim 1 wherein at least one of the inserted procedures implements, when executed, a pre-defined function which is independent of functionality provided by the non-marked application program.

6. Apparatus in claim 1 wherein the security code provides functionality independent of any functionality provided by application program.

7. Apparatus in claim 1 wherein the means for performing acts, in response to the stored instructions, performs additional acts comprising:

(a) generates first and second separate flow representations for the first and second portions of the input executable code;

(b) partitions each of the first and second flow representations into k clusters each so as to yield first and second cluster flow representations, respectively (where k is a pre-defined integer);

(c) randomly selects the first and second nodes in the first and second cluster flow representations, respectively, so as to form a corresponding one of the nodal pairs;

(d) inset a designation for a selected executable procedure at a first node in the nodal pair; and

(e) repeats operations (c) and (d) a pre-defined number of times so as to insert a pre-defined number of separate procedures into the first and second flow representations so as to yield the combined flow representation.

8. Apparatus in claim 7 wherein the means for performing acts, in response to the stored instructions, inserts executable code for a selected one procedure in noncontiguous locations in the input executable code.

9. Apparatus in claim 7 wherein the means for performing acts, in response to the stored instructions, selects a one procedure from a pre-defined library of stored routines, wherein said one procedure is one of the stored routines.

10. Apparatus in claim 7 wherein each of the inserted procedures implements, when executed, a pre-defined function such that if any of said inserted procedures is removed from the marked code, the marked code, when subsequently executed, will terminate its execution.

11. Apparatus in claim 7 wherein at least one of the inserted procedures implements, when executed, a pre-defined function which is independent of functionality provided by the non-marked application program.

12. Apparatus in claim 7 wherein the means for performing acts, in response to the stored instructions, performs additional acts comprising:

randomly selects a node, U, in the first cluster flow representation;

randomly selects, with probability 1−

λ

(where λ

is a pro-defined value with 0≦

λ

≦

1), a node Y in the second cluster flow representation;

randomly selects, with probability λ

, a node Z, other than U, in the first cluster flow representation; and

provides designations of nodes Y and Z as the nodes forming the nodal pair.

13. Apparatus in claim 7 wherein the means for performing acts, in response to the stored instructions, randomly selects the first and second nodes from different clusters solely within the first cluster flow representation or from different clusters solely within the second cluster flow representation.

14. One or more computer-readable media having computer-executable instructions that, when executed by a computer, perform acts for forming an identifier for input executable code and for securely marking the input executable code with the identifier so as to yield marked code, the acts comprising:

generating a flow representation for the input object, the representation having a plurality of nodes, said nodes representing pre-defined first operations performed by the input object, and connections among the nodes signifying associated flow among the pre-defined first operations performed by an input object;

randomly selecting first and second nodes from the plurality of nodes in the representation so as to form a pre-defined number of nodal pairs, each of said pairs having one of the first nodes and a corresponding one of the second nodes;

for each of the nodal pairs, forming an executable procedure associated with each of the nodal pairs by establishing flow between the first and second nodes in said each nodal pair and inserting, in the flow so established, a selected one of a plurality of different pre-defined second operations so as to collectively define the marked object whereby the marked object implements the pre-defined first operations and a plurality of selected ones of the pre-defined second operations, each of which has been randomly spliced into flow of the input object, wherein the identifier collectively comprises all ones which differ within the plurality of pry-defined second operations, and execution flow associated therewith and involving the nodal pairs;

inserting a pre-defined number of separate links and designations for selected ones of the procedures into the flow representation so as to yield a combined flow representation; and

converting, in response to said input executable code and executable code for said selected ones of the procedures, said combined flow representation into output executable code, said output executable code being the marked code;

wherein;

the input object comprises a software object which comprises input executable code, at least one instruction in the input executable code being associated with a corresponding one of the pre-defined first operations, and executable code for a corresponding executable procedure being associated with each selected one of the pre-defined second operations;

the input executable code comprises first and second portions thereof and the flow representation comprises first and second separate flow representations for the first and second portions of the input executable code, respectively;

the first portion of the input executable code comprises at least a pre-defined portion of a non-marked application program; and

the second portion of the input executable code comprises a remaining portion of the non-marked application program or pre-defined executable security code.

15. One or more media as recited in claim 14 further comprising selecting a procedure from a pre-defined library of stored routines, wherein said procedure is one of the stored routines.

16. One or more media as recited in claim 14 further comprising inserting executable code for a selected one procedure in noncontiguous locations in the input executable code.

17. One or more media as recited in claim 14 wherein each of the inserted procedures implements, when executed, a pre-defined function such that if any of said inserted procedures is removed from the marked code, the marked code, when subsequently executed, will terminate its execution.

18. One or more media as recited in claim 14 wherein at least one of the inserted procedures implements, when executed, a pre-defined function which is independent of functionality provided by the non-marked application program.

19. One or more media as recited in claim 14 wherein the security code provides functionality Independent of any functionality provided by application program.

20. One or more computer-readable media having computer-executable instructions that, when executed by a computer, perform acts for forming an identifier for input executable code and for securely marking the input executable code with the identifier so as to yield marked code, the acts comprising:

generating a flow representation for the input object, the representation having a plurality of nodes, said nodes representing pre-defined first operations performed by the input object, and connections among the nodes signifying associated flow among the pre-defined first operations performed by an input object;

randomly selecting first and second nodes from the plurality of nodes in the representation so as to form a pre-defined number of nodal pairs, each of said pairs having one of the first nodes and a corresponding one of the second nodes;

for each of the nodal pairs, forming an executable procedure associated with each of the nodal pairs by establishing flow between the first and second nodes in said each nodal pair and inserting, in the flow so established, a selected one of a plurality of different pre-defined second operations so as to collectively define the marked object, whereby the marked object implements the pre-defined first operations and a plurality of selected ones of the pre-defined second operations, each of which has been randomly spliced into flow of the input object, wherein the identifier collectively comprises all ones which differ within the plurality of pre-defined second operations, and execution flow associated therewith and involving the nodal pairs;

inserting a pre-defined number of separate links and designations for selected ones of the procedures into the flow representation so as to yield a combined flow representation;

converting, in response to said input executable code and executable code for said selected ones of the procedures, said combined flow representation into output executable code, said output executable code being the marked code;

generating first and second separate flow representations for the first and second portions of the input executable code;

partitioning each of the first and second flow representations into k clusters each so as to yield first and second cluster flow representations, respectively (where k is a pre-defined integer);

randomly selecting the first and second nodes in the first and second cluster flow representations, respectively, so as to form a corresponding one of the nodal pairs;

inserting a designation for a selected executable procedure at a first node in the nodal pair; and

repeating a pre-defined number of times steps “

randomly selecting the first and second nodes” and

“

inserting a designation”

so as to insert a pre-defined number of separate procedures into the first and second flow representations so as to yield the combined flow representation;

wherein;

the input object comprises a software object, which comprises input executable code, at least one instruction in the input executable code being associated with a corresponding one of the pre-defined first operations, and executable code for a corresponding executable procedure being associated with each selected one of the pre-defined second operations;

the input executable code comprises first and second portions thereof and the flow representation comprises first and second separate flow representations for the first and second portions of the input executable code, respectively;

the first portion of the input executable code comprises at least a pre-defined portion of a non-marked application program; and

the second portion of the input executable code comprises a remaining portion of the non-marked application program or pry-defined executable security code.

21. One or more media as recited in claim 20 further comprising inserting executable code for the selected one procedure in noncontiguous locations in the input executable code.

22. One or more media as recited in claim 20 further comprising selecting the procedure from a pre-defined library of stored routines, wherein said procedure is one of the stored routines.

23. One or more media as recited in claim 20 wherein each of the inserted procedures implements, when executed, a pre-defined function such that if any of said inserted procedures is removed from the marked code, the marked code, when subsequently executed, will terminate its execution.

24. One or more media as recited in claim 20 wherein, at least one of the inserted procedures implements, when executed, a pre-defined function which is independent of functionality provided by the non-marked application program.

25. One or more media as recited in claim 20 wherein the first and second nodes randomly selecting step comprises:

randomly selecting a node, U, in the first cluster flow representation;

randomly selecting, with probability 1−

λ

(where λ

is a pre-defined value with 0≦

λ

≦

1), a node Y in the second cluster flow representation;

randomly selecting, with probability λ

, a node Z, other than U, in the first cluster flow representation; and

providing designations of nodes Y and Z as the nodes forming the nodal pair.

26. One or more media as recited in claim 20 wherein the first and second nodes randomly selecting step comprises the step of randomly selecting the first and second nodes from different clusters solely within the first cluster flow representation or from different clusters solely within the second cluster flow representation.