Automatic correction of program logic
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.
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.
2. The computer implemented method of claim 1 wherein performing the known behavior includes providing a predetermined value to the first software component.
3. 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.
4. The computer implemented method of claim 3 wherein performing the confirmation routine includes requesting a confirmation from a user of the first software component.
5. The computer implemented method of claim 1 wherein identifying the invariants includes identifying invariants of parameter values of interactions.
6. The computer implemented method of claim 1 wherein identifying the invariants includes identifying invariants associated with a plurality of contexts of the interactions.
7. 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.
8. The computer implemented method of claim 7 wherein the context of an interaction comprises a procedure call sequence.
9. 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.
10. 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.
11. 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.
12. The computer implemented method of claim 11 wherein the constraints include a constraint satisfied by a function of a parameter value.
13. 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.
14. 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.
15. 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.
16. 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.
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.
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.