引用: S. Cha, S. Lee and H. Oh, "Template-Guided Concolic Testing via Online Learning," 2018 33rd IEEE/ACM International Conference on Automated Software Engineering (ASE), Montpellier, France, 2018, pp. 408-418, doi: 10.1145/3238147.3238227.
摘要
我們提出了模版引導的混合執行測試，這是一種在混合執行測試中有效減少搜索空間的新技術。解決路徑爆炸問題一直是混合執行測試中的一個重大挑戰。人們已經提出了多種搜索啟發式方法來緩和這個問題，但僅僅使用搜索啟發式方法還不足以大幅提高實際程序的代碼覆蓋率。本文的目標是補充現有的技術，并通過在混合執行測試中利用模板來獲得更高的覆蓋率。在我們的方法中，模板是一個部分符號化的輸入向量，其工作是減少搜索空間。然而，選擇一組正確的模板是不容易的，并且會顯著影響我們方法的最終性能。我們提出了一種算法，它可以根據從以前運行的混合執行測試收集來的數據去自動在線學習有用的模板。開源程序的實驗結果表明，我們的技術比常規的混合執行測試實現了更大的分支覆蓋率，并且更有效地發現漏洞。
一. 引言
混合執行測試是一種流行的能夠軟件測試方法，它能有效地、系統地實現高代碼覆蓋率和發現漏洞。混合執行測試的關鍵思想是同時具體化和符號化地執行程序，其中新的測試用例系統地被生成通過符號化執行被具體化執行強化。近來，混合執行測試已經被用于不同的應用領域，如操作系統、固件和二進制代碼等等。
混合執行測試中一個主要的公開挑戰是如何有效地探索搜索空間。隨著現實程序中執行路徑的數量呈指數級增長，混合執行測試必須能夠偏重和探索最有可能有利于最終測試結果的路徑。然而，有效地引導混合執行測試是不容易的。存在許多不同的以緩解路徑爆炸問題為目標的方法：例如路徑剪枝方法，搜索啟發式方法等。
在本文中，我們提出了模板引導的混合執行測試，這是一種自適應減少混合執行測試搜索空間的新技術。其關鍵思想是用模板引導混合執行測試，模板通過有選擇地生成符號變量來限制輸入空間。與常規的混合執行測試(符號化地追蹤所有的輸入值)不同的是，我們的技術將一組選定的輸入值視為符號變量，并將未選定的輸入值固定為特定的具體輸入值，從而減少了原始搜索空間。然而，我們面臨的一個挑戰是，如何選擇要符號化跟蹤的輸入值并將剩余的輸入值替換為適當的值。為了解決這個挑戰，我們開發了一種算法，它在執行混合執行測試的同時自動生成、使用和完善模板。該算法基于兩個關鍵思想。首先，通過使用序列模式挖掘，我們從一組有效的測試用例中生成候選模板，其中測試用例有助于提高代碼覆蓋率，這些測試用例在執行常規的混合執行測試時被收集。其次，我們使用了一種算法，在混合執行測試過程中從候選模板中學習有效模板。我們的算法根據前幾次測試中評估的模板的有效性對候選模版進行迭代得排名。我們的技術與現有的技術是正交的，并且可以與它們(特別是與最先進的搜索啟發式技術)進行有效的結合。
實驗結果表明，我們的方法在分支覆蓋率和漏洞查找方面優于常規的混合執行測試。我們已經在 CREST 中實現了我們的方法，并將我們的技術與中等規模的開源 C 程序(最大 165K LOC)的傳統混合執行測試進行了比較。對于所有的基準，我們的技術與常規的混合執行測試相比實現了顯著的更高的分支覆蓋率。例如，對于 vim-5.7 我們同時進行了 70 個小時的測試，我們的技術完全覆蓋了 883 個傳統混合執行測試無法覆蓋的分支。我們的技術還成功地發現了三個開源 C 程序的最新版本中可能引發的真實漏洞：sed-4.4、grep-3.1 和 gawk-4.21。
本文做出了以下貢獻。
1.我們提出了模板引導的混合執行測試。這是一種新的技術，它通過有選擇地生成符號化的值來減少輸入空間，而不需要任何事先的領域知識。
2.我們提出了一種在線學習算法，以從以前的混合執行測試的運行中選擇有用的模板。
3.我們廣泛地比較了我們的技術和作用在常規的開源 C 程序上的混合執行測試。我們開源了我們的工具(稱為 ConTest)和數據。
二．概述
在本節中，我們用一個例子來說明我們的方法。
2.1 啟發性舉例
圖 1 展示了一個簡化自 tree-1.6.0 的代碼片段，其中我們假設 strncmp 的主體不可用。函數 f 接收兩個字符數組作為輸入，命名為輸入 1 和輸入 2，其中每個數組的長度為 4。程序的執行由這些數組的內容決定。在第 5 行，如果輸入 1 的前兩個字符是'-'和'X'，Xflag 被設置為 1。在第 9 行，如果輸入 2 包含字符串"--du"，則 duflag 被設置為 1。因此，當函數在以下輸入下執行時，可以到達錯誤位置(第 12 行)。
其中 ∗ 表示一個任意字符。混合執行測試的目標是產生這樣的輸入以驅動程序執行能夠運行到錯誤位置。
但是，由于搜索空間巨大，常規的混合執行測試不太可能觸發錯誤。為了到達錯誤位置，程序執行必須成功執行第 5 行和第 9 行。為此，混合執行測試最初用隨機輸入運行程序，同時用符號輸入執行程序。
在執行過程中，符號變量(α1, ... , α8)的約束條件被收集起來，并用于生成下一個輸入。例如，當初始執行按照第 4 行的條件語句為真的分支和第 7、11 行的條件語句為假的分支去執行時，以下的約束條件會被收集。
例如，否定最后一個連接條件，將產生使程序執行到第 7 行的第一個條件語句為真的分支的輸入。然后，假設新的輸入不滿足第 7 行的第二個條件，將新生成以下路徑條件。
再次否定最后一個連接的條件，混合執行測試成功到達第 8 行條件語句之前的程序位置。但在這個點，它仍然需要探索一個巨大的搜索空間來生成滿足條件(!strncmp(...))的輸入：因為 strncmp 的主體不可用，符號變量 α7 和 α8 是不受限制的。因此，最后兩個字符'du'一定是被偶然的生成且生成概率太低，鑒于從程序入口到第 8 行已經存在多條(更確切的來說，9 條)。
我們的模板引導的混合執行測試旨在有效和自動地減少搜索空間。在混合執行測試過程中，我們的技術會自適應地生成模板，這些模版通過有選擇地引入符號變量從而被用來限制輸入空間。例如，當它被應用到圖 1 中的程序中時，我們的技術會自動生成以下模板來限制搜索空間。
也就是說，除了最后兩個輸入值之外，所有的輸入值都由具體的值固定下來，這樣，混合執行測試就不再無謂地試圖探索無法到達第 8 行的那些執行路徑。換句話說，我們的技術能夠強制執行到達錯誤位置的必要條件，使得混合執行測試能夠專注于分別生成 α7 和 α8 的輸入'd'和'u'。通過該模板，混合執行測試能夠更有效地生成能夠觸發錯誤的輸入，比傳統方法在示例程序中的速度快 9 倍。
2.2 模板引導下的在線學習混合執行測試
圖 2 說明了我們的技術在用于執行混合執行測試同時在線自動生成模板。我們的技術能夠在不需要任何事先的領域知識的情況下生成有效的模板。該算法重復以下五個過程，直到給定的測試預算用完。
2.2.1 常規的混合執行測試。我們首先執行常規的混合執行測試(無模板)，以生成一組有效的測試用例。如果一個測試用例能夠在混合執行測試過程中行使之前未覆蓋到的分支，我們就說它是有效的。我們在一定時間內運行混合執行測試，收集有效的測試用例。例如，當我們對圖 1 中的示例程序運行幾分鐘的混合執行測試時，我們可以收集到超過 40000 個有效的測試用例，例如以下的測試用例：
2.2.2 序列模式挖掘。一旦收集到有效測試用例的數據集，我們就會嘗試捕捉這些輸入向量中的共同模式。具體來說，我們的目標是提取有效測試用例中經常出現的部分字符序列。為此我們使用了一種最新的序列模式挖掘算法，它從上一階段收集到的 40000 個測試用例中找出以下四種模式：
例如，模式 P1 表示有效測試用例很可能依次包含字符'-'、'X'、'-'。
2.2.3 模式排序。在通過序列模式挖掘生成候選模式后，我們選擇最有可能最大化獨特分支覆蓋范圍的前 k 種模式；該覆蓋范圍的計算方法是常規的混合執行測試沒有發現的分支數量。在我們的例子中為了快速覆蓋獨特分支（例如圖 1 中第 8 行的判斷為真的分支），需要使用圖 2 中的模式 P3。然而，在候選者中精確定位有效模式是不容易的，因為在現實程序上運行算法通常會發現成千上萬的模式。更糟糕的是，只有一小部分候選模式對增加分支覆蓋范圍是有效的。我們通過根據之前運行中評估的類似模式的有效性對候選模式進行排名來解決這一挑戰。我們在算法過程中積累了一些好的和壞的模式集合，利用它們來估計新生成的模式的有效性。對于示例程序，當 k=2 時，我們選擇 P3 和 P2 這兩種候選模式。
2.2.4 模式到模板。下一個步驟是將模式轉化為模板。請注意，模式只是一個有意義的輸入值（如字符）的有序序列；要變為模板，我們需要決定給定模式中包含的每個值的位置。為此我們首先收集包含了模式的測試用例，然后確定模板值出現頻率最高的位置。例如，假設具體值'X'在測試用例中的第二個索引處出現得最多。那么，我們將輸入 2 中第二個索引處的符號值 α2 替換為具體值'X'。通過將這一規則應用于前一階段選擇的模式 P3 和 P2，我們得到以下兩個模板：
在本文的其他部分，我們也用一組具體值及它們的位置來表示一個模板。例如，第一個模板可以表示如下：
2.2.5 帶模版的混合執行測試。最后一步是用生成的模板(T1 和 T2)進行混合執行測試。例如，當使用模板 T1 時我們只生成四個符號值(α3, α4, α7, α8)，其余的用模板 T1 中的具體值代替。需要注意的是，這些具體的值并不是任意的，而是通過強制程序執行沿著特定的路徑(取第 4 行和第 7 行條件語句判斷為真的所有分支)從而有效地引導混合執行測試到達錯誤發生的地點(如圖 1 中第 11 行判斷為真的分支)。
在對模板進行了一段時間的混合執行測試后，我們用覆蓋到的獨特分支的數量來評估生成模板的質量。作為結果，我們將圖 2 中相應的模式分為好模式和壞模式，這種反饋將被排名算法在下一次算法迭代中使用。在整個過程中，我們的算法會積累評價數據并因此排名算法能夠根據這些增加的知識挑選出更有效的模式。
三．在線學習的模板指導下的混合執行測試
在本節中，我們介紹了我們的算法(算法 2)，用于執行模板引導下的混合執行測試，同時在線自動生成有效模板。算法 2 由四個主要階段組成：常規的混合執行測試、序列模式挖掘、排名和模板引導的混合執行測試。在第 2 行，算法從初始化數據開始。集合 B 和 TB 分別代表傳統的混合執行測試和模板引導的混合執行測試所覆蓋的分支。集合 Good 和 Bad 分別表示有效和無效的輸入模式。
該算法有三個超參數(η1、η2 和 η3)。第一個參數 η1 在第 6 行被使用，決定第一階段的常規的混合執行的執行次數。第二個參數 η2 在第 23 行被使用，表示每個模板的混合執行的執行次數。最后一個參數 η3 表示模式 p 成為好模式(即被包含在集合 Good 中)的閾值。在實驗中，我們設置 η1=100，η2=20，η3=20。在這項工作中，我們通過試錯對這些超參數進行了手動調整并發現算法 2 的性能很大程度上取決于這些參數。未來一個有趣的方向是在算法過程中自動尋找最優超參數。
