Integrity ordainment and ascertainment of computer-executable instructions

TECHNICAL FIELD

[0001] This invention generally relates to a technology for facilitating the protection computer-executable instructions, such as software.

BACKGROUND

[0002] Digital goods (e.g., software products, data, content, etc.) are often distributed to consumers via fixed computer readable media, such as a compact disc (CD-ROM), digital versatile disc (DVD), soft magnetic diskette, or hard magnetic disk (e.g., a preloaded hard drive). More recently, more and more content is being delivered in digital form online over private and public networks, such as Intranets and the Internet. Online delivery improves timeliness and convenience for the user, as well as reduces delivery costs for a publisher or developers. Unfortunately, these worthwhile attributes are often outweighed in the minds of the publishers/developers by a corresponding disadvantage that online information delivery makes it relatively easy to obtain pristine digital content and to pirate the content at the expense and harm of the publisher/developer.

[0003] One concern of the publisher/developer is the ability to check digital content, after distribution, for alteration. Such checking is often referred to as SRI (Software Resistance to Interference). The reasoning for the desire to check for such alterations can vary (e.g., to ensure that the content continues to operate as intended by the publisher/developer, to protect against improper copying, etc.).

[0004] The unusual property of content is that the publisher/developer (or reseller) gives or sells the content to a client, but continues to restrict rights to use the content even after the content is under the sole physical control of the client. For instance, a software developer typically sells a limited license in a software product that permits a user to load and run the software product on one or more machines (depending upon the license terms), as well as make a back up copy. The user is typically not permitted to make unlimited copies or redistribute the software to others.

[0005] These scenarios reveal a peculiar arrangement. The user that possesses the digital bits often does not have full rights to their use; instead, the provider retains at least some of the rights. In a very real sense, the legitimate user of a computer can be an adversary of the data or content provider.

[0006] DRM Techniques

[0007] One of the uses for SRI (Software Resistance to Interference) is to provide “digital rights management” (or “DRM”) tamper-resistance (i.e., protection) to prevent unauthorized modification, distribution, copying, and/or illegal operation of, or access to the digital goods. An ideal digital goods distribution system would substantially prevent unauthorized modification/distribution/use of the digital goods.

[0008] Digital rights management is fast becoming a central requirement if online commerce is to continue its rapid growth. Content providers and the computer industry must quickly address technologies and protocols for ensuring that digital goods are properly handled in accordance with the rights granted by the developer/publisher. If measures are not taken, traditional content providers may be put out of business by widespread theft or, more likely, will refuse altogether to deliver content online.

[0009] Various DRM techniques have been developed and employed in an attempt to thwart potential pirates from illegally copying or otherwise distributing the digital goods to others.

[0010] Original Media Required

[0011] For example, one conventional DRM technique includes requiring the consumer to insert the original CD-ROM or DVD for ascertainment prior to enabling the operation of a related copy of the digital good. Unfortunately, this DRM technique typically places an unwelcome burden on the honest consumer, especially those concerned with speed and productivity. Moreover, such techniques are impracticable for digital goods that are site licensed, such as software products that are licensed for use by several computers, and/or for digital goods that are downloaded directly to a computer. Additionally, it is not overly difficult for unscrupulous individuals/organizations to produce working pirated copies of the CD-ROM.

[0012] Registration

[0013] Another conventional DRM technique includes requiring or otherwise encouraging the consumer to register the digital good with the provider. For example, this is often done either through the mail or online via the Internet or a direct connection. Thus, the digital good may require the consumer to enter a registration code before allowing the digital good to be fully operational or the digital content to be fully accessed. Unfortunately, such DRM techniques are not typically effective since unscrupulous individuals/organizations need only undermine the DRM protections in a single copy of the digital good. Once broken, copies of the digital good can be illegally distributed; hence, such DRM techniques are considered to be Break-Once, Run-Everywhere (BORE) susceptible. Various techniques may be used to overcome some of the BORE susceptible, such as per-user software individualization, watermarks, etc. However, a malicious user may still be able to identify and remove from the digital good these various protections.

[0014] Code Obfuscation

[0015] Still another DRM technique is an emerging one called “code obfuscation” or “code scrambling.” Code obfuscation is described, to some degree, in the following co-pending patent applications (all of which are assigned to the Microsoft Corporation):

[0016] U.S. patent application Ser. No. 09/670,916, entitled “Code Integrity Verification that Includes One or More Cycles” filed on Sep. 29, 2000;

[0017] U.S. patent application Ser. No. 09/536,033, entitled “System and Method for Protecting Digital Goods using Random and Automatic Code Obfuscation” filed on Mar. 27, 2000;

[0018] U.S. patent application Ser. No. 09/651,424, entitled “Method and System for Using a Portion of a Digital Good as a Substitution Box” filed on Aug. 30, 2000; and

[0019] U.S. patent application Ser. No. 09/651,901, entitled “Protecting Digital Goods using Oblivious Checking” filed on Aug. 30, 2000.

[0020] Code obfuscation thwarts would-be software pirate's attempt to attack the licensing provisions in digital goods (such as software). It also thwarts malicious would-be interlopers when they attempt to modify the security portions of such digital goods. In either case, existing code obfuscation techniques complicate an attacker's attempt to locate and identify specific portions of code within a software program (such as the operating system or an application).

[0021] Code obfuscation techniques effectively “hide” (i.e., obfuscate) or “scramble” the underlying code of a digital good, thereby making it difficult for a would-be attacker to locate and identify portions of the code.

[0022] Although it may be difficult, an attacker may be able to overcome code obfuscation. For example, an attacker can track the execution instance of the software program to identify where and when specific actions are performed. Once an attacker identifies and locates specific portions of code, she may modify it. Conventional code obfuscation cannot prevent code modification. Conventional code obfuscation cannot detect when code has been modified.

[0023] Code Modification

[0024] As stated above, the publisher/developer would like the ability to check digital content, after distribution, for alteration. The reasons for checking for such alterations may vary (e.g., to ensure that the content continues to operate as intended by the publisher/developer, to protect against improper copying, etc.). However, conventional DRM techniques do not actually check for alteration of digital content, such as software code.

[0025] Strictly speaking, conventional DRM techniques are chiefly designed to complicate code analysis by the digital pirate. They erect barriers and obstacles to unauthorized use of the software and/or unauthorized access the underlying code. However, they cannot detect code modification (i.e., alternation).

[0026] Accordingly, there is a challenge for a DRM technique to increase tamper resistance by detecting code modification without imposing unnecessary and burdensome requirements on legitimate users.

[0027] Remote Code Ascertainment

[0028] “Remote code ascertainment” is another realm that lacks the capability to effectively detect code modifications. A generic example of “remote code ascertainment” is the following: a computing entity (e.g., server) can ensure that only authorized (e.g., unaltered) computing entities (e.g., a client software program) connect via a remote coupling and that such remote entities remain free from tampering. This is also called: “persistent remote authentication.”

[0029] Some systems, such as those employing Internet instant-messaging systems, include a small, simple client program that connects to a secure server over a network. Deployers of such systems may require that only authorized, unmodified client software use the servers.

[0030] How does the server in such a system ascertain that the client software with which it is communicating is unmodified, unaltered, unadulterated, untainted, etc. by the devious hands of malicious would-be infiltrator? The issue here is not whether the proper security protocol is followed and the proper security information is provided. Rather the issue is whether the server can be certain that the security features of the client software have not be hijacked by a malicious would-be infiltrator.

[0031] Generally speaking, for an experienced software expert, it is not particularly difficult to reverse engineer the client-server communications. Therefore, an attacker can create a fully functional but unauthorized client program. Moreover, an attacker can patch the original code or data of authorized client software to instruct it to perform unauthorized and undesirable actions.

[0032] Traditional authentication protocols do not address the problem described. Unauthorized parties can reverse engineer such protocols and write new software to implement them. An attacker can modify a client program's code or data without changing its implementation of an authentication protocol. Traditional protocols do not address code tampering.

[0033] Accordingly, there is a challenge for a technique to confirm the veracity of a remote software program. Conventionally, it is a challenge to effectively thwart maliciously modified programs from harming a network system by preventing their initial passage through the security layers by masquerading as the original and unaltered program.

[0034] The Challenge of Accurately Detecting Code Modification

[0035] Accordingly, it is a challenge for a technique to address the concerns of the publisher/developer in protecting their rights in a digital good, such as software. Specifically, it is a challenge for to detect an alteration of the digital content without imposing unnecessary and burdensome requirements on legitimate users.

[0036] Furthermore, it is a challenge for to test the veracity of a remote software program. Specifically, it is a challenge for to detect a modified program so that it cannot impersonate the original and unaltered program.

SUMMARY

[0037] Described herein is a technology for facilitating the protection computer-executable instructions, such as software.

[0038] At least one implementation, described herein, may generate integrity signatures of multiple sets of computer-executable instructions based upon the output trace and/or an execution trace of such sets. With at least one implementation, described herein, a determination may be made about whether two or more of such sets are unaltered duplicates by comparing integrity signatures of such sets.

[0039] With at least one implementation, described herein, a plurality of input parameters to provide to a set of computer-executable instructions (e.g., a program module) of a digital good. The execution instance of the set of instructions generates an output for a specified input parameter. These outputs are stored in output trace. This implementation generates an integrity signature based upon the output trace. This technique may be generally called “integrity ordainment,” herein.

[0040] With at least one implementation, described herein, hidden instructions are inserted within the set of computer-executable instructions of the digital good to produce a protected form of such. When the set of instructions are executed, these hidden instructions generate an execution trace of various morsels of data. This implementation generates an integrity signature based upon the execution trace of the set of instructions when the set is given one or more specified parameters. This technique may be generally called “integrity ordainment,” herein.

[0041] Another implementation, described herein, combines the features and functions of the “execution-trace” implementation and the “output-trace” implementation.

[0042] Still another implementation, described herein, verifies the integrity of a digital good. It does so by determining whether one or more computer-executable instructions of the digital goods have been altered. This detection technique is called “integrity ascertainment,” herein.

[0043] At least one implementation, described herein, generates an integrity signature for a set of instructions of a subject digital good (i.e., the one being tested for integrity). With at least one implantation, described here, the same specified parameters (or associated parameters) are used to generate both the original signature during integrity ordainment and during integrity ascertainment.

