Automated Generation of Computationally Hard Feature Models Using Evolutionary Algorithms

Automated Generation of Computationally Hard Feature Models using Evolutionary Algorithms Sergio Seguraa,∗, Jos´ e A. Parejoa,∗∗, Robert M. Hieronsb, David Benavidesa, Antonio Ruiz-Cort´ esa aDepartment of Computer Languages and Systems, University of Seville Av Reina Mercedes S/N, 41012 Seville, Spain bSchool of Information Systems, Computing and Mathematics, Brunel University Uxbridge, Middlesex, UB7 7NU United Kingdom Abstract A feature model is a compact representation of the products of a software product line. The automated extraction of information from feature models is a thriving topic involving numerous analysis operations, techniques and tools. Performance evaluations in this domain mainly rely on the use of random feature models. However, these only provide a rough idea of the behaviour of the tools with average problems and are not sufficient to reveal their real strengths and weaknesses. In this article, we propose to model the problem of finding computationally hard feature models as an optimization problem and we solve it using a novel evolutionary algorithm for optimized feature models (ETHOM). Given a tool and an analysis operation, ETHOM generates input models of a predefined size maximizing aspects such as the execution time or the memory consumption of the tool when performing the operation over the model. This allows users and developers to know the performance of tools in pessimistic cases providing a better idea of their real power and revealing performance bugs. Experiments using ETHOM on a number of analyses and tools have successfully identified models producing much longer executions times and higher memory consumption than those obtained with random models of identical or even larger size. Keywords: Search-based testing, software product lines, evolutionary algorithms, feature models, performance testing, automated analysis. 1. Introduction1 Software Product Line (SPL) engineering is a sys-2 tematic reuse strategy for developing families of re-3 lated software systems [16]. The emphasis is on de-4 riving products from a common set of reusable assets5 and, in doing so, reducing production costs and time–6 to–market. The products of an SPL are defined in terms7 of features where a feature is any increment in prod-8 uct functionality [6]. An SPL captures the commonal-9 ities (i.e. common features) and variabilities (i.e. vari-10 ant features) of the systems that belong to the product11 line. This is commonly done by using a so-called fea-12 ture model. A feature model [32] represents the prod-13 ucts of an SPL in terms of features and relationships14 amongst them (see the example in Fig. 1).15 ∗Principal corresponding author ∗∗Corresponding author Email addresses: [email protected] (Sergio Segura), [email protected] (Jos´ e A. Parejo) The automated extraction of information from feature16 models (a.k.a automated analysis of feature models) is17 a thriving topic that has received much attention in the18 last two decades [10]. Typical analysis operations allow19 us to know whether a feature model is consistent (i.e.20 it represents at least one product), the number of prod-21 ucts represented by a feature model, or whether a model22 contains any errors. Catalogues with up to 30 anal-23 ysis operations on feature models have been reported24 [10]. Techniques that perform these operations are typ-25 ically based on propositional logic [6, 45], constraint26 programming [9, 76], or description logic [70]. Also,27 these analysis capabilities can be found in several com-28 mercial and open source tools including AHEAD Tool29 Suite [3], Big Lever Software Gears [15], FaMa Frame-30 work [19], Feature Model Plug-in [20], pure::variants31 [53] and SPLOT [43].32 The development of tools and benchmarks to eval-33 uate the performance and scalability of feature model34 analysis tools has been recognised as a challenge [7,35 Preprint submitted to Elsevier March 25, 2015 10, 51, 62]. Also, recent publications reflect an in-36 creasing interest in evaluating and comparing the perfor-37 mance of techniques and tools for the analysis of feature38 models [4, 25, 26, 31, 45, 39, 50, 51, 52, 55, 64, 71].39 One of the main challenges when performing experi-40 ments is finding tough problems that show the strengths41 and weaknesses of the tools under evaluation in ex-42 treme situations, e.g. those producing longest execu-43 tion times. Feature models from real domains are by far44 the most appealing input problems. Unfortunately, al-45 though there are references to real feature models with46 hundreds or even thousands of features [7, 37, 66], only47 portions of them are usually available. This lack of48 hard realistic feature models has led authors to eval-49 uate their tools with large randomly generated feature50 models of 5,000 [46, 76], 10,000 [23, 45, 67, 74] and51 up to 20,000 [47] features. In fact, the size of the fea-52 ture models used in experiments has been increasing,53 suggesting that authors are looking for complex prob-54 lems on which to evaluate their tools [10]. More re-55 cently, some authors have suggested looking for hard56 and realistic feature models in the open source commu-57 nity [13, 21, 49, 61, 62]. For instance, She et al. [62]58 extracted a feature model containing more than 5,00059 features from the Linux kernel.60 The problem of generating test data to evaluate the61 performance of software systems has been largely stud-62 ied in the field of software testing. In this context,63 researchers realised long ago that random values are64 not effective in revealing the vulnerabilities of a sys-65 tem under test. As pointed out by McMinn [42]: “ran-66 dom methods are unreliable and unlikely to exercise67 ‘deeper’ features of software that are not exercised by68 mere chance”. In this context, metaheuristic search69 techniques have proved to be a promising solution for70 the automated generation of test data for both functional71 [42] and non–functional properties [2]. Metaheuristic72 search techniques are frameworks which use heuristics73 to find solutions to hard problems at an affordable com-74 putational cost. Examples of metaheuristic techniques75 include evolutionary algorithms, hill climbing, and sim-76 ulated annealing [69]. For the generation of test data,77 these strategies translate the test criterion into an ob-78 jective function (also called a fitness function) that is79 used to evaluate and compare the candidate solutions80 with respect to the overall search goal. Using this in-81 formation, the search is guided toward promising ar-82 eas of the search space. Wegener et al. [72, 73] were83 one of the first to propose the use of evolutionary al-84 gorithms to verify the time constraints of software back85 in 1996. In their work, the authors used genetic algo-86 rithms to find input combinations that violate the time87 constraints of real–time systems, that is, those inputs88 producing an output too early or too late. Their exper-89 imental results showed that evolutionary algorithms are90 much more effective than random search in finding in-91 put combinations maximising or minimising execution92 times. Since then, a number of authors have followed93 their steps using metaheuristics and especially evolu-94 tionary algorithms for testing non–functional properties95 such as execution time, quality of service, security, us-96 ability or safety [2, 42].97 Problem description. Current performance evalu-98 ations on the analysis of feature models are mainly99 carried out using randomly generated feature models.100 However, these only provide a rough idea of the aver-101 age performance of tools and do not reveal their specific102 weak points. Thus, the SPL community lacks mech-103 anisms that take analysis tools to their limits and re-104 veal their real potential in terms of performance. This105 problem has negative implications for both tool users106 and developers. On the one hand, tool developers have107 no means of performing exhaustive evaluations of the108 strengths and weaknesses of their tools making it hard109 to find faults affecting their performance. On the other110 hand, users are not provided with full information about111 the performance of tools in pessimistic cases and this112 makes it difficult for them to choose the tool that best113 meets their needs. Hence, for instance, a user could114 choose a tool based on its average performance and later115 realisethatitperformsvery badly in particular cases that116 appear frequently in their application domain.117 In this article, we address the problem of generating118 computationally hard feature models as a means to re-119 veal the performance strengths and weaknesses of fea-120 ture model analysis tools. The problem of generating121 hard feature models has traditionally been addressed122 by the SPL community by simply randomly generating123 huge feature models with thousands of features and con-124 straints. That is, it is generally observed and assumed125 that the larger the model the harder its analysis. How-126 ever, we remark that these models are still randomly127 generated and therefore, as warned by software testing128 experts, they are not sufficient to exercise the specific129 features of a tool under evaluation. Another negative130 consequence of using huge feature models to evaluate131 the performance of tools is that they frequently fall out132 of the scope of their users. Hence, both developers and133 users would probably be more interested in knowing134 whether a tool may crash with a hard model of small135 or medium size.136 Finally, we may mention that using realistic or stan-137 dard collections of problems (i.e. benchmarks) is138 equally insufficient for an exhaustive performance eval-139 2 uation since they do not consider the specific aspects140 of a tool or technique under test. Thus, feature mod-141 els that one tool finds hard to analyse could be trivially142 processed by another and vice versa.143 Solutionoverviewandcontributions. In this article,144 we propose to model the problem of finding computa-145 tionally hard feature models as an optimisation prob-146 lem and we solve it using a novel Evolutionary algo-147 riTHm for Optimised feature Models (ETHOM). Given148 a tool and an analysis operation, ETHOM generates in-149 put models of a predefined size maximising aspects such150 as the execution time or the memory consumed by the151 tool when performing the operation over the model. For152 the evaluation of our approach, we performed several153 experiments using different analysis operations, tools154 and optimisation criteria. In particular, we used FaMa155 and SPLOT, two tools for the automated analysis of fea-156 ture models developed and maintained by independent157 laboratories. In total, we performed over 50 million158 executions of analysis operations for the configuration159 and evaluation of our algorithm, during more than six160 months of work. The results showed how ETHOM suc-161 cessfully identified input models causing much longer162 executions times and higher memory consumption than163 randomly generated models of identical or even larger164 size. As an example, we compared the effectiveness165 of random and evolutionary search in generating fea-166 ture models with up to 1,000 features maximising the167 time required by a constraint programming solver (a.k.a.168 CSP solver) to check their consistency. The results re-169 vealed that the hardest randomly generated model found170 required 0.2 seconds to analyse while ETHOM was able171 to find several models taking between 1 and 27.5 min-172 utes to process. Besides this, we found that the hard-173 est feature models generated by ETHOM in the range174 500-1,000 features were remarkably harder to process175 than randomly generated models with 10,000 features.176 More importantly, we found that the hard feature mod-177 els generated by ETHOM had similar properties to re-178 alistic models found in the literature. This suggests that179 the long execution times and high memory consumption180 detected by ETHOM might be reproduced when using181 real models with the consequent negative effect on the182 user.183 Our work enhances and complements the current184 state of the art on performance evaluation of feature185 model analysis tools as follows:186 •To the best of our knowledge, this is the first ap-187 proach that uses a search–based strategy to exploit188 the internal weaknesses of the analysis tools and189 techniques under evaluation rather than trying to190 detect them by chance using randomly generated191 models.192 •Our work allows developers to focus on the search193 for computationally hard models of realistic size194 that could reveal performance problems in their195 tools rather than using huge feature models out of196 their scope. If a tool performs poorly with the gen-197 erated models, developers could use the informa-198 tion as input to investigate possible improvements.199 •Our approach provides users with helpful infor-200 mation about the behaviour of tools in pessimistic201 cases helping them to choose the tool that best202 meets their needs.203 •Our algorithm is highly generic and can be applied204 to any automated operation on feature models in205 which the quality (i.e. fitness) of models with re-206 spect to an optimisation criterion can be quantified.207 •Our experimental results show that the hardness of208 feature models depends on different factors in con-209 trast to related work in which the complexity of the210 models is mainly associated with their size.211 •Our algorithm is ready-to-use and publicly avail-212 able as a part of the open-source BeTTy Frame-213 work [14, 58].214 Scope of the contribution. The target audience of215 this article is practitioners and researchers wanting to216 evaluate and test the performance of their tools that217 analyse feature models. Several aspects regarding the218 scope of our contribution may be clarified, namely:219 •Our work follows a black-box approach. That220 is, our algorithm does not make any assumptions221 about an analysis tool and operation under test.222 ETHOM can therefore be applied to any tool or223 analysis operation regardless of how it is imple-224 mented.225 •Our approach focuses on testing, not debugging.226 That is, our work contributes to the detection of227 performance failures (unexpected behaviour in the228 software) but not faults (causes of the unexpected229 behaviour). Once a failure is detected using the230 test data generated by ETHOM, a tool’s develop-231 ers and designers should use debugging to identify232 the fault causing it, e.g. bad variable ordering, bad233 problem encoding, parsing problems, etc.234 •It is noteworthy that many different factors could235 contribute to a technique finding it hard to analyse236 3 a given feature model, some of them not directly237 related to the analysis algorithm used. Examples238 including: bad variable ordering, bad problem en-239 coding, parsing problems, bad heuristic selection,240 etc. However, as previously mentioned, the prob-241 lem of identifying the factors that make a feature242 model hard to analyse when using a specific tool is243 out of the scope of this article.244 The rest of the article is structured as follows. Sec-245 tion 2 introduces feature models and evolutionary algo-246 rithms. In Section 3, we present ETHOM, an evolu-247 tionary algorithm for the generation of optimised fea-248 ture models. Then, in Section 4, we propose a specific249 configuration of ETHOM to automate the generation250 of computationally hard feature models. The empiri-251 cal evaluation of our approach is presented in Section252 5. Section 6 presents the threats to validity of our work.253 Related work is described in Section 7. Finally, we sum-254 marise our conclusions and describe our future work in255 Section 8.256 2. Preliminaries257 2.1. Feature models and their analyses258 Feature models define the valid combinations of fea-259 tures in a domain and are commonly used as a compact260 representations of all the products of an SPL. A feature261 model is visually represented as a tree-like structure in262 which nodes represent features and connections illus-263 trate the relationships between them. These relation-264 ships constrain the way in which features can be com-265 bined. Fig. 1 depicts a simplified sample feature model.266 The model illustrates how features are used to specify267 and build software for Global Position System (GPS)268 devices. The software loaded in the GPS is determined269 by the features that it supports. The root feature (i.e.270 ‘GPS’) identifies the SPL.271 Feature models were first introduced in 1990 as a272 part of the FODA (Feature–Oriented Domain Analysis)273 method [32]. Since then, feature modelling has been274 widely adopted by the software product line community275 and a number of extensions have been proposed in at-276 tempts to improve properties such as succinctness and277 naturalness [56]. Nevertheless, there seems to be a con-278 sensus that at a minimum feature models should be able279 to represent the following relationships among features:280 •Mandatory. If a child feature is mandatory, it is281 included in all products in which its parent feature282 appears. In Fig. 1, all GPS devices must provide283 support for Routing.284 •Optional. If a child feature is defined as optional,285 it can be optionally included in products in which286 its parent feature appears. For instance, the sample287 model defines Multimedia to be an optional fea-288 ture.289 •Alternative. Child features are defined as alter-290 native if only one feature can be selected when291 the parent feature is part of the product. In our292 SPL, software for GPS devices must provide sup-293 port for either an LCD or Touch screen but only one294 of them.295 •Or-Relation. Child features are said to have an296 or-relation with their parent when one or more of297 them can be included in the products in which the298 parent feature appears. In our example, GPS de-299 vices can provide support for an MP3 player, a300 Photo viewer or both of them.301 Notice that a child feature can only appear in a prod-302 uct if its parent feature does. The root feature is a part303 of all the products within the SPL. In addition to the304 parental relationships between features, a feature model305 can also contain cross-tree constraints between features.306 These are typically of the form:307 •Requires. If a feature A requires a feature B, the308 inclusion of A in a product implies the inclusion of309 B in the product. GPS devices with Traffic avoid-310 ing require Auto-rerouting.311 •Excludes. If a feature A excludes a feature B, both312 features cannot be part of the same product. In our313 sample SPL, a GPS with Touch screen cannot in-314 clude a Keyboard and vice-versa.315 The automated analysis of feature models deals with316 the computer-aided extraction of information from fea-317 ture models. It has been noted that in the order of 30 dif-318 ferent analysis operations on feature models have been319 reported during the last two decades [10]. The analy-320 sis of feature models is usually performed in two steps.321 First, the analysis problem is translated into an interme-322 diate problem such as a boolean satisfiability problem323 (SAT) or a Constraint Satisfaction Problem (CSP). SAT324 problems are often modelled using Binary Decision Di-325 agrams (BDD). Then, an off-the-shelf solver is used to326 analyse the problem. Most analysis problems related to327 feature models are NP-hard [7, 51]. However, solvers328 provide heuristics that work well in practice. Experi-329 ments have shown that each technique has its strengths330 and weaknesses. For instance, SAT solvers are efficient331 when checking the consistency of a feature model but332 4 GPS Routing Interface MP3 player 3D map view Multimedia Screen LCDTouch Mandatory Optional Alternative Or Requires Excludes Photo viewer Traffic avoiding Radar detector Auto-rerouting Predictive entry Keyboard Figure 1: A sample feature model incapable of calculating the number of products in a333 reasonable amount of time [11, 45, 51]. BDD solvers334 are the most efficient solution known for calculating the335 number of products but at the price of high memory con-336 sumption [11, 46, 51]. Finally, CSP solvers are espe-337 cially suitable for dealing with numeric constraints as-338 sociated with feature models with attributes (so-called339 extended feature models) [9].340 2.2. Evolutionary algorithms341 The principles of biological evolution have inspired342 the development of a whole branch of optimisation tech-343 niques called Evolutionary Algorithms (EAs). These al-344 gorithms manage a set of candidate solutions to an opti-345 misation problem that are combined and modified itera-346 tively to obtain better solutions. Each candidate solution347 is referred to as an individual or chromosome in analogy348 to the evolution of species in biological genetics where349 the DNA of individuals is combined and modified along350 generations enhancing the species through natural se-351 lection. Two of the main properties of EAs are that they352 are heuristic and stochastic. The former means that an353 EA is not guaranteed to obtain the global optimum for354 the optimisation problem. The latter means that differ-355 ent executions of the algorithm with the same input pa-356 rameters can produce different output, i.e. they are not357 deterministic. Despite this, EAs are among the most358 widely used optimisation techniques and have been ap-359 plied successfully in nearly all scientific and engineer-360 ing areas by thousands of practitioners. This success is361 due to the ability of EAs to obtain near optimal solu-362 tions to extremely hard optimisation problems with af-363 fordable time and resources.364 As an example, let us consider the design of a car as365 an optimisation problem. A similar example was used366 to illustrate the working of EAs in [73]. Let us suppose367 that our goal is to find a car design that maximises368 Initialization Stop criteria met? Selection Mutation Crossover Evaluation [NOT] [YES] Evaluation Encoding Decoding Survival Figure 2: General working scheme of evolutionary algorithms speed. This problem is hard since a car is a highly369 complex system in which speed depends on a number370 of parameters such as engine type and the shape of the371 car. Moreover, there are likely to be extra constraints372 like keeping the cost of the car under a certain value,373 making some designs infeasible. All EA variants are374 based on a common working scheme shown in Fig. 2.375 Next, we describe its main steps and relate them to our376 example.377 378 Initialisation. The initial population (i.e. set of379 candidate solutions to the problem) is usually generated380 randomly. In our example, this could be done by381 randomly choosing a set of values for the design382 parameters of the car. Of course, it is unlikely that383 this initial population with contain an optimal or384 5 near optimal car design. However, promising val-385 ues found at this step will be used to produce variants386 along the optimisation process leading to better designs.387 388 Evaluation. Next, individuals are evaluated using a389 fitness function. A fitness function is a function that390 receives an individual as input and returns a numerical391 value indicating the quality of the individual. This392 enables the objective comparison of candidate solutions393 with respect to an optimisation problem. The fitness394 function should be deterministic to avoid interferences395 in the algorithm, i.e. different calls to the function with396 the same set of parameters should produce the same397 output. In our car example, a simulator could be used398 to provide the maximum speed prediction as fitness.399 400 Stopping criterion. Iterations of the remaining steps401 of the algorithm are performed until a termination cri-402 terion is met. Typical stopping criteria are: reaching a403 maximum or average fitness value, maximum execution404 times of the fitness function, number of iterations of405 the loop (so-called generations) or number of iterations406 without improvements on the best individual found.407 408 Encoding. In order to create offspring, an individual409 needs to be encoded (represented) in a form that facili-410 tates its manipulation during the rest of the algorithm.411 In biological genetics, DNA encodes an individual’s412 characteristics on chromosomes that are used in re-413 production and whose modifications produce mutants.414 Classical encoding mechanisms for EAs include the415 use of binary vectors that encode numerical values in416 genetic algorithms (so-called binary encoding) and tree417 structures that encode the abstract syntax of programs418 in genetic programming (so-called tree encoding)419 [1, 54]. In our car example, this step would require420 design patterns of cars to be expressed using a data421 structure, e.g. binary vectors for each design parameter.422 423 Selection. In the main loop of the algorithm (see Fig.424 2), individuals are selected from the current population425 in order to create new offspring. In this process, better426 individuals usually have a greater probability of being427 selected, with this resembling natural evolution where428 stronger individuals are more likely to reproduce. For429 instance, two classic selection mechanisms are roulette430 wheel and tournament selection [1]. When using the431 former, the probability of choosing an individual is432 proportional to its fitness and this can be seen as deter-433 mining the width of the slice of a hypothetical spinning434 roulette wheel. This mechanism is often modified435 by assigning probabilities based on the position of436 Figure 3: Sample crossover and mutation in the search of an optimal car design. the individuals in a fitness–ordered ranking (so-called437 rank-based roulette wheel). When using tournament438 selection, a group of nindividuals is randomly chosen439 from the population and a winning individual is selected440 according to its fitness.441 442 Crossover. These are the techniques used to combine443 individuals and produce new individuals in an analo-444 gous way to biological reproduction. The crossover445 mechanism used depends on the encoding scheme but446 there are a number of widely-used mechanisms [1].447 For instance, two classical crossover mechanisms for448 binary encoding are one-point crossover and uniform449 crossover. When using the former, a location in the450 vector is randomly chosen as the break point and451 portions of vectors after the break point are exchanged452 to produce offspring (see Fig. 5 for a graphical example453 of this crossover mechanism). When using uniform454 crossover, the value of each vector element is taken455 from one parent or other with a certain probability,456 usually 50%. Fig. 3(a) shows an illustrative application457 of crossover in our example of car design. An F1458 car and a small family car are combined by crossover459 producing a sports car. The new vehicle has some460 design parameters inherited directly from each parent461 such as number of seats or engine type and others462 mixed such as shape and intermediate size.463 464 Mutation. At this step, random changes are applied to465 the individuals. Changes are performed with a certain466 probability where small modifications are more likely467 than larger ones. Mutation plays the important role468 of preventing the algorithm from getting stuck prema-469 turely at a locally optimal solution. An example of470 mutation in our car optimisation problem is presented471 in Fig. 3(b). The shape of a family car is changed472 by adding a back spoiler while the rest of its design473 parameters remain intact.474 475 6 Decoding. In order to evaluate the fitness of new476 and modified individuals decoding is performed.477 For instance, in our car design example, data stored478 on data structures is transformed into a suitable car479 design that our fitness function can evaluate. It often480 happens that the changes performed in the crossover481 and mutation steps create individuals that are not valid482 designs or break a constraint, this is usually referred483 to as an infeasible individual, e.g. a car with three484 wheels. Once an infeasible individual is detected, this485 can be either replaced by an extra correct one or it486 can be repaired, i.e. slightly changed to make it feasible.487 488 Survival. Finally, individuals are evaluated and the next489 population is formed in which individuals with better490 fitness values are more likely to remain in the popula-491 tion. This process simulates the natural selection of the492 better adapted individuals that survive and generate off-493 spring, thus improving a species.494 3. ETHOM: an Evolutionary algoriTHm for Opti-495 mized feature Models496 In this section, we present ETHOM, a novel evo-497 lutionary algorithm for the generation of optimised498 feature models. The algorithm takes several constraints499 and a fitness function as input and returns a feature500 model of the given size maximising the optimisation501 criterion defined by the function. A key benefit of our502 algorithm is that it is very generic and so is applicable503 to any automated operation on feature models in which504 the quality (i.e. fitness) of the models can be measured505 quantitatively. In the following, we describe the basic506 steps of ETHOM as shown in Fig. 2.507 508 Initial population. The initial population is generated509 randomly according to the size constraints received510 as input. The current version of ETHOM allows the511 user to specify the number of features, percentage of512 cross-tree constraints and maximum branching factor of513 the feature model to be generated. Several algorithms514 for the random generation of feature models have been515 proposed in the literature [57, 67, 78]. There are also516 tools such as BeTTy [14, 58] and SPLOT [43, 65] that517 support the random generation of feature models.518 519 Evaluation. Feature models are evaluated according520 to the fitness function received as input obtaining a521 numeric value that represents the quality of a candidate522 solution, i.e. its fitness.523 524 0 2 13 45 6 Op,2 Or,1 M,0 Or,0 Alt,0 Alt,1 M,0 E,3,6 7 Op,0 R,6,7 TREE CTC Individual 0 1 2 3 4 5 6 7 Figure 4: Encoding of a feature model in ETHOM Encoding. For the representation of feature models as525 individuals (a.k.a. chromosomes) we propose using a526 custom encoding. Generic encodings for evolutionary527 algorithms were ruled out since these either were not528 suitable for tree structures (i.e. binary encoding) or529 were not able to produce solutions of a fixed size (e.g.530 tree encoding), a key requirement in our approach. Fig.531 4 depicts an example of our encoding. As illustrated,532 each model is represented by means of two arrays,533 one storing information about the tree and another one534 containing information about Cross-Tree Constraints535 (CTC). The order of each feature in the array corre-536 sponds to the Depth–First Traversal (DFT) order of537 the tree. Hence, a feature labelled with ‘0’ in the tree538 is stored in the first position of the array, the feature539 labelled with ‘1’ is stored the second position and so540 on. Each feature in the tree array is defined by a pair541 <PR,C>where PR is the type of relationship with542 its parent feature (M: Mandatory, Op: Optional, Or:543 Or-relationship, Alt: Alternative) and Cis the number544 of children of the given feature. As an example, the545 first position in the tree array, <Op,2>, indicates that546 the feature labelled with ‘0’ in the tree has an optional547 relationship with its parent feature and has two child548 features (those labelled with ‘1’ and ‘3’). Analogously,549 each position in the CTC array stores information about550 one constraint in the form <TC,O,D>where TC is551 the type of constraint (R: Requires, E: Excludes) and552 Oand Dare the indexes of the origin and destination553 features in the tree array respectively.554 555 Selection. Selection strategies are generic and can556 be applied regardless of how the individuals are557 represented. In our algorithm, we implemented both558 rank-based roulette-wheel and binary tournament559 selection strategies. The selection of one or the other560 7 E,3,6 Op,2 Or,1 M,0 Or,0 Alt,0 E,3,6 R,6,7 M,0 Or,0 Alt,0 Alt,1 M,0 Op,0Op,2 Or,1 0 2 13 45 6 7 TREE CTC 0 2 136 7 5 Op,2 Or,1 Op,0 Or,0 Op,3 Alt,0 Alt,0 R,3,5 4 Alt,0 R,2,6 0 2 1 3 5 6 4 Alt,0 Alt,0 Alt,0 R,2,6 7 Parent A Parent B Offspring Crossover point 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 Figure 5: Example of one-point crossover in ETHOM mainly depends on the application domain.561 562 Crossover. We provided our algorithm with two563 different crossover techniques, one-point and uniform564 crossover. Fig. 5 depicts an example of the application565 of one-point crossover in ETHOM. The process starts566 by selecting two parent chromosomes to be combined.567 For each array in the chromosomes, the tree and568 CTC arrays, a random point is chosen (the so-called569 crossover point). Finally, the offspring is created by570 copying the contents of the arrays from the beginning571 to the crossover point from one parent and the rest from572 the other one. Notice that the characteristics of our573 encoding guarantee a fixed size for the individuals in574 terms of features and CTCs.575 576 Mutation. Mutation operators must be specifically de-577 signed for the type of encoding used. ETHOM uses four578 different types of custom mutation operators, namely:579 •Operator 1. This randomly changes the type580 of a relationship in the tree array, e.g. from581 mandatory,<M,3>, to optional,<Op,3>.582 •Operator 2. This randomly changes the number of583 children of a feature in the tree, e.g. from <M,3>584 to <M,5>. The new number of children is in the585 range [0,BF] where BF is the maximum branching586 factor indicated as input.587 •Operator 3. This changes the type of a cross-tree588 constraint in the CTC array, e.g. from excludes589 <E,3,6>to requires <R,3,6>.590 •Operator 4. This randomly changes (with equal591 probability) the origin or destination feature of a592 constraint in the CTC array, e.g. from <E,3,6>593 to <E,1,6>. The implementation of this ensures594 that the origin and destination features are differ-595 ent.596 These operators are applied randomly with the same597 probability.598 599 Decoding. At this stage, the array-based chromosomes600 are translated back into feature models so that they601 can be evaluated. In ETHOM, we identified three602 types of patterns making a chromosome infeasible or603 semantically redundant, namely: i) those encoding set604 relationships (orand alternative) with a single child605 feature (e.g. Fig. 6(a)), ii) those containing cross-tree606 constraints between features with parental relationship607 (e.g. Fig. 6(b)), and iii) those containing features linked608 by contradictory or redundant cross-tree constraints609 (e.g. Fig. 6(c)). The specific approach used to address610 infeasible individuals, replacing or repairing (see611 Section 2.2 for details), mainly depends on the problem612 and it is ultimately up to the user. In our work, we used613 a repairing strategy described in the next section.614 615 B A B A B A B ABA B A BA B A BA (a) (d) (b) (e) (c) (f) InconsistencyRepair Figure 6: Examples of infeasible individuals and repairs Survival. Finally, the next population is created by616 including all the new offspring plus those individuals617 8 from the previous generation that were selected for618 crossover but did not generate descendants.619 620 For a pseudo-code listing of the algorithm we refer621 the reader to [59].622 4. Automated generation of hard feature models623 In this section we propose a method that models the624 problem of finding computationally hard feature mod-625 els as an optimisation problem and explain how this is626 solved using ETHOM. In order to find a suitable con-627 figuration of ETHOM, we performed numerous execu-628 tions of a sample optimisation problem evaluating dif-629 ferent combination of values for the key parameters of630 the algorithm, presented in Table 1. The optimisation631 problem was to find a feature model maximising the632 execution time taken by the analysis tool when check-633 ing model consistency, i.e. whether it represents at least634 one product. We chose this analysis operation because635 it is currently the most frequently quoted in the litera-636 ture [10]. In particular, we searched for feature models637 of different size maximising execution time in the CSP638 solver JaCoP [29] integrated into the framework for the639 analysis of feature models FaMa [19]. Next, we clarify640 the main aspects of the configuration of ETHOM:641 •Initial population. We used a Java program im-642 plementing the algorithm for the random genera-643 tion of feature models described by Th¨ um et al.644 [67]. For a detailed description of the generation645 approach, we refer the reader to [59].646 •Fitness function. Our first attempt was to mea-647 sure the time (in milliseconds) taken by FaMa to648 perform the operation. However, we found that649 the result of the function was significantly affected650 by the system load and was not deterministic. To651 solve this problem, we decided to measure the fit-652 ness of a feature model as the number of back-653 tracks produced by the analysis tool during its anal-654 ysis. A backtrack represents a partial candidate so-655 lution to a problem that is discarded because it can-656 not be extended to a full valid solution [68]. In con-657 trast to the execution time, most CSP backtracking658 heuristics are deterministic, i.e. different execu-659 tions of the tool with the same input produce the660 same number of backtracks. Together with execu-661 tion time, the number of backtracks is commonly662 used to measure the complexity of constraint satis-663 faction problems [68]. Thus, we can assume that664 the higher the number of backtracks the longer the665 computation time.666 •Infeasible individuals. We evaluated the effec-667 tiveness of both replacement and repair techniques.668 More specifically, we evaluated the following re-669 pair algorithm applied to infeasible individuals: i)670 isolated set relationships are converted into op-671 tional relationships (e.g. the model in Fig. 6(a) is672 changed as in Fig. 6(d)), ii) cross-tree constraints673 between features with parental relationships are re-674 moved (e.g. the model in Fig. 6(b) is changed as in675 Fig. 6(e)), and iii) two features cannot be linked by676 more than one cross-tree constraint (e.g. the model677 in Fig. 6(c) is changed as in Fig. 6(f)).678 •Stopping criterion. There is no means of decid-679 ing when an optimum input has been found and680 ETHOM should be stopped [73]. For the config-681 uration of ETHOM, we decided to allow the al-682 gorithm to continue for a given number of execu-683 tions of the fitness function (i.e. maximum number684 of generations) taking the largest number of back-685 tracks obtained as the optimum, i.e. the solution to686 the problem.687 Table 1 depicts the values evaluated for each config-688 uration parameter of ETHOM. These values were based689 on related work using evolutionary algorithms [23], the690 literature on parameter setting [18], and our previous691 experience in this domain [48]. Each combination of692 parameters used was executed 10 times to avoid hetero-693 geneous results and to allow us to perform statistical694 analysis on the data. The values underlined are those695 that provided better results and were therefore selected696 for the final configuration of ETHOM. In total, we per-697 formed over 40 million executions of the objective func-698 tion to find a good setup for our algorithm.699 Parameter Values evaluated and selected Selection strategy Roulette-wheel, 2-Tournament Crossover strategy One-point, Uniform Crossover probability 0.7, 0.8, 0.9 Mutation probability 0.005, 0.0075, 0.02 Size initial population 50, 100, 200 #Executions fitness function 2000, 5000 Infeasible individuals Replacing, Repairing Table 1: ETHOM configuration 5. Evaluation700 In order to evaluate our approach, we developed a701 prototype implementation of ETHOM. The prototype702 was implemented in Java to facilitate its integration into703 9 CSP Solver SAT Solver BDD Solver Modelling element Min Avg Max Min Avg Max Min Avg Max % relative to no. of features Mandatory 25.3 27.9 31.0 20.0 25.1 28.0 10.0 17.1 24.8 Optional 27.5 34.9 45.0 30.5 36.9 44.0 18.0 35.7 46.5 Set subfeatures 29.0 37.0 41.5 31.0 37.8 45.5 34.5 46.3 62.0 Set relationships 11.0 14.1 16.0 12.0 13.8 15.3 13.3 16.1 20.0 - Or 5.5 7.0 9.0 5.5 7.1 8.3 6.0 8.9 12.0 - Alternative 5.5 7.1 8.5 4.0 6.7 8.8 3.3 7.2 10.0 % relative to no. of constraints Requires 31.3 47.5 56.6 41.1 51.9 68.4 31.0 48.5 64.3 Excludes 43.4 52.5 68.7 31.6 48.1 58.9 35.7 51.5 69.0 Table 5: Properties of the hardest feature models found in our experiments. were trivially analysed in a few seconds. Then, we re-1145 peated the analysis of the hardest feature models found1146 in Experiment #1 using the other seven heuristics avail-1147 able in the CSP solver JaCoP. The results revealed that1148 the hardest feature models found in our experiment, us-1149 ing the heuristic MostConstrainedDynamic, were triv-1150 ially solved by some of the others heuristics. For exam-1151 ple, the hardest model in the range of 800 features and1152 10% CTC produced 5.3 million backtracks when us-1153 ing the heuristic MostContrainedDynamic and only 431154 backtracks when using the heuristic SmallestMin. This1155 finding clearly shows that feature models that are hard1156 to analyse by one tool or technique could be trivially1157 processed by others and vice-versa. Hence, we con-1158 clude that using a standard set of problems, randomly1159 generated or not, is not sufficient for a full evaluation1160 of the performance of different tools. Instead, as in1161 our approach, the techniques and tools under evaluation1162 should be exercised to identify their strengths and weak-1163 nesses providing helpful information for both users and1164 developers.1165 The average effectiveness of our approach ranged1166 from 85.8% to 94.4% in all the experiments. As ex-1167 pected from an evolutionary algorithm, we found that1168 these variations in the effectiveness were caused by the1169 characteristics of the search spaces of each problem.1170 In particular, ETHOM behaves better when the search1171 space is heterogeneous and there are many different fit-1172 ness values, i.e. it is easy to compare the quality of1173 the individuals. However, results get worse in homo-1174 geneous search spaces in which most fitness values are1175 equal (e.g. Experiment #1, range of 10% of CTCs).1176 A common strategy to alleviate this problem is to use1177 a larger population, increasing the chances of the al-1178 gorithm finding promising individuals during initialisa-1179 tion. We also found that the maximum timeout of 301180 minutes was insufficient in some size ranges (e.g. Ex-1181 periment #2, 250 features and 30% CTCs), adversely1182 affecting the results. Increasing this timeout would have1183 certainly increased the effectiveness of ETHOM at the1184 price of making our experiments more time-consuming.1185 Finally, as a safety check, we tested ETHOM with1186 different optimisation problems. In particular, we used1187 problems with a known global maximum where the ef-1188 ficacy of ETHOM was easier to observe. For instance,1189 we used ETHOM to search for feature models with1190 nfeatures and m% of CTCs that represent as many1191 products as possible, 2nbeing the maximum. Interest-1192 ingly, the algorithm progressively removed the relation-1193 ships constraining the set of products (i.e. mandatory1194 and alternative), generating models with optional and1195 or-relationships only. This demonstrates the ability of1196 ETHOM to change the model if that helps to make it1197 better for the given problem. This and other examples1198 are available as a part of the BeTTy testing framework1199 [14].1200 5.4. Statistical analysis1201 Statistical analysis is usually performed by formulat-1202 ing two contrary hypotheses. The first hypothesis is re-1203 ferred to as the null hypothesis (Hi 0) and says that the1204 algorithm has no impact at all on the goodness of the re-1205 sults obtained, i.e. there is no difference between the re-1206 sults obtained by ETHOM and random search. Opposite1207 to the null hypothesis, an alternative hypothesis (Hi 1) is1208 formulated, stating that ETHOM has a significant ef-1209 fect in the quality of the results obtained. Statistical1210 tests provide a probability (named p-value) ranging in1211 [0,1]. A low p-value indicates that the null hypothesis is1212 probably false and the alternative hypothesis is probably1213 true, i.e. ETHOM works. Alternatively, high p-values1214 suggest that ETHOM does not work. Researchers have1215 established by convention that p-values under 0.05 or1216 16 0.01 are so-called statistically significant and are suf-1217 ficient to reject the null hypothesis, i.e. demonstrate1218 that ETHOM provides better results that random search.1219 The statistical analysis described in this section was per-1220 formed using the SPSS 17 statistical package [28].1221 The techniques used to perform the statistical analy-1222 sis and obtain the p-values depend on whether the data1223 follows a normal frequency distribution or not. After1224 some preliminary tests (Kolmogorov-Smirnov [35, 63]1225 and Shapiro-Wilk [60] tests) we concluded that our1226 data did not follow a normal distribution and thus our1227 tests required the use of so-called non–parametric tech-1228 niques. In particular, we applied the Mann-Withney U1229 non–parametric test [41] to the experimental results ob-1230 tained with ETHOM and random search. Tables A.61231 and A.7 show the results of these tests in SPSS for1232 Experiments #1 and #2 respectively. For each num-1233 ber of features and percentage of cross-tree constraints,1234 the values of the test are provided. As illustrated, the1235 tests rejected the null hypotheses with extremely low p-1236 values (zero in most cases) for nearly all experimental1237 configurations of both experiments. This, coupled with1238 the results shown in Section 5, clearly shows the su-1239 periority of our algorithm when compared to random1240 search. As expected, statistical tests accepted some null1241 hypotheses in the range of 10% of CTCs in Experiment1242 #1. As explained in Section 6, this is due to the small1243 complexity of the analysis on those models which made1244 the fitness landscape extremely flat. Similarly, the tests1245 accepted some null hypotheses in the range of 250 fea-1246 tures and 30% of CTCs in Experiment #2. This was1247 due to the maximum timeout of 30 minutes used for our1248 experiments that made our algorithm stop prematurely,1249 stopping it from evolving toward promising solutions.1250 For a more detailed explanation of our statistical anal-1251 ysis of the data we refer the reader to [59].1252 6. Threats to validity1253 In order to clearly delineate the limitations of the1254 experimental study, next we discuss internal and1255 external validity threats.1256 1257 Internal validity. This refers to whether there is1258 sufficient evidence to support the conclusions and1259 the sources of bias that could compromise those1260 conclusions. In order to minimise the impact of1261 external factors in our results, ETHOM was executed1262 25 times for each problem to get averages. Moreover,1263 statistical tests were performed to ensure significance1264 of the differences identified. Regarding the random1265 generation of feature models, we avoided the risk of1266 creating syntactically incorrect models as follows.1267 First, we used a publicly available (and previously1268 used) algorithm for the random generation of feature1269 models. Second, we performed several checks using1270 the parser of BeTTy, FaMa and SPLOT to make sure1271 that the generated models were syntactically correct1272 and had the desired properties, e.g. a maximum1273 branching factor. A related risk is the possibility of our1274 random and evolutionary algorithms having different1275 expressiveness, e.g. tree patterns that can be generated1276 with ETHOM but not with our random algorithm. To1277 minimise this risk, we imposed the same generation1278 constraints on both our random and evolutionary1279 generators. More specifically, both generators received1280 exactly the same input constraints: number of features,1281 percentage of CTC and maximum branching factor1282 of the model to be generated. Also, both generators1283 prohibit the generation of CTCs between features with1284 parental relation and features linked by more than1285 one CTC. A related limitation of the current ETHOM1286 encoding is that it does not allow there to be more than1287 one set relationship of the same type (e.g. alternative1288 group) under a parent feature. Hence, for instance,1289 if two alternative groups are located under the same1290 feature, these are merged into one during decoding.1291 We may remark, however, that this only affects the1292 expressiveness of ETHOM putting it at a disadvantage1293 against random search. Also, the results do not reveal1294 any correlation between the number of set relationships1295 and the hardness of the models which means that this1296 restriction did not benefit our algorithm. Besides this,1297 the results show that ETHOM is equally capable of1298 generating consistent or inconsistent models if that1299 make them harder for the target solver. Therefore, it1300 seems unlikely that our algorithm has a tendency to1301 generate only consistent or inconsistent models.1302 1303 External validity. This is concerned with how the ex-1304 periments capture the objectives of the research and the1305 extent to which the conclusions drawn can be gener-1306 alised. This can be mainly divided into limitations of1307 the approach and generalizability of the conclusions.1308 Regarding the limitations, the experiments showed1309 no significant improvements when using ETHOM with1310 problems of low complexity, i.e. feature models with1311 10% of constraints in Experiment #1. As stated in Sec-1312 tion 5.1, this limitation is due to the fitness landscape1313 being relatively flat for simple problems; most fitness1314 values are zero or close to zero. Another limitation of1315 the experimental approach is that experiments for ex-1316 tremely hard feature models become too time consum-1317 ing, e.g. feature models with 250 features in Experi-1318 17 ment #2. This threat is caused by the nature of the hard1319 feature models we intend to find, with the analysis of1320 promising feature models becoming increasingly time1321 consuming and memory intensive. We may remark,1322 however, that this limitation is intrinsic to the problem1323 of looking for hard feature models and thus it equally1324 affects random search. Finally, we emphasise that in1325 the worst case ETHOM behaves randomly equalling the1326 strategies for the generation of hard feature models used1327 in the current state of the art.1328 Regarding the generalisation of the conclusions, we1329 used two different analysis operations and the results1330 might not generalise further. We remark, however,1331 that these operations are currently the most frequently1332 quoted in the literature, have different complexity and,1333 more importantly, are the basis for the implementation1334 of many other analysis operations on feature models1335 [10]. Thus, feature models that are hard to analyse1336 for these operations would certainly be hard to anal-1337 yse for those operations that use them as an auxiliary1338 function making our results extensible to other analy-1339 ses. Similarly, we only used two analysis tools for the1340 experiments, FaMa and SPLOT. However, these tools1341 are developed and maintained by independent labora-1342 tories providing a sufficient degree of heterogeneity for1343 our study. Also, the results revealed that a number of1344 metrics for the generated models (e.g. percentage of1345 CTCs) were in the ranges observed in realistic models1346 found in the literature, which supports the realism of the1347 hard feature models being generated. We may remark,1348 however, that these models could still contain structures1349 that are unlikely in real-world models and therefore this1350 issue requires further research. Finally, our random and1351 evolutionary generators do not allow two features to be1352 linked by more than one CTC for simplicity (see Section1353 4). This implicitly prohibits the generation of cycles of1354 requires constraints, i.e. A−>Band B−>A. How-1355 ever, these cycles express equivalence relationships and1356 seem to appear in real models (e.g. Linux kernel fea-1357 ture model [49]) which could slightly affect the gener-1358 alisation of our results. These cycles will be allowed in1359 future versions of our algorithm.1360 7. Related work1361 In this section we discuss related work in the areas of1362 software product lines and search-based testing.1363 7.1. Software product lines1364 A number of authors have used realistic feature mod-1365 els to evaluate their tools [4, 9, 24, 26, 31, 33, 46,1366 45, 50, 51, 55, 64, 67, 70]. By realistic models we1367 mean those modelling real–world domains or a sim-1368 plified version of them. Some of the realistic feature1369 models most quoted in the literature are e-Shop [36]1370 with 287 features, graph product line [38] with up to1371 64 features and BerkeleyDB [34] with 55 features. Al-1372 though there are reports from industry of feature models1373 with hundreds or even thousands of features [7, 37, 66],1374 only a portion of them is typically published. This has1375 led authors to generate feature models automatically1376 to show the scalability of their approaches with large1377 problems. These models are generated either randomly1378 [12, 11, 22, 26, 44, 47, 57, 74, 75, 76, 78, 79] or using a1379 process that tries to produce models with the properties1380 of those found in the literature [23, 45, 64, 67]. More re-1381 cently, some authors have suggested looking for tough1382 and realistic feature models in the open source commu-1383 nity [13, 21, 49, 61, 62]. As an example, She et al. [62]1384 extracted a feature model from the Linux kernel con-1385 taining more than 5,000 features and compared it with1386 publicly available realistic feature models.1387 Regarding the size of the models used for experi-1388 ments, there is a clear tendency for model size to in-1389 crease: this ranges from the model with 15 features used1390 in 2004 [8] to models with up to 10,000 and 20,000 fea-1391 tures used in recent years [23, 45, 47, 67, 74]. These1392 findings reflect an increasing interest in using complex1393 feature models in performance evaluation. This also1394 suggests that the only mechanism used to increase the1395 complexity of the models is by increasing size. When1396 compared to previous work, our approach is the first to1397 use a search–based strategy to reveal the performance1398 weaknesses of the tools and techniques under evalua-1399 tion rather than simply using large randomly generated1400 models. This allows developers to focus on the search1401 for tough models of realistic size that could reveal de-1402 ficiencies in their tools rather than using huge feature1403 models out of their scope. Similarly, users could have1404 more information about the expected behaviour of the1405 tools in pessimistic cases helping them to choose the1406 tool or technique that best meets their needs.1407 The application of optimisation algorithms in the1408 context of software product lines has been explored by1409 several authors. Guo et al. [23] proposed a genetic al-1410 gorithm called GAFES for optimised feature selection1411 in feature models, e.g. selecting the set of features1412 that minimises the total cost of the product. Sayyad1413 et al. [55] compared the effectiveness of five multi-1414 objective optimization algorithms for the selection of1415 optimised products. Other authors [25, 39, 71] have1416 proposed algorithms for the selection of test suites (i.e.1417 set of products) maximising or minimising certain pref-1418 18 erences, e.g. feature coverage. Compared to their1419 work, our approach differs in several aspects. First, our1420 work addresses a different problem domain, hard fea-1421 ture model generation. Second, and more importantly,1422 ETHOM searches for optimum feature models while1423 related algorithms search for optimum product config-1424 urations. This means that ETHOM and related algo-1425 rithms bear no resemblance and face completely differ-1426 ent challenges. For instance, related algorithms use a1427 standard binary encoding to represent product configu-1428 rations while ETHOM uses a custom array encoding to1429 represent feature models of fixed size.1430 Pohl et al. [51] presented a performance comparison1431 of nine CSP, SAT and BDD solvers on the automated1432 analysis of feature models. As input problems, they1433 used 90 realistic feature models with up to 287 features1434 taken from the SPLOT repository [65]. The longest1435 execution time found in the consistency operation was1436 23.8 seconds, far from the 27.5 minutes found in our1437 work. Memory consumption was not evaluated. As part1438 of their work, the authors tried to find correlations be-1439 tween the properties of the models and the performance1440 of the solvers. Among other results, they identified an1441 exponential runtime increase with the number of fea-1442 tures in CSP and SAT solvers. This is not supported1443 by our results, at least not in general, since we found1444 feature models producing much longer execution times1445 than larger randomly generated models. Also, the au-1446 thors mentioned that SAT and CSP solvers provided a1447 similar performance in their experiment. This was not1448 observed in our work in which the SAT solver was much1449 more efficient than the CSP solver, i.e. random and1450 evolutionary search were unable to find hard problems1451 for SAT. Overall, we consider that using realistic fea-1452 ture models is helpful but not sufficient for an exhaus-1453 tive evaluation of the performance of solvers. In con-1454 trast, our work provides the community with a limitless1455 source of motivating problems to explore the strengths1456 and weaknesses of analysis tools.1457 In later work, Pohl et al. [52] proposed using width1458 measures from graph theory to characterise the struc-1459 tural complexity of feature models as a way to estimate1460 the difficulty in analysing them. They performed several1461 experiments running the consistency operation on ran-1462 domly generated models of up to 1,000 features in nine1463 state of the art CSP, SAT and BDD solvers. As a result,1464 for some of the solvers they found a correlation between1465 one of the metrics and the time taken by the analysis.1466 When compared to their work, ETHOM uses a black-1467 box strategy and thus it may be used to find hard input1468 feature models for any analysis tool or analysis opera-1469 tion regardless of their implementation details. Further-1470 more, ETHOM explores the whole search space of fea-1471 ture models, not only those with different width prop-1472 erties, in looking for input problems that increase the1473 execution times of analysis tools. Having said this, we1474 think that both works are complementary since ETHOM1475 generates hard feature models and their approach tries to1476 determine what makes the models hard to analyse.1477 During the preparation of this article, we presented a1478 novel application of ETHOM in the context of reverse1479 engineering of feature models [40]. More specifically,1480 we used ETHOM to search for a feature model that rep-1481 resents a specific set of products provided as input. The1482 results showed that within a few generations our algo-1483 rithm was able to find feature models that represent a1484 superset of the desired products. This contribution sup-1485 ports our claims about the generalisability of our algo-1486 rithm showing its applicability to other domains beyond1487 the analysis of feature models.1488 Finally, we would like to remark that our approach1489 does not intend to replace the use of realistic or ran-1490 domly generated models which can be used to evalu-1491 ate the average performance of analysis techniques. In-1492 stead, our work complements previous approaches en-1493 abling a more exhaustive evaluation of the performance1494 of analysis tools using hard problems.1495 7.2. Search-based testing1496 Regarding related work in search-based testing, We-1497 gener et al. [72] were the first to use genetic algorithms1498 to search for input values that produce very long or very1499 short execution times in the context of real time systems.1500 In their experiments, they used C programs receiving1501 hundreds or even thousands of integer parameters. Their1502 results showed that genetic algorithms obtained more1503 extreme execution times with equal or less test effort1504 than random testing. Our approach may be considered a1505 specific application of the ideas of Wegener and later au-1506 thors to the domain of feature modelling. In this sense,1507 our main contribution is the development and configura-1508 tion of a novel evolutionary algorithm to deal with opti-1509 misation problems on feature models and its application1510 to performance testing in this domain.1511 Many authors continued the work of Wegener et al.1512 in the application of metaheuristic search techniques to1513 test non-functional properties such as execution time,1514 quality of service, security, usability or safety [2]. The1515 techniques used by the search-based testing community1516 include, among others, hill climbing, ant colony opti-1517 misation, tabu search and simulated annealing. In our1518 approach, we used evolutionary algorithms inspired by1519 the work of Wegener et al. and their promising results in1520 a related optimisation problem, i.e. generation of input1521 19 values maximising the execution time in real time sys-1522 tems. We remark, however, that the use of other meta-1523 heuristic techniques for the generation of hard feature1524 models is a promising research topic that requires fur-1525 ther study.1526 GeneticAlgorithms(GAs)[1]area subclass of evolu-1527 tionary algorithms in which solutions are encoded using1528 bit strings. However, it is difficult to encode the hierar-1529 chical structure of feature models using this approach1530 and therefore we discarded their use. Genetic Program-1531 ming (GP) is another variant of evolutionary algorithms1532 in which solutions are encoded as trees [54]. This en-1533 coding is commonly used to represent programs whose1534 abstract syntax can be naturally represented hierarchi-1535 cally. Crossover in GP is applied on an individual by1536 switching one of its branches with another branch from1537 another individual in the population, i.e. individuals can1538 have different sizes. We identified several factors that1539 make GPs unsuitable for our problem. First, the classic1540 tree encoding does not consider cross-tree constraints as1541 in feature models. As a result, crossover would proba-1542 bly generate many dangling edges which may require1543 costly repairing heuristics. Second, and more impor-1544 tantly, crossover in GP does not guarantee a fixed size1545 for the solution which was a key constraint in our work.1546 These reasons led us to design a custom evolutionary al-1547 gorithm, ETHOM, supporting the representation of fea-1548 ture trees of fixed size with cross-tree constraints.1549 7.3. Performance evaluation of CSP and SAT solvers1550 CSP and SAT solvers (hereinafter, CP solvers) use1551 algorithms and techniques of Constraint Programming1552 (CP) to solve complex problems from domains such as1553 computer science, artificial intelligence or hardware de-1554 sign6. Theunderlying problems of CSP and SAT solvers1555 are NP-complete and so CSP and SAT solvers have an1556 exponential worst case runtime. This makes efficiency1557 a crucial matter for these types of tools. Hence, there1558 exist a number of available benchmarks to evaluate and1559 compare the performance of CP solvers [27]. Also, sev-1560 eral competitions are held every year to rank the per-1561 formance of the participants’ tools. As an example, 931562 solvers took part in the SAT competition7in 2013.1563 CP solvers use three main types of problems for per-1564 formance evaluation: problems from realistic domains1565 (e.g. hardware design), randomly generated problems1566 and hard problems. Both randomly generated and hard1567 6A SAT problem can be regarded a subclass of CSP with only boolean variables. 7http://www.satcompetition.org problems are automatically generated and are often1568 forced to have at least one solution (i.e. be satisfiable).1569 The CP research community realised long ago that there1570 are benefits in using hard problems to test the perfor-1571 mance of their tools. In 1997, Cook and Mitchell [17]1572 presented a survey on the strategies to find hard SAT1573 instances proposed so far. In their work, the authors1574 warned about the importance of generating hard prob-1575 lems for understanding their complexity and for provid-1576 ing challenging benchmarks. Since then, many other1577 contributions have explored the generation of hard SAT1578 and CSP problems [5, 77].1579 A common strategy to generate hard CSP and SAT1580 problems is by exploiting what is known as the phase1581 transition phenomenon [77]. This phenomenon estab-1582 lishes that for many NP-complete problems the hardest1583 instances occur between the region in which most prob-1584 lems are satisfiable and the region in which most prob-1585 lems are unsatisfiable. This happens because for these1586 problems the solver has to explore the search space in1587 depth before finding out whether the problem is satisfi-1588 able or not. CSP and SAT solvers can be parametrically1589 guided to search in the phase transition region enabling1590 the systematic generation of hard problems. We are not1591 aware of any work using evolutionary algorithms for the1592 generation of hard CP problems.1593 When compared to CP problems, the analysis of fea-1594 ture models differs in several ways. First, CSP and SAT1595 are related problems within the constraint programming1596 paradigm. The analysis of feature models, however, is a1597 high-level problem usually solved using quite heteroge-1598 neous approaches such as constraint programming, de-1599 scription logic, semantic web technologies or ad-hoc al-1600 gorithms [10]. Also, CP solvers focus on a single anal-1601 ysis operation (i.e. satisfiability) for which there exist1602 a number of well known algorithms. In the analysis of1603 feature models, however, more than 30 analysis opera-1604 tions have been reported. In this scenario, we believe1605 that our approach may help the community to generate1606 hard problems and study their complexity, leading to a1607 better understanding of the analysis operations and the1608 performance of analysis tools.1609 We identified two main advantages in our work when1610 compared to the systematic generation of hard CP prob-1611 lems. First, our approach is generic and can be applied1612 to any tool, algorithm or analysis operation for the au-1613 tomated treatment of feature models. Second, our algo-1614 rithm is free to explore the whole search space looking1615 for input models that reveal performance vulnerabilities.1616 In contrast, CP related work focuses the search for in-1617 puts problem in a specific area (the transition phase re-1618 gion).1619 20 Overall, we conclude that related work in CP support1620 our approach for the generation of hard feature mod-1621 els as a way to evaluate the performance strengths and1622 weakness of feature model analysis tools.1623 8. Conclusions and future work1624 In this paper, we presented ETHOM, a novel evo-1625 lutionary algorithm to solve optimisation problems on1626 feature models and showed how it can be used for1627 the automated generation of computationally hard fea-1628 ture models. Experiments using our evolutionary ap-1629 proach on different analysis operations and indepen-1630 dent tools successfully identified input models produc-1631 ing much longer executions times and higher memory1632 consumption than randomly generated models of iden-1633 tical or even larger size. In total, more than 50 mil-1634 lion executions of analysis operations were performed1635 to configure and evaluate our approach. This is the1636 first metaheuristic-based strategy to guide the search for1637 computationally hard feature models rather than sim-1638 ply using randomly generated models. This approach1639 will allow developers to focus on the search for tough1640 models of realistic size that could reveal deficiencies in1641 their tools rather than using huge randomly generated1642 feature models out of the scope of their tools. Simi-1643 larly, users are provided with more information about1644 the expected behaviour of the tools in pessimistic cases,1645 helping them to choose the tool or technique that better1646 meets their needs. Contrary to general belief, we found1647 that model size has an important, but not decisive, effect1648 on performance. Also, we found that the hard feature1649 models generated by ETHOM had similar properties to1650 realistic models found in the literature. This means that1651 the long execution times and high memory consumption1652 found by our algorithm might be reproduced in real sce-1653 narios with the consequent negative effect on the user.1654 In view of the positive results obtained, we expect this1655 work to be the seed for many other research contribu-1656 tions exploiting the benefits of ETHOM in particular,1657 and evolutionary computation in general, on the anal-1658 ysis of feature models. In particular, we envision two1659 main research directions to be explored by the commu-1660 nity in the future, namely:1661 •Algorithms development. The combination1662 of different encodings, selection techniques,1663 crossover strategies, mutation operators and other1664 parameters may lead to a whole new variety of evo-1665 lutionary algorithms for feature models to be ex-1666 plored. Also, the use of other metaheuristic tech-1667 niques (e.g. ant colony optimisation) is a promis-1668 ing topic that need further study. The develop-1669 ment of more flexible algorithms would be desir-1670 able in order to deal with other feature modelling1671 languages (e.g. cardinality-based feature models)1672 or stricter structural constraints, e.g. enabling the1673 generation of hard models with a given percent-1674 age of mandatory features. Also, the generation of1675 feature models with complex cross-tree constraints1676 (those involving more than two features) remains1677 an open challenge that we intend to address in our1678 future work.1679 •Applications. Further applications of our algo-1680 rithm are still to be explored. Some promising ap-1681 plications are those dealing with the optimisation1682 of non–functional properties in other analysis oper-1683 ations or even different automated treatments, e.g.1684 refactoring feature models. The application of our1685 algorithm to minimisation problems is also an open1686 issue in which we have started to obtain promising1687 results. Additionally, it would be nice to apply our1688 approach to verify the time constraints of real time1689 systems dealing with variability like those of mo-1690 bile phones or context–aware pervasive systems.1691 Last, but not least, we plan to study the hard fea-1692 ture models generated and try to understand what1693 makes them hard to analyse. From the information1694 obtained, more refined applications and heuristics1695 could be developed leading to more efficient tool1696 support for the analysis of feature models.1697 A Java implementation of ETHOM is ready-to-use1698 and publicly available as a part of the open-source1699 BeTTy Framework [14, 58].1700 Material1701 The prototype implementation of ETHOM, hard fea-1702 ture models generated (in XML format), statistical1703 results (in SPSS format) and raw experiment data1704 are available at http://www.lsi.us.es/~segura/1705 files/material/ESWA13/.1706 Acknowledgments1707 We would like to thank Dr. Don Batory, Dr. Javier1708 Dolado, Dr. Arnaud Gotlieb, Dr. Andreas Metzger, Dr.1709 Jose C. Riquelme, Dr. David Ruiz and Dr. Javier Tuya1710 whose comments and suggestions helped us to improve1711 the article substantially. We would also like to thank1712 Jos´ e A. Galindo for his work integrating ETHOM into1713 the framework BeTTy.1714 21 This work has been partially supported by the Euro-1715 pean Commission (FEDER) and Spanish Government1716 under CICYT projects SETI (TIN2009-07366) and1717 TAPAS (TIN2012-32273) and the Andalusian Govern-1718 ment projects THEOS (TIC-5906) and COPAS (P12-1719 TIC-1867).1720 Appendix A. Statistical analysis results1721 #Features CTC (%) 10 20 30 40 200 0.53 0 0 0 400 0.28 0 0 0 600 0.36 0 0 0 800 0 0 0 0 1000 0.12 0 0 0 Table A.6: p-values obtained in Experiment #1 using the MannWhitney-Wilcoxon test 1722 #Features CTC (%) 10 20 30 50 0 0 0 100 0 0 0 150 0 0 0 200 0 0 0 250 0 0 0.85 Table A.7: p-values obtained in Experiment #2 using the MannWhitney-Wilcoxon test 1723 References1724 [1] M. Affenzeller, S. Wagner, S. Winkler, and A. Beham. Genetic1725 Algorithms and Genetic Programming: Modern Concepts and1726 Practical Applications. Numerical Insights. Taylor & Francis,1727 2009.1728 [2] W. Afzal, R. Torkar, and R. Feldt. A systematic review of1729 search-based testing for non-functional system properties. In-1730 formation and Software Technology, 51(6):957–976, 2009.1731 [3] AHEAD Tool Suite. http://www.cs.utexas.edu/users/1732 schwartz/ATS.html, accessed July 2013.1733 [4] N. Andersen, K. Czarnecki, S. She, and A. Wasowski. Effi-1734 cient synthesis of feature models. In 16th International Software1735 Product Line Conference, pages 106–115, 2012.1736 [5] C. Ansotegui, R. Bejar, C. Fernandez, and C. Mateu. Edge1737 matching puzzles as hard SAT/CSP benchmarks. In P. Stuckey,1738 editor, Principles and Practice of Constraint Programming, vol-1739 ume 5202 of Lecture Notes in Computer Science, pages 560–1740 565. Springer Berlin /Heidelberg, 2008.1741 [6] D. Batory. Feature models, grammars, and propositional formu-1742 las. In Software Product Lines Conference (SPLC), volume 37141743 of Lecture Notes in Computer Sciences, pages 7–20. Springer–1744 Verlag, 2005.1745 [7] D. Batory, D. Benavides, and A. Ruiz-Cort´ es. Automated anal-1746 ysis of feature models: Challenges ahead. Communications of1747 the ACM, December:45–47, 2006.1748 [8] D. Benavides, A. Ruiz-Cort´ es, and P. Trinidad. Coping with au-1749 tomatic reasoning on software product lines. In Proceedings of1750 the 2nd Groningen Workshop on Software Variability Manage-1751 ment, November 2004.1752 [9] D. Benavides, A. Ruiz-Cort´ es, and P. Trinidad. Automated rea-1753 soning on feature models. In 17th International Conference on1754 Advanced Information Systems Engineering (CAiSE), volume1755 3520 of Lecture Notes in Computer Sciences, pages 491–503.1756 Springer–Verlag, 2005.1757 [10] D. Benavides, S. Segura, and A. Ruiz-Cort´ es. Automated anal-1758 ysis of feature models 20 years later: A literature review. Infor-1759 mation Systems, 35(6):615 – 636, 2010.1760 [11] D. Benavides, S. Segura, P. Trinidad, and A. Ruiz-Cort´ es. A first1761 step towards a framework for the automated analysis of feature1762 models. In Managing Variability for Software Product Lines:1763 Working With Variability Mechanisms, 2006.1764 [12] D. Benavides, S. Segura, P. Trinidad, and A. Ruiz-Cort´ es. Using1765 Java CSP solvers in the automated analyses of feature models.1766 LNCS, 4143:389–398, 2006.1767 [13] T. Berger, S. She, R. Lotufo, A. Wasowski, and K. Czarnecki.1768 Variability modeling in the real: a perspective from the operat-1769 ing systems domain. In Proceedings of the IEEE/ACM Interna-1770 tional Conference on Automated Software Engineering, pages1771 73–82. ACM, 2010.1772 [14] BeTTy Framework. http://www.isa.us.es/betty, ac-1773 cessed July 2013.1774 [15] BigLever. Biglever software gears. http://www.biglever.1775 com/, accessed July 2013.1776 [16] P. Clements and L. Northrop. Software Product Lines: Practices1777 and Patterns. SEI Series in Software Engineering. Addison–1778 Wesley, August 2001.1779 [17] S.A. Cook and D.G. Mitchell. Finding hard instances of the1780 satisfiability problem: A survey. In Satisfiability Problem: The-1781 ory and Applications, volume 35 of Dimacs Series in Discrete1782 Mathematics and Theoretical Computer Science, pages 1–17.1783 American Mathematical Society, 1997.1784 [18] A.E. Eiben and S.K. Smit. Parameter tuning for configuring1785 and analyzing evolutionary algorithms. Swarm and Evolution-1786 ary Computation, 1(1):19 – 31, 2011.1787 [19] FaMa Tool Suite. http://www.isa.us.es/fama/, accessed1788 July 2013.1789 [20] Feature Modeling Plug-in. http://gp.uwaterloo.ca/fmp/,1790 accessed July 2013.1791 [21] J.A. Galindo, D. Benavides, and S. Segura. Debian packages1792 repositories as software product line models. Towards auto-1793 mated analysis. In Proceedings of the 1st International Work-1794 shop on Automated Configuration and Tailoring of Applications1795 (ACoTA), Antwerp, Belgium, 2010.1796 [22] R. Gheyi, T. Massoni, and P. Borba. A theory for feature mod-1797 els in Alloy. In Proceedings of the ACM SIGSOFY First Alloy1798 Workshop, pages 71–80, Portland, United States, nov 2006.1799 [23] J. Guo, J. White, G. Wang, J. Li, and Y. Wang. A genetic algo-1800 rithm for optimized feature selection with resource constraints1801 in software product lines. Journal of Systems and Software,1802 84:2208–2221, December 2011.1803 [24] A. Hemakumar. Finding contradictions in feature models. In1804 First International Workshop on Analyses of Software Product1805 Lines (ASPL), pages 183–190, 2008.1806 [25] C. Henard, M. Papadakis, G. Perrouin, J. Klein, and Y.L. Traon.1807 Multi-objective test generation for software product lines. In1808 Proceedings of the 17th International Software Product Line1809 Conference, SPLC ’13, pages 62–71, New York, NY, USA,1810 2013. ACM.1811 [26] R. Heradio-Gil, D. Fernandez-Amoros, J.A. Cerrada, and1812 C. Cerrada. Supporting commonality-based analysis of software1813 22 product lines. Software, IET, 5(6):496 –509, dec. 2011.1814 [27] H. Hoos and T. Stutzle. SATLIB: An online resource for re-1815 search on SAT. In I.P. van Maaren, H. Gent, and T. Walsh, ed-1816 itors, Sat2000: Highlights of Satisfiability Research in the Year1817 2000, pages 283–292. IOS Press, 2000.1818 [28] IBM. SPSS 17 Statistical Package. http://www.spss.com/,1819 accessed November 2010.1820 [29] JaCoP. http://jacop.osolpro.com/, accessed July 2013.1821 [30] JavaBDD. http://javabdd.sourceforge.net/, accessed1822 July 2013.1823 [31] M.F. Johansen, Ø. Haugen, and F. Fleurey. An algorithm for1824 generating t-wise covering arrays from large feature models.1825 In 16th International Software Product Line Conference, pages1826 46–55, 2012.1827 [32] K. Kang, S. Cohen, J. Hess, W. Novak, and S. Peterson.1828 Feature–Oriented Domain Analysis (FODA) Feasibility Study.1829 Technical Report CMU/SEI-90-TR-21, SEI, 1990.1830 [33] A. Karatas, H. Oguzt¨ uz¨ un, and A. Dogru. Global constraints1831 on feature models. In D. Cohen, editor, Principles and Practice1832 of Constraint Programming, volume 6308 of Lecture Notes in1833 Computer Science, pages 537–551, 2010.1834 [34] C. Kastner, S. Apel, and D. Batory. A case study implementing1835 features using AspectJ. In SPLC ’07: Proceedings of the 11th1836 International Software Product Line Conference, pages 223–1837 232, Washington, DC, USA, 2007. IEEE Computer Society.1838 [35] A. Kolmogorov. Sulla determinazione empirica di una legge di1839 distribuzione. G. Inst. Ital. Attuari, 4:83, 1933.1840 [36] S.Q. Lau. Domain analysis of e-commerce systems using1841 feature–based model templates. master’s thesis. Dept. of ECE,1842 University of Waterloo, Canada, 2006.1843 [37] F. Loesch and E. Ploedereder. Optimization of variability in1844 software product lines. In Proceedings of the 11th Interna-1845 tional Software Product Line Conference (SPLC), pages 151–1846 162, Washington, DC, USA, 2007. IEEE Computer Society.1847 [38] R.E Lopez-Herrejon and D. Batory. A standard problem for1848 evaluating product-line methodologies. In GCSE ’01: Proceed-1849 ings of the Third International Conference on Generative and1850 Component-Based Software Engineering, pages 10–24, Lon-1851 don, UK, 2001. Springer-Verlag.1852 [39] R.E. Lopez-Herrejon, F. Chicano, J. Ferrer, A. Egyed, and1853 E. Alba. Multi-objective optimal test suite computation for soft-1854 ware product line pairwise testing. In Proceedings of the 29th1855 IEEE International Conference on Software Maintenance, 2013.1856 [40] R.E. Lopez-Herrejon, J.A. Galindo, D. Benavides, S. Segura,1857 and A. Egyed. Reverse engineering feature models with evolu-1858 tionary algorithms: An exploratory study. In Search Based Soft-1859 ware Engineering, volume 7515 of Lecture Notes in Computer1860 Science, pages 168–182. Springer Berlin Heidelberg, 2012.1861 [41] H.B. Mann and D.R. Whitney. On a test of whether one of two1862 random variables is stochastically larger than the other. Ann.1863 Math. Stat., 18:50–60, 1947.1864 [42] P. McMinn. Search-based software test data generation: a sur-1865 vey. Software Testing Verification and Reliability., 14(2):105–1866 156, 2004.1867 [43] M. Mendonca, M. Branco, and D. Cowan. S.P.L.O.T.: Software1868 Product Lines Online Tools. In Companion to the 24th ACM1869 SIGPLAN International Conference on Object-Oriented Pro-1870 gramming, Systems, Languages, and Applications (OOPSLA),1871 pages 761–762, Orlando, Florida, USA, October 2009. ACM.1872 [44] M. Mendonca, D.D. Cowan, W. Malyk, and T. Oliveira. Collab-1873 orative product configuration: Formalization and efficient algo-1874 rithms for dependency analysis. Journal of Software, 3(2):69–1875 82, 2008.1876 [45] M. Mendonca, A. Wasowski, and K. Czarnecki. SAT–based1877 analysis of feature models is easy. In Proceedings of the Inter-1878 national Sofware Product Line Conference (SPLC), 2009.1879 [46] M. Mendonca, A. Wasowski, K. Czarnecki, and D.D. Cowan.1880 Efficient compilation techniques for large scale feature models.1881 In 7th International Conference on Generative Programming1882 and Component Engineering (GPCE), pages 13–22, 2008.1883 [47] A. Osman, S. Phon-Amnuaisuk, and C.K. Ho. Using first or-1884 der logic to validate feature model. In Third International1885 Workshop on Variability Modelling in Software-intensive Sys-1886 tems (VaMoS), pages 169–172, 2009.1887 [48] J.A.. Parejo, A. Ruiz-Cort´ es, S. Lozano, and P. Fernandez.1888 Metaheuristic optimization frameworks: a survey and bench-1889 marking. Soft Computing - A Fusion of Foundations, Method-1890 ologies and Applications, 16:527–561, 2012.1891 [49] L. Passos, M.Novakovic, Y. Xiong, T. Berger, K. Czarnecki, and1892 A. Wasowski. A study of non-boolean constraints in variability1893 models of anembedded operating system. InThird International1894 Workshop on Feature-Oriented Software Development (FOSD),1895 SPLC ’11, pages 2:1–2:8. ACM, 2011.1896 [50] G. Perrouin, S. Oster, S. Sen, J. Klein, B. Baudry, and Y. Traon.1897 Pairwise testing for software product lines: comparison of two1898 approaches. Software Quality Journal, 20:605–643, 2012.1899 [51] R. Pohl, K. Lauenroth, and K. Pohl. A performance comparison1900 of contemporary algorithmic approaches for automated analy-1901 sis operations on feature models. In 26th International Con-1902 ference on Automated Software Engineering, pages 313–322.1903 IEEE, 2011.1904 [52] R. Pohl, V. Stricker, and K. Pohl. Measuring the structural com-1905 plexity of feature models. In 28th International Conference on1906 Automated Software Engineering, pages 454–464. IEEE, 2013.1907 [53] pure::variants. http://www.pure-systems.com/, accessed1908 July 2013.1909 [54] F. Rothlauf. Representations for Genetic and Evolutionary Al-1910 gorithms. Springer, 2nd edition, 2012.1911 [55] A.S. Sayyad, T. Menzies, and H. Ammar. On the value of user1912 preferences in search-based software engineering: A case study1913 in software product lines. In Proceedings of the 2013 Interna-1914 tional Conference on Software Engineering, ICSE ’13, pages1915 492–501, Piscataway, NJ, USA, 2013. IEEE Press.1916 [56] P. Schobbens, P. Heymans, J. Trigaux, and Y. Bontemps. Fea-1917 ture Diagrams: A Survey and A Formal Semantics. In Proceed-1918 ings of the 14th IEEE International Requirements Engineering1919 Conference (RE’06), Minneapolis, Minnesota, USA, September1920 2006.1921 [57] S. Segura. Automated analysis of feature models using atomic1922 sets. In First Workshop on Analyses of Software Product Lines1923 (ASPL), pages 201–207, Limerick, Ireland, September 2008.1924 [58] S. Segura, J.A. Galindo, D. Benavides, J.A. Parejo, and A. Ruiz-1925 Cort´ es. BeTTy: Benchmarking and Testing on the Automated1926 Analysis of Feature Models. In U.W. Eisenecker, S. Apel, and1927 S. Gnesi, editors, Sixth International Workshop on Variabil-1928 ity Modelling of Software-intensive Systems (VaMoS’12), pages1929 63–71, Leipzig, Germany, 2012. ACM.1930 [59] S. Segura, J.A. Parejo, R.M. Hierons, D. Benavides, and1931 A. Ruiz-Cort´ es. ETHOM: An evolutionary algorithm for1932 optimized feature models generation (v1.3). Technical Re-1933 port ISA-2013-TR-01, Applied Software Engineering Research1934 Group, Seville, Spain, 2013. http://www.isa.us.es/1935 sites/default/files/HardFMUsingEA_1.pdf.1936 [60] S. S. Shapiro and M. B. Wilk. An analysis of variance test1937 for normality (complete samples). Biometrika, 52(3/4):pp. 591–1938 611, 1965.1939 [61] S. She, R. Lotufo, T. Berger, A. Wasowski, and K. Czarnecki.1940 The variability model of the linux kernel. In Fourth Interna-1941 tional Workshop on Variability Modelling of Software-intensive1942 Systems (VaMoS), Linz, Austria, January 2010.1943 23 [62] S. She, R. Lotufo, T. Berger, A. Wasowski, and K. Czarnecki.1944 Reverse engineering feature models. In Proceeding of the 33rd1945 International Conference on Software Engineering, pages 461–1946 470. ACM, 2011.1947 [63] N. V. Smirnov. Tables for estimating the goodness of fit of em-1948 pirical distributions. Annals of Mathematical Statistic, 19:279,1949 1948.1950 [64] S. Soltani, M. Asadi, D. Gasevic, M. Hatala, and E. Bagheri.1951 Automated planning for feature model configuration based on1952 functional and non-functional requirements. In 16th Interna-1953 tional Software Product Line Conference, pages 56–65, 2012.1954 [65] S.P.L.O.T.: Software Product Lines Online Tools. http://1955 www.splot-research.org/, accessed July 2013.1956 [66] M. Steger, C. Tischer, B. Boss, A. M¨ uller, O. Pertler, W. Stolz,1957 and S. Ferber. Introducing PLA at Bosch gasoline systems: Ex-1958 periences and practices. In International Sofware Product Line1959 Conference (SPLC), pages 34–50, 2004.1960 [67] T. Th¨ um, D. Batory, and C. K¨ astner. Reasoning about edits to1961 feature models. In International Conference on Software Engi-1962 neering, pages 254–264, 2009.1963 [68] Edward Tsang. Foundations of Constraint Satisfaction. Aca-1964 demic Press, 1995.1965 [69] S. Voß. Meta-heuristics: The state of the art. In ECAI ’00:1966 Proceedings of the Workshop on Local Search for Planning and1967 Scheduling-Revised Papers, pages 1–23. Springer-Verlag, Lon-1968 don, UK, 2001.1969 [70] H.H. Wang, Y.F. Li, J. Sun, H. Zhang, and J. Pan. Verifying1970 feature models using OWL. Journal of Web Semantics, 5:117–1971 129, June 2007.1972 [71] S. Wang, S. Ali, and A. Gotlieb. Minimizing test suites in1973 software product lines using weight-based genetic algorithms.1974 In Proceeding of the Fifteenth Annual Conference on Genetic1975 and Evolutionary Computation Conference, GECCO ’13, pages1976 1493–1500, New York, NY, USA, 2013. ACM.1977 [72] J. Wegener, K. Grimm, M. Grochtmann, and H. Sthamer. Sys-1978 tematic testing of real-time systems. In Proceedings of the1979 Fourth International Conference on Software Testing and Re-1980 view (EuroSTAR), 1996.1981 [73] J. Wegener, H. Sthamer, B.F. Jones, and D.E. Eyres. Testing1982 real-time systems using genetic algorithms. Software Quality1983 Control, 6(2):127–135, 1997.1984 [74] J. White, B. Doughtery, and D. Schmidt. Selecting highly op-1985 timal architectural feature sets with filtered cartesian flattening.1986 Journal of Systems and Software, 82(8):1268–1284, 2009.1987 [75] J. White, B. Doughtery, D. Schmidt, and D. Benavides. Au-1988 tomated reasoning for multi-step software product-line config-1989 uration problems. In Proceedings of the Sofware Product Line1990 Conference, pages 11–20, 2009.1991 [76] J. White, D. Schmidt, D. Benavides P. Trinidad, and Ruiz-1992 Cort´ es. Automated diagnosis of product-line configuration er-1993 rors in feature models. In Proceedings of the 12th Sofware1994 Product Line Conference (SPLC), Limerick, Ireland, September1995 2008.1996 [77] K. Xu, F. Boussemart, F. Hemery, and C. Lecoutre. Random1997 constraint satisfaction: Easy generation of hard (satisfiable) in-1998 stances. Artificial Intelligence, 171(8-9):514–534, 2007.1999 [78] H. Yan, W. Zhang, H. Zhao, and H. Mei. An optimization strat-2000 egy to feature models’ verification by eliminating verification-2001 irrelevant features and constraints. In ICSR, pages 65–75, 2009.2002 [79] W. Zhang, H. Yan, H. Zhao, and Z. Jin. A BDD–based approach2003 to verifying clone-enabled feature models’ constraints and cus-2004 tomization. In 10th International Conference on Software Reuse2005 (ICSR), LNCS, pages 186–199. Springer, 2008.2006 24