# ImReMuDF: Redundant Mutants Identification Method Based on Definition and Reference of Variables

Authors: Zhenpeng Liu; Xianwei Yang; Yi Liu; Yonggang Zhao; Xiaofei Li
Journal: Scientific Programming
 (2021)

---

## Abstract

Mutation testing is an effective defect-based software testing method, but a large number of mutants lead to expensive testing costs, which hinders the application of variation testing in industrial engineering. To solve this problem and enable mutation testing to be applied in industrial engineering, this paper improves the method of identifying redundant mutants based on data flow analysis and proposes the inclusion relationship between redundant mutants, so that the redundancy rate of mutants is reduced. In turn, the cost of mutation testing can be reduced. The redundant mutants identification method based on definition and reference of variables (ImReMuDF) was validated and evaluated using 8 C programs. The minimum improvement in redundant mutant identification rate was 34.0%, and the maximum improvement was 71.3% in the 8 C programs tested, and the verification results showed that the method is feasible and effective and has been improved in reducing redundant mutants and effectively reducing the execution time of mutation testing.


---

## Body

## 1. Introduction

Mutation testing is a fault-based software testing technique [1] that has received a great deal of attention in program analysis, defect detection, and test case generation [2]. Mutation testing not only has the advantages of strong troubleshooting ability, convenience, and flexibility, but also can be used to expose defects in the software, and it has the ability to measure the error found in the test data set and evaluate the adequacy of the test [3]. Mutation testing has strong fault detection capabilities [4]. Mutation testing technology has gradually become popular in the industry [5] but has not been widely used. The reason is that running and analyzing tests are expensive in terms of resources and manpower [6], the computational cost of mutation testing is high, the identification of equivalent mutations is difficult, the effective automated mutation testing tools are not perfect, etc. [7].The concept of mutation testing was first proposed by Demillo [8], which refers to the execution of mutation operations on the original program to generate a new program (program with defects), and the new program is called a mutant. Subsequently, a large number of scientific research results appeared. In terms of reducing the number of mutants, Wong [9] proposed random selection of mutants to achieve the purpose of reducing the number of mutants. Sridharan and Namin [10] proposed the preferential selection of more informative mutation operators. Usaola et al. [11] proposed the minimization of test cases to reduce the time of mutation testing. Sun et al. [12] proposed a method for identifying redundant mutants based on data flow analysis. Chekam et al. [13, 14] proposed a dynamic symbolic execution method and a mutant priority method. Shomali and Arasteh [15] proposed the firefly optimization algorithm as a heuristic algorithm for identifying the most error-prone path in the program. Hooseini et al. [16] proposed a genetic algorithm to identify the path where the program is most likely to propagate errors as the mutation location. In terms of shortening the time of mutation testing, Krauser et al. [17] proposed parallel execution of mutants. King and Offutt [18] proposed prioritization of mutation compilation. Although the above method optimizes the mutation testing from different aspects, it is not perfect in terms of adequacy assessment, and it still has a certain impact on adequacy. The method proposed by Sun et al. reduces the mutants caused by variables very well. It reduces the execution time of mutation testing by reducing the number of mutants, but it does not extend well to the identification of redundant mutants of multiple variables.In order to increase the recognition rate of redundant mutants and reduce redundant mutants, this paper proposes a redundant mutants identification method based on definition and reference of variables (ImReMuDF). The main contributions of this paper are as follows:(1)
The definition and reference of two variables are proposed to increase the recognition rate of redundant mutants in the test.(2)
In the definition and reference of two variables, the inclusion relationship of the variables in the same situation is introduced. This method improves the identification of redundant mutants caused by variables, thereby achieving the purpose of reducing the number of mutants.(3)
In 8 C program experiments, the effectiveness and feasibility of this method are verified.Compared with the definition and reference of one variable, the ImReMuDF method can be extended to the definition and reference of multiple variables to identify redundant mutants.


## 2. Identification of Redundant Mutants

### 2.1. Traditional Mutation Testing

In traditional mutation testing, errors are embedded into the program through mutant operators [19] or manually, and then the embedded defects are detected by test cases, and the adequacy of defect detection is determined by the mutation score. Given the tested program P and the set of test cases T, the tested program P uses mutation operators or manual embedding errors to generate a set of mutants M. It is very important to identify equivalent mutants and nonequivalent mutants in the mutation testing [20]. The traditional mutation testing process is shown in Figure 1. The traditional mutation testing process is as follows:(1)
The set of mutants identifies and classifies the set of equivalent mutantsI and the set of nonequivalent mutants L(2)
Run the set of test casesTT=T∪t on the set L(3)
Calculate the mutation score for the set of test casesT(4)
If the mutation testing meets the requirements, exit; if the mutation testing does not meet the requirements, add a new test caset and repeat the (2)-(3) operationsFigure 1
Traditional mutation testing process.


### 2.2. Redundant Mutant

