@inproceedings{heo2018effective,
  title={Effective program debloating via reinforcement learning},
  author={Heo, Kihong and Lee, Woosuk and Pashakhanloo, Pardis and Naik, Mayur},
  booktitle={Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security},
  pages={380--394},
  year={2018}
}

Effective Program Debloating via Reinforcement Learning (Chisel)

0 摘要

  • 在软件工程中，代码重用和“一刀切”的方法是导致软件规模和复杂性显著增加的主要因素。由此产生的软件膨胀导致了性能下降和安全漏洞的增加。
  • 我们提出了一个名为Chisel的系统，旨在帮助程序员有效地定制和去膨胀程序。
    • Chisel接受一个待去膨胀的程序和一个对其所需功能的高级别规范作为输入
    • 输出是一个根据规范正确减少的版本的程序
    • 与其它方法相比,Chisel通过使用一种基于强化学习的新颖方法来加速搜索减少的程序并扩展到大型程序，从而显著提高了效果。
  • 我们对一组包含10个广泛使用的UNIX实用程序的13-90 KLOC(Kilo lines of code) C源代码套件进行了评估，结果表明Chisel能够成功去除所有不需要的功能并减少攻击面。

1 介绍

  • 软件膨胀导致性能下降并增加安全漏洞,此外常见库中的各种gadget使得攻击者可以在不向应用程序注入任何代码的情况下执行任意算法

  • 此外软件经常包含一些被用户几乎没用过的功能,但没有给用户任何实际和有效的方法去除它们

    • 目前流行的做法是对现有程序重新进行一个轻量级的实现.例如针对嵌入式平台的轻量级实现:WebServer(Lighttpd),DataBase(SQLite),C/C++ libaries(EGLIBC,yClibc-bg),命令行实用程序(BusyBox,ToyBox). 但这种方法需要源代码开源且需要大量手动工作
    • 在移动应用程序中,IOS APP引入乐系统瘦身,可以自动检测用户设备型号,仅下载特定设备所需的内容,但这需要开发者标记其软件来对应关系,这导致在IOS上该方法也不常用

  • 我们开发了一个实用的系统,使得程序员能够定制和简化程序

    • 该系统将一个程序,及其需要保留功能的相关高级规范作为输入
    • 输出一个根据规范正确简化的程序

  • 我们认为简化后的程序有效需要以下五个关键点

    • Minimality 最小:系统是否尽可能地 根据期望地特点 修建了程序
    • Efficiency 效率:系统是否高效地 找到了最小化地程序并且可以扩展到大规模的程序
    • Robustness 鲁棒:系统是否避免了 引入新的异常和漏洞 在生成的程序中
    • Naturalness 自然:系统是否生成了 可维护和可扩展 的代码
    • Generality 通用:系统是否可以应用于 大量不同的 程序和特点吗

  • 如下图示,Chisel系统需要一个程序P和一个质量测试函数S,来检查获选程序是否满足或与需要的属性冲突,最后输出一个最简化的程序P’同时满足S

  • Chisel提供了一个 在生成程序最小性上的 正是保证,叫做 1-minimality,已经被证实在程序简化中有效

    • 调用质量测试函数可能很昂贵,例如其可能会参与候选程序的编译和 在程序套件运行
    • 而1-minimality 保证 缩小算法在最坏情况下,调用质量测试函数的次数 为 程序大小的二次方
    • 尽管 此保证 不能保证找到最优解,但也有次优性质,也很难扩展到大程序
    • 而Chisel通过避免生成大量的 语义或语法上 无效的候选程序 来避免这个问题

  • Chisel保证简化后的程序满足给定的属性期望,所以其具有鲁棒性.

    • 其避免会随换程序或破环其自然性的转换
    • 最后,其将 程序和属性 都视为黑盒,使其适用于各种不同类型的程序和规范

  • C-REDUCE 和 PERSES不满足上述特点,这两个工具同Chisel一样,接受一个需要简化的程序和一个质量测试函数作为输入,并输出一个简化的程序

    • C-REDUCE满足了与Chisel相同的最小性和正确性标准,但其牺牲了效率,自然度和通用性.C-Reduce针对手写的程序转换规则是定制且紧密耦合的,由于这些规则是短时的,所以C-reduce在寻找简化程序时会产生大量的语义和语法无效的候选程序,此外,该工具经常生成不自然的代码
    • Perses同样牺牲了效率和通用性,其简化过程是基于语法引导的,这可以避免在搜索过程中产生语法无意义的候选程序.然而依然无法避免语义无效的候选程序,因为其无法感知程序元素间的语义依赖关系(例如def-use关系). 同时,基于语法感知的简化在每一步都太过保守,因此比C-Reduce效率更低.

  • 我们客服现有方法限制的 主要技术见解 是 使用 强化学习 来 加速程序的简化

    • 通过反复的试错,chisel构建并完善了一个静态模型,来决定每个候选程序通过测试的可能性,该模型可以有效的捕捉程序元素间的语义依赖同时引导搜索至最小程序
    • Chisel的学习方法是跨语言的,因为模型是从 尝试的候选程序和他们的属性测试结果 的简单向量中 学习的

  • 在10个UNIX上广泛使用的实用程序套件上对Chisel进行评估,Chisel高效地收敛到最小程序,由于其它所有方法.

    • 并成功修复了10个程序中的6个漏洞(CVE),平均消除了66.2%的gadgets,简化的程序通过SOTA的fuzz:AFL的持续三天的进一步验证
    • 此外,我们还手动分析了简化后的源码,确认删除功能符合预期,同时保留了诸如 模块化和局部性的理想软件工程实践

  • 论文贡献总结

      1. 提出Chisel系统来减少程序的大小和复杂度,其目标是从现有软件中移除不需要的功能并减少他们的攻击面
      1. 提出了一个通用的强化学习框架,为了更高效和更大的程序简化. 该框架可以在不同目标语言和规范上使用
      1. 使用一组UNIX的通用程序对Chisel进行评估,结果显示其可以减少软件的缺陷和攻击面且不引入新的bug

