Method of UNIT testing for algorithms of computing software modules

Abstract

The method of automating Unit testing processes for computing software modules is considered in the paper. Modern means of testing automation, which are analyzed in many scientific studies, specialize mainly in testing graphical user interfaces, web-interfaces, network communications, information systems, etc., which is the result of a huge demand in the market for software products within these spheres. Software modules of computing character are overshadowed by such products despite the fact that these modules have considerable scientific and practical value. They deal mostly with high tech spheres: aerospace cluster, energy industry, defense complex, etc. The article presents an original method of Unit testing for computing modules based on the algorithm of global search for infinite discontinuity points of testing function, which allows to find fatal errors in computing software modules, as well as incorrectness in implementation of algorithms for mathematical models. The universal method of Unit testing is offered within the class of computing modules, which helps to minimize the time for program debugging and to find fatal errors with less effort, as well as to organize total module testing for all modules of the program.

Keywords

• Unit testing
• testing automation
• computing software modules
• global optimization
• fatal errors

-

systems, etc. This results from the huge demand in the market for software products within these spheres. Software modules of computing character are overshadowed by such products despite the fact that these modules have considerable scientific and practical value. They deal mostly with high tech spheres [ 3 ]: aerospace cluster, energy industry, defense complex, etc.

Testing is the method of providing the required level of SW quality. In the general sense, software testing is the process that allows to determine the correctness, completeness and quality of the developed software product. Unfortunately, it is impossible to determine unambiguously whether the analyzed program functions correctly or not, as well as to guarantee the absence of defects in a software product because human factor problems may appear at all SW lifecycle stages [ 4 ]. Therefore, all existing testing methods operate within private formal methods of testing organized for the analyzed product. The list of modern methods and approaches for solving the problem of program testing is extensive and diverse. On the one hand, this diversity is determined by the current practice of using a computer while solving a variety of problems and, accordingly, by the specific features of software products themselves.

The class of computing software modules (CSM), based on the use of mathematical models, has some specific features. Such programs, carried out on a computer, are sure to calculate any function that realizes the display output of input data. This implies that a computer by means of its resources finishes the definition of a partly determined function, which results in complete definition. Consequently, it is possible to estimate if the results of program execution are right or wrong only by comparing the specification of the expected function with the results of its calculation; this is carried out in the testing process. For the class of computing software modules, methods of Unit testing [ 20 ] and test tools based on models using formal methods [ 4,6 ] are more suitable.

Formal methods usually allow to solve a limited range of testing software tasks within a particular class, however, they are able to work effectively in industrial projects and require a minimum number of special skills and knowledge so that to be used [ 4 ]. Currently, within monitoring the formal properties of SW, methods of test construction are thoroughly developed on the basis of finite-state automation [ 7, 8 ]. For them, accuracy characteristics and evaluation of completeness of performed tests are known. In these techniques, computing route is analyzed not only for performing some formulae, but also for coordination with the specified automation model of the proper behavior. Nowadays these methods are rarely used, mainly for monitoring small critical applications [ 4 ]. Formal methods are rather “heavy-weight”, they require well-qualified specialists, at least at the stage of software modeling. The weak point of formal methods is the need to construct the model itself on the parallel basis and to check its correctness.

The practice of industrial software production shows that the most effective strategy is to search and correct as many errors as possible at the earliest stage of software development. Methods of Unit testing are appropriate for this purpose. Unit testing consists in checking the software performance on a set of input and corresponding output data. This approach allows to reveal a significant number of errors and locate them quickly as it is easier to find an error within a module than to do it within the whole project. CSM can be easily interpreted with a vector computable function = ( ) = ( 1( ), 2( ), … , ( )) , having a set of input parameters = ( 1, 2, … , ) of the module and a set of calculated data = ( 1, 2, … , ) .

The origin of errors for CSM is extensive and diverse. Errors occur when initial and boundary conditions, which characterize the value and location of external factors, are set incorrectly. They may be related with a set of limitations and assumptions resulting from the physical nature of the object and limiting the range of input parameters.

