Universal verification and validation system and method of computer-aided software quality assurance and testing

• US 6,671,874 B1
• Filed: 04/03/2000
• Issued: 12/30/2003
• Est. Priority Date: 04/03/2000
• Status: Expired due to Term

• Current Assignee: Blueprint Software Systems, Inc.
• Original Assignee: Blueprint Software Systems, Inc.
• Inventors: Passova, Sofia
• Primary Examiner(s): Chaki, Kakali
• Assistant Examiner(s): VU, TUAN A
• Application Number:
  US09/541,507
• Time in Patent Office: 1,366 Days
• Field of Search: 717/124-135, 717/162-166, 714/25-41
• US Class Current: 717/126
• CPC Class Codes: G06F 11/3608 using formal methods, e.g. model checking, abstract interpretation theorem proving G06N5/013
• CPC Class Codes: G06F 11/3696 Methods or tools to render software testable
• CPC Class Codes: G06F 8/73 Program documentation

Abstract

A method of developing a model of a computer program represents the system requirement conditions and events as a set of positions and transitions, maps the system requirements in a table of positions with position and optionally transition designations, tags one or more significant positions in the including any conditional positions, and creates a reference designation associating alternative conditions with their respective conditional positions. A universal software test development method can be applied to the model by mapping the conditions to a set of positions including a starting position which has no input, a terminal position which has no output, and intermediate positions between the starting position and the terminal position, and generating from the set of positions a table of positions, associating each positions with an expression of the position representing the corresponding system requirements. Both the model development method and the test development method can be implemented automatically by computer software, and the test development method allows for automated development of test documentation. These methods can thus be applied for the verification and validation of computer software.

Claims

1. A method of developing a model of a computer program implementing specified requirements, the method comprising the steps of

a. applying positions to statements in the requirements,

b. mapping the positions to the corresponding statements to create a table of positions,

c. adding transitions between the positions,

d. identifying significant positions which are positions defining points for test development,

e. adding as an input to each transition immediately following a significant position a redundant position having no input transition, the state of which controls activation of its output transition, and

f. mapping the redundant positions in the table of positions.

2. The method of claim 1 further comprising the step of generating an input matrix of positions against transitions in which an intersection of each transition and its associated input position is marked.

3. The method of claim 2 further comprising the step of generating an output matrix of transitions against positions in which an intersection of each transition and its associated output position is marked.

4. The method of claim 1 further comprising the step of tagging the significant positions.

5. The method of claim 1 further comprising the step of assigning a reference designation associating one or more alternative output positions with respective significant positions.

6. The method of claim 1, wherein the statements are divided into conditions and events and positions are applied to conditions and further comprising the steps of applying transitions to events and mapping the transitions in a table of transitions relating the transitions to the corresponding events.

7. The method of claim 1 further comprising the step of developing a test based on a segment of the model by reverse analysis from a position having no output transition to a redundant position.

8. The method of claim 7 further comprising the step of mapping positions back to their corresponding requirements.

9. The method of claim 7 further comprising the step of testing design level algorithms using one or more tests generated from system requirements.

10. The method of claim 7 further comprising the step of testing implementation level code using tests generated from system requirements or design algorithms.

11. The method of claim 1 wherein the statements are system level requirements described in a natural language or design level requirements described as algorithms.

12. The method of claim 1 wherein the model is a hierarchical Petri net model extended by mapping.

13. A computer program product for use with a computer, the computer program product comprising a computer usable medium having computer readable program code means embodied in said medium for generating a model of a computer program implementing specified requirements comprising a series of statements, said computer program product having

a. computer readable program code means for mapping positions in a Petri net to the statements to create a table of positions,

b. computer readable program code means for identifying one or more significant positions which are positions defining segments of the model which can be independently analyzed,

c. computer readable program code means for adding as an input to each transition immediately following a significant position a redundant position having no input transition, the state of which controls activation of its output transition, and

d. computer readable program code means for mapping the redundant positions in the table of positions.

14. The computer program product of claim 13 further comprising computer readable program code means for generating an input matrix of positions against transitions in which an intersection of each transition and its associated input position is marked.

15. The computer program product of claim 14 further comprising computer readable program code means for generating an output matrix of transitions against positions in which an intersection of each transition and its associated output position is marked.

