Karta – 二进制文件中的开源匹配

介绍

“Karta”（俄语中的“map”）是IDA的源代码辅助二进制匹配插件。该插件的开发是为了匹配非常大的二进制文件（通常是固件文件）中的开源库的符号。对于那些每天处理固件文件的人来说，重复逆转net-snmp是浪费时间的; 显然需要一种工具来识别使用过的开源，并在IDA中自动匹配它们的符号。

最初的重点是匹配过程快速发生。即使我们试图进行逆向工程的二进制文件包含超过100,000个函数，也只能等待几个小时来匹配300个函数的库。然而，结合逆向工程贸易的几个教训使我们能够解决这个问题，结果好于预期。

事实证明，出于性能原因我们部署的启发式算法对匹配结果也有很大影响。该插件产生非常低的假阳性率，以及高真阳比率。这使得它甚至可以用于匹配中小型二进制文件，这不是我们最初的议程。

因此，我们认为Karta可以成为研究人员工具箱中的重要工具，并且在以下场景中非常有用：

Recon阶段 - 识别二进制中使用的开源（包括其版本）。
清除杂乱 - 匹配使用的开源的符号，从而节省时间逆向工程似乎已知的功能。
查找1天 - 使用已使用的开放源列表及其符号已在二进制文件中匹配，以轻松找到可执行文件\固件文件中的1天。

KARTA

如前所述，Karta是IDA *的源代码辅助二进制匹配插件。该插件实现了两个重要的研究目标：

标识 - 标识静态编译的开源的确切版本。
匹配 - 匹配已识别的开源的符号。

该插件现在是开源的，可以在我们的Github中找到。

由于在不同体系结构上编译开源库有时可能是一项痛苦的任务，因此我们通过使插件架构独立来消除此步骤。例如，如果我们想要匹配libpng开源的1.2.29版本（我们的HP OfficeJet固件中使用的那个），我们所要做的就是从Github克隆它并在我们的（x86）机器上编译它。在编译之后，Karta可以生成描述库的规范.json配置文件。使用此配置，即使固件已编译为Big-Endian ARM Thumb模式，我们的插件现在也可以在固件中成功找到库。

* Karta由模块组成，IDA反汇编模块可以由任何其他反汇编模块替换。感谢@megabeets_，对radare2的支持现在处于最后的开发阶段。

寻找1天

虽然我们为插件描述了几个用例，但在热门软件中查找1天可能是最有趣的。以下是我们在研究过程中发现的两个真实例子。

HP OfficeJet固件

在我们的传真研究期间，我们需要将1天用作调试漏洞。最终，我们使用了Devil的常春藤。在我们完成Karta的开发之后，是时候回到我们的固件并检查Karta如何帮助我们进行研究。

标识符插件告诉我们固件中使用的开源库是：

libpng：1.2.29
zlib：1.2.3
OpenSSL：1.0.1.j
mDNSResponder：未知
gSOAP：2.7

在这里我们可以看到确实使用了gSOAP，快速CVE搜索向我们展示了它包含一个关键漏洞：CVE-2017-9765（Devil's Ivy）。

在我们快速编译了此版本的gSOAP的配置之后，我们运行了匹配器并导入了匹配的符号。在这里，我们可以看到易受攻击的代码函数soap_get_pi与Karta匹配：

图1：反编译的soap_get_pi函数，与我们的插件匹配。

这对我们的插件来说是一个非常好的消息：它在现实生活中的情况下工作（太糟糕了，我们只在完成传真研究后才有它）。

普通的闭源程序 - TeamViewer

轻松找到1天固件很方便，但我们在Windows PC上使用的日常程序呢？在阅读Project Zero的WebRTC博客文章时，我们看到他们在名为libvpx的库中发现了一个漏洞：

CVE-2018-6155 是一个名为VP8的视频编解码器中的免费使用。这很有意思，因为它影响了VP8库libvpx而不是WebRTC中的代码，因此它有可能影响使用除WebRTC之外的其他库的软件。由于此错误，已发布libvpx的通用修补程序。

这看起来很有趣，因为Project Zero特别指出这个漏洞“有可能影响使用除WebRTC之外的这个库的软件。”我们在计算机上安装了TeamViewer，听起来它应该使用相同的开源库，让我们检查一下出来。