2 MOTIVATING EXAMPLE

  • 我们通过一个例子(Unix通用工具 tar)来解释Chisel如何帮助程序员定制和简化程序.
    • 假设针对嵌入式 我们需要一个简易的tar,目前针对嵌入式的tar有一个BusyBox.原始的tar提供97个命令行选项,BusyBox仅提供8个
    • 我们将演示如何通过向Chisel提供简单而高级的规范来自动获取与BusyBox有相同功能的程序
    • 同时我们还将展示这种简化如何导致 简化的代码 和 安全性的增强. 最后我们解释了如何保证结果程序的鲁棒性

2.1 明确Chisel的输入

  • 首先,我们需要用户编写一个高等级的特征规范,该规范描述了程序的期望功能.
    • 规范可以是一个脚本程序,其接收一个源程序并编译,并检查编译后的程序恮输出行为是否符合期望,如果不符合返回false,否则返回true
1 #!/bin/bash
2
3 function compile {
4 clang −o tar.debloat tar−1.14.c
5 return $?
6 }
7
8 function core {
9 # test 1: archiving multiple files
10 touch foo bar
11 ./tar.debloat cf foo.tar foo bar
12 rm foo bar
13 ./tar.debloat xf foo.tar
14 test −f foo −a −f bar || exit 1
15
16 # test 2: extracting from stdin
17 touch foo
18 ./tar.debloat cf foo.tar foo
19 rm foo
20 cat foo.tar | ./tar.debloat x
21 test −f foo || exit 1
22 ... #12 more tests that exercise the 8 target options
23 return 0
24 }
25
26 function non_core {
27 for test_script in ‘ls other_tests/∗.sh‘; do # for all optional test cases
28 { sh −x −e $test_script; } >& log
29 grep 'Segmentation fault' log && exit 1
30 done
31 return 0
32 }
33
34 compile || exit 1
35 core || exit 1
36 non_core || exit 1
  • 上述代码是一个可用作规范的脚本程序,该脚本包括三个步骤
      1. 第一步中调用complie函数(第三行),检查源程序是否可以编译
      1. 第二步调用core函数来检查程序是否表现出期望的属性,这一步包括14个测试用例,用于测试8个命令行选项,仅在通过全部测试用例时进入下一步
      • 例如:第14行,第一个测试用例,检测是否可以压缩和解压缩文件
      1. 第三步调用non_core避免简化带来新的错误,其指定了一种要求,即调用了简化去掉的功能时,程序至少不能崩溃(第29行),如果没有这个要求,简化器可能会随意地删除非核心功能地代码,这将导致移除删除功能被调用后很容易崩溃和受到攻击
  • 为了完成这样的脚本,我们需要广泛覆盖目标功能地测试程序,这些测试用例可以通过开发人员使用自动测试生成技术活回归测试套件来获得.本文中,使用开发人员为原始程序写的测试套件

2.2 Chisel与其它方法的结果比较

  • 给定tar的原始程序(45778行,13227个语句),12小时内,Chisel生成了简化版本(1687行,538个语句),而C-Reduce和Perses都无法在12小时内生成简化版本,简化例子如下
