Program Fault Localization And Repair In Software Debugging

For software developers and maintainers,software debugging is a routine job.Gen-erally speaking,the process of software debugging includes fault localization,fault un-derstanding and fault fixing.Unfortunately,software debugging is a time consuming and exhausting task,and empirical studies show that software debugging can cost a software project up to 50%of its budget.To meet the challenge,automated software debugging has been proposed and extensively investigated.However,due to the com-plexity of software and software evolution phenomenon,existing automated software debugging methods suffer from problems,such as low quality of debugging results and poor practicability.To overcome these challenges,and improve existing automated software debugging approaches,this thesis studies three aspects of software debugging as described below:Model-based diagnosis,an intelligent diagnosis theory has been successfully applied in software fault localization with promising results.However,traditional MBD relies on the assumption that components in the system fail dependently,which makes the diagnoses with a high false-positive rate in software fault localization.In this thesis,a component redundancy analysis approachis presented.The approach not only uses Craig interpolant to filter redundant components,but also employs a fact that a branch predicate evaluates to either true or false to filter some branch condition components.Experimental results show that the proposed approach effectively reduces the false posi-tive rates of diagnoses,i.e.,reducing the number of diagnosis by 48.4%,and reducing the number of nodes of hitting set tree generated during diagnosis computation by 47.6%.JUnit test repair has been proposed as a way to alleviate the burden of maintaining the broken tests caused by evolving software.Existing techniques for JUnit test repair either focus on repairing failing assertions or fixing test case compilation errors rendered by evolving method declarations.The empirical work suggests that the synthesis of new method calls is often needed when repairing test cases in practice.Therefore,we propose TestFix,an approach to fix broken JUnit test cases by synthesizing new method calls.TestFix reduces the synthesis to a search problem and uses a genetic algorithm to solve it.Evaluated on real world applications,preliminary experimental results show that TestFix can repair broken tests with adding or deleting method calls.Evaluations on the performance of JUnit test repair technique using a genetic algorithm against a random search algorithm are also conducted.Experimental results indicate the clear superiority of genetic algorithms over random search algorithm.Search based program repair techniques exploits search methods such as genetic programming or random search method to search for a repair solution for buggy pro-grams.Due to the randomness of search methods,these techniques usually produce nonsensical results.Mutation based repair approach draws on the idea of mutation test-ing to fix a buggy program,that is,it tries to fix faults by applying mutant operators to the faulty statement.This approach,however,is ineffective in terms of repair success rate because it is not syntax-directed and has the limited number of mutant operators.Inspired by the programming by demonstration,a version,space algebra based program repair method is proposed.Specifically,if the regression test suites of programs are re-garded as training instances,the repair problem of faulty statements can be formulated as a induction learning problem.To this end,a lot of improvements about version space algebra are made:(1)automatic derivation of version spaces from grammars,(2)defin-ing version space according to its type,and(3)combining type checking with version space algebra.In the end,Experimental results show the proposed method outperforms other existing automatic program repair approaches in terms of repair success rate,and type-checking mechanism can prune the hypothesis space efficiently.