Software Debloating 论文阅读 (7) BLADE

@article{aliblade,
  title={BLADE: Scalable Source Code Debloating Framework},
  author={Ali, Muaz and Habib, Rumaisa and Gehani, Ashish and Rahaman, Sazzadur and Uzmi, Zartash}
}

BLADE: Scalable Source Code Debloating Framework

0 摘要

现有的源代码精简工具在动态云环境中应用时存在可扩展性低和运行时开销高的问题，其中实例会即时启动（指明场景）
为了解决这一挑战，我们提出了BLADE，它利用常见的编码习惯和语言限制构建简单而有效的启发式方法，以实现更快的源代码精简
- 例如：通常在使用之前定义变量，因此删除节点时，其在语法树的位置越深，破坏代码的概率越低；
- 例如：在精简某些功能时，基本块中的语句可能会被一起删除
为此，Blade使用分层源代码简化，通过反向谦虚遍历选择简化候选，以便在定义之前删除使用
低运行开销使得BLADE能够实际应用于大型工作负载的代码精简
我们的评估表明，与现有的源代码精简工具相比，BLADE运行更快。
- 与 Chisel 相比，BLADE平均快2.3倍，并在代码大小和攻击面的减小方面提供可比较的效果。
- 与另一款源代码精简工具 Debop 相比，BLADE平均快2.75倍。
- （然而这两款都很慢）

1 介绍

简化工具需要的性质
- 1. 快速且可拓展,同时不损害通用性
  - 动态云环境中,实例会即时启动,因此需要快速的精简工具
  - CI/CD中,需要即时提供更新的构建
- 1. 可审计性:
  - 允许在精简后检查生成的代码是否存在任何意外的副作用。不在源代码级别操作的精简工具[2]，[4]–[6] 对于这种用例不太理想。
基于源代码简化方案的工作原理
- 1. 创建测试规范描述所需的功能
- 1. 迭代地选择要从代码库中删除的一组代码语句的候选集
- 1. 将剩余的代码与规范进行测试。
  - 如果通过，就永久性地删除所选的语句。然后继续对剩余的代码进行搜索。
  - 如果测试失败，将那些选定的语句放回代码库，并考虑一个新的候选语句集，直到所有集合都用尽。
当今的简化方法很慢,甚至超时[1]，[7]–[9],它们常规地使用Delta-Debugging进行搜索,复杂度为 $O(n^2)$ ;而Debop[7]使用随机优化进行搜索,然而其精简效率较低
为此我们提出BLADE,支持快速且可扩展的代码精简
- BLADE采用了一个结构感知的代码精简过程，其运行时间为 $O(n)$ ,这使得将 BLADE 用于精简大型代码库（例如 nginx、sqlite3）变得实际可行。
- BLADE在源代码级别上操作，以实现可审计性。
评估表明,BLADE比 Chisel 快 2.3 倍，比 Debop 快 2.75 倍.
总的来说, 高度的代码精简、安全强化和低运行时开销的通用潜力使得 BLADE 在现代动态精简使用案例中更具有优势。
本文贡献如下
- 1. 新颖方法：BLADE利用其快速算法，有效地扩展到大型工作负载（例如，nginx、sqlite3）。这使得BLADE成为现实工作负载的实际解决方案。
- 1. 全面评估：与现有的精简框架进行的比较评估显示，BLADE在精简时间上相比其他方案有显著改进，而不会牺牲代码精简。
- 1. 开源:仓库地址

2 动机和见解

DD算法低效的两个原因
- 1. 可以被简化的语句可能分散而不是成片出现.因此,搜索可移除代码的最大片段所需的时间潜在地可能超过实际删除大块代码所带来的可能时间优势
- 1. 没有考虑编程语言的语法规则
  - 例如:在候选删除集中包含一个定义语句,在未删除的代码中有其应用,此时不能够删除该定义语句. 这样会产生语法错误,且编译这样的代码也是不必要的,编译这样代码浪费的时间可以通过在删除语句的定义之前优先删除其应用来避免
