这篇论文是来自RUB-SysSec小组在Usenix Security 2020 的关于分析crash的论文。之前看过他们组在ASCAC上发的PrimGen，感觉安全圈真小。
该工具已经开源，见网址：https://github.com/RUB-SysSec/aurora

简介

软件测试的自动化技术在实践中发现了很多crash。分析这些crash的根源是很耗时的。为了解决这个问题，学术界提出了各种方法来解决，比如逆向执行，后向污点分析。然而，这些方法局限于特定的错误种类，或者只给分析人员提供汇编指令，而没有上下文信息或者关于错误的解释。

这篇文章提出了一种自动化分析的方法，不仅能识别导致二进制可执行文件崩溃的crash的根源，而且能提供程序错误行为的上下文信息。从一个崩溃输入出发，我们生成相类似的输入，可能会使得程序崩溃，或者不崩溃。然后当执行我们找到的输入和产生predicate时，追踪程序的状态。然后对predicate进行数据分析，定位到根源。

作者基于以上思想做了一个工具叫AURORA，并且在25个不同的软件错误上进行评估。评估结果表明AURORA能够对复杂漏洞分析。相比于现有的方法，AURORA能够应对在crash和root cause之间无数据依赖的漏洞，比如类型混淆漏洞。

背景

模糊测试是一个很强大的软件测试技术，尤其是在近些年，在学术界和工业界取得了不错的成绩。本质上，模糊测试是生成各种各样的输入到目标程序中，并且尽可能地覆盖不同的路径。最近的新的模糊测试方法为软件系统产生了很多的crash，有时导致开发者没有时间去处理它们。许多情况下，找到一个新的导致崩溃的输入是很容易，并且纯自动化的工作。然而分析crash是一个手动，耗时耗力的工作。主要是麻烦在追踪crash的根源。实际情况更为糟糕，一个bug就可能导致多个crash输入。这就导致分析员需要去挖掘发现许多潜在的漏洞。也就导致开发者没有时间去修复已知bug。
为了减少许多crash映射到同一个bug，分析员尝试对这些输入进行分组。也就是按照某种指标，比如覆盖率或者调用栈的hash，来把崩溃的输入分类。理论上来说，分析每一类的一个bug就够了。然而，最近的实验表明普通的分类方案存在2个问题：

• 产生了太多的分类
• 分类分得不够准确
  即使只有一部分的输入要去分析，分析员也不知道为什么给定的输入会导致崩溃。通常，真正导致crash的根本原因不是崩溃那个点，有可能在更加前面的地方。因此分析员就需要去分析从崩溃发生的地方往前去找到root cause，而这需要很多精力。

比如说，有一个类型混淆的bug，一个指针指向一个A类型的对象，然后用的时候却指向了一个B类型对象。如果B对象的域被访问了，就会导致A的子模块非法访问。如果两个结构不兼容的话，就会导致内存损坏。在这个例子中，崩溃的位置很有可能不是falut的root cause处。论文认为这个bug的根源在于生成一个从A类型到B类型的值的那个控制流。

传统的方法，一个分析员用调试器去查看栈和寄存器的值。从crash开始，手动地去后向追踪到root cause。使用先进的sanitizer比如ASAN，可以检测到离root cause很近的内存非法访问。而在我们的例子中，手动分析需要从crashing的位置开始，而ASAN只会检测到什么位置发生内存损坏。分析员仍然需要手动地去识别类型混淆是root cause。而这是一个复杂的工作，因为大部分的代码都是正常的。

其他工作POMP，RETRACER，REPT和DEEPVSA使用自动逆向执行和后向污点分析。这些工作在crash无法复现的时候是有用的。REPT和RETRACER通过结合core dumps和intel的PT trace来分析发生在端设备的crash。如果没有直接的数据依赖关系连接root cause和崩溃的指令，这些方法并不能自动地分析root cause。REPT和RETRACER更侧重于为分析员提供一个在crash之前的交互式调试环境。

难点

方法

给定一个崩溃的输入和二进制程序，目标是去输出软件错误的root cause的一个解释。核心思想是通过崩溃和不崩溃输入的行为差异来确定的root cause。
因此，我们首先创建一个多样化的程序行为的数据集，然后监控相关的输入行为，最后比较地分析他们。用这种方式的出发点在于崩溃的输入必须在某种程度上，语义上与不崩溃的输入不同。直觉上来说，在程序执行过程中第一个偏离不崩溃的输入的行为就是root cause。
在第一步，我们创建两个相关但不同输入的集合，一个是crashing input ， 另一个是non-crashing input。理想上，我们只包含由同一个root cause导致的crashing input。non-crashing input的集合没有这个限制。为了获取这些集合，我们使用crash exploration fuzzing在一个初始的crashing input上实现（seed）。

给定两个集合的输入，我们观察和监控（trace）程序的行为。这些追踪允许我们去关联观察的不同和执行的输出。使用数据推断，我们可以预测程序是否会崩溃。为了进一步格式化不同之处，我们生成了predicate来说明是否触发了bug。理论上来说，第一个predicate就能成功预测所有执行的结果，也能解释root cause。最终，我们为分析员提供一个列表的相关解释和地址，以他们预测的价值排序和执行时间排序。也就是，我们更喜欢预测结果好的解释。在所有好的解释里，我们更喜欢哪些能够尽快预测crash的。

