以途徑分析方法做並行程式測試

Abstract

A concurrent program consists of concurrent synchronized task; its execution behavior is nondeterministic. Because of indeterminacy, it is generally accepted that testing concurrent programs is more difficult than testing sequential ones. However, most of previous achievements on program testing are specifically designed for sequential program testing; the area of concurrent program testing has received little attention in the past. In this dissertation, a path analysis approach, derived from conventional path analysis testing methodology for sequential programs, is proposed for concurrent program testing. Three basic issues of concurrent program testing, namely, test case difinition, coverage measurement, and test execution, are investigated. A concurrent path model is proposed for modeling the execution behavior of concruuent program. In the model, program flowgraph is used to model the static structure, and rendezvous graph to model the dynamic structure, of a concurrent program. Accordingly, a computation of the concurrent program is modeled as a three-tuple (α,σ,δ), where α is an input, σ is a concurrent path of program flowgraph, and δ is a concurrent route of rendezvous graph. Each possible execution result of a concurrent program can be uniquely identified by computation. Based on the model, path analysis testing of concurrent program is regarded as a process to select concurrent paths and concurrent routes and to verify their correctness. To guide testers in testing concurrent programs step by step, a path analysis testing methodology is presented. The methodology uses definite test case, which consists of an input and a concurrent route, to identify the execution behavior to be tested; and a two-stage test execution strategy to systematically execute concurrent program with generation and test execution issues. For test coverage issue, several program-based coverage criteria are defined, including criteria for measuring test coverage of static structure, and criteria for measuring test coverage of dynamic structure, of concurrent programs. For test path generation issue, static feasibility of concurrent paths is investigated. A static analysis technique based on the analysis of execution order of rendezvous statements is proposed for identifying static infeasible concurrent paths. And, an algorithm based on reachability analysis technique is presented for generating static feasible concurrent paths of a concurrent program. For test case generation issue, the problems of concurrent rout and input generation are studied. Two algorithms are proposed for generating feasible concurrent routes along a concurrent paht. One is based on the analysis of possible ways to traverse the concurrent path, and the other is based on the analysis of possible execution sequences of rendezvous statements in the concurrent path. It also has been shown that, with slight extension, the input generation techniques for sequential programs is applicable to input generation for concurrent programs. For test execution issue, a test execution mechanism based on program transformational approach is designed for monitoring and controlling test execution of concurrent program. One distinguished feature of our test execution mechanism is thatno extra control task is needed; the execution monitor and control are done by the monitored and controlled task themselves. To minimize the need of execution monitor and control in test execution, deterministic input, which can be tested without execution monitor and control, is presented. Several decision rules are proposed for identifying deterministic inputs of a concurrent program. 近年來並行程式設計逐漸受到重視，由於並行程式具有許多‘工作單元’（task）同 時執行，且各工作單元之間又互有交互關係（synchronization） ，因此產生了許多 新的測試問題，例如測試資料格式定義、測試涵蓋度之量度（coverage measurement ）、測試資料執行技巧（test execution mechanism）等等，但過去有關並行程式測 試之研究成果仍十分有限。本研究擴充傳統途徑分析測試方法（path analysis testing method），提出一個整體性並行程式測試方法，並對並行程式之各項基本問 題做整合性的探討。 本論文中首先提出一並行途徑模式（concurrent path model） 來模塑並行程式之所 有可能執行行為，並提出並行程式途徑分析測試方法（path analysis testiong methodology） 以系統化測試步驟測試並行程式各執行行為之正確性。此方法採用確 定測試資料（definite test case）做為測試資料格式，提出二階段式測試資料 執行策略以系統化的方式執行所有確定測試資料。為使此測試方法實用化，本文中並 逐一探討做途徑分析測試中所遭遇之四個實用性問題－－涵蓋度之量度標準，測試途 徑產生方法，測試資料產生方法與執行控制技巧。 本文中提出許多量度標準（coverage criteria） ，來測量並行程式各種不同特性之 測試涵蓋度；設計各種演算法分析沿一並行途徑執行時可能之同步狀況，以判定並行 途徑之靜態可執行性（static feasibiliyt），產生並行程式的所有靜態可執行之並 行途徑及其對應之確定測試資料；並利用程式轉換方式，設計執行監督與控制技巧， 以有效掌握測試執行過程及降低測試執行之成本。