@inproceedings{liu2024minimon,
  title={MiniMon: Minimizing Android Applications with Intelligent Monitoring-Based Debloating},
  author={Liu, Jiakun and Zhang, Zicheng and Hu, Xing and Thung, Ferdian and Maoz, Shahar and Gao, Debin and Toch, Eran and Zhao, Zhipeng and Lo, David},
  booktitle={Proceedings of the IEEE/ACM 46th International Conference on Software Engineering},
  pages={1--13},
  year={2024}
}

MiniMon

0 ABSTRACT

  • 为了满足多样的用户需求，安卓应用的大小正变得越来越大。然而，并不是所有应用的功能是被特定用户所期望的。不必要的或不期望的功能增多了攻击面，消耗系统资源如存储和内存。为了解决这一问题，我们提出了一种框架 MiniMon 基于特定用户与APP的交互的日志来从安卓应用中去除不必要功能。
  • 然而，很少使用的功能在数据收集中可能不被记录，并且用户的偏好可能随时间变化。为此，我们内嵌了几种措施在我们的框架中，可以通过学习和泛化用户与应用交互的日志揭示用户期望的功能。
      1. MiniMon首先收集应用的方法，他们在用户交互时被调用。
      1. 随后给定收集的运行方法及应用的调用图，MiniMon使用10种技术来泛化这些日志，辨别出与日志记录方法相似的额外的方法
      • 3种基于程序分析的技术
      • 2种图聚类的技术
      • 5种图内嵌技术
      1. 最后，MiniMon通过移除与运行方法不相似的方法后，生成一个简化后的程序。
  • 为了评估MiniMon使用不同泛化技术后不同的变现，我们为受控实验创建了一个基准。
    • 结果显示，基于图内嵌的泛化技术最为全面地考虑了调用图中的所有结点，并且可以正确地揭示75.5%未被观测到但期望的行为，同时简化了APP超过一半。
  • 我们还进行了一项用户研究，发现使用 MiniMon 的智能（泛化）方法可将用户总体满意度提高 37.6%。

1 INTRODUCTION

  • 安卓在移动操作系统具有统治地位，占据71.95%的市场[4]。
  • 随着CPU性能和移动设备存储的提升，安卓应用由于开发者为了满足各式的用户而普遍提供很多功能（a feature is -functionality that satisfies a certain requirement [59]），这导致了应用变得庞大。
    • 如，Twitter的大小为108MB。用户可以使用 Twitter 发布推文、转发推文、回复、分享、探索热门话题，甚至进行有声交流 [6,13] 。
  • 然而，并非应用所有的功能被用户所需要，这将导致应用的膨胀。旋前研究展示了软件产品中平均80%的功能很少或从未使用[15]。这些不使用的功能提升了攻击面并且消耗了额外的资源，如内存和存储[22]。更具体的，确定的功能对一些用户很必要，但对另一些用户可能不重要。如图1示，“书签”功能是否需要每个用户各异，每个用户都有自己的偏好。
  • 为了解决用户的期望与使用更多功能吸引用户之间的矛盾，先前的研究已经提出了很多措施来简化安卓应用，如通过移除特定功能（如按照活动，权限，模块的粒度），或通过静态[44]或动态[51]移除死代码。
    • [43]提出一种基于UI的方法移除用户选定的不需要的UI组件及相关的后端代码。他们需要用户手动地标记不想要的组件。然而，从所有组件种标识不需要的组件时困难的，因为 （1）组件会动态地创建[14],（2）很难获得应用的所有组件。
    • 现有最优秀的方法在活动层面都没有较高的覆盖度68%[47]，更不用说组件级别。因此，这里存在用户从未探索到的不需要的组件。用户不会意识到这些功能的存在，只会把这些功能认为是不需要的功能。
    • 因此，这驱动我们需要积极地询问用户需要的功能而不是标记不需要的功能。同时[43]需要开发者手动地获得具体UI组件的id来对应到后端代码。这降低了自动化等级，这驱使我们自动化地讲UI元素对应到后端代码。
  • 为了弥补这一差距，我们提出了MinMon，其可以保留用户需要的功能同时移除终端用户不使用的。
  • MiniMon首先静态地对应用进行插桩。
    • 当用户探索插桩应用时，应用运行的方法记录在日志中。这样我们可以收集 （1）收集用户期望的功能（2）及交互种用户期望功能相应的后端方法。
    • 然而，一些用户的行为在监视中可能没被记录（如与仅使用功能相关的），同时用户偏好可能轻微改变[66]。如图1示，用户可能在监视中不使用 “书签”功能，但在未来可能使用。这驱动我们生成的简化后程序需要包括可见及不可见的用户需要的功能，
  • 为了确定未见的用户行为代表的用户需要的功能，MiniMon生成应用的调用图（call graph，CG）。之后，一种方法是采用半监督学习，利用图节点分类方法预测哪些方法与用户所需的特征相关[39,45,46,50,56,60,67,70].然而，我们无法应用这些解决方案，因为在半监督图节点分类任务中，标注数据中存在不止一个标签，即存在负样本。不幸的是，在我们的任务中，我们只有在用户探索应用时执行的方法，而没有永远不会执行的方法。因此，在给定监控过程中记录的 CG 和特征方法的情况下，MiniMon 需要使用无监督技术识别出所需特征的其他方法。之后，MiniMon可以删除与所需功能的执行无关的方法，并生成一个去浮应用程序。
  • 我们将MiniMon中辨识期望功能的方法的组件称为 MethodGeneralizer.我们需要数据来构建 MethodGeneralizer 模型。然而，目前还没有这样一个数据集，可以记录与一系列类似用户行为相对应的已执行方法。为了解决这个问题，我们在 SARA [40] 的帮助下创建了一个基准，记录了 45 个 Android 应用中 214 种类似用户行为的交互以及相应的执行方法。
  • 基于在监控 45 个应用程序期间记录的执行方法及其相应的 CG，我们探讨了三个研究问题：
  • RQ1：MethodGeneralizer 的不同变体在识别具有所需特征的方法方面效果如何？
    • 我们在 MethodGeneralizer 组件中应用了三种基于程序分析的技术、两种基于图聚类的技术和五种基于图嵌入的技术。我们在基准上对每种方法泛化技术进行了实验评估，评估指标包括回调率（发现具有所需特征的方法的能力）和简化率（被删除方法的比例），以及回调率和简化率的加权调和平均值（即 𝐹𝑑𝑒𝑏𝑙𝑜𝑎𝑡𝐹_{𝑑𝑒𝑏𝑙𝑜𝑎𝑡} ）。
    • 评估结果表明，四种基于图嵌入的技术（Node2Vec 和反文档频率技术，LSTM 除外）在所有指标上都优于基于程序分析的技术和基于图聚类的技术。MiniMon 能将应用程序平均简化 58%，并能使用表现最佳的 MethodGeneralizer 技术挖掘出 76% 的所需特征方法。
  • RQ2: MiniMon可以高效率地简化应用吗
    • 我们在由表现最好的方法泛化器生成地简化后应用复现基准中的交互。
    • 我们对8个应用进行了用户调研，收集了8位用户的使用情况。我们发现88.8%的测试用例复现成功。用户研究结果表明使用MiniMon的智能（泛化）方法使总体用户满意度提高了37.6%。
    • 我们还通过消融研究讨论了表现最佳的方法泛化器技术（基于图嵌入的技术）的最重要组成部分。我们发现，考虑调用图中的所有节点是基于图嵌入的技术中最重要的组成部分。
  • 总之，本文的贡献包括：
      1. 我们创建了一个基准，包括45个安卓应用的214个用户的行为及相关的运行方法
      1. 我们实现了一个基于监督的简化框架MiniMon，尽可能地简化一个程序使其包含用户所需要的功能
      1. 我们提出MethodGeneralizer组件，对于给定监视中的调用图和记录的运行的方法，这是MiniMon辨识期望功能相关的未运行方法的组件。我们使用了10种技术在该组件中并在实验中评估他们的表现。结果显示基于图内嵌的技术可以有效地考虑调用图的全局信息，很好的辨识出期望功能的相关方法。
  • 余下部分结构如下：
    • Section2描述基于监督的简化框架MiniMon及其使用场景。
    • Section3构建MethodGeneralizer，辨识用户期望功能的在使用中未出现的相关方法。
    • Section4描述我们构建基准的过程
    • Section5描述评估设置
    • Section6描述评估结果
    • Section7讨论 MethodGeneralizer中最重要的部分以及对有效性的威胁
    • Section8相关工作
    • Section9总结