In mutation testing, the adequacy of the test case set is evaluated by the ratio of the number of detected mutants to the total mutants. In mutation testing, a large number of redundant mutants bring a large number of repeated checks to the mutation testing. On the one hand, it increases the test time, and on the other hand, it brings expensive test costs. Therefore, a large number of redundant mutants must be removed before mutation testing. The removed mutants will not be repeatedly tested, reducing the time of mutation testing, to achieve the purpose of saving test costs.The redundant mutants are shown in Figure2. In Figure 2, it can be found that the mutants m1 and m2 mutate in the 3rd and 4th rows, respectively. Although the position of the mutation has changed, the program status below the mutation location is similar. In the mutation testing, if there is a test case that can execute the above code, it must be able to kill mutants m1 and m2. In the calculation of the mutation score, since whether the mutant can be killed can be obtained by the test result of the mutant m2, only the mutant m1 needs to be executed during the mutation testing, and the mutant m2 is not executed.Figure 2
Examples of redundant mutant.Given the programP and the mutant m1 generated by the mutation operator, if the output results of the program P and the mutant m1 are not equal when running on the test case t, then the mutation testing is called strong mutation testing. Given the program P and the mutant m2 generated by the mutation operator, if the state of the program P and the mutant m2 is inconsistent when running on the test case t, then the mutation testing is called weak mutation testing. Compared with strong mutation testing, weak mutation testing has the advantage of shortening the test time. As can be seen from the above description, traditional mutation testing is based on strong mutation testing. This paper is to optimize the execution time of the mutation testing based on the weak mutation testing.Definition 1.
(inclusive relationship between mutants). Given the program P to be tested and an input t=t=tii=1,2,…,n containing n-tuples, all possible t forms the input space T of the program P. Suppose there are two mutants m1 and m2 generated by P, and the output states of P and m when the input is t are Pt and mt, respectively; the mutant m1 including the mutant m2 must meet the two following conditions:(1)
∃t∈T,pt≠m1t∧pt≠m2t(2)
Tm1⊆Tm2,Tm=t∈T|pt≠mt
Then, it can be expressed asm1↦m2.
Based on the above analysis, whenTm1⊆Tm2,Tm=t∈T|pt≠mt exists between the mutants, and m1 and m2 meet Definition 1, m2 is called the redundant mutant of m1. Assuming that there are sets of mutants M1 and M2 satisfying ∀mi∈M2, ∃mj∈M1, where mi∈mj, then M2 is called the set of redundant mutants, and M1 is the set of nonredundant mutants.


### 2.3. Data Flow Analysis

Data flow analysis is a technology used during compilation. And data flow analysis plays an important role in program analysis, compilation optimization, program verification, defect detection, etc. [2]. Data flow analysis mainly focuses on the data flow or possible values on the program execution path. Its purpose is to determine the relationship between variable definitions and references within a certain range of the program [21]. Therefore, the following two definitions are given.Definition 2.
(definition set and reference set). Definable set: in the programP, if x exists in the assignment statement y, and the variable value of x changes, then x is an assignment variable, which can be expressed as(1)defy=x|xis the assignment variable in the y statement.
Reference set: in the programP, if x exists in the assignment statement y, and the variable value of x does not change, then x is a reference variable, which can be expressed as(2)refy=x|xis the reference variable in theystatement.Definition 3.
(reference chain). In PDG [22], there is a path from defu,v,s1 to refu,v,s2, and there is no other path from s1 to s2, then there is a definition-reference Chain of variables u and v, denoted as dru,v,s1,s2.


### 2.4. Improved Redundant Mutant Identification Steps

When performing redundant mutant detection on the mutant setM, firstly, a series of information about each mutant is obtained; then, after the identification rules, the redundant mutants in the mutant set are identified; finally, the redundant mutants are removed from the mutant set, and a new mutant set is output. The redundant mutant process of data flow analysis is as follows:(1)
The program structure of the programP to be tested is analyzed, and the block rule file of the program is obtained(2)
Compare the mutant program and the source program one by one to obtain the mutation location of the mutants(3)
Determine the class of the mutant according to the block rule file(4)
Analyze the data flow of the source program, and generate data flow information such as variable definition, variable reference, and definition-reference chain;(5)
Identify the set of redundant mutants according to the redundant mutant identification rules and combining the block categories of the mutants and information of the program data flow(6)
Output the set of mutantsThe process of identifying redundant mutants based on data flow analysis is shown in Figure3.Figure 3
Redundant mutant identification by data flow analysis.In redundant mutant based on data flow analysis, program structure analysis and mutation location analysis are applied to mutation testing tools [23]. In this paper, the data flow analysis is implemented using Frama-C [24].Time complexity analysis of the algorithm: suppose that the number of mutants of the program to be tested isn, and the number of definition-reference chains is m. In the algorithm, each definition-reference chain needs to traverse the entire set of mutants, so the time complexity of obtaining the set of definition mutants and reference mutants is On; when the definition-reference chain meets the identification rules, it is necessary to traverse entire mutants in the set of reference mutant of the variable, so the time complexity is Om. Therefore, the time complexity of the algorithm is On×m.


## 2.1. Traditional Mutation Testing

In traditional mutation testing, errors are embedded into the program through mutant operators [19] or manually, and then the embedded defects are detected by test cases, and the adequacy of defect detection is determined by the mutation score. Given the tested program P and the set of test cases T, the tested program P uses mutation operators or manual embedding errors to generate a set of mutants M. It is very important to identify equivalent mutants and nonequivalent mutants in the mutation testing [20]. The traditional mutation testing process is shown in Figure 1. The traditional mutation testing process is as follows:(1)
The set of mutants identifies and classifies the set of equivalent mutantsI and the set of nonequivalent mutants L(2)
Run the set of test casesTT=T∪t on the set L(3)
Calculate the mutation score for the set of test casesT(4)
If the mutation testing meets the requirements, exit; if the mutation testing does not meet the requirements, add a new test caset and repeat the (2)-(3) operationsFigure 1
Traditional mutation testing process.


## 2.2. Redundant Mutant

