Automated Debugging Based On "Generate-and-Validate" Systems

Debugging is a time-and labour-consuming yet inevitable activity in software development.Automated debugging techniques therefore hold an important role in software engineering research.Recently "generate-and-validate" systems,a class of automated debugging systems,have caught the attention of many researchers.They take as input the source code and test suite of the target program,and generate modification suggestions so that the modified program can pass the test suite.Recent experiment reports have demonstrated the fixing capability of existing systems,yet the efficiency and success rate of the systems are far from satisfactory.In this thesis,we propose to enhance the system by both optimizing existing modules(i.e.fault localizer and search engine)and extending the framework.Main contributions of this thesis are:· We point out the problem that the oracle assumption does not hold in real software development process,and present statistical evidence that SFL algorithms suffer from accuracy loss when oracle error exists.On this ground we propose an algorithm that can debug the oracle through calculating the "similarity" of test case execution traces and identifying the suspicious test oracle judgments.Experiment shows that SFL accuracy is enhanced prominently.To the best of our knowledge,this is the first research on SFL algorithms without the oracle assumption.· We propose an optimization strategy called "pre-filtering" on the search engine.Through "pre-filtering",expression related fix candidates are examined before entering "validation",so that large proportions of fixes that are impossible to fix the bug are tossed away early and thus relieving the validator from huge workload and compressing the search space.Experimental results show that "pre-filtering" is able to reduce the size of search space to around 10%.In some complex programs the reduction ratio is even below 1%.· We propose two designs of framework extension.One is "interactive debugging",which aims at utilizing programmers' judgment of program running state to improve fault localization accuracy.Experimental results show that the interactive system is able to accelerate the speed of manual debugging.The other is a developing framework that enables developers to introduce new fix algorithms for specific error types as a supplement to the original structure.As an example we implemented a fix algorithm for NPEs(null pointer exception).Experimental results show that the newly implemented algorithm is able to fix NPEs successfully,proving the practicality of the extended framework.