Motwani M, Brun Y. Automatically generating precise Oracles from structured natural language specifications[C]//2019 IEEE/ACM 41st International Conference on Software Engineering (ICSE’19). IEEE, 2019: 188-199.
2. 摘要
系統規範通常使用自然語言來描述預期行為，但是通常很難自動地驗證這些規範。本文介紹了 Swami，一種自動提取測試預言並根據結構化自然語言規範生成可執行測試的技術。Swami 專注於異常行為和邊界條件，它們通常會導致程序故障，而開發人員需要為此手動編寫測試。相關實驗表明 Swami 生成的測試 98.4％符合正式的 JavaScript 規範。使用 Swami 擴充開發人員編寫的測試用例可以明顯提高覆蓋率表現。此外，Swami 還能夠識別出 Rhino 中的 1 個先前未知的錯誤和 15 個 JavaScript 功能的缺失、能夠識別出 Node.js 中的一個 1 個先前未知錯誤，以及 ECMA-262 規範中的 18 中語義歧義。
3 引言
軟件工程的主要挑戰之一是驗證軟件是否可以完成人們想要的工作。然而人類最常見的描述和指定軟件的方式是自然語言，這種語言很難形式化，因此也難以在自動化過程中用作該軟件的預言。
本文解決了“如何根據自然語言規範自動生成測試以驗證軟件是否執行了規範要求”的問題。測試包括兩部分，一個是觸發行為的輸入，另一個是表示預期行為的預言。預言主要對意圖進行編碼，並且傳統上是手動指定的，這既費時又容易出錯。很少有計算機自動使用的正式規範，同時開發人員大多編寫自然語言規範，這些規範通常是結構化的，作為軟件需求規範文檔的一部分。例如，圖 1 顯示了 JavaScript 的 Array(len) 構造函數的結構化自然語言規範。本文着重於從這種結構化的自然語言規範中生成預言，測試輸入通常可以隨機生成，並與預言一起生成可執行的測試用例。
圖 1 Array (len) 構造函數規範
尤其是針對異常行為和邊界條件，開發人員通常花費大量時間手動編寫測試。在對十個流行的，且具有良好測試的開源項目的研究中，我們發現異常處理語句的覆蓋率明顯低於整體語句覆蓋率。例如開發人員經常針對常見行為編寫測試，而忘記考慮特殊值或邊界情況。IBM 的一項研究發現，多達三分之二的代碼專門用於處理異常行為。而且，由於異常處理機制需要預見程序所有可能出現的問題，因此異常行為通常更為複雜也更容易出錯，在出現故障時通常難以恢復。同時異常行為通常會引起現場故障，因此需要進行高質量的測試。
本文介紹了 Swami，這是一種根據自然語言規範自動生成可執行測試的技術。我們將工作重點放在異常行為和邊界行為上，這些行為也恰恰是開發人員經常忽視的重要領域方
Swami 使用正則表達式來識別結構化自然語言規範，鎖定其中可以編碼為測試行為的部分。同時如果可以獲得源代碼，Swami 也可以使用信息檢索技術來識別這些部分。Swami 使用基於正則表達式的一系列規則來提取有關要需要被測試的方法的語法信息，即相關的變量賦值等。同時 Swami 根據可見行為語句回溯，以根據規範`遞歸地填充變量值賦值，從而生成一個預言的測試模板，並由測試輸入對其進行參數化。Swami 然後生成隨機的，啓發式驅動的測試輸入以生成可執行的測試。
在之前為迴歸測試或人工編寫的預言自動生成測試工作基礎上，我們通過自動的從自然語言規範提取測試預言對其進行了擴展。Swami 的實現和其他可復現數據可以在項目網站（http://swami.cs.umass.edu/）中獲得。
5. 方法概述
本節將詳細介紹了 Swami 方法的具體流程，如圖 1 所示。Swami 對規範進行歸一化與詞類標記，標識相關規範中關聯部分，使用基於正則表達式的規則創建測試模板，並通過基於啓發式的隨機輸入生成實例化測試。
5.1 規範預處理
Swami 使用標準的自然語言處理技術將規範轉換為可解析的格式。Swami 通過刪除標點符號，大小寫摺疊和標記術語來規範化文本。然後 Swami 刪除停用詞，並阻止文本合併單詞變體以改進詞語匹配。Swami 使用 Indri 工具來刪除停用詞並阻止詞幹，同時使用 Standford coreNLP 工具包來標記語音部分。
圖 1 Swami 流程
5.2 標識可測試部分
Swami 使用兩種方法決定從規範的哪一部分生成測試。對於許多結構化的規範（例如 ECMA-262），描述方法的各節均標有方法名稱。對於此類規範，Swami 使用正則表達式來調用“段標識”來標識相關段。Swami 的正則表達式識別會丟棄空格和方括號，並查找數字標籤，然後可選地查找帶有“new”關鍵字、方法名、左括號、參數（標記為“NN”）、以及右括號。
5.3 提取測試模板
為了生成測試模板，Swami 對相關的規範節使用基於規則的自然語言處理。Swami 具體使用 4 種規則：模板初始化，分配標識，條件標識和條件翻譯。每個規則首先使用一個正則表達式來決定該句子是否由該規則處理。如果需要處理，則該規則使用其他正則表達式來提取顯着信息，例如方法名稱，參數名稱，賦值，條件謂詞等。當句子與規則不匹配時，它們將被下面的規則處理並丟棄。只有符合所有四個規則的句子才能生成測試模板
5.4 生成可執行測試
Swami 通過啓發式驅動的隨機輸入生成技術實例化測試模板。ECMA-262 描述了五種基本數據類型：布爾，空，未定義，數字和字符串，以及兩種非基本數據類型：符號和對象。Swami 使用對象的五種基本數據類型和幾種子類型（數組，映射，日期時間，正則表達式等）。對布爾類型，Swami 生成 true 和 false；對空類型，生成 null；對未定位類型，生成 undefined；對數字類型，生成隨機整數和浮點數值。Swami 同時使用以下特殊取值：NaN、-0、+0、Infinity 和-Infinity。對對象子類型，Swami 使用以下幾種啓發式生成數組，正則表達式等。例如當生成一個數組時，Swami 保證生成合法長度的參數（一個介於 1 到 2^32 的整數），非法長度將拋出 RangeError 異常。最後，Swami 通過開發人員在規範中使用的抽象操作實現來擴充測試用例集。
6 實驗評估
我們使用兩種經典的 JavaScript 實現來評估 Swami：Rhino（Java）和 Node.js（C++）。我們主要從下面四個方面進行分析。因此在理想情況下，Swami 會對一部分規範進行高精度測試。
6.1 測試精度評估
本小節主要回答 Swami 生成的測試精度表現如何。Swami 主要針對異常行為和邊界條件生成測試，因此我們不希望對大多數普通的規範進行測試。
我們將 Swami 應用於 ECMA-262（v8）為 JavaScript 生成黑盒測試用例。Swami 為 98 種方法生成了測試模板，但是其中 15 個測試模板無法編譯，剩餘 83 個可編譯模板。我們手動檢查了這 83 個測試模板，並將它們與自然語言規範進行了比較，以確保它們正確地捕獲了規範的預言。然後，我們使用 1,000 個隨機生成的測試輸入實例化每個模板，創建 83,000 個測試。我們這這些測試模板進行插樁，以幫助我們將 83,000 個測試分為三類：（1）正確對規範進行編碼並會捕獲某些不正確實現的良好測試；（2）對規範進行不正確編碼並可能在正確實現時失敗的不良測試，（3）通過所有實現的無關測試。在 83,000 個測試中，有 32,379 個（39.0％）測試為良好測試，有 535 個（0.6％）為不良測試，而 500,086 個（60.3％）是無關的。
6.2 人工測試補充評估
本小節主要回答 Swami 生成的測試是否能夠發現開發人員手動編寫的測試遺漏的行為。Rhino 中開發者手動編寫的測試用例集的總體語句覆蓋率為 71％，分支覆蓋率為 66％。Swami 為 12 種 Rhino 方法中手動測試用例忽略的行為進行了測試，這些方法的語句覆蓋率平均提高了 15.2％，分支覆蓋率提高了 19.3％。對於 Node.js，開發人員編寫的測試用例集已經具有很高的覆蓋率，Swami 並未增加 Node.js 語句和分支覆蓋率。但是，覆蓋率是對測試用例集質量的近似評估，事實上 Swami 在兩個項目中都發現了缺陷。
Swami 生成的測試中發現了 Rhino 中 1 個以前未知的缺陷和 15 個缺少的 JavaScript 功能，1 個 Node.js 中的未知的缺陷以及 ECMA-262 規範中的 18 個語義歧義。Rhino 問題追蹤器包含 2 個開放功能請求（但沒有測試），對應於 Rhino 中 15 個缺失功能中的 12 個。我們已提交了有關新缺陷的錯誤報告，以及針對現有請求未涵蓋的 3 個功能的請求報告。
6.3 自動測試補充評估
本小節主要回答 Swami 生成的測試是否能夠發現自動測試生成工具遺漏的行為。隨機測試生成工具，例如 EvoSuit 和 Randoop 可以通過兩種方式生成測試：使用代碼中的顯式斷言（通常是手動編寫），或作為迴歸測試。因此，Swami 本質上是不同的，它從規範中提取預言以捕獲那些規範中編碼的意圖。儘管如此，我們仍想比較 Swami 和 EvoSuite 生成的測試，因為我們預計它們將互相補充。
我們使用 EvoSuite 以 5 分鐘的時間限制和行覆蓋率作為測試標準為 Rhino 生成了五個獨立的測試用例集，一共為 Rhino 實現的 251 個類生成了 16,760 個測試。其中有 392（2.3％）個測試失是失敗的。這一發現與先前對異常行為的自動測試生成的研究一致。相比之下，Swami 生成的無關測試只佔 1.6％，所有測試中只有 0.6％是錯誤警報。我們發現 Swami 的性能明顯優於 EvoSuite，因為它可以從規範中提取預言。
7 總結與展望
本文中我們介紹了 Swami，基於正則表達式從結構化自然語言規格中為邊界值和異常行為自動生成預言和測試。儘管正則表達式較為僵硬，但 Swami 在實踐中表現出色。Swami 是第一個處理與 ECMA262 JavaScript 標準相同複雜的規範的相關技術。我們的評估實驗表明 Swami 在測試生成方面是有效的，可以對開發人員手動編寫和 EvoSuite 生成測試的測試進行補充，並且在成熟，開發完善的軟件中發現新的故障。