见解1:利用先定义后使用的结构
- 通常,变量先定义后使用,因此在语法树中,被删除的语句未知越深,出现错误概率越低
- 因此BLADE利用这一见解优化迭代次数,因为DD是优删除前部分的定义语句,而BLADE优先删除后部分的定义语句
见解2:利用语法树层次结构
- 给定一个包含多个语句的代码块,可以在考虑其中单个语句之前先把整个语句删除
- 而DD采用二分搜索移除大块,BLADE利用这一见解可以加快速度

3 系统设计

形式化定义:类似Chisel等
简化流程如下

识别并从程序中删除一组候选语句。
编译剩余的程序。
测试 Oracle 执行程序所需的功能。
测试 Oracle 比较程序输出与预期输出。
根据测试 Oracle 的结果，候选语句要么被永久性地删除（精简），要么重新引入到程序中。这个过程重复进行，直到精简算法无法进一步精简程序。

系统总体设计如下,下面进行详细介绍

A 语句树

对于给定的程序简历语句树,不同于AST,其叶子节点是完整的语句,中心节点是代码块(如函数,循环,if-else语句或结构体).
BLADE将语句块保留为内部节点以进行分层简化:删除内部节点及其子树等效删除整个代码块,删除后如未通过测试,则将该块重新放回1,并在该块中反向遍历进行DD
下图为一个语句树例子
构建语句树使用LLVM的前端Clang [12]提取原始代码的token,随后使用这些token构建语句数,并分类为块或语句

B 简化算法

简化算法以语句树为输入,递归地进行简化. 其以后序遍历语句树,没有并行优化的基本算法如下
- 首先尝试删除整个树来简化(第2行),否则回复树(第5行)
- 该算法对于每个节点只遍历一遍,因此复杂度是 $O(n)$

C 并行操作

同时多节点简化:在一次迭代中同时处理给定节点下的多个子节点

具体来说在多个进程中运行算法1,并行移除不同组合的子节点,通过测试集的删除最多的是最佳状态,此外永久删除节点更新全局状态
算法如下图所示
- 第5,6行为进程分配节点
- 第7行进程并行删除分配的节点,并测试
- 最佳简化在15行确定
- n是节点的子节点数,有 $2^n$ 种组合,我们依据 见解1 进行排序.在原型实现种,我们只考虑前n种组合
- 在给定节点，BLADE选择第一个即将到来的节点作为第一个进程的候选集；第二个进程获得前两个即将到来的节点，依此类推，第n个进程获取前n个即将到来的节点作为运行算法1的候选集。
多节点并行主要有两个好处
- 1. 速度:可以在一次迭代种删除更大的代码块,例如并行5个进程可一次删除5个节点.下图标明,在67.6%的情况下,一次迭代删除的语句多余一个
- 1. 简化:允许多节点组合简化,这在移除具有中和作用代码时有帮助

次级减小:

BLADE仅使用一组优先级高的组合,因此始终存在次级迭代能产生更多的简化.
为此,我们运行另外一组进程执行次级同时遍历,有以下目的
- 1. 在第一轮简化后制作新一轮的简化组合
- 1. 死代码清除(包括删除标签定义,不遵循先定义后使用原则)
这些次级迭代使用不同程度的语句树执行算法2,然而保持至少一个函数的并行迭代器之间的距离是重要的,原因有两个
- 1. 使得多个迭代器的简化路径不重叠
- 1. 允许迭代器为下一个迭代器创建新的简化组合之前能够全面搜索函数.
BLADE提供了调整并行迭代器及其调整进程数量的功能.使用多个迭代器减少了对程序执行多次完整遍历的需求,显著提高了代码简化水平

D 测试Oracle

功能检查器:
- 使用一组测试脚本(bash脚本),测试脚本需要完全覆盖核心功能
- 程序相对于给定功能的通用性被定义为程序处理指定功能的一般范围输入的适应性. 为了增加通用性会增加输入,导致时间增加,通过优化迭代次数,BLADE使得更好的通用性称为可能
适应检查器:
- 维系简化程序的质量,如安全性评估等
- 目前实现种,使用Clang静态分析来保证简化适应度如[1]中所实现。
  - 控制流完整性（Control Flow Integrity）Sanitizer
  - 地址（Address）Sanitizer
  - 内存（Memory）Sanitizer
  - 未定义行为（Undefined Behavior）Sanitizer
  - 泄漏（Leak）Sanitizer，

