Software watermarking techniques

The A computer implemented method of verifying the integrity or origin of a software object wherein a watermarking computer performs the following functions, including:

• (a) watermarking the software object in a memory of the watermarking computer, wherein a watermark-generating program piece in the memory of the watermarking computer is embedded by the watermarking computer in the software object, in such a way that a watermark graph generated by the watermark-generating program piece becomes present and detectable in an execution state of the watermarked software object within a memory of a verifying computer executing the watermarked software object with an input sequence, the execution state of the watermarked software object in the executing computer comprising all current values in all stacks, heaps, global variables, data registers, and program counters in the memory of the executing computer which have been modified by the executing computer while executing instructions form the watermarked software object;
• (b) building a computerized recognizer for use by the executing computer, wherein the computerized recognizer is adapted to extract the watermark from dynamically allocated data wherein the computerized recognizer is kept separately from the from the watermarked software object;
• wherein the computerized recognizer is adapted to detect the watermark by checking for a watermark integer associated with a watermark graph whose nodes and edges are identified within the execution state of the computerized recognizer.

A computer-readable medium including a program executed on a computer for watermarking software, the program including instructions for:

• (a) embedding a watermark by a watermarking computer in a static string on the watermarking computer;
• (b) including in the software object a watermark-string reproduction program piece, the watermark-string reproduction program piece being executed on at least one input determined during the watermarking process that reproduces the string of step (a), and that produces at least one other string on an executing computer when code is executed with at least one other input;
• and
• (c) using the watermarking computer to transform the watermarked software object created in step (b), using an opaque predicate to obfuscate at least one branch in a string-reproduction program piece of the watermarked software object.

A computer-readable medium including a program executed on a computer for watermarking software, the program including instructions for:

• (a) choosing a watermark graph by a watermarking computer from a class of graphs having a plurality of members having at least one property that are stored in memory and embedding the chosen watermark graph into an execution state of a software object for the program in a memory in a manner that the watermark is detectable by a computerized recognizer which examines the execution state of an executing computer executing the program to find data elements representing nodes having one or more pointer fields representing edges, the execution state of the watermarked software object in the executing computer comprising all current values in all stacks, heaps, global variables, data registers, and program counters in the memory of the executing computer which have been modified by the executing computer while executing instructions from the watermarked software object as the watermarked software object is being run on the computer with a particular input sequence;
• (b) providing the computerized recognizer on the computer-readable medium;
• and
• (c) providing an integrity tester on the computer-readable medium which tests for the satisfaction of the at least one property in a possibly-modified version of the watermarked software object.

A watermarking computer for watermarking software comprising:

• (a) a memory for storing data representing a string that has a watermark embedded in it;
• (b) a memory for storing a program piece;
• (c) a watermarking program piece constructed to accept at least one input determined during a watermarking process such that the watermarking program piece will produce a watermark string which is detectable in the execution state of an executing computer by a computerized recognizer on the executing computer, and such that the watermarking program piece will produce at least one other string in the execution state of the executing computer when executed with at least one other input;
• and
• (d) obfuscating code constructed to obfuscate the watermarking program piece stored on the watermarking computer using at least one opaque predicate, and introduce the obfuscated watermarked program piece into the software.

A computer implemented method of watermarking a software object, wherein a watermarking computer performs the following functions comprising:

• a) determining at least one input sequence;
• b) determining at least one property of an execution trace comprising one or more of:
• i) the sequence of addresses from which executed instructions are fetched from the memory of the executing computer executing the software object on the input sequence;
• ii) the sequence of instructions in the software object that are executed by the executing computer executing the watermarked software object on the input sequence.
• c) making multiple measurements of the at least one execution-trace property for the watermarked software object by measuring the at least one execution-trace property of the software object when it is executed with the at least one input sequence on at least one executing computer;
• d) creating a watermark signature property for the software object by computing the likely range of measured values for the at least one execution-trace property when the software object is executed with the at least one input sequence on a typical executing computer.

A computer implemented method for watermarking a software object, wherein a watermarking computer performs the following functions comprising:

• a) selecting a watermark
• b) embedding the watermark in a string;
• c) determining an input sequence;
• d) creating a watermarked software object by modifying the software object so that the watermark becomes present and detectable in an execution state of the software object within a memory of an executing computer executing the watermarked software object with the input sequence, the execution state of the watermarked software object in the executing computer comprising all current values in all stacks, heaps, global variables, data registers, and program counters in the memory of the executing computer which have been modified by the executing computer while executing instructions from the watermarked software object with the input sequence, such that some values in said execution state correspond to characters in said watermark string;
• e) modifying the software object so that the watermark will not become present or detectable in an execution state of the watermarked software object whenever the watermarked software object is run with an input different to the input sequence;
• and
• f) further modifying the software object by introducing at least one opaque predicate to obfuscate at least one of the branches in said software object, so that the target of said branch cannot be computed by a static analysis of said software object, thereby producing a watermarked software object whose watermark string is opaque to static analysis.