靜態測試(白箱測試)

Testing from Internal

Testing code by looking into its internal structure and verify whether it satisfies the requirements, i.e., design test cases to cover Program structures, e.g., statements, branches, conditions, and/or paths Data flow definitions and usages Fault sensitive parts, e.g., mutation or domain testing

內部測試的意涵是將軟體程式打開，深入檢查它的內部結構，並藉由程式的執行，察看它是否滿足原始功能設計的要求。對於測試者而言，由於程式的各部份細節可以被察看並一覽無遺，因此，我們稱之為白箱測試。

白箱測試並沒有特定的缺陷對象要偵測。其基本精神是要確認程式的每一部份都是符合預期，並可以被正確地執行。為了達到這個目的，它會是針對受測軟體(稱作Software Under Test)內部的路徑、結構和實施細節來設計測試個案。正因為如此，它與黑箱測試不同；白箱測試一般要求測試者具備一定程度的編程技能。此外，白箱測試無法偵測缺漏型的缺陷。

White-Box Testing

Statement coverage Branch coverage Path coverage Condition coverage Mutation testing Data flow-based testing

常見的白箱測試主要有兩種：控制流測試（control flow coverage）與資料流測試(data flow-based testing)。此外，範圍測試（domain testing）與突變測試(mutation testing)也屬於白箱測試，但是較不容易實施，因此一般很少用到。

Statement Coverage

Statement coverage methodology Design test cases so that every statement in a program is executed at least once The principal idea Unless a statement is executed, we have no way of knowing if a fault exists in that statement But given only one test input poses no guarantee that it will behave correctly for all input values. 敘述涵蓋的準則是產生足夠的測試案例，以便程式中的每個敘述至少能被執行一次。其基本想法是除非每個敘述被有效地執行，否則我們沒法知道是否那個敘述裡隱藏著缺陷。但是只用一個測試個案不能保證一定會發現那個隱藏的缺陷，如果有的話。

Example Program

int f1(int x, int y){                    
  while (x != y){
    if (x>y) then 
         x=x-y;
    else y=y-x;
  }
  return x;        
}

Test Cases for Statement Coverage

An example test set could be following {(x=3,y=3), (x=4,y=3), and (x=3,y=4)} All statements are executed at least once here.

Problems in Statement Coverage

In order to examine code coverage we will use two simple code examples. The simple question is “Which of the two flow-graphs is more complex?” (Obviously the answer is B!) The next question is “Therefore which requires more testing?”. Again the answer is clearly B.

Statement Coverage Only

When examining code coverage, we can see that minimum 2 tests are required to cover all the code for example A. When looking at example B, we can also see that 2 similar tests will also cover all the code. In fact, if there were 1,000,000 decisions in sequence in example B, then 2 tests would still cover all the code. Clearly, code coverage has nothing to do with the amount of logic in a piece of code. In fact, Code coverage is just a mathematical side effect of executing code and is not a good mechanism for determining the testedness of code.

Branch Coverage

Test cases are designed such that different branch conditions is given true and false values in turn. Branch testing subsumes statement coverage i.e., a stronger testing compared to the statement coverage-based testing

分支涵蓋的準則是程式中的每個分支敘述至少能被一個測試個案執行過。其基本邏輯是除非每個程式的分支都被有效地執行，否則無法判斷是否有缺陷隱藏在某個分支裡。根據定義，分支涵蓋包含敘述涵蓋，亦即滿足分支涵蓋的測試準則，則必然滿足敘述涵蓋。

Test Cases for Branch Coverage

An example test set could be following {(x=3,y=3), (x=4,y=3), and (x=3,y=4)} All branches here are executed at least once

Condition Coverage

Test cases are designed such that each component of a composite conditional expression given both true and false values. stronger than branch testing Example Consider the conditional expression ((c1.and.c2).or.c3) Each of c1, c2, and c3 are exercised at least once i.e. given true and false values. 條件涵蓋是分支涵蓋的延伸。由於分支涵蓋只要求到各分支被執行，而並未考慮到分支的每一個條件是否都被驗證過。因此，就測試的角度來說，還是可能有隱藏的缺陷沒有被偵測到。所以條件涵蓋進一步要求每一個合成布林表示式中個別的條件，都必須被測試過一次。例如，合成條件((c1.and.c2) .or.c3)中的c1，c2和c3，至少都要有一次為真值，一次為假值。

Problems in Condition Coverage Testing

If a Boolean expression having n components For condition coverage, it will require 2n test cases Thus, it is practical only if n (the number of conditions) is small.

如果某個布林表示式有n個條件，對條件涵蓋來說，它將需要2n個測試案例。因此，只有當n(條件的數目)很小的時候，條件涵蓋才有可能被實行。

Independent Path & Cyclomatic Metric Testing

A path through a program is a node and edge sequence from the starting node to a terminal node of the control flow graph An independent path is one through the program that introduces at least one new node not included in any other independent paths. Design test cases such that all linearly independent paths in the program are executed at least once

