Checking for access problems with data stores

• US 8,601,457 B1
• Filed: 03/13/2009
• Issued: 12/03/2013
• Est. Priority Date: 01/31/2008
• Status: Active Grant

• Current Assignee: The MathWorks, Inc.
• Original Assignee: The MathWorks, Inc.
• Inventors: Han, Zhi
• Primary Examiner(s): Tang, Kenneth
• Assistant Examiner(s): YUEN, KEITH CHI HANG
• Application Number:
  US12/404,085
• Time in Patent Office: 1,726 Days
• Field of Search: 717/154
• US Class Current: 717/156
• CPC Class Codes: G06F 11/3608 using formal methods, e.g. model checking, abstract interpretation theorem proving G06N5/013
• CPC Class Codes: G06F 8/34 Graphical or visual programming

Abstract

In an embodiment, a technique that may be used to identify a pattern with respect to accessing a data store in a model. The pattern may be a desirable, undesirable, anomalous or some other type of pattern with respect to accessing the data store. The technique may include generating an execution control graph that represents an execution of the model. The execution control graph may be analyzed to identify the pattern. Analysis may include generating an expression based on the execution control graph and a condition to test for and determining, based on the expression, if the condition is met. If the condition is met, the pattern may be said to exist in the model. A result may generated based on the analysis and the result may be output.

Claims

1. One or more non-transitory computer-readable storage media comprising:

one or more instructions that, when executed by processing logic, cause the processing logic to;

generate an execution control graph that represents an execution of a model, the execution control graph including;

a plurality of nodes,

each node, of the plurality of nodes, corresponding to one or more blocks of the model, and

a plurality of edges,

each edge, of the plurality of edges, extending between two of the plurality of nodes to indicate an execution relationship between the two of the plurality of nodes;

analyze the plurality of edges and the plurality of nodes in the execution control graph;

determine, based on analyzing the plurality of edges and the plurality of nodes, an existence of a particular pattern associated with accessing a data store during the execution of the model,

the one or more instruction that, when executed by the processing logic, cause the processing logic to determine the existence of the particular pattern further causing the processing logic to;

generate an expression based on the execution control graph and a condition,

the condition representing the particular pattern;

determine, based on the generated expression, whether the condition is satisfied; and

determine the existence of the particular pattern based on determining whether the condition is satisfied,

where the condition is satisfied when at least one of;

 

the data store is accessed to read first data from the data store prior to the data store being accessed to write second data to the data store, or

 

the data store is accessed to write the second data to the data store prior to the data store being accessed to read the first data from the data store;

generate a result based on determining the existence of the particular pattern,

the generated result including information identifying the particular pattern associated with accessing the data store; and

output the result.

2. The one or more non-transitory computer-readable storage media of claim 1, where the plurality of edges indicate at least one of:

dependencies between blocks in the model, or

hierarchical relationships between the blocks in the model, and

where the one or more instructions that, when executed by the processing logic, cause the processing logic to analyze the plurality of edges and the plurality of nodes in the execution control graph further cause the processing logic to;

analyze the plurality of edges and the plurality of nodes in the execution control graph based on the plurality of edges indicating the at least one of the dependencies or the hierarchical relationships.

3. The one or more non-transitory computer-readable storage media of claim 1, where the model is one of:

a time-based graphical block diagram model,

a state transition diagram,

a discrete event model,

an activity diagram,

a Unified Modeling Language (UML) diagram,

a sequence diagram, or

a data flow model.

4. The one or more non-transitory computer-readable storage media of claim 1, where the one or more instructions that, when executed by the processing logic, cause the processing logic to generate the expression further cause the processing logic to:

generate the expression is in a normal form.

5. The one or more non-transitory computer-readable storage media of claim 1, where the one or more instructions that, when executed by the processing logic, cause the processing logic to generate the expression further cause the processing logic to:

generate the expression in a conjunctive normal form, or

generate the expression in a disjunctive normal form.

