Simulated program execution error detection method and apparatus

• US 5,790,778 A
• Filed: 08/07/1996
• Issued: 08/04/1998
• Est. Priority Date: 08/07/1996
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Intrinsa Corp. (Microsoft Corporation)
• Inventors: Wilbur, Richard E., Majors-Degnan, Debby, Bush, William R., Pincus, Jonathan D., Sielaff, David Jon
• Primary Examiner(s): Beausoliel, Jr., Robert W.
• Assistant Examiner(s): Wright, Norman M.
• Application Number:
  US08/694,470
• Time in Patent Office: 727 Days
• Field of Search: 395/183.14, 395/183.13, 395/183.04, 395/183.05, 395/183.09, 395/183.15, 395/183.01, 395/183.02, 395/701, 395/704, 395/183.1
• US Class Current: 714/38.1
• CPC Class Codes: G06F 11/3612 by runtime analysis performance monitoring G06F11/3466

Abstract

A computer program error detection system that detects errors in a computer program by simulating execution of program statements. An internal format structure is retrieved along with a list of all functions defined by the computer program. The internal format structure is analyzed to determine all function calls and the function call ordering. External behavior models corresponding to the discovered function calls are retrieved and stored in a model table. One or more control flow paths are traversed through the computer program. For each path traversed, a structural memory model is maintained to represent the effect of the simulated execution of statements along the control flow path. A statement is simulated by executing a built in model of the operation. A function call is emulated by executing an external behavior model corresponding to the called function. Execution of an external behavior model causes the structural model memory to be updated to reflect execution of the called function. Information describing the manipulation of the memory model is logged for automodelling purposes. Invalid conditions in the structural memory model are detected and reported. The information logged for automodelling purposes is scanned after analysis of each path to build an outcome for that path. After individual path analysis completes, the different outcomes are processed, duplicates are removed, and an external behavior model representing the computer program under analysis is generated.

Claims

1. A method for simulating execution of a computer program to detect programming errors in said computer program, said computer program containing at least one function, said function containing one or more statements, said method comprising:

retrieving a representation of said computer program;

traversing a first control flow path through said function wherein said first control flow path comprises a first sequence of said statements, wherein said traversing comprises;

maintaining a first structural memory model for said function over said first control flow path;

manipulating said first structural memory model to simulate execution of said first sequence of said statements;

detecting an invalid condition in said first structural memory model; and

reporting said invalid condition in said first structural memory model.

2. A method as in claim 1 wherein said representation of said computer program is an internal format structure.

3. A method as in claim 1 further comprising:

identifying all said functions defined by said computer program;

ordering a list of said functions defined by said computer program based on a function call ordering; and

scheduling an analysis of said computer program based upon said ordering a list of said functions defined by said computer program.

4. A method as in claim 1 further comprising:

accepting a configuration control command; and

modifying an analysis of said computer program based upon said configuration control command.

5. A method as in claim 4 further comprising:

accepting a second configuration control command for a specified function; and

modifying an analysis of said specified function based upon said second configuration control command.

6. A method as in claim 5 further comprising:

accepting a third configuration control command for a specified statement; and

modifying an analysis of said specified statement based upon said third configuration control command.

7. A method as in claim 6 wherein said reporting said invalid condition in said first sturctural memory model further comprises:

determining that one of said configuration control command, said second configuration control command and said third configuration control command orders suppression of said invalid condition; and

suppressing reporting of said invalid condition.

8. A method as in claim 1 wherein said traversing a first control flow path through said function further comprises:

identifying an unresolved choice point in said first control flow path;

representing said unresolved choice point by a node in a tree, wherein said node contains an edge for each potential resolution of said choice point; and

resolving said unresolved choice point by randomly choosing a first unselected edge to determine a first choice.

9. A method as in claim 8 wherein said resolving said unresolved choice point further comprises:

maintaining a history of said first choice; and

randomly choosing a second unselected edge to determine a second choice.

10. A method as in claim 8 wherein said traversing a first control flow path through said function further comprises:

updating said first structural memory model to reflect said resolving said unresolved choice point.

11. A method as in claim 1 further comprising:

analyzing said representation of said computer program to identify a function call;

locating an external behavior model of a called function corresponding to said function call;

retrieving said external behavior model of a called function corresponding to said function call; and

, wherein said manipulating said first structural memory model to simulate execution of said first sequence of said statements further comprises;

emulating execution of said function call through execution of said external behavior model of a called function corresponding to said function call.

12. A method as in claim 1 wherein said invalid condition in said first structural memory model signals an uninitialized piece of memory.

13. A method as in claim 1 wherein said invalid condition in said first structural memory model signals an invalid pointer.

14. A method as in claim 1 wherein said invalid condition in said first structural memory model signals a zero divisor.

15. A method as in claim 1 further comprising:

logging information describing said manipulating said first structural memory model to produce a first logged data.

16. A method as in claim 15 further comprising automodelling said function to generate an external behavior model corresponding to said function, wherein said automodelling comprises:

scanning said first logged data to produce a first outcome for said first control flow path.

17. A method as in claim 16 wherein said automodelling said function further comprises:

scanning said first logged data to identify an extern of said function.

18. A method as in claim 17 further comprising:

traversing a second control flow path through said function, wherein said second control flow path comprises a second sequence of said statements, wherein said traversing comprises;

maintaining a second structural memory model for said function over said second control flow path;

manipulating said second structural memory model to simulate execution of said second sequence of said statements;

logging information describing said manipulating said second structural memory model to produce a second logged data; and

