@inproceedings{ali2023sok,
  title={SoK: A Tale of Reduction, Security, and Correctness-Evaluating Program Debloating Paradigms and Their Compositions},
  author={Ali, Muaz and Muzammil, Muhammad and Karim, Faraz and Naeem, Ayesha and Haroon, Rukhshan and Haris, Muhammad and Nadeem, Huzaifah and Sabir, Waseem and Shaon, Fahad and Zaffar, Fareed and others},
  booktitle={European Symposium on Research in Computer Security},
  pages={229--249},
  year={2023},
  organization={Springer}
}

2. SoK: A Tale of Reduction, Security, and Correctness - Evaluating Program Debloating Paradigms and Their Compositions

0 摘要

  • 本文提出 DebloatBencha,一个可以 扩展的,可持续的 基准平台,可以比较方法间的不同
  • 然后,对现阶段的技术进行了一个全面的比较
  • 我们整合了4种不同的方法进行比较,揭漏了其中的一些隐秘
    • 基于源程序的
    • 基于编译器的中间表示
    • 基于运行时的二进制代码
    • 基于外部库的
  • 同时我们也将一些方法进行了结合,发现了一些方法组合起来的效果((e.g., Chisel-Occam, Chisel-Occam-Razor)优于单独实用的效果

1 介绍

  • 当前去膨胀方法遇到的挑战:不能合适地去评估正确性和表现,首要的原因是缺乏一个基准平台,由此简历多样化的分析工具的路径变得不清晰且代价高昂

  • 评估平台:设计DEBLOATBENCHA基准框架,来评估目标程序是C/C++ 的去膨胀方法,因为C/C++ 使用范围广且攻击面多

    • 当前平台集成了一组软件去膨胀研究,代表了四种类别:Chisel(源代码),Occam（编译器中间表示）,Razor（可执行二进制文件）和Piece-wise（外部库）
    • 当前目标程序套件包括10个来自ChiselBencha的实用程序,3个基于GUI(graphical user interface)的程序和2个面向网络的程序
    • 该平台提供易于使用的命令行接口来运行不同的去膨胀工具
    • 同时平台设计有可定制性和可扩展性

  • 评估去膨胀方法:对 继承在评估平台的4种方法进行了全面的研究,具体而言,检查了由去膨胀方法生成的二进制文件的正确性,内存使用量,磁盘大小,安全相关的代码片段,运行时间的变化,我们发现

    • 基于静态分析的方法(Occam,PECEC-WISE)通过了所有测试
    • 使用动态分析的方法(Chisel,Razor)的二进制文件随着去膨胀程度的增加失败的测试越多
    • CHisel对非核心工具程序无法产生二进制文件,RAZOR也在3个非核心工具程序无法产生二进制文件,这表明测试驱动的去膨胀器在处理GUI和网络编程的程序中存在限制
    • 此外,四个工具中有三个运行很快,可以集成到软件阶段工作流中,我们创建了首种将多个工具组合来应用到单个二进制文件的方法,根据我们实验证明,这种组合可在某些方面达到很好的效果

  • 在平台的开发和方法评估中,我们同时也修复报告了一些bug,并提出了一些改进方法

  • 我们的贡献总结

      1. 开发了一种易于扩展的框架 DebloatBenchA ,来评估去膨胀算法.为 目标程序套件(10个来自ChiselBencha的实用程序,3个基于GUI(graphical user interface)的程序和2个面向网络的程序) 创建了82个变体来进行鲁棒性测试. 在该框架中集成了4种不同类型的方法,目前正在开源中
      1. 对4种方法进行了全面的评估,发现了一些隐秘,并提出了一些改进方法
      1. 利用多个去膨胀方法的优势,提出了一种组合分析方法,经过评估显示优于单个方法

2 去膨胀算法

  • DebloatBencha支持应用级和库级别的去膨胀,因为评估内核级的去膨胀需要与 应用级和库级别 不同的机制,故暂不考虑.下表总结了各种应用程序和库级别的程序去膨胀方法

2.1 应用程序级别的去膨胀

  • 应用程序级的去膨胀器可以分为三类
    • 源代码级:包括Chisel,C-Reduce,Perses,大部分源代码级的方法使用delta调试算法的变体进行去膨胀.delta调试算法(Delta-debugging)使用一个测试集来涵盖去膨胀后程序拥有行为,但会导致过拟合.
      • 根据辛等人论文所说,Chisel在简化程度上表现最佳,因此,我们选择了Chisel作为源代码级的去膨胀器代表
    • 中间代码级:该级别工具的操作作用在LLVM位码上,使用部分求值法对代码进行缩减.
      • 例子:OCCAM算法,该算法结合部分求值和类型理论来移除不必要的代码,支持多趟跨模型分析
      • 由于OCCAM是唯一开源的支持自动化分析的工具,所以我们选择其为中间代码级别的代表
    • 二进制代码级:该级别方法依赖于执行跟踪,由选择的测试用例(RAZOR)或模糊测试(Ancile)触发
      • 例子:Razor运行二进制代码在测试用例上,然后使用 Tracer来收集运行踪迹,然后解码踪迹,用执行过的指令来构建程序的CFG(Control Flow Graph 控制流图),Ancile还需要一组测试用例来作为模糊器的种子
      • 因为Razor是开源的,所以我们选择其为二进制代码级的代表

2.2 库级别的去膨胀

  • 库级别的去膨胀器可以分为三种:
    • (1) 静态时:给定一组应用,静态去膨胀器会静态的环境下对动态链接库进行去膨胀,从而永久替代原始的库集合(e.g. Nibbler)
    • (2) 加载时:在将目标库加载到内存时对函数进行去膨胀(RIECE-WISE)
    • (3) 运行时:仅在运行时加载需要的函数(BlankIt)
  • 由于PIECE_WISE是开源的,所以我们选择其为库级别的代表

3 DebloatBencha框架的组成

  • 框架架构如上图.

    • 设计遵循了 开闭原则(Open-Close Principle),即对扩展开放,对修改关闭,以确保更好的可扩展性和可维护性
    • 基于容器的方式来构建建构以隔离不同方法使用的环境,并为每个方法构建相应容器
    • 使用基于命令行工具的管理系统(称为编排器)来构建和管理这些容器的生命周期
    • 框架中的每个输入程序都有一个相关的配置文件描述其各种元数据(例如 测试样例位置,构建信息)
    • 由于不同的程序使用不同的专有程序输入,为每个容器提供一个适配器将程序输入转换为框架自己的格式

  • 框架组成,主要有三部分:(1)输入程序(2)去膨胀工具(3)编排器和测量脚本.

    • 输入程序,编排器和测量脚本位于主机种,去膨胀工具和适配器位于容器中

去膨胀工具

  • 在框架中的每个去膨胀工具通过容器创建
  • 框架使用一个配置文件收集与一个程序相关的输入
  • 同时创建了一个脚本来解析配置文件并且为每个工具生成各自的输出,该脚本称为 适配器脚本,该脚本将工具和框架链接起来

目标程序套件

  • 从ChiselBencha中选择了10个实用程序,为了评估通用性,选择3个GUI程序和2个网络程序,作为目标程序套件
  • 为了捕捉多样性,我们为每个应用选择多样性的部署上下文. 我们将一个目标程序和其特定的部署上下文称为一个变体
  • 下表总结了完成工作负载的82个变体

测试用例

  • 测试用例的数量影响基于测试用例去膨胀工具的训练时间,因此选择高质量的测试用例来最大化覆盖同时不影响性能很重要.
  • 给定一个应用的运行配置,生成其高质量的测试用例是一个活跃的研究领域.但这个问题是一个正交问题(指与当前讨论的问题或主题无关的问题),这种自动化超出了本文的范围,因此我们使用人工创造的测试用例.
  • 在准备这些测试用例时,我们的目标是捕捉多样化行为来最大化覆盖范围

测量脚本

  • 通过以下五个指标衡量 (?哪有五个)
      1. 去膨胀后二进制文件的正确性
      1. 二进制文件大小的减少
      1. 从 gadgets 减少的角度进行安全性分析
      1. 去膨胀时间
  • 没有使用 CVE 进行安全评估，主要是因为与功能相关。消除它们更可能受到功能选择的影响，而不是工具本身。

内存gadget计数

  • PIECE-WISE 在 外部库 加载进入内存时 以 函数为单位 对其进行简化,然后我们使用gdb来寻找在内存中简化版本库中缺失的函数.在收集到信息后,我们通过用NOPS替换确实的函数体来创建一个新版本的库.最后我们使用个版本的库使用ROPgadget工具来收集ROP gadgets

4 DebloatBenchA 的实验配置

  • 集成4种去膨胀工具
  • 我们进行了两组实验，以测量独立工具和它们的组合的性能。
  • 最后，我们讨论了用于比较性能的指标。

4.1 独立模式

  • CHISEL配置:从Chisel的作者那里，我们了解到CIL [34]用于合并较早版本的Chisel中输入程序的C文件。为了成功运行Chisel，我们重新使用了来自ChiselBench的10个coreutils程序的合并C文件。对于其他5个大型程序，我们利用了其构建系统集成功能。
  • OCCAM配置:OCCAM支持很多策略来简化二进制文件,每个策略都会产生不同的简化程度,从激进到没有特征化.运行一个有效性检查的试验来找到最佳配置,我们选择 the onlyonce(最佳配置) 来衡量比较OCCAM性能
  • RAZOR配置:RAZOR的性能取决于Pathfinder模块所使用的启发式方法的选择.由于RAZOR运行的比其它程序块,我们为每种启发式方法创建了多个版本的二进制文件,从中选择正确率最高的版本进行性能分析和与其它工具的比较
  • PIECE-WISE配置:首先使用了Docker容器提供的预构建编译器和加载器.我们使用 musl-libc v1.1.15 作为我们程序套件中每个输入程序的依赖库.然后,我们使用 PIECE-WISE 的对依赖库进行简化. 为了对比,我们要创建非PIECE-WISE编译的二进制文件,我们使用PIECE-WISE仓库提供的同样的Docker容器,同时下载未经修改的LLVM和Clang以及musl-libc,并与之前PIECE-WISE使用的版本相同

4.2 组合模式

  • 因为不同方法在不同程序代码级别运行,所以可以将多种方法运用到同一个程序上,例如CHISEL在源代码级别进行简化,然后产生的二进制用RAZOR进行进一步简化,依据这一思想,我们构思了4种工具的组合来对框架的输入程序组进行简化
      1. Chisel-Occam
      1. Chisel-Occam-Razor
      1. Chisel-Razor
      1. Occam-Razor
  • 因为PIECE-WISE需要同时在源代码和二进制上进行简化,所以其只能与CHISEL进行组合,我们尝试了其组合,但效果有限
  • 对于给定的指标,我们将 组合方法的性能 和 单个工具的最优情况 进行比较

5 去膨胀器的评估

  • 研究问题
    • RQ1:去膨胀方法是否会对目标应用程序的正确性产生负面影响？
    • RQ2:在简化单个程序大小规模时各方法的效果如何?
    • RQ3:简化程序对程序 gadget相关安全性有何影响?
    • RQ4:实际中,各简化程序的使用性如何
    • RQ5:组合多个 去膨胀方法是否有进一步的提升

5.1 在10个 utilcore程序上的评估

  • RQ1:工具正确性:首先使用测试用例评估 去膨胀器的正确性,总是会高估正确性,因为测试用例可能无法覆盖全部情况

      1. 下图表示了各方法的正确度
      • 基于静态分析的方法,OCCAM和PIECE-WISE通过了全部测试用例
      • 基于动态分析的方法,CHISEL和RAZOR通过了大部分测试用例
      • OCCAM的正确性最好因为他的静态部分求职方法保守地保留了给定参数地所有功能.CHISEL表现不好因为其过度依赖于给定的测试脚本
      1. 下图表示了方法随训练数据的变化正确度的变化:可以看出随着训练数据的增多,正确性在增加

  • RQ2:大小简化程度:去膨胀一个目标应用程序就是通过在一个特定地部署环境下删除不用的代码来减小其大小,其效果体现在磁盘中二进制文件的大小,各方法表现如下图所示(图中减少百分比为正表示二进制文件变小程度)

    • CHISEL在源代码中简化,可以减少二进制代码大小,增加训练量有时会增加代码大小
    • OCCAM在中间代码中简化,可以减少二进制代码大小,由于OCCAM的部分求值方法可能会增加函数的数量,有时会增加代码大小
    • RAZOR保留原始二进制代码并使用转换后的代码扩充它
    • PIECE-WISE将表示程序控制流图的元数据添加到二进制文件中

  • RQ3:Gadget 的表现: 原始ROP gadget数量和代码大小并不是评估二进制文件漏洞的可靠指标.[14, 15]。Homescu等人[24]认为，gadget可以根据提供的功能类型进行分类，每个类别只需要一个成员即可用于特定类别的攻击。他们构造了“micro-gadgets”类别（限制为最大长度为3字节），这些gadget提供了每个类别的基础。我们报告了去bloating对ASLR-proof和Turing-complete表达能力的两个类别中的变化的影响。如下图示

    • 在两种类别中,CHISEL有着最高的减少程度
    • 在Turing-complete中,OCCAM比RAZOR有效,而在ASLR-proof中,RAZOR比OCCAM有效
    • 而PIECE-WISE在这两个类别中几乎没有减少gadget

  • RQ4:工具实用性:为了了解每种去膨胀工具潜在部署环境,我们测量了其在框架工作负载上所有变体上运行的时间,如下图示

    • CHISEL使用13000s,是其它方法的三个数量级,因为其依靠马尔可夫决策过程来找到满足所提供测试用例的最小语句子集。
    • PIECE-WISE,OCCAM,RAZOR分别为22.1,4.9,5.2 s,因为其主要依靠静态分析,因此这三种方法更容易应用到传统的优化流程种

  • 总结

    • 正确性:Chisel: 80.4%, Occam: 100%, Razor: 94.8%, Piece-Wise:100%. 基于静态分析的比基于动态分析的效果好
    • 磁盘上大小:CHISEL和OCCAM 减小大小,而RAZOR和PIECE_WISE因为扩充了原始二进制大小,造成二进制大小变大
    • Gadat表现:CHISEL表现比其它方法都好
    • 去膨胀时间:CHISEL比其它方法时间长很多(3.75h),PIECE-WISE,OCCAM,RAZOR分别为22.1,4.9,5.2 s

5.2 在5个非utilcore程序上的评估

  • RQ1:正确性:
    • 使用247个测试用例,来自5个非utilcore程序的22个变体.
    • 在容器种对目标程序进行去膨胀
    • 在主机系统中进行正确性测试(因为GUI不好在容器中)
    • 评估显示
      • 只有OCCAM和PIECE-WISE产生了正确的二进制文件可以通过所有的测试用例
      • RAZOR可以产生vlc和ngnix的正确二进制文件,而其它不行
      • CHISEL一个都不能正确产生
  • RQ2:简化性:一定程度上都增大了二进制文件的大小
  • RQ1和RQ2的表现如下图示
  • RQ3:Gadget 的表现
    • PIECE-WISE的最大平均时间是129.67s(在Graphicsmagick上),最小是13.66s(在Gvpdf上)
    • OCCAM平均最大时间是95.6s(在Graphicsmagick上),最小是1.3s(在Vlc上)
    • RAZOR最大平均时间120s
  • RQ4:工具实用性:只有OCCAM将两种类别的gadget都移除了,RAZOR还增加了Turing-complete类别的gadget,如下图示

5.3 去膨胀器组合

  • 为了更有意义的比较,尽在utilcore程序上进行比较(以为有的方法不能再非utilcore上运行)

  • 将四种方法的组合取首字母组合进行表示,如COR表示CHISEL-OCCAM-RAZOR组合运行,组合运行时需要保证最后的二进制程序能够运行

  • 组合后正确性和简化性如下图示

    • 正确性:由于CHISEL在单独测试中未通过测试用例的几率大,这些未通过的测试用例在组合测试中被去除,同时由于OCCAM通过了所有测试用例,因此作为基线
    • 简化度:
      • 单个工具的最大简化度是CHISEL减少了70.4%,而CO组合的简化度是 74.6%,COR为67.5%
    • Gadget表现:
      • 在Turing-complete ROP中 单个工具的最好情况是CHISEL,减少了36.6%,然而COR达到了38.8%,CO更是达到了50.5%
      • 在ASLR-proof ROP中,单个工具最好情况是CHISEL,减少了28.2%,而CO,CR,COR表现都更出色,分别为45.9%、40.4%和45.8%。

  • 对于CHISEL和PIECE-WISE的组合,在使用CHISEL进行去膨胀后,PIECE-WISE只能在去膨胀的10个程序中成功编译五个,且这些程序中,grep,date和tar三个程序的变体无法被PIECE_WISE编译.这是因为musl-libc和glibc不兼容导致的,CHISEL使用的glibc而PIECE-WISE使用的musl-libc

  • 组合总结

    • 正确性:对于非Chisel流水线，它能够生成正确的二进制文件
    • 大小:CO组合由于单个方法
    • Gadget:CO,COR组合均优于单个Chisel

6 讨论

6.1 设计选择的影响

  • CHISEL在测试用例上的依赖:
    • 我们的评估揭示了CHISEL在二进制文件上的正确性最弱,这是因为CHISEL对测试脚本有着很强的依赖.同时这些脚本也很难保证是对的,即使脚本正确,CHISEL也可能出现问题.
    • 在我们的实验中,平均有超过96%的去膨胀的时间是用在了运行属性测试脚本上
  • OCCAM的部分求值法:
    • 部分求值法降低了OCCAM的可用性,它只允许非冲突的标志存在于去膨胀的二进制程序中.(我们称两个标志是非冲突的,仅当它们可以在同一个执行过程中同时执行).因此,对于两个冲突的标志,需要创建两个变体.
    • 然而,我们要注意到在OCCAM中通过部分求值法,可以使得 去膨胀程序 易于通过配置去设置,以为其不需要小心和无聊地使用测试用例,其质量会影响去膨胀二进制文件地可用性
  • RAZOR中基于跟踪地简化:
    • RAZOR的不同启发式搜索影响其正确性和简化性,所以我们需要对使用不同的启发方法进行充分评估,已选择最佳的启发方法,保留合理的功能,下图展示了启发度级别与正确性的关系
    • 此外,RAZOR的训练时间取决于提供给他的测试用例数量,下图展示了其关系
  • PIECE-WISE中加载时间的缩减:
    • PIECE-WISE在编译时计算程序的依赖图并将其添加到ELF头文件中的.dep部分,用于减少加载时间,但这显著增加了大小.对于一些应用而言,大小的增加可能盖过了其好处

6.2 研究的限制

  • 目前DebloatBenchA仅选择了每一类中的单个工具,并提供了深入的分析.然而工具的覆盖范围可以很容易地进行扩展.
  • 目前 目标应用程序的选择受到了 去膨胀器功能的限制
  • 我们创建了大量的测试用例来覆盖训练和测试,但总有疏漏

7 相关工作

  • C/C++程序特化方向:
    • 主要有三个方向
      • (1)源代码级（例如Chisel [22]、C-Reduce [42]、Perses [46]和DomGad [52]）
      • (2)中间代码级（例如Trimmer [6, 7, 44]、LLPE [45]、LMCAS [8]和Occam [31, 33]）
      • (3)二进制代码级.（例如Razor [37]）
      • 另外也有库级别 ( 例如Piece-wise [39]、BlankIt [36]和Nibbler [5])
    • DebloatBenchA是第一个系统地审查所有类别的工具以强调每种方法的优势和劣势的基准测试。
    • 我们的评估还强调，组合多种方法具有比任何单个工具更好的性能的潜力。
  • 环境/系统级的去膨胀
    • MultiK [29]和shard [4]提供了针对应用程序的内核级别的去bloat化
    • Cimplifier [41]使用动态分析来检测容器内的具有逻辑上不同之处的应用程序，并自动将其分解为较小的容器。
    • LightBlue [50]利用静态分析执行应用程序引导的固件去bloat化。
    • CDE [20]利用执行跟踪来识别应用程序的依赖项以实现无缝移植
    • 最近，Hassan等人开发了一个名为DebloatBenchC的框架来评估容器去bloat化器[21]。
  • 去膨胀的其它程序语言的研究
    • Piranha [40]针对Objective-C
    • JShrink [16]; JSCleaner [17], Lacuna [35], Muzeel [30],Stubbifier [48] and [49] 针对JS
    • Red [26]，JAX [47]，BloatLid [18] Depclean [2]和[9]分别针对基于Java和PHP的应用程序
    • 也有在字节码上的研究 [19, 28].

8 结论

    1. 我们提出了DebloatBenchA,一个可扩展可维护的基准测试框架,用于对程序去膨胀方法进行严格的评估
    1. 我们将Chisel,Occam,Razor,Piece-wise集成到该框架中,进行了全面的比较研究.
    • 我们发现保守的静态分析工具更能产生正确的二进制文件
    • 而激进的动态分析工具在减少二进制文件大小,gadget类方面表现更好
    • 而Piece-wise在增大二进制文件大小的同时未能减少任何gadget类
    • 基于测试用例的工具在非coreuntils程序上的表现不好
    1. 对不同阶段多去膨胀工具的组合使用开辟了道路