Dimitris E Simos
email: dsimos@sba-research.org

Kristoffer Kleine
email: kkleine@sba-research.org

Laleh Shikh

Gholamhossein Ghandehari
email: laleh.shikhgholamhosseing@mavs.uta.edu

Bernhard Garn
email: bgarn@sba-research.org

Yu Lei
email: ylei@cse.uta.edu

A Combinatorial Approach to Analyzing Cross-Site Scripting (XSS) Vulnerabilities in Web Application Security Testing

Keywords: Combinatorial Testing, XSS, Fault Localization, Security Testing

Web applications typically employ sanitization functions to sanitize user inputs, independently whether this input is assumed to be legitimate, invalid or malicious. When such functions do not work correctly, a web application immediately becomes vulnerable to security attacks such as XSS. In this paper, we report a combinatorial approach to analyze XSS vulnerabilities in web applications. Our approach first performs combinatorial testing where a set of test vectors is executed against a subject application. If one or more XSS vulnerabilities are triggered during testing, we analyze the structure of each test vector to identify XSS-inducing combinations of its parameter model. If an attack vector contains an XSS-inducing combination, then the execution of this vector will successfully exploit an XSS vulnerability. Identification of XSS-inducing combinations provides insights about which kinds of user input might still be leverageable for XSS attacks and how to correct the function to provide better security guarantees. We conducted an experiment in which our approach was applied to four sanitization functions from the Web Application Vulnerability Scanner Evaluation Project (WAVSEP). The experimental results show that our approach can effectively identify XSS-inducing combinations for these sanitization functions.

Introduction

Web application security is as important as ever but pervasive ubiquitous computing, bundled with 24/7 network access, makes any connected web application especially susceptible to attacks. Naturally, injection attacks are remote exploits which can cause security breaches. Cross-site scripting (XSS) falls into this category and constitutes the third serious vulnerability according to the Open Web Application Security Project (OWASP) [START_REF] Williams | OWASP Top 10 2013[END_REF]. We focus on analyzing XSS vulnerabilities where we distinguish between two different types of XSS, namely reflected XSS and stored XSS. In the former case the web server response contains some data from the corresponding request, while the latter case includes data stored permanently on the server (e.g., in a database). In line of this work we are concerned only for reflected XSS vulnerabilities.

In this paper, we apply for the first time a fault-localization technique based on combinatorial methods to identify one or more combinations of input parameter values that would definitely trigger an XSS vulnerability for a given system under test (SUT). We refer to these combinations as XSS-inducing combinations or simply inducing combinations. If an XSS attack vector (test vector) contains an inducing combination, then the execution of this test vector against the SUT will successfully exploit an XSS vulnerability. The identification of inducing combinations provides important information about why an input filter fails to sanitize a malicious vector, which in turns helps to make necessary corrections.

Note that this is different from traditional fault localization, which is aimed at identifying the location of a fault in the source code. Sanitization functions are typically employed in web applications to sanitize invalid or malicious user inputs. XSS vulnerabilities, if they exist, are in most cases contained in these sanitization functions, which are mostly simply referred to as filters. Thus, the location of an XSS vulnerability in the source code is typically considered known or not difficult to be identified. However, designing and implementing rigorous and secure input filters is a very complicated and challenging task [START_REF] Argyros | Back in black: Towards formal, black box analysis of sanitizers and filters[END_REF]. In particular, when an input filter does not work as expected, it could be difficult for one to understand why it does not work and how to correct a vulnerable filter. The results of this paper enhance the capabilities of security testers to design better attack models for web applications but at the same time guide the developers on how to improve the filtering mechanisms met in such applications.

In Section 2 we describe related work for web application security testing and fault localization techniques. Sections 3 and 5 reviews past achievements on combinatorial testing for web security testing and fault localization methods, respectively, that relate to this work. Section 4 discusses the test execution method used in this work. In Section 6 we present our methodology for analyzing XSS vulnerabilities using combinatorial based fault localization methods. An experimental evaluation that validates our approach is given in Section 7. Finally, Section 8 concludes the work and discusses directions for future work.

Related Work

In this section, we describe related works with respect to fault localization approaches for combinatorial testing and security testing frameworks devoted to XSS detection. For a systematic literature review on research devoted to XSS we refer to [START_REF] Hydara | Current state of research on cross-site scripting (XSS) a systematic literature review[END_REF] while for important contributions in combinatorial testing and fault localization that relate to the work presented in this paper we refer to Sections 3 and 5, respectively, and cited references there in.

Web Application Security Testing Frameworks Security testing is meant to support vulnerability detection, and for this task several approaches and tools have been developed in the past. In the following, we depict the most important of them. A comparison of several penetration testing tools is given in [START_REF] Garn | On the applicability of combinatorial testing to web application security testing: a case study[END_REF] and [START_REF] Van Der Loo | Comparison of Penetration Testing Tools for Web Applications[END_REF]. The authors of these works compare commercial as well as open source penetration testing tools by testing several web applications. Security testing tools incorporating fuzzing techniques have been presented in [START_REF] Tripp | Finding your way in the testing jungle: A learning approach to web security testing[END_REF], [START_REF] Duchene | Xss vulnerability detection using model inference assisted evolutionary fuzzing[END_REF] and [START_REF] Duchene | KameleonFuzz: Evolutionary Fuzzing for Black-Box XSS Detection[END_REF]. The authors of the last two works apply evolutionary approaches and learning in order to detect potential vulnerabilities. Even though these works add towards test automation, complete automation of the security testing process remains a very active challenge. Recent works on XSS vulnerability detection include unit testing methods that can detect XSS vulnerabilities which cannot be found by static analysis tools [START_REF] Mohammadi | Automatic web security unit testing: Xss vulnerability detection[END_REF] and attack patterns for black-box security testing of web applications [START_REF] Sudhodanan | Attack patterns for black-box security testing of multi-party web applications[END_REF].

It is evident that even though a lot of works have been devoted to XSS vulnerability detection very few of them focus on analyzing these vulnerabilities and even fewer correlate malicious vectors with sanitizing functions.

Fault Localization Techniques based on Combinatorial Methods Combinatorial testing has been shown to be a very effective testing strategy [START_REF] Kuhn | Pseudo-exhaustive testing for software[END_REF]. A t-way combinatorial test set is designed to detect failures that are triggered by combinations involving no more than t parameters. After a failure is detected, the next task is to identify the fault that causes the failure. The problem of fault localization can be divided into two sub-problems: 1) Identifying failureinducing combinations. A combination is failure-inducing or simply inducing if its existence in a test causes the test to fail. 2) Identifying actual faults in the source code. A fault is a code defect that can be an incorrect, extra, or missing statement. As explained in Section 1, we are mainly interested in identifying XSS-inducing combinations. Thus, in the following, we will focus on existing approaches to identify failure inducing combinations.

Two techniques, called FIC and FIC BS [START_REF] Zhang | Characterizing failure-causing parameter interactions by adaptive testing[END_REF], take as input a single failed test from a combinatorial test set, and identify as output a minimal inducing combination that causes the test to fail. The main idea of the two techniques consists of changing, in a systematic manner, the parameter values in the failed test. A parameter value is considered to be involved in an inducing combination if changing it to a different value causes the failed test to pass. It is assumed that changing a parameter value does not introduce any new inducing combination.

The AIFL technique in [START_REF] Shi | A software debugging method based on pairwise testing[END_REF] first identifies a set of suspicious combinations as candidates for being inducing. Second, it generates a group of tests for each failed test. After executing the newly generated tests, combinations which appeared in the passed tests are removed from the suspicious set. The IterAIFL technique is an iterative approach proposed by Wang et al. in [START_REF] Wang | Adaptive interaction fault location based on combinatorial testing[END_REF]. It iteratively generates and refines suspicious set until it becomes stable.

In our earlier work, we developed a approach called BEN that identifies suspicious combinations in the same way as AIFL and IterAIFL. However, BEN produces a ranking of suspicious combinations and focuses on the most suspicious combinations. Moreover, BEN significantly differs from AIFL and IterAIFL in the way of generating new tests. A detailed description of BEN is given in Section 5.

Lastly, to the best of our knowledge this is the first work where combinatorial based fault localization techniques are applied to analyze security vulnerabilities.

Combinatorial Testing for Web Security Testing

Combinatorial testing has been successfully applied for testing (critical) software systems in large organizations [START_REF] Hagar | Introducing combinatorial testing in a large organization[END_REF]. It is an already proven method for blackbox security testing of large-scale web software systems [START_REF] Garn | On the applicability of combinatorial testing to web application security testing: a case study[END_REF], [START_REF] Bozic | Evaluation of the IPO-family algorithms for test case generation in web security testing[END_REF], [START_REF] Bozic | Attack pattern-based combinatorial testing with constraints for web security testing[END_REF] where t-way testing was applied successfully to XSS detection. In this section, we review these key contributions in web security testing that are based on combinatorial methods and are used as a basis for analyzing XSS vulnerabilities via fault localization methods throughout this paper. For a general treatment of the field of combinatorial testing we refer the interest reader to the surveys of [START_REF] Brcic | Combinatorial testing in software projects[END_REF] and [START_REF] Nie | A survey of combinatorial testing[END_REF].

Throughout this paper, we are uniformly using a strength four (t = 4) test set against the SUTs for reasons explained later in this section. The underlying combinatorial model of XSS attack vectors is a refined and extended version from the works in [START_REF] Garn | On the applicability of combinatorial testing to web application security testing: a case study[END_REF] and [START_REF] Bozic | Attack pattern-based combinatorial testing with constraints for web security testing[END_REF] and is a form of input parameter model [START_REF] Grindal | Input parameter modeling for combination strategies[END_REF]. Its goal is to discretize the input space to parameters and discrete values so that these can be given to combinatorial testing tools.

The generated test vectors aim at producing valid JavaScript code when these are executed against SUTs. A description of parameters that appear in the input model has briefly been mentioned in [START_REF] Garn | On the applicability of combinatorial testing to web application security testing: a case study[END_REF] and [START_REF] Bozic | Attack pattern-based combinatorial testing with constraints for web security testing[END_REF], however we give an excerpt here, for the sake of completeness:

-The JSO (JavaScript Opening Tags) type represents tags that open a JavaScript code block. -The WS (white space) type family represents white space characters.

-The INT (input termination) type represents values that terminate the original valid tags (HTML or others). -The EVH (event handler) type contains values for JavaScript event handlers.

-The PAY (payload) type contains executable JavaScript.

-The PAS (payload suffix) type contains different values that should terminate the executable JavaScript payload (PAY parameter). -The JSE (JavaScript end tag) type contains different forms of JavaScript end tags.

Moreover, this input model is optimized to fit to the employed test execution method (see Section 4). A suitable metric has been introduced in [START_REF] Bozic | Attack pattern-based combinatorial testing with constraints for web security testing[END_REF] to assess the quality of produced combinatorial test sets for XSS detection, called exploitation rate (ER), which measures the proportion of XSS attack vectors that were successful, e.g. the ones that exploit an XSS vulnerability, per given test set and SUT.

In particular, past work of ours has revealed that the usage of a 4-way test set (with constraints) yields satisfactory practical results for web application security testing and is justified as follows:

-In the majority of our past security testing experiments [START_REF] Bozic | Attack pattern-based combinatorial testing with constraints for web security testing[END_REF], [START_REF] Bozic | Evaluation of the IPO-family algorithms for test case generation in web security testing[END_REF], [START_REF] Garn | On the applicability of combinatorial testing to web application security testing: a case study[END_REF] we have witnessed that higher strength interaction testing yields better results w.r.t. exploitation rate. More specifically, we were able to report an increase in the exploitation rate when moving from 2-way to 3-way and 4-way testing. Also, in [START_REF] Bozic | Attack pattern-based combinatorial testing with constraints for web security testing[END_REF] we reported on cases where only a 4-way test set was able to successfully trigger XSS exploits for specific SUTs but none of the test sets with weaker t-way coverage properties could. -In some of our past experiments [START_REF] Garn | On the applicability of combinatorial testing to web application security testing: a case study[END_REF], we have noticed performance issues when moving from pairwise-testing to higher interaction testing. Depending on the test execution method (see Section 4) (i.e. used penetration testing tool), the SUT (i.e. tested HTTP parameter of a web application) and the underlying operating system, we have seen execution times to vary greatly between repeated test runs. We further noticed SUTs to become unresponsive, as well as, increased memory usage. However, we were still able to exploit XSS vulnerabilities using a 4-way test set. -An important finding in the post-processing of 2-way test sets used in [START_REF] Bozic | Evaluation of the IPO-family algorithms for test case generation in web security testing[END_REF] was that it revealed a surprising high percentage of 3-way and 4-way combinations covered in the successful XSS attack vectors (per test set and SUT).

