1. Boosting Search Based Testing by using Constraint Based Testing Abdelilah Sakti, Yann-Ga¨l e Gu´h´neuc, Gilles e e Pesant Introduction Motivating Example CSBT : Constrained Search Based Testing Implementation for integer data type Boosting Search Based Testing by using Constraint Based Testing Abdelilah Sakti Yann-Ga¨l Gu´h´neuc e e e Gilles Pesant Department of Computer and Software Engineering ´ Ecole Polytechnique de Montr´al, Qu´bec, Canada e e Evaluation Related work Conclusions September 28, 2012 SSBSE, Riva del Garda Pattern Trace Identification, Detection, and Enhancement in Java SOftware Cost-effective Change and Evolution Research Lab 2. Boosting Search Based Testing by using Constraint Based Testing Abdelilah Sakti, Yann-Ga¨l e Gu´h´neuc, Gilles e e Pesant Introduction What is the cost of a programming error ? Software testing approaches for finding errors What is the cost of a programming error ? Every year inadequate infrastructure software costs the U.S. economy around 60 billion $. 1996 : Flight 501 caused the destruction of the Ariane 5 rocket just 40 seconds after launching. CBT versus SBT Motivating Example CSBT : Constrained Search Based Testing Implementation for integer data type Between 1985 and 1987 : the radiotherapy machine Therac-25 sent to patients a X-ray dose 100 times greater than expected. Evaluation Related work Conclusions 2 / 19 The test is a very important phase in the life cycle of software. It may cost more than 50 % of the budget of a critical software. 3. Boosting Search Based Testing by using Constraint Based Testing Abdelilah Sakti, Yann-Ga¨l e Gu´h´neuc, Gilles e e Pesant Introduction What is the cost of a programming error ? Software testing approaches for finding errors CBT versus SBT Motivating Example CSBT : Constrained Search Based Testing Implementation for integer data type Evaluation Related work Conclusions 3 / 19 Software testing approaches for finding errors Search based testing (SBT) Was introduced in 1976 by Miller and Spooner ; Dynamic analysis of the program ; Consists of translating the test problem into an optimization problem. Constraint based testing (CBT) Was introduced in 1976 by J.C. KING ; Static analysis of the program ; Consist of translating a test problem into a constraint satisfaction problem (CSP). 4. Boosting Search Based Testing by using Constraint Based Testing Abdelilah Sakti, Yann-Ga¨l e Gu´h´neuc, Gilles e e Pesant Introduction What is the cost of a programming error ? Software testing approaches for finding errors CBT versus SBT CBT versus SBT Search based testing (SBT) + Handles any sort of programs ; - Incomplete - Depends on many parameters. Motivating Example CSBT : Constrained Search Based Testing Implementation for integer data type Evaluation Related work Conclusions 4 / 19 Constraint based testing (CBT) + Precision in test data generation ; + Ability to prove that some paths are unreachable ; - Not Scalable ; - The incompleteness of decision procedures. 5. Boosting Search Based Testing by using Constraint Based Testing Motivating Example Example : foo function Abdelilah Sakti, Yann-Ga¨l e Gu´h´neuc, Gilles e e Pesant 1 Introduction 2 Motivating Example 3 Constraint Based Testing Search based testing CSBT : Constrained Search Based Testing 4 5 6 7 8 9 Implementation for integer data type 10 11 Evaluation Related work Conclusions 5 / 19 12 13 14 int foo(int X, int Y){ if(X<=0 || Y<=0) return 0; int Z; if ((X < Y/2)|| (Y==0)) Z= 1 ; //Target 1 else if (Y>3∗X) Z=2 ; //Target 2 : (2 ∗ X >= Y ) ∧ (Y > 3 ∗ X) is unsatisfied else{ Z = fun(X,Y); //native function that returns X 2 /Y if ((Z >8) && (Y==10)) if(Z==Y) Z=3 ;//Target 3 is a nested branch predicates (10,10) } 6. Boosting Search Based Testing by using Constraint Based Testing Motivating Example Example : foo function Abdelilah Sakti, Yann-Ga¨l e Gu´h´neuc, Gilles e e Pesant 1 Introduction 2 Motivating Example 3 Constraint Based Testing Search based testing CSBT : Constrained Search Based Testing 4 5 6 7 8 9 Implementation for integer data type 10 11 Evaluation Related work Conclusions 5 / 19 12 13 14 int foo(int X, int Y){ if(X<=0 || Y<=0) return 0; int Z; if ((X < Y/2)|| (Y==0)) Z= 1 ; //Target 1 else if (Y>3∗X) Z=2 ; //Target 2 : (2 ∗ X >= Y ) ∧ (Y > 3 ∗ X) is unsatisfied else{ Z = fun(X,Y); //native function that returns X 2 /Y if ((Z >8) && (Y==10)) if(Z==Y) Z=3 ;//Target 3 is a nested branch predicates (10,10) } 7. Boosting Search Based Testing by using Constraint Based Testing Motivating Example Example : foo function Abdelilah Sakti, Yann-Ga¨l e Gu´h´neuc, Gilles e e Pesant 1 Introduction 2 Motivating Example 3 Constraint Based Testing Search based testing CSBT : Constrained Search Based Testing 4 5 6 7 8 9 Implementation for integer data type 10 11 Evaluation Related work Conclusions 5 / 19 12 13 14 int foo(int X, int Y){ if(X<=0 || Y<=0) return 0; int Z; if ((X < Y/2)|| (Y==0)) Z= 1 ; //Target 1 else if (Y>3∗X) Z=2 ; //Target 2 : (2 ∗ X >= Y ) ∧ (Y > 3 ∗ X) is unsatisfied else{ Z = fun(X,Y); //native function that returns X 2 /Y if ((Z >8) && (Y==10)) if(Z==Y) Z=3 ;//Target 3 is a nested branch predicates (10,10) } 8. Boosting Search Based Testing by using Constraint Based Testing Motivating Example Example : foo function Abdelilah Sakti, Yann-Ga¨l e Gu´h´neuc, Gilles e e Pesant 1 Introduction 2 Motivating Example 3 Constraint Based Testing Search based testing CSBT : Constrained Search Based Testing 4 5 6 7 8 9 Implementation for integer data type 10 11 Evaluation Related work Conclusions 5 / 19 12 13 14 int foo(int X, int Y){ if(X<=0 || Y<=0) return 0; int Z; if ((X < Y/2)|| (Y==0)) Z= 1 ; //Target 1 else if (Y>3∗X) Z=2 ; //Target 2 : (2 ∗ X >= Y ) ∧ (Y > 3 ∗ X) is unsatisfied else{ Z = fun(X,Y); //native function that returns X 2 /Y if ((Z >8) && (Y==10)) if(Z==Y) Z=3 ;//Target 3 is a nested branch predicates (10,10) } 9. Boosting Search Based Testing by using Constraint Based Testing Motivating Example Example : foo function Abdelilah Sakti, Yann-Ga¨l e Gu´h´neuc, Gilles e e Pesant 1 Introduction 2 Motivating Example 3 Constraint Based Testing Search based testing CSBT : Constrained Search Based Testing 4 5 6 7 8 9 Implementation for integer data type 10 11 Evaluation Related work Conclusions 12 13 14 int foo(int X, int Y){ if(X<=0 || Y<=0) return 0; int Z; if ((X < Y/2)|| (Y==0)) Z= 1 ; //Target 1 else if (Y>3∗X) Z=2 ; //Target 2 : (2 ∗ X >= Y ) ∧ (Y > 3 ∗ X) is unsatisfied else{ Z = fun(X,Y); //native function that returns X 2 /Y if ((Z >8) && (Y==10)) if(Z==Y) Z=3 ;//Target 3 is a nested branch predicates (10,10) } Challenge Combine CBT and SBT to overcome the limitations associated with each of them. 5 / 19 10. Boosting Search Based Testing by using Constraint Based Testing Motivating Example Constraint Based Testing Abdelilah Sakti, Yann-Ga¨l e Gu´h´neuc, Gilles e e Pesant Introduction Example 1 : Generated constraints for Target 3 Original version : 1 2 Motivating Example 3 Constraint Based Testing 4 Search based testing 5 CSBT : Constrained Search Based Testing Implementation for integer data type Evaluation Related work Conclusions 6 / 19 6 not((x0 ≤ 0)||(y0 ≤ 0))∧ not((x0 < y0 /2)||(y0 = 0))∧ not(y0 > 3 × x0 )∧ z3 = f un(x0 , y0 )∧ ((z3 > 8) ∧ (y0 = 10))∧ (z3 = y0 ) 11. Boosting Search Based Testing by using Constraint Based Testing Motivating Example Constraint Based Testing Abdelilah Sakti, Yann-Ga¨l e Gu´h´neuc, Gilles e e Pesant Introduction Example 1 : Generated constraints for Target 3 Original version : 1 2 Motivating Example 3 Constraint Based Testing 4 Search based testing 5 CSBT : Constrained Search Based Testing 6 Implementation for integer data type not((x0 ≤ 0)||(y0 ≤ 0))∧ not((x0 < y0 /2)||(y0 = 0))∧ not(y0 > 3 × x0 )∧ z3 = f un(x0 , y0 )∧ ((z3 > 8) ∧ (y0 = 10))∧ (z3 = y0 ) Example 1 : Constraints solutions in the domain [−2 × 104 + 1, 2 × 104 ] Evaluation Related work Original version : Conclusions 1 2 3 4 6 / 19 Unsolvable 12. Boosting Search Based Testing by using Constraint Based Testing Motivating Example Constraint Based Testing Abdelilah Sakti, Yann-Ga¨l e Gu´h´neuc, Gilles e e Pesant Introduction Example 1 : Generated constraints for Target 3 Original version : 1 2 Motivating Example 3 Constraint Based Testing 4 Search based testing 5 CSBT : Constrained Search Based Testing 6 Implementation for integer data type not((x0 ≤ 0)||(y0 ≤ 0))∧ not((x0 < y0 /2)||(y0 = 0))∧ not(y0 > 3 × x0 )∧ z3 = f un(x0 , y0 )∧ ((z3 > 8) ∧ (y0 = 10))∧ (z3 = y0 ) Example 1 : Constraints solutions in the domain [−2 × 104 + 1, 2 × 104 ] Evaluation Related work Original version : Conclusions 1 2 3 4 6 / 19 Unsolvable 13. Boosting Search Based Testing by using Constraint Based Testing Motivating Example Constraint Based Testing Abdelilah Sakti, Yann-Ga¨l e Gu´h´neuc, Gilles e e Pesant Introduction Example 1 : Generated constraints for Target 3 Original version : 1 2 Motivating Example 3 Constraint Based Testing 4 Search based testing 5 CSBT : Constrained Search Based Testing 6 Implementation for integer data type not((x0 ≤ 0)||(y0 ≤ 0))∧ not((x0 < y0 /2)||(y0 = 0))∧ not(y0 > 3 × x0 )∧ z3 = f un(x0 , y0 )∧ ((z3 > 8) ∧ (y0 = 10))∧ (z3 = y0 ) 1 2 3 4 5 6 not((x0 ≤ 0)||(y0 ≤ 0))∧ not((x0 < y0 /2)||(y0 = 0))∧ not(y0 > 3 × x0 )∧ z3 = f un(x0 , y0 )∧ ((z3 > 8) ∧ (y0 = 10))∧ (z3 = y0 ) Example 1 : Constraints solutions in the domain [−2 × 104 + 1, 2 × 104 ] Evaluation Related work Original version : Conclusions 1 2 3 4 6 / 19 Relaxed version : Unsolvable 14. Boosting Search Based Testing by using Constraint Based Testing Motivating Example Constraint Based Testing Abdelilah Sakti, Yann-Ga¨l e Gu´h´neuc, Gilles e e Pesant Introduction Example 1 : Generated constraints for Target 3 Original version : 1 2 Motivating Example 3 Constraint Based Testing 4 Search based testing 5 CSBT : Constrained Search Based Testing 6 Implementation for integer data type not((x0 ≤ 0)||(y0 ≤ 0))∧ not((x0 < y0 /2)||(y0 = 0))∧ not(y0 > 3 × x0 )∧ z3 = f un(x0 , y0 )∧ ((z3 > 8) ∧ (y0 = 10))∧ (z3 = y0 ) Relaxed version : 1 2 3 4 5 6 Example 1 : Constraints solutions in the domain [−2 × 104 + 1, 2 × 104 ] Evaluation Related work Original version : Relaxed version : Conclusions 1 Unsolvable 1 2 2 3 3 4 6 / 19 not((x0 ≤ 0)||(y0 ≤ 0))∧ not((x0 < y0 /2)||(y0 = 0))∧ not(y0 > 3 × x0 )∧ z3 = f un(x0 , y0 )∧ ((z3 > 8) ∧ (y0 = 10))∧ (z3 = y0 ) 4 x0 ∈ [5, 2 × 104 ] y0 ∈ [10, 10] 15. Boosting Search Based Testing by using Constraint Based Testing Motivating Example Constraint Based Testing Abdelilah Sakti, Yann-Ga¨l e Gu´h´neuc, Gilles e e Pesant Introduction Example 1 : Generated constraints for Target 3 Original version : 1 2 Motivating Example 3 Constraint Based Testing 4 Search based testing 5 CSBT : Constrained Search Based Testing 6 Implementation for integer data type not((x0 ≤ 0)||(y0 ≤ 0))∧ not((x0 < y0 /2)||(y0 = 0))∧ not(y0 > 3 × x0 )∧ z3 = f un(x0 , y0 )∧ ((z3 > 8) ∧ (y0 = 10))∧ (z3 = y0 ) Relaxed version : 1 2 3 4 5 6 Example 1 : Constraints solutions in the domain [−2 × 104 + 1, 2 × 104 ] Evaluation Related work Original version : Relaxed version : Conclusions 1 Unsolvable x0 ∈ [5, 2 × 104 ] y0 ∈ [10, 10] 3 3 4 1 2 2 6 / 19 not((x0 ≤ 0)||(y0 ≤ 0))∧ not((x0 < y0 /2)||(y0 = 0))∧ not(y0 > 3 × x0 )∧ z3 = f un(x0 , y0 )∧ ((z3 > 8) ∧ (y0 = 10))∧ (z3 = y0 ) Search space size is (16 × 108 ) 4 Search space size is (2 × 104 − 5) 16. Boosting Search Based Testing by using Constraint Based Testing Abdelilah Sakti, Yann-Ga¨l e Gu´h´neuc, Gilles e e Pesant Introduction Motivating Example Constraint Based Testing Search based testing CSBT : Constrained Search Based Testing Implementation for integer data type Evaluation Related work Conclusions 7 / 19 Search based testing 17. Boosting Search Based Testing by using Constraint Based Testing Abdelilah Sakti, Yann-Ga¨l e Gu´h´neuc, Gilles e e Pesant Introduction Motivating Example Constraint Based Testing Search based testing CSBT : Constrained Search Based Testing Implementation for integer data type Evaluation Related work Conclusions 7 / 19 Search based testing 18. Boosting Search Based Testing by using Constraint Based Testing Abdelilah Sakti, Yann-Ga¨l e Gu´h´neuc, Gilles e e Pesant Introduction Motivating Example Constraint Based Testing Search based testing CSBT : Constrained Search Based Testing Implementation for integer data type Evaluation Related work Conclusions 7 / 19 Search based testing 19. Boosting Search Based Testing by using Constraint Based Testing Search based testing Abdelilah Sakti, Yann-Ga¨l e Gu´h´neuc, Gilles e e Pesant Introduction Motivating Example Constraint Based Testing Search based testing CSBT : Constrained Search Based Testing Implementation for integer data type Evaluation Related work Conclusions 7 / 19 Random aspect used to generate the initial population and also, less often, during the evolution process ; 20. Boosting Search Based Testing by using Constraint Based Testing Search based testing Abdelilah Sakti, Yann-Ga¨l e Gu´h´neuc, Gilles e e Pesant Introduction Motivating Example Constraint Based Testing Search based testing CSBT : Constrained Search Based Testing Implementation for integer data type Evaluation Related work Conclusions Random aspect used to generate the initial population and also, less often, during the evolution process ; Start SBT with some test candidates drawn from CBT is better than a random initial population. 7 / 19 21. Boosting Search Based Testing by using Constraint Based Testing Abdelilah Sakti, Yann-Ga¨l e Gu´h´neuc, Gilles e e Pesant Introduction Motivating Example CSBT : Constrained Search Based Testing Overview Unit Under Test Relaxation Example : Unit Under Test Relaxation Constrained Population Generator(CPG) Constrained Evolution Operator (CEO) Implementation for integer data type Evaluation Related work Conclusions 8 / 19 CSBT : Constrained Search Based Testing Overview Program input data 22. Boosting Search Based Testing by using Constraint Based Testing Abdelilah Sakti, Yann-Ga¨l e Gu´h´neuc, Gilles e e Pesant CSBT : Constrained Search Based Testing Overview Program input data Introduction Motivating Example T1 CSBT : Constrained Search Based Testing Overview Unit Under Test Relaxation Example : Unit Under Test Relaxation Constrained Population Generator(CPG) T3 Constrained Evolution Operator (CEO) Implementation for integer data type Evaluation Related work Conclusions 8 / 19 T2 23. Boosting Search Based Testing by using Constraint Based Testing Abdelilah Sakti, Yann-Ga¨l e Gu´h´neuc, Gilles e e Pesant CSBT : Constrained Search Based Testing Overview Program input data Introduction Motivating Example T1 CSBT : Constrained Search Based Testing R1 Overview Unit Under Test Relaxation Example : Unit Under Test Relaxation Constrained Population Generator(CPG) T3 Constrained Evolution Operator (CEO) Implementation for integer data type Evaluation Related work Conclusions 8 / 19 R2 T2 Unit Under Test Relaxation. 24. Boosting Search Based Testing by using Constraint Based Testing Abdelilah Sakti, Yann-Ga¨l e Gu´h´neuc, Gilles e e Pesant CSBT : Constrained Search Based Testing Overview Program input data Introduction × Motivating Example CSBT : Constrained Search Based Testing × Unit Under Test Relaxation. T1 R1 Overview Unit Under Test Relaxation × Example : Unit Under Test Relaxation Constrained Population Generator(CPG) T3 Constrained Evolution Operator (CEO) Implementation for integer data type Evaluation Related work Conclusions 8 / 19 × R2 T2 × 25. Boosting Search Based Testing by using Constraint Based Testing Abdelilah Sakti, Yann-Ga¨l e Gu´h´neuc, Gilles e e Pesant CSBT : Constrained Search Based Testing Overview Program input data Introduction × Motivating Example CSBT : Constrained Search Based Testing × T1 Unit Under Test Relaxation. ∗ R1 Overview Unit Under Test Relaxation Example : Unit Under Test Relaxation Constrained Population Generator(CPG) Constrained Evolution Operator (CEO) Implementation for integer data type Evaluation Related work Conclusions 8 / 19 ∗ ∗ ∗ ∗ R2 × T3 T2 × × Constrained Population Generator (CPG). 26. Boosting Search Based Testing by using Constraint Based Testing Abdelilah Sakti, Yann-Ga¨l e Gu´h´neuc, Gilles e e Pesant CSBT : Constrained Search Based Testing Overview Program input data Introduction × Motivating Example CSBT : Constrained Search Based Testing × T1 Unit Under Test Relaxation. ∗ R1 Overview Unit Under Test Relaxation × Example : Unit Under Test Relaxation Constrained Population Generator(CPG) Constrained Evolution Operator (CEO) Implementation for integer data type Evaluation Related work Conclusions 8 / 19 ∗ ∗ ∗ R2 T3 ∗ T2 × × Constrained Population Generator (CPG). 27. Boosting Search Based Testing by using Constraint Based Testing Abdelilah Sakti, Yann-Ga¨l e Gu´h´neuc, Gilles e e Pesant CSBT : Constrained Search Based Testing Overview Program input data Introduction × Motivating Example CSBT : Constrained Search Based Testing × T1 Unit Under Test Relaxation. ∗ R1 Overview Unit Under Test Relaxation × Example : Unit Under Test Relaxation Constrained Population Generator(CPG) Constrained Evolution Operator (CEO) Implementation for integer data type Evaluation Related work Conclusions 8 / 19 ∗ ∗ ∗ R2 ∗ Constrained Population Generator (CPG). T3 ∗ T2 × × Constrained Evolution Operator (CEO). 28. Boosting Search Based Testing by using Constraint Based Testing CSBT : Constrained Search Based Testing Unit Under Test Relaxation Abdelilah Sakti, Yann-Ga¨l e Gu´h´neuc, Gilles e e Pesant Introduction Motivating Example CSBT : Constrained Search Based Testing 1. For each data type that needs a different solver a new relaxed version is created. 2. Any statement over unsupported data type is ignored ; Overview Unit Under Test Relaxation Example : Unit Under Test Relaxation Constrained Population Generator(CPG) Constrained Evolution Operator (CEO) Implementation for integer data type Evaluation Related work Conclusions 9 / 19 3. Any unsupported expression (function call, operator) is relaxed ; 4. Any variable assigned inside a loop is relaxed just after this loop ; 29. Boosting Search Based Testing by using Constraint Based Testing Abdelilah Sakti, Yann-Ga¨l e Gu´h´neuc, Gilles e e Pesant CSBT : Constrained Search Based Testing Example : Unit Under Test Relaxation 1 2 3 Introduction 4 Motivating Example 6 CSBT : Constrained Search Based Testing Overview Unit Under Test Relaxation Example : Unit Under Test Relaxation Constrained Population Generator(CPG) Constrained Evolution Operator (CEO) Implementation for integer data type Evaluation Related work Conclusions 10 / 19 5 7 8 9 10 intStr(int x,int y,String S1,String S2) { int y= x«y; int x=y+x/y; String s=S1+S2; if((s.equals(” OK” ) && (x>0) && s.length()>x) return 1; // Target return 0; } 30. Boosting Search Based Testing by using Constraint Based Testing Abdelilah Sakti, Yann-Ga¨l e Gu´h´neuc, Gilles e e Pesant CSBT : Constrained Search Based Testing Example : Unit Under Test Relaxation 1 2 3 Introduction 4 Motivating Example 6 CSBT : Constrained Search Based Testing Overview Unit Under Test Relaxation Example : Unit Under Test Relaxation Constrained Population Generator(CPG) Constrained Evolution Operator (CEO) Implementation for integer data type Evaluation Related work Conclusions 10 / 19 5 7 8 9 10 intStr(int x,int y,String S1,String S2) { int y= x«y; int x=y+x/y; String s=S1+S2; if((s.equals(” OK” ) && (x>0) && s.length()>x) return 1; // Target return 0; } 31. Boosting Search Based Testing by using Constraint Based Testing Abdelilah Sakti, Yann-Ga¨l e Gu´h´neuc, Gilles e e Pesant CSBT : Constrained Search Based Testing Example : Unit Under Test Relaxation 1 2 3 Introduction 4 Motivating Example 6 CSBT : Constrained Search Based Testing Overview Unit Under Test Relaxation Example : Unit Under Test Relaxation Constrained Population Generator(CPG) Constrained Evolution Operator (CEO) Implementation for integer data type Evaluation Related work Conclusions 10 / 19 5 7 8 9 10 intStr(int x,int y,String S1,String S2) { int y= x«y; int x=y+x/y; String s=S1+S2; if((s.equals(” OK” ) && (x>0) && s.length()>x) return 1; // Target return 0; } 32. Boosting Search Based Testing by using Constraint Based Testing CSBT : Constrained Search Based Testing Example : Unit Under Test Relaxation Abdelilah Sakti, Yann-Ga¨l e Gu´h´neuc, Gilles e e Pesant 1 2 3 Introduction 4 Motivating Example 6 5 7 CSBT : Constrained Search Based Testing 8 9 Overview 10 Unit Under Test Relaxation Example : Unit Under Test Relaxation Constrained Population Generator(CPG) Constrained Evolution Operator (CEO) Implementation for integer data type 1 2 3 4 5 Evaluation 6 Related work 7 Conclusions 8 9 10 10 / 19 intStr(int x,int y,String S1,String S2) { int y= x«y; int x=y+x/y; String s=S1+S2; if((s.equals(” OK” ) && (x>0) && s.length()>x) return 1; // Target return 0; } intStr(int x,int y,String S1,String S2) { x«y; int y= int x=y+x/y; String s=S1+S2; OK”) if((s.equals(” && (x>0) && s.length()>x) return 1; // Target return 0; } 33. Boosting Search Based Testing by using Constraint Based Testing CSBT : Constrained Search Based Testing Example : Unit Under Test Relaxation Abdelilah Sakti, Yann-Ga¨l e Gu´h´neuc, Gilles e e Pesant 1 2 3 Introduction 4 Motivating Example 6 5 7 CSBT : Constrained Search Based Testing 8 9 Overview 10 Unit Under Test Relaxation Example : Unit Under Test Relaxation Constrained Population Generator(CPG) Constrained Evolution Operator (CEO) Implementation for integer data type 1 2 3 4 5 Evaluation 6 Related work 7 Conclusions 8 9 10 10 / 19 intStr(int x,int y,String S1,String S2) { int y= x«y; int x=y+x/y; String s=S1+S2; if((s.equals(” OK” ) && (x>0) && s.length()>x) return 1; // Target return 0; } intStr(int x,int y, ){ x«y; int y= int x=y+x/y; ; if(( && (x>0) && s.length()>x) return 1; // Target return 0; } 34. Boosting Search Based Testing by using Constraint Based Testing CSBT : Constrained Search Based Testing Example : Unit Under Test Relaxation Abdelilah Sakti, Yann-Ga¨l e Gu´h´neuc, Gilles e e Pesant 1 2 3 Introduction 4 Motivating Example 6 5 7 CSBT : Constrained Search Based Testing 8 9 Overview 10 Unit Under Test Relaxation Example : Unit Under Test Relaxation Constrained Population Generator(CPG) Constrained Evolution Operator (CEO) Implementation for integer data type 1 2 3 4 5 Evaluation 6 Related work 7 Conclusions 8 9 10 10 / 19 intStr(int x,int y,String S1,String S2) { int y= x«y; int x=y+x/y; String s=S1+S2; if((s.equals(” OK” ) && (x>0) && s.length()>x) return 1; // Target return 0; } intStr(int x,int y, ){ ; int y= R1 int x=y+x/y; ; if(( && (x>0) && R2 >x) return 1; // Target return 0; } 35. Boosting Search Based Testing by using Constraint Based Testing CSBT : Constrained Search Based Testing Example : Unit Under Test Relaxation Abdelilah Sakti, Yann-Ga¨l e Gu´h´neuc, Gilles e e Pesant 1 2 3 Introduction 4 Motivating Example 6 5 7 CSBT : Constrained Search Based Testing 8 9 Overview 10 Unit Under Test Relaxation Example : Unit Under Test Relaxation Constrained Population Generator(CPG) Constrained Evolution Operator (CEO) Implementation for integer data type 1 2 3 4 5 Evaluation 6 Related work 7 Conclusions 8 9 10 10 / 19 intStr(int x,int y,String S1,String S2) { int y= x«y; int x=y+x/y; String s=S1+S2; if((s.equals(” OK” ) && (x>0) && s.length()>x) return 1; // Target return 0; } intStr(int x,int y, ){ ; int y= R1 int x=y+x/y; ; if(( && (x>0) && R2 >x) return 1; // Target return 0; } 1 2 intStr( String S1,String S2) { 3 4 String s=S1+S2; if(s.equals(” OK” )) 5 6 7 8 return 1; // Target return 0; 9 10 11 } 36. Boosting Search Based Testing by using Constraint Based Testing Abdelilah Sakti, Yann-Ga¨l e Gu´h´neuc, Gilles e e Pesant CSBT : Constrained Search Based Testing Constrained Population Generator(CPG) RV1 (integer) CSBT : Constrained Search Based Testing Overview Unit Under Test Relaxation Example : Unit Under Test Relaxation Constrained Population Generator(CPG) Constrained Evolution Operator (CEO) Implementation for integer data type Evaluation Related work Conclusions 11 / 19 RV2 (string) s21 s31 s22 s32 s11 Introduction Motivating Example RV2 (float) s12 s13 37. Boosting Search Based Testing by using Constraint Based Testing Abdelilah Sakti, Yann-Ga¨l e Gu´h´neuc, Gilles e e Pesant CSBT : Constrained Search Based Testing Constrained Population Generator(CPG) RV1 (integer) CSBT : Constrained Search Based Testing RV2 (string) s21 s31 s22 s32 s11 Introduction Motivating Example RV2 (float) s12 s13 Overview Unit Under Test Relaxation Example : Unit Under Test Relaxation Constrained Population Generator(CPG) Initial Population Constrained Evolution Operator (CEO) Implementation for integer data type Evaluation Related work Conclusions 11 / 19 s11 , s21 , s31 38. Boosting Search Based Testing by using Constraint Based Testing Abdelilah Sakti, Yann-Ga¨l e Gu´h´neuc, Gilles e e Pesant CSBT : Constrained Search Based Testing Constrained Population Generator(CPG) RV1 (integer) RV2 (float) RV2 (string) s21 s31 s22 s32 s11 Introduction Motivating Example CSBT : Constrained Search Based Testing s12 s13 Overview Unit Under Test Relaxation Example : Unit Under Test Relaxation Constrained Population Generator(CPG) Initial Population s11 , s22 , s32 Constrained Evolution Operator (CEO) s11 , s21 , s31 s11 , s21 , s32 s11 , s22 , s31 Implementation for integer data type s11 , s22 , s32 Evaluation s11 , s21 , s31 s11 , s21 , s32 s11 , s22 , s31 Related work s11 , s22 , s32 Conclusions s11 , s21 , s31 11 / 19 s11 , s21 , s32 s11 , s22 , s31 39. Boosting Search Based Testing by using Constraint Based Testing CSBT : Constrained Search Based Testing Constrained Evolution Operator (CEO) Abdelilah Sakti, Yann-Ga¨l e Gu´h´neuc, Gilles e e Pesant Introduction smallinteger Solver int f loat Motivating Example CSBT : Constrained Search Based Testing (val1 , val2 , ? , val4 ) type ? small smallfloat Solver Overview Unit Under Test Relaxation Example : Unit Under Test Relaxation Constrained Population Generator(CPG) Constrained Evolution Operator (CEO) smallstring Solver (val1 , val2 , nval3 , val4 ) Implementation for integer data type solvable ? small Evaluation Related work Conclusions 12 / 19 (val1 , val2 ,nval3 , nval4 ) 40. Boosting Search Based Testing by using Constraint Based Testing Implementation for integer data type Abdelilah Sakti, Yann-Ga¨l e Gu´h´neuc, Gilles e e Pesant Introduction Motivating Example CSBT : Constrained Search Based Testing Implementation for integer data type Evaluation Related work Conclusions For SBT, CSBT uses eToc [P. Tonella, ISSTA 2004] ; For CBT, CSBT uses Cp-sst [A. SAKTI, JFPC 2011] ; 13 / 19 41. Boosting Search Based Testing by using Constraint Based Testing Evaluation Subjects Abdelilah Sakti, Yann-Ga¨l e Gu´h´neuc, Gilles e e Pesant Introduction Motivating Example CSBT : Constrained Search Based Testing Implementation for integer data type Evaluation Subjects Configurations Results Related work Conclusions 14 / 19 Publicly available classes from Java standard library and Apache Commons project Subject Integer BitSet ArithmticUtils # LOC 1244 755 959 # Branches 38 145 102 42. Boosting Search Based Testing by using Constraint Based Testing Abdelilah Sakti, Yann-Ga¨l e Gu´h´neuc, Gilles e e Pesant Introduction Motivating Example CSBT : Constrained Search Based Testing Implementation for integer data type Evaluation Subjects Configurations Evaluation Configurations analysed approaches SBT alone : eToc ; CBT alone : CP-SST ; CSBT : SBT+CPG ; SBT+CEO ; SBT+CPG+CEO. Parameters All default eToc parameters are kept as is. Integer domain : [−2 × 104 , 2 × 104 ] ; Results Related work Conclusions 15 / 19 Solver time out : 500ms ; Every approach has been executed 10 times on every class for a runtime limited at 300 s. 43. Boosting Search Based Testing by using Constraint Based Testing Evaluation Results Abdelilah Sakti, Yann-Ga¨l e Gu´h´neuc, Gilles e e Pesant Comparing all techniques on all classes 90 Introduction Motivating Example Implementation for integer data type Evaluation Subjects 80 Branch Coverage % CSBT : Constrained Search Based Testing 70 60 Configurations Results Related work 50 SBT CBT CPG CEO CPG+CEO Conclusions 40 0 50 100 150 Time (s) 16 / 19 200 250 300 44. Boosting Search Based Testing by using Constraint Based Testing Evaluation Results Abdelilah Sakti, Yann-Ga¨l e Gu´h´neuc, Gilles e e Pesant Comparing all techniques on all classes 90 Introduction Motivating Example Implementation for integer data type Evaluation Subjects 80 Branch Coverage % CSBT : Constrained Search Based Testing 70 60 Configurations Results Related work 50 SBT CBT CPG CEO CPG+CEO Conclusions 40 0 50 100 150 Time (s) 16 / 19 200 250 300 45. Boosting Search Based Testing by using Constraint Based Testing Evaluation Results Abdelilah Sakti, Yann-Ga¨l e Gu´h´neuc, Gilles e e Pesant Comparing all techniques on all classes 90 Introduction Motivating Example Implementation for integer data type Evaluation Subjects 80 Branch Coverage % CSBT : Constrained Search Based Testing 70 60 Configurations Results Related work 50 SBT CBT CPG CEO CPG+CEO Conclusions 40 0 50 100 150 Time (s) 16 / 19 200 250 300 46. Boosting Search Based Testing by using Constraint Based Testing Evaluation Results Abdelilah Sakti, Yann-Ga¨l e Gu´h´neuc, Gilles e e Pesant Comparing all techniques on all classes 90 Introduction Motivating Example Implementation for integer data type Evaluation Subjects 80 Branch Coverage % CSBT : Constrained Search Based Testing 70 60 Configurations Results Related work 50 SBT CBT CPG CEO CPG+CEO Conclusions 40 0 50 100 150 Time (s) 16 / 19 200 250 300 47. Boosting Search Based Testing by using Constraint Based Testing Evaluation Results Abdelilah Sakti, Yann-Ga¨l e Gu´h´neuc, Gilles e e Pesant Comparing all techniques on all classes 90 Introduction Motivating Example Implementation for integer data type Evaluation Subjects 80 Branch Coverage % CSBT : Constrained Search Based Testing 70 60 Configurations Results Related work 50 SBT CBT CPG CEO CPG+CEO Conclusions 40 0 50 100 150 Time (s) 16 / 19 200 250 300 48. Boosting Search Based Testing by using Constraint Based Testing Abdelilah Sakti, Yann-Ga¨l e Gu´h´neuc, Gilles e e Pesant Introduction Motivating Example CSBT : Constrained Search Based Testing Implementation for integer data type Evaluation Related work Related work Using SBT to overcame CBT limits FLoPSy [K. Lakhotia et al, ICTSS 2010] Using CBT to overcame SBT limits Combining search based and constraint based testing. [Malburg and Fraser, ISSTA 2011] ; Symbolic search-based testing [M. Harman et al., ASE 2011]. Conclusions Others EVACON [T. Xie et al, ASE 2007]. 17 / 19 49. Boosting Search Based Testing by using Constraint Based Testing Abdelilah Sakti, Yann-Ga¨l e Gu´h´neuc, Gilles e e Pesant Introduction Motivating Example CSBT : Constrained Search Based Testing Implementation for integer data type Evaluation Related work Conclusions Conclusions CSBT CPG and CEO are two new techniques for combining CBT and SBT. The obtained results are promising but more experiments must be performed. Future work Enhancing our technique CEO. Extending results by using several solvers at the same time. Extending our approach by exploring new combination techniques. 18 / 19 50. Boosting Search Based Testing by using Constraint Based Testing Abdelilah Sakti, Yann-Ga¨l e Gu´h´neuc, Gilles e e Pesant Introduction Motivating Example CSBT : Constrained Search Based Testing Implementation for integer data type Evaluation Related work Conclusions 19 / 19 Thank you Questions ?