US5790778A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Simulated program execution error detection method and apparatus
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1996-08-07
•
Granted: 1998-08-04
•
Expires: 2016-08-07
Abstract
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.
Inventors
- 👤 William R. Bush
- 👤 Jonathan D. Pincus
- 👤 Richard E. Wilbur
- 👤 Debby Majors-Degnan
- 👤 David Jon Sielaff
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-31 03:01
CPC Classifications
G; G06; G06F; G06F11/00; G06F11/36; G06F11/3604; G06F11/3612
Claims Analysis
Total Claims: 45
Claim 1
Independent Claim
120 words
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.
Claim 2
Independent Claim
120 words
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.
Claim 3
Dependent Claim
18 words
A method as in claim 1 wherein said representation of said computer program is an internal format structure.
Claim 4
Dependent Claim
56 words
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.
Claim 5
Dependent Claim
27 words
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.
Claim 6
Dependent Claim
33 words
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.
Claim 7
Dependent Claim
33 words
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.
Claim 8
Dependent Claim
52 words
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.
Claim 9
Dependent Claim
73 words
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.
Claim 10
Dependent Claim
34 words
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.
Claim 11
Dependent Claim
33 words
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.
Claim 12
Dependent Claim
91 words
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.
Claim 13
Dependent Claim
22 words
A method as in claim 1 wherein said invalid condition in said first structural memory model signals an uninitialized piece of memory.
Claim 14
Dependent Claim
20 words
A method as in claim 1 wherein said invalid condition in said first structural memory model signals an invalid pointer.
Claim 15
Dependent Claim
20 words
A method as in claim 1 wherein said invalid condition in said first structural memory model signals a zero divisor.
Claim 16
Dependent Claim
24 words
A method as in claim 1 further comprising: logging information describing said manipulating said first structural memory model to produce a first logged data.
Claim 17
Dependent Claim
41 words
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.
Claim 18
Dependent Claim
25 words
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.
Claim 19
Dependent Claim
148 words
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.
Claim 20
Dependent Claim
14 words
A method as in claim 18 wherein said computer program is a first function.
Claim 21
Dependent Claim
44 words
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.
Claim 22
Dependent Claim
45 words
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.
Claim 23
Dependent Claim
35 words
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.
Claim 24
Independent Claim
114 words
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.
Claim 25
Independent Claim
114 words
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.
Claim 26
Dependent Claim
24 words
A method as in claim 23 wherein said automodelling said function further comprises: scanning said logged data to identify an extern of said function.
Claim 27
Independent Claim
114 words
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.
Claim 28
Independent Claim
114 words
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.
Claim 29
Dependent Claim
18 words
A method as in claim 25 wherein said representation of said computer program is an internal format structure.
Claim 30
Dependent Claim
74 words
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.
Claim 31
Dependent Claim
34 words
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.
Claim 32
Dependent Claim
34 words
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.
Claim 33
Dependent Claim
91 words
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.
Claim 34
Dependent Claim
22 words
A method as in claim 25 wherein said invalid condition in said first structural memory model signals an uninitialized piece of memory.
Claim 35
Dependent Claim
20 words
A method as in claim 25 wherein said invalid condition in said first structural memory model signals an invalid pointer.
Claim 36
Dependent Claim
20 words
A method as in claim 25 wherein said invalid condition in said first structural memory model signals a zero divisor.
Claim 37
Dependent Claim
24 words
A method as in claim 25 further comprising: logging information describing said manipulating said first structural memory model to produce a first logged data.
Claim 38
Dependent Claim
43 words
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.
Claim 39
Dependent Claim
46 words
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.
Claim 40
Dependent Claim
27 words
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.
Claim 41
Dependent Claim
152 words
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.
Claim 42
Dependent Claim
45 words
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.
Claim 43
Dependent Claim
99 words
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.
Claim 44
Dependent Claim
99 words
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.
Claim 45
Dependent Claim
26 words
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.
References Cited (Backward Citations)
US5481705A
Cited
US5446900A
Cited
US5325533A
Cited
US5574854A
Cited
US5590329A
Cited
US5583988A
Cited
US5687375A
Cited
US5581696A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-08-03 | 2002-02-02 | 2002-08-04 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-08-03 | 2006-02-02 | 2006-08-04 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-08-03 | 2010-02-02 | 2010-08-04 | $7700.00 | Window Closed / Lapsed |