论文：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_t中的解决方案进行非支配排序。当达到最大迭代时，NBM输出帕累托最优集。图3描述了NBM的工作流程。为了使其适应我们的测试生成问题，我们需要定义交叉和变异操作符。

我们使用了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, 15.

[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级硕士巫浩然翻译转述