隨著多核心電腦的快速發展，軟體也趨向多執行緒開發，然而，並行程式會造成非決定性行為，也就是說給定一組輸入，執行多次後可能會產生多個不同運行順序和結果，這產生了一個關於同步程式測試的重要議題：如何將目標程式所有可能執行順序找出來，在這篇論文中，我們提出了一個動態測試架構，可運用在Java監視器和共享記憶體上，這個動態測試架構只需要去分析在執行時蒐集到的同步序列，而不需要對語法以及語義做靜態測試，更不需要使用測試模組來找出所有可能的交錯執行順序，只要可行的同步序列是有限的，就能使用我們提出的架構來進行測試，找出並行程式所有可能的執行順序，達到測試的效果。

Concurrent programs exhibit nondeterministic behavior in that multiple executions thereof with the same input might produce different sequences of synchronization events and different results. This is because different executions of a concurrent major issues in the testing of concurrent programs is to explore different interleavings or exhaust all the possible interleavings of the target programs. In this paper we present a framework we have developed for performing dynamic testing on monitor-based and shared-memory concurrent programs. The proposed scheme only has to analyze the synchronization sequences (SYN-sequences) that are collected during the dynamic testing of the concurrent program – static analysis of syntax and semantics of the target concurrent program is unnecessary. It also does not need to employ a model checker to explore the feasible interleavings of the execution of the concurrent program. If the SYN-sequence of the tested concurrent program is finite, our scheme can perform dynamic testing on all the feasible SYN-sequences. The implementation and experimental results obtained with real codes and some benchmark programs demonstrate the feasibility of the proposed scheme.

[1]Charles E. Mcdowell and David P. Helmold, "Debugging Concurrent Programs," ACM Computing Surveys, Volume 21, Issue 4, December 1989.
[2]Anne Dinning, "A Survey of Synchronization Methods for Parallel Computers, " IEEE Computer, July 1989.
[3]Abraham Silberschatz, Peter Baer Galvin, and Greg Gagne, "Operation System Concepts, " John Wiley & Sons, ISBN: 0471417432, 6th Edition, June 26, 2001.
[4]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, pp. 493-510, December 1995.
[5]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.
[6]Roger S. Pressman, "Software Engineering (A practitioner’s approach), " 5th Edition, 2000, Mc Graw-Hill Education, ISBN 978-0071181822.
[7]K. C. Tai, "Testing of Concurrent Software, " Proceeding of the 13th annual International Computer Software and Applications Conference, pp. 62-64, 1989.
[8]S. D. Stoller, "Testing Concurrent Java Programs Using Randomized Scheduling," Proceedings of the 2nd Workshop on Runtime Verification, Amsterdam, 2002.
[9]Edelstein O., Farchi E., Nir Y., Ratsaby G., and Ur S.,"Multithreaded Java Program Test Generation," IBM Systems Journal, Volume 41, Issue 1, pp. 111-125, 2002.
[10]D. Helmbold and D. Luckham, "Debugging Ada Tasking Programs, " IEEE Software, Volume 2, Number2, pp. 66-74, 1985.
[11]Y. Ben-Asher, E. Farchi, and Y. Eytani, "Heuristics for Fingin Concurrent Bugs, " Proceeding of the International Parallel and Distributed Processing Symposium (IPDPS 2003), April, 2003.
[12]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, January, 2004.
[13]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.
[14]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.
[15]"ConTest — A Tool for Testing Multi-threaded Java Applications, " http://www.haifa.ibm.com/projects/verification/contest/ .
[16]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.
[17]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.
[18]Microsoft, "CHESS: Find and Reproduce Heisenbugs in Concurrent Program, " http://research.microsoft.com/en-us/projects/chess/, 2010.
[19]M. Musuvathi, S. Qadeer, and T. Ball, "CHESS: A Systematic Testing Tool for Concurrent Software, "Microsoft Research Technical Report MSR-TR-2007-149, 2007.
[20]M. Musuvathi and S. Qadeer, "Fair stateless Model Checking," ACM Conference on Programming Language Design and Implementation (PLDI), 2008.
[21]Felipe S. Sarmanhol, Paulo S. L. Souzal, Simone R. S. Souzal, and Adenilso S. Simaol, "Structual Testing for Semaphore-Based Multithread Programs, " ICCS 2008, LNCS 5101, pp. 337-346, 2008.
[22]Rahul Agarwal and Scott D. Stoller, "Run-time detection of potential deadlocks for programs with locks, semaphores, and condition variable, " Proc. 2006 workshop on Parallel and distributed systems: testing and debugging, pp. 51-60, 2006.
[23]A. Williams, W. Thies, and M. D. Ernst, "Static deadlock detection for Java libraries, " ECOOP 2005, LNCS 3586, pp. 602-629, 2005.
[24]Kuo-Chung Tai, "Reachability Testing of Asynchronous Message-passing Programs, " Proceeding of the second International Workshop on Software Engineering for Parallel and Distributed Systems, 1997.
[25]Richard H. Carver and Yu Lei, "A General Model for Reachability Testing of Concurrent Programs, "ICFEM 2004, LNCS 3308, pp. 76-98, 2004.
[26]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.
[27]Che-Sheng Lin and Gwang-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.
[28]Che-Sheng Lin and Gwan-Hwan Hwang, "Dynamic Effective Testing: An Approach to Testing Concurrent Programs," Technical Report, National Taiwan Normal University, 2010.
[29]Yu Lei, Carver R., Kung D., Gupta V., Hernandez M., "A State Exploration-Based Approach to Testing Java Monitors," International Symposium on Software Reliability Engineering (ISSRE '06), pp. 256-265, Nov. 2006.
[30]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.
[31]Allen B. Downey, "The little book of Semaphores," 2008.