Reformulating Branch Coverage as a Many-Objective Optimization Problem
The DOI matches its Crossref record; 25 of the 25 references it cites were found in a registry or an index.
Abstract
Test data generation has been extensively investigated as a search problem, where the search goal is to maximize the number of covered program elements (e.g., branches). Recently, the whole suite approach, which combines the fitness functions of single branches into an aggregate, test suite-level fitness, has been demonstrated to be superior to the traditional single-branch at a time approach. In this paper, we propose to consider branch coverage directly as a many-objective optimization problem, instead of aggregating multiple objectives into a single value, as in the whole suite approach. Since programs may have hundreds of branches (objectives), traditional many-objective algorithms that are designed for numerical optimization problems with less than 15 objectives are not applicable. Hence, we introduce a novel highly scalable many-objective genetic algorithm, called MOSA (Many-Objective Sorting Algorithm), suitably defined for the many- objective branch coverage problem. Results achieved on 64 Java classes indicate that the proposed many-objective algorithm is significantly more effective and more efficient than the whole suite approach. In particular, effectiveness (coverage) was significantly improved in 66% of the subjects and efficiency (search budget consumed) was improved in 62% of the subjects on which effectiveness remains the same.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
A fast and elitist multiobjective genetic algorithm: NSGA-II
Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. (2002) · IEEE Transactions on Evolutionary Computation · doi:10.1109/4235.996017 · Cited by 50,053
Practical Nonparametric Statistics
Groggel, D. J. (2000) · Technometrics · doi:10.1080/00401706.2000.10486067 · Cited by 11,041
SPEA2: Improving the strength pareto evolutionary algorithm
Zitzler, E., Laumanns, M., & Thiele, L. (2001) · doi:10.3929/ethz-a-004284029 · Cited by 5,008 · cited 3×
“…been demonstrated that classical multi-objective evolutionary algorithms, such as the Non-dominated Sorting Genetic Algorithm II (NSGA-II) [14] and the improved Strength Pareto Evolutionary Algorithm (SPEA2) [15], are not effective in solving optimization problems with more than three-objectives.”
BackgroundIndicator-Based Selection in Multiobjective Search
Zitzler, E., & Künzli, S. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-30217-9_84 · Cited by 2,259 · cited 1×
“Zitzler and Künzli [18] proposed the usage of the hypervolume indicator instead of the Pareto dominance when selecting the best solutions to form the next generation.”
BackgroundPractical Nonparametric Statistics (2nd ed).
Groeneveld, R. A., & Conover, W. J. (1981) · Journal of the American Statistical Association · doi:10.2307/2287607 · Cited by 1,849
Combining Convergence and Diversity in Evolutionary Multiobjective Optimization
Laumanns, M., Thiele, L., Deb, K., & Zitzler, E. (2002) · Evolutionary Computation · doi:10.1162/106365602760234108 · Cited by 1,487 · cited 1×
“For example, Laumanns et al. [16] proposed the usage of an -dominance relation ( - MOEA) instead of the classical one.”
BackgroundSearch‐based software test data generation: a survey
McMinn, P. (2004) · Software Testing, Verification and Reliability · doi:10.1002/stvr.294 · Cited by 1,368 · cited 4×
“In the literature, two variants of the single objective formulation can be found: (i) targeting one branch at a time [2], and (ii) targeting all branches at once (whole suite approach [3]).”
BackgroundMethodInfluentialDeb, K., & Deb, K. (2014) · Search Methodologies · doi:10.1007/978-1-4614-6940-7_15 · Cited by 1,248 · cited 3×
“In many-objective optimization, candidate solutions are evaluated in terms of Pareto dominance and Pareto optimality [4]:”
BackgroundInfluentialA Critique and Improvement of the CL Common Language Effect Size Statistics of McGraw and Wong
Vargha, A., & Delaney, H. D. (2000) · Journal of Educational and Behavioral Statistics · doi:10.3102/10769986025002101 · Cited by 938 · cited 1×
“Other than testing the null hypothesis, we used the Vargha-Delaney (Â12) statistic [25] to measure the effect size, i.”
MethodA Grid-Based Evolutionary Algorithm for Many-Objective Optimization
Yang, S., Li, M., Liu, X., & Zheng, J. (2013) · IEEE Transactions on Evolutionary Computation · doi:10.1109/tevc.2012.2227145 · Cited by 893 · cited 1×
“Yang et al. [19] introduced a Grid-based Evolutionary Algorithm (GrEA) that divides the search space into hyperboxes of a given size and uses the concepts of grid dominance and grid difference to determine the mutual relationship of individuals in a grid environment.”
MethodA Critique and Improvement of the "CL" Common Language Effect Size Statistics of McGraw and Wong
Vargha, A., Delaney, H. D., & Vargha, A. (2000) · Journal of Educational and Behavioral Statistics · doi:10.2307/1165329 · Cited by 828
Fraser, G., & Arcuri, A. (2013) · IEEE Transactions on Software Engineering · doi:10.1109/tse.2012.14 · Cited by 586 · cited 2×
“Keywords: Evolutionary testing, many-objective optimization, branch coverage.”
BackgroundPractical Nonparametric Statistics, 3rd Ed.
Borror, C. M. (2001) · Journal of Quality Technology · doi:10.1080/00224065.2001.11980074 · Cited by 583
Evolutionary testing of classes
Tonella, P. (2004) · Proceedings of the 2004 ACM SIGSOFT international symposium on Software testing and analysis · doi:10.1145/1007512.1007528 · Cited by 410 · cited 1×
“Hence, we introduce a novel highly scalable many-objective genetic algorithm, called MOSA (Many-Objective Sorting Algorithm), suitably defined for the many-objective branch coverage problem.”
MethodSelf-citationReducing Local Optima in Single-Objective Problems by Multi-objectivization
Knowles, J. D., Watson, R. A. R., & Corne, D. (2001) · Lecture notes in computer science · doi:10.1007/3-540-44719-9_19 · Cited by 403 · cited 4×
“Stemming from the consideration that many-objective approaches can be more efficient when solving complex problems [5], [6], in this paper we propose to explicitly reformulate the branch coverage criterion as a many-objective optimization problem, where different branches are considered as different objectives to be o…”
BackgroundInfluentialParameter tuning or default values? An empirical investigation in search-based software engineering
Arcuri, A., & Fraser, G. (2013) · Empirical Software Engineering · doi:10.1007/s10664-013-9249-9 · Cited by 384 · cited 2×
“Furthermore, such attempts to find the best configuration may not always pay off in practice as compared to using default configurations widely used in the literature [26].”
MethodResultA survey on multi-objective evolutionary algorithms for many-objective problems
von Lücken, C., Barán, B., & Brizuela, C. (2014) · Computational Optimization and Applications · doi:10.1007/s10589-014-9644-1 · Cited by 297 · cited 3×
“As a consequence, it is not possible to assign a preference among individuals for selection purposes and the search process becomes equivalent to a random one [22].”
BackgroundInfluentialAn Investigation on Preference Order Ranking Scheme for Multiobjective Evolutionary Optimization
di Pierro, F., Khu, S.-T., & Savi, D. A. (2007) · IEEE Transactions on Evolutionary Computation · doi:10.1109/tevc.2006.876362 · Cited by 280 · cited 1×
“[20] used a preference order-approach (POGA) as an optimality criterion in the ranking stage of NSGA-II.”
MethodAn improved NSGA-III procedure for evolutionary many-objective optimization
Yuan, Y., Xu, H., & Wang, B. (2014) · Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation · doi:10.1145/2576768.2598342 · Cited by 183 · cited 1×
“Yuan et al. [21] proposed θ-NSGA-III, an improved version of the classical NSGA-II, where the non-dominated sorting scheme is based on the concepts of θ-dominance to rank solutions in the environmental selection phase, which ensures both convergence and diversity.”
BackgroundA multi-objective approach to search-based test data generation
Lakhotia, K., Harman, M., & McMinn, P. (2007) · Genetic and Evolutionary Computation Conference (GECCO) · doi:10.1145/1276958.1277175 · Cited by 158 · cited 1×
“In this paper, we introduce a novel highly-scalable manyobjective GA, named MOSA (Many-Objective Sorting Algorithm), that modifies the selection scheme used by existing 978-1-4799-7125-1/15/$31.00 ©2015 IEEE many-objective GA. Results achieved on 64 Java classes extracted from 16 well-known…”
MethodInfluentialHarman, M., Kim, S. G., Lakhotia, K., McMinn, P., & Yoo, S. (2010) · 2010 Third International Conference on Software Testing, Verification, and Validation Workshops · doi:10.1109/icstw.2010.31 · Cited by 85 · cited 1×
“In this paper, we introduce a novel highly-scalable manyobjective GA, named MOSA (Many-Objective Sorting Algorithm), that modifies the selection scheme used by existing 978-1-4799-7125-1/15/$31.00 ©2015 IEEE many-objective GA. Results achieved on 64 Java classes extracted from 16 well-known…”
MethodInfluentialEvolutionary algorithms for the multi‐objective test data generation problem
Ferrer, J., Chicano, F., & Alba, E. (2011) · Software Practice and Experience · doi:10.1002/spe.1135 · Cited by 80 · cited 1×
“In this paper, we introduce a novel highly-scalable manyobjective GA, named MOSA (Many-Objective Sorting Algorithm), that modifies the selection scheme used by existing 978-1-4799-7125-1/15/$31.00 ©2015 IEEE many-objective GA. Results achieved on 64 Java classes extracted from 16 well-known…”
MethodInfluentialA Multi-Objective Genetic Algorithm to Test Data Generation
Pinto, G., & Vergílio, S. R. (2010) · IEEE International Conference on Tools with Artificial Intelligence (ICTAI) · doi:10.1109/ictai.2010.26 · Cited by 43 · cited 1×
“In this paper, we introduce a novel highly-scalable manyobjective GA, named MOSA (Many-Objective Sorting Algorithm), that modifies the selection scheme used by existing 978-1-4799-7125-1/15/$31.00 ©2015 IEEE many-objective GA. Results achieved on 64 Java classes extracted from 16 well-known…”
MethodInfluentialOn the Effectiveness of Whole Test Suite Generation
Arcuri, A., & Fraser, G. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-09940-8_1 · Cited by 23 · cited 2×
“, targeting one branch at a time) has been shown to be inferior to the whole suite approach [3], [7], mainly because it is significantly affected by the inevitable presence of unreachable or difficult targets.”
BackgroundOrthogonal exploration of the search space in evolutionary test case generation
Kifetew, F. M., Panichella, A., Lucia, A. D., Oliveto, R., & Tonella, P. (2013) · International Symposium on Software Testing and Analysis · doi:10.1145/2483760.2483789 · Cited by 22 · cited 1×
“Finally, since MOSA uses the crowding distance when selecting the test cases, it promotes diversity, which represents a key factor to avoid premature convergence toward suboptimal regions of the search space [23].”
MethodSelf-citation
Cited by
Panichella, A., Kifetew, F. M., & Tonella, P. (2018) · IEEE Transactions on Software Engineering · doi:10.1109/tse.2017.2663435 · Cited by 352
Self-citationEffective test generation using pre-trained Large Language Models and mutation testing
Dakhel, A. M., Nikanjam, A., Majdinasab, V., Khomh, F., & Desmarais, M. C. (2024) · Information and Software Technology · doi:10.1016/j.infsof.2024.107468 · Cited by 157
Exploring and Unleashing the Power of Large Language Models in Automated Code Translation
Yang, Z., Liu, F., Yu, Z., Keung, J. W., Li, J., Liu, S., Hong, Y., Ma, X., Jin, Z., & Li, G. (2024) · Proceedings of the ACM on Software Engineering · doi:10.1145/3660778 · Cited by 104
Metadata
- Authors
- Panichella, A., Kifetew, F. M., & Tonella, P.
- Venue
- 2015 IEEE 8th International Conference on Software Testing, Verification and Validation (ICST)
- Publisher
- IEEE
- Published
- 2015-04
- Pages
- 1-10
- OpenAlex
- W1599808047
- Cited by
- 174
- References
- 25
- FWCI
- 10.35
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.