HyDiff: Hybrid Differential Software Analysis
# Remarks
Conference: ICSE 2020
Full Paper: https://yannicnoller.github.io/publications/icse2020_noller_hydiff.pdf
Artifact: https://github.com/yannicnoller/hydiff
# Summary
(+) Sigenifcance: The authors address three important problems that are detecting regression bugs, analyzing side-channels and evaluating robustness in DNN.
(+) Novelty: The authors present that all three problems can be seen as instances of differential software analysis. The presented approach integrates and extends two testing techniques: Feedback-directed grey-box fuzzing and symbolic execution. With regard to fuzzing, HyDiff leverages several fitness functions to maximize the divergence across multiple program executions. With regard to symbolic execution, HyDiff leverages four-way forking in an incremental manner and introduces novel heuristics to maximize divergence.
(+) Soundness: Experiments are conducted on all three applications for differential fuzzing, differential symbolic execution, and their combination, averaged over 30 runs. For Side-Channel Analysis, HyDiff was compared against Diffuzz. For robustness analysis of DNNs, HyDiff was performed on neural networks taken from the MNIST dataset.
# Introduction
Q: 什么是差分软件分析？
A: 差分软件分析有两种情况。一种情况是分析同一程序上执行不同输入的差异，另一种情况是分析多个程序或变体上执行相同输入的差异。在这篇文章关注的是如何在程序执行过程中产生最大行为差异的输入的问题。
Q: 差分软件分析具有哪些挑战?
A: 差分软件分析需要同时执行多个程序进行推理。而且差异表现在不同的方面，例如控制流路径（决策差异）、观测输出（输出差异）和资源消耗（成本差异）方面。不同目标应用需要分析不同类型的差异。
Q: 差分软件分析有哪些应用？
A: 文中介绍了差分软件分析的三个应用：检测软件在版本更新过程中产生的回归错误；对程序进行side-channels分析；评估深度神经网络（DNNs）的鲁棒性。
- 许多现有的回归测试生成技术只关注更改版本中的受影响路径。然而，回归测试本质上要求同时对两个程序版本进行推理，以减轻错误否定的问题。
- 软件的side-channels分析旨在给定相同的公钥，生成两个秘钥，以使它们的执行产生不同的资源消耗。可观察到的内存消耗差异或执行时间的差异，可能会造成密钥的信息泄漏。例如，如果检查长度为n的密码所需的时间与n成正比，则攻击者可以通过观察执行时间来获取密码长度。
- 评估深度神经网络（DNNs）的鲁棒性的目标是生成两个仅略有不同（在不可察觉的程度上）的输入，但DNN对它们的分类不同。通过扰动而产生的对抗性样本在实际应用中可能造成重大的安全问题。例如，当在自动驾驶汽车中使用DNN分类器识别街道标志时，错误分类会损害乘客的安全。
Q: 作者提出的方法？
A: Differential Fuzzing + 符号执行
# Approach
HyDiff的整体工作流程如下图所示，该图从上到下可分为三个部分。顶端的部分：HyDiff以几个程序和一组种子文件作为输入；底端的部分：产生的测试输入按照差异进行反馈（Feedback），除了覆盖率信息（+cov），反馈信息还包括输出差异（+odiff），控制流差异（+ddiff），崩溃的行为（+crash），以及资源开销（+cdiff）；中间的部分：左侧是差分Fuzzing的工作流程，右侧是差分符号执行的工作流程。对于差分Fuzzing，HyDiff采用不同版本的程序、测试驱动程序和目标规范。对于差分符号执行，它接受带更改注释的程序、测试驱动程序和配置。对于这两种情况，它都将种子输入文件作为初始种子语料库。种子输入文件用于执行程序的初始探索。
# Illustrating Example
下图显示了一个被更改之后的程序（注释的内容说明了更改的地方）。这些更改修复了一个错误，但引入了另一个错误。具体地说，在第16行中，开发人员将右侧表达式从y+123455更改为y+123456，该表达式修复了y=-123455的零除错误，但为y=-123456引入了另一个崩溃。在第23行中，如果result>0，开发人员添加了一个条件语句result=result+1，这将更改所有结果的输出。但是，它不会直接修复或引入任何崩溃。
fuzzer组件可以很快找到差异，很快执行到14行和16行，但是要触发x = 123456 ∧ y = −123456这个条件有一定的难度，因此符号执行帮助攻克这条语句。
该例子将用fuzzer组件和符号执行组件同时运行。fuzzer组件在分别编译的两个连续版本的计算程序上执行每个生成的输入。而符号执行组件将在更改后的新版本的程序上执行。fuzzer组件需要一个驱动程序来启动，将生成的输入喂给两个连续版本的程序执行，并收集输出差异（+odiff），控制流差异（+ddiff），以及资源开销差异（+cdiff）等信息。
与fuzzer组件一样，符号执行组件也需要一个小的测试驱动程序来启动。符号执行的驱动程序读取输入，标记符号值，并执行新版本的的程序。符号执行的驱动程序如下图所示。输入被标记为符号（第12-13行），并以符号方式执行变更后的新版本程序。在trie扩展阶段，给定的具体输入被标记为符号（第5-9行），并且使用具体输入来执行更改过的新版本的程序。
在本例中，HyDiff的混合方法检测回归错误的速度比HyDiff的DSE组件本身快9倍以上。仅fuzzer组件在10分钟后超时而未检测到回归错误。HyDiff使用了这两种技术的优点，因此它可以通过利用符号执行进入更多的路径，并且通过利用fuzzer快速找到第一个输出差异。
# Evaluation
Three application:
- Detecting regression bugs in software evolution
- Analyzing side-channels in programs
- Evaluating robustness in deep neural networks
Limitation:
- There is the required manual effort to prepare a program for differential analysis
- HyDiff required more computational resources, as it uses both symbolic execution and fuzzing.