Multi-objective test case prioritization in highly configurable systems: A case study

Accepted Manuscript Multi-Objective Test Case Prioritization in Highly Configurable Systems: A Case Study Jos´ e A. Parejo, Ana B. S´ anchez, Sergio Segura, Antonio Ruiz-Cort´ es, Roberto E. Lopez-Herrejon, Alexander Egyed PII: S0164-1212(16)30193-5 DOI: 10.1016/j.jss.2016.09.045 Reference: JSS 9857 To appear in: The Journal of Systems & Software Received date: 23 December 2015 Revised date: 8 September 2016 Accepted date: 25 September 2016 Please cite this article as: Jos´ e A. Parejo, Ana B. S´ anchez, Sergio Segura, Antonio Ruiz-Cort´ es, Roberto E. Lopez-Herrejon, Alexander Egyed, Multi-Objective Test Case Prioritization in Highly Configurable Systems: A Case Study, The Journal of Systems & Software (2016), doi: 10.1016/j.jss.2016.09.045 This is a PDF file of an unedited manuscript that has been accepted for publication. As a service to our customers we are providing this early version of the manuscript. The manuscript will undergo copyediting, typesetting, and review of the resulting proof before it is published in its final form. Please note that during the production process errors may be discovered which could affect the content, and all legal disclaimers that apply to the journal pertain. ACCEPTED MANUSCRIPT ACCEPTED MANUSCRIPT Highlights •A multi-objective test case prioritization real-world case study is presented •Seven objective functions based on functional and non-functional data are proposed •Comparison of the effectiveness of 63 combinations of up to three objectives •NSGA-II evolutionary algorithm to solve the multiobjective prioritization problem •Multi-objective prioritization is more effective than mono-objective approaches 1 ACCEPTED MANUSCRIPT ACCEPTED MANUSCRIPT Multi-Objective Test Case Prioritization in Highly Configurable Systems: A Case Study Jos´e A. Parejoa, Ana B. S´ancheza, Sergio Seguraa, Antonio Ruiz-Cort´esa, Roberto E. Lopez-Herrejonb, Alexander Egyedb aETS Ingenier´ıa Inform´atica Universidad de Sevilla, Spain bInstitute for Software System Engineering Johannes Kepler University, Austria Abstract Test case prioritization schedules test cases for execution in an order that attempts to accelerate the detection of faults. The order of test cases is determined by prioritization objectives such as covering code or critical components as rapidly as possible. The importance of this technique has been recognized in the context of Highly-Configurable Systems (HCSs), where the potentially huge number of configurations makes testing extremely challenging. However, current approaches for test case prioritization in HCSs suffer from two main limitations. First, the prioritization is usually driven by a single objective which neglects the potential benefits of combining multiple criteria to guide the detection of faults. Second, instead of using industry-strength case studies, evaluations are conducted using synthetic data, which provides no information about the effectiveness of different prioritization objectives. In this paper, we address both limitations by studying 63 combinations of up to three prioritization objectives in accelerating the detection of faults in the Drupal framework. Results show that non–functional properties such as the number of changes in the features are more effective than functional metrics extracted from the configuration model. Results also suggest that multi-objective prioritization typically results in faster fault detection than mono-objective prioritization. 1. Introduction Highly-Configurable Systems (HCSs) provide a common core functionality and a set of optional features to tailor variants of the system according to a given set of requirements [9, 69]. For instance, operating systems such as Linux or eCos are examples of HCSs where functionality is added or removed by installing and uninstalling packages, e.g. Debian Wheezy offers more than 37,000 available packages [13]. Content management systems are also examples of HCSs were configuration is managed in terms of modules, e.g. the e-commerce platform Prestashop has more than 3,500 modules and visual templates [63]. Recently, cloud applications are also being presented as configurable systems, e.g. the Amazon Elastic Compute Cloud (EC2) service offers 1,758 different possible configurations [27]. HCSs are usually represented in terms of features. A feature depicts a choice to include a certain functionality in a system configuration [69]. It is common that not all combinations of features are allowed or meaningful. In this case, additional constraints are defined between them, normally using a variability model, such as a feature model. Email addresses: [email protected] (Jos´e A. Parejo), [email protected] (Ana B. S´anchez), [email protected] (Sergio Segura), [email protected] (Antonio Ruiz-Cort´es), [email protected] (Roberto E. Lopez-Herrejon), [email protected] (Alexander Egyed) Afeature model represents all the possible configurations of the HCS in terms of features and constraints among them [40]. A configuration is a valid composition of features satisfying all the constraints. Figure 1 depicts a feature model representing a simplified family of mobile phones. The model illustrates how features and relationships among them are used to specify the commonalities and variabilities of the mobile phones. The following set of features represents a valid configuration of the model: {Mobile Phone, Calls, Screen, HD, GPS, Media, Camera}. HCS testing is about deriving a set of configurations and testing each configuration [54]. In this context, a test case is defined as a configuration of the HCS under test (i.e. a set of features) and a test suite is a set of test cases [54]. Henceforth, the terms test case and configuration are used indistinctly. Testing HCSs is extremely challenging due to the potentially huge number of configurations under test. As an example, Eclipse [13] has more than 1,650 plugins that can be combined (with restrictions) to form millions of different configurations of the development environment. This makes exhaustive testing of HCSs infeasible, that is, testing every single configuration is too expensive in general. Also, even when a manageable set of configurations is available, testing is irremediably limited by time and budget constraints which requires making tough decisions with the goal of finding as many faults as possible. Typical approaches for HCS testing use a model-based Preprint submitted to Elsevier Monday 26th September, 2016 ACCEPTED MANUSCRIPT ACCEPTED MANUSCRIPT approach, that is, they take an input feature model representing the HCS and return a valid set of feature configurations to be tested, i.e. a test suite. In particular, two main strategies have been adopted: test case selection and test case prioritization. Test case selection reduces the test space by selecting an effective and manageable subset of configurations to be tested [16, 34, 50]. Test case prioritization schedules test cases for execution in an order that attempts to increase their effectiveness at meeting some performance goal, typically detecting faults as soon as possible [2, 45, 75]. Both strategies are complementary and are often combined. Test case prioritization in HCSs can be driven by different functional and non–functional objectives. Functional prioritization objectives are those based on the functional features of the system and their interactions. Some examples are those based on combinatorial interaction testing [75], configuration dissimilarity [2, 33, 60] or feature model complexity metrics [59, 60]. Non–functional prioritization objectives consider extra–functional information such as user preferences [21, 39], cost [75], memory consumption [45] or execution probability [15] to find the best ordering for test cases. In a previous work [59], we performed a preliminary evaluation comparing the effectiveness of several functional and non–functional prioritization objectives in accelerating the detection of faults in an HCS. Results suggested that non–functional properties such as the number of changes or the number of defects in a previous version of the system were among the most effective prioritization criteria. Challenges. Current approaches for test case prioritization in HCSs follow a single objective approach [2, 39, 15, 21, 33, 45, 59], that is, they either aim to maximize or minimize an objective (e.g. feature coverage) or another (e.g. suite size) but not both at the same time. Other works [70, 75] combine several objectives into a single function by assigning them weights proportional to their relative importance. While this may be acceptable in certain scenarios, it may be unrealistic in others where users may wish to study the trade-offs among several objectives [44]. Thus, the potential benefits of optimizing multiple prioritization objectives simultaneously, both functional and non–functional, is a topic that remains unexplored. A further challenge is related to the lack of HCSs with available code, variability models and fault reports that can be used to assess the effectiveness of testing approaches. As a result, authors typically evaluate their contributions in terms of performance (e.g. execution time) using synthetic feature models and data [2, 34, 56, 76]. This introduces significant threats to validity, limit the scope of their conclusions and, more importantly, it raises questions regarding the fault–detection effectiveness of the different algorithms and prioritization objectives. Contributions. In this paper, we present a case study on multi–objective test case prioritization in HCSs. In particular, we model test case prioritization in HCSs as a multi–objective optimization problem, and we present a search–based algorithm to solve it based on the classical NSGA-II evolutionary algorithm. Additionally, we present seven objective functions based on both functional and non–functional properties of the HCS under test. Then, we report a comparison of 63 different combinations of up to three objectives in accelerating the detection of faults in the Drupal framework. Drupal is a highly modular open source web content management system for which we have mined a feature model and extracted real data from its issue tracking system and Git repository [59]. Results reveal that non–functional properties, such as the number of defects in previous versions of the system, accelerate the detection of faults more effectively than functional properties extracted from the feature model. Results also suggest that multi-objective prioritization is more effective at accelerating the detection of faults than mono-objective prioritization. The rest of the paper is structured as follows: Section 2 introduces the concepts of feature models and multiobjective evolutionary algorithms. Section 3 presents the Drupal case study used to perform this work. In Section 4 and Section 5 we respectively describe the overview and definition of our approach and the multi-objective optimization algorithm proposed. Section 6 defines seven objective functions for HCSs based on functional and nonfunctional goals. The evaluation of our approach is described in Section 7. Section 8 presents the threats to validity of our work. The related work is discussed in Section 9. Finally, we summarize our conclusions and outline our future work in Section 10. 2. Background 2.1. Feature Models Afeature model defines all the possible configurations of a system or family of related systems [6, 40]. A feature model is visually represented as a tree–like structure in which nodes represent features, and edges denote the relationships among them. A feature can be defined as any increment in the functionality of the system [5]. A configuration of the system is composed of a set of features satisfying all the constraints of the model. Figure 1 shows a feature model describing a simplified family of mobile phones. The hierarchical relationship among features can be divided into: •Mandatory. If a feature has a mandatory relationship with its parent feature, it must be included in all the configurations in which its parent feature appears. In Figure 1, all mobile phones must provide support for Calls. •Optional. If a feature has an optional relationship with its parent feature, it can be optionally included 3 ACCEPTED MANUSCRIPT ACCEPTED MANUSCRIPT Figure 1: Mobile phone feature model in all the configurations including its parent feature. For example, GPS is defined as an optional feature of mobile phones. •Alternative. A set of child features has an alternative relationship with their parent feature when only one of them can be selected when its parent feature is part of the configuration. In Figure 1, mobile phones can provide support for Basic or HD (High Definition) screen, but not both of them at the same time. •Or. A set of child features has an or-relationship with their parent when one or more of them can be included in the configurations in which its parent feature appears. In Figure 1, software for mobile phones can provide support for Camera,MP3 or both in the same configuration. In addition to the hierarchical relationships between features, a feature model can also contain cross-tree constraints. These are usually of the form: •Requires. If a feature A requires a feature B, the inclusion of A in a configuration implies the inclusion of B in such configuration. In Figure 1, mobile phones including the feature Camera must include support for a HD screen. •Excludes. If a feature A excludes a feature B, both features cannot appear in the same configuration. The following is a sample configuration derived from the feature model in Figure 1: {Mobile Phone,Calls, Screen,HD,Media,Camera}. This configuration includes all the mandatory features (Mobile Phone,Calls,Screen) and some extra features (HD,Media,Camera) meeting all Feature Changes Faults Size Basic 1 0 270 Calls 6 10 1,000 Camera 11 8 680 GPS 8 6 460 HD 3 3 510 Media 9 5 1,100 MP3 11 8 390 Screen 2 4 930 Table 1: Mobile phone feature attributes the constraints of the model, e.g. Camera requires HD. Feature models can be automatically analysed to extract all its possible configurations or to determine whether a given configuration is valid (it fulfils all the constraints of the model), among other analysis operations [6]. Some tool supporting the analysis of feature models are FaMa [24], SPLAR [53] and FeatureIDE [66]. Feature models can be extended with additional information by means of feature attributes, these are called attributed or extended feature models [6]. Feature attributes are often defined as tuples < name, value > specifying non–functional information of features such as cost or memory consumption. As an example, Table 1 depicts three different feature attributes (number of changes, number of faults and lines of code) and their values on the features of the model in Figure 1. Feature models are often used to represent the test space of an HCS where each configuration of the model represents a potential test case. Since typical HCSs can have thousands or even millions of different configurations, several sampling techniques have been proposed to reduce the number of configurations to be tested (e.g. [46, 50, 55]). Salient among them is pairwise testing whose goal is to select test suites that contain all possible combinations of pairs of features [46]. As an example, Table 3 shows the set of configurations obtained when applying pairwise testing to the model in Figure 1. The test suite is reduced from 13 (total number of configurations of the feature model) to five in the pairwise suite. Once a set of configurations are selected for testing, their behaviour has to be tested using standard testing mechanisms, e.g. executable unit tests. However, in this article we focus only on the first step: obtaining a set of high-level test cases respect to different testing objectives. In Section 4 we present in further detail the role of feature models in our work. 2.2. Multi–objective evolutionary algorithms Evolutionary algorithms are a widely used strategy to solve multi–objective optimization problems. These algorithms manage a set of candidate solutions to an optimization problem that are combined and modified iteratively to obtain better solutions. This process simulates the natural selection of the better adapted individuals that survive and generate offspring improving species. In evolution- 4 ACCEPTED MANUSCRIPT ACCEPTED MANUSCRIPT Figure 2: Working scheme of evolutionary algorithm ary algorithms each solution is referred to as individual or chromosome, and objectives are referred to as fitness functions. The working scheme of an evolutionary algorithm is depicted in Figure 2. Initialization generates the set of individuals that the algorithm will use as starting point. Such initial population is usually generated randomly. Next, the fitness functions are used to assess the individuals. In order to create offspring, individuals need to be encoded, expressing its characteristics in a form that facilitates its manipulation during the rest of the algorithm. Then, the main loop of the evolutionary algorithm is executed until meeting a termination criterion as follows. First, individuals are selected from current population in order to create new offspring. In this process, better individuals usually have higher probability of being selected resembling the natural evolution where stronger individuals have more chances of reproduction. Next, crossover is performed to combine the characteristics of a pair of the chosen individuals to produce new ones in an analogous way to biological reproduction. Crossover mechanisms depend strongly on the scheme used for the encoding. Mutation generates random changes on the new individuals. Changes are performed with certain probability where small modifications are more likely than larger ones. In order to evaluate the fitness of new and modified individuals, decoding is performed and fitness functions are evaluated. Finally, the next population is conformed in such a way that individuals with better fitness values are more likely to remain in the next population. Multi–Objective Evolutionary Algorithms (MOEAs) are a specific type of evolutionary algorithm where more than one objective are optimized simultaneously. However, except in trivial systems, there rarely exist a single solution that simultaneously optimizes all the objectives. In that case, the objectives are said to be conflicting, and there exists a (possibly infinite) number of so-called Pareto optimal solutions. A solution is said to be a Pareto optimal (a.k.a. non-dominated) if none of the objectives can be improved without degrading some of the others objectives. Analogously, the solutions where all the objectives can be improved are referred to as dominated solutions. The surface obtained from connecting all the Pareto optimal solutions is the so-called Pareto Front. Among the many MOEAs proposed in the literature, the Non-dominated Sorting Genetic Algorithm-II (NSGA-II) [12] has become very popular due to its effectiveness in many of the benchmarks in multi–objective optimization [11, 81]. 3. The Drupal case study In this section, we present the Drupal case study fully reported by the authors in a previous work [59]. Drupal is a highly modular open source web content management framework written in PHP [8, 67]. This tool can be used to build a variety of websites including internet portals, e-commerce applications and online newspapers [67]. Drupal has more than 30,000 modules that can be composed to form valid configurations of the system. The size of the Drupal community (more than 630,000 users and developers) together with its extensive documentation are strengths to choose this framework as our empirical case study. More importantly, the Drupal Git repository and the Drupal issue tracking systems are publicly available sources of valuable functional and non-functional information about the framework and its modules. Figure 3 depicts the feature model of Drupal v7.23. Nodes in the tree represent features where a feature corresponds to a Drupal module. A module is a collection of functions that provides certain functionality to the system. Some modules extend the functionality of other modules and are modelled as subfeatures, e.g. Views UI extends the functionality of Views. The feature model includes the core modules of Drupal, modelled as mandatory features, plus some optional modules, modelled as optional features. In addition, the cross-tree constraints of the features in the model are depicted in Figure 3. These are of the form Xrequires Y, which means that configurations including the feature Xmust also include the feature Y. A Drupal configuration is a combination of features consistent with the hierarchical and cross-tree constraints of the model. In total, the Drupal feature model has 48 features, 21 non-redundant cross-tree constraints and it represents 2.09E9 different configurations [59]. In this paper, we model the non-functional data from Drupal as feature attributes, depicted in Table 2. These data were obtained from the Drupal website, the Drupal 5 ACCEPTED MANUSCRIPT ACCEPTED MANUSCRIPT Figure 3: Drupal feature model Git repository and the Drupal issue tracking system [59]. In particular, we use the following attributes: •Feature size. Number of Lines of Code (LoC) of the source code associated to the feature (blank lines and test files were excluded from the counting). The sizes range from 284 LoC (feature Ctools custom content) to 54,270 LoC (feature Views). •Number of changes. Number of commits made by the contributors to the feature in the Drupal Git repository1during a period of two years, from 1 May 2012 to 31 April 2014. As illustrated, the number of changes ranges from 0 (feature Blog) to 90 (feature Backup migrate). •Single faults. Number of faults reported in the Drupal issue tracking system2. Faults were collected for two consecutive versions of the framework v7.22 and v7.23 in a period of two years, from 1 May 2012 to 31 April 2014. For instance, we found 19 reported bugs related to the Drupal module Taxonomy (feature Taxonomy) in Drupal v7.23. The number of total faults ranges from 0 in features as Options to 1,091 in the feature Views. •Integration faults. List of features for which integration faults have been reported in the Drupal issue tracking system. In total, we identified three faults triggered by the interaction of four features, 25 caused by the interaction of three features and 132 faults triggered by the interaction between two features. These faults have been computed on the features that triggered them in Table 2. For instance, the fault caused by the interaction of Blog and Entity API is computed as one integration fault in the feature Blog and one integration fault in the feature Entity API. We refer the reader to [59] for detailed information about the bug mining process in Drupal. 4. Approach overview In this section, we define the problem addressed and our approach illustrating it with an example. 4.1. Problem The classical problem of test case prioritization consists in scheduling test cases for execution in an order that attempts to increase their effectiveness at meeting some performance goal [57]. A typical goal is to increase the so-called rate of fault detection, a measure of how quickly faults are detected during testing. In order to meet a goal, 1http://drupalcode.org/project/drupal.git 2https://drupal.org/project/issues 6 ACCEPTED MANUSCRIPT ACCEPTED MANUSCRIPT Feature Size Changes Faults (v7.22) Faults (v7.23) Single Integration Single Integration Backup migrate 11,639 90 80 4 80 4 Blog 551 0 1 3 0 3 Captcha 3,115 15 17 1 17 1 CKEditor 13,483 40 197 11 197 9 Comment 5,627 1 10 19 13 15 Ctools 17,572 32 181 31 181 31 Ctools acc. rul. 317 0 0 0 0 0 Ctools cus. con. 284 1 10 1 10 1 Date 2,696 9 44 3 44 3 Date API 6,312 11 41 1 41 1 Date popup 792 4 30 1 30 1 Date views 2,383 6 25 1 25 1 Entity API 13,088 14 175 18 175 18 Entity tokens 327 1 22 6 22 6 Features 8,483 72 97 9 97 9 Field 8,618 7 45 18 48 17 Field SQL sto. 1,292 2 3 2 3 2 Field UI 2,996 3 13 2 11 1 File 1,894 1 10 5 11 5 Filter 4,497 3 19 5 19 5 Forum 2,849 2 6 4 5 4 Google ana. 2,274 14 11 1 11 1 Image 5,027 3 10 8 9 6 Image captcha 998 0 3 0 3 0 IMCE 3,940 9 9 5 9 5 Jquery update 50,762 1 64 12 64 12 Libraries API 1,627 7 11 0 11 0 Link 1,934 11 82 4 82 4 Node 9,945 4 26 29 24 23 Options 898 1 0 0 0 0 Panel nodes 480 2 16 1 16 1 Panels 13,390 34 87 24 87 24 Panels IPE 1,462 20 19 2 19 2 Path 1,026 20 3 1 2 1 Pathauto 3,429 2 54 9 54 9 Rules 13,830 5 240 15 240 15 Rules sch. 1,271 4 13 0 13 0 Rules UI 3,306 1 26 0 26 0 System 20,827 16 35 5 35 4 Taxonomy 5,757 4 15 22 19 22 Text 1,097 1 6 3 5 3 Token 4,580 10 37 7 37 7 User 8,419 12 20 25 19 22 Views 54,270 27 1,091 51 1,091 51 Views content 2,683 5 23 2 23 2 Views UI 782 0 12 4 12 4 WebForm 13,196 46 292 0 292 0 Total 336,025 573 3,231 3,232 Table 2: Non–functional feature attributes in Drupal prioritization can be driven by one or more objectives. For instance, in order to accelerate the detection of faults, a sample objective could be to increase the code coverage in the system under test at a faster rate, under the assumption that faster code coverage implies faster fault detection. Inspired by the previous definition, we next define the multi-objective test case prioritization problem in HCSs. Given the set of configurations of an HCS represented by a feature model fm, we present the following definitions. Test case. A test case is a set of features of fm, i.e., a configuration. A test case is valid if its features satisfy the constraints represented by the feature model. As an example the following set of features represent a valid test case of the model presented in Figure 1: {Mobile Phone, Calls, Screen, Basic, Media, MP3}. Test suite. A test suite is an ordered set of test cases. Table 3 depicts a sample test suite of the model presented in Figure 1. Objective function. An objective function represents a goal to optimize. In this work, objective functions receive an attributed feature model (fm) and a test suite as inputs and return a numerical value measuring the quality of the suite with respect to the optimization goal. 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 Table 3: Mobile phone test suite Given a feature model representing the HCS under test and an objective function, the problem of test case prioritization in HCSs consists in generating a test suite that optimizes the target objective. This problem can be generalized to a multi–objective problem by considering more than one objective. In this case, the problem may have more than one solution (i.e., test suites) if there not exist a single solution that simultaneously optimizes all the objectives. 4.2. Our approach Our approach can be divided in two parts described in the next sections. 4.2.1. Multi–objective test case prioritization We propose to model the multi–objective test case prioritization problem in HCSs as a multi–objective optimization problem. Figure 4 illustrates our approach. Given an input attributed feature model, the problem consists in finding a set of solutions (i.e., test suites) that optimize the 7 ACCEPTED MANUSCRIPT ACCEPTED MANUSCRIPT Figure 4: Our multi–objective test case prioritization approach for HCSs target objectives. In this paper, we propose seven objective functions based on both functional and non–functional properties of the HCS under test. 4.2.2. Comparison of prioritization objectives We propose to compare the effectiveness of different combinations of prioritization objectives at accelerating the detection of faults in the Drupal framework. To that purpose, we used historical data collected from a previous version of Drupal as detailed in Section 3. In particular, we propose using the Average Percentage of Faults Detected (APFD) [19, 57, 65] metric to check which one of the Pareto optimal solutions obtained accelerates the detection of faults more effectively. This enables the selection of a global solution and makes it possible to identify the objectives that lead to better test suites. The Average Percentage of Faults Detected (APFD) [19, 57, 65] metric measures the weighted average of the percentage of faults detected during the execution of the test suite. To formally define APFD, let Tbe a test suite which contains ntest cases, and let Fbe a set of mfaults revealed by T. Let TFi be the position of the first test case in ordering T’ of Twhich reveals the fault i. The APFD metric for the test suite T’ is given by the following equation: APF D = 1 −T F1+T F2+...+T Fn n×m+1 2n APFD value ranges from 0 to 1. The closer the value is to 1, the better is the fault detection rate, i.e., the faster is the suite at detecting faults. 4.3. Illustrative example Table 4 shows the information of four test suites, using the test cases of Table 3. Note that the order of test cases matters. Along with the test cases that compose each suite, the table also shows the value of the objective functions Changes and Faults defined in Section 6. Roughly speaking, these functions measures the ability of the suite to test those features with a greater number of code changes or reported bugs as quickly as possible. Figure 5 depicts the Pareto front obtained when trying to find a test suite that maximizes both objectives. As denoted in the call-out of Figure 5, TS4 is dominated ID Test cases Changes Faults TS1 TC4, TC1, TC5, TC3 109 49 TS2 TC1, TC2, TC3, TC4, TC5 80 52 TS3 TC3, TC4, TC5, TC2, TC1 77 57 TS4 TC5, TC4, TC2, TC3, TC1 59 53 Table 4: A set of test suites for the mobile phone Figure 5: Test suites of table 4 as a pareto front for objectives Changes and Faults (both to be maximized) by TS3, since TS3 detects more faults and covers more changes faster; i.e. TS3 is better than TS4 according to both objectives. Once the optimal test suites are generated, we calculate their APFD to evaluate how quickly they detect faults (based on historical data from a previous version of the system). Consider the faults detected by each test case shown in Table 5. According to the previous APFD equation, test suite TS1 produces an APFD of 46%: 1−2+2+4+4+1+3 4×6+1 2×4= 0.46, TS2 an APFD of 57%: 1−1+1+2+3+4+5 5×6+1 2×5= 0.57 TS3 an APFD of 80%: 1−1+1+1+1+2+3 5×6+1 2×5= 0.8 and TS4 an APFD of 53%: 1−3+4+3+4+2+1 5×6+1 2×5= 0.53 Based on the previous results, TS3 is better than TS1 and TS2 and therefore it is the best solution at accelerating the detection of faults. The process could then be repeated with different groups of objectives comparing their effectiveness in terms of the APFD values achieved. 5. Multi-objective optimization algorithm We used a MOEA to solve the multi–objective test case prioritization problem in HCSs. In particular, we 8 ACCEPTED MANUSCRIPT ACCEPTED MANUSCRIPT Functional Multi-Objective Functional Mono-Objective CASA Connectivity Dissimilarity Pairwise VCoverage Connectivity + Dissimilarity 0.484 0.587 0.923 0.527 0.946 Connectivity + Pairwise 0.801 0.880 0.992 0.839 0.999 Connectivity + VCoverage 0.528 0.631 0.893 0.577 0.924 Dissimilarity + Pairwise 0.840 0.911 0.994 0.873 0.994 Dissimilarity + VCoverage 0.489 0.593 0.901 0.530 0.914 Pairwise + VCoverage 0.698 0.791 0.983 0.757 0.997 Connectivity + Dissimilarity + Pairwise 0.851 0.921 0.996 0.884 0.998 Connectivity + Dissimilarity + VCoverage 0.504 0.606 0.921 0.552 0.924 Connectivity + Pairwise + VCoverage 0.789 0.870 0.988 0.831 1.000 Dissimilarity + Pairwise + VCoverage 0.855 0.924 0.994 0.892 1.000 CASA 0.064 0.054 0.276 0.073 - Table 8: d A12 values for mono vs. multi–objective prioritization using functional objectives. Cells revealing very large statistical differences are highlighted in light grey (in favour of the row) and dark grey (in favour of the column). Values in boldface reveal statistically significant differences (the p-value with Holm’s correction <0.05). Objectives NSGA-II CASA Avg Avg Max Max Avg Max Changes 0.902 0.922 0.959 0.871 0.927 Faults 0.955 0.955 0.959 0.873 0.944 Size 0.921 0.934 0.955 0.868 0.932 Changes + Faults 0.953 0.955 0.959 0.865 0.952 Changes + Size 0.915 0.936 0.956 0.868 0.938 Faults + Size 0.955 0.955 0.959 0.876 0.940 Changes + Faults + Size 0.952 0.955 0.959 0.871 0.942 Average 0.936 0.945 0.958 0.871 0.939 Table 9: APFD values achieved by non-functional prioritization objectives 15 ACCEPTED MANUSCRIPT ACCEPTED MANUSCRIPT Figure 9: Box plot of the maximum APFD achieved on each execution (40 in total) were found between the use of multi–objective prioritization with two or three objectives. The average execution time of NSGA-II for all the combinations of non-functional objectives was 3.7 minutes, with a maximum average execution time of 4.6 minutes for Faults +Size and a minimum average execution time of 2.5 seconds for Size. Non-Functional Mono-Objective Multi-Objective Changes Faults Size Changes + Faults 0.955 0.565 0.968 Changes + Size 0.670 0.084 0.549 Faults + Size 0.960 0.597 0.978 Changes + Faults + Size 0.951 0.536 0.960 Table 10: d A12 values for mono vs. multi-objective prioritization using non–functional objectives. Cells revealing very large statistical differences are highlighted in light grey (in favour of the row). Values in boldface reveal statistically significant differences (the p-value with Holms correction <0.05). 7.5. Experiment 3. Functional and non–functional objectives In this experiment, we evaluated the rate of fault detection achieved by each mixed combination of 2 and 3 functional and non–functional prioritization objectives, 48 combinations in total. The results of the experiment are presented in Table 11. The cells with the top three best average, average maximum, and global maximum APFD values of the table are highlighted in boldface. The results show that all the multi–objective combinations greatly improved CASA on the average, average maximum, and global maximum APFD values obtained. As in the previous experiment, 10 out of the 12 top best APFD values were achieved by multi–objective combinations including the objective Faults, which confirms the effectiveness of fault history in accelerating the detection of faults in Drupal. Analogously, 6 out of the 10 best APFD values include the objective Dissimilarity which confirms the findings of previous studies on the effectiveness of promoting the differences among test cases to detect faults more quickly. As in the previous experiments, all the test suites generated detected at least the 99% of the seeded faults. Table 12 shows the values of the d A12 effect size on the comparison between single and multi–objective combinations of functional and non–functional objectives. Values indicate a better performance of multi–objective prioritization compared to single–objective prioritization with the exception of Faults where most cells were under 0.5. The overall dominance, however, was observed in the combination of objectives Dissimilarity +Faults followed by Dissimilarity +Faults +VCoverage, with values over 0.6 in all cells and over 0.93 in 6 out of 7 columns. Table 13 depicts the effect size on the comparison between multi–objective prioritization using functional objectives and multi–objective prioritization using both functional and non–functional objectives. In general, d A12 values show statistical differences in favour or the combination of functional and non-functional objectives, especially those including Faults. Interestingly, all the cells revealing differences in favour of functional-objectives include the objective Pairwise, which supports its potential when combined with other prioritization objectives, as observed in Experiment 1. Finally, Table 14 depicts the effect size on the comparison between multi–objective prioritization using non– functional objectives and multi–objective prioritization using both functional and non–functional objectives. d A12 values reveal that when Faults is present in the combination of non–functional objectives, mixed combinations are outperformed in general, showing large effect sizes and statistically significant differences. On the contrary, mixed objective combinations including Faults clearly outperform Changes +Size, but behave slightly worse than the other combinations of non-functional objectives. Therefore, the objective Faults seems to have a key influence in the performance of prioritization providing slightly better result when combined with other non-functional objectives. It is remarkable, however, that some mixed combinations of objectives such as Dissimilarity +Faults provided the best overall results of this experiment. The average execution time of NSGA-II for the mixed combinations of functional and non–functional prioritization objectives was 9.2 minutes. The maximum average execution time was 23.6 minutes reached by the objectives Connectivity +Faults +Pairwise. The minimum execution time, 73.8 seconds, was obtained by the combination of objectives Connectivity +Size +VCoverage. 16 ACCEPTED MANUSCRIPT ACCEPTED MANUSCRIPT Objectives NSGA-II CASA Avg Avg Max Max Avg Max Changes + Connectivity 0.911 0.936 0.959 0.871 0.942 Changes + Dissimilarity 0.905 0.935 0.959 0.873 0.943 Changes + Pairwise 0.938 0.952 0.959 0.878 0.950 Changes + VCoverage 0.919 0.940 0.958 0.867 0.941 Connectivity + Faults 0.954 0.955 0.959 0.884 0.935 Connectivity + Size 0.915 0.941 0.959 0.881 0.946 Dissimilarity + Faults 0.954 0.956 0.959 0.871 0.947 Dissimilarity + Size 0.904 0.930 0.957 0.858 0.921 Faults + Pairwise 0.944 0.954 0.959 0.868 0.944 Faults + VCoverage 0.954 0.955 0.959 0.869 0.940 Pairwise + Size 0.940 0.953 0.960 0.878 0.943 Size + VCoverage 0.914 0.937 0.958 0.876 0.948 Changes + Connectivity + Dissimilarity 0.908 0.938 0.958 0.873 0.935 Changes + Connectivity + Faults 0.950 0.955 0.959 0.875 0.935 Changes + Connectivity + Pairwise 0.936 0.953 0.958 0.862 0.933 Changes + Connectivity + Size 0.914 0.942 0.959 0.878 0.929 Changes + Connectivity + VCoverage 0.916 0.942 0.959 0.876 0.947 Changes + Dissimilarity + Faults 0.952 0.955 0.959 0.880 0.936 Changes + Dissimilarity + Pairwise 0.939 0.954 0.958 0.874 0.936 Changes + Dissimilarity + Size 0.911 0.941 0.957 0.867 0.943 Changes + Dissimilarity + VCoverage 0.910 0.946 0.957 0.869 0.945 Changes + Faults + Pairwise 0.944 0.954 0.958 0.874 0.941 Changes + Faults + VCoverage 0.951 0.955 0.959 0.883 0.946 Changes + Pairwise + Size 0.941 0.955 0.963 0.866 0.952 Changes + Pairwise + VCoverage 0.937 0.954 0.958 0.875 0.947 Changes + Size + VCoverage 0.909 0.940 0.957 0.874 0.940 Connectivity + Dissimilarity + Faults 0.954 0.956 0.960 0.877 0.941 Connectivity + Dissimilarity + Size 0.913 0.941 0.959 0.879 0.941 Connectivity + Faults + Pairwise 0.944 0.954 0.964 0.867 0.932 Connectivity + Faults + Size 0.954 0.955 0.959 0.876 0.947 Connectivity + Faults + VCoverage 0.953 0.955 0.959 0.858 0.925 Connectivity + Pairwise + Size 0.937 0.954 0.962 0.870 0.937 Connectivity + Size + VCoverage 0.908 0.936 0.959 0.881 0.954 Dissimilarity + Faults + Pairwise 0.944 0.955 0.959 0.871 0.947 Dissimilarity + Faults + Size 0.953 0.955 0.959 0.875 0.938 Dissimilarity + Faults + VCoverage 0.953 0.956 0.964 0.876 0.947 Dissimilarity + Pairwise + Size 0.940 0.954 0.959 0.868 0.944 Dissimilarity + Size + VCoverage 0.913 0.941 0.957 0.873 0.936 Faults + Pairwise + Size 0.942 0.955 0.959 0.863 0.937 Faults + Pairwise + VCoverage 0.944 0.954 0.958 0.866 0.938 Faults + Size + VCoverage 0.953 0.956 0.959 0.874 0.931 Pairwise + Size + VCoverage 0.941 0.954 0.959 0.877 0.938 Average 0.934 0.949 0.959 0.873 0.940 Table 11: APFD values achieved by functional and non-functional prioritization objectives 17 ACCEPTED MANUSCRIPT ACCEPTED MANUSCRIPT Mixed Multi-Objective Functional Objectives Non-Functional Objectives Connectivity Dissimilarity Pairwise VCoverage Changes Faults Size Changes + Connectivity 0.550 0.639 0.902 0.588 0.693 0.124 0.596 Changes + Dissimilarity 0.518 0.614 0.906 0.573 0.671 0.118 0.563 Changes + Pairwise 0.814 0.893 0.993 0.856 0.899 0.298 0.858 Changes + VCoverage 0.530 0.633 0.954 0.571 0.701 0.131 0.583 Connectivity + Faults 0.924 0.967 1.000 0.946 0.948 0.556 0.966 Connectivity + Size 0.566 0.684 0.956 0.616 0.736 0.092 0.630 Dissimilarity + Faults 0.951 0.967 0.999 0.958 0.962 0.686 0.971 Dissimilarity + Size 0.455 0.553 0.879 0.481 0.601 0.108 0.497 Faults + Pairwise 0.885 0.947 0.997 0.914 0.931 0.418 0.931 Faults + VCoverage 0.936 0.964 0.999 0.949 0.956 0.589 0.972 Pairwise + Size 0.863 0.931 0.994 0.903 0.914 0.336 0.893 Size + VCoverage 0.542 0.631 0.924 0.584 0.685 0.101 0.580 Changes + Connectivity + Dissimilarity 0.534 0.634 0.939 0.570 0.681 0.128 0.578 Changes + Connectivity + Faults 0.918 0.961 0.998 0.938 0.944 0.509 0.953 Changes + Connectivity + Pairwise 0.877 0.939 0.995 0.907 0.921 0.370 0.911 Changes + Connectivity + Size 0.593 0.693 0.958 0.646 0.744 0.143 0.644 Changes + Connectivity + VCoverage 0.573 0.673 0.960 0.623 0.743 0.176 0.633 Changes + Dissimilarity + Faults 0.932 0.965 0.999 0.948 0.952 0.570 0.963 Changes + Dissimilarity + Pairwise 0.873 0.936 0.995 0.911 0.925 0.384 0.910 Changes + Dissimilarity + Size 0.541 0.639 0.963 0.589 0.728 0.121 0.600 Changes + Dissimilarity + VCoverage 0.677 0.761 0.970 0.731 0.812 0.189 0.730 Changes + Faults + Pairwise 0.910 0.948 0.996 0.930 0.941 0.471 0.942 Changes + Faults + VCoverage 0.926 0.963 0.999 0.944 0.950 0.554 0.964 Changes + Pairwise + Size 0.909 0.953 0.996 0.930 0.939 0.494 0.938 Changes + Pairwise + VCoverage 0.888 0.947 0.997 0.917 0.932 0.429 0.925 Changes + Size + VCoverage 0.573 0.682 0.943 0.620 0.729 0.093 0.625 Connectivity + Dissimilarity + Faults 0.940 0.963 0.999 0.956 0.959 0.624 0.973 Connectivity + Dissimilarity + Size 0.558 0.659 0.951 0.606 0.728 0.133 0.622 Connectivity + Faults + Pairwise 0.899 0.946 0.998 0.922 0.938 0.457 0.931 Connectivity + Faults + VCoverage 0.929 0.970 0.999 0.949 0.949 0.616 0.961 Connectivity + Faults + Size 0.934 0.964 1.000 0.948 0.954 0.577 0.968 Connectivity + Pairwise + Size 0.903 0.949 0.997 0.926 0.939 0.450 0.942 Connectivity + Size + VCoverage 0.521 0.626 0.919 0.548 0.665 0.144 0.570 Dissimilarity + Faults + Pairwise 0.915 0.957 0.998 0.934 0.942 0.496 0.947 Dissimilarity + Faults + Size 0.936 0.968 0.999 0.953 0.955 0.620 0.971 Dissimilarity + Faults + VCoverage 0.940 0.963 0.998 0.957 0.960 0.637 0.968 Dissimilarity + Pairwise + Size 0.895 0.950 0.998 0.921 0.931 0.391 0.926 Dissimilarity + Size + VCoverage 0.572 0.680 0.953 0.622 0.742 0.123 0.628 Faults + Pairwise + Size 0.914 0.958 0.999 0.938 0.946 0.479 0.953 Faults + Pairwise + VCoverage 0.905 0.951 0.997 0.930 0.938 0.442 0.935 Faults + Size + VCoverage 0.937 0.968 0.999 0.956 0.959 0.616 0.969 Pairwise + Size + VCoverage 0.887 0.946 0.997 0.914 0.931 0.447 0.932 Table 12: d A12 values for mono vs. multi–objective combinations of functional and non-functional objectives. Cells revealing very large statistical differences are highlighted in light grey (in favour of the row) and dark grey (in favour of the column). Values in boldface reveal statistically significant differences (the p-value with Holm’s correction is <0.05) 18 ACCEPTED MANUSCRIPT ACCEPTED MANUSCRIPT Mixed Multi-Objective Functional Multi-Objective Con+Dis Con+Pai Con+VCo Dis+Pai Dis+VCo Pai+VCo Con+Dis+Pai Con+Dis+VCo Con+Pai+VCo Dis+Pai+VCo Changes + Con 0.556 0.267 0.529 0.221 0.559 0.386 0.203 0.547 0.284 0.208 Changes + Dis 0.518 0.242 0.489 0.198 0.531 0.363 0.187 0.513 0.268 0.199 Changes + Pai 0.800 0.523 0.792 0.463 0.827 0.703 0.418 0.810 0.551 0.438 Changes + VCo 0.536 0.245 0.488 0.211 0.541 0.338 0.200 0.517 0.248 0.201 Con + Faults 0.900 0.738 0.921 0.713 0.938 0.893 0.667 0.909 0.753 0.683 Con + Size 0.573 0.242 0.534 0.189 0.580 0.388 0.168 0.571 0.271 0.178 Dis + Faults 0.915 0.823 0.947 0.811 0.956 0.919 0.778 0.924 0.803 0.769 Dis + Size 0.463 0.208 0.424 0.176 0.467 0.294 0.156 0.442 0.216 0.162 Faults + Pai 0.864 0.641 0.878 0.600 0.910 0.830 0.560 0.879 0.676 0.580 Faults + VCo 0.906 0.780 0.932 0.754 0.956 0.907 0.721 0.916 0.767 0.719 Pai + Size 0.834 0.571 0.849 0.519 0.878 0.790 0.473 0.854 0.637 0.503 Size + VCo 0.544 0.239 0.515 0.196 0.549 0.363 0.175 0.537 0.272 0.180 Changes + Con + Dis 0.528 0.253 0.492 0.220 0.540 0.367 0.198 0.519 0.270 0.214 Changes + Con + Faults 0.888 0.730 0.917 0.694 0.940 0.877 0.654 0.900 0.736 0.668 Changes + Con + Pai 0.849 0.618 0.864 0.563 0.896 0.798 0.508 0.869 0.651 0.543 Changes + Con + Size 0.602 0.281 0.559 0.238 0.606 0.420 0.217 0.592 0.318 0.227 Changes + Con + VCo 0.585 0.293 0.540 0.256 0.586 0.394 0.244 0.573 0.299 0.237 Changes + Dis + Faults 0.898 0.758 0.927 0.736 0.947 0.898 0.688 0.908 0.761 0.701 Changes + Dis + Pai 0.849 0.621 0.864 0.570 0.896 0.802 0.524 0.865 0.648 0.543 Changes + Dis + Size 0.557 0.224 0.497 0.189 0.548 0.323 0.181 0.526 0.231 0.171 Changes + Dis + VCo 0.674 0.373 0.645 0.319 0.690 0.517 0.296 0.669 0.389 0.298 Changes + Faults + Pai 0.877 0.708 0.902 0.672 0.933 0.854 0.622 0.890 0.707 0.643 Changes + Faults + VCo 0.901 0.754 0.933 0.735 0.946 0.898 0.687 0.912 0.761 0.705 Changes + Pai + Size 0.876 0.706 0.900 0.662 0.924 0.848 0.624 0.893 0.716 0.634 Changes + Pai + VCo 0.859 0.650 0.874 0.603 0.906 0.823 0.549 0.876 0.678 0.580 Changes + Size + VCo 0.581 0.242 0.549 0.189 0.590 0.395 0.171 0.585 0.277 0.171 Con + Dis + Faults 0.911 0.798 0.944 0.783 0.957 0.914 0.742 0.922 0.780 0.745 Con + Dis + Size 0.570 0.268 0.520 0.227 0.569 0.388 0.213 0.554 0.278 0.215 Con + Faults + Pai 0.868 0.689 0.891 0.645 0.920 0.844 0.604 0.887 0.700 0.619 Con + Faults + Size 0.906 0.772 0.935 0.753 0.954 0.909 0.713 0.917 0.770 0.722 Con + Faults + VCo 0.900 0.757 0.925 0.742 0.938 0.894 0.706 0.917 0.772 0.718 Con + Pai + Size 0.875 0.698 0.888 0.646 0.927 0.846 0.604 0.888 0.700 0.620 Con + Size + VCo 0.519 0.268 0.495 0.236 0.537 0.372 0.216 0.524 0.284 0.220 Dis + Faults + Pai 0.886 0.719 0.911 0.689 0.936 0.871 0.643 0.898 0.727 0.664 Dis + Faults + Size 0.907 0.779 0.941 0.764 0.951 0.907 0.723 0.917 0.779 0.734 Dis + Faults + VCo 0.909 0.792 0.936 0.779 0.950 0.906 0.736 0.917 0.777 0.738 Dis + Pai + Size 0.866 0.655 0.883 0.602 0.914 0.838 0.543 0.878 0.688 0.576 Dis + Size + VCo 0.584 0.257 0.540 0.213 0.588 0.399 0.199 0.578 0.284 0.198 Faults + Pai + Size 0.883 0.716 0.915 0.676 0.936 0.876 0.628 0.898 0.723 0.649 Faults + Pai + VCo 0.872 0.691 0.901 0.647 0.924 0.856 0.595 0.885 0.707 0.619 Faults + Size + VCo 0.908 0.783 0.937 0.765 0.950 0.910 0.729 0.923 0.780 0.737 Pai + Size + VCo 0.871 0.663 0.891 0.632 0.911 0.835 0.586 0.876 0.691 0.606 Table 13: d A12 values for combinations of functional objectives vs. mixed combinations of functional and non–functional prioritization objectives. Cells revealing very large statistical differences are highlighted using dark grey (in favour of the column) or light grey (in favour of the row). Values in boldface reveal statistically significant differences (the p-value with Holm’s correction is <0.05) 19 ACCEPTED MANUSCRIPT ACCEPTED MANUSCRIPT Mixed Multi-Objective Non-Functional Multi-Objective Changes + Faults Changes + Size Faults + Size Changes + Faults + Size Changes + Connectivity 0.098 0.549 0.087 0.116 Changes + Dissimilarity 0.100 0.517 0.093 0.110 Changes + Pairwise 0.239 0.807 0.222 0.273 Changes + VCoverage 0.117 0.543 0.105 0.126 Connectivity + Faults 0.470 0.924 0.438 0.514 Connectivity + Size 0.063 0.569 0.055 0.083 Dissimilarity + Faults 0.643 0.947 0.571 0.639 Dissimilarity + Size 0.078 0.451 0.072 0.095 Faults + Pairwise 0.343 0.882 0.318 0.391 Faults + VCoverage 0.555 0.932 0.473 0.548 Pairwise + Size 0.269 0.853 0.251 0.314 Size + VCoverage 0.083 0.535 0.073 0.094 Changes + Connectivity + Dissimilarity 0.113 0.528 0.100 0.118 Changes + Connectivity + Faults 0.454 0.917 0.408 0.480 Changes + Connectivity + Pairwise 0.290 0.865 0.269 0.350 Changes + Connectivity + Size 0.113 0.595 0.108 0.130 Changes + Connectivity + VCoverage 0.165 0.584 0.149 0.167 Changes + Dissimilarity + Faults 0.528 0.929 0.469 0.537 Changes + Dissimilarity + Pairwise 0.327 0.866 0.302 0.359 Changes + Dissimilarity + Size 0.122 0.547 0.101 0.113 Changes + Dissimilarity + VCoverage 0.166 0.680 0.136 0.173 Changes + Faults + Pairwise 0.443 0.904 0.392 0.446 Changes + Faults + VCoverage 0.505 0.929 0.458 0.523 Changes + Pairwise + Size 0.435 0.903 0.394 0.467 Changes + Pairwise + VCoverage 0.367 0.882 0.330 0.401 Changes + Size + VCoverage 0.077 0.578 0.067 0.088 Connectivity + Dissimilarity + Faults 0.598 0.941 0.535 0.589 Connectivity + Dissimilarity + Size 0.097 0.563 0.095 0.124 Connectivity + Faults + Pairwise 0.424 0.891 0.378 0.434 Connectivity + Faults + Size 0.548 0.933 0.476 0.546 Connectivity + Faults + VCoverage 0.565 0.929 0.520 0.578 Connectivity + Pairwise + Size 0.404 0.897 0.348 0.418 Connectivity + Size + VCoverage 0.111 0.521 0.106 0.134 Dissimilarity + Faults + Pairwise 0.444 0.913 0.403 0.469 Dissimilarity + Faults + Size 0.567 0.942 0.515 0.583 Dissimilarity + Faults + VCoverage 0.607 0.942 0.548 0.595 Dissimilarity + Pairwise + Size 0.295 0.884 0.279 0.364 Dissimilarity + Size + VCoverage 0.096 0.584 0.082 0.111 Faults + Pairwise + Size 0.419 0.914 0.373 0.452 Faults + Pairwise + VCoverage 0.388 0.901 0.348 0.419 Faults + Size + VCoverage 0.590 0.937 0.531 0.586 Pairwise + Size + VCoverage 0.388 0.893 0.359 0.434 Table 14: d A12 values for combinations of non-functional objectives vs. mixed combinations of functional and non–functional prioritization objectives. Cells revealing very large statistical differences are highlighted using dark grey (in favour of the column) or light grey (in favour of the row). Values in boldface reveal statistically significant differences (the p-value with Holm’s correction is <0.05) 20 ACCEPTED MANUSCRIPT ACCEPTED MANUSCRIPT 7.6. Experiment 4. Functional vs non–functional objectives In this experiment, we performed a further statistical analysis of the data obtained in previous experiments to measure the effect size on the comparison of functional objectives against non–functional objectives, both single and combined. Table 15 shows the values of the d A12 effect size. A majority of cells show d A12 values under 0.5 indicating that non-functional objectives are in general more effective than functional objectives for test case prioritization in HCSs. As observed in Experiment 2 and 3, the objective Faults, and those combinations including it consistently show the largest differences. Also, as observed in Experiment 1, the objective Pairwise is consistently outperformed by all non-functional objectives, but it provides the best results in favour of functional objectives when combined with others. 7.7. Experiment 5. Algorithm comparison In this experiment, we compared the performance of NSGA-II with a random search algorithm and a deterministic test case prioritization algorithm. The experimental setup and results of both comparisons are described in the following sections. 7.7.1. Comparison with Random Search The pseudo-code of our implementation of Random Search (RS) algorithm is described in Algorithm 1. The algorithm takes an input attributed feature model afm and returns a set of test suites optimizing the target objectives. The algorithm has two configuration parameters: the number of iterations to be performed nIterations, and the maximum size of the random test suites to be generated maxSize. We set maxSize to the ceiling for the average size of the pairwise suites generated by CASA (13 test cases). Regarding the value of nIterations, we set its values to 5000, in order to ensure a fair comparison with NSGA-II, which performs 50 iterations with a population of 100 individuals (50 ∗100 = 5000 evaluations). Three functions are invoked in the pseudo-code of Algorithm 1: i) randomSuite, that generates a suite of random size (between 1 and maxSize), comprising of random products generated using the PLEDGE tool [33]; ii) isNotDominated that checks if the solution sol provided as parameter is not dominated by any solution in the Pareto front estimation pFront; and iii) notDominated that returns the solutions from pFront that are dominated by sol. Table 16 shows the results of the comparison. For each group of objectives and algorithm under comparison, the table shows the execution time, average and maximum APFD value of the test suites in the Pareto front. The best values of each metric on each row are highlighted in boldface. As illustrated, NSGA-II outperforms RS in 58 out of the 63 combinations of objectives in terms of average APDF value. Interestingly, there is not a clear winner Algorithm 1 Random search algorithm 1: procedure RS(afm) 2: i←1 3: pFront ← {} 4: while i≤nIterations do 5: sol ←randomSuite(afm, maxSize) 6: if isNotDomiated(sol, pFront)then 7: pFront ←notDominated(pF ront, sol)Ssol 8: end if 9: i←i+ 1 10: end while 11: return pFront 12: end procedure in terms of execution time: RS was faster in 36 out of the 63 objective groups (57.2%) meanwhile NSGA-II achieved lower average execution times in 42.8% of the objectives. We found that the overhead in the RS algorithm was due to the cost of generating random valid test cases. In terms of fault detection, NSGA-II detected slightly more faults than RS. However, both algorithms detected more than 99.5% of the emulated faults and thus the differences are not significant. Table 7.7.1 shows the average, standard deviation and maximum values of the hypervolume achieved by each algorithm and objective group under comparison. The hypervolume is the n-dimensional space contained by a set of solutions with respect to a reference point [7]. The hypervolume metric is widely used to compare the performance of multi-objective algorithms, where solutions with a larger hypervolume provide a better trade-offs among objectives than solutions with a smaller hypervolume. The best values of each metric on each row are highlighted in boldface. NSGA-II provides better results for the majority of executions both in terms of average hypervolume (38 out of 63 objective sets) and maximum hypervolume (41 out of 63 objective sets). Interestingly, RS provides better results than NSGA-II for a fair percentage of objective sets. This is probably because NSGA-II mainly focuses on re-ordering the test cases in the initial population, while RS performs a wider exploration of the search space generating solutions with different (random) test cases. It is noteworthy, however, that a larger hypervolume does not necessarily implies a better rate of fault detection, as observed in Table 16. In summary, NSGA-II outperforms RS in accelerating the detection of faults in HCSs since NSGA-II provides higher average and maximum APFD values, it usually generates Pareto fronts approximations with better hypervolumes, and both algorithms have similar executions times. 7.7.2. Comparison with a coverage-based prioritization algorithm For a further validation, we compared the results of our MOEA with the deterministic coverage-based prioritization algorithm for software product lines proposed by 21 ACCEPTED MANUSCRIPT ACCEPTED MANUSCRIPT Functional Objectives Non-Functional Objectives Changes Faults Size Changes + Faults Changes + Size Faults + Size Changes + Faults + Size Connectivity 0.675 0.083 0.550 0.060 0.509 0.057 0.078 Dissimilarity 0.583 0.037 0.442 0.036 0.403 0.035 0.037 Pairwise 0.166 0.000 0.083 0.000 0.076 0.000 0.000 VCoverage 0.637 0.061 0.509 0.051 0.463 0.045 0.056 Connectivity + Dissimilarity 0.657 0.115 0.536 0.093 0.493 0.087 0.108 Connectivity + Pairwise 0.895 0.278 0.851 0.212 0.802 0.201 0.265 Connectivity + VCoverage 0.704 0.088 0.589 0.070 0.541 0.054 0.080 Dissimilarity + Pairwise 0.912 0.314 0.887 0.242 0.838 0.225 0.290 Dissimilarity + VCoverage 0.654 0.064 0.534 0.039 0.497 0.039 0.058 Pairwise + VCoverage 0.848 0.116 0.741 0.090 0.697 0.081 0.108 Connectivity + Dissimilarity + Pairwise 0.915 0.363 0.898 0.289 0.849 0.274 0.342 Connectivity + Dissimilarity + VCoverage 0.688 0.104 0.553 0.089 0.516 0.079 0.097 Connectivity + Pairwise + VCoverage 0.891 0.273 0.831 0.234 0.792 0.221 0.261 Dissimilarity + Pairwise + VCoverage 0.918 0.342 0.896 0.286 0.848 0.258 0.322 Table 15: d A12 values for functional vs. non–functional prioritization objectives. Cells revealing very large statistical differences are highlighted in dark grey (in favour of the column). Values in boldface reveal statistically significant differences (the p-value with Holm’s correction is < 0.05) S´anchez et al. [60]. The algorithm takes an attributed feature model afm as input, generates a pairwise suite from the model and re-arranges its products in descending order of pairwise coverage using bubble search. For the deterministic generation of a pairwise suite, we used the SPLCAT tool [38]. The pseudo-code of our implementation is described in Algorithm 2. Two functions are invoked in the pseudo-code of this algorithm: i) ICPL which represents the ICPL algorithm for generating pairwise suites as implemented by the tool SPLCAT, and cov that is equivalent to the PairwiseCoverage objective function defined in section 6 assuming that the suite has a single test case, specified as a parameter. Algorithm 2 Coverage-based prioritization algorithm 1: procedure PWCMax(afm) 2: suite ←ICP L(afm) 3: size ←size(suite) 4: repeat 5: swapped ←false 6: for i←2, size do 7: if cov(suite[i−1], afm)< cov(suite[i], afm)then 8: aux ←suite[i] 9: suite[i]←suite[i−1] 10: suite[i−1] ←aux 11: swapped ←true 12: end if 13: end for 14: until ¬swapped 15: return suite 16: end procedure The APFD value achieved by the coverage-based algorithm is 0.946, which is less than the average AFPD value of the best solution in the Pareto front found by NSGA-II for 38 out of the 63 objective sets, i.e. column “Avg Max” in Table 16. More importantly, NSGA-II achieved better results than the coverage-based algorithm in all the 40 executions for 29 out of the 63 objective sets. This means that, for almost half of the objective sets, our algorithm was always better than the coverage-based algorithm. It is noteworthy, however, that the differences between the APFD values of NSGA-II and the coverage-based algorithm are small, probably due to the size of the generated suites (13 test cases on average). We conjecture that these differences would be larger when dealing with bigger test suites (e.g. 3-wise), but this is something that requires further research. In terms of execution time, the coverage-based algorithm was executed in less than 2 seconds, which makes it appropriate when fast response times are required. 7.8. Discussion We now summarize the results and what they tell us about the research questions. RQ1: Mono vs. multi–objective prioritization using functional objectives. Experiment 1 revealed that multi–objective prioritization outperforms mono-objective prioritization when using functional objectives. The superiority was especially noticeable in the comparison with Pairwise as a single-objective, which consistently achieved the worse rate of fault detection. Interestingly, however, Pairwise performed very well when combined with other functional objectives. In the light of these results, RQ1 is answered as follows: Multi–objective prioritization using functional objectives is more effective than mono–objective prioritization with functional objectives in accelerating the detection of faults in HCSs. 22 ACCEPTED MANUSCRIPT ACCEPTED MANUSCRIPT NSGA-II Random Search Objectives Ex.Time Avg Avg Max Ex.Time Avg Avg Max Connectivity 77251.6 0.923 0.935 119627.9 0.911 0.915 Dissimilarity 75856.1 0.912 0.931 112480.8 0.885 0.894 Pairwise 1478882.8 0.880 0.880 714078.2 0.913 0.913 VCoverage 79107.7 0.888 0.933 102457.4 0.893 0.918 Connectivity + Dissimilarity 83767.4 0.912 0.937 106497.4 0.898 0.914 Connectivity + Pairwise 1421967.3 0.938 0.951 709398.8 0.933 0.952 Connectivity + VCoverage 78199.5 0.914 0.934 120115.3 0.891 0.899 Dissimilarity + Pairwise 1400685.8 0.941 0.952 715289.6 0.931 0.953 Dissimilarity + VCoverage 77182.5 0.916 0.936 128498.2 0.900 0.919 Pairwise + VCoverage 1453296.7 0.936 0.948 714764.8 0.927 0.952 Connectivity + Dissimilarity + Pairwise 1414754.9 0.929 0.954 711827.3 0.927 0.953 Connectivity + Dissimilarity + VCoverage 80922.4 0.906 0.929 111031.5 0.917 0.933 Connectivity + Pairwise + VCoverage 1434254.1 0.932 0.949 720098.3 0.928 0.953 Dissimilarity + Pairwise + VCoverage 1405714.7 0.938 0.952 715958.6 0.926 0.952 Changes 154553.9 0.902 0.915 255249.5 0.907 0.907 Faults 266983.7 0.955 0.955 311060.0 0.953 0.953 Size 147161.1 0.917 0.931 267076.5 0.917 0.917 Changes + Faults 267046.7 0.953 0.955 315937.0 0.933 0.954 Changes + Size 150685.2 0.918 0.942 250050.4 0.909 0.942 Faults + Size 266313.0 0.955 0.956 317911.9 0.941 0.954 Changes + Faults + Size 267405.4 0.951 0.955 319803.3 0.935 0.954 Changes + Connectivity 89517.2 0.916 0.939 134150.5 0.907 0.944 Changes + Dissimilarity 89095.0 0.907 0.939 143702.3 0.905 0.940 Changes + Pairwise 1174272.6 0.937 0.952 602875.9 0.928 0.951 Changes + VCoverage 86759.7 0.917 0.936 133983.3 0.906 0.950 Connectivity + Faults 248148.2 0.953 0.955 221543.1 0.944 0.954 Connectivity + Size 95670.1 0.915 0.944 134395.5 0.910 0.948 Dissimilarity + Faults 253215.6 0.954 0.955 219950.5 0.940 0.954 Dissimilarity + Size 85769.7 0.903 0.923 129575.3 0.913 0.946 Faults + Pairwise 1328146.5 0.943 0.954 681334.3 0.938 0.954 Faults + VCoverage 258827.7 0.955 0.956 211328.7 0.944 0.954 Pairwise + Size 1190707.6 0.942 0.953 608338.8 0.932 0.953 Size + VCoverage 82624.5 0.913 0.935 148241.0 0.908 0.950 Changes + Connectivity + Dissimilarity 90333.7 0.912 0.939 141020.4 0.899 0.947 Changes + Connectivity + Faults 242090.7 0.951 0.955 213817.3 0.932 0.955 Changes + Connectivity + VCoverage 91098.6 0.915 0.943 147589.7 0.904 0.942 Changes + Dissimilarity + Faults 258500.8 0.952 0.955 237274.7 0.932 0.954 Changes + Dissimilarity + VCoverage 79023.9 0.912 0.948 149348.8 0.887 0.946 Changes + Faults + Pairwise 1314596.2 0.942 0.954 685275.2 0.929 0.955 Changes + Faults + VCoverage 253188.5 0.952 0.955 227043.4 0.927 0.954 Changes + Pairwise + Connectivity 1159383.0 0.935 0.954 609231.8 0.926 0.954 Changes + Pairwise + Dissimilarity 1156172.8 0.935 0.953 608587.6 0.923 0.953 Changes + Pairwise + VCoverage 1154166.3 0.936 0.954 601289.3 0.924 0.954 Changes + Size + Connectivity 81688.1 0.911 0.939 131841.9 0.903 0.947 Changes + Size + Dissimilarity 87032.2 0.913 0.942 131280.7 0.913 0.950 Changes + Size + Pairwise 1185686.4 0.940 0.955 609731.4 0.925 0.955 Changes + Size + VCoverage 93134.0 0.908 0.940 138131.6 0.906 0.952 Connectivity + Dissimilarity + Faults 254147.6 0.954 0.955 232744.1 0.938 0.954 Connectivity + Dissimilarity + Size 77954.7 0.910 0.944 130562.3 0.902 0.945 Connectivity + Faults + Pairwise 1324924.1 0.942 0.954 689787.5 0.935 0.955 Connectivity + Faults + Size 254000.3 0.954 0.955 221594.3 0.925 0.954 Connectivity + Faults + VCoverage 245731.1 0.951 0.955 217372.5 0.941 0.954 Connectivity + Size + Pairwise 1167713.3 0.938 0.955 604217.1 0.924 0.955 Connectivity + Size + VCoverage 83282.2 0.914 0.944 156937.0 0.904 0.951 Dissimilarity + Faults + Pairwise 1324060.1 0.945 0.955 677402.6 0.929 0.954 Dissimilarity + Faults + Size 243985.7 0.952 0.955 226250.4 0.931 0.954 Dissimilarity + Faults + VCoverage 251145.3 0.952 0.955 225094.4 0.934 0.954 Dissimilarity + Pairwise + Size 1130349.7 0.942 0.954 607200.3 0.927 0.953 Dissimilarity + Size + VCoverage 95906.8 0.912 0.945 137942.8 0.906 0.949 Faults + Pairwise + VCoverage 1299913.7 0.944 0.955 682123.5 0.935 0.954 Faults + Pairwise + Size 1315391.8 0.942 0.955 686569.3 0.939 0.954 Faults + Size + VCoverage 246233.0 0.953 0.956 218511.5 0.924 0.955 Pairwise + Size + VCoverage 1169411.1 0.939 0.955 603278.3 0.923 0.953 Average 552301.4 0.930 0.946 351709.2 0.920 0.945 Table 16: APFD values and execution times achieved by NSGA-II and Random Search (40 executions in total). 23 ACCEPTED MANUSCRIPT ACCEPTED MANUSCRIPT NSGA-II Random Search Objective Avg HV StdDev HV Max HV Avg HV StdDev HV Max HV Connectivity 0.062 0.031 0.144 0.026 0.007 0.060 Dissimilarity 0.055 0.024 0.129 0.036 0.006 0.050 Pairwise 0.151 0.003 0.157 0.318 0.004 0.324 VCoverage 0.062 0.026 0.115 0.021 0.003 0.033 Connectivity + Dissimilarity 0.103 0.040 0.166 0.068 0.014 0.107 Connectivity + Pairwise 0.217 0.034 0.303 0.349 0.006 0.360 Connectivity + VCoverage 0.108 0.047 0.206 0.049 0.010 0.071 Dissimilarity + Pairwise 0.206 0.032 0.261 0.355 0.008 0.374 Dissimilarity + VCoverage 0.109 0.039 0.185 0.060 0.010 0.089 Pairwise + VCoverage 0.218 0.026 0.257 0.344 0.007 0.364 Dissimilarity + Pairwise + VCoverage 0.269 0.049 0.356 0.379 0.009 0.396 Connectivity + Dissimilarity + Pairwise 0.281 0.062 0.428 0.379 0.010 0.398 Connectivity + Dissimilarity + VCoverage 0.167 0.062 0.297 0.083 0.012 0.105 Connectivity + Pairwise + VCoverage 0.278 0.052 0.393 0.372 0.014 0.407 Changes 0.110 0.025 0.178 0.082 0.008 0.103 Faults 0.157 0.017 0.188 0.166 0.015 0.201 Size 0.065 0.015 0.093 0.050 0.003 0.058 Changes + Faults 0.260 0.026 0.308 0.245 0.015 0.273 Changes + Size 0.169 0.044 0.299 0.133 0.009 0.160 Faults + Size 0.207 0.025 0.251 0.213 0.017 0.248 Changes + Faults + Size 0.305 0.040 0.404 0.290 0.019 0.330 Changes + Connectivity 0.168 0.039 0.304 0.113 0.009 0.137 Changes + Dissimilarity 0.165 0.038 0.291 0.115 0.008 0.131 Changes + Pairwise 0.245 0.028 0.311 0.386 0.008 0.400 Changes + VCoverage 0.173 0.037 0.266 0.106 0.007 0.124 Connectivity + Faults 0.214 0.041 0.309 0.197 0.019 0.254 Connectivity + Size 0.129 0.043 0.256 0.083 0.006 0.097 Dissimilarity + Faults 0.199 0.031 0.295 0.201 0.016 0.244 Dissimilarity + Size 0.111 0.028 0.179 0.087 0.009 0.106 Faults + Pairwise 0.293 0.019 0.360 0.435 0.012 0.470 Faults + VCoverage 0.204 0.040 0.298 0.194 0.023 0.249 Pairwise + Size 0.213 0.022 0.256 0.360 0.004 0.373 Size + VCoverage 0.124 0.033 0.196 0.077 0.004 0.092 Changes + Connectivity + Dissimilarity 0.212 0.054 0.385 0.147 0.014 0.182 Changes + Connectivity + Faults 0.317 0.044 0.416 0.273 0.019 0.315 Changes + Connectivity + Pairwise 0.324 0.039 0.415 0.418 0.009 0.433 Changes + Connectivity + Size 0.226 0.043 0.341 0.162 0.011 0.188 Changes + Connectivity + VCoverage 0.221 0.053 0.346 0.134 0.009 0.158 Changes + Dissimilarity + Faults 0.297 0.042 0.421 0.283 0.018 0.319 Changes + Dissimilarity + Pairwise 0.307 0.048 0.425 0.419 0.009 0.445 Changes + Dissimilarity + Size 0.211 0.041 0.303 0.164 0.009 0.181 Changes + Dissimilarity + VCoverage 0.212 0.040 0.334 0.145 0.012 0.189 Changes + Faults + Pairwise 0.374 0.034 0.452 0.499 0.012 0.530 Changes + Faults + VCoverage 0.303 0.043 0.391 0.271 0.017 0.303 Changes + Pairwise + Size 0.300 0.051 0.417 0.423 0.007 0.435 Changes + Pairwise + VCoverage 0.323 0.039 0.410 0.412 0.008 0.430 Changes + Size + VCoverage 0.226 0.051 0.364 0.160 0.009 0.183 Connectivity + Dissimilarity + Faults 0.256 0.044 0.366 0.237 0.021 0.279 Connectivity + Dissimilarity + Size 0.166 0.046 0.249 0.115 0.012 0.138 Connectivity + Faults + Pairwise 0.340 0.054 0.444 0.462 0.014 0.489 Connectivity + Faults + Size 0.266 0.046 0.368 0.249 0.019 0.288 Connectivity + Faults + VCoverage 0.252 0.057 0.394 0.218 0.018 0.258 Connectivity + Pairwise + Size 0.281 0.053 0.388 0.391 0.007 0.410 Connectivity + Size + VCoverage 0.184 0.046 0.288 0.107 0.009 0.127 Dissimilarity + Faults + Pairwise 0.342 0.040 0.422 0.471 0.015 0.514 Dissimilarity + Faults + Size 0.265 0.044 0.435 0.251 0.020 0.282 Dissimilarity + Faults + VCoverage 0.248 0.058 0.403 0.231 0.020 0.290 Dissimilarity + Pairwise + Size 0.267 0.034 0.359 0.394 0.008 0.412 Dissimilarity + Size + VCoverage 0.166 0.030 0.215 0.113 0.010 0.157 Faults + Pairwise + Size 0.339 0.021 0.382 0.473 0.013 0.497 Faults + Pairwise + VCoverage 0.345 0.029 0.392 0.456 0.009 0.479 Faults + Size + VCoverage 0.263 0.045 0.375 0.246 0.017 0.273 Pairwise + Size + VCoverage 0.275 0.030 0.350 0.390 0.007 0.404 Table 17: Comparison of hypervolumes obtained by NSGA-II and Random Search. 24 ACCEPTED MANUSCRIPT ACCEPTED MANUSCRIPT Jose A. Parejo received his Ph.D. (with honors) from University of Sevilla in 2103, where he currenly works as Senior Lecturer of software engineering. He has worked in the industry as developer, architect and project manager from 2001 to 2007. His research interests include metaheuristic optimization and software engineering, focusing mainly on search-based software engineering. He serves regularly as reviewer for international journals and conferences. Ana B. Snchez received her Ph.D. (with honors) from University of Seville in May 2016. She has worked as a research assistant in the Applied Software Engineering research group (ISA, www.isa.us.es) at the University of Seville in the area of automated testing of highlyconfigurable systems. Contact her at [email protected]. Sergio Segura received his Ph.D. in Software Engineering (with honours) from Seville University, where he currently works as a Senior Lecturer. His research interests include software testing, software variability and search-based software engineering. He has co-authored some highly cited papers as well as tools used by universities and companies in various countries. He also serves regularly as a reviewer for international journals and conferences. Antonio Ruiz-Cortés is an accredited Full Professor and Head of the Applied Software Engineering research group at the University of Seville, in which he received his Ph.D (with honours). and M.Sc. in Computer Science. His research interests are in the areas of service oriented computing, software variability, software testing, and business process management. Further information about his publications, research projects and activities can be found at www.isa.us.es Roberto Erick Lopez-Herrejon is an Associate Professor at the Department of Software Engineering and Information Technology of the École de Technologie Supérieure of the University of Quebec in Montreal, Canada. Prior he was a senior postdoctoral researcher at the Johannes Kepler University in Linz, Austria. He was an Austrian Science Fund (FWF) Lise Meitner Fellow (2012– 2014) at the same institution. From 2008 to 2014 he was an External Lecturer at the Software Engineering Masters Programme of the University of Oxford, England. From 2010 to 2012 he held an FP7 Intra-European Marie Curie Fellowship sponsored by the European Commission. He obtained his Ph.D. from the University of Texas at Austin in 2006, funded in part by a Fulbright Fellowship. From 2005 to 2008, he was a Career Development Fellow at the Software Engineering Centre of the University of Oxford. His main expertise is in software customization, software product lines, and search based software engineering. [email protected] Department of Software Engineering and IT. École de Technologie Supérieure, (ÉTS), Notre-Dame Street Ouest. 1100, H3C 1K3. Montreal, Canada Alexander Egyed heads the Institute for Software Engineering and Automation at the Johannes Kepler University, Austria. He is also an Adjunct Assistant Professor at the University of Southern California, USA. Before joining the JKU, he worked as a Research Scientist for Teknowledge Corporation, USA (2000–2007) and then as a Research Fellow at the University College London, UK (2007–2008). He received a Doctorate degree in 2000 and a Master of Science degree in 1996, both in Computer Science, from the University of Southern California, USA under the mentorship of Dr. Barry Boehm. His research interests include software design modeling, requirements engineering, consistency checking and resolution, traceability, and change impact analysis. He is a member of ACM, ACM SigSoft, IEEE, and IEEE Computer Society.