Constructing petri nets from traces for diagnostics

• US 8,276,124 B2
• Filed: 06/20/2007
• Issued: 09/25/2012
• Est. Priority Date: 06/20/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Maennel, Hartmut
• Primary Examiner(s): TECKLU, ISAAC TUKU
• Application Number:
  US11/820,594
• Publication Number:
  US 20080320437A1
• Time in Patent Office: 1,924 Days
• Field of Search: None
• US Class Current: 717/128
• CPC Class Codes: G06F 11/3604 Software analysis for verifying properties of programs byte-code verification G06F9/44589
• CPC Class Codes: G06F 11/366 using diagnostics G06F11/0703 takes precedence

Abstract

Various technologies and techniques are disclosed for using Petri Nets for diagnostics of concurrent programs. One or more initial traces are obtained from a concurrent program that executed properly. The initial trace is used to create a Petri Net. To generate the Petri Net, unique task identifiers and places of interest are generated, and transitions are added. The resulting Petri Net is stored for later use in differential debugging. A trace is obtained from a later execution of the concurrent program that did not execute properly. The later trace is run against the Petri Net to identify at least one difference. A Petri Net can also be used for model checking of concurrent programs. A model checking process is performed to analyze possible executions in the Petri Net to look for one or more problems. A result of the model checking process is output.

Claims

1. A computer-readable storage medium having computer-executable instructions for causing a computer to perform steps comprising:

obtain at least one initial trace from a concurrent program that executed properly;

use the at least one initial trace to create a Petri Net;

using the at least one trace to generate unique label or task identifiers for a Petri Net;

obtain a later trace from a later execution of the concurrent program that did not execute properly; and

run the later trace against the Petri Net to identify at least one difference by comparing the Petri Net to the later trace corresponding to a subsequent execution of the concurrent program where the concurrent program executed improperly, wherein the comparing includes determining whether a transition in the Petri Net has at least one of the corresponding label or task identifier in the later trace.

2. The computer-readable storage medium of claim 1, further having computer-executable instructions for causing a computer to perform steps comprising:

output the identified difference.

3. The computer-readable storage medium of claim 1, wherein the Petri Net is generated with one or more colors that provide additional details.

4. Then computer-readable storage medium of claim 3, wherein the color is a variable that is used for passing data between threads.

5. The computer-readable storage medium of claim 3, wherein the color is used to track an instance of each procedure.

6. Then computer-readable storage medium of claim 3, wherein the color is used to store a thread identifier to identify which thread is executing a giver section.

7. The computer-readable storage medium of claim 3, wherein the color is an index of an array that allows a dynamically allocated array to be represented in the Petri Net.

8. The computer-readable storage medium of claim 1, wherein the Petri Net is created by generating unique task identifiers, generating places of interest, and adding transitions.

9. A method for generating a Petri Net for use in differential debugging of a concurrent program comprising the steps of:

obtaining at least one trace from a concurrent program that executed properly;

obtain a later trace from a later execution of the concurrent program that did not execute properly;

using the at least one trace to generate unique label or task identifiers for a Petri Net;

using the trace to generate places of interest for the Petri Net;

adding transitions to the Petri Net;

storing the resulting Petri Net for later use in differential debugging; and

comparing the Petri Net to a later trace corresponding to a subsequent execution of the concurrent program where the concurrent program executed improperly, wherein the comparing includes determining whether a transition in the Petri Net has at least one of the corresponding label or task identifier in the later trace.

10. The method of claim 9, wherein the Petri Net is generated with one or more colors that are used to provide additional information.

11. The method of claim 10, wherein variable values are added as colors to the Petri Net.

12. The method of claim 11, wherein variable values for control flow are added as colors to the Petri Net.