Application of the shortest cover problem in testing a software product

The combinatorial problem of shortest cover can be applied successfully in testing software. Two tasks whose solution is reduced to finding a shortest column cover of a Boolean matrix are considered in the paper. Both the tasks can be solved with the minimax algorithm. The first task is connected with minimization of a test set in regression testing of a program functional. As a Boolean matrix, there is matrix R whose rows correspond to the program functionals being tested and columns to the tests intended for it. An element rij of the matrix R is equal to 1 if the test tj is suitable for testing the functional f otherwise it is equal to 0. As an example, the real project of "Site-platform of comparing costs for services on automobile insurance" was considered. For this purpose, the key elements of the system (the tested functional) are extracted whose faultless work was critical for this application. Those are the following: enter to a site; exit; registration; recognized user; user-student; user working; user unemployed; user with additional driver; anonymous user; user with elapsed time of a purchase; check of notification on a mistake; user with additional work; individual business owner; page with results of purchase; distribution of information to post. Then, a test set of regression testing was created that contained checks of declared functionality (11 tests). As a result of the search of a shortest cover of matrix R, it was found that the initial test set could be 14.3% decreased (2 tests) without lost of cover percentage of the functional. Similarly, this method was applied for another project; it was "Site of property insurance". According to the solving problem, both the applications resemble and have a little number of distinctive features. Therefore the test set is the same in much. At the second case, the decrease of the initial test set was by 21.4%. The second task concerns to the search for the minimal diagnostic test that can qualify defects in a software product. It is useful for automation of testing large products when testers are divided into certain groups. Let us consider two sets D = (A, D2, ..., Dn} and B = {b1, b₂, ..., bn}. The set D is the set of possible defects and B is the set of outward signs (symptoms) that appear as a result of disclosure of a defect. A symptom is a characteristic of a defect that can help to qualify defects according to their typical exposure. The diagnostic Boolean matrix C is constructed that shows what characters one or another defect is characterized. Then, the distinction matrix R is constructed whose rows correspond to the row pairs of the diagnostic matrix and show by what components those pairs differ. At that, the component-wise operation of modulo 2 addition is used executing it over all the row pairs of the diagnostic matrix. Let {1, 2, 3, 4, 5, 6, 7, 8, 9} be the set of symptoms. The defect D1 is characterized by the symptoms 1 and 8 and negates the rest. The defect D2 is characterized by the symptoms 2, 6, 7, 8 and negates the rest. Then the first row of the distinction matrix is D1D2 = (1 1 0 0 0 1 1 0 0). For the obtained distinction matrix, a shortest column cover is found. The set of characters corresponding to the columns in the found cover is the desired solution of the problem of searching for a minimum unconditional diagnostic test. At that, any defect is defined unambiguously by the corresponding row of the obtained submatrix. It helps to classify the defects in the most rational way at the moment of their appearance according to the given characters. This problem can be useful when the automation of testing large projects is organized and it is necessary to divide the test experts into certain groups. Then the problem of defect classification appears.

Keywords

Authors

References