1 /∗ Chisel: global variable declarations removed ∗/
2 
3
4 char ∗safer_name_suffix (char ∗file_name, int link_target) {
5     /∗ Chisel: code containing CVE removed ∗/
6     return file_name;
7 }
8
9 void extract_archive() {
10    char ∗file_name = safer_name_suffix(stat_info.file_name, 0);
11    /∗ Chisel: overwriting functionalities removed ∗/
12 }
13
14 void list_archive() { ... /∗ same as original ∗/ }
15
16 void read_and(void ∗(do_something)(void)) {
17  enum read_header status;
18  while (...) {
19    status = read_header();
20      switch (status) {
21        case HEADER_SUCCESS: (∗do_something)(); continue;
22        /∗ Chisel: unnecessary functionalities removed ∗/
23        default: break;
24      }
25    }
26 }
27
28 /∗ Supports only 8 options: −c, −f, −x, −v, −t, −O, −o, −k ∗/
29 int main(int argc, char ∗∗argv) {
30    int optchar;
31    while (optchar = getopt_long(argc, argv) != −1) {
32        switch (optchar) {
33          case 'x': read_and(&extract_archive); break;
34          case 't': read_and(&list_archive); break;
35          /∗ Chisel: unsupported options removed ∗/
36        } 
37      }
38 ... /∗ same as original ∗/
39 }
/*
  Code snippet of the original version of tar
*/
1 int absolute_names;
2 int ignore_zeros_option;
3 struct tar_stat_info stat_info;
4
5 char ∗safer_name_suffix (char ∗file_name, int link_target) {
6     char ∗p;
7     if (absolute_names) {
8       p = file_name;
9     } else {
10      /∗ CVE−2016−6321 ∗/
11      /∗ Incorrect sanitization when "file_name" contains ".." ∗/
12      /∗ "p" points to the longest suffix of "file_name" without "../" ∗/
13      ...
14    }
15    ...
16    return p;
17 }
18
19 void extract_archive() {
20    char ∗file_name = safer_name_suffix(stat_info.file_name, 0);
21    /∗ Overwrite "file_name" if exists ∗/
22    ...
23 }
24
25 void list_archive() { ... }
26 void read_and(void ∗(do_something)(void)) {
27    while (...) {
28       enum read_header status = read_header();
29      switch (status) {
30        case HEADER_SUCCESS: (∗do_something)(); continue;
31        case HEADER_ZERO_BLOCK:
32          if (ignore_zeros_option) continue;
33          else break;
34        ...
35        default: break;
36      }
37    }
38  ...
39 }
40
41 /∗ Support all options: −x, −t, −P, −i, ... ∗/
42 int main(int argc, char ∗∗argv) {
43    int optchar;
44    while (optchar = getopt_long(argc, argv) != −1) {
45      switch (optchar) {
46        case 'x': read_and(&extract_archive); break;
47        case 't': read_and(&list_archive); break;
48        case 'P': absolute_names = 1; break;
49        case 'i': ignore_zeros_option = 1; break;
50        ...
51      }
52    }
53  ...
54 }
  1. main函数中reduced版本,与原始版本比较,减少了不需要得选项
  2. read_and函数检查输入文件的头部,并在头部无效时进行异常处理,如果头部有效,根据命令调用响应函数.在简化版本中,异常处理部分被移除,头部无效即终止程序
  3. safer_name_suffix函数通过和三处冗余分支得到显著简化
  • 实现上述简化,不能只是用典型的静态分析和动态分析
    • 静态分析保守地保留了所有代码部分,因为在编译时命令行选项和输入文件都是未知的,因此静态方法无法删除函数read_and中的任何代码,因为原本代码中29行status无法确定
    • 动态可达性不能删除函数safer_name_suffix中的任何代码,因为测试用例中没有执行选项’-P’,所以变量absolute_name总为0,结果动态方法总是覆盖第9行地分支,因此无法删除从原始代码第9行开始的讨论安全漏洞的方法

2.3 分析Chisel的输出

  • 从两方面进行 输出安全漏洞和进一步验证

安全漏洞移除

  • tar工具在解压缩文件时的安全漏洞和修复措施。原始版本的tar存在一个漏洞，允许攻击者通过恶意构造的路径名覆盖现有文件。开发人员通过忽略包含’…/'的路径名来修复了这个问题。在Chisel版本中，由于删除了相关功能，这个漏洞无法再被利用。

  • 详细情况请看论文描述

进一步验证

  • 化简后的程序很小,并且很大程度上保留了语法结构,用户可以很轻松的与源代码进行比较.复杂的代码也可以通过比较工具清晰的展示缩减程度
  • 此外,化简后的大小和复杂度可以使用准确的自动化技术.
    • 为了检查简化版本是否引入了新bug,我们使用现有的技术进行推理(例如 静态/动态分析,模糊测试,运行时监控或验证),来提高正确率
    • 我们对简化后的tar进行了静态分析和随机模糊测试
  • 去膨胀化使得人工检查静态分析称为可能
    • 例如,Sparrow[13]是一种用于发现安全漏洞的静态分析器，它在一秒钟内只为简化后的tar程序生成了19个警报，而原始程序则生成了1,290个警报。经过手动检查，我们得出结论认为所有19个警报都是假的。
  • 去臃肿化后的程序还可以通过随机测试工具（如模糊器）进行高效测试
    • 我们在简化后的tar程序上运行了AFL工具[1]，即使在三天内也没有找到任何导致失败的输入。这提高了对去臃肿化后的程序正确性的信心。

3 背景

本节正式定义了我们的程序去臃肿化设置,并介绍了基于我们的程序去臃肿化方法的 增量调试和强化学习的概念。

