最佳測試個案選取問題之研究

Abstract

最佳測試個案選取問題探討如何選取最少測試個案以滿足一個指定的涵蓋準則，最佳測試個案選取問題已有相當多的研究成果，然而現有的研究成果有以下缺點： 1.利用現有的最佳路徑集合選取方法對一個複雜的程序導向程式所找到的路徑集合在某些階段並不一定是最佳的， 2.在迴歸測試中，現有的測試個案選取方法無法保證找到的測試個案集合是最佳的， 3.物件導向程式測試的最佳測試個案選取問題並未被探討。 本研究旨在探討及解決上述三個缺點。 第一個缺點是因為現有的最佳路徑集合選取方法沒有考慮涵蓋準則之間的包含關係所造成的，假如涵蓋準則C1被涵蓋準則C2所包含，滿足涵蓋準則C1的最佳路徑集合P1也滿足C2的部分元件，因此本論文提出可由剩餘未測試路徑中選取一個最佳路徑集合滿足所有未被涵蓋的元件，此最佳路徑集合與P1的聯集滿足C2且包含最少未測試路徑。 尋找一個測試個案集合的一個最小子集合以滿足迴歸測試之需求稱為最佳代表集合選取問題，最佳代表集合選取問題與最佳路徑集合選取問題同屬集合涵蓋問題，因此本論文提出可利用零壹最佳路徑集合選取方法來解決最佳代表集合選取問題。 假如一個物件導向程式只由一個執行緒所執行，此一程式是一個循序物件導向程式，否則是一個並行物件導向程式。循序物件導向程式通常利用由下而上的方式作測試，一次測試一個類別，類別測試順序是：被使用的類別先測，再測使用的類別，及被繼承的類別先測，再測衍生的類別。由於一個函式的路徑數目通常很小，對單一函式測試實無必要作最佳測試個案選取。同一類別之不同函式的路徑集合是相互獨立的，所以一個類別內各個函式的最佳路徑集合的聯集應為該類別的最佳路徑集合。同樣地，不同類別的路徑集合是相互獨立的，所以在循序物件導向程式測試談最佳測試個案選取問題並不是很有意義。 探討並行物件導向程式測試的最佳測試個案選取問題之前應先了解程式的測試個案，因為目前尚無並行物件導向程式的測試方法，本論文提出一個two-step plus bottom-up並行Java程式測試方法，此一測試方法的測試個案包括：類別的路徑集合、main()函式的路徑集合、主動類別的run()函式的路徑集合以及並行路徑集合。在單一類別、main()函式以及主動類別的run()函式測試談最佳測試個案選取問題並不是很有意義，但是在並行路徑測試談最佳測試個案選取問題則是有意義的，本論文提出可利用零壹最佳路徑集合選取方法來找到最小的並行路徑集合以滿足一個涵蓋準則。

The optimal test case selection problem is to select the minimal number of test cases satisfying a required coverage criterion. Many studies dealing with the optimal test case selection problem are available. However, these studies suffer the following drawbacks: 1.Applying existing optimal path set selection methods to a complicated procedure-oriented program, the path set derived may not be optimal in some stage(s). 2.Existing test case set selection methods in regression testing can not ensure that the test case set found is optimal. 3.The optimal test case selection problem in object-oriented (OO) program testing is rarely discussed. The goal of this research is to propose some methods to solve the above three drawbacks. The first drawback is caused by that the existing optimal path set selection methods do not consider the subsumption relation of coverage criteria. If a coverage criterion C1 is subsumed by another coverage criterion C2, the optimal path set P1 satisfying C1 should satisfy partial set of components of C2. So this dissertation proposes to find the optimal path set from the remaining unselected paths to satisfy the remaining uncovered components of C2, the union of the obtained optima path set and P1 will contain the minimal number of untested paths to satisfy C2. Finding a minimal subset of a test suite to satisfy the requirements of the regression testing is referred to as optimal representative set selection problem. Both the optimal representative set selection problem and the optimal path set selection problem are equivalent to solving the set-covering problem, so this dissertation proposes to adapt the enhanced zero-one optimal path set selection method to find the optimal representative set for the regression testing. If an OO program is executed by only one thread, this program is considered as a sequential OO program. Otherwise, it is a concurrent OO program. Sequential OO programs are usually tested by bottom-up approach which tests a class at a time and tests used (or base) class before using (or derived) class. Since the number of paths of a method is usually small and the path set of a method is disjoint with the path set of another method, it is not meaningful to discuss the optimal path set selection problem of a class. Similarly, the path set of a class is disjoint with the path set of another class, so it is not meaningful to discuss the optimal path set selection problem of sequential OO program. To discuss the optimal path set selection problem of a concurrent OO program, we should know the test cases of this program first. However, no concurrent OO program testing method is available now. This dissertation proposes a two-step plus bottom-up method to test concurrent Java program first. Based on this method, the test cases include path sets to test classes, the main() method, and run() methods of active classes, and concurrent paths to test inter-thread interaction behavior of the concurrent Java program. It is not meaningful to discuss optimal path set selection problem of a class, the main() method, or a run() method. However, this dissertation proposes to apply the enhanced zero-one optimal path set selection method to find the minimal number of concurrent paths to satisfy a criterion.