Method, apparatus, and system for automatic test generation from statecharts

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.

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. 
 
 
     
     
       2. The method of  claim 1 , wherein at least one output test vector is generated for each transition in the plurality of transitions. 
     
     
       3. The method of  claim 1 , further comprising executing a test based on at least one output test vector in the plurality of output test vectors. 
     
     
       4. The method of  claim 1 , further comprising generating a human-readable form of at least one output test vector in the plurality of output test vectors. 
     
     
       5. The method of  claim 1 , wherein the plurality of variables comprises one or more statechart-defined variables, and wherein the forward-propagation pass comprises propagating one or more values of the one or more statechart-defined variables to satisfy at least one condition of a reachable transition. 
     
     
       6. The method of  claim 1 , further comprising:
 detecting at least one specification error in the statechart. 
 
     
     
       7. The method of  claim 6 , wherein detecting at least one specification error in the statechart comprises detecting at least one transition whose condition is infeasible after performing both the forward-propagation pass and the backward-propagation pass. 
     
     
       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. 
 
 
     
     
       9. The test generator of  claim 8 , wherein the machine-language instructions stored in the data storage further comprise instructions to execute at least one test in the plurality of tests. 
     
     
       10. The test generator of  claim 8 , further comprising a user interface. 
     
     
       11. The test generator of  claim 10 , wherein outputting the plurality of tests comprises outputting the plurality of tests via an output unit of the user interface. 
     
     
       12. The test generator of  claim 10 , wherein receiving a statechart comprises receiving a statechart via an input unit of the user interface. 
     
     
       13. The test generator of  claim 10 , wherein machine-language instructions stored in the data storage and executable by the processor further comprise instructions executable to receive a statechart via the user interface. 
     
     
       14. The test generator of  claim 10 , wherein machine-language instructions stored in the data storage and executable by the processor further comprise instructions executable to:
 receive user input from an input unit of the user interface to determine a maximum depth of a backward-propagation pass; and 
 during the backward-propagation pass, inhibiting the generation of a timestep whose depth exceeds the maximum depth. 
 
     
     
       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. 
 
     
     
       16. The method of  claim 15 , further comprising:
 generating an NTSO based on a previous-feasible-timestep-sequence object, wherein the previous-feasible-timestep-sequence object represents at least one feasible action taken at least one timestep prior to the current step. 
 
     
     
       17. The method of  claim 16 , wherein the at least one feasible action comprises an action performed within a state of the plurality of states of the statechart.