Skip to content

根因分析

什么是根因分析？ 根因分析(Root Cause Analysis)或者说缺陷定位(Fault Localization)是程序开发人员或安全分析人员在确认程序存在异常行为后，通过手动或自动的方法来定位异常行为的根本原因的过程。根因分析是程序安全分析流程中比较重要的一环。

为什么需要设计一些根因分析方法？ 在当下各类自动化漏洞挖掘工具(比如各类fuzzer)的辅助下，每日发现的bug数量已经远超开发人员确认并修复的数量。设计一种自动化发现漏洞的工具并不难，难在如何根据这些工具报出的crash信息来准确地分析出漏洞的根本原因。对于大型程序而言，崩溃测试样例(crashing testcase)执行下来可能经历了几百万条汇编指令，手工确认稍微有点不现实了。因此需要设计一些(自动化)的根因分析工具。

怎么进行根因分析？目前有哪些工作？ 最朴素而直观的思想就是消耗安全分析人员的精力，从程序的入口点(entry)或者崩溃点(crash site)出发，看看程序是怎么执行的，哪些元素(program entity)会导致最后的crash，然后再进行对应的修复。根据定位元素的粒度不同，根因分析可以定位到函数级(function level)、语句级(statement level)、汇编指令级(instruction level)。由于在汇编指令上进行分析可以更普适地适应多种编程语言、不需要获取源码，所以下文的讨论都是围绕汇编指令级展开。

目前一些自动化根因分析研究思路有：

  1. 基于程序谱的分析方法(Spectrum-based)。大概思路是不需要考虑汇编指令的语义信息，利用一些统计学的方法来分析哪些指令有问题。这类方法基于这样一个场景：假设我们有一大批相似的测试样例，其中有些会导致程序崩溃，有些不会，那么这两类测试样例的执行路径可能有不同的偏好。那么那些更倾向于在崩溃测试样例中执行的指令更有可能是root cause。
  2. 事后分析方法(Postmortem-based)。直译尸检分析，形象理解为从程序崩溃后留下的“尸体”开始分析。它假定程序崩溃后会产生一个coredump(核心转储)文件，包含了崩溃点的内存快照(memory snapshot)，以及这个测试样例的执行路径(execution trace)。前者用于提供数据流信息(比如内存值、寄存器值)，后者用于提供控制流信息(汇编指令执行与跳转)。在此基础上，结合一些逆向执行(reverse execution)和后向污点分析(backward taint analysis)的方法，定位可能的root cause。
  3. 基于模型的分析方法(Model-based)。这一类方法是近些年提出的，它通过定义语义相关的模型，利用机器学习或深度学习的思想，找到语义上导致崩溃的root cause。

这些研究思路都解决了什么问题？有什么独特的优点？存在哪些独有的不足？ 基于程序谱的分析方法直观上似乎有点道理。它仅考虑汇编指令本身，而但仅仅从统计结果上去分析，可能并不能准确分析出逻辑上的root cause。这类方法一般会设计一种排名策略(ranking)，对选择出的可疑指令进行top1-topn的排名，来试图提高准确性。这类方法一般需要根据一个崩溃样例以及和它相似的崩溃样例和非崩溃样例进行分析，因此时空开销都比较大。

事后分析方法相比程序谱分析方法考虑了指令语义，比如在逆向执行的时候会设计一些汇编指令handler，对于内存的分析也会更精确些。但污点分析方法毕竟存在过度污染(over-tainting)的问题，导致结果冗余比较严重。

基于模型的分析方法利用AI的优势，可以给出更有语义信息的root cause，在一定程度上帮助开发人员去分析。不过模型的训练依赖训练集的质量，并且受程序语义影响很大。在不同领域之间可能迁移性不是很好，比如没法处理一些特定的密码学函数。且为待测程序建立模型来描述其结构与行为是非常复杂、耗时的事情

现有的这些方法有没有什么普遍存在的问题？ 在最后评估阶段(evaluation)，一般先通过手工分析确定哪些汇编指令，如果方法输出的汇编指令集合里包含这些指令，那么就认为是发现了root cause。但自动化方法毕竟缺少人工参与，给出的结果一定是不准确的。现有的工作的一个主流思想在于“方法给出的集合可以包含无关指令，但不能缺少相关指令”，旨在提高召回率(recall)。因此往往给出与root cause不相关的指令。但实际上，在最后的修复端，如果给出不相关指令过多，那么仍然需要开发者去分析，依旧耗时耗力。

据ISSTA 2016一篇调研（Practitioners’ expectations on automated fault localization），9.43%希望root cause在分析结果的Top1，73.58%容许在Top5，15.09%容许在Top10。所以约98%的情况下需要在Top10内给出结果。就分析准确度与开发人员满意度而言，如果RCA工具准确度达90%，满意度几乎达到100%了。准确度低于20%时只有12%接受，如果满意度达50%、75%、90%，准确度需要分别达到50%、75%、85%（但是原文说90%）。

目前的绝大部分RCA分析的工作的输出是两类：ranked list和suspicious set。但两者都存在的问题是仅仅高亮了可能存在bug的元素，而缺乏一些rational的分析。

不同的分析粒度的优势

基于文件粒度的RCA工作（比如Scaffle）希望找到包含百万级同质代码库中哪些文件和crash有关。在此基础上让对应的工程师团队去处理bug，有利于大型组织管理。

据ISSTA 2016一篇调研（Practitioners’ expectations on automated fault localization），开发者对粒度的top3期望依次是方法级别、语句级别、基本块级别，不过对这三种粒度的倾向之间没有明显差异。而当时比较多的方法是语句级别的

分析时间开销

根据采用的策略不同，RCA之间的时间开销差异可能达两个数量级。（秒级-分钟级-小时级）。

据ISSTA 2016一篇调研（Practitioners’ expectations on automated fault localization），90%开发者接受1min以内的分析，不到9%开发者接受超过1h的分析。50%开发者大概在30min以内。

一些想法

  1. 什么是漏洞的根本原因？假如函数A内创建临时变量x并调用函数B(x)，在B内引发crash，那么应该归咎为A没有处理x呢，还是B没有检查x呢？这是API实现的问题，还是API误用的问题？(开发者or用户)
  2. 对于某一个crash，如果开发人员进行了修复，那么这个修复能拿来当root cause吗？不同开发人员修复的风格可能不一样，修复也未必是完全的，root cause就是一个主观的问题了。

相关论文的一些发现（疑问）

  • “传统的SFL方法效果在Defects4J等部分数据集可能远优于DLFL方法，可能是基准实验的过拟合问题。”传统方法的过拟合指的是什么？DLFL为什么在基准测试集取得和别的数据集一样好的效果？传统方法在不同测试集的表现差异是方法的问题还是测试集的问题？（A Universal Data Augmentation Approach for Fault Localization, ICSE 2022）
  • 不同种类的FL方法在时间开销上数量级是不同的。测试的时候如果集成上较低数量级开销的方法，不会对运行时间有很大影响，但可以提升效率。不同种类FL方法相关性不高，可以考虑结合使用。（An Empirical Study of Fault Localization Families and Their Combinations, TSE 2021）
  • 调用栈做FL分析时，如果根因在栈上的话，40%是第一个栈帧，90%在前10个栈帧里。（Do stack traces help developers fix bugs? Mining Softw. Repositories, 2010）

参考文献

  • Scaffle: Bug Localization on Millions of Files, ISSTA 2020
  • Probabilistic reasoning in diagnosing causes of program failures, STVR 2016
  • Practitioners’ expectations on automated fault localization, ISSTA 2016

以上内容仅代表个人观点，不定期更新，欢迎讨论