Spectrum-based fault localization in software product lines

Spectrum-based fault localization in software product lines Aitor Arrieta ⁎,a , Sergio Segura b , Urtzi Markiegi a , Goiuria Sagardui a , Leire Etxeberria a a Mondragon Unibertsitatea, Mondragon, Spain b ETS Ingeniería Informática, Universidad de Sevilla, Spain Keywords: Software product lines Spectrum-based fault localization Feature models Debugging ABSTRACT Context: Software Product Line (SPL) testing is challenging mainly due to the potentially huge number of products under test. Most of the research on this field focuses on making testing affordable by selecting a representative subset of products to be tested. However, once the tests are executed and some failures revealed, debugging is a cumbersome and time consuming task due to difficulty to localize and isolate the faulty features in the SPL. Objective: This paper presents a debugging approach for the localization of bugs in SPLs. Method: The proposed approach works in two steps. First, the features of the SPL are ranked according to their suspiciousness (i.e., likelihood of being faulty) using spectrum-based localization techniques. Then, a novel fault isolation approach is used to generate valid products of minimum size containing the most suspicious features, helping to isolate the cause of failures. Results: For the evaluation of our approach, we compared ten suspiciousness techniques on nine SPLs of different sizes. The results reveal that three of the techniques (Tarantula, Kulcynski2 and Ample2) stand out over the rest, showing a stable performance with different types of faults and product suite sizes. By using these metrics, faults were localized by examining between 0.1% and 14.4% of the feature sets. Conclusion: Our results show that the proposed approach is effective at locating bugs in SPLs, serving as a helpful complement for the numerous approaches for testing SPLs. 1. Introduction Software Product Line (SPL) engineering focuses on the systematic development of related software products from a set of reusable features [1].Afeature is defined as any increment in product functionality [2]. Features and their possible interactions are commonly depicted in a feature model. A Feature Model (FM) represents all the possible products of a SPL in terms of features and constraints among them [3]. In this context, a product is a set of features satisfying all the constraints of the FM. Fig. 1 depicts a sample FM representing a simplified product line of mobile phones. Most SPL testing approaches focus on deriving and testing each product individually [4,5]. Since the number of potential products in a SPL is typically huge, several sampling techniques have been proposed to derive a manageable subset of products to be tested (e.g., [5–7]). Salient among them are Combinatorial Interaction Testing (CIT) techniques, whose goal is to select products where every combination of t features appears at least once, this is also called t-wise testing [8]. Another line of research addresses the problem of test case prioritization, where products are scheduled for testing in an order that attempts to increase their effectiveness at meeting some performance goal, typically detecting faults as soon as possible [9–12]. Both strategies, sampling and prioritization, are complementary and are often combined. Developing high-quality software requires not only effective testing methods to uncover failures, but also debugging techniques to locate and fix the bugs that trigger them. Debugging is mostly a manual process where testers must identify the defective code using techniques such as tracing, memory dumps or step-by-step execution. More sophisticated techniques include Spectrum-Based Fault Localization (SBFL), which ranks code components (e.g., statements) according to their probability of having faults, so-called suspiciousness [13–16]. Debugging SPLs is challenging due to the difficulty to find and isolate the faulty features in the SPL. Also, even if a suspicious feature or set of features are detected, it might still be difficult to generate small valid products (i.e., satisfying the constraints of the feature model) where the failure is reproduced and the defective assets can be pinpointed. Some works have proposed techniques based on machine ⁎ Corresponding author. E-mail addresses: [email protected] (A. Arrieta), [email protected] (S. Segura), [email protected] (U. Markiegi), [email protected] (G. Sagardui), [email protected] (L. Etxeberria). T learning to locate faults in configurable software in the past [17]. However, the recent advances on SPL testing contrast with the low number of studies that support SPL debugging, which remains a manual and time-consuming endeavour. In this paper, we propose an approach to SPL debugging. The approach works in two steps. First, the outcomes of testing (test coverage and test outputs) are used to rank features according to their probability of having faults, so-called suspiciousness score. The suspiciousness score of each feature (or set of features) is calculated using SBFL techniques adapted for the SPL domain. Then, a fault isolation approach is proposed to generate, by automatically analysing the feature model, products of minimum size containing the most suspicious features, in order to facilitate the isolation of the failure causes. A key contribution of our approach is the application of SBFL at the feature level (key atomic element in SPLs), rather than at the statement level, as in conventional SBFL approaches (e.g., [13,14,18–20]). In particular, we follow a model-based approach where the complexity of the code dependencies is managed through a simpler high-level representation of the features and the constraints among them: a feature model. This also permits to abstract the complexity of the underlying implementations such as the use of different programming languages or the combination of hardware and software features, e.g., cyber physical systems [21]. For the evaluation of the approach, we compared ten state-of-the-art SBFL techniques on nine SPLs of different sizes. Results reveal that SBFL performs well at locating faults in SPLs. More specifically, we found that three of the techniques under evaluation (Kulcynski2, Tarantula and Ample2) stand out over the rest, being able to localize the bugs by examining between 0.1% and 14.4% of the feature sets. This paper is structured as follows. Section 2 presents general background related to SPL engineering and SBFL. Section 3 presents our approach for fault localization in SPL and the fault isolation algorithm. An empirical evaluation of our approach is performed in Section 4. Section 5 highlights the main issues that threaten our empirical evaluation. Section 6 positions our work with the current literature. Section 7 concludes the study and highlights future work. 2. Background 2.1. Feature models Feature models (FMs) are the de-facto standard for modelling commonality and variability in SPLs [3,22]. Structurally, a feature model is a tree-like structure in which nodes represent features and edges represent constraints among the features. A feature represents an increment in product functionality [2]. Each feature is related to a set of assets that implement the feature’s functionality, i.e., code, documentation, test cases, etc. A product is a set of features satisfying the constraint of the feature model. Products are implemented by integrating the assets of the features that are part of them. Fig. 1 depicts a sample feature model representing a SPL of mobiles phones. Child features can be divided into mandatory and optional features. Mandatory features must be included in all the products including its parent feature, e.g., all mobile phones in Fig. 1 must provide support for Calls.Optional features can be optionally included in those products containing its parent feature, e.g., phones can optionally provide support for GPS. Additionally, child features can be grouped into alternative and or relationships. 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 product, e.g., phones can only support one type of screen: Basic,Colour or High resolution. Finally, in or relations at least one of the child features must be included in the products containing its parent feature, e.g., phones supporting media content must include the features Camera, MP3 or both of them. In addition to the parental relationships among features, feature models can include cross-tree constraints among features. Typical constraints model dependencies such as “Arequires B”, indicating the products containing the feature A must also include the feature B, or “A excludes B”, indicating that the features A and B cannot be part of the same product, i.e., they are incompatible features. In the example, phones including the feature Camera must include support for a High resolution screen. The analysis of feature models deals with the automated extraction of information from feature models. The analysis is performed in terms of analysis operations. Among others, these operations allow finding out whether a feature model is void (i.e., it represents no products) whether it contains errors (e.g., dead features) or what is the number of products represented by the model. Catalogues with up to 30 different analysis operations on feature models have been reported in the literature [22]. A number of tools support the analysis of feature models including FaMa [23], SPLAR [24] and FeatureIDE [25]. In the following, we define some of the terms that will be used throughout the rest of the paper. For the definitions, let Fbe the set of features in a feature model. •Feature set. Non-empty set of features S, S ⊆F, with |S|≥1, e.g., S= {Media,MP3}. •Configuration. A configuration is a 2–tuple of the form (S, R) such that S, R ⊆Fbeing Sthe set of features to be selected and Rthe set of features to be removed such that ∩= ⌀ SR and ∪=SR F .If S∪R⊂Fthe configuration is called partial configuration [22]. For instance, the following is a partial configuration of the model in Fig. 1: (S,R) = ({Media,MP3},{GPS}). •Product. A product is equivalent to a configuration where only selected features are specified and omitted features are implicitly removed [22], e.g., see products in Table 1. •Product suite. Set of products under test. Table 1 shows the set of products obtained when applying 2-wise testing to the model in Fig. 1. The product suite is reduced from 13 products (total number of products in the SPL) to 8 products containing all the possible feature pairs, 41 in total. •Core features. These are the set of features included in all the products of the SPL [22]. In the example the core features are Mobile phone,Calls and Screen. Fig. 1. Example of a product line from the mobile phone industry [22]. Table 1 Product suite (2-wise). ID Product P1 {MobilePhone, Screen, Calls, High resolution} P2 {MobilePhone, Screen, Calls, Colour, Media, MP3} P3 {MobilePhone, Screen, Calls, Colour, GPS} P4 {MobilePhone, Screen, Calls, High resolution, Media, MP3, Camera} P5 {MobilePhone, Screen, Calls, High resolution, Media, Camera, MP3, GPS} P6 {MobilePhone, Screen, Calls, Basic, Media, MP3} P7 {MobilePhone, Screen, Calls, Basic} P8 {MobilePhone, Screen, Calls, High resolution, Media, Camera} 2.2. Spectrum-based fault localization Spectrum-Based Fault Localization (SBFL) is a technique to assist on the location of program bugs [13,26]. SBFL uses the results of test cases and their corresponding code coverage information to estimate the risk of each program component (e.g., statements) of being faulty. A program spectrum refers to a collection of data that provides a specific view on the dynamic behavior of a software program such as statement or branch coverage [13,27]. Various forms of program spectra have been proposed [14]. For example, block-hit is a commonly used program spectra, where the program code is divided into statement blocks [26]. When SBFL with block-hit spectra is used, the result of the technique is an ordered list of code blocks sorted by their likelihood to cause the failure, so-called suspiciousness score. Table 2 illustrates an example of SBFL with block hit spectra in a C program. To avoid confusion, we remark that Table 2 illustrates an example of SBFL, but in our case we do not apply this technique at the code level, but at the feature level; for further information of the application of SBFL at the feature level, refer to Section 3.1. Horizontally, the table shows the five code blocks in which the program has been divided, i.e., the components. Note that the code has a bug in block b 3 . Vertically, the table shows four test cases of the program. For each test case (i.e., T 1 ,T 2 ,T 3 and T 4 ), a cell is marked with “•” if the program block of the row has been exercised by the test case of the column, creating what is known as the coverage matrix [18]. Additionally, the final row depicts the so-called error vector, which contains the outcome of each test case, either successful (“S”) or failed (“F”). Based on this information, the suspiciousness score of each block can be calculated using more than 30 different techniques proposed in the literature [15]. One of the most well-known techniques to calculate the suspiciousness score is named Tarantula, which, for a program component (in our example a statement block), is computed as follows [26]. =+ Suspiciousness Tarantula() N N N N N N CF F CF F CS S(1) where N CF is the number of failing test cases that cover the block, N F is the total number of failing test cases, N CS is the number of successful test cases that cover the block, and N S is the total number of successful test cases. The suspiciousness score of each block is in the range [0,1], i.e., the higher the suspiciousness score of the block, the higher the probability of having a fault. The values of N CF ,N CS ,N S ,N F and the Tarantula suspiciousness value of each code block are given in Table 2. The last column indicates the position of the statement in the suspiciousness-based ranking where top-ranked blocks are more likely to be faulty. In the example, the faulty block (b 3 ) is ranked first. Suspiciousness techniques may often provide the same value for different components, being these tied for the same position in the ranking, e.g., blocks b 2 ,b 4 , and b 5 in Table 2. Under this scenario, different approaches are applicable such as measuring the effectiveness in the best and worst scenarios, using an additional technique to break the tie, or using some simple heuristics such as alphabetical ordering [16]. 3. Approach In this section, we present a two-step approach for locating bugs in SPLs. First, SBFL-based techniques are used to calculate the suspiciousness of each feature set based on the testing outcomes, namely code coverage data and testing results (passes and failures). Second, the obtained suspiciousness scores are processed by a novel fault isolation approach to generate the smallest valid product containing the faulty feature set, helping to isolate the cause of the failure, and thus the bug causing it. We may recall that this paper focuses on debugging and not testing. Thus, we assume the existence of a product suite (e.g., pairwise suite) and their corresponding testing results, obtained using any state-of-the- art testing technique, e.g., manual integration test cases. Note that a key requirement for the application of SBFL is that multiple failed and multiple successful test cases are available [16]. In what follows, our approach is described in detail, including the overall methodology for its application. Table 2 An example showing the suspiciousness value computed using the Tarantula technique. ID Program block T 1 T 2 T 3 T 4 N CF N CS N S N F Suspiciousness Ranking b 1 int count n; ••••1 3 3 1 0.5 2 Ele *proc; List *src_queue, *dest_queue; if (prio >=MAXPRIO) { /*MAXPRIO=3*/ b 2 return; •0 1 310 3 } b 3 src_queue = prio_queue[prio]; •••1 2 3 1 0.6 1 dest_queue = prio_queue[prio + 1]; count = src_queue- > mem_count; if (count > 1) { /* BUG: It should be if (count >= 1) */ b 4 n= (int) (count*ratio + 1); •• 0 2 310 3 proc = find_nth(src_queue,n); if (proc) { b 5 src_queue = del_ele(src_queue,proc); •• 0 2 310 3 proc- > priority = prio; dest_queue = append_ele(dest_queue,proc); } } Execution results SSSF •Propagate operation. This operation (also called dependency analysis operation [22]) receives a partial configuration as input, and it automatically selects and unselects the necessary features to create a valid product according to the constraints of the model (if such product exists). For example, suppose that we run the propagate analysis operation on the selected features {GPS, Camera}. The operation would propagate the decisions returning the product {Mobile Phone, Calls, Screen, High resolution, Media, Camera, GPS}. Notice that the product includes the core features, plus the features Media and High resolution (both required by Camera). 20 3.1. Spectrum-based fault localization in SPLs We propose to adapt SBFL techniques to measure the suspiciousness score of each feature set in a SPL. Fig. 2 depicts the overview of the approach from a black-box perspective. Our approach receives a feature model and a product suite as inputs, and it returns a ranking of all the feature sets in the SPL, ordered by their suspiciousness value in descendent order, according to a given suspiciousness technique, e.g., Tarantula. The process to calculate the suspiciousness scores and to break ties in the final ranking is detailed next. 3.1.1. Constructing the coverage matrix and error vector Based on the SBFL theory (explained in Section 2.2), we consider the SPL products under test as the test cases, and the feature sets as the components where faults must be located. As an example, consider the feature model in Fig. 1 and the product suite in Table 1.Table 3 depicts the coverage matrix, where the products under test are placed in columns, and the feature sets are listed in rows (note that a bug is simulated in the feature MP3). For the sake of simplicity, only feature sets composed of one or two features are considered, although the approach could be generalized to feature sets of any size. In the example, only some feature pairs are shown to keep this paper at a reasonable size. For each product under test (i.e., P 1 ,P 2 , ... , P 8 ), a cell is marked with “•” if it contains the feature set of the row. Additionally, the final row depicts the error vector, that is, the test outcome of each product, either successful (“S”), if all the test cases associated to the product passed, or failed (“F”), if at least one of the test failed. We may recall that test cases related to each product can be executed using any state-of-the-art testing technique, e.g., ASTERYSCO for CPS product lines [21]. Also, we reiterate that an underlying assumption in SBFL is that multiple failed and multiple successful test cases are available [16]. Based on the information collected in the coverage matrix and the error vector, the suspiciousness score of each feature set can be calculated using any of the state-of-the-art suspiciousness techniques proposed in the literature [15]. To this purpose, we propose a slight modification of the meaning of the classical notation used in SBFL formulas, where test cases are replaced by products and components are replaced by feature sets, namely: Table 3shows the values of N CF ,N CS ,N F and N S for each feature set. Based on this information, the suspiciousness of each feature set using Tarantula is depicted in the column “Suspiciousness”, followed by the position of each feature set in the ranking. As illustrated, the feature sets MP3 (where a fault was seeded) and MP3-Colour are placed at the top of the ranking, followed by Media and Camera, with a suspiciousness score of 0.8 and 0.75 respectively. The rest of single features have a suspiciousness score of 0.5 according to Tarantula. Finally, the feature set GPS-Colour has a suspiciousness score of 0. 3.1.2. Breaking ties The last column in Table 3 indicates the suspiciousness ranking of each feature set. As illustrated, the suspiciousness score of some feature sets are identical. We have taken three different strategies to break ties: •Core features: If a core feature is faulty, all products will fail, and thus, for some techniques (e.g., Tarantula) all the feature sets will have the same suspiciousness score. If this occurs, our SBFL approach places core features at the top of the suspiciousness ranking. Notice that this does not happen with all techniques (e.g., Wong). •Feature interactions: Faults in isolated features may distort feature groups suspiciousness scores. Take as an example the simulated fault in MP3. All feature sets including the feature MP3 will fail, which will result, for some techniques (e.g., Tarantula), in all feature sets including MP3 having the same suspiciousness score, e.g., the Tarantula scores of MP3 and MP3-Colour in Table 3 are equal. Under this scenario, when a feature set Shas the same suspiciousness that any of its feature subsets S′⊂S, then S′is ranked over S. •Parental relations: If a parent feature is faulty, all the products containing one or more of its subfeatures will also be faulty, since parent and child features must appear together in products. Hence, for instance, a bug in the feature Media would make all the products including any of its child features to fail, that is, those including Camera,MP3, or both. To address this issue, when a parent feature has the same suspiciousness score as its child features, the parent feature is ranked first. All ties obtained after applying the previous strategies are broken randomly. We remark, however, that other strategies would also be feasible and studying their effectiveness remains for future work. Fig. 2. Overview of our approach on SBFL for SPL. Table 3 An example showing the suspiciousness value computed using the Tarantula technique in the Mobile Phone SPL. ID Feature Set P 1 P 2 P 3 P 4 P 5 P 6 P 7 P 8 N CF N CS N F N S Suspiciousness Ranking F 1 MobilePhone ••••••••4 4 4 4 0.5 5 F 2 Screen ••••••••4 4 4 4 0.5 5 F 3 Calls ••••••••4 4 4 4 0.5 5 F 4 High resolution ••••2 2 4 4 0.5 6 F 5 Basic •• 1 1 4 4 0.5 6 F 6 Colour •• 1 1 4 4 0.5 6 F 7 GPS •• 1 1 4 4 0.5 6 F 8 Media • ••• •4 1 4 4 0.8 3 F 9 Camera •• •2 1 4 4 0.75 4 F 10 MP3 (BUG)• ••• 40441 1 F 11 GPS-Colour •01440 7 F 12 MP3-Colour •10441 2 Execution results S F S FFFSS NCF number of failed products that cover a feature set. NUF number of failed products that do not cover a feature set. NCS number of successful products that cover a feature set. NUS number of successful products that do not cover a feature set. N C total number of products that cover a feature set. NU total number of products that do not cover a feature set. N S total number of successful products. NF total number of failed products. 21 3.2. Fault isolation Even if we have a list of the most suspicious feature sets, it could still be challenging to find a product, hopefully as small as possible, where the fault can be easily located. This is the goal of techniques like delta-debugging [28], which aims to generate minimal inputs inducing the failure in the program under test (see related work section). Based on this idea, in this section, we present a debugging approach for the isolation of bugs in SPLs. The goal is to generate a minimal product, in terms of number of features, where the fault(s) can be easily located. For the generation of the product, we leveraged advanced tools for the automated analysis of feature models. More specifically, we used the analysis operations on feature models integrated into the tool SPLAR [24]. The overall overview of the approach for generating the minimal product is depicted in Fig. 3. The debugging approach receives a suspicious feature set (FS), a feature model (with a set of features F), and the failing product being debugged (P) as inputs. Then, a partial configuration is created in three steps, namely: (1) unselect the features that are not part of the product being debugged, (2) select the core features (C), and (3) select the features in the suspicious feature set (out of the remaining features). Formally, let Sand Rbe the sets of selected and removed features in the partial configuration respectively. The partial configuration is defined as follows. ∀∈ ∉ ⇒ ∈ ∧ ∈⇒∈∧ ∈⇒∈ fF fP fR fC fS fFS fS • (2) The partial configuration is then provided as an input to the propagate operation, which generates a minimal valid product including the suspicious feature set. It is noteworthy that the minimal product generated is composed of a subset of the features in the product being debugged, and thus no new features are considered, which could result in unexpected results, e.g., new faults being introduced. Continuing with the previous example, let us assume that the feature MP3 has the highest suspiciousness score, and P5 = {MobilePhone,Screen,Calls,High resolution,Media, Camera,MP3,GPS} is the faulty product being debugged. A partial configuration would be created by unselecting the features not contained in the product (Colour,Basic), selecting the core features (Mobile phone,Calls,Screen), and selecting the suspicious feature set (MP3). This configuration would be then provided as input to the propagate operation, together with the feature model and the product under debug (i.e., P5). The propagation function would return the following product {Mobile phone,Calls,Screen,High resolution,Media,MP3}. Note that the features Media and High resolution are automatically selected, whereas the feature GPS is not selected. On the one hand, the feature Media would be included because it is the parent feature of the MP3 feature. On the other hand, the feature High resolution is selected because the product under debug employs this feature as an alternative child of the Screen feature, which is one of the core features of the product line. We may remark that the products generated by the propagate operation are always minimal, i.e., only those features strictly necessary to make a valid product are selected. Therefore, the debugger is provided with the smallest product including the suspicious feature set, contributing to reduce the effort required to locate the bug. The reason for proposing an incremental approach instead of a decremental approach is complexity. Minimizing a product is an exponential problem: given a product P with t features, the potential number of sub-products of P (products composed of a subset of the features of P) is −2 1 t . Of course, not all feature combinations are valid and, thus, the feature model must be taken into account, which includes further constraints. In addition to this, a decremental approach may require re-testing many large products until finding the faulty feature (s). Instead, the incremental approach proposed would be faster since it requires a single SAT propagation and, more importantly, it guarantees that a minimal product is generated. As a further benefit, the generated products are as small as possible (since they only include the core features and the first suspicious feature set in the ranking), which is good in the case that several iterations are needed before locating the faulty feature sets (i.e., a product with less features requires less test effort [29,30]). 3.3. Methodology Fig. 4 depicts the overall methodology to apply our SPL debugging approach. First, the suspiciousness scores of each feature sets are calculated based on the coverage information and test results, as explained in Section 3.1. Then, for each faulty product, the most suspicious feature set is selected and a minimal product is generated and tested. We reiterate that the tests can be performed using any state-of-the-art testing technique and it is out of the scope of this paper. If the test Fig. 3. Overview of our approach for fault isolation in SPL. Fig. 4. Overview of the methodology for SPL fault isolation. features GPS and MP3. In addition to the fault simulator, we developed a test system to simulate the test outcomes of each product using a simple oracle: if a product contains any of the features labelled as faulty, the execution of the product is classified as failed, otherwise it is classified as successful. This is an intuitive approach that assumes that the test cases of each product are good enough to reveal failures in the products under test. Note that this is a key requirement for the application of SBFL: if test cases are not able to identify failures, they will certainly not be helpful in identifying faults. Both, the fault simulator and the test system, have been previously used in the literature [11]. As for the UAV case study, the experiments were performed employing a Simulink model in charge of simulating the UAV. We employed a test suite composed of 120 test cases. A test case in our case was a set of signals stimulating the inputs of the SUT over a specific amount of time. The test execution time for each test case lasts from 30 s to 3000 s. 1 Furthermore, we employed mutation testing to simulate faults. Mutation testing was employed since it has been demonstrated to be a good substitute of real faults [42]. For each fault in a specific feature set, a mutant was created, performing the mutation in one of the assets of that feature sets. This mutant was later selected when a product included the faulty feature set. We employed the mutation operators proposed by Hanh et al. for Simulink models [43]. To speed up the evaluation process, we prioritized the test cases with an additional greedy algorithm that used historical data of the test cases. This algorithm demonstrated to be effective in a previous work at detecting faults as fast as possible [32]. Since SBFL only uses information whether the test execution passed or failed, once the test cases detected a fault, the test execution was stopped with the aim of speeding up the evaluation process. 4.2.3. Suspiciousness techniques We assessed the effectiveness of ten state-of-the-art suspiciousness techniques for the isolation of faults in SPLs. The chosen techniques were Tarantula, Ochiai, Dstar, Naish2, Wong and Russel-Rao, as proposed in [26]. We also included Kulcynski2, Arithmetic mean, Ample2 and M2, as they showed promising results in preliminary experiments [15]. The algebraic form of the chosen techniques are shown in Table 5 using the notation presented in Section 3.1. In the Dstar technique’s formula, the * is an exponent of N CF . We set * equal to 2 based on the original paper [20] and other relevant ones (e.g., [19]). 4.2.4. Evaluation metrics The following metrics were used to measure the effectiveness of the approach. Percentage of examined features (EXAMF). The EXAM score is one of the most common metrics to evaluate the effectiveness of fault localization techniques [16,19,44,45]. It is calculated as the number of statements examined with respect to the total number of statements in the program. In our approach, the number of statements examined Table 4 Subject feature models. Case study Features CTC Products 2-wise 3-wise Drupal V3 21 9 96,768 11 37 Weather station 23 2 1056 14 40 Eclipse 29 3 983,150 17 54 Android 45 5 36,240 18 67 UAV 46 4 2.3E6 22 74 Dell Laptop 47 109 2319 47 142 Arcade 62 35 3.3E9 18 65 HIS 68 4 6400 12 41 Model transformation 88 0 1.6E13 28 133 1 Notice that this is the simulated test execution time. outcome is successful, the next most suspicious feature set is selected and another minimal product is generated. Conversely, if the product fails, the suspicious feature set is reported to the engineer to fix it. This process is repeated until all faults have been fixed. Notice that every time a faulty product is selected, the tests must be executed again to confirm that the product is still buggy, since the faults could have been fixed while debugging previous products. Finally, it is noteworthy that the calculation of the suspiciousness scores is only performed once, unlike related approach where it is calculated every time a bug is fixed [31]. Although this may affect the accuracy of our approach, we believe that this is a sensible strategy for SPLs where re-executing all the tests is usually very costly [12,29,32]. 4. Evaluation 4.1. Research questions In order to evaluate the effectiveness of feature-based SBFL in SPLs we aim to answer the following Research Questions (RQs): RQ1: What is the effectiveness of different state-of-the-art suspiciousness techniques at isolating the causes of failures in SPLs? RQ2: How the size of the product suite affects the performance of the techniques under study? RQ3: How the number and type of faults (single or interaction) affect the performance of the techniques under study? 4.2. Experimental design 4.2.1. Subject models and product suites We selected nine feature models representing SPLs of different sizes for the evaluation. Seven of the models were taken from the SPLOT repository [24]. Furthermore, we used the feature model of the Drupal framework, a realistic case study to evaluate variability testing techniques proposed by Sanchez et al. [33]. Additionally, we included a case study of an Unmanned Aerial Vehicle (UAV) that we previously used in other evaluations (e.g., [21,30,34]). For each subject model, the SPLCAT tool [35] was used to generate two product suites using 2-wise and 3-wise coverage criteria [36]. Table 4 depicts the characteristics of the selected models including number of features, number of cross-tree constraints (CTCs), total number of products, and number of products in the 2-wise and 3-wise product suites respectively. 4.2.2. Fault seeding and test execution We faced two obstacles in the selection of case studies for the evaluation of our approach. First, we found a lack of case studies with available feature models, source code, and test cases. Second, based on our experience with industrial partners [37], the execution of test cases in real setting is usually a time-consuming process, which hinders the use of real test cases in a large-scale evaluation as the one required in our paper. To address both obstacles, we resorted to a fault simulator in eight of the subject case studies (where no code nor test cases were available), as previously done in related papers [9,11,38–40]. Additionally, we used a real-world case study with available feature model, source code and test cases (Unmanned Aerial Vehicle), in order to evaluate the approach in realistic settings. For the simulation of faults (in all case studies except UAV), we developed a fault generator to simulate different number and types of faults in the SPLs under test. The fault generator is based on the one proposed by Ensan et al. [38] and it has been used in several works to evaluate the fault detection rate of SPL test suites (e.g., [11,38,41]). The fault generator simulates faults in single features as well as faults caused by the interaction of two features. More specifically, our generator receives a feature model as an input and returns a random list of faulty feature sets as an output. For instance, the following list simulates two faults in the SPL in Fig. 1:{{Colour}, {GPS, MP3}}, a fault in the feature Colour and another fault caused by the interaction of the could be intuitively substituted by the number of feature sets examined, and the total number of statements by the total number of features sets. Given a product pbeing debugged and a faulty feature set f, we propose a variant of the EXAM score, called EXAMF, calculated as follows: =× E XAMF p f NF NF ( , ) 100 % f p(3) Where NF f is the number of feature sets examined to isolate the fault in f, and NF p is the total number of feature sets in p. Since we are aiming at faults caused by a single feature or interaction between two features, NF p is equal to all the valid possible combinations of one or two of the features of p. This was calculated using the SPLCAT tool. The lower the EXAMF score is, the more effective is the technique. As an example, consider a fault in the feature MP3, and P5 = {MobilePhone,Screen,Calls,High resolution,Media, Camera,MP3,GPS} the faulty product being debugged. Let us suppose that GPS is the most suspicious feature and MP3 the second most suspicious feature, according to a certain technique. Accordingly, the debugger would examine first the GPS feature, proceeding later to examine the MP3 feature. Considering that the total number of valid feature sets (i.e., single features and pairs of features) in P5 is 28, this metric is calculated as =×= E XAMF P MP( 5, { 3}) (2/28) 100 7.1 4 . This means that 7.14% of the feature sets in P5 had to be examined in order to locate the fault in MP3. The EXAMF metric measures the effectiveness of a fault localization technique at detecting a single fault. In the cases where several faults are present, the effectiveness of each fault localization technique was evaluated as the average EXAMF score. Thus, the average EXAMF score for multiple faulty feature sets Fin a product pthat is being debugged is calculated as follows: ∑=EXAMF p F F (, ) i Fi 1 (4) As an example, let us suppose two faults in the MP3 and GPS features, and P5 the faulty product being debugged. Let us suppose that 4 feature sets were examined before isolating the fault in MP3, and 5 feature sets were checked before isolating the bug in GPS, i.e., =×= E XAMF P MP( 5, { 3}) (4/28) 100 14.2 and E XAMF P G(5,{ =×= P S}) (5/28) 100 17. 8 . The average EXAMF is calculated as += ( 14.2 17.8)/2 1 6 . That is, 16% of the feature sets need to be examined on average to locate each faulty feature set in P5. 4.2.5. Experiments In order to answer our research questions, we performed five independent experiments with different number and types of simulated faults. Each experiment was conducted on the subject models depicted in Table 4 assessing the effectiveness of the ten suspiciousness techniques depicted in Table 5.Table 6 shows the number of simulated faults in single and pairs of features in each experiment. As proposed by Sanchez et al. [11], the maximum number of faults in each model was set to n/10, being nthe number of features in the SPL. For the fifth experiment, where faults due to single features and interaction of two features are combined, the distribution of the simulated faults was the same for both type of faults, as proposed in [11]. For each experiment and case study, five different distributions of faults were randomly generated, so-called test scenarios, in order to calculate averages. In total, 40 different test scenarios were run on each experiment and product suite: 8 case studies × 5 test scenarios. 4.3. Experimental results 4.3.1. Experiment 1: a fault in a single feature This experiment aims at evaluating the approach when the SPL has one fault in a single feature. Tables 7 and 8report the EXAMF values of each suspiciousness technique under evaluation on the data collected from the 2-wise and 3-wise product suites respectively. The best value on each column is highlighted in boldface. We reiterate that the shown values are the average of five different scenarios with a randomly simulated fault on each of them. The EXAMF score ranged between 0.07% and 7.6% for the 2-wise product suite, and between 0.07% and 8.43% for the 3-wise suite. That is, both product suites yielded similar results, with only slight differences in favor of the 2-wise suite. This means that having more test data information was not necessarily helpful in this experiment. The performance of all the techniques was consistent in all the case studies, and in both product suites. The faulty feature was successfully ranked as the most suspicious feature in 100% of the test scenarios for Ample2, Dstar, Kulcynski2, M2, and Ochiai, i.e., these were the techniques showing the best performance. In the case of Tarantula, the most suspicious feature was ranked first in 98% (88 out of 90) of the test scenarios. The technique performing worst was Arithmetic mean, followed by Naish2, Russel-Rao, and Wong. 4.3.2. Experiment 2: multiple faults in single features This experiment evaluates the approach when the SPL contains multiple faults in two or more single features. Tables 9 and 10 show the average EXAMF value of each technique under evaluation on the data collected from the 2-wise and 3-wise product suites respectively. As illustrated, the results obtained with the 3-wise suite (between 0.10% and 8.89%) were slightly better than those obtained with the 2-wise suite (between 0.22% and 12.38%). More specifically, the EXAMF Technique Equation Technique Equation Tarantula + NN NN NN / // CF F CS S CF F Russel–Rao +− + +− N NNNNNN CF CFFCFCSSCS Ochiai + N NN N() CF FCF CS Kulcynski2 + N NN CF UF CS Dstar −+ N NN N () * () CF FCF CS Arithmetic mean ×−× +×+++×+ NNNN NN NN NN NN 2( ) ()()()() CF US UF CS CF CS US UF CF UF CS US Naish2 −+− + N N NNN()1 CF CS CS S CS Ample2 +−+ N NN N NN CF CF F CS CS US Wong N CF M2 +− + − + N NNN NNN2( ) CF CF S CS F CF CS Table 6 Types of faults simulated in each experiment (n = number of features in the SPL). Experiment Single faults Interaction faults 11 0 2 [2, n/10] 0 30 1 4 0 [2, n/10] 5 [1, n/5] [1, n/5] Table 5 Algebraic form of the suspiciousness techniques under evaluation. values of the 3-wise suite outperformed those of the 2-wise suite in 69 out of the 90 measures (10 techniques × 9 case studies). This means that the use of more test data improved the performance of the fault isolation techniques in this particular experiment. Overall, the technique performing best with both product suites was Tarantula, followed by Kulcynski2, and Ample2. Conversely, Russel- Rao, Wong and Naish2, which showed exactly the same results in all case studies, resulted in the techniques with worst performance in this experiment. Table 7 EXAMF scores obtained using the 2-wise product suite in Experiment 1. Best values on each column are highlighted in boldface. Technique Drupal V3 Weather St. Eclipse Android UAV Dell L. Arcade HIS Model T. Mean Ample2 1.24 1.20 1.04 0.30 0.31 0.77 0.14 0.07 0.12 0.58 Arithmetic M. 7.64 2.14 4.2 1.27 2.62 3.86 0.97 0.64 2.06 2.82 Dstar 1.24 1.20 1.04 0.30 0.31 0.77 0.14 0.07 0.12 0.58 Kulcynski2 1.24 1.20 1.04 0.30 0.31 0.77 0.14 0.07 0.12 0.58 M2 1.24 1.20 1.04 0.30 0.31 0.77 0.14 0.07 0.12 0.58 Naish2 1.73 1.20 1.94 0.30 0.36 1.71 0.24 0.16 0.34 0.88 Ochiai 1.24 1.20 1.04 0.30 0.31 0.77 0.14 0.07 0.12 0.58 Russel-Rao 1.73 1.20 1.94 0.30 0.36 1.71 0.24 0.16 0.34 0.88 Tarantula 1.24 1.20 1.17 0.30 0.31 0.77 0.14 0.07 0.12 0.59 Wong 1.73 1.20 1.94 0.30 0.36 1.71 0.24 0.16 0.34 0.88 Mean 2.03 1.29 1.64 0.34 0.56 1.36 0.25 0.15 0.38 0.90 Table 8 EXAMF scores obtained using the 3-wise product suite in Experiment 1. Best values on each column are highlighted in boldface. Technique Drupal V3 Weather St. Eclipse Android UAV Dell L. Arcade HIS Model T. Mean Ample2 1.92 1.11 0.91 0.29 0.31 0.76 0.13 0.07 0.10 0.62 Arithmetic M. 8.43 1.83 3.83 1.31 2.83 3.82 1.00 0.61 1.98 2.85 Dstar 1.92 1.11 0.91 0.29 0.31 0.76 0.13 0.07 0.10 0.62 Kulcynski2 1.92 1.11 0.91 0.29 0.31 0.76 0.13 0.07 0.10 0.62 M2 1.92 1.11 0.91 0.29 0.31 0.76 0.13 0.07 0.10 0.62 Naish2 2.48 1.11 1.73 0.29 0.36 1.71 0.24 0.16 0.28 0.93 Ochiai 1.92 1.11 0.91 0.29 0.31 0.76 0.13 0.07 0.10 0.62 Russel-Rao 2.48 1.11 1.73 0.29 0.36 1.71 0.24 0.16 0.28 0.93 Tarantula 1.92 1.11 0.99 0.29 0.31 0.76 0.13 0.07 0.10 0.63 Wong 2.48 1.11 1.73 0.29 0.36 1.71 0.24 0.16 0.28 0.93 Mean 2.74 1.18 1.46 0.39 0.58 1.35 0.25 0.15 0.34 0.94 Table 9 EXAMF scores obtained using the 2-wise product suite in Experiment 2. Best values on each column are highlighted in boldface. Technique Drupal V3 Weather St. Eclipse Android UAV Dell L. Arcade HIS Model T. Mean Ample2 3.27 1.37 6.26 0.90 0.77 1.11 1.27 0.60 1.42 1.88 Arithmetic M. 7.32 2.95 6.26 1.10 2.36 2.79 0.98 0.35 1.32 2.82 Dstar 3.74 1.41 11.50 3.00 3.42 2.04 2.98 0.89 4.99 3.78 Kulcynski2 3.10 1.21 3.74 0.40 0.46 0.98 0.49 0.22 0.39 1.22 M2 3.74 1.71 12.06 3.16 3.97 2.28 3.04 0.89 5.60 4.05 Naish2 4.59 2.01 12.38 3.33 4.57 2.54 3.10 0.94 5.79 4.36 Ochiai 3.58 1.41 10.13 2.48 2.69 1.40 2.66 0.89 3.89 3.23 Russel-Rao 4.59 2.01 12.38 3.33 4.57 2.54 3.10 0.94 5.79 4.36 Tarantula 3.10 1.21 3.59 0.37 0.46 0.98 0.49 0.22 0.36 1.20 Wong 4.59 2.01 12.38 3.33 4.57 2.54 3.10 0.94 5.79 4.36 Mean 4.16 2.73 9.07 2.14 2.78 1.92 2.12 0.69 3.53 3.12 Table 10 EXAMF scores obtained using the 3-wise product suite in Experiment 2. Best values on each column are highlighted in boldface. Technique Drupal V3 Weather St. Eclipse Android UAV Dell L. Arcade HIS Model T. Mean Ample2 2.1 1.10 1.67 0.72 0.62 1.12 1.14 0.34 0.80 1.06 Arithmetic M. 8.55 2.80 6.00 1.23 2.21 2.85 0.91 0.38 1.08 2.89 Dstar 3.66 1.20 7.14 2.65 2.66 2.23 2.91 1.22 4.41 3.12 Kulcynski2 2.50 1.10 1.33 0.34 0.29 0.95 0.38 0.10 0.22 0.80 M2 3.93 1.26 7.72 2.88 3.00 2.40 3.03 1.25 4.72 3.36 Naish2 4.13 1.66 8.89 3.09 3.36 2.60 3.10 1.27 5.24 3.71 Ochiai 2.61 1.10 5.37 2.20 1.91 1.47 2.62 1.11 3.55 2.43 Russel-Rao 4.13 1.66 8.89 3.09 3.36 2.60 3.10 1.27 5.24 3.71 Tarantula 2.50 1.10 1.21 0.31 0.29 0.95 0.38 0.10 0.20 0.78 Wong 4.13 1.66 8.89 3.09 3.36 2.60 3.10 1.27 5.24 3.71 Mean 3.82 1.46 5.71 1.96 2.11 1.98 2.07 0.83 3.07 2.56 4.3.3. Experiment 3: fault in a feature interaction This experiment evaluates the approach under the presence of one fault due to the interaction of two features. Tables 11 and 12 show the mean EXAMF value of each technique over the five test scenarios. As in the previous experiment, the results obtained with the 3-wise suite were significantly better than those obtained with the 2-wise suite. More specifically, the EXAMF values of the 3-wise suite outperformed those of the 2-wise suite in 82 out of the 90 measures. Interestingly, the mean EXAMF values were significantly higher (up to 47.57%) than those observed in the previous experiments, which suggests that, as expected, locating bugs caused by the interaction of features is harder than isolating bugs in single features. Also, analogously to Experiment 1, where a single fault was also simulated, the performance of the techniques was consistent across all the case studies showing identical conclusions for both product suites. More specifically, the techniques performing best were Ample2, Dstar, Kulcynski2, M2, and Ochiai, all of them with the same average score. Conversely, the technique Arithmetic mean performed significantly bad in comparison with the rest of techniques, with a mean score over 21% with both product suites. 4.3.4. Experiment 4: multiple faults in feature interactions This experiment aims to evaluate our approach when the SPL has multiple faults caused by feature interactions. Tables 13 and 14 show the average EXAMF values obtained in each of the case studies for five different test scenarios. As in the previous two experiments, the techniques showed significantly better performance with the 3-wise suite compared to the 2-wise suite. This improvement was significant in the case of Tarantula where the overall average EXAMF value decreased from 5.13% with the 2-wise suite to 0.93% with the 3-wise suite. Overall, the EXAMF values of the 3-wise suite outperformed those of the 2-wise suite in 68 out of the 90 measures. It is also noteworthy that the average EXAMF scores in this experiment are noticeably higher than in the previous ones. This suggests that isolating multiple interaction faults imposes a significantly hard problem for the techniques under evaluation. From the results, it is observed that Tarantula is the most effective technique to isolate multiple interaction faults, achieving the lowest average EXAMF value in 8 out of the 9 case studies with both test suites. Conversely, Arithmetic mean was the technique that showed the worst performance, followed by Russel-Rao, Naish2 and Wong. Table 11 EXAMF scores obtained using the 2-wise product suite in Experiment 3. Best values on each column are highlighted in boldface. Technique Drupal V3 Weather St. Eclipse Android UAV Dell L. Arcade HIS Model T. Mean Ample2 2.2 1.24 1.22 0.27 0.3 0.97 0.32 0.16 0.31 0.77 Arithmetic M. 36.41 17.05 47.35 13.59 13.57 15.7 13.34 5.34 22.37 20.52 Dstar 2.2 1.24 1.22 0.27 0.3 0.97 0.32 0.16 0.31 0.77 Kulcynski2 2.2 1.24 1.22 0.27 0.3 0.97 0.32 0.16 0.31 0.77 M2 2.2 1.24 1.22 0.27 0.3 0.97 0.32 0.16 0.31 0.77 Naish2 13.89 5.28 23.2 3.16 4.98 11.59 2.44 2.19 6.51 8.14 Ochiai 2.2 1.24 1.22 0.27 0.3 0.97 0.32 0.16 0.31 0.77 Russel–Rao 13.89 5.28 23.2 3.16 4.98 11.59 2.44 2.19 6.51 8.14 Tarantula 4.93 4.2 3.27 1.29 0.65 1.66 2.56 0.34 1.06 2.21 Wong 13.89 5.28 23.2 3.16 4.98 11.59 2.44 2.19 6.51 8.14 Mean 9.40 4.32 12.63 2.57 3.07 5.70 2.48 1.30 4.45 5.10 Table 12 EXAMF scores obtained using the 3-wise product suite in Experiment 3. Best values on each column are highlighted in boldface. Technique Drupal V3 Weather St. Eclipse Android UAV Dell L. Arcade HIS Model T. Mean Ample2 1.42 1.05 0.73 0.21 0.26 0.71 0.20 0.07 0.10 0.53 Arithmetic M. 38.86 17.73 47.57 12.43 13.89 15.80 14.58 5.47 22.9 21.03 Dstar 1.42 1.05 0.73 0.21 0.26 0.71 0.20 0.07 0.10 0.53 Kulcynski2 1.42 1.05 0.73 0.21 0.26 0.71 0.20 0.07 0.10 0.53 M2 1.42 1.05 0.73 0.21 0.26 0.71 0.20 0.07 0.10 0.53 Naish2 5.94 3.14 5.30 2.01 1.68 6.35 1.49 1.16 1.19 3.14 Ochiai 1.42 1.05 0.73 0.21 0.26 0.71 0.20 0.07 0.10 0.53 Russel–Rao 5.94 3.14 5.30 2.01 1.68 6.35 1.49 1.16 1.19 3.14 Tarantula 1.42 1.86 0.73 0.21 0.26 0.71 0.47 0.07 0.10 0.65 Wong 5.94 3.14 5.30 2.01 1.68 6.35 1.49 1.16 1.19 3.14 Mean 6.52 3.43 6.78 1.97 2.05 3.91 2.05 0.94 2.71 3.37 Table 13 EXAMF scores obtained using the 2-wise product suite in Experiment 4. Best values on each column are highlighted in boldface. Technique Drupal V3 Weather St. Eclipse Android UAV Dell L. Arcade HIS Model T. Mean Ample2 8.93 3.93 14.47 2.35 3.69 2.38 4.93 1.49 5.15 5.25 Arithmetic M. 44.69 19.86 52.54 11.52 17.44 14.96 10.90 5.39 23.23 22.28 Dstar 13.06 7.39 27.70 4.97 6.17 8.85 7.14 3.40 15.06 10.42 Kulcynski2 14.92 5.19 14.49 3.23 2.27 1.79 3.69 1.48 5.38 5.83 M2 13.19 6.14 27.57 5.89 6.9 5.23 7.91 3.42 15.29 10.17 Naish2 23.13 13.01 37.55 8.72 12.45 9.53 9.86 4.20 18.56 15.22 Ochiai 11.91 4.51 23.26 3.52 3.78 1.96 5.99 2.97 11.16 7.67 Russel–Rao 23.13 13.01 37.55 8.72 12.45 9.53 9.86 4.20 18.56 15.22 Tarantula 12.96 3.73 13.78 2.10 1.75 1.66 3.66 1.45 5.09 5.13 Wong 23.13 13.01 37.55 8.72 12.45 9.53 9.86 4.20 18.56 15.22 Mean 18.90 8.98 28.65 5.97 7.93 6.54 7.38 3.22 13.60 11.34