我们在IDA中打开了TeamViewer.exe，我们在分析过程中开始工作。我们下载了最新版本的libvpx（1.7.0），为它编写了一个简单的标识符，并将其添加到Karta中。由于我们不能等待IDA完成分析，我们停止了它并运行Karta的标识符插件。确定的公开来源是：

zlib：1.2.5
mDNSResponder：未知
libjpeg：8b
libvpx：1.6.1

TeamViewer不仅使用libvpx，而且使用2017年1月以来的旧版本。

看看Google发布的补丁，我们知道我们感兴趣的功能是vp8_deblock，如下所示：

图2： vp8_deblock函数的代码片段，易受CVE-2018-6155攻击。

我们告诉IDA恢复分析，然后继续编译libvpx版本1.6.1的Karta配置。配置完成后，IDA完成对二进制文件的分析后，我们运行了Karta的matcher插件。如您所见，匹配器发现了我们易受攻击的功能：

图3： Karta的匹配结果显示它与易受攻击的功能相匹配 - 以蓝色突出显示。

在我们将结果导回IDA之后，我们可以使用数字常量清楚地看到这是正确的匹配。

图4：易受攻击的功能，与我们的插件相匹配，如IDA Pro所示。

我们拥有它，我们在TeamViewer程序中发现了一个漏洞，我们甚至知道在调试时确切地放置断点的位置。

整个过程大约需要2个小时。唯一的瓶颈是IDA的分析，因为TeamViewer是一个非常大的程序，包含超过143,000个函数。

Karta - 它是如何工作的？

二进制匹配101

二进制匹配的核心可以解决最基本的问题：我们想要检查两个函数，一个来自编译的开源，另一个来自我们的二进制，代表相同的函数。为了能够比较这两个函数，我们需要将它们转换为统一的基本表示，通常称为“规范表示”。这种表示通常包括我们从函数中提取的一组特征：数字常量列表，列表字符串，汇编指令的数量等

当尝试匹配一组相关函数时，例如，编译的开源项目，我们在规范表示中存储附加信息，以便编码函数之间的关系：被调用函数列表（被调用者），列表调用我们的函数（调用者）等。使用此信息，我们可以尝试根据控制流图（CFG）中的规则/位置匹配两个函数。

这里我们使用一些传统的二进制匹配工具，如BinDiff或Diaphora。虽然每个匹配工具都有自己独特的巧妙匹配启发式算法，但它们都基于相同的缩减：比较两个规范表示并对结果进行评分。这意味着二进制匹配工具首先将所有函数转换为规范表示，然后从那里继续。

避免内存爆炸

在分析具有大约65,000个函数的二进制文件时，例如我们的OfficeJet打印机的固件，为所有函数构建规范表示的过程根本无法扩展。它需要很长时间（通常超过一个小时），并且可以在磁盘空间中消耗超过3GB的空间。不用说，稍后将此数据集加载到内存通常会使匹配的程序崩溃。

如果我们想要匹配巨大的二进制文件中的任何东西，我们需要改变策略。由于开源库相对较小，我们的问题可以描述为：

M - 我们的开源函数
N - 二进制中的函数数量

我们希望在大小为N的二进制中匹配M函数，其中M << N，理想情况下通过消耗依赖于M而不依赖于N的存储器。

图5：我们尝试匹配库的二进制地址空间的图示。

关键理念 - 链接器位置

如果我们将稍后讨论的特定边缘情况放在一边，我们可以删除编译过程并链接到以下步骤：

编译器独立编译每个源文件，并创建匹配的二进制文件（.o用于gcc，.obj用于visual studio）。
链接器将所有二进制文件组合成单个二进制blob。
在链接阶段，此blob将按原样插入最终程序/固件。

这导致两个重要结论：

已编译的源包含在固件/可执行文件内的单个连续blob中。
一旦我们找到该blob的单个代表（让它被称为锚点），我们就可以根据我们知道应该在这个blob中的函数数量推测二进制中这个blob的下限和上限。

从本质上讲，这是Karta所依据的关键点。

Karta - 建立地图

Karta是一个源代码辅助工具。通过利用源代码中的信息，我们可以构建一个映射：哪些函数包含在哪个文件中，以及该库包含哪些文件。

这是匹配二进制文件库的过程：

从基本标识符脚本开始，该脚本检查二进制文件是否使用该库，以及使用的版本 - O（N）时间和O（1）内存消耗。
识别后，扫描二进制文件以搜索锚函数 - O（N）时间和O（1）内存消耗。
使用定位的锚函数放大推测的二进制函数范围，这些函数可能是我们库的一部分--O（1）时间和O（1）内存消耗。
从这一点来看，所有逻辑都将在聚焦范围内，其大小为O（M）。