In mutation testing, the adequacy of the test case set is evaluated by the ratio of the number of detected mutants to the total mutants. In mutation testing, a large number of redundant mutants bring a large number of repeated checks to the mutation testing. On the one hand, it increases the test time, and on the other hand, it brings expensive test costs. Therefore, a large number of redundant mutants must be removed before mutation testing. The removed mutants will not be repeatedly tested, reducing the time of mutation testing, to achieve the purpose of saving test costs.The redundant mutants are shown in Figure2. In Figure 2, it can be found that the mutants m1 and m2 mutate in the 3rd and 4th rows, respectively. Although the position of the mutation has changed, the program status below the mutation location is similar. In the mutation testing, if there is a test case that can execute the above code, it must be able to kill mutants m1 and m2. In the calculation of the mutation score, since whether the mutant can be killed can be obtained by the test result of the mutant m2, only the mutant m1 needs to be executed during the mutation testing, and the mutant m2 is not executed.Figure 2
Examples of redundant mutant.Given the programP and the mutant m1 generated by the mutation operator, if the output results of the program P and the mutant m1 are not equal when running on the test case t, then the mutation testing is called strong mutation testing. Given the program P and the mutant m2 generated by the mutation operator, if the state of the program P and the mutant m2 is inconsistent when running on the test case t, then the mutation testing is called weak mutation testing. Compared with strong mutation testing, weak mutation testing has the advantage of shortening the test time. As can be seen from the above description, traditional mutation testing is based on strong mutation testing. This paper is to optimize the execution time of the mutation testing based on the weak mutation testing.Definition 1.
(inclusive relationship between mutants). Given the program P to be tested and an input t=t=tii=1,2,…,n containing n-tuples, all possible t forms the input space T of the program P. Suppose there are two mutants m1 and m2 generated by P, and the output states of P and m when the input is t are Pt and mt, respectively; the mutant m1 including the mutant m2 must meet the two following conditions:(1)
∃t∈T,pt≠m1t∧pt≠m2t(2)
Tm1⊆Tm2,Tm=t∈T|pt≠mt
Then, it can be expressed asm1↦m2.
Based on the above analysis, whenTm1⊆Tm2,Tm=t∈T|pt≠mt exists between the mutants, and m1 and m2 meet Definition 1, m2 is called the redundant mutant of m1. Assuming that there are sets of mutants M1 and M2 satisfying ∀mi∈M2, ∃mj∈M1, where mi∈mj, then M2 is called the set of redundant mutants, and M1 is the set of nonredundant mutants.


## 2.3. Data Flow Analysis

Data flow analysis is a technology used during compilation. And data flow analysis plays an important role in program analysis, compilation optimization, program verification, defect detection, etc. [2]. Data flow analysis mainly focuses on the data flow or possible values on the program execution path. Its purpose is to determine the relationship between variable definitions and references within a certain range of the program [21]. Therefore, the following two definitions are given.Definition 2.
(definition set and reference set). Definable set: in the programP, if x exists in the assignment statement y, and the variable value of x changes, then x is an assignment variable, which can be expressed as(1)defy=x|xis the assignment variable in the y statement.
Reference set: in the programP, if x exists in the assignment statement y, and the variable value of x does not change, then x is a reference variable, which can be expressed as(2)refy=x|xis the reference variable in theystatement.Definition 3.
(reference chain). In PDG [22], there is a path from defu,v,s1 to refu,v,s2, and there is no other path from s1 to s2, then there is a definition-reference Chain of variables u and v, denoted as dru,v,s1,s2.


## 2.4. Improved Redundant Mutant Identification Steps

When performing redundant mutant detection on the mutant setM, firstly, a series of information about each mutant is obtained; then, after the identification rules, the redundant mutants in the mutant set are identified; finally, the redundant mutants are removed from the mutant set, and a new mutant set is output. The redundant mutant process of data flow analysis is as follows:(1)
The program structure of the programP to be tested is analyzed, and the block rule file of the program is obtained(2)
Compare the mutant program and the source program one by one to obtain the mutation location of the mutants(3)
Determine the class of the mutant according to the block rule file(4)
Analyze the data flow of the source program, and generate data flow information such as variable definition, variable reference, and definition-reference chain;(5)
Identify the set of redundant mutants according to the redundant mutant identification rules and combining the block categories of the mutants and information of the program data flow(6)
Output the set of mutantsThe process of identifying redundant mutants based on data flow analysis is shown in Figure3.Figure 3
Redundant mutant identification by data flow analysis.In redundant mutant based on data flow analysis, program structure analysis and mutation location analysis are applied to mutation testing tools [23]. In this paper, the data flow analysis is implemented using Frama-C [24].Time complexity analysis of the algorithm: suppose that the number of mutants of the program to be tested isn, and the number of definition-reference chains is m. In the algorithm, each definition-reference chain needs to traverse the entire set of mutants, so the time complexity of obtaining the set of definition mutants and reference mutants is On; when the definition-reference chain meets the identification rules, it is necessary to traverse entire mutants in the set of reference mutant of the variable, so the time complexity is Om. Therefore, the time complexity of the algorithm is On×m.


## 3. Identification Rules of Redundant Mutant

When mutants undergo static analysis, the following three aspects need to be qualified: (1) the set of mutants with similar mutation locations; (2) the set of mutants with the same predecessor path conditions; (3) the set of mutants with similar program states (the state of the program after the mutation location). In the case of redundant mutant identification, to ensure the existence of a reachable path from variable definition to use between the source mutant and the mutation location of the redundant mutant, the solution is to set the analysis location after the mutant is used. Based on the above principles, the redundant mutant identification rules are defined in 4 dimensions (intrablock, sequential block, subfast, and intermodule) in the technique of data flow analysis.


### 3.1. Identification Rule 1 (D1)

Suppose that there is a definition-reference chaindru,v,s1,s2 in the program, let mutant mi=1,2,3 be the definition mutant set Mdef,u,v,s1 of variable u, v, and let mutant mj=1,2,3 be the reference mutant set Mref,u,v,s2 of variable u, v. When s1 and s2 are in the same basic block and in the definition mutant set, m1↦m2,m3. It can be concluded that mx=2,3,…,6 is a redundant mutant of m1.According to the identification ruleD1 of the definition, it is qualified that its source variant m1 and redundant mutants mx=2,3,…,6 belong to the same basic block. mi=1,2,3 and mj=1,2,3 are defined by the variable definability appearing in the s1 statement (mx=2,3,…,6) and the variable reference line appearing in the s2 statement ref,u,v,s2, respectively, where the s1 statement and the s2 statement belong to the BasicBlockn. From the data flow analysis technique, we can know that if the execution of s1 in mi is triggered in the mutation test, it can cause the execution of s2 in mj, and then the definition-reference company can ensure the propagation of the state at s1 to s2. Based on the inclusion relationship between mutants and the definition of redundant mutant, mx=2,3,…,6 can be identified as a redundant mutant of m1. Figure 4 shows an example of the D1 identification rule application.Figure 4
Example program for identifying ruleD1.In the mutantsmi=1,2,3, the variables x and y are defined in the 4th and 5th lines defx,y,4,5, and in the mutants mj=4,5,6, the variables x and y are referenced in the 6th line refx,y,6. In the mutants mi=1,2,3, the changes in the value of the variable in the definition mutant set Mdef,x,y,4,5 of the variables x and y will cause the value of the variable temp in the 6th line of the program to change. In the mutants mj=4,5,6, the reference mutant set Mref,x,y,6 of the variables x and y has a direct effect on the value of the variable temp in the program. Due to the definition-reference chain drx,y,4,5,6, the 6 mutants entirely have the same change state in the 6th row; that is, mx=2,3,…,6 are redundant mutants of m1.


