{'fraction_non_alphanumeric': 0.028201256636306075, 'fraction_numerical': 0.00969265988018119, 'mean_word_length': 4.503082283570088, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Effectively Sampling Higher Order Mutants Using Causal Effect

Higher Order Mutation (HOM) has been proposed to avoid equivalent mutants and improve the scalability of mutation testing, but generating useful HOMs remain an expensive search problem on its own. We propose a new approach to generate Strongly Subsuming Higher Order Mutants (SSHOM) using a recently introduced Causal Program Dependence Analysis (CPDA). CPDA itself is based on program mutation, and provides quantitative estimation of how often a change of the value of a program element will cause a value change of another program element. Our SSHOM generation approach chooses pairs of program elements using heuristics based on CPDA analysis, performs First Order Mutation to the chosen pairs, and generates an HOM by combining two FOMs.


I. INTRODUCTION
Mutation testing aims to inject artificial faults (i.e., mutate the program under test) to evaluate the adequacy of the existing test suite [1]. Since the evaluation of test adequacy is based on concrete detection of actual faults (i.e., syntactic changes made to the program under test), mutation testing has great potential to improve the effectiveness of software testing. However, a couple of problems limit the practical applicability of mutation testing: the high cost of mutation analysis, in which we generate, build, and test a large number of mutants, and the existence of equivalent mutants, whose detection is theoretically undecidable.
Higher Order Mutation, in which multiple mutations are combined to create a Higher Order Mutant (HOM), has been proposed as a solution to the equivalent mutant problem. Through an empirical study, Offutt showed that approximately 10% of First Order Mutants (FOMs) are equivalent, while only about 1% of the second order mutants are equivalent [2]. However, the number of possible HOMs is far greater than that of FOMs, due to the combinatorial nature of HOMs. This exacerbates the problem of efficiency and scalability. While it is possible to devise a combinatorial approach for generation and sampling of HOMs [3], a purely combinatorial approach may fall short because HOMs are by definition easier to kill (i.e., they deviate more from the original program due to multiple mutations). A HOM that is trivial to kill may not be beneficial.
The concept of Strongly Subsuming Higher Order Mutant (SSHOM) was introduced by Jia and Harman [4]. SSHOMs are higher order mutants that are harder to kill than its constituent first order mutants. If it is possible to search for SSHOMs efficiently, it may reduce the number of HOMs we need to consider. A search based approach has been studied for the generation of SSHOMs [5]: the fitness function guides the search towards satisfying the conditions of SSHOMs.
In this paper, we propose constructive heuristics for generating SSHOMs based on a novel type of dependence analysis called Causal Program Dependence Analysis (CPDA) [6]. Based on CPDA, we propose two heuristics that are designed to sample SSHOMs not only more efficiently, but also in a way that produces diverse mutants.
Unlike traditional static dependence analysis that determines whether a program element depends on another element in a Boolean fashion, CPDA assigns quantitative likelihood values to each dependence: higher likelihood means that the change of value in one element is highly likely to cause the change in the value of another element. Using this, we can prioritise pairs of program elements in the order of the likelihood of FOMs generated at each location masking each other when combined as a HOM, in turn resulting in a SSHOM. We propose heuristics that will choose different pairs of program elements based on the results of CPDA. A case study with two small, easy to analyse programs suggests that CPDA based generation of SSHOMs can be effective.
The remainder of this paper are as follows. In Section II, we show how dependency between program elements can be used to generate strongly subsuming higher order mutants, using a motivating example. Section III introduces Causal Program Dependence Analysis, an approach to calculate dependence. Section IV introduces four heuristics for sampling higher order mutants. Section V describes the setup of our evaluation, and Section VI presents the results. Section VII presents related work, and Section VIII concludes.

II. A MOTIVATING EXAMPLE
Consider a HOM h that is composed of two FOMs, f 1 and f 2 . In order for h to be a SSHOM, there must exist at least one test, t, such that t fails due to f 1 as a FOM, which is masked by f 2 , so that t does not fail under h. For the masking to take place, it is reasonable to assume that the locations of f 1 and f 2 are connected by program dependence: otherwise, a mutation in one of the location is not likely to mask the mutation in another. Algorithm 1 contains a concrete motivating example. We are going to use Expression Replacement mutation operator to generate HOMs. Let Line 2 be one of the constituent FOMs: for example, we mutate it to a = 2. Now, let us consider the program element in Line 3. Whenever a in Line 2 gets mutated, the effect is delivered to program element in Line 3. In other words, program element in Line 3 is frequently dependent on program element in Line 2. In contrast, the variable a in Line 5 is affected by a in Line 2 only when b is even. The element in Line 5 is, therefore, less frequently dependent on element in Line 2 when compared to a in Line 3. Finally, program element in Line 6 is not dependent on a in Line 2. Now consider mutating either Line 3, 5, or 6, to mask the effect of the mutation in Line 2 towards Line 7. Mutating program element in Line 3 has highest chance of masking the first mutation, since the effect of the mutation in Line 2 is always delivered to Line 3. Mutating Line 5 can mask the fault, but with a smaller probability, since the effect of the mutation in Line 2 is only delivered when b is even. Finally, no mutation in Line 6 can mask the mutation in Line 2, since it cannot change the value of a.
Through the motivating example, we can observe that the more frequently dependence relation occurs between two program elements, the higher the chance of fault masking will be. The fact that we need program dependence relationship between two program elements for fault masking to happen may be a trivial observation. However, what Causal Program Dependence Analysis allows us to reason about is the relative likelihood of a dependence relationship actually affecting the value of a specific program element. Unlike traditional dependence analysis whose outcome is binary (either dependent or not), CPDA allows us to reason about the degree of dependence quantitatively. We will present a brief introduction to CPDA in Section III.

III. CAUSAL PROGRAM DEPENDENCE ANALYSIS
Causal Program Dependence Analysis (CPDA), a recently introduced dynamic program dependence analysis technique, can measure the degree of dependence between two program elements [6]. Applying the causal inference [7] on the program execution trajectory, CPDA estimates how often a change of the value of a program element causes a change of the value of another program element. CPDA calculates the dependence by a given test suite. CPDA first generates data on which program element's values are associated. It gets association data by running tests on programs that have modified part of the code in various ways, observing which program elements have simultaneously changed compared to the values they had in the original program. Given the association data, CPDA discovers the causal structure of the program. The causal structure is a directed graph that represents the direct dependence between program elements; for each child node in the causal structure, the set of parent nodes (immediate predecessor nodes) comprises a minimal Markov blanket of the behavior of the child node [7]. Using the association data and discovered causal structure, CPDA estimates two metrics representing the degree of dependence. A causal effect is an aggregate of the effect of each program element's change causing a change in other program elements. A direct effect is the effect of one program element on another, excluding all the indirect effects through other program elements.
Given association data O, the causal effect from a program element S i to the other program element S j , denoted as CE O (S 1 , S j ), is calculated as follows: . In the equation, S j = 1 implies the value of the program element S j is changed compared to the original program, or otherwise, S j = 0. P O (x | do(y)) calculates the probability of an event x caused by the event y [7]. The causal effect aims to measure the difference of the effect that S j gets when S i moves its state from unchanged (0) to changed (1). Instead of subtracting the probability, we multiply the probability when S i = 1 and the complementary probability when S i = 0, keeps the causal effect having a positive value.
From the example in Sec. II, SSHOMs can be created more easily from pairs of program locations that affect more frequently. Thus, we claim that we could efficiently search the higher-order mutant space to sample SSHOMs by utilizing the CPDA. Our main hypothesis is that the causal effect could prioritize the second-order mutation position for SSHOMs. Our empirical evaluation investigates whether there is a positive correlation between the high causal effect and the strongly subsuming rate. Assuming the hypothesis is plausible, setting up an actual guideline for searching on the higher-order mutant space is needed. In the next section, we introduce several heuristics that can efficiently sample the higher-order mutant using the causal effect.

IV. HEURISTICS FOR SSHOM GENERATION
In this section, we introduce heuristics to effectively sample second order mutants (SOM).

A. Heuristics for selecting SOM
In order to search for efficient methods of sampling second order mutants we came up with four heuristics: Random, Prop, Dsort, and MWM. The purpose of each heuristic is to 1) sample as much SSHOM as possible with fixed number of mutants, 2) sample diverse mutants. Therefore, each heuristic tries to find the best pair of program elements to generate the second order mutants along with the number of mutants to generate per pair. While we investigate through second order mutants, it can easily be extended to select three for more mutation locations utilizing the causal effect (e.g., choosing n locations whose sum of the pairwise causal effect is high.) All heuristics other than Random approach make use of the dependency calculated in terms of causal effect. Therefore, modeling CPDA and calculating the causal effect comes firsthand for the three last heuristics.
The four heuristics are as follows. 1) Random: Among all possible pairs of program elements, we choose a random pair. We repeat this process independently for number of total mutants, while allowing duplicates. If a certain pair is selected k times, we create k mutants by mutating the pair of program elements.
2) Prop (Proportional): We first weight each pair of program elements with their causal effect values. Subsequently, we choose a pair with a probability proportional to its weight. Let PP be the set of all pairs of program elements. Let CE(p i ) be the causal effect value of p i ∈ PP . The probability of p i being selected, P (p i ) is: Note that, according to Equation 1, a pair with causal effect value of 0 cannot be selected. We repeat this process of choosing a pair for number of total mutants. Similar to Random, if a pair of program elements is selected k times, we build k mutants by mutating the pair.
3) Dsort (Descending Sort): With Dsort, we sort all pairs of program elements according to their causal effect values, and choose the top n pairs. Subsequently, we distribute the number of mutants to generate, k, equally to the chosen n pairs. In our evaluation, we set n for Dsort as the number of pairs selected by the MWM heuristic.