[0044] With at least one implantation, described here, the signature may be an execution-signature that is based upon an execution trace of the set of instructions of a subject digital good. With at least another implantation, described here, the signature may be an output-signature that is based upon an output trace of the set of instructions of a subject digital good. With at least another implantation, described here, the signature may be either, both, or some combination of the execution-signature and/or the output-signature.

[0045] With at least one implantation, described here, the original signature(s) generated during integrity ordainment is/are compared to the signature(s) generated during integrity ascertainment. If they are indistinguishable, then the digital good is unmodified. Otherwise, the digital good has been modified from its original state.

[0046] This summary itself is not intended to limit the scope of this patent. Moreover, the title of this patent is not intended to limit the scope of this patent. For a better understanding of the present invention, please see the following detailed description and appending claims, taken in conjunction with the accompanying drawings. The scope of the present invention is pointed out in the appending claims.

BRIEF DESCRIPTION OF THE DRAWINGS

P-0047[0047] The same numbers are used throughout the drawings to reference like elements and features.

P-0048[0048] FIGS. <b>1</b>A-<b>1</b>F are block diagrams illustrating the logical components manipulated by an implementation described herein and their relationships and associations with each other within the context of the implementation.

P-0049[0049]FIG. 2A is a block diagram graphically illustrating actions performed by an embodiment described herein.

P-0050[0050]FIG. 2B is a block diagram graphically illustrating actions performed by an embodiment described herein.

P-0051[0051]FIG. 3 illustrates an example of a digital rights management (DRM) distribution architecture in accordance with an implementation described herein. In particular, this illustrates an implementation of the integrity ordainment aspect described herein.

P-0052[0052]FIG. 4 illustrates an example of a digital rights management (DRM) distribution architecture in accordance with an implementation described herein. In particular, this illustrates an implementation of the integrity ascertainment aspect described herein.

P-0053[0053]FIG. 5 is a flow diagram showing a methodological implementation described herein.

P-0054[0054]FIG. 6 is a flow diagram showing a methodological implementation described herein.

P-0055[0055]FIG. 7 is a flow diagram showing a methodological implementation described herein.

P-0056[0056]FIG. 8 is a flow diagram showing a methodological implementation described herein.

P-0057[0057]FIG. 9 is an example of a computing operating environment capable of implementing an embodiment (wholly or partially) described herein.

DETAILED DESCRIPTION

P-0058[0058] The following description sets forth one or more specific embodiments of integrity ordainment and ascertainment of computer-executable instructions that incorporate elements recited in the appended claims. These embodiments are described with specificity in order to meet statutory written description, enablement, and best-mode requirements. However, the description itself is not intended to limit the scope of this patent.

P-0059[0059] The one or more specific embodiments, described herein, are exemplary implementations of an integrity ordainment and ascertainment of computer-executable instructions. The inventors intend these exemplary implementations to be examples. The inventors do not intend these exemplary implementations to limit the scope of the claimed present invention. Rather, the inventors have contemplated that the claimed present invention might also be embodied and implemented in other ways, in conjunction with other present or future technologies.

P-0060[0060] An example of an embodiment of an integrity ordainment and ascertainment of computer-executable instructions may be referred to as an “exemplary integrity ordainer/ascertainer.” Alternatively, it may be called an “exemplary integrity veracitor.” The exemplary integrity veracitor may include an exemplary integrity ordainer and/or an exemplary integrity ascertainer.

P-0061[0061] Brief Glossary

P-0062[0062] To aid the reader, the following brief glossary is provided as a quick reference to the definitions of terms that are otherwise not common in the art. This glossary primarily covers terms related to the color-coding of computer-executable instructions (i.e., code). This color-coding is purely for explanatory purposes only. Of course, such code has no actual color, but if it did, the actual color plays no functional role. Integrity Veracitication—this includes integrity ordainment and integrity ascertainment. “Veracitication” is noun form of a verb form of the word “veracity,” which generally means “adherence to the truth; truthfulness; conformity to fact or truth; something that is true.”

P-0063[0063] Integrity Ordainment—this may be thought of as the front-end of integrity veracitication. “Ordainment” is noun form of the word “ordain,” which generally means, “to prearrange unalterably.” Implementations of integrity ordainment techniques may employ execution tracing and hashing, output tracing and hashing, or a combination of both.

P-0064[0064] Integrity Ascertainment—this may be thought of as the back-end of integrity veracitication. “Ascertainment” is noun form of the word “ascertain,” which generally means, “to discover with certainty, as through examination or experimentation.” This may also be called “integrity verification.”

P-0065[0065] Clear code <b>111</b>—unprotected original computer-executable instructions of a digital good. Alternatively, this may refer to same instructions after it is obfuscated using code obfuscation techniques, but for the purpose of this discussion, it will be assumed that the original instructions are “unprotected” in terms of integrity veracitication.

P-0066[0066] Black code <b>120</b>—hidden, special-purpose instructions that are strategically, distributively inserted within the clear code. With the exemplary integrity veracitor, this code generates an execution trace of various morsels of data. Use of black code is not necessary for output tracing and hashing.

P-0067[0067] Green code <b>130</b>—the combination of clear and black code. This code is known and/or determined to be unmodified. This code is the result of integrity ordainment. The green code <b>130</b> is derived from the clear code <b>110</b>, but it is modified to detect alterations that a pirate might do. When output tracing and hashing are employed (without execution tracing and hashing), clear code and green code are the same because black code is unnecessary.

P-0068[0068] Red code <b>150</b>—modified code; green code after it has been modified by a pirate; code that is determined and/known to be modified.

P-0069[0069] Yellow code <b>160</b>—code that is suspected of having been modified (i.e., it is subject of detection tests); code that is the subject of integrity ascertainment tests.

P-0070[0070] Parameters <b>140</b>—herein, this refers to one or more specific parameters that are passed to a program module (i.e., function, set of instructions, etc.) that are used to generate one or more signatures. Typically, these parameter(s) have specified value(s) that generate a signature that remains the same for each execution instance of the module as long as the module remains unmodified.

P-0071[0071] Green signature <b>132</b>—a signature is a specific value that identifies the execution instance of a program module (in this case, of green code) based upon one or more specified parameters. A green signature is one generated during integrity ordainment and it is the basis for determining if the code of a module has been modified.

P-0072[0072] Yellow signature <b>162</b>—a signature is a specific value that identifies the execution instance of a program module (in this case, of yellow code). A yellow signature is one generated during integrity ascertainment and it is compared to the green signature to determine if the code of a module has been modified.

P-0073[0073] Integrity Veracitication

P-0074[0074] The one or more exemplary implementations, described herein, of the present claimed invention may be implemented (in whole or in part) by an integrity veracitication system. The integrity veracitication system may be part of a digital rights management (DRM) distribution architecture <b>300</b>; an integrity ascertainment architecture <b>400</b>; and/or a computing environment like that shown in FIG. 9. It may be implemented by an integrity ordainer <b>370</b>; an integrity ascertainment system <b>402</b>; and/or a computing environment like that shown in FIG. 9.

P-0075[0075] At least one implementation, described herein, may generate integrity signatures of multiple sets of computer-executable instructions based upon the output trace and/or an execution trace of such sets. With at least one implementation, described herein, a determination may be made about whether two or more of such sets are unaltered duplicates by comparing integrity signatures of such sets.

P-0076[0076] There are at least two forms “integrity veracitication” techniques: One employs execution tracing and another employs output tracing. These two forms may be employed together or separately of the other.

P-0077[0077] Integrity Ordainment

P-0078[0078] There are two forms of a technique generally called “integrity ordainment:” One for execution tracing and one for output tracing. These two forms of technique may be employed together or separately of the other.

P-0079[0079] With at least one implementation of the output-tracing form of the integrity ordainment technique, a plurality of input parameters to provide to a set of computer-executable instructions (e.g., a program module) of a digital good. The execution instance of the set of instructions generates an output for a specified input parameter. These outputs are stored in output trace. This implementation generates an integrity signature based upon the output trace. This integrity signature may also be called an “output-identifying” signature. However, more generally, this integrity signature may also be called an “execution-identifying” signature since it represents (and thus identifies) multiple execution instances of a program module.

P-0080[0080] With at least one implementation of the execution-tracing form of the integrity ordainment technique, hidden instructions are inserted within the set of computer-executable instructions of the digital good to produce a protected form of such. When the set of instructions are executed, these hidden instructions generate an execution trace of various morsels of data. This implementation generates an integrity signature based upon the execution trace of the set of instructions when the set is given one or more specified parameters. This integrity signature may also be called an “execution-identifying” signature.

P-0081[0081] Other implementations may combine the features and functions of the “execution-trace” implementation and the “output-trace” implementation.

P-0082[0082] Although code obfuscation may be used to limit code accessibility and to make code modification more difficult to accomplish, the tamper-resistance (i.e., protection) afforded by this implementation enables detection of alterations to the executable instructions of a digital good. Consequently, an alternative implementation may combine code obfuscation with the integrity ordainment techniques.

P-0083[0083] Clear, Black, and Green Code

P-0084[0084]FIG. 1A illustrates an implementation of the execution-trace form of the integrity ordainment technique. Such technique strategically, distributively inserts hidden, special-purpose instructions within the existing executable instructions. These hidden instructions are called “black code,” which are shown as a set of shaded blocks <b>120</b> labeled “black”. The otherwise unprotected original instructions are called “clear code,” which are shown as a block <b>110</b> labeled “clear.” The combination is called “green code” to be metaphorically consistent. It is shown as a block <b>130</b> labeled “green.” Alternatively, it is generally called “modification-detectable code.”

P-0085[0085] As FIG. 1A summarizes, the combination of clear code <b>110</b> and black code <b>120</b> results in green code <b>130</b>. In other words, the combination of unprotected code <b>110</b> and code implementing integrity ordainment <b>120</b> results in modification-detectable code <b>130</b>.

P-0086[0086] This tamper-resistance (i.e., protection) technique, which facilitates later code-modification detection, may include code obfuscation to shield the code from malicious attacks. In alternative implementations, the clear code and/or the green code may be subject to further code obfuscation techniques. For the purposes of clarity, the tamper-resistance (i.e., protection) afforded by such code obfuscation will be largely ignored herein. That is because the focus is on providing a way to detect and to actually detect code alterations regardless of the barriers erected to prevent such alterations.