这是一个例子：

我们的库有322个函数，我们找到了5个锚函数。
最低锚位于二进制中的函数＃2622。
最高的锚位于二进制的函数＃2842。
锚之间包含的范围包括2842 - 2622 + 1 = 221个函数。
我们仍然需要找到322 - 221 = 101个函数。
为了安全起见，在我们的地图中，我们在第一个锚点之前包含101个函数，在最后一个锚点之后包含101个函数。
总的来说，聚焦函数的数量：101 + 221 + 101 = 423函数<<完整二进制函数中的65,000。

我们现在要做的只是为聚焦功能构建规范表示，从而大大提高了我们从这一点开始的性能。

注意：映射可以提供进一步的帮助，因为来自文件ac的函数foo（）应该只与ac中的函数匹配。这样就不需要将它与我们已经识别为驻留在不同文件中的函数进行比较。

选择我们的主播

就其性质而言，锚定函数在我们具有规范表示之前是匹配的。这限制了我们在搜索时可以使用的功能。此外，我们希望确保我们的锚点唯一地标识我们的库，并且不包括对我们正在处理的二进制文件中的其他库的任何误报。

决定复杂的独特功能的标准有点雄心勃勃，而不事先知道所有开源的外观。然而，我们写了一些似乎在实践中运作良好的启发式方法。我们扫描开源中的所有函数，并搜索唯一的数字常量和唯一字符串。如果常量足够复杂（具有高熵或足够长的字符串的数字）或者可以组合在一起足够独特（例如：同一函数中的3个唯一中等长度字符串），我们将该函数标记为锚。

以下是OpenSSL中的锚函数示例：

图6： IDA Pro中的OpenSSL函数SHA224_Init。

我们选择此函数是因为它具有独特的数字常量。

确切的规则是可配置的，可以在这个文件中找到：src / config / anchor_config.py

匹配步骤

现在我们知道Karta匹配引擎背后的主要逻辑是什么，让我们完整列出匹配的步骤。

识别码

每个受支持的库都有一个标识符，试图在二进制文件中找到它。由于大多数开源包括唯一字符串，通常具有完整版本详细信息，因此大多数标识符都是基于字符串的，并且是为他们试图识别的库配置的。找到库后，标识符会尝试提取版本信息，并指纹可执行文件/固件使用的确切版本。

图7： libpng中包含在编译二进制文件中的版权字符串。

如您所见，在大多数用例中，识别可执行文件中是否存在开源库相对容易。

虽然还有其他解决方案可用于识别阶段，例如Google最近的Project Zero 博客文章中描述的解决方案，但似乎很难与这个基本但有效的简单字符串搜索竞争。依靠我们标识符的优异成果，我们决定将大部分精力集中在匹配逻辑上，使我们的标识符保持整洁和简单。

由于我们的标识符的简化性质，我们希望其他研究人员可以轻松扩展我们的插件并添加对新开源库的支持。由于它是开源的，我们对插件的任何贡献都将有助于社区中的其他研究人员完成他们的项目。

锚点搜索

使用标识符中的信息，将加载特定库版本的配置（基于.json *）。第一步是扫描二进制文件以获取与我们库的锚函数匹配的唯一数字常量和唯一字符串。如果没有锚点，我们无法放大库并继续匹配过程。

*匹配开始后，整个配置都会加载到内存中。这消除了使用更流行的sqlite数据库的需要，因为我们没有在配置上发出查询。从sqlite到json的这种转换导致配置文件大小的大幅减少（KB而不是MB）。

文件边界

使用由匹配的锚定义的聚焦函数范围，我们绘制文件图的初始草图。我们可以精确定位包含匹配锚函数的每个文件的位置，并估计其下限和上限（使用前面描述的相同逻辑）。其余的文件被标记为“浮动”，被称为“无所不在”; 它们可以位于整个焦点区域内的任何位置。

图8：到目前为止我们匹配结果的示例图。

使用文件提示

许多开源项目往往包含包含源文件名称的调试/跟踪字符串。通常这些字符串位于上述源文件的函数中，这意味着我们可以将它们用作文件提示。绘制初始地图后，我们可以使用这些提示来确定其他文件的位置。依赖于搜索空间非常小的事实以及这些字符串的性质，这些匹配将具有相对较高的真实正比率。