所謂路徑，是指一條貫穿程式從控制流程圖的起點直到終點，由結點與連結交織而成的序列。而一條獨立路徑是一條貫穿程式的路徑，其中至少包含一個不在其他獨立路徑中的新結點。獨立路徑測試，是指所有程式中線性獨立的路徑，都必須被至少一個測試案例執行過。

雖然條件涵蓋考慮了各種條件的組合，但是範圍僅限於一個分支，並不包含多個分支的組合測試。從測試的角度來看，這樣仍然有所不足。但是若要涵蓋程式所有的路徑，在實務上並不可行。折衷的辦法是選取獨立路徑，或依照迴圈度量（Cyclomatic Metric）的要求加以測試。

McCabe's Cyclomatic Complexity

McCabe's complexity metric counts the number of independent paths through the program control graph G i.e., the number of basic paths (all paths composed of basic paths) The cyclomatic complexity (or number) is defined as V(G) = L - N + 2 * P, where L is the number of links in the graph, N is the number of nodes in the graph, and P is the number of connected parts in the graph P = 1 when there is only one program, no subroutines

馬克比的複雜度衡量（McCabe's complexity metric）可用來計算一個程式中獨立路徑的數目。假設程式的控制流程圖是G，則迴圈複雜度的定義為 V(G) = L - N + 2 * P，其中 L是圖中的連結數目，N是圖中的結點數目，P是圖中副程式的數目。（通常我們一個程式為計算單位，因此P = 1） 另一種方法也能計算馬克比的迴圈度量。在只有單一個入口和單一個出口的控制流程圖中，迴圈複雜度等於圖中二元分支的數目加一，亦即V(G) = B + 1，其中B是分支的數目。（一個三向分支等於兩個二元分支；一個N向分支等於N-1個二元分支。）

This metric can also be calculated by adding one to the number of binary decisions in a structured flow graph with only one entry and one exit counting a three-way decision as two binary decisions and N-way case statements as N – 1 binary decisions The rationale behind this counting of N-way decisions is that it would take a string of N – 1 binary decisions to implement an N-way case statement. Thus V(G) can be used as a lower bound for the number of test cases for branch coverage

Cyclomatic Complexity & Quality

McCabe's metric provides a quantitative measure of estimating testing difficulty, also the psychological complexity of a program, and the difficulty level of understanding the program since it increases with the number of decision nodes and loops. 馬克比度量還有另外一層意義，就是提供一個估計1）測試的困難度，2）程式的心理複雜性，和3）解讀程式的困難度之量化指標，因為這些會隨著分支以及迴圈的數目增加而增加。根據非正式的觀察顯示，以下幾點存在著相關性：馬克比度量、程式碼中缺陷的數目、以及測試程式碼所花費的時間。因此，馬克比度量可當作指引，以聚焦在測試高風險或難以測試的區域；或當作衡量測試進展的客觀指標以決定何時可以停止測試；也可以用來評估一個完整的測試所需要的時間和資源。

Applications of Cyclometic Complexity

Informal correlation exists among McCabe's metric, the number of faults existing in the code, and time spent to test the code. Thus, this metric can be used to focus testing on high-risk or hard-to-test areas objectively measure testing progress and know when to stop testing assess the time and resources needed to ensure a well-tested application

Cyclomatic Complexity & Risks

根據軟體工程研究所上面的網站所公布的建議，迴圈複雜度與風險之間的關連大約如上圖。

Some Limitations of Cyclomatic Complexity

The cyclomatic complexity is a measure of the program's control complexity and not the data complexity The same weight is placed on nested and non-nested loops. However, deeply nested conditional structures are harder to understand than non-nested structures. It may give a misleading figure with regard to a lot of simple comparisons and decision structures. Whereas the dataflow method would probably be more applicable as it can track the data flow and its usage.

迴圈複雜度所衡量的，是程式控制流程的複雜性而不是資料的複雜性。此外，對於同樣數量的巢狀和非巢狀迴圈，所得到的是同樣的複雜度，然而，深層的巢狀結構比非巢狀結構更難於理解。

Data-Flow Based Testing

A program performs its function through a series of computations with immediate results retrieving from and storing into different variables In contrast to checking program structure, a good place to look for faults is these variable definition-and-usage chains The data flow testing strategy is to select test cases of a program according to the locations of definitions and uses of different variables in a program.

除了控制流測試之外，結構測試還可以根據資料流來制訂測試準則。一支程式在接受輸入資料後，進行一連串的計算直到輸出最後的結果。這些從輸入到輸出的一連串資料變化，即是所謂的資料流。更具體來說，個別的資料流是指程式中某個資料值從「存入」一個變數到取出「使用」的流程。資料流測試就是要驗證這些資料流在程式中是正確的。 For a statement numbered S, DEF(S) = {X| variables that are defined in statement S} USES(S)= {X| variables that are referenced in statement S} For example, let statement 1 be a=b, then DEF(1)={a}, USES(1)={b}; Or let statement 2 be a=a+b, then DEF(1)={a}, USES(1)={a,b}. 我們需要一些定義來描述資料流測試的各種準則。假設S是一個敘述的編號，則DEF(S) = {X| 定義在敘述S的變數}是一個在S敘述被「存入」資料值的變數集合；USE(T)= {X| 在敘述T使用的變數}則剛好相反，是指在敘述T中「取用」資料值的變數集合。例如，假設敘述S是：a = b，則DEF(S)={a}，USES(S)={b}。

