System and Method for Reproducing Device Program Execution

• US 20110078666A1
• Filed: 05/26/2010
• Published: 03/31/2011
• Est. Priority Date: 05/26/2009
• Status: Abandoned Application

• Current Assignee: University of California
• Original Assignee: University of California
• Inventors: Altekar, Gautam
• Application Number:
  US12/788,233
• Publication Number:
  US 20110078666A1
• Time in Patent Office: Days
• US Class Current: 717/131
• CPC Class Codes: G06F 11/3636 by tracing the execution of the program

Abstract

Provided are a system and method for precisely reproducing a device program execution, such as reproducing a software program executed on a computer for example. The method provides a solution to a class of diagnosis methods known as “record/replay” or “deterministic replay”, where information related to a program execution is recorded for later replay, often for diagnostic purposes to reproduce errors in device function such as software bugs and other anomalous behavior. In contrast with other methods in this class, the invention provides a method for low-overhead recording and high-precision replay of programs possibly utilizing multiple processor cores, and also low-overhead recording and high-precision replay of programs that perform input and/or output operations at high data rates, and further provides a system and method provide a solution with substantially few hardware requirements beyond that of a modern electronic device, such as a personal computer, or a laptop computer, or other electronic device controlled by one or more processors. Taken together, these features enable efficient and cost-effective execution replay of modern multiprocessor and networked software.

Claims

1. A method for Data Center Replay (DCR), comprising:

running a program;

capturing data from a non-deterministic date source;

substituting the captured data into subsequent re-executions of the program;

re-running the program with the captured data; and

analyzing the re-running of the program.

2. A method according to claim 1, wherein the non-deterministic data source is a keyboard.

3. A method according to claim 1, wherein the analyzing the rerunning of the program includes analyzing the operations of the program with tracing tools.

4. A method according to claim 1, wherein the analyzing the rerunning of the program includes analyzing the operations of the program with race detection.

5. A method according to claim 1, wherein the analyzing the rerunning of the program includes analyzing the operations of the program with memory leak detection.

6. A method according to claim 1, wherein the analyzing the rerunning of the program includes analyzing the operations of the program with global predicates.

7. A method according to claim 1, wherein the analyzing the rerunning of the program includes analyzing the operations of the program with casualty tracing.

8. A method for reproducing electronic program execution, comprising:

running a program;

collecting output data while the program is running;

performing an output deterministic execution;

searching a predetermined space of potential executions of the program; and

calculating inferences from the collected output data to find operational errors in the program.

9. A method according to claim 8, wherein collecting output data includes collecting output data clues indicative of the operation of the program being run.

10. A method according to claim 8, wherein searching a space of potential executions includes searching the collected output data using symbolic reasoning to infer values of non-deterministic access values.

11. A system for reproducing electronic program execution, comprising:

a run module configured to run a program;

a collection module configured to collect data clues during the running of the program; and

an execution program configured to run the program in an output deterministic execution to determine operational errors in the program based on the data clues collected when the program is run in the run module.

12. A system according to claim 11, wherein collection module is configured to collect output data clues indicative of the operation of the program being run.

13. A system according to claim 11, wherein the execution module is configured to search a space of potential executions includes searching the collected output data using symbolic reasoning to infer values of non-deterministic access values.

14. A method for Data Center Replay (DCR), comprising:

running a collection of programs;

observing the behaviors of the programs while they are running; and

analyzing programs'"'"' executions that exhibit the observed behaviors

15. A method according to claim 14, wherein running a collection of programs includes:

running individual programs on distributed CPUs;

wherein distributed CPUs may be on the same machine or spread across multiple machines

wherein programs may communicate through shared memory if on the same machine or the network if on different machines

16. A method according to claim 14, wherein observing program behaviors includes:

collecting the values of program reads and writes from/to select inter-cpu communication channels;

wherein inter-cpu channels includes shared memory, console, network (e.g., sockets), inter-process (e.g., pipes), and file channels

wherein select inter-cpu channels include those that operate at low data rates, or those designated by the user as having low data rates

wherein collecting includes recording the data values to reliable storage

17. A method according to claim 14, wherein analyzing execution(s) consistent with the observed behaviors comprises of:

formulating queries for execution state of interest;

wherein formulating queries includes translating debugger state inspection commands to queries

wherein query specifies portion of program execution state to observe

wherein query includes those queries automatically generated by analysis tools as well as those generated by a person

providing values for execution state specified in the query; and

wherein values are provided by reconstructing execution state consistent with the observed behaviors

wherein reconstructing state values comprises of searching a predetermined space of potential programs'"'"' executions for one that exhibits the observed behavior; and

wherein searching includes using symbolic reasoning to infer program state of target execution

wherein the symbolic reasoning includes reasoning done on demand in response to queries

wherein the on demand reasoning includes doing only the work necessary to answer queries

wherein the symbolic reasoning includes reasoning done with the aid of an automated symbolic reasoning program (e.g., constraint solver or theorem prover)

wherein the predetermined space of potential executions includes only those executions that exhibit the observed behaviors

extracting specified state values.

inspecting returned execution state;

wherein inspecting includes checking return state for program invariant violations, data races, memory leaks, or causality anomalies.

18. A method for reproducing electronic multi-program execution, comprising:

running a collection of programs;

observing behaviors of the programs while they are running;

reconstructing programs'"'"' executions that exhibit the original executions'"'"' outputs; and

analyzing the reconstructed executions.

19. A method according to claim 18, wherein running a collection of programs includes:

running individual programs on different CPUs on the same machine

20. A method according to claim 18, wherein observing outputs and other program behaviors comprises of:

collecting the values of program outputs (i.e., writes to user-visible channels); and

wherein user-visible channels includes the console, network (e.g., sockets), inter-process (e.g., pipes), and file channels

optionally includes collecting the values of program reads from inter-cpu channels

wherein inter-cpu channels include shared-memory, keyboard, network, pipe, file, and device channels

21. A method according to claim 18, wherein reconstructing program executions comprises of:

searching a predetermined space of potential programs'"'"' executions for one that produces the observed output; and

wherein searching includes using symbolic reasoning to infer values of non-deterministic accesses of target execution

wherein the symbolic reasoning includes reasoning done with the aid of an automated symbolic reasoning program (e.g., constraint solver or theorem prover)

wherein the non-deterministic accesses include those of racing instruction accesses

wherein the predetermined space of potential executions includes only those executions likely to exhibit the observed output behaviors

wherein executions likely to exhibit the observed output behaviors includes those executions that exhibit all observed behaviors

extracting essential state for the future reproduction of the reconstructed execution;

wherein essential state includes the inferred values of non-deterministic accesses

22. A method according to claim 18, where the analyzing of the reconstructed program'"'"'s behaviors comprises of:

re-running the reconstructed executions; and

analyzing the re-run with tracing tools;

wherein tracing tools include debuggers, race detectors, memory leak detectors, and causality tracers.