Lecture
As noted above (see item 13.1), evaluating the correctness of software systems can be represented as two kinds of work:
verification — the sequential top-down tracing of the implementation of the requirements for the system and the software system by the program components of the lower levels;
determining the completeness of test coverage of their structure and checks that the original requirements for the software system and its components are met.
Test coverage can be evaluated by the degree to which testing covers the set of requirements for the program, or by the coverage of the program's structure by tests. Tracing and covering the set of requirements for programs with tests is difficult to formalize and to evaluate their effect on the correctness achieved for the software system. Existing experience shows that such an analysis is quite accessible to informal analysis, but has a relatively weaker effect on correctness than insufficient testing of program structure. Therefore, the discussion below focuses on evaluating the testing and correctness of structural program coverage.
Analyzing and evaluating the test coverage of program structure makes it possible to detect defects and errors that threaten the most severe consequences during the operation of the software system. The limited effort and time resources available for testing complex program complexes in order to ensure their maximum correctness make it necessary to use the available resources rationally, above all to eliminate the most dangerous errors. Testing fragments of a program's structure does not guarantee the complete absence of errors in them, but it substantially reduces their probability. Fragments of the structure that are skipped during testing may well contain undetected errors, which negatively affect program correctness. Thus, testing the structural coverage of programs is a necessary condition for ensuring their relative correctness, but it is not sufficient to fully ensure the correctness of their operation. At the same time, testing and test coverage of program structure is the most amenable to formalization for evaluating the achieved relative correctness and the probability of the absence of errors in the program, and makes it possible to eliminate the most dangerous errors, which threaten the absence or complete distortion of the required results at the output of the software system.
In practice, in the absence of an orderly analysis of control flows, some routes in the program turn out to be skipped during testing (up to 50%), so the first task that must be solved when testing program structure — is obtaining information about the complete set of actual execution routes in each program and its structural complexity. Such a representation of program coverage makes it possible to orderly monitor the verification of routes achieved and, to some extent, guards against the accidental omission of individual untested routes and their elements.
Full structural coverage of a program by tests is determined by the number of interacting components, the number of links between components, and the complexity of their interaction. The structural complexity and correctness of a program module depends not so much on the size of the program (the number of lines of text) as on the number of separate paths-routes of its execution that exist in the program. In the limit, to ensure complete structural correctness, all routes of possible data processing must be checked when the program is created, and this in turn determines the complexity of testing it.
In a number of cases, a fairly high adequacy has been confirmed for using the structural complexity of programs for of estimating testing effort, the probability of undetected errors, and the cost of developing program modules and components as a whole. The complexity of testing the structure of program modules can be evaluated by the number of routes needed to verify them, or more fully — by the total number of conditions that must be specified in tests to execute all routes of the program. It is convenient to analyze testing criteria, test coverage, and the identification of testable routes using graph models of programs. When planning the testing of program structure, above all two tasks: forming criteria for identifying routes for testing and choosing strategies for ordering the identified routes arise.
Route selection criteria for testing correspond to the criteria for determining the structural complexity of program modules. The following criteria are mainly used:
X1 — coverage of the program graph by the minimum number of routes that cover each arc of the graph at least once;
X2 — identification of all linearly independent routes that differ from the others by at least one arc in the route;
X3 — identification of routes for all possible combinations of arcs included in the routes.
Testing can be planned according to one of the criteria, or by successively using stricter criteria for identifying routes, under which the scope and complexity of testing increase accordingly.
Loops in programs usually lead to a significant increase in the number of routes.
Strategies for ordering routes. The importance indicator of a route for testing a program and for evaluating its correctness can take into account the complexity of the route and of the tests for verifying it: the number of statements, conditional branches and loops in the route; the frequency of its execution during the operational functioning of the software system; and the complexity of obtaining the corresponding reference data. First of all, to establish the correctness of a program it is advisable to check the main group of routes with extreme values of the chosen complexity indicator, within the resources allocated for testing. Given the available resource constraints, some part of the routes may remain unverified, and this characterizes the achieved correctness of the given program according to the chosen criterion.
Ordering routes when planning testing is based mainly on using three characteristics of program modules:
strategy 1 takes into account the number of lines of program text in the selected routes, or the estimated duration of their execution during program operation;
strategy 2 analyzes the number of alternatives or conditional branches that determine the formation of each route;
strategy 3 is based on using the probability of route execution during actual program operation.
These testing strategies make it possible to focus the developer's attention on analyzing the program components that are most important for correctness. Under strategy 1 the routes subject to primary testing are those that are longest in number of lines and/or execution time. These usually correspond to the routes with the largest volume of computations and variable transformations. This strategy is advisable when planning the testing of programs that have a computational character of data processing, with a small number of logical conditions and program execution routes.
Under strategy 2 priority is given to the routes that are most complex in terms of the number of conditions analyzed. This strategy is preferable when testing logical programs with a small volume of computations. Under both strategies, the routes that are simple in computation or logic remain for the final stages of testing, and these reflect the program's potential structural incorrectness. This corresponds to the traditional strategy of many program developers: to prepare, at first, tests with as broad a coverage as possible of the computational or logical components of the program, and to achieve as quickly as possible the highest possible level of their correctness.
When ordering routes by strategy 3 the main difficulty consists in estimating and taking into account the branching probabilities in conditional transfers and switches, as well as the number of loop iterations. Their values must be specified by the program developers, which is quite labor-intensive and subjective. Nevertheless, this strategy makes it possible to plan testing in the greatest detail and to evaluate the limiting level of program correctness.
The effectiveness of testing is determined by the completeness of checking a program module, or by the probability that undetected errors are present, depending on the resource costs: for creating tests, executing programs, and analyzing testing results. The costs largely depend on the total complexity of forming the tests that verify the program's execution routes. On each arc of the program graph, between conditional transfers, computations and variable transformations are performed, and their volume can vary within wide limits. To simplify the analysis and evaluation of testing program structure, let us assume that the duration and complexity of computations on the arcs of program graphs are the same and relatively small. Some vertices of the program graph may be formed as a result of the convergence of arcs without subsequent branching. Such vertices do not affect the number of routes, and they can be combined with the nearest subsequent vertex at which branching occurs. Under these assumptions, the complexity of the test that verifies each i-th route is, to a first approximation, proportional to the number of arcs of the program graph included in that route, or to the number of Et conditions that must be specified in the test.
Experimentally confirmed is the adequacy of using the structural complexity of programs for evaluating the effort of testing, as well as the probability that undetected errors are present and the cost of developing program modules as a whole. The testing complexity of a PM
can be evaluated by the number of routes Mx, needed to verify them, or more fully by the total number of conditions Ex, that must be specified in tests to traverse all routes of the program identified by the X-th criterion:
where E i — is the number of predicate conditions determining the i-th route. The execution routes of a program module can be divided into two kinds:
routes for executing predominantly the computational part of the program and the transformation of continuous variables;
routes for making logical decisions and transforming logical variables.
Routes of the first kind is usually logically simpler and shorter than the second kind, and is intended for transforming quantities that are quantized measurement results of some continuous physical characteristics (continuous variables). The values of such variables are related by smoothness conditions, i.e., conditions of small changes in the derivatives of these variables with respect to time or other parameters. When evaluating the complexity of a program's computational routes, it is necessary to take into account the number of operands involved in the computations. In addition, the input and output data during testing must take on several values. Across the entire range of input variables, several characteristic points should be chosen (limiting values and several intermediate ones) at which the program is checked. At special points of values and combinations of variables, and at points of discontinuity of the function, additional checks must be planned. Thus, the complexity of checking a program module will be determined by the number of routes Mx of program execution and the number of operands processed, i, on each i-th route, multiplied by the number of values s/7 for each input j-th quantity on that route:
Calculating the testing complexity indicator of a program module according to such a scheme has considerable uncertainty due to the arbitrariness in choosing the number of values ni(mainly special points) when varying the input data in the test. At the same time, the share of the computational part in many complex software systems is relatively small.
The second kind of routes is the result of the operation of decision-making schemes and the transformation of logical variables. For logical variables there is no strong correlation between neighboring values, and each change in a variable can determine different regions of resulting values. Such a transformation of variables is provided by algorithms with a complex logical structure containing a number of checks of logical conditions, loops for searching and selecting variables, as well as logical transformations of variables. As a result, a multitude of routes for processing the input data is formed in the program, and these determine the complexity of the program's structure.
The structural complexity of a program module can be calculated from the number of routes Mx in the program and the complexity of each i-th route Ei. Together these indicators determine the minimum complexity of the £*-tests for checking the program module (13.1), and consequently the effort required for its development and testing and the probability of missing a logical error in the program. Program modules are the most numerous components in a software system and require, in total, the largest expenditure of resources for testing. The cost of testing each module is directly proportional to its complexity, which depends on its structure and the volume of computations, i. When testing a program module it is necessary to specify and analyze the number of parameter values:
The total resource costs for testing a module are proportional to the value of its complexity Bx and, taking into account the unit cost of creating each test — c, are determined by the expression:
The value of the factor c depends on the degree of automation of the testing and test-generation process. In highly automated systems, the manual labor costs for preparing and analyzing test data are reduced, but the machine time costs required for generating tests and for automatically processing testing results increase. Depending on these factors, the values of the factor c can differ several times over, and they should be determined experimentally for each test automation system.
The complexity of testing programs containing loops. The presence of loops in a program can sharply increase the complexity of testing them. Complete, exhaustive testing must cover the verification of every route in the loop for all possible loop iterations and for all combinations of loops with the routes of the acyclic part of the program. Let us assume for simplicity that the number of routes in the lower acyclic part of the program equals M1 = 1. Then the complete set of routes M consists of the entire set of all routes Mx in the upper acyclic part of the program and a group of routes M2, in which each route from Mx has 1..2..3... loop iterations (turns) attached to it. In doing so, at least one of the internal routes of the loop body is executed on each iteration.
For example, for a graph that has one loop requiring the execution of five iterations (turns) with three internal routes, and also containing Mi = 10 acyclic routes passing through the loop, the total number of routes for exhaustive testing equals M = (3 x 5) x 10 = 150. As any of the factors increases (the number of independent acyclic routes passing through the loop, the number of internal routes of the loop body, or the number of its iterations), their product grows proportionally, and consequently so does the complexity of testing. Therefore exhaustive testing of real complex programs with loops can be practically impossible.
The complexity of testing a loop is influenced by its structure and two parameters: the number of routes in the loop body and the number of loop iterations. In the dynamics of the actual execution of the simplest loop, dependencies of at least three kinds'.
— on different iterations of the loop, all possible routes of the loop body are executed independently;
on all iterations of the loop, the same route of the loop body is executed, or some particular sequence of them;
on different iterations of the loop, due to the presence of semantic dependencies, a subset of the feasible routes of the loop body is executed, depending on the data or on the iteration number.
With a dependency of the first kind, which occurs most rarely, it becomes necessary to fully enumerate all internal routes of the loop body in combination with each number of iterations. In this case the complexity of testing the loop is determined by both parameters at once: the number of routes of the loop body and the number of iterations, and it approaches the complexity of exhaustive testing. With a dependency of the second kind the number of routes of the loop body practically does not affect the complexity of the loop. The determining factor becomes the number of iterations needed to test the computations in the loop body (for example, taking into account the required accuracy). With the third, most common dependency, the determining factor in assessing the complexity of testing is not the number of loop iterations but the number of routes of the loop body. It is advisable to carry out the simplest estimates of the complexity of loop structures under the assumption that the order in which the routes of the loop body are executed does not depend on the iteration number. In this case, when assessing the complexity of loop structures, a constructive approach is one based on the minimum required number of checks of loop iterations.
To assess the complexity of structural testing of acyclic logical programs with the simplest loops, it is advisable to refine the verification criteria. According to the first criterion, the acyclic part of the program is covered by a minimum number of routes, which include routes passing through the loop, opening it, and forming a minimum coverage of the loop body. In addition, a route containing the closing arc of the loop is added to the coverage. According to the second criterion the acyclic part of the program is verified by a number of tests equal to the complexity of the acyclic part of the program. In doing so, all loops adjacent to each such route are attached to it. Each loop is verified by one route containing as many iterations as the complexity of the loop body, while the loop body is covered by linearly independent routes.
With such estimates, the determining factors are the completeness of verification of the loop body and of its closing and opening conditions. Under these criteria, the complexity of a loop is most easily assessed by representing it as an equivalent acyclic subgraph. For example, under the second criterion, the equivalent of a loop with one entry point and one exit point will be a linear subgraph containing all linearly independent routes of the loop body, connected in series, linking its entry point to its exit point. Such an equivalent acyclic subgraph is added to each route in the coverage of the acyclic part of the graph under this criterion.
When nested loops with a complex structure and a large number of branches in the loop body are used, the complexity of testing increases sharply and the probability of undetected errors remaining in the program rises. However, loops with the simplest structure lead to a relatively small increase in the total complexity of the tests. Therefore, in the process of designing programs, it is necessary to simplify the loop components in the structure to the greatest extent possible, since in many cases they determine the achievable correctness of program modules during their testing.
Expression (13.3) is useful for identifying complex modules that require the greatest testing effort, and for the rational distribution of limited module-testing resources when creating large-scale program complexes. Some modules may turn out to be insufficiently tested because of their high complexity and the need for large expenditures, which are always limited. The limited resources available for testing program modules lead to the expediency of equalizing their structural complexity and allocating verification costs according to the complexity of each module. Especially complex modules should be divided into smaller and simpler ones, and their structure rebuilt so as to reduce the total number of routes in each individual module and their length.
The complexity of testing program components (functional groups of programs) is determined by the total complexity of the modules and of the intermodule control and information links. Each module must be tested autonomously before being included in a program group, and partly as part of the group. The costs of testing modules as part of
a program group must take into account the relative total costs of testing all the modules it includes, with a coefficient dk<\, depending on the degree of prior verification of the module. If the modules were not tested autonomously (for example, in top-down testing), then dk = 1, and the cost of testing each module will be included in full in the cost of testing the program group. With thorough autonomous testing of the modules, it can be assumed that dk = 0.1—0.01, i.e., within the software system the cost of testing each of the modules amounts to a few percent.
Comments