Group of Software Security In Progress

GoSSIP @ LoCCS.Shanghai Jiao Tong University

Automatic Generation of Non-intrusive Updates for Third-Party Libraries in Android Applications

作者:Yue Duan, Lian Gao, Jie Hu, Heng Yin

单位:Cornell University, University of California, Riverside

出处:RAID’19

原文:https://www.usenix.org/system/files/raid2019-duan.pdf


Abstract

Andrdoid App中普遍存在的第三方库(third-party library, TPL)很少能够得到App开发者的及时更新,过时第三方库中存在的未被修复的安全漏洞使得最终用户面临着极大的安全威胁。这一问题的原因在于,人工更新App中包含的第三方库对于App开发者来说是一件复杂且耗时的工作。

在这篇文章中,作者提出了一种为Android App中包含的第三方库自动化生成非侵入式更新(non-intrusive update)的技术。对于一个包含有过时第三方库的Android App,该技术自动化的更新此过时第三方库,并能够保证此更新是完全向后兼容,且不会影响此第三方库与其它组件的任何交互。

作者实现了一个名为LIBBANDAID的原型,并在9个流行第三方库的83个不同版本以及100个现实存在的开源App上评估了其有效性。实验结果表明,LIBBANDAID能够成功修复平均80.6%的安全漏洞,在进一步结合潜在可修复漏洞(potentially patchable vulnerability)的情况下,该工具能够成功修复平均94.07%的安全漏洞。

1 Introduction

对于Android App的开发者来说,更新App中包含的第三方库是一件极其耗时且冗杂的工作。更新第三方库至最新版本往往会需要大量的人力来解决由此带来的向后兼容问题。因此在很多情况下,App开发者并不会主动去更新App中包含的过时第三方库。

为了解决这一问题,作者提出了一种为Android App中包含的第三方库自动化生成更新的技术,其不需要修改App中的任何代码,并且不会影响第三方库与其它组件的任何本地或远程交互。作者称这种更新为非侵入式更新。非侵入式更新的优势在于:1)其不需要修改Android App中的任何代码,因此App的完全向后兼容性以及可维护性便得到了保证;2)由于其能够保证不会影响App中包含的第三方库的程序逻辑,App内在的状态一致性便得到了维护。

为了实现这一目标,LIBBANDAID使用前向程序切片算法(forward program slicing algorithm)来推断更新过时第三方库至最新版本所可能带来的影响。由于传统切片算法极其保守,生成的切片往往也十分笨重,作者提出了一种名为取值敏感的差分切片(value-sensitive differential slicing)的新型切片算法,其充分利用了两个版本程序之间的差分信息并通过记录程序中所有变量的值集(value set)变化,以克服传统切片算法过度保守的缺陷。

2 Problem Statement

部署模型:

文章提出的技术是面向Android App开发者而不是App市场或最终用户的。开发者将包含有过时第三方库的App以及此第三方库最新版本提供给LIBBANDAID,其将自动化的对App中包含的过时第三方库生成并应用非侵入式更新,而不修改App中的任何代码。该技术能够保证在非侵入式更新的前提下最大化更新提交的App。

假设:

LIBBANDAID能够在不违反非侵入式更新的前提下尽可能的更新App中包含的过时第三方库,并对于安全相关的更新具有极高的覆盖率。其所基于的假设在于,一个安全相关的更新不太可能会导致向后兼容问题或者影响第三方库与其它组件的本地或远程交互。

设计目标:

  • 文章提出的技术不需要Android App或者其中包含的第三方库的源代码;
  • LIBBANDAID在更新过时第三方库时对于安全相关的更新具有高覆盖率;
  • 生成的更新符合非侵入式更新的前提,不会影响第三方库与其它组件的任何交互或者破坏原始App的正确性。

3 System Overview

文章提出的技术是针对字节码(byte-code)而不是源代码的,文章中展示源代码只是为了便于理解。

3.1 Running Example

20191007194352

3.2 Overview of LIBBANDAID

20191007195241

LIBBANDAID一共有4个主要组件:预处理(preprocessing)、差分分析(diffing analysis)、更新生成(update generation)和选择更新(selective updating)。

预处理:

20191007195345

此步骤的目的是过滤掉两个版本第三方库之间没有被更改的函数,并生成被更改的函数对。具体来说,其提取出Android App中包含的过时第三方库,分析两个版本第三方库中的所有类,并进行函数级的逐字节比较。

差分分析:

此步骤的目的是以代码语句的粒度来进行函数级的匹配,从而推断第三方库在新旧两个版本之间的确切代码更改。为了实现这一目标,作者利用Tracelet Execution,并使用3-tracelet来进行代码语句级的代码匹配。

更新生成:

此步骤首先对于新旧两个版本的第三方库生成系统依赖图(system dependence graph, SDG),随后通过进行影响分析(impact analysis)对于每处代码更改生成一份切片。最后,其基于指向分析(points-to analysis)所得到的别名信息对于所有代码更改进行分类,并生成更新。

此步骤的目的在于:1)由于许多代码更改之间存在控制与数据依赖,LIBBANDAID应当总是将它们组合在一起共同更新;2)为了实现非侵入式更新的设计目标,LIBBANDAID进行影响分析,将每处代码更改与其潜在影响的所有代码相联系,从而判断更新是否的确符合非侵入式更新的前提。

选择更新:

此步骤过滤掉前一步骤生成的更新中潜在违反非侵入式更新前提的更新,并最终生成包含有经过更新的第三方库的新App。此步骤的核心是系统的设计一套预先定义的过滤规则,以保证生成的更新符合非侵入式更新的前提。

