江苏龙网

  1. 主页 > 生活百科 > >

通过在线学习进行模版引导的混合执行测试

模版引导


通过在线学习进行模版引导的混合执行测试

文章插图
 
引用: 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 行) 。


推荐阅读


上一篇：梦见掉了一颗上牙一颗下牙 梦见自己掉了一颗尖牙齿

下一篇：淘宝鞋子女靴子款 淘宝鞋子女款