軟體測試對軟體工業而言是一個重要而昂貴的動作，測試至少佔了軟體50％以上的成本。為了緩解這種情況，測試自動化是一個非常重要的軟體測試進程。在測試自動化中，其中一個重要組成部分是一個可執行的測試判定器。傳統上的可執行的測試判定器通常是從軟體規格、軟體文檔、程序、甚至程序斷言本身......等，建構而成的。
在本文中，我們從一群測試案例經由類神經網路構造一個測試判定器。我們的方法特別強調測試案例的輸出與輸入串列之間的關係。我們還制定了輸入/輸出串列關係語言（IOLRL）作為輔助工具，進一步讓使用者可以輸入其需要的輸出/輸入串列的關係。透過挖掘使用者給予的測試案例中輸出與輸入串列資訊，我們利用類神經網路構建可執行的測試判定器。這個構造出來的測試判定器可以用來自動化軟體驗證的過程。從實驗結果可以得知，我們構建出來的判定器具有良好的性能。

Software testing is an important and expensive activity to the software industry, with testing accounting for over 50% of the cost of software. To ease this situation, test automation is very critical to the process of software testing. One important component of the test automation is an executable test oracle. Traditionally an executable test oracle is constructed from the software specifications, software documentation, program assertions or even the program itself, etc.
In this paper, we construct a test oracle from a set of test cases with neural networks. Our approach especially emphasizes on the relation between the input and output lists of the test cases. We also present input/output list relation language (IOLRL) as an auxiliary tool for users to further specify the particular relation between the input and output lists. By mining the knowledge of the input/output relation from the given set of test cases, we construct an executable test oracle with neural networks. This constructed test oracle can be used to automate the software testing. The experiments show our constructed test oracles have good performance.

口試委員會審定書i
誌謝iii
中文摘要v
Abstract vii
1 Introduction 1
2 Related work 5
3 Preliminaries 7
4 Background 11
5 SUT models for recursive programs 15
5.1 The models................................. 15
5.1.1 The model of quick sort...................... 15
5.1.2 The model of binary search tree.................. 16
5.1.3 The mode of depth first traverse.................. 16
5.2 Inductive hypotheses............................ 20
6 Feature rules 23
6.1 Default rules................................. 23
6.2 Input/output list relation language(IOLRL)................. 25
7 Framework of the test oracle construction 27
8 Test oracle construction with neural networks 31
9 Experiment 33
9.1 Benchmarks................................. 33
9.2 Settings................................... 34
9.2.1 The parameters of the neural networks............ 34
9.2.2 The settings of the benchmarks, test cases, and feature rules... 35
9.3 Performance evaluation procedures............ 36
9.4 Results.................................... 38
10 Conclusion 43
Bibliography 45
Appendix A 49
Appendix B 53
Appendix C 57

[1] C. Anderson, A. von Mayrhauser, and R. Mraz. On the use of neural networks to guide software testing activities. In Procs. International Test Conference, 1995.
[2] H. Barringer, A. Goldberg, K. Havelund, and K. Sen. Rule-based runtime verification. In B. Steffen and G. Levi, editors, VMCAI, volume 2937 of Lecture Notes in Computer Science, pages 44–57. Springer, 2004.
[3] C. M. Bishop. Neural Networks for Pattern Recognition. Oxford University Press, Inc., New York, NY, USA, 1995.
[4] D. B. Brown, R. F. Roggio, J. H. Cross II, and C. L. McCreary. An automated oracle for software testing. IEEE Transactions on Reliability, 41(2):272–280, 1992.
[5] H. Do, S. Elbaum, and G. Rothermel. Supporting controlled experimentation with testing techniques: An infrastructure and its potential impact. Empirical Software Engineering: An International Journal, 10(4):405–435, 2005.
[6] E. Dustin, J. Rashka, and J. Paul. Automated software testing: introduction, management, and performance. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1999.
[7] J. Edvardsson. A survey on automatic test data generation. In Proceedings of the Second Conference on Computer Science and Engineering in Link‥oping, pages 21– 28. ECSEL, October 1999.
[8] L. V. Fausett. Fundamentals of Neural Networks. Prentice Hall, Upper Saddle River, NJ, USA, 1994.
[9] J. Grabowski, D. Hogrefe, G. Rethy, I. Schieferdecker, A. Wiles, and C. Willcock. An introduction to the testing and test control notation (ttcn-3). Computer Networks, 42(3):375 – 403, 2003. ITU-T System Design Languages (SDL).
[10] M. Grochtmann and K. Grimm. Classification trees for partition testing. Software Testing, Verification and Reliability, 3(2):63–82, 1993.
[11] E. L. Jones and C. L. Chatmon. A perspective on teaching software testing. In Proceedings of the seventh annual consortium for computing in small colleges central plains conference on The journal of computing in small colleges, pages 92–100, , USA, 2001. Consortium for Computing Sciences in Colleges.
[12] G. Khanna, M. Y. Cheng, P. Varadharajan, S. Bagchi, M. P. Correia, and P. Verissimo. Automated rule-based diagnosis through a distributed monitor system. IEEE Trans. Dependable Sec. Comput., 4(4):266–279, 2007.
[13] T. M. Khoshgoftaar and R. M. Szabo. Using neural networks to predict software faults during testing. IEEE Transactions on Reliability, 45(3):456–462, 1996.
[14] B. Korel and A. M. Al-Yami. Assertion-oriented automated test data generation. In ICSE ’96: Proceedings of the 18th international conference on Software engineering, pages 71–80, Washington, DC, USA, 1996. IEEE Computer Society.
[15] D. Kriesel. A Brief Introduction to Neural Networks. 2007. available at http://www.dkriesel.com.
[16] M. Minsky and S. Papert. Perceptrons: An Introduction to Computational Geometry. MIT Press, 1969.
[17] M. M”oller, E. R. Olderog, H. Rasch, and H.Wehrheim. Integrating a formal method into a software engineering process with uml and java. Formal Aspects of Computing, 2008.
[18] D.W. Patterson. Artificial Neural Networks: Theory and Applications. Prentice Hall PTR, Upper Saddle River, NJ, USA, 1998.
[19] D. K. Peters and D. L. Parnas. Using test oracles generated from program documentation. IEEE Transactions on Software Engineering, 24(3):161–173, 1998.
[20] F. Rosenblatt. The perception: a probabilistic model for information storage and organization in the brain. pages 89–114, 1988.
[21] Y. S. Su and C. Y. Huang. Neural-network-based approaches for software reliability estimation using dynamic weighted combinational models. Journal of Systems and Software, 80(4):606–615, 2007.
[22] M. Vanmali, M. Last, and A. Kandel. Using a neural network in the software testing process. Int. J. Intell. Syst., 17(1):45–62, 2002.
[23] M. Ye, B. Feng, L. Zhu, and Y. Lin. Neural networks based automated test oracle for software testing. In ICONIP (3), pages 498–507, 2006.
[24] G. P. Zhang. Neural networks for classification: a survey. IEEE Transactions on Systems, Man, and Cybernetics–Part C: Applications and Reviews, 30(4):451–462, 2000.
[25] J. M. Zurada. Introduction to Artificial Neural Systems. Pws Publish Co., 1992.