在並行程式中會透過同步機制保護共享資源的存取和進行執行緒間的通訊。在測試並行程式時，我們必須要考慮並行程式的非確定性行為。透過紀錄及控制程式執行的方式，發現並行程式潛在的錯誤。然而對於使用各種同步機制的並行程式而言，同步機制可能使得記錄與控制執行的方式更為複雜，需要更進一步針對各種同步機制的行為進行研究，才能適當地完成測試。Java程式語言中提供了monitor作為主要的同步機制之一。相較於semaphore，monitor提供了更多同步操作，諸如wait及notify等，複雜度較高。除此，誤用monitor可能會造成程式死結，這也是需要透過測試發現的。本篇論文運用dynamic effective testing，對Java monitor進行測試。能夠找出並行程式中死結的發生位置，以及產生並行程式使用Java monitor的所有狀態。在運用時我們需要實做Java monitor的prefix-based replay protocol，並且提出一個演算法濾除不符合Java monitor semantic的race variant。最後我們做了簡化的動作，大幅度的降低程式的測試時間。

In this thesis, we study how to apply the dynamic effective testing to Java programs which the synchronization mechanism is the Java monitor. Compare with the shared-memory access and shared semaphore based concurrent program, Java monitor based concurrent programs exhibit much more complicated synchronization behavior as the Java monitor contains "wait", "notify", "notify all", and exclusive execution of synchronization methods and a segment of codes. Thus, we need to design new prefix-based replay protocol for Java monitor based concurrent program to conduct dynamic effective testing. We also design an algorithm to make the feasibility check of generated race variants. According to the implementation and experimental results, we demonstrate that we can perform dynamic effective testing on Java monitor based concurrent program to achieve the goal of state-cover testing.

