# US 8,788,884 B2 · Automatic correction of program logic > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 8,788,884 B2 - Document ID: US8788884B2 - Status: Granted - Kind: B2 - Application number: 12/961,922 - Filed: 2010-12-07 - Published: 2012-06-07 - Granted: 2014-07-22 - Earliest claimed: 2010-12-07 - Assignees: Massachusetts Institute of Technology; BAE Systems Information and Electronic Systems Integration Inc. - Applicants: Jeff Herbert Perkins; Stylianos Sidiroglou; Martin Conway Rinard; Eric Patrick Lahtinen; Paolo Mario Piselli; Basil C Krikeles; Timothy Alan Anderson; Greg Timothy Sullivan - Inventors: Jeff Herbert Perkins; Stylianos Sidiroglou; Martin Conway Rinard; Eric Patrick Lahtinen; Paolo Mario Piselli; Basil C Krikeles; Timothy Alan Anderson; Greg Timothy Sullivan - Web page: https://patentgrep.com/patent/US8788884B2 ## CPC - G06F 11/3636: {by tracing the execution of the program} - G06F 11/0793: {Remedial or corrective actions (recovery from an exception in an instruction pipeline G06F9/3861; by retry G06F11/1402; for recovering from a failure of a protocol instance or entity H04L69/40)} - G06F 11/3612: {by runtime analysis (performance monitoring G06F11/3466)} - G06F 21/52: during program execution, e.g. stack integrity {; Preventing unwanted data erasure; Buffer overflow} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract An approach to detection and repair of application level semantic errors in deployed software includes inferring aspects of correct operation of a program. For instance, a suite of examples of operations that are known or assumed to be correct are used to infer correct operation. Further operation of the program can be compared to results found during correct operation and the logic of the program can be augmented to ensure that aspects of further examples of operation of the program are sufficiently similar to the examples in the correct suite. In some examples, the similarity is based on identifying invariants that are satisfied at certain points in the program execution, and augmenting (e.g., “patching”) the logic includes adding tests to confirm that the invariants are satisfied in the new examples. In some examples, the logic invokes an automatic or semi-automatic error handling procedure if the test is not satisfied. Augmenting the logic in this way may prevent malicious parties from exploiting the semantic errors, and may prevent failures in execution of the programs that may have been avoided. ## Claims ### Claim 1 A computer implemented method for automatically patching errors in a software system that includes a first software component and a second software component including a set of interfaces, the method comprising: monitoring a first set of executions of the software system including: monitoring a plurality of error-free interactions between the first software component and the set of interfaces of the second software component; identifying invariants from the plurality of error-free interactions, each invariant being associated with one or more contexts; forming a data structure including an association of each interface in the set of interfaces with invariants associated with that interface; and monitoring a second set of executions of the software system including: accepting the formed data structure; for each interaction of a plurality of interactions between the first software component and the set of interfaces of the second software component in a second set of executions: using the data structure to determine whether the interaction between the first software component and an interface of the set of interfaces violates any invariants associated with the interface and their associated contexts; and initiating an error control procedure including performing a known behavior in response to the interaction if it is determined that the interaction violates any invariants associated with the interface and their associated contexts. ### Claim 2 (depends on 1) The computer implemented method of claim 1 wherein performing the known behavior includes providing a predetermined value to the first software component. ### Claim 3 (depends on 1) The computer implemented method of claim 1 wherein performing the known behavior includes performing a confirmation routine to confirm that the interaction with the second software component should be performed. ### Claim 4 (depends on 3) The computer implemented method of claim 3 wherein performing the confirmation routine includes requesting a confirmation from a user of the first software component. ### Claim 5 (depends on 1) The computer implemented method of claim 1 wherein identifying the invariants includes identifying invariants of parameter values of interactions. ### Claim 6 (depends on 1) The computer implemented method of claim 1 wherein identifying the invariants includes identifying invariants associated with a plurality of contexts of the interactions. ### Claim 7 (depends on 6) The computer implemented method of claim 6 wherein the formed data structure includes an association of each interface and a context of an interaction with said interface with the invariants associated with said interface and context. ### Claim 8 (depends on 7) The computer implemented method of claim 7 wherein the context of an interaction comprises a procedure call sequence. ### Claim 9 (depends on 7) The computer implemented method of claim 7 wherein the data structure represents, for each interface, a tree structure for a set of call sequences leading to the interaction with the interface, each leaf of the tree corresponding to a different context. ### Claim 10 (depends on 1) The computer implemented method of claim 1 where invariants associated with an interface characterize constraints satisfied by parameters used in the interactions with said interface. ### Claim 11 (depends on 10) The computer implemented method of claim 10 wherein the constraints include at least a constraint chosen from the set of: equality of a parameter value with a constant; equality of two parameter values; and membership of a parameter value in a set of values. ### Claim 12 (depends on 11) The computer implemented method of claim 11 wherein the constraints include a constraint satisfied by a function of a parameter value. ### Claim 13 (depends on 12) The computer implemented method of claim 12 wherein the function of the parameter value includes at least one of an extension, directory, and directory path of a parameter value representing a pathname in a file structure. ### Claim 14 (depends on 1) The computer implemented method of claim 1 wherein the first software component comprises a program component and the second software component comprises an operating system component, and the set of interfaces comprise interfaces to services provided by the operating system. ### Claim 15 (depends on 1) The computer implemented method of claim 1 wherein the first software component comprises a program component and the second software component comprises a software library component, and the set of interfaces comprise interfaces to library routines provided by the library component. ### Claim 16 (depends on 1) The computer implemented method of claim 1 wherein the first software component and the second software component comprise software components of a distributed system, and the interactions between the components comprise messages passed between the components. ### Claim 17 A computer implemented method for automatically patching errors in a software system that includes a first software component and a second software component including a set of interfaces, at least some of the interfaces each having a set of parameters, the method comprising: accepting a data structure including an association of each interface in the set of interfaces with invariants associated with that interface; and for each interaction of a plurality of interactions between the first software component and the set of interfaces of the second software component: using the data structure to determine whether the interaction between the first software component and an interface of the set of interfaces violates any invariants associated with the interface and their associated contexts; and initiating an error control procedure including performing a known behavior in response to the interaction if it is determined that the interaction violates any invariants associated with the interface and their associated contexts. ### Claim 18 A computer implemented method for automatically patching errors in a plurality of software systems, each including a first software component and a second software component including a set of interfaces, at least some of the interfaces each having a set of parameters, the method comprising: monitoring a first set of executions of each of the software systems including: monitoring a plurality of error-free interactions between the first software component and the set of interfaces of the second software component; identifying invariants from the plurality of error-free interactions, each invariant being associated with one or more contexts; forming a data structure including an association of each interface in the set of interfaces with invariants associated with that interface; and merging the data structures formed by each of the software systems into a central data structure monitoring a second set of executions of each of the plurality of software systems including: accepting the central data structure; for each interaction of a plurality of interactions between the first software component and the set of interfaces of the second software component: using the data structure to determine whether the interaction between the first software component and an interface of the set of interfaces violates any invariants associated with the interface and their associated contexts; and initiating an error control procedure including performing a known behavior in response to the interaction if it is determined that the interaction violates any invariants associated with the interface and their associated contexts.