@inproceedings{xin2022studying,
  title={Studying and understanding the tradeoffs between generality and reduction in software debloating},
  author={Xin, Qi and Zhang, Qirun and Orso, Alessandro},
  booktitle={Proceedings of the 37th IEEE/ACM International Conference on Automated Software Engineering},
  pages={1--13},
  year={2022}
}

Studying and Understanding the Tradeoffs Between Generality and Reduction in Software Debloating

00 摘要

  • 现有程序去膨胀方法通过使用配置文件作为识别程序特性的依据,通常是以一组输入的形式提供.具体来说,给定一个程序和输入,这些技术将生成一个在这些输入上正确运行的简化程序

  • 然而只关注简化会和输入过拟合,为此我们需要考虑通用性,即未在配置文件中的输入的正确性

  • 为此,我们对4种去膨胀方法(3种SOTA,1种基准方法)在25个程序和这些程序的不同输入集上进行了减少和通用性的实证评估。结果表明，这些方法确实会产生对使用的输入过拟合并且通用性较低的程序。

  • 基于这些结果，我们还提出了两种新的增强方法，并评估了它们的有效性。这个额外的评估结果显示，这两种方法可以在不显著影响减少程序大小的情况下提高程序的通用性。

  • 最后，由于不同的方法具有不同的优势和劣势，我们还提供了指南，以帮助用户根据其特定需求和背景选择最合适的方法。

01 介绍

  • 软件越来越复杂,带来的软件肿胀问题影响软件性能和安全

  • 基于输入的指定软件预期功能方法: 通过输入来指定软件预期功能.然而因为输入只能覆盖有限的功能,所以这种方法会导致过拟合

  • 因此简化和通用性需要同时考虑,然而这两点有着固有的矛盾,我们的去膨胀方法要在这两点间取得平衡

  • 早期去膨胀方法激进的追求大小的缩减,忽略了通用性;

  • 两种新的方法考虑了通用性,但未正确地衡量,并且没有 简化和通用性地平衡

    • Debop:(Qi Xin, Myeongsoo Kim, Qirun Zhang, and Alessandro Orso. 2020. Program debloating via stochastic optimization. In 2020 IEEE/ACM 42st International Conference on Software Engineering: New Ideas and Emerging Results (ICSE-NIER).):根据提供的输入评估程序的通用性，而不考虑未观察到的输入
    • Razor(Chenxiong Qian, Hong Hu, Mansour Alharthi, Pak Ho Chung, Taesoo Kim,and Wenke Lee. 2019. RAZOR: A Framework for Post-deployment Software Debloating):使用一个弱（基于崩溃）的预测模型来确定程序的行为正确性，并评估通用性

  • 进行一项研究,评估基于输入地去膨胀方法在 简化,通用性及二者权衡之间地表现

    • 调查了3种面向C程序的SOTA(Chisel,Debop,Razor),1种基准方法(Cov)基于代码覆盖率进行去膨胀。
    • 应用于包含25个程序的两个不同基准测试集,进行 去膨胀和通用性评估
    • 评估方法
      • 评估去膨胀方法:使用两种简化类型:基于大小和攻击面
      • 评估通用性方法:使用两种通用类型:正确性(C-通用性) 和 鲁棒性(R-通用性)
      • 评估二者间的平衡:使用F-score度量

  • 实验结果显示

    • Chesel和Debop并未考虑程序处理未观察到的输入的能力,会较低的C通用性
    • Razor通过基于覆盖率的减少和基于启发式的增强,在C通用性上表现较好,但在R通用性上表现较差

  • 为了解决这些问题,我们提出了两种增强方法CovF和CovA,旨在提高R,C-通用性和通用性和简化的权衡,这俩种方法均基于Cov,但是CovF基于模糊测试,而CovA基于分析的代码增强,以此识别互补相关的代码,并在去膨胀时简化这些代码

  • 具体来说,对于程序p和输入集合I

      1. CovF和CovA首先调用Cov从p中删除未被I执行的代码,得到去膨胀程序pcovp_{cov}.
      1. CovF利用模糊测试生成可以暴露pcovp_{cov}鲁棒性问题的输入,从p中恢复代码,消除这些问题;CovA利用静态和动态分析计算得到信息来增强pcovp_{cov},即通过静态程序依赖关系,执行频率和覆盖灵活性等

  • 直观地说,CovF专注于导致pcovp_{cov}崩溃地代码,CovA保留与pcovp_{cov}相关地代码,由此产生具有增强鲁棒性和正确性地程序

  • 实际情况下去膨胀涉及多个相互冲突地目标,本次研究中有四个具体目标

    • 高的简化度
    • 攻击面减少
    • C-通用性
    • R-通用性

  • 同时我们所考虑的方法各有优缺点,为此我们提供了一个指南,帮助用户选择方法

02 背景

2.1 基于输入的去膨胀方法

  • pp为程序,II为一组输入的集合,p(i)p(i)为pp在输入为ii上的执行结果.
  • 给定pp和II,基于输入的去膨胀方法通过生成一个简化程序p′p',使得i∈Ii\in I,p′(i)=p(i)p'(i)=p(i)

2.2 评估方法

2.2.1 简化度
  • 两种简化度度量方法
    • 基于大小的简化度(size reduction): sred(p,p′)=size(p)−size(p′)size(p)sred(p,p')=\frac{size(p) - size(p')}{size(p)},size()size()为程序大小,有两种度量方法
        1. 语句数
        1. 执行时内存的字节数
    • 基于攻击面的简化度(attack surface reduction): ared(p,p′)=asurf(p)−asurf(p′)asurf(p)ared(p,p')=\frac{asurf(p)-asurf(p')}{asurf(p)},asurf()asurf()表示用程序包含的面向返回编程（ROP,Return-Oriented-Programming）小工具的数量来衡量程序的攻击面。
      • ROP（Return-Oriented Programming）小工具是一系列机器指令的序列，通常以返回指令结束。攻击者可以利用漏洞（例如堆栈溢出）来覆盖一个小工具的返回地址，从而改变控制流并执行恶意代码。ROP小工具通常用于测量攻击面。我们使用ROPgadget工具来计算ROP小工具的数量。
