这篇博客的核心内容来源于本人发表于软件工程顶级会议ICSE2018并获得“ACM SIGSOFT Distinguished Paper Award”的同名论文，在后面的内容中，若未做特殊说明，本文将使用以下抽象语法树作为例子：
研究问题
- 给定程序的最优动态符号执行测试策略是什么？
- 能不能有效的得到最优策略?
- 现有算法是否很好的逼近最优策略?
- 是否能设计一个可用算法来逼近最优策略?
- 如果4的回答是肯定的，那么该算法与现有算法的相比如何?
程序抽象
- 程序是带标签的转移系统P=(C,init,V,φ,T)
- C是控制节点的有限集合
- init ∈ C是唯一入口
- V是变量的有限集合
- φ是捕获V初始取值集合的断言
- T : C × GC → C是转移函数
- P的一条程序路径就是一个转移序列π = ⟨(c1, gc1, c2), (c2, gc2, c3), · · · , (ck, gck, ck+1)⟩
马尔可夫链抽象
本文将使用马尔可夫决策过程来求解最优策略，首先需要形式化的说明P能够转换为对应的马尔可夫链，由于这是显而易见的，所以这里对原作中相关定义不做翻译，截图如下：
最优策略
问题可以被定义为：
- 测试用例生成方法的搜索空间是{𝑅𝑇}∪{𝑆𝐸(P)|P ∈ 𝑝𝑎𝑡ℎ(𝑃)}
- 一个策略是一个测试用例生成方法的序列<t1, t2, t3, …>
- 使用测试用例生成方法t的代价是cost(t)
- 找到达到100%覆盖率并具有最小总代价的策略
这里通过举例来说明最优策略的选择，首先作如下假设：
- 随机测试的cost是1
- 求解n边路径的代价为10n
那么有就会有以下策略：
- 完全随机测试：期望cost: 5*(2^32)/4 = 5368709120
- 完全符号执行：对<1,2,3,4>和<1,3,5,6,7,8>执行符号执行，相关Cost：30+50=80
- 最优策略：对<1,2>和<1,3,5,6>执行符号执行，其余执行随机测试，相关Cost：10+30+5=45
注意：随机测试的期望数目决定于具有最小到达概率的节点!
事实上，寻找最优策略的问题可以简化为基于带代价的马尔可夫决策过程的模型检测问题，比如说下面这个极其简单的程序的相关抽象：
其抽象语法树为：
相对应的马尔可夫决策过程为：
显然，根据带代价的马尔可夫决策过程可以很轻松地回答研究问题1和2：
- 最优策略是具有最小期望成本的策略
- 其求解复杂性随着P中的控制节点数量指数级增长
模拟实验
该部分实验主要是为了验证现有算法（相关算法的理论可以参考前一篇)的性能，实验基于随机生成的马尔可夫链，而非现有程序，实验设置如下：
- 随机生成抽象表示程序的DTMC模型（分支密度50%；低概率分支密度0.2（10，15，20），0.8（5），低概率程度1.0E-4）
- 随机生成表示每条分支符号执行代价的cost（不超过1000）
- 每种情况有50个模型，每个方法运行1000次
相应的实验结果如下：
| 5 states | 10 states | 15 states | 20 states | |
|---|---|---|---|---|
| Optimal | 1 | 1 | 1 | 1 |
| RT | 138.9 | 11.3 | 44.2 | 114.7 |
| RCN | 1.7 | 14.4 | 15.1 | 12.7 |
| RSS | 12.8 | 50.7 | 64.0 | 68.1 |
| RPS | 12.8 | 50.6 | 63.9 | 68.5 |
| DFS | 7.1 | 27.4 | 21.8 | 18.6 |
| DART | 1.8 | 13.0 | 12.8 | 13.0 |
| GS | 1.9 | 13.5 | 13.9 | 13.3 |
| CGS | 1.8 | 12.6 | 13.6 | 13.8 |
| SGS | 11.2 | 32.4 | 29.4 | 25.5 |
说明：这里RCN对应前文中的Coverage-Optimized Search
显然，现在可以回答研究问题3：现有算法还有很大的改进空间
贪婪算法
算法的核心想法为根据单位时间(cost)所能覆盖的期望节点数(reward)选择局部最优策略和路径
离散时间马尔可夫链估计
使用拉普拉斯估计方法来估计离散时间马尔可夫链
- 如果在P中从s到t是不可能的，置Pr(s, t)=0
- 否则，置Pr(s,t) = (#(s, t)+1) / (#s+n)
举例说明：
cost估计
使用函数拟合来估计cost：
- 假设cost是基础操作的加权和
- 根据收集的cost来估计权值
- 给定一个约束，利用其所有基础操作的加权和来估计cost
举例说明： 约束c是a * b > 0，所以SC(c) = WC(*) + WC(>)
算法
首先，根据实证研究做如下假设：
- 求解一个线性（不）等式及其结合的cost是4
- 求解一个非线性（不）等式的cost是10
- 求解一个非线性（不）等式的布尔组合的cost是50
具体相关步骤如下：
- 根据下图公式计算每个节点的reward
比如对于下面这种情况：
可以获得以下方程组：
- 𝑅1 = 1/3*𝑅2+2/3*𝑅3
- 𝑅2 = 1+𝑅3
- 𝑅3 = 1/3*𝑅4+2/3*𝑅5
- 𝑅4 = 1
- 𝑅5 = 1/3*𝑅6+2/3*𝑅8
- 𝑅6 = 1+1/2*𝑅7+1/2*𝑅8
- 𝑅7 = 1+𝑅8
- 𝑅8 = 0
相应的部分解为： - 𝑅1 = 1
- 𝑅2 = 5/3
- 𝑅4 = 1
- 𝑅6 = 1.5
- 随机测试的期望收益：∑𝑠∈𝑆 {𝜇(𝑠)×𝑅𝑠}
- 随机测试：cost 1, reward 1
-
选择只有结束节点未被覆盖的路径
- SE(π)的期望收益：𝑅𝑠，如果last(π)是s
- 路径<1, 2>：cost 4, reward 5/3
- 路径<1, 3, 4>：cost 50, reward 1
- 路径<1, 3, 5, 6>：cost 50, reward 3/2
-
选择其中最大的reward/cost
- 更新离散时间马尔可夫链
模拟实验结果
该部分实验仍使用上文中提到的模拟马尔可夫链，结果如下：
| 5 states | 10 states | 15 states | 20 states | |
|---|---|---|---|---|
| Optimal | 1 | 1 | 1 | 1 |
| G | 2.1 | 4.8 | 3.1 | 4.8 |
显然，现在可以回答研究问题4：这里提出的贪婪算法更接近最优策略
KLEE实验
该部分实验针对的是实际程序，而非之前的模拟马尔可夫链，实验设置如下：
- 测试平台：KLEE
- 测试对象：GNU科学库中的程序集
- 测试目标：测量不同策略实现的覆盖率随时间的变化
实验结果如下:
| 时间 | G | RCN | RSS | RPS | DFS | RT |
|---|---|---|---|---|---|---|
| 5 min (%) | 72.6 | 28.1 | 22.5 | 29.7 | 17.9 | 65.5 |
| 15 min (%) | 73.9 | 30.1 | 24.3 | 34.3 | 21.0 | 72.7 |
| 30 min (%) | 76.9 | 32.6 | 25.0 | 36.5 | 22.3 | 74.0 |
更直观的折线图如下：
以及对于每个程序，实际执行的SE以及RT的次数统计如下：
贡献
- 定义了基于程序行为概率抽象的最优动态符号执行测试策略
- 将确定最优策略的问题简化为基于带代价的马尔可夫决策过程的模型检测问题
- 使用模拟实验验证了现有算法并揭示它们还有很大的改进空间
- 提出了一种接近最优策略的贪婪算法
未来工作
- 研究其它用于估算概率以及求解代价的方法
- 把该框架扩展到其它的测试用例生成方法中（注意到有人工智能系统分析与测试方向的论文引用了本文）