P-0087[0087] If an implementation employs only the output-tracing form of the integrity ordainment technique, then the clear code <b>110</b> and green code <b>130</b> are the same. That is because black code <b>120</b> is not employed to implement the output-tracing form alone.

P-0088[0088] Green Signature

P-0089[0089]FIG. 1B shows that, during the integrity ordainment, the green code <b>130</b> is provided one or more given (i.e., known, determined, specified, etc.) parameters <b>140</b>. Presumably, the green code <b>130</b> is one or more program modules that typically accept input in the form of parameters, such as parameters <b>140</b>.

P-0090[0090] Typically, the actual value(s) of parameter(s) <b>140</b> are selected with the intent of a signature that is likely to change if there is a slight modification in the code

P-0091[0091] With at least one implementation employing the execution-trace form, as the green code <b>130</b> executes, the black code (which is now within it) generates a trace of various status conditions. Thus, it generates an execution trace.

P-0092[0092] Given the parameters on which the green code executes, the resulting execution trace (or further computation of such trace) is effectively a “signature” of the execution instance of that green code. Generally, this may be called a green signature <b>132</b>. More specifically, it may be called the green execution-signature. If the green code is modified, the resulting signature of such a modified code differs from the green signature <b>132</b> (i.e., original signature) of the green code <b>130</b>.

P-0093[0093] With at least one implementation employing the execution-trace form, as the green code <b>130</b> is repeatedly executed, each time with specified input parameters. Each execution instance generates an output that is stored as an output trace.

P-0094[0094] Given the parameters on which the green code repeatedly executes, the resulting output trace (or further computation of such trace) is effectively a “signature” of the output of the execution instances of that green code. Generally, this may be called a green signature <b>132</b>. More specifically, it may be called the green output-signature. If the green code is modified, the resulting signature of such a modified code differs from the green signature <b>132</b> (i.e., original signature) of the green code <b>130</b>.

P-0095[0095] Red Code

P-0096[0096] To continue the metaphor further, code that has actually been modified (i.e., modification has been detected) is called “red code.”

P-0097[0097]FIG. 1C shows that a malicious attack <b>152</b> by a digital pirate on green code <b>130</b> generates red code <b>150</b>. The computer-executable instructions of the red code are compromised. The pirate has modified the green code (unmodified code) and produced the red code (modified code).

P-0098[0098] Yellow Code

P-0099[0099] To continue the metaphor further, code that is suspected of having been modified (i.e., it is subject of detection tests) is called “yellow code.” It is not known whether such code is green or red.

P-0100[0100] Integrity Ascertainment

P-0101[0101] Another implementation verifies the integrity of a digital good. It does so by determining whether one or more computer-executable instructions of the digital good have been altered. This detection technique is called “integrity ascertainment,” herein.

P-0102[0102] Like above, there are two forms of a technique generally called “integrity ascertainment:” One for execution tracing and one for output tracing. These two forms of technique may be employed together or separately of the other.

P-0103[0103] Yellow Signature

P-0104[0104]FIG. 1D shows that this implementation generates a yellow signature <b>162</b> (or “verification” signature) for yellow code <b>160</b> (i.e., the code being tested for integrity). This yellow signature is based upon an execution trace of the computer instructions of the yellow code <b>160</b>. With at least one implantation, the same specified parameters <b>140</b> are used to generate both the original signature <b>132</b> (i.e., the green signature) during integrity ordainment (see FIG. 1B) and the verification signature <b>162</b> (i.e., the yellow signature) during integrity ascertainment (see FIG. 1D).

P-0105[0105] With at least one implantation, the signature may be an execution-signature that is based upon an execution trace of the execution instance of a set of instructions of a subject digital good. With at least another implantation, the signature may be an output-signature that is based upon an output trace of the execution instance of a set of instructions of a subject digital good. With at least another implantation, the signature may be either, both, or some combination of the execution-signature and/or the output-signature.

P-0106[0106] Comparison of Yellow and Green Signatures

P-0107[0107] With at least one implantation, the original signature(s) (i.e., the green signature <b>132</b>) generated during integrity ordainment is/are compared to the signature(s) (i.e., the yellow signature <b>162</b>) generated during integrity ascertainment.

P-0108[0108] If they are substantially indistinguishable (e.g., they match exactly), then the digital good is unmodified. Otherwise, the digital good has been modified from its original state. When the parameters are employed for integrity ordainment and integrity ascertainment are the same, “indistinguishable” here means the same or substantially so. Also, “indistinguishable” here takes into account any relationship between parameters if differing parameters are employed for integrity ordainment and integrity ascertainment.

P-0109[0109] As shown in FIGS. 1E and 1F, the yellow and green signatures are compared. FIG. 1E shows that if the yellow and green signatures are indistinguishable, then the yellow code <b>160</b> is the unmodified green code <b>130</b>. FIG. 1F shows that if they are distinguishable, then the yellow code <b>160</b> has been modified from the original green code. Thus, it is red code <b>150</b>.

P-0110[0110] Execution and/or Output Tracing

P-0111[0111] The exemplary integrity veracitor may employ execution tracing and hashing, output tracing and hashing, or a combination of both. Generally, with execution tracing and hashing, the execution instance of a program module is traced and the result of such is hashed to generate an execution-trace signature. Generally, with output tracing and hashing, the output of a program module is traced and the result of such is hashed to generate an output-trace signature.

P-0112[0112] Execution Tracing and Hashing

P-0113[0113] With at least one implementation, the yellow and green signatures being compared are based upon an execution trace (i.e., computation trace) of one or more program modules of the digital good. The program modules include computer-executable instructions. By their nature, these instructions execute.

P-0114[0114] A typical program module receives input and that input is often labeled parameters. While a program module executes, various morsels of stored data are changed. The program module probably will change registers in the processor and data stored in memory locations. Typically, a module returns some data at the conclusion of its execution instance.

P-0115[0115] Tracking the changes in various morsels of data while a program module executes is called an execution trace, or alternatively a computation trace.

P-0116[0116]FIG. 2A illustrates the execution tracing of the exemplary integrity veracitor. A program module <b>210</b> of code includes a series of computer-executable instructions (which as shown as rectangles and diamonds). If the green signature <b>132</b> is being generated (during integrity ordainment), then the program module <b>210</b> is part of green code <b>130</b>. If the yellow signature <b>152</b> is being generated (during integrity ascertainment), then the program module <b>210</b> is part of yellow code <b>150</b>.

P-0117[0117] For the purpose of clarity in the discussion that follows, assume that the program module <b>210</b> of FIG. 2A is part of the green code and a green signature <b>132</b> is being generated. This assumption is only for the purpose of discussion only.

P-0118[0118]FIG. 2A shows the program module <b>210</b> receiving one or more parameters <b>140</b>. The program modules include the original instructions, which are unlabeled and represented as rectangles and diamonds. These instructions may be thought of as the clear code before integrity ordainment. The program module also includes several blocks of hidden code (e.g., <b>212</b><i>a</i>-<i>d</i>). These are the black code. They are strategically dispersed throughout the program module.

P-0119[0119] The black code insertion may occur at most any level of language. Examples of such levels include (but are not limited to):

P-0120[0120] source code

P-0121[0121] AST—abstraction syntax

P-0122[0122] IL—intermediate language

P-0123[0123] machine language (executable)

P-0124[0124] With this implementation, the purpose of each block of the black code is to record the present status of various morsels of data at the time that the black code is executed. Consequently, the black code records a history of the execution instance of that program module for given input parameters <b>140</b>.

P-0125[0125]FIG. 2A shows an execution-trace memory <b>220</b>, which simply is a block of memory where the black code stores the execution trace as it generates it and uses it.

P-0126[0126] It illustrates a simple data structure table with rows and columns. The rows (<b>1</b>-X) represent a set of data morsels stored by a specific block of black code—perhaps, more precisely, by a specific execution instance of a block of black code. It is likely that blocks of black code will be executed more than once. In FIG. 2, that association is illustrated by the dashed-dotted arrow between a row and a block of black code.

P-0127[0127] The columns represent each selected morsel of data that is being traced. For example, columns R₁-R_Nrepresent registers <b>1</b>-N and M₁-M_Yrepresent memory locations <b>1</b>-Y.

P-0128[0128] Specific data is shown in the table of the execution-trace memory <b>220</b>, but this data is for illustration purposes only and has no other significance.

P-0129[0129] The exemplary integrity veracitor hashes the completed execution trace memory <b>220</b> to produce a hash value <b>230</b>. That value may be generically called an execution-trace signature.

P-0130[0130] This hashing of the execution trace may be called “computational,” or “execution,” hashing. It is an example of “oblivious” hashing.

P-0131[0131] Execution hashing is a technique to detect modifications in the code by examining the computations of that code, rather than the code itself. To put it another way, it is a technique to verify code integrity of the code as it executes. Thus, to perform the test, the code being tested must execute. However, the code is not tested directly; rather, an historical record of the computations performed during execution instance is tested.

P-0132[0132] To be more precise, this historical computation record is hashed to get a hash value. That hash value is compared to the expected hash value when a given set of parameters is passed to the code being tested.

P-0133[0133] Execution hashing computes hashes or checksums of intermediate program states, thus preventing easy changing of program behavior. This procedure essentially verifies code without reading code bytes, and serves to identify a particular program module. Hashes depend on the states of a program at particular times, and such states are extremely unlikely to be equivalent for distinct programs, even if the programs perform similar actions.

P-0134[0134] Output Tracing and Hashing

P-0135[0135] With at least one implementation, a plurality of input parameters to provide to a set of computer-executable instructions (e.g., a program module) of a digital good. The execution instance of the set of instructions generates an output for a specified input parameter. The outputs from multiple execution instances of the program module—with each using specified parameters—are stored in output trace. Presumably, at least some of the specified parameters from different execution instances differ from each other.

P-0136[0136] This implementation generates an integrity signature based upon the output trace. This integrity signature may also be called an “output-identifying” signature. However, more generally, this integrity signature may also be called an “execution-identifying” signature since it represents (and thus identifies) multiple execution instances of a program module.

P-0137[0137] A typical program module receives input and that input is often labeled parameters. A typical program module generates one or more outputs while it executes or upon the completion of execution instance. Typically, the output varies depending upon the input parameters.

P-0138[0138] Tracking the output from multiple execution instances of a program module, where each execution instance has a set of input parameters, generates an output trace, or alternatively, a write trace.

