Patent US5694539A successfully refreshed from Google Patents.
US5694539A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Computer process resource modelling method and apparatus
Assignee: LIGHTHOUSE DEVELOPMENT Inc
•
Filing: 1994-08-10
•
Granted: 1997-12-02
•
Expires: 2014-08-10
Abstract
Abstract An error detection mechanism for detecting programing errors in a computer program. A component of the computer program, e.g., a procedure or function of the computer program, is analyzed to determine the effect of the component on resources used by the computer program. A component is analyzed by traversing the computer instructions, i.e., statements, of the component and tracking the state of resources used by the component as affected by the statements of the component. Each resource has a prescribed behavior represented by a number of states and transition between states. Violations in the prescribed behavior of a resource resulting from an emulated execution of the statements of the component are detected and reported as programming errors. Resources used by two or more components are modelled by modelling externals of the components. The effect of execution of a component on externals and resources of the component is determined by traversing one or more possible control flow paths through the component and tracking the use of each external and resource by each statement of each control flow path. Once the effect of execution of a component on externals and resources of the component is determined, a model of the component is created and used to model externals and resources of other components which invoke the modelled component.
Inventors
- 👤 Matthew A. Haley
- 👤 Jonathan D. Pincus
- 👤 William R. Bush
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-07 14:30
CPC Classifications
G; G06; G06F; G06F11/00; G06F11/36; G06F11/362; G06F11/366
Claims Analysis
Total Claims: 75
Claim 1
Independent Claim
118 words
A method for detecting programming errors in a component of a computer program, the component comprising one or more statements, the method comprising: (a) defining one or more valid states for a resource which has a resource state; (b) traversing a control flow path through the one or more statements; (c) for each of the one or more statements along the control flow path, performing the following steps: (i) evaluating an effect of the statement on the resource state of the resource; and (ii) modelling a transition from the resource state to a new resource state of the resource in accordance with the effect; and (d) detecting that the new state is not one of the valid states.
Claim 2
Independent Claim
118 words
A method for detecting programming errors in a component of a computer program, the component comprising one or more statements, the method comprising: (a) defining one or more valid states for a resource which has a resource state; (b) traversing a control flow path through the one or more statements; (c) for each of the one or more statements along the control flow path, performing the following steps: (i) evaluating an effect of the statement on the resource state of the resource; and (ii) modelling a transition from the resource state to a new resource state of the resource in accordance with the effect; and (d) detecting that the new state is not one of the valid states.
Claim 3
Dependent Claim
11 words
The method of claim 1 wherein the component is a function.
Claim 4
Dependent Claim
47 words
The method of claim 1 wherein the step of traversing comprises: determining that a selected statement of the one or more statements determines a portion of the control flow path according to a value of a predicate; and evaluating the predicate to determine the control flow path.
Claim 5
Dependent Claim
30 words
The method of claim 3 wherein the step of evaluating the predicate comprises: determining that the value of the predicate is unknown; and assigning to the predicate an assumed value.
Claim 6
Dependent Claim
26 words
The method of claim 4 wherein the step of evaluating the predicate further comprises: inferring from the assumed value information regarding the state of the resource.
Claim 7
Dependent Claim
29 words
The method of claim 4 wherein the step of evaluating the predicate further comprises: inferring from the assumed value respective values of one or more operands of the predicate.
Claim 8
Dependent Claim
84 words
The method of claim 6 wherein the step of traversing further comprises: determining that a second selected statement of the one or more statements determines a second portion of the control flow path according to a second value of a second predicate, which comprises one or more of the operands of the first-mentioned predicate; and evaluating the second predicate to determine the second portion of the control flow path using the inferred respective values of the one or more operands of the first predicate.
Claim 9
Dependent Claim
51 words
The method of claim 1 wherein step (c)(i) comprises: determining whether the statement is a call to a called component; if the statement is a call to a called component, emulating execution of the called component to evaluate the effect of the called component on the resource state of the resource.
Claim 10
Dependent Claim
55 words
The method of claim 8 wherein the step of emulating execution of the called component comprises: determining that the resource is associated with an external of the called component; and determining from a model of the called component the effect of execution of the called component on the resource, which is associated with the external.
Claim 11
Dependent Claim
22 words
The method of claim 1 further comprising: reporting to a user that the resource state is not one of the valid states.
Claim 12
Dependent Claim
35 words
The method of claim 1 further comprising: identifying to a user the statement whose effect on the resource state causes a transition to a new resource state which is not one of the valid states.
Claim 13
Independent Claim
140 words
A method for detecting programming errors in a component of a computer program, the component comprising one or more statements, the method comprising: (a) defining one or more valid states for a resource which has a resource state; (b) defining one or more valid state transitions, each state transition being from a first of the valid states to a second of the valid states; and (c) traversing a control flow path through the one or more statements; (d) for each of the one or more statements along the control flow path, performing the following steps: (i) evaluating an effect of the statement on the resource state of the resource; and (ii) modelling a change in the resource state of the resource in accordance with the effect; and (e) detecting that the change is not one of the valid state transitions.
Claim 14
Independent Claim
140 words
A method for detecting programming errors in a component of a computer program, the component comprising one or more statements, the method comprising: (a) defining one or more valid states for a resource which has a resource state; (b) defining one or more valid state transitions, each state transition being from a first of the valid states to a second of the valid states; and (c) traversing a control flow path through the one or more statements; (d) for each of the one or more statements along the control flow path, performing the following steps: (i) evaluating an effect of the statement on the resource state of the resource; and (ii) modelling a change in the resource state of the resource in accordance with the effect; and (e) detecting that the change is not one of the valid state transitions.
Claim 15
Dependent Claim
47 words
The method of claim 12 wherein the step of traversing comprises: determining that a selected statement of the one or more statements determines a portion of the control flow path according to a value of a predicate; and evaluating the predicate to determine the control flow path.
Claim 16
Dependent Claim
30 words
The method of claim 13 wherein the step of evaluating the predicate comprises: determining that the value of the predicate is unknown; and assigning to the predicate an assumed value.
Claim 17
Dependent Claim
26 words
The method of claim 14 wherein the step of evaluating the predicate further comprises: inferring from the assumed value information regarding the state of the resource.
Claim 18
Dependent Claim
29 words
The method of claim 14 wherein the step of evaluating the predicate further comprises: inferring from the assumed value respective values of one or more elements of the predicate.
Claim 19
Dependent Claim
84 words
The method of claim 16 wherein the step of traversing further comprises: determining that a second selected statement of the one or more statements determines a second portion of the control flow path according to a second value of a second predicate, which comprises one or more of the elements of the first-mentioned predicate; and evaluating the second predicate to determine the second portion of the control flow path using the inferred respective values of the one or more elements of the first predicate.
Claim 20
Dependent Claim
51 words
The method of claim 12 wherein step (d)(i) comprises: determining whether the statement is a call to a called component; if the statement is a call to a called component, emulating execution of the called component to evaluate the effect of the called component on the resource state of the resource.
Claim 21
Dependent Claim
54 words
The method of claim 18 wherein the step of emulating execution of the called component comprises: determining that the resource is associated with an external of the called component; and determining from a model of the called component the effect of execution of the component on the resource, which is associated with the external.
Claim 22
Dependent Claim
22 words
The method of claim 12 further comprising: reporting to a user that the resource state is not one of the valid states.
Claim 23
Dependent Claim
35 words
The method of claim 12 further comprising: identifying to a user the statement whose effect on the resource state causes a transition to a new resource state which is not one of the valid states.
Claim 24
Independent Claim
122 words
A method for modelling the behavior of a component of a computer program, the component including an external, the method comprising: (a) defining one or more valid states for the external, which has an external state; (b) traversing a control flow path, which comprises one or more statements of the component; (c) for each of the one or more statements, performing the following steps: (i) determining that execution of the statement has an effect on the external state of the external; and (ii) modelling a transition from the external state to a new external state of the external in accordance with the effect; and (d) building a model which represents a collective effect of the statements of the component on the external.
Claim 25
Independent Claim
122 words
A method for modelling the behavior of a component of a computer program, the component including an external, the method comprising: (a) defining one or more valid states for the external, which has an external state; (b) traversing a control flow path, which comprises one or more statements of the component; (c) for each of the one or more statements, performing the following steps: (i) determining that execution of the statement has an effect on the external state of the external; and (ii) modelling a transition from the external state to a new external state of the external in accordance with the effect; and (d) building a model which represents a collective effect of the statements of the component on the external.
Claim 26
Dependent Claim
47 words
The method of claim 22 wherein the step of traversing comprises: determining that a selected statement of the one or more statements determines a portion of the control flow path according to a value of a predicate; and evaluating the predicate to determine the control flow path.
Claim 27
Dependent Claim
30 words
The method of claim 23 wherein the step of evaluating the predicate comprises: determining that the value of the predicate is unknown; and assigning to the predicate an assumed value.
Claim 28
Dependent Claim
26 words
The method of claim 24 wherein the step of evaluating the predicate further comprises: inferring from the assumed value information regarding the state of the resource.
Claim 29
Dependent Claim
29 words
The method of claim 24 wherein the step of evaluating the predicate further comprises: inferring from the assumed value respective values of one or more components of the predicate.
Claim 30
Dependent Claim
84 words
The method of claim 26 wherein the step of traversing further comprises: determining that a second selected statement of the one or more statements determines a second portion of the control flow path according to a second value of a second predicate, which comprises one or more of the elements of the first-mentioned predicate; and evaluating the second predicate to determine the second portion of the control flow path using the inferred respective values of the one or more elements of the first predicate.
Claim 31
Dependent Claim
26 words
The method of claim 24 wherein the step of evaluating the predicate further comprises: inferring from the assumed value information regarding the state of the external.
Claim 32
Dependent Claim
51 words
The method of claim 22 wherein step (c)(i) comprises: determining whether the statement is a call to a called component; if the statement is a call to a called component, emulating execution of the called component to evaluate the effect of the called component on the resource state of the resource.
Claim 33
Dependent Claim
54 words
The method of claim 29 wherein the step of emulating execution of the called component comprises: determining that the resource is associated with an external of the called component; and determining from a model of the called component the effect of execution of the component on the resource, which is associated with the external.
Claim 34
Dependent Claim
102 words
The method of claim 22 further comprising: (e) traversing a second control flow path, which comprises a second collection of one or more statements; (f) for each statement of the second collection of one or more statements, performing the following steps: (i) determining that execution of the statement has an effect on the external state of the external; and (ii) modelling a transition from the external state to a second new external state of the external in accordance with the effect; (g) forming from the first-mentioned new external state and the second new external state a composite external state of the external.
Claim 35
Dependent Claim
49 words
The method of claim 31 wherein the step of traversing comprises: determining that a selected statement of the one or more statements determines a portion of the second control flow path according to a value of a predicate; and evaluating the predicate to determine the second control flow path.
Claim 36
Dependent Claim
30 words
The method of claim 32 wherein the step of evaluating the predicate comprises: determining that the value of the predicate is unknown; and assigning to the predicate an assumed value.
Claim 37
Dependent Claim
26 words
The method of claim 33 wherein the step of evaluating the predicate further comprises: inferring from the assumed value information regarding the state of the resource.
Claim 38
Dependent Claim
29 words
The method of claim 33 wherein the step of evaluating the predicate further comprises: inferring from the assumed value respective values of one or more elements of the predicate.
Claim 39
Dependent Claim
26 words
The method of claim 33 wherein the step of evaluating the predicate further comprises: inferring from the assumed value information regarding the state of the external.
Claim 40
Dependent Claim
84 words
The method of claim 35 wherein the step of traversing further comprises: determining that a second selected statement of the one or more statements determines a second portion of the control flow path according to a second value of a second predicate, which comprises one or more of the elements of the first-mentioned predicate; and evaluating the second predicate to determine the second portion of the control flow path using the inferred respective values of the one or more elements of the first predicate.
Claim 41
Dependent Claim
51 words
The method of claim 31 wherein step (f)(i) comprises: determining whether the statement is a call to a called component; if the statement is a call to a called component, emulating execution of the called component to evaluate the effect of the called component on the resource state of the resource.
Claim 42
Dependent Claim
54 words
The method of claim 38 wherein the step of emulating execution of the called component comprises: determining that the resource is associated with an external of the called component; and determining from a model of the called component the effect of execution of the component on the resource, which is associated with the external.
Claim 43
Dependent Claim
23 words
The method of claim 31 further comprising: deriving from the composite state of the external a model of the behavior of the component.
Claim 44
Dependent Claim
29 words
The method of claim 40 further comprising: including in the model of the behavior of the component information prescribing one or more transitions in the state of the external.
Claim 45
Dependent Claim
43 words
The method of claim 22 further comprising: using the model during analysis of a calling component of the computer program, the calling component including a call to the first-mentioned component, to determine the effect of execution of the first component on the external.
Claim 46
Independent Claim
124 words
A method for modelling the behavior of a component of a computer program, the component prescribing use of a resource, the method comprising: (a) defining one or more valid states for the resource, which has a resource state; (b) traversing a control flow path, which comprises one or more statements of the component; (c) for each of the one or more statements, performing the following steps: (i) determining that execution of the statement has an effect on the resource state of the resource; and (ii) modelling a transition from the resource state to a new resource state of the resource in accordance with the effect; and (d) building a model which represents a collective effect of the statements of the component on the resource.
Claim 47
Independent Claim
124 words
A method for modelling the behavior of a component of a computer program, the component prescribing use of a resource, the method comprising: (a) defining one or more valid states for the resource, which has a resource state; (b) traversing a control flow path, which comprises one or more statements of the component; (c) for each of the one or more statements, performing the following steps: (i) determining that execution of the statement has an effect on the resource state of the resource; and (ii) modelling a transition from the resource state to a new resource state of the resource in accordance with the effect; and (d) building a model which represents a collective effect of the statements of the component on the resource.
Claim 48
Dependent Claim
47 words
The method of claim 43 wherein the step of traversing comprises: determining that a selected statement of the one or more statements determines a portion of the control flow path according to a value of a predicate; and evaluating the predicate to determine the control flow path.
Claim 49
Dependent Claim
30 words
The method of claim 44 wherein the step of evaluating the predicate comprises: determining that the value of the predicate is unknown; and assigning to the predicate an assumed value.
Claim 50
Dependent Claim
26 words
The method of claim 45 wherein the step of evaluating the predicate further comprises: inferring from the assumed value information regarding the state of the resource.
Claim 51
Dependent Claim
29 words
The method of claim 45 wherein the step of evaluating the predicate further comprises: inferring from the assumed value respective values of one or more elements of the predicate.
Claim 52
Dependent Claim
84 words
The method of claim 47 wherein the step of traversing further comprises: determining that a second selected statement of the one or more statements determines a second portion of the control flow path according to a second value of a second predicate, which comprises one or more of the elements of the first-mentioned predicate; and evaluating the second predicate to determine the second portion of the control flow path using the inferred respective values of the one or more elements of the first predicate.
Claim 53
Dependent Claim
51 words
The method of claim 43 wherein step (c)(i) comprises: determining whether the statement is a call to a called component; if the statement is a call to a called component, emulating execution of the called component to evaluate the effect of the called component on the resource state of the resource.
Claim 54
Dependent Claim
54 words
The method of claim 49 wherein the step of emulating execution of the called component comprises: determining that the resource is associated with an external of the called component; and determining from a model of the called component the effect of execution of the component on the resource, which is associated with the external.
Claim 55
Dependent Claim
99 words
The method of claim 43 further comprising: (e) traversing a second control flow path, which comprises a second collection of one or more statements; (f) for each statement of the second collection of one or more statements, performing the following steps: (i) evaluating an effect of the statement on the resource state of the resource; and (ii) modelling a transition from the resource state to a second new resource state of the resource in accordance with the effect; (g) forming from the first-mentioned new resource state and the second new resource state a composite resource state of the resource.
Claim 56
Dependent Claim
47 words
The method of claim 51 wherein the step of traversing comprises: determining that a selected statement of the one or more statements determines a portion of the control flow path according to a value of a predicate; and evaluating the predicate to determine the control flow path.
Claim 57
Dependent Claim
30 words
The method of claim 52 wherein the step of evaluating the predicate comprises: determining that the value of the predicate is unknown; and assigning to the predicate an assumed value.
Claim 58
Dependent Claim
26 words
The method of claim 53 wherein the step of evaluating the predicate further comprises: inferring from the assumed value information regarding the state of the resource.
Claim 59
Dependent Claim
29 words
The method of claim 53 wherein the step of evaluating the predicate further comprises: inferring from the assumed value respective values of one or more elements of the predicate.
Claim 60
Dependent Claim
84 words
The method of claim 55 wherein the step of traversing further comprises: determining that a second selected statement of the one or more statements determines a second portion of the control flow path according to a second value of a second predicate, which comprises one or more of the elements of the first-mentioned predicate; and evaluating the second predicate to determine the second portion of the control flow path using the inferred respective values of the one or more elements of the first predicate.
Claim 61
Dependent Claim
51 words
The method of claim 51 wherein step (g)(i) comprises: determining whether the statement is a call to a called component; if the statement is a call to a called component, emulating execution of the called component to evaluate the effect of the called component on the resource state of the resource.
Claim 62
Dependent Claim
54 words
The method of claim 57 wherein the step of emulating execution of the called component comprises: determining that the resource is associated with an external of the called component; and determining from a model of the called component the effect of execution of the component on the resource, which is associated with the external.
Claim 63
Dependent Claim
23 words
The method of claim 51 further comprising: deriving from the composite state of the resource a model of the behavior of the component.
Claim 64
Dependent Claim
29 words
The method of claim 59 further comprising: including in the model of the behavior of the component information prescribing one or more transitions in the state of the resource.
Claim 65
Dependent Claim
43 words
The method of claim 43 further comprising: using the model during analysis of a calling component of the computer program, the calling component including a call to the first-mentioned component, to determine the effect of execution of the first component on the resource.
Claim 66
Dependent Claim
130 words
A resource checker for detecting programming errors in a component of a computer program, the component comprising one or more statements, the resource checker comprising: a resource behavior model which defines one or more valid states for a resource which in turn has a resource state; an execution engine which traverses a control flow path through the one or more statements and which determines that each of the one or more statements has a respective effect on the resource state of the resource; and a state machine which models a transition from the resource state to a new resource state of the resource in accordance with the effect of each of the one or more statements and which detects that the new state is not one of the valid states.
Claim 67
Dependent Claim
130 words
A resource checker for detecting programming errors in a component of a computer program, the component comprising one or more statements, the resource checker comprising: a resource behavior model which defines one or more valid states for a resource which in turn has a resource state; an execution engine which traverses a control flow path through the one or more statements and which determines that each of the one or more statements has a respective effect on the resource state of the resource; and a state machine which models a transition from the resource state to a new resource state of the resource in accordance with the effect of each of the one or more statements and which detects that the new state is not one of the valid states.
Claim 68
Dependent Claim
12 words
The resource checker of claim 62 wherein the component is a function.
Claim 69
Dependent Claim
46 words
The resource checker of claim 62 wherein the execution engine determines that a selected statement of the one or more statements determines a portion of the control flow path according to a value of a predicate and evaluates the predicate to determine the control flow path.
Claim 70
Dependent Claim
32 words
The resource checker of claim 64 wherein the execution engine evaluates the predicate by determining that the value of the predicate is unknown and by assigning to the predicate an assumed value.
Claim 71
Dependent Claim
22 words
The resource checker of claim 65 wherein the execution engine infers, from the assumed value, information regarding the state of the resource.
Claim 72
Dependent Claim
25 words
The resource checker of claim 65 wherein the execution engine infers, from the assumed value, respective values of one or more elements of the predicate.
Claim 73
Dependent Claim
93 words
The resource checker of claim 67 wherein the execution engine traverses the control flow path by determining that a second selected statement of the one or more statements determines a second portion of the control flow path according to a second value of a second predicate, which comprises one or more of the elements of the first-mentioned predicate; and further wherein the execution engine evaluates the second predicate to determine the second portion of the control flow path using the inferred respective values of the one or more elements of the first predicate.
Claim 74
Dependent Claim
65 words
The resource checker of claim 62 wherein the execution engine determines whether a selected statement of the one or more statements is a call to a called component; further wherein the execution engine emulates execution of the called component to evaluate the effect of the called component on the resource state of the resource if the selected statement is a call to a called component.
Claim 75
Dependent Claim
56 words
The resource checker of claim 69 wherein the execution engine emulates execution of the called component by determining that the resource is associated with an external of the called component and by determining from a model of the called component the effect of execution of the component on the resource, which is associated with the external.
References Cited (Backward Citations)
US5253158A
Cited
US5355469A
Cited
US5293629A
Cited
US5193180A
Cited
US5613063A
Cited
US5615369A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-12-01 | 2001-06-02 | 2001-12-02 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-12-01 | 2005-06-02 | 2005-12-02 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-12-01 | 2009-06-02 | 2009-12-02 | $7700.00 | Window Closed / Lapsed |