4) MWM (Maximum Weight Matching):
While Dsort picks program pairs by considering solely causal effect, MWM considers the diversity of the mutant set. Since the purpose of each mutant is to mimic real faults of developers a good mutant set should contain diverse mutants rather than mutants with similar faults.
To sample diverse set of mutants, we utilize maximum weight matching from graph theory. A set M of independent edges in a graph G = (V, E) is called a matching [8]. A maximum weight matching M of graph G = (V, E) where every edge e ∈ E have weight w e is set M of independent edges maximizing the sum of weights of edges in M .
To perform maximum weight matching with respect to causal effects in the program, we modify the causal structure G. Whenever there is a path from v 1 to v 2 , we add a directed edge from v 1 to v 2 . Subsequently, we weight all edges: the weight of e from v 1 to v 2 is the causal effect v 2 gets from v 1 .
After modifying the causal structure G we compute the maximum weight matching of G. The aim is not only to select pairs with high dependency, but also to select a diverse set of program pairs across the entire program. Similar to Dsort, total number of mutants to be made is then distributed equally to all program pairs, making same number of second order mutants per pair.
V. EXPERIMENTAL SETUP A. Research Questions RQ1. Causal Effect and SSHOM: Does high Causal Effect lead to strongly subsuming second order mutant? To answer this question, we first calculate causal effects between program elements of studied programs. We then distribute the pairs with non-zero causal effect values into ten equal size buckets; we also group all pairs with causal effect value of 0 in a separate bucket. Subsequently, we randomly select five program element pairs from each of the 11 buckets, and generate 100 second order HOMs from each pair. We then calculated the number of SSHOM made from each bucket. We repeat this ten times to remove the sampling bias.
RQ2. SSHOM Heuristics: How do different heuristics compare to each other in terms of the number of SSHOMs generated, as well as their diversity? We implemented all introduced heuristics and calculated the rate of SSHOMs, as well as the diversity metric. We generate 1,000 HOMs for each heuristic, and repeat the process five times to remove the sampling bias.
RQ3. HOM Survival Rate: Which algorithm achieves the highest survival rate? We compared the survival rate of HOMs generated with each heuristic, along with the FOMs. The purpose of RQ3 is to see to what extent higher order mutants can survive compared to current First Order Mutation testing. For FOMs, we sample 1,000 mutants generated by MUSIC [9].