2 MINIMON: MONITORING-BASED DEBLOATING FRAMEWORK

  • 图2展示MiniMon的概要
    • 1.1 插桩（instruments，insert code）安卓应用程序监视运行，用户探索插桩程序（section 2.1）
    • 1.2 MiniMon使用静态分析得到应用调用图（section 2.2）
    • 2 基于调用图和记录的运行方法，MethodGeneralizer组件辨识出用户期望功能的额外方法（section 3）
    • 3 最后MiniMon修建对于期望功能不需要的代码指令(section 2.3)

2.1 Instrumenting Android Applications

  • （函数或方法级别简化原因）我们关注监视过程中运行的方法。这是因为：
    • 如果我们只关注类的层面，就无法对应用程序进行细粒度拆解：许多函数可能只与单个方法相关。
    • 如果我们关注指令级别，我们需要记录太多信息，需要大量存储。
    • 因此，我们详细函数粒度是一个合适的选择
  • 因此需要静态插桩安卓应用程序.
    • 不能使用现实中基于源码的监视用户的插桩工具(如Amplitude[18],Dynatrace [1]),因为我们没有app源码
    • 不能使用动态插桩,太费工作.如(1)root权限安卓设备(2)运行应用时链接电脑[6].
  • 因此,我们使用Soot中BodyTransformer类静态地插桩程序,通过插入(1)方法签名(2)时间戳(3)应用名再每个方法的第一个指令前[7].一旦方法运行,插入的代码会被运行,方法签名,时间戳和应用名将会被记录
  • 在我们的实验中,我们使用Logcat从安卓模拟器中收集数据.实际上,我们要求用户从GooglePlay下载Logcat记录工具. 与其它现实用户常用的监视工具类似,日志将会在安卓设备的RAM中缓存,并被成块的写入磁盘以最小化影响应用的性能.

2.2 Generating Call Graph

  • 我们使用 FlowDroid 进行静态分析来生成CG.CG中的节点代表方法,边代表方法间的关系(如调用者和被调用者)
  • 跟随之前的研究,我们使用(1)安卓组件中(如活动)的生命周期方法(如onCreate(),onStop())(2)回调(如位置更新或UI交互),作为应用的入口[19,59].
    • 在安卓中,生命周期方法是组件的标准入口.安卓中回调函数的运行(更新位置或点击按钮)回触发应用代码的运行.之后,我们可以将具体的方法调用构建在调用图中CG[54].
  • 然而,安卓应用也支持模糊方法调用.
    • 如反射,为了识别反射的目标,我们识别了所有传播的字符串常量[19].
    • 对于组件间通信（即 ICC），我们使用 ICCBot 来检测应用程序中的 ICC [68].与传统的 ICC 解析工具（如 Epicc [49] 和 IC3 [48]）相比，ICCBot 是一种片段感知且对上下文敏感的 ICC 解析工具。
    • 对于异步任务，我们沿用 Tang 等人[59]的方法，在 CG 中添加以下边：AsyncTask.execute() → onPreExecute，以及 onPreExecute→doInBackground 等。

2.3 Debloating Android Application

  • 在识别出需要保留和删除的方法后(在Section 3),我们使用Soot从安卓应用中移除需要移除的方法.
  • 依据之前的简化Java程序的研究[27],对于每个需要移除的方法,我们提供两个选择(1) 情况函数体并改变返回值为null或0.(2) 替换函数体为标识功能已被移除的代码
    • 基于之前的研究[27],我们默认为第一个选择,我们在Section 6中展示地也是这个选择.
  • 我们没有改变应用的UI元素,所有用户可以看到之前的特征.
  • 注意到基于图内嵌的方法(在Section 3) 计算了所有应用方法与监视地运行方法间地相似度.我们设置了一个相似阈值,对于每个阈值,我们识别出了相似方法集合.这表明了我们由多个方法的集合,每个集合关联一个阈值.因此,对于图内嵌方法,我们会有多个不同阈值的简化版本的安卓应用.

