Group of Software Security In Progress

GoSSIP @ LoCCS.Shanghai Jiao Tong University

Automatic Hot Patch Generation for Android Kernels

作者:Zhengzi Xu, Yulong Zhang, Longri Zheng, Liangzhao Xia, Chenfu Bao, Zhi Wang, and Yang Liu

单位:Nanyang Technological University, Baidu X-Lab, and Florida State University

出处:USENIX Security ‘20

原文:Automatic Hot Patch Generation for Android Kernels

Abstract

随着Android生态的飞速发展,其碎片化的问题也变得越来越严重,大量经过定制的Android系统在市面上涌现。然而,Android供应商往往难以及时修复他们定制的Android内核中出现的漏洞,这就带来了非常严重的安全问题。近年来热补丁(hot patching)技术的发展便为这个问题提供了理想的解决方案,该技术能够被应用于各式各样的Android内核中,且不会影响它们的正常功能。然而,目前的热补丁往往是由人工编写,费时费力且易于出错。

为此,作者调查了2012年至2016年Android官方公布的373个Android内核CVE,以研究自动补丁生成(automatic patch generation)技术的可行性。随后,作者提出了自动热补丁生成工具VULMET,该工具基于官方补丁,通过最弱前置条件推理(weakest precondition reasoning),以生成与官方补丁语义一致的热补丁。实验结果表明,VULMET成功为55个真实的Android内核CVE生成了正确的热补丁,这些热补丁没有影响到内核的稳定性,且只有极少的性能开销。

1 Introduction

经过用户同意,作者收集了5亿台安装有Baidu app的设备在2018年10月的Android版本和补丁版本。

20200313140409

从2018年8月起,Android Security Bulletin停止发布针对Android 6.x及更低版本系统的安全补丁。因此,基于表中的统计,44.72%的Android设备将不再收到任何的安全补丁,除非其Android供应商能够自己更新系统固件。

20200313140455

只有20%的设备能够安装3个月之内的安全补丁,只有60%的设备能够安装6个月之内的安全补丁,剩下20%的设备只安装了1年前的安全补丁。

然而,Android供应商并没有动力来修复遗留Android系统中出现的漏洞。将官方补丁应用在经过定制的Android内核中,这需要经过冗长的测试过程,以保证补丁没有破坏已有的功能。

热补丁技术提供了一种便利的方式来修复已知的漏洞,且不会影响程序的正常功能。该技术能够极大的提升用户体验,在不需要设备重启的前提下,保证系统的安全性。

然而,目前的热补丁框架往往不支持自动补丁生成。在源代码层面,开发者能够通过修改函数的任意部分来修复漏洞,而在二进制层面,精确的定位到相同的位置来进行修改是非常困难的。

为此,文章提出了一种自动化热补丁生成过程的解决方案。为了全面的了解漏洞补丁,作者首先分析了2012年至2016年大部分的Android CVE,并基于它们的修复行为进行了分类。随后,根据分析结果,作者提出了VULMET,该工具能够通过程序分析来提取官方补丁的语义,以自动生成与官方补丁语义一致的热补丁。

2 Automatic Hot Patch Generation

2.1 Problem Definition

作者针对自动热补丁生成的定义如下:

给定一个存在漏洞的函数$F$,该函数的官方补丁$P$被置于位置$L$,作者想要在函数$F$的二进制中定位到一个合适的位置$L’$,以应用自动生成的热补丁$P’$,该热补丁与官方补丁$P$的语义一致。

2.2 Requirements

为了保证生成的热补丁的可用性,作者设定了以下三点要求,以判断该热补丁是否适合于修复Android内核:

  • 要求一:生成的热补丁应当与官方补丁的语义一致,以保证该热补丁的正确性。
  • 要求二:生成的热补丁不应破坏系统的正常功能,以保证该热补丁的健壮性。
  • 要求三:生成的热补丁应当具有较少的性能开销,以保证该热补丁的效率。

2.3 Operation Scopes

为了保证修复程序的健壮性,作者设定了以下三条规则,以限制热补丁中所使用的操作:

  • 操作规则一:补丁只能被置于函数的开头和结尾,或者函数调用的开头和结尾。
  • 操作规则二:补丁只能读取内存中有效的内容,而不能修改内存中的内容。
  • 操作规则三:补丁只能包含较小的修改,且只能修复存在于单个函数中的漏洞。

20200313161218

针对修改了函数的绝大部分的补丁,热补丁技术往往难以在不引入其它问题的前提下,修复这类漏洞。然而,如果一个较大的官方补丁能够被划分为多个存在于单个函数中的较小的补丁,这些较小的补丁便能够被逐个转化为热补丁。

2.4 Real-world Example

20200313161243

为了生成与官方补丁语义一致的热补丁,作者需要通过最弱前置条件推理的程序分析技术,使用在当前位置取值已知的变量,以表示与官方补丁中相同的合法性检查。

20200313164029

3 Patch Type Analysis

由于VULMET针对的是遗留漏洞,作者选择了2012年至2016年的Android内核CVE,这些CVE主要存在于主版本号为3的Linux内核中。