B. Diversity Metric
We measure the diversity of mutant set by comparing the set of test cases that kill each mutant . For a mutant m of original program P with test suite T , a kill vector v ∈ R |T | of m is defined as follows.
The diversity of set of mutants M = {m 1 , m 2 , . . . , m k } is then defined as follows.
where v i is the kill vector of m i , and the numerator represents the number of distinct kill vectors. A higher dScore is achieved if the mutant set contains more mutants with distinct kill vectors. The reason we define diversity with kill vectors is because two mutants with same kill vectors are not distinguishable from the point of test suite [10].

C. Benchmark Programs
We study two C programs: a toy example called Bill's Car, and schedule from the SIR benchmark [11].
1) Bill's Car: Algorithm 2 shows Bill's Car, which is a C program that calculates parking fees. The fee depends on the day of the week, the car type, and minutes stayed in the parking zone. There are three kinds of vehicle types. Senior, car, and truck. The fee structure, as well as discounts based on the day of week, means that the program contains nontrivial dependence structure.  vehicle types, three categories of days of week, and 11 different time intervals (0 to 1,000 minutes at intervals of 100): this results in 3 × 3 × 11 test cases. We add two edge cases, one with invalid car type and the other with missing arguments (only car type specified). We use 6,400 mutants (100 mutants for each of 64 program elements) to build CPDA.
2) Schedule: Schedule is a C program from the Softwareartifact Infrastructure Repository [11]. It is a schedule that calculates an ordering of given tasks. We use the coverageextended test suite 456, which contains 81 test cases. To build CPDA, we use 940 mutants (10 mutants for each of 94 program elements).