2.4 Usage Scenario

  • 图3展示了与样例应用的可能交互(Amaze File Manager).
  • 考虑用户Bob,他想要浏览在Amaze File Manage的本地应用.使用我们工具,Bob下载完整的 AFM APK.用户不想要的功能,如链接FTP,会加载进内存.这些额外的功能会消耗Bob手机额外的电源和存储.如果Bob使用我们的工具,Bob可以简化APK,使其只包含Bob想要的功能.
  • 更具体的,Bob需要首先下载插桩APK的应用,随后日常使用.随后,Bob放松日志到我们的服务,我们的服务会发送使用不同相似度阈值的简化后的AFM APL给Bob. Bob会基于他的风险偏好和试错意愿选择下载的APK.
    • 如果关注大小和安全更多,选择简化程度最高的.同时如果简化过于苛刻,也可以选择其它程度的简化.
    • 如果Bob不想试错,就选择APK相对简化的,这样就可以执行与功能稍有关联的行为。

3 METHODGENERALIZER: GENERALIZING DESIRED METHODS

3.1 Our Task

  • 对于给定的方法集合 MM ,其包含了应用中所有方法. 集合 mm 为记录到的用户使用应用时运行的方法.我们的目的是找到集合 M′M' ,包含用户所有想要的功能(而并不是单纯地从方法记录标记功能[17,20,37,65]).
  • 通过这样我们可以找到很少使用,但用户期望的,收集的方法中没有的功能.更具体地 m⊆M′⊆Mm\subseteq M' \subseteq M

3.2 Our Techniques for MethodGeneralizer

  • 先前关于程序理解研究表明[16,23,41,55,58,61],使用方法-调用关系来推断特征相关性是有效地.例如，Biggerstaff 等人[23] 和 Alanazi 等人[16] 使用方法调用关系来识别源代码和特征之间的映射关系。
  • 受这些研究的启发，我们使用方法调用关系来推断特征相关性。我们考虑了三种基于程序分析的技术（即forward-slicing, backward-slicing, and forwardbackward-slicing）[62]，两种基于图聚类的技术（Louvain community detection [25], and Label propagation algorithm[71]），以及五种基于图嵌入的技术（node2vec[39], LSTM [42], OneHot Encoding, IDF-Encoding, and IDF-POSencoding）作为 MethodGeneralizer 的候选技术。

3.2.1 Program analysis-based techniques

  • Forward slicing: (简称 FORWAER)
    • 直觉地,如果方法m正在运行,被方法m调用的方法未来也会被执行.
    • 例如,如果两个方法被同一个方法集合调用(如,被同一个入口点调用),他们应该是相似的(如,在Amaze file manager中打开不同类型的文件)
    • 更具体地,我们直接将 mm 调用的方法加入到 M′M'
  • Backward slicing:(简称 BACKWARD)
    • 直觉地,如果方法 m 正在运行,调用m的函数在未来可能被执行(多入口点)
    • 类似的,如果两个方法钓友同一个方法集合,这两个方法是相似的(如,在FTP活动中使用FTP功能与FTP按钮)
    • 更具体地,我们将直接或简介调用 m 的方法加入到 M′M'
  • Forward and backward slicing:(简称 BIDIRECTION))
    • 以上2者的结合

3.2.2 Graph clustering-based techniques

  • Louvain community detection algorithm(简称 LCD)
    • 根据面向对象编程的原则，具有高内聚性和低耦合性（即高模块性）的方法可被视为一个模块。
    • 我们将程序中的模块视为用户的一项功能，并采用 LCD 算法来识别模块。
    • LCD 算法首先将每个节点分配到其社区中。然后，该算法会反复判断将节点移至其相邻社区是否能获得更好的模块化效果。如果是，该节点就会被移到它的邻近社区。
  • Label propagation algorithm:(简称 LPA)
    • 直觉是方法的执行过程与标签传播类似。即如果其邻居被执行，那么该方法就有可能被执行。因此,接可以使用LPA识别类似的方法
    • 更具体地,LPA为每个节点初始化唯一的标签,然后重复设置节点的标签,使其称为邻居中出现频率最高的标签.
    • 我们沿用Tang等人的工作,设置边权0.5或1. 前者表示单向调用(如 n调用m或m调用n),后者表示双向调用(n调用m且m调用n).
    • 我们使用LCD和LPA在CG上,其它参数设置默认如[9,10]. 如果由LCD或LPA生成的运行的方法,我们加入到 M′M'

