US6038378A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for testing implementations of software specifications
Assignee: Hewlett Packard Development Co LP
•
Filing: 1996-07-10
•
Granted: 2000-03-14
•
Expires: 2016-07-10
Abstract
Abstract A method and apparatus for automatically generating validation tests for implementations of a program specification for an operating system, software application or a machine, where the program specification is expressed at least in part in terms of data structures and relationships. The method is carried out by a computer. The program specification is expressed in an interface specification language which is automatically parsed, and is then transformed into an extended finite state machine (EFSM) or multiple-EFSM architecture internally represented in the computer, the EFSM including objects representing states and transitions between those states representing executable functions, annotated to the states. The annotations may represent predicates, test data, value assignments, branch conditions, etc. The EFSM or architecture is traversed by a path traversal procedure, either exhaustively or in part, thereby producing path files, one for each path taken. Each path file is linked to a program shell, which is automatically generated for the specification, resulting in one independent validation test for each path file. Each validation test includes a call to the implementation of the program specification, and presents that implementation with a test vector representing a given path through the model. Failure and success responses are produced, indicating whether the implementation behaved as expected. Multiple validation tests may be linked or combined in a variety of ways to form a superstructure (architecture) of validation tests for testing of many routines in conjunction with one another, such as for testing all the routines specified for an operating system at the same time.
Inventors
- 👤 Ronald Allen Kita
- 👤 Mark Edward Trumpler
- 👤 Lois Scirocco Elkind
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-07 16:19
CPC Classifications
G; G06; G06F; G06F11/00; G06F11/36; G06F11/3668; G06F11/3672; G06F11/3684
Claims Analysis
Total Claims: 34
Claim 1
Independent Claim
317 words
A method for generating tests for an implementation of a program to insure that the implementation conforms to a natural language and computer readable program specification that specifies the functions the program will have to fulfill, defines the types and uses of variables, defines parameters and their relationships, and other system requirements, the method being carried out in a processor and including the steps of: (1) accepting as an input the natural language and computer readable program specification, wherein data relationships are expressed in the program specification with predefined syntax and semantics; (2) parsing the program specification in accordance with said predefined syntax and semantics to generate data structures and relationships between the data structures which represent parameters and functionality expressed in the program specification; (3) modeling the program specification by transforming the parsed program specification according to said semantics into a finite state machine (FSM), which represents data relationships in the program specification and which includes at least a starting state, an ending state, a plurality of intermediate states, and a set of transitions defining conditions under which the FSM is traversed from a given state to a subsequent state; (4) generating a test specification comprised of a set of computer readable path files, wherein the path files are generated by traversing paths in the FSM, each path file defining a path beginning at the starting state and ending at the ending state and including a unique traversal of said set of transitions and intermediate states and defining data and variables for one test; (5) generating executable program code as an implementation of the program specification and derived from the FSM, wherein the program code is in the form of a program shell; and (6) generating executable test programs for testing the implementation of the program specification, each test program being generated by merging into a copy of the program shell one of said path files.
Claim 2
Independent Claim
317 words
A method for generating tests for an implementation of a program to insure that the implementation conforms to a natural language and computer readable program specification that specifies the functions the program will have to fulfill, defines the types and uses of variables, defines parameters and their relationships, and other system requirements, the method being carried out in a processor and including the steps of: (1) accepting as an input the natural language and computer readable program specification, wherein data relationships are expressed in the program specification with predefined syntax and semantics; (2) parsing the program specification in accordance with said predefined syntax and semantics to generate data structures and relationships between the data structures which represent parameters and functionality expressed in the program specification; (3) modeling the program specification by transforming the parsed program specification according to said semantics into a finite state machine (FSM), which represents data relationships in the program specification and which includes at least a starting state, an ending state, a plurality of intermediate states, and a set of transitions defining conditions under which the FSM is traversed from a given state to a subsequent state; (4) generating a test specification comprised of a set of computer readable path files, wherein the path files are generated by traversing paths in the FSM, each path file defining a path beginning at the starting state and ending at the ending state and including a unique traversal of said set of transitions and intermediate states and defining data and variables for one test; (5) generating executable program code as an implementation of the program specification and derived from the FSM, wherein the program code is in the form of a program shell; and (6) generating executable test programs for testing the implementation of the program specification, each test program being generated by merging into a copy of the program shell one of said path files.
Claim 3
Dependent Claim
30 words
The method of claim 1, wherein the FSM is an extended finite state machine (EFSM), and step 4 includes the step of maintaining context during the traversal of the EFSM.
Claim 4
Dependent Claim
21 words
The method of claim 1, wherein the traversal of step 4 is carried out by traversing all paths through the FSM.
Claim 5
Dependent Claim
30 words
The method of claim 1, further including, before step 4, a step of generating constraints for confining the traversal of step 4 to a subset of states of the FSM.
Claim 6
Dependent Claim
73 words
The method of claim 1, wherein step 3 includes the steps of: generating at least one value partition for each of at least one variable value to be tested, each said partition corresponding to a value range to be tested for said at least one variable; and generating a transition for each said partition, said transition including test information for assigning to said at least one variable a value corresponding to said partition.
Claim 7
Dependent Claim
39 words
The method of claim 1, wherein at least one said transition includes a predicate correlated with it, and including, as part of step 4, the step of determining whether said predicate is true, and if so, taking the transition.
Claim 8
Dependent Claim
30 words
The method of claim 1, wherein at least one said transition includes an action correlated with it, and including, as part of step 4, the step of executing the action.
Claim 9
Dependent Claim
40 words
The method of claim 1, wherein at least one said transition includes a test data annotation correlated with it, and including, as part of step 4, the step of generating a test routine for testing a function of the implementation.
Claim 10
Dependent Claim
52 words
The method of claim 2, further including the steps of: combining the EFSM produced in step 3 with a second EFSM for generating a multiple-model architecture; and carrying out step 4 on the multiple-model architecture for generating path files for use in steps 5-6 to generate test programs for the multiple-model architecture.
Claim 11
Dependent Claim
53 words
The method of claim 5, wherein said value partition includes a plurality of subsidiary partitions, and wherein step 3 includes the steps of: generating a branch transition for each said subsidiary partition, said branch transition including test information for assigning to said at least one variable a value corresponding to said subsidiary partition.
Claim 12
Dependent Claim
66 words
The method of claim 6, wherein at least one said transition includes a predicate correlated with it, and including, as part of step 4, the step of generating a first branch transition and a second branch transition for said predicate, said first branch transition representing a test case where said predicate is true, and said second branch transition representing a case where said predicate is false.
Claim 13
Independent Claim
356 words
A method for testing an implementation of a program to insure that the implementation conforms to a natural language and computer readable program specification that specifies the functions the program will have to fulfill, defines the types and uses of variables, defines parameters and their relationships, and other system requirements, the method being carried out in a processor and including the steps of: (1) accepting as a input the natural language and computer readable program specification, wherein data relationships are expressed in the program specification with predefined syntax and semantics; (2) parsing the program specification in accordance with said predefined syntax and semantics to generate data structures and relationships between the data structures which represent parameters and functionality expressed in the program specification; (3) modeling the program specification by transforming the parsed program specification according to said semantics into a finite state machine (FSM), which represents data relationships in the program specification and which includes at least a starting state, an ending state, a plurality of intermediate states, and a set of transitions defining conditions under which the FSM is traversed from a given state to a subsequent state; (4) generating a test specification comprised of a set of computer readable path files, wherein the path file are generated by traversing paths in the FSM, each path file defining a path beginning at the starting state and ending at the ending state and including a unique traversal of said set of transitions and intermediate states and defining data and variables for one test; (5) generating executable program code as an implementation of the program specification and derived from the FSM, wherein the program code is in the form of a program shell; (6) generating executable test programs for testing the implementation of the program specification, each test program being generated by merging into a copy of the program shell one of said path files; (7) executing each said test program; (8) determining whether outputs of each said test program are consistent with the program specification; and (9) for each output which is not consistent with the program specification, generating a diagnostic indicating failure of the implementation.
Claim 14
Independent Claim
356 words
A method for testing an implementation of a program to insure that the implementation conforms to a natural language and computer readable program specification that specifies the functions the program will have to fulfill, defines the types and uses of variables, defines parameters and their relationships, and other system requirements, the method being carried out in a processor and including the steps of: (1) accepting as a input the natural language and computer readable program specification, wherein data relationships are expressed in the program specification with predefined syntax and semantics; (2) parsing the program specification in accordance with said predefined syntax and semantics to generate data structures and relationships between the data structures which represent parameters and functionality expressed in the program specification; (3) modeling the program specification by transforming the parsed program specification according to said semantics into a finite state machine (FSM), which represents data relationships in the program specification and which includes at least a starting state, an ending state, a plurality of intermediate states, and a set of transitions defining conditions under which the FSM is traversed from a given state to a subsequent state; (4) generating a test specification comprised of a set of computer readable path files, wherein the path file are generated by traversing paths in the FSM, each path file defining a path beginning at the starting state and ending at the ending state and including a unique traversal of said set of transitions and intermediate states and defining data and variables for one test; (5) generating executable program code as an implementation of the program specification and derived from the FSM, wherein the program code is in the form of a program shell; (6) generating executable test programs for testing the implementation of the program specification, each test program being generated by merging into a copy of the program shell one of said path files; (7) executing each said test program; (8) determining whether outputs of each said test program are consistent with the program specification; and (9) for each output which is not consistent with the program specification, generating a diagnostic indicating failure of the implementation.
Claim 15
Dependent Claim
30 words
The method of claim 12, wherein the FSM is an extended finite state machine (EFSM), and step 4 includes the step of maintaining context during the traversal of the EFSM.
Claim 16
Dependent Claim
21 words
The method of claim 12, wherein the traversal of step 4 is carried out by traversing all paths through the FSM.
Claim 17
Dependent Claim
30 words
The method of claim 12, further including, before step 4, a step of generating constraints for confining the traversal of step 4 to a subset of states of the FSM.
Claim 18
Dependent Claim
73 words
The method of claim 12, wherein step 3 includes the step of: generating at least one value partition for each of at least one variable value to be tested, each said partition corresponding to a value range to be tested for said at least one variable; and generating a transition for each said partition, said transition including test information for assigning to said at least one variable a value corresponding to said partition.
Claim 19
Dependent Claim
30 words
The method of claim 12, wherein at least one said transition includes an action correlated with it, and including, as part of step 4, the step of executing the action.
Claim 20
Dependent Claim
40 words
The method of claim 12, wherein at least one said transition includes a test data annotation correlated with it, and including, as part of step 4, the step of generating a test routine for testing a function of the implementation.
Claim 21
Dependent Claim
52 words
The method of claim 13, further including the steps of: combining the EFSM produced in step 3 with a second EFSM for generating a multiple-model architecture; and carrying out step 4 on the multiple-model architecture, for generating path files for use in steps 5-6 to generate test programs for the multiple-model architecture.
Claim 22
Dependent Claim
53 words
The method of claim 16, wherein said value partition includes a plurality of subsidiary partitions, and wherein step 3 includes the steps of: generating a branch transition for each said subsidiary partition, said branch transition including test information for assigning to said at least one variable a value corresponding to said subsidiary partition.
Claim 23
Dependent Claim
39 words
The method of claim 16, wherein at least one said transition includes a predicate correlated with it, and including, as part of step 4, the step of determining whether said predicate is true, and if so, taking the transition.
Claim 24
Dependent Claim
66 words
The method of claim 21, wherein at least one said transition includes a predicate correlated with it, and including, as part of step 4, the step of generating a first branch transition and a second branch transition for said predicate, said first branch transition representing a test case where said predicate is true, and said second branch transition representing a case where said predicate is false.
Claim 25
Dependent Claim
315 words
Apparatus for generating tests for an implementation of a program specification to insure that the implementation conforms to a natural language and computer readable program specification that specifies the functions the program will have to fulfill, defines the types and uses of variables, defines parameters and their relationships, and other system requirements, the apparatus operating in a processor and comprising: means for accepting as an input the natural language and computer readable program specification, wherein data relationships are expressed in the program specification with predefined syntax and semantics; a parser which parses the modeled program specification in accordance with said predefined syntax and semantics to generate data structures and relationships between the data structures which represent parameters and functionality expressed in the program specification; a state machine generator which transforms the parsed program specification according to said semantics to generate a finite state machine (FSM) model of the program specification, which represents data relationships in the program specification and includes at least a starting state, an ending state, a plurality of intermediate states, and a set of transitions defining conditions under which the FSM is traversed from a given state to a subsequent state; a path file generator which traverses paths in the FSM for generating a set of path files forming a test specification, each path file defining a path beginning at the starting state and ending at the ending state and including a unique traversal of said set of transitions and intermediate states and defining data and variables for one test; a program shell generator for generating executable program code as an implementation of the program specification, wherein the implementation is in the form of a program shell and is the implementation to be tested; and a test program generator which generates executable test programs for testing the implementation by merging one of said path files into a copy of the program shell.
Claim 26
Dependent Claim
315 words
Apparatus for generating tests for an implementation of a program specification to insure that the implementation conforms to a natural language and computer readable program specification that specifies the functions the program will have to fulfill, defines the types and uses of variables, defines parameters and their relationships, and other system requirements, the apparatus operating in a processor and comprising: means for accepting as an input the natural language and computer readable program specification, wherein data relationships are expressed in the program specification with predefined syntax and semantics; a parser which parses the modeled program specification in accordance with said predefined syntax and semantics to generate data structures and relationships between the data structures which represent parameters and functionality expressed in the program specification; a state machine generator which transforms the parsed program specification according to said semantics to generate a finite state machine (FSM) model of the program specification, which represents data relationships in the program specification and includes at least a starting state, an ending state, a plurality of intermediate states, and a set of transitions defining conditions under which the FSM is traversed from a given state to a subsequent state; a path file generator which traverses paths in the FSM for generating a set of path files forming a test specification, each path file defining a path beginning at the starting state and ending at the ending state and including a unique traversal of said set of transitions and intermediate states and defining data and variables for one test; a program shell generator for generating executable program code as an implementation of the program specification, wherein the implementation is in the form of a program shell and is the implementation to be tested; and a test program generator which generates executable test programs for testing the implementation by merging one of said path files into a copy of the program shell.
Claim 27
Dependent Claim
19 words
The apparatus of claim 23, wherein the path file generator comprises means for traversing all paths through the FSM.
Claim 28
Dependent Claim
43 words
The apparatus of claim 23, further comprising a multiple model generator which generates a second FSM and combines it with the FSM to form a combined FSM so that the path file generator traverses paths in the combined FSM to generate path files.
Claim 29
Dependent Claim
30 words
The apparatus of claim 24 wherein the path file generator comprises means for generating constraints for confining the traversal of the FSM to a subset of states of the FSM.
Claim 30
Dependent Claim
329 words
A computer program product for generating tests for an implementation of a program to insure that the implementation conforms to a natural language and computer readable program specification that specifies the functions the program will have to fulfill, defines the types and uses of variables, defines parameters and their relationships, and other system requirements, the computer program product comprising a computer usable medium having computer readable program code thereon including: program code for accepting as an input a computer readable and natural language program specification, which expresses data relationships in predefined syntax and semantics; program code for parsing the program specification in accordance with said predefined syntax and semantics to generate data structures and relationships between the data structures which represent parameters and functionality expressed in the program specification; program code for modeling the program specification by transforming the parsed program specification according to said semantics into a finite state machine (FSM), which represents data relationships in the program specification and which includes at least a starting state, an ending state, a plurality of intermediate states, and a set of transitions defining conditions under which the FSM is traversed from a given state to a subsequent state; program code for generating a test specification comprised of a set of computer readable path files, wherein the path files are generated by traversing paths in the FSM, each path file defining a path beginning at the starting state and ending at the ending state and including a unique traversal of said set of transitions and intermediate states and defining data and variables for one test; program code for generating executable program code as an implementation of the program specification and derived from the FSM, wherein the program code is in the form of a program shell; and program code which generates executable test programs for testing the implementation of the program specification, each test program being generated by merging one of said path files into a copy of the program shell.
Claim 31
Dependent Claim
329 words
A computer program product for generating tests for an implementation of a program to insure that the implementation conforms to a natural language and computer readable program specification that specifies the functions the program will have to fulfill, defines the types and uses of variables, defines parameters and their relationships, and other system requirements, the computer program product comprising a computer usable medium having computer readable program code thereon including: program code for accepting as an input a computer readable and natural language program specification, which expresses data relationships in predefined syntax and semantics; program code for parsing the program specification in accordance with said predefined syntax and semantics to generate data structures and relationships between the data structures which represent parameters and functionality expressed in the program specification; program code for modeling the program specification by transforming the parsed program specification according to said semantics into a finite state machine (FSM), which represents data relationships in the program specification and which includes at least a starting state, an ending state, a plurality of intermediate states, and a set of transitions defining conditions under which the FSM is traversed from a given state to a subsequent state; program code for generating a test specification comprised of a set of computer readable path files, wherein the path files are generated by traversing paths in the FSM, each path file defining a path beginning at the starting state and ending at the ending state and including a unique traversal of said set of transitions and intermediate states and defining data and variables for one test; program code for generating executable program code as an implementation of the program specification and derived from the FSM, wherein the program code is in the form of a program shell; and program code which generates executable test programs for testing the implementation of the program specification, each test program being generated by merging one of said path files into a copy of the program shell.
Claim 32
Dependent Claim
21 words
The computer program product of claim 27, wherein the path file generator comprises means for traversing all paths through the FSM.
Claim 33
Dependent Claim
45 words
The computer program product of claim 27, further comprising a multiple model generator which generates a second FSM and combines it with the FSM to form a combined FSM so that the path file generator traverses paths in the combined FSM to generate path files.
Claim 34
Dependent Claim
32 words
The computer program product of claim 28 wherein the path file generator comprises means for generating constraints for confining the traversal of the FSM to a subset of states of the FSM.
References Cited (Backward Citations)
US4696003A
Cited
US5121497A
Cited
US4991176A
Cited
US5038307A
Cited
US5164912A
Cited
US5218605A
Cited
US5513316A
Cited
US5657438A
Cited
US5388258A
Cited
US5572727A
Cited
US5481717A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-03-14 | 2003-09-13 | 2004-03-14 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-03-14 | 2007-09-13 | 2008-03-14 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-03-14 | 2011-09-13 | 2012-03-14 | $7700.00 | Window Closed / Lapsed |