16. The computer program product of claim 13 further comprising computer readable program code means for developing a test based on a segment of the model by reverse analysis from a position having no output transition to a redundant position.

17. The computer program product of claim 16 further comprising computer readable program code means for analyzing results of the test development by replacing positions between the position having no output transition to the redundant position with a description of their respective statements.

18. The computer program product of claim 13 wherein the statements are system level requirements described in a natural language or design level requirements described as algorithms.

19. The computer program product of claim 13 wherein the model is a hierarchical Petri net model extended by mapping.

20. A method of test development for a computer program having program code and designed to implement requirements comprising conditions and events, to verify concordance between the computer program and the requirements, the method comprising the steps of

a. mapping the conditions and events to a set of positions and transitions comprising at least one starting position which has no input, at least one terminal position which has no output, and intermediate positions and transitions connected between the starting position and the terminal position,

b. identifying one or more significant positions that are significant for test development,

c. adding as an input to each transition immediately following a significant position a redundant position having no input transition, the state of which controls activation of its output transition,

d. conducting a reverse analysis of at least a portion of the requirements from a terminal position to generate a table of positions comprising, in sequence, the terminal position, positions between the terminal position and the starting position, and the starting position, and

e. inverting information in the table of positions and reverse mapping from positions to statements to generate a natural language test.

21. A method of modelling user requirements, said method comprising:

acquiring information regarding the user requirements;

dividing the information regarding user requirements into statements having a natural language format;

mapping positions to the statements;

identifying one or more significant positions, wherein the significant positions comprise positions mapped to condition statements, positions mapped to other statements relevant to test development, and positions mapped to other statements selected by a user;

mapping significant positions within the basic flow and alternative flows to associated significant positions within the basic and alternative flows;

generating a Petri net that models the basic flow and alternative flows using the positions and transitions added between the positions;

adding redundant positions to the Petri net that are associated with each significant position that represents a condition statement, wherein the redundant positions have no input transition and a marking of each redundant position controls activation of the associated significant position'"'"'s output transition; and

generating input and output matrices of positions and transitions within the extended Petri net.

22. The method of claim 21, further comprising:

generating a flowchart of the user requirements based on the extended Petri net.

23. The method of claim 21, further comprising:

generating tests for a computer program application based on the user requirements by reverse analysis of the extended Petri net and reverse mapping from positions to statements.

24. The method of claim 23, wherein said tests relate to system requirements, design requirements and implementation requirements for the computer program application.

25. The method of claim 21, further comprising:

simulating a computer program application based on the user requirements by using the extended Petri net, wherein the simulation utilises the reverse mapping of positions to statements to present a user with the statements having a natural language format.

26. The method of claim 25, further comprising:

generating a flowchart of the user requirements based on the extended Petri net; and

presenting the user with the flowchart simultaneously with the statements.

27. The method of claim 21, wherein said verification comprises:

moving through the extended Petri net in a step-by-step manner and using reverse mapping of positions to statements to present a user with statements.

28. The method of claim 21, wherein the Petri net analysis comprises Petri net simulation.

29. A computer program product for modeling user requirements, the computer program product comprising a computer usable medium having computer readable program code embodied therein, wherein when said computer readable program code is executed in a computer, said computer readable program code causes said computer to:

acquire information regarding the user requirements;

divide the information regarding user requirements into statements having a natural language format;

map positions to the statements;

identify one or more significant positions, wherein the significant positions comprise positions mapped to condition statements, positions mapped to other statements relevant to test development, and positions mapped to other statements selected by a user;

map significant positions within the basic flow and alternative flows to associated significant positions within the basic and alternative flows;

generate a Petri net that models the basic flow and alternative flows using the positions and transitions added between the positions;

add redundant positions to the Petri net that are associated with each significant position that represents a condition statement, wherein the redundant positions have no input transition and a marking of each redundant position controls activation of the associated significant position'"'"'s output transition; and

generate input and output matrices of positions and transitions within the extended Petri net.

30. The computer program product of claim 29, wherein said computer readable program code further causes said computer to:

generate tests for a computer program application based on the user requirements by reverse analysis of the extended Petri net and reverse mapping from positions to statements.

31. The computer program product of claim 29, wherein said computer readable program code further causes said computer to:

simulate a computer program application based on the user requirements by using the extended Petri net, wherein the simulation utilises the reverse mapping of positions to statements to present a user with the statements having a natural language format.