3.2.3 Graph embedding-based techniques

  • 这里我们(1)生成CG中每个方法的嵌入的东西然后(2)这用这些嵌入的东西来识别用户期望的但未收集到的可能的方法.

  • 直觉上,如果我们可以将CG中多维度的信息(如结构信息,调用关系)到低维度的向量空间,我们可以使用这些信息更好地识别出期望的方法.

  • 如图4示,我们是要首先探究如何通过将CG转换为序列来生成方法嵌入.

    • 具体地,为了生成CG中每个方法的嵌入,我们(1)首先将图结构转换为序列(2)使用4种技术(LSTM,One-hot,IDF,IDF-POS) 来为每个序列的每个方法生成嵌入.然后(3)统计每个方法在序列种的所有嵌入得到每个方法的最终嵌入.

  • 我们同时也使用一个属性的图嵌入技术Node2Vec[39],来直接地生成CG种方法的嵌入,我们使用cosine similarity来识别用户期望功能的额外方法.

  • 生成静态运行路径

    • Static Execution Path 是方法序列,被CG中的边链接.
    • 静态运行路劲的第一个方法是应用的入口点(入口点入度为0).随后使用DFS在CG上获得静态运行路径.为了解决递归,每条边只遍历一次.
    • 图4展示了样例CG和静态运行路径,这样我们可以将图结构转化为序列结构,同时保持图的拓扑序.例如,CG中度数高的节点会分布在很多静态路径中,静态路径记录了所有可能的路径

  • 生成在静态运行路径中每个方法的嵌入

    • 运行路径:因为静态运行路径代表了CG的信息,我们希望利用静态执行路径的嵌入来获得 CG 中方法的嵌入。具体来说，我们探索了以下技术：

  • 1 LSTM

    • 是一种递归神经网络,可以学习序列中的长期依赖关系[42].
    • 我们将静态执行路径视为一个序列,并使用LSTM模型来学习执行路径中方法之间的长期依赖关系。我们使用 LSTM 模型的最后一个隐藏状态作为执行路径的嵌入。
    • 具体来说，对于静态执行路径中的每个方法，我们将其分为两部分，即直接调用该方法的路径（即调用者路径）和被该方法直接调用的路径（即被调用者路径）。
    • 然后，我们使用 LSTM 模型分别生成调用者路径和被调用者路径的嵌入。最后，我们将这些嵌入连接起来，作为该路径中方法的嵌入。

  • 2 One-hot

    • 将路径中所有节点考虑编码.对于路径中的每个方法,其嵌入与上下文一起考虑:
      Embedding(𝑚𝑖)=[1(𝑚1),...,1(𝑚𝑖−1),0,1(𝑚𝑖+1),...,1(𝑚n)]Embedding(𝑚𝑖 ) = [1(𝑚_{1}), . . . , 1(𝑚_{𝑖−1}), 0, 1(𝑚_{𝑖+1}), . . . , 1(𝑚_n)]
      1(𝑚𝑗)1(𝑚_𝑗) 是方法 𝑚𝑗𝑚_𝑗 的指示函数。如果方法 𝑚𝑗𝑚_𝑗 是在 𝑚𝑖𝑚_𝑖 的语境中，则 1(𝑚𝑗)=11(𝑚_𝑗) = 1；否则，1(𝑚𝑗)=01(𝑚_𝑗) = 0。

  • 3 IDF

    • 如果一个方法在静态运行路径中普遍被执行,那么其应该在嵌入中权值较低.
      • 例如,一个工具方法,如 amaze file应用中重写 ImmutableEntry class,在静态执行路径中被普遍执行.ImmutableEntry class在Map class运行时会频繁地被运行.当 ImmutableEntry class 在一个具体的功能中被运行时,这并不意味着用户会使用其它功能.
      • 相反,⟨𝑐𝑜𝑚.𝑎𝑚𝑎𝑧𝑒.𝑓𝑖𝑙𝑒𝑚𝑎𝑛𝑎𝑔𝑒𝑟 .𝑎𝑠𝑦𝑛𝑐ℎ𝑟𝑜𝑛𝑜𝑢𝑠.𝑠𝑒𝑟𝑣𝑖𝑐𝑒𝑠.𝑓 𝑡𝑝.𝐹𝑡 -𝑝𝑆𝑒𝑟𝑣𝑖𝑐𝑒 : 𝑣𝑜𝑖𝑑𝑟𝑢𝑛()⟩ 方法在静态路径中很少被执行(52/12363 静态运行轨迹). 该方法的运行表示用户使用了FTP链接功能.这驱使着我们将方法频率纳入生成方法嵌入的考量中.
    • 受信息检索中 IDF（inverse document frequency）的启发，我们将一种方法的反向文档频率（IDF）定义为 IDF(𝑚)=log𝑁𝑛𝑚IDF(𝑚) = log \frac{𝑁}{𝑛_𝑚} 。包含方法的静态执行路径越多，方法的 IDF（即重要性）就越小。方法的嵌入为
      Embedding(𝑚𝑖)=[1(𝑚1)×IDF(𝑚1),⋅⋅⋅,1(𝑚𝑖−1)×IDF(𝑚𝑖−1),0,1(𝑚𝑖+1)×IDF(𝑚𝑖+1),⋅⋅⋅,1(𝑚𝑛)×IDF(𝑚𝑛)]Embedding(𝑚_𝑖) = [1(𝑚_1 ) × IDF(𝑚_1 ), · · · , 1(𝑚_{𝑖−1})×IDF(𝑚_{𝑖−1} ), 0, 1(𝑚_{𝑖+1} ) × IDF(𝑚_{𝑖+1} ), · · · , 1(𝑚_𝑛 ) × IDF(𝑚_𝑛 ) ]

  • 4 IDF-POS

    • 考虑的是相对于到嵌入节点的位置信息。如果一个方法被执行，那么离嵌入方法较近的方法比离嵌入方法较远的方法更有可能被执行。
    • 我们定义方法 mqm_q 在方法 mpm_p 的嵌入贡献为 $ Weight \frac{m_q}{m_p} = \frac{q}{p} if(q<p) or \frac{(n-q+1)}{(n-p+1)} (if q>p)$
    • 因此我们有
      Embedding(𝑚𝑖)=[1(𝑚1)×IDF(𝑚1)×Weight𝑚𝑖1,⋅⋅⋅,1(𝑚𝑖−1)×IDF(𝑚𝑖−1)×Weight𝑚𝑖𝑖−1,0,1(𝑚𝑖+1)×IDF(𝑚𝑖+1)×Weight𝑚𝑖𝑖+1,1(𝑚𝑛)×IDF(𝑚𝑛)×Weight𝑚𝑖𝑛] Embedding(𝑚_𝑖) = [1(𝑚_1)×IDF(𝑚_1)× Weight^1_{𝑚_𝑖} , · · · ,1(𝑚_{𝑖−1}) × IDF(𝑚_{𝑖−1} ) × Weight^{𝑖−1}_{𝑚_𝑖} , 0, 1(𝑚_{𝑖+1} ) × IDF(𝑚_{𝑖+1} )× Weight^{𝑖+1}_{𝑚_𝑖} , 1(𝑚_𝑛 ) × IDF(𝑚_𝑛 ) × Weight^𝑛_{𝑚_𝑖}]
    • Aggregating Embedding From Each Path
      • 图四展示了一个方法可以在不同的静态执行路径中.这可能导致每个方法在每个静态路径上的嵌入不同.因此,我们将不同静态执行路径的嵌入聚合在一起，以获得特定方法的嵌入
      • 为此,我们取每个方法在每个静态执行路径上的最大嵌入值为确定方法的嵌入值(如最大池).通过这种方法的嵌入是静态执行路径中方法上下文中最重要的方法。

  • 5 Node2Vec (简称N2V)

    • 直接将图中点映射到低维向量空间(没有用图4描述的过程)
    • 不同于之前提到的技术使用DFS生成序列,N2V基于随机游走将图转换为序列.然后使用神经网络.
      • 如 Word2Vec 为了基于序列生成嵌入,从而从附近 k 个窗口的标记中捕捉图的属性。当 Node2Vec 的参数设置足够大时，它将生成从入口点到终点的序列（与我们的方法相同），并且可以从整个图的信息中获得一种方法的嵌入（与我们的方法相同，但嵌入技术不同）： Node2Vec 采用的是 Word2Vec，而我们使用的是 IDF 信息）。我们使用 Node2Vec 的默认设置，输入为 CG [31]。
    • Finding Similar Methods:
      • 在获得方法的嵌入后,给定运行的方法集合 mm ,我们需要找到用户期望的功能的所有方法集合 M′M' . 如果我们训练了一个预测模型使用 (半)监督方法,在训练数据集中,在 mm 中的方法标记为1,没有数据标记为0(即这里没有方法不会被用户运行). 所以这驱动我们使用无监督方法来通过 mm 找到 M′M'
      • 此外,不同用户对简化有不同看法.
        • 例如,一些用户可能会使用不同的功能实现同一个目标(如 用户可以使用FTP功能,通过不同的入口,如FTP活动,FTP链接按钮,FTP 片段);或应用同一行动包含不同功能(如amazi file manager中不同的文件类型). 这指示我们这些用户对某个功能有多种行为,所有我们需要给他们更大的 M′M'.
        • 另一些用户可能更喜欢使用与我们收集数据时相同的功能。这表明这类用户对该功能的使用行为较少，我们需要为他们提供较小的 𝑀′。
      • 在我们的工作中,我们使用Cosine similarity计算 所有方法与运行方法嵌入的相似度.
        • Cosine similarity设置不同的阈值,可以获得不同大小的M’,用户可以选择.

