Application of genetic algorithm in black box testing

    Abstract: This paper proposes a method that uses genetic algorithms to help testers complete black-box testing of software modules in a shorter time and provide test results and good test cases.

    Keywords: genetic algorithm test case coupling degree

    In software testing, black box testing is mainly functional testing of modules. The most common method is to divide the input of the software into several equivalence classes based on the software's function description, and run the software multiple times to check whether the software can meet the requirements for different equivalence classes. However, in practical applications, some modules are too large or have too many input parameters, and the testing required after equivalence class division may be a huge task. At this time, how to select the optimal test cases becomes an important task for testers.

    Genetic algorithm is an optimization method that imitates biological genetic and evolutionary mechanisms. It introduces some behaviors similar to genetic genes, such as cross-recombination, mutation, selection and elimination, into the improvement process of algorithm solution. One of the characteristics of the genetic algorithm is that it retains several local optimal solutions at the same time and seeks better solutions through cross recombination or solution mutation. Compared with the greedy algorithm, the genetic algorithm is more likely to find the global optimal solution, while the greedy algorithm is easily limited to the local optimum and cannot reach the global optimum.

    If genetic algorithms can be effectively used in black-box testing to help testers select optimal test cases, it will be of great help to testing work.

1 Application method

    Before designing a specific algorithm, we first introduce the basic algorithm of the genetic algorithm. Its algorithm framework is as follows [1 ] :

    The first step, initialization: select p candidate solutions as the initial solution, and use the best solution as the temporary solution. Definite (optimal) solution.

    The second step is the improvement of the solution: if the termination condition is met, the tentative solution is output and the algorithm terminates. Otherwise, perform the following operations:

    (1) Cross-reorganization of solutions: Select two or more solutions from p solutions for cross-reorganization to obtain a new solution, and repeat this operation several times.

    (2) Mutation of solutions: Randomly add some mutations to the candidate solutions to generate new solutions.

    (3) Local search: Use the local search method to improve the newly generated solutions. If a better solution than the candidate solution can be obtained, update the candidate solution.

    (4) Select p solutions from all solutions according to certain criteria as candidate solutions for the next generation, and update the tentative solutions.

    Go to step two.

    After understanding the algorithm framework of the genetic algorithm, the next thing to do is how to convert different equivalence classes into candidate solutions of the genetic algorithm in the black box test of the software, how to set the quality standards of the solutions, and how to set the appropriate Termination condition.

    We assume that a software module has 5 input parameters: A, B, C, D, and E. After reasonable equivalence class division, each parameter has 5 different equivalence classes: A1~A5. ． ． ． ． ． , E1~E5. We use a generalized genetic algorithm candidate solution concept. General genetic algorithms often set the candidate solution form as a binary data string, such as: 111010, 010001, etc., and when different equivalence classes are input as candidate solutions, we will The form is determined as (based on the above assumptions): A3B1C2D4E5, A2B2C4D1E3 and so on. In this way, we have solved the problem of candidate solutions. We need to use tools as standards for the quality standards of solutions and the setting of termination conditions.

    The purpose of software testing is to improve the reliability of the software. The termination condition is of course that the software reaches the purpose and requirements of the testing. The standard of solution quality is exactly opposite to software quality, that is, the greater the probability of software failure, the better this test case (an input solution) is. Literature 结 2 The test environment of the Blue Bird Black Box in Peking University proposed a failure data model based on test execution. Using this model we can do [2]:

    (1) Provide a consistent reliability measurement process for failure data modeling, collection and management, thereby supporting reliability measurement;

    (2) Use data collected from testing and software on-site to evaluate Validity of test plans, operational overviews and test methods.

    The purpose of software testing is to find errors. In black box testing, errors manifest themselves in the form of software failure. However, since software errors are not a sufficient condition for software failure, in other words, not all errors will be exposed during testing or running, so the purpose of black box testing is to discover errors by running test cases to make the software fail as much as possible. When we evaluate the test cases, we use the following data to express the pros and cons of the test cases:

    A = P + λ / M + μ × F

    where A represents the fitness Adaptation in the genetic algorithm, and P represents the probability of the test case occurring in practice Probabi ｌｉｔｙ , M represents the mean time to failure (MTTF), and F represents the failure level. Because the test is for use, it is not difficult to understand that test cases with high probability of occurrence have high fitness; and M - the longer the average failure time, the test case should not be easy to find software errors, so the lower A; F It means that some special circumstances occur that cause the software to seriously fail (such as causing crashes, damaging instruments, etc.). At this time, the test case and its descendants must be focused on, so the larger A is at this time. λ and μ are coefficients corresponding to each specific software module being tested. In practical applications, since the possibility of software failure is not particularly high, the genetic result is often that test cases with a high probability of occurrence have more offspring. Therefore, we should design an accurate occurrence probability generation algorithm for the specific software being tested. The specific algorithm framework is shown in Figure 1.

    The description of this algorithm is as follows:
    *1. Each input parameter often has a probability (can be defined in advance), which can be simply added to obtain the probability of the test case. However, when the input parameters have strong correlation, this method cannot accurately obtain the probability of occurrence of a certain test case. One solution is to set the correlation coupling degree of the input parameters. During the crossover and mutation of the genetic algorithm, the probability of simultaneous crossover and mutation is proportional to the relative coupling degree. That is, for input parameters with a high relative coupling degree, the probability of simultaneous crossover and mutation is high, and vice versa.

    *２． When checking whether the test requirements are met, a counter needs to be set first. Each time a new test case is run, the test counter is incremented by one. When the first failure or malfunction is detected, the counter is incremented by two. If the generated genetic offspring causes the software to fail again, the counter is increased by 22. In the same way, when the test cases generated by the genetic algorithm fail the software n times in a row, the counter is increased by 2n. At the same time, record all test situations (this work is completed by the peripheral test environment, such as Peking University's Jade Bird black box test environment). If a serious error occurs, the test is terminated and the program is checked. If the genetic descendants of consecutive k generations of test cases run well, the counter value is increased by 2k. The value of k is determined by the number of equivalence classes of the specific software being tested, the number of input parameters, etc. When the value of the test counter reaches the value of all black-box test case equivalence classes (for the example we gave above, the value is 55 = 3125), the test ends. The algorithm must also end when the generated grandchildren, children, and parent generations are exactly the same, because there will be no new results in the test at this time. So we also need to set an end condition. And this condition is stronger than the counter condition.

    *3. Each group of test cases can generate multiple test cases, and the size of the fitness function determines which test cases are left to form a new test case group.

    It can be seen from the above algorithm block diagram and description that if a certain test case causes problems in the operation of the software (that is, a software error occurs), its descendants will also be trapped by the software error. The algorithm can quickly discover these most recent errors. The best test cases and results are given. Testers can then hand them over to developers to resolve these issues. If the software itself is indeed of good quality, failures cannot be found by these test cases and their different descendants, and the algorithm can be terminated as quickly as possible without completing all test cases (although in theory we would like the test to run as many test cases as possible).

2 Effects

    The algorithm in the previous section has no obvious advantages over running all test cases. Especially for testing, the algorithm does not speed up the running of test cases, but seems to slow down the running speed. In fact, the algorithm itself is not used to speed up the running of test cases. Its purpose is to find an optimal set of test cases. Because in practice it is almost impossible to run all test cases or even all equivalence classes for many modules.

    As explained in the example given in the previous section, the input equivalence class is roughly 55=3125. If a module has 10 inputs and each input has 10 equivalence classes, then the input equivalence class is 1010. Based on the calculation that it takes 1 minute to run one equivalence class (many cyclic running modules may take more than 1 minute), it will take several months to run all equivalence classes. At this time, the advantages of using genetic algorithms are reflected.

    In summary, this article proposes a testing method principle that uses genetic algorithms to find the best test cases. It can complete the black box testing of software modules in a relatively short period of time and provide test results and good test cases. Using the principle of this algorithm, you can make some settings or modify the test integration environment, which can greatly improve the efficiency of testing work.