Among the errors of this kind for CSM, two most common groups can be distinguished: calculation errors and logical (algorithmic) errors. Calculation errors are mostly connected with incorrect recording or programming of mathematical expressions and manifest themselves as arithmetic error of division by 0, the square root of a negative number, as calculation of rational or transcendental functions, etc. They can only be detected while executing the program and lead to program stoppage.

Logical errors are connected with the distortion of problem solving algorithm and result from incorrect problem setting, wrong consideration of all conditions for solving the problem, incorrect management organization within CSM, and errors in the input of logical expressions. These errors are difficult to correct, corrections often being made with the help of formal methods [ 5 ].

Nevertheless, there is a universal method for detecting errors of calculating and partly logical character in computing software modules [ 3, 9 ]. This method is based on the fact that all computing modules, implemented as a program, “work” within integrity of used functions or mathematical models. Otherwise, the program can’t be used. If we organize the search for infinite discontinuity of the function by some means, we will be able to detect all calculating errors of any origin mentioned above. Relatively “simple” methods of global optimization (GO) of multivariable functions are appropriate for this purpose[ 10 ].

In this paper we consider the improved algorithm of global search for points of discontinuity of the second type, intended for detecting error situations in the software modules of computing character. This algorithm is the basis of Unit testing for computing software modules.

1. Problem Statement

Let the area of error search in computing module be a unit cube (in general – hypercube) П  [ 0, 1 ][ 0, 1 ][ 0, 1 ] , which is proportionally divided into eight smaller cubes.

Unit testing algorithm of computing modules, formally described by vector function = ( ), can be put as the problem of global optimization max fk2 ( X ),

X

k  1,..., m, which is aimed at detecting (or ensuring the absence of) discontinuity points of the second type in the examined function. The infinite discontinuity   is realized in numbers marked by code NaN on a computer; in fact we can specify the upper limit (1) where  – estimation of Lipschitz constant, which is calculated in the process of function extremum search:

M  0,   1 M  max zi  zi1 ,

rM M  0, i ( xi  xi1) where r – parameter.

The condition of Lipschitz for optimized function simplifies greatly the search for function extremum as the limitation of function growth degree allows to find local extremum vicinity quickly. However, while searching for a set of infinite discontinuity, areas of function monotony as well as extremum vicinity are equally useless. It is much more important to determine the criteria which will be responsive to the fast increase and decrease of function.

Nowadays, mathematical aspects of function behavior in vicinities of discontinuity points are not analyzed thoroughly, which complicates detecting function discontinuity presence while analyzing its behavior on local continuous sections. The paper [ 11 ] offers the characteristic function, created by analogy with (2), but it is more adapted to solve the task of search for infinite discontinuities points. The following characteristic function is offered to use: of acceptable values | ( )| ≤ ( ) or each calculating parameter of a module. To simplify the situation, we will further consider scalar function ( ) = 2( ).

Among the well-known one-parameter methods of multiextremal optimization, R.G. Strongin statistic information method is the most effective [ 10 ]. The method is based on the use of approximate posterior probability distribution of global extremum location, which is formed in the process of function testing, which allows to realize a more balanced strategy to search for function global minimum. This strategy is so effective that it is often transferred from one-dimensional case to multivariable function optimization.

It is shown in the paper [ 10 ] that function extremum search is realized by maximizing a simple characteristic function: R(i)  (d 2 f ( Xic ))2 D , r i where – the centre of a cube, – cube diagonal of search algorithm, r – scaling parameter.

The second differential of function can be calculated with the help of interpolation of initial function using Newton’s first interpolation formula [ 12 ] for full factorial plan 3 [ 13 ]. Then, using 2,2,2( ) it is easy to calculate 2 ( ) ≈ 2 2,2,2( ).

In search algorithm, there is a proportional division of search area into smaller parts: the unit interval – into 2 parts; square – into 4 parts, cube – into 8 parts, etc. Fig. 1 shows a diagram of search area division for two-dimensional case. We will consider the three-dimensional case further in order to present a good illustration. (2) (3)

