SYSTEM AND METHOD FOR VERIFYING OPERATION OF A TARGET SYSTEM

• US 20090193294A1
• Filed: 01/26/2009
• Published: 07/30/2009
• Est. Priority Date: 01/28/2008
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Nakamura, Hiroaki, Ono, Kohichi
• Granted Patent: US 8,078,915 B2
• Time in Patent Office: Days
• US Class Current: 714/26
• CPC Class Codes: G06F 11/3612 by runtime analysis performance monitoring G06F11/3466

Abstract

A system and method for verifying operation of a target system to be inspected. The system includes an abstract binary tree generation unit and a matching unit. The abstract binary tree generation unit obtains information about a functional specification of the target system and generates one or more binary trees that associate one or more states that can occur in the target system with respective nodes and that associate state transitions of objects constituting the target system and interactions between the objects with connection relationships between the nodes. The matching unit receives an event sequence in an application model of the target system obtained in response to the operation of the target system and matches the event sequence against the binary trees generated by the abstract binary tree generation unit. The method includes steps for accomplishing the functionality of the system.

Claims

1. A system for verifying operation of a target system to be inspected, the system comprising:

a binary-tree generating unit; and

a matching unit;

wherein the binary-tree generating unit obtains information about a functional specification of the target system and generates one or more binary trees that associate (1) one or more states that can occur in the target system with respective nodes and (2) state transitions of objects constituting the target system and interactions between the objects with connection relationships between the nodes; and

wherein the matching unit receives an event sequence in an application model of the target system obtained in response to the operation of the target system to match the event sequence against the binary trees generated by the binary-tree generating unit.

2. The system according to claim 1, wherein the binary-tree generating unit obtains a state transition diagram of each of the objects and a sequence diagram for each use case of the target system as information about a functional specification of the target system and generates the binary trees based on the information about state transitions obtained from the state transition diagrams and information about interactions obtained from the sequence diagram.

3. The system according to claim 2, wherein the binary-tree generating unit aggregates non-interactive sub sequences of an action sequence constituting the sequence diagram, the non-interactive sub sequences having a same state of the target system at their starting point and a same state of the target system at their end point thereof, to generate the binary trees.

4. The system according to claim 1, wherein:

the binary-tree generating unit generates a graph representing an implication of a plurality of assertions being the states of the target system at starting points of the binary trees, and

the matching unit retrieves an assertion that matches the state of the target system at a starting point of the obtained event sequence from the graph and makes a binary tree having the retrieved assertion be subjected to the matching of the event sequence.

5. The system according to claim 1, wherein the matching unit defines a plurality of search spaces corresponding to a plurality of event sequences occurring in the target system in memory and matches the event sequences against the binary trees in the plurality of search spaces in parallel therewith.

6. The system according to claim 5, wherein the matching unit sets a finishing time interval for each of the defined search spaces and terminates processing performed in a search space that reaches the end of the finishing time interval to free up a storage area used by the search space in the memory.

7. The system according to claim 1, wherein the matching unit narrows down an event sequence to be subjected to the verification using a software filter that specifies an event that is not to be subjected to the verification from the operation of the target system.

8. The system according to claim 1, further comprising a conversion unit for converting information obtained by a probe provided in the target system together with the operation of the target system into an event sequence in the application model of the target system and transmitting the event sequence to the matching unit.

9. A method of verifying operation of a target system to be inspected, the method comprising the steps of:

obtaining a state transition diagram of each object and a sequence diagram for each use case of the target system as information about a functional specification of the target system;

generating one or more binary trees that associate one or more states that can occur in the target system with respective nodes based on information about state transitions obtained from the state transition diagrams and information about interactions obtained from the sequence diagram and that associate state transitions of the objects constituting the target system and interactions between the objects with connection relationships between the nodes; and

receiving an event sequence in an application model of the target system obtained in response to the operation of the target system and matching the event sequence against the generated binary trees.

10. The method according to claim 9, wherein the binary-tree generating step further includes the step of aggregating non-interactive sub sequences of an action sequence constituting the sequence diagram, the non-interactive sub sequences having the same state of the target system at their starting points and the same state of the target system at their end points, to generate the binary trees.

11. The method according to claim 9, further comprising the steps of:

generating a graph representing an implication of a plurality of assertions being the states of the target system at starting points of the binary trees; and

retrieving an assertion that matches the state of the target system at a starting point of the obtained event sequence from the graph and making a binary tree having the retrieved assertion be subjected to the matching of the event sequence.

12. A computer readable article of manufacture tangibly embodying computer readable instructions for executing the steps of a method of verifying operation of a target system to be inspected, the method comprising:

obtaining information about a functional specification of a target system to be inspected and generating one or more binary trees that associate one or more states that can occur in the target system with respective nodes and that associate state transitions of objects constituting the target system and interactions between the objects with connection relationships between the nodes; and

receiving an event sequence in an application model of the target system obtained in response to the operation of the target system and matching the event sequence against the binary trees generated by the binary-tree generating means.

13. The computer readable article according to claim 12, wherein the method further comprises the steps of:

obtaining a state transition diagram of each of the objects and a sequence diagram for each use case of the target system as the information about the functional specification of the target system; and

generating the binary trees on the basis of information about state transitions obtained from the state transition diagrams and information about interactions obtained from the sequence diagram.

14. The computer readable article according to claim 13, wherein the method further comprises the step of:

aggregating non-interactive sub sequences of an action sequence constituting the sequence diagram, the non-interactive sub sequences having the same state of the target system at their starting points and the same state of the target system at their end points, to generate the binary trees.

15. The computer readable article according to claim 12, wherein the method further comprises the steps of:

generating a graph representing an implication of a plurality of assertions being the states of the target system at starting points of the binary trees; and

retrieving an assertion that matches the state of the target system at a starting point of the obtained event sequence from the graph and making a binary tree having the retrieved assertion be subjected to the matching of the event sequence.