對於非決定性並行軟體的語句覆蓋測試

Statement Coverage Testing for Non-deterministic Concurrent Software

林劭彥(Shao-Yan Lin)

指導教授 ： 黃冠寰

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

摘要

不論是軟體專案、工程專案或是其他許許多多的應用程式，在完成之前總是需要大大小小的測試來驗證其可靠性。以軟體來說單元測試、功能測試接著是整合測試等等。但是測試所花費的成本十分的高，不管是人力成本或是其他相關的軟硬體成本都不少。而statement coverage通常被要求是軟體測試中的一項指標。
在並行程式中的statement coverage需要考慮數隻程式同時執行的情況，如何得知有哪些statement無法執行到是因為什麼條件，便需要利用symbolic execution。再來同一組輸入執行多次可能有不同的結果，要如何將所有的可能的interleaving都一一找到，這邊介紹了三種方法Concolic Testing、Model checking與Reachability Testing並加以介紹與比較。
此篇研究主要在於發展一種測試的方法，來達到statement coverage。以現有的Reachability Testing為基礎，加上symbolic execution來達成statement coverage。提出一套演算法利用Statement Mapping Table來和SYN-sequence結合，來探討程式中未能執行到的statement是否可透過更改輸入，來讓它被執行到。最後告知使用者程式是否有存在dead code無法執行到或是可以在一個或數個輸入之下順利達成statement coverage。

關鍵字

並行程式 ； 符號執行 ； 可達性測試 ； 語句覆蓋

並列摘要

No matter what the software project, engineering projects or other applications is, we need a lot of different tests to verify the reliability before completion.In software testing, we need unit testing first, and then function testing. Finally, we need to integration testing. But the cost of testing is extremely high, regardless of human cost, or other related costs. And Statement Coverage is usually a criterion of software testing.Statement coverage in concurrent software needs to consider the different application execution simultaneously. To know which statement cannot be performed and with what condition, we need to use symbolic execution. Because the same input might causes different results, we should find out all the possible interleaving.
In this paper, we introduce and compare Concolic Testing, Model checking and Reachability Testing.The purpose in this paper is to develop a testing method to achieve the Statement Coverage.In addition to achieve Statement Coverage, we combine existing Reachability Testing and symbolic execution together . We propose an algorithm which uses the Statement Mapping Table with the SYN-sequence to discuss whether the non-reach statement can be executed by changing the input. Last but not the less, we would tell the user whether the program exists dead code cannot be performed or can enter in one or several inputs to reach Statement coverage.

並列關鍵字

current program ； symbolic execution ； Reachability Testing ； statement coverage

參考文獻

[23] Che-Sheng Lin and Gwan-Hwan Hwang, “State-Cover Testing for

Information Engineering, National Taiwan Normal University, 11677 Taipei

[1] Charles E. Mcdowell and David P. Helmold, “Debugging Concurrent

[2] K.C. Tai and Richard H. Carver, “Testing of Distributed Programs,” Chapter 33

in Parallel and Distributed Computing Handbook, Editor: A. Y.