論文：Wang, X.Y., Wu, H.R., Sun, W.S., & Zhao, Y. (2019). “Towards Generating Cost-Effective Test Suite for Ethereum Smart Contract”, Proceedings of the 2019 International Conference on Software Analysis, Evolution and Reengineering (SANER), pp.549-553

論文摘要：

在以太坊中，許多賬戶和基金都是由智能合約管理的，因此很容易成為攻擊者的目標。同時由於區塊鏈的不可修改性，修改已部署的智能合約幾乎是不可能的。這兩個因素提高了管理資金的風險，從而增加了對以太坊智能合約（ESC）進行有效測試的需求。與傳統的軟件不同，ESC是由燃氣（gas）驅動的程序，部署和測試都需要消耗gas。因此，提供一個既具有成本效益又有代表性的測試套件十分重要，這裡的代表性通常可以通過分支覆蓋率來衡量。在本文中，我們將ESC測試生成問題視為帕累託最小化問題，並考慮了三個目標：最小化（1）未覆蓋的分支率，（2）時間成本和（3）gas成本。然後，我們提出了一種基於隨機的和一種基於NSGA-II的多目標方法來尋找具有成本效益的測試套件。我們對八個廣泛使用的以太坊去中心化應用（DAPP）中的一組智能合約進行了實證研究，驗證了所提出的方法可以顯著降低gas成本和時間成本，同時保留其分支覆蓋的能力。

技術介紹：

通常，要想完成一次成功的測試，就必須為被測智能合約設計和生成高質量的測試套件。那麼，如何衡量測試套件的質量？對於傳統軟件，行業測試標準通常要求用分支覆蓋率來評估生成的測試用例的質量。分支覆蓋率越高，被測試的程序塊就越多。因此，最小化未覆蓋的分支成為測試套件生成中的一個重要目標。減少未覆蓋分支的一種自然方法是通過為未覆蓋分支生成額外的測試輸入來增加現有的測試套件。然而，生成更多的測試輸入表明測試人員必須花費更多的時間來執行被測試的程序。此外，當調用ESC時，它將在以太坊中的每個節點中運行，大量的調用會造成擁堵並降低以太坊的性能。在這方面，以太坊採用gas機制來限制執行時間和內存消耗[1]，即執行一個已部署的ESC，需要用以太幣購買足夠的gas。毫無疑問，對智能合約進行有效的測試將消耗大量的gas。因此，生成的測試套件也應該具有成本效益，即儘可能少地花費時間和gas。

如前所述，高質量的ESC測試套件必須滿足以下三個目標：（1）最小化未覆蓋的分支，（2）最小化時間成本，和（3）最小化gas成本。顯然，目標(1)和（2）以及（1）和（3）衝突，這意味著確定一個能夠在每個目標中都實現最佳結果的解決方案是不現實的。因此，ESC測試生成可以看作是一個多目標優化問題，其目的是通過生成帕累託解來在多個目標之間取得平衡[2]。在本文中，我們提出了第一個針對以太坊智能合約的多目標測試生成方法。具體來說，我們採用兩種算法來尋找經濟有效的測試套件，即基於隨機的多目標測試生成算法（RBM）和基於NSGA-II的多目標測試生成算法（NBM）。具體內容如下：

A. 基於隨機的多目標測試生成（RBM）

對於一個智能合約，RBM需要：（1）其源代碼；（2）其應用程序二進制接口（ABI）；（3）創建測試套件的時間預算；以及（4）解決方案的數量。如圖2所示，首先隨機生成一系列解，再對其進行非支配排序，最後選擇帕累托最優集作為輸出[2]。解決方案是一組隨機生成的測試用例，其中每個用例對應於ABI中的一個方法聲明。生成所有解決方案後，我們會評估它們的分支覆蓋率、時間成本和氣體成本，所有這些都是通過跟蹤部署的ESC上的測試案例收集的。

B. 基於NSGA-II的多目標測試生成（NBM）

NSGA-II是一種具有代表性的多目標遺傳算法[3]。我們重新設計瞭解決方案的表示以及進化運算符（即選擇、重組和突變），以便將NSGA-II應用到ESC測試套件生成中。首先從隨機群體

開始進行進化，直到滿足終止條件（即迭代次數）。在每次迭代中，通過選擇和進化（即交叉和突變）最後一代中最好的m個個體來創建子代群體Q_t。接著將P_t和Q_t同時加入到新一代群體R_t中，然後對R

我們使用了5個常用以太坊去中心化應用作為實驗對象。我們使用完全隨機的方法（CRB）和兩種單目標的方法（RBS和NBS）來比較我們的方法。CRB對應於完全基於隨機的測試生成，在測試生成過程中不考慮任何目標。RBS和NBS以最低未覆蓋分支率為優化目標，分別對應於基於隨機和基於NSGA-II的方法。我們之所以選擇這些對比實驗，是因為如果我們在目標之間做出微妙的權衡，它們就可以重新反映出來。

表2展示了我們的實驗結果。從表中可以看出，基於NSGA-II的方法總是比基於隨機的方法有更好的分支覆蓋率，而完全隨機的方法CRB總是表現最差的。RBM和NBM的平均分均略高於單目標方法RBS和NBS的平均分，分別為0.90%和0.89%，這表明我們的方法能夠保留分支覆蓋的能力。此外，我們還可以觀察到，我們的方法的執行時間以及gas消耗總是小於三種對比方法的執行時間。例如，NBM的平均gas成本為147萬，這遠低於對比方法生成的測試套件的gas成本。這意味著在實證研究中，我們的方法可以產生更具成本效益的測試套件。

本文的主要貢獻：

（1）我們第一次在ESC測試中引入了帕累託最小化方法，結合了用於傳統軟件的一個目標（即最小化未覆蓋的分支）和兩個具有成本效益的目標（即最小化時間成本和氣體成本）。

（2）我們實現了我們的方法並對一組去中心化應用進行了實證研究。結果證實，我們的方法可以顯著降低氣體和時間成本，同時保持覆蓋分支能力。

[1] G. Wood, “Ethereum: A secure decentralised generalised transaction ledger,” Ethereum Project Yellow Paper, pp. 1–32, 2014.

[2] N. Srinivas et al., “Multiobjective function optimization using nondomi-nated sorting genetic algorithms,” IEEE TEC, vol. 2, no. 3, pp. 221–248, 1995.

[3] K. Deb et al., “A fast and elitist multiobjective genetic algorithm: NSGA-II,” IEEE TEC, vol. 6, no. 2, pp. 182–197, 2002.

致謝

本文由南京大學軟件學院2018級碩士巫浩然翻譯轉述

閱讀更多 慕測科技 的文章

關鍵字: 設計 算法 智能