Method, apparatus, and system for automatic test generation from statecharts
First Claim
1. A method for creating a plurality of output test vectors from a statechart, wherein the statechart specifies requirements of a system function to be executed by a system-performing device and comprises a plurality of states, a plurality of variables and a plurality of transitions, wherein at least one transition of the plurality of transitions comprises a condition expressed in terms of at least one variable in the plurality of variables, comprising:
- providing a processor, and data storage having machine-language instructions executable by the processor to perform a method comprising;
generating a plurality of forward-reached-transition environments using a forward-propagation pass through the statechart, wherein each forward-reached-transition environment in the plurality of forward-reached-transition environments is generated for a forward-reached transition forward propagated during the forward-propagation pass;
determining a transition was unreached during the forward-propagation pass;
responsive to the determination was unreached during the forward-propagation pass, generating a plurality of backward-reached-transition environments via a backward-propagation pass through the statechart, wherein each backward-reached-transition environment in the plurality of backward-reached-transition environments is generated for a backward-reached transition propagated during the backward-propagation pass;
determining a transition was unreached during both the forward-propagation pass and the backward-propagation pass;
responsive to the determination that a transition was unreached during both the forward-propagation and backward-propagation pass, performing alternating passes of forward-propagation and backwards-propagation until an insufficient number of transitions has been reached by a pass of forward-propagation and backward-propagation;
generating a plurality of output test vectors from the plurality of forward-reached-transition environments and the plurality of backward-reached-transition environments; and
outputting the plurality of output test vectors.
1 Assignment
0 Petitions
Accused Products
Abstract
An apparatus and methods for generating a plurality of output test vectors from a statechart are provided. The statechart may specify requirements of a system function to be executed by a system-performing device. The statechart comprises a plurality of states, a plurality of transitions, and a plurality of variables. A forward-propagation pass through the statechart may be performed to generate a plurality of forward-reached-transition environments. A backward-propagation pass through the statechart may be performed to generate a plurality of backward-reached-transition environments. The plurality of output test vectors is generated from the plurality of forward-reached-transition environments and/or the plurality of backward-reached-transition environments. A test driver may execute a plurality of tests on the system-performing device, wherein the plurality of tests are based on the plurality of output test vectors.
-
Citations
17 Claims
-
1. A method for creating a plurality of output test vectors from a statechart, wherein the statechart specifies requirements of a system function to be executed by a system-performing device and comprises a plurality of states, a plurality of variables and a plurality of transitions, wherein at least one transition of the plurality of transitions comprises a condition expressed in terms of at least one variable in the plurality of variables, comprising:
providing a processor, and data storage having machine-language instructions executable by the processor to perform a method comprising; generating a plurality of forward-reached-transition environments using a forward-propagation pass through the statechart, wherein each forward-reached-transition environment in the plurality of forward-reached-transition environments is generated for a forward-reached transition forward propagated during the forward-propagation pass; determining a transition was unreached during the forward-propagation pass; responsive to the determination was unreached during the forward-propagation pass, generating a plurality of backward-reached-transition environments via a backward-propagation pass through the statechart, wherein each backward-reached-transition environment in the plurality of backward-reached-transition environments is generated for a backward-reached transition propagated during the backward-propagation pass; determining a transition was unreached during both the forward-propagation pass and the backward-propagation pass; responsive to the determination that a transition was unreached during both the forward-propagation and backward-propagation pass, performing alternating passes of forward-propagation and backwards-propagation until an insufficient number of transitions has been reached by a pass of forward-propagation and backward-propagation; generating a plurality of output test vectors from the plurality of forward-reached-transition environments and the plurality of backward-reached-transition environments; and outputting the plurality of output test vectors. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
8. A test generator, comprising:
-
a processor; data storage; and machine-language instructions stored in the data storage and executable by the processor to perform functions including; receiving a statechart; generating a plurality of forward-reached-transition environments using a forward-propagation pass through the statechart, wherein each forward-reached-transition environment in the plurality of forward-reached-transition environments is generated for a forward-reached transition forward propagated during the forward-propagation pass; determining a transition was unreached during the forward-propagation pass; responsive to the determination was unreached during the forward-propagation pass, generating a plurality of backward-reached-transition environments via a backward-propagation pass through the statechart, wherein each backward-reached-transition environment in the plurality of backward-reached-transition environments is generated for a backward-reached transition propagated during the backward-propagation pass; determining a transition was unreached during both the forward-propagation pass and the backward-propagation pass; responsive to the determination that a transition was unreached during both the forward-propagation and backward-propagation pass, performing alternating passes of forward-propagation and backwards-propagation until an insufficient number of transitions has been reached by a pass of forward-propagation and backward-propagation; generating a plurality of output test vectors from the plurality of forward-reached-transition environments and the plurality of backward-reached-transition environments; and outputting the plurality of output test vectors. - View Dependent Claims (9, 10, 11, 12, 13, 14)
-
-
15. A method for performing a backward-propagation pass through a statechart, wherein the statechart specifies requirements of a system function to be executed by a system-performing device and comprises a plurality of states, a plurality of variables and a plurality of transitions, wherein at least one transition of the plurality of transitions comprises a condition expressed in terms of at least one variable in the plurality of variables, comprising:
-
retrieving a candidate-backward-reachable transition (CBRT) from an unreached-transition list; generating an associated timestep-sequence object (ATSO) from a sequence list, wherein the ATSO is associated with the CBRT; determining if a complete-constraint expression of the generated ATSO is satisfied; and responsive to determining that the complete-constraint expression of the generated ATSO is satisfied, updating a CBRT environment as a backward-reached transition; responsive to determining that the complete-constraint expression of the generated ATSO is not satisfied, generating one or more new-timestep-sequence objects (NTSOs); and setting an unresolved constraint of each NTSO to be a computed unresolved constraint of the ATSO after simulating effects of the ASTO. - View Dependent Claims (16, 17)
-
Specification