Multi-Criteria Test Suite Minimization with Integer Nonlinear Programming

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
 
 
2
 
Source: https://www.imore.com/evolution-social-media-icon
 
 
3
 
4
5
Regression Testing
Provide confidence that the newly introduced features of
the system do not interfere with the existing features.
6
Issue of Regression Testing
 
Too many test cases to rerun for regression testing
7 weeks to rerun
1
> 30 million test executions
2
Test suite management
Test suite minimization
Test case prioritization
Test case selection
 
 
 
7
 
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
Multi-Criteria Test Suite Minimization
(MCTSM)
Multi-Criteria Test Suite Minimization (MCTSM)
Problem: Bi-Criteria Example
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
e.g.,
10
Constraints
(Limit the solution space)
Statement Coverage (Constraint Criterion)
 
11
Use the optimization criterion (fault detection)
to select the best solution
Fault Detection Effectiveness
(Optimization Criterion)
12
 
“Fault revealing capability”:
Linear Formulation
for the Bi-Criteria TSM Problem
13
 
The optimal solution
(with minimal value)
Limitation of Prior Work
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
16
Fault revealing capability:
Should be dynamically adjusted
depending on current selection of test cases
Overlap among faults should be considered
When t
2
 is Selected…
17
The optimal solution by our formulation
is also the best solution for the MCTSM problem
Nonlinearly Model Test-Case Dependencies
in Objective Function
18
Model test-case dependency in terms of faults
(whether the fault is already covered
 by other previously selected test cases)
Nonlinearly Model Test-Case Dependencies
in Objective Function
19
Multiplication of decision variables
(nonlinear)
MCTSM is inherently nonlinear
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 variables
1
 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 MINTS
1
 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
 
 
 
 
 
 
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
 
 
27
Equivalent suite size reduction by Nemo
(1) Bi-criteria problem: FDE on Known Faults
 
 
28
Avg. 13% (Max. 24%) improvement by Nemo
(1) Bi-criteria problem: FDE on New Faults
 
 
29
Avg. 4% (Max. 13%) improvement by Nemo
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
 
 
31
+124%
Avg. 81% (Max. 124%) improvement by Nemo
(2) Tri-criteria problem: FDE on New Faults
 
 
32
Avg. 47% (Max. 105%) improvement by Nemo
(2) Tri-criteria problem: Statement Coverage
 
 
33
+159%
Avg. 46% (Max. 159%) improvement by Nemo
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)
34
 
Thank You!
Thank You!
Slide Note
Embed
Share

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.


Uploaded on Aug 01, 2024 | 1 Views


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


  1. 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

  2. Software Evolves Rapidly Source: https://www.imore.com/evolution-social-media-icon 2

  3. 3

  4. 4

  5. Regression Testing Provide confidence that the newly introduced features of the system do not interfere with the existing features. 5

  6. 6

  7. 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

  8. 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

  9. Outline Background and motivation Prior research (Linear formulation of MCTSM) Nemo (Nonlinear formulation of MCTSM) Evaluation Conclusion 9

  10. 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

  11. 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

  12. 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

  13. 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

  14. 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

  15. Outline Background and motivation Prior research (Linear formulation of MCTSM) Nemo (Nonlinear formulation of MCTSM) Evaluation Conclusion 15

  16. 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

  17. 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

  18. 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

  19. 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

  20. 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

  21. Outline Background and motivation Prior research (Linear formulation of MCTSM) Nemo (Nonlinear formulation of MCTSM) Evaluation Conclusion 21

  22. 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

  23. 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

  24. 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

  25. 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

  26. 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

  27. (1) Bi-criteria problem: Suite Size Reduction Equivalent suite size reduction by Nemo 27

  28. (1) Bi-criteria problem: FDE on Known Faults Avg. 13% (Max. 24%) improvement by Nemo 28

  29. (1) Bi-criteria problem: FDE on New Faults Avg. 4% (Max. 13%) improvement by Nemo 29

  30. 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

  31. (2) Tri-criteria problem: FDE on Known Faults +124% Avg. 81% (Max. 124%) improvement by Nemo 31

  32. (2) Tri-criteria problem: FDE on New Faults Avg. 47% (Max. 105%) improvement by Nemo 32

  33. (2) Tri-criteria problem: Statement Coverage +159% Avg. 46% (Max. 159%) improvement by Nemo 33

  34. 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

Related


More Related Content

giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#