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

• US 8,307,342 B2
• Filed: 06/10/2008
• Issued: 11/06/2012
• Est. Priority Date: 05/14/2008
• Status: Active Grant

• Current Assignee: Honeywell International Inc.
• Original Assignee: Honeywell International Inc.
• Inventors: Oglesby, David, Schloegel, Kirk, Bhatt, Devesh, Hickman, Stephen O.
• Primary Examiner(s): DENG, ANNA CHEN
• Application Number:
  US12/136,146
• Publication Number:
  US 20090287963A1
• Time in Patent Office: 1,610 Days
• Field of Search: 717/124, 717/126
• US Class Current: 717/124
• CPC Class Codes: G06F 11/3684 for test design, e.g. generating new test cases

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.

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.

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.