定位代理商

一个代理是本地唯一的功能。它也可以称为本地锚。在它的文件中它是一个锚，但它包含的常量弱于全局锚所需的常量。每个找到的文件都会尝试匹配自己的代理，同样具有相对较高的True Positive比率。

匹配轮次

从现在开始，我们的逻辑非常传统。基于两个规范表示的相似性，每个匹配尝试都给出一个分数。当没有更多要匹配的函数（乐观场景），或者当匹配轮未能找到新匹配时，或者当内部文件识别出内部假设未能保持时，匹配结束。后一种情况经常发生在IDA存在分析问题或者存在链接器优化时（参见下一章）。

如前所述，Karta试图尽可能多地使用地理知识，包括：

函数必须仅与同一文件中的函数匹配。
其他文件中的函数不能引用静态函数。
编译器倾向于维护局部性，这意味着相邻的源函数也倾向于以二进制形式保持相邻。

已经显示这些基于位置的启发法中的每一个都显着改善了实际情况中的匹配结果。完整的匹配启发式提示列表可以在Karta的read-the-docs文档中找到，可以从我们的Github存储库中访问。

链接器优化

在此之前，我们选择忽略房间里的大象：Karta的主要假设是开源将被编译为单个连续的blob，并且内部文件不会彼此混淆。不幸的是，在使用链接器优化进行编译时情况并非如此，正如使用Visual Studio编译Windows程序时所做的那样。

实际上，当我们最初尝试在一个Adobe PDF的二进制文件（2d.x3d）中匹配libtiff时，我们得到的结果不是最佳：只有176/500个函数匹配。经过简短的调查，似乎链接器将功能与相同的二进制结构相结合。例如，使用不同名称或不同名称范围（不同文件中的静态函数）实现两次的函数。

图9：来自libtiff的两个相同的函数，它们位于不同的文件中。

图10：来自IDA Pro的分析，显示使用左侧功能而不是右侧功能。

虽然这种优化减少了可执行文件的大小，但它不仅与我们的局部性假设混淆，而且还大大改变了控制流图。两个不相关的函数（每个函数都有自己的边）将合并到调用图中的单个顶点中。稍后进行几次快速检查，我们发现这种优化也会破坏其他二进制匹配工具的匹配结果。

我们决定像链接器那样解决这个问题。在编译开源库的规范表示时，我们对每个函数的链接器视图*进行散列，并将其存储为唯一的函数ID。*最初我们自己对字节进行了哈希处理，但是当两个函数引用相同的全局变量并且该变量驻留在每个文件中的不同偏移量时，这引入了一个错误。请参见图11和12.我们通过散列大多数操作码的字节来解决此问题，并在引用导出的全局变量时散列指令的文本。

图11：来自文件tif_dirwrite.c的函数TIFFClampDoubleToFloat（）。

图12：来自文件tif_dir.c的函数TIFFClampDoubleToFloat（）。

我们的匹配器使用这些“冲突ID”来定义链接器可能决定合并在一起的潜在合并候选组。在匹配过程中，匹配器会查找任何可能合并的线索。当匹配器在控制流图中发现两个合并候选函数是相同二元函数的可能候选者时，它可以判定合并发生。做出这个决定后，二进制函数现在知道它代表了几个源函数，并且将保存它匹配的合并源函数的列表。

使用此优化，我们现在可以修复控制流图中的异常，因为每个检测到的合并有效地将控制流图扩展回链接器优化之前的原始状态。当在相同的二进制文件（2d.x3d）上再次测试时，我们得到了明显更好的结果：匹配了248/500个函数，改进了41％。

我们可以看到，Karta确定了链接器对函数_TIFFNoFixupTags的优化：

图13：匹配成功识别链接器合并函数的Karta结果。

匹配结果

是时候测试Karta如何处理我们原来的OfficeJet固件了。我们在计算机上的虚拟机（VM）中测试了插件（不是最佳的基准测试环境），结果如下：

图14：在我们测试的OfficeJet固件上匹配结果。

我们可以很容易地看到，即使有大约65,000个函数，也只需不到30秒就可以将开源与libpng等300个函数相匹配。此外，我们能够匹配所有引用的库函数，即在控制流图中至少有一个边的函数。

*验证结果的唯一方法是对IDA **中的功能进行手动分析。由于OpenSSL包含大量功能（对于开源），误报率可能更高，因为我们没有手动分析其所有功能。

