Path coverage criterion in specification-based testing based on an extended context-free grammar-based test specification model and a new test generation algorithm

• US 20060214948A1
• Filed: 03/23/2006
• Published: 09/28/2006
• Est. Priority Date: 03/25/2005
• Status: Active Grant

• Current Assignee: Siemens Information Systems Limited (Siemens AG)
• Original Assignee: Siemens Information Systems Limited (Siemens AG)
• Inventors: Murthy, P.V.R.
• Granted Patent: US 7,930,682 B2
• Time in Patent Office: Days
• US Class Current: 345/622
• CPC Class Codes: G06F 11/3676 for coverage analysis

Abstract

A system and method for generating test frames in specification-based testing by using a path-coverage criterion is provided. The method includes receiving a test design as an input, and constructing a context-free grammar graph, based on the test design. The method further includes analyzing the context-free grammar graph to generate a first set of paths, and emitting a set of test frames as an output, based on the first set of paths.

Claims

1. A method of generating test frames in specification-based testing the method comprising the steps of:

receiving a test design as an input, wherein the test design is represented as an extended context-free grammar (ECFG);

constructing a context-free grammar graph based on the test design, wherein the context-free grammar graph comprises a plurality of paths;

analyzing the context-free grammar graph to generate a first set of paths from the plurality of paths that satisfy one or more pre-conditions, wherein the one or more pre-conditions are associated with choices of the context-free grammar graph; and

emitting a set of test frames as an output, wherein the set of test frames is a second set of paths obtained from the first set of paths that satisfy a frame constraint specified in the test design.

The method of generating test frames as claimed in claim 1, wherein individual internal nodes of the context-free grammar graph are associated with non-terminals and individual leaf nodes of the context-free grammar graph are associated with terminals.

2. The method of generating test frames as claimed in claim 1, wherein the ECFG is capable of associating a pre-condition with a choice.

3. The method of generating test frames as claimed in claim 1, wherein analyzing the context-free grammar graph comprises the step of:

examining each path from the plurality of paths, starting from a root node of the context-free grammar graph to a leaf node of the context-free grammar graph.

4. The method of generating test frames as claimed in claim 4, wherein examining the path comprises the steps of:

visiting a first node of the path;

initially selecting a choice out of the first node based on depth-first traversal, wherein the first node is a non-terminal;

finally selecting the choice by evaluating a pre-condition associated with the choice; and

visiting a next node of the path by visiting a choice out of the next node when the pre-condition is satisfied, wherein the next node is a child node of the first node.

5. The method of generating test frames as claimed in claim 5, wherein the steps of visiting the first node, initially selecting the choice, finally selecting the choice, and visiting the next node are iteratively repeated till the next node is a terminal.

6. The method of generating test frames as claimed in claim 5, further comprising the step of:

adding the path to the first set of paths when the pre-condition associated with the choice is satisfied for each node of the path.

9. The method of generating test frames as claimed in claim 5 further comprising the step of:

exploring alternative choices out of the first node when the precondition associated with the choice is not satisfied; and

back-tracking to a previous node of the path to explore an alternative choice out of the previous node, when pre-conditions associated with alternative choices out of the first node are not satisfied, wherein the previous node is an ancestor node of the first node.

12. The method of generating test frames as claimed in claim 5 further comprising the steps of:

detecting cycles in the context-free grammar graph by maintaining a list of visited nodes; and

repeatedly expanding the cycles in a generic path for one or more times to obtain specific cycle-free paths.

7. The method of generating test frames as claimed in claim 7, further comprising the steps of:

evaluating a path from the first set of paths for the frame constraint; and

adding the path to the second set of paths, when the frame constraint for the path is satisfied.

8. The method of generating test frames as claimed in claim 8, further comprising the step of:

discarding the path, when the frame constraint for the path is not satisfied.

10. The method of generating test frames as claimed in claim 10, wherein the previous node and the alternative choice out of the previous node are a part of an alternative path from the plurality of paths, wherein the alternative path is considered as the test frame.

11. The method of generating test frames as claimed in claim 10, wherein the ancestor node is the root node of the context-free grammar graph.

13. A method of generating test frames in specification-based testing based on extended context-free grammar models using path coverage criterion, the method comprising the steps of:

constructing a context-free grammar graph based on a test design in Test Specification Language (TSL), wherein the context-free grammar graph comprises a plurality of paths, further wherein individual nodes of the context-free grammar graph represent non-terminals with choices joining non-terminals, further wherein the ECFG is capable of associating a pre-condition with a choice;

analyzing the plurality of paths of the context-free grammar graph to generate a first set of paths, wherein each path from the first set of paths satisfies pre-conditions that are associated with the choices in the path; and

emitting a set of test frames, wherein the set of test frames is a second set of paths from the first set of paths that satisfy a frame constraint associated with the test design.

14. The method of generating test frames as claimed in claim 14, wherein analyzing the context-free grammar graph comprises the step of:

examining each path from the plurality of paths, starting from a root node of the context-free grammar graph to a leaf node of the context-free grammar graph.

15. The method of generating test frames as claimed in claim 15, wherein examining the path comprise the steps of:

visiting a first node of the path;

initially selecting a choice out of the first node, wherein the first node is a non-terminal;

finally selecting the choice by evaluating a pre-condition associated with the choice; and

