對於單一通道多個接收者非同步訊息傳遞程式的動態測試

Dynamic Testing for Single-Channel-Multiple-Receivers Asynchronous Message Passing Programs

周柏宏(Bo Hung Chou)

指導教授 ： 黃冠寰

國立臺灣師範大學/理學院/資訊工程研究所/碩士(2012年)

摘要

軟體測試(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.

並列關鍵字

Concurrent Testing ； Concurrent Program ； Non-deterministic behavior ； Non-deterministic Testing ； Deterministic Testing ； Reachability Testing ； Asynchronous message passing programs

參考文獻

[1] Charles E. Mcdowell and David P. Helmold, “Debugging Concurrent Programs,” ACM Computing Surveys, Volume 21, Issue 4, December 1989.

[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.