3.1 Patch Categorization

由于文章的关注点在于补丁生成,因此补丁的分类应当反映出函数代码的修改,而不是漏洞的后果。

20200313195342

20200313195411

3.2 Observations

作者在研究漏洞补丁的过程中,获得了以下四点观察结果:

  • 观察结果一:相比于其它程序更新,漏洞补丁包含的修改通常较小。
  • 观察结果二:较大的漏洞补丁通常是由多个较小的独立补丁组成的。
  • 观察结果三:补丁的修复模式与漏洞类型没有很强的相关性。
  • 观察结果四:某些补丁既包含非安全更新,同时也包含漏洞补丁。

观察结果二表明,作者能够使用分治法来分析某些较大且复杂的漏洞修复。通过适当的划分较大的补丁,作者便可以得到能够被独立转化为热补丁的较小的补丁。

3.3 VULMET Work Scope

20200313195441

针对补丁类型Function Call,VULMET能够进入被调用函数来进行分析。如果被调用函数不涉及内存写入操作,VULMET便可以支持该补丁。

VULMET不支持补丁类型Redesign,因为这些补丁极大的改变了原函数的语义,违背了操作规则三。

4 Methodology

4.1 Overview

20200313203659

4.2 Patch Filtering

禁止的操作包括,变量或指针的赋值,以及调用修改内存的函数。如果官方补丁包含禁止的操作,VULMET将会把该补丁过滤掉。

4.3 Insertion Location Optimization

某些修复位置可能没有包含足够的变量取值信息来生成与官方补丁语义一致的热补丁。某些修复位置可能会影响程序的正常执行,导致无法预料的副作用。VULMET需要考虑到这些不同的方面,以在目标函数内的多处修复位置中找到最佳的一处。

不可避免的是,在某些情况下,漏洞修复的副作用可能会导致函数的正常功能与原目标函数不同。在这种情况下,VULMET选择牺牲函数的正常功能,以保证补丁修复漏洞,因为VULMET的首要目标是保护系统。

4.4 Weakest Precondition Reasoning

在程序中,前置条件是在函数调用之前,应当为真的表达式,而后置条件则是在函数结束,且所有前置条件都满足的前提下,应当为真的表达式。

20200313203757

20200313212818

20200313212845

VULMET的最弱前置条件推理是基于SVF与LLVM实现的。

如果被调用函数调用了其它的函数,即存在嵌套的函数调用,VULMET将会把该函数视为复杂函数,并略过该函数。如果循环过于复杂,即该循环包含新的函数调用或多层的嵌套循环,VULMET将会略过该循环,而不进行任何分析。

20200313213615

4.5 Binary Hot Patch Generation

VULMET生成的热补丁包含具有补丁逻辑的可执行二进制程序,以及记录修复位置的文件。该热补丁便可以被标准的热补丁框架应用在真实的32位和64位ARM架构的Android平台上。

5 Evaluation

在实验中,所有的补丁都是在Google Nexus 5X上进行测试,该设备的Android内核版本为7.1.1 r31 bullhead build。

5.1 Correctness Evaluation

Experiment 1: Patches against Exploits

20200313221129

针对CVE-2014-3153,CVE-2016-4470,和CVE-2014-4943,热补丁彻底的修复了这些漏洞。

针对CVE-2018-17182,热补丁能够成功防止其被利用,但不能阻止系统崩溃。这是因为该补丁只能部分的修复该漏洞。

20200313221859

20200313221922

20200313221955

Experiment 2: Manual Verification

20200313222039

结果表明,VULMET成功为55个漏洞生成了正确的补丁。针对剩下的4个漏洞生成的补丁是错误的,因为这些补丁中包含修改内存的部分操作。为了修复这些漏洞,VULMET需要改善其语义分析的能力,以检测内存写入操作。

Experiment 3: Comparison with Human Written Patches

20200313222106

针对CVE-2016-4470,人工编写的补丁与生成的补丁不同,这是因为人可以理解此漏洞的根本原因,并直接应用补丁来修复此问题。然而,这两个补丁最终都可以修复此漏洞。

5.2 Robustness Evaluation

在实验中,作者通过运行Android benchmark来评估修复Android内核的健壮性。作者选择的Linux内核版本为3.10。在这个特定的Android内核上,VULMET成功将21个漏洞补丁转化为了热补丁。

作者在修复Android内核上测试了AnTuTu benchmark和CF-bench,并监视任何的异常行为,例如崩溃和挂起。

20200313222133

为了进一步检验现实情况中补丁的健壮性,作者在修复Android系统中安装了Google Play排名前100的Android app,并使用脚本打开、加载、和关闭app,并监视任何的异常行为。

总的来说,生成的补丁没有破坏修复程序的正常功能。

5.3 Efficiency Evaluation

作者在Google Nexus 5X上运行AnTuTu benchmark,以评估Android系统在修复前后的性能。

20200313222211

结果表明,热补丁没有在Android系统方面引入明显的性能开销。