P-0139[0139]FIG. 2B illustrates the output tracing of the exemplary integrity veracitor. Program modules <b>250</b><i>a</i>, <b>250</b><i>b</i>, <b>250</b><i>c</i>, and <b>250</b><i>x </i>represent multiple execution instances of the same series of computer-executable instructions (which as shown as rectangles and diamonds). If the green signature <b>132</b> is being generated (during integrity ordainment), then the program modules <b>250</b><i>a</i>-<i>x </i>are part of green code <b>130</b>. If the yellow signature <b>152</b> is being generated (during integrity ascertainment), then the program modules <b>250</b><i>a</i>-<i>x </i>are part of yellow code <b>150</b>.

P-0140[0140] For the purpose of clarity in the discussion that follows, assume that the program modules <b>250</b><i>a</i>-<i>x </i>of FIG. 2B is part of the green code and a green signature <b>132</b> is being generated.

P-0141[0141]FIG. 2B shows an output-trace memory <b>260</b>, which simply is a block of memory where the output(s) of each execution instance is stored. Although the output trace memory may have the original input parameters (e.g., <b>140</b><i>a</i>-<i>x</i>) stored therewith, it may be undesirable to do so. That is because it may allow a digital pirate to reverse engineer the output trace process. However, this may be done if it is determined that the risk of such reverse engineering is tolerable.

P-0142[0142]FIG. 2B shows the execution instance of program module <b>250</b><i>a </i>receiving one or more input parameters <b>140</b><i>a</i>. The result is saved in block <b>1</b> of the output-trace memory <b>260</b>. FIG. 2B shows the execution instance of program module <b>250</b><i>b </i>receiving one or more input parameters <b>140</b><i>b</i>. The result is saved in block <b>2</b> of the output-trace memory <b>260</b>. FIG. 2B shows the execution instance of program module <b>250</b><i>c </i>receiving one or more input parameters <b>140</b><i>c</i>. The result is saved in block <b>3</b> of the output-trace memory <b>260</b>. FIG. 2B shows the execution instance of program module <b>250</b><i>x </i>receiving one or more input parameters <b>140</b><i>x</i>. The result is saved in block X of the output-trace memory <b>260</b>. Other execution instances may occur using other input parameters. Those outputs would be saved in the output-trace memory <b>260</b> also.

P-0143[0143] Presumably, at least one of the input parameters <b>140</b><i>a</i>-<i>x </i>differ from the other. It is desirable for many (to all) to differ from the others.

P-0144[0144] Specific data is shown in the table of the output-trace memory <b>260</b>, but this data is for illustration purposes only and has no other significance.

P-0145[0145] The exemplary integrity veracitor hashes the completed output trace memory <b>260</b> to produce a hash value <b>270</b>. That value may be generically called an output-trace signature.

P-0146[0146] This hashing of the output trace may be called “write,” or “output,” hashing. It is an example of “oblivious” hashing.

P-0147[0147] It is a technique to detect modifications in the code by examining the output of multiple execution instances of that code, rather than the code itself. To put it another way, it is a technique to verify code integrity of the code by validating its output from multiple execution instances. Thus, to perform the test, the code being tested must execute multiple times. However, the code is not tested directly; rather, an historical record of the outputs generated during/from the execution instances is tested.

P-0148[0148] To be more precise, this historical output record is hashed to get a hash value. That hash value is compared to the expected hash value when a specified set of parameters is passed to the code being tested over multiple execution instances.

P-0149[0149] This procedure essentially verifies code without reading code bytes, and serves to identify a particular program module. Hashes depend on the outputs of a program given specified inputs, and such outputs are extremely unlikely to be equivalent for distinct programs, even if the programs perform similar actions.

P-0150[0150] Oblivious Hashing

P-0151[0151] Although those skilled in the art are aware that other techniques are available, these implementations hash the execution-trace and/or output-trace records to generate a unique (or nearly) unique identifier for a program module. Such implementations my employ a scheme called “oblivious hashing.”

P-0152[0152] With oblivious hashing scheme, the behavior of a module (i.e., function) is hashed without reading the module's code. The hashing has weak collision resistance in the following sense: given a function f and its hash value H(f)=h, it is hard to make minor modifications to f such that the resulting function f′ has the same hash value H(f′)=h.

P-0153[0153] In general, those of ordinary skill in the art know how to hash a table (such as the one shown at <b>220</b> if FIG. 2A) to generate a hash value.

P-0154[0154] In general, one advantage of hashing is to generate a short and manageable identifier that represents the trace. The hash value is one that heavily influenced by any differences from one trace to another. Those of ordinary skill in the art know that other types of encoding may be employed.

P-0155[0155] Note that both the yellow and green signatures may be generated in this manner.

P-0156[0156] If the yellow code is unmodified, then the black code (e.g., <b>212</b><i>a</i>-<i>d</i>) will generate the same execution trace during integrity ordainment and ascertainment. Consequently, the same execution traces produce the same execution-trace signatures <b>230</b>.

P-0157[0157] If the yellow code is unmodified, then the outputs of multiple execution instances will generate the same output trace during integrity ordainment and ascertainment. Consequently, the same output traces produce the same output-trace signatures <b>230</b>.

P-0158[0158] The signatures that are compared to verify the integrity of the subject code are based upon traces. The green signature <b>132</b> is based upon a trace of the green code <b>132</b> (see FIG. 1B). The yellow signature <b>152</b> is based upon a trace of the yellow code <b>152</b> (see FIG. 1D).

P-0159[0159] Input-Parameter Deterministic

P-0160[0160] The exemplary integrity veracitor is particularly applicable to program modules (i.e., functions) that are deterministic with respect to input parameters and that are relatively free of side effects. This does not, however, imply purely-functional functions as in a functional language. For example, one may pass pointers to objects to a program module, as long as the objects are allocated dynamically. This allows for fabrication of a set of parameters a priori and call the target program module with an expected hash value and without worry of side effects. These program modules may be called input-parameter deterministic program modules.

P-0161[0161] If a program module is input-parameter deterministic, it is logical to conclude that the execution traces (upon which the signatures are based) of the original set of instructions would differ from a trace of a modified set of instructions. Conversely, it is logical to conclude that the execution traces of the original set of instructions would be identical to a trace of an unmodified (i.e., identical) set of instructions.

P-0162[0162] If a program module is input-parameter deterministic, it is logical to conclude that the output traces (upon which the signatures are based) of multiple execution instances of the original set of instructions would differ from a trace of a modified set of instructions. Conversely, it is logical to conclude that the output traces of multiple execution instances of the original set of instructions would be identical to a trace of an unmodified (i.e., identical) set of instructions.

P-0163[0163] Given the same set of parameters, with the exemplary integrity veracitor, distinct signatures represent the execution instance of program modules with distinct sets of computer-executable instructions. In other words, given the same set of parameters, program modules that have a different (i.e., distinct) set of computer-executable instructions have different (i.e., distinct) signatures.

P-0164[0164] DRM Distribution Architecture

P-0165[0165] A digital rights management (DRM) distribution architecture produces and distributes digital goods in a fashion that renders the digital goods resistant to many known forms of attacks or makes such attacks detectable.

P-0166[0166] Digital Goods

P-0167[0167] Essentially any type of digital good may be protected using this architecture, including such digital goods as software, audio, video, and other content. For discussion purposes, many of the examples are described in the context of software goods and in particular goods that include computer-executable instructions. However, the techniques described herein may be effective for other digital goods (such as audio data, video data, and other forms of multimedia data) if they include some form of computer-executable instructions.

P-0168[0168] Architecture

P-0169[0169]FIG. 3 shows a DRM distribution architecture <b>300</b> in which unprotected (i.e., modification-undetectable) digital goods are transformed into protected (i.e., modification-detectable) digital goods and distributed in their protected form. This involves the employment of integrity ordainment using execution-trace and/or output-trace forms.

P-0170[0170] The architecture <b>300</b> has a developer/producer/provider system <b>302</b> that develops or otherwise produces the protected good and distributes the protected good to a client <b>304</b> via some form of distribution channel <b>306</b>. The protected digital goods may be distributed in many different ways. For instance, the protected digital goods may be stored on a computer-readable medium <b>308</b> (e.g., CD-ROM, DVD, floppy disk, etc.) and physically distributed in some manner, such as conventional vendor channels or mail. Alternatively, the protected goods may be downloaded over a network (e.g., the Internet) as streaming content or files <b>310</b>.

P-0171[0171] The developer/producer system <b>302</b> has a memory (e.g., memory <b>320</b> and <b>360</b>) to store an original digital good <b>110</b> (i.e., clear code), as well as the protected digital good <b>130</b> (i.e., green code) created from the original digital good. The memory also stores the black code <b>120</b>, the parameters <b>140</b>, and the green signature <b>132</b>.

P-0172[0172] The system <b>302</b> also has a production server <b>330</b> that transforms the clear code <b>110</b> into the green code <b>130</b> that is suitable for distribution. The production server <b>330</b> has a processing system <b>332</b> and implements an integrity ordainer <b>370</b>.

P-0173[0173] The integrity ordainer <b>370</b> is the exemplary integrity ordainer of the exemplary integrity veracitor, described herein.

P-0174[0174] Alternatively, the processing system <b>332</b> may include an obfuscator <b>334</b>. The obfuscator <b>334</b> obfuscates the digital good. While obfuscation makes it extremely difficult for pirates to modify the original digital goods, it does not prevent it. A pirate can fool a conventional obfuscator and modify the digital good without detection.

P-0175[0175] The developer/producer system <b>302</b> is illustrated as a single entity, with memory and processing capabilities, for ease of discussion. In practice, however, the system <b>302</b> may be configured as one or more computers that jointly or independently perform the tasks of transforming the original digital good into the protected digital good.

P-0176[0176] The client <b>304</b> has a secure processor <b>340</b>, memory <b>342</b> (e.g., RAM, ROM, Flash, hard disk, CD-ROM, etc.), one or more input devices <b>344</b> (e.g., keyboard, joystick, voice recognition, etc.), and one or more output devices <b>346</b> (e.g., monitor, speakers, etc.). The client may be implemented as a general-purpose computing unit (e.g., desktop PC, laptop, etc.) or as other devices, such as set-top boxes, audio/video appliances, game consoles, and the like.

