Subdomain-Based Generality-Aware Debloating

@inproceedings{xin2020subdomain,
  title={Subdomain-based generality-aware debloating},
  author={Xin, Qi and Kim, Myeongsoo and Zhang, Qirun and Orso, Alessandro},
  booktitle={Proceedings of the 35th IEEE/ACM International Conference on Automated Software Engineering},
  pages={224--236},
  year={2020}
}

0 摘要

• 程序膨胀降低性能和安全

• 为了突破基于输入的方法过拟合输入集的限制,我们提出了 DOMGAD ,有两个主要优点超过现有方法

  • 1. 其生成的简化程序保证在子域上工作,而不是输入
  • 2. 使用随机优化简化程序,以在简化和通用性(即简化程序能够正确处理整个域中输入的程度)上实现权衡

• 在ChiselBench上评估,50%的代码减少和95%的通用性,高于目前两种SOTA

1 介绍

• DOMGAD两个优点

  • 1. 生成的简化程序保证在子域上工作,而不是输入;
    • 即DomGad生成的程序对属于这些子域的每一个输入都能正确运行;
    • 对不属于当前子域的输入都会禁止运行防止异常行为; 与此相对基于输入的方法仅能保证在特定输入下正确运行,因此阻止异常行为的唯一方法是阻止未知输入的执行
  • 2. DOMGAD不仅考虑了简化,也考虑了在通用性上的权衡

• 我们的方法中,使用路径 $\pi$ 来符号化 程序 $P$ 的子域,使用符号 $\mathcal{D}(\pi)$ 来指示所有属于该子域的输入.

• 为了正确运行子域内所有输入,DOMGAD保守地保留 运行运行路径上的代码

• DOMGAD的目标是生成一个可以处理子域的简化程序,并实现简化和通用之间的权衡. 即,假设输入在程序中均匀分布,我们的方法生成尽可能小的程序同时处理子域内尽可能多的输入

• 为了实现这一目标,我们将简化为顶定义为一个优化为题,定义一个目标函数,量化 reduction 和 generality,并使用随机优化算法来解决它

• 量化通用性很难,我们提出了一种基于关键洞察的实际技术，即可以对程序域的底层输入分布进行建模并利用基于采样的方法

  • 具体来说,DOMGAD
    • 1. 从输入分布中抽取样本,来识别出一组有限的路径集合 $\prod$ ,这些路径集合覆盖了程序域的大部分输入
    • 2. 基于导致该路径的采样输入数量,估计每个路径 $\pi \in \prod$ 相对应的子域大小. 尽管我们的采样方法只能计算通用性的近似值,但可以通过计算,界定解的误差. 因此通过足够的样本,我们的方法误差将会非常小

• 我们总的简化过程如下

  • 输入程序 $P$ , 一个输入采样器 $IS$ , 该采样器模拟 $P$ 域中的输入分布 并生成输入样本,给定这些输入,DOMGAD进行三个主要步骤: (1) 路径识别 (2)路径量化 (3) 随机优化
  • 1. 路径识别:DOMGAD调用 $IS$ 生成输入样本,并识别出一组路径 $\prod$ ,这些路径覆盖了程序域的大部分输入
  • 2. 路径量化:DOMGAD再次调用 $IS$ 生成额外的样本用于估计每个路径 $\pi \in \prod$ 相对应的子域大小. 基于这些估计,DOMGAD计算每个生成的简化程序的通用性. 在这一步中,同时也比较 reduction 和工具面
  • 3. 随机优化:DOMGAD使用MCMC随机优化算法,来实现生成 通用性和简化之间的权衡

• 使用ChiselBench评估DOMGAD,与Chisel和DEBOP进行比较.

• 本文主要贡献如下

  • 1. 一个新的,基于子域的,注重通用性的简化技术DOMGAD, 使用随机优化算法来生成简化程序来达到简化和通用性之间的权衡
  • 2. 通过实验评估展示我们技术的效果,并证实了进行注重泛化的简化是可行的
  • 3. 提供了DOMGAD的原型实现,并开源

2 示例

3 初步定义

4 我们的方法:DOMGAD

5 评估

6 相关工作

程序简化

• DOMGAD与一系列[22,41,45,55,57] 依赖 使用配置文件的简化技术相关

  • TRIMMER [55] 通过激进的编译器优化实现简化
  • OOCAM [38] 通过部分估值实现简化
  • C-Reduce[45],Perses[57],CHISEL[22] 是基于delta-debugging的简化技术
  • J-Reduce[20] 使用依赖信息来改进delta-debugging
  • RAZOR [41] 采用基于代码覆盖,推理,和二进制重写的简化方法

• 与上述技术不同

  • DOMGAD是基于子域的,而不是具体的输入
  • DOMGAD不是单纯的简化导向,而是在简化和通用性之间进行权衡

• DEBOP[61] 是我们之前提出的方法,但其是基于输入的,并且在语句级别操作,而不是路径级别.如我们结果显示,这对其简化和效率产生了影响

• DomGad也和一些基于静态分析来删除死代码或未使用代码的技术相关[1, 24, 26, 27, 29, 42],以及对应特别程序(例如 容器[44] 或 web应用[3]),或特殊目的(例如安全检测[15]) 而执行简化的技术有关

• 更广泛地硕,DOMGAD和膨胀检测[4,62,63],识别不必要代码[21],以及通过程序切片识别感兴趣代码的技术有关[60]

模型计数和概率分析

• 因为DOMGAD使用静态采样方法,因此其与 模型技术有关[2,7,32],这些技术旨在量化满足给定公式的模型数量
• 处于类似原因,其也与概率软件分析[5,16,51] 有关,这些技术旨在量化程序的概率行为
• 与统计模型检验技术[35]有关,该技术通过验证统计方法验证概率事件的属性

MCMC和优化

• DOMGAD使用基于MCMC的,以此其和使用MCMC解决其它问题的技术间接有关,如优化[52]、漏洞查找[8,33]基于模型的GUI测试[56]和程序混淆[36]。最后，DomGad与资源适应[12]、能量减少[53]、程序修复[34]以及更广泛的软件改进[40]的优化技术有松散的关联。

7 结论和未来工作

• 结论
  • 现有基于输入的方法容易过拟合输入,且只考虑简化
  • 我们提出了一种新的,基于子域的,注重通用性的简化技术DOMGAD, 使用随机优化算法,来生成简化程序来达到简化和通用性之间的权衡,通过一个综合这两个相互冲突度量的目标函数执行随机优化
  • 结果显示我们的技术可以生成显著的代码减少（平均50%），同时保持高泛化性（平均95%）
  • 与SOTA比较,DOMGAD表现良好
• 未来工作
  • 1. 扩展我们的评估
    • (1) 使用 DOMGAD 应用于更广泛的程序集,来评估我们现在的结果是否具有普遍性
    • (2) 进行用户研究,评估现实环境中通用性的价值
  • 2. 探究提升路径识别和量化 效率的新方法
    • 具体而言,将考虑 分层抽样[47],顺序抽样[58] 等方法
    • 以及研究基于共享输入样本 ,同时执行路径识别和量化的可能性
  • 3. 考虑其它随机方法
    • 例如 Gibbs Sampling[17],来改进优化结果
  • 4. 研究推断程序输入分布的方法
    • 可能基于使用配置文件,自动构建输入样本生成器.为此,可以考虑基于 概率程序合成[39],概率密度估计[59],分布估计[30]和深度生成模型[43, 46]的方法。