4 评估

与Chisel,Razor,Debop比较

A 标准

分析效率:运行时间表现对比
简化:
安全:
通用性

B 评估顺序

1. 在小程序上对比
1. 在大的应用程序上对比,着重体现了BLADE的优势:在实际工作负载上的可扩展性

C 评估环境

Linux Server
2个 Xeon Silver 4210 CPU@2.20GHz处理器
512GB DDR4
操作系统为Ubuntu 20.04.4 LTS

D 评估配置

目标程序和功能选择:

使用 nginx、sqlite3、make 和 tar 作为大型程序样本，以衡量可扩展性。
使用ChiselBench作为小程序样本
选择每个程序的核心参数,需要保证功能检查其全面覆盖了程序的各种输入范围.
- 例如:对于sort,uniq,输入包括文本,二进制,图像和压缩文件

设置BLADE,Chisel,Debop和Razor

使用相同测试Oracle对于所有工具,并针对各自修改
- Razor需要Oracle为python
- Debop要求每次结束时输出一组测量值,还要两个参数

E 分析效率评估

ChiselBench种,BLADE平均比Chisel快2.3倍,比Debop快2.75倍;
这使得它能够扩展到大型代码库，并鼓励添加更复杂的测试用例到测试 Oracle 中。

F 简化评估

从4个维度出发
- 二进制大小:
  - BLADE平均减少 67%
  - Chisel 67%
  - Debop 7%
  - Razor -19%:因为razor会将之前的设为只读而添入新的代码块
- 运行代码大小:
  - BLADE减少 83%
  - Chisel 86%
  - Razor 50%
  - Debop 10%
- 静态块
  - BLADE减少 86%
  - Chisel 88%
  - Razor 45%
  - Debop 7%
- 代码行
  - BLADE减少 83%
  - Chisel 76%
  - Debop 1%
  - 注意到从Chisel到BLADE代码行数有显著的减少,主要有以下BLADE考虑了但Chisel没有的两个原因
    - 1. 未使用声明的减少
    - 1. 结构体的减少

G 安全评估

从三个方面考虑
- 1. ROP Gadgets:使用Salwan的ROP Gadget工具[13]计算总共的唯一ROP gadgets.
  - BLADE减少 83%
  - Chisel 84%
  - Razor 52%
  - Debop 4%
- 1. 内存泄漏:使用名为Saber [14]的静态分析工具评估给定程序的内存泄漏
  - BLADE和Chisel处理内存泄漏能力是相当的,某些情况下BLADE引入了新的泄漏,这是因为BLADE的适应性检查其使用Clang的静态分析其,存在漏检情况
- 1. CVEs:Common Vulnerabilities and Exposures:是特定程序已知的漏洞,这些漏洞被识别然后与公众分享
  - BLADE在9个中删了5个,与Chisel相同
  - Razor从9个中删了4个

H 通用性评估

程序相对于给定功能的通用性定义为程序处理指定功能/在精简后保留的参数的一般输入范围的能力。
- 例如:bzip2对于-fc参数,为了测试通用性，我们为每个目标程序设计了一组新的测试用例，这些测试用例不属于功能检查器的预定义测试用例. 结果如下
通用性和训练用例的数量:下图展示了训练用例数量和验证集数量之间的关系
- 其粗略表明:随着训练用例数量的增加,通用性也会增加
- 对于多样化输入的程序,需要更多的训练用例以保证通用性
总结:BLADE的通用性与SOTA相当,并且可以增加训练集进一步增强通用性

更进一步:对大型应用进行精简

两个大的:nginx:76k 行,sqlite3-manager 75k 行
两个中的:tar 31k,make 27k
效果如下
现有方法在大型应用上:
- DEBOP表现不好,在大程序上不用
- Chisel在24h内无法完成简化,且在简化中出现错误
- Razor不是基于源代码的,我们没有再次耗费太多精力
nginx:
- 选择原因:(1)大程序(2)CVE中的漏洞
- BLADE移除了6个CVE,因为简化删除了易受攻击的功能
- 对简化后的二进制文件进行通用性测试,托管了20个不同的html界面,18个运行成功
sqlite3-manager:因其大程序,可解释如何通过移除功能增加安全性(移除update和delete可去除SQL注入)

