Research On Software Fault Localization Method By Analyzing Failure Propagation

Bugs may reduce the reliability,usability and security of the systems.When the failure occurs,it is necessary for the software developer to observe the execution behavior of the program,find out the root cause of the failure,and then eliminate bugs.However,due to the huge program state space and the propagation of error states along the execution paths,the understanding of "What causes the failure?" and "Why does the program fail?" has become a question worthy of study.Therefore,automatic software fault localization technology is urgently needed to provide such information and assist software debugging.The field of programming education also needs the support of fault localization technology to provide timely debugging feedback and assistance for students' online learning and programming.Unlike industrial software,student programs especially novice student programs often contain conceptual errors,and the fault density is high.The types of bugs may be various,and key statements may be missing,so that the programs may fail for all test cases.The hypothesis of "buggy programs may pass some test cases" is not entirely applicable to the debugging of student programs.It is necessary to research fault localization methods according to the characteristics of student programming.In this paper,a “failure-fault localization-comprehension” model is proposed,and key scientific issues in the field of software fault localization are analyzed.According to the different characteristics of software development and student programming debugging,fault localization techniques are studied respectively.Firstly,to achieve the goal "In the presence of some passed test cases,accurately localize bugs,and provide sufficient information for developers to understand and repair bugs.",the test case optimization method and the invariant based fault localization method are studied.Then,to achieve the goal of "When sufficient sample programs are provided,even if the buggy program cannot pass any test case,suspicious statements can be accurately localized",the fault localization method suitable for student programs is studied.The main research contents are as follows.(1)In order to make the best use of the testing information,and select the test cases suitable for fault localization,a test case optimization method for effective fault localization is proposed.Firstly,the "test case prioritization criterion by similarity of failure coverage vector" is proposed to prioritize the passed test case whose execution path is more similar to that of the failed test case.Secondly,the "test case selection criterion by equivalent coverage division" is defined to select passed test cases,which can maximally differentiate the statements in the failure execution path.On this basis,the test case selection model is established.Experimental results have shown that in terms of the reduction rate and expense metrics,our method is better than the existing statement-based and vector-based test case reduction approaches.(2)To solve the problems of the existing methods,such as insufficient invariant definition which limits the bug types that can be localized,lack of analysis on the impact of test cases which leads to false positives of invariant violation detection,a program invariant based fault localization method for analyzing various types of bugs is proposed.Firstly,float range invariants,set invariants and Boolean sequence invariants are defined.In addition,two classes of suspicious statements i.e.statements that are covered only by failed test cases and the permanent True/False predicates,which are difficult to be localized with invariant violation detection are identified.Then,the test case optimization method is combined with program invariant based fault localization to reduce false positives of invariant violation detection.Experimental results have shown that the proposed method can effectively localize more kinds of bugs than the existing methods based on program invariants.(3)Existing program invariant based methods lack the analysis of failure propagation,which leads to the false negatives and false positives of invariant violation detection,thus obstructs the localizing of the root cause of failure.To solve this problem,an invariants-based fault localization method by analyzing failure propagation is proposed.On the one hand,reaching-definition analysis is used to identify the constant assignment statements,so as to localize the missed assignment bugs.On the other hand,dependence analysis is performed,so as to filter out the false positives of invariant violation introduced by failure propagation.Experimental results have shown that the proposed method can effectively reduce the false negatives and false positives of invariant based fault localization,and it is more effective than the program spectrum based method.(4)In view of the fact that student programs may fail for all the test cases,but there are a large number of sample programs for reference,the sample based fault localization method is studied.Firstly,a program clustering method based on structural metrics and execution value sequences is proposed to identify sample programs from a large number of existing programs.Then,a fault localization method by analyzing failure propagation context is proposed to localize suspicious statements by analyzing the difference of execution states and structural semantics between the buggy program and the sample program.Experimental results have shown that,when sufficient sample programs are provided,the proposed method can effectively localize the suspicious statements and assist the bug fixing.