軟體測試(software testing)是軟體工程一重要的階段，產品上市之前藉由軟體測試可以讓工程師驗證是否與當初設計的原意符合，也可以找出許多產品上的缺陷，在循序結構(sequential)的程式中做測試往往得到的結果都是可以預料的，但是在並行結構(concurrent)執行時，若程式規模較大所產生的結果就未必能夠預測。
所謂並行程式是指包含多個行程(Process)或是執行緒(thread)同時執行，並且完成所指派某些的任務，常見的並行程式測試的方法包含非決定性測試(Non-deterministic Testing)、決定性的測試(deterministic testing)、可達性測試(Reachability Testing)，前面兩者第一個主要缺點是程式執行測試所找到的交錯(Interleaving)的涵蓋率極低，第二個缺點是在於按照自訂的順序所執行，產生較繁瑣，第三個方法去除了上述兩個缺點，且能夠找到程式執行時的交錯(Interleaving)也能完全找到。
本論文主要是在以單一通道多個接收者非同步訊息傳遞為基礎的程式(Single-Channel-Multiple-Receivers Asynchronous Message Passing-Based Programs)上做動態測試，由於非同步訊息傳遞為基礎的程式可能存在潛在的競爭情況(message race)，若在設計程式時未考慮到有非決定性的行為(non-deterministic behavior)，所產生的結果可能會造成嚴重的損失，甚至導致整體的系統停擺，我們使用的架構是採用可達性測試(Reachability Testing)，可達性測試結合了非決定性測試以及決定性測試的特性，可以根據收集來的資訊，有效的分析競爭情況，進而導出執行時各種競爭情況可能產生的執行順序，但是單純使用傳統的可達性測試在非同步訊息傳遞程式上做測試可能會有死結(Deadlock)問題，因為可達性架構所設計的情況是針對share memory裡的read和write事件，所以必須針對整體架構做大幅度的修改，才能方便在受測程式上做動態測試(Dynamic Testing)，且可針對欲分析的情況做紀錄特定的資訊，將分析結果收集判定是否存在錯誤情況的發生。

The Software testing is a one of phase of software engineering. This can find out defects on Products, in the sequential program testing, the results often can be predicted, but in the concurrent testing results are always unpredicted.
The concurrent program is composed by more than one Processes(or Threads) to complete the assigned tasks at the same time ,The common testing methods include Non-Deterministic Testing、Deterministic Testing and Reachability Testing , The Non- Deterministic Testing lets the Programs free running on Testing , but It may only show part of situation . Not all cases, Deterministic Testing of Concurrent Program P is carefully select a set of tests (X,S), and the forced execution determines whether S is feasible for P , But deterministic testing has additional problems to solve. One major problem is deciding which pairs of inputs and SYN-sequences to select for a concurrent program.
In this paper, I will study how to use reachability testing in dynamic testing of Single-Channel-Multiple-Receivers asynchronous message passing programs. Because the reachability testing is used in test shared memory read/write event. If I use the reachability testing on asynchronous message passing programs. It will be deadlock, It is necessary for architecture to make big changes. Finally, I will use a modified version of reachability testing method on asynchronous message passing programs, and collect execution information to do analysis of whether there is message competition.

[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] E.Clarke,O.Grumberg,and D. Peled ,”Model Checking”. The MIT Press,1999.
[4] Wikipedia “Message-Passing”, http://en.wikipedia.org/wiki/Message_passing
[5] Abraham Silberschatz, Peter Baer Galvin and Greg Gagne,”Operating System Concepts ” , John Wiley & Sons,ISBN: 0471725951,7th edition(2006)
[6] Yu Lei and Eric Wong , “A Novel Framework for Non-deterministic Testing of Message-Passing Program”,pp. 66 - 75,HASE 2005. Oct. 2005
[7] 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.
[8] Che-Sheng Lin and Gwan-Hwan Hwang ,“State-cover Testing for Nondeterministic Concurrent Programs with an infite number of Synchronization Sequence”
[9] Gwan-Hwan Hwang , Kuo-Chung Tai and Ting-Lu Huang, “Rechability Testing : An Approach to Testing Concurrent Software” Software Engineering Conference,pp246-255, 7-9 Dec 1994
[10] Gwan-Hwan Hwang , Sheng-Jen Chang and Huey-Der Chu, “Technology for Testing Nondeterministic Client/Server Database Applications”, IEEE Transactions on Software Engineering,pp59-77, April 2004
[11] J Lei , “Non-deterministic Testing of Concurrent Programs”, ISSRE 2003
[12] Jason Gait, “A probe effect in concurrent programs”, Software: Practice and Experience, Volume 16, Issue 3, pages 225–233, March 1986
[13] D. Heimbold and D. Luckham, “Debugging Ada Tasking Programs”, Journal IEEE Software archive, Volume 2 Issue 2, March 1985
[14] Yu Lei and Richard Carver, “Reachability Testing of Semaphore-based Programs”, COMPSAC '04 Proceedings of the 28th Annual International Computer Software and Applications Conference - Volume 01,2004
[15] Yu Lei and Richard Carver, “A New Algorithm for Reachability Testing of Concurrent Programs”, ISSRE’05 , 2005
[16] Kuo-Chung Tai ,” Rechability Tesing of Asynchronous Message Passing Program”, Software Engineering for Parallel and Distributed Systems,pp50-61., 1997
[17] TOSHIAKI KUROKAWA and MASATO SHINAGAWA , “Technical Trends and Challenges of Software Testing”, pp34-45. 2008
[18] Kuo-Chung Tai ,” Race analysis of traces of asynchronous message-passing programs”, International Conference on Distributed Computing Systems, 1997.
[19] Yu Lei and Kuo-Chung Tai, ” Effcient Reachability Testing of Asynchronous Message-Passing Program”, ICECCS '02 Proceedings of the Eighth International Conference on Engineering of Complex Computer Systems, 2002.
[20] RICHARD H. CARVER and KLJO-CHLJNG TAI , “Replay and testing for concurrent programs”, pp66-74. Volume: 8, Issue: 2, March 1991
[21] Kuo-Chung Tai , Richard H. Carver and Evelyn E. Obaid ,“Debugging concurrent Ada programs by deterministic execution”, IEEE Transactions on Software Engineering, Volume 17 Issue 1, January 19911