These statements are in accordance with a relationship known as interaction rule in combinatorial testing which is based on empirical data and shows that most software faults are triggered by a single parameter value, or interactions between a small number of parameters, generally two to six [START_REF] Kuhn | Introduction to Combinatorial Testing[END_REF].

Penetration Testing Execution Methods

In this section, we provide details about the penetration testing execution method we have used in our experimental evaluation. We give a detailed description of its procedure, functionality and test oracle, applicable when testing for XSS vulnerabilities. The described method can be applied to security testing in general, but in this paper we focus explicitly on penetration testing, e.g. exploiting XSS vulnerabilities, where the main difference (to security testing) relies on the fact that we initiate the testing procedure once the web applications are installed in an operational environment. The main difference to conventional penetration testing is that we are not interested in pinpointing where a vulnerability is located in the source code, but rather to analyze a known vulnerable input field in a web application in order to get insights into its structure, i.e. the necessary degree of interaction to trigger the successful exploitation of an XSS vulnerability.

Test Execution. As test execution environment we used the the Burp Suite3 which is an integrated platform for performing security testing of web applications. It is widely used by security professionals since it allows to perform many penetration testing tasks.

In our case the Intruder module of BURP was used to execute our test vectors. Intruder offers automated customized attacks against web applications, to identify and exploit all kinds of security vulnerabilities including XSS attacks. In order to test an SUT we supplied its location (server, port and URL) to Intruder and also provided the position for the input parameter. Then, our test set consisting of XSS attack vectors was loaded and executed one by one. The response (HTML) of the SUT for each test vector was recorded and supplied to the test oracle in order to determine whether an XSS vulnerability was triggered.

Test Oracle. The usual penetration testing procedure is mostly concerned with finding which parts of a web application are potentially vulnerable to an XSS attack. Here, the tester submits a request with user-controlled string in a HTTP-parameter (e.g. the user enters a string <script> in a search function and submits the query) and then examines the HTML response page from the web application whether it contains any part of the submitted string. If there are no sanitization functions invoked on the input at all, then this input field is a very probable candidate for having an XSS vulnerability. It is a common practice in security testing to rely on string matching as the underlying test oracle which is commonly referred to as reflection oracle. This process is repeated with all HTTP parameters in a web application. However, the reflection oracle can not decide whether an identically reflected user input string would actually be executed by a web browser. Therefore, the reflection oracle decision is not indicative of the vector actually triggering an XSS vulnerability. Thus, in relation to the detection of true XSS an oracle relying on reflection alone is not infallible as it suffers both from false positives and false negatives. In order to determine if the XSS vulnerability was indeed triggered by a test vector -meaning that we have a true XSS -the response of the web application needs to be evaluated under real-world conditions.

This necessary task can be fulfilled by employing a new test oracle, henceforward called the execution oracle. As indicated by the name, this oracle operates similar to a web browser and evaluates/parses the page response from a web application. The generated test vectors must be designed in such a way that their behavior is detectable by the execution oracle. Additionally, in the presented form it must be ensured that this behavior is distinct from normal intended behavior by the SUT, so that we can deduce true XSS by page-parsing anomaly detection. We have used the XSS Validator extension of BURP to fill the role of the execution oracle. The inner workings of the Validator are described below in detail. We state an important fact: Under these conditions, every vector marked as triggering by the execution oracle is indeed a test vector which triggers a true XSS vulnerability exploitation and as such the execution oracle does not produce false positives. To illustrate this point, consider the test vector onError=alert(1) which is reflected inside the body tag of an HTML page. Under the assumption that the web application applies no filtering to the input then this vector will be reflected without changes in the page response and the reflection oracle will flag this vector. The execution oracle however, will not flag this vector because it does not exploit the vulnerability.

An instantiation of the execution oracle can be found in the XSS Validator4 extension to BURP. This extension enhances the test execution capabilities of BURP by adding a detection mechanism of triggered XSS vulnerabilities.

The XSS Validator receives the response from the SUT (including the reflected test vector) and renders the HTML. During rendering, JavaScript contained in the website will be executed. When it is detected that JavaScript was executed which originated from a test vector then this test vector is flagged as having triggered the XSS vulnerability.

Since the Validator extension comes with its own set of test vectors and is targeted towards the detection of XSS vulnerabilities triggered by them we modified the code to use our own test vectors and adapted the detection code to recognize behavior triggered by them (see Section 6.2 for more details).

Fault Localization based on Combinatorial Methods

BEN [START_REF] Ghandehari | Fault localization based on failure-inducing combinations[END_REF], [START_REF] Ghandehari | Identifying failureinducing combinations in a combinatorial test set[END_REF] adopts a spectrum-based fault localization technique and has been applied to a Siemens test set and two programs i.e., grep and gzip. It leverages the results of the combinatorial test set and generates the ranking of statements in terms of their likelihood of being faulty. BEN consists of two major phases: 1) In phase 1, BEN identifies a combination that is very likely to be a failureinducing combination. 2) In phase 2, BEN takes the failure-inducing combination identified in phase 1 and then produces a ranking of statements in the source code by analyzing the spectra of the small group of tests.

In this work, we only applied the first phase of BEN because we are not interested on the ranking of statements in the source code since we are following a black-box security testing approach. Therefore, we focus solely on the first phase, identifying failure-inducing combinations. BEN takes the input parameter model and a t-way combinatorial test set with execution results as input, and adopts an iterative framework to identify inducing combinations of size t or larger. At each iteration, BEN analyzes a test set F , which initially is the tway combinatorial test set taken as input. BEN first identifies a set of t-way suspicious combinations, π, then, ranks them based on their suspiciousness, i.e., likelihood to be inducing. Next, a small set of new tests, F , is generated. If all tests in F that contain a suspicious combination c are failing, then c is marked as an inducing combination, and the process stops. Otherwise, all tests in F , will be added to test set F , to refine the set of suspicious combinations and their ranking. BEN continues the two steps, i.e., rank and test generation iteratively until a t-way suspicious combination is marked as an inducing combination or a stopping condition is satisfied [START_REF] Ghandehari | Identifying failureinducing combinations in a combinatorial test set[END_REF]. In the latter case, no t-way inducing combination is identified, BEN increases the size of inducing combination, and tries to identify a (t + 1)-way inducing combination.

Rank generation and test generation are based on two notions, suspiciousness of a combination and suspiciousness of the environment of a combination. Informally, the environment of a combination consists of other parameter values that appear in the same test case. The higher the suspiciousness of a combination, the lower the suspiciousness of its environment, the higher this combination is ranked. Moreover, new tests are generated for the most suspicious combinations. Let f be a new test generated for a suspicious combination c. Test f is generated such that it contains c and the suspiciousness of the environment for c is minimized. If f fails, it is more likely to be caused by c instead of other values in f . This process is repeated until an inducing combination is found. Note that this process must terminate, as a failed test is by definition an inducing combination. Note that if there is a resource limitation, the user can stop the process. The top-ranked suspicious combination is reported as failure-inducing combination, in this case.

Methodology

In this section, we present our approach for analyzing XSS vulnerabilities using combinatorial based fault localization methods. Our methodology is comprised of two parts: First executing XSS attack vectors against SUTs and second identifying one or more combinations of input values that can trigger a successful XSS exploit. Our utter goal is to map the failure-inducing combinations found to XSS-inducing combinations. As explained in Sections 4 and 5, respectively, we used the BURP suite for the first part and the BEN tool for the second. Further, we discuss below modifications of the BEN tool needed for XSS detection and also the necessity for a refinement of the attack model.

Modifications of BEN for XSS Detection

As explained in Section 5, BEN first looks for a t-way inducing combination, where t is the strength of the initial test set. Since all t-way combinations are covered by the t-way combinatorial test set, BEN guarantees to identify t-way inducing combination if such a combination exists. When there is no t-way inducing combination, BEN looks for (t + 1)-way inducing combination that is covered by the t-way test set.

For our experiments, we modified BEN to take the size of inducing combination as well as the t-way combinatorial test set. The user can search for an inducing combination whose size is equal to, greater or less than the strength of combinatorial test set, t. When the size of inducing combination is equal to or less than t, BEN could identify inducing combination of a requested size, if there is any. When the size of inducing combination is greater than the strength of the combinatorial test set, BEN starts looking for an inducing combination with the requested size is covered by the test set. In this case, BEN does not search for t-way inducing combination, although it may exist.

In the test generation step, a set of new tests is generated for a user-specified number of top-ranked suspicious combinations. Note that the user could specify the number of top-ranked suspicious combinations and the number of tests generated for each top-ranked combination. The more tests generated, the more effort it takes to execute them, but the more confidence we have about the identified inducing combinations. Moreover, the bigger the top-ranked set, the more effort to generate and execute the new tests, but the faster an inducing combination may be identified. This is because if an inducing combination c is included in the top-ranked set, c is identified to be an inducing combination in the first iteration. Otherwise, it may take multiple iterations for c to move up into the top-ranked set.

For our experiments, we configure BEN to generate two tests for each of the five top ranked suspicious combinations at each iteration. So, at each iteration maximum 10 new tests will be added to the test set. Note that this is a practical decision made in consideration with resource constraints.

Model Refinement

We revised our combinatorial model of XSS attack vectors from [START_REF] Garn | On the applicability of combinatorial testing to web application security testing: a case study[END_REF] and [START_REF] Bozic | Attack pattern-based combinatorial testing with constraints for web security testing[END_REF] to fit to the new execution oracle based on the Validator extension of BURP and to limit the size of the generated 4-way test set (due to the performance issues mentioned in Section 3), resulting in a significantly more robust and sophisticated test framework able to cast a 100% confidence decision on triggering test cases. To this end, we changed some parameter values and removed some others such that the resulting test vectors are in line with the implementation of hooks in the Validator so we can detect triggering test vectors. Most importantly, we chose two kinds of values for the payload parameter. One kind contains a call to the built-in JavaScript alert function while the other defines the src attribute pointing to some predefined and non-existing resource. Both types of these payloads trigger detectable behavior at runtime by PhantomJS. We have also verified this kind of JavaScript is not contained in our SUTs used in the experimental evaluation.

Experimental Evaluation

In this section, we conduct an experimental evaluation in order to validate our methodology for analyzing XSS vulnerabilities.

Design of the Experiment

The purpose of the experiment is to have a setup where we can evaluate our methodology for analyzing XSS vulnerabilities using combinatorial based fault localization techniques. To this end we choose 4 input fields as SUTs from WAVSEP, the Web Application Vulnerability Scanner Evaluation Project5 , version 1.2. WAVSEP is a web application specifically designed to allow testing for various kinds of XSS exploits, among other vulnerabilities. In contrast with training applications for web application security testing that have been thoroughly tested in the past [START_REF] Hydara | Current state of research on cross-site scripting (XSS) a systematic literature review[END_REF], WAVSEP offers sophisticated filter mechanisms and the majority of its SUTs can be tested for XSS vulnerabilities. In the following, we give details about the chosen input fields.

In particular, we use four input HTTP parameters as SUTs out of the WAVSEP when testing for XSS vulnerabilities. Each SUT receives over HTTP one GET parameter which is reflected on the page in different contexts. Also, the input might optionally be filtered by a SUT specific sanitization function.

SUT ID SUT name reflection site 1 Tag2HtmlPageScope <body>$input</body> 2 Tag2TagStructure <input type="text" value="$input"> 3 Event2TagScope <img src="$input"> 4
Event2DoubleQuotePropertyScope <img src="$input">

We give an description of these four SUTs, below:

SUT 1 This SUT just outputs the received parameter without modifications into the HTML body tag. Thus, possible exploits could just inject any HTML tag without having to worry about properly terminating a preceding tag in the page. SUT 2 This SUT outputs the received parameter without modifications into the value attribute of an input tag. SUT 3 This SUT outputs the received parameter into the src attribute of an image tag and filters angle brackets. SUT 4 This SUT outputs the received parameter into the src attribute of an image tag and filters angle brackets and single quotes.

Test vectors

We have employed the ACTS combinatorial test generation tool [START_REF] Yu | Acts: A combinatorial test generation tool[END_REF] for automated test generation of test vectors. The tool is developed jointly by the US National Institute of Standards and Technology and the University of Texas at Arlington and currently has more than 1400 individual and corporate users. In line of this work, we generated a 4-way test set consisting of 6891 test vectors.

Workflow The test vectors described above were then all executed against all four SUTs and classified as either triggering an XSS vulnerability or not. Then, BEN was run on the abstract test set together with the positions of vectors which did trigger a vulnerability (positive vectors) one time for each SUT. In the first round BEN searched for 4-way suspicious combinations and produced a set of recommended tests. These tests were then translated to concrete attack vectors and executed again. Depending on the result, BEN classified the underlying suspicious combinations either as inducing (in the case of all recommended tests succeeding) or not.

In the case that inducing combinations were found, we instructed BEN to look for lower strength faults to confirm if the fault was a true 4-way fault or an embedded lower strength fault. In the other case, when not all recommended tests succeeded, we instructed BEN to look for 5 or 6-way inducing combinations.

Results and Analysis

Here, we present our evaluation results grouped per analyzed SUT. In particular, we evaluate our findings w.r.t. underlying vulnerabilities and also correlate failure-inducing combinations with shortcomings in the filter mechanisms.

SUT 1

The initial test execution revealed 24 test vectors to trigger the XSS vulnerability. All ten recommended tests produced by BEN for 4-way suspicious combinations did not trigger the vulnerability. Therefore, we increased the strength and searched for 5 and 6-way suspicious combinations. As all eight recommended tests from 6-way suspicious combinations triggered the vulnerability we arrived at four inducing combinations of strength 6. In Table 1 we show the composition of these recommended tests and highlight in red the inducing combinations.

In the table the common structure of the triggering vectors is clearly visible as they all start with an opening img tag and contain a reference to the predefined resource. The other components of the inducing combination make sure that the vector does not contain any interfering characters to ensure that the vector will be parsed correctly when reflected in the page response. This SUT also does not perform any filtering of the input parameter and the page response will include the following HTML expression after the first recommended test from the table above is reflected: <input type="text" value=""><script> alert(1) </script>">">

This vector, as well as the other recommended 5-way tests, triggers the XSS vulnerability because of the embedded inducing combination. First the value field and the input tag are terminated and then a new script environment with the payload is created. Upon rendering the payload inside the script environment is then executed. SUT 3 In the initial test execution 228 test vectors triggered the XSS vulnerability. Based on these results, BEN recommended 10 tests using the found 4-way suspicious combinations. All of these tests triggered the vulnerability. We also instructed BEN to look for 2-way and 3-way suspicious combinations but none were found. This means that the reported 4-way inducing combinations are truly 4-way and not lower-strength inducing combinations embedded inside higher-strength combinations. The recommended tests and the inducing combinations are displayed in Table 3.

As this SUT encodes angle brackets a page response contains the following HTML part after the first recommended test is reflected: 3. Recommended tests with embedded 4-way inducing combinations <img src="<<script> "> onError= alert(1) '> \>"> This vector succeeds in triggering the vulnerability because it contains an inducing combination which first defines the src attribute as "<<script> " which of course is not a valid image resource. This causes the onError handler to be called which activates the payload, in this case alert [START_REF] Argyros | Back in black: Towards formal, black box analysis of sanitizers and filters[END_REF].

SUT 4

The initial test execution showed 280 vectors to trigger the XSS vulnerability. As all ten tests recommended by BEN for 4-way suspicious combinations triggered the vulnerability five inducing combinations were found. As for SUT 3, we also instructed BEN to look for 2-way and 3-way suspicious combinations but none were found, meaning that the inducing 4-way combinations are minimal inducing combinations. The recommended tests can be found in Table 4 To illustrate how the inducing combinations trigger the vulnerability consider the example below which shows the first recommended test vector from the above table reflected in the page response after all angle brackets and single quotes have been encoded by the SUT. <img src=""><script> '; onError= alert(1) '> \>"> Here the vector succeeds in triggering the vulnerability because it first closes the src attribute leaving it empty. Since the empty string is not a valid resource the onError handler is called which in turn calls the alert(1) statement.

Conclusion and Future Work

In this paper we have presented a combinatorial approach to analyzing XSS vulnerabilities in web applications. Our approach is based on the notion of XSSinducing combinations. An XSS-inducing combination is a combination of input parameter values whose appearance in a test vector would definitely result in a successful triggering of an XSS vulnerability at runtime when executed against the SUT. Identification of XSS-inducing combinations helps to better understand the root cause of an XSS vulnerability and provides insights about how to fix a flawed sanitization function. Our approach is developed based on our earlier work on applying combinatorial methods to security testing. In particular, our approach consists of a refinement of a combinatorial model of XSS attack vectors and a modification of a combinatorial testing-based fault localization method that are developed in our earlier works. We have reported an experiment in which our approach is applied to four sanitization functions from WAVSEP. The experimental results show that our approach can effectively identify XSSinducing combinations and that these combinations provide significant insights about the inner working of these sanitization functions.

We plan to continue our work in the following three directions. First, we plan to conduct additional experiments for a more thorough evaluation of our approach. In particular, we plan to apply our approach to more sanitization functions that are found in real-life web applications. Second, we plan to apply our approach to other types of vulnerabilities, e.g., SQL injections. We believe that the principles embodied in our approach are general, i.e. not limited to XSS vulnerabilities. Finally, we plan to build a software tool that automates our approach with the goal to make our approach accessible to web application developers.

Table 1 .

 1 Recommended tests with embedded 6-way inducing combinationsSince this SUT applies no filter to the input parameter the final page response will include the following HTML body when the first recommended test in the table above is submitted:<body><img src="invalid"\></body>This will force the application to load the resource invalid and thus trigger the XSS vulnerability.SUT 2The initial test execution revealed 3 test vectors to trigger the XSS vulnerability. Four out of ten generated recommended tests derived from 4-way suspicious combinations triggered the vulnerability. Because of this we instructed BEN to search for 5-way inducing combinations. Since all four recommended tests for 5-way suspicious combinations triggered, we found two inducing combinations. The final recommended tests and inducing combinations are summarized in Table2.

	JSO WS1 INT WS2 EVH WS3	PAY	WS4 PAS WS5	JSE
	<img	src="invalid"		\>
	<img	src="invalid"		'\>
	<img	src="invalid"
	<img	src="invalid"		<</script>
	<img	src="invalid"		>
	<img	src="invalid"		>>
	<img	src="invalid"		</script>">
	<img	src="invalid"		</script>

Table 2 .

 2 Recommended tests with embedded 5-way inducing combinations

Table 4 .

 4 . Recommended tests with embedded 4-way inducing combinations

	JSO	WS1 INT WS2	EVH	WS3	PAY	WS4 PAS WS5 JSE
	"><script>	';	onError=		alert(1)	'>	\>
	"><script>	'>	onError=		alert(1)	'>	\>
	"><script>	'>	onError=		alert(1)	')	\>
	"><script>		onError=		alert(1)	'>	\>
	"><script>		onError=		alert(1)	')	\>
	"><script>	'>>	onError=		alert(1)	')	\>
	"><script>	';	onError=		src="invalid"	'>	\>
	"><script>	'>	onError=		src="invalid"	'>	\>
	"><script>	'>	onError=		src="invalid"	')	\>
	"><script>		onError=		src="invalid"	'>	\>

http://portswigger.net/burp/

https://portswigger.net/bappstore

https://github.com/sectooladdict/wavsep

Acknowledgments. This work has been funded by the Austrian Research Promotion Agency (FFG) under grant 851205 and the Austrian COMET Program (FFG).


Dipesh Pradhan

Shuai Wang

Shaukat Ali

Tao Yue

Marius Liaaen
email: marliaae@cisco.com

STIPI: Using Search to Prioritize Test Cases Based on Multi-objectives Derived from Industrial Practice

Keywords: Test Case Prioritization, Search, Configurations, Test APIs. 1

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Testing is a critical activity for system or software development, through which system/software quality is ensured [START_REF] Walcott | Timeaware test suite prioritization[END_REF]. To improve the testing efficiency, a large number of researchers have been focusing on prioritizing test cases into an optimal execution order to achieve maximum effectiveness (e.g., fault detection capability) as quickly as possible [START_REF] Rothermel | Test case prioritization: An empirical study[END_REF][START_REF] Li | Search algorithms for regression test case prioritization[END_REF][START_REF] Wang | Multi-objective test prioritization in software product line testing: an industrial case study[END_REF]. In the industrial practice of automated testing, test case prioritization is even more critical because usually there is a limited budget (e.g., time) to execute test cases, and thus executing all available test cases at a given context is infeasible [START_REF] Walcott | Timeaware test suite prioritization[END_REF][START_REF] Wang | Enhancing Test Case Prioritization in an Industrial Setting with Resource Awareness and Multi-Objective Search[END_REF].

Our industrial partner for this work is Cisco System, Norway, who develops product lines of Video Conferencing Systems (VCSs), which enable high quality conference meetings [START_REF] Wang | Multi-objective test prioritization in software product line testing: an industrial case study[END_REF][START_REF] Wang | Enhancing Test Case Prioritization in an Industrial Setting with Resource Awareness and Multi-Objective Search[END_REF]. To ensure the delivery of high quality VCSs to the market, test engineers of Cisco continually develop test cases to test software of VCSs under various hardware or software configurations, statuses (i.e., states) of VCSs with dedicated test APIs. A test case is typically composed of the following parts: 1) setting up test configurations of a set of VCSs under test; 2) invoking a set of test APIs of the VCSs; and 3) checking the statuses of the VCSs after invoking the test APIs to determine the success or failure of an execution of the test case. When executing test cases, several objectives need to be achieved, i.e., covering the maximum number of possible configurations, test APIs, statuses and detecting as many faults as possible. However, given a number of available test cases, it is often infeasible to execute all of them in practice due to a limited budget of execution time (e.g., ten hours), and it is therefore important to seek an approach for prioritizing the given test cases to cover maximum number of configurations, test APIs, statuses and detect faults as quickly as possible.

To address the above-mentioned challenge, we propose a search-based test case prioritization approach named Search-based Test case prioritization based on Incremental unique coverage and Position Impact (STIPI). STIPI defines a fitness function with four objectives to evaluate the quality of test case prioritization solutions, i.e., Configuration Coverage (CC), test API Coverage (APIC), Status Coverage (SC) and Fault Detection Capability (FDC), and integrates the fitness function with a widely-applied multi-objective search algorithm (i.e., Non-dominated Sorting Genetic Algorithm II) [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: NSGA-II[END_REF]. Moreover, we propose two prioritization strategies when defining the fitness function in STIPI: 1) Incremental Unique Coverage, i.e., for a specific test case, we only consider the incremental unique elements (e.g., test APIs) covered by the test case as compared with the elements covered by the already prioritized test cases; and 2) Position Impact, i.e., a test case with a higher execution position (i.e., scheduled to be executed earlier) has more impact on the quality of a prioritization solution. Notice that both of these strategies are defined to help search to achieve high criteria (i.e., CC, APIC, SC and FDC) as quickly as possible.