[1] Charles E. Mcdowell and David P. Helmold, “Debugging Concurrent Programs,” ACM Computing Surveys, Volume 21, Issue 4, December 1989.
[2] K.C. Tai and Richard H. Carver, “Testing of Distributed Programs,” Chapter 33 in Parallel and Distributed Computing Handbook, Editor: A. Y. Zomaya, McGraw-Hill, 1996.
[3] Anne Dinning, “A Survey of Synchronization Methods for Parallel Computers,” IEEE Computer, July 1989.
[4] Abraham Silberschatz, Peter Baer Galvin, and Greg Gagne, “Operating System Concepts,” John Wiley & Sons, ISBN: 0471417432, 6th Edition (June 26, 2001).
[5] W. Richards Adrion, Martha A. Branstad, and John C. Cherniavsky, “Validation, Verification, and Testing of Computer Software,” ACM Computing Surveys, Volume 14, Issue 2, June 1982.
[6] Roger S. Pressman, “Software Engineering (A practitioner’s approach),” 5th Edition, 2000, Mc Graw-Hill Education, ISBN 978-0071181822.
[7] D. Helmbold and D. Luckham, “Debugging Ada Tasking Programs,” IEEE Software, Volume 2, Number 2, pp. 66-74, 1985.
[8] K. C. Tai, “Testing of Concurrent Software,” Proceedings of the 13th Annual International Computer Software and Applications Conference, pp. 62-64, 1989.
[9] J. Gait, “A probe effect in concurrent programs,” Software-Practice and Experience, March 1986, pp. 225-233.
[10] S. D. Stoller, “Testing Concurrent Java Programs Using Randomized Scheduling,” Proceedings of the 2nd Workshop on Runtime Verification, Amsterdam, 2002.
[11] Y. Ben-Asher, E. Farchi, and Y. Eytani, “Heuristics for Finding Concurrent Bugs,” Proceedings of the International Parallel and Distributed Processing Symposium (IPDPS 2003), April 2003.
[12] Edelstein O, Farchi E, Nir Y, Ratsaby G, and Ur S. “Multithreaded Java Program Test Generation,” IBM Systems Journal 2002, 41(1):111–125. Available at: http://www.research.ibm.com/journal/sj/411/edelstein.html.
[13] “CHESS: Find and Reproduce Heisenbugs in Concurrent Programs,” http://research.microsoft.com/en-us/projects/chess/.
[14] M. Musuvathi, S. Qadeer, and T. Ball, “CHESS: A Systematic Testing Tool for Concurrent Software,” Microsoft Research Technical Report MSR-TR-2007-149, 2007.
[15] Gwan-Hwan Hwang, “A Systematic Parallel Testing Method for Concurrent Programs,” Master Thesis, Institute of Computer Science and Information Engineer, National Chiao-Tung University, Taiwan, 1993.
[16] Gwan-Hwan Hwang, Kuo-Chung Tai, and Ting-Lu Huang, “Reachability Testing: An Approach To Testing Concurrent Software,” International Journal of Software Engineering and Knowledge Engineering, 5, 4, (Dec. 1995), 493-510.
[17] Gwan-Hwan Hwang, Sheng-Jen Chang, and Huey-Der Chu, “Technology for Testing Nondeterministic Client/Server Database Applications,” IEEE Transaction on Software Engineering, Volume 30, Number 1, pp. 59-77, Jan., 2004.
[18] Kuo-Chung Tai, “Reachability Testing of Asynchronous Message-passing Programs,” Proceedings of the second International Workshop on Software Engineering for Parallel and Distributed Systems, 1997.
[19] Yu Lei and Kuo-Chung Tai, “Efficient Reachability Testing of Asynchronous Message-Passing Programs,” Proceedings 8th IEEE Intl. Conf. on Engineering for Complex Computer Systems, pp. 35-44, Dec. 2002.
[20] Richard H. Carver and Yu Lei, “A General Model for Reachability Testing of Concurrent Programs,” ICFEM 2004, LNCS 3308, pp. 76-89, 2004.
[21] Yu Lei and Richard H. Carver, “Reachability Testing of Concurrent Programs,” IEEE Transaction on Software Engineering, Volume 32, Number 6, pp. 382-403, June 2006.
[22] Koushik Sen and Gul Agha, “Automated Systematic Testing of Open Distributed Programs,” The 9th International Conference on Fundamental Approaches to Software Engineering, FASE 2006, pp. 339-356.
[23] Che-Sheng Lin and Gwan-Hwan Hwang, “State-cover Testing for Nondeterministic Concurrent Programs with an Infinite number of Synchronization Sequences,” submitted to IEEE Transaction on Software Engineering for publication.
[24] K. Sen, “Effective Random Testing of Concurrent Programs,” Proceedings of 22nd IEEE/ACM International Conference on Automated Software Engineering (ASE’07), pp. 323-332, 2007.
[25] P. Joshi, M. Naik, C.-S. Park, and K. Sen, “An Extensible Active Testing Framework for Concurrent Programs,” Proceedings 21st International Conference on Computer Aided Verification (CAV'09), 2009.
[26] “ConTest - A Tool for Testing Multi-threaded Java Applications,” http://www.haifa.ibm.com/projects/verification/contest/.
[27] Orit Edelstein, Eitan Farchi, Evgeny Golden, Yarden Nir, Gil Ratsaby and Shmuel Ur, “ConTest – A User's Perspective,” The 5th International Conference on Achieving Quality In Software, Italy, March 13, 2002.
[28] Yarden Nir-Buchbinder and Shmuel Ur, “Multithreaded Unit Testing with ConTest,” http://www.ibm.com/developerworks/java/library/j-contest.html.
[29] Yu Lei, Richard H. Carver, Raghu Kacker, and David Kung, “A Combinatorial Testing Strategy for Concurrent Programs,” Software Testing, Verification & Reliability , Volume 17, Issue 4, pp. 207-225, December 2007.
[30] M. Musuvathi and S. Qadeer, “Fair Stateless Model Checking,” ACM Conference on Programming Language Design and Implementation (PLDI), 2008.
[31] M. Musuvathi and S. Qadeer, “Iterative Context Bounding for Systematic Testing of Multithreaded Programs,” ACM Conference on Programming Language Design and Implementation (PLDI), 2007.
[32] Verification and Validation Laboratory ,Computer Science Department,Brigham Young University"Concurrency Tool Comparison" https://facwiki.cs.byu.edu/vv-lab/index.php/Concurrency_Tool_Comparison
[33] Verification and Validation Laboratory, Computer Science Department,Brigham Young University"Java benchmarks " svn://svn-smc.cs.byu.edu/smc-lab/concurrency-benchmarks/Java
[34] Che-Sheng Lin and Gwan-Hwan Hwang ,” Dynamic Effective Testing: An Approach to Testing Concurrent Programs”http://www.csie.ntnu.edu.tw/~ghhwang/DET2010.pdf
[35] Bill Venners "Thread Synchronization" in Thread Synchronization,2nd,McGraw-Hill Professional ,1997