Elementary Landscape Decomposition of the Test Suite Minimization Problem

Elementary Landsap e Deomp osition of the Test Suite Minimization Problem Franiso Chiano, Javier Ferrer, and Enrique Alba University of Malaga, Spain, f hiano,ferrer,alba g l.uma.e s Abstrat. Landsap e theory provides a formal framework in whih ombinatorial optimization problems an b e theoretially haraterized as a sum of a speial kind of landsape alled elementary landsape. The de- omp osition of the ob jetive funtion of a problem into its elementary omp onents provides additional knowledge on the problem that an b e exploited to reate new searh metho ds for the problem. We analyze the Test Suite Minimization problem in Regression Testing from the p oint of view of landsape theory. We nd the elementary landsap e de- omp osition of the problem and propose a pratial appliation of suh deomp osition for the searh. Keywords: Fitness landsap es, test suite minimization, regression testing, elementary landsap es 1 Intro dution The theory of landsap es fouses on the analysis of the struture of the searh spae that is indued by the ombined inuenes of the ob jetive funtion of the optimization problem and the hoie neighb orho o d operator [8℄. In the eld of ombinatorial optimization, this theory has been used to haraterize optimization problems and to obtain global statistis of the problems [11℄. However, in reent years, researhers have been interested in the appliations of landsap e theory to improve the searh algorithms [5℄. A landsape for a ombinatorial optimization problem is a triple ( X ; N ; f ), where f : X 7! R denes the ob jetive funtion and the neighborhood operator funtion N ( x ) generates the set of p oints reahable from x 2 X in a single appliation of the neighborho o d operator. If y 2 N ( x ) then y is a neighb or of x . There exists a speial kind of landsap es, alled elementary landsapes , whih are of partiular interest due to their prop erties [12℄. We dene and analyze the elementary landsapes in Setion 2, but we an advane that they are hara- terized by the Grover's wave equation : avg f f ( y ) g y 2 N ( x ) = f ( x ) +  d   f  f ( x )  where d is the size of the neighb orho o d, j N ( x ) j , whih we assume is the same for all the solutions in the searh spae,  f is the average solution evaluation over the entire searh spae,  is a harateristi onstant and avg f f ( y ) g y 2 N ( x ) is the average of the ob jetive funtion f omputed in its neighb orho o d: avg f f ( y ) g y 2 N ( x ) = 1 j N ( x ) j X y 2 N ( x ) f ( y ) (1) For a given problem instane whose ob jetive funtion is elementary, the values  f and  an b e easily omputed in an eÆient way, usually from the problem data. Thus, the wave equation makes it possible to ompute the average value of the tness funtion f evaluated over all of the neighbors of x using only the value f ( x ), without evaluating any of the neighb ors. This means that in elementary landsapes we get additional information from a single solution evaluation. We get an idea of what is the quality of the solutions around the urrent one. This information an b e used to design more lever searh strategies and op erators whih eetively use the information. Lu et al. [5℄ provide a nie example of the appliation of the landsap e analysis to improve the p erformane of a searh metho d. In their work, the performane of the Sampling Hill Climbing is improved by avoiding the evaluation of non-promising solutions. The average tness value in the neighborho o d of the solutions omputed with (1) is at the ore of their prop osal. When the landsape is not elementary it is always p ossible to write the objetive funtion as a sum of elementary omponents, alled elementary landsape deomposition of a problem [1℄. Then, Grover's wave equation an be applied to eah elementary omponent and all the results are summed to give the average tness in the neighb orho o d of a solution. Furthermore, for some problems the average annot be limited to the neighborho o d of a solution, but it an b e extended to the seond-order neighrb ors (neighb ors of neighb ors), third-order neighbors, and, in general, to any arbitrary region around a given solution, inluding the whole searh spae. Sutton et al. [10℄ show how to ompute the averages over spheres and bal ls of arbitrary radius around a given solution in p olynomial time using the elementary landsap e deomp osition of real-valued funtions over binary strings. In [9℄ they prop ose a metho d that uses these averages over the balls around a solution to esap e from plateaus in the MAXk -SAT problem. The empirial results notied an improvement when the metho d was applied. Langdon [4℄ also analyzed the spheres of arbitrary radius from the point of view of landsap e theory, highlighting that the Walsh funtions are eigenvetors of the spheres and the mutation matrix in GAs. If we extend the landsap e analysis of the ob jetive funtion f to their powers ( f 2 , f 3 , et.), Grover's wave equation allows one to ompute higher-order moments of the tness distribution around a solution and, with them, the variane, the skewness and the kurtosis of this distribution. Sutton et al. [10℄ provide an algorithm for this omputation. We analyze here the Test Suite Minimization problem in regression testing from the p oint of view of landsap e theory. This software engineering problem onsists in seleting a set of test ases from a large test suite that satises a given ondition, like maximizing the overage and minimizing the orale ost [13℄. The remainder of the pap er is organized as follows. In Setion 2 we present the mathematial tools required to understand the rest of the paper and Se- tion 3 formally denes the Test Suite Minimization problem. Setion 4 presents the two main ontributions: the elementary landsape deomp osition of the objetive funtion of the problem and its square. We provide losed-form formulas for b oth f and f 2 . In the mathematial development we inlude a novel appliation of the Krawthouk matries to the landsap e analysis. Setion 5 proposes an appliation of the deomp ositions of f and f 2 and presents a short exp erimental study showing the b enets (and drawbaks) of the prop osal. Finally, with Setion 6 we onlude the paper. 2 Bakground In this setion we present some fundamental results of landsap e theory. We will only fo us on the relevant information required to understand the rest of the pap er. The interested reader an deep en on this topi in [7℄. Let ( X ; N ; f ) b e a landsap e, where X is a nite set of solutions, f : X ! R is a real-valued funtion dened on X and N : X ! P ( X ) is the neighborho o d op erator. The adjaeny and degree matries of the neighb orho o d N are dened as: A xy =  1 if y 2 N ( x ) 0 otherwise ; D xy =  j N ( x ) j if x = y 0 otherwise (2) We restrit our attention to regular neighb orho o ds, where j N ( x ) j = d > 0 for a onstant d , for all x 2 X . Then, the degree matrix is D = dI , where I is the identity matrix. The Laplaian matrix  asso iated to the neighb orho o d is dened by  = A  D . In the ase of regular neighb orho o ds it is  = A  dI . Any disrete funtion, f , dened over the set of andidate solutions an b e haraterized as a vetor in R j X j . Any j X j  j X j matrix an b e interpreted as a linear map that ats on vetors in R j X j . For example, the adjaeny matrix A ats on funtion f as follows A f = 0 B B B  P y 2 N ( x 1 ) f ( y ) P y 2 N ( x 2 ) f ( y ) . . . P y 2 N ( x j X j ) f ( y ) 1 C C C A ; ( A f )( x ) = X y 2 N ( x ) f ( y ) (3) Thus, the omp onent x of ( A f ) is the sum of the funtion value of all the neighb ors of x . Stadler denes the lass of elementary landsapes where the funtion f is an eigenvetor (or eigenfuntion) of the Laplaian up to an additive onstant [8℄. Formally, we have the following Denition 1. Let ( X ; N ; f ) be a landsape and  the Laplaian matrix of the onguration spae. The funtion f is said to be elementary if there exists a onstant b , whih we al l oset , and an eigenvalue  of   suh that (   )( f  b ) =  ( f  b ) . The landsape itself is elementary if f is elementary. We use   instead of  in the denition to avoid negative eigenvalues. In onneted neighb orho o ds (the ones we onsider here) the oset b is the average value of the funtion over the whole searh spae: b =  f . Taking into aount basi results of linear algebra, it an b e proved that if f is elementary with eigenvalue  , af + b is also elementary with the same eigenvalue  . Furthermore, in regular neighborho o ds, if g is an eigenfuntion of   with eigenvalue  then g is also an eigenvalue of A , the adjaeny matrix, with eigenvalue d   . The average value of the tness funtion in the neighb orho o d of a solution an b e omputed using the expression avg f f ( y ) g y 2 N ( x ) = 1 d ( A f )( x ). If f is an elementary funtion with eigenvalue  , then the average is omputed as: avg f f ( y ) g y 2 N ( x ) = avg y 2 N ( x ) f f ( y )   f g +  f = 1 d ( A ( f   f ))( x ) +  f = d   d ( f ( x )   f ) +  f = f ( x ) +  d (  f  f ( x )) and we get Grover's wave equation. In the previous expression we used the fat that f   f is an eigenfuntion of A with eigenvalue d   . The previous denitions are general onepts of landsap e theory. Let us fo us now on the binary strings with the one-hange neighb orho o d, whih is the representation and the neighborho o d we use in the test suite minimization problem. In this ase the solution set X is the set of all binary strings of size n . Two solutions x and y are neighb oring if one an b e obtained from the other by ipping a bit, that is, if the Hamming distane b etween the solutions, denoted with H ( x; y ), is 1. We dene the sphere of radius k around a solution x as the set of all solutions lying at Hamming distane k from x [10℄. A bal l of radius k is the set of all the solutions lying at Hamming distane lower or equal to k . In analogy to the adjaeny matrix we dene the sphere and ball matries of radius k as: S ( k ) xy =  1 if H ( x; y ) = k 0 otherwise ; B ( k ) xy = k X  =0 S (  ) xy =  1 if H ( x; y )  k 0 otherwise (4) Sine the ball matries are based on the sphere matries we an fous on the latter. The sphere matrix of radius one is the adjaeny matrix of the one-hange neighb orho o d, A , and the sphere matrix of radius zero is the identity matrix, I . Following [10℄, the matries S ( k ) an be dened using the reurrene: S (0) = I ; S (1) = A ; S ( k +1) = 1 k + 1  A  S ( k )  ( n  k + 1) S ( k  1)  (5) With the help of the reurrene we an write all the matries S ( k ) as polynomials in A , the adjaeny matrix. For example, S (2) = 1 2  A 2  nI  . As we previously noted, the eigenvetors of the Laplaian matrix  are eigenvetors of the adjaeny matrix A . On the other hand, if f is eigenvetor of A , then it is also an eigenvetor of any polynomial in A . As a onsequene, all the funtions that are elementary are eigenvetors (up to an additive onstant) of S ( k ) and their eigenvalues an be omputed using the same p olynomial in A that gives the expression for S ( k ) . The same is true for the ball matries B ( k ) , sine they are a sum of sphere matries. Let us dene the following series of polynomials: S (0) ( x ) = 1 (6) S (1) ( x ) = x (7) S ( k +1) ( x ) = 1 k + 1  x  S ( k ) ( x )  ( n  k + 1) S ( k  1) ( x )  (8) We use the same name for the p olynomials and the matries related to the spheres. The reader should notie, however, that the polynomials will b e always presented with their argument and the matries have no argument. That is, S ( k ) is the matrix and S ( k ) ( x ) is the p olynomial. Using the previous p olynomials, the matrix S ( k ) an b e written as S ( k ) ( A ) (the p olynomial S ( k ) ( x ) evaluated in the matrix A ) and any eigenvetor g of A with eigenvalue  is also an eigenvetor of S ( k ) ( A ) with eigenvalue S ( k ) (  ). One relevant set of eigenvetors of the Laplaian in the binary representation is that of Walsh funtions [11℄. Furthermore, the Walsh funtions form an orthogonal basis of eigenvetors in the onguration spae. Thus, they have b een used to nd the elementary landsape deomp osition of problems with a binary representation like the SAT [6℄. We will use these funtions to provide the landsap e deomp osition of the ob jetive funtion of the test suite minimization problem. Given the spae of binary strings of length n , B n , a (non-normalized) Walsh funtion with parameter w 2 B n is dened as: w ( x ) = n Y i =1 (  1) w i x i = (  1) P n i =1 w i x i (9) Two useful prop erties of Walsh funtions are w  v = w + v where w + v is the bitwise sum in Z 2 of w and v ; and 2 w = w  w = 2 w = 0 = 1. We dene the order of a Walsh funtion w as the value h w j w i = P n i =1 w i , that is, the numb er of ones in w . A Walsh funtion with order p is elementary with eigenvalue  = 2 p [8℄. The average value of a Walsh funtion of order p > 0 is zero, that is, w = 0 if w has at least one 1. The only Walsh funtion of order p = 0 is 0 = 1, whih is a onstant. In the mathematial development of Setion 4 we will use, among others, Walsh funtions of order 1 and 2. Thus, we present here a sp eial ompat notation for those binary strings having only one or two bits set to 1. We will denote with i the binary string with p osition i set to 1 and the rest set to 0. We also denote with i; j ( i 6 = j ) the binary string with positions i and j set to 1 and the rest to 0. We omit the length of the string n , but it will b e lear from the ontext. For example, if we are onsidering binary strings in B 4 we have 1= 1000 and 2 ; 3 = 0110. Using this notation we an write i ( x ) = (  1) x i = 1  2 x i (10) Given a set of binary strings W and a binary string u we denote with W ^ u the set of binary strings that an b e omputed as the bitwise AND of a string in W and u , that is, W ^ u = f w ^ u j w 2 W g . For example, B 4 ^ 0101 = f 0000 ; 0001 ; 0100 ; 0101 g . Sine the Walsh funtions form an orthogonal basis of R 2 n , any arbitrary pseudob o olean funtion an be written as a weighted sum of Walsh funtions in the following way: f = X w 2 B n a w w (11) where the values a w are alled Walsh o eÆients. We an group together the Walsh funtions having the same order to nd the elementary landsap e deomp osition of the funtion. That is: f ( p ) = X w 2 B n h w j w i = p a w w (12) where eah f ( p ) is an elementary funtion with eigenvalue 2 p . The funtion f an b e written as a sum of the n + 1 elementary omponents, that is: f = P n p =0 f ( p ) . Thus, any funtion an b e deomp osed in a sum of at most n elementary landsap es, sine we an add the onstant value f (0) to any of the other elementary omp onents. One we know that the p ossible eigenvalues of the elementary omponents of any funtion f are 2 p with 0  p  n , we an ompute the p ossible eigenvalues of the sphere matries. Sine the size of the neighb orho o d is d = n , we onlude that the only p ossible eigenvalues for the spheres are S ( k ) ( n  2 p ) with p 2 f 0 ; 1 ;:::;n g . With the help of Eqs. (6) to (8) we an write a reurrene formula for the eigenvalues of the sphere matries whose solution is S ( k ) ( n  2 p ) = K ( n ) k;p , where K ( n ) k;p is the ( k ; p ) element of the n -th Krawthouk matrix [10℄, whih is an ( n + 1)  ( n + 1) integer matrix. We will use Krawthouk matries to simplify the expressions and redue the omputation of the elementary omp onents of the test suite minimization. The interested reader an deepen on Krawthouk matries in [3℄. One important prop erty of the Krawthouk matries that will b e useful in Setion 4 is: (1 + x ) n  p (1  x ) p = n X k =0 x k K ( n ) k;p (13) Eah omp onent f ( p ) of the elementary landsape deomp osition of f is an eigenfuntion of the sphere matrix of radius r with eigenvalue S ( r ) ( n  2 p ) = K ( n ) r;p . Thus, we an ompute the average tness value in a sphere of radius r around a solution x as: avg f f ( y ) g y jH ( y ;x )= r =  n r   1 n X p =0 K ( n ) r;p f ( p ) ( x ) (14) We an also ompute the  -th moment of the funtion f in a sphere of radius r if we know the elementary landsape deomp osition of f  :   = avg f f  ( y ) g y jH ( y ;x )= r =  n r   1 n X p =0 K ( n ) r;p ( f  ) ( p ) ( x ) (15) 3 Test Suite Minimization Problem When a piee of software is mo died, the new software is tested using some previous test ases in order to hek if new errors were introdued. This hek is known as regression testing . In [14℄ Yo o and Harman provide a very omplete survey on searh-based tehniques for regression testing. They distinguish three dierent related problems: test suite minimization, test ase seletion and test ase prioritization. The problem we fae here is the test suite minimization [13℄. We dene the problem as follows. Let T = f t 1 ; t 2 ;:::;t n g b e a set of tests for a program and let M = f m 1 ; m 2 ;:::;m k g b e a set of elements of the program that we want to over with the tests. After running all the tests T we nd that eah test an over several program elements. This information is stored in a matrix T that is dened as: T ij =  1 if node m i is overed by test t j 0 otherwise (16) We dene the overage of a subset of tests X  T as: ov er ag e ( X ) = jf i j9 j 2 X ; T ij = 1 gj (17) The problem onsists in nding a subset X  T suh that the overage is maximized while the numb er of tests ases in the set j X j is minimized. We an dene the ob jetive funtion of the problem as the weighted sum of the overage and the number of tests. Thus, the ob jetive funtion an be written as: f ( X ) = ov er ag e ( X )    j X j (18) where  is a onstant that set the relative importane of the ost and overage. It an b e interpreted as the ost of a test measured in the same units as the b enet of a new overed element in the software. We assume here that all the elements in M to b e overed have the same value for the user and the ost of testing one test in T is the same for all of them. We defer to future work the analysis of the ob jetive funtion when this assumption is not true. Although the funtion prop osed is a weighted sum, whih simplies the landsap e analysis, non-linear funtions an b e also used and analyzed. In the following we will use binary strings to represent the solutions of the problem. Thus, we intro due the deision variables x j 2 B for 1  j  n . The variable x j is 1 if test t j is inluded in the solution and 0 otherwise. With this binary representation the overage, the numb er of ones of a string and the ob jetive funtion f an b e written as: ov er ag e ( x ) = k X i =1 n max j =1 f T ij x j g ; ones ( x ) = n X j =1 x j (19) f ( x ) = k X i =1 n max j =1 f T ij x j g    ones ( x ) (20) 4 Elementary Landsap e Deomp osition In this setion we present two of the main ontributions of this work: the elementary landsap e deomp osition of f and f 2 . In order to simplify the equations let us intro due some notation. Let us dene the sets V i = f j j T ij = 1 g . V i ontains the indies of the tests whih over the element m i . We also use in the following the term T i to refer to the binary string omp osed of the elements of the i -th row of matrix T . T i is a binary mask with 1s in the positions that app ear in V i . 4.1 Deomp osition of f The goal of this setion is to nd the Walsh deomp osition of f . We rst de- omp ose the funtions ov er ag e ( x ) and ones ( x ) into elementary landsap es and then we ombine the results. Let us start by analyzing the ov er ag e funtion and, in partiular, let us write the maximum in its denition as a weighted sum of Walsh funtions with the help of (10). n max j =1 f T ij x j g = 1  n Y j =1 (1  T ij x j ) = 1  Y j 2 V i (1  x j ) = 1  Y j 2 V i 1 + j ( x ) 2 = 1  2 j V i j Y j 2 V i (1 + j ( x )) (21) We an expand the produt of Walsh funtions in (21) using u v = u + v to get the Walsh deomp osition of max n j =1 . n max j =1 f T ij x j g = 1  2 j V i j Y j 2 V i (1 + j ( x )) = 1  2 j V i j X W 2P ( V i ) Y j 2 W j ( x ) (22) = 1  2 j V i j X w 2 B n ^ T i w ( x ) Using the Walsh deomp osition we an obtain that elementary landsap e deomp osition. The elementary omponents are the sums of weighted Walsh funtions having the same order (numb er of ones in the string w ). We an distinguish two ases: the onstant elementary omp onent (with order 0) and the non-onstant omp onents. Then, the elementary landsap e deomp osition of max n j =1 is: n max j =1 f T ij x j g (0) = 1  1 2 j V i j (23) n max j =1 f T ij x j g ( p ) =  1 2 j V i j X w 2 B n ^ T i h w ; w i = p w ( x ) where p > 0 (24) Eqs. (23) and (24) are the elementary landsap e deomp osition of the overage of one single software element. We just have to add all the omp onents of all the k elements to get the elementary landsap e deomp osition of ov er ag e ( x ). However, we should highlight that the previous expression is not very eÆient to ompute the omp onents of the maximum. We an observe that it requires to ompute a sum of  j V i j p  Walsh funtions. Before ombining all the piees to get the elementary landsape deomp osition of the ob jetive funtion of the problem, we need rst to nd a simpler and more eÆient expression for the elementary omp onents of the overage of one single element. Up to the b est of our knowledge, this is the rst time that the following mathematial development is performed in the literature. The essene of the development, however, is useful by itself and an b e applied to other problems with binary representation in whih the Walsh analysis an b e applied (like the Max-SAT problem). We will fous on the summation of (24). Let us rewrite this expression again as: X w 2 B n ^ T i h w ; w i = p w ( x ) = X W 2 P ( V i ) j W j = p Y j 2 W j ( x ) (25) Now we an identify the seond memb er of the previous expression with the o eÆient of a p olynomial. Let us onsider the p olynomial Q ( i ) x ( z ) dened as: Q ( i ) x ( z ) = Y j 2 V i ( z + j ( x )) = j V i j X l =0 z l 0 B B B  X W 2 P ( V i ) j W j = j V i j  l Y j 2 W j ( x ) 1 C C C A = j V i j X l =0 q l z l (26) From (26) we onlude that the summation in (25) is the o eÆient of z j V i j p in the polynomial Q ( i ) x ( z ), that is, q j V i j p . Aording to (10) and (26) we an write Q ( i ) x ( z ) = ( z + 1) n ( i ) 0 ( z  1) n ( i ) 1 where n ( i ) 0 and n ( i ) 1 are the numb er of zeros and ones, respetively, in the positions x j of the solution with j 2 V i . It should b e lear that n ( i ) 0 + n ( i ) 1 = j V i j . Now we an prot from the fat that, aording to (13), the p olynomials Q ( i ) x ( z ) are related to the Krawthouk matries by Q ( i ) x ( z ) = (  1) n ( i ) 1 P j V i j l =0 K j V i j l;n ( i ) 1 z l and we an write q l = (  1) n ( i ) 1 K j V i j l;n ( i ) 1 . Finally