**实际上，Karta被证明比我们的手动分析更准确，因为在大多数冲突中，我们发现我们错了，Karta在标记功能方面做得更好。

注意＃1：重要的是要注意，当Karta处理函数的规范表示时，它与架构无关。我们用于上述比较的配置是在x86 32位设置上使用gcc编译的，后来与Big-Endian ARM Thumb模式二进制文件匹配。

注意＃2：因为我们的匹配是从匹配的开源库的角度完成的，所以我们还可以推导出“外部”函数的信息 - 这些函数不是我们库的一部分，而是从它调用的。例如，libpng使用zlib，因此我们的匹配器甚至在开始匹配zlib之前也能够识别inflateEnd和deflateEnd函数。

图15：在libpng匹配期间匹配的外部zlib函数。

此外，在大多数情况下，我们能够匹配标准库中的函数，例如：memcpy，memcmp，malloc等。任何研究逆向固件文件的研究人员都知道缺少FLIRT签名使得必须通过以下方式启动每个项目：反转和匹配流行的libc函数。通过使用Karta，大多数流行的功能将“免费”匹配，这使我们无需弄清楚哪个功能是memcpy，哪个是memmove。

与已知的Bin-Diffing工具的比较

我们知道有时很难区分所有可用的二进制差异/匹配工具。现在我们已经完成了Karta的演示，现在是将我们的插件与其他流行工具进行比较的好时机，重点关注每个工具的不同目标和特征。请记住，我们不会对工具的结果进行基准测试，主要是因为这些工具并非针对同一目标而设计。

由于我们无法比较所有现有工具，我们选择关注以下流行工具：

BinDiff： “ BinDiff是二进制文件的比较工具，可以帮助漏洞研究人员和工程师快速找到反汇编代码中的差异和相似之处。

使用BinDiff，您可以识别并隔离供应商提供的修补程序中的漏洞修复程序。您还可以在同一二进制文件的多个版本的反汇编之间移植符号和注释，或使用BinDiff收集代码被盗或专利侵权的证据。“

Diaphora： “ Diaphora（διαφορά，希腊语为'差异'）是IDA的一个程序差异插件，类似于Zynamics Bindiff或其他FOSS对手，如YaDiff，DarunGrim，TurboDiff等......它是在SyScan 2015期间发布的。”

Pigaios： “ Pigaios（'πηγαίος'，希腊语'源''在'源代码'中）是一种用于直接对二进制文件进行差异/匹配源代码的工具。我们的想法是将工具指向代码库，无论它是否可编译（例如，部分源代码或不在您手中的平台的源代码），从该代码库中提取信息，然后导入IDA数据库函数名称（符号），结构和枚举。“

FunctionSimSearch：FunctionSimSearch是一组工具，可以有效地执行模糊搜索到相对较大的可能函数空间（二进制）。这些工具的目标是匹配已知（可能是易受攻击的）功能，以便识别静态链接的软件库*。

* Project Zero没有明确定义FunctionSimSearch的摘要。这是我们的描述，而不是他们网站的引用。

Karta（我们的插件）： “ Karta（俄语为”map“）是一个IDA Python插件，用于识别和匹配给定二进制文件中的开源库。该插件使用一种独特的技术，使其能够支持巨大的二进制文件（> 200,000个函数），几乎不影响整体性能。“

比较参数是：

开源 - 该工具是开源的吗？（是）或闭源？（没有）
架构不可知 - 它可以比较两个样本，无论它们最初编译的架构如何？
支持大型二进制文件 - 它是否支持大型二进制文件？
源代码辅助 - 它是否利用源代码中的信息来提高匹配率？
标识版本 - 它是否标识比较样本的版本？它是在匹配之前还是之后执行此操作？

这是我们的结果表：

图16：我们的匹配工具和流行的差异/匹配工具之间的比较。

注意：尽管BinDiff和Diaphora可用于比较（bin-diff）两个二进制文件，例如，对于补丁程序差异，Karta的开发目的是匹配已知开源的二进制符号。虽然这限制了可以使用Karta的用例，但其重点目标使其能够使用更简单的比较启发法实现改进的匹配率。

由于没有（已知的）银弹来解决所有二元匹配/差异问题，我们认为根据最初设计的目标来判断每个工具是很重要的。

附录A-当前支持的标识符列表

本文作者为Mr.Bai，转载请注明。

karta 二进制