Automatic Hot Patch Generation for Android Kernels
主要解决什么问题
Android 版本升级覆盖缓慢，往往发布半年的最新Android系统设备覆盖率只有个位数，如此便使得旧版本的Android系统的内核漏洞无法修复，而OEM厂商又无意修补这些漏洞，因为内核的改动需要繁琐的测试保证更改不会影像现有功能和性能。因此，多数设备上搭载的旧版Android系统会保持漏洞存在很长一段时间。
为了解决上述问题，已经有很多方案被制定出来，在所有可能的解决方案中，热补丁技术提供了一种在不中断程序正常功能的情况下修复漏洞的便捷方法。由于它可以在不重新启动设备的情况下修补内核漏洞，因此极大地改善了用户体验。
根据正式发布的补丁程序编写热补丁程序是较难的工作。在二进制文件中，很难准确找到要修改的脆弱点。为了在适当的位置打上热补丁，安全专家需要了解官方补丁的语义并编写相应的热补丁。但是，这是一个耗时并且容易出错的过程。受限于快速的开发周期和有限的安全预算，人工开发热补丁往往是商业公司不可接受的。因此，需要开发一种自动解决方案以将正式补丁正确转换为热补丁。
为此，本文提出了一种自动执行热补丁生成过程的解决方案。为了对漏洞修补程序有完整的了解，我们首先分析了2012年至2016年的大多数Android CVE，并根据其修补行为对其进行了分类。根据这些分析，我们开发了Vulmet，它可以通过程序分析提取官方补丁的语义来自动生成热补丁。Vulmet将在函数中找到合适的位置，构建并应用语义等效的热补丁来修复漏洞。为了测试Vulmet的有效性，我们为实际的Android CVE生成了热补丁。热补丁程序可以以很少的系统开销来修补漏洞。
概述结论：
为此，我们首先研究了从2012年到2016年从373个Android内核CVE中自动生成补丁的可行性（结论为可行）。然后，我们开发了一种自动热补丁生成工具，名为Vulmet，该工具通过从官方补丁中学习来生成语义保留热补丁。 Vulmetis的关键思想是使用最弱的前提推理（weakest precondition reasoning）将官方补丁所做的更改转换为hot patch约束。实验表明，Vulmet可以为55个现实世界的Android kernel CVE生成正确的热补丁。热补丁不影响内核的健壮性，并且性能开销较低。
PS：
注意1：本文实现的热补丁生成工具Vulmet，需要看官方补丁，从中学习语义，根据Vulmet被定义的约束条件和操作范围，生成可行的热补丁。（在我看来本文想法稍微有点鸡肋，既然发布了官方补丁，OEM厂商只要跟进就好了呀，只能说热补丁具有不需要重启的优势，这种优势在服务器系统补丁上会更明显吧😐）
注意2：Vulmet并不能百分百根据官方补丁生成热补丁，只能实现满足下述Requirements和Operation Scopes的情况下，官方补丁自动生成热补丁。
使用的方法
本节叙述Vulmet的实现过程：解释热补丁生成，android漏洞类型分析并定义操作范围，自动热补丁生成框架
Section 2 Automatic Hot Patch Generation
Problem Definition（定义热补丁生成）：
给定一个易受攻击的function F及在F的L位置上打上官方的patch P ，我们希望在二进制代码中找到function F的一个合适位置L’来插入自动生成的热补丁P’，其语义与P相同。
Requirements：
- Requirements 1：生成的热补丁应该保留和官方补丁一致的语义，确保其正确性
- Requirements 2：生成的热修补程序不应破坏系统，确保系统运行的健壮性
- Requirements 3：生成的热补丁应该产生较低的开销，确保系统效率
Operation Scopes：
Operation Rule 1：补丁只能放在函数的开始或结尾处，或函数调用的开始或结尾处
Operation Rule 2：补丁可以读取内存的有效内容，但禁止修改
Operation Rule 3：该补丁只能在一个函数范围内进行很小的更改，以尝试修复漏洞
原文2.4节介绍了一个用本文定义的规则和操作范围修补CVE-2015-8940整数溢出漏洞的过程，大意就是官方补丁检查了几个变量的值，本文做法是在函数开始处检查上述值，由于这些值并不是一开始就知道的，所以通过一个algorithm（in Section4）自动确定这些变量之间的关系，以此生成了和官方语义相同的检查约束添加到函数开始，热补丁结束。详细过程请参考原文。
Section 3 Patch Type Analysis
在研究中，我们提供了漏洞补丁分类和分布情况以及从观察中的发现。本节，我们将讨论Vulmet能够支持的漏洞补丁的类型。
我们的工作聚焦于热补丁生成，所以补丁分类应该反应补丁功能，而不是反应补丁修复漏洞的类型。目前来说针对后者的分类要原多于前者，我们遵从[36]的分类方案思想，形成我们的分类方案，如下图所示：
3.2 Observation
在漏洞补丁的研究过程中，我们获得了四个有趣的发现。
Observation 1: 与程序更新相比，漏洞补丁的更改通常很小
Observation 2: 大型漏洞补丁通常由几个小型独立补丁组成
Observation 3: 补丁类型和漏洞类型并不是一定相关的，或者说是比较无关的
Observation 4: 一些补丁同时包括安全补丁和非安全补丁
3.3 Vulmet Work Scope
Sanity Testing 健壮性检查上面的栗子说过了，符合Requirements和Operation Scopes，Vulmet完全支持。
对于Function Call类型，Vulmet可以进入被调用函数并该函数。如果此补丁的更改不涉及内存写入操作，则Vulmet可以支持该修补程序。
对于Change of Variables和Change of Data Types都涉及内存写操作，因此不支持。
Vulmet不支持Redesign类型补丁，因为它极大地改变了原始函数的语义并违反了Operation Scopes 3。
Section 4 Methodology
Patch Filtering
Vulmet将通过对比存在漏洞的代码和已修补的代码之间的不同来提取官方补丁。然后，针对补丁中的每个语句，将其分为正常操作和禁止操作。禁止的操作包括变量或指针值的分配以及对内存修改函数的调用。如果正式补丁不包含禁止的操作，Vulmet会将其选择为生成热补丁的候选对象。否则，补丁将被过滤掉。
Insertion Location Optimization
根据第2.3节的规则1，函数头或尾是patch 可以hook的位置。因此，Vulmet只能hook 漏洞函数或者漏洞函数中调用的函数。这些可以hook的位置都是为可能的补丁插入位置。Vulmetis需要寻找最佳的插入位置。具体的寻找算法看原文吧，不赘述了。
Weakest Precondition Reasoning
在选择补丁插入点之后，下一步是通过计算和官方补丁的语义等效性的热补丁。在Vulmet中，此过程被重构为最弱的前提推理任务。在编程中，前提条件是在调用函数之前应为true的语句。而后置条件是一个陈述，如果函数完成并且所有先决条件都满足，则该陈述为真。表6展示了语义计算与最弱前提条件推理之间的关系。给定一个正式补丁，其语义可以转换为一个或多个后置条件。漏洞函数中的陈述将定义解决最弱前提的transformer。获得热补丁约束的过程等同于计算最弱的前提条件。产生的最弱前提条件是官方补丁的语义等价的热补丁。（这就是核心算法，看不懂的话就算了，知道是使用这个算法就可）
Binary Hot Patch Generation
最后一步是根据precondition constraints生成热补丁。Vulmet使用空函数作为模板，并将函数的输入参数的数量和类型设置为与原始目标函数相同。然后，将所有约束插入其中，并将功能编译为可以热修补到内核的二进制可执行文件。
关于热补丁生成的细节，包括变量地址，指令集支持，可执行文件生成等细节问题就不多赘述了。
结果评估
我们对Vulmet生成的热补丁的正确性，鲁棒性和效率进行了评估。
正确性可以量化补丁修复漏洞的能力，健壮性可以量化补丁维护程序稳定性的能力，效率可以量化补丁引入的开销。
我们设计了实验来测试这三个方面的补丁有效性。在实验中，所有补丁均在具有Android kernel版本7.1.1 r31 bullhead 构建的Android Open SourceProject（AOSP）平台Google Nexus 5X上进行了测试。
5.1 Correctness Evaluation
在本节中，我们评估生成的热补丁的正确性。实验包括三个部分。首先，我们使用真实的CVE漏洞测试补丁。其次，对于无法利用的漏洞，我们手动验证补丁的正确性。第三，我们手动编写热补丁，并将生成的热补丁与它们进行比较，以检查生成的补丁是否以与人类专家相同的方式解决了漏洞。
手工收集了四个CVE攻击方法，用来攻击被Vulmet打过补丁的系统。结果表明，所有补丁均已成功阻止了来自攻击的攻击。对于CVE-2018-17182，该热补丁可以成功阻止漏洞利用，但无法阻止系统崩溃。这是因为该修补程序只能部分修复漏洞。
人工验证59个自动生成的热补丁有55个是正常工作的，沃觉得算是相当不错了。
与人类安全专家相比55个自动生成的热补丁只有一个语义不同，具体哪里不同参考原文。
5.2 Robustness Evaluation
为了构建测试环境，我们选择要使用Linux内核版本3.10构建的Android bullhead，然后回滚以生成具有许多未修补漏洞的内核。在此特定内核中，Vulmet管理21个漏洞补丁，可以将其转换为热补丁。
然后我们将这些补丁应用到内核并运行安兔兔Benchmark和CF-bench，监控系统异常，比如崩溃和挂起。表11总结了该实验的结果。出于演示目的，我们选择5个CVE作为示例，并列出所有21个补丁的最终结果
结果表明，所有热补丁都不会使程序崩溃或挂起。为了进一步检查现实情况中补丁的健壮性，我们从Google App Store中选择并安装了前100个Android应用程序。我们使用脚本来打开，加载和关闭已修补系统上的应用程序，并监视异常行为。结果是可以正确执行所有应用程序，这表明这些修补程序在实际情况下保持了良好的鲁棒性。总而言之，生成的补丁不会破坏补丁程序的正常功能
5.3 Efficiency Evaluation
我们在Google Nexus 5X设备上使用安兔兔基准测试修补前后的系统性能。我们将实验设置控制为相同，以便一次测试一个热补丁。每个实验重复10次，取平均分以避免噪声引起的变化。表12列出了具有5个单独CVE补丁的内核的性能以及应用所有21个补丁的总体性能。
所有结果都在合理范围内，与原始内核结果相比，该范围略高或略低。因此，补丁使系统的开销较低。
缺点和不足（选）
- Vulmet的前提之一是自动生成的热补丁无法修改内存和原始程序的内容。这就使得诸如变量类型修改，变量数值修改，函数过程重构等补丁类型无法自动生成。
- Vulmet依靠官方补丁语义的精确总结来生成正确的热补丁。在实验中，由于Vulmet无法完全提取语义，因此某些生成的热补丁不完整。
- 有些补丁过于复杂而无法分析。很难找到大补丁的精确语义。当前Vulmet只能处理，仅对一个函数过程进行修补的补丁。
对我有什么启发
Hot Patch 技术是我没有接触过的，主要借助此篇文章了解内核补丁技术、热补丁技术，希望能更加深入的了解内核级补丁修补和应用原理。
这项研究的未来方向
可能会和人工智能结合的比较紧密吧，就如缺点2和3所述，补丁的生成依赖语义分析，如果语义分析器能借助人工智能技术的发展，强大到根据漏洞类型自动分析出某段代码的修补方案，这样的话，没有漏洞的世界就完成了。😃
论文链接：https://www.usenix.org/conference/usenixsecurity20/presentation/xu