2.2.2 通用性
  • C通用性(correctness-based):收集另一个输入集合I′I',使得I′∩I=∅I' \cap I = \emptyset,有cgen(p′,I′)=∑i′∈I′p′(i′)=p(i′)∣I′∣cgen(p',I')=\frac{\sum_{i'\in I'} p'(i')=p(i')}{|I'|},其中p(),p′()p(),p'()表示p,p′p,p'产生的输出,∣I′∣|I'|表示输入的数量
    • 两种不同类型的C通用性
        1. 当I′I'为输入全集时,得到的通用性称为 all-input-based c-generality
        1. 当𝐼’是一个包含与𝐼相关的输入（例如，用于测试类似功能）,得到的通用性称为 related-input-based c-generality
  • R通用性(robustness-based):该指标衡量对于未被观测到的输入的适应能力,反映了程序的可靠性. 同样收集另一个输入集合I′I',使得I′∩I=∅I' \cap I = \emptyset,rgen(p′,I′)=∑i′∈I′robust(p′(i′))∣I′∣rgen(p',I')=\frac{\sum_{i'\in I'} robust(p'(i'))}{|I'|},robust()robust()表示程序运行结束后是否崩溃(如 段错误). 本文通过生产 II 的fuzzed 版本得到I′I'
2.2.3 简化度-通用性 权衡
  • 使用调和平均数,或F-score
    f(red,gen)=2⋅red⋅genred+genf(red,gen) = \frac{2\cdot red \cdot gen}{red+gen}

03 相关去膨胀方法

  • RazorRazor 是 binary-based ,修改程序的二进制码
  • 其他方法是 source-based ,修改程序源代码
  • CovACovA和CovFCovF都是基于CovCov的,他们的强化方法也可以用到其它方法上

3.1 Previous Input-Based Approaches: ChISEL,DEBOP,RAZOR

  • CHISEL是一种基于 强化学习引导(reinforcement-learning-guided),增量调试(delta-debugging-base)的 减量化(reduction-oriented) 去膨胀算法

  • DEBOP 是一种 多目标方法(multi-objective),考虑了三个因素(size reduction,attack surface reduction,generality),并在这三个因素中寻求平衡

  • RAZOR 是一种 基于 追踪(tracing),启发式增强(heuristic-based augmentation)和二进制重写(binary-rewriting) 的 二进制级的精简方法

3.2 Cov:Coverage-Based Debloating

  • 给定一个程序pp和输入II,CovCov Instrument(启动,引导?) pp 使用II 识别出运行的语句,CovCov会删除未被使用的语句和使用过但不需要(比如定义了但未被使用的变量)的语句

  • CovCov 原型 使用 llvm-cov 和 gcov:依赖于Clang构建 抽象语法树(AST abstract syntax tree),遍历AST上所有语句,通过分析覆盖报告CovCov找到为执行的语句进行删除,同时通过依赖分析,还可以删除其它不必要的语句

      1. “dangling”(悬空指令):没有实际操作且条件没有实际作用的指令,如 if(x==0){}
      1. 未使用的变量命名
      1. 未使用的标签语句

3.3 CovF: Coverage-Based Debloating with Fuzz-Based Augmentation

  • 问题:基于覆盖率的方法通常会消除未执行的代码生成过度简化的代码,即过拟合
  • 解决:开发CovF,基于模糊测试增强的方法,提升精简后程序的鲁棒性
  • 方法描述:
      1. 给定程序pp和输入II,使用CovCov生成精简程序pcovp_{cov}
      1. 基于II进行模糊测试生成输入I′I',使得I′I' 与 II 鲁棒性相关,即可以使得pcovp_{cov}崩溃或无法终止
      • 当前实现中CovF使用 黑盒模糊测试工具 Radamsa 应用于II,生成Iinit′I'_{init}然后运行pcovp_{cov}对Iinit′I'_{init}进行测试,识别出 I′∈Iinit′I'\in I'_{init}使得pcov(I′)p_{cov}(I')崩溃或无法终止
      1. CovFCovF保留被I,I′I,I'执行的语句,删除其它语句,得到最终程序pcovfp_{covf}
  • 注意:原始程序pp可能本来就存在鲁棒性问题,该问题并不是由去膨胀引起的,CovF只是通过模糊测试找到了这些问题

3.4 CovA: Coverage-Based Debloating with Analysis-Based Augmentation

  • 问题:CovF方法可以通过 产生 不合规的输入增强程序的鲁棒性,但这些输入更多锻炼了非核心逻辑,但没有锻炼到其它不同特性
    • 例子:对输入i:"−m777testdir"i:"-m 777 testdir"很难模糊测试到另一个输入i′:"−ma=rwxtestdir"i':"-m a=rwx testdir",这两个鲁棒相关,但i′i'涉及到另一个功能f:使用符号表示权限而不是数字,创建一个目录f:使用符号表示权限而不是数字,创建一个目录,因此模糊测试很难保留该功能ff
  • 方法:CovACovA通过 对函数间的依赖关系和精简后的程序运行踪迹 进行 静态和静态分析 推断 需要被增强的相关代码
  • 方法效果:
      1. 与CovF相比,直接识别与功能相关的函数并保留
      1. 通过对函数进行增强,降低了生成 语法或语义无用的程序(e.g.:有循环但没break的语句)
      1. CovA对每一个函数计算一个增强分数,是对与所需功能的相关估计,该分数基于函数的依赖关系,执行频率和覆盖变化,越高与功能相关性越高
      1. 针对不同的输入时,如果一个方法的覆盖率经常发生变化,则该方法需要进行额外的增强
      1. 最后我们可以根据得到的分数选择前KK个函数进行增强
  • 方法具体:给定程序pp和输入II,增强阈值topktop_k
      1. CovACovA首先得到pp所有函数,对每个函数ff,计算三个分数:specificity−spec,frequency−freq,flexibility−flexspecificity-spec,frequency-freq,flexibility-flex,用map存储;分数详解在后面
      1. CovACovA对这些分数进行标准化,然后计算归一化分数的平均值左右增强分数aug(f)aug(f) aug(f)=specn(f)+freqn(f)+flexn(f)3aug(f) = \frac{spec_n(f)+freq_n(f)+flex_n(f)}{3} ,其中specn(f),freqn(f),flexn(f)spec_n(f),freq_n(f),flex_n(f)分别表示spec(f),freq(f),flex(f)spec(f),freq(f),flex(f)的标准化值
      1. CovACovA对函数按照增强分数进行排序然后生成一个简化的程序,该简化程序包含(1) 经过输入II后精简的代码,和(2) 与前topktop_k个函数相关的代码
  • 分数详解
    • SpecificitySpecificity(特异性值):CovACovA通过静态分析,更具体说是以来分析计算得到,表现了函数与程序具体特点的相关程度
      • 为了计算SpecificitySpecificity,CovACovA构建了一个函数调用图,对每个函数ff计算一个指标,该指标基于 ff依赖函数的数量(fan−in)(fan-in)和 依赖ff的函数的数量(fan−out)(fan-out),最后SpecificitySpecificity计算公式如下
        spec(f)=1−util(f)=1−fanin(f)N×log⁡(Nfanout(f)+1)log⁡(N)spec(f) = 1 - util(f) = 1 - \frac{fanin(f) }{N} \times \frac{\log(\frac{N}{fanout(f)+1})}{\log(N)}
      • NN是函数的总数;fanin(f),fanout(f)fanin(f),fanout(f)是ff的fan−infan-in和fan−outfan-out,分别是 图中调用ff的函数数量和ff调用的函数数量
      • 由某论文可知 utilutil取值0−10-1之间,fanin,fanoutfanin,fanout取值0到∣N∣−1|N|-1之间,而当fanin(f)fanin(f)越大,即ff被更多函数调用,则fanout(f)fanout(f)越小,即ff调用的函数越少,则函数ff更可能是一个工具类,有很高的实用性指标,所以它有较低的 SpecificitySpecificity值
    • FrequencyFrequency(调用频率):公式
      freq(f,I)=NfNIfreq(f,I)=\frac{N_f}{N_I}
      NfN_f表示函数ff在II中被调用的次数,NIN_I表示II中输入的数量
    • Flexibility(灵活度)Flexibility(灵活度):CovACovA分析函数ff的执行情况
      • 对于每个被II执行的函数ff,CovACovA跟踪对于II中的每个ii,被ii执行的所有语句集合S(f,i)S(f,i).如果ff没有被ii执行,则S(f,i)=∅S(f,i)=\emptyset
      • 然后计算在II中被执行函数ff中唯一语句集合c(f,I)c(f,I)
      • 例子:假设II中包含3个输入i0,i1,i2i_0,i_1,i_2,ff被这些输入执行的语句集合分别是S(f,i0)={s0,s1},S(f,i1)={s0},S(f,i2)={s0,s1}S(f,i_0)= \{ s_0,s_1 \},S(f,i_1)=\{s_0\},S(f,i_2)=\{s_0,s_1\},其中s0,s1,s2s_0,s_1,s_2是三个语句.此时c(f,I)=2c(f,I)=2,因为有两个唯一的语句集合,即{s0,s1},{s0}\{s_0,s_1\},\{s_0\}
      • CovACovA计算ff的灵活性flexflex公式:flex(f,I)=c(f,I)NIflex(f,I)=\frac{c(f,I)}{N_I} 其中NIN_I是II中输入的数量;
      • 使用机理:对于低 flexibilityflexibility的函数,他在执行未被观察到的输入时,其行为可能会发生变化的概率较小,因此CovACovA认为这些函数增强的优先级较低

04 评估

  • 探究以下四个问题
    • RQ1：就减少程度、c-普适性和它们之间的权衡而言，所考虑的方法有何区别？
    • RQ2：就减少程度、r-普适性和它们之间的权衡而言，所考虑的方法有何区别？
    • RQ3：当使用越来越多的输入进行精简时，所考虑的方法的表现如何？
    • RQ4：这些方法的效率如何？

4.1 工具实现

  • CHISEL,DEBOP,RAZORCHISEL,DEBOP,RAZOR
  • CovF,CovACovF,CovA

4.2 基准(Benchmarks)

4.2.1 基准程序

  • 在我们的评估中，我们使用了两组程序：十个实用程序（Util）和来自SIR基准[2]的15个程序（SIR）。

    • 这十个实用程序，因为它们在之前的精简方法CHISEL,DEBOP,RAZOR的评估中使用过。对于这些程序，我们使用了它们在Chisel基准[20]中提供的单文件版本。一个单文件程序包含一个C文件，将项目中所有原始C源文件合并在一起。
    • 一组15个程序，它们是SIR基准提供的所有C程序。它们代表了不同类型的程序，包括词法分析器（printtokens）、实用程序（例如make）、Unix shell（bash）和文本编辑器（vim）。我们选择这些基准程序也是因为它们有大量（从几百到几千个）相关的测试。拥有大量的测试能够有效评估精简程序的普适性，并对使用不断增加的输入进行精简的效果进行全面调查。对于SIR程序，我们使用CIL合并工具[1]为它们获取了用于精简的单文件版本。

  • 下表表示了25个程序的基准:

    • 从属 belong (Bench)
    • 名字 name (Program)
    • 代码行数 size in lines of code (LOC)
    • 函数数量 number of functions (#Func)
    • 语句数量 statements (#Stmt)

  • SIR基准包含七个程序(SSIR),比另外八个小(LSIR),我们应该重点分析方法在使用程序和大型程序上的效果,因为去膨胀技术更适用于大程序

4.2.2 输入

  • 在对程序进行去膨胀和通用性评估时,由于需要大量的输入,所以没有使用与程序关联的人为创建的小的数据集,而是通过谷歌搜索,在网络上获得真实用户的输入

  • 实用工具输入

    • 具体而言,我们为每个实用工具收集十个输入集,均来自真实用户,网站来源见引用
    • 下1介绍了输入的统计信息，包括#TotalIn（总输入数）、#MinIn（所有输入集中最小输入数的集合𝑆𝑚𝑖𝑛）、#MaxIn（所有输入集中最大输入数的集合𝑆𝑚𝑎𝑥）和#AvgIn（所有输入集的平均输入数）,程序的总输入数（#TotalIn）

  • SIR程序输入

    • 我们将与程序相关的输入集IuI_u分为两个子集IdI_d和IeI_e,用于评估去简化效果和正确性
    • IdI_d:从IuI_u中随机选择10个输入,使其大小约等于实用工具输入的数量
    • 额外的三个IdI_d:分别占IuI_u的10%,20%,30%10\%,20\%,30\%,并获得相应的IeI_e集合,以评估输入大小与简化效果之间的关系

  • 为了评估基于相关输入的通用性，我们针对不同的程序使用了不同的方法来识别相关输入。

    • 对于接受带选项的命令行输入的程序（例如bzip2），如果它们使用相同的选项集，我们认为两个输入是相关的，这种方法类似于Razor [49]的评估中所使用的方法。
    • 对于bash和vim，提供的输入已经使用标签标记了它们所使用的功能（例如，算术功能的标签为“arith”）。因此，对于这些输入，我们使用标签来确定它们之间的相关性。
    • 对于所有其他程序，即SSIR程序，我们认为所有输入都是相关的。

  • 为了评估鲁棒性,我们使用了Radamsa [53]和AFL [4]基于去除冗余代码的输入来生成一组模糊输入𝐼′𝐼'

4.2.3 校验器
  • 我们使用校验器来评估程序的行为正确性和稳健性
    • 校验器比较 简化程序的输出和原始程序的输出
    • 对于 实用程序,也要考虑程序的 退出值,打印的消息,所生成的文件;对于文件,会检查文件内容(必要时需要检查文件的权限)
    • 对于SIR程序,使用其原始的对应的校验器;此外我们开发了一个校验器来评估鲁棒性
    • 为了确定程序是否崩溃，oracle会检查一系列表示异常终止的退出代码

4.3 配置

4.3.1 评估方法

  • 对与每个实用程序 pp,获得10组输入,使用 去膨胀方法TT基于 输入IdI_d生成 简化程序p′p'测量这些程序的简化程度、通用性和权衡得分，并计算它们的平均值作为𝑇𝑇所实现的得分。

    • 为了衡量c-generality，我们对于每个未用于去冗余的输入集合（共九组），执行𝑝′𝑝'，并计算𝑝′𝑝'正确行为的输入比例的平均值

  • 对于每个SIR程序 pp,使用 去膨胀方法TT基于 输入IdI_d生成 简化程序p′p'\

    • 基于测试输入IeI_e评估p′p'的正确性
    • 基于模糊测试输入和校验器I′I'评估p′p'的鲁棒性
4.3.2 参数设置
  • 使用默认参数运行 CHISEL,DEBOP,RAZOR
    • 由于CHISEL和DEBOP运行时间长,设置时间上限6h
    • RAZOR在四个级别上进行增强并进行实验
  • 对于CovF,从输入集选择最多100个输入,使用Radamsa为每个选定的输入生成10模糊测试输入进行去膨胀
  • 对于CovA,试验了15个K值,比较不同的结果
  • 为了衡量通用性,我们设置了10s的超时,因为一个去膨胀程序对一个输入可能不会停止
4.3.3 平台
  • Ubuntu-18.04机器上运行的260GB RAM和32 AMD-Opteron 1.4GHz处理器,该机器需要超过284小时(11天)才能完成所有实验的去膨胀工作

4.4 探究问题一:简化度,正确性和权衡

4.4.1 CHISEL和DEBOP,COV 比较
  • CHISEL和DEBOP的正确性较低,低于0.6,即这两种方法容易产生过拟合的程序
  • Tradeoff中,CHISEL和DEBOP的基于大小的F-score较低,即这两种方法在正确性和简化度的平衡不如Cov
  • 原因:
      1. CHISEL基于增量调试,在删除代码时非常激进.但其增量调试费时,所以在大型程序上CHISEL无法修建大量不需要的代码
      1. DEBOP依赖随机优化,基于Cov的代码再进行删除,因此DEBOP不会增加COV的正确性,但可以提高简化度,所以DEBOP会生产高简化度和低正确性的程序
  • 对于实用程序,CHISEL和DEBOP移除的ROP gadgets比Cov多,导致RelAF和AllAF分数略高.(ROP gadgets，全称Return Oriented Programming gadgets，指的是一段以汇编指令"ret"结尾的一小段指令序列。这些 gadgets 可以被用来修改某些地址的内容，从而有效地控制程序的执行流程。本文即指攻击面)
    • 原因:
        1. DEBOP和CHISEL在执行路径中删除语句,可以有效减少ROP gadgets
        1. DEBOP将ROP gadgets的减少列为目标之一
    • 对于大程序,由于CHISEL费时,其减少攻击面的能力降低
4.4.2 CovF, CovA, and others 比较
  • CovF和CovA的正确性高于Cov,CovA尤其明显,且CovA时正确性最高的方法;CovF更专注于鲁棒性,所以正确性较低于CovA
  • CovF和CovA的简化程度小于Cov,但在4.5中可以看到这两个方法可以在不影响简化程度的情况下显著提高程序通用性
  • CovF和CovA的基于攻击面的F分数较低,因为方法基于Cov,无法有效减少攻击面;优化Cov以减少攻击面,这可能是未来的一个研究方向
4.4.3 RAZOR和基于源代码的方法比较
  • RAZOR时基于二进制的方法,其获得了高简化和高正确的分数,即其在两个基准测试中的大小和攻击面的F分都是最高的,原因是
      1. 指令级别的操作
      • 因此RAZOR的搜索空间比基于源代码的大,能找到更多更好的权衡空间.
      • 同时因为RAZOR能够在指令级别上修改编译器带来的冗余代码,将其和基于源代码的方法相比可能不恰当.
      • 为此我们使用RAZOR基于覆盖率的方法(称为RazorCov)生成没有增强的简化程序,发现通过修建指令生成的程序内存大小和攻击面都比Cov小,从而有更大的增强空间
      1. 使用增强来补充输入中未被测试到的代码
4.4.5 在小程序上的比较
  • Cov没有达到高简化分数和高F分数,CovA和CovF简化分数提高但F分依然不高.这似乎意味着基于源代码的方法在小型程序上的效果不好
  • Chisel和Debop简化分数和F分数都很高,因为程序搜索空间小. Razor因为基于二进制,所以简化分数和F分数都很高

4.5 探究问题二:简化度,鲁棒性和权衡

  • 上图第二列展示了所有方法的平均鲁棒性分数,这些分数基于Radamsa生成的模糊输入计算而成.同时表格显示了三种 简化分数和权衡分数

  • 结论

    • CovF实现了最高的鲁棒性,并且简化分数和Cov并没有差太多
    • 基于输入的方法对于未观察到的输入鲁棒性都很低,因为其去冗余的输入只反映了程序的典型使用情况
    • Razor生成的简化程序鲁棒性最低,且RazorCov的鲁棒性更低,其对输入过拟合严重
      • 原因:大多数程序中,Razor的增强与稳定性无关,只会追求更好的简化程度,这会排除一些防御性检查,如printf和exit等,

  • 还使用了AFL [4] 评估测试每种方法生成的简化程序的鲁棒性,结果显示CovF具有最高的r-generality（0.87），其次是Chisel，其r-generality为0.75，其他方法的得分均为0.67。CovF也是实现最高基于大小的权衡得分的方法：SF为0.76，MF为0.71。这些结果进一步证实了CovF的有效性。

  • 还使用Radamsa生成的模糊输入对SSIR中的所有小程序进行了测试，并发现对于这些程序，所有方法都实现了较高的r-generality，其中CovF的得分最高（0.96），而Razor的得分最低（0.88）。与我们在第4.4.4节中展示的情况类似，CovF和CovA使用的基于源代码的增强策略在小程序中往往是无效的，因为这些程序只能进行有限的代码减少。

4.6 探究问题三:当使用越来越多的输入进行精简时，所考虑的方法的表现

  • 实验不同数量的输入时不同的简化方法的表现
  • 使用SIR基准进行了这个实验,因为其有大量的测试集
  • 对每个程序pp,创建三个输入集I1,I2,I3I_1,I_2,I_3,其中I0⊂I1⊂I2⊂I3I_0\subset I_1 \subset I_2 \subset I_3,并且I1,I2,I3I_1,I_2,I_3的大小分别为II的10%,20%,30%10\%,20\%,30\%,I0I_0是之前实验的10个输入集;使用这些输入集进行去膨胀,用剩下的输入集进行正确性评估,使用Radamsa生成的模糊输入进行鲁棒性评估

  • 上图展示了不同方法在减少（mred和aread）、通用性（allcgen, relcgen, 和 rgen）以及权衡（从mf-allcgen到af-rgen）方面的平均得分
  • 结论
    • 当输入规模增大,简化分数会降低,但正确性会提高
    • 当输入规模增大,鲁棒性不会显著提升,同时由于鲁棒性的增加少于代码的增加,对应的F分可能会下降

4.7 探究问题四:这些方法的效率

  • Chisel和Debop最耗时,平均需要4.7小时和5.4小时来生成一个去臃肿的程序
  • Razor、Cov和CovA的效率更高，平均只需要0.2分钟、0.4分钟和0.6分钟来生成一个去臃肿的程序。
  • 因为基于覆盖的方法不需要像Chisel和Debop那样反复执行相同的输入
  • 此外,增强过程也是高效的,除CovF需要模糊测试外,但也只要3.3分钟

4.8 讨论

  • 选择软件去膨胀方法的建议

    • Razor在减少大小和c-通用性之间取得了良好的平衡，但生成的去臃肿程序可能存在鲁棒性问题，即在未观察到的输入上执行时可能会崩溃或无法终止。因此，如果鲁棒性很重要且程序源代码可用，用户应考虑使用基于源代码的方法。
    • 其中，Cov是一种简单的方法，可以产生合理的结果。在鲁棒性是优先考虑的情况下，应该优先选择CovF。
    • 相反，如果主要目标是高正确性通用性，用户应考虑使用CovA。
    • 如果特别关注大小减小并且效率不是问题，Chisel是一个不错的选择，因为它的去臃肿过程可能需要花费几个小时才能完成，特别是对于大型程序。
    • 最后，如果去臃肿的主要原因是减少攻击面，应该使用Debop。

  • 我们的研究证明了在去臃肿时考虑减少和通用性的重要性，并为在不显著降低减少程度的情况下提高通用性提供了解决方案

  • 这里的一个困难是很难衡量实际的程序通用性并确定改进它的方法

  • 另一个可能的研究方向是,探索一种 可以指导 ,基于输入的去膨胀方法的, 估计通用性的技术

4.9 有效性威胁

  • 内部威胁:使用了作者提供的Chisel、Debop和Razor的实现，并对我们实施的方法进行了仔细测试
  • 外部威胁:评估基于一组包含10个Unix实用程序和15个SIR程序的数据集，我们收集了不同的输入集合。需要进行额外的实证研究来评估我们的结果是否适用于其他程序和输入。

05 相关工作

  • 除基于输入的方法外,还有一些其它方法

    • 基于人工注释的特征规范,基于人工开发的领域采样,数据配置和调查 的方法
    • 针对特定类型的应用程序的 (Chrome浏览器,Android应用程序)的方法
    • 不移除不需要的功能,而是以来静态分析删除未使用的代码或裁剪指令和库的方法
    • 在给定领域进行程序大小缩减(如容器,服务器系统,Java应用程序等)
    • 或专注于特定任务(如安全性检查,API特化等)

  • Cimplifier方法,特别是在对容器的去膨胀时,使用了类似于CovF的技术

    • 但CovF使用模糊测试提高程序鲁棒性,生成额外的输入
    • Cimplifier使用符号执行来获取额外的输入，以改善对所需系统资源的识别。
分支/路径 预测
  • CovA于CovF的增强旨在简化程序中保留正确的代码,所以本文的研究也与 静态 分支/路径 预测有关
    • 但是,静态分支/路径预测的目标是提高程序的性能,而不是简化程序,所以他们不需要考虑简化和泛化的权衡
    • 且原本预测更多基于 启发式方法和机器学习,本文预测 基于模糊测试和静态和动态分析
特征识别定位
  • 本文去膨胀算法依赖于一组输入来识别所需的特征及对应的代码,这与特征识别定位的方法有关,这些方法可以用于简化对程序的理解,对去膨胀算法有帮助
程序修复
  • 类似于去膨胀算法,依赖于一组测试用例来指定程序的正确行为.因此同样可能会出现过拟合并,或修复错误
  • 解决此类问题的技术包括 生成新的测试用例,根据启发式方法优先考虑补丁,使用概率模型

06 结论和未来工作

  • 以往的去膨胀方法主要关注于简化程序,而忽略了程序的通用性和鲁棒性,为了填补这一空白,本文进行了研究

      1. 将三种SOTA的去膨胀方法和基础方法应用于25个程序和这些程序不同的输入集
      1. 系统的评估了他们在 简化程度,泛化程度以及二者间权衡程度的比较

  • 同时,本文提出了两个新的方法,实验证明了他们在不影响简化程度的情况下,在简化程度和泛化程度取得了更好的权衡

  • 本文的研究还表明了不同方法间的优势和劣势,我们提供了一份指南帮助用户根据需求来选择最合适的去膨胀方法,同时我们的研究也为未来的研究提供了方向

  • 未来工作

    • 如何根据程序大小,输入覆盖及其它因素动态调整简化的程度
    • 通过包括更多程序,额外的模糊测试 进行鲁棒性评估
    • 进行用户研究,评估在实际场景使用去膨胀技术的可行性
    • 调查在工业实际中去膨胀方法的使用情况