To evaluate STIPI, we chose five approaches for the comparison: 1) Random Search (RS) to assess the complexity of the problem; 2) Greedy approach; 3) One existing approach [START_REF] Arrieta | Test Case Prioritization of Configurable Cyber-Physical Systems with Weight-Based Search Algorithms[END_REF] and two modified approaches from the existing literature [START_REF] Rothermel | Prioritizing test cases for regression testing[END_REF][START_REF] Elbaum | Incorporating varying test costs and fault severities into test case prioritization[END_REF]. The evaluation uses in total 211 test cases from Cisco, which are divided into three sets with varying complexity. Moreover, four different time budgets are used for our evaluation, i.e., 25%, 50%, 75% and 100% (100% refers to the total execution time of all the test cases in a given set). Notice that 12 comparisons were performed (i.e., three sets of test cases*four time budgets) for comparing STIPI with each approach, and thus in total 60 comparisons were conducted for the five approaches. Results show that STIPI significantly outperformed the selected approaches for 54 out of 60 comparisons (90%). In addition, STIPI managed to achieve higher performance than RS for on average 39.9% (configuration coverage), 18.6% (test API coverage), 32.7% (status coverage), and 43.9% (fault detection capability).

The remainder of the paper is organized as follows: Section 2 presents the context, a running example and motivation. STIPI is presented in Section 3 followed by experiment design (Section 4). Section 5 presents experiment results and overall discussion. Related work is discussed in Section 6, and we conclude the work in Section 7.

Context, Running Example and Motivation

Figure 1 presents a simplified context of testing VCSs (Systems Under Test (SUTs)), and Figure 2 illustrates (partial) configuration, test API and status information for testing a VCS. First, one VCS consists of one or more configuration variables (e.g., attribute protocol of class VCS in Figure 2), each of which can take two or more configuration variable values (e.g., literal SIP of enumeration Protocol). Second, a VCS holds one or more status variables defining the statuses of the VCS (e.g., NumberofActive-Calls), and each status variable can have two or more status variable values (e.g., Num-berofActiveCalls taking values of 0, 1, 2, 3 and 4). Third, testing a VCS requires employing one or more test API commands (e.g., dial), each of which includes zero or more test API parameters (e.g., callType for dial). Each test API parameter can take two or more test API parameter values (e.g., Video and Audio for CallType). 3 configures the configuration variable protocol with SIP (Line 1). Second, a test API command is invoked with appropriate values assigned to its input parameters, if any. For example, the test case in Figure 3 invokes the test API command dial consisting of the two test API parameter values: Video for callType and SIP for protocol) (Line 2). Third, the test case checks the actual statuses of VCSs. For example, the test case in Figure 3 checks the status of the VCS to see if NumberOfActiveCalls equals to 1 (Line 4).

Figure 3. An Excerpt of a Sanitized and Simplified Test Case

In the context of testing VCSs, test case prioritization is a critical task since it is practically infeasible to execute all the available test cases within a given time budget (e.g., five hours). Therefore, it is essential to cover maximum configurations (i.e., configuration variables and their values), test APIs (i.e., test API commands, parameters and their values) and statuses (i.e., status variables and their values), and detect faults as quickly as possible. For instance, Table 1 lists five test cases (𝑇 1 …𝑇 5 ) with the information about configurations, test APIs and statuses. The test case in Figure 3 is represented as T1 in Table 1, which 1) sets the configuration variable protocol as SIP; 2) uses three test API commands: dial with two parameters (callType, protocol), accept and disconnect; and 3) checks values of three status variables (e.g., MaxVideoCalls).

protocol dial accept disconnect SV1 SV2 SV3 callType protocol T1 SIP Video SIP   0, 1 1 1 T2 SIP Audio SIP   0, 1 1 0 T3 SIP Audio SIP  1 1 0 T4 H323 Audio H323  0, 1, 2 2 0 T5 H320 Audio H320  1 1 1
* SV1: NumberOfActiveCalls, SV2: MaxNumberOfCalls, SV3: MaxVideoCalls.

Notice that the five test cases in Table 1 can be executed in 325 orders (i.e., 𝐶(5,1) × 1! + 𝐶(5,2) × 2! + … + 𝐶(5,5) × 5!). When there is a time budget, each particular order can be considered as a prioritization solution. Given two prioritization solutions 𝑠 1 = {𝑇 5 , 𝑇 1 , 𝑇 4 , 𝑇 2 , 𝑇 3 } , 𝑠 2 = {𝑇 1 , 𝑇 3 , 𝑇 5 , 𝑇 2 , 𝑇 4 }, one can observe that 𝑠 1 is better than 𝑠 2 since the first three test cases in 𝑠 1 can cover all the configuration variables and their values, test API commands, test API parameters, test API parameter values, status variables and status variable values, while 𝑠 2 needs to execute all the five test cases to achieve the same coverage as 𝑠 1 . Therefore, it is important to seek an efficient approach to find an optimal order for executing a given number of test cases to achieve high coverage of configurations, test APIs and statuses, and detect faults as quickly as possible, which forms the motivation of this work.

STIPI: Search-based Test case prioritization based on Incremental unique coverage and Position Impact

This section presents the problem representation (Section 3.1), four defined objectives, fitness function (Section 3.2) and solution encoding (Section 3.3).

Basic Notations and Problem Representation

Basic Notations. We provide the basic notations as below used throughout the paper. )|. 𝐸𝑓𝑓𝑒𝑐𝑡 = {𝑒𝑓𝑓𝑒𝑐𝑡 1 … 𝑒𝑓𝑓𝑒𝑐𝑡 𝑛𝑒𝑓𝑓𝑒𝑐𝑡 } defines a set of effectiveness measures. 𝑆 = {𝑠 1 , 𝑠 2 … 𝑠 𝑛𝑠 } represents a set of potential solutions, such that 𝑛𝑠 = 𝐶(𝑛, 1) × 1! + 𝐶(𝑛, 2) × 2! + … + 𝐶(𝑛, 𝑛) × 𝑛!. Each solution 𝑠 𝑗 consists of a set of prioritized test cases in 𝑇: 𝑠 𝑗 = {𝑇 𝑗1 … 𝑇 𝑗𝑛 }, where 𝑇 𝑗𝑖 ∈ 𝑇 refers to the test case with the execution position i in the prioritized solution 𝑠 𝑗 . Note that it is possible for the maximum number of test cases in 𝑠 𝑗 (i.e., 𝑗𝑛) to be less than the total number of test cases in 𝑇, since only a subset of T is prioritized during limited budget (e.g., time).

Problem Representation. We aim to prioritize the test cases in 𝑇 in two contexts: 1) 100% time budget and 2) less than 100% time budget (i.e., time-aware [START_REF] Walcott | Timeaware test suite prioritization[END_REF]). Therefore, we formulate the test case prioritization problem as follows: a) search a solution 𝑠 𝑘 with 𝑛𝑘 test cases from the total number of 𝑛𝑠 solutions in 𝑆 to obtain the highest effectiveness; and b) a test case 𝑇 𝑗𝑟 in a particular solution (e.g., 𝑠 𝑗 ) with a higher position 𝑝 has more influence for 𝐸𝑓𝑓𝑒𝑐𝑡 than the test case with a lower position 𝑞. 1) With 100% time budget:

∀ 𝑖=1 𝑡𝑜 𝑛𝑒𝑓𝑓𝑒𝑐𝑡 ∀ 𝑗=1 𝑡𝑜 𝑛𝑠 𝐸𝑓𝑓𝑒𝑐𝑡 (𝑠 𝑘 , 𝑒𝑓𝑓𝑒𝑐𝑡 𝑖 ) ≥ 𝐸𝑓𝑓𝑒𝑐𝑡 (𝑠 𝑗 , 𝑒𝑓𝑓𝑒𝑐𝑡 𝑖 ) ∨ 𝑒𝑓𝑓𝑒𝑐𝑡 𝑖 (𝑇 𝑗𝑟 , 𝑝) > ∀ 𝑞≥(𝑝+1) 𝑒𝑓𝑓𝑒𝑐𝑡 𝑖 (𝑇 𝑗𝑟 , 𝑞).
where 𝑒𝑓𝑓𝑒𝑐𝑡 𝑖 (𝑇 𝑗𝑟 , 𝑝) and 𝑒𝑓𝑓𝑒𝑐𝑡 𝑖 (𝑇 𝑗𝑟 , 𝑞) refer to the effectiveness measure 𝑖 for a test case 𝑇 𝑗𝑟 at position p and q, respectively for a particular solution 𝑠 𝑗 . 𝐸𝑓𝑓𝑒𝑐𝑡 (𝑠 𝑘 , 𝑒𝑓𝑓𝑒𝑐𝑡 𝑖 ) and 𝐸𝑓𝑓𝑒𝑐𝑡 (𝑠 𝑗 , 𝑒𝑓𝑓𝑒𝑐𝑡 𝑖 ) returns the effectiveness measure 𝑖 for solutions 𝑠 𝑘 , 𝑠 𝑗 respectively.

2) With a time budget tb less than 100% time budget:

∀ 𝑖=1 𝑡𝑜 𝑛𝑒𝑓𝑓𝑒𝑐𝑡 ∀ 𝑗=1 𝑡𝑜 𝑛𝑠 𝐸𝑓𝑓𝑒𝑐𝑡 (𝑠 𝑘 , 𝑒𝑓𝑓𝑒𝑐𝑡 𝑖 ) ≥ 𝐸𝑓𝑓𝑒𝑐𝑡 (𝑠 𝑗 , 𝑒𝑓𝑓𝑒𝑐𝑡 𝑖 ) ∨ ∑ 𝐸𝑇 𝑙 𝑛𝑘 𝑙=1
≤ 𝑡𝑏, 𝑒𝑓𝑓𝑒𝑐𝑡 𝑖 (𝑇 𝑗𝑟 , 𝑝) > ∀ 𝑞≥(𝑝+1) 𝑒𝑓𝑓𝑒𝑐𝑡 𝑖 (𝑇 𝑗𝑟 , 𝑞).

Fitness Function

Recall that we aim at maximizing the overall coverage for configuration, test API and status, and detect faults as quickly as possible (Section 2). Therefore, we define four objective functions for the fitness function to guide the search towards finding optimal solutions, which are presented in details as below. , where 𝑛 is the total number of test cases, and 𝑖 is a specific execution position in a prioritization solution. Thus, test cases with higher execution positions have higher impact on the quality of a prioritization solution, which fits the scope of test case prioritization that aims at achieving higher criteria as quickly as possible. For instance, using this strategy, 𝐶𝑉𝑉𝐶 for 𝑠 1 is:

Maximize Configuration Coverage (CC

𝐶𝑉𝑉𝐶 𝑠 1 = 1× 5 5 +1× 4 5 +1× 3 5 +0× 2 5 +0× 1 5 3 = 0.8. Moreover, CC for 𝑠 𝑗 is represented as:𝐶𝐶 𝑠 𝑗 = 𝐶𝑉𝐶 𝑠 𝑗 + 𝐶𝑉𝑉𝐶 𝑠 𝑗 2 .
A higher value of CC shows a higher coverage of configuration. , with a higher value indicating a higher status coverage, and therefore representing a better solution. Maximize Fault Detection Capability (FDC). In the context of Cisco, FDC is defined as the detected number of faults for test cases in a solution 𝑠 𝑗 [START_REF] Wang | Multi-objective test prioritization in software product line testing: an industrial case study[END_REF][START_REF] Wang | Enhancing Test Case Prioritization in an Industrial Setting with Resource Awareness and Multi-Objective Search[END_REF][START_REF] Wang | A Practical Guide to Select Quality Indicators for Assessing Pareto-based Search Algorithms in Search-Based Software Engineering[END_REF][START_REF] Wang | Cost-effective test suite minimization in product lines using search techniques[END_REF][START_REF] Wang | Minimizing test suites in software product lines using weight-based genetic algorithms[END_REF]

Maximize Test API Coverage (APIC

𝑚𝑓𝑑𝑐

. 𝐹𝐷𝐶 𝑇 𝑗𝑖 denotes the FDC for a 𝑇 𝑗𝑖 , 𝑚𝑓𝑑𝑐 represents the sum of all FDC of test cases, and a higher value of 𝐹𝐷𝐶 implies a better solution. Notice that we cannot apply the incremental unique coverage strategy for calculating 𝐹𝐷𝐶 𝑠 𝑗 since the relations between faults and test cases are not known in our case (i.e., we only know whether the test cases can detect faults after executing it for a certain number of times rather than having access to the detailed faults detected).

Solution Representation

The test cases in 𝑇 are encoded as an array 𝐴 = {𝑣 1 , 𝑣 2 … 𝑣 𝑛 }, where each variable 𝑣 𝑖 represents one test case in T, and holds a unique value from 0 to 1. We prioritize the test cases in 𝑇𝑆 by sorting the variables in 𝐴 in a descending order from higher to lower, such that 1 is the highest, and 0 is the lowest order. Initially, each variable in 𝐴 is assigned a random value between 0 and 1, and during search our approach returns solutions with optimal values for 𝐴 guided by the fitness function defined in Section 3.2. In terms of time-aware test case prioritization (i.e., with a time budget less than 100%), we pick the maximum number of test cases that fit the given time budget. For example, in Table 1 for 𝑇𝑆 = {𝑇 1 … 𝑇 5 } with 𝐴 as {0.6, 0.2, 0.4, 0.9, 0.3} and the execution time (recorded as minutes) as 𝐸𝑇 = {4, 5, 6, 4, 3} , the prioritized test cases are {𝑇 4 , 𝑇 1 , 𝑇 3 , 𝑇 5 , 𝑇 2 } based on our encoding way for test case prioritization. If we have a time budget of 11 minutes, the first two test cases (in total 8 minutes for execution) are first added to the prioritized solution 𝑠 𝑗 , and there are 3 minutes left, which is not sufficient for executing 𝑇 3 (6 minutes). Thus, 𝑇 3 is not added into 𝑠 𝑗 , and the next test case is evaluated to see if the total execution time can fit the given time budget. 𝑇 5 with three minutes will be added into 𝑠 𝑗 , since the inclusion of 𝑇 5 will not make the total execution time exceed the time budget. Therefore, the new prioritized solution will be {𝑇 4 , 𝑇 1 , 𝑇 5 }. Moreover, we integrate our fitness function with a widely applied multi-objective search algorithm named Non-dominated Sorting Genetic Algorithm (NSGA-II) [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: NSGA-II[END_REF][START_REF] Sarro | Multi-objective software effort estimation[END_REF][START_REF] Wang | UPMOA: An improved search algorithm to support user-preference multi-objective optimization[END_REF]. The tournament selection operator [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: NSGA-II[END_REF] is applied to select individual solutions with the best fitness for inclusion into the next generation. The crossover operator is used to produce offspring solutions from the parent solutions by swapping some of the parts (e.g., test cases in our context) of the parent solutions. The mutation operator is applied to randomly change the values of one or more variables (e.g., in our context, each variable represents a test case) based on the pre-defined mutation probability, e.g., 1/(total number of test cases) in our context. We also compare the running time of STIPI with all the five chosen approaches, since STIPI is invoked very frequently (e.g., more than 50 times per day) in our context, i.e., the test cases require to be prioritized and executed often. Therefore, it would be practically infeasible if it takes too much time to apply STIPI.

Empirical Study Design

Experiment tasks

As shown in Table 2 (Experiment Task column), we designed two tasks (T1, T2) for addressing RQ1-RQ2. The task T1 is designed to compare STIPI with RS for the four time budgets (i.e., 100%, 75%, 50% and 25%) and three sets of test cases (i.e., 100, 150 and 211). Similarly, the task T2 is designed to compare STIPI with the other four test case prioritization approaches, which is divided into four sub-tasks for comparing Greedy, A1, A2 and A3, respectively.

Moreover, we employed 211 real test cases from Cisco for evaluation by dividing it into three sets with varying complexity (#Test Cases column in Table 2). For the first set, we used all the 211 test cases. For the second set, we used 100 random test cases from the 211 test cases. Finally, for the third set, we used the 150 test cases by choosing 111 test cases not selected in the second set (i.e., 100) and 39 random test cases from the second set. Notice that the goal for using three test case sets is to evaluate our approach with test datasets with different complexity.

Evaluation metrics

To answer the RQs, we defined in total seven EMs (Table 3). Six are used to assess how fast the configurations, test APIs and statuses can be covered: When there is a limited time budget, it is possible that not all the configurations, test APIs and statuses can be covered. Therefore, we defined APCCp, APACp, and APACp to give penalty to missing configurations, test APIs, and statuses for time-aware prioritization (i.e., 25%, 50% and 75% time budget) based on the variant of APFD metric used for time-aware prioritization [START_REF] Walcott | Timeaware test suite prioritization[END_REF][START_REF] Lu | How does regression test prioritization perform in realworld software evolution?[END_REF]. For example, for a solution 𝑠 𝑗 with jn test cases 𝑟𝑒𝑣𝑒𝑎𝑙(𝑐𝑣, 𝑠 𝑗 ) gives the test case from 𝑠 𝑗 that covers cv for APCVCp in Table 3. If 𝑠 𝑗 does not contain a test case that covers cv, 𝑟𝑒𝑣𝑒𝑎𝑙(𝑐𝑣, 𝑠 𝑗 ) = 𝑗𝑛 + 1. Notice that in our context, we only have information about how many times in a given period (e.g., a week) a test case was successful in finding faults. Therefore, it is not possible to use the APFD metric to evaluate FDC. Hence, we defined a metric: Measured Fault Detection Capability (MFDC) to measure the percentage of fault detected for time budget of 25%, 50% and 75%.

Quality Indicator, Statistical Tests and Parameter Settings

When comparing the overall performance of multi-objective search algorithms (e.g., NSGA-II [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: NSGA-II[END_REF]), it is common to apply quality indicators such as hypervolume (HV). Following the guideline in [START_REF] Wang | A Practical Guide to Select Quality Indicators for Assessing Pareto-based Search Algorithms in Search-Based Software Engineering[END_REF], we employ HV based on the defined EMs to address RQ2.2-RQ2.4 (i.e., tasks T2.2 -T2.4 in Table 2). HV calculates the volume in the objective space covered by members of a non-dominated set of solutions (i.e., Pareto front) produced by search algorithms for measuring both convergence and diversity [START_REF] Nebro | AbYSS: Adapting scatter search to multiobjective optimization[END_REF]. A higher value of HV indicates a better performance of the algorithm. The Vargha and Delaney 𝐴 ̂12 statistics [START_REF] Vargha | A critique and improvement of the CL common language effect size statistics of McGraw and Wong[END_REF] and Mann-Whitney U test are used to compare the EMs (T1 and T2), and HV (T2.2 -T2.4), as shown in Table 2 by following the guidelines in [START_REF] Arcuri | A practical guide for using statistical tests to assess randomized algorithms in software engineering[END_REF]. The Vargha and Delaney 𝐴 ̂12 statistics is a non-parametric effect size measure, and Mann-Whitney U test tells if results are statistically significant [START_REF] Mann | On a test of whether one of two random variables is stochastically larger than the other[END_REF]. For two algorithms A and B, A has better performance than B if 𝐴 ̂12 is greater than 0.5, and the difference is significant if p-value is less than 0.05.

Notice that STIPI, A1, A2 and A3 are all combined with NSGA-II. Since tuning parameters to different settings might result in different performance of search algorithms, standard settings are recommended [START_REF] Arcuri | A practical guide for using statistical tests to assess randomized algorithms in software engineering[END_REF]. We used standard settings (i.e., population size=100, crossover rate=0.9, mutation rate=1/(number of test cases)) as implemented in jMetal [START_REF] Durillo | jMetal: A Java framework for multi-objective optimization[END_REF]. The search process is terminated when the fitness function has been evaluated for 50,000 times. Since A2 does not support prioritization with a time budget, we collect the maximum number of test cases that can fit a given time budget.

Results, Analyses and Discussion

RQ1: Sanity Check (STIPI vs. RS)

Results in Table 4 and Table 5 show that on average STIPI is higher than RS for all the EMs across the three sets of test cases. Moreover, for the three test sets using four time budgets, STIPI managed to achieve higher performance than RS for on average 39.9% (configuration coverage), 18.6% (test API coverage), 32.7% (status coverage), and 43.9% (FDC). In addition, results of the Vargha and Delaney statistics and the Mann Whitney U test show that STIPI significantly outperformed RS for all the Ems since all the values of 𝐴 ̂12 are greater than 0.5 and all the p-values are less than 0.05.

RQ2: Comparison with the selected approaches

We compared STIPI with Greedy, A1, A2 and A3 using the statistical tests (Vargha and Delaney statistics and Mann Whitney U test) for the four time budgets (25%, 50%, 75% and 100%), and the three sets of test cases (i.e., 100, 150, 211). Results are summarized in Figure 4. For example, the first bar (i.e., Gr) in Figure 4 refers to the comparison between STIPI and Greedy for the 100% time budget where A= STIPI and B=Greedy. A>B means the percentage of EMs for which STIPI has significantly better performance than Greedy (𝐴 ̂12 > 0.5 && 𝑝 < 0.05), A<B means the opposite (𝐴 ̂12 < 0.5 && 𝑝 < 0.05), and A=B implies there is no significant difference in performance (𝑝 ≥ 0.05).

RQ2.1 (STIPI vs. Greedy).

From Table 4 and Table 5, we can observe that the average values of STIPI are higher than Greedy for 93.3% (42/45) 1 EMs across the three sets of test cases with the four time budgets. Moreover, from Figure 4, we can observe STIPI performed significantly better than Greedy for an average of 93.1% for the four time budgets (i.e., 88.9% for 100%, 91.7% for 75%, 91.7% for 50%, and 100% for 25% time budget). Detailed results are available in [15]. 4 and Table 5, we can see that STIPI has a higher average value than A1 for 82.2% (37/45) EMs, and STIPI performed significantly better than A1 for an average of 76.4% EMs across the four time budgets, while there was no difference in performance for 14.6% from Figure 4. Figure 5 shows that for HV, STIPI outperformed A1 for all the three sets of test cases with the four time budgets, and such better results are statistically significant. Detailed results are in [15]. 4 shows that the two approaches had similar average for EMs with 100% time budget. Moreover, for 100% time budget, there was no significant difference in the performance between STIPI and A2 in terms of EMs and HV (Figure 4 and Figure 5). However, when considering the time budgets of 25%, 50% and 75%, STIPI had a higher performance for 96.3% (26/27) EMs (Table 4 and Table 5). Furthermore, the statistical tests in Figure 4 and Figure 5 show that STIPI significantly outperformed A2 for an average of 88.9% EMs and HV values across the three time budgets (25%, 50%, 75%), while there was no significant difference for 11.1%.

RQ2.4 (STIPI vs. A3).

Based on the results (Table 4 and Table 5), STIPI held a higher average values for 75% (27/36) EM values for the four time budgets and three sets of test cases. For 100%, 75%, and 50%, we can observe from Figure 4 that STIPI performed significantly better than A3 for an average of 74.1% EMs, while there was no significant difference for 22.2%. For the 25% time budget, there was no statistically significant difference in terms of EMs for STIPI and A3. However, when comparing the HV values, STIPI significantly outperformed A3 for an average of 91.7% across the four time budgets and three sets of test cases. Notice that 12 comparisons were performed when comparing STIPI with each of the five selected approaches (i.e., three test case sets * four time budgets), and thus in total 60 comparisons were conducted. Based on the results, we can observe that STIPI significantly outperformed the five selected approaches for 54 out of 60 comparisons (90%), which indicate that STIPI has a good capability for solving our test case prioritization problem. In addition, STIPI took an average time of 36.5, 51.6 and 82 seconds (secs) for the three sets of test cases. The average running time for the five chosen approaches are: 1) RS: 18, 24.7 and 33.2 secs; 2) Greedy: 42, 48 and 54 milliseconds; 3) A1: 35.7, 42.8 and 65.5 secs; 4) A2: 35.2, 42.2 and 55.4 secs; and 5) A3: 8.9, 33.4 and 41.2 secs. Notice that there is no practical difference in terms of the running time for the approaches except Greedy, however the performance of Greedy is significantly worse than STIPI (Section 5.2), and thus Greedy cannot be employed to solve our test case prioritization problem. In addition, based on the domain knowledge of VCS testing, the running time in seconds is acceptable when deployed in practice.

Overall Discussion

For RQ1, we observed that STIPI performed significantly better than RS for all the EMs with the three sets of test cases under the four time budgets. Such an observation reveals that solving our test case prioritization problem is not trivial, which requires an efficient approach. As for RQ2, we compared STIPI with Greedy, A1, A2 and A3 (Section 4.1).

Results show that STIPI performed significantly better than Greedy. This can be explained that Greedy is a local search algorithm that may get stuck in a local space during the search process, while STIPI employs mutation operator (Section 4.4) to explore the whole search space towards finding optimal solutions. In addition, Greedy converted our multi-objective optimization problem into a single-objective optimization problem by assigning weights to each objective, which may lose many other optimal solutions that hold the same quality [START_REF] Konak | Multi-objective optimization using genetic algorithms: A tutorial[END_REF], while STIPI (integrating NSGA-II) produces a set of non-dominated solutions (i.e., solutions with equivalent quality). When comparing STIPI with A1, A2 and A3, the results of RQ2 showed that STIPI performed significantly better than A1, A2 and A3 by 83.3% (30/36). Overall STIPI outperformed the five selected approaches for 90% (54/60) comparisons. That might be due to two main reasons: 1) STIPI considers the coverage of incremental unique elements (e.g., test API commands) when evaluating the prioritization solutions, i.e., only the incremental unique elements covered by a certain test case are taken into account as compared with the already prioritized test cases; and 2) STIPI provides the test cases with higher execution positions more influence on the quality of a given prioritization solution. Furthermore, A2 and A3 usually work under the assumption that the relations between detected faults and test cases are known beforehand, which is sometimes not the situation in practice, e.g., in our case, we are only aware how many execution times a test case can detect faults rather than having access to the detailed faults detected. However, STIPI defined FDC to measure the fault detection capability (Section 3.2) without knowing the detailed relations between faults and test cases, which may be applicable to the similar other contexts when the detailed faults cannot be accessed. It is worth mentioning that the current practice of Cisco do not have an efficient approach for test case prioritization, and thus we are working on deploying our approach in their current practice for further strengthening STIPI.