6. The one or more non-transitory computer-readable storage media of claim 1, where the one or more instructions that, when executed by the processing logic, cause the processing logic to determine the existence of the particular pattern based on whether the condition is satisfied further cause the processing logic to:

determine the existence of the particular pattern when the condition is satisfied.

7. The one or more non-transitory computer-readable storage media of claim 1, where the one or more instructions that, when executed by the processing logic, cause the processing logic to output the result further cause the processing logic to:

output an indication that identifies the existence of the particular pattern when the condition is satisfied.

8. The one or more non-transitory computer-readable storage media of claim 1, where the one or more instructions that, when executed by the processing logic, cause the processing logic to generate the expression further cause the processing logic to:

generate a Boolean expression.

9. The one or more non-transitory computer-readable media of claim 1, where the one or more instructions that, when executed by the processing logic, cause the processing logic to output the result, further cause the processing logic to:

output the result to a device that is associated with the processing logic.

10. The one or more non-transitory computer-readable storage media of claim 1, where the one or more instructions that, when executed by the processing logic, cause the processing logic to output the result, further cause the processing logic to at least one of:

display the result on a display device associated with the processing logic, or

store the result in a storage device associated with the processing logic.

11. The one or more non-transitory computer-readable storage media of claim 1, where the one or more instructions that, when executed by the processing logic, cause the processing logic to determine the existence of the particular pattern further cause the processing logic to:

determine whether the data store is accessed a plurality of times to write third data to the data store before the data store is accessed to read fourth data from the data store.

12. A method comprising:

generating, using processing logic, an execution control graph that represents an execution of a model, the execution control graph including;

a plurality of nodes,

each node, of the plurality of nodes, corresponding to one or more blocks of the model, and

a plurality of edges,

each edge, of the plurality of edges, extending between two of the plurality of nodes to indicate an execution relationship between the two of the plurality of nodes;

analyzing, using the processing logic, the plurality of edges and the plurality of nodes;

determine an existence of a particular pattern associated with accessing a data store during the execution of the model based on analyzing the plurality of edges and the plurality of nodes,

determining the existence of the particular pattern including;

generating, using the processing logic, an expression based on the execution control graph and a condition,

the condition representing the particular pattern,

determining, based on the generated expression, whether the condition is satisfied; and

determining the existence of the particular pattern based on determining whether the condition is satisfied,

the condition being satisfied when at least one of;

 

the data store is accessed to read first data from the data store prior to the data store being accessed to write second data to the data store, or

 

the data store is accessed to write the second data to the data store prior to the data store being accessed to read the first data from the data store; and

generating, using the processing logic, a result based on whether the expression is satisfied.

13. The method of claim 12, further comprising:

outputting, using the processing logic, the result to a device that is accessible to the processing logic.

14. The method of claim 12, further comprising at least one of:

displaying, using the processing logic, the result on a display device accessible to the processing logic, or

storing, using the processing logic, the result in a storage device accessible to the processing logic.

15. The method of claim 14, where outputting the result comprises displaying the result on the display device, and

where displaying the result further comprises:

displaying an indication of the pattern in;

a display of the execution control graph, or

a graphical block diagram display of the model.

16. The method of claim 12, where generating the expression includes:

generating the expression in a conjunctive normal form, or

generating the expression in a disjunctive normal form.

17. The method of claim 12, where generating the expression includes:

generating a Boolean expression.

18. The method of claim 12, where the model is one of:

a time-based graphical block diagram model,

a state transition diagram,

a discrete event model,

an activity diagram,

a Unified Modeling Language (UML) diagram,

a sequence diagram, or

a data flow model.

19. The method of claim 12, where the condition further includes:

whether the data store is accessed to write the second data to the data store a plurality of times before the data store is accessed to read the second data from the data store.

20. A system comprising:

an output device; and

a processor to;

generate an execution control graph including a plurality of nodes and a plurality of edges,

