Software variation for robustness through randomized execution contexts

• US 20070234296A1
• Filed: 03/31/2006
• Published: 10/04/2007
• Est. Priority Date: 03/31/2006
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zorn, Benjamin, Berger, Emery
• Application Number:
  US11/395,631
• Publication Number:
  US 20070234296A1
• Time in Patent Office: Days
• US Class Current: 717/124
• CPC Class Codes: G06F 11/008 Reliability or availability analysis
• CPC Class Codes: G06F 11/0796 Safety measures, i.e. ensuring safe condition in the event of error, e.g. for controlling element
• CPC Class Codes: G06F 11/1494 N-modular type

Abstract

Improved robustness of software program executions is achieved via randomization of their execution contexts. For instance, errors related to runtime allocation of memory on the heap can be probabilistically addressed by generating an approximation of the infinite heap and using a randomized memory manager to allocate memory on the heap. In addition to stand alone randomization, several replicas of a software program are executed, each with a memory manager configured with different randomization seeds for randomly allocating memory on an approximation of an infinite heap. Outputs of correctly executing instances of the replicas are determined by accepting the output that at least two of the replicas agree upon.

Claims

1. A computer-implemented method for improving the robustness of a software program execution, the method comprising:

initiating execution of the program;

determining an execution context for the program that is error tolerant; and

allowing the program to execute according to the error tolerant execution context.

2. The method of claim 1 wherein determining the execution context that is error tolerant comprises configuring an error tolerant stack layout.

3. The method of claim 1 wherein determining the execution context that is error tolerant comprises configuring an error tolerant runtime heap layout.

4. The method of claim 1 wherein determining the execution context for the program that is error tolerant comprises:

initiating execution of at least one replica of the program;

generating correspondingly randomized execution contexts for the program and each of the at least one replica of the program;

periodically comparing the outputs of the program and at least one replica of the program; and

accepting the outputs that agree as outputs of a correctly executing program.

5. The method of claim 4 wherein periodically comparing the outputs of the program and the at least one replica comprises comparing the outputs during input/output operations.

6. A computer implemented method for randomized management of runtime heap-based memory associated with an executing software program, the method comprising:

receiving a call related to managing runtime heap-based memory; and

handling the call in accordance with a runtime system configured to manage a heap which is an approximation of an infinite heap.

7. The method of claim 6 further comprising, generating the approximation of the infinite heap.

8. The method of claim 7 wherein generating the approximation of the infinite heap comprises:

determining a maximum heap size required by the executing program assuming perfect packing of the heap; and

generating the approximation of the infinite heap as a multiple of the maximum heap size assuming perfect packing.

9. The method of claim 8 wherein the multiple is at least two.

10. The method of claim 8 wherein randomized management of the runtime heap-based memory comprises randomized allocation of memory space on the approximation of the infinite heap to objects associated with the software program.

11. The method of claim 10 wherein the randomized allocation comprises:

generating a random number that corresponds to some address associated with the approximation of the infinite heap;

on a free list comprising a listing of addresses indicative of unallocated locations on the approximation of the infinite heap, identifying the randomly generated address; and

if memory space associated with the location indicated by the identified randomly generated address is sufficient for the object, allocating the location to the object.

12. The method of claim 11 further comprising repeating the generating step, if the location indicated by the randomly generated address is insufficient for the object.

13. The method of claim 8 wherein generating the approximation of the infinite heap as a multiple of the maximum heap size assuming perfect packing comprises:

subdividing the approximation of the infinite heap into a plurality of page sets, each page set comprising memory elements of a specific size class which are reserved for allocation of objects of the corresponding size.

14. The method of claim 13 wherein randomized management of the heap-based memory comprises randomized allocation of memory space to objects on the approximation of the infinite heap, further wherein randomized allocation comprises:

mapping memory allocation requests to a size class;

generating a random number between zero and a current number of memory elements in the page set corresponding to the size class;

mapping the random number to a specific location; and

allocating the object to a free location on the page set after the location associated with the random number.

15. A computer implemented method for improving robustness of a software program execution, the method comprising:

initiating execution of a plurality of replicas of the software program;

generating approximations of infinite heaps correspondingly associated with each of the replicas, wherein each replica has associated therewith a different randomization seed for randomizing allocation of the memory on their respective approximation of the infinite heap;

periodically comparing data outputs of at least some of the replicas; and

accepting as an output of correctly executing programs, the output agreed upon by at least two of the plurality of replicas.

16. The method of claim 15 wherein generating the approximations of the infinite heap comprises:

determining a maximum heap size required by the executing program assuming perfect packing of the heap; and

generating the approximation of the infinite heap by expanding the maximum heap size assuming perfect packing by an expansion factor that is a multiple of the maximum heap size assuming perfect packing.

17. The method of claim 16 wherein a number of replicas and the expansion factors are received as input parameters to a function call for performing the method of claim 16.

18. The method of claim 15 further comprising terminating execution of those replicas whose outputs do not agree with any of the other replicas and starting execution of another replica in their place with a different randomization seed.

19. The method of claim 15 further comprising filling locations within each of the approximations of the infinite heap associated with the replicas with values that are randomly generated based on their respective randomization seeds.

20. The method of claim 15 wherein at least some of the replicas are executed on different processors.

21. The runtime system for heap-based memory management related to execution of a software program, the system comprising a memory manager programmed to be operable for:

generating a heap to be associated with the software program that approximates infinite heap semantics;

receiving requests for allocating heap memory from the program; and

in response to receiving the requests, allocating randomly selected locations on the approximated infinite heap.

22. The runtime system of claim 21 wherein generating the heap that approximates infinite heap semantics comprises generating a heap that is a multiple of a heap size required for the program assuming perfect packing.

23. The runtime system of claim 21 further operable for:

initiating execution of a plurality of replicas of the software program;

generating heaps that approximate infinite heap semantics to be correspondingly associated with each of the replicas, wherein each replica has associated therewith a different randomization seed for randomizing allocation of the memory on their respective approximation of the infinite heap;

receiving requests for allocating heap memory from the program;

in response to the received requests, allocating randomly selected locations on the approximated infinite heap;

periodically comparing data outputs of at least some of the replicas; and

accepting as an output of correctly executing programs, the output agreed upon by at least two of the plurality of replicas.

24. The runtime system of claim 23 further comprising filling locations within each of the executing program replicas with values randomly generated based on their respective randomization seeds.

25. At least one computer-readable medium useful in conjunction with a computer, the computer comprising at least one processor and memory, the computer-readable medium having stored thereon computer executable instructions for improving robustness of a software program execution method, the method comprising:

initiating execution of a plurality of replicas of the software program;

generating heaps correspondingly associated with each of the replicas having semantics that are approximations of those of an infinite heap,

filling the heaps of at least some of the replicas with random values generated using a different randomization seed;

in response to requests for memory allocation by the replicas, allocating memory on the respective approximations of the infinite heap;

periodically comparing data outputs of at least some of the replicas; and

accepting as an output of correctly executing programs, the output agreed upon by at least two of the plurality of replicas.