Threats to Validity

The internal validity threat arises due to using search algorithms with only one configuration setting for its parameters as we did in our experiment [START_REF] Oliveira Barros | Threats to Validity in Search-based Software Engineering Empirical Studies[END_REF]. However, we used the default parameter setting from the literature [START_REF] Arcuri | On parameter tuning in search based software engineering[END_REF], and based on our previous experience [START_REF] Wang | Enhancing Test Case Prioritization in an Industrial Setting with Resource Awareness and Multi-Objective Search[END_REF][START_REF] Wang | A Practical Guide to Select Quality Indicators for Assessing Pareto-based Search Algorithms in Search-Based Software Engineering[END_REF], good performance can be achieved for various search algorithms with the default setting. To mitigate the construct validity threat, we used the same stopping criteria (50,000 fitness evaluations) for finding the optimal solutions. To avoid conclusion validity threat due to the random variations in the search algorithms, we repeated the experiments 10 times to reduce the possibility that the results were obtained by chance. Following the guidelines of reporting the results for randomized algorithms [START_REF] Arcuri | A practical guide for using statistical tests to assess randomized algorithms in software engineering[END_REF], we employed the Vargha and Delaney test as the effect size measure and Mann-Whitney test to determine the statistical significance of results. First external validity threat is that one may argue the comparison performed only included RS, Greedy, one existing approach and two modified versions of the existing approaches, which may not be sufficient. Notice that we discussed and justified why we chose these approaches in Section 4.1, and it is also possible to compare our approach with other existing approaches, which requires further investigation as the next step. Second external validity threat is due to the fact that we only performed the evaluation using one industrial case study. We need to mention that we conducted the experiment using three sets of test cases with four distinct time budgets based on the domain knowledge of VCS testing.

Related Work

In the last several decades, test case prioritization has attracted a lot of attention and considerable amount of work has been done [START_REF] Walcott | Timeaware test suite prioritization[END_REF][START_REF] Rothermel | Test case prioritization: An empirical study[END_REF][START_REF] Li | Search algorithms for regression test case prioritization[END_REF][START_REF] Rothermel | Prioritizing test cases for regression testing[END_REF]. Several survey papers [START_REF] Yoo | Regression testing minimization, selection and prioritization: a survey[END_REF][START_REF] Catal | Test case prioritization: a systematic mapping study[END_REF] present results that compare existing test case prioritization techniques from different aspects, e.g., based on coverage criteria. Followed by the aspects presented in [START_REF] Yoo | Regression testing minimization, selection and prioritization: a survey[END_REF], we summarize the related work close to our approach and highlight the key differences from the following three aspects: coverage criteria, search-based prioritization techniques (which is related with our approach) and evaluation metrics.

Coverage Criteria. Existing works defined a number of coverage criteria for evaluating the quality of prioritization solutions [START_REF] Rothermel | Test case prioritization: An empirical study[END_REF][START_REF] Li | Search algorithms for regression test case prioritization[END_REF][START_REF] Catal | Test case prioritization: a systematic mapping study[END_REF] such as branch coverage and statement coverage, function coverage and function-level fault exposing potential, block coverage, modified condition/decision coverage, transition coverage and round trip coverage. As compared with the state-of-the-art, we proposed three new coverage criteria driven by the industrial problem (Section 3.2): 1) Configuration coverage (CC); 2) Test API coverage (APIC) and 3) Status coverage (SC).

Search-Based Prioritization Techniques. Search-based techniques have been widely applied for addressing test case prioritization problem [START_REF] Li | Search algorithms for regression test case prioritization[END_REF][START_REF] Wang | Multi-objective test prioritization in software product line testing: an industrial case study[END_REF][START_REF] Wang | Enhancing Test Case Prioritization in an Industrial Setting with Resource Awareness and Multi-Objective Search[END_REF][START_REF] Wang | A Practical Guide to Select Quality Indicators for Assessing Pareto-based Search Algorithms in Search-Based Software Engineering[END_REF]. For instance, Zhang et al. [START_REF] Li | Search algorithms for regression test case prioritization[END_REF] defined a fitness function with three objectives (i.e., Block, Decision and Statement Coverage) and integrated the fitness function with hill climbing and GA for test case prioritization. Arrieta et al. [START_REF] Arrieta | Test Case Prioritization of Configurable Cyber-Physical Systems with Weight-Based Search Algorithms[END_REF] proposed to prioritize test cases by defining a twoobjective fitness function (i.e., test case execution time and fault detection capability) and evaluated the performance of several search algorithms. The authors of [START_REF] Arrieta | Test Case Prioritization of Configurable Cyber-Physical Systems with Weight-Based Search Algorithms[END_REF] also proposed a strategy to give higher importance to test cases with higher positions (to be executed earlier). A number of research papers have focused on addressing the test case prioritization problem within a limited budget (e.g., time and test resource) using search-based approaches. For instance, Walcott et al. [START_REF] Walcott | Timeaware test suite prioritization[END_REF] proposed to combine selection (of a subset of test cases) and prioritization (of the selected test cases) for prioritizing test cases within a limited time budget. Different weights are assigned to the selection part and prioritization part when defining the fitness function followed by solving the problem with GA. Wang et al. [START_REF] Wang | Enhancing Test Case Prioritization in an Industrial Setting with Resource Awareness and Multi-Objective Search[END_REF] focused on the test case prioritization within a given limited test resource budget (i.e., hardware, which is different as compared with the time budget used in this work) and defined four cost-effectiveness measures (e.g., test resource usage), and evaluated several search algorithms (e.g., NSGA-II).

As compared with the existing works, our approach (i.e., STIPI) defines a fitness function that considers configurations, test APIs and statuses, which were not addressed in the current literature. When defining the fitness function, STIPI proposed two strategies, which include 1) only considering the unique elements (e.g., configurations) achieved; and 2) taking the impact of test case execution orders on the quality of prioritization solutions into account, which is not the case in the existing works.

Evaluation Metrics (EMs).

APFD is widely used in the literature as an EM [START_REF] Rothermel | Test case prioritization: An empirical study[END_REF][START_REF] Li | Search algorithms for regression test case prioritization[END_REF][START_REF] Rothermel | Prioritizing test cases for regression testing[END_REF][START_REF] Lu | How does regression test prioritization perform in realworld software evolution?[END_REF]. Moreover, the modified version of APFD (i.e., APFDp) using time penalty [START_REF] Walcott | Timeaware test suite prioritization[END_REF][START_REF] Lu | How does regression test prioritization perform in realworld software evolution?[END_REF] is usually applied for test case prioritization with a time budget. Other metrics were also defined and applied as EMs [START_REF] Elbaum | Incorporating varying test costs and fault severities into test case prioritization[END_REF][START_REF] Catal | Test case prioritization: a systematic mapping study[END_REF] such as Average Severity of Faults Detected, Total Percentage of Faults Detected and Average Percentage of Faults Detected per Cost (APFDc). As compared with the existing EMs, we defined in total six new EMs driven by our industrial problem for configurations, test APIs and statuses (Table 3), which include: 1) APCC, APAC, and APSC, inspired by APFD, when there is 100% time budget; and 2) APCCp, APACp, and APSCp inspired by APFDp, when there is a limited time budget (e.g., 25% time budget). Furthermore, we defined the seventh EM (MFDC) to assess to what extent faults can be detected when the time budget is less than 100% (Table 3). To the best of our knowledge, there is no existing work that applies these seven EMs for assessing the quality of test case prioritization solutions.

Conclusion and Future Work

Driven by our industrial problem, we proposed a multi-objective search-based test case prioritization approach named STIPI for covering maximum number of configurations, test APIs, statuses, and achieving high fault detection capability as quickly as possible.

We compared STIPI with five test case prioritization approaches using three sets of test cases with four time budgets. The results show that STIPI performed significantly better than the chosen approaches for 90% of the cases. STIPI managed to achieve a higher performance than random search for on average 39.9% (configuration coverage), 18.6% (test API coverage), 32.7% (status coverage) and 43.9% (FDC). In the future, we plan to compare STIPI with more prioritization approaches from the literature using additional case studies with larger scale to further generalize the results.

Figure 1 .Figure 2 .

 12 Figure 1. A Simplified Context of Testing VCSs

Figure 4 .

 4 Figure 4. Results of Comparing STIPI with Greedy, A1, A2 and A3 for EMs RQ2.2 (STIPI vs. A1). Based on Table4and Table5, we can see that STIPI has a higher average value than A1 for 82.2% (37/45) EMs, and STIPI performed significantly better than A1 for an average of 76.4% EMs across the four time budgets, while there was no difference in performance for 14.6% from Figure4. Figure5shows that for HV, STIPI outperformed A1 for all the three sets of test cases with the four time budgets, and such better results are statistically significant. Detailed results are in[15].

Figure 5 .

 5 Figure 5. Results of Comparing STIPI with A1, A2 and A3 for HV RQ2.3 (STIPI vs. A2). RQ2.3 is designed to compare STIPI with the approach A2 (Section 4.1). Table4shows that the two approaches had similar average for EMs with 100% time budget. Moreover, for 100% time budget, there was no significant difference in the performance between STIPI and A2 in terms of EMs and HV (Figure4and Figure5). However, when considering the time budgets of 25%, 50% and 75%, STIPI had a higher performance for 96.3% (26/27) EMs (Table4 and Table 5). Furthermore, the statistical tests in Figure4and Figure5show that STIPI significantly outperformed A2 for an average of 88.9% EMs and HV values across the three time budgets (25%, 50%, 75%), while there was no significant difference for 11.1%.