the plurality of nodes corresponding to a plurality of blocks associated with a model,

the plurality of edges indicating at least one of;

dependencies between blocks in the model or

hierarchical relationships between blocks in the model, and the execution control graph representing an execution of the model,

analyze the plurality of edges in the execution control graph,

determine, based on analyzing the plurality of edges in the graph, an existence of a particular pattern associated with accessing a data store during the execution of the model,

when determining the existence of the particular pattern, the processor being to;

generate an expression based on the execution control graph and a condition,

 

the condition representing the particular pattern,

determine, based on the generated expression, whether the condition is satisfied, and

determine the existence of the particular pattern based on determining whether the condition is satisfied,

 

where the condition is satisfied when at least one of;

 

the data store is accessed to read first data from the data store prior to the data store being accessed to write second data to the data store, or

 

the data store is accessed to write the second data to the data store prior to the data store being accessed to read the first data from the data store,

generate a result based on determining the existence of the particular pattern,

the generated result including information identifying the particular pattern, and

output the result via the output device.

21. The system of claim 20, where the output device comprises:

a display device, and

where, when outputting the result, the processor is further to;

transform a graphical display of the model to indicate one or more portions of the model associated with the particular pattern.

22. A system comprising:

one or more devices including at least one processor to;

generate an execution control graph that includes a plurality of nodes and a plurality of edges,

the plurality of nodes corresponding to a plurality of blocks associated with a model,

the plurality of edges indicating at least one of dependencies between blocks in the model or hierarchical relationships between blocks in the model, and

the execution control graph representing an execution of the model;

analyze the plurality of edges in the execution control graph,

determine an existence of a particular pattern associated with accessing a data store during an execution of the model,

when determining the existence of the particular pattern, the processor being to;

generate an expression based on the execution control graph and a condition,

the condition representing the particular pattern,

determine, based on the generated expression, whether the condition is satisfied, and

determine the existence of the particular pattern based on determining whether the condition is satisfied,

wherein the condition is satisfied when at least one of;

 

the data store is accessed to read first data from the data store prior to the data store being accessed to write second data to the data store, or

 

the data store is accessed to write the second data to the data store prior to the data store being accessed to read the first data from the data store; and

transform a graphical display of the model to indicate one or more portions of the model associated with the identified pattern.

23. One or more non-transitory computer-readable storage media storing instructions, the instructions comprising:

one or more instructions that when executed by one or more processors, cause the one or more processors to;

generate an execution control graph that represents an execution of a model;

the execution control graph including a plurality of nodes and a plurality of edges,

the plurality of nodes corresponding to a plurality of blocks associated with a model, and

the plurality of edges indicating at least one of;

dependencies between blocks in the model, or

hierarchical relationships between blocks in the model, and

the execution control graph representing an execution of the model;

analyze the plurality of edges in the execution control graph;

determine, based on analyzing the plurality of edges in the execution control graph, an existence of a particular pattern associated with accessing a data store during the execution of the model,

when determining the existence of the particular pattern, the processor being to;

generate an expression based on;

the execution control graph, and

a condition,

 

the condition representing a pattern with respect to accessing a data store during an execution of the model,

 

the condition being at least one of;

 

whether the data store is accessed to read first data from the data store prior to the data store being accessed to write second data to the data store, or

 

whether the data store is accessed to write the second data to the data store prior to the data store being accessed to read the first data from the data store,

determine whether the expression is satisifiable,

the expression being satisfiable when;

 

the data store is accessed to read the first data from the data store prior to the data store being accessed to write the second data to the data store, or

 

the data store is accessed to write the second data to the data store prior to the data store being accessed to read the first data from the data store.

24. The non-transitory computer-readable storage media of claim 23, where the instructions further comprise:

One or more instructions that, when executed by the one or more processors, cause the one or more processors to;

transform, when the expression is satisfiable, at least one of a graphical display of the model or a graphical display of the execution control graph to indicate one or more portions of the model that are associated with the pattern.