臺灣博碩士論文加值系統

Automatically correcting software bugs is not an easy job because the process of repairing bugs contains many uncertainties. As the size and complexity of software increases, manually correcting software bugs becomes very difficult. Hence, automatic software repair is becoming more and more essential. Genetic programming (GP) is a great method for addressing this problem and a great deal of research has used GP to find ways the repair faulty programs in recent years. Nevertheless, most of variants generated by GP are not precise to detect solution repair.
In this thesis, we propose a fault-based genetic-like programming approach that heuristically searches all possible variants as they increasing with the number of modifications. Our method is able to find the best repairs for programs with few faults faster than genetic programming. However, the penalty is that heuristically searching for suitable repairs takes too much time. Hence, we also optimized our approach to speed up the performance.
In this study, our approach was used to repair faulty C programs and the results were compared with those generated by genetic programming. The results show that our approach was able to better detect faulty programs in up to 18000 lines of code when the number of program faults was less than two.

自動修復軟體的錯誤並不是一件容易的事，因為在過程中會有許多的不確定性在裡面。隨著軟體的大小和複雜度逐漸地增加，人工的去修復軟體的錯誤變的更加的困難，進而使得自動軟體修復的重要性也將變得越來越大。針對這個問題，基因規劃(GP) 是一個很好的方法，近幾年來有很多的研究已經運用此種方法去修正程式的錯誤。然而，這個方法所產生的程式變異體並不是針對程式的錯誤去進行變異的。
在本篇論文中，我們提出了一種基於故障之類基因規劃方法去隨著修改的數量啟發式地尋找所有可能的變異體。我們的方法可以比運用基因規劃更快的在錯誤不多的程式上找到最好的修改。但是，啟發式地搜尋合適的修復之耗費很大。因此，我們對於我們的方法也做了一些最佳化處理來改善這個缺點。
此外，我們將這個方法運用於修復C的程式上並和基因規劃產生的結果互相比較。經比較後發現，我們的方法擁有比基因規劃更好的能力去修復程式碼高達一千八百行並且少於兩個錯誤的程式。

Abstract i
Abstract in Chinese ii
Acknowledgement iii
List of Tables vi
List of Figures vii
Chapter 1 Introduction 1
Chapter 2 Related Work 4
2.1 Automatic software repair 4
2.2 Genetic Programming 6
2.2.1 Program Representation 6
2.2.2 Genetic Operator 7
2.2.3 Fitness Function 8
Chapter 3 Fault-Based Genetic-Like Programming 10
3.1 Motivation 10
3.2 Simple Example 11
3.3 The Fault-Based Genetic-Like Programming 14
3.4 Initial Mutation 18
3.5 Reducing the Search Space of the Initial Mutation 20
3.6 Cross Mutation 24
3.7 Stratified Random Sampling 26
Chapter 4 Experimental Results and Discussion 29
4.1 Environment Setup 29
4.2 Performance Analysis 31
4.3 Other Discussion of Space Reduction and Sampling Mechanisms 37
4.3.1 Reduction Analysis 37
4.3.2 Sampling Analysis 42
Chapter 5 Conclusions and Future Work 44
Reference 46

[1] B. Beizer. Software Testing Techniques. Van Nostrand Rheinhold, New York, 1990.

[2] B. Korel and A. M. Al-Yami. “Assertion-oriented automated test data generation,” In Proceedings of the 18th International Conference on Software Engineering (ICSE), pp. 71-80, 1996.

[3] J. Edvardsson. “A Survey on Automatic Test Data Generation,” In Proceedings of the 2nd Conference on Computer Science and Engineering, pp. 21–28, Linkoping, October 1999.

[4] A. Eiben and J. Smith. Introduction to Evolutionary Computing. Springer, 2003.

[5] J. L. Wilkerson and D. Tauritz. “Coevolutionary automated software correction,” In Proc. of GECCO, pp. 1391–1392, 2010.

[6] J. R. Koza. Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, 1992.

[7] R. Poli, W. B. Langdon, and N. F. McPhee. “A field guide to genetic Programming,” Published via http://lulu.com and freely available at http://www.gp-field-guide.org.uk, 2008. (With contributions by J. R. Koza).

[8] Zeller, “Automated debugging: Are we close,” In IEEE Computer, pp. 26–31, November 2001.

[9] M. Auguston, C. Jeffery, and S. Underwood, “A framework for automatic debugging,” In IEEE International Conference on Automated Software Engineering (ASE), pp. 217–222, 2002.