P-0177[0177] The client <b>304</b> runs an operating system <b>350</b>, which is stored in memory <b>342</b> and executed on the secure processor <b>340</b>. Operating system <b>350</b> represents any of a wide variety of operating systems, such as a multi-tasking, open platform system (e.g., a “Windows”-brand operating system from Microsoft Corporation).

P-0178[0178] Alternatively, the operating system <b>350</b> may include a local integrity ascertainer <b>352</b> that evaluates the digital goods (i.e., yellow code) prior to their utilization to determine whether the goods have been tampered with or modified in any manner. The local integrity ascertainer <b>352</b> is the exemplary integrity ascertainer (in whole or in part) of the exemplary integrity veracitor, described herein. In particular, the local integrity ascertainer <b>352</b> is configured to analyze the various portions according to the tamper-resistance (i.e., protection) scheme of the exemplary integrity veracitor.

P-0179[0179] The local integrity ascertainer <b>352</b> includes code portions that may be executed in these most secure areas of the operating system and secure processor. Although the local ascertainer <b>352</b> is illustrated as being integrated into the operating system <b>350</b>, it may be implemented separately from the operating system.

P-0180[0180] In the event that the client detects some tamper activity, the secure processor <b>340</b> acting alone, or together with the operating system <b>350</b>, may decline to execute the suspect digital code. For instance, the client may determine that the software product has been modified because the evaluations performed by the ascertainer <b>352</b> are not successful. In this case, the local ascertainer <b>352</b> informs the secure processor <b>340</b> and/or the operating system <b>350</b> of the suspect code and the secure processor <b>340</b> may decline to run that software product.

P-0181[0181] It is further noted that the operating system <b>350</b> may itself be the protected digital good. That is, the operating system <b>350</b> may be modified with various tamper-resistance (i.e., protection) schemes to produce a product that is difficult to copy and redistribute, or at least makes it easy to detect such copying. In this case, the secure processor <b>340</b> may be configured to detect an improper version of the operating system during the boot process (or at other times) and prevent the operating system from fully or partially executing and obtaining control of system resources.

P-0182[0182] For the local integrity ascertainer <b>352</b> to ascertain the integrity of yellow code, it should have a secure copy of the green signature and the parameters. Because simply having a copy of the parameters and the green signature in an inherently unsecured environment (of a client) exposes them to attack, it is desirable to have integrity ascertainment performed by or in cooperation with a system in a secure site. The system securely stores the parameters and the green signature. Such a scenario is shown in FIG. 4 and described in its accompanying description below. But, of course, local integrity ascertainment is a desirable solution when it is difficult or not possible to remotely connect to a secure site.

P-0183[0183] For protected digital goods delivered over a network, the client <b>304</b> implements a tamper-resistant software (not shown or implemented as part of the operating system <b>350</b>) to connect to the server <b>302</b> using an SSL (secure sockets layer) or other secure and authenticated connection to purchase, store, and utilize the digital good. The digital good may be encrypted using well-known algorithms (e.g., RSA) and compressed using well-known compression techniques (e.g., ZIP, RLE, AVI, MPEG, ASF, WMA, MP3).

P-0184[0184] Exemplary Integrity Veracitor

P-0185[0185]FIG. 4 shows the integrity ascertainment architecture <b>400</b> in which it is ascertained whether digital goods have been modified from their original protected self. In many ways, it is directly comparable to the DRM architecture <b>300</b> of FIG. 3 except that the focus here is on ascertaining whether a good has been tampered with.

P-0186[0186] The architecture <b>400</b> includes the integrity ascertainment system <b>402</b>. The integrity ascertainment system <b>402</b> has a memory <b>460</b> to store the parameters <b>140</b><i>a </i>and green signatures <b>132</b> for each digital good that it is configured to test.

P-0187[0187] The system <b>402</b> also has an integrity ascertainment server <b>420</b> that tests the yellow code <b>160</b> to determine if it is green or red code. The server <b>420</b> has a processing system <b>422</b> and implements an integrity ascertainer <b>424</b>.

P-0188[0188] The integrity ascertainer <b>424</b> is the exemplary integrity ascertainer of the exemplary integrity veracitor, described herein.

P-0189[0189] The integrity ascertainment system <b>402</b> is illustrated as a single entity, with memory and processing capabilities, for ease of discussion. In practice, however, the system <b>402</b> may be configured as one or more computers that jointly or independently perform the tasks of ascertaining whether a digital good has been tampered.

P-0190[0190] The integrity ascertainment system <b>402</b> is coupled to a client via a network <b>406</b> (such as the Internet). The client <b>404</b> is analogous to the client <b>304</b> illustrated in FIG. 3 and described above. The client <b>404</b> includes a memory <b>442</b> storing a copy of yellow code <b>160</b>.

P-0191[0191] When a client wishes to confirm the integrity of yellow code <b>160</b>, it requests the assistance of the integrity ascertainer <b>424</b> of the integrity ascertainment system <b>402</b>. Alternatively, the integrity ascertainment system <b>402</b> may initiate the integrity verification of the yellow code <b>160</b>.

P-0192[0192] In response, the ascertainer <b>424</b> transmits the parameters (shown as parameters <b>140</b><i>b </i>in transit) over a network (such as the Internet) to the client <b>404</b>. The client includes a local portion of the integrity ascertainer (as illustrated in FIG. 3). That local portion generates a yellow signature <b>162</b> using the yellow code <b>160</b> and the parameters <b>140</b><i>b</i>. The client sends the yellow signature <b>162</b> back to the integrity ascertainer <b>124</b>, where the ascertainer compares it to the green signature <b>132</b>.

P-0193[0193] Alternatively, the client may transmit the yellow code (or a portion thereof) to the integrity ascertainment system <b>402</b>. In this case, all parts of the test are performed at the system <b>402</b>, rather than partially at the client.

P-0194[0194] In the event that the exemplary integrity ascertainer detects some tamper activity (e.g., the signatures are distinguishable), it directs the client to decline execution of the tampered code.

P-0195[0195] Remote Code Verification

P-0196[0196] One implementation for the exemplary integrity veracitor is in the field of remote code verification. This is where secure access from a remote client to a server is limited to secure program modules. The server should remotely verify that the program module seeking access from the client is untampered.

P-0197[0197] A challenge-response protocol periodically requests that the client send a hash of its execution and/or output, and the server verifies the hash by executing the client code. Unlike any other existing remote verification technique, this requires the actual execution and/or output of the code being verified. Therefore, an attacker cannot modify the program to simply return some predetermined response to a given challenge.

P-0198[0198] Methodological Implementations of the Exemplary Integrity Veracitor

P-0199[0199]FIGS. 5 and 6 show methodological implementations of the exemplary integrity veracitor performed (in whole or in part) by an integrity veracitication system. In particular, these methodological implementations employ the execution-tracing form. These implementations may be performed by embodiments of the integrity ordainer <b>270</b>; the integrity ascertainment system <b>302</b>; and/or a computing environment like that shown in FIG. 9. These methodological implementations may be performed in software, hardware, or a combination thereof.

P-0200[0200]FIG. 5 shows a methodological implementation of the exemplary integrity ordainer performed (in whole or in part) by the integrity ordainer <b>370</b>.

P-0201[0201] At <b>510</b>, the exemplary integrity ordainer produces the green code by strategically inserting black code into the clear code. At <b>512</b>, an execution trace is generated while one or more program modules of the green code are executed with given parameters.

P-0202[0202] At <b>514</b>, the results of the trace are hashed to produce the green signature. At <b>516</b>, the green signature and parameters are stored in association with the green code. At <b>520</b>, this process ends.

P-0203[0203]FIG. 6 shows a methodological implementation of the exemplary integrity ascertainer performed (in whole or in part) by the integrity ascertainment system <b>402</b>.

P-0204[0204] At <b>610</b>, one or more program modules of the yellow code are identified. The associated green signature and given parameters are located. At <b>612</b>, the exemplary integrity ascertainer generates an execution trace while the one or more identified program modules of the yellow code are executed with the given parameters.

P-0205[0205] At <b>614</b>, the results of the trace are hashed to produce the yellow signature. At <b>616</b>, the yellow signature and green signature are compared. Block <b>618</b> determines if these signatures are indistinguishable. If they are indistinguishable, then the integrity of the code is confirmed at <b>620</b>. If they are distinguishable, then it is indicated that the code has been tampered with at <b>622</b>. See FIGS. 1E and 1F for visual representation of blocks <b>616</b>-<b>622</b>.

P-0206[0206] At <b>630</b>, this process ends.

P-0207[0207] Other Methodological Implementations of the Exemplary Integrity Veracitor

P-0208[0208]FIGS. 7 and 8 show methodological implementations of the exemplary integrity veracitor performed (in whole or in part) by an integrity veracitication system. In particular, these methodological implementations employ the output-tracing form. These implementations may be performed by embodiments of the integrity ordainer <b>270</b>; the integrity ascertainment system <b>302</b>; and/or a computing environment like that shown in FIG. 9. These methodological implementations may be performed in software, hardware, or a combination thereof.

P-0209[0209]FIG. 7 shows a methodological implementation of the exemplary integrity ordainer performed (in whole or in part) by the integrity ordainer <b>370</b>.

P-0210[0210] At <b>712</b>, the exemplary integrity ordainer generates an output trace of multiple execution instances the green code based upon specified parameters.

P-0211[0211] At <b>714</b>, the results of the trace are hashed to produce the green signature. At <b>716</b>, the green signature and parameters are stored in association with the green code. At <b>720</b>, this process ends.

P-0212[0212]FIG. 8 shows a methodological implementation of the exemplary integrity ascertainer performed (in whole or in part) by the integrity ascertainment system <b>402</b>.

P-0213[0213] At <b>810</b>, one or more program modules of the yellow code are identified. The associated green signature and specified parameters are located. At <b>812</b>, the exemplary integrity ascertainer generates an output trace of multiple execution instances the yellow code based upon specified parameters.

P-0214[0214] At <b>814</b>, the results of the trace are hashed to produce the yellow signature. At <b>816</b>, the yellow signature and green signature are compared. Block <b>818</b> determines if these signatures are indistinguishable. If they are indistinguishable, then the integrity of the code is confirmed at <b>820</b>. If they are distinguishable, then it is indicated that the code has been tampered with at <b>822</b>. See FIGS. 1E and 1F for visual representation of blocks <b>816</b>-<b>822</b>.

