Event driven graph explorer for model-based testing of software

• US 20040225919A1
• Filed: 05/08/2003
• Published: 11/11/2004
• Est. Priority Date: 05/08/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Krovvidi, Praveen K., Lindquist, William B., Rohman, Michael R., Reissman, Pierre-Jean
• Granted Patent: US 7,302,677 B2
• Time in Patent Office: Days
• US Class Current: 714/38
• CPC Class Codes: G06F 11/3604 Software analysis for verifying properties of programs byte-code verification G06F9/44589

Abstract

A software testing system uses a graph traversal algorithm to explore a model simulating a software product in order to identify errors in the software product. The model employs a Petri'"'"'s net construct for maintaining state and governing transitions. In particular, the model mediates between a test driver and the software product. The model-based approach is usable both to validate the design of the software and verify the implementation of that design. Using the Petri net model, the test space is bounded.

Claims

1. A system for error-checking a software product comprising:

a model of the software product having places, transitions, and tokens, wherein a transition is operable to pass at least one token from at least one place;

a simulation engine for manipulating the software product and the model of the software product to cause an occurrence of an event in the software product and to cause an occurrence of a corresponding transition in the model of the software product, and to compare a state of the software product after occurrence of the event with the state of the model of the software product after occurrence of the corresponding transition.

2. The system according to claim 1, wherein the simulation engine is further adapted to log any errors in the software product determined when the state of the software product after occurrence of the event differs from the state of the model of the software product after occurrence of the corresponding transition.

3. The system according to claim 1, further comprising a graph traversal algorithm set, in accordance with which the software product and the model of the software product are manipulated by the simulation engine.

4. The system according to claim 1, further comprising a model editor for creating and manipulating the model of the software product.

5. The system according to claim 4, wherein the model editor comprises a visual user interface having therein visual model components that are selectable and mutable by a user.

6. The system according to claim 1, wherein the model of the software product further comprises components automatically extracted from the software product.

7. The system according to claim 6, wherein the components automatically extracted from the software product include a component corresponding to a method of a class in the software product and a component corresponding to an attribute of the class in the software product.

8. The system according to claim 5, wherein the visual user interface of the model editor further comprises a window having model units, each model unit comprising model components, wherein selection of a model unit causes the components of the selected unit to be displayed in a separate window as visual model components.

9. A computer-readable medium having stored thereon computer-executable instructions for instantiating in a memory of a computer the system according to claim 1.

10. A system for testing a software product to identify errors in the software product comprising:

model means for describing the software product; and

driver means for driving the software product and for driving the model means in a corresponding manner, whereby differences in the behavior of the software product relative to the model means are identified as errors in the software product.

11. A method of producing error-checked software code comprising:

producing a body of software code to be error-checked;

creating a model of the desired functionality of the software code to be error-checked, wherein the model comprises at least one Petri net; and

dynamically determining whether there is a difference in behavior of the software code to be error-checked as compared to the behavior of the model, whereby if there is such a difference in behavior, the difference is logged as an error in the software code to be error-checked.

12. The method according to claim 11, further comprising modifying the software to eliminate the logged error.

13. The method according to claim 11, wherein the model of the desired functionality of the software code to be error-checked is derived from a specification for the software code to be error-checked.

14. The method according to claim 11, wherein creating a model of the desired functionality of the software code to be error-checked comprises extracting information from the software code to be error-checked.

15. The method according to claim 14 wherein extracting information from the software code to be error-checked comprises extracting an attribute and a method of a class of the software code to be error-checked, wherein the attribute and method are used as a state and a transition respectively in the model.

16. The method according to claim 11, wherein the model defines a model space consisting of a set of states of the model, and wherein dynamically determining whether there is a difference in behavior of the software code to be error-checked as compared to the behavior of the model comprises receiving a graph traversal algorithm and traversing the model space pursuant to the received graph traversal algorithm.

17. A computer-readable medium having stored thereon computer-executable instructions for performing the method according to claim 11.

19. The model editor according to claim 17, wherein interconnecting of the visual depictions of elements within the user interface causes an interconnecting transition to be created between the corresponding elements of the model.

20. A computer-readable medium having thereon computer-executable instructions for running on a computer a model editor according to claim 17.

18. A model editor for creating and editing a Petri net model of a software body to be tested for errors, wherein the model is hierarchically constructed of one or more components, each component containing one or more elements, wherein the model editor comprises a hierarchical visual user interface having:

a first window containing a visual depiction of the of one or more components; and

a second window containing a visual depiction of one or more elements corresponding to one of the one or more components, wherein user selection of a component causes display in the second window of the visual depiction of the one or more elements associated with that component.

21. A method for testing a software product to identify at least one error in the software product comprising:

receiving input by the software product from a simulation engine; and

in response to said input, causing the occurrence of an event in the software product, whereby a state of the software product after the occurrence of said event is comparable with a state of a corresponding model of the software product to identify the at least one error in the software product.