4 BENCHMARK CREATION

  • 基准构造原理: 一个用户可能只运行了期望功能的子集,MiniMon需要泛化这个子集找到期望功能的所有行为.为了测试MiniMon的泛化能力在大量应用和功能中的情况,我们构建了一个基准.
    • 基准中,对于每个应用,我们定义了一组功能.对于每个功能,我们识别相对应的用户行为.
      • 例如 “Open File” 是图3中左部分代表的功能.其可能包括的行为有 “open a PDF file”, “open a text file”, “open a PPT file”.
    • 对于给定的功能 FF , 及其相关的用户行为 LFLF,我们获得了 LFLF 的子集 LF′,LF′⊆LFLF',LF'\subseteq LF,并将其给到MiniMon. 随后我们观察MiniMon揭示的在 LF−LF′LF - LF' 中出现的方法.这些方法与目标所需功能所需的方法相对应，但在用户与应用程序之前的交互过程中并未观察到。
  • 程序来源: 我们从Google Play中收集了45个应用程序.
    • 这些应用在AndroidRank排前40.
    • 这些应用程序的平均反编译代码行数为 15,318 行，最多可达 67,312 行.这一平均行数大于先前简化研究的基准应用程序的平均代码行数[27,53]
    • 如果用户只使用某些功能，应用程序就可以被视为臃肿；未使用的功能不会给用户带来任何好处，而且出于安全[24,38,52,57]和其他原因，这些功能可以被省略。
  • 基准具体构造: 对于每个应用程序，我们希望收集一组类似的用户行为。根据 Material Design 指南[11]、同一活动中的小部件更有可能相互关联[69].因此，我们将同一活动中的小部件视为一组相似的用户行为。
    • 在上述启发式方法的基础上,我们创建了测试用例,以捕捉应用程序功能相关的用户行为.我们使用SARA[40]记录测试用例.
      • SARA是一种记录和重放工具.可以(1) 根据屏幕坐标记录运动事件，(2) 根据屏幕坐标和部件重放记录的事件。
    • 我们第一第二作者记录了程序的启动,确保了简化后程序的正确运行.然后,作者启动一个活动,并且与其中一个小部件进行交互.如果小部件触发了对话框,那么作者会选择一个选项或直接关闭对话框并存储测试用例.这些都是随机完成,如果选项启动了一个新的活动或没有任何其他弹出窗口，我们将直接停止
    • 请注意，每次开始生成新的测试用例时，我们都会重新安装应用程序，以避免不同的初始条件影响已记录的测试用例。因此，对于每个功能，我们都会根据目标活动中部件的数量生成 4 到 6 个测试用例（共 214 个）。
    • 对于每个应用程序，探索、生成和记录测试用例通常需要 30 分钟。最后，我们使用 SARA 来重放插桩应用程序的用户行为，并收集运行过程中执行的方法,

5 EVALUATION SETUP

  • 这里介绍实验设置和评估指标