3.1 程序去膨胀

  • 定义
    • 令P∈P,PP \in \mathbb{P},\mathbb{P}是所有程序的集合
    • 一个property 属性 定义各位一个属性测试函数O:P→BO:\mathbb{P} \rightarrow \mathbb{B},B={T,F}\mathbb{B} = \{T,F\},当O(P)=TO(P)=T时,当且仅当PP有该属性,否则O(P)=FO(P)=F
    • 令∣P∣|P|为P的大小,根据一个合适的度量标准,例如语句或符号的数量
  • 给定一个程序PP,一个属性测试函数OO满足O(P)=TO(P)=T,程序去膨胀的目标是找到最小的程序P∗∈PP^{*} \in \mathbb{P}满足
    P∗=arg minP′∈P∣P′∣     s.t.   O(P′)=TP^* = {arg\,min}_{P' \in \mathbb{P}} |P'| \,\,\,\,\,s.t.\,\,\,O(P')=T
    • 如果实现这个目标则成为全局最小性,但这是NPC问题
    • 因此实践中去膨胀的追求为一个更可行的目标称为 1-minimality[45]. 一个程序P∗∈PP^* \in \mathbb{P}被称为 1-minimality当且仅当对于任意的从P∗P*删除单个元素获得的变体P′P'不能通过属性测试

3.2 Delta Debugging(DD for short)

算法描述

  • 给定程序PP和属性OO,DD首先将输入程序转换为列表LL,其中包含任意粒度(tokens,lines,函数)
  1. 初始化时,将解决方案设为L,分区数设为n(第1,2行)
  2. 当前解决方案候选L划分为n个分区(第4行)
  3. 对于每个分区uiu_i算法测试 该分区(或其补集) 是否可以保留属性(第5,7行)
  4. 如果能保留,删除其补集,否则删除分区(第6,8行)
    1. 如果一个分区通过属性测试,DD将n设置为2重复该过程;
    2. 如果一个补集通过测试,DD将n设置为n-1,维持当前粒度等级;
    3. 当没有分区和补集通过属性测试时,DD将每个分区分为两半
  6. 如果每个分区都不能分割(12行),则返回对应剩余元素列表L的程序P′P'(13行);
  7. 否则,通过将每个剩余分区分成两半继续主循环(10行)
  8. 此算法最坏复杂度为O(∣P∣2)O(|P|^2)

算法例子

1 int f1 () { return 0; }
2 int f2 () { return 1; }
3 int f3 () { return 1; }
4 int f4 () { return 1; }
5 int f5 () { return 1; }
6 int f6 () { return 1; }
7 int f7 () { return 1; }
8 int main () { return f1(); }
  • 考虑上述简单的C代码,我们的目标属性时终止并返回0,同时定义在函数粒度上进行简化,因此,最小的程序应该仅包含函数 f1和main.
  • 下图展示了算法的迭代过程
  1. 最初两次迭代中,算法尝试两个分区(n=2),每个分区包含前四行和最后四行。
  2. 由于这两个分区都无法保留属性，算法通过将n设置为4来增加粒度，并尝试了四个分区，但都失败了（迭代3-6）。
  3. 然后算法尝试了这四个分区的补集。在第8次迭代中，算法找到了一个保留属性的补集。通过将n减1，算法保持当前的粒度并尝试当前候选的n = 3个子集。
  4. 由于所有三个子集（⟨f1, f2⟩，⟨f5, f6⟩，⟨f7, main⟩）都已经尝试过，所以它们被跳过。然后它尝试它们的补集，并在第9次迭代中找到另一个较小的程序。
  5. 再次将n减1，算法保持当前的粒度并尝试当前候选的n = 2个子集。同样，所有两个子集（及其补集）都已经尝试过并且失败了。
  6. 现在算法将粒度翻倍（n <- 2 × 2），并尝试四个子集（迭代10-13），但都失败了。
  7. 继续尝试它们的补集，在第15次迭代中找到了另一个正确的补集。n = 4 - 1 = 3
  8. 现在它尝试程序的n = 3个子集及其补集，并在最后一次迭代中找到最小解决方案。

3.3 强化学习 Reinforcement Learning

马尔可夫决策过程 Markov Decision Process

  • Markov Decision Process(MDP) 是一个用于解决顺序决策问题的框架.在这个框架中,一个代理(agent)作为学习者和决策者,与所谓的环境进行交互,代理根据每个状态下的行为从环境中获得奖励. 形式上,MDP有以下几个部分
    • 一组状态SS,初始状态s0∈Ss_0 \in S
    • 一组动作A\mathcal{A}和函数A:S→2AA:S\rightarrow 2^{\mathcal{A}},指定每个状态下可用的函数
    • 过渡模型T:S×A→Pr(S)T:S\times \mathcal{A} \rightarrow Pr(S),其中T(s′∣s,a)T(s'|s,a)表示从状态ss执行动作AA转移到状态s′s'的概率
    • 奖励函数R:S→RR:S\rightarrow \mathbb{R},其中R(s)R(s)表示状态ss的预期奖励
  • 求解MDP的目标是找到一个策略 π:S→A\pi: S \rightarrow \mathcal{A} ,该策略指定了在给定状态下的代理采取的理想的行为.通常我们感兴趣的是找到一个最优的策略 π∗\pi^{*} ,使得对于每个状态 s∈Ss\in S,其被定义为
    π∗(s)=arg maxa∈A(s)∑s′T(s′∣s,a)V∗(s′)\pi^* (s) = \underset{a\in A(s)}{arg \,max} \underset{s'}{\sum } T(s'|s,a)V^*(s')
    其中 V∗(s)V^*(s) 表示在代理在状态s下施行最优策略是奖励的期望和,其是如下递归定义
    V∗(s)=R(s)+γ∑S′T(s′∣s,π∗(S))V∗(s′) V^*(s) = R(s) + \gamma \underset{S'}{\sum} T(s'|s,\pi^*(S)) V^*(s')
    其中 \gamma $ 是一个折扣因子,用于平衡当前奖励和未来奖励的重要性. 通常情况下,我们假设 $0 \leq \gamma \leq 1 ,并且 γ\gamma 越大,未来奖励的重要性越高

基于模型的强化学习

  • 基于模型的强化学习（Model-based Reinforcement Learning，MBRL）是一种在马尔可夫决策过程（Markov Decision Process，MDP）中使用模型来指导代理与环境交互的技术。
  • MBRL通过预测环境对代理在每个状态下采取的动作的响应来学习转移概率和奖励模型。
  • 在解决MDP的过程中，MBRL跟踪状态转换和动作，根据获取的信息更新模型。
  • 对于每个状态，代理根据模型估计未来奖励的期望总和，并选择使未来奖励期望总和最大化的动作。

4 我们的方法

4.1 非正式描述

  • 我们方法的关键是优先考虑能通过属性测试候选者,以此来快速收敛出一个解决方案,相当于在DD中减少属性测试的失败率,减少遍历失败的候选者的时间

  • 为此,我们使用MBRL,维护一个模型来预测每个候选者通过属性测试的几率.

  • 与原生DD相比,基于上面的例子,我们的算法只需要调用10次即可,下面详细展示使用标准树决策模型时算法的每次迭代

    1. 第一次迭代中,程序P通过属性测试,将此结果添加到模型数据集中,此时模型预测全部程序都能通过测试
    2. 使用模型考虑优先候选者,此时二者优先级相同,故第一次迭代随机选择子集⟨f5, f6, f7, main⟩,没有通过测试,此结果添加至数据集中,形成图中(b)中第一个决策树,内部节点表示特定函数的存在条件,叶子节点表示给定程序通过属性测试的概率.第一棵树预测包含f4的程序通过属性测试,没有则不通过
    3. 第二次迭代选择第一次的补集⟨f1, f2, f3, f4⟩并失败,此结果加入数据集,模型决策树发生变化. 现在分区大小缩小一半,目前模型认为需要同时又f4和main才能通过属性测试
    4. 第三次迭代中,< f1,f2 >的补集被预测通过测试,但没有,将数据加入数据集得到新的预测树,预测同时需要< f2, main> 才能通过测试
    5. 在经过6次迭代后,获得理想决策树,认为包含main和f1是能通过属性测试的,此后再分区大小再缩小,均不能通过属性测试,因此迭代终止,返回程序< main, f1> 为最小程序

4.2 用于DD的MDP

  • 接下来对用于DD的MDP作正式定义

  • 给定原始程序P和属性测试函数O,MDP的目标是找到一个好的策略来引导DD找到满足O的最小程序

  • MDP的每个组件定义如下

    • State:为候选程序列表和粒度等级的二元组S=⟨L,n⟩S = \langle L, n \rangle,其中LL是候选程序列表,nn是粒度等级
    • Action:状态s=⟨L,n⟩s=\langle L,n \rangle的可能的行为A(s)A(s)定义为
      A(s)={⟨⟨u1⟩,2⟩,...,⟨⟨un⟩,2⟩}(subsets)∪ {⟨⟨L/u1⟩,n−1⟩,...,⟨⟨L/un⟩,n−1⟩}    (complements)∪{⟨L,2n⟩}(more  granularity)A(s)=\{ \langle \langle u_1 \rangle ,2 \rangle,..., \langle \langle u_n \rangle ,2 \rangle \} \quad (subsets) \\ \cup\, \{ \langle \langle L/u_1 \rangle ,n-1 \rangle,..., \langle \langle L/u_n \rangle ,n-1 \rangle \} \,\,\,\, (complements) \\ \cup \{ \langle L ,2n \rangle \} (more\,\, granularity)
      即A(s)A(s)由当前状态中下一个候选程序和所有粒度对组成
    • Transition function:转移函数定义如下,(s=⟨L,n⟩,a=s′s=\langle L,n \rangle,a=s') T(s′∣s,a)T(s'|s,a)定义为
      T(s′∣s,a)={1if  s′=⟨ui,2⟩  ,  O(ui)=T1if  s′=⟨L/ui,n−1⟩  ,  O(L/ui)=T1if  s′=⟨L,2n⟩  ,  ∄i.O(ui)=T∨O(L/ui)=T 0otherwiseT(s'|s,a)=\begin{cases} 1 & if\,\,s'=\langle u_i,2 \rangle \,\,,\,\,O(u_i)=T \\ 1 & if\,\,s'=\langle L/u_i,n-1 \rangle \,\,,\,\,O(L/u_i)=T\\ 1 & if\,\,s'=\langle L,2n \rangle \,\,,\,\, \nexists i. O(u_i)=T \lor O(L/u_i)=T\ \\0 & otherwise \end{cases}
      即状态转移仅放生在 下一个候选程序通过属性测试 或 需要更小的粒度时
    • Reward function:奖励函数定义如下
      R(⟨L,n⟩)={1(L  is  1−minimal)0(otherwise)R( \langle L,n \rangle ) = \begin{cases} 1\quad (L\,\,is\,\,1-minimal) \\ 0\quad (otherwise)\end{cases}
      即当LL是1-minimal时,奖励为1,否则为0

  • 解决MDP是不切实际的,为此使用MBRL

  • 我们学习了一个概率模型 M:P→[0,1]\mathcal{M}: \mathbb{P} \rightarrow [0,1] ,返回候选程序通过属性测试函数的概率 并 从中获得策略

  • 我们用 T^,R^\hat{T},\hat{R}表示T,RT,R的估计,他们的定义和M\mathcal{M}而不是OO,

    • T^\hat{T}定义如下
      T^(s′∣s,a)={M(ui)/Ks,a(s′=⟨ui,2⟩)M(L/ui)/Ks,a(s′=⟨L/ui,n−1⟩)(∏⟨L′,n′⟩∈A(s)/s′1−M(L′))/Ks,a(s′=⟨L,2n⟩,2n≤∣L∣)0(s′=⟨L,2n⟩,2n≥∣L∣)\hat{T}(s'|s,a) = \begin{cases} \mathcal{M}(u_i)/K_{s,a} \quad (s' = \langle u_i,2 \rangle) \\ \mathcal{M}(L /u_i)/K_{s,a} \quad (s' = \langle L/u_i,n-1 \rangle) \\ (\prod_{\langle L',n'\rangle \in A(s)/s'}1-\mathcal{M}(L'))/K_{s,a} \quad (s' = \langle L,2n \rangle,2n\leq|L|) \\ 0 \quad (s' = \langle L,2n \rangle,2n\geq|L|)\end{cases}
      其中Ks,aK_{s,a}是一个归一化因子,使得T^\hat{T}成为一个概率分布
      • 前两个例子中,转移概率被定义为子集和他的补集通过质量测试函数的概率
      • 另外两个例子针对更小的粒度,其概率为,1减去所有子集通过属性测试的概率. 最后如果粒度已经达到最小,则转移概率为0
    • R^\hat{R}定义如下
      R^(⟨L,n⟩)=∏1≤i≤∣L∣(1−M(L/ui))\hat{R}(\langle L,n\rangle) = \prod_{1\leq i\leq |L|}(1 - \mathcal{M}(L/u_i))
      其中uiu_i是LL的部分,即R^(⟨L,n⟩)\hat{R}(\langle L,n\rangle) 表示LL在模型M\mathcal{M}下为1-minimal的概率

  • 最后给定估计的转移和奖励函数 T^,R^\hat{T},\hat{R},我们的目标是找到最优策略

    π^(s)=arg  maxa∈A(s)∑s′T^(s′∣s,a)V^(s′)(1)\hat{\pi}(s) = \underset{a\in A(s)}{arg\,\, max}\underset{s'}{\sum} \hat{T}(s'|s,a) \hat{V}(s') \quad (1)
    其中 V^\hat{V} 是在策略 π^\hat{\pi}下的期望价值和,其定义如下
    V^(s)=R^(s)+γ∑s′T^(s′∣s,π^(s))V^(s′)(0≤γ≤1)(2) \hat{V}(s) = \hat{R}(s) + \gamma \underset{s'}{\sum} \hat{T}(s'|s,\hat{\pi}(s)) \hat{V}(s') \quad (0\leq \gamma \leq 1) \quad (2)
    其中 V^\hat{V} 可以通过动态规划获得.

    • 根据该策略,由行为导致的状态转移和奖励 为被用于 改进估计值,这将继续优化政策.
    • 在我们的评估中,我们发现当 γ=0\gamma = 0 时 效果最好(即仅考虑即时奖励)

4.3 静态模型

我们描述了如何学习上述模型。我们的目标是使用该模型来预测给定程序 $ P $ 的 $ O§ $ 的概率。我们从程序去膨胀过程中收集的数据中学习模型。

  • 特征表示:假设一个程序由 $ n $ 个元素组成 $ \langle u_1,…u_n \rangle $ , 每个 $ P $ 的子程序 $ P’ $ 被特点编码函数 $ F $ 编码成一个长度为 $ n $ 的二进制向量

    F(P′)=⟨b1,...,bn⟩ F(P') = \langle b_1,...,b_n \rangle
    其中 $ b_i = 1 $ 当且仅当 $ u_i \in P’ $,否则 $ b_i = 0 $.

  • 数据标记:每个特征向量被一个布尔值标记 $ \mathcal{O}§ $ ,表示该程序是否通过属性测试. 每个标记数据在DD过程中每次实验中进行收集

  • 模型学习:使用现成的监督学习模型如决策树,该算法在DD过程中说及特征向量和标记. 该模型可以预测 对于一个给定的特征向量 $ P $ 预测其标记 $ \mathcal{O}§ $ . 通过将 $ \mathcal{O} $ 替换为 $ \mathcal{M} $ , 我们可以定义近似版本的 $ \hat{T} , \hat{R}$

4.4 基于学习的程序Debloating

  • 现在正式说明我们的方法
  • 入参:
      1. 原始程序 $ P $ 和属性测试函数 $ O $
      1. 一个现成的监督学习方法 $ \mathcal{L} $ ,用于学习模型
      1. 一个特征编码函数 $ F $ ,用于将程序编码为特征向量
  • 算法解析
    • 第2行,状态 $ s $ 初始化为原始程序
    • 第3行,数据集 $ D $ 初始化为 原始程序的特征向量和其标签(T) 的二元组
    • 第4-13行为主循环,直至程序不能再分割
      • 第5行更新数据集
      • 第6行计算当前模型得到的策略
      • 第7行根据策略选择下一个状态
      • 第8行检查属性测试是否通过
      • 第9行:当前状态通过属性测试 或 需要更细粒度划分程序的时候,改变当前状态,
      • 第12行:属性测试结果添加到数据集中

5 评估

  • Q1. Effectiveness:debloating的质量和时间
  • Q2. Security:是否移除的缺陷和攻击面的减少
  • Q3. Robustness:对未见过输入的鲁棒性

5.1 实验设置

  • 实施:
    • 我们将Chisel作为C程序的简化器,采用了基于语法引导的分层增量调试法(Delta-Debugging)
      • Chisel首先使用标准的增量调试法简化全局级组件(全局变量声明,类型定义,函数定义等)
      • 随后递归的再局部级组件(赋值,循环体,条件语句等)
      • 局部级简化完成或,Chisel重新调用全局级简化，并继续整个过程直到找到一个最小版本
      • 同时,Chisel通过简单的依赖分析,拒接无用的程序(如缺失主函数等)
    • Chisel由2361行OCaml代码组成。我们使用FastDT3的现成决策树算法来学习模型。我们使用精确的决策树（即不使用提升/袋装法，也不限制树的最大深度）。所有实验在3.0 GHz和128 GB内存的Linux机器上进行
  • 基准 Benchmarks
    • 使用GNU软件包中的10个基准程序来评估Chisel,
    • 下表展示了这些程序的特征
    • 且这些程序均为开源且广泛应用
    • 每个都有一个或多个已知的安全漏洞CVE
    • 并且有人工缩减的版本,可以在BusyBox中找到
  • 规范
    • 期望保留的功能参考了BusyBox的实现,我们假设BusyBox默认配置支持的选项是每个程序的核心功能
    • 处于安全考虑,我们强制简化的程序在执行非核心功能程序时不产生任何未定义的行为(不仅是崩溃),例如缓冲区溢出或使用未初始化的变量
    • 为此,我们使用Clang的sanitizer选项[4]编译程序在运行时监视未定义的行为
    • 为了广泛的测试所有功能,我们从源代码仓库收集了测试用例
    • 总的来说,Chisel生成的简化版本的程序满足以下限制
        1. 可以编译
        1. 与原始程序相比在核心功能上有着相同的输出
        1. 在执行非核心功能时不会产生未定义的行为
    • 此外,为每次运行设置时间限制,防止由Chisel引入的无限循环的程序
  • 基线化简器:C-REDUCE 和 PERSES

5.2 简化的效率

    1. 简化大小
    • 使用以下三种情况进行比较
      • 原始程序
      • 基于静态分析 Sparrow [13] 删除未使用的代码: statements 从 172,304 到 55,848 (32.4%) (因为Unix实用程序有公共库)
      • Chisel:减少89.1%,只剩6111
    1. 与现有方法比较运行时间
    • Chisel在12h内完成简化,因其不仅避免了语法错误,也学习去避免了语义错误
    • C-REDUCE超时6个,因其是基于行的简化器
    • PERSES超时2个,因其是一个纯粹的基于语法的简化器
    1. 与BusyBox中的人工简化版本比较
    • BusyBox为一个单一的可执行程序,通过子命令调用所有工具
    • BusyBox有7个程序比Chisel生成的程序更小,但这主要因为人工可以使用更优化的代码和数据结构,总的来说,Chisel生成的代码大小合理
    1. Chisel比现有方法产生的程序更自然,使得人可以维护和扩展,同时保留了原始结构 和 软件工程实践(如模块化和局部化)
    1. 与Cov进行比较,证明Chisel的必要,覆盖率使用llvm-cov [11]计算,结果如下图示,结果显示Chisel可以比朴素的Cov方法显著的减少更多的代码

5.3 安全增强

  1. 首先检查简化后程序,查看Chisel是否已经去除已知的露铜
  2. 计算原始程序和简化程序的gadgets数量衡量攻击面的减少,这里使用ROP-gadget[12]工具
  3. 使用SOTA静态缓冲区溢出分析器Sparrow [13],检查所有报告的警报

  • 结果展示如上图
      1. Chisel 去除了10个程序中6个的CVEs
      1. 去除了潜在的攻击面,具体而言平均减少了 66.2%的ROP gadgets
      1. 减少了95.4%的缓冲区溢出警报,剩下的警报较少进行手动检查后确认是假警报

5.4 鲁棒性

  • 通过SOTA 模糊器 AFL,生成随机的命令行输入 和 必要的输入文件进行测试,实验进行了三天
  1. 大多数情况下,Chisel生成的程序在测试中表现良好,模型测试没有检测到崩溃.此外,由于有sanitizer的保护,Chisel生成程序时有效的过滤掉了错误的程序
  2. 然而在未见过的输入可能会出现错误.
    • 根据我们的经验,随机模糊测试可以丰富测试脚本生成更健壮的程序:将使得简化后程序崩溃的模糊测试生成样例加入到测试脚本中,并重新运行Chisel和模糊测试,程序健壮性进一步提升,接下来3天内模糊器没有发生崩溃

6 对有效性的威胁

  1. Chisel可能会因为测试脚本返回不确定的结果而出错.
    • 主要有未定义的行为引起,我们可以使用sanitizer来过滤这些有问题的程序,但如果目标程序使用了未受相同保护方案编译外部库,则无法过滤. 如果外部库是开源的话可以通过再编译进行解决
    • 另一个原因是我们避免了 不能终止的程序 产生,因为简化可能导致不能终止(如去除了循环语句的终止条件),为此我们设置了时间限制. 然而如果限制不够大,测试脚本可能返回不能确定的结果.这个问题可以通过动态监测和躲避无限循环解决
  2. 测试用例不够完备
    • 我们使用AFL模糊测试工具对生成的程序进行了鲁棒性测试。然而，如果输入需要符合特定的格式，我们的测试可能不够全面，因为我们无法向AFL提供特定的语法，使其能够通过过滤不合法的测试输入来剪枝搜索空间。
    • 为了解决这个问题，我们可以使用基于语法的模糊测试工具[25, 44]。
  3. 静态分析的不确定性
    • 我们使用Sparrow静态分析器与AFL一起测试鲁棒性。尽管该分析器对于大多数C程序功能是准确的，但如果目标程序具有复杂的指针算术操作或由未知语义的API函数引起的复杂控制流程，则可能会存在不确定性。
    • 在实践中，由于设计一个完全准确的静态分析器极其具有挑战性，因此会使用对于不同语言功能而言是准确的各种静态分析工具[31]。在此方面，我们可以通过结合多个具有不同功能的静态分析器的结果来缓解这个问题。

7 相关工作

  • 程序Debloating:现在有很多在不同粒度缓解软件膨胀的技术
    • coarse-grained(大粒度级,如应用级)
      • 例子:Rastogi et al. [35] 容器级别 Docker. 可以根据用户的限制将一个复杂容器分成多个简单的小容器,其方法基于动态分析获取应用的信息
    • finer-grained(小粒度级)
      • JRed [28] 和 RedDroid [27] 去除了Java和Android应用中的未使用的类和方法
      • Quach et al. [34] 提出了一个简化系统 ,在编译和加载中去除不必要的代码,其系统通过静态分析和基于训练的技术计算函数依赖来简化应用和库
    • 与之前方法比较,Chisel可以再更细的粒度进行简化,如语句级别. 现有的小粒度的方法基于静态分析只能去除不用的代码,而Chisel很激进甚至可以出去在运行路径上的代码
    • 程序膨胀检查
      • Bhattacharya等人[19]介绍了一种分析技术，用于检测Java应用程序中可能的膨胀源;我们的方法自动删除相对于属性测试程序的冗余代码
    • 监测和减少运行时内存膨胀
      • 这与程序debloating正交但互补,因为程序debloating可能潜在缓解这一问题通过移除运行路径上的代码
  • 测试输入最小化
    • 目前很多简化程序的方法都是 最小化使得编译器或解释器不会崩溃的程序,由于其不关注简化后的代码是否可以运行或维护,最后产生的代码安全性和可读性都很差. 例如C-REDUCE不能维护程序的软件工程时间,而我们的目标是开发人员可以后续使用的精简程序
    • 现有的方法仅通过简单的指导来搜寻最小的程序.最近出现了能够识别程序语法结构的方法,这种先验知识可以避免很多语法错误的程序的尝试,但不能从语义上避免错误.我们的系统通过构建静态模型避免了语义上错误的尝试. 同时,我们的方法可以加速现有的所有方法,包括又非结构化输入的增量调试法
  • 程序切片和可达性分析
    • 切片是从程序中提取的与某个感兴趣点的值相关的子部分,通常由静态分析和动态分析得出. 我们的方法旨在更一般的属性并且不需要特定的语义和依赖分析,且我们的方法可以获得比程序切片更小的程序
    • 在我们的实验中，我们与可达性分析相比较，而不是使用切片技术，原因如下。
      • 动态切片包含了在程序的特定执行下影响目标变量值的所有语句。然而，从高级规范中确定感兴趣的变量和程序点可能是具有挑战性的。即使用户手动注释这些目标，动态切片对于程序精简可能仍然效果不佳。例如，“safer_name_suffix” 的输出实际上取决于函数中的大部分语句。因此，与 Chisel（相比，动态切片无法消除漏洞。
    • 静态可达性计算通常会因为静态分析的不可判定性而产生对实际可达代码的不精确近似。
      • 通常无法有效处理复杂的控制流，例如间接过程调用（如 setjmp / longjmp，函数指针或反射）、复杂的条件语句和指针算术。
      • 而我们的方法不受这些问题的限制。动态可达性计算在代码大小方面可能比静态方法更有效。然而，我们的研究表明，我们的方法产生的程序比基于动态可达性的程序具有更小的攻击面

8 结论

  • 我们提出了Chisel, 一种基于 增量调试法的学习系统,用于程序debloating

    • 我们的方法通过给定的测试脚本高效地简化程序
    • 学习到的概率模型加速找到最小程序的速度
    • 此外这种精简方法除去了一些漏洞,并显著减少了潜在的攻击面
    • 此外,简化获得的 程序大小和复杂度 运行更进一步应用精确的推理方法和人工检查

  • 在未来,计划在以下方向扩展Chisel

      1. 探索更好的概率模型和高效的增量学习方法
      1. 设计除 IO 之外的其它规范
      1. 应用于简化二进制等其它语言的方法

9 阅读总结

  • Chisel:使用强化学习框架辅助增量调试法来进行程序去膨胀
  • 问题:
      1. 需要用户提供属性测试函数,很麻烦的
      1. 增量调试法很慢的,套上强化学习更慢了
      1. 删除的代码取决于输入,并且只会删除代码,因为使用的是增量调试法

10 复现

  • 在win11上使用ubuntu20.04虚拟机

    • 直接下载源码,编译运行,运行失败,应该是新版被不兼容旧版本的问题
    • 于是在虚拟机上使用docker,在docker上跑chisel,最小的gzip跑了14h(

  • 结论:很慢的,之后也不用跑了,感受下效果练练手就行了