Definition-Use chain (DU chain)

A variable X is said to be live at statement S1, if X is defined at a statement S there exists a path from S to S1 not containing any definition of X, i.e., the value of X is not redefined. [X,S,S1] is a DU chain where S and S1 are statement numbers, X in DEF(S) X in USES(S1), and the definition of X in the statement S is live at statement S1.

從一個變數的「存入」到「取用」的流程，可用一個概念來描述，稱作這個變數的定義與使用鏈(definition-and-usage chains)。變數X被認為在敘述S1中是活的，如果從X被定義的敘述S到S1的任意一條路徑，都不包含任何X的定義，即X的值沒有被重新定義。則[X, S, S1]是一個定義與使用鏈，如果X in DEF(S)，X in USES(S1)，並且X的定義在敘述S1是活的。

DU Chain Example

1 X(){
2  a=5; /* Defines variable a */
3  While(C1) {                           
4     if (C2)                        
5           b=a*a;   /*Uses variable a */
6           a=a-1; /* Defines variable a */
7     }
8   print(a); } /*Uses variable a */

Data-Flow Based Testing Strategies

There are a number of testing strategies based on data flow information, e.g., all-def, all-use, all-DU-chain, etc. which are similar to the hierarchy of structure coverage testing criteria The simplest one is all-def, which requires every variable definition in a program be covered at least once All-DU-chain, on the other hand, is more comprehensive and requires every DU chain in a program be covered at least once.

類似於結構涵蓋。資料流測試的各種準則，由簡單到複雜，包含以下幾種： 定義涵蓋(All-defs) 使用涵蓋(All-uses) 定義與使用鏈涵蓋(All-DU-chains) 其中定義涵蓋最簡單，只需要程式中每個變數定義至少被一個測試案例執行過即可。而定義與使用鏈涵蓋最複雜，程式中的每個定義與使用鏈，都需要被執行至少一次。

Data Flow-Based Testing Example

   1 X() {
   2  B1;      /* Defines variable a */
   3  While(C1) {                           
   4     if (C2)                        
   5           if(C4) B4; /* Uses variable a */                    6          else B5;
   7          else  if (C3) B2;              
   8          else B3;     }
   9  B6 }

[a,1,5] a DU chain. Assume DEF(X) = {B1, B2, B3, B4, B5} USED(X) = {B2, B3, B4, B5, B6} There are 25 DU chains. However only 5 paths are needed to cover these chains.

Structure Based or Data-Flow Based

Structure based testing criteria, e.g., statement coverage, branch coverage, etc. are easier to implement; However, data-flow based testing strategies are more useful for selecting test paths of a program containing nested if and loop statements

一般來說，結構測試如，敘述涵蓋、分支涵蓋等比較容易實行。但是資料流測試對於包含巢狀IF以及迴圈敘述的程式會更有效。

Measuring Testing Quality -- Mutation Testing

First testing the software using any testing method or strategy that is discussed. After the planned testing is complete, mutation testing is applied. The idea behind mutation testing is to create a number of mutants that make a few arbitrary small changes to a program at a time; test a mutated program against the full test suite of the program; and then check the test results.

當我們已經依照計畫，使用某種測試準則執行過軟體測試之後，是否表示接著就可以讓軟體直接出貨呢？有時候我們可能還不放心。這時候另一種軟體測試－突變測試－就上場了。突變測試背後的想法，是創造出一定數量的突變程式，其中每一支只有很少的改變，然後將原來的測試案例，對這些突變程式一一執行，然後檢驗測試結果。

Check the Testing Results

If there exists at least one test case in the test suite for which a mutant gives an incorrect result, then the mutant is said to be dead or ‘killed’. If a mutant remains alive even after all test cases have been exhausted, the test suite is enhanced to kill the mutant. The process of generation and killing of mutants can be automated by predefining a set of primitive changes that can be applied to the program.

如果在測試的過程中，存在至少一個測試案例，使得某支突變程式產生不正確的結果，則這支突變程式就被宣告死亡(dead)或被殺死(killed)。如果所有測試案例都執行過了，而某支突變程式仍然活著，就意味著原先的測試案例還需要更加強。由於突變測試產生大量的程式及資料，實務上除非將上述流程自動化，否則很難實行。

Mutation Testing Operators

The primitive changes can be altering an arithmetic operator, changing the value of a constant, adding or removing a constant, altering a relational operator, and changing a data type, etc. 突變程式是由突變運算所製造出來。常見的突變運算有：改變某個算數運算；改變某個常數值；增加或移除一個常數；改變某個關聯運算，以及改變某個資料的型別等等。 突變測試並不常見，其主要問題是儘管突變測試可以被自動化，但是它是需要非常大量計算的，並且需要產生非常大量可能的突變程式，使得實行上變的非常困難。

Problems in Mutation Testing

Although mutation testing can be automated, the major problem of mutation testing still exists, which is it is very computationally expensive, and There are a very large number of possible mutants that can be generated, which makes it vary hard to be implemented