wherein, automodelling said function to generate an external behavior model corresponding to said function further comprises;

scanning said second logged data to produce a second outcome for said second control flow path;

eliminating duplicates among said first outcome and said second outcome to generate one or more remaining outcomes; and

packaging said remaining outcomes and said extern into said external behavior model corresponding to said function.

19. A method as in claim 18 wherein said computer program is a first function.

20. A method as in claim 19 wherein said first function is part of a second computer program and wherein said external behavior model generated by said automodelling said function is used to emulate said first function in an analysis of said second computer program.

21. A method as in claim 16 wherein said automodelling said function further comprises:

ordering a symbol table, wherein said symbol table comprises one or more links to said first structural memory model prior to said logging information describing said manipulating said first structural memory model.

22. A method as in claim 1 wherein said reporting said invalid condition in said first structural memory model further comprises:

determining that said invalid condition is a duplicate; and

suppressing reporting of said invalid condition.

23. A method for simulating execution of a computer program to detect programming errors in said computer program, said computer program containing at least one function, said function containing zero statements, said method comprising:

retrieving a representation of said computer program;

traversing a control flow path through said function wherein said control flow path comprises zero statements, wherein said traversing comprises;

maintaining a structural memory model for said function over said control flow path;

logging information describing said function to produce a logged data; and

automodelling said function to generate an external behavior model corresponding to said function, wherein said automodelling comprises;

scanning said logged data to produce an outcome for said control flow path.

24. A method as in claim 23 wherein said automodelling said function further comprises:

scanning said logged data to identify an extern of said function.

25. A method for simulating execution of a computer program to detect programming errors in said computer program, said computer program containing one or more statements, said method comprising:

retrieving a representation of said computer program;

traversing a first control flow path through said computer program wherein said first control flow path comprises a first sequence of said statements, wherein said traversing comprises;

maintaining a first structural memory model for said computer program over said first control flow path;

manipulating said first structural memory model to simulate execution of said first sequence of said statements;

detecting invalid conditions in said first structural memory model; and

reporting said invalid conditions in said first structural memory model.

26. A method as in claim 25 wherein said representation of said computer program is an internal format structure.

27. A method as in claim 25 wherein said traversing a first control flow path through said computer program further comprises:

identifying an unresolved choice point in said first control flow path;

representing said unresolved choice point by a node in a tree, wherein said node contains an edge for each potential resolution of said choice point; and

resolving said unresolved choice point by randomly choosing a first unselected edge to determine a first choice.

28. A method as in claim 27 wherein said resolving said unresolved choice point further comprises:

maintaining a history of said first choice; and

randomly choosing a second unselected edge to determine a second choice.

29. A method as in claim 27 wherein said traversing a first control flow path through said computer program further comprises:

updating said first structural memory model to reflect said resolving said unresolved choice point.

30. A method as in claim 25 further comprising:

analyzing said representation of said computer program to identify a function call;

locating an external behavior model of a called function corresponding to said function call;

retrieving said external behavior model of a called function corresponding to said function call; and

, wherein said manipulating said first structural memory model to simulate execution of said first sequence of said statements further comprises;

emulating execution of said function call through execution of said external behavior model of a called function corresponding to said function call.

31. A method as in claim 25 wherein said invalid condition in said first structural memory model signals an uninitialized piece of memory.

32. A method as in claim 25 wherein said invalid condition in said first structural memory model signals an invalid pointer.

33. A method as in claim 25 wherein said invalid condition in said first structural memory model signals a zero divisor.

34. A method as in claim 25 further comprising:

logging information describing said manipulating said first structural memory model to produce a first logged data.

35. A method as in claim 34 further comprising automodelling said computer program to generate an external behavior model corresponding to said computer program, wherein said automodelling comprises:

scanning said first logged data to produce a first outcome for said first control flow path.

36. A method as in claim 35 wherein said automodelling said computer program further comprises:

ordering a symbol table, wherein said symbol table comprises one or more links to said first structural memory model prior to said logging information describing said manipulating said first structural memory model.

37. A method as in claim 35 wherein said automodelling said computer program further comprises:

scanning said first logged data to identify an extern of said computer program.

38. A method as in claim 37 further comprising:

traversing a second control flow path through said computer program wherein said second control flow path comprises a second sequence of said statements, wherein said traversing comprises;

maintaining a second structural memory model for said computer program over said second control flow path;

manipulating said second structural memory model to simulate execution of said second sequence of said statements;

logging information describing said manipulating said second structural memory model to produce a second logged data; and

wherein, automodelling said computer program to generate an external behavior model corresponding to said computer program further comprises;

scanning said second logged data to produce a second outcome for said second control flow path;

eliminating duplicates among said first outcome and said second outcome to generate one or more remaining outcomes;

packaging said remaining outcomes and said extern into said external behavior model corresponding to said computer program.

39. A method as in claim 25 wherein said computer program is part of a second computer program and wherein said external behavior model generated by said automodelling said computer program is used to emulate said computer program in an analysis of said second computer program.

40. An error detection processor for detecting errors in a computer program, said computer program comprising one or more statements, said error detection processor comprising:

a structural memory model which represents the behavior of said computer program upon a simulation;

an analysis engine which traverses a control flow path through said computer program, wherein said control flow path is comprised of a sequence of said statements;

a statement unit which simulates the effect of said statements in the said control flow path; and

an error generation unit which reports invalid conditions detected within said structural memory model after said simulation.

41. The error detection processor of claim 40 further comprising:

an automodeller which generates an external behavior model to represent the visible behavior of said computer program.