Multi-Criteria Test Suite Minimization with Integer Nonlinear Programming
The study introduces a method for minimizing test suites using Integer Nonlinear Programming. It addresses regression testing challenges, such as managing large numbers of test cases, through Multi-Criteria Test Suite Minimization (MCTSM). The research explores the application of Integer Programming to optimize test case selection and prioritization, enhancing software testing efficiency and quality assurance.
- Test Suite Minimization
- Integer Programming
- Regression Testing
- Software Testing
- Multi-Criteria Optimization
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Nemo: Multi-Criteria Test-Suite Minimization with Integer Nonlinear Programming Jun-Wei Lin, Reyhaneh Jabbarvand, Joshua Garcia, and Sam Malek Donald Bren School of Information and Computer Sciences University of California, Irvine
Software Evolves Rapidly Source: https://www.imore.com/evolution-social-media-icon 2
Regression Testing Provide confidence that the newly introduced features of the system do not interfere with the existing features. 5
Issue of Regression Testing Too many test cases to rerun for regression testing 7 weeks to rerun1 > 30 million test executions2 Test suite management Test suite minimization Test case prioritization Test case selection Multi-Criteria Test Suite Minimization (MCTSM) 1 G. Rothermel, R. H. Untch, C. Chu, and M. J. Harrold. Prioritizing test cases for regression testing. TSE 01 2 K. Herzig, M. Greiler, J. Czerwonka, and B. Murphy. The Art of Testing Less Without Sacrificing Quality. ICSE 15 7
Multi-Criteria Test Suite Minimization (MCTSM) Problem: Bi-Criteria Example ? = ?1,?2,?3 Find a minimal subset of ? Covers all statements ( constraint criterion ) ?1,?2, ?2,?3 Reveals as many distinct faults as possible ( optimization criterion ) ?1,?2 8
Outline Background and motivation Prior research (Linear formulation of MCTSM) Nemo (Nonlinear formulation of MCTSM) Evaluation Conclusion 9
Formulate MCTSM with Integer Programming Integer Programming: an optimization technique Objective function e.g., ??: decision variables ??: coefficients Minimize ?1?1+ ?2?2 Subject to ?1+ ?2 1 and ?? are binary variables Minimize ?1?1+ ?2?2 Subject to ?1+ ?2 1 Constraints (Limit the solution space) 10
Statement Coverage (Constraint Criterion) ?1,?2,?3:?????? ????????? Constraints: ????1 1?1+ ?3 1 ????2 ????3 ?2+ ?3 1 ?2 1 The subsets satisfying the constraints: ?1,?2, ?2,?3,{?1,?2,?3} Use the optimization criterion (fault detection) to select the best solution 11
Fault Detection Effectiveness (Optimization Criterion) Minimize 1 1 Minimize 1 1 4?1+ 1 3 4?1+ 1 3 4?2+ 1 3 4?2+ 1 3 4?3 4?3 Fault revealing capability : ?1:1 ?2:3 ?3:3 4 4 4 12
Linear Formulation for the Bi-Criteria TSM Problem Minimize 1 1 4?1+ 1 3 4?2+ 1 3 4?3 The subsets satisfying the constraints: 1 1 + 1 3 ?1,?2: = 1 4 4 1 3 + 1 3 =1 The optimal solution (with minimal value) ?2,?3: 4 4 2 1 1 + 1 3 + 1 3 =5 ?1,?2,?3: 4 4 4 4 13
Limitation of Prior Work The optimal solution by the linear formulation: ?2,?3 The best solution for the MCTSM problem: ??,?? Linear formulation doesn t consider overlap among faults covered by test cases 14
Outline Background and motivation Prior research (Linear formulation of MCTSM) Nemo (Nonlinear formulation of MCTSM) Evaluation Conclusion 15
Fault Revealing Capability of Test Cases Minimize 1 1 4?1+ 1 3 4?2+ 1 3 Should be dynamically adjusted depending on current selection of test cases 4?3 Fault revealing capability: ?1:1 ?2:3 ?3:3 4 4 4 Overlap among faults should be considered 16
When t2is Selected Fault revealing capability for ?1 and ?3: ?3:0 ?1:1 4 4 ?1 ?2 0 0 0 1 ?3 1 1 1 0 0 ?3 0 0 0 ?1,?2: 1 1 + 1 3 = 1 ?1 ?2 ?3 ?4 1 1 1 0 4 4 ?2,?3: 1 0 The optimal solution by our formulation is also the best solution for the MCTSM problem + 1 0 = 2 4 4 17
Nonlinearly Model Test-Case Dependencies in Objective Function ???????? |?| ? 1 ??? 1 ?? ? ??? ?? ?? 1 ?? , ?? ?? ?=1 ?=1 Model test-case dependency in terms of faults (whether the fault is already covered by other previously selected test cases) 18
Nonlinearly Model Test-Case Dependencies in Objective Function ???????? |?| ? 1 ? MCTSM is inherently nonlinear 1 ??? ?? ?? 1 ?? ?? , ?? ?? ?=1 ?=1 1 ? ?=1 |?| ? = ?=1 ??? ?? ??1 ????, ?? ?? ?? Multiplication of decision variables (nonlinear) 19
Challenge of Solving Nonlinear Formulation Issues of nonlinear solvers No known efficient algorithm to find optimal solution May return sub-optimal solution, if the objective function is non-convex Use auxiliary variables1 to transform the nonlinear formulation into an equivalent linear form Linear solvers can be leveraged to find optimal solutions 1 L. A. Wolsey. 1998. Integer programming. Wiley-Interscience, New York, NY, USA. 20
Outline Background and motivation Prior research (Linear formulation of MCTSM) Nemo (Nonlinear formulation of MCTSM) Evaluation Conclusion 21
Empirical Evaluation MINTS vs. Nemo MINTS Re-implementation of MINTS1 by Hsu and Orso at Georgia Tech Linearly formulates the MCTSM problem Nemo Nonlinearly formulates the MCTSM problem Transforms the nonlinear formulation into an equivalent linear form and then use linear solvers 1 H. Y. Hsu and A. Orso. MINTS: A general framework and tool for supporting test-suite minimization. ICSE 09 22
Experimental Setup Subjects # Known Faults # New Faults Program Ver. Description LOC # Test Grep 2.7 Pattern search and match 58,344 746 54 41 Flex 2.5.4 Lexical analyzer 12,366 605 37 25 Sed 4.2 Command-line text editor 26,466 324 25 19 Make 3.80 Executables builder 23,400 158 15 9 Gzip 1.3 Data compressor 5,682 397 56 41 Use CPLEX as linear solver 23
Minimization Problems (1) Bi-criteria problem Maintain the statement coverage of the original suite Maximize fault detection effectiveness (FDE) (2) Tri-criteria problem Fix the sizes of the reduced suites Maximize both statement coverage and FDE More complex; larger solution space 24
MINTS vs. Nemo Apply MINTS and Nemo to the minimization problems Evaluate them on: Suite size reduction Effectiveness Fault detection effectiveness (FDE) on both known and new faults Statement coverage (for problem 2) 25
Minimization Problems (1) Bi-criteria problem Maintain the statement coverage of the original suite Maximize fault detection effectiveness (FDE) (2) Tri-criteria problem Fix the sizes of the reduced suites Maximize both statement coverage and FDE More complex; larger solution space 26
(1) Bi-criteria problem: Suite Size Reduction Equivalent suite size reduction by Nemo 27
(1) Bi-criteria problem: FDE on Known Faults Avg. 13% (Max. 24%) improvement by Nemo 28
(1) Bi-criteria problem: FDE on New Faults Avg. 4% (Max. 13%) improvement by Nemo 29
Minimization Problems (1) Bi-criteria problem Maintain the statement coverage of the original suite Maximize fault detection effectiveness (FDE) (2) Tri-criteria problem Fix the sizes of the reduced suites Maximize both statement coverage and FDE More complex; larger solution space 30
(2) Tri-criteria problem: FDE on Known Faults +124% Avg. 81% (Max. 124%) improvement by Nemo 31
(2) Tri-criteria problem: FDE on New Faults Avg. 47% (Max. 105%) improvement by Nemo 32
(2) Tri-criteria problem: Statement Coverage +159% Avg. 46% (Max. 159%) improvement by Nemo 33
Conclusion MCTSM problem is inherently nonlinear Programmatically transform the nonlinear formulation to a linear form Use modern ILP solvers to find optimal solutions Evaluation on minimization problems Executed up to 159% more statements and detected 124% more faults than prior work Apply to other test case management problems (e.g., selection, prioritization) Thank You! 34
