Software Multiple-fault Localization Technique Based On Higher-order Mutation

Fault localization is one of the most essential and time-consuming steps during software debugging.The automated fault localization technique seeks to identify the potentially faulty entity in the programs automatically and helps to locate the root cause of the fault in the program quickly.However,with the updating and iterating of the software,the faults in the program become more complex,and the traditional fault localization techniques are mainly focusing on single faults,i.e.,the fault can be fixed by making a single change to the program,but these techniques did not deeply investigate multiple faults that can be fixed by making multiple changes to the program,which makes it difficult to achieve a good fault localization effectiveness on multiple faults.Mutation-based fault localization(MBFL)technique is one kind of fault localization technique that can achieve a promising fault localization accuracy proposed in recent years.MBFL works by seeding faults into the program under test and then generating mutants and the mutants are usually classified into first-order mutants(FOMs)and higher-order mutants(HOMs)according to the number of faults seeding into the program.HOMs can simulate multiple faults by seeding multiple artificial faults in the program under test,which can be applied in multiple-fault localization theoretically.However,the existing HOMs generation techniques only use the combination of FOMs,but do not consider the correlation between single faults in the composition of multiple faults.Hence it is the first challenge that this topic faces to study a HOMs generation method that can simulate real multiple faults.On the other hand,the statement suspiciousness measurement method is the core of fault localization,which determines the position of the faulty entities in the ranking list directly.In MBFL,the existing measurement method is based on the execution information of FOMs,hence it is another challenge that this topic faces to propose a statement suspiciousness measurement method that is suitable for HOMs.This paper conducts a research on software multiple-fault localization techniques and proposes a multiple-fault localization technique based on HOMs.In detail,this paper proposes a multiple faults-oriented HOMs generation method and a multiple faults-oriented higher-order mutation statement suspiciousness measurement method.Moreover,this paper proposes the cost reduction method for the higher-order mutation fault localization technique for the huge cost.The main research works of this paper include:(1)Multiple faults-oriented higher-order mutants generation methodsMultiple faults can be regarded as composed of single faults,and these single faults may be correlated with each other.This paper analyses the correlation and distribution among these single faults based on the types of multiple faults in programs systematically,and then proposed corresponding HOMs generation methods.Firstly,it is assumed that these single faults are unrelated to each other but have similarities,and then this paper proposes the HOMs generation method based on single fault clustering(SFClu).Secondly,assuming that there is a logical correlation between single faults,this paper considers the location of single faults and proposes the HOMs generation method based on single faults distribution(SFDis)and the HOMs generation method based on single faults density(SFDen)from the perspective of single faults’ distribution and density.Experiment results on 237 multiple-fault programs from two datasets indicate that SFClu combines the FOMs that can characterize unrelated faults to generate HOMs,which are more simulate multiple faults,compared with SFDis and SFDen.Furthermore,this paper applied the proposed HOMs generation method in the higher-order mutation-based fault localization technique and the fault localization accuracy is significantly improved.(2)Multiple faults-oriented higher-order mutation statement suspiciousness measurement methodDue to the traditional MBFL techniques not considering multiple faults when measuring the statements’ suspiciousness,this paper proposes two statement suspiciousness measurement methods.The methods are proposed based on the possible characteristic of multiple faults’ location and HOMs,by constructing the mapping relationship between HOMs and statements.At first,considering the close relationship between the multiple faults’ location and the HOMs’ suspiciousness,this paper proposes a higher-order mutation statement suspiciousness measurement method based on multiple fault suspiciousness distribution(MFSD),including the method based on the maximum value(MFSD-Max),the average value(MFSD-Average),and weight(MFSD-Weight)of HOMs’ suspiciousness.Next,further analysising the execution feature of tests on multiple faults,this paper proposes a statement suspiciousness measurement method based multiple fault test execution change(MFTEC).Experiment results on 237 versions of multiple faults show that MFSD-Weight is more capable of revealing the location of faulty statements.Furthermore,this paper applied the proposed statement suspiciousness measurement method method in the higher-order mutation-based fault localization technique and the fault localization accuracy is significantly improved.(3)Multiple faults-oriented higher-order mutants reduction methodBecause the higher-order mutation-based fault localization technique suffers huge execution costs when applied HOMs,this paper proposes two reduction methods for reducing HOMs.The methods are proposed based on the characteristic of complex faults and HOMs,from the mapping relationship between HOMs and statements,and the value of HOMs for fault localization.At first,to ensure the mutation diversity of the statements,this paper proposes the HOM reduction method based on statement granularity sampling(SGS).Next,considering the value of HOMs on fault localization,this paper proposes HOM reduction method based on mutant test analysis(MTA).The experiments on 237 programs demonstrate that SGS has a higher fault localization accuracy than other reduction methods.Furthermore,this paper applied the proposed higher-order mutants reduction method SGS-20% in the higher-order mutation-based fault localization technique and the fault localization accuracy is similar to that of the original,and performs significantly better than the traditional fault localization techniques.SGS-20% decreases the mutation execution cost by 80.0% effectively,which improves the mutation execution efficiency by 4 times.In summary,this paper investigates the multiple faults-oriented higher-order mutation-based fault localization technique for the problems of multiple-fault localization.At first,for generating HOMs,this paper studies three multiple faults-oriented higher-order mutants generation methods.Secondly,for measuring the higher-order mutation statements’ suspiciousness,this paper proposes two multiple faults-oriented higher-order mutation statement suspiciousness measurement methods.Finally,for reducing the cost of higher-order mutation-based fault localization technique,this paper presents two methods for reducing HOMs.The fault localization accuracy of the higher-order mutation-based fault localization technique adopted by SGS-20% is similar to that of the original and it performs significantly better than the traditional fault localization techniques.SGS-20% reduces mutation execution cost by 80.0%,which improves the mutation execution efficiency by 4.00 times.This paper provides a basis for the practical application on higher-order mutant fault localization techniques.