[10] H. He and N. Gupta. “Automated debugging using path-based weakest preconditions,” In Fundamental Approaches to Software Engineering, pp. 267–280, March 2004.

[11] S. Staber, B. Jobstmann, and R. Bloem. “Finding and fixing faults,” In 13th IFIP WG 10.5 Advanced Research Working Conference on Correct Hardware Design and Verification Methods, volume 3725 of LNCS, pp. 35–49. Springer, 2005.

[12] B. Jobstmann, A. Griesmayer and R. Bloem, “Program repair as a game,” In Conference on Computer Aided Verification (CAV), pp. 226–238, 2005.

[13] D. Ashlock, Evolutionary Computation for Modeling and Optimization, Springer, ISBN 0-387-22196-4, 2006.

[14] T. Mens. ”A survey of software refactoring,” In IEEE Transactions on Software Engineering, vol. 30, no. 2, pp. 126.139, February 2004.

[15] W. Weimer. “Patches as better bug reports,” In Generative Programming and Component Engineering, pp. 181–190, 2006.

[16] A. Arcuri. “On the automation of fixing software bugs,” In Proceedings of the Doctoral Symposium of the IEEE International Conference on Software Engineering, 2008.

[17] A. Arcuri and X. Yao. “A novel co-evolutionary approach to automatic software bug fixing,” In CEC, 2008.

[18] J. Clark, J. Dolado, M. Harman, R. Hierons, B. Jones, M. Lumkin, B. Mitchell, S. Mancoridis, K. Rees, M. Roper, and M. Shepperd. “Reformulating Software Engineering as a Search Problem,” In IEE Proc. Software, vol. 150, no. 3, pp. 161-175, 2003.

[19] M. Harman and B. F. Jones. “Search-based software engineering”. In Journal of Information & Software Technology, vol. 43, no. 14, pp. 833–839, 2001.

[20] W. Weimer, T. Nguyen, C. Le Goues, and S. Forrest. “Automatically finding patches using genetic programming,” In International Conference on Software Engineering, pp. 364–374. IEEE, 2009.

[21] S. Forrest, W. Weimer, T. Nguyen, and C. Le Goues. “A genetic programming approach to automated software repair,” In GECCO, pp. 947–954, 2009.

[22] W. Weimer, S. Forrest, C. L. Goues, and T. Nguyen. “Automatic program repair with evolutionary computation,” In CACM, vol. 53, no. 5, May 2010.

[23] J.H. Perkins, S. Kim, S. Larsen, S. Amarasinghe, J. Bachrach, M. Carbin, C. Pacheco, F. Sherwood, S. Sidiroglou, G. Sullivan, W.-F. Wong, Y. Zibin, M.D. Ernst, M. Rinard. “Automatically patching errors in deployed software,” In ACM Symposium on Operating Systems Principles, pp. 87–102, 2009.

[24] B. Demsky and M. C. Rinard. “Automatic detection and repair of errors in data structures,” In Proceedings of the 2003 ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages and Applications, pp. 78-95. ACM, 2003.

[25] M. Z. Malik, K. Ghori, B. Elkarablieh, and S. Khurshid. “A case for automated debugging using data structure repair,” In 24th IEEE/ACM International Conference on Automated Software Engineering. IEEE, 2009.

[26] B. Elkarablieh and S. Khurshid. “Juzi: A tool for repairing complex data structures,” In Proc. 30th International Conference on Software Engineering (ICSE), Leipzig, Germany, 2008.

[27] G. C. Necula, S. McPeak, S. P. Rahul, and W. Weimer. “Cil: An infrastructure for C program analysis and transformation”. In International Conference on Compiler Construction, pp. 213–228, Apr 2002.

[28] J. A. Jones and M. J. Harrold. “Empirical evaluation of the tarantula automatic fault-localization technique”. In Proc. ASE, New York, pp. 273-282, 2005.

[29] T. Ball, M. Naik, and S. K. Rajamani. “From symptom to cause: Localizing errors in counterexample traces”. In Proceedings of the Symposium on Principles of Programming Languages, pp. 97–105, Jan 2003.

[30] V. Debroy, W.E. Wong. “Using mutation to automatically suggest fixes for faulty programs”. In Third International Conference on Software Testing, Verification and Validation (ICST). IEEE, Los Alamitos, 2010.

[31] E. Fast, C. Le Goues, S. Forrest, and W. Weimer. “Designing better fitness functions for automated program repair”. In Genetic and Evolution Computation Conference, pp. 965–972, 2010.

[32] Evolutionary Program Repair (EPR) http://epr.adaptive.cs.unm.edu/publications.html