Event driven graph explorer for model-based testing of software

• US 7,302,677 B2
• Filed: 05/08/2003
• Issued: 11/27/2007
• Est. Priority Date: 05/08/2003
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Reissman, Pierre-Jean, Krovvidi, Praveen K., Lindquist, William B., Rohman, Michael R.
• Primary Examiner(s): Khatri; Anil
• Application Number:
  US10/431,733
• Publication Number:
  US 20040225919A1
• Time in Patent Office: 1,664 Days
• Field of Search: 717124-130, 717135-140
• US Class Current: 717/135
• 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:

at least one processor and a computer-readable storage medium coupled to the at-least one processor;

a model of the software product defining a model space comprising a set of states of the model, the model having places, transitions, and tokens, wherein a transition is operable to pass at least one token from at least one place, and wherein the model of the software product comprises components automatically extracted from the software product; and

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, and to log errors found in the software product.

2. The system according to claim 1, wherein logged errors are 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 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.

7. The system according to claim 1, 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. A computer-implemented 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 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; 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 found in the software code to be error-checked.

9. The method according to claim 8, further comprising modifying the software to eliminate the logged error.

10. The method according to claim 8, 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.

11. The method according to claim 8 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.

12. The method according to claim 8, 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.

13. A computer-readable storage medium having stored thereon computer-executable instructions for performing the method according to claim 8.

14. A computer-implemented 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;

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 found in the software product, wherein the model comprises components automatically extracted from the software product; and

providing data associated with the at least one error for review.