开发一个基于Dalvik字节码的相似性检测引擎，比较同一款Android应用程序的不同版本之间的代码差异...

Dalvik是Google公司自己设计用于Android平台的虚拟机，Dalvik虚拟机是Google等厂商合作开发的Android移动设备平台的核心组成部分之一。它可以支持已转换为 .dex（即Dalvik Executable）格式的 Java 应用程序的运行，.dex格式是专为Dalvik设计的一种压缩格式，适合内存和处理器速度有限的系统。Dalvik 经过优化，允许在有限的内存中同时运行多个虚拟机的实例，并且 [1]  每一个Dalvik 应用作为一个独立的 Linux 进程执行。独立的进程可以防止在虚拟机崩溃的时候所有程序都被关闭。很长时间以来，Dalvik虚拟机一直被用户指责为拖慢安卓系统运行速度不如IOS的根源。2014年6月25日，Android L 正式亮相于召开的谷歌I/O大会，Android L 改动幅度较大，谷歌将直接删除Dalvik，代替它的是传闻已久的ART。

我会在这篇文章中，为你介绍如何对比同一款Android应用程序的不同版本之间的代码迭代情况。简单来说，就是通过Android应用程序中的相似性检测。

《针对Dalvik字节码的相似性检测引擎，比较同一款Android应用程序的不同版本之间的代码差异》这篇文章我们计划分2部分来讲解，在本文中，只介绍如何利用Quarkslab公司开发的diff引擎。第二部分除了介绍一个用例：URl欺骗漏洞(CVE-2019-10875) ，我们还会介绍如何将Redex与diff工具相结合，检测被混淆处理的应用程序中到底发生了哪些修改？

背景知识

相似性检测并不是一个新概念，并且已经被一些学术论文以及BinDiff，Diaphora，YaDiff等 工具 所验证。

相似性检测这个概念可以用于各个目的，比如在一个集合中识别一个函数，或者在APK中检测一个库或第三方SDK。在本文的示例中，我们的目标是从APK的两个不同版本中提取的两组类或方法中发现被修改过的代码。

diff的检测结果可以用于检测漏洞的修补情况，基于先前的分析对混淆的代码(比如Proguard输出的代码)进行逆向分析。

实现diff引擎时遇到的挑战

与汇编代码不同，Dalvik指令集非常冗长，而且字节码的结构使分析变得更容易。例如，在Dalvik字节码中，访问方法字符串很简单，而在本机代码中，我们必须处理重定位等问题。

但是，Android应用程序变得越来越大，会导致采用多个.dex文件。我们需要克服的第一个挑战是有效地处理应用程序的多DEX结构。第二个挑战是实现一个可扩展的diff引擎，该引擎支持大量要比较的对象。在常见的Android应用程序中，嵌入数万个类是相当普遍的。

解决办法

利用DEX格式和Dalvik指令集带来的一些特殊功能，来设计和构建针对Android应用程序的diff引擎。

首先，为了准确理解diff引擎的实现，我们需要介绍它的用途。 diff引擎可以将两组类（来自两个APK）作为输入对象，并输出对应的匹配列表。每个匹配列表都包含有相似性值，该值越趋近于1，类就越相似。当距离严格等于1时，我们假设它是完全匹配的。这意味着这两个匹配的类看起来完全一样。这是一个至关重要的参考，因为如果我们能弄清楚类有多相似，那么我们就能分析检测到的变化情况。

现在让我们来介绍diff引擎的内部结构，从技术上讲，它包括三个主要阶段，使我们能够快速有效地比较两组类：第一阶段将类划分为簇，第二阶段执行粗略比较，而最后一个阶段执行准确的比较。

在运行这些阶段之前，我们可以选择减少发送给diff引擎的类的输入集，以提高性能。这一步非常重要，因为它会显著影响diff引擎的运行。如果diff引擎将更快，更有可能精准地找到其中的差异。换句话说，发送给diff引擎的类的输入集越少越好。例如，可以按如下方式减少类的集合：

v1, v2 = load("v1.apk"), load("v2.apk")
classes_v1 = filter(v1.classes, CONDITION)
classes_v2 = filter(v2.classes, CONDITION)
diff_result = diff(classes_v1, classes_v2)

准备阶段：过滤类

由于应用程序常常嵌入一大堆外部模块和第三方SDK，因此类的数量可能非常巨大。例如，Twitter应用程序包含36352个类，但只有10078个位于包名com.twitter.android中。但是，大多数情况下，在检测Android应用程序时，逆向分析程序只关注特定的部分或包。这意味着许多类根本不在被分析的范围中。在这种情况下，将所有类别作为一个广泛的类别进行比较是没有意义的。此外，根据应用程序的大小，比较太多的类将更加耗费资源和时间。由于Dalvik的设计和它从Java借用的模块化模型，这些功能通常已经分成不同的包，并且这些信息可以从DEX文件中被检索到。