D. Implementation and Environment
Every first order mutants are made by C mutation testing tool, MUSIC [9]. Second order HOMs are generated by independently mutating program elements in the given pair, and combining the mutated lines. We use the networkx Python library to compute maximum weight matching.
Experiments for Bill's Car was ran on Ubuntu 18.04, Intel(R) Core(TM) i7-10700 CPU @ 2.90GHz with GeForce RTX 3070. Experiments for schedule was ran on Ubuntu 16.04.5, Intel(R) Core(TM) i7-6700 CPU @ 3.40GHz with GeForce GTX 1080. Table I shows the results of the bucketing analysis for RQ1. While Bill's Car had more program element pairs with zero causal effect, Schedule had more program element pairs with positive causal effects. For Bill's Car, 2.25% of the total pair of program elements turned out to have causal effect value over 0.5 while for Schedule 18% of pairs were. The range of causal effect values for each bucket tends to increase. Average range of first three buckets for the two benchmark programs was 0.056, while the average range of final three buckets was 0.214. This suggests that the space of program pairs get sparse as the causal effect value goes up.  Table I. We were able to observe that the top bucket does significantly better job of generating SSHOM than other buckets. Since number of program element pairs in the top bucket are much smaller than total pairs (6.85% for Schedule, 2.40% for Bill's Car), we can significantly reduce the search space for second order HOMs by focusing on the pairs in the top bucket. Based on these results, we conclude that mutating program elements with high causal effect can lead to the generation of SSHOMs with higher probability.  B. RQ2: Performance of each Heuristic Figure 2 shows for each benchmark programs the number of evaluated SSHOM, dScore, and the number of distinct kill vectors for the generated SSHOM. Table II shows   However, the higher diversity of chosen pairs results in higher dScore. Figure 2(b) and 2(d) shows boxplots of the unique number of SSHOMs generated by different heuristics. MWM produces more unique SSHOMs for Bill's Car than Dsort, but the trend is the opposite in Schedule. We suspect that diversity of HOMs in general (captured by dScore in Table II), and the diversity of SSHOMs, may not align perfectly.  Figure 3(a) and 3(b) visualises the program element pairs chosen by MWM and Dsort. The causal structure is shown in gray edges, while chosen pairs are shown with blue arrowed edges. While chosen pairs from MWM tend to be spread out in various places by not sharing common vertices, pairs from Dsort does overlap and tend to cover only some specific regions of the program, as expected.   Table III. It shows that HOMs are easier to kill, possibly due to the larger semantic differences.

A. RQ1: Causal Effect and number of SSHOM
Among the proposed heuristics, MWM showed highest number of surviving mutants, followed by Random. Dsort shows the lowest survival rate. The survival rate differs a lot for Bill's Car while there are not so much variance in Schedule.
We observe that, in Bill's Car, there are specific program locations that produce more surviving mutants than others. For example, mutants generated in the flow of PrintFee function tend to survive more. Since the main objective of the function is to print status, the return value is not used anywhere. Consequently, it is harder to kill.
We also observe that pairs with high causal effect values tend to exist in the part of program with main functionalities. For example, pairs chosen by Dsort from Bill's Car are mostly from functions calculating the fee, while MWM also chooses from the PrintFee function, resulting in a higher survival rate. Random and Prop all showed high survival rate due to a similar reason. In Schedule, survival rates of mutants are not significantly affected by the location of mutation.