### 3.2. Identification Rule 2 (D2)

Assuming the existence of a definition-reference chaindru,v,s1,s2, let mutant mi=1,2,3 be the definition mutation set Mdef,u,v,s1 of variable u, v, and let mutant mj=1,2,3 be the reference mutation set Mref,u,v,s2 of variable u, v. s1, belongs to the program block bn (bn is one of the BasicBlock, OptiomBlock, and LoopBlock), and s2 belongs to BasicBlocki, where bn and BasicBlocki satisfy the sequential block relationship and meet Definition 1 in s1. It can be concluded that mx=2,3,…,6 is a redundant mutant of m1.According to the defined identification ruleD2, it is qualified that its mutant mi=1,2,3 and mutant mj=4,5,6 belong to the sequential block relationship. mi=1,2,3 and mj=4,5,6 are variables defined, respectively, in the s2 statement def,u,v,s1 and referenced in the s2 statement ref,u,v,s2, where s1 belongs to program block bn (bn is one of the BasicBlock, OptiomBlock, and LoopBlock) and s2 belongs to BasicBlocki. According to the definition of the sequential block, in the mutation testing, if the execution condition of s1 in mi is triggered, it will cause the execution of s2 in mj. Then, the definition-reference chain of the variable can ensure that the state at s1 is propagated to s2. Based on the inclusion relationship between mutants and the definition of redundant mutants, mx=2,3,…,6 can be identified as redundant mutants of m1. An example of the recognition rule is shown in Figure 4 below. Figure 5 shows an example of the D2 identification rule application.Figure 5
Example program for identifying ruleD2.The source program in Figure5 is divided into blocks. It can be seen that lines 3, 4, and 5 belong to the same BasicBlock (b1), lines 6, 7, and 8 belong to the same BasicBlock (b2), and line 9 belongs to the same BasicBlock (b3). The definitions of the variables x and y are in the 4th and 5th lines, expressed as (defx,y,4,5), and the references to the variables x and y are in the 9th line, expressed as (refx,y,9). b2 is the sequential block of b1, and b3 is the sequential block of b2, so b3 is the indirect block of b1. The mutants mi=1,2,3 belong to the definition mutation set Mdef,x,y,4,5 of the variables x and y. If the values of the variables x and y change, the influence of the program is propagated to line 9 by reference to the variables x and y, thereby changing the value of the variable temp. The mutants mj=4,5,6 belong to the reference mutation set Mref,x,y,9 of the variables x and y, and the changes in the values of the variables x and y directly affect the value of the variable temp. From the definition-reference chain drx,y,4,5,9, it can be seen that the 6 mutants have the same change state in the 9th row; that is, mx=2,3,…,6 are redundant mutants of m1.


### 3.3. Identification Rule 3 (D3)

Assuming the existence of a definition-reference chaindru,v,s1,s2, let mutant mi=1,2,3 be the definition mutation set Mdef,u,v,s1 of variables u, v, and let mutant mj=4,5,6 be the reference mutation set Mref,u,v,s2 of variables u, v. When s1 belongs to program block bn (bn is one of the BasicBlock, OptiomBlock, and LoopBlock), and s2 belongs to BasicBlocki, BasicBlocki is the sequential block of the subblock of bn and meets Definition 1 in s1. It can be concluded that mx=2,3,…,6 are redundant mutants of m1.According to the identification ruleD3, it is qualified that the relationship between the mutants mi=1,2,3 and mutants mj=4,5,6 is defined as a composite of the relationship of the subblock and the sequential block. mi=1,2,3 and mj=4,5,6 are variables defined, respectively, in the s2 statement (def,u,v,s1) and referenced in the s2 statement (ref,u,v,s2). s1 belongs to program block bn (bn is one of the BasicBlock, OptiomBlock, and LoopBlock) and s2 belongs to BasicBlocki, where bn and BasicBlockn directly or indirectly satisfy the composite of the relationship of the subblock and the sequential block. It can be known from the subblock relationship that, in the mutation testing, if bn is executed, its upper block will be executed, and then the sequential block BasicBlockn will be executed. The definition-reference chain can ensure that the error state at s1 is propagated to s2. According to the inclusion relationship between mutants and the definition of redundant mutants, mx=2,3,…,6 can be identified as the redundant mutant of m1. Figure 6 shows an example of the D3 identification rule application.Figure 6
Example program for identifying ruleD3.The source program in Figure6 is divided into blocks. It can be seen that lines 3, 4, 5, and 6 belong to the same loop block (b1), lines 4 and 5 belong to the same basic block (b2), and line 7 belongs to the same basic block (b3). b1 is the upper block of b2, and b3 is the sequential block of b1. The definitions of the variables x and y are in the 4th and 5th lines, expressed as defx,y,4,5,), and the references to the variables x and y are in the 9th line, expressed as refx,y,9. The mutants mi=1,2,3 belong to the definition mutation set Mdef,x,y,4,5 of the variables x and y. The change of variables x and y changes the value of the variable sum by refx,y,7 in line 7. mj=4,5,6 directly affect the change of the value of the variable sum by referencing the variables x and y. From the definition-reference chain drx,y,4,5,7, it can be seen that the 6 mutants have the same change state in the 7th row; that is, mx=2,3,…,6 are redundant mutants of m1.


### 3.4. Identification Rule 4 (D4)