5.1 试验设置

  • MethodGeneralizer将监视中记录的方法作为输入(即集合 mm ), 来辨识期望功能的其它方法 (即集合 M′M' ).
  • 为了评估 MethodGeneralizer 的性能，我们随机选取一个用户行为（启动应用除外）中的方法作为未见用户行为（ 𝑚𝑡𝑒𝑠𝑡𝑚_{𝑡𝑒𝑠𝑡}，即测试集）中的方法。然后，我们将其他用户行为中的方法作为监测过程中记录的执行方法（𝑚𝑚，即输入）。我们为每个应用反复选择测试集和执行方法𝑚，直到测试集中有额外的方法为止（即 𝑡𝑒𝑠𝑡⊄𝑚𝑡𝑒𝑠𝑡 ⊄ 𝑚 ）。

5.2 评估指标

  • 使用 recall召回率,简化率,二者的加权平均 作为评估MethodGeneralizer识别期望功能的指标
  • recall
    • 当用户运行未见过行为时(运行 mtestm_{test}),我们需要评估 M′M' 中的方法是否满足用户的需求,如(mtest⊆M′m_{test} \subseteq M'). 这驱动我们使用racall召回率作为评估指标.
    • 一个方法的recall的定义是指认 M′M' 中正确方法的能力:
      recall=∣mtest∩M′∣∣mtest∣recall = \frac{|m_{test} \cap M'|}{|m_{test}|}
      我们需要最大化recall的值,包含尽可能多的未见过行为
  • debloating rate
    • debloating rate为方法移除 MM 中方法的能力:
      debloating \; rate = \frac{|M|-|M'|}
    • 我们需要最大化简化率.我们并不考虑准确值,因为我们不知道与用户特征无关的方法.因此,我们无法计算准确度,只能用简化率代替准确度.
  • trade-off
    • 保留更多的方法导致较校的简化率.我们想要平衡二者,二者中,recall比简化率更重要,因为我们想要用户在使用应用时至少不会崩溃.
    • 基于标准的 FβF_{\beta} 分数,如 fβ=(1+β2)×precision×recallβ2×precision+recallf_{\beta} = (1+\beta^2) \times \frac{precision \times recall}{\beta^2 \times precision + recall},我们定义 FdebloatF_{debloat} 分数为recall和debloating rate的加权平均.我们设置 β=1/2\beta = 1/2 给recall更高权重.
      Fdebloat=5×recall×debloating  rate4×recall+debloating  rateF_{debloat} = \frac{5 \times recall \times debloating\;rate}{4\times recall + debloating\;rate}
      高 FdebloatF_{debloat} 值意味着可以同时实现高简化率和高recall,同时我们对recall权重较高.

6 EVALUATION RESULT

6.1 MethodGeneralizer 的不同变体在识别具有所需特征的方法方面效果如何

设计

  • 不同变体间比较,同时与不使用泛化的基线比较(移除未运行的方法)
  • 注意到使用图内嵌技术时,MethodGeneralizer 会生成不同的 M′M' 集合,每个关联不同的阈值.我们选择 F_{debloat} $ 最高的 $M' 集合作为应用的最终结果.

结果

  • 图5展示了三种指标的结果,“.” 表示平均值
    • 图内嵌技术(除LSTM)比其它技术在所有指标上都表现好
    • 且差异在统计学上有很大意义（P 值小于 0.05 且效应大小很大）。
    • 我们使用 Wilcoxon 符号秩检验来比较 MiniMon 变体的性能，并使用 Bonferroni 校正来调整 p 值 [33, 63]。我们计算 Cliff’s delta 来衡量效应大小[30]。
      • Bonferroni 校正用于抵消多重比较的问题。
      • Cliff’s delta 是一种非参数效应大小测量方法，用于评估两组之间的差异量。Romano 等人将小于 0.147、介于 0.147 和 0.33 之间、介于 0.33 和 0.474 之间以及大于 0.474 的绝对 delta 分别定义为 “可忽略”、“小”、"中 "和 "大 "效应大小[30]。
  • 基于图嵌入的技术（LSTM 除外）之间没有明显差异。
    • N2V、Onehot、IDF 和 IDF-POS 的平均 𝐹𝑑𝑒𝑏𝑙𝑜𝑎𝑡𝐹_{𝑑𝑒𝑏𝑙𝑜𝑎𝑡} 分别为 62.82%、64.44%、64.77% 和 64.95%。
    • 这表明这些特征对这项任务的影响不大。不过，考虑到平均 𝐹𝑑𝑒𝑏𝑙𝑜𝑎𝑡𝐹_{𝑑𝑒𝑏𝑙𝑜𝑎𝑡} 的改进，我们将 IDF-POS 作为最佳方法泛化技术。
    • IDF-POS最坏情况,相似阈值为0.1,也比不基于图嵌入的技术表现好。
    • 结论： 图嵌入技术在本任务中展示出了很大的优势，不论节点如何嵌入（不论idf信息或使用word2vec）。未来研究应继续在该方向，在CG的方法上生成更好的基于图嵌入的表示
  • 除图嵌入技术外，BIDIRECTION在 𝐹𝑑𝑒𝑏𝑙𝑜𝑎𝑡𝐹_{𝑑𝑒𝑏𝑙𝑜𝑎𝑡} 平均上表现最好。
    • 这意味着简单的将CG所有可达方法纳入考虑是一个直觉地且有效地方法。然而其在简化率上表现较差，因为引入了过多用户不期望功能地方法。
    • 相反，FORWARD表现最差
    • 结论： 当决定两个方法是否相似时，调用这两个方法地调用者与被这两个方法调用的被调用者更重要。
  • 除图嵌入技术外，LCD是在 𝐹𝑑𝑒𝑏𝑙𝑜𝑎𝑡𝐹_{𝑑𝑒𝑏𝑙𝑜𝑎𝑡} 平均上表现第二好的。
    • 其回调率高，简化率较低。
    • 这告诉我们 应用的模块可以高效地辨认出用户功能相关的方法。然而，LCD辨识的模块太粗粒度，导致简化率较低
    • LPA表现比LCD差，因为LPA只考虑了本地邻居，并没有反映正确的运行顺序
  • LSTM表现最差之一。
    • 这是因为LSTM目的是抓取方法在静态运行路径中出现的样式，而不是每个方法在静态执行路径中的权重。导致其简化率很低。
    • **结论：**在静态路径中方法出现的样式对辨识相似路径贡献有限。

6.2 MiniMon可以高效率地简化应用吗

  • 报告反编译后移除的代码的百分比。

  • 同时评估简化后程序是否能正常使用，使用SARA回放Section 4中的操作，将简化后程序与原始程序进行比较。

  • 我们同时进行了一个用户调研，探究我们方法的有效性。

    • 在我们的机构以多种方法向人们进行调研。如线上聊天频道。这个过程类似于 prior study[35]。
    • 当有人对此产生兴趣时，我们选出8个应用，让用户选择一个他熟悉的使用。
    • 8个毕业生参与其中。他们安卓使用经验丰富，对所有软件熟悉。
    • 我们的用户调研的规模喝参与者与之前研究类似[21,28,29,34-36]
    • 过程：
        1. 我们首先解释简化的理念
        1. 随后选择8个程序，随后插桩程序
        1. 最后我们得到8*8 = 64个数据点，来自真实用户，比之前研究[43,51]用的数据点大。
      • 我们提供指导来帮助用户收集日志，并要求每个用户在3天内使用每个应用5min。（5min长于应用的平均使用时间71.56s[26]，与之前研究设置时间相同[21,29]）
    • 具体过程
      • 第一天，他们被要求自由探索插桩后应用，理解软件功能
      • 第二天和第三天，他们被要求使用插桩应用使用它们想要的功能。我们用这两天的收集的日志进行简化，使用每种技术中最好的方法（LCD，BIDIRECTION，IDF_POS）。
      • 我们要求用户使用每个简化后程序5min，它们不知道每个简化程序对应的技术。
      • 最后我们要求用户对每个简化后应用进行打分1-5（very unsatisifed - very satisified） 。包括
        • （1）可用性：简化后程序保留期望功能到什么程度
        • （2）泛化性：简化后程序保留了他们想要的功能但之前未运行的到什么程度
        • （3）大小：它们对简化后程序的大小变化惊喜到什么程度
        • （4）整体满意度：

  • 结果

    • 简化后程序比原始程序反编译后代码平均减少38.8%。
    • 214个测试用例中，88.8%的测试用例可以在表现最好的MethodGeneralizer简化后程序复现
      • 如 IDF-POS在10个应用中24个测试用例失败。我们深入探究了原因，发现 mm 中的静态路径和 mtestm_{test} 中的没有交集，方法相似度为0。
      • 一个可能的原因是，用户在使用应用程序时可能会出现松动现象，有些方法不小心没有触发，因此无法记录（例如，关闭 Wi-Fi功能在Wi-Fi已经关的状态就不会被触发）
    • 表1展示了用户给的平均分。
      • 用户对IDF—POS产生的简化后程序有很高满意度，除过大小上。
      • 智能（泛化）方法提升了37.6%的总体用户满意度

7 DISCUSSION

7.1 最好MethodGeneralizer分析

  • 调查IDF-POS，N2V。其它图嵌入技术是IDF-POS变体，N2V是最受欢迎的一种
  • 第3.2.3节表明，基于图嵌入的技术首先（1）使用CG中的所有节点生成方法的嵌入。然后它（2）直接将相似度分数高于特定阈值的两个方法视为相似。然而，我们不知道哪个组件是最重要的。因此，我们调查了每个组件在MiniMon中的效果。
  • 我们将每个MethodGeneralizer与其两个变体进行比较：（这种比较可以让我们理解MethodGeneralizer组件的表现）
    • MethodGeneralizer-PART使用每个静态执行路径中邻居的三分之一（而不是全部）节点来生成方法的嵌入。
    • MethodGeneralizer-CLU使用层次聚类来识别相似方法（而不是直接添加相似度分数高于阈值的最近邻居）。每个层次都有一个特定的相似度级别（按照第3节的设置，相似度级别从0到1，步长为0.1），其中包含一组集群。对于每个层次，如果集群中有执行的方法，我们将把集群中的所有方法添加到𝑀′中。
  • 表2为我们的比较结果。我们可以看到IDF-POS和N2V比他们的所有变体表现优秀
    • **结论：**这表明图的全局信息（如考虑图中所有的点）是识别与用户所需功能相关方法的最重要组件。
      • 考虑两个不同UI组件的onclick方法，它们调用了不同的方法，但在CG的长链后，都调用了FTP相关的方法，如果仅考虑局部信息，这两个方法并不相似，因为其调用方法并不相似。但在考虑所有信息后，这两个方法是相似的
      • 当我们在每个静态执行路径中仅考虑邻居的三分之一节点时，性能显著下降，特别是在N2V中。这表明，当Node2Vec中的窗口大小无法覆盖整个图时，N2V的性能会显著下降。未来的研究人员应考虑CG中的所有节点（具有足够大的窗口大小）来生成方法的嵌入。
      • 此外，聚类方法不如简单地将最近邻居添加到𝑀′中有效。一个可能的原因是，聚类方法将集群中的所有方法都识别为相似的方法，这可能引入更多的噪音。

7.2 限制和有效性威胁

  • 本文的发现可能并不适用于所有应用程序。例如，与之前的研究类似[43,59]，我们没有考虑带有篡改检测机制和使用本地代码实现的功能的应用程序。
    • 我们无法修改带有篡改检测机制的应用程序，因为这些应用程序会检测到修改并停止工作[5]。
    • 此外，本论文主要关注dex文件。本地代码实现的功能在dex文件中不可用，需要额外的努力进行分析和修改。我们相信，一旦获得这些应用程序的CG（调用图），我们的MethodGeneralizer组件也可以推广到这些应用程序上。
    • 未来，我们计划在更多的应用程序上评估我们的工作，并研究如何简化带有篡改检测机制和使用本地代码实现功能的应用程序。
  • 在构建基准时，我们使用了一些启发式方法。例如，我们的基准是由作者根据假设创建的，即同一活动中的小部件可能与同一功能相关（基于指南[11,69]），而不是由实际用户创建的。然而，可能存在一些应用程序并不遵循这些指南。我们承认，基准创建过程并不完美，但目前没有其他替代基准。即使是我们创建的当前基准，也需要大量的手工工作。为了减轻不完美基准带来的威胁，我们通过用户研究评估了我们提出的方法，收集了真实用户与应用程序的交互数据。
  • **评估指标：**我们使用简化率、召回率和𝐹𝑑𝑒𝑏𝑙𝑜𝑎𝑡来评估我们的方法。我们没有报告实际的应用程序大小减少情况，因为每个应用程序中的资源占用了大量空间，而本文主要关注的是移除代码（即方法）。我们在真实设备上通过人类进行的真实世界应用程序实验。
  • 用户研究的局限性：我们的用户研究只有8名参与者。然而，这一研究规模在之前的研究中也被采用[21,28,29,34,35,36]。

8 相关工作

  • 安卓应用的简化
  • Google提出了一些减少安卓应用程序大小的方法。例如
    • （1）使用R8静态检测并移除无效代码及其库依赖
    • （2）移除未使用的资源
    • （3）缩短类和成员的名称以减少DEX文件大小[12]
    • 开发者还可以配置App Bundle或使用按需交付，以便只下载特定设备或功能所需的代码和资源[2,8]。
    • 这些方法已成为Android应用程序开发的默认设置，并且可以与MiniMon互补。MiniMon可以在R8之前或之后运行。
  • 我们利用Bruce等人的工作设置，检查我们的实验应用程序是否可以通过这些方法进一步简化。Bruce[27]等人将他们的方法（即JShrink）与ProGuard（使用与R8相同的设置）和其他基于静态分析的方法进行了比较。我们发现没有方法可以被移除。这意味着开发者已经在构建阶段使用了像R8这样的静态工具来简化Android应用程序。尽管如此，我们的研究表明，在这些应用程序中，仍然有大量特定用户不需要的方法，我们的工作对于更好的用户特定应用程序简化是必要的。
  • Xie等人通过简化应用程序来最小化移动网络的带宽消耗。[64]
  • Jiang等人基于静态分析移除无效代码。[44]
  • Tang等人在Activity、权限和模块化级别上对应用程序进行了简化。[59]
    • 为了在模块化级别上进行简化，他们将每个模块视为一个功能，并使用Louvain社区检测来识别CG（调用图）中的模块。
    • 继他们的工作之后，我们也使用了LCD作为我们的一种技术。我们的结果显示，LCD在识别与用户所需功能相关的方法方面不如其他基于图嵌入的技术。
  • Pilgun等人在测试过程中移除了未执行的指令。[51]
    • 我们尝试将MiniMon与Pilgun的工作在指令级别进行比较，但遇到了困难（我们只能在两个示例应用程序上复制他们的结果）。尽管与作者联系，我们仍未能解决问题。Pilgun承诺在更多应用程序上运行他们的工具，但在我们提交论文时尚未兑现。因此，我们实现了一个基线方法，即移除未执行的方法（即EXECUTED）。我们的结果显示，在𝐹𝑑𝑒𝑏𝑙𝑜𝑎𝑡和召回率方面，MiniMon优于EXECUTED。
  • Huang等人提出了一种移除未使用的UI组件的方法。[43]
    • 他们要求用户指定要移除的组件，并使用前向/后向切片技术来识别与UI组件相关的指令，从而消除仅与这些组件相关的指令。然而，我们的工作旨在保留所有已执行的方法，并将其推广到未来的用户行为。与Huang等人不同，我们并不知道哪些UI组件是不必要的。因此，我们的方法与Huang等人的方法有不同的目标，无法直接进行比较。
    • 尽管如此，我们相信EXECUTED基线方法在一定程度上体现了Huang等人的方法，通过记录经过仪器化的应用程序的日志信息来识别与UI组件相关的方法。此外，我们的程序分析技术在前向切片和后向切片方面也部分借鉴了Huang等人的方法。我们有信心已经进行了与Huang等人方法最相关的比较。
  • Qian等人[53]和Xin等人[66]提出了基于单个用户使用情况简化C/C++程序（例如UNIX工具）的方法。
    • 他们首先收集C/C++程序使用时执行的语句日志，然后采用一些扩充技术来识别与已执行语句相关的程序元素。已执行和相关的程序语句被保留，而其余部分被删除。虽然我们的工作动机与这两项研究相似，但存在一些使这些工作互为补充的差异。
    • 首先，Qian等人和Xin等人使用的扩充技术需要在语句级别进行插桩，而我们提出的方法（MiniMon）只需要在方法级别进行插桩，这更轻量，并且带来的性能开销对Android手机用户来说是可以接受的。
      • 此外，由于考虑的插桩级别不同，这两篇论文中扩充技术使用的启发式方法不能轻易应用于MiniMon。
        • 例如，Qian等人的扩充技术包括4种策略：添加额外的分支、可达指令、同一二进制文件内的可达函数或已执行的外部函数，以及具有相同功能的可达库函数。目前尚不清楚这些启发式方法如何应用于MiniMon以识别相关方法。我们认为，考虑所有调用方法作为用户所需功能方法的FORWARD技术在某种程度上体现了Qian等人的方法。
        • 此外，Xin等人扩充技术（CovA）中灵活性的计算需要计算C/C++函数中已执行语句的唯一集合数量。
  • 我们的工作还与特征定位相关。现有的工作主要集中在促进程序理解。在我们的工作中，我们使用监控期间收集的特征来找到与所有用户所需功能对应的方法。我们相信，许多特征定位工作可以适应我们的任务。我们已经将我们的方法与我们领域中使用的一些特征定位方法进行了比较。未来，我们计划探索其他特征定位工作（如果基于无监督学习）以进一步提高性能。

9 结论与未来工作

  • 在本文中，我们旨在根据用户的使用方式简化Android应用程序。为了解决这个任务，我们实现了一个基于监控的简化框架MiniMon，该框架可以在监控时（1）收集执行的方法。然后，结合应用程序调用图，MiniMon中的MethodGeneralizer组件（2）采用三种基于程序分析的技术、两种基于图聚类的技术和五种基于图嵌入的技术来识别所需特征的其他方法。最后，MiniMon（3）通过删除剩余的方法生成简化的应用程序。
  • 为了评估，我们手动创建了一个基准，该基准收集了每个特征执行的方法。使用此基准进行的受控实验突显了考虑调用图中所有节点信息的嵌入式泛化技术是最佳的，可以正确地发现75.5%的所需特征的其他方法，并简化超过一半的应用程序。
  • 我们的用户研究表明，使用MiniMon的智能（泛化）方法将整体用户满意度提高了37.6%。
  • 在未来，我们计划利用其他Android特性来识别与用户所需特征相关的方法。我们还计划使用更多的应用程序和测试用例扩大基准。·

10 开源地址

开源地址

个人总结

  • 在安卓应用中，从函数粒度出发，记录用户期望的功能对应的函数（到这里相当于Cov），随后对这些方法进行泛化（相当于找到功能相关的函数），最后再加上这些泛化后的函数组成简化后程序
  • 本文主要创新点：
      1. 在函数调用图上，使用3种泛化方法，包含10种具体技术，其中基于图嵌入的技术表现最好，达到了最好的简化平衡
      1. 构建了一个安卓简化基准
      1. 用户实际使用来验证结果
  • 可能问题
      1. 基于APK文件的简化，看不到源码，简化的可审计性缺失，工业界是不敢用的
      1. 由于是在apk文件上基于函数级别，所以函数内部还有再进一步简化的可能
      1. 实际没有和其它方法对比，不知道是没有其它方法吗

工具使用

  • new:没文档，真不好搞，感觉不如重新写
  • 自己重新拉依托还是比吃依托好受些
  • 有以下几个文件夹
    • /lib：依赖库
    • /SATA：我们的数据集合
      • 包括APK文件 /apks
      • 记录的交互及复现的脚本/trace
      • 记录的log文件/logcat_repeat
    • /src：源代码位置
      • 首先配置config.java
      • 随后跑/task里的代码
    • /UserStudy 用户调研相关