SyML: Guiding Symbolic Execution Toward Vulnerable States Through Pattern Learning

RAID 2021

背景

在二进制程序里探索很多的执行路径对于发现新的漏洞是很重要的。动态符号执行能够触发复杂的输入条件，并且能够精确地探索程序，同时提供crash的可复现性和语义信息。然而，要扩展这种分析方式到复杂的二进制程序里是很困难的。目前的方法有很严重的路径爆炸问题。尽管现在有很多方式提出来解决这个问题，但现阶段这个挑战仍然很难解决，并且通过这种技术发现的漏洞都很少。

这篇文章的工作重心就是尝试去解决符号执行的路径爆炸问题。

方法

数据集（放实验讲吧）

选择CGC数据集，包含232个漏洞程序，其中有超过400个漏洞输入能够触发各种漏洞。然而，由于DSE引擎的问题，有些漏洞无法分析。最后就只剩下包含120多个漏洞的75个二进制可以用。

作者还列举了选测试集的一些标准，包含volume、variety、consistency、complexity、confidence这些指标。

整体框架

整体可以分为特征提取、数据清洗、训练模型、导向符号执行这几个部分。

特征提取

特征提取包含三个步骤：

具体追踪
- 用会崩溃的输入在QEMU里运行漏洞二进制，收集导致crash的trace。
静态分析
- 收集全局的静态信息，包括CFG等，来支持后续的分析
动态符号追踪
- 然后沿着记录的trace去符号执行

提取的特征如下：

数据清洗

去除缺失值、异常值、离群值和重复值

训练模型

采用四个指标来评估分类模型：

F1-score：
准确率
trace覆盖率
判分时间

导向符号执行

由于预测不一定准确，并且搜索空间很大，因此需要使用一些策略来最大化利用状态预测的结果。

探索策略如下：

性能考量

初始开销。为了避免在探索阶段引入额外开销，这里提前从上下文信息里计算某些特征来作为初始开销，比如connectivity，centrality，function_size，function complexity，components information，community partition这些。
特征数目。特征数目太多会导致计算开销增加或者模型准确率降低。因此，使用information gain来手动检查所有的特征，确保他们都是相关的特征。

结果

模型准确度和特征评估。

选择了几个常见的机器学习模型来进行训练。所有的模型都是调用scikit-learn来实现的。下面的数据都是使用交叉验证来验证的，在每次验证回合，将一个二进制取出来，然后其他的二进制用来训练，得到F1，准确率等指标。下面的表格基本说明他提的特征是没啥问题的。

实际上他的特征也不是一次就提取正确的。这个结果应该是他把系统调用等一些特征移出去得到的结果。最后考虑模型下面的指标，选择了XGBoost作为模型来预测状态。

和现有工作做对比

作者将自己的工作和现有的先进路径选择策略做了对比。这些策略包含KLEE Coverage（2008），KLEE Random（2008），AEG Loop Exhaustion（2011）。感觉都挺老的，说明现在没有什么更先进的路径选择策略。

从结果来看，作者的方法更加通用，能测试更多的有漏洞的二进制。但也不是所有的都能跑通。有的时间上也比传统的启发式方法要更慢。

作者也整理了一下时间维度的对比。随着时间的增加，作者的方法能跑出更多的crash。在相同时间内能跑出的crash的数量和其他传统方法差不多。另外，这种路径选择方式更加通用，不局限于特定的漏洞种类。

score 分析

有点不太清楚这个score是什么，是如何计算的？

在探索时分析syml的score的分布情况，期望在探索到漏洞时候分数增加，反之则减小。作者发现这里分数分布和漏洞发现的模式很相同。在刚开始，分数很不稳定，也偏低。分数在崩溃点之后会进入一个谷底，然后又是一段平稳期。随后，分数又变高了，意味着程序在离崩溃点很近的位置或者其他有趣的地方开始探索了。

应用到真实程序里

作者将方法应用到三个真实的linux二进制里，asp2php，o3read，ringtonetools。这三个程序代码量都不大，万行左右的代码量级。

在真实程序里测试的结果不是很理想。数据都偏低。因此，作者将CGC上训练好的模型和linux程序一起学习，性能得到了一定的提升。但还是属于一个比较偏低的水平。

横坐标表示程序执行的情况。0表示刚从程序开始运行，100表示运行到漏洞点了。

讨论

作者认为这是第一个机器学习方法应用到符号执行引擎里的分支选择里。刚好今年的CCS 2021年也出了一篇类似的，通过提取分支的特征，来训练机器学习模型，从而进一步去指导符号执行。

最大的缺陷就是在真实的linux程序上的效果很差。Learning to Explore Paths for Symbolic Execution

结论

将符号执行里的分支选择问题，当作是二分类问题来看待。

利用现有的PoC的trace，沿着trace进行符号执行来收集特征信息，训练好模型，利用训练好的模型来选择状态。

相比启发式规则，更加通用。能够挖掘漏洞的类型取决于训练的数据集。

研究方法看起来相对复杂。但理清了思路感觉还是比较有创新性的。

如果能够应用到更多的真实程序里，应该能够发顶会。

其他：

RAID 属于安全领域的四小顶会。也算是个水平比较高的会议了。

讲这篇B会是想让大家感受下B会的论文的水平是怎么样的。

总的来说，B会的论文，可能实验效果在真实程序上不理想，但至少实验是相对来说比较完整的。各个小实验里能够支撑论文的点，并且都有些很有意思的发现。

iskindar的博客

【论文笔记】SyML, Guiding Symbolic Execution Toward Vulnerable States Through Pattern Learning