因此，利用包是减少输入集的好方法，因为内部包结构不太可能在不同版本之间发生根本变化。比如，在本文的示例中我们只处理包com.android.app.signup和com.android.app.webapi中的类。请注意，所有嵌套包（如com.android.app.webapi.ping）都未在此处表示。

根据包名过滤类

第1阶段：聚类方法(Clustering) 

此时，我们已经选择了两组类——A类和B类，来对它们进行比较。现在进入diff引擎的内部，将类分成几个组。这些组称为簇（cluster），并根据类所在的包构建。如果类PingRequest和PingResponse都是com.android.app.webapi.ping的一部分，它们将被放置在同一个簇中。尽管如此，它们不会同时出现在com.android.app.webapi.picture和com.android.app.webapi.ads中的SendPictureRequest和AdsResponse。 然后，来自集合A的每个簇根据其包名，将它们链接到集合B中的相应簇。两个簇就构成了我们所说的池（pool）。

簇类和创建池之后的结果

通过处理类池，我们就可以进行规模化的比较，这大大减少了比较的总体数量，并实现了并行性计算。

但是，这个阶段不是强制进行的，可以在特定情况下被跳过。

第2阶段：批量比较

在优化和减少比较集之后，我们可以开始比较每个池中的类。然而，有些池可能仍然非常大，并且可能包含数千个类的集群。因此，我们需要一种有效的方法来处理这个问题。为了解决这个问题，我们从应用于近似重复检测的技术（例如用于查找重复页面的Google网络爬虫）中获取了灵感，更确切地说，我们应用了基于SimHash的算法。

SimHash是什么

SimHash是Google在2007年发表的论文《Detecting Near-Duplicates for Web Crawling 》中提到的一种指纹生成算法或者叫指纹提取算法，被Google广泛应用在亿级的网页去重的Job中，作为locality sensitive hash（局部敏感哈希）的一种，其主要思想是降维，什么是降维？ 举个通俗点的例子，一篇若干数量的文本内容，经过simhash降维后，可能仅仅得到一个长度为32或64位的二进制由01组成的字符串，这一点非常相似我们的身份证，试想一下，如果你要在中国13亿+的茫茫人海中寻找一个人，如果你不知道这个人的身份证，你可能要提供姓名 ，住址， 身高，体重，性别，等等维度的因素来确定是否为某个人，从这个例子已经能看出来，如果有一个一维的核心条件身份证，那么查询则是非常快速的，如果没有一维的身份证条件，可能综合其他几个非核心的维度，也能确定一个人，但是这种查询则就比较慢了，而通过我们的SimHash算法，则就像是给每个人生成了一个身份证，使复杂的事物，能够通过降维来简化。

以本文的示例为例，我们不需要每次比较每个类的一个类特性，而是计算一个表示整个类的哈希，称为类签名。这意味着可以通过简单地计算他们自己的签名之间的汉明距离来比较两个类。签名越近，类越相似。请注意，由于x86 POPCNT指令的存在，此操作在现代CPU上非常容易实现。

但是，为了产生这样的签名，必须将一组值作为输入对象。需要说明的是，必须聪明地选择这些值，因为它们必须准确地描述该类。幸运的是，可以从各个角度描述一个类：字段的数量、方法的数量、方法原型的数量、交叉引用的数量等等。请注意，这些仅与结构相关，因为诸如类名，字段或变量值（特别是字符串）之类的嵌入数据容易混淆，最好一开始就不要依赖这些特性。

因此，我们决定生成四部分32位的哈希值，这些哈希值在连接后会形成一个128位的类签名。每部分哈希表示一类信息，最后，我们得到了四类信息：

类：方法数量，字段数量，访问标志等；

字段：类型，值集（如果有的话），静态可见性等；

方法：参数数量、交叉引用数量、返回类型等；

代码：指令操作码。

下图显示了一个类签名的二进制表示形式以由四部分哈希组成的表示形式：

通过这种设计，我们就可以比较不同级别的类。例如，如果我们只想在字段级别专门比较两个类，只需要计算与字段信息对应的两部分哈希值之间的汉明距离即可。当然，我们也可以通过考虑完整的类签名来进行整体比较。请注意，此模型还允许我们在类签名上传播信息。

此外，我们会单独对待每段字节。也就是说，我们不考虑诸如父类或子类的类亲属，因为在这样的配置中，复杂性很容易增加。