P-0215[0215] At <b>830</b>, this process ends.

P-0216[0216] Exemplary Computing System and Environment

P-0217[0217]FIG. 9 illustrates an example of a suitable computing environment <b>900</b> within which an exemplary integrity veracitor, as described herein, may be implemented (either fully or partially). The computing environment <b>900</b> may be utilized in the computer and network architectures described herein.

P-0218[0218] The exemplary computing environment <b>900</b> is only one example of a computing environment and is not intended to suggest any limitation as to the scope of use or functionality of the computer and network architectures. Neither should the computing environment <b>900</b> be interpreted as having any dependency or requirement relating to any one or combination of components illustrated in the exemplary computing environment <b>900</b>.

P-0219[0219] The exemplary integrity veracitor may be implemented with numerous other general purpose or special purpose computing system environments or configurations. Examples of well known computing systems, environments, and/or configurations that may be suitable for use include, but are not limited to, personal computers, server computers, thin clients, thick clients, hand-held or laptop devices, multiprocessor systems, microprocessor-based systems, set top boxes, programmable consumer electronics, network PCs, minicomputers, mainframe computers, distributed computing environments that include any of the above systems or devices, and the like.

P-0220[0220] The exemplary integrity veracitor may be described in the general context of computer-executable instructions, such as program modules, being executed by a computer. Generally, program modules include routines, programs, objects, components, data structures, etc. that perform particular tasks or implement particular abstract data types. The exemplary integrity veracitor may also be practiced in distributed computing environments where tasks are performed by remote processing devices that are linked through a communications network. In a distributed computing environment, program modules may be located in both local and remote computer storage media including memory storage devices.

P-0221[0221] The computing environment <b>900</b> includes a general-purpose computing device in the form of a computer <b>902</b>. The components of computer <b>902</b> can include, by are not limited to, one or more processors or processing units <b>904</b>, a system memory <b>906</b>, and a system bus <b>908</b> that couples various system components including the processor <b>904</b> to the system memory <b>906</b>.

P-0222[0222] The system bus <b>908</b> represents one or more of any of several types of bus structures, including a memory bus or memory controller, a peripheral bus, an accelerated graphics port, and a processor or local bus using any of a variety of bus architectures. By way of example, such architectures can include an Industry Standard Architecture (ISA) bus, a Micro Channel Architecture (MCA) bus, an Enhanced ISA (EISA) bus, a Video Electronics Standards Association (VESA) local bus, and a Peripheral Component Interconnects (PCI) bus also known as a Mezzanine bus.

P-0223[0223] Computer <b>902</b> typically includes a variety of computer readable media. Such media can be any available media that is accessible by computer <b>902</b> and includes both volatile and non-volatile media, removable and non-removable media.

P-0224[0224] The system memory <b>906</b> includes computer readable media in the form of volatile memory, such as random access memory (RAM) <b>910</b>, and/or non-volatile memory, such as read only memory (ROM) <b>912</b>. A basic input/output system (BIOS) <b>914</b>, containing the basic routines that help to transfer information between elements within computer <b>902</b>, such as during start-up, is stored in ROM <b>912</b>. RAM <b>910</b> typically contains data and/or program modules that are immediately accessible to and/or presently operated on by the processing unit <b>904</b>.

P-0225[0225] Computer <b>902</b> may also include other removable/non-removable, volatile/non-volatile computer storage media. By way of example, FIG. 9 illustrates a hard disk drive <b>916</b> for reading from and writing to a non-removable, non-volatile magnetic media (not shown), a magnetic disk drive <b>918</b> for reading from and writing to a removable, non-volatile magnetic disk <b>920</b> (e.g., a “floppy disk”), and an optical disk drive <b>922</b> for reading from and/or writing to a removable, non-volatile optical disk <b>924</b> such as a CD-ROM, DVD-ROM, or other optical media. The hard disk drive <b>916</b>, magnetic disk drive <b>918</b>, and optical disk drive <b>922</b> are each connected to the system bus <b>908</b> by one or more data media interfaces <b>926</b>. Alternatively, the hard disk drive <b>916</b>, magnetic disk drive <b>918</b>, and optical disk drive <b>922</b> can be connected to the system bus <b>908</b> by one or more interfaces (not shown).

P-0226[0226] The disk drives and their associated computer-readable media provide nonvolatile storage of computer readable instructions, data structures, program modules, and other data for computer <b>902</b>. Although the example illustrates a hard disk <b>916</b>, a removable magnetic disk <b>920</b>, and a removable optical disk <b>924</b>, it is to be appreciated that other types of computer readable media which can store data that is accessible by a computer, such as magnetic cassettes or other magnetic storage devices, flash memory cards, CD-ROM, digital versatile disks (DVD) or other optical storage, random access memories (RAM), read only memories (ROM), electrically erasable programmable read-only memory (EEPROM), and the like, can also be utilized to implement the exemplary computing system and environment.

P-0227[0227] Any number of program modules can be stored on the hard disk <b>916</b>, magnetic disk <b>920</b>, optical disk <b>924</b>, ROM <b>912</b>, and/or RAM <b>910</b>, including by way of example, an operating system <b>926</b>, one or more application programs <b>928</b>, other program modules <b>930</b>, and program data <b>932</b>. Each of such operating system <b>926</b>, one or more application programs <b>928</b>, other program modules <b>930</b>, and program data <b>932</b> (or some combination thereof) may include an embodiment of challenger, response-receiver, authenticator, integrity ordainer, and integrity ascertainer.

P-0228[0228] A user can enter commands and information into computer <b>902</b> via input devices such as a keyboard <b>934</b> and a pointing device <b>936</b> (e.g., a “mouse”). Other input devices <b>938</b> (not shown specifically) may include a microphone, joystick, game pad, satellite dish, serial port, scanner, and/or the like. These and other input devices are connected to the processing unit <b>904</b> via input/output interfaces <b>940</b> that are coupled to the system bus <b>908</b>, but may be connected by other interface and bus structures, such as a parallel port, game port, or a universal serial bus (USB).

P-0229[0229] A monitor <b>942</b> or other type of display device can also be connected to the system bus <b>908</b> via an interface, such as a video adapter <b>944</b>. In addition to the monitor <b>942</b>, other output peripheral devices can include components such as speakers (not shown) and a printer <b>946</b> which can be connected to computer <b>902</b> via the input/output interfaces <b>940</b>.

P-0230[0230] Computer <b>902</b> can operate in a networked environment using logical connections to one or more remote computers, such as a remote computing device <b>948</b>. By way of example, the remote computing device <b>948</b> can be a personal computer, portable computer, a server, a router, a network computer, a peer device or other common network node, and the like. The remote computing device <b>948</b> is illustrated as a portable computer that can include many or all of the elements and features described herein relative to computer <b>902</b>.

P-0231[0231] Logical connections between computer <b>902</b> and the remote computer <b>948</b> are depicted as a local area network (LAN) <b>950</b> and a general wide area network (WAN) <b>952</b>. Such networking environments are commonplace in offices, enterprise-wide computer networks, intranets, and the Internet.

P-0232[0232] When implemented in a LAN networking environment, the computer <b>902</b> is connected to a local network <b>950</b> via a network interface or adapter <b>954</b>. When implemented in a WAN networking environment, the computer <b>902</b> typically includes a modem <b>956</b> or other means for establishing communications over the wide network <b>952</b>. The modem <b>956</b>, which can be internal or external to computer <b>902</b>, can be connected to the system bus <b>908</b> via the input/output interfaces <b>940</b> or other appropriate mechanisms. It is to be appreciated that the illustrated network connections are exemplary and that other means of establishing communication link(s) between the computers <b>902</b> and <b>948</b> can be employed.

P-0233[0233] In a networked environment, such as that illustrated with computing environment <b>900</b>, program modules depicted relative to the computer <b>902</b>, or portions thereof, may be stored in a remote memory storage device. By way of example, remote application programs <b>958</b> reside on a memory device of remote computer <b>948</b>. For purposes of illustration, application programs and other executable program components such as the operating system are illustrated herein as discrete blocks, although it is recognized that such programs and components reside at various times in different storage components of the computing device <b>902</b>, and are executed by the data processor(s) of the computer.

P-0234[0234] Computer-Executable Instructions

P-0235[0235] An implementation of an exemplary integrity veracitor may be described in the general context of computer-executable instructions, such as program modules, executed by one or more computers or other devices. Generally, program modules include routines, programs, objects, components, data structures, etc. that perform particular tasks or implement particular abstract data types. Typically, the functionality of the program modules may be combined or distributed as desired in various embodiments.

P-0236[0236] Exemplary Operating Environment

P-0237[0237]FIG. 9 illustrates an example of a suitable operating environment <b>900</b> in which an exemplary integrity veracitor may be implemented. Specifically, the exemplary integrity veracitor(s) described herein may be implemented (wholly or in part) by any program modules <b>928</b>-<b>930</b> and/or operating system <b>926</b> in FIG. 9 or a portion thereof.

P-0238[0238] The operating environment is only an example of a suitable operating environment and is not intended to suggest any limitation as to the scope or use of functionality of the exemplary integrity veracitor(s) described herein. Other well known computing systems, environments, and/or configurations that are suitable for use include, but are not limited to, personal computers (PCs), server computers, hand-held or laptop devices, multiprocessor systems, microprocessor-based systems, programmable consumer electronics, wireless phones and equipments, general- and special-purpose appliances, application-specific integrated circuits (ASICs), network PCs, minicomputers, mainframe computers, distributed computing environments that include any of the above systems or devices, and the like.

P-0239[0239] Computer Readable Media

P-0240[0240] An implementation of an exemplary integrity veracitor may be stored on or transmitted across some form of computer readable media. Computer readable media can be any available media that can be accessed by a computer. By way of example, and not limitation, computer readable media may comprise “computer storage media” and “communications media.”

P-0241[0241] “Computer storage media” include volatile and non-volatile, removable and non-removable media implemented in any method or technology for storage of information such as computer readable instructions, data structures, program modules, or other data. Computer storage media includes, but is not limited to, RAM, ROM, EEPROM, flash memory or other memory technology, CD-ROM, digital versatile disks (DVD) or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium which can be used to store the desired information and which can be accessed by a computer.