Table 1 . Illustrating Test Case Prioritization* Test Case Configuration Test API Status

 1

  𝑠𝑣 2 … 𝑠𝑣 𝑚𝑠𝑣 } represents a set of status variables covered by 𝑇. For each 𝑠𝑣 𝑖 , 𝑆𝑉𝑉 𝑖 refers to the status variable values: 𝑆𝑉𝑉 𝑖 = {𝑠𝑣𝑣 𝑖1 … 𝑠𝑣𝑣 𝑖𝑠𝑣𝑣 }.

	𝐴𝐶 = {𝑎𝑐 1 , 𝑎𝑐 2 … 𝑎𝑐 𝑚𝑎𝑐 } represents a set of test API commands covered by 𝑇. For
	each 𝑎𝑐 𝑖 , 𝐴𝑃 𝑖 denotes the test API parameters: 𝐴𝑃 𝑖 = {𝑎𝑝 𝑖1 … 𝑎𝑝 𝑖𝑎𝑝 }. 𝑚𝑎𝑝 is the total number of unique test API parameters, calculated as: 𝑚𝑎𝑝 = |(⋃ 𝐴𝑃 𝑖 𝑚𝑎𝑐 )|. For each 𝑖=1 𝑎𝑝 𝑖 , 𝐴𝑉 𝑖 refers to the test API parameter values: 𝐴𝑉 𝑖 = {𝑎𝑣 𝑖1 … 𝑎𝑣 𝑖𝑎𝑣 }. 𝑚𝑎𝑣 is the total number of unique test API parameter values, i.e., 𝑚𝑎𝑣 = |(⋃ 𝐴𝑉 𝑖 𝑚𝑎𝑝 𝑖=1 )|.
	𝑆𝑉 = {𝑠𝑣 1 , 𝑚𝑠𝑣𝑣 is the
	total number of unique status variable values, calculated as: 𝑚𝑠𝑣𝑣 = |(⋃	𝑚𝑠𝑣 𝑖=1	𝑆𝑉𝑉 𝑖
	𝑇 = {𝑇 1 , 𝑇 2 … 𝑇 𝑛 } represents a set of n test cases to be prioritized.
	𝐸𝑇 = {𝑒𝑡 1 , 𝑒𝑡 2 … 𝑒𝑡 𝑛 } refers to the execution time for each test case in 𝑇.
	𝐶𝑉 = {𝑐𝑣 1 , 𝑐𝑣 2 … 𝑐𝑣 𝑚𝑐𝑣 } represents the configuration variables covered by 𝑇. For
	each 𝑐𝑣 𝑖 , 𝐶𝑉𝑉 𝑖 refers to the configuration variable values: 𝐶𝑉𝑉 𝑖 = {𝑐𝑣𝑣 𝑖1 … 𝑐𝑣𝑣 𝑖𝑐𝑣𝑣 }.
	𝑚𝑐𝑣𝑣 is the total number of unique values for all the configuration variables, which
	can be calculated as: 𝑚𝑐𝑣𝑣 = |(⋃	𝑚𝑐𝑣 𝑖=1	𝐶𝑉𝑉 𝑖	)|.

  𝐶𝑉𝐶 𝑠 𝑗 = 𝑚𝑐𝑣𝑣 = 3). Moreover, we propose two prioritization strategies for calculating 𝐶𝑉𝐶 and 𝐶𝑉𝑉𝐶. The first one is Incremental Unique Coverage, i.e., 𝑈𝐶𝑉 𝑇 𝑗𝑖 and 𝑈𝐶𝑉𝑉 𝑇 𝑗𝑖 representing the number of incremental unique CV and CVV covered by 𝑇 𝑗𝑖 (Section 3.1). For example, in Table1, for one test case prioritization solution 𝑠 1 = {𝑇 5 , 𝑇 1 , 𝑇 4 , 𝑇 2 , 𝑇 3 }, 𝑈𝐶𝑉𝑉 𝑇 5 is 1 since 𝑇 5 is in the first execution position and covers one CVV (i.e., H320). 𝑈𝐶𝑉𝑉 𝑇 1 and 𝑈𝐶𝑉𝑉 𝑇 4 are at the second and third position, and cover one CVV each (i.e., SIP, H323). However, 𝑈𝐶𝑉𝑉 𝑇 2 and 𝑈𝐶𝑉𝑉 𝑇 3 are 0, since they are already covered by 𝑈𝐶𝑉𝑉 𝑇 1 . This strategy is defined since test case prioritization in our case concerns how many configurations, test APIs, and statuses can be covered rather than how many times they can be covered. The second prioritization strategy is Position Impact, which is calculated as

	𝑛-𝑖+1
	𝑛
	∑	𝑗𝑛 𝑖=1	𝑈𝐶𝑉 𝑇 𝑗𝑖 × 𝑚𝑐𝑣	𝑛-𝑖+1 𝑛	, 𝐶𝑉𝑉𝐶 𝑠 𝑗 =	∑	𝑗𝑛 𝑖=1	𝑈𝐶𝑉𝑉 𝑇 𝑗𝑖 ×	𝑛-𝑖+1 𝑛

). CC measures the overall configuration coverage of a solution 𝑠 𝑗 with 𝑗𝑛 number of test cases, which is composed of Configuration Variable Coverage (CVC) and Configuration Variable Values Coverage (CVVC). We can calculate CVC and CVVC for 𝑠 𝑗 as: 𝑚𝑐𝑣𝑣 , where mcv and mcvv represent the total number of unique Configuration Variables (CV) and Configuration Variable Values (CVV) respectively covered by the total test cases in 𝑇 (e.g., in Table 1

  ). APIC measures the overall test API coverage of a solution 𝑠 𝑗 with 𝑗𝑛 number of test cases. It consists of three sub measures: Test API Command Coverage (ACC), Test API Parameter Coverage (APC), and Test API parameter Value Coverage (AVC). ACC, APC and AVC can be calculated as below: Incremental Unique Coverage and Position Impact) are applied for calculating 𝐴𝐶𝐶, 𝐴𝑃𝐶 and 𝐴𝑉𝐶, where 𝑈𝐴𝐶 𝑇 𝑗𝑖 , 𝑈𝐴𝑃 𝑇 𝑗𝑖 and 𝑈𝐴𝑉 𝑇 𝑗𝑖 denotes the number of unique test API commands (AC), test API parameters (AP), and test API parameter values (AV) respectively covered by 𝑇 𝑗𝑖 (Section 3.1). They are measured similar as for 𝑈𝐶𝑉𝑉 𝑇 in CVVC. 𝑚𝑎𝑐, 𝑚𝑎𝑝, and 𝑚𝑎𝑣 refer to the total number of unique AC, AP, and AV covered by the total number of test cases as explained for 𝑚𝑐𝑣𝑣 in CVVC. The APIC for 𝑠 𝑗 is represented as: 𝐴𝑃𝐼𝐶 𝑠 𝑗 = 𝑈𝑆𝑉 𝑇 𝑗𝑖 and 𝑈𝑆𝑉𝑉 𝑇 𝑗𝑖 are the number of unique Status Variables (SV) and Status Variable Values (SVV) respectively covered by 𝑇 𝑗𝑖 (Section 3.1), which are measured similar as 𝑈𝐶𝑉𝑉 𝑇 in 𝐶𝑉𝑉𝐶. 𝑚𝑠𝑣 and 𝑚𝑠𝑣𝑣 represent the total number of unique SV and SVV respectively measured similar as for 𝑚𝑐𝑣𝑣 in CVVC. The SC for 𝑠 𝑗 is represented as: 𝑆𝐶 𝑠 𝑗 =

	𝐴𝐶𝐶 𝑠 𝑗 = 𝐴𝐶𝐶 𝑠 𝑗 + 𝐴𝑃𝐶 𝑠 𝑗 ∑ 𝑈𝐴𝐶 𝑇 𝑗𝑖 × 𝑗𝑛 𝑖=1 𝑚𝑎𝑐 + 𝐴𝑉𝐶 𝑠 𝑗 𝑛-𝑖+1 𝑛 , 𝐴𝑃𝐶 𝑠 𝑗 = ∑ 𝑈𝑆𝑉𝑉 𝑇 𝑗𝑖 × 𝑛-𝑖+1 𝑛 𝑗𝑛 𝑖=1 𝑚𝑠𝑣𝑣 . Similarly, SVC 𝑠 𝑗 ∑ 𝑈𝐴𝑃 𝑇 𝑗𝑖 × 𝑛-𝑖+1 𝑛 𝑗𝑛 𝑖=1 𝑚𝑎𝑝 , 𝐴𝑉𝐶 𝑠 𝑗 = + 𝑆𝑉𝑉𝐶 𝑠 𝑗 2	∑ 𝑈𝐴𝑉 𝑇 𝑗𝑖 × 𝑗𝑛 𝑖=1 ∑ 𝑈𝑆𝑉 𝑇 𝑗𝑖 × 𝑛-𝑖+1 𝑛 𝑛-𝑖+1 𝑛 𝑗𝑛 𝑖=1 𝑚𝑠𝑣	, 𝑆𝑉𝑉𝐶 𝑠 𝑗 =

𝑚𝑎𝑣

.

Similarly, the same two strategies (i.e.,

3

. A higher value of APIC shows a higher coverage of test APIs.

Maximize Status Coverage (SC). SC measures the total status coverage of a solution 𝑠 𝑗 . It consists of two sub measures: Status Variable Coverage (SVC) and Status Variable

Value Coverage (SVVC), calculated as follow: 𝑆𝑉𝐶 𝑠 𝑗 =

  . The FDC for a test case 𝑇 𝑗𝑖 is calculated as: 𝐹𝐷𝐶 𝑇 𝑗𝑖 = FDC of 𝑇 𝑗𝑖 is calculated based on the historical information of executing 𝑇 𝑗𝑖 .For example, if 𝑡𝑐 𝑖 was executed 10 times, and it detected fault 4 times, the FDC for 𝑡𝑐 𝑖 is 0.4. We calculate FDC for a solution 𝑠 𝑗 as: 𝐹𝐷𝐶 𝑠 𝑗 =

	𝑁𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑡𝑖𝑚𝑒𝑠 𝑡ℎ𝑎𝑡 𝑇 𝑗𝑖 𝑓𝑜𝑢𝑛𝑑 𝑎 𝑓𝑎𝑢𝑙𝑡 𝑁𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑡𝑖𝑚𝑒𝑠 𝑡ℎ𝑎𝑡 𝑇 𝑗𝑖 𝑤𝑎𝑠 𝑒𝑥𝑒𝑐𝑢𝑡𝑒𝑑	. No-
	𝑗𝑛 tice that the ∑ 𝐹𝐷𝐶 𝑇 𝑗𝑖 × 𝑖=1	𝑛-𝑖+1 𝑛

  Is STIPI effective for test case prioritization as compared with RS (i.e., random prioritization)? We compare STIPI with RS for four time budgets: 100% (i.e., total execution time of all the test cases in a given set), 75%, 50% and 25%, to assess the complexity of the problem such that the use of search algorithms is justified. RQ2: Is STIPI effective for test case prioritization as compared with four selected approaches, in the contexts of four time budgets: 100%, 75%, 50% and 25%? RQ2.1: Is STIPI effective as compared with the Greedy approach (a local search approach)? RQ2.2: Is STIPI effective as compared with the approach used in[START_REF] Arrieta | Test Case Prioritization of Configurable Cyber-Physical Systems with Weight-Based Search Algorithms[END_REF] (named as A1 in this paper)? Notice that we chose A1 since it also proposed a strategy to give higher importance to test cases with higher execution positions.

	4.1	Research Questions
	RQ1: ∑ 𝑚𝑐𝑣𝑣 (∑ 𝑗𝑛 𝑘=𝑇𝐶𝑉𝑉 𝑖 𝑖=1	𝑒𝑡 𝑘 -	1 2	𝑒𝑡 𝑇𝐶𝑉𝑉 𝑖	)
		∑ 𝑗𝑛 𝑘=1	𝑒𝑡 𝑘 ×𝑚

RQ2.3:

Is STIPI effective as compared with the modified version of the approach proposed in

[START_REF] Rothermel | Prioritizing test cases for regression testing[END_REF]

(named as A2 in this paper)? We chose A2 since it combines the Average Percentage of Faults Detected (APFD) metric and NSGA-II for test case prioritization without considering time budget. We modified it by defining Average Percentage of Configuration Coverage (APCC), Average Percentage of test API Coverage (APAC) and Average Percentage of Status Coverage (APSC) (Section 4.3) for assessing the quality of prioritization solutions for configurations, test APIs and statuses. RQ2.4: Is STIPI effective as compared with the modified version of the approach in

[START_REF] Elbaum | Incorporating varying test costs and fault severities into test case prioritization[END_REF]

(named as A3 in this paper)? We chose A3 since 1) it combines the ADFD with cost (APFDc) metric and NSGA-II for addressing time-aware test case prioritization problem. We revised A3 by defining Average Percentage of Configuration Coverage with cost (APCCc), Average Percentage of test API Coverage with cost (APACc) and Average Percentage of Status Coverage with cost (APSCc). For illustration, we provide a formula for Average Percentage of Configuration Variable Value Coverage with cost (APCVVCc) that is a sub-metric for APCCc as: 𝐴𝑃𝐶𝑉𝑉𝐶 𝑐 = 𝑐𝑣𝑣 . For a solution 𝑠 𝑗 with jn test cases, 𝑇𝐶𝑉𝑉 i is the first test case from 𝑠 𝑗 that covers 𝐶𝑉𝑉 i (i.e., the i th configuration variable value), 𝑚𝑐𝑣𝑣 is the total number of unique configuration variable value, and 𝑒𝑡 𝑘 is the execution time for k th test case. Notice that the detailed formulas for APCCc, APACc and APSCc can be consulted in our technical report in