visiting a next node of the path by visiting a choice out of the next node, based on depth-first traversal when the pre-condition is satisfied, wherein the next node is a child node of the first node.

16. The method of generating test frames as claimed in claim 16, wherein the steps of visiting the first node, initially selecting the choice, finally selecting the choice, and visiting the next node are iteratively repeated till the next node is a terminal.

17. The method of generating test frames as claimed in claim 16, further comprising the step of:

adding the path to the first set of paths when the pre-condition associated with the choice is satisfied for each node of the path.

20. The method of generating test frames as claimed in claim 16 further comprising the step of:

exploring alternative choices out of the first node when the pre-condition associated with the choice is not satisfied; and

back-tracking to a previous node of the path to explore an alternative choice out of the previous node, when pre-conditions associated to the alternative choices are not satisfied, wherein the previous node is an ancestor node of the first node.

24. The method of generating test frames as claimed in claim 16 further comprising the steps of:

detecting cycles in the context-free grammar graph by maintaining a list of visited nodes; and

repeatedly expanding the cycles in a generic path for one or more times to obtain specific cycle-free paths.

18. The method of generating test frames as claimed in claim 18, further comprising the steps of:

evaluating a path from the first set of paths for the frame constraint; and

adding the path to the second set of paths, when the frame constraint for the path is satisfied.

19. The method of generating test frames as claimed in claim 18, further comprising the step of:

discarding the path, when the frame constraint for the path is not satisfied.

21. The method of generating the test frames as claimed in claim 21, wherein the previous node and the alternative choice out of the previous node are a part of a next path from the plurality of paths.

23. The method of generating test frames as claimed in claim 21, wherein the ancestor node is the root node of the context-free grammar graph.

25. A computer program product for generating test frames in specification-based testing, the computer program product comprising a computer readable medium comprising:

program instruction means for receiving a test design as an input, wherein the test design is represented as an extended context-free grammar (ECFG);

program instruction means for constructing a context-free grammar graph based on the test design, wherein the context-free grammar graph comprises a plurality of paths;

program instruction means for analyzing the plurality of paths of the context-free grammar graph to generate a first set of paths, wherein one or more pre-conditions associated with choices that are associated with the first set of paths are satisfied; and

program instruction means for emitting a set of test frames as an output, wherein the set of test frames is a second set of paths from the first set of paths that satisfy a frame constraint associated with the test design.

26. The computer program product for generating test frames as claimed in claim 25 further comprising:

program instruction means for examining each path from the plurality of paths, starting from a root node of the context-free grammar graph to a leaf node of the context-free grammar graph.

27. The computer program product for generating test frames as claimed in claim 26, wherein program instruction means for examining comprises:

program instruction means for visiting a node of the path;

program instruction means for selecting a choice out of the node of the path, wherein the node is a non-terminal;

program instruction means for evaluating a pre-condition associated with the choice; and

program instruction means for evaluating each path from the first set of paths for the frame constraint associated with the test design.

28. The computer program product for generating test frames as claimed in claim 27 further comprising:

program instruction means for discarding the path;

program instruction means for back-tracking to another node of the path for exploring an alternative choice out of the another node, wherein the another node is an ancestor node of the node; and

program instruction means for detecting cycles in the context-free grammar graph.

29. A test generator for generating test frames in specification-based testing procedure, the test generator comprising:

means for receiving a test design as an input, wherein the test design is represented as an extended context-free grammar (ECFG);

means for constructing a context-free grammar graph based on the test design, wherein the context-free grammar graph comprises a plurality of paths;

means for analyzing the plurality of paths of the context-free grammar graph to generate a first set of paths, wherein the first set of paths satisfy one or more pre-conditions; and

means for emitting a set of test frames as an output, wherein the set of test frames is a second set of paths from the first set of paths that satisfy a frame constraint associated with the test design.

30. The test generator for generating test frames as claimed in claim 29 further comprising:

means for examining each path from the plurality of paths, starting from a root node of the context-free grammar graph to a leaf node of the context-free grammar graph.

31. The test generator for generating test frames as claimed in claim 30, wherein the means for examining comprises:

means for selecting a choice out of a node;

means for evaluating a pre-condition associated with a choice;

means for adding the path to a set of paths;

means for evaluating the path for the frame constraint;

means for discarding the path;

means for back-tracking to an ancestor node of the path; and

means for detecting cycles in the context-free grammar graph, wherein the cycles are recorded as a part of a generic path and expanded one or more times to form specific paths that are free of cycles.

32. A test generator for generating test frames based on specification-based testing, the test generator comprising:

a memory for storing a test design, wherein the test design is represented as an extended context-free grammar (ECFG); and

a processor operatively coupled to the memory, wherein the processor is operable to;

construct a context-free grammar graph based on the test design, wherein the context-free grammar graph comprises a plurality of paths;

analyze the context-free grammar graph to generate a first set of paths from the plurality of paths that satisfy one or more pre-conditions, wherein the one or more pre-conditions are associated with choices of the context-free grammar graph; and

emit a set of test frames as an output, wherein the set of test frames is a second set of paths obtained from the first set of paths that satisfy a frame constraint specified in the test design.

33. The test generator as claimed in claim 32, further comprising:

an input interface operatively coupled to the memory and the processor, wherein the input interface provides the test design as an input for the test generator.