P-0242[0242] “Communication media” typically embodies computer readable instructions, data structures, program modules, or other data in a modulated data signal, such as carrier wave or other transport mechanism. Communication media also includes any information delivery media.

P-0243[0243] The term “modulated data signal” means a signal that has one or more of its characteristics set or changed in such a manner as to encode information in the signal. By way of example, and not limitation, communication media includes wired media such as a wired network or direct-wired connection, and wireless media such as acoustic, RF, infrared, and other wireless media. Combinations of any of the above are also included within the scope of computer readable media.

P-0244[0244] Other Implementation Details

P-0245[0245] The focus of this section is on “remote code verification.” However, these implementation details are applicable to other implementations of integrity ordainment and ascertainment of computer-executable instructions.

P-0246[0246] Persistent Remote Authentication

P-0247[0247] Some applications, such as Internet instant-messaging systems, include a small, simple client program that connects to a (physically) secure server over a network. Deployers of such systems may require that only authorized, unmodified client software use the servers. However, a pirate may reverse engineer the client-server communications without great difficulty and create a fully functional but unauthorized client program. Moreover, a pirate can patch the code or data of an original, authorized client in order to have it perform unauthorized actions.

P-0248[0248] This raises the question of how a server can ensure that only authorized clients connect and that such clients remain free from tampering. This problem may be called “persistent remote authentication.” It may also be called “remote code verification.”

P-0249[0249] Traditional authentication protocols do not address the problem described, because unauthorized parties can reverse engineer such protocols and write new software to implement them. Furthermore, traditional protocols do not deal with code tampering; an attacker can modify a client program's code or data without changing its implementation of an authentication protocol. To take into account both of these issues simultaneously, a new approach is necessary.

P-0250[0250] The exemplary integrity veracitor may be implemented to provide a persistent-authentication technique that addresses the problems presented. The technique includes a challenge-response authentication protocol combined with code execution and/or output ordainment and ascertainment. Oblivious hashing (OH) is the form of code execution and/or output ordainment and ascertainment, described hereafter.

P-0251[0251] Briefly, the challenge-response protocol periodically requests that the client send a hash of its execution and/or output, and the server verifies the hash by executing or simulating the client code.

P-0252[0252] Oblivious Hashing of a Function

P-0253[0253] This subsection describes some details of a scheme for oblivious hashing. The technique converts a function into a protected version automatically or semi-automatically by adding code. One can do this at the source-code level (by parsing source files, inserting code, and recompiling) or at the binary level (by analyzing an executable with a tool and injecting code and data).

P-0254[0254] As described herein, the technique concentrates on a tool-based approach of inserting extra instructions and calls for hashing and checking a function's state. A function can verify itself by making recursive calls with appropriate inputs; alternately, calls injected into other functions can perform the verification.

P-0255[0255] With this oblivious hashing (OH) technique, a function's behavior is hashed without reading the function's code. The hashing has weak collision resistance in the following sense: given a function f and its hash value H(f)=h, it is hard to make minor modifications to f such that the resulting function f′ has the same hash value H(f′)=h.

P-0256[0256] OH Infrastructure

P-0257[0257] Spy variables (S-vars)—these are global variables that provide secure storage for values. If a value is stored in an s-var, it has very high tamper resistance. Implementation of spy variables will be discussed later.

P-0258[0258] Spy loops (S-loops)—these are loops in the program that can be called in a controlled fashion (e.g., they can be called wherever needed). Note that a loop from the original program is likely not to serve the purpose, because of its side effects. Often an S-loop is a redundant dummy loop inserted into the program, whose redundancy is hard to detect through simple analysis. One way to achieve this is to have the loop call an arbitrary function γ and its inverse γ⁻¹, in succession, on a spy variable. S-loops are not necessarily traditional ‘for’ or ‘while’ loops, but rather arbitrary execution sequences that form loops; such sequences can include many functions at various nesting levels, and can be difficult to detect as loops.

P-0259[0259] Automatic generation of coverage data—Given a ‘small’ sized function f, it should be possible to generate, automatically or semi-automatically, a set of inputs I, such that the union of the execution paths forced by these inputs covers all statements in the function.

P-0260[0260] Oblivious Hashing

P-0261[0261] Given a function f to be hashed,

P-0262[0262] Insert, at strategic points in f, “capture” instructions (C-instructions) that load “snapshots” of function state into special registers or variables.

P-0263[0263] C-instructions are normal instructions that modify registers and/or memory. Any clever attack should detect all of these first.

P-0264[0264] Removal of a C-instruction is not a valid attack—an attack should make the modified function produce the same snapshots. This is because the hash value is dependent on the snapshot values, and the attack should achieve the same hash value for a modified function.

P-0265[0265] One possible attack is to hardwire the C-instruction to record the expected snapshot—such hardwiring becomes infeasible if there are many possible snapshots at the same point; if all possible inputs to the function are not known, this attack may fail.

P-0266[0266] Another attack is to insert appropriate instructions after the last C-instruction—this attack can be effective, but the adversary should go through the entire function, detect all the C-instructions, and copy all other instructions. Thus this attack can be expensive.

P-0267[0267] A “snapshot” is a set of register and flag values that were (potentially) modified since the last snapshot. In other words, it is a row in the table of the execution trace shown in FIG. 2A. This snapshot may be discovered by a simple static analysis (conservative) (e.g., to detect the appropriate registers one only has to detect register defs in a basic block).

P-0268[0268] An efficient implementation for taking the aforementioned “snapshot” can be achieved by inserting instructions after every assignment, branch, and procedural call. This insertion can best be done in the intermediate representation (i.e., syntax tree) of the source program. In addition, each instance of inserted “snapshot-taking” function need not be a cryptographically strong function. It can be as simple as the following form: H=H op V, where H is the variable holding the hash value and V is the value of the assignment, or branch condition, or function call result expression, and op is randomly chosen from a pre-determined set of arithmetic and logical operators. Note that even though each snapshot-taking function is simple, a sequence of these functions, randomly chosen when the program is being compiled, but otherwise fixed afterwards, provides a strong means to hash the execution instance of a procedure.

P-0269[0269] The snapshot can be loaded into global variables created specially for this purpose. Such variables should be referenced with secrecy (e.g., through pointers). Spy variables could be used for this purpose. The other option is to use an extra argument (local variable—on the stack) to store the snapshot in. This can be slightly tricky to implement, but it is stealthier, since it is very common for functions to access parameters passed on the stack.

P-0270[0270] Having augmented f (as above) to capture its state at different execution points, the exemplary integrity veracitor inserts calls to fat strategic points in the program. Such calls may be referred to as “hashing calls”. These calls are made with specially chosen input values so that among them they force most of the possible execution paths in f to be exercised.

P-0271[0271] A hashing call is typically an indirect call. It takes its target address from a global variable, which has been set to the address of f a priori. This is done in the “preparation stage” of the hashing call—a small piece of code that dominates the call, but is not very close to the call, and preferably in another function. Potentially, the same global variable can serve to hold the target address for all hashing calls to f, but its reference pattern may become conspicuous. It is desirable to test if normal code has several indirect calls through the same variable.

P-0272[0272] A hashing call captures the function behavior on the given input, and loads it into some variables. These variable values will be called the “output” of f (on the corresponding input), and be denoted by f (i) where i is the input. The point where a hashing call is made is called a hashing caller. Such callers have the following general behavior—

P-0273[0273] i←S_i

P-0274[0274] o←f(i)

P-0275[0275] o←g(o)

P-0276[0276] S_j←o

P-0277[0277] S_iand S_jare arbitrary but pre-determined S-vars. Each caller takes the input from an S-var, calls f, processes the output in some way (the function g), and stores it in another S-var, to be picked up later by some other caller. i and o are abstract temporaries, they may or may not be actual registers or memory.

P-0278[0278] A hashing caller (defined above) may or may not be a separate function. If it is, it will be amenable to oblivious hashing itself, but will also be more prominent (less stealthy) than when it is part of another function.

P-0279[0279] Now that the hashing calls have been described, the oblivious hashing scheme will be described. Given the function f, the scheme produces a hash of this function, H(f), which changes if f changes behavior.

P-0280[0280] Let H^fbe the set of all hashing callers of f. They may be implemented as separate functions that are called from inside an s-loop. For a particular input i, some subset of H^fbecomes “active”, in the sense that only active callers are actually executed. The active ones in the above diagram are shaded in blue, and are named h₁through h₄. The sequence of events is:

P-0281[0281] The value i is written into a spy variable S_j.

P-0282[0282] The s-loop containing H^fis called. Each h_icontains a hashing call to f. However, not all h_iare active, and only the active ones are actually called from inside the loop.

P-0283[0283] Each h_imodifies a pre-determined S-var, and the next h_jto be executed automatically picks up its input from there.

P-0284[0284] After the s-loop executes, the last modified S-var is produced as output, H. the pair {i,H} is the required hash value.

P-0285[0285] One aspect of this scheme that has not been discussed yet is how to choose input value i so that most of the possible execution paths in f are exercised. This may be done as follows (by way of example and not limitation):

P-0286[0286] A set of inputs I={i₁, i₂, . . . i_k} is chosen that forces most execution paths in f to be exercised.

P-0287[0287] Suppose the total number of hashing callers intended multiplied by the number of times each is executed is n. I is a cardinality n (i.e., k=n). I is stored in the form of an array.

P-0288[0288] Now, the behavior of a hashing caller, as described above, is modified to be:

P-0289[0289] i←S_i

P-0290[0290] index←R(i)

P-0291[0291] i←(index)

P-0292[0292] o←f(i)

P-0293[0293] o←g(o)

P-0294[0294] S_j←o

P-0295[0295] (i.e., instead of using S₁as input directly, the hashing caller uses it to index into I, and gets the actual input from there.)

P-0296[0296] Note: The S_iand S_jmentioned above will be different for different i, since each i defines a unique set of fixed intermediate values. In fact, each S_icould be an array element, indexed by i.

P-0297[0297] Spy Variables

P-0298[0298] A spy variable (S-var) is a global variable where pre-determined values (such as those encountered in checksum computations) may be stored in a secure (tamper resistant) and stealthy (inconspicuous) manner. The basic idea behind S-vars is the following: Suppose I want to store the constant value v securely. If I can integrate this constant v into the rest of the program so that it is needed for the correct execution of the program, then the value becomes secure—tampering can result in unpredictable results, and since the variable is referenced by the main program (as opposed to the added security code), it is not conspicuous.