总的来说，这篇论文的方法分为三个点：
（1） 输入多样化，来生成两个不同的输入集合
（2）监控输入的行为，来追踪这些输入是怎么表现的
（3）生成解释，生成描述性的predicate来区分crashing input 和non-crashing input

实现

主要分为三个部分的实现：

• Input Diversification：基于AFL 2.52b修改。
• Monitoring Input Behavior：基于PIN 3.7 修改
• Explanation Synthesis：基于Rust语言编写，代码量为5000行，同时还用到了binutils addr2line。

结果

实验结果主要回答以下三个问题：

• AURORA能否识别和解释复杂和可利用bug的root cause，比如类型混淆，UAF和堆溢出？
• 自动识别的解释和开发者弄的补丁之间有多接近？
• 有多少predicate是与fault相关？（其实也是在说，这个aurora工具生成结果好不好用，容不容易找到crash的root cause）

论文选取了25个比较常见的数据，从中选取了各种类型的漏洞来做实验。说明主要实验结果是这个表1（重点放第一个）。

说明一下漏洞有多复杂。

对假阳性的分析。

追踪的成功率。

追踪需要的时间。

相关工作

基于范围的错误定位

这类基于范围的错误定位主要是指基于代码覆盖率的错误定位技术。换句话说，这类工作主要是定位导致bug的程序元素，比如，单一语句，基本块，函数。

相关论文：

• The inflection point hypothesis: a principled debugging approach for locating the root cause of a failure
• A practical evaluation of spectrumbased fault localization
• Localizing software faults simultaneously
• Empirical evaluation of the tarantula automatic fault-localization technique.
• Isolating suspiciousness from spectrum-based fault localization techniques
• A general noise-reduction framework for fault localization of Java programs
• Scalable statistical bug isolation
• Statistical debugging using compound boolean predicates.
• SOBER: statistical model-based bug localization.

逆向执行

有大量的工作去分析crash，尤其是使用core dump的。为了实现这点，通过逆向执行程序，重构导致crash的数据流。为了实现这个，CREDAL使用程序源码信息去自动地分析core dump，从而辅助分析人员发现内存损坏类漏洞。为了进一步减少人工劳动力，POMP利用控制流追踪和crash dump这些信息，并使用后向污点分析来逆向生成数据流，识别出对crash有贡献的语句。与之相似的一个工作，不过是在OS级别，RETRACER使用后向污点分析（没有使用追踪）来在栈上重构对bug有贡献的函数。Cui等人在RETRACER做了改进，开发了一个REPT，一个逆向的debugger，引入了错误纠正机制来重构执行理事。从而能够恢复导致crash的数据流。为了克服不准确性，Guo等人提出了深度学习的值集分析来解决内存别名问题。

相关论文：

• CREDAL: towards locating a memory corruption vulnerability with your core dump.
• REPT: Reverse debugging of failures in deployed software.
• RETracer: Triaging crashes by reverse execution from partial memory dumps.
• DEEPVSA: Facilitating value-set analysis with deep learning for postmortem program analysis
• POMP++: Facilitating postmortem program diagnosis with value-set analysis
• Postmortem program analysis with hardware-enhanced post-crash artifacts

讨论

实验结果显示，我们的方法可以识别和解释root cause，甚至是root cause和crashing 没有直接关系的情况。然而，这个方法也不是银弹。仍然会报告一些predicate是与root cause无关的情况。这是由于crash exploration的数据量不够的情况。这实际上也是基于语法的fuzzer的一个问题，即AFL的突变种类不足以为目标产生足够的不同输入。作者期望更好的fuzzing技术出现去生成更合适的语料。不管fuzzer有多好，定位root cause的自动化方法仍然是一个复杂的目标，即使一个人类专家，也经常不能识别一个bug的根源。
依赖模糊测试还有一个问题，bugs在模糊测试setup时是可以复现的。因此，该方法不能分析分布式或者高度关联的bug。然而，这个是fuzzer的问题，不是aurora的问题。aurora的优势在于其数据模型可以很好地移植到别的复杂的系统，比如network，database。而传统的分析技术，比如污点追踪是不行的。

某些情况下，我们生成的predicate是不够准确的。比如，有可能存在一个使用未初始化值的bug，要触发需要满足两个特定条件：程序一开始不经过初始化值的路径，然后经过访问了那个值的路径。（听的怪绕的，本质上就是一个单一位置的predicate没法表示基于两个位置的bug行为。）这里的问题感觉和另外一篇文章讲数据流攻击的BOPC的很像。也是因为粒度问题所导致的。

最后，系统需要一定时间去识别和解释root cause。某些情况下，Aurora运行时间高达17小时（12h在crash exploration）。作者认为这不是问题，因为我们的系统是和传统的fuzzing的结合。因此，在测试setup阶段的额外的17h的fuzzing几乎不会导致很严重的开销。

总结

这篇文章主要是提出了一种针对二进制程序的自动分析崩溃原因的系统。研究的意义是帮助分析员定位crash，从而修复漏洞。因为现在模糊测试工具产生的crash太多了，而且很多crash都是指向同一个漏洞。这个工作的很多局限性都在于fuzzer自身的问题。另外，这个工作只是辅助开发者去定位漏洞，还是需要开发者去手工分析一下。
论文写作上也有很多可以借鉴的。文章的写作思路也有很多值得学习的地方。实验怎么设计的也可以再细看一下。总的来说，是篇不错的文章~（要是多点图就好了）