Type and range propagation through data-flow models

• US 8,984,488 B2
• Filed: 01/14/2011
• Issued: 03/17/2015
• Est. Priority Date: 01/14/2011
• Status: Active Grant

• Current Assignee: Honeywell International Inc.
• Original Assignee: Honeywell International Inc.
• Inventors: Bhatt, Devesh, Hickman, Steve, Patodi, Manish, Oglesby, David V., Schloegel, Kirk
• Primary Examiner(s): Chen, Xi D
• Application Number:
  US13/006,750
• Publication Number:
  US 20120185729A1
• Time in Patent Office: 1,523 Days
• Field of Search: None
• US Class Current: 717/126
• CPC Class Codes: G06F 11/3604 Software analysis for verifying properties of programs byte-code verification G06F9/44589
• CPC Class Codes: G06F 11/3684 for test design, e.g. generating new test cases

Abstract

Systems and methods for type and range propagation through data flow models are provided. In one embodiment, a test generating system for processing data flow diagrams, the system comprises: a processor programmed to perform a test generation process; and at least one memory device coupled to the processor, the at least one memory device including a data flow diagram. The test generation process computes range information and data type information for outputs of one or more functional blocks defined by the data flow diagram by applying transformations to input range information for inputs of each of the one or more functional blocks. The transformations are at least in part performed by applying specific mathematical and functional effects that are pre-defined for each of the one or more functional blocks based on block type.

Claims

1. A method for conducting an analysis of a data flow diagram, the method comprising:

propagating range information, language independent representations, and data type information to one or more inputs of a functional block defined by a data flow diagram;

performing a predefined transformation to the input range information to determine an output range, language independent representation, and data type information for the functional block, wherein the predefined transformation is at least in part performed by applying specific mathematical and functional effects defined for the functional block; and

propagating the output range, language independent representation, and data type information to any subsequent block defined by the data flow diagram;

wherein the range information and data type information is computed for a parent block type functional block by recursively performing a range and hierarchical data type information computation on one or more sub-models that define the parent block type functional block, wherein the parent block type functional block is hierarchically decomposed into one or more sub-models to specify functions performed as part of the parent block type functional block;

wherein the hierarchical data type information computation determines at least one data type based on the internal structures of variables used by the one or more sub-models; and

wherein the range type information computation determines input and output ranges of the one or more sub-models.

2. The method of claim 1, wherein when propagation did not provide input range information for every input of the functional block, the method further comprises:

performing a contextual analysis of the functional block to resolve each instance of missing input range information.

3. The method of claim 2, wherein when the contextual analysis identifies a feedback loop, the test generation process computes input range information by computing loop invariants;

wherein computing loop invariants comprises analyzing a feedback signal for either a monotonically increasing or decreasing variable value; and

wherein computing loop invariants comprises analyzing the data flow diagram for signal value limiting structures.

4. The method of claim 1, further comprising obtaining user specified information to resolve missing input range information.

5. The method of claim 1, wherein a criteria for determining output range and data type information for the functional block is either specified via a range transformation data base, or is specified within objects that define the data flow diagram.

6. A test generating system for processing data flow diagrams, the system comprising:

a processor programmed to perform a test generation process; and

at least one memory device coupled to the processor, the at least one memory device including a data flow diagram;

wherein the test generation process determines range information, language independent representation, and data type information for outputs of one or more functional blocks defined by the data flow diagram by applying transformations to input range information for inputs of each of the one or more functional blocks, wherein the transformations propagate the range information, language independent representation, and data type information through the one or more functional blocks;

wherein the transformations are at least in part performed by applying specific mathematical and functional effects that are pre-defined for each of the one or more functional blocks based on block type; and

wherein the range information and data type information is computed for a parent block type functional block by recursively performing a range and data type information computation on one or more sub-models that define the parent block type functional block, wherein the parent block type functional block is hierarchically decomposed into one or more sub-models to specify functions performed as part of the parent block type functional block;

wherein the data type information computation determines at least one data type based on the internal structures of variables used by the one or more sub-models; and

wherein the range type information computation determines input and output ranges of the one or more sub-models.

7. The system of claim 6, wherein the transformation is further performed by the test generation process for at least a first functional block of one or more functional blocks based on a contextual analysis.

8. The system of claim 7, wherein when the contextual analysis identifies a feedback loop, the test generation process computes input range information by computing loop invariants.

9. The system of claim 8, wherein computing loop invariants comprises:

analyzing a feedback signal for either a monotonically increasing or decreasing variable value; and

analyzing the data flow diagram for signal value limiting structures.

10. The system of claim 7, wherein the test generation process calls for user specified range and data type information when the contextual analysis does not provide a range solution for at least one input of a first functional block of one or more functional blocks.

11. The system of claim 10, wherein the user specified range and data type information is stored in a feedback loop range file.

12. The system of claim 6, wherein the at least one memory device further includes a range transformation data base accessed by the test generation process to determine the specific mathematical and functional effects to be applied to each of the one or more functional blocks.

13. The system of claim 6, wherein the specific mathematical and functional effects to be applied to each of the one or more functional blocks are specified within objects that define the data flow diagram.

14. The system of claim 6, wherein the test generation process calls for user specified range and data type information when the specific mathematical and functional effects are not defined for one or more of the functional blocks.

15. The system of claim 6, wherein the test generation process calculates at least one output range for a first functional block of the one or more functional blocks by interpolating outputs from a function performed by the first functional block across a range of inputs to the first functional block.

16. The system of claim 6, wherein the input range information for at least one of the one or more functional blocks comprises a split range and the output range information is determined by a union of all combinations of sub-ranges.

17. The system of claim 16, wherein at least two sub-ranges of the split input range are simplified prior to determining the union of all combinations of sub-ranges.

18. The system of claim 6, wherein the input range information for at least a first block of the one or more functional blocks comprises a split range, a function associated with the first block is continuous and monotonic, and at least one input value for the first block includes a continuous range of values around zero whose magnitude is larger than a largest gap in any split range when applied to the function;

and

wherein an output range for the first block is computed with no gaps based only upon the continuous range, a minimum min value, and a maximum max value.

19. A non-transitory computer readable media device having computer-executable instructions for performing range and type information transformation for functional blocks of a data flow diagram, the method comprising:

determining range information, language independent representations, and data type information for outputs of one or more functional blocks defined by the data flow diagram by applying transformations to input range information for inputs of each of the one or more functional blocks, wherein the transformations propagate the range information, language independent representations, and data type information through the one or more functional blocks, wherein the transformations are at least in part performed by applying specific mathematical and functional effects that are pre-defined for each of the one or more functional blocks based on block type;

wherein the range information and data type information is computed for a parent block type functional block by recursively performing a range and data type information computation on one or more sub-models that define the parent block type functional block, wherein the parent block type functional block is hierarchically decomposed into one or more sub-models to specify functions performed as part of the parent block type functional block;

wherein the data type information computation determines at least one data type based on the internal structures of variables used by the one or more sub-models; and

wherein the range type information computation determines input and output ranges of the one or more sub-models.