非決定性並行程式之動態測試

Dynamic Testing for Nondeterministic Concurrent Programs

林哲生(CHE-SHENG LIN)

指導教授 ： 黃冠寰

國立臺灣師範大學/理學院/資訊工程學系/博士(2013年)

摘要

對於並行程式而言，非決定性行為代表即使給予相同的輸入值，在多次執行的過程中仍可能產出不同的執行結果。非決定性行為導因於：並行程式給予相同輸入的多次執行中，內部指令具有多種執行順序。因此如何儘可能地找出所有執行順序、達到完整測試，一直是測試並行程式時的主要課題。然而當程式中具有忙碌等待迴圈而衍生重複進入相同狀態時，程式執行將衍生無窮多種執行順序，造成無法對所有執行順序完整測試。此論文提出一動態測試方法，藉由執行所有可達的狀態與狀態間轉移，充分測試具有迴圈行為的並行程式。相較於驗證並行程式時常用的模型檢驗方法，本文提出的測試方法具有：毋須對受測程式預先靜態分析，並降低與受測程式間的程式語言耦合度等優點。測試過程中僅需分析程式執行後產生的同步行為序記錄，用以分析執行中的競爭行為並限制執行時的狀態走訪情形；因此我們提出的測試方法將更易於根據需求移植至其他程式語言。最後透過實驗數據，我們將實證此種針對具有迴圈行為並行程式的充分測試可被系統化地完成。

關鍵字

並行程式 ； 非決定性行為 ； 並行測試 ； 可達性測試法 ； 終止決定 ； 訊息傳遞

並列摘要

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 program with the same input may exhibit different interleavings. Thus, one of the major issues in the testing of concurrent programs is how to explore different interleavings or exhaust all the possible interleavings of the target programs. However, for terminating concurrent programs that have cyclic state spaces due to using iterative statements such as busy-waiting loops, they might have an infinite number of feasible synchronization sequences; that is, there is an infinite number of possible interleavings, which makes it impossible to explore all the possible interleavings for this type of concurrent program. To overcome this problem, we propose a testing scheme called dynamic effective testing that can perform state-cover testing for nondeterministic terminating concurrent programs with an infinite number of synchronization sequences. Dynamic effective testing does not require static analysis of the target concurrent program or the assistance of a model checker, and thus is loosely coupled to the syntax of the target concurrent program. It only needs to analyze sequences of synchronization events produced by the execution of the concurrent programs for race detection and state-traversal control. Therefore, the method is easy to port to different programming languages. The implementation and experimental results obtained with real code demonstrate that source-code-level dynamic testing can be systematically performed on nondeterministic concurrent programs with infinite synchronization sequences.

並列關鍵字

Concurrent program ； Nondeterministic behavior ； Concurrent testing ； Reachability testing ； Termination decision ； Message passing

參考文獻

68. Y.-Y. Li. The Formal Verification of SYN-Sequence Generated in Dynamic Testing, Master Thesis, Department of Computer Science and Information Engineering, National Taiwan Normal University, Taiwan, 2009.

73. L.-T. Tsao. Dynamic Testing for Non-determinisitc Service-Oriented Architecture Application, Master Thesis, Department of Computer Science and Information Engineering, National Taiwan Normal University, Taiwan, 2009.

3. A. Dinning, “A Survey of Synchronization Methods for Parallel Computers,” IEEE Computer, Volume 22, Issue 7, pp. 66-77, July 1989. DOI = http://dx.doi.org/10.1109/2.30733.

8. K.-C. Tai, “Testing of Concurrent Software,” In Proceedings of the 13th Annual International Computer Software and Applications Conference, pp. 62-64, 1989. DOI = http://dx.doi.org/10.1109/CMPSAC.1989.65057.

13. R. N. Taylor, “A General-Purpose Algorithm for Analyzing Concurrent Programs,” Communications of the ACM, Volume 26, Issue 5, pp. 361-376, May 1983. DOI = http://dx.doi.org/10.1145/69586.69587.