並行程式在現代的計算中已經變得非常地普遍。然而，因為並行程式的非確定性行為，在並行程式中的錯誤通常都很難被偵測到。在電腦科學中信號機是其中一個主要的同步機制，在多元程式規劃中，它通常被用來控制共享資料的存取。對信號機的誤用是一個非常嚴重的問題，因為這可能導致程式發生死結或是造成一些對共享資料的違規存取。
在這篇論文中，我們會描述如何將動態敏捷測試應用到測試使用信號機的並行程式。我們提出了一些可以對信號機的運算做前綴重播(prefix-based replay)和當死結發生時能夠記錄下程式狀態的協定。我們也針對使用信號機的程式定義了新的同步序列格式。然後，我們提出了一個演算法用來過濾掉被競爭分析(race analyzer)產生的不可行的競爭變異(race variant)。最後，我們發展了一個壓縮的功能來解決被重複的事件所引起的狀態空間爆炸(state space explosion)問題。如此一來，我們可以成功地針對使用信號機和共享記憶體的並行程式做狀態全覆(state-cover)的動態測試，並且可以產生使用信號機以及共享記憶體的並行程式的所有狀態以及所有在程式中的死結。

Concurrent program is becoming commonplace in modern computing. However, the bugs in concurrent program are usually difficult to be detected because of the non-deterministic behavior of concurrent programs. Semaphore is one of the major synchronization mechanisms in computer science. It often used to control the access of shared data in a multiprogramming environment. The misuse of semaphore is a very serious problem, because this may cause the program deadlock or make some inappropriate access of shared data.
In this thesis, we describe how to apply dynamic effective testing to semaphore-based concurrent programs. We propose some protocols that can perform prefix-based replay on semaphore operations and record the program status when the deadlock happened. We also define a novel format for the SYN-sequence of semaphore-based program. Then, we have an algorithm to filter out the infeasible race variants generated by race analyzer in reachability testing. Last, we develop a compression function to deal with the state space explosion problem induced by the reiterative events. Thus, we can successfully perform state-cover testing for semaphore-based and shared memory concurrent programs and find out all the states of the concurrent programs which contain shared semaphores and shared memories and all the deadlocks in the programs.