Suppose that there exists a definition-reference chaindru,v,s1,s2, let mutants mi=1,2,3 be the definition mutation set Mdef,u,v,s1 of the variables u, v, and let mutants mj=4,5,6 be the reference mutation set Mref,u,v,s2 of the variables u, v. If s1 is a function call statement i⟶∗j in module i with the variables u, v as arguments, s2 belongs to a BasicBlockj in module j, SBasicBlockj=∅ and meets Definition 1 in s1. It can be concluded that mx=2,3,…,6 are redundant mutants of m1.According to the identification ruleD4, it is qualified that mutants mi=1,2,3 and mutants mj=4,5,6 belong to the cross-module relationship. mi=1,2,3 and mj=4,5,6 are the block, where the variable definitional appearance (def,u,v,s1) is located as bn∈i, and the variable reference line appears in the BasicBlockn∈j where (ref,u,v,s2) is located, and there is a call relationship i⟶∗j between bn and BasicBlockn, and BasicBlockn has no subblock relationship in module j. From this, it can be deduced that, after the execution of bn, BasicBlockn must be executed, and then the definition-reference chain can ensure that the error state at s1 is propagated to s2. Based on the inclusion relationship between mutants and the definition of redundant mutants, mx=2,3,…,6 can be identified as redundant mutants of m1. Figure 7 shows an example of the D4 identification rule application.Figure 7
Example program for identifying ruleD4.Themul function is called by the f function in the third line, and the passing parameters are the variables x and y. The definition of variables x and y in the mutants mi=1,2,3 is represented as defx,y,3, and the references in the mutants mj=4,5,6 are represented as refx,y,6. mi=1,2,3 belong to the definition mutation set Mdef,x,y,3 of variables x and y. The change of the variable will affect the return value of the function, and the value of the variable mulp in the program can be changed through the call of the function. mj=4,5,6 belong to the reference mutation set Mref,x,y,5 of the variables x and y, and the reference of variables x and y will directly affect the value of the variable mulp. From the definition-reference chain drx,y,3,6, it can be seen that the 6 mutants have the same change state in the 6th row; that is, mx=2,3,…,6 are redundant mutants of m1.


## 3.1. Identification Rule 1 (D1)

Suppose that there is a definition-reference chaindru,v,s1,s2 in the program, let mutant mi=1,2,3 be the definition mutant set Mdef,u,v,s1 of variable u, v, and let mutant mj=1,2,3 be the reference mutant set Mref,u,v,s2 of variable u, v. When s1 and s2 are in the same basic block and in the definition mutant set, m1↦m2,m3. It can be concluded that mx=2,3,…,6 is a redundant mutant of m1.According to the identification ruleD1 of the definition, it is qualified that its source variant m1 and redundant mutants mx=2,3,…,6 belong to the same basic block. mi=1,2,3 and mj=1,2,3 are defined by the variable definability appearing in the s1 statement (mx=2,3,…,6) and the variable reference line appearing in the s2 statement ref,u,v,s2, respectively, where the s1 statement and the s2 statement belong to the BasicBlockn. From the data flow analysis technique, we can know that if the execution of s1 in mi is triggered in the mutation test, it can cause the execution of s2 in mj, and then the definition-reference company can ensure the propagation of the state at s1 to s2. Based on the inclusion relationship between mutants and the definition of redundant mutant, mx=2,3,…,6 can be identified as a redundant mutant of m1. Figure 4 shows an example of the D1 identification rule application.Figure 4
Example program for identifying ruleD1.In the mutantsmi=1,2,3, the variables x and y are defined in the 4th and 5th lines defx,y,4,5, and in the mutants mj=4,5,6, the variables x and y are referenced in the 6th line refx,y,6. In the mutants mi=1,2,3, the changes in the value of the variable in the definition mutant set Mdef,x,y,4,5 of the variables x and y will cause the value of the variable temp in the 6th line of the program to change. In the mutants mj=4,5,6, the reference mutant set Mref,x,y,6 of the variables x and y has a direct effect on the value of the variable temp in the program. Due to the definition-reference chain drx,y,4,5,6, the 6 mutants entirely have the same change state in the 6th row; that is, mx=2,3,…,6 are redundant mutants of m1.


## 3.2. Identification Rule 2 (D2)

Assuming the existence of a definition-reference chaindru,v,s1,s2, let mutant mi=1,2,3 be the definition mutation set Mdef,u,v,s1 of variable u, v, and let mutant mj=1,2,3 be the reference mutation set Mref,u,v,s2 of variable u, v. s1, belongs to the program block bn (bn is one of the BasicBlock, OptiomBlock, and LoopBlock), and s2 belongs to BasicBlocki, where bn and BasicBlocki satisfy the sequential block relationship and meet Definition 1 in s1. It can be concluded that mx=2,3,…,6 is a redundant mutant of m1.According to the defined identification ruleD2, it is qualified that its mutant mi=1,2,3 and mutant mj=4,5,6 belong to the sequential block relationship. mi=1,2,3 and mj=4,5,6 are variables defined, respectively, in the s2 statement def,u,v,s1 and referenced in the s2 statement ref,u,v,s2, where s1 belongs to program block bn (bn is one of the BasicBlock, OptiomBlock, and LoopBlock) and s2 belongs to BasicBlocki. According to the definition of the sequential block, in the mutation testing, if the execution condition of s1 in mi is triggered, it will cause the execution of s2 in mj. Then, the definition-reference chain of the variable can ensure that the state at s1 is propagated to s2. Based on the inclusion relationship between mutants and the definition of redundant mutants, mx=2,3,…,6 can be identified as redundant mutants of m1. An example of the recognition rule is shown in Figure 4 below. Figure 5 shows an example of the D2 identification rule application.Figure 5
Example program for identifying ruleD2.The source program in Figure5 is divided into blocks. It can be seen that lines 3, 4, and 5 belong to the same BasicBlock (b1), lines 6, 7, and 8 belong to the same BasicBlock (b2), and line 9 belongs to the same BasicBlock (b3). The definitions of the variables x and y are in the 4th and 5th lines, expressed as (defx,y,4,5), and the references to the variables x and y are in the 9th line, expressed as (refx,y,9). b2 is the sequential block of b1, and b3 is the sequential block of b2, so b3 is the indirect block of b1. The mutants mi=1,2,3 belong to the definition mutation set Mdef,x,y,4,5 of the variables x and y. If the values of the variables x and y change, the influence of the program is propagated to line 9 by reference to the variables x and y, thereby changing the value of the variable temp. The mutants mj=4,5,6 belong to the reference mutation set Mref,x,y,9 of the variables x and y, and the changes in the values of the variables x and y directly affect the value of the variable temp. From the definition-reference chain drx,y,4,5,9, it can be seen that the 6 mutants have the same change state in the 9th row; that is, mx=2,3,…,6 are redundant mutants of m1.


