Lecture
The functioning of any program can be viewed as processing a data flow transmitted from the input of the program to its output (see Section 13.1). The input data is sequentially used to determine a series of intermediate results, up to obtaining the required set of output data. The task of testing and analyzing the data flow consists in establishing the correctness of its processing and in detecting errors in the program under test. This task can be solved statically — without executing the program (by analysis of its text), and dynamically — by actually executing the program on a computer in machine code with various initial data.
The sets of actions for converting source data into output data can be formalized using data flow diagrams (DFD — Data Flow Diagrams). For this purpose, a system of graphical elements is used, containing boxes with descriptions of entities and numbers, as well as process arrows connecting them:
external entities — objects that are sources or consumers of information, identified by their content and numbers;
processes that move objects from one action to another, converting source data into resulting data;
data stores of objects or data, where they are temporarily placed for storage;
data flows — information transmitted from a source to a consumer.
For constructing DFD diagrams, the syntax and semantics of the graphical elements have been formalized: those reflecting the movement of objects — program procedures; descriptions of external entities — sources and consumers of data; and their storage. It is recommended to first define the set of actions describing what the program procedures must perform. Then build a model of the environment — external entities that generate processes and specific behavior when processing data. Sets of the simplest DFD diagrams — program statements — are combined into hierarchical structures reflecting the data flows in program modules or functional components consisting of a number of modules.
The data involved in computations, in high-level programming languages, are explicitly defined by name, type, and methods of access and use. This makes it possible to view the program as a multigraph, given by the structure of control transfers (control flow) and by the graph of the transformations of the data involved in the computations (data flow). The intersection of the control flow and the data flow occurs in branch statements: condition checks and loops. Joint analysis of the control and data flows makes it possible to verify the correctness of the implementation of variable definition domains along the program's execution paths.
The consequences of errors in a program can manifest as small changes in certain variables during computation, or as a complete distortion or absence of the required values at the output. It is advisable to test a program module on ordered sets of data, taking into account the degree of their influence on the output results. From this standpoint, for subsequent analysis it is advisable to distinguish two kinds of processing data:
completely changing the domain of definition and the values of the processing results;
changing the results within some limited, correct domain of definition.
The first type of processing correspond to source data at critical points and at the boundaries of the domains of variable change. At such critical values, the program's execution path may change, as a result of which the greatest change in results is possible. Therefore, testing of data processing is usually aimed, first of all, at verifying the execution of programs for variable values that influence the choice of path and the logic of program functioning (the strategy of isolating variable domains). Boundary conditions are situations arising in the immediate vicinity of the boundaries of the domains of fundamental change of the processed variables. The number of such critical values of each variable may be several orders of magnitude smaller than the number of values across the entire interior of the domain of change of that quantity.
Most critical values (predicates) can significantly influence the results and are subject to the most thorough testing. In this respect, testing of data processing is, in content, close to testing of program structure (see Section 13.4). In this type of testing, paths are formed during the analysis and processing of data at successive condition statements in the program text. The set of combinations of source data in the tests directly influences the degree of testing coverage of the complete set of program segments. By comparing the verified paths with the paths identified from the program graph under various criteria, it is possible to assess the achieved completeness of module testing and, approximately, the degree of its correctness.
The second type of processing corresponds to data in a bounded (or unbounded) domain of definition, which can be divided into some set of adjoining domains (subdomains). A change in the data within such a domain does not affect the program's execution path. Therefore, to verify the functioning of the program, out of the entire set of values it is sufficient to use in testing only a few values within and near the boundaries of the domain. The number of values used for testing when processing this type may be several orders of magnitude smaller than the total number of values of each variable in the domain. During testing, the accuracy of the computations performed, the correctness of the scaling and dimensionality of the processed values, and the correctness of the formation of logical values are verified. In this case, testing must cover the entire domain of change of each processed variable and of each resulting value.
When analyzing the processing of data within the domains of their definition, it is advisable to apply testing methods in an orderly manner, in the following sequence:
testing with data values that determine the program's execution paths (the domain strategy);
testing the correctness of writing and reading variables during computations, and the completeness of the composition of output data along all execution paths of the program;
testing the accuracy of the computation results and the correctness of processing each variable;
testing for full compliance with the requirements specification for the composition, values and accuracy of the output data.
In the sequence presented, the particular testing methods make it possible, first of all, to detect primary errors capable of distorting the results to the greatest extent. With limited resources and such a testing sequence, errors that have the least effect on the correctness of the output data may remain in the program. On the basis of such checks, the degree of testing coverage of all conditions defined in the specification can be assessed, and additional testing should be carried out only for individual, insufficiently verified input data.
Testing with data values that determine the program's execution paths (the domain strategy). The paths of the data-processing sequence can depend on any types of the analyzed values. One of the tasks of testing is to verify the comparability of the value types being compared and the identity of their coding conditions (bit width, scale). Critical values — predicates, that influence the choice of paths, in many cases are not fixed, but are formed during data processing and/or the comparison of several variables. In this case, predicates can be formed throughout the entire domain of change of each of the variables, for example, when they turn out to be equal or differ by some constant value.
The predicates that determine the choice of the program's execution paths can be formed as a result of computations on linear sections
of the program. These sections are, on average, small and contain about 5—10 lines of program text. Each bounded domain of source data corresponds to a specific path in the program. The boundary of the domain is determined by the interpretations of the predicates along the path and consists of a set of boundary segments, each of which is determined by a single, simple predicate that selects an arc of the path in the program graph. Each segment of the domain boundary can be open or closed, depending on the condition operator in the predicate. A closed boundary segment belongs to the bounded domain and is formed by predicates with the operators <, > or = . An open boundary segment is not part of the domain and is formed by the operators < , > and F. The total number of predicates on the path is the upper limit on the number of boundary segments of the input-variable domain for the given path, since some predicates on the path may not actually create boundary segments. Such cases arise when a predicate is required for several paths, and on some of them it is re-analyzed on the path.
Thus, a program, with respect to the data flow, can be regarded, first of all, as performing a partitioning of the source-data space into domains, each of which corresponds to a single executed path. Errors in the program can be caused by modification of the boundary of the domain of a given path, leading to an expansion or contraction of the source-data space of the corresponding path. In addition, deformation of domain boundaries can lead to errors that destroy some domains and lose the paths corresponding to them. The causes of such errors can be distortions of the condition-analysis operators, or distortions in the process of computing the predicate values with the condition operator's content otherwise correct. Distortions of the condition-analysis operators can lead both to deformation of the domain boundary and to the appearance of new boundaries or their destruction, as a result of which domains may split apart or merge.
The complexity of the tests grows linearly with an increase in the dimensionality of the source-data space (the number of requirements or variables) and with an increase in the number of predicates on the paths. For many typical modules, the complexity of the tests turns out to be acceptable for practically complete verification of the module. The limitations of the domain-testing method can appear with complex loop organizations, when the number of paths and analyzed conditions increases sharply.
Testing the correctness of the definition and use of data on the program's execution paths. If the program's execution paths correspond to the permissible domains of change of the input data, then it is advisable to verify the correctness of the basic data-processing operations on the identified paths. Each value on the program's execution path is read from memory, and after being used for computations is written to the computer's memory for storage and subsequent processing. The alternation of variable read and write operations can be disrupted as a result of errors in the program. To detect such errors, testing of the correctness of writing and reading real data, or static analysis of these operations from the program's source text, is carried out.
Testing the correctness of processing each variable and the accuracy of the computation results. When it has been shown that the combinations of data and their domains of definition correspond to the correct formation of paths in the program, and there are also no obvious errors in the sequences of definition and use of each variable, it is advisable to carry out testing of the correctness of processing each variable and the accuracy of the computational part of the program. This type of testing is carried out predominantly with real and integer values in the interior of their domains of definition, for fixed-point operations. In addition, additional monitoring of computation accuracy can be performed at the boundary values previously used for testing the paths over the domains of definition.
The set of test values for verifying computations with simple numeric variables should advisably be constructed in an orderly manner, taking into account the following rules:
input test data in the domain of smooth change of the results depending on them should take on, at minimum, values close to the largest and smallest, as well as one or two intermediate values;
testing must be carried out at all special values of the input variables — at points of sharp increase or discontinuity of derivatives, at zero, unit and extremely small numerical values;
input test values must ensure verification of the program at output results having special points of sharp change or discontinuity of derivatives;
if the values of one variable depend on the values of another variable, then they must be tested at special values of the variable combinations (equality of both variables, a small and an extremely large difference between them, zero and unit values).
Thus, for each simple numeric variable, in addition to three points near and at the boundary of the domain of definition, testing of the program is usually required at 3—4 intermediate and at 2—5 special points of input data values. With 10 input variables and complex computations in a program module, up to 50 test values may be required for testing the computations. By grouping and ordering the test values of different variables, their total number can be reduced to 5—10 test sets.
Comments