[1] Charles E. Mcdowell and David P. Helmold, “Debugging Concurrent Programs,” ACM Computing Surveys, vol. 21, no. 4, pp. 593-622, Dec. 1989.
[2] K.C. Tai and Richard H. Carver, “Testing of Distributed Programs,” in Parallel and Distributed Computing Handbook, Albert Y. Zomaya Ed. New York: McGraw-Hill, 1996, pp. 955-978.
[3] Anne Dinning, “A Survey of Synchronization Methods for Parallel Computers,” IEEE Computer, vol. 22, no. 7, pp. 66-77, July 1989.
[4] Abraham Silberschatz, Peter Baer Galvin, and Greg Gagne, Operating System Concepts, 6th ed. New York: John Wiley, 2001.
[5] D. Helmbold and D. Luckham, “Debugging Ada Tasking Programs,” IEEE Software, vol. 2, no. 2, pp. 47-57, Mar. 1985.
[6] K. C. Tai, “Testing of Concurrent Software,” Proc. 13th Annual International Computer Software and Applications Conf., pp. 62-64, Sep. 1989.
[7] W. Richards Adrion, Martha A. Branstad, and John C. Cherniavsky, “Validation, Verification, and Testing of Computer Software,” ACM Computing Surveys, vol. 14, no. 2, pp. 159-192, June 1982.
[8] Roger S. Pressman, Software Engineering (A practitioner’s approach), 5th ed. New York: McGraw-Hill, 2000.
[9] Che-Sheng Lin and Gwan-Hwan Hwang, “State-Cover Testing for Nondeterministic Concurrent Programs with an Infinite Number of Synchronization Sequences,” Submitted to IEEE Transactions on Software Engineering, 2010 for publication.
[10] Sun Microsystems, Inc., “Java Semaphore,” http://java.sun.com/javase/6/docs/api/java/util/concurrent/Semaphore.html, 2009.
[11] 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.
[12] Kuo-Chung Tai, “Reachability Testing of Asynchronous Message-passing Programs,” Proc. 2nd International Workshop on Software Engineering for Parallel and Distributed Systems, 1997.
[13] Yu Lei and Kuo-Chung Tai, “Efficient Reachability Testing of Asynchronous Message-Passing Programs,” Proc. 8th IEEE International Conf. on Engineering for Complex Computer Systems, pp. 35-44, Dec. 2002.
[14] Richard H. Carver and Yu Lei, “A General Model for Reachability Testing of Concurrent Programs,” ICFEM 2004, LNCS 3308, pp. 76-98, 2004.
[15] Yu Lei and Richard H. Carver, “Reachability Testing of Concurrent Programs,” IEEE Transactions on Software Engineering, vol. 32, no. 6, pp. 382-403, June 2006.
[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, vol. 5, no. 4, pp. 493-510, Dec. 1995.
[17] Gwan-Hwan Hwang, Sheng-Jen Chang, and Huey-Der Chu, “Technology for Testing Nondeterministic Client/Server Database Applications,” IEEE Transactions on Software Engineering, vol. 30, no. 1, pp. 59-77, Jan. 2004.
[18] Thomas J. LeBlanc and John M. Mellor-Crummey, “Debugging Parallel Programs with Instant Replay,” IEEE Transactions on Computers, vol. 36, no. 4, pp. 471-482, April 1987.
[19] Yu Lei and Richard H. Carver, “Reachability Testing of Semaphore-based Programs,” Proc. 28th Annual International Computer Software and Applications Conf. (COMPSAC’04), 2004.
[20] K. Sen, “Effective Random Testing of Concurrent Programs,” Proc. 22nd IEEE/ACM International Conf. on Automated Software Engineering (ASE’07), pp. 323-332, 2007.
[21] P. Joshi, M. Naik, C.-S. Park, and K. Sen, “An Extensible Active Testing Framework for Concurrent Programs,” Proc. 21st International Conference on Computer Aided Verification (CAV'09), 2009.
[22] Microsoft, “CHESS: Find and Reproduce Heisenbugs in Concurrent Programs,” http://research.microsoft.com/en-us/projects/chess/, 2010.
[23] M. Musuvathi, S. Qadeer, and T. Ball, “CHESS: A Systematic Testing Tool for Concurrent Software,” Microsoft Research Technical Report MSR-TR-2007-149, 2007.
[24] M. Musuvathi and S. Qadeer, “Fair Stateless Model Checking,” ACM Conference on Programming Language Design and Implementation (PLDI), 2008.
[25] IBM, “ConTest - A Tool for Testing Multi-threaded Java Applications,” http://www.haifa.ibm.com/projects/verification/contest/.
[26] T. Li, C. S. Ellis, A. R. Lebeck, and D. J. Sorin, “Pulse: A Dynamic Deadlock Detection Mechanism Using Speculative Execution,” Proc. USENIX Annual Technical Conf., pp. 31-44, 2005.
[27] Neha Rungta and Eric G. Mercer, “Clash of the Titans: tools and techniques for hunting bugs in concurrent programs,” Proc. 7th Workshop on Parallel and Distributed Systems: Testing, Analysis, and Debugging, 2009.
[28] “Java PathFinder,” http://javapathfinder.sourceforge.net/.
[29] Felipe S. Sarmanho1, Paulo S. L. Souza1, Simone R. S. Souza1, and Adenilso S. Simão1, “Structural Testing for Semaphore-Based Multithread Programs,” ICCS 2008, LNCS 5101, pp. 337-346, 2008.
[30] Rahul Agarwal and Scott D. Stoller, “Run-time detection of potential deadlocks for programs with locks, semaphores, and condition variables,” Proc. 2006 workshop on Parallel and distributed systems: testing and debugging, pp. 51-60, 2006.
[31] D. R. Engler and K. Ashcraft, “RacerX: Effective, static detection of race conditions and deadlocks,” Proc. 24th ACM Symposium on Operating System Principles, pp. 237–252, Oct. 2003.
[32] A. Williams, W. Thies, and M. D. Ernst, “Static deadlock detection for Java libraries,” ECOOP 2005, LNCS 3586, pp. 602-629, 2005.
[33] Yu Lei, Richard H. Carver, Raghu Kacker, and David Kung, “A Combinatorial Testing Strategy for Concurrent Programs,” Software Testing, Verification & Reliability, vol. 17, no. 4, pp. 207-225, Dec. 2007.
[34] John Ellson, Emden Gansner, Yifan Hu, and Arif Bilgin, “Graphviz - Graph Visualization Software,” http://www.graphviz.org/.
[35] Allen B. Downey, The Little Book of Semaphores, 2008.
[36] J.-D. Choi and H. Srinivasan, “Deterministic Replay of Java Multithreaded Applications,” Proc. SIGMETRICS Symposium on Parallel and Distributed Tools, pp. 48-59, 1998.
[37] Yan-You Li, “The Formal Verification of SYN-sequences Generated in Dynamic Testing,” Master thesis, Department of Computer Science and Information Engineering, National Taiwan Normal University, Taiwan, 2009.