​由于频繁的更新迭代，移动终端上的大型应用程序越来越普遍。因此，从应用商店里下载大型应用安装包将无可避免的耗费大量时间，这已经成为移动终端用户的一大痛点。对于应用开发者而言，也需要改变现有的整包安装方案以满足用户需求。

在传统的应用安装方案中，开发者通过ADB（Android Debug Bridge）以有线或无线的方式与终端用户连接，或者用户从软件商店直接下载，然而该方案需要用户等待完整的安装包传输结束后才能启动安装，在这期间产生了不良的用户体验。

增量安装技术是一种流式的安装方案：一旦安装包的核心文件传输完成便可启动应用。流式安装意味着允许优先传输核心数据以启动应用，并在后台流式传输剩余数据。

对于APK而言，其核心数据包括可执行文件和重要的资源文件等。在数据传输开始前，ADB筛选出安装包的核心文件优先传输，一旦移动设备接收到启动应用所需的核心数据块后，该应用程序便可在虚拟文件系统上启动。

在Android 11中，Google在内核中实现了增量文件系统用于对增量安装的支持。(详见https://source.android.com/devices/architecture/kernel/incfs)

这使得Android os可以通过ADB流式传输APK。同时，Android 11为了适应增量安装，添加了新的V4签名方案。

此方案不改变前代签名方案而是创建一种新的签名：基于APK所有字节数据计算出Merkle哈希树，并将Merkle树的根哈希、盐值作为签名数据进行包完整性验证。新的签名数据保存在.idsig文件中并且在进行增量安装前必须为APK创建对应的V4签名文件。

本文将简要介绍增量安装的基本原理和基于Merkle树的V4签名方案。

文| 陈振明/潘雨晨/闻迪桉

1-增量安装

上图所示为增量安装的基本框架[1]。

ADB筛选出需要优先传输的文件，并通过增量文件流传递数据，同时在传输过程中创建传输日志并提供给开发者。

移动设备上的增量文件系统内核模块用于在操作系统中创建增量服务。增量服务接收来自ADB的增量安装请求，通知增量文件系统内核模块和包管理器(Package Manager)启动增量安装并追踪应用程序的安装过程。

接收到增量安装请求后，增量文件系统内核模块接收来自ADB的APK核心数据并放在增量文件系统内。

增量文件系统是运行在设备文件系统上的虚拟文件系统，它在接收到APK的核心数据文件后为整包分配空间并创建APK包的虚拟文件进行增量安装。

核心数据安装完毕后便可在设备上显示应用图标和应用所在目录。在用户启动应用后，ADB将在后台继续传输剩余的APK包数据。

上图所示为ADB优先选择的APK核心文件。ADB以增量的方式将APK数据传输给移动设备。预先传输的数据可以让APK提前启动。ADB追踪正在传输的数据并创建日志文件并提供给应用开发者。

2-Merkle树

Android V4签名方案的签名和验证是基于Merkle树进行。

Merkle树的设计之初是为了解决单一Lamport密钥不能签署多条信息及大信息量下公钥过长的问题[2]。

Merkle树本质上是将一系列Lamport公钥组合在一起，并用哈希函数计算出一个统一的公钥，这个公钥便是Merkle树的根哈希。

下面介绍利用Merkle树的生成并验证签名的过程。

对于下图的Merkle树：

● 数据块1~数据块4有各自的密钥对(X_i,Y_i)，

● Merkle树的叶子节点是对每个数据块的公钥计算的哈希值：h_i=H(Y_i)。

● 非叶子节点的值是通过合并其子节点的值并计算哈希得到的。

以节点a_1,0的计算为例，a_1,0=H(a_0,0||a_0,1)。

依此类推，便可以计算出根节点哈希值并建立Merkle树，将根节点值作为公钥用于验证签名。

数块的签名包括加密该数据块的密钥以及该密钥的验证路径，其中验证路径是从叶子节点到根节点路径上的所有节点的兄弟节点。

Merkle树验证签名需要首先验证数据块的一次性签名，再验证该公钥的正确性。

以数据块1为例，首先验证密钥对(X₀,Y₀)是否正确匹配；

若是则验证Y₀的正确性，根据a_0,0的验证路径和根哈希进行验证。

节点a[0,0]的验证路径包括a[0,1]和a[1,1]。

通过a[0,0]与a[0,1]可计算出a[1,0]，a[1,0]与a[1,1]可计算出根节点a[2,0]，与Merkle树的公钥进行对比，若一致接收签名。

3-V4签名

V4签名基于APK字节计算Merkle树用于文件验证。

V4签名以如下数据结构保存在.idsig文件内，其中包括了用于验证签名的根哈希。

struct V4Signature {int32 version; // only version 2 is supported as of nowsized_bytes<int32> hashing_info;sized_bytes<int32> signing_info;sized_bytes<int32> merkle_tree;  // 可选择是否保存完整merkle树};​

其中sized_bytes的结构如下：

template <class SizeT>struct sized_bytes {SizeT size;byte bytes[size];};

hashing_info 保存着哈希树的相关信息：哈希算法（SHA256）、数据块大小（4KB），盐值、根哈希。hashing_info的定义如下：

public static class HashingInfo {public final int hashAlgorithm;  public final byte log2BlockSize;     public final byte[] salt;public final byte[] rawRootHash;......};

signing_info 保存用于验证签名的参数：数据摘要、签名数据、公钥、证书等。signing_info的定义如下：

public static class SigningInfo {public final byte[] apkDigest;  public final byte[] certificate; public final byte[] additionalData;public final byte[] publicKey;public final int signatureAlgorithmId;public final byte[] signature;};

下面介绍如何生成V4签名。

首先以自底向上的方式生成Merkle树，如下图所示：

我们首先将APK的源数据划分为多个4KB的数据块，如果源文件最后部分不足4KB，则进行零填充来凑足4KB；

然后对这些4KB的数据块进行SHA256计算得到32B的哈希值，这部分哈希值就组成了Merkle树的第一层。

对于Merkle树的第二层，需要将第一层的进行组合，组合方式是依次将第一层的128个哈希值组合成4KB的数据块，如不足4KB则进行零填充，最后对这些4KB块进行SHA256计算得到Merkle树的第二层。

后面的部分以此类推，直到计算出Merkle数的根哈希。生成的哈希树以V4Signature的结构保存在.idsig文件内。

由根哈希计算出Hashinfo结构，根据Hashinfo和APK摘要生成V4签名。

当ADB请求增量安装时，PMS从.idsig文件中获取原生签名封装在V4Signature对象中。进行验证时，则从V4Signature获得签名数据和公钥，验证的过程与上一代签名方案类似。

4-总结

本文以增量安装和安卓V4签名方案为切入点，主要介绍了增量安装技术的应用框架以及V4签名方案的理论依据。

综上所述，增量安装是一种允许应用快速启动的流式安装技术，而为了支持增量安装而设计的V4签名则是一种具有Merkle树结构的签名。

在可预见的未来，增量安装和V4签名都将具有更广泛的应用场景。

参考文献：

[1] Eason, Jamal, et al. "Incremental File Streaming of a Package File for Application Installation on a Mobile Electronic Device." (2020).

[2] Becker, Georg. "Merkle signature schemes, merkle trees and their cryptanalysis." Ruhr-University Bochum, Tech. Rep (2008).

作者：陈振明/潘雨晨/闻迪桉

团队：OPPO终端安全团队