P-0299[0299] However, this simple idea is not trivial to implement. First of all, it is not apparent how an arbitrary value may be integrated (inconspicuously) into a given program. Secondly, one has to be wary of fairly simple constant-propagation kind of analyses—these may reveal constant values being used. S-vars are a means to integrating a pre-determined value into the main program.

P-0300[0300] S-vars may be implemented as follows (by way of example and not limitation):

P-0301[0301] If global variables S₁and S₂are known to have pre-determined values v₁and v₂at point P in the program and thereafter. Also, let v_diff=v₁−v₂. Clearly, V_diffis a known constant.

P-0302[0302] Suppose static analysis shows that there is a function g that is called after point P, and cannot be called before point P is reached. Let a be one of the arguments of the call to g.

P-0303[0303] In every call to g, the argument a is replaced by (a+S₁). Inside the body of function g, the following code is inserted in the very beginning: a←(a−S₂−v_diff). Clearly, the semantics of function g are preserved.

P-0304[0304] The key observation is that the adversary does not know that S₁and S₂have fixed pre-determined values. They look like ordinary variables, set in one region of the program and referenced in another. Hence, attacks based on constant propagation are ruled out.

P-0305[0305] Generation of Coverage Data

P-0306[0306] Knowledge of a particular function's inputs and actions can greatly help with generating coverage data. One can specify the types and possible values of inputs, and rely on a tool to generate specific input data. This manual process can accelerate and simplify the task at hand, although in an ideal setting, coverage-data generation would be fully automatic.

P-0307[0307] Mini-Implementation

P-0308[0308] Below are the details of a “mini-implementation” of the oblivious hashing scheme, assuming tool-based code injection into a binary.

P-0309[0309] Input:

P-0310[0310] A program binary B.

P-0311[0311] A function f in B that is to be hashed—f is indicated by a name prefix, “hash_this”

P-0312[0312] A point p where the hash is to be computed, i.e., where the check is to be placed. p is marked using a special label “INSERT_CHECK_HERE:”.

P-0313[0313] Output: Modified program B′, with added code for oblivious hashing of f, and for computing the checksum (of f) at point p.

P-0314[0314] Assumptions:

P-0315[0315] The function f is completely free of side effects (purely functional).

P-0316[0316] The function f has no indirect memory references.

P-0317[0317] While such assumptions often do not hold in real code, oblivious hashing can simply ignore the parts of the state that cannot be hashed (e.g., because they change unpredictably). In order for hashing to work well, such state components are not critical to security.

P-0318[0318] Steps:

P-0319[0319] Scan B for f and p.

P-0320[0320] Analyze f, determine what constitutes an “input” to f, and create an array of inputs I that force most execution paths to be exercised. This step is done manually as of now. One way to facilitate this is to use visual representation tools displaying the function structure.

P-0321[0321] Add C-instructions to f.

P-0322[0322] First, decide which points need C-instructions. Each register de f has a C-instruction associated with it, and at a point where the register is still live.

P-0323[0323] Maintain a list of unrecorded register defs at every point in the function.

P-0324[0324] Traverse the CFG of basic blocks in a breadth first manner.

P-0325[0325] The unrecorded register list at the end of a block is “transferred” to the children (children does not include call targets.)

P-0326[0326] If a block has no children, or its children have already been handled, the register list is emptied (recorded).

P-0327[0327] Recording a register list need not be a sequence of move or add instructions.

P-0328[0328] It could be some random operations that reads each of the registers in the list, and copies the result on to the recording variable.

P-0329[0329] The recording variable is a variable allocated on the top of the stack.

P-0330[0330] Expand the stack by one word: i.e., the C-instructions will store the “snapshot” in a word just above the stack.

P-0331[0331] The register esp typically points to the top of the stack (except during a function call, when it is first raised during the push-es and then lowered (add esp,.) after call). Thus in order to write “above” the top of the stack, it is simply written at dword ptr [esp-4].

P-0332[0332] During function calls should not overwrite that word. It should be pushed on to the stack before the function call. The other option is to save it in global variables during calls.

P-0333[0333] Create a function h as follows (by way of example and not limitation):

P-0334[0334] It has a single argument (i)

P-0335[0335] There is a dummy loop in the body that applies a function γ followed by γ⁻¹on a global variable S. γ is a manually designed pre-determined function. S is a specially allocated global variable. The number of times the loop executes is obtained from the last four bits of i.

P-0336[0336] The loop has calls to functions h_j, conditioned on specific bits of i, and with three arguments—the addresses of the S-var where the h_jgets its input from, and where it stores its output, and the address of f. The third argument could be in the form of a global variable S_f.

P-0337[0337] Insert a call to h at point p. Use i as argument. (i is stored a priori in a global variable.)

P-0338[0338] Insert the bodies of the functions h_jat different places in B. Each function h_jlooks like this:

P-0339[0339] One argument gives it the address of the variable that stores its input. It fetches the input i from that address.

P-0340[0340] It converts i into a suitable index to fetch the actual input from the array I. The actual input is then fetched into i.

P-0341[0341] It calls f (i). It gets the address of f as an argument too.

P-0342[0342] It uses the known offset of the snapshot on f 's stack to fetch the “output” of f. It applies some transformations to this value and stores it in a fixed address S_j. This address is obtained in the form of an argument to h_j.

P-0343[0343] Simulate the call to h. Examine the final values of all the S_js. Let these be denoted by v_j. Use pairs of such v_js to create S-vars as described above. Store these v_js in the appropriate S-vars.

P-0344[0344] A Protocol for Persistent Remote Authentication

P-0345[0345] This subsection presents the details of our persistent-authentication protocol. The scheme provides an example of how oblivious hashing can be used to protect a specific algorithm.

P-0346[0346] Scenario: Server S, Client C, program P.

P-0347[0347] S gives C a (potentially modified) copy of P. Let us call this copy P_cC executes P_c. There is a communication channel CS between C and S.

P-0348[0348] Requirements: A communication protocol between S and C by which S can infer the following:

P-0349[0349] That the other communicating party is a program issued by S. (Authentication)

P-0350[0350] That the communicating party is P_c—if the latter were replaced by another program or a modified program P_cthen S would detect the change. (Tamper-resistance)

P-0351[0351] That a certain function f in P_cwas executed on C.

P-0352[0352] Scheme:

P-0353[0353] C sends S its hardware id h.

P-0354[0354] S uses h to create a secret key K_h. S then uses K_hto create a randomly individualized version P_cof P.

P-0355[0355] S sends C the program P_c.

P-0356[0356] Periodically, S sends a challenge x to C, via channel CS.

P-0357[0357] Upon receiving a challenge x C performs some actions, and sends a response r(x) to S.

P-0358[0358] S verifies that the response from C.

P-0359[0359] Challenge-Response Schemes

P-0360[0360] The input x is treated as a concatenation of two numbers x₁and x₂(of known lengths). The response, likewise, is a concatenation of two responses—r₁(x₁) and r₂(x₂).

P-0361[0361] Computing r₁(x₁)—A coin is tossed, using x₁and h as seeds. Based on the result of the coin toss, the response is computed by one out of two schemes S₁and S₂with probabilities p and 1-p respectively. The schemes S₁and S₂are described shortly. Since the server knows x and h, it knows the result of the coin toss (remotely), and therefore knows which kind of challenge-response to expect. Scheme S₁is used with a very high probability p—the server can compute the expected response in this scheme very efficiently. Scheme S₂is deployed with a relatively low probability 1-p—computing its response involves executing (a part of) P_c—this puts a much higher load on server S.

P-0362[0362] Scheme S₁

P-0363[0363] A cryptographic function R resides secretly in P_C. It is thoroughly integrated with P_c, so it is hard to isolate and determine this function. One has to execute (a part of) P_cto execute R. In scheme S₁, the response r₁(x₁) is the output of the function R on input x. The function R is individualized for client C—it uses some unique constants that are secretly hard-wired into it—so that R(x₁) is different for different clients. An implementation of R is merged so thoroughly with the original code P_cthat to unravel it requires manually examining most of the code.

P-0364[0364] The response of this scheme is simply the value R(x₁), or more precisely, R(x₁,K_h), since R is individualized for C using key K_h. The server can efficiently compute this value since it knows K_h. This scheme meets requirements (1) and (2) in a weak sense. A functionally equivalent version of P_cwill be detected by the server, but minor changes in P_cthat do not change R will not be detected.

P-0365[0365] Scheme S₂

P-0366[0366] x₁specifies a path in the execution of P_c, and r₁(x₁) captures (a hash of) the intermediate program states. This meets requirements (1) and (2) in a robust manner—even minor changes in P_ccan be detected in the response computed. Moreover, by having the function f called in the course of the executed path, requirement (3) may also be met. The flip side is that this scheme requires the server to execute (a portion of) P_cin order to compute the expected challenge-response. Obviously, this is expensive and is hence used rarely.

P-0367[0367] The combination of the two schemes above, with the first scheme executed most often, provides a balance between efficiency and robustness of tamper-resistance (i.e., protection). One should remember that a single failed check is enough to classify client C as a compromised client.

P-0368[0368] Computing r₂(x₂)—Consider the program P_cas a collection of pieces. On any input x (out of a finite large set), one piece in the collection is “special”—some signature configuration is encountered when it is reached. Which piece is special (the “coordinates” C_x) depends on h and K_h—this is the individualization. The server doesn't have to execute the program to verify the challenge-response. The relationship (x, C_x) can be verified by using the secret key. The “special configuration” might be a known pattern that is hard to detect without executing the relevant piece of code—something like an Easter egg. There is a response module: It calls different functions, and checks if the Easter egg has been found, and if so, in which function. The function f is one of the functions that might be special—this forces its execution for computing the response r₂. A problem with the above scheme is that only a finite set of challenges “x” is possible. The solution is in posing many more (say 1000 times more) dummy challenges. The correct response to these would be a “no-show” response. Thus, most of the time x₂is a dummy challenge soliciting a dummy no-show response. However, in order to know which challenges are dummy and which are not, the client has to execute (a portion of) P_con x₂. The server S, however, doesn't need to execute P_c.

Conclusion

P-0369[0369] Although the invention has been described in language specific to structural defined in the appended claims is not necessarily limited to the specific features or steps described. Rather, the specific features and steps are disclosed as preferred