5.1.4 启发式引导的k+1循环处理模型
受到选择性符号执行技术的启发,本书将一个循环结构抽象成为一段独立代码,对循环结构进行分类并采用不同的策略来处理,定义了目标函数,利用目标函数的信息来引导具体执行的路径选择过程。这两种策略结合在一起为程序中指定的覆盖目标生成测试用例和可达路径。
1.循环分类
当程序中包含循环结构时,其对应的控制流图是一个有向有环图。循环结构表示为L=(E L,N L,in L,out L),in L和out L分别是循环的入口节点和出口节点。给定一个程序元素t作为覆盖目标,程序中的循环结构可以根据与t的相对位置分为3类:目标之前的循环L before、包含目标的循环L target、目标之后的循环L after。
定义5-1 循环L=(E L,N L,in L,out L)是L target:当且仅当t∈N。
此定义同样适用于嵌套循环结构,若目标t位于内层的循环,则其外层的循环结构也是L target。L target的定义描述了循环结构L和目标t之间的静态相对位置,与此相对,L before和L after是根据路径搜索过程中的节点序列动态确定的。
定义5-2 当以某种策略遍历控制流图时遇到了不包含目标t的循环结构L,若已得到的轨迹中包含覆盖目标t,则L是L after,否则L是L before。
图5-2为不同程序结构的循环分类示意图。白色的节点代表循环结构的入口节点和出口节点,灰色的节点代表覆盖目标t,虚线表示在节点之间存在路径。
图5-2 循环结构的分类示意图
在实际的程序中,循环结构往往会组合出现,根据不同的组合情况,可以将程序中包含的循环结构总体分为3类[6]:简单循环、嵌套循环、串联循环。3类循环结构的控制流图如图5-3所示。
当程序中包含串联或者嵌套的循环结构时,对于复杂循环的分类方法如下。
(1)串联循环
串联循环指的是有两个或多个循环串联组成的循环结构,目标元素可能位于其中某一个循环中。以图5-3中的串联循环为例,当目标元素位于第一个循环体中时,第一个循环是L target,第二个循环相对于目标元素来说是L after。
当目标元素位于第二个循环体时,第一个循环是L before,第二个循环是L target。
(2)嵌套循环
嵌套循环中的循环结构相对于目标元素,有两种可能的情况:目标元素位于最内层循环内、目标函数位于外层循环内,如图5-4所示。
当目标元素位于最内层循环内时,这两个循环都是L target;当目标元素位于外层循环内时,最内层循环不包含目标元素,此时外层循环是L target,若路径搜索过程遇到内层循环时尚未覆盖到目标元素,内层循环不包含目标元素,内层循环是L before;当搜索过程到达内层循环时已经得到了包含目标元素的路径,此时内层循环是L after。
图5-3 循环结构的分类
(https://www.daowen.com)
图5-4 两种嵌套循环的情况
2.基于循环分类的选择性循环路径生成策略
在选择性符号执行中,用户根据所关注的代码来选择进行全路径搜索(符号执行)和单路径搜索(具体执行)的范围。根据对于循环结构的分类,此处基于以下考虑给出不同循环结构的路径搜索策略。
①L target:目标t在L target中,L target与目标具有直接的关联关系,因此在L target中使用符号执行技术搜索可达路径,为了防止路径爆炸,将展开上限设置为k。得到包含目标的路径之后进行1次动态执行得到剩余部分的路径,称为L target内的k+1模型。
②L before:循环结构中的程序路径数量可能是无穷多的,因此展开每一个循环搜索每一条路径变得不现实。由于L before对于可达路径的影响可能十分复杂,以至于无法判定是否必须进入L before以得到最终的可达路径,因此在L before中利用具体执行来获得一条可达路径。当路径搜索过程中遇到L before时,首先生成一个满足前置条件的测试用例,利用此测试用例进行具体执行,截取执行的轨迹中L before的部分作为子路径继续进行路径搜索。
③L after:当搜索过程遇到L after时,意味着已经得到了包含目标t的部分路径,此时利用这条部分路径的约束生成测试用例,以此用例进行动态执行就能够得到完整的包含t的路径。
④程序的剩余部分利用符号执行进行全路径搜索。
3.包含目标的循环内的k+1模型
对于包含目标的循环结构,采用符号执行在L target的所有程序路径中搜索可达路径,假设循环体中的路径数目为m,迭代次数限定为k,循环内有一个目标覆盖元素,包含目标覆盖元素的子路径为目标子路径,以“m=4,k=3”为例进行说明(设子路径分别为P1、P2、P3和P4,目标子路径为P1),循环的控制流图如图5-5所示。
图5-5 循环示意图(k+1模型)
根据上面的讨论,循环结构会导致程序的路径数量爆炸,若对循环结构进行完全展开,则需要对指数级的搜索树进行遍历。为了减少在循环内部进行路径生成所花费的代价,我们给出一种动静结合的k+1循环处理模型,即静态展开循环k次,得到一条循环内的部分可达路径,利用这条可达路径所对应的测试用例,进行1次动态执行,得到循环内的完整路径。其整体流程如图5-6所示。
图5-6 动静结合的k+1模型的整体流程
4.启发式引导的具体执行过程
选择性符号执行的一个主要缺陷就是其具体执行的步骤是随机挑选一个满足前置约束条件的用例并执行。这个用例能够保证具体执行轨迹与已得到的部分路径一致,但是在接下来的程序中随机执行,因此很难保证到达目标。路径生成过程是在程序的输入空间中找到能够覆盖到目标的解的过程,因此可以将路径生成过程看作一个搜索算法。为了引导具体执行部分选择生成更接近目标的路径,本书在具体执行过程中引入目标函数对得到的子路径进行评价和排序。
在利用搜索算法求解优化问题的过程中,需要先对解决的问题建模得到目标函数,利用目标函数和搜索策略来找到满足目标函数的解,目标函数对每一次得到的解进行评价,引导搜索向搜索空间中更有可能产生解的方向进行。
本书定义节点和路径之间的距离作为目标函数。
定义5-3 令节点n是CFG上不同于目标t的节点,节点距离d t(n)指的是在CFG上n到t的最短路径的长度。节点n和路径p之间的路径距离[7]d t(p)是所有p上的节点n 1,n 2,…∈p中与t距离最小的节点距离min{d t(n 1),d t(n 2),…}。
更小的路径距离意味着此路径接近目标点。计算路径距离d t(p)的算法分为如下两个步骤。