5 讨论

通用性和训练样例
- BLADE的通用性与训练样例的全面性有关
- 然而蚕蛹少量训练数据达到更好通用性仍是一个开放问题
编程语言
- 目前BLADE面向C/C++程序,但理论上可以面向任何先定义后使用的结构,然而原始的DD确实可以应用于所有程序
- 为了应对更广泛的语言,BLADE可以以LLVM IR为输入,这是一种中间代码,任何语言编写的程序都可以首先编译为LLVM IR的形式,然后使用BLADE简化啊

6 相关工作

基于源代码的简化器:
- 有很多 :C-reduce [8], Perses [9],Chisel [1], Debop [7], DomGad [25], and Cov-A/F [26]
- 大部分使用了Delta Debugging (DD) algorithm [10]:该算法最初是为了确定在程序中起作用的“昨天”（工作模板程序）但在“今天”（错误程序）不起作用的最小故障诱导代码. DD就是发现有问题的代码,然后去掉这些代码将是程序正确;这与代码简化有着相似的原理
  - 基于DD,C-reduce[8] 对源代码应用一系列变换（更改标识符、变量范围、合并定义和用函数体替换函数调用）以减小源代码. 这不仅费时间,也不可行,且代码难以审计. 而BLADE很快,同时保持源代码的可审计行和可读性
  - 基于DD,语法指导的方法Perse[9],利用语言的语法减少了无效输出,但仍然会超时,而BLADE为线性算法
  - Chisel(被认为是SOTA),基于强化学习优化DD,而BLADE平均比其块2.3倍
- 上述方法都基于DD,而BLADE不基于DD,而是用新的算法选择候选集,进行简化;
- DomGad和Debop使用随即优化消除对DD的依赖,实现简化和通用性之间的权衡
- 而BLADE侧重速度,这反过来促进更多的训练数据来实现高通用性,这种高速可以应用于实际工作负载
- [26]也提出了使用模糊测试和静态分析方法来阻止输入过拟合,相同的方法也可以应用于BLADE来强化训练数据
基于 IR和 binary 的简化器
- JShrink[27] 对Java字节码构造静态和动态的扩展调用图来及逆行转化
- J-Reduce[28] 使用DD有效减少Java字节码
- Trimmer[5]和OCCAM[4]基于IR,使用如输入特化、循环展开和常量传播等技术，在程序的LLVM IR [24]上执行减小
- RAZOR[2]在二进制可执行文件上进行简化
- 上述方法的主要缺点就是不支持可审计性
基于库的简化
- Nibber[6] 通过删除共享库中未使用的函数来简化的放啊
- PieceWise[29] 针对共享库和静态库的代码,识别模块间的依赖关系并删除它们之间未使用的代码
- 这类技术是见解的,可以和BLADE和其它基于源码码的简化技术结合使用
杂项
- 一系列工作在不同的起点进行简化[30]-[40] (如JS,浏览器,app,配置文件)
- 有一项工作对简化进行了比较[41]

7 结论

我们提出了BLADE简化框架,利用程序语言的结构实现更高效的简化,使其可以应用于大的程序上
它满足了一个有效的减小工具所设定的所有目标（减小代码大小和攻击面，快速减小，维护正确性以及可审计性）
与先前方法相比,我们BLADE在大的程序负载上有了很大的提升

Mr_cold's blog

Software Debloating 论文阅读 (7) BLADE
Click back to the top

Home

Archives

Software Debloating 论文阅读 (7) BLADE

BLADE: Scalable Source Code Debloating Framework

0 摘要

1 介绍

2 动机和见解

3 系统设计

A 语句树

B 简化算法

C 并行操作

D 测试Oracle

4 评估

A 标准

B 评估顺序

C 评估环境

D 评估配置

E 分析效率评估

F 简化评估

G 安全评估

H 通用性评估

更进一步:对大型应用进行精简

5 讨论

6 相关工作

7 结论