Construction of interpolating polynomial for multidimensional case can be realized as follows. = ‖ ‖( , , = 0,1,2) is the matrix of testing function values at nodal points of full factorial plan 3 . We introduce new variables = 1−ℎ 1(0) ; = 2−ℎ 2(0) ; = 3−ℎ 3(0). The starting point of interpolation grid is (0) = ( 1(0), 2(0), 3(0); h – the step of interpolation grid. Newton’s interpolation polynomial is to be calculated in the form of matrix. Symbols of multidimensional matrix and content of main operations are borrowed from the paper [ 13 ]. To do this, we need to calculate the matrix of finite differences ̃. 1r z 2rr z 1q z 1qr1z 1qr2rz 2qqz 2qq1rz 2qq2rrz (4) 1pr1z 1pr2rz 1qp1z 1qp1r1z 1qp1rr2z 2qq1pz 2qq1pr1z 2qq1pr2r z 2pp1rz 2pp2rrz 1qp2pz 1qp2pr1z 1qp2pr2r z 2qq2ppz 2qq2pp1rz 2qq2pp2rrz Here α= 000. We introduce a vector Q  (1 q P  (1 p R  (1 r q(q 1) / 2); p( p 1) / 2); r(r 1) / 2).

Considering (, ) -convoluted product of vectors Q, P, R with λ = 0, µ= 0, we get the matrix of independent variables ̃ = = ‖ ∙ ∙ ‖ ( , , = 0,1,2 (6) Thus, Newton’s interpolation polynomial has the following matrix form P2,2,2 ( X ) 3 Z~ X~   c0 ,c1,c30 2 ~ ~  Zc0c1c2  X c0c1c2 , (5) (6) where c  (c0, c1, c2 ) – Caylean summation index [ 14 ].

The elements of matrix (4) can be calculated using the definition of finite differences of corresponding orders.

To calculate partial derivatives we need vectors ′ = (0 1 − 0.5)′; ; = (0 1 − 0.5)′; ′ = (0 1 − 0.5)′; ′′ = ′′ = ′′ = (0 0 1)′, then

1 1 1 Px ( X ) 3 (Z~ (QPR)) ; Px2 ( X ) 3 (Z~ (QPR)) ; Px3 ( X ) 3 (Z~ (QPR)) , 1 h h h and the second derivatives:

1 1 1 Px1x1 ( X ) 3 (Z~ (QPR)) 2 ; Px2x2 ( X ) 3 (Z~ (QPR)) 2 ; Px3x3 ( X ) 3 (Z~ (QPR)) 2 .

h h h

Now it is easy to calculate the value of the second differential in the centers of each eight cubes of original search area partition: d 2 f (Xic )  (Px1x1 (Xic )  Px2x2 (Xic )  Px3x3 (Xic )  2(Px1x2 (Xic )  Px1x3 (Xic )  Px2x3 (Xic )))h2.

The value of characteristic function is calculated for each of new cubes, which are written onto the line ordered list in descending order of values. At each stage of search algorithm for discontinuity points of testing function, the first item on the list is chosen – a cube with maximum value of characteristic function, which is subjected to further division. The algorithm works till the condition of algorithm stoppage appears: (max| | > )˅( ℎ < ). This condition of algorithm stoppage ensures the completion of its work if the value of testing function is outside function domain or the given density of viewing the original area of testing function is reached.

2. Examples of using the proposed method of Unit testing for computing modules

2.1. Method testing with model examples

The proposed testing method of CSM got its name as finite differences method (FDM) due to the use of finite differences of the function. The efficiency of its work can be evaluated by means of discontinuous function – Kovartsev’s test [ 11 ], specially developed for this case, and a set of test functions generated by the GKLS generator [ 15 ]. The first test is characterized by a single discontinuity point (which is difficult to detect) added to linear combination of error functions. The second one is a continuous function with a large number of local extrema. Test functions are presented in Table 1.

In literature, the efficiency of search algorithms is usually evaluated using the operating characteristics machine [ 16 ]. Operating characteristic is the dependence of error detection probability on the amount of calls to the tested function .

Since the second-order discontinuity points can be found by any of the global optimization algorithms, the efficiency of the proposed FDM algorithm was compared with the efficiency of direct GO method, for example, the modified bisection method (BM) [ 17 ]. GKLS test functions.

Continuous twice differentiable function. 10 local extrema. One global extremum. Points of discontinuity are not observed.

General view

The operating characteristics of FDM and BM methods are shown in Fig. 2. They are created for test function 1 which has a local discontinuity point of the second type (see Table 1). As we can see from fig. 2, the efficiency of the proposed algorithm is much greater than the efficiency of the bisection method. In Fig. 2 the solid line indicates operating characteristics of FDM algorithm, the dashed one indicates characteristics of BM algorithm. It happens because the bisection method is focused on the optimization of continuous functions, which leads to a more detailed analysis of the function areas when Lipschitz constant evaluation increases. This situation occurs every time when the function is calculated near the points of its discontinuity. By contrast, FDM method is oriented on looking for areas of rapid growth of the test function.

The situation changes if FDM method “works” with continuous function. Figure 3 shows the operating characteristics of these methods, created for continuous GKLS test function.

The figure illustrates the fact that the efficiency of FDM algorithm for continuous functions is much lower than the efficiency of BM algorithm. If we have continuous functions with no discontinuity points of the second type (test software module has no errors), the finite difference method is forced to examine thoroughly the space of the optimized variables.

2.2. Testing of software modules for calculating acoustic characteristics of gas pressure regulator

This part presents the results of Unit testing for computing models included in the program that realizes the optimization of gas pressure regulator (GPR) parameters with use of orifice plates [ 21 ].Significant changes in pressure during orificing and speed acceleration generate the noise which accompanies the work of these machines. This noise exceeds the established health standards. Rational choice of orifice flow area (and their quantity) can significantly reduce the noise level of this device [ 18 ]. Gn1  Gn  0, (7) – gas flow through the valve, – gas flow through i-orifice plate. When the input parameters of module are given, for example, , +1– pressure before and after orifice plate correspondingly; – areas of i-orifice flow, etc. we can calculate gas mass flux through orifice and as a result – acoustic power generated by orifice plate [ 19 ].

We used a rather simple module for calculating the orifice flow capacity ( ) in order to calculate the gas mass flux through orifice. Testing the module by FDM method with approximately 200 calls to the module revealed methodological error in the algorithm model. It turned out that if → +1 − → ∞, and < +1, flow capacity is indefinite (error code NaN occurs).

Certainly, it would be possible to require the calculation with this module ( , +1) to be carried out only in accordance with the condition > +1, which is natural for this type of device. But how can it be realized when numerical method for solving systems of nonlinear equations (8) generates the values of independent variables at each iteration on its own, not taking into consideration the above mentioned circumstances? The easiest way to solve the problem is the artificial replacement of function infinite discontinuity ( , +1) with a larger but finite discontinuity, and extension of definition by “penalty” value where it is indefinite. In this case, the algorithm for solving systems of nonlinear equations is to find solutions on its own, “starting with” “dysfunctional” combinations of independent variables.

High speed of detecting fallible combinations of FDM independent variables in this example can be explained by the fact that at the first stage of work, when the area of rapid function growth is not detected, FDM distributes test points of testing function in the search area. Since function ( , +1) has significant areas of uncertainty, FDM finds them quickly.

Conclusion

The paper offers an original method of Unit testing for computing modules, based on the algorithm of global search for infinite discontinuity of the testing function, which allows to detect fatal errors in software computing modules, as well as incorrectness in implementation of mathematical models of algorithms.

The proposed scheme of accelerating algorithms for global optimization applied to the search for points of discontinuity of the second order has confirmed completely its viability with model and real examples. The basic idea of FDM algorithm is to introduce a new heuristic characteristic function to the classical algorithm of global optimization. The new function is based on the analysis of Strongin characteristic function and takes into account the problem matters being solved. FDM algorithm is the universal method of Unit testing for the class of computing modules. The application of this method leads to the reduction of time for debugging, helps to find fatal errors with less effort, and, as a result, to organize total testing of all program modules.

References

1. Dastin E , Reshka D , Paul D. Automatic software testing. Application, operation and maintenance . Moscow: Lori, 2003 ; 567 p. [in Russian]

2. Lipaev VV . Program testing . M.: Radio and connection, 1986 ; 296 p. [in Russian]

3. Kovartsev AN . Automation of software development and testing . Samara State Aerospace University, 1999 ; 148 p. [in Russian]

4. Kuliamin VV . Software verification methods . Source: <http://panda.ispras.ru/~kuliamin/docs/VerMethods-2008-ru.pdf >

5. Kovartsev AN . An efficient algorithm for testing the truth of assertions for real numbers expressed in relational signatures . Computer Optics , 2014 ; 38 ( 3 ): 550 - 554 . [in Russian]

6. Heitmeyer C , Archer M , Bharadwaj R , Jeffords R . Tools for constructing requirements specifications: The SCR toolset at the age of ten . Journal of Computer Systems Science and Engineering , 2005 ; 20 ( 1 ): 19 - 35 .

7. Farchi E , Hartman F , Pinter SS . Using a model-based test generator to test for standard conformance . IBM Systems Journal , 2002 ; 41 ( 1 ): 89 - 110 .

8. Cavalli A , Gervy C , Prokopenko S . New approaches for passive testing using an Extended Finite State Machine specification . Information and Software Technology , 2003 ; 45 ( 12 ): 837 - 852 .

9. Kovartsev AN , Logvinov AL . Efficiency improvement of testing algorithms for computing modules . Journal of Telecommunication systems , 2004 ; 4 . [in Russian]

10. Strongin RG . Search for global optimum . Moscow: Znanie, 1990 . [in Russian]

11. Kovartsev AN , Popova-Kovartseva DA , Serpovskaya EE . Testing mathematical models of computing algorithms based on global optimization method . Information technology and nanotechnologies. SSAU , 2015 ; 191 - 196 . [in Russian]

12. Kovartsev AN . Computational mathematical. Samara: Ofort , 2011 ; 230 p. [in Russian]

13. Ermakov SM , Zhigliavsky AA . Mathematical theory of optimal experiment operation . Moscow: Nauka, 1987 ; 320 p. [in Russian]

14. Sokolov NP . Introduction to multidimensional matrix theory . Kiev: Nukova dumka, 1972 ; 177 p. [in Russian]

15. Gaviano M , Kvasov DE , Lera D , Sergeyev YaD . Software for generation of classes of test functions with known local and global minima for global optimization . ACM TOMS , 2003 ; 29 ( 4 ): 469 - 480 .

16. Gergel VP , Strongin RG . Absolute. Software system for global optimization method studying . Textbook . Nizhny Novgorod: Nizhegorodsky University Press, 1998 ; 141 p. [in Russian]

17. Kovartsev AN , Popova-Kovartseva DA , Abolmasov PV . Efficiency study of global parallel optimization for multivariable function . Vestnik NNGU , 2013 ; 3 ( 1 ): 252 - 261 . [in Russian]

18. Igolkin АА , Kruchkovа AN , Koh AI , Safin AI , Shakhmatov EV . Pressure reducing valve noise reduction . Proceedings of the Nineteen International Congress on Sound and Vibration (ICSV 19) . The international institute of Acoustics and Vibration , 2012 , July 08- 12.

19. Istvan L , Beranek V , Beranek L . Noise and vibration control engineering. Second edition. Principles and applications . Published by Wiley and Sons, Inc, 2006 ; 966 p.

20. Meszaros , G. xUnit test patterns: rafactoring test code . U.S. at Courier in Wesrford, Massachusetts, 2009 ; 835 p.

21. Karczub DG , Catron FW , Allen C . Blow-down valve noise and interactions with down stream orifice plates . Fagerlund Proceedings of IMECE'03 . ASME International Mechanical Engineering Congress, 2003 ; 43 - 49 .