## 3.3. Identification Rule 3 (D3)

Assuming the existence of a definition-reference chaindru,v,s1,s2, let mutant mi=1,2,3 be the definition mutation set Mdef,u,v,s1 of variables u, v, and let mutant mj=4,5,6 be the reference mutation set Mref,u,v,s2 of variables u, v. When s1 belongs to program block bn (bn is one of the BasicBlock, OptiomBlock, and LoopBlock), and s2 belongs to BasicBlocki, BasicBlocki is the sequential block of the subblock of bn and meets Definition 1 in s1. It can be concluded that mx=2,3,…,6 are redundant mutants of m1.According to the identification ruleD3, it is qualified that the relationship between the mutants mi=1,2,3 and mutants mj=4,5,6 is defined as a composite of the relationship of the subblock and the sequential block. mi=1,2,3 and mj=4,5,6 are variables defined, respectively, in the s2 statement (def,u,v,s1) and referenced in the s2 statement (ref,u,v,s2). s1 belongs to program block bn (bn is one of the BasicBlock, OptiomBlock, and LoopBlock) and s2 belongs to BasicBlocki, where bn and BasicBlockn directly or indirectly satisfy the composite of the relationship of the subblock and the sequential block. It can be known from the subblock relationship that, in the mutation testing, if bn is executed, its upper block will be executed, and then the sequential block BasicBlockn will be executed. The definition-reference chain can ensure that the error state at s1 is propagated to s2. According to the inclusion relationship between mutants and the definition of redundant mutants, mx=2,3,…,6 can be identified as the redundant mutant of m1. Figure 6 shows an example of the D3 identification rule application.Figure 6
Example program for identifying ruleD3.The source program in Figure6 is divided into blocks. It can be seen that lines 3, 4, 5, and 6 belong to the same loop block (b1), lines 4 and 5 belong to the same basic block (b2), and line 7 belongs to the same basic block (b3). b1 is the upper block of b2, and b3 is the sequential block of b1. The definitions of the variables x and y are in the 4th and 5th lines, expressed as defx,y,4,5,), and the references to the variables x and y are in the 9th line, expressed as refx,y,9. The mutants mi=1,2,3 belong to the definition mutation set Mdef,x,y,4,5 of the variables x and y. The change of variables x and y changes the value of the variable sum by refx,y,7 in line 7. mj=4,5,6 directly affect the change of the value of the variable sum by referencing the variables x and y. From the definition-reference chain drx,y,4,5,7, it can be seen that the 6 mutants have the same change state in the 7th row; that is, mx=2,3,…,6 are redundant mutants of m1.


## 3.4. Identification Rule 4 (D4)

Suppose that there exists a definition-reference chaindru,v,s1,s2, let mutants mi=1,2,3 be the definition mutation set Mdef,u,v,s1 of the variables u, v, and let mutants mj=4,5,6 be the reference mutation set Mref,u,v,s2 of the variables u, v. If s1 is a function call statement i⟶∗j in module i with the variables u, v as arguments, s2 belongs to a BasicBlockj in module j, SBasicBlockj=∅ and meets Definition 1 in s1. It can be concluded that mx=2,3,…,6 are redundant mutants of m1.According to the identification ruleD4, it is qualified that mutants mi=1,2,3 and mutants mj=4,5,6 belong to the cross-module relationship. mi=1,2,3 and mj=4,5,6 are the block, where the variable definitional appearance (def,u,v,s1) is located as bn∈i, and the variable reference line appears in the BasicBlockn∈j where (ref,u,v,s2) is located, and there is a call relationship i⟶∗j between bn and BasicBlockn, and BasicBlockn has no subblock relationship in module j. From this, it can be deduced that, after the execution of bn, BasicBlockn must be executed, and then the definition-reference chain can ensure that the error state at s1 is propagated to s2. Based on the inclusion relationship between mutants and the definition of redundant mutants, mx=2,3,…,6 can be identified as redundant mutants of m1. Figure 7 shows an example of the D4 identification rule application.Figure 7
Example program for identifying ruleD4.Themul function is called by the f function in the third line, and the passing parameters are the variables x and y. The definition of variables x and y in the mutants mi=1,2,3 is represented as defx,y,3, and the references in the mutants mj=4,5,6 are represented as refx,y,6. mi=1,2,3 belong to the definition mutation set Mdef,x,y,3 of variables x and y. The change of the variable will affect the return value of the function, and the value of the variable mulp in the program can be changed through the call of the function. mj=4,5,6 belong to the reference mutation set Mref,x,y,5 of the variables x and y, and the reference of variables x and y will directly affect the value of the variable mulp. From the definition-reference chain drx,y,3,6, it can be seen that the 6 mutants have the same change state in the 6th row; that is, mx=2,3,…,6 are redundant mutants of m1.


## 4. Experimental Analysis

### 4.1. Experimental Subjects

