Many-Objective Test Suite Generation for Software Product Lines

Many-Objective Test Suite Generation for Software Product Lines ROBERT M. HIERONS, The University of Sheffield MIQING LI, The University of Birmingham XIAOHUI LIU, Brunel University JOSE ANTONIO PAREJO and SERGIO SEGURA, Universidad de Sevilla XIN YAO, Southern University of Science and Technology and The University of Birmingham A Software Product Line (SPL) is a set of products built from a number of features, the set of valid products being defined by a feature model. Typically, it does not make sense to test all products defined by an SPL and one instead chooses a set of products to test (test selection) and, ideally, derives a good order in which to test them (test prioritisation). Since one cannot know in advance which products will reveal faults, test selection and prioritisation are normally based on objective functions that are known to relate to likely effectiveness or cost. This article introduces a new technique, the grid-based evolution strategy (GrES), which considers several objective functions that assess a selection or prioritisation and aims to optimise on all of these. The problem is thus a many-objective optimisation problem. We use a new approach, in which all of the objective functions are considered but one (pairwise coverage) is seen as the most important. We also derive a novel evolution strategy based on domain knowledge. The results of the evaluation, on randomly generated and realistic feature models, were promising, with GrES outperforming previously proposed techniques and a range of many-objective optimisation algorithms. Additional Key Words and Phrases: Software product line, test selection, test prioritisation, multi-objective optimisation This work has been partially supported by the European Commission (FEDER) and Spanish Government under CICYT projects BELI (TIN2015-70560-R) and HORATIO (RTI2018-101204-B-C21), the Science and Technology Innovation Committee Foundation of Shenzhen (ZDSYS201703031748284), Shenzhen Peacock Plan (KQTD2016112514355531), the Program for Guangdong Introducing Innovative and Enterpreneurial Teams (Grant No. 2017ZT07X386), and EPSRC (EP/J017515/1 and EP/P005578/1). Authors’ addresses: R. M. Hierons, The University of Sheffield; email: [email protected]; M. Li, The University of Birmingham; email: [email protected]; X. Liu, Brunel University; email: [email protected]; J. A. Parejo and S. Segura, Universidad de Sevilla; emails: {japarejo, sergiosegura}@us.es; X. Yao, Southern University of Science and Technology and The University of Birmingham; email: [email protected]. 1 INTRODUCTION A Software Product Line (SPL) is a set of products, which are built from a number of features, a feature being some aspect of functionality [11]. A product can be seen as being a set of features and feature models are often used to define the allowed combinations of features and so the valid products. There is evidence of a number of companies using feature models, including Boeing [64], Siemens [35], and Toshiba [55]. Ideally one would test all of the products in an SPL defined by a feature model. However, a feature model might specify a vast number of products; often it is not feasible to test every valid product. In addition, since the products of an SPL are built from a common set of features, one would expect that the testing of all valid products would introduce significant redundancy. Thus, even if one could test all valid products, this is likely to be inefficient and, assuming a limited testing budget, might also be ineffective. These observations have led to two problems being investigated: the problem of choosing a set of products to test (the test selection problem) and the problem of choosing a good order in which products should be tested (the test prioritisation problem). Test selection aims to choose products that are likely to reveal any faults that are present, while prioritisation aims to find faults as early as possible. Previous work in this area has taken the view that these problems complement each other and has therefore considered selection and prioritisation together [24, 29, 50, 73]. This is the approach we also take in this article. The selection and prioritisation problems, as described above, are expressed in terms of the actual faults in the products of an SPL. However, normally the tester does not have access to this information before testing begins. Thus, the problem is to find a test suite (sequence of valid products) that is likely to be a good solution (in terms of selection and prioritisation). It has been observed that a number of properties of good test suites can be captured by objective functions that map a test suite to a value that represents how “good” this test suite is according to the properties (see, for example, [19], [23], [29], [31], [32], [48], [50], [57], [60], [70], [71], and [73]). For example, a fault might be associated with the interaction of a pair of features and so we might want to test as many such interactions as possible (pairwise coverage). This is an example of a functional objective; one associated with the functionality of the features and how the features are combined in the feature model. There are also non-functional objectives (quality attributes) such as the cost of a feature. Since a number of objectives/fitness functions have been identified, the problem of finding a good solution has been expressed as a multi-objective optimisation problem [19, 23, 24, 31, 47, 48, 54, 57, 70, 71, 73]. Previous work developed test-generation approaches based on evolutionary multi-objective algorithms and found these to be effective [19, 23, 31, 48, 57, 70, 71, 73]; a recent survey was provided by Lopez-Herrejon et al. [49]. The literature on test generation from feature models has three important limitations that we address in this article. First, most previous work has looked at multi-objective optimisation problems, in which there are two or three objectives, but only a few have explored the benefits of many-objective optimisation, with four [23, 73] and five objectives [71]. In fact, Lopez-Herrejon et al. [49] explicitly mentioned many-objective search in SPL testing as an open challenge. Second, previous work has typically addressed the problem by either weighting the objectives or separately considering test selection and prioritisation. Third, all previous approaches have resorted to standard state-of-the-art optimisation algorithms neglecting the potential benefits of exploiting the knowledge of the problem to develop more powerful algorithms. As a result, such approaches may either be unable to provide a set of good trade-offs for the tester or fail to guarantee the quality of the test suite on some objectives. In this article, we address the many-objective optimisation problem and devise a novel approach to this optimisation problem, the grid-based evolution strategy (GrES). In addition, the proposed approach is inspired by the observation that typically, when testing the products of a product line, the tester will want to ensure that all pairs of features are tested. The motivation for this is that combinatorial testing, and specifically pairwise testing, is the main coverage criterion considered in the SPL literature (e.g., in [52], the authors identified over 40 approaches for combinatorial testing in SPL). The essential idea is that we have a type of coverage that should be achieved and we want the “best” solution that achieves this coverage. Naturally, it would be straightforward to generalise the approach to the case where one wants to achieve a certain level of pairwise coverage that is less than 100%. As a result of our approach, the proposed evolution strategy prioritises pairwise coverage: when comparing two solutions, it first compares them on pairwise coverage and only then (if they have the same pairwise coverage) on the other objectives. In Section 3,we further explain and justify this decision. An alternative approach would be to weight the different objectives, in order to turn a multiobjective optimisation problem into a single-objective optimisation problem (see, for example, [19], [31], [70], [73]). However, the multi-objective approach has a number of advantages. In the singleobjective approach, when giving a high weight to a particular objective (such as pairwise coverage), one is making this “more important” but by a fixed multiplier. Thus, for example, if we have two objectives and we give the first a weighting ten times that of the second, then (under minimisation) we prefer (3,12) to (4,3) but we do not prefer (3,12) to (4,1). In contrast, in our approach, we always prefer a solution with higher pairwise coverage—we are saying that pairwise coverage is more important than the other objectives, rather than it being X times more important for some fixed X. This better captures the nature of the problem. In addition, the multi-objective approach provides a range of trade-offs between the other objectives (those other than pairwise coverage) and the developer can then assess these alternatives and choose from them. Note also that GrES does not require the developer to choose values for weights; for the single-objective approach, it is unclear how a developer would choose weights without, for example, some initial experiments/tuning. This article makes the following main contributions. It proposes a novel approach to manyobjective test suite generation for software product lines, in which we consider nine fitness functions. Novelty is also provided by the algorithm design, which uses a rarely used class of evolutionary algorithms (evolution strategy) that works on a small population and does not have a crossover operation (i.e., asexual reproduction—variance being introduced only by mutation). We also customised the evolution strategy by taking advantage of domain knowledge in selecting individuals for variation. This article then reports on the results of experiments that compared GrES with two algorithms previously devised for this problem and a range of multi-objective optimisation algorithms. The evaluation used randomly generated feature models, in order to enable us to explore the effect of the size of the feature model. It also used 19 realistic feature models: feature models from the literature with randomly generated attribute values. Finally, this article reports on the results of an experiment using a realistic feature model with real attribute values. In the experiments, we found that the proposed approach for comparing individuals always led to a population in which all individuals (test suites) provided full pairwise coverage; in contrast, the other approaches returned populations in which at most 10% of individuals provided full pairwise coverage. In addition, GrES returned populations that had higher quality, as assessed by their hyper-volume (HV)1[81], with many of the effect sizes being large. In order to evaluate whether the use of an evolution strategy was a good choice, we also had experiments in which a number of different multi-objective approaches were adapted to use our novel comparison mechanism. In these experiments, all approaches returned a population whose individuals all had full pairwise 1HV is a metric which can reflect the quality of a solution set in both approaching the optimal solution set and diversifying its solutions. Fig. 1. Mobile phone feature model [57]. coverage. However, the evolution strategies returned the highest HV values, with most differences being statistically significant. Two previous multi-objective approaches used variants of NSGA-II but with fewer objectives [48,57]. We had experiments in which we compared GrES with these two approaches, restricting the objectives considered in the evaluation to those previously used. Unsurprisingly, the results more mixed: GrES produced lower HV values for the smaller models buthigherHVvaluesforthelargermodels.Notethatwedidnotchangethesetofobjectives that GrES was attempting to optimise and so GrES had the disadvantage of considering additional objectives that were not used in the comparison. Finally, experiments were performed to assess scalability; in this it was found that GrES is faster than the two previous approaches and that the approaches that use our novel comparison mechanism had similar execution times. This article is structured as follows: In Section 2, we review background material, and in Section 3, we describe our novel many-objective approach. Section 4then outlines the experimental design while Section 5gives the results of the experiments and discusses these. In Section 6, we discuss threats to validity and Section 7then places our work in the context of the literature. Finally, in Section 8, we draw conclusions and discuss possible lines of future work. 2 BACKGROUND 2.1 Feature Models Software Product Lines (SPL) engineering focuses on the systematic development of families of software products [11]. Products in SPLs are represented in terms of features where a feature is any distinguishable characteristic relevant for the stakeholders [37]. A feature model is a tree-like representation of all the products of an SPL in terms of features and relationships among them. These relationships constrain the way in which features can be combined to form valid products. Feature models were first introduced as a part of the Feature-Oriented Domain Analysis method (FODA) by Kang et al. back in 1990 [37]. Since then, feature modelling has become the de-facto standard for variability management in SPLs. Figure 1depicts a sample feature model representing an SPL for mobile phones [57]. The software loaded into the mobile phone is determined by the features that it supports, e.g., Camera. The root feature (“Mobile Phone”) identifies the SPL. The following types of relationships constrain how features can be combined in a product: •Mandatory. If a feature has a mandatory relationship with its parent feature, it must be included in all the products in which its parent feature appears. In Figure 1, all the products of the SPL must provide support for the mandatory feature Calls. Table 1. Mobile Phone Feature Attributes Feature Changes Cost Faults Size Basic 1 25 0 270 Calls 6 20 5 1,000 Camera 12 35 7 680 GPS 8 45 11 460 HD 3 25 2 510 Media 9 5 5 1,100 MP3 4 10 3 390 Screen 2 5 1 930 •Optional. If a feature has an optional relationship with its parent feature, it can be optionally included in the products that include its parent feature. For instance, GPS is defined as an optional feature in Figure 1. •Alternative. The children of a feature are defined as alternatives if exactly one feature should be selected when its parent feature is part of the product. In the example, mobile phones must support a Basic or a High Definition (HD) screen, but not both in the same product. •Or-Relation. Child features are said to have an or-relation with their parent when one or more of them can be included in the products in which its parent feature appears. In Figure 1, mobile phones may include a Camera,anMP3 player, or both of them. In addition to hierarchical relationships, feature models can also contain Cross-Tree Constraints (CTCs) between features. These are typically of the form “Feature A requires feature B” or “Feature A excludes feature B”. In Figure 1, mobile phones including a Camera require an HD screen. Feature models can be extended with extra-functional information by means of feature attributes. These models are referred to as attributed feature models. An attribute usually consists of a name, a domain, and a value, e.g., GPS.cost =20. Attributes are usually represented either graphically in the feature model or as a table indicating the values of the attributes for each feature. Table 1depicts four sample numeric attributes and random values for the features of the model in Figure 1,namelyChanges (number of changes), Cost (estimated cost of the resources needed to test the feature), Faults (number of reported defects), and Size (numberoflinesofcode). Feature models can be automatically analysed to extract information from them. Catalogues with up to 30 analysis operations on feature models have been published [9]. Typical analysis operations allow us to know whether a feature model is consistent (it represents at least one product), the number of products represented by a feature model, or whether a feature model contains any errors. The analysis of feature models is supported by a number of tools including the FaMa framework [68], FeatureIDE [67], PLEDGE [30], and Clafer [8]. SPL testing approaches typically follow a model-based approach, where the feature model represents the testing space of the product line, and the products represent potential test cases. In this article, a test case is a product and so we use these two terms interchangeably. Likewise, we define a test suite to be a sequence of test cases, i.e., products. The number of products represented by a feature model tends to increase exponentially with the number of features. Hence, for instance, the Drupal feature model, derived from the popular Web framework Drupal, has 48 features and 21 cross-tree constraints, and it represents 2.09 ·109potential products [59]. Thus, typically it is not feasible to test every single product. To address this problem, several test case selection techniques have been proposed to select a representative subset of the products to be tested. Among them, pairwise testing is a highly used technique that selects test suites that contain all the possible Table 2. Mobile Phone Pairwise Test Suite with Pairwise Coverage of Features ID Test Case TC1 Mobile Phone, Calls, Screen, Basic, Media, MP3 TC2 Mobile Phone, Calls, Screen, HD, GPS, Media, Camera, MP3 TC3 Mobile Phone, Calls, Screen, HD, Media, Camera TC4 Mobile Phone, Calls, Screen, HD TC5 Mobile Phone, Calls, Screen, Basic, GPS combinations of pairs of features [52]. For instance, Table 2 depicts a pairwise suite for the model in Figure 1, where the number of products is reduced from 12 (total number of products represented by the model) to 5 containing all the possible feature pairs. However, as will be explained later, there are many other properties of a good selection or prioritisation that can be captured by a range of fitness functions. For example, recently changed features tend to be more fault prone and so ideally should be included in products that are tested relatively early in the process. 2.2 Evolutionary Multi-Objective Optimisation In multi-objective optimisation, we have two or more objectives/fitness functions that we wish to optimise. Let us suppose that we have a multi-objective optimisation problem in which the search space is X . The classic approach to comparing two candidate solutions A ∈ X and B ∈ X is to use Pareto dominance [12], where A is said to Pareto dominate B if A is better than B on at least one objective and at least as good as B on all other objectives. Thus, if A Pareto dominates B and we have already found A, then there is no point in considering B; A is preferable to B.Incontrast,if A and B are not related under Pareto dominance then they represent different trade-offs between the objectives. Under Pareto dominance, the “best” candidate solutions are those in the Pareto optimal set (called Pareto front) in the objective space, which is the set of elements in X that are not Pareto dominated by any other element in X . Evolutionary algorithms (EAs) are a class of stochastic search and optimisation methods that mimic the process of natural evolution. Over the past two decades, there has been significant interest in the use of EAs to solve multi-objective optimisation problems (MOPs) [12, 16, 79], the resulting research branch called evolutionary multi-objective optimisation (EMO). The success of EMOs can be attributed to two major advantages of EAs. One is that they have low requirements on the problem characteristics and are capable of handling large and highly complex search spaces. The other is that their population-based search can achieve an approximation of the problem’s whole Pareto front. The population returned represents a set of alternative trade-offs between the objectives. In general, evolutionary algorithms can be loosely categorised into three metaheuristics: genetic algorithm (GA), evolution strategy (ES), and genetic programming (GP) [4]. GA and ES are commonly used to generate solutions to optimisation and search problems, while the solutions in GP are in the form of computer programs. GA often operates on a relative large population (e.g., with 100 individuals), and performs both crossover and mutation to produce new individuals. In contrast, ES is based on ideas of self-adaptation, and often has a very small population and no crossover in its variation operation [62]. Formally, an ES has a (μ + λ) evolution form, where μ and λ are the number of parental individuals and offspring individuals, respectively. In EMO, most algorithms are GAs; very few are based on the ES principles and the most popular multi-objective ES is the Pareto archived evolution strategy (PAES) [38, 39]. Many-objective optimisation refers to the simultaneous optimisation of four or more objectives [40]. There are a number of differences between many-objective optimisation and multiobjective optimisation with two or three objectives. The increase in objective dimensionality can bring many difficulties, such as the ineffectiveness of the Pareto dominance criterion, aggravation of the conflict between convergence and diversity, inaccuracy of density estimation, inefficiency of recombination operation, increasing sensitivity to parameter settings, and rapid increase of time or space requirement. These issues cause significant challenges when using EAs in dealing with many-objective optimisation problems, especially for Pareto-based approaches. 3 THE PROPOSED ALGORITHM In this section, we describe the proposed algorithm, the grid-based evolution strategy (GrES). We start by presenting an approach to optimisation (i.e., how to view the objectives to be optimised) that takes into account domain knowledge. We then explain the motivation for using an evolution strategy (rather than a generic genetic algorithm), and also what makes GrES different from existing evolution strategies. Next we describe the method used for selecting parental individuals for variation in the evolutionary process. This is followed by an explanation of the individual encoding and variation operators. Finally, we give the main procedure of GrES. 3.1 Optimisation Approach As stated previously, SPL test suite generation can be seen as a combination of two problems, the test selection problem and the prioritisation problem. Test selection aims to choose products (as few as possible) that are likely to reveal any faults that are present, while prioritisation aims to find faults as early as possible. These problems result in two groups of objectives to be optimised in test suite generation: selection (including pairwise coverage), and prioritisation. Note that the two groups often have several objectives, and this thus forms an optimisation problem with many objectives. Much of the previous work in the area has integrated all (or some) of the above objectives into one single fitness function with weighting factors (see, for example, [31], [54], [70], [73]). As previously discussed, when giving a high weight to a particular objective (such as pairwise coverage), one is making this more important by a fixed multiplier. This less effectively represents the nature of the problem, in which one objective is more important than the others (and not by a fixed ratio). Another (complementary) approach that has been used is to separately consider test selection and prioritisation (see, for example, [1], [19], [29], [31], [47], [48], [54], [57], [60]). These approaches can decrease the difficulty of the considered problem from many objectives to multiple objectives. However, they may either be unable to provide a set of good trade-offs for the tester or fail to guarantee the quality of the test suite on some objectives (i.e., those not being considered in the optimisation). In this article, we use nine fitness functions that represent both groups of objectives and aim to achieve a set of good trade-offs between them. Yet, we do not treat all the objectives equally; instead we consider pairwise coverage first and then optimise the remaining objectives simultaneously. This was motivated by the fact that pairwise coverage can be seen as the main aim in test suite generation—we want to achieve full pairwise coverage and ideally also do well for other objectives. Another advantage of this approach is that it avoids the simultaneous optimisation of heavily conflicting objectives (i.e., pairwise coverage versus cost), thus enabling Pareto-based approaches (those using Pareto dominance to assign individuals’ fitness) to work well on this many-objective problem. This can be seen in the proposed Pareto-based algorithm GrES. Fig. 2. Grid-based archive in a bi-objective case, where the grid degree of nondominated solutions A, B, C, D and E is 1, 1, 2, 2 and 1, respectively. For selection (i.e., Selection_III(Q)in Step 3 of Algorithm 1), only the solution with the lowest grid degree (A, B or E) is considered. For archive truncation (i.e., Algorithm 5), only the solution with the highest grid degree (C or D) is considered. The grid environment was constructed by predefined divisions and the boundaries of the nondominated solutions adaptively, see [76] for details. Specifically, we use two simple rules to compare two individuals in the (environmental) selection process of GrES2: (1) preferring the individual with higher pairwise coverage and (2) preferring the individual with better fitness (determined by the other objectives) when their pairwise coverage is equal. 3.2 Why Use an Evolution Strategy We ran some initial experiments with EAs on the considered SPL testing problem, with a seeding strategy that used the CASA tool to generate an initial test suite that achieves full pairwise coverage, as in [48]. In these initial experiments, we observed that, with the seeding strategy, evolutionary search that had no crossover operation performed better than (or at least as well as) search that used crossover. And we also observed that the crossover between the seed individual and a randomly generated individual typically produced offspring with worse performance (i.e., prioritisation objectives and cost objectives) than the seed individual. One explanation for this is that a crossover operation, which typically brings a big change to the individual, could disturb some good building blocks of chromosomes in the seed individual. In addition, we also observed that in an algorithm without crossover the individuals in the final population were all from the seed individual (i.e., all being offspring of the seed individual). This means that randomly generated individuals in the initial population make no contribution to the final result. Given these two observations, evolution strategy, which has a very small population size and no crossover operator, seems a good option. That is, we continually do some variations around the seed individual and its offspring during the evolutionary process in an effort to produce some new promising individuals. This has the potential to significantly reduce the number of evaluations, resulting from the randomly generated individuals, and make the search focus on the seed individual. Like PAES [39], GrES uses a grid-based archive (see Figure 2) to store promising solutions (nondominated solutions3) generated during the evolutionary process. However, GrES significantly 2These two rules can apply to any EMO algorithm, and in our experimental studies, the peer EMO algorithms used the same rules in their selection process. 3Note that the dominance rule is based on the proposed optimisation approach; i.e., for two solutions p and q,ifp dominates q, then either p has a better coverage than q,orp has the same coverage as q but dominates q on the remaining objectives. differs from PAES (and other ESs) in that the current population (i.e., the solutions that act as parental individuals to generate offspring) is not based on the last-generation population and their offspring, but rather its elements are selected carefully from the archive set. In each generation, GrES selects three specific individuals from the archive according to some domain knowledge (this will be explained in detail in the next subsection) to form the current population and mutates them to form three new individuals, thus resulting in a (3+3) evolution form. Finally, it is worth mentioning that the grid-based archive of GrES is managed by an individualcentred calculation environment (inspired by [76]) whose computational cost is virtually independent of the number of hyperboxes in the grid and only increases linearly with the number of objectives. This contrasts with many grid-based EAs (such as PAES) whose selection operation entails a traversal of all the hyperboxes in the grid; the number of such hyperboxes grows exponentially with the number of objectives [14]. 3.3 Selection for Variation In an evolving population, the selection of the individuals from which to produce offspring (called mating selection) is crucial. Unlike existing ESs, whose population always comes from either the last-generation population or their offspring, GrES constructs the population by selecting some specific solutions from the archive set. Here, we explain how domain knowledge was used to design the mating selection of the algorithm. Specifically, GrES takes advantage of the fact that in the test suite generation problem the cost objectives are not directly in conflict with the prioritisation objectives. That is, removing a product in a test suite does not necessarily worsen the prioritisation objectives of the suite, and changing the order of products in a test suite for a better prioritisation does not increase the cost of the test suite. This also means that a test suite may achieve both a high prioritisation and a low cost. In light of this, we consider the following two operations. One operation randomly performs some variations on an individual in the archive to achieve a better cost or prioritisation. For better cost, a test case removal operation (which will be explained in the next subsection) is carried out in order to tentatively reduce the suite size. For better prioritisation, a test case swap operation is carried out to give a perturbation. Note that, in each generation of GrES, only one individual in the archive set is selected to perform the above variations. The selection is based on the grid; this process is like the one in PESA-II [13]. First, we randomly select one non-empty hyperbox in the grid and then randomly select one individual from this hyperbox. The other operation is applied to the individual having the best prioritisation under one specific size of the current test suites; i.e., from a set of test suites with the same number of test cases in the population, the operator selects one with the best prioritisation (determined by the sum of the normalised prioritisation objectives). For this individual, one of the four variations, test case swap, test case removal, test case addition and test case substitution, is randomly performed. The test case removal operation is to tentatively reduce the suite size of the individual. The test case swap and addition operations are to tentatively increase the prioritisation values of the individual. The test case substitution is for both. Finally, as the archive only allows the entry of new individuals that are not dominated by the existing individuals in the archive, it contains the best individuals produced so far. Individuals located in sparse areas of the archive tend to have not been developed well, e.g., they are probably newly produced individuals that just entered the archive. Here, we try to explore such individuals. To do so, we consider a well-known density estimator, grid degree [13]. Specifically, we first consider a non-empty hyperbox with the fewest individuals in the archive (randomly select one if there are two or more such hyperboxes) and then randomly select one individual from this hyperbox; see an illustration in Figure 2. After the selection, one of the above four variations are randomly performed on the selected individual for a better cost or prioritisation. reference point was set to 1.1 times the upper bound of the estimated Pareto front (i.e., r=1.1m) to emphasise the quality balance between convergence and diversity. In addition, since an exact calculation of the HV metric can be computationally expensive in many-objective optimisation, we estimated the HV result by Monte Carlo sampling. Here, 10,000,000 sampling points were used to ensure accuracy [5]. Since the software engineer is typically only interested in test suites that achieve full pairwise coverage, we also introduced a metric to evaluate the ability of each algorithm to return such test suites, called full coverage ratio (FCR), namely, the proportion of solutions with full pairwise coverage in the final population. In addition, it is necessary to note that in computing HV, we only used solutions with full pairwise coverage. That is, we computed HV of only the solutions with full pairwise coverage in the population, considering all objectives except the first one (the pairwise coverage). 4.2 Overview The proposed approach, GrES, was evaluated through experiments that compared it with several alternatives. The experiments compared FCR and HV values and addressed the following five research questions. •Research Question 1 (RQ1): How does GrES perform, in terms of FCR and HV, when compared with current solutions to the problem (the two variants of NSGA-II and PLEDGE)? •Research Question 2 (RQ2): How large are the HV values of the populations returned by the evolution strategy, when compared with the results of alternative representative multiobjective optimisation algorithms using the same approach (first optimise on pairwise coverage)? •Research Question 3 (RQ3): How large are the HV values of the populations returned by GrES when compared with previous approaches if we restrict the set of objectives to those previously considered? •Research Question 4 (RQ4): How large are the differences in the HV values of the populations returned in the experiments used for RQ1-3? •Research Question 5 (RQ5): How long do the different algorithms take? The initial experiments, addressing the first research question (RQ1) compared GrES with two related approaches proposing the use of different instances of NSGA-II, which we call NSGA-IIH [48] and NSGA-IIP [57]. We chose these approaches because we found them easy to reproduce and because they are both closely related to our work (they addressed the problems of test selection [48] and test prioritisation [57] in SPL). We also used PLEDGE (Product Line Editor and Test Generation Tool) [30] in the experiments that addressed the first research question. PLEDGE is an open-source tool for the selection and prioritisation of SPL products maximising the feature interactions covered. The key feature of PLEDGE is that it maximises the dissimilarity among products as a proxy to achieve high coverage, allowing it to scale to large SPLs. More specifically, the tool works in two steps. First, a set of products maximising dissimilarity is selected. Second, the products are ordered (i.e., prioritised) based on dissimilarity, i.e., the most different products are ranked first. In practice, PLEDGE aims to optimise two of the objectives presented in Section 3.6: pairwise coverage (selection) and dissimilarity (prioritisation). PLEDGE receives as inputs a feature model, the number of products to be generated, and the time allowed for generating them. In our experiment, we set the number of products equal to the size of the pairwise suite generated by CASA, used as seed in GrES (between 6 and 61 products). For the execution time limit, we used the median of the execution times of all the other techniques under evaluation for a model (reported in the next sections). Note that, when comparing PLEDGE and GrES, GrES has the advantage that it starts with a seed that provides full pairwise coverage. GrES, however, is required to optimise over nine objectives whereas PLEDGE only has to optimise on two (a multi-objective problem). We then performed additional experiments that addressed the second research question (RQ2) and so compared GrES with alternative multi-objective optimisation algorithms when using the same approach (i.e., by first considering pairwise coverage). The aim of these experiments was to evaluate our novel evolution strategy (i.e., if RQ1 found that GrES outperformed the current techniques, then we wanted to know whether this was entirely due to it first optimising on pairwise coverage). These alternative evolutionary algorithms were NSGA-II [17], IBEA [80], MOEA/D [78], SPEA2+SDE [44], and PAES [39]. The first three are representative approaches of Pareto-based, indicator-based, and decomposition-based genetic algorithms, respectively. The main difference among them lies in the environmental selection operation (i.e., selection for survival), which uses the Pareto dominance, performance indicator, and decomposition (by a set of weight vectors), respectively. SPEA2+SDE is a genetic algorithm designed for many-objective optimisation. Very recently, it has been found to perform in general best out of various state-of-the-art many-objective algorithms in several experimental studies [41,43]. PAES is the most popular evolution strategy which has a (1+1) evolution form. It shares the grid-based environmental selection with our algorithm. In these experiments, all approaches returned populations will 100% FCR and so we only compared the HV values. The parameter settings used in the experiments will be discussed along with implementation details in Section 4.4. In order to address RQ3, we compared the HV values of populations returned by GrES with those produced by previous approaches that only aim to optimise a subset of the objectives. We are not only interested in the relative HV values but also whether the differences are substantial and so we computed effect sizes (RQ4). Finally, we recorded execution times for a range of experiments (RQ5). In the rest of this section, we outline the experimental setup; in the next section, we explain what experiments were performed and give the results of these. 4.3 Experimental Subjects For the evaluation of the approach, we used a set of 20 realistic feature models whose characteristics are depicted in Table 5.Byrealistic, we mean that all the models are related to actual SPLs whose code is publicly available or accessible under request to the respective authors [51,59]. For each model, the number of features, number of CTCs, number of products and application domain are presented. These models have been used as benchmarks to assess related SPL testing techniques [47,48,51,57,59]. Experiments were also performed on three groups of 10 randomly-generated feature models, with 30, 50, and 100 features, respectively. These models were generated using the tool BeTTy [63] with the following parameters: 25% mandatory features; 25% optional features; 25% disjunctive relationships; 25% alternative relationships; maximum branching factor of 12; maximum of 5 subfeatures; and 10% CTC (with respect to the number of features). These values have been found to be common in feature models [66]. All models are valid (i.e., they represent at least one valid product) and have no dead features, i.e., all features are part of at least one valid product. Additional feature models, with 500 features, were also used to address the last research question (regarding scalability). For the calculation of the objective functions, the subject models were extended with four attributes with randomly generated values: cost, number of faults, number of changes, and code size. This is a common approach to evaluate optimisation approaches on attributed feature models Table 5. Realistic Feature Models Feature model Features CTC Products Domain Apache 10 0 256 Web server argo-uml-spl 11 0 192 UML tool BerkeleyDatabase (BDB) 117 282 32 Database BDBFootprint 9 0 256 Database BDBMemory 19 0 3,840 Database BDBPerformance 27 0 1,440 Database Curl 14 0 1,024 Data transfer DesktopSearcher 22 0 462 File search Drupal 48 21 2.09 ·109Web framework fame_dbms_fm 20 0 320 Database gpl 18 13 73 Graph algorithms LinkedList 27 0 1,344 Data structures LLVM 12 0 1,024 Compiler PKJab 12 0 72 Messenger Prevayler 6 0 32 Object persistence SensorNetwork 27 7 16,704 Networking TankWar 37 0 1,741,824 Game Wget 17 0 8,192 File retrieval x264 17 0 2,048 Video encoding ZipMe 8 0 64 Data compression [27, 56, 61]. The cost attribute was assigned real values between 0 and 10. The rest of the attributes were assigned integer values between 0 and 10. Additionally, for each model, we generated a matrix of feature pairs representing integration faults. In particular, for each valid feature pair (calculated using the tool SPLCAT [36]), we randomly simulated either 1 or 2 faults with a probability of 0.03. This probability is based on the percentage of integration faults observed in a recent case study [59]. Exceptionally, the Drupal feature model is provided with real values for the aforementioned attributes (except cost) and integration faults extracted from the Drupal Git repository and the Drupal issue tracking system [59]. In this subject, we used the real values for all the attributes except the cost, for which random values were generated as previously described. 4.4 Implementation Details All the peer algorithms were executed 30 times for each experiment to reduce the impact of their stochastic nature. The termination criterion used in all the algorithms was a predefined number of evaluations, which was set to 10,000. The size of the population for the genetic algorithms except MOEA/D was set to 100. The population size in MOEA/D, which is the same as the number of weight vectors, cannot be specified arbitrarily, so we followed the common practice of using the closest integer to 100 amongst the possible values. The evolution form of PAES was (μ+λ) with μ = λ = 1, and the archive size was set to 100. Some of the algorithms require several parameters to be set. As suggested in their original papers, the neighbourhood size was set to 10% of the population size in MOEA/D and the scaling factor κ to 0.05 in IBEA. The number of grid divisions in PAES and GrES was set to 10. In addition, it is worth noting that the cell-centred calculation in the original PAES makes it unable to work in many-objective optimisation [14]. To address this issue, we modified the implementation of PAES by considering the individual-centred calculation [76], as the same used in GrES. All the algorithms under evaluation searched over valid products only, i.e., all the test cases meet the constraints defined in the feature model. The single point crossover and four mutation operators from [57] (test case swap, test case removal, test case substitution and test case addition) were used to produce offspring in all the genetic algorithms. To mutate a solution, the four operators were randomly selected and the mutation probability was 1/n,wherendenotes the number of the solution’s decision variables (i.e., its suite size). As for crossover probability, 0.8 was used according to the practice in [48]. As a result of using standard values from the literature, we did not require a tuning phase. All algorithms except one were implemented using C++. The one exception, NSGA-IIP, was coded in Java. C++ programs were executed in a notebook computer equipped with an Intel(R) Core(TM)i5-5200 U CP[email protected] GHz and 8 GB of RAM running Window 7 Ultimate. The Java program was executed in a desktop computer equipped with Intel(R) Core(TM)i7-4770 CP[email protected] GHz and 16 GB of RAM, running Windows 10 Education. 5 RESULTS In this section, we outline the experiments carried out to evaluate GrES and the results of these experiments. The experiments used the settings described in the previous section. The HV results in all tables give the mean and standard deviation over 30 independent runs, and the best/better mean for each problem instance is highlighted in boldface. Moreover, in order to have statistically sound conclusions, we adopted the Wilcoxon’s rank sum test at a 0.05 significance level to examine the significance of the difference between the results obtained by GrES and its competitors. Symbol “†” indicates that the difference is statistically significant. 5.1 Research Question 1: Comparison with Existing Approaches The main purpose of this comparison was to verify the proposed optimisation framework in Section 3(i.e., first consider pairwise coverage and then the other objectives). In order to do this, we compared the proposed (GrES) approach with the two previous approaches (NSGA-IIHand NSGAIIP) and the well-established tool (PLEDGE) as a baseline algorithm. As previously explained, we used two metrics: full coverage ratio FCS (the proportion of solutions in the final population that had full pairwise coverage) and the hypervolume (HV) of these solutions. No results are given for NSGA-IIPfor models with 100 features since the computation time was excessive. Note that since on most of the models there is no solution obtained by PLEDGE reaching the full pairwise coverage (consequently, both FCS and HV being zero), for comparing GrES with PLEDGE, we show the objective values of the best solution in terms of pairwise and dissimilarity. Consider first the comparison with NSGA-IIHand NSGA-IIP. The results of the experiments with randomly generated feature models can be found in Tables 6,7,and8. The first observation is that GrES always returned a population in which all test suites provided 100% pairwise coverage. This is in contrast with the other two approaches, which in all cases had a mean FCR of less than 10%. Thus, the GrES approach provides the Software Engineer with more test suites that are suitable (that provide full pairwise coverage). If we consider the HV values, then we can see that the proposed approach is best in the majority of experiments with models that had 30 features and was best in all experiments with larger feature models. The differences were found to be statistically significant. Thus, not only does GrES provide more suitable solutions (test suites), it also provides a relatively diverse set of solutions. As a result, the Software Engineer has more test suites to choose from and also a wider range of trade-offs between objectives. The potential weakness of using randomly generated experimental subjects is that they might not be representative of real examples (feature models). It is therefore promising that similar results Table 6. FCR and HV of NSGA-IIH,NSGA-II Pand GrES on the 10 Random Models with 30 Features Problem NSGA-IIHNSGA-IIPGrES FCR HV FCR HV FCR HV Model30-1 7.03% 1.371E-03(8.7E-04)†1.80% 4.121E-02(1.0E-01)†100% 2.218E-02(3.2E-02) Model30-2 7.27% 5.315E-03(2.1E-02)†2.17% 3.612E-02(6.0E-02)†100% 1.875E-01(7.4E-02) Model30-3 7.13% 2.342E-04(3.5E-04)†1.03% 2.707E-03(1.4E-02)†100% 3.943E-02(1.8E-02) Model30-4 7.07% 1.115E-04(1.9E-04)†2.93% 4.694E-02(1.0E-01)†100% 3.466E-02(1.0E-02) Model30-5 6.80% 7.145E-07(1.4E-06)†1.07% 4.264E-02(2.3E-01)†100% 2.783E-03(2.7E-03) Model30-6 6.70% 4.502E-06(1.7E-05)†1.13% 6.076E-02(2.9E-01)†100% 2.057E-01(4.4E-02) Model30-7 6.13% 3.838E-04(2.1E-03)†1.07% 1.143E-06(6.3E-06)†100% 5.731E-01(2.9E-01) Model30-8 7.10% 2.844E-05(1.6E-04)†1.27% 1.066E-03(5.8E-03)†100% 4.512E-02(5.8E-02) Model30-9 6.30% 4.813E-02(1.6E-03)†1.17% 2.648E-02(1.2E-02)†100% 3.230E-01(1.2E-01) Model30-10 7.70% 0.000E+00(0.0E+00)†1.13% 5.536E-04(2.6E-03)†100% 1.970E-01(8.5E-02) Table 7. FCR and HV of NSGA-IIH,NSGA-II Pand GrES on the 10 Random Models with 50 Features Problem NSGA-IIHNSGA-IIPGrES FCRHVFCRHVFCRHV Model50-1 8.93% 1.467E-03(8.0E-03)†1.03% 2.758E-02(3.9E-02)†100% 2.481E-01(6.7E-02) Model50-2 5.77% 0.000E+00(0.0E+00)†1.03% 0.000E+00(0.0E+00)†100% 5.370E-01(2.2E-01) Model50-3 5.63% 0.000E+00(0.0E+00)†1.07% 1.072E-05(5.6E-05)†100% 2.707E-01(2.1E-01) Model50-4 5.77% 0.000E+00(0.0E+00)†1.07% 8.574E-07(2.7E-06)†100% 9.165E-01(7.6E-02) Model50-5 7.17% 1.055E-04(5.8E-04)†1.03% 2.065E-05(9.4E-05)†100% 5.901E-01(1.9E-01) Model50-6 5.20% 0.000E+00(0.0E+00)†1.10% 6.552E-03(3.6E-02)†100% 1.517E-02(3.0E-03) Model50-7 5.37% 0.000E+00(0.0E+00)†1.00% 0.000E+00(0.0E+00)†100% 4.768E-01(6.9E-02) Model50-8 6.20% 3.676E-02(2.5E-02)†1.03% 3.688E-02(1.6E-02)†100% 5.056E-01(5.1E-02) Model50-9 6.87% 2.144E-07(1.2E-06)†1.03% 6.236E-03(1.5E-02)†100% 4.272E-01(1.6E-01) Model50-10 6.23% 0.000E+00(0.0E+00)†1.07% 1.168E-02(1.7E-02)†100% 4.933E-01(1.3E-01) Table 8. FCR and HV of NSGA-IIHand GrES on the 10 Random Models with 100 Features Problem NSGA-IIHGrES FCR HV FCR HV Model100-1 2.27% 1.572E-06(8.6E-06)†100% 5.076E-01(1.9E-01) Model100-2 2.67% 0.000E+00(0.0E+00)†100% 6.737E-01(1.2E-01) Model100-3 2.80% 5.773E-03(3.2E-02)†100% 9.572E-01(6.8E-02) Model100-4 3.33% 0.000E+00(0.0E+00)†100% 8.153E-01(8.4E-02) Model100-5 4.17% 7.860E-07(4.3E-06)†100% 2.087E-01(8.1E-02) Model100-6 4.07% 0.000E+00(0.0E+00)†100% 2.519E-01(1.8E-01) Model100-7 4.90% 0.000E+00(0.0E+00)†100% 6.107E-01(3.7E-02) Model100-8 1.90% 1.149E-03(1.3E-04)†100% 1.199E+00(1.7E-01) Model100-9 3.60% 3.573E-07(9.9E-07)†100% 8.971E-01(8.2E-02) Model100-10 3.67% 0.000E+00(0.0E+00)†100% 1.802E-01(4.9E-02) Table 9. FCR and HV of NSGA-IIH,NSGA-II P, and GrES on the 19 Realistic Models Problem NSGA-IIHNSGA-IIPGrES FCR HV FCR HV FCR HV Apache 5.53% 0.000E+00(0.0E+00)†1.10% 0.000E+00(0.0E+00)†100% 3.417E-02(7.3E-02) argo-uml-spl 6.00% 4.746E-04(5.9E-04)†2.53% 4.657E-03(1.0E-02)†100% 2.322E-05(7.6E-06) BerkeleyDB 7.83% 1.915E-05(3.4E-05)†5.27% 1.004E-02(3.8E-02)†100% 7.753E-05(7.2E-05) BerkeleyDBFootprint 6.47% 1.273E-04(2.8E-05)†1.77% 1.054E-03(1.6E-03)†100% 9.718E-03(1.1E-02) BerkeleyDBMemory 3.47% 0.000E+00(0.0E+00)†1.03% 1.864E-04(1.0E-03)†100% 1.232E-01(1.0E-01) BerkeleyDBPerformance 6.30% 1.118E-04(4.0E-04)†2.30% 1.608E-02(3.7E-02)†100% 1.522E-01(5.2E-02) Curl 9.40% 0.000E+00(0.0E+00)†3.57% 3.614E-02(1.2E-01)†100% 1.263E-01(4.4E-02) DesktopSearcher 5.87% 7.159E-03(1.5E-02)†3.73% 6.168E-03(7.8E-03)†100% 1.196E-01(6.0E-02) fame-dbms-fm 6.73% 2.144E-07(6.5E-07)†1.27% 1.859E-02(4.6E-02)†100% 4.048E-01(2.9E-02) gpl 7.47% 0.000E+00(0.0E+00)†2.90% 4.254E-02(1.9E-01) 100% 4.269E-04(1.0E-04) LinkedList 6.20% 1.140E-03(3.8E-03)†1.70% 2.732E-03(4.2E-03)†100% 2.950E-02(1.4E-02) LLVM 6.10% 1.225E-04(1.6E-05)†3.60% 1.766E-03(2.7E-03)†100% 1.234E-01(1.6E-01) PKJab 6.57% 5.923E-05(2.5E-04)†4.13% 5.785E-04(4.6E-04)†100% 5.550E-02(1.1E-01) Prevayler 7.60% 5.922E-04(3.2E-03)†0.87% 1.899E-03(8.3E-03)†100% 5.039E-02(5.9E-02) SensorNetwork 6.67% 1.058E-05(5.8E-05)†1.40% 2.843E-03(8.0E-03)†100% 1.009E-01(7.3E-02) TankWar 6.73% 0.000E+00(0.0E+00)†1.00% 1.770E-03(6.7E-03)†100% 3.395E-01(1.6E-01) Wget 7.60% 0.000E+00(0.0E+00)†1.73% 1.663E-03(3.7E-03)†100% 1.968E-02(2.1E-02) x264 5.33% 0.000E+00(0.0E+00)†1.87% 2.237E-02(4.5E-02)†100% 5.057E-02(5.4E-03) ZipMe 6.40% 8.860E-06(3.9E-05)†1.33% 0.000E+00(0.0E+00)†100% 4.124E-02(5.3E-02) Table 10. FCR and HV of NSGA-IIH,NSGA-II PandGrESontheRealModelDrupalFM Problem NSGA-IIHNSGA-IIPGrES FCR HV FCR HV FCR HV DrupalFM 8.93% 5.097E-03(1.6E-03)†1.00% 6.722E-03(8.2E-03)†100% 6.789E-01(2.2E-01) were found for the realistic feature models (Table 9). Specifically, in all cases GrES had an FCR of 100%, while the other approaches always had an FCR of less than 10%. In addition, in 16 of the 19 cases, the HV of GrES was highest and the differences were found to be statistically significant. Overall, it is clear that GrES outperformed the other two approaches in terms of both FCR and HV. Table 10 gives the results for the Drupal feature model with real attribute values, with GrES again being most effective. Regarding the comparison between PLEDGE and GrES, since on most of the models there is no solution returned by PLEDGE having full pairwise coverage (thus both FCS and HV were zero), we do not show the FCS and HV results here. Instead, we show the objective values of the best solution in terms of the pairwise coverage and the dissimilarity which PLEDGE aims to optimise, on the random models and the realistic/real models in Table 11 and Table 12, respectively. For PLEDGE, the best solution is determined first by coverage and then by dissimilarity; for GrES, the best solution is by dissimilarity since all solutions produced have the same coverage. As can be seen in the tables, indeed the pairwise coverage of the solution of PLEDGE on all of the random models is close to but not up to the full value, with some exceptions on realistic models. But we need to note that a seed with full coverage was used in GrES’s search. For the objective dissimilarity, GrES always has a better result; similar patterns can be seen in the other five prioritisation objectives. Table 11. Objective Values of the Best Solution (in Terms of Pairwise Coverage and Dissimilarity) Obtained by PLEDGE and GrES on the 30 Random Models Problem Algorithm PC NF FS NC VCCC CoC D TSC TSS Model30-1 PLEDGE 1226.0 131.3 102.3 87.2 7.2 51.7 23.5 1490.1 16.0 GrES 1230.0 155.3 125.0 106.5 9.0 61.5 28.5 1234.4 12.0 Model30-2 PLEDGE 1031.0 125.1 111.0 131.9 6.6 46.3 20.3 1238.1 15.0 GrES 1033.0 177.2 148.7 175.3 9.8 60.3 27.6 860.5 10.0 Model30-3 PLEDGE 1182.0 121.3 137.5 114.8 8.7 54.4 23.8 1366.4 14.0 GrES 1191.0 139.6 145.7 141.2 10.3 58.5 26.7 1265.4 12.0 Model30-4 PLEDGE 764.0 149.7 146.4 105.3 7.6 54.5 22.1 1164.7 16.0 GrES 767.0 160.8 153.8 118.3 7.4 57.0 24.8 784.4 10.0 Model30-5 PLEDGE 1391.0 138.6 105.0 92.0 8.2 47.1 20.6 870.9 13.0 GrES 1393.0 186.1 140.8 115.0 9.9 59.2 26.7 843.1 12.0 Model30-6 PLEDGE 1180.0 138.6 123.8 108.6 9.2 58.4 25.5 1440.2 14.0 GrES 1184.0 141.6 126.1 113.9 9.9 59.6 26.1 1259.4 12.0 Model30-7 PLEDGE 1223.0 99.9 102.0 97.0 7.0 45.6 19.6 1001.6 17.0 GrES 1232.0 122.8 128.2 115.5 9.5 59.3 25.8 870.4 15.0 Model30-8 PLEDGE 1266.0 115.0 119.8 108.0 10.2 53.8 23.8 1172.7 13.0 GrES 1269.0 139.8 138.8 125.0 12.4 62.3 28.3 1016.6 11.0 Model30-9 PLEDGE 1408.0 116.3 106.3 152.4 11.5 54.4 23.9 1288.3 14.0 GrES 1416.0 139.0 125.0 171.3 12.5 61.3 27.8 1123.2 12.0 Model30-10 PLEDGE 1434.0 101.6 90.1 95.6 7.4 42.8 18.8 1229.4 16.0 GrES 1439.0 156.5 138.5 134.3 10.7 59.8 26.8 1076.8 14.0 Model50-1 PLEDGE 3030.0 238.6 204.5 190.5 13.7 95.2 40.3 2116.4 11.0 GrES 3041.0 284.8 235.0 210.5 16.3 105.0 47.5 1958.6 10.0 Model50-2 PLEDGE 4299.0 208.2 148.3 166.7 12.2 79.6 34.1 2284.6 17.0 GrES 4321.0 292.2 195.1 220.5 15.7 99.3 43.4 2324.9 17.0 Model50-3 PLEDGE 4204.0 174.2 150.3 143.7 10.9 71.9 31.4 2689.0 22.0 GrES 4237.0 255.5 205.4 213.7 15.3 100.6 44.1 2514.1 20.0 Model50-4 PLEDGE 4352.0 169.5 149.7 167.6 12.3 73.7 31.9 2016.9 18.0 GrES 4436.0 226.1 201.1 224.9 13.3 91.3 41.1 2067.5 19.0 Model50-5 PLEDGE 3791.0 129.8 137.2 133.8 9.3 58.9 26.0 2094.7 17.0 GrES 3819.0 206.1 240.3 217.4 15.3 100.3 43.9 2422.4 16.0 Model50-6 PLEDGE 3824.0 145.9 143.3 189.2 12.8 77.6 32.8 2593.7 21.0 GrES 3842.0 203.1 203.7 250.3 18.0 101.3 44.3 2729.1 22.0 Model50-7 PLEDGE 3929.0 211.6 196.4 200.9 12.6 88.2 38.5 2010.1 22.0 GrES 3974.0 211.9 202.7 210.4 16.5 94.0 40.5 1704.0 20.0 Model50-8 PLEDGE 3656.0 186.1 208.7 190.3 15.0 97.0 40.6 2696.4 17.0 GrES 3684.0 204.6 211.1 208.3 14.3 99.1 43.5 2610.1 16.0 Model50-9 PLEDGE 3964.0 171.8 157.9 140.2 11.8 74.1 31.5 1862.2 15.0 GrES 3976.0 256.6 228.2 204.2 15.9 101.2 44.7 1984.3 15.0 Model50-10 PLEDGE 3667.0 129.9 122.0 150.2 8.9 64.8 28.4 1615.0 13.0 GrES 3706.0 219.3 192.6 221.2 14.5 100.9 44.4 1823.5 13.0 Model100-1 PLEDGE 18187.0 548.6 374.5 345.7 27.1 175.2 72.8 11001.3 52.0 GrES 18429.0 632.4 392.8 376.4 28.6 182.0 76.8 9013.2 52.0 (Continued) Table 11. Continued Problem Algorithm PC NF FS NC VCCC CoC D TSC TSS Model100-2 PLEDGE 18211.0 442.5 302.9 226.2 19.9 123.4 52.0 9290.8 41.0 GrES 18298.0 788.4 391.4 367.7 30.7 196.9 82.5 8380.6 39.0 Model100-3 PLEDGE 15483.0 356.4 214.6 225.7 17.4 102.0 44.3 9564.6 42.0 GrES 15626.0 747.3 416.2 444.8 32.2 200.0 86.0 7891.1 36.0 Model100-4 PLEDGE 18114.0 772.7 364.0 395.7 26.1 191.0 81.2 8158.5 33.0 GrES 18256.0 734.3 445.5 420.7 26.8 196.7 86.4 7532.8 31.0 Model100-5 PLEDGE 17516.0 529.3 312.3 314.6 21.6 153.1 65.9 6920.4 28.0 GrES 17559.0 717.2 419.7 400.3 27.5 193.2 82.6 6173.4 28.0 Model100-6 PLEDGE 16323.0 391.0 223.8 228.2 18.2 106.4 46.2 7499.7 31.0 GrES 16433.0 718.6 406.1 430.4 31.4 198.3 84.9 8355.8 29.0 Model100-7 PLEDGE 18090.0 530.2 371.2 316.2 22.9 160.9 66.9 5823.5 22.0 GrES 18204.0 737.0 441.3 375.6 26.2 195.4 84.5 6596.2 24.0 Model100-8 PLEDGE 17511.0 429.1 289.7 263.2 22.1 134.7 54.9 10982.6 63.0 GrES 17694.0 552.8 365.9 343.8 23.8 166.2 69.0 9578.4 58.0 Model100-9 PLEDGE 17474.0 401.6 243.0 228.1 16.1 108.9 47.7 7698.0 35.0 GrES 17560.0 733.3 416.1 396.4 27.8 194.2 82.7 8760.8 38.0 Model100-10 PLEDGE 17836.0 544.6 321.0 305.8 26.9 159.5 66.4 6821.9 31.0 GrES 18041.0 712.2 391.1 375.7 30.3 186.7 80.9 7329.1 33.0 For PLEDGE, the best solution is determined first by coverage and then by dissimilarity; for GrES, the best solution is by dissimilarity as all solutions have the same coverage. A better value is highlighted in boldface. PC: Pairwise coverage, NF: Number of faults, FS: Feature size, NC: Number of changes, VCCC: Variability coverage and cyclomatic complexity, CoC: Coefficient of connectivity-density, D: Dissimilarity, TSC: Test suite cost, TSS: Test suite size. One interesting exception is on the model BerkeleyDB where the two algorithms have the same values on all the prioritisation objectives. As for the two cost objectives, the solution of PLEDGE does perform better on some models, 12 and 5, respectively, on the test suite cost and test suite size out of all the 50 test models. Nevertheless, it is worth mentioning that even for the models where the solution of PLEDGE in the tables is better in terms of the costs, there may exist other solutions obtained by GrES that were better than PLEDGE’s solution for all nine objectives (they were not shown in the tables since they are not the best on dissimilarity). 5.2 Research Question 2: Comparison with Representative Multi-Objective Evolutionary Approaches The results in the previous subsection did not specifically evaluate the evolution strategy used in GrES. As a result, we also carried out experiments that compared two evolution strategies (GrES and PAES [39]) with four representative genetic algorithms (NSGA-II [17], IBEA [80], MOEA/D [78], and SPEA2+SDE [44]). In order to focus the evaluation on the use of an evolution strategy, all techniques used our optimisation framework in which one first compares solutions based on pairwise coverage and only then, if they have the same pairwise coverage, use the other objectives. The optimisation framework led to an FCR of 100% in all cases and so we only report the HV values. Tables 13,14,and15 give the results with randomly generated models. In all cases, the best technique was one of those that used an evolution strategy (PAES or GrES) and the difference between the best of PAES/GrES and the other multi-objective optimisation algorithms was statistically significant. Interestingly, GrES tended to produce higher HV values than PAES: this was the Table 12. Objective Values of the Best Solution (in Terms of Pairwise Coverage and Dissimilarity) Obtained by PLEDGE and GrES on the 20 Realistic and Real Models Problem Algorithms PC NF FS NC VCCC CoC D TSC TSS Apache PLEDGE 145.0 51.3 32.0 40.5 1.0 16.0 8.0 177.6 8.0 GrES 145.0 61.0 40.0 53.0 1.0 18.0 10.0 133.2 6.0 argo-uml-spl PLEDGE 161.0 39.0 46.0 52.5 3.0 18.5 9.5 379.9 8.0 GrES 162.0 48.0 53.0 60.0 3.0 20.0 11.0 339.5 7.0 BerkeleyDB PLEDGE 14138.0 722.0 539.0 554.0 568.0 778.0 111.0 2900.1 8.0 GrES 14138.0 722.0 539.0 554.0 568.0 778.0 111.0 2169.9 6.0 BerkeleyDBFootprint PLEDGE 128.0 33.3 31.0 42.0 1.0 13.8 6.8 167.1 8.0 GrES 128.0 38.0 41.0 58.0 1.0 16.0 9.0 125.3 6.0 BerkeleyDBMemory PLEDGE 618.0 71.5 45.9 58.5 3.0 28.9 11.9 1216.0 32.0 GrES 623.0 82.2 59.0 71.7 3.0 31.4 14.4 1144.3 30.0 BerkeleyDBPerformance PLEDGE 903.0 121.0 117.0 96.3 8.0 40.5 20.0 834.7 11.0 GrES 908.0 148.2 142.7 126.3 10.0 49.8 24.8 851.7 10.0 Curl PLEDGE 288.0 58.6 62.6 45.3 1.5 21.1 10.6 478.0 10.0 GrES 292.0 70.7 80.3 56.5 2.0 24.8 12.8 438.6 9.0 DesktopSearcher PLEDGE 573.0 62.2 74.3 64.8 6.0 29.5 14.5 733.3 11.0 GrES 574.0 96.8 113.5 89.2 8.0 39.8 19.8 517.6 7.0 fame-dbms-fm PLEDGE 544.0 88.3 83.7 72.6 6.5 32.3 15.3 841.6 12.0 GrES 554.0 90.4 81.4 77.0 6.5 32.8 15.8 697.7 10.0 gpl PLEDGE 411.0 86.9 84.8 83.5 22.5 50.3 15.1 900.6 14.0 GrES 411.0 89.5 86.0 84.7 23.2 51.3 15.3 642.9 10.0 LinkedList PLEDGE 780.0 94.5 144.3 114.1 9.0 48.2 23.2 1015.5 14.0 GrES 793.0 107.8 161.3 123.3 9.0 49.6 24.6 900.2 12.0 LLVM PLEDGE 219.0 49.8 61.2 52.5 1.0 19.8 9.8 276.6 8.0 GrES 220.0 59.0 71.0 65.0 1.0 22.0 12.0 274.8 7.0 PKJab PLEDGE 177.0 55.9 51.0 59.0 3.0 21.0 11.0 380.1 9.0 GrES 177.0 64.0 53.0 66.0 3.0 22.0 12.0 255.0 6.0 Prevayler PLEDGE 50.0 34.5 35.0 26.0 1.0 9.5 5.5 175.4 10.0 GrES 50.0 39.0 35.0 30.0 1.0 10.0 6.0 100.0 6.0 SensorNetwork PLEDGE 1211.0 83.4 88.3 86.7 13.1 44.8 17.7 1142.3 14.0 GrES 1213.0 135.0 126.5 134.5 21.5 65.0 26.0 854.2 11.0 TankWar PLEDGE 2150.0 176.6 152.8 131.2 10.0 60.6 28.1 2089.1 16.0 GrES 2157.0 200.6 180.7 162.0 11.0 67.8 32.8 1953.2 15.0 Wget PLEDGE 473.0 58.2 57.0 69.8 2.0 28.3 13.3 645.4 14.0 GrES 475.0 70.5 70.5 88.0 2.0 30.8 15.8 576.4 13.0 x264 PLEDGE 465.0 67.8 69.4 56.3 3.0 28.0 13.0 763.7 19.0 GrES 469.0 77.8 76.5 63.7 3.0 29.7 14.7 572.8 16.0 ZipMe PLEDGE 85.0 34.5 39.5 42.5 1.0 13.5 7.5 256.3 9.0 GrES 85.0 39.0 41.0 45.0 1.0 14.0 8.0 152.9 6.0 DrupalFM PLEDGE 3726.0 2545.3 254567.3 348.3 34.4 105.8 33.8 1652.6 13.0 GrES 3748.0 3326.5 325334.0 450.0 50.1 135.0 45.0 1693.8 13.0 For PLEDGE, the best solution is determined first by coverage and then by dissimilarity; for GrES, the best solution is by dissimilarity as all solutions have the same coverage. A better value is highlighted in boldface. PC: Pairwise coverage, NF: Number of faults, FS: Feature size, NC: Number of changes, VCCC: Variability coverage and cyclomatic complexity, CoC: Coefficient of connectivity-density, D: Dissimilarity, TSC: Test suite cost, TSS: Test suite size. Table 13. HV of the Six Algorithms on the 10 Random Models with 30 Features Problem NSGA-II IBEA MOEAD SPEA2+SDE PAES GrES Model30-1 9.182E-03(1.9E-03)†9.157E-03(1.9E-03)†6.208E-03(2.9E-03)†8.888E-03(1.7E-03)†1.625E-02(2.4E-02) 2.218E-02(3.2E-02) Model30-2 1.119E-01(6.4E-02)†1.194E-01(8.7E-02)†8.149E-02(1.0E-01)†1.531E-01(1.1E-01)†2.495E-01(7.7E-02)†1.875E-01(7.4E-02) Model30-3 5.385E-03(2.5E-03)†5.367E-03(1.7E-03)†4.209E-03(7.8E-03)†5.832E-03(3.1E-03)†2.695E-02(2.6E-02)†3.943E-02(1.8E-02) Model30-4 1.157E-02(4.8E-03)†1.241E-02(5.8E-03)†6.370E-03(4.7E-03)†1.346E-02(6.1E-03)†3.140E-02(1.3E-02) 3.466E-02(1.0E-02) Model30-5 1.419E-04(2.8E-04)†1.246E-04(3.5E-04)†8.739E-05(2.7E-04)†9.410E-05(1.9E-04)†2.466E-03(3.7E-03) 2.783E-03(2.7E-03) Model30-6 9.242E-02(3.0E-02)†1.091E-01(3.1E-02)†5.308E-02(4.3E-02)†1.042E-01(2.7E-02)†1.486E-01(4.6E-02)†2.057E-01(4.4E-02) Model30-7 4.776E-02(1.4E-01)†7.170E-02(1.3E-01)†3.716E-02(1.3E-01)†3.126E-02(3.4E-02)†5.487E-01(2.2E-01) 5.731E-01(2.9E-01) Model30-8 9.289E-03(4.2E-02)†2.046E-03(8.2E-03)†1.228E-04(5.6E-04)†1.075E-03(2.7E-03)†7.343E-02(9.6E-02) 4.512E-02(5.8E-02) Model30-9 1.396E-01(1.0E-01)†1.016E-01(4.0E-02)†7.748E-02(6.8E-02)†1.007E-01(3.0E-02)†2.788E-01(1.4E-01) 3.230E-01(1.2E-01) Model30-10 8.608E-02(4.4E-02)†7.205E-02(2.6E-02)†4.341E-02(2.6E-02)†7.215E-02(2.6E-02)†2.214E-01(1.7E-01) 1.970E-01(8.5E-02) Table 14. HV of the Six Algorithms on the 10 Random Models with 50 Features Problem NSGA-II IBEA MOEAD SPEA2+SDE PAES GrES Model50-1 1.230E-01(9.1E-03)†1.368E-01(3.9E-02)†1.005E-01(5.1E-02)†1.289E-01(2.6E-02)†2.073E-01(6.9E-02)†2.481E-01(6.7E-02) Model50-2 1.301E-01(1.1E-01)†7.882E-02(9.0E-02)†3.174E-02(6.0E-02)†1.174E-01(8.1E-02)†4.278E-01(1.8E-01) 5.370E-01(2.2E-01) Model50-3 2.518E-03(2.8E-03)†9.719E-03(2.0E-02)†1.474E-03(2.6E-03)†9.195E-03(2.2E-02)†2.179E-01(2.2E-01) 2.707E-01(2.1E-01) Model50-4 3.137E-01(3.1E-01)†2.560E-01(2.7E-01)†4.128E-02(1.1E-01)†2.266E-01(3.0E-01)†8.540E-01(9.1E-02)†9.165E-01(7.6E-02) Model50-5 1.232E-01(1.1E-01)†1.213E-01(9.4E-02)†3.926E-02(3.4E-02)†9.377E-02(4.5E-02)†4.337E-01(1.3E-01)†5.901E-01(1.9E-01) Model50-6 4.675E-03(3.0E-03)†4.645E-03(3.4E-03)†1.066E-03(1.9E-03)†5.180E-03(2.9E-03)†9.887E-03(7.2E-03)†1.517E-02(3.0E-03) Model50-7 6.250E-02(1.1E-01)†4.729E-02(1.0E-01)†2.674E-02(6.2E-02)†8.568E-02(1.2E-01)†4.162E-01(1.2E-01) 4.768E-01(6.9E-02) Model50-8 2.991E-01(6.1E-02)†3.032E-01(4.5E-02)†1.188E-01(9.6E-02)†2.979E-01(5.4E-02)†4.933E-01(5.4E-02) 5.056E-01(5.1E-02) Model50-9 5.407E-02(4.6E-02)†6.949E-02(5.5E-02)†1.194E-02(1.9E-02)†4.831E-02(2.3E-02)†3.751E-01(2.0E-01) 4.272E-01(1.6E-01) Model50-10 1.428E-01(6.8E-02)†1.476E-01(7.1E-02)†8.360E-02(9.0E-02)†1.243E-01(4.5E-02)†5.059E-01(2.1E-01) 4.933E-01(1.3E-01) Table 15. HV of the Six Algorithms on the 10 Random Models with 100 Features Problem NSGA-II IBEA MOEAD SPEA2+SDE PAES GrES Model100-1 7.177E-03(2.5E-02)†7.520E-03(3.0E-02)†5.778E-04(3.1E-03)†8.135E-03(2.9E-02)†2.863E-01(1.9E-01)†5.076E-01(1.9E-01) Model100-2 1.751E-01(2.0E-01)†1.520E-01(2.2E-01)†1.144E-02(6.3E-02)†1.996E-01(2.0E-01)†4.371E-01(1.7E-01)†6.737E-01(1.2E-01) Model100-3 1.191E-01(1.8E-01)†3.893E-02(1.2E-01)†2.133E-02(6.8E-02)†1.476E-01(2.1E-01)†7.914E-01(2.4E-01)†9.572E-01(6.8E-02) Model100-4 5.556E-02(1.5E-01)†5.323E-02(1.5E-01)†2.074E-02(7.9E-02)†5.252E-02(1.5E-01)†6.694E-01(1.4E-01)†8.153E-01(8.4E-02) Model100-5 2.778E-02(4.7E-02)†2.267E-02(4.7E-02)†2.156E-03(1.1E-02)†1.768E-02(4.0E-02)†1.750E-01(7.2E-02)†2.087E-01(8.1E-02) Model100-6 4.589E-03(1.1E-02)†9.446E-03(2.0E-02)†3.542E-04(1.1E-03)†5.354E-03(1.3E-02)†2.923E-01(2.8E-01) 2.519E-01(1.8E-01) Model100-7 3.152E-02(7.8E-02)†6.004E-02(1.1E-01)†6.416E-03(2.1E-02)†6.840E-02(1.0E-01)†5.659E-01(6.3E-02)†6.107E-01(3.7E-02) Model100-8 3.391E-02(7.1E-02)†6.581E-02(9.9E-02)†5.686E-02(1.2E-01)†4.771E-02(7.6E-02)†8.018E-01(3.0E-01)†1.199E+00(1.7E-01) Model100-9 1.666E-01(1.9E-01)†1.804E-01(1.9E-01)†3.355E-02(9.2E-02)†9.929E-02(1.7E-01)†6.690E-01(1.7E-01)†8.971E-01(8.2E-02) Model100-10 3.663E-04(1.1E-03)†3.752E-03(1.6E-02)†4.087E-05(2.2E-04)†4.930E-05(2.4E-04)†1.640E-01(6.8E-02) 1.802E-01(4.9E-02) case in 7 out of 10 experiments with 30 features and 9 out of 10 cases in each of the 2 other experiments (with 50 and 100 features). Interestingly, although GrES had higher HV values in the same number of experiments with models with 50 and 100 features, only four of these differences were statistically significant for models with 50 features, while all of the differences were statistically significant for models with 100 features. optimising on all of the objectives but then the comparison was only on the objectives used by the other approaches; this clearly disadvantages GrES. 5.4 Research Question 4: How Large Are the Differences in HV Values in the Experiments Used for RQ1-3? To further investigate the differences between the HV values of the populations returned by different algorithms, the Vargha and Delaney’s  A12 statistic [69] was used to evaluate the effect size, i.e., determine which technique led to higher HV values and to what extent. The  A12 statistic generalises the notion of effect size estimator to data that does not follow a normal distribution, such as those generated by the techniques evaluated in the experiments. Specifically, the  A12 statistic shownineachcellofTable28 relates to how often on average GrES provides higher HV values than the technique in the column for the model in the row. The value of the  A12 statistic ranges from 0.0 to 1.0, and when the value is exactly 0.5, it means that either the technique provided exactly the same results as GrES on all runs, or that GrES provided higher HV values for exactly 50% of the runs. If the value of the  A12 statistic is lower than 0.5, the technique provided higher HV values than GrES for a majority of runs. Conversely, if the value is higher than 0.5, GrES provided higher HV values for a majority of runs. Vargha and Delaney [69] suggested the use of thresholds for interpreting the effect size: values around 0.5 (0.43 – 0.57) means a negligible difference; values over 0.57 indicates a small (0.57 – 0.64), medium (0.65 – 0.71), or large (0.72 – 1) difference in favour of GrES; values below 0.43 indicate a small (0.43 – 0.36), medium (0.36 – 0.29), or large (0.29 – 0.0) difference in favour of the algorithm specified in the column of the table. Cells indicating medium, large, and very large differences are shaded in light grey, grey, and dark grey, respectively. The 9-objectives HV values confirm the superiority of GrES for 9 objectives, showing large differences in its favour in 285 out of 340 pairwise comparisons. Furthermore, there is not a single cell showing large nor even medium differences against GrES for the peers except PAES. Comparing GrES with PAES, large, medium, and small differences in favour of GrES vs PAES are 13 vs 1, 5 vs 2, and 13 vs 2, respectively. The  A12 results for the HV computed using 6 and 2 objectives are also shown in the last columns of Table 28. Specifically, the second to last column shows the  A12 comparison with the NSGA-IIP algorithm for the HV of the six objectives used in [57]. The results show the superiority of GrES also in this case, with large differences in its favour for 31 out of 40 models, and with negligible  differences in 4 out of the 9 remaining comparisons. The last column shows the A12 comparison with the NSGA-IIH algorithm for the HV of the two objectives used in [48] (the NSGA-IIH algorithm was re-executed using only those two objectives). The results show that the HV values are quite similar for the 2-objectives case, showing negligible differences in 43 out of the 50 models, with large differences in favour of GrES in 3 large models (100 features), and large differences in favour of NSGA-IIH in 2 small models (30 features). 5.5 Research Question 5: How Long Do the Different Algorithms Take? Execution time information is given in Table 29 and Figure 4. Specifically, Table 29 provides the average execution time in seconds per model (in rows) and algorithm (in columns). Figure 4 shows a scatterplot of the average execution time (Y axis measured in seconds) per model size (X axis measured in features). Thus, the values in the horizontal axis of Figure 4 range from a minimum of 6 features for Prevlayer to a maximum of 117 features for BerkeleyDatabase. Each point in the figure represents the run of an algorithm (represented using a specific shade of grey and line dash) for a number Table 28.  A12 Values Comparing the Hyper-Volumes of the Fronts Generated by GrES with Those Generated by the Other Algorithms Problem 9ObjectivesHV 6Obj.HV 2Obj.HV NSGAIIHIBEA MOEAD NSGAII PAES NSGAIIPSPEA2+SDE NSGAIIPNSGAIIH 30Feat-10CTC1 1.00 .895 .979 .872 .632 .727 .902 .300 .550 30Feat-10CTC2 .997 .776 .876 .842 .273 .936 .710 .317 .026 30Feat-10CTC3 1.00 1.00 .978 1.00 .751 .967 1.00 .483 .250 30Feat-10CTC4 1.00 .991 1.00 .998 .631 .752 .981 .350 .452 30Feat-10CTC5 1.00 .973 .986 .978 .619 .933 .991 .467 .500 30Feat-10CTC6 1.00 .997 1.00 .990 .828 .967 1.00 .933 .500 30Feat-10CTC7 1.00 .961 .977 .973 .501 1.00 .998 1.00 .500 30Feat-10CTC8 1.00 .968 .998 .943 .434 .983 .978 .967 .350 30Feat-10CTC9 1.00 .983 .979 .909 .612 1.00 .993 .948 .500 30Feat-10CTC10 1.00 .958 .984 .912 .527 1.00 .958 1.00 .484 50Feat-10CTC1 1.00 .953 .984 .993 .670 1.00 .980 .967 .500 50Feat-10CTC2 1.00 .999 1.00 .973 .647 1.00 1.00 1.00 .500 50Feat-10CTC3 1.00 .992 1.00 1.00 .607 1.00 .990 1.00 .617 50Feat-10CTC4 1.00 1.00 1.00 1.00 .693 1.00 1.00 1.00 .500 50Feat-10CTC5 1.00 .987 1.00 .989 .733 1.00 1.00 1.00 .500 50Feat-10CTC6 1.00 .999 1.00 .990 .819 .967 .998 .483 .500 50Feat-10CTC7 1.00 1.00 1.00 1.00 .637 1.00 1.00 1.00 .500 50Feat-10CTC8 1.00 1.00 1.00 .996 .543 1.00 .999 1.00 .500 50Feat-10CTC9 1.00 .989 1.00 .992 .591 1.00 1.00 1.00 .500 50Feat-10CTC10 1.00 .991 .986 .992 .499 1.00 .998 1.00 .500 100Feat-10CTC1 1.00 .999 1.00 .999 .808 - .999 - .871 100Feat-10CTC2 1.00 .972 .999 .982 .911 - .979 - .517 100Feat-10CTC3 1.00 1.00 1.00 1.00 .756 - 1.00 -.952 100Feat-10CTC4 1.00 .999 1.00 .997 .808 - 1.00 - .500 100Feat-10CTC5 1.00 .994 1.00 .993 .684 - .997 - .500 100Feat-10CTC6 1.00 1.00 1.00 1.00 .528 - 1.00 - .500 100Feat-10CTC7 1.00 1.00 1.00 1.00 .740 - 1.00 - .500 100Feat-10CTC8 1.00 1.00 1.00 1.00 .897 - 1.00 -.983 100Feat-10CTC9 1.00 1.00 1.00 1.00 .899 - 1.00 - .517 100Fea-10CTC10 1.00 .998 1.00 1.00 .597 - 1.00 - .500 Apache .733 .733 .733 .733 .446 .733 .733 1.00 .500 argo-uml-spl .000 .514 .519 .514 .513 .662 .514 .803 .500 BerkeleyDB .848 .545 .476 .525 .466 .681 .474 .000 .500 BerkeleyDBFp 1.00 .776 .832 .761 .341 .992 .821 .950 .500 BerkeleyDBMem 1.00 1.00 1.00 .996 .312 1.00 1.00 1.00 .500 BerkeleyDBPerf 1.00 .958 .990 .994 .579 .964 .972 .530 .483 Curl 1.00 .951 .970 .942 .610 .933 .943 .230 .500 DesktopSearcher 1.00 .974 .986 .979 .490 1.00 .950 .217 .499 fame_dbms_fm 1.00 1.00 1.00 1.00 .830 1.00 1.00 .967 .500 gpl 1.00 .982 .993 .978 .543 .440 .982 .183 .517 LinkedList .999 .928 .941 .871 .562 1.00 .971 .417 .517 LLVM 1.00 .966 .980 .992 .572 1.00 .990 .950 .500 PKJab .996 .887 .873 .908 .424 .951 .882 .850 .450 Prevayler .986 .453 .774 .442 .485 .972 .454 .850 .500 SensorNetwork 1.00 .946 .993 .941 .508 1.00 .953 .922 .466 TankWar 1.00 .983 1.00 1.00 .814 1.00 .993 1.00 .450 Wget 1.00 .992 .923 .946 .414 .937 .924 .644 .550 x264 1.00 1.00 1.00 .998 .674 .816 1.00 .800 .517 ZipMe 1.00 .712 .758 .696 .569 1.00 .667 1.00 .500 DrupalFM 1.00 .992 .988 .973 .510 1.00 .998 1.00 .500 Table 29. Average Execution Times of the Algorithms per Model Using Nine Objectives (in Seconds) Problem Algorithms GrES NSGA-IIHIBEA MOEAD NSGA-II PAES NSGA-IIPSPEA2+SDE 30Feat-10CTC1 7.76 10.55 24.52 8.27 8.05 9.50 124.27 11.10 30Feat-10CTC2 6.08 6.78 23.22 6.60 6.85 6.82 88.41 9.41 30Feat-10CTC3 7.54 9.26 24.23 7.49 7.58 8.92 105.90 10.77 30Feat-10CTC4 4.57 5.06 26.51 4.89 5.18 5.19 58.34 14.61 30Feat-10CTC5 8.31 10.38 23.80 7.99 8.01 9.63 206.14 14.07 30Feat-10CTC6 8.00 9.50 24.40 7.68 7.63 9.54 203.61 10.39 30Feat-10CTC7 9.89 11.95 26.64 9.81 9.69 11.54 167.77 12.10 30Feat-10CTC8 7.27 9.02 25.87 7.54 7.38 8.86 432.87 9.61 30Feat-10CTC9 8.28 10.22 25.46 8.24 8.15 9.89 161.55 11.06 30Feat-10CTC10 9.80 12.16 27.26 9.74 9.56 11.19 188.15 12.00 50Feat-10CTC1 14.83 19.83 30.08 13.38 13.50 17.87 590.89 16.39 50Feat-10CTC2 32.48 40.49 47.37 30.74 30.78 38.13 1918.98 32.84 50Feat-10CTC3 40.11 52.44 55.03 39.14 39.26 45.24 2171.35 41.43 50Feat-10CTC4 33.00 42.71 47.11 31.93 31.89 36.83 1850.81 33.91 50Feat-10CTC5 25.15 32.72 42.54 24.72 24.58 27.81 1315.45 26.40 50Feat-10CTC6 35.41 44.67 47.91 34.08 34.21 39.16 1614.20 36.66 50Feat-10CTC7 36.25 47.24 51.62 35.73 35.67 38.50 1781.94 38.15 50Feat-10CTC8 27.47 35.22 41.63 26.01 26.07 30.03 1269.60 28.12 50Feat-10CTC9 25.46 33.50 41.61 24.27 24.43 28.31 1322.43 26.65 50Feat-10CTC10 20.60 25.76 35.95 18.73 19.27 23.64 985.06 21.23 100Feat-10CTC1 382.07 474.57 399.82 387.02 399.81 420.55 - 392.96 100Feat-10CTC2 308.98 371.09 319.09 305.58 306.55 331.85 - 308.45 100Feat-10CTC3 253.20 315.33 267.57 254.31 253.82 263.03 - 254.82 100Feat-10CTC4 253.92 332.44 261.86 245.46 248.16 273.64 - 249.62 100Feat-10CTC5 208.64 278.37 213.10 199.27 202.36 220.61 - 204.19 100Feat-10CTC6 207.90 260.39 217.88 202.09 202.13 222.91 - 201.49 100Feat-10CTC7 167.58 215.10 177.24 161.59 162.89 176.21 - 164.30 100Feat-10CTC8 450.22 528.68 481.20 461.59 451.61 475.61 - 454.84 100Feat-10CTC9 258.81 333.72 269.24 250.77 250.41 279.87 - 253.23 100Fea-10CTC10 236.02 297.37 244.35 227.10 234.61 247.14 - 231.39 Apache 0.98 1.14 16.99 0.68 0.86 1.14 1.86 4.71 argo-uml-spl 1.07 1.27 17.23 0.74 0.95 1.15 3.80 4.65 BerkeleyDB 34.52 52.33 43.20 33.62 34.10 33.97 22945.38 38.97 BerkeleyDBFp 0.88 0.74 18.62 0.59 0.76 0.83 1.78 3.67 BerkeleyDBMem 10.26 11.74 23.98 9.76 10.09 10.03 62.35 13.23 BerkeleyDBPerf 4.90 5.91 22.05 4.32 4.65 5.59 70.06 6.85 Curl 1.79 1.99 18.55 1.46 1.67 2.00 9.58 4.44 DesktopSearcher 3.20 3.55 21.08 2.88 3.18 3.40 28.45 5.84 fame_dbms_fm 3.72 4.15 19.94 3.15 3.41 4.44 30.15 5.77 gpl 2.69 2.82 17.44 2.61 2.85 2.89 16.97 5.93 LinkedList 5.53 6.35 21.03 5.11 5.42 5.84 53.56 8.14 LLVM 1.34 1.18 19.22 0.90 1.14 1.36 4.22 3.60 PKJab 1.12 1.00 14.68 0.85 1.05 1.03 3.88 4.80 Prevayler 0.43 0.41 12.12 0.35 0.52 0.47 0.60 4.00 SensorNetwork 7.15 8.73 19.69 6.99 7.15 7.39 108.84 10.97 TankWar 16.41 20.51 29.99 14.64 15.26 16.76 400.78 17.88 Wget 3.43 4.37 17.15 3.16 3.44 3.92 23.37 6.31 x264 4.49 5.32 17.22 4.14 4.48 4.74 27.00 7.98 ZipMe 0.67 0.56 14.68 0.48 0.65 0.63 1.05 3.84 DrupalFM 29.84 29.34 46.81 25.85 27.47 31.10 2261.00 29.29 Fig. 4. Average execution times (in seconds) per algorithm and model size (logarithmic scale) using nine objectives. of constraints, and types of CTCs, points tend to cluster in columns. In order to aid the visualisation of the execution time, an interpolation curve4per algorithm has been added to Figure 4. From this we can see that GrES is consistently slightly faster than NSGA-IIHand always much faster than NSGA-IIP. The other algorithms, that all first optimise on pairwise coverage, have similar execution time. In particular, this execution time appears to converge as the feature model size increases. Figure 4clearly shows that NSGA-IIPis slowest for models with more than 16 features, followed by IBEA. One of the possible causes for such relatively high execution time could be the JAVA implementation of NSGA-IIP, while the other algorithms are implemented in C++.Moreover,IBEA was slowest for models with fewer than 16 features. For larger models, the remaining algorithms provide similar results with GrES providing the shortest time in many cases. In order to delve deeper on the scalability of GrES, we executed an additional experiment using 5 different features models with 500 features and a 10% of CTC. The execution times of GrES for such big models were significantly longer, with a minimum of 6.9 and a maximum of 13.5 hours, having an average execution time of 9 hours. The main factor for such differences in models with the same size is the shape and structure of constraints of the specific feature models, with a small variability of execution time for the executions on the same feature model. Figure 5depicts the scalability of GrES for all the models with model size (in number of features) in the horizontal 4The curve was computed using a generalized additive model which was estimated by a quadratically penalised likelihood approach [74]. Fig. 5. Execution times (in seconds, using logarithmic scale in the vertical axis) of each GrES execution per model size using nine objectives. axis, and execution time (measured in seconds) in the vertical axis using a logarithmic scale. Each point represents a run of the algorithm, and the specific shade of grey is used to represent the type of model used (real, realistic, or randomly generated). All the executions were performed without problems for such large models obtaining results in less than 14 hours. 5.6 Discussion In this section, we review what the results of the experiments tell us about the research questions. First consider Research Question 1, which concerns how the performance (i.e., FCS and HV) of GrES compares with two related techniques (NSGA-IIH and NSGA-IIP ). Encouragingly, GrES always returned a population in which all solutions had full pairwise-coverage. Thus, the proposed approach provided the Software Engineer with many alternative solutions representing different trade-offs between objectives. In contrast, N SGA-IIH and N SGA-IIP always returned an FCS (the proportion of solutions in the final population that had full pairwise coverage) of below 10%. In addition, GrES also outperformed both of the previously reported approaches when we consider the HV values. With the randomly generated models, this difference appears to increase as the model size increases. Similar results were obtained with the realistic models including the feature model (Drupal) for which we had real attribute values. Finally, PLEDGE typically did not produce test suites with full pairwise coverage and in most cases GrES produced better values for the objective functions. The second research question concerned the effectiveness (i.e., higher prioritisation values and lower costs) of the proposed evolution strategy. Again the results were promising: when we used our approach to comparing individuals, we found that the two evolution strategies used (GrES and PAES) produced populations with higher HV values than the four multi-objective optimisation algorithms considered (all had 100% FCR). This confirms our decision to use an evolution strategy. Similar to the first set of experiments, the improvement seems to be greater for larger models. In addition, GrES led to higher HV values than PAES for the majority of the models, particularly on larger models. This verifies the effectiveness of the problem-based selection operation in GrES which can produce more promising offspring on complex problems. We noted that previous work had used fewer objective functions and the third research question concerned how GrES performed, in terms of HV values, when compared with the previous algorithms using the (smaller number of) objective functions reported in the corresponding papers. Note that the previously reported approaches optimised on these smaller sets of objective functions but we compared them (on these objective functions) with results returned using GrES optimising on all of the objective functions. Unsurprisingly, the results of these experiments were more mixed. In these experiments, GrES typically led to lower HV values than NSGA-IIHand NSGA-IIPwhen we used the smaller models (with 30 features). However, GrES tended to return populations with higher HV values than NSGA-IIHand NSGA-IIPwith larger models. Encouragingly, many of the differences in favour of GrES had large effect-size. In addition, in those cases where another technique returned higher HV values than GrES, the effect size was small. The following are the key outcomes of the experiments. (1) PLEDGE finds solutions with relatively high pairwise coverage but in almost all cases this coverage was not 100%. It may thus be unsuitable in cases where full pairwise coverage is required. (2) The variants of NSGA-II were found to perform well, in terms of FCR and HV, for problems with 2 objectives and small feature models (i.e., around 30 features). (3) The variants of NSGA-II also performed well, in terms of FCR and HV, for problems with up to 6 objectives and small feature models (approximately 30 features) where execution time is not an issue. (4) GrES was found to be the most effective, in terms of FCR and HV, for problems with more than 2 objectives, and medium or large feature models (more than 30 features) and time constraints. It was much more effective than the variants of NSGA-II and PLEDGE, in terms of FCR. (5) Both GrES and PAES were effective in finding solutions with complete pairwise coverage. However, for larger models GrES tended to produce higher HV values (in 9 out of 10 experiments, with the differences being statistically significant) and so a more diverse set of solutions. Overall, the results were very promising. In the experiments, GrES outperformed the previously published techniques in terms of both FCR and HV. It also tended to lead to higher HV values than the other multi-objective optimisation algorithms. It is worth noting that while PAES was also highly effective when we used our novel strategy (first optimise on pairwise coverage), the original PAES does not scale well to problems with many objectives.5In our experiments, we adapted PAES (by using the individual-centred calculation) to make it workable in many-objective optimisation. Even so, it was still slightly slower than GrES. The proposed approach provides Software Engineers with a wide range of objective functions to choose from. In addition, GrES is able to optimise these objective functions simultaneously while prioritising pairwise coverage, returning a diverse set of solutions that represent alternative tradeoffs between the objectives. This makes the approach highly flexible and suitable for different SPL scenarios where optimisation goals may differ, e.g., testing a cyber-physical SPL vs testing a web SPL. 5For the considered settings, the original PAES needs to examine 108grids during every generation. 6 THREATS TO VALIDITY This section briefly discusses threats to validity and how these were addressed. We consider three types of threats: those to internal validity, construct validity, and external validity. Internal Validity. This concerns any factors that could lead to bias. Threats could arise from the tools used in the experiments and so, where possible, we used tools that have been used in previous experiments (e.g., CASA and PLEDGE). We carefully tested our implementation of GrES and the code of the other EMO algorithms was taken from their authors except that of NSGA-IIH ,which was written by ourselves. In addition, all experiments were run 30 times to reduce the effect of the stochastic nature of the techniques and standard statistical tests were used. HV values were computed using sampling with 10,000,000 values. The choice of reference point may introduce bias and so we followed common practice of basing this on an estimate of the Pareto front. All of the EMO algorithms have configuration parameters, such as crossover and mutation rate, that could affect performance (i.e., higher prioritisation values and lower costs). We chose to use recommended values found in the literature, rather than carry out parameter tuning. Naturally, however, parameter tuning might further improve performance. The fact that GrES works well without tuning is promising. Finally, programs were run in two different computers, which could make execution times incomparable. We remark, however, that all seven C++ programs were run in the same computer and so the time comparison among them is fair. As detailed in Section 4.4, the JAVA program (NSGA-IIP ) was developed and executed by a different team in another computer. It is worth mentioning, however, that this computer was significantly more powerful than the one used for the C++ programs. Construct Validity. This concerns whether the measurements reflect properties that are of interest in practice. The objectives used in the experiments are those reported in previous studies but the Software Engineer could choose to use a subset of these. Pairwise coverage is a widely used test objective in SPL testing and so we reported the proportion of the solutions returned that achieved 100% coverage. In addition, we used HV since it is the most widely used measure of the diversity and quality of the set of solutions returned; a set with high HV provides a diverse set of good solutions. The measurements of time may well have been affected by the fact that one algorithm was implemented in JAVA and the others in C++. External Validity. This refers to the degree to which we can generalise from the experiments. This threat will always exist in Software Engineering research since we do not know the population of real problems and have no way of sampling from this in a uniform manner. We reduced this threat by using a mixture of randomly generated feature models, 19 realistic feature models with randomly generated attribute values, and 1 realistic feature model with real attribute values. 7 RELATED WORK Recent surveys and mapping studies on SPL testing reveal an increasing interest in the topic [15, 20, 21, 49]. In this section, we briefly summarise those papers that address the problem of test case selection and prioritisation from feature models using both multi and single-objective approaches. Multi-objective testing for SPL.Wang etal. [73] presented an industrial case study on multiobjective test case prioritisation for SPL. The problem was modelled using a single fitness function with four weighted objectives: minimising execution cost, maximising number of prioritised test cases, maximising pairwise coverage, and maximising fault detection capability. Four search-based algorithms were compared, namely, alternative variable method, a custom genetic algorithm, (1+1) evolutionary algorithm, and random search. The experiments were conducted on a real feature model with 53 features and 500 randomly generated models with up to 500 features. Henard et al. [31] presented an ad-hoc multi-objective genetic algorithm for test case selection from feature models. Three objectives were combined into a single fitness function with weighting factors: maximising pairwise coverage, minimising number of test cases, and minimising test cost. Their approach was compared with random solutions for 8 feature models from the SPLOT repository with up to 94 features. Lopez-Herrejon et al. [47] proposed an approach for computing the exact Pareto front of a feature model using SAT solvers. Two objectives were optimised: maximising pairwise coverage and minimising test suite size. As expected, the approach suffers from scalability issues: the Pareto front could be calculated in only 10 out of the 20 realistic feature models used in this study. In a subsequent work [48], the authors compared four classical multi-objective algorithms (NSGA-II, MOCell, SPEA2, and PAES) and the impact of three different seeding strategies on computing test suites with maximum coverage and minimum size. Their approach was evaluated on 19 out of the 20 feature models presented in Table 5(the Drupal feature model was presented later). In a later paper [49], the authors presented an overview of the state of the art on evolutionary computation for SPL testing. As a part of their work, they identified some open challenges including the application of many-objectives algorithms and the use of non-functional properties for test case prioritisation. Wang et al. [70] presented an approach to minimise SPL test suites by eliminating redundant test cases, where test cases are inputs and expected outputs to test products (rather than products). Given an input product and a test suite for testing it, their approach searches for a “good” subset of the suite according to several effectiveness and cost-related objectives, i.e. a separate optimisation problem is solved for each product. Their work compared three genetic algorithms where three objectives were combined into a single fitness function with weighting factors: minimising the number of test cases, maximising pairwise coverage, and maximising fault detection capability. Their approach was evaluated using several models from the SPLOT repository plus four feature models from an industrial project with sizes ranging from 17 to 77 features. In subsequent work [71], the authors compared their weight-based genetic algorithms against seven multi-objective search-based algorithms, namely NSGA-II, MOCell, SPEA2, PAES, SMPSO, CellDE and random search. Four fitness functions related to test effectiveness (to be maximised) and one fitness function to measure cost (to be minimised) were presented. The experiments were conducted on four feature models from an industrial project and 500 random feature models with up to 1,000 features. Algorithms were compared using a custom metric that combines the values of the five fitness functions for each solution. Lopez-Herrejon et al. [50] presented a genetic algorithm for the generation of prioritised pairwise test suites of minimum size from a feature model. The algorithm follows a master-slave strategy to parallelise the evaluation of products, which are prioritised based on some user-defined weights. In a related work [24], some of the authors presented two hybrid algorithms based on integer programming to address the same problem, outperforming the parallel genetic algorithm in both solution quality and computation time. Devroey et al. [19] proposed a search-based approach for test case selection in SPLs maximising the distance between products (in terms of features) and the distance between behavioural actions, derived from a model representing the behaviour of the SPL named Featured Transition System. Both distances were combined into a single fitness function integrated into the (1+1) Evolutionary Algorithm. Their approach was evaluated using four feature models with up to 44 features. Ferreira et al. [23,65] presented a hyper-heuristic approach for dynamic selection of evolutionary operators to be applied during the execution of a multi-objective evolutionary algorithm. The hyper-heuristic tries to determine the best mutation and crossover operators based on their performance. In their paper, they compared several hyper-heuristics on NSGA-II, SPEA2, IBEA, and MOEA/D-DRA with four objective functions: minimising suite size, maximising mutation score, maximising pairwise coverage, and maximising dissimilarity of products. The approach was evaluated using four realistic feature models with sizes ranging from 14 to 22 features. Parejo et al. [57] presented a case study on multi-objective test case prioritisation in highlyconfigurable s ystems u sing t he D rupal Web f ramework [59]. T hey p roposed s even prioritisation objective functions based on functional information extracted from the feature model, and non-functional data extracted from code and issue repositories. The approach was evaluated by comparing the effectiveness of 63 different combinations of up to three objective functions at accelerating the detection of faults in Drupal using the NSGA-II algorithm. Markiegi et al. [54] proposed a genetic algorithm for test selection using three objectives combined into a single fitness function with weighting factors: maximising fault detection capability, minimising test execution time, and maximising test case appearance frequency. The approach was evaluated using a cyber-physical SPL with 46 features. Our work is related to articles on multi-objective product selection where the goal is to select a product that optimises two or more objectives (see, for example, [26], [27], [33], [34], [61]). Compared to them, we address a different problem—the selection of a sequence of products (a test suite)—which means that we could not directly apply the algorithms used for optimal product selection. This being said, we see some potential in applying some of the ideas used in the generation of optimal products in our future work, such as enhancing the diversity of randomly generated products [26, 33]. Single-Objective Testing for SPL. A vast majority of the single-objective test case selection techniques for SPL are based on feature coverage using combinatorial techniques. Lopez-Herrejon et al. conducted a systematic mapping study on combinatorial interaction testing for SPLs [52]. They identified over forty approaches using different techniques such as genetic and greedy algorithms. They also found that a majority of the papers focus on deriving products from variability models (typically a feature model) using pairwise testing. Henard et al. [32] proposed a mutation-based approach for test case selection in SPLs that works in two steps. First, a set of faulty versions of the feature model, so-called mutants, are created, e.g., removing an excludes constraint. Then, the (1+1) Evolutionary Algorithm is used to search for test cases that kill as many mutants as possible, i.e., products that do not conform to the mutated feature models. Henard et al. [29] presented a search-based approach to generate and prioritise t-wise test suites, with t ∈{2,...,6}, on some of the largest features model available (with up to 6.8K features). They employ a variant of the (1+1) Evolutionary Algorithm with no crossover and a fitness function based on the Jaccard’s dissimilarity metric. The initial population is generated randomly using a modified SAT solver to guarantee that solutions are generated in an unpredictable way. Their work is based on the assumption that the higher the differences between the products of the suite, the higher the t-wise coverage. The suite is also prioritised based on the dissimilarity distances among the products in a subsequent step. Their algorithm computes suites of fixed size within a given time used as a stopping criterion. In related work, Al-Hajjaji et al. [3] proposed an algorithm for SPL prioritisation using an adaptation of the Hamming distance to measure the similarity among products. Xu et al. [75] proposed an SPL test suite augmentation approach and related tool named CONTESA. Their tool incrementally generates test cases that exercise parts of the code that have not yet been covered by previous test cases, e.g., code branches. A genetic algorithm was used to automatically generate test cases for the products under test. Devroy et al. [18]proposedtoprioritise products according to the likelihood of their executions, derived from a usage model represented by a Featured Transition System (a type of Markov chain). Ensan et al. [22] proposed a genetic algorithm approach for the generation of SPL test suites with good fault detection capability and feature coverage. The fitness of each suite was measured using a combination of the variability coverage and cyclomatic complexity metrics for feature models [7]. Inspired by their work, those metrics were adapted and used in the VCoverage prioritisation function used in this paper. In related work, the authors proposed eight coverage criteria based on the transformation of feature models into formal context-free grammars [6]. The rationale behind the proposed coverage criteria is based on the development of equivalence partitions on the SPL under test and the use of boundary–value analysis for test case generation. Al-Hajjaji et al. [1] proposed a cluster-based approach for similarity-based product prioritisation. The approach was evaluated using 10 feature models with up to 6,888 features. In a related paper [2], the authors proposed a prioritisation approach based on product similarity using deltamodeling, that is, specific information about how each product is implemented. The approach was evaluated by means of an SPL from the automotive domain with 27 features. Finally, the synergies between SBSE and SPLs have been extensively explored and summarised in several survey papers [28,53]. This article takes a step further in exploiting the benefits of many-objective search-based optimisation for testing SPLs. Compared to the extensive body of related research, this article presents several novel contributions. First, we propose the first many-objective approach for SPL testing optimising up to 9 different objectives, addressing both test selection and prioritisation simultaneously. Also, we present a novel evolutionary algorithm (GrES) and an optimisation framework, where pairwise coverage is given priority over the rest of the objectives. The evaluation results with both random and realistic feature models show that this approach is able to tame the complexity of the problem and outperform the state-of-the-art algorithms used in previous approaches. 8 CONCLUSIONS This paper investigated the problem of producing good test suites for SPL testing: test suites that achieve full pairwise coverage and also have a number of other desirable properties related to test selection and test prioritisation. Test generation is thus a many-objective optimisation problem, with different solutions (that are not related under Pareto dominance) representing alternative trade-offs that can be provided to the Software Engineer. We noted that one of the objectives, pairwise coverage, is more important than the others: the Software Engineer is only interested in tests that achieve full coverage. As a result, we introduced a novel approach, based on this piece of domain knowledge, that optimises first on pairwise coverage and only then on the other objectives. Importantly, it is straightforward to adapt any EMO to use this approach. We then developed a novel evolution strategy, GrES, that uses this approach. GrES adapts a standard evolution strategy to reflect domain knowledge including the fact that the set of objectives can be partitioned into two sets (for selection and prioritisation). We had observed that the crossover operation could break good building blocks of chromosomes of the seed individual in the evolutionary search, and thus GrES conducts repeated explorations around the seed individual and its offspring. We evaluated the proposed approach, GrES, through a range of experiments that addressed the following research questions: whether GrES outperformed current techniques (in terms of both FCR, the number of test suites with full pairwise coverage, and the HV values of the populations returned); whether the novel evolution strategy used in GrES contributed to its performance; how GrES performed with the subsets of objectives used in previous studies; whether differences in