CN113377676B - A solver performance defect detection method based on multi-objective genetic algorithm - Google Patents
A solver performance defect detection method based on multi-objective genetic algorithm Download PDFInfo
- Publication number
- CN113377676B CN113377676B CN202110767573.7A CN202110767573A CN113377676B CN 113377676 B CN113377676 B CN 113377676B CN 202110767573 A CN202110767573 A CN 202110767573A CN 113377676 B CN113377676 B CN 113377676B
- Authority
- CN
- China
- Prior art keywords
- test
- solver
- population
- files
- file
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
- 238000004422 calculation algorithm Methods 0.000 title claims abstract description 37
- 230000007547 defect Effects 0.000 title claims abstract description 36
- 238000001514 detection method Methods 0.000 title claims abstract description 12
- 230000002068 genetic effect Effects 0.000 title claims abstract description 9
- 238000012360 testing method Methods 0.000 claims abstract description 211
- 238000000034 method Methods 0.000 claims abstract description 48
- 230000035772 mutation Effects 0.000 claims description 16
- 238000012216 screening Methods 0.000 claims description 12
- 238000011156 evaluation Methods 0.000 claims description 6
- 230000009191 jumping Effects 0.000 claims description 4
- 238000005457 optimization Methods 0.000 claims description 4
- 238000010187 selection method Methods 0.000 claims description 3
- 238000006467 substitution reaction Methods 0.000 claims description 2
- 238000011161 development Methods 0.000 abstract description 4
- 238000005516 engineering process Methods 0.000 abstract description 2
- 238000010845 search algorithm Methods 0.000 abstract description 2
- 238000013522 software testing Methods 0.000 abstract description 2
- 230000003044 adaptive effect Effects 0.000 description 5
- 230000009286 beneficial effect Effects 0.000 description 2
- 238000004364 calculation method Methods 0.000 description 2
- 238000013461 design Methods 0.000 description 2
- 238000013515 script Methods 0.000 description 2
- 238000004458 analytical method Methods 0.000 description 1
- 230000007812 deficiency Effects 0.000 description 1
- 238000009795 derivation Methods 0.000 description 1
- 238000010586 diagram Methods 0.000 description 1
- 238000013100 final test Methods 0.000 description 1
- 230000010354 integration Effects 0.000 description 1
- 238000011056 performance test Methods 0.000 description 1
- 230000005481 string theory Effects 0.000 description 1
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F11/00—Error detection; Error correction; Monitoring
- G06F11/36—Prevention of errors by analysis, debugging or testing of software
- G06F11/362—Debugging of software
- G06F11/3628—Debugging of software of optimised code
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F11/00—Error detection; Error correction; Monitoring
- G06F11/36—Prevention of errors by analysis, debugging or testing of software
- G06F11/3668—Testing of software
- G06F11/3672—Test management
- G06F11/3676—Test management for coverage analysis
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F11/00—Error detection; Error correction; Monitoring
- G06F11/36—Prevention of errors by analysis, debugging or testing of software
- G06F11/3668—Testing of software
- G06F11/3672—Test management
- G06F11/3684—Test management for test design, e.g. generating new test cases
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F11/00—Error detection; Error correction; Monitoring
- G06F11/36—Prevention of errors by analysis, debugging or testing of software
- G06F11/3668—Testing of software
- G06F11/3672—Test management
- G06F11/3688—Test management for test execution, e.g. scheduling of test suites
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06N—COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- G06N3/00—Computing arrangements based on biological models
- G06N3/12—Computing arrangements based on biological models using genetic models
- G06N3/126—Evolutionary algorithms, e.g. genetic algorithms or genetic programming
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Quality & Reliability (AREA)
- Computer Hardware Design (AREA)
- Biophysics (AREA)
- Health & Medical Sciences (AREA)
- Life Sciences & Earth Sciences (AREA)
- Evolutionary Biology (AREA)
- Bioinformatics & Cheminformatics (AREA)
- Bioinformatics & Computational Biology (AREA)
- Molecular Biology (AREA)
- Evolutionary Computation (AREA)
- General Health & Medical Sciences (AREA)
- Physiology (AREA)
- Computing Systems (AREA)
- Data Mining & Analysis (AREA)
- Computational Linguistics (AREA)
- Mathematical Physics (AREA)
- Software Systems (AREA)
- Biomedical Technology (AREA)
- Artificial Intelligence (AREA)
- Genetics & Genomics (AREA)
- Debugging And Monitoring (AREA)
Abstract
The invention belongs to the field of software testing, relates to a technology for automatically generating test cases for detecting performance defects of a solver, and particularly relates to a solver performance defect detection method based on a multi-objective genetic algorithm. The method and the device maximize the running time difference between the target solver and the reference solver and the code coverage rate of the target solver by using a multi-target search algorithm to increase the guide information in the search process, shorten the time required for finding the performance defects, prevent the volume of the test cases from being excessively expanded by minimizing the complexity of the test cases, and simultaneously calculate the similarity among the test cases by using a dynamic tracking file to ensure the diversity of a generated result set so that the algorithm can find more potential performance defects. The method is suitable for each version of the development of the solver, can help a developer find out the performance defects in the development process of the solver, and effectively reduces the non-encountered errors caused by the performance defects of the solver in the use process.
Description
Technical Field
The invention belongs to the field of software testing, relates to a technology for automatically generating test cases for detecting performance defects of a solver, and particularly relates to a solver performance defect detection method based on a multi-objective genetic algorithm.
Background
SMT (The Satisfiability Modulo Theories) is that the satisfiability modulus theory is a decision problem for solving the satisfiability of the first order logic formula. Solvers are software tools that aim to solve a variety of theoretical constraint problems. It has been applied to various fields including software verification and program testing. But the solver error may cause the application to crash, even worse. For example, in symbolic execution using a solver, if the solver has a performance defect, the correct analysis result cannot be obtained. The performance deficiency of the solver is that for a given input, the solver cannot complete the decision within a specified time.
Existing papers and invention patents focus less on solver performance issues. Most of the inventive patents focus on how to solve the problems of a specific field using solvers. For example, a solver design method for rocket online trajectory planning (patent application number: CN 202011262143.1) proposes a solver design method for rocket online trajectory planning, which can meet the requirement of rocket online trajectory planning on solving instantaneity. However, if the solver itself has performance defects, the solving speed cannot be guaranteed. A patent is an easily-extensible software system, a calling method and a terminal (patent application number: CN 202011262143.1) of a reactor core numerical solver, which applies the solver to a terminal interface, and facilitates integration of a new numerical solving algorithm and derivation of a numerical solving interface meeting different requirements. These invention patents focus on how to solve the practical problem using solvers, but do not focus much on testing with the solver itself. 2018D Blotsky proposes a method of automatically generating test cases using genetic algorithms, detecting solver bugs. However, the method uses a random search strategy, takes the running time of a solver as an optimization target, and cannot guarantee the convergence of the algorithm and the validity of the result. The problem that the algorithm has long running time and few found performance defects exists, and the problem that the performance of a solver can be found effectively cannot be guaranteed.
In summary, the performance test of the existing solver has the following two problems that firstly, the guiding information is insufficient when the test cases are automatically generated, so that the effective overtime cases cannot be found for detecting the performance defects of the solver, the potential performance errors of the solver cannot be effectively detected, and secondly, the lack of diversity evaluation in the searching process can cause the test cases in the generated result set to have higher repeatability, the test range cannot be effectively covered, and the accuracy of the solver is ensured.
Disclosure of Invention
In order to solve the above problems, an object of the present invention is to provide a method for automatically generating test cases that can trigger the performance defect of a solver. The method and the device are beneficial to detecting potential performance defects in the solver by generating the test cases for triggering the performance defects of the solver, help developers to test updated versions of the solver, and ensure high availability of the solver.
The technical scheme of the invention is as follows:
a solver performance defect detection method based on a multi-objective genetic algorithm comprises the following specific steps:
step 1, pile inserting compiling target solver
The method specifically comprises the steps that code statement coverage rate of a test case needs to be calculated in algorithm operation, so that a code coverage rate detection tool needs to be used for instrumentation compiling of a target solver, the code coverage rate detection tool can generate accurate counts of execution of each statement in a program, the instrumentation compiling does not influence normal operation of the target solver, only a file containing statement execution times information is generated after the operation, and the code statement coverage rate of the test case is calculated in step 7.
Step 2, randomly generating seed test file sets to form a primary population
The method comprises the steps of randomly generating test case files conforming to SMT grammar rules, wherein the test case files form a first generation population, namely each individual in the population is a test file, and the size of the population represents the number of the test files contained in the population.
Step 3, screening seed test files in the primary population by a binary tournament selection method
The method for selecting the binary tournament comprises the steps of taking two test files from a first generation group each time, and selecting one of the test files which enables the target solver to run for a longer time as the test file with excellent performance.
Step 4, performing cross mutation on fine test files in the population to generate offspring population
The method comprises the steps of selecting good test files, generating new test files to form child populations through a crossover operator and a mutation operator, selecting test files to be operated from the good test files each time, judging which operation is carried out on the test files to generate the new test files through the crossover rate and the mutation rate, and continuously carrying out the operation until the number of the new test files reaches the specified population number.
The crossover operator selects two test files to exchange each other's assertion statement, wherein the crossover operator selects a part of assertion statements in the two test files to exchange in order to ensure enough crossover quantity, and exchanges one assertion statement if the assertion quantity of the parent test file is less than the exchange quantity, namely, at least one assertion statement in each test case is ensured.
The mutation operator is operated aiming at a single test file, and comprises newly built variables, deleted variables, added assertion statement, deleted assertion statement, character strings and numbers in alternative assertion statement, functions in alternative assertion statement and nodes with the same substitution type.
Step 5, judging whether the algorithm converges or reaches the maximum iteration number of the algorithm
The method comprises the steps of judging whether the maximum iteration times of an algorithm are reached or whether the algorithm is converged, if not, jumping to the step 6 to iterate the algorithm, and if the maximum iteration times are reached or the algorithm and the convergence are reached, jumping to the step 11, wherein the algorithm convergence means that the average fitness of the population is not changed within a certain algebra.
Step 6, combining the excellent test file in the parent and the test file of the child population to generate a new population
Combining the excellent test files in the parent and the test files in the child population into a new test file set, namely a new population, and performing the next iteration operation.
Step 7, evaluating the adaptability of the test files in the population, and respectively calculating the running time difference of the solver, the code coverage rate and the complexity of the test cases
Carrying out fitness function evaluation on each test file in a population, wherein three optimization target indexes are used in an algorithm, namely the running time difference of a target solver and a reference solver, the code coverage rate of the target solver and the complexity of a test case; the method comprises the steps of obtaining a first adaptive score by using a running time difference of a target solver and a reference solver, counting the time spent by the target solver and the reference solver by using the running time difference of the target solver and the reference solver as a first adaptive score, generating a code coverage information file and a dynamic tracking file in the process, calculating the code statement coverage of the target solver by using code statement execution information contained in the code coverage information file, taking the code statement coverage of the target solver when the test case runs (namely counting the proportion of the number of covered code statements and the total code statement number of the target solver when the test case is executed) as a second adaptive score, and taking a third adaptive score by minimizing the complexity of the test case, wherein the complexity of the test case is kept in a small volume by using the weighted score at n-th node as a third adaptive score, and taking the weighted score of each step as a weighted score, and taking the weighted score of each step 8.
Step 8, performing non-dominated pareto sorting on the test cases in the population, and calculating crowding distances among the test cases
The method comprises the steps of carrying out non-dominant pareto sorting, namely selecting all non-dominant test case sets from a population to serve as a pareto front, then removing the test cases from the population, selecting non-dominant test cases again to form a new pareto front, repeating the operation until all the test cases are added to the pareto front, and calculating crowding distances among the test cases by using dynamic tracking files generated by each test case in the step 7 when a target solver runs, wherein the dynamic tracking files are used for selecting operation in the step 9.
Step 9, selecting test cases with excellent performance in the population
The method comprises the steps of selecting and screening good test cases by using a binary tournament based on dominance, selecting and screening the good test cases by using a non-dominance pareto ordering, wherein each test case has two attributes, namely a non-dominance ordering and a crowding distance, observing rules when the test case I is compared with the test case J, wherein the non-dominance ordering of the test case I is superior to the test case J, the test case I wins, the test case I is the same as the non-dominance ordering of the test case J, but the crowding distance of the test case I is greater than the test case J, the test case I wins, and repeating the selection operation until the number of the test cases with good performances reaches the specified population size to form a new population.
Step 10, performing cross mutation on the excellent test cases to generate new sub-populations
Specifically, the step is the same as the operation of the step 4, and a new sub population is obtained.
Step 11, verifying the generated test file and screening out test cases triggering performance defects
The method comprises the steps of enabling a target solver to re-execute test files in a population under a time-out time long enough, adding the test files into a final result set if the test files still cannot be solved, triggering performance defects of the solver by test examples in the result set, and ending an algorithm.
The method has the beneficial effects that the potential performance defect of the solver can be detected through automatically generating the test case. By using a multi-target search algorithm, the running time difference between the target solver and the reference solver and the code coverage rate of the target solver are maximized to increase the guide information in the search process, reduce the time required for finding the test file triggering the performance defect, and prevent the volume of the test case from being excessively expanded by minimizing the complexity of the test case. Meanwhile, the similarity among test cases is calculated by using the dynamic tracking file, so that the diversity of a generated result set is ensured, and more potential performance defects can be found by an algorithm. The method is suitable for each version of the development of the solver, can help a developer find out the performance defect of the solver in the development process, and effectively reduces the occurrence of the non-encountered errors in the use process caused by the performance defect of the solver.
Drawings
FIG. 1 is a schematic workflow diagram of a solver performance defect detection method based on a multi-objective genetic algorithm according to the present invention.
Detailed Description
The method of the invention is described in detail below with reference to the accompanying drawings, technical solutions and examples.
In this embodiment, the method of the present invention is deployed on a Linux server, and the specific configuration of the server is shown in table 1. In this embodiment, z3str3 is used as a target solver, cvc4 is used as a reference solver, the population size is 40, the crossover rate is 0.75, the mutation rate is 0.25, and the maximum iteration algebra is 60 generations. The method comprises a seed test file generation module, an adaptability evaluation module, a test file cross variation module, a non-dominant pareto ordering module, a test case crowding degree calculation module and the like.
Table 1Linux server configuration information table
| Processor model | Memory | Operating system |
| IntelCorei9-10900 | 32GB | Ubuntu 18.04.01 |
As shown in FIG. 1, the solver performance defect detection method based on the multi-objective genetic algorithm is carried out according to the following flow. The method comprises the steps of inserting piles, compiling a target solver, randomly generating an initial seed test file set, constructing an initial population, screening the initial population, generating a sub population through cross mutation, merging test cases with excellent parent performance and test cases in the sub population, evaluating the adaptability of the new population, carrying out non-dominant pareto sorting on the test cases in the population, calculating the crowding distance, selecting excellent test cases to carry out cross mutation to generate the new population, verifying test files in the final population, and outputting test files capable of triggering the performance defects of the target solver.
In the description of the steps in this embodiment, z3str3 is taken as an example of a target solver, and specific steps can be adjusted by other solvers. The method comprises the following specific steps:
step 1, pile inserting compiling target solver
Specifically, the command LDFLAGS+＝'-fprofile-arcs'CFLAGS+＝'-fprofile-arcs-ftest-coverage'CXXFLAGS+＝'-fprofile-arcs-ftest-cover age'CPPFLAGS+＝'-fprofile-arcs-ftest-coverage'python3 scripts/mk_make.py is used to perform instrumentation compiling on the z3str3, and then the z3str3 running process generates a file of 'gcda' containing the code statement running times.
Step 2, randomly generating seed test file sets to form a primary population
Specifically, random test files are generated using the grammar generator in StringFuzz and packaged as Instance classes, which include four parts, setlogic, declare, assert and checksat. section setlogic specifies the grammar used by the test case as string theory, section declare states the variables and their types that may be used, and the assert section stores abstract grammar trees, each of which is an predicate statement, using a list. Part checksat is the fixed syntax of the test case, letting the solver check the satisfaction of the test case. The first generation population is a collection of 80 Instance objects.
Step 3, screening seed test files in the primary population by a binary tournament selection method
The method comprises the steps of selecting Instance of an Instance object from a population in pairs, putting the Instance of the Instance object with good performance into a set of Instance instances of good performance, and replacing the Instance of the Instance object with poor performance into the population. This operation was repeated until 40 good Instance of Instance object were obtained, constituting a new population.
Step 4, performing cross mutation on fine test files in the population to generate offspring population
The method comprises the steps of selecting two test cases from good test cases, generating a random number between 0 and 1, if the generated random number is smaller than 0.25, performing cross operation on the two test cases by using a cross operator to obtain a new sub-test case, if the generated random number is between 0.25 and 1, performing mutation operation on the two test cases by using a mutation operator to obtain two new sub-test cases, adding the new sub-test cases into a sub-population, and repeating the operation until the size of the sub-population reaches 40.
Step 5, judging whether the algorithm converges or reaches the maximum iteration number of the algorithm
Specifically, the average fitness is calculated in each subsequent iteration, if the average fitness of the continuous 10-generation population has not changed, the algorithm is considered to be converged, and if the convergence condition is not met, but the operation reaches 60 generations, the iteration is judged to be ended. And then jumps back to step 11. If the decision fails, jump to step 6.
Step 6, combining the excellent test file in the parent and the test file of the child population to generate a new population
The method specifically comprises the steps of combining a test case set with excellent performance in a parent and a newly generated child population to generate a new population, and participating in the fitness evaluation of the step 7.
Step 7, evaluating the adaptability of the test files in the population, and respectively calculating the running time difference of the solver, the code coverage rate and the complexity of the test cases
Specifically, each test case is sequentially taken out from the new population, converted into a test file which can be identified by z3str3 and cvc4, and subjected to fitness evaluation. The test file is first run at a timeout of 5s using z3str3 and cvc s4, respectively, resulting in two run times. The run-time difference is used as the first fitness score. During this process, a ". Gcda" file containing code overlay information is generated, and all ". Gcda" files are traversed by the python script. And counting the number of times of code statement operation to calculate the code statement coverage rate of the test case, and taking the code statement coverage rate as a second fitness score. Finally, the complexity of the test file is calculated. That is, the nodes in each abstract syntax tree are counted, the nodes of the first layer are integrated into one fraction, and the nodes of the nth layer are integrated into n fractions. And then summing all node scores, and taking the final result as a third fitness score. Through the operation of the step, each test case can obtain a triplet as an fitness score to participate in the sorting of the step 8.
Step 8, performing non-dominated pareto sorting on the test cases in the population, and calculating crowding distances among the test cases
Specifically, through step 8, all test cases in the population contain an fitness score tuple. And sorting, namely selecting test cases which are not subjected to other test cases, namely that each fitness score of no other test cases is better than those test cases. These test patterns will be selected as the first pareto front. The above operation is then repeated again for the remaining test cases in the population until all test cases have been assigned to the pareto front. And then, calculating the crowding distance of each test case on each front surface, and analyzing the dynamic tracking file generated in the step 7 through diffoscope tools to calculate the crowding distance of each test case.
Step 9, selecting test cases with excellent performance in the population
The method specifically comprises the steps of randomly selecting two test cases from a population, comparing, and if the non-dominant ordering of the test case I is better than that of the test case J, winning the test case I, wherein the non-dominant ordering of the test case I is the same as that of the test case J, but the crowding distance of the test case I is larger than that of the test case J. The selection operation is repeated until the number of test cases that perform well is 40.
Step 10, performing cross mutation on the excellent test cases to generate new sub-populations
Specifically, the step is the same as the operation of the step 4, and a new sub population is obtained.
Step 11, verifying the generated test file and screening out test cases triggering performance defects
Specifically, the timeout time is set to 40 minutes, and z3str3 is allowed to solve the test files in the population again. If the test case still times out and the solver cannot solve, a test file capable of triggering the performance problem of the solver is found and recorded in the result set. The result set may then be reported to the developer of z3str 3.
The method can be used for guiding searching by using code statement coverage rate information, can find the performance defects of the solver in a shorter time, can help developers to locate defect positions faster by minimizing the complexity of test cases, can ensure the diversity of final test files by using a unique test case crowding distance calculation method, and can effectively detect potential performance defects in the target solver and reduce unpredictable errors caused by the defects of the solver.
Claims (1)
1. A solver performance defect detection method based on a multi-target genetic algorithm is characterized by comprising the following specific steps:
step 1, pile inserting compiling target solver
The method comprises the steps that code statement coverage rate of a test case needs to be calculated in algorithm operation, so that a code coverage rate detection tool needs to be used for instrumentation compiling of a target solver, the code coverage rate detection tool can generate accurate counts of execution of each statement in a program, the instrumentation compiling does not influence normal operation of the target solver, only a file containing statement execution times information is generated after the operation, and the code statement coverage rate of the test case is calculated in a step 7;
Step 2, randomly generating seed test file sets to form a primary population
Randomly generating test case files conforming to SMT grammar rules, wherein the test case files form a first generation population, namely each individual in the population is a test file, and the size of the population represents the number of the test files contained in the population;
Step 3, screening seed test files in the primary population by a binary tournament selection method
The method for selecting the binary tournament comprises the steps of taking out two test files from the population each time, wherein the primary screening can select one of the test files which enables the target solver to run for a longer time as the test file with excellent performance;
step 4, performing cross mutation on fine test files in the population to generate offspring population
Selecting a test file to be operated from the test files with excellent performance each time, judging which operation should be performed on the test file to generate a new test file according to the crossover rate and the mutation rate, and continuously performing the operation until the number of the new test files reaches the specified population number;
Selecting two test files to exchange each other's assertion statement by a crossover operator, wherein the crossover operator is used for selecting a part of assertion statements in the two test files to exchange in order to ensure enough crossover quantity;
The mutation operator is operated aiming at a single test file, and comprises newly built variables, deleted variables, added assertion statement, deleted assertion statement, character strings and numbers in alternative assertion statement, functions in alternative assertion statement and nodes with the same substitution type;
step 5, judging whether the algorithm converges or reaches the maximum iteration number of the algorithm
Judging whether the maximum iteration times of the algorithm are reached or whether the algorithm is converged, if not, jumping to the step 6 to iterate the algorithm, and if the maximum iteration times are reached or the algorithm is converged, jumping to the step 11, wherein the algorithm convergence means that the average fitness of the population is not changed within a certain algebra;
step 6, combining the excellent test file in the parent and the test file of the child population to generate a new population
Combining the excellent test files in the parent and the test files in the child population into a new test file set, namely a new population, and performing the next iteration operation;
step 7, evaluating the adaptability of the test files in the population, and respectively calculating the running time difference of the solver, the code coverage rate and the complexity of the test cases
The method comprises the steps of carrying out fitness function evaluation on each test file in a population, wherein three optimization target indexes are used in an algorithm, wherein a first optimization target is the running time difference of a target solver and a reference solver, and under the appointed timeout time, the target solver and the reference solver are used for respectively running test cases, and the time spent of the target solver and the reference solver is counted; the method comprises the steps of obtaining a code coverage information file and a dynamic tracking file, wherein the code coverage information file and the dynamic tracking file are generated in the process by using the running time difference of a target solver and a reference solver as a first fitness score, the code statement coverage of the target solver is obtained by using code statement execution information of the code coverage information file, the code statement coverage of the target solver in the running time of the test case is calculated by using weighting scores, namely, the proportion of the number of covered code statements and the total code statement number of the target solver in the execution of the test case is counted as a second fitness score;
step 8, performing non-dominated pareto sorting on the test cases in the population, and calculating crowding distances among the test cases
Selecting all non-dominant test cases from a population to serve as a pareto front, then removing the test cases from the population, selecting non-dominant test cases again to form a new pareto front, repeating the operation until all the test cases are added to the pareto front, and calculating crowding distances among the test cases by using dynamic tracking files generated by each test case in the step 7 when the target solver operates for the selection operation in the step 9;
Step 9, selecting test cases with excellent performance in the population
The method comprises the steps of selecting and screening good test cases by using a binary tournament based on dominance, selecting and screening the good test cases by using a non-dominance pareto ordering, wherein each test case has two attributes, namely a non-dominance ordering and a crowding distance, observing the following rules when the test case I is compared with the test case J, wherein the non-dominance ordering of the test case I is superior to the test case J, the test case I wins out, the test case I is the same as the non-dominance ordering of the test case J, but the crowding distance of the test case I is greater than the test case J, the test case I wins out, repeating the selection operation until the number of the test cases with good performance reaches the specified population size, and forming a new population;
step 10, performing cross mutation on the excellent test cases to generate new sub-populations
The method specifically comprises the steps of obtaining a new sub-population in the same operation as the step 4;
step 11, verifying the generated test file and screening out test cases triggering performance defects
The method comprises the steps of enabling a target solver to re-execute test files in a population under a time-out time long enough, adding the test files into a final result set if the test files still cannot be solved, triggering performance defects of the solver by test examples in the result set, and ending an algorithm.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202110767573.7A CN113377676B (en) | 2021-07-07 | 2021-07-07 | A solver performance defect detection method based on multi-objective genetic algorithm |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202110767573.7A CN113377676B (en) | 2021-07-07 | 2021-07-07 | A solver performance defect detection method based on multi-objective genetic algorithm |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN113377676A CN113377676A (en) | 2021-09-10 |
| CN113377676B true CN113377676B (en) | 2024-12-06 |
Family
ID=77581264
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202110767573.7A Active CN113377676B (en) | 2021-07-07 | 2021-07-07 | A solver performance defect detection method based on multi-objective genetic algorithm |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN113377676B (en) |
Families Citing this family (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN114880218B (en) * | 2022-04-26 | 2024-07-30 | 大连理工大学 | A search-based fault location method for SMT solvers |
| CN114827174B (en) * | 2022-04-28 | 2024-05-07 | 深圳赛宝工业技术研究院有限公司 | Method and system for synchronizing real resources and multiple virtual resources of manufacturing resources for social manufacturing |
| CN114935538A (en) * | 2022-06-06 | 2022-08-23 | 河南科技大学 | A method for measuring coefficient of friction in cold forming |
| CN119357068B (en) * | 2024-12-26 | 2025-04-04 | 天翼云科技有限公司 | Method, device, computer equipment, computer readable storage medium and computer program product for generating test cases |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN104281522A (en) * | 2014-10-14 | 2015-01-14 | 中国矿业大学 | Statement coverage and defect detection based multi-objective test data reduction method |
| CN110059009A (en) * | 2018-04-13 | 2019-07-26 | 百度（美国）有限责任公司 | Method and apparatus for testing code file |
Family Cites Families (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| IN2014CH01329A (en) * | 2014-03-13 | 2015-09-18 | Infosys Ltd | |
| CN111666209B (en) * | 2020-05-20 | 2023-03-31 | 牡丹江师范学院 | Multi-objective optimization-based test case priority ordering method |
-
2021
- 2021-07-07 CN CN202110767573.7A patent/CN113377676B/en active Active
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN104281522A (en) * | 2014-10-14 | 2015-01-14 | 中国矿业大学 | Statement coverage and defect detection based multi-objective test data reduction method |
| CN110059009A (en) * | 2018-04-13 | 2019-07-26 | 百度（美国）有限责任公司 | Method and apparatus for testing code file |
Also Published As
| Publication number | Publication date |
|---|---|
| CN113377676A (en) | 2021-09-10 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN113377676B (en) | A solver performance defect detection method based on multi-objective genetic algorithm | |
| Wardat et al. | Deeplocalize: Fault localization for deep neural networks | |
| Panichella et al. | A large scale empirical comparison of state-of-the-art search-based test case generators | |
| CN107590073B (en) | An automatic test case generation method based on path coverage software testing | |
| White et al. | Evolutionary improvement of programs | |
| CN114626071B (en) | Vulnerability-oriented fuzzy test method, system and medium | |
| CN115687115B (en) | Automatic testing method and system for mobile application program | |
| Tulsian et al. | MUX: algorithm selection for software model checkers | |
| EP4075281A1 (en) | Ann-based program test method and test system, and application | |
| Mkaouer et al. | A robust multi-objective approach for software refactoring under uncertainty | |
| Tonella et al. | Finding the optimal balance between over and under approximation of models inferred from execution logs | |
| Gagnon et al. | A critical analysis of the bat algorithm | |
| CN112181420A (en) | Compiler defect positioning method based on reinforcement learning | |
| My et al. | Survey on mutation-based test data generation | |
| Rao et al. | Optimizing the software testing efficiency by using a genetic algorithm: a design methodology | |
| CN115629998B (en) | A Test Case Screening Method Based on KMeans Clustering and Similarity | |
| CN114462043B (en) | Java deserialization vulnerability detection system and method based on reinforcement learning | |
| McGraw et al. | Generating software test data by evolution | |
| Tripathi et al. | Multi-objective ANT lion optimization algorithm based mutant test case selection for regression testing | |
| CN117251375A (en) | A two-layer fuzz testing method based on model-guided smart contract call sequence generation | |
| CN116680164A (en) | Circulation code test data generation method based on deep learning fuzzy test | |
| El Mandouh et al. | Guiding functional verification regression analysis using machine learning and big data methods | |
| Inoue et al. | International competition on graph counting algorithms 2023 | |
| CN114880218B (en) | A search-based fault location method for SMT solvers | |
| Kumar et al. | Notice of Retraction: Generation of efficient test data using path selection strategy with elitist GA in regression testing |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |