@inproceedings{xin2020program,
  title={Program debloating via stochastic optimization},
  author={Xin, Qi and Kim, Myeongsoo and Zhang, Qirun and Orso, Alessandro},
  booktitle={Proceedings of the ACM/IEEE 42nd International Conference on Software Engineering: New Ideas and Emerging Results},
  pages={65--68},
  year={2020}
}

DEBOP:Program Debloating via Stochastic Optimization

0 摘要

  • Debloating的定义

  • 我们确信程序debloating是一个多方面的问题,必须用更通用的方法解决. 基于此,我们提出了一种通用的方法,可以将程序去膨胀问题形式化为一个多目标优化问题(multi-objective optimization problem, MOP),并使用随机优化算法来解决它.

  • 给定一个需要简化的程序,我们需要用户指定

      1. 程序的使用情况(例如:一组带有相关使用概率的输入)
      1. 去膨胀关注的因素
      1. 这些因素的相对重要性

  • 基于以上信息,该方法定义了一个合适的目标函数,用于将分数非陪给每个可能的简化程序,并生成最大化目标函数的解决方案

  • 我们同时提出和评估了DEBOP:我们方法的一个具体实例,考虑了 大小减小,攻击面减小和通用性三个方面

  • 结果现实,尽管仍然是初步的(albeit still preliminary),表明我们的方法可以有效地生成实现不同去膨胀目标之间良好权衡的去膨胀程序

1 介绍

  • 去膨胀有很多目标,且目标间可能冲突,例如

    • 失败10%的输入,但减少了80%的漏洞,这是可以接受的
    • 当通用性更重要时,程序大小的减小程度可以牺牲

  • 因此我们提出了一种新的,通用的程序去膨胀方法,将其视为多目标优化问题

  • 我们方法根据以下元素指定简化任务

    • pp 需要简化的程序
    • 一组带有使用概率的输入(即使用情况)
    • 去膨胀任务关注的因素
    • 这些因素的相对重要性,用权重表示

  • 基于以上信息,该方法生成一个目标函数 OO ,方法使用 OO 来聘雇搜索出的简化程序的分数,最终需要最大化 OO

  • 我们同时介绍了DEBOP,为我们方法的一个具体实例,考虑了三个去膨胀目标

      1. 程序大小减小
      1. 程序攻击面减小
      1. 程序通用性

  • 除此外,DEBOP也接受三个目标的权重,以此重定义 OO

  • 我们使用MCMC(Markov Chain Monte Carlo 马尔可夫蒙特卡洛)技术来 有效地探索解空间,MCMC在函数 OO 的指导下,对 pp 的简化版本进行采样,并报告具有最佳值得版本,这个过程我们称为 pdebp_{deb} , 其是实际解得近似值

  • 评估,在ChiselBenchmark

    • 在多目标权衡上表现不错,同时与另一个方法进行比较
    • DEBOP可能通用性不佳,但会产生更好得整体效果

  • 本文贡献如下

      1. 一个新的通用的简化程序形式化方法,将其视为多目标优化问题
      1. 一个具体的实例DEBOP,用于简化程序,并在多个目标之间进行权衡
      1. 一个概念验证聘雇,展示我们方法的潜在用途,并提供了对程序简化中权衡的新见解
      1. DEBOP开源

2 背景

  • Debloating定义
  • 程序表示