4 Update Generation

LIBBANDAID进行更新生成一共有3个主要步骤:影响分析(impact analysis)、指向分析(points-to analysis)和分类(grouping)。

4.1 Impact Analysis

影响分析的目的是推断每处代码更改所影响的代码。在了解了每处代码更改的影响之后,LIBBANDAID将所有代码更改进行分类,生成更新,并过滤掉违反非侵入式更新前提的更新。

4.2 Points-to Analysis and Grouping

在影响分析之后,LIBBANDAID进行指向分析以提取别名信息,并进一步将所有代码更改进行分类,生成更新。此步骤的目的是将访问相同全局变量或者具有重叠代码语句的切片进行分类。

5 Value-Sensitive Differential Slicing

5.1 Formal Definitions

Definition 1:

文章将一处代码更改对于一条代码语句的影响记为$I(d, c)$:

  • $d$代表在最新版本第三方库中的一处代码更改;
  • $c$代表在新旧两个版本第三方库之间没有被更改的一条代码语句。

$I(d, c) = \empty$代表代码更改$d$没有影响代码语句$c$。

Definition 2:

$I(d, c) = \empty \Longleftrightarrow B^d_c \subseteq B_c$:

  • $B^d_c$代表在应用代码更改$d$的前提下,代码语句$c$所有可能的程序行为;
  • $B_c$代表在未应用代码更改$d$的前提下,代码语句$c$所有可能的程序行为。

此时,一处代码更改对于一条代码语句的影响被转化为此条代码语句程序行为的更改。

Definition 3:

$VS^d(I, c) \subseteq VS(I, c) \Rightarrow B^d_c \subseteq B_c$:

  • $VS^d(I, c)$代表在应用代码更改$d$的前提下,代码语句$c$中使用到的所有变量$I$以及它们组合的值集;
  • $VS(I, c)$代表在未应用代码更改$d$的前提下,代码语句$c$中使用到的所有变量$I$以及它们组合的值集。

实质上,这条定义表明如果一条代码语句中使用到的所有变量以及它们组合的值集都没有更改或者依旧是原始值集的子集,那么此条代码语句的程序行为则也没有更改或者依旧是原始程序行为的子集。

5.2 Basic Scheme

取值敏感的差分切片的核心是考虑在新旧两个版本程序之间所有变量取值的变化,并利用此信息来克服传统切片算法过度保守的缺陷。其基本方案是从一处代码更改开始,对于此处代码更改所依赖的每条代码语句中使用到的所有变量以及它们的组合进行完整的第三方库的上下文敏感且控制流敏感的值集分析(value-set analysis, VSA),并比较新旧两个版本第三方库的值集分析结果。

理论上来说,此分析是可靠的且能够克服传统切片算法过度保守的缺陷。然而,完整的第三方库的上下文敏感且控制流敏感的值集分析所带来的巨大性能开销,使得此基本方案无法实行。

5.3 Slice-wise VSA

20191007220732

为了降低取值敏感的差分切片的复杂度,作者提出了将值集分析的搜索空间限制在从当前代码更改开始的切片内的优化方案。此优化方案是基本方案的一种近似,其比基本方案更加保守,虽然牺牲了完整的第三方库的值集分析的精度,但也极大的提升了性能。

5.4 Intra-procedural VSA

20191007220753

如同先前讨论的,第一种优化方案只在当前切片内搜索,可能同样存在过度保守的缺陷。因此,作者进一步提出了将值集分析的搜索空间放宽至包含有当前代码更改的函数起始处。

5.5 Value-sensitive Differential Slicing

20191007220817

6 Selective Updating

6.1 Filtering

在此步骤中,LIBBANDAID依赖于一套预先定义的规则来过滤掉生成的更新中可能会影响第三方库与其它组件交互的更新,从而实现非侵入式更新的设计目标。为此,作者调查了第三方库的工作原理,并总结出了第三方库与其它组件的4类交互:1)与App的交互;2)与服务端的交互;3)与Android系统的交互;4)与其它App的交互。

20191007220842

6.2 Updating

在基于预先定义的规则过滤掉不满足的更新之后,LIBBANDAID将满足过滤规则的更新应用到App中包含的过时第三方库中。此步骤是使用Soot的字节码重写功能在第三方库的Jimple IR上进行的。

7 Evaluation

7.1 Dataset and Configuration

20191007220908

20191007220934

7.2 Effectiveness of LIBBANDAID

安全相关的更新可以被分为3类:1)修复的(patched);2)未被修复的(fail to patch);3)潜在可修复的(potentially patchable)。潜在可修复的更新是指此更新更改了过时第三方库的API,如果包含此过时第三方库的App没有直接调用被更改的API,那么LIBBANDAID还是可以修复此类安全相关的更新。

20191007221053

20191007221126

20191008005022

7.3 Correctness of LIBBANDAID

LIBBANDAID的正确性是通过进行随机测试(random testing)以及人工检查经过更新的App来保证的。对于每个经过更新的App,文章使用Monkey进行了2个小时的随机测试,并通过人工尝试所有UI控件的组合来进行检查,最终取得了平均25.7%的代码覆盖率。

7.4 Effectiveness of New Slicing

文章通过将取值敏感的差分切片算法与传统切片算法进行比较,以评估其有效性,并回答以下两个问题:

  • 此算法能够克服传统切片算法过度保守的缺陷吗?
  • 此算法能够帮助LIBBANDAID取得更好的结果吗?

20191007220959

20191008005053