那我们怎样才能在另一个簇中找到对应的比较类？此时，我们仍然面临一个问题，就是每个类签名都必须与来自其他簇的签名进行比较。要解决这个问题，就请参考来自谷歌 Project Zero的Thomas Dullien提出的策略 。

简单来说，就是构建一个哈希列表，再将其分为几个哈希桶。这样，我们不再需要逐个各个哈希，而只需使用与目标哈希具有相同属性的签名。显然，这种技术也只是一种估计，因此根据桶的数量有可能得到一些错误的结果，但它为批量比较提供了很大的权衡。我们设置的桶越多，结果就越准确。尽管如此，这仍然需要很多的资源和时间。

通过进一步研究这个策略，我们发现它就是一个搜索框架。所以，我们需要知道要查找哪些值。因此，第一步是注册来自给定簇的所有签名。为此，我们必须对每个输入签名执行n个排列，其中n是我们想要使用的桶的数量。然后，我们在一个已 排序 的容器中保留内存，这些不同的哈希值和它们的排列索引标识了排列过程中的步骤。为了识别给定签名的最相似属性，我们调用了相同的置换函数。如果哈希也共享相同的排列索引，则将其放置在候选列表中，并计算和存储它们的初始签名之间的汉明距离。

第3阶段：准确比较

此时，我们已经获得了目标类的n个属性最相近的类。尽管如此，正如我们之前解释的那样，这些结果只是基于类签名的近似值。但是，我们的目标是准确地了解目标类及对比值的相似程度。彻底的比较是完全可行的，因为对于每个类，它最多与其他三个类进行比较，这种方法显著地增加比较的准确性。

为了做到这一点，我们将目标类和上面描述的特性相似的类一个一个地提取出来，并计算它们之间的相似度百分比。然后，根据这些数据计算出总体相似度平均值。在此阶段，我们还可以根据具体情况和混淆的类型考虑其他特性，比如源文件名或嵌入字符串。

另外，我们还必须考虑实际代码，也就是说，对Dalvik字节码的相似性进行检测。这部分必须足够灵活，以匹配不同编译中的代码，这些编译可能对相同的输入Java代码使用不同的指令和不同的优化。因此，我们使用了一个抽象层作为指令的分类机制。换句话说，每个指令操作码根据其执行的操作类型进行分类。例如，由于开发人员没有修改相关的Java代码，则有一堆 invoke-*操作码可能会在比较过程中引起误差。因此，我们不是处理原始操作码，而是处理抽象操作码（abstract opcode）。抽象操作码会进行以下操作：

无(像nop)；

测试(如if-eq, if-ne)；

基本块的结束(如return-object、throw)；

比较(如cmp-long, cmpl-float)；

调用(如调用虚拟调用、调用静态调用)；

算术(比如负整数，非整数)；

转换(类似于intto -float、intto -double)；

静态字段访问(如sget-object、sget-boolean)；

实例字段访问(如iput-wide、iput-byte)；

数组访问(如new-array、filed -new-array)；

字符串(如const-string, const-string/jumbo)；

偏移(比如Move -wide/16, Move -wide/from16)；

整数(如const/16、const/4)。

请注意，我们不考虑寄存器，因为它们可能会在不同的编译之间发生变化。现在，我们将所有类方法的所有抽象操作码整合成为一个字节序列，并将整个操作码连接起来，以表示嵌入到类中的代码。此操作的目的是将这些字节序列与已知的字符串距离算法进行比较。事实证明，当方法的顺序在不同的版本中不同时，就代表发生了版本变化，因为一个给定的方法可能首先出现在1.0版本中，但是在1.1版本中第三个方法没有进行任何Java修改。

因此，我们必须事先对此进行排序。为此，我们生成一个16位签名，该签名存储方法拥有的指令数和它包含的每个操作码的XOR操作结果。然后，在对这些签名进行数字排序之后，我们能够为每个类建立最终的字节序列。由于Levenshtein算法会计算出它们之间的距离，因此可以有效地比较它们，然后将这个距离添加到上面描述的总体相似度平均值中。

最后，产生最高整体相似度平均值的相似代码就是要比较的对象，两者之间的距离用百分比表示。

评估

为了正确评估我们所对比的对象是否正确，我们对几个众所周知的应用程序的迭代版本进行了比较。至于评估的有效性，请关注下一篇文章。下表显示了我们选定的三个应用程序利用本文所述的对比方法，所得出的不同版本之间的评估结果。请注意，加载时间表示加载原始APK和修改后的APK所花费的时间。 load()操作包括DEX解析，字节码反汇编和多DEX解析。