[15]

.

Table 2 . Overview of the Experiment Design

 2

	RQ	Experiment Task	#Test Cases	Time Budget %	Evaluation Metric (EM)	Quality Indicator	Statistical Test
	1 2	T1: STIPI vs. RS STIPI vs. T2.1 Greedy T2.2 STIPI vs. A1 T2.3 STIPI vs. A2 T2.4 TIPI vs. A3	100 150 211	100 25, 50, 75 100 25, 50, 75 100 25, 50, 75 100 25, 50, 75 100 25, 50, 75	APCC, APAC, APSC APCCp, APACp, APSCp, MFDC APCC, APAC, APSC APCCp, APACp, APSCp, MFDC APCC, APAC, APSC APCCp, APACp, APSCp, MFDC APCC, APAC, APSC APCCp, APACp, APSCp APCC, APAC, APSC APCCp, APACp, APSCp	----Hypervol-ume (HV)	Vargha and Delaney 𝐴 ̂12 Mann-Whitney U Test

Table 3 . Different Metrics for Evaluating the Approaches*

 3

	EC	Time Budget %	EM	Name			Sub Metric Formula			Formula
	Con	100 25 50 75	APCC APCCp	APCVC APCVVC APCVCp APCVVCp	1 -1 -	𝑇𝐶𝑉 1 + 𝑇𝐶𝑉 2 + … + 𝑇𝐶𝑉 𝑚𝑐𝑣 𝑛 × 𝑚𝑐𝑣 𝑇𝐶𝑉𝑉 1 + 𝑇𝐶𝑉𝑉 2 + … + 𝑇𝐶𝑉𝑉 𝑚𝑐𝑣𝑣 1 + 2𝑛 𝑛 × 𝑚𝑐𝑣𝑣 1 -∑ 𝑟𝑒𝑣𝑒𝑎𝑙(𝑐𝑣, 𝑠 𝑗 ) 𝑚𝑐𝑣 𝑐𝑣=1 𝑗𝑛 × 𝑚𝑐𝑣 1 + 2𝑗𝑛 1 -∑ 𝑟𝑒𝑣𝑒𝑎𝑙(𝑐𝑣𝑣, 𝑠 𝑗 ) 𝑚𝑐𝑣𝑣 𝑐𝑣𝑣=1 𝑗𝑛 × 𝑚𝑐𝑣𝑣 1 + 2𝑗𝑛	+	1 2𝑛	𝐴𝑃𝐶𝐶 = 𝐴𝑃𝐶𝐶 𝑝 =	𝐴𝑃𝐶𝑉𝐶 + 𝐴𝑃𝐶𝑉𝑉𝐶 2 𝐴𝑃𝐶𝑉𝐶 𝑝 + 𝐴𝑃𝐶𝑉𝑉𝐶 𝑝 2
		100	APAC	APACC APAPC APAVC	1 -1 -1 -	𝑇𝐴𝐶 1 + 𝑇𝐴𝐶 2 + … + 𝑇𝐴𝐶 𝑚𝑎𝑐 𝑛 × 𝑚𝑎𝑐 𝑇𝐴𝑃 1 + 𝑇𝐴𝑃 2 + … + 𝑇𝐴𝑃 𝑚𝑎𝑝 𝑛 × 𝑚𝑎𝑝 𝑇𝐴𝑉 1 + 𝑇𝐴𝑉 2 + … + 𝑇𝐴𝑉 𝑚𝑎𝑣 𝑛 × 𝑚𝑎𝑣	+ + +	1 2𝑛 1 2𝑛 1 2𝑛	𝐴𝑃𝐴𝐶 = 𝐴𝑃𝐴𝐶𝐶 + 𝐴𝑃𝐴𝑃𝐶 + 𝐴𝑃𝐴𝑉𝐶 3
	API	25 50 75	APACp	APACCp APAPCp APAVCp			1 -1 -1 -	∑ 𝑚𝑎𝑐 𝑎𝑐=1 𝑗𝑛 × 𝑚𝑎𝑐 𝑟𝑒𝑣𝑒𝑎𝑙(𝑎𝑐, 𝑠 𝑗 ) ∑ 𝑟𝑒𝑣𝑒𝑎𝑙(𝑎𝑝, 𝑠 𝑗 ) 𝑚𝑎𝑝 𝑎𝑝=1 𝑗𝑛 × 𝑚𝑎𝑝 ∑ 𝑟𝑒𝑣𝑒𝑎𝑙(𝑎𝑣, 𝑠 𝑗 ) 𝑚𝑎𝑣 𝑎𝑣=1 𝑗𝑛 × 𝑚𝑎𝑣	+ + +	1 2𝑗𝑛 1 2𝑗𝑛 1 2𝑗𝑛	𝐴𝑃𝐴𝐶 𝑝 = 𝐴𝑃𝐴𝐶𝐶 𝑝 + 𝐴𝑃𝐴𝑃𝐶 𝑝 + 𝐴𝑃𝐴𝑉𝐶 𝑝 3
	Stat	100 25 50 75	APSC APSCp	APSVC APSVVC APSVCp APSVVCp	1 -1 -𝑇𝑆𝑉𝑉 1 + 𝑇𝑆𝑉𝑉 2 + … + 𝑇𝑆𝑉𝑉 𝑚𝑠𝑣𝑣 𝑇𝑆𝑉 1 + 𝑇𝑆𝑉 2 + … + 𝑇𝑆𝑉 𝑚𝑠𝑣 𝑛 × 𝑚𝑠𝑣 + 𝑛 × 𝑚𝑠𝑣𝑣 1 -∑ 𝑟𝑒𝑣𝑒𝑎𝑙(𝑠𝑣, 𝑠 𝑗 ) 𝑚𝑠𝑣 𝑠𝑣=1 𝑗𝑛 × 𝑚𝑠𝑣 1 + 2𝑗𝑛 1 -∑ 𝑟𝑒𝑣𝑒𝑎𝑙(𝑠𝑣𝑣, 𝑠 𝑗 ) 𝑚𝑠𝑣𝑣 𝑠𝑣𝑣=1 𝑗𝑛 × 𝑚𝑠𝑣𝑣 1 + 2𝑗𝑛	1 2𝑛 +	1 2𝑛	𝐴𝑃𝑆𝐶 = 𝐴𝑃𝑆𝐶 𝑝 =	𝐴𝑃𝑆𝑉𝐶 + 𝐴𝑃𝑆𝑉𝑉𝐶 2 𝐴𝑃𝑆𝑉𝐶 𝑝 + 𝐴𝑃𝑆𝑉𝑉𝐶 𝑝 2
	FDC	25,50,75	MFDC	-				-			𝑀𝐹𝐷𝐶 =	𝑗𝑛 ∑ 𝐹𝐷𝐶 𝑇𝑖 𝑖=1 ∑ 𝐹𝐷𝐶 𝑇𝑘 𝑘=1 𝑛	× 100%

*EC: Evaluation Criteria, Con: Configuration, API: Test API, Stat: Status.

Table 4 . Average Values of the EMs with 100% and 75% Time Budget*

 4

	#T	EM	RS	100% time budget Gr A1 A2	A3	STI	EM	RS	75% time budget Gr A1 A2	A3	STI
	100		0.7	0.76	0.75	0.77	0.75	0.77		0.63	0.71	0.73	0.74	0.73	0.74
	150	CC	0.68	0.84	0.8	0.79	0.75	0.79	CCp	0.60	0.81	0.69	0.72	0.73	0.77
	211		0.74	0.83	0.83	0.85	0.81	0.85		0.67	0.76	0.79	0.80	0.79	0.81
	100		0.83	0.74	0.85	0.85	0.84	0.86		0.78	0.70	0.83	0.82	0.84	0.83
	150	AC	0.78	0.64	0.83	0.86	0.85	0.86	ACp	0.72	0.57	0.75	0.81	0.83	0.84
	211		0.82	0.67	0.85	0.89	0.89	0.89		0.77	0.56	0.83	0.87	0.87	0.88
	100		0.73	0.65	0.76	0.82	0.76	0.82		0.67	0.60	0.73	0.79	0.79	0.81
	150	SC	0.74	0.62	0.8	0.85	0.83	0.85	SCp	0.68	0.56	0.71	0.80	0.81	0.83
	211		0.78	0.64	0.79	0.85	0.82	0.85		0.72	0.56	0.79	0.84	0.85	0.86
	100	-	-	-	-	-	-	-		0.78	0.79	0.91	-	-	0.89
	150	-	-	-	-	-	-	-	MF	0.79	0.80	0.70	-	-	0.87
	211	-	-	-	-	-	-	-		0.77	0.63	0.91	-	-	0.90

*T: Test Case, Gr: Greedy, CC: APCC, AC: APAC, SC: APSC, CCp: APCCp, ACp: APACp, SCp: APSCp, MF: MFDC, STI: STIPI.

Table 5 . Average Values of the EMs with 25% and 50% Time Budget*

 5

	EM	#T	RS	Gr	25% time budget A1 A2	A3	STIPI	RS	Gr	50% time budget A1 A2 A3	STIPI
		100	0.37	0.30	0.55	0.51	0.62	0.66	0.52	0.65	0.65	0.67	0.70	0.73
	APCCp	150	0.35	0.59	0.52	0.45	0.66	0.71	0.50	0.81	0.74	0.63	0.72	0.74
		211	0.42	0.43	0.63	0.56	0.69	0.71	0.52	0.53	0.65	0.67	0.70	0.73
		100	0.56	0.26	0.70	0.61	0.74	0.70	0.71	0.61	0.79	0.77	0.81	0.81
	APACp	150	0.50	0.35	0.59	0.55	0.74	0.75	0.64	0.54	0.76	0.74	0.81	0.82
		211	0.58	0.33	0.71	0.65	0.77	0.75	0.71	0.52	0.79	0.81	0.85	0.85
		100	0.42	0.14	0.59	0.55	0.70	0.66	0.57	0.51	0.68	0.72	0.76	0.76
	APSCp	150	0.44	0.33	0.54	0.53	0.73	0.74	0.52	0.53	0.65	0.67	0.70	0.73
		211	0.48	0.24	0.66	0.62	0.78	0.77	0.63	0.52	0.74	0.78	0.84	0.85
		100	0.30	0.06	0.55	-	-	0.50	0.54	0.45	0.77	-	-	0.78
	MFDC	150	0.30	0.19	0.40	-	-	0.63	0.55	0.74	0.75	-	-	0.76
		211	0.29	0.09	0.52	-	-	0.44	0.53	0.48	0.75	-	-	0.76

An EM has one average value for one set of test case with one time budget (Table4 and Table 5). Thus, for 100% time budget with 3 EMs there are 9 values, and 45 average values for 4 time budgets and 4 EMs for other 3 time budgets.

Acknowledgements. This research is supported by the Research Council of Norway (RCN) funded Certus SFI. Shuai Wang is also supported by the RFF Hovedstaden funded MBE-CR project. Shaukat Ali and Tao Yue are also supported by the RCN funded Zen-Configurator project, the EU Horizon 2020 project funded U-Test, the RFF Hovedstaden funded MBE-CR project and the RCN funded MBT4CPS project.