3 方法DEBOP

  • DEBOP

    • 支持三个目标:程序大小减小,程序攻击面减小,程序通用性
    • 通过MCMC取样技术,在优化问题上取得近似解

  • 形式化描述

    • 一个简化程序的版本 p′∈Sub(p)p'\in Sub(p)
    • size reduction: sr(p,p′)=sz(p)−sz(p′)sz(p)sr(p,p')=\frac{sz(p)-sz(p')}{sz(p)}, sz(p)sz(p)是程序 pp 的大小,如代码行数
    • attack surface reduction: ar(p,p′)=as(p)−as(p′)as(p)ar(p,p')=\frac{as(p)-as(p')}{as(p)}, as(p)as(p)是程序 pp 的攻击面数量,如 gadget数量
    • generality: g(p,p′)=∑ik∈IprkT(ik)g(p,p')=\sum_{i_k\in I} pr_kT(i_k), II 是一组输入, prkpr_k 是输入 iki_k 的使用概率, T(ik)T(i_k) 是 p′p' 在输入 iki_k 上的测试结果, T(ik)=1T(i_k)=1 表示通过, T(ik)=0T(i_k)=0 表示失败

  • DEBOP的目标是生成一个简化程序,最大化 sr,ar,g 的加权和

    • 首先计算简化程序的分数, r(p,p') $ , 与sr,ar组合 $r(p,p’)=(1-\alpha) * sr(p,p’) + \alpha * ar(p,p’)$ , 其中 $\alpha 表示sr和ar的相关重要性
    • 随后计算目标函数 O(p,p′)O(p,p') , 与r,g组合
      O(p,p′)=(1−β)∗r(p,p′)+β∗g(p,p′)O(p,p')=(1-\beta) * r(p,p') + \beta * g(p,p')
      , 其中 β\beta 表示r和g的相关重要性
    • 我们将这个值称为 O-score , 现在可以将DEBOP的简化任务形式化为一个优化问题
      Pdeb=argmaxp′∈Sub(p)O(p,p′)P_{deb} = argmax_{p'\in Sub(p)} O(p,p')
      通过使用不同的权重 α\alpha 和 β\beta , 可以调整DEBOP的行为,以便在sr,ar,g之间进行权衡

  • 由于 Sub(p)Sub(p) 的指数规模，通过枚举每个 p′∈Sub(p)p'∈Sub(p) 并找到具有最高O-score的 p′p' 来解决这个问题是不可行的。因此，Debop利用随机搜索，特别是马尔可夫链蒙特卡洛（MCMC）采样方法，生成一个近似的 pdebp_{deb}。

MCMC & Metropolis-Hastings Algorithm

  • MCMC采样用来估计一个分布 dd 的期望值. 为了使用MCMC,我们需要使用 O(p,p′)O(p,p') 为 dd 定义一个密度函数 f(p,p′)f(p,p') ,

    f(p,p′)=1Zexp(k∗O(p,p′))f(p,p')=\frac{1}{Z}exp(k*O(p,p'))
    其中k,Z是常数

  • 我们的目标是根据密度值 dd 的比例来抽取足够数量的样本 SS ，并基于 SS 推断 dd 的性质。直观地说，这意味着应该从具有较高密度值（因此具有较高O-score）的 dd 中抽取更多样本，而不是从具有较低密度值的 dd 中抽取样本。在我们的情况下，样本是一个简化的程序 p′∈Sub(p)p'∈Sub(p) 。为了抽取这样的样本，我们使用 *Metropolis-Hastings（MH）*算法[7]，给定当前样本 pi′p'_{i} ，定义新样本pi+1′p'_{i+1}被接受的概率为：

    A(pi′→pi+1′)=min(1,f(p,pi+1′)∗q(pi′,pi+1′)f(p,pi′)∗q(pi+1′,pi′))=min(1,exp(k∗O(p,pi+1′))∗q(pi′,pi+1′)exp(k∗O(p,pi′))∗q(pi+1′,pi′)) \begin{aligned} A(p'_i \rightarrow p'_{i+1}) &= min(1,\frac{f(p,p'_{i+1}) * q(p'_i,p'_{i+1})}{f(p,p'_i)*q(p'_{i+1},p'_i)}) \\ &=min(1,\frac{exp(k*O(p,p'_{i+1})) *q(p'_i,p'_{i+1})}{exp(k*O(p,p'_i)) *q(p'_{i+1},p'_i)}) \end{aligned}
    其中 q(pi′,pi+1′)q(p'_i,p'_{i+1}) 是从 pi′p'_i 到 pi+1′p'_{i+1} 的转移概率. 当转移是对称时(例如 q(pi′,pi+1′)=q(pi+1′,pi′)q(p'_i,p'_{i+1})=q(p'_{i+1},p'_i) ),被接受的概率称为
    A(pi′→pi+1′)=min(1,exp(k∗O(p,pi+1′))exp(k∗O(p,pi′)))A(p'_i \rightarrow p'_{i+1})=min(1,\frac{exp(k*O(p,p'_{i+1})) }{exp(k*O(p,p'_i)) })

  • 总的MH算法从样本 p0′p_0' 开始,随后迭代执行以下步骤

      1. 从 pi′p'_i 中随机生成一个新的样本 pi+1′p'_{i+1}
      1. 计算 A(pi′→pi+1′)A(p'_i \rightarrow p'_{i+1})
      1. 以概率 A(pi′→pi+1′)A(p'_i \rightarrow p'_{i+1}) 接受 pi+1′p'_{i+1} ,否则拒绝 pi+1′p'_{i+1} ,并保持 pi′p'_i 作为下一个样本

  • 下图明确了DEBOP使用的MH算法

    • 1到5行初始化,6到21行是迭代
    • 在每次迭代中,从当前样本 psps 突变到一个新样本 ps′ps' ,有两种方式
        1. 从程序中随机选择一个语句
        1. 从 psps 中加入或删除这一语句(7-11行)
    • 随后算法根据公式 计算接收概率,直到产生样本数为n个

4 概念验证评估

  • 探究两个问题
    • RQ1:当提供不同的 α,β\alpha,\beta 参数时,DEBOP的产生的简化程序在sr,ar,g之间如何权衡?
    • RQ2:DEBOP的简化与具体单目标的简化方法相比如何

实现

  • 用C++实现DEBOP原型
  • 使用Clang构建p的AST来识别其语句
  • 用(GCC v7.4.0 -O3) 编译简化程序后的运行大小来衡量程序大小
  • 使用ROPgadget来识别程序的gadget数量,衡量程序攻击面

实验设置

  • ChiselBench
  • 设置1s超时限制,防止未终止
  • 设置1000个样本,k=50来计算期望概率

4.1 RQ1结果

RQ1

  • 当 α\alpha 增加时,sr更接近ar,因为生成的程序更倾向攻击面减少
  • 当 β\beta 增加时,即更重视通用性,g增加而sr,ar减少
  • 以上结果证实了DEBOP可以在简化过程中进行不同的权衡

4.2 RQ2结果

RQ2

  • 由于空间限制,只展示每个 α\alpha 下Debop的分数和Chisel分数的比率,这些比率是在考虑的九个β值上计算得出的平均值和标准差。

  • 上表的扩展版本可以在网上找到。

  • 与Chisel进行对比

    • DEBOP在sr,ar,g之间权衡,而Chisel只考虑sr
    • 在sr上,Chisel比Debop好
    • ar,g上,Debop比Chisel好

  • 且Debop后续可以再改进

5 相关工作

  • 很少有简化的工作考虑多个目标,我们的方法基于MCMC技术用多目标思想来考虑这一问题
  • 我们的工作也与用MCMC解决其它问题有关,如超优化[20],以及更广泛的使用遗传算法来改进软件的技术[16]

6 结论和未来工作

  • 我们提出了一种新的通用的程序去膨胀方法,将其视为多目标优化问题

  • 并且我们提出了DEBOP,为我们方法的一个具体实例,考虑了三个去膨胀目标,并使用MCMC技术来解决它.

  • 最后，我们通过概念验证评估展示了我们方法的可行性和潜在用途

  • 未来工作,除更广泛的评估外

    • 我们将研究如何通过使用(1) 除语句之外的其它变异元素(2)基于程序结构的变异,来改进算法
    • 同样计划研究其它采样算法(Gibbs sampling[10]),其它随机搜索算法 (genetic programming[15]) 来进行优化
    • 在更长期和更广泛的未来研究方向上，我们提出的方法具有通用性，可以应用于去臃肿之外的领域。特别是，我们计划在我们的方法的背景下研究资源适应[8]、能源减少[21]和程序修复方面的应用。