8 C program sets (program source:http://sir.csc.ncsu.edu/portal/index.php, containing detailed information about experimental data) are used as experimental objects to verify the feasibility and effectiveness of the algorithm, which can be divided into two categories: (1) Siemens program sets and the functional descriptions of the program set: print_tokens and print_tokens2 are lexical analyzers; schedule and schedule2 are schedulers; replace is pattern matching and replacement; tcas is a vehicle collision program; tot_info is data generation statistics. (2) The space assembly is the interpreter of the array definition language.Firstly, a large number of mutants were generated for each source program using Proteum [25]; then, the data set was preprocessed to filter a set of equivalent mutants and a set of applicable mutants. The relevant information of the program set is shown in Table 1.Table 1
Experimental procedure information.
Experimental subjectNumber of lines of code (including commented lines of code)Lines of code (excluding comment lines and blank lines)Number of test casesTotal number of mutantsNumber of equivalent mutantsNumber of applicable mutationsprint_tokens5653434130108815833619print_token2510355411593695453478Schedule412296265035162041441schedule2307263271057944712045Replace56351355422170315567805Tcas173137168064784422044tot_info406281105243086783654Space91265982136467938010797986


### 4.2. Experimental Steps and Results Analysis

Firstly, all sets of mutants with nonequivalent and single mutants are selected, and the data flow information of the experimental subjects is obtained using Frama-C [24]; then, the block rule file of the program to be tested is obtained using the static analysis method, and the mutation location information of the mutants is obtained; finally, the redundant mutants are identified after the identification rules (D1∼D4).The redundant mutants identified by the program for different experimental subjects were summed and counted, and the statistical results are shown in Table2. The redundancy rate of their mutants was used to verify the effectiveness of the algorithm in reducing the execution time of the mutation testing, and the redundancy rate was calculated by the formula shown in equation (1):(3)R=NRVIMN−MEN×100%,where R denotes the redundancy rate, NRVI denotes the number of identified redundant mutants, MN denotes the total number of mutants, and MEN denotes the number of equivalent mutants.Table 2
Redundant mutants of two variables for different experimental subjects.
Experimental subjectsNumber of redundant mutantsTotal redundant mutantsD1D2D3D4print_tokens783262180352print_token233076112221Schedule4102340104schedule21872753105Replace1750267131573Tcas0011237149tot_info8616213186501Space104613278601964From Table2 and Figure 8, it can be seen that there are different numbers of redundant mutants in the set of mutants of different experimental subjects. Although the redundancy rate accounted for by different experimental subjects varies greatly, this is enough to verify the existence of redundant mutants. From the side, it also verifies the reason why a small number of test cases can kill a large number of mutants in mutation testing.Figure 8
Redundant mutants of a variable in different subjects.From Table2 and Figure 9, it can be seen that the redundancy recognition rate varies widely among the different experimental objects, and the recognition variation of different identification rules is relatively large. Among the 8 C programs, it can be seen that the redundancy recognition rate of the space program reaches a maximum of 1964. However, the number of redundancy recognitions of the schedule is only 104. The validity analysis of the method is shown in Figure 9: This figure visualizes the proportion of redundant mutants under different identification rules. The number of redundant mutants identified in D1 and D3 is relatively high, accounting for 37% and 39% of the total number of mutants, respectively; the number of redundant mutants identified in D2 and D4 is relatively low, accounting for 5% and 19% of the total number of mutants, respectively. The following two points are summarized: (1) the larger the program size is, the more efficient the redundant mutants will be identified; (2) from the identification rules, the program structure distribution of the program can be judged, and we can verify this from the source code of the program. If there are more sequential structures in a program, the rule D1 recognition will work in the recognition rule. There are more branch structures and loop structures in the Siemens program set. The variables defined in the branch structure and loop structure are used more in sequential blocks, which makes D3 identify more redundant mutants. The use of variables in the Siemens assembly is mostly through function calls, which makes D4 recognize more redundant mutants. Therefore, when there are more cyclic structures, the recognition rate of D3 will be increased. When there are more function calls, the recognition rule D4 will play an important role.Figure 9
Percentage of redundant mutant identification rules.When the program size increases in the experimental program, the number of mutants increases accordingly when the test program passes through the mutation operator, and the number of test cases also increases, in which case the traditional mutation test execution time increases exponentially, significantly increasing the expensive resources for mutation testing. The redundant mutants are identified by statically scanning the definition-use chain of the program and the set of mutants, and it can be concluded that the identification of redundant mutants is linearly related to the size of the program and is not correlated with the test cases. Therefore, the expensive resources for mutation testing are reduced to some extent.In order to better show the identification of redundant mutants based on two variables for data flow analysis, the identification of redundant variants based on one variable proposed by Sun et al. is given in Table3 for Sun et al. [12].Table 3
Redundant mutants of one mutation for different experimental subjects.
Experimental subjectsNumber of redundant mutantsTotal redundant mutantsD1D2D3D4print_tokens591037123249print_tokens21904169129Schedule310122063schedule2123183366Replace88016094342Tcas00732396tot_info52787150296Space8727352101466Since the changed redundant mutant identification based on data flow analysis contains a definition-reference chain of variables as proposed by Sun et al., i.e., our proposed scheme has a higher identification rate in terms of implementation than the scheme proposed by Sun et al. As can be seen in Figure10, the improved redundancy rate varies from one experimental subject to another, with the highest redundant mutant identification improvement of up to 498 in the space program; however, the schedule2 program has the lowest redundant mutant identification improvement of only 39 mutants.Figure 10
Comparison of redundant mutants before and after experimental improvement.


## 4.1. Experimental Subjects

8 C program sets (program source:http://sir.csc.ncsu.edu/portal/index.php, containing detailed information about experimental data) are used as experimental objects to verify the feasibility and effectiveness of the algorithm, which can be divided into two categories: (1) Siemens program sets and the functional descriptions of the program set: print_tokens and print_tokens2 are lexical analyzers; schedule and schedule2 are schedulers; replace is pattern matching and replacement; tcas is a vehicle collision program; tot_info is data generation statistics. (2) The space assembly is the interpreter of the array definition language.Firstly, a large number of mutants were generated for each source program using Proteum [25]; then, the data set was preprocessed to filter a set of equivalent mutants and a set of applicable mutants. The relevant information of the program set is shown in Table 1.Table 1
Experimental procedure information.
Experimental subjectNumber of lines of code (including commented lines of code)Lines of code (excluding comment lines and blank lines)Number of test casesTotal number of mutantsNumber of equivalent mutantsNumber of applicable mutationsprint_tokens5653434130108815833619print_token2510355411593695453478Schedule412296265035162041441schedule2307263271057944712045Replace56351355422170315567805Tcas173137168064784422044tot_info406281105243086783654Space91265982136467938010797986


## 4.2. Experimental Steps and Results Analysis

Firstly, all sets of mutants with nonequivalent and single mutants are selected, and the data flow information of the experimental subjects is obtained using Frama-C [24]; then, the block rule file of the program to be tested is obtained using the static analysis method, and the mutation location information of the mutants is obtained; finally, the redundant mutants are identified after the identification rules (D1∼D4).The redundant mutants identified by the program for different experimental subjects were summed and counted, and the statistical results are shown in Table2. The redundancy rate of their mutants was used to verify the effectiveness of the algorithm in reducing the execution time of the mutation testing, and the redundancy rate was calculated by the formula shown in equation (1):(3)R=NRVIMN−MEN×100%,where R denotes the redundancy rate, NRVI denotes the number of identified redundant mutants, MN denotes the total number of mutants, and MEN denotes the number of equivalent mutants.Table 2
Redundant mutants of two variables for different experimental subjects.
Experimental subjectsNumber of redundant mutantsTotal redundant mutantsD1D2D3D4print_tokens783262180352print_token233076112221Schedule4102340104schedule21872753105Replace1750267131573Tcas0011237149tot_info8616213186501Space104613278601964From Table2 and Figure 8, it can be seen that there are different numbers of redundant mutants in the set of mutants of different experimental subjects. Although the redundancy rate accounted for by different experimental subjects varies greatly, this is enough to verify the existence of redundant mutants. From the side, it also verifies the reason why a small number of test cases can kill a large number of mutants in mutation testing.Figure 8
Redundant mutants of a variable in different subjects.From Table2 and Figure 9, it can be seen that the redundancy recognition rate varies widely among the different experimental objects, and the recognition variation of different identification rules is relatively large. Among the 8 C programs, it can be seen that the redundancy recognition rate of the space program reaches a maximum of 1964. However, the number of redundancy recognitions of the schedule is only 104. The validity analysis of the method is shown in Figure 9: This figure visualizes the proportion of redundant mutants under different identification rules. The number of redundant mutants identified in D1 and D3 is relatively high, accounting for 37% and 39% of the total number of mutants, respectively; the number of redundant mutants identified in D2 and D4 is relatively low, accounting for 5% and 19% of the total number of mutants, respectively. The following two points are summarized: (1) the larger the program size is, the more efficient the redundant mutants will be identified; (2) from the identification rules, the program structure distribution of the program can be judged, and we can verify this from the source code of the program. If there are more sequential structures in a program, the rule D1 recognition will work in the recognition rule. There are more branch structures and loop structures in the Siemens program set. The variables defined in the branch structure and loop structure are used more in sequential blocks, which makes D3 identify more redundant mutants. The use of variables in the Siemens assembly is mostly through function calls, which makes D4 recognize more redundant mutants. Therefore, when there are more cyclic structures, the recognition rate of D3 will be increased. When there are more function calls, the recognition rule D4 will play an important role.Figure 9
Percentage of redundant mutant identification rules.When the program size increases in the experimental program, the number of mutants increases accordingly when the test program passes through the mutation operator, and the number of test cases also increases, in which case the traditional mutation test execution time increases exponentially, significantly increasing the expensive resources for mutation testing. The redundant mutants are identified by statically scanning the definition-use chain of the program and the set of mutants, and it can be concluded that the identification of redundant mutants is linearly related to the size of the program and is not correlated with the test cases. Therefore, the expensive resources for mutation testing are reduced to some extent.In order to better show the identification of redundant mutants based on two variables for data flow analysis, the identification of redundant variants based on one variable proposed by Sun et al. is given in Table3 for Sun et al. [12].Table 3
Redundant mutants of one mutation for different experimental subjects.
Experimental subjectsNumber of redundant mutantsTotal redundant mutantsD1D2D3D4print_tokens591037123249print_tokens21904169129Schedule310122063schedule2123183366Replace88016094342Tcas00732396tot_info52787150296Space8727352101466Since the changed redundant mutant identification based on data flow analysis contains a definition-reference chain of variables as proposed by Sun et al., i.e., our proposed scheme has a higher identification rate in terms of implementation than the scheme proposed by Sun et al. As can be seen in Figure10, the improved redundancy rate varies from one experimental subject to another, with the highest redundant mutant identification improvement of up to 498 in the space program; however, the schedule2 program has the lowest redundant mutant identification improvement of only 39 mutants.Figure 10
Comparison of redundant mutants before and after experimental improvement.


## 5. Conclusion

This paper improves the identification technique based on data flow redundant mutants from the point of view of reducing the execution time of mutant test, combines the program block structure and data flow analysis technique, and defines a set of redundant mutant identification rules based on the weak mutant test. A set of redundant mutant identification rules is defined based on weak mutation testing. The effectiveness of the proposed redundant mutant identification technique is evaluated using 8 C programs. The experiments show that a large number of redundant mutants can be identified using the method in this paper, which not only reduces the number of mutants, but also shortens the execution time of mutation testing; we have compared this with the previous technique and found that our improvement still greatly improves the identification of redundancy rate and further optimizes the identification of redundant mutants.The main work in this paper is based on the improvement of the redundant mutant identification technique for data flow analysis. We introduce the inclusion relation of redundant mutants by adding one variable to achieve redundant mutant identification for two mutants, and the method can be better extended to multiple variables. Our next work is the redundant mutant identification technique for arbitrary multiple mutations, and better algorithms to further improve the testing efficiency.



---

*Source: 7543896-2021-10-21.xml*