Karta在二进制文件中匹配开放源代码

介绍

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

最初的重点是快速进行匹配过程。仅仅为了匹配一个包含300个函数的库而等待几个小时是不可接受的，即使我们试图反向工程的二进制文件包含超过100000个函数。然而，结合逆向工程贸易中的若干经验教训，我们得以解决这一问题，取得了比预期更好的结果。

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

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

●侦察阶段—识别二进制文件中使用的开放源代码（包括其版本）。

●清除杂波—匹配使用过的开放源代码的符号，从而节省时间反向工程似乎是已知的功能。

●查找1天—使用已使用的开放源代码列表，其符号已在二进制文件中匹配，以便在可执行文件\固件文件中轻松查找1天。

Karta

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

1.标识–标识静态编译的开放源代码的确切版本。

2.匹配–匹配已识别的开放源代码的符号。

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

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

*Karta由模块组成，IDA分解器模块可由任何其他分解器模块替换。多亏了 megabeets_，对radare2的支持现在处于最后开发阶段。

发现oneday

虽然我们描述了插件的几个用例，但在流行软件中找到oneday可能是最有趣的。以下是我们在研究过程中发现的两个现实例子。

HP OfficeJet固件

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

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

libpng:1.2.29

zlib:1.2.3

OpenSSL:1.0.1.j

mDNSResponder:未知

gSOAP:2.7

在这里，我们可以看到gSOAP确实被使用，快速的CVE搜索显示它包含一个关键漏洞：CVE-2017-9765（魔鬼常春藤）。

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

对于我们的插件来说，这是一个好消息：它在现实场景中按预期工作（太糟糕了，我们在完成传真研究后才有了它）。

普通闭源程序——TeamViewer

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

CVE-2018-6155是一款名为VP8的视频编解码器的免费使用。这很有趣，因为它影响了VP8库libvpx，而不是WebRTC中的代码，因此它有可能影响使用该库而非WebRTC的软件。由于此错误，发布了libvpx的通用修复程序。

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

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

●zlib:1.2.5

●mDNSResponder:unknown

●libjpeg:8b

●libvpx:1.6.1

TeamViewer不仅使用libvpx，还使用2017年1月的旧版本。

看看谷歌发布的补丁，我们知道我们感兴趣的函数是vp8_deblock，它看起来像这样：

我们告诉IDA继续分析，并继续编译libvpx的Karta配置，版本1.6.1。一旦配置就绪，在IDA完成分析二进制文件后，我们运行Karta的matcher插件。如您所见，匹配器发现了我们的易受攻击函数：

将结果导入IDA后，我们可以清楚地看到，使用数值常量，这是一个正确的匹配。

我们在TeamViewer程序中发现了一个漏洞，我们甚至知道在调试时将断点放在哪里。

整个过程大约需要2个小时。唯一的瓶颈是IDA的分析，因为TeamViewer是一个相当大的程序，包含超过143000个函数。

Karta—它是如何工作的？

二进制匹配101

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

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

这里我们使用一些传统的二进制匹配工具，如BinDiff或Diaphora。虽然每个匹配工具都有自己独特的智能匹配启发式，但它们都基于相同的简化：比较两个标准表示并对结果打分。这意味着二进制匹配工具从将所有函数转换为它们的规范表示开始，然后继续。

避免内存爆炸

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

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

●M–我们开放源码中的函数数量

●N–二进制函数的数量

我们希望在大小为N的二进制中匹配M函数，其中M<

关键思想——链接器位置

如果我们将稍后讨论的特定边缘案例放在一边，我们可以简化编译和链接到以下步骤的过程：

1.编译器独立编译每个源文件，并创建一个匹配的二进制文件（.o用于gcc，.obj用于visualstudio）。

2.链接器将所有二进制文件合并为一个二进制blob。

3.在链接阶段，该blob将按原样插入最终程序/固件。

这导致了两个重要结论：

1.编译的源代码包含在固件/可执行文件内的单个连续blob中。

2.一旦我们找到了该blob的单个代表（让它称为锚定），我们就可以根据我们知道的该blob中应该存在的函数的数量来推测二进制中的blob下界和上界。

本质上，这是Karta所基于的关键点。

Karta—构建地图

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

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

1.从一个基本标识符脚本开始，该脚本检查二进制文件是否使用库，以及使用哪个版本——O（N）时间和O（1）内存消耗。

2.一旦确定，扫描二进制文件以搜索锚函数——O（N）时间和O（1）内存消耗。

3.使用定位的锚函数放大可能是我们库的一部分的二进制函数的推测范围–O（1）时间和O（1），内存消耗。

4.从这一点开始，所有逻辑都将集中在大小为O（M）的聚焦范围上。

下面是一个例子：

●我们的库有322个函数，我们发现了5个锚函数。

●最低锚在二进制中的函数#2622处。

●最高锚在二进制中的函数#2842处。

●锚之间的包含范围包括2842–2622+1=221个函数。

●我们仍然需要找到322–221=101个函数。

●为了安全起见，在我们的地图中，我们在第一个锚之前包含101个函数，在最后一个锚之后包含101个。

●总的来说，聚焦函数的数量：101+221+101=423个函数<<65000个。

我们现在所要做的就是只为集中的函数构建一个规范表示，从而从现在开始大幅提高我们的性能。

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

选择我们的锚

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

在不事先知道所有开放源代码是什么样子的情况下，决定复杂独特功能的标准有点雄心勃勃。尽管如此，我们编写了一些在实践中似乎效果良好的启发式方法。我们扫描开源中的所有函数，并搜索唯一的数值常量和唯一的字符串。如果常数足够复杂（具有高熵的数字或足够长的字符串），或者可以组合在一起以具有足够的唯一性（例如：同一函数中有3个唯一的中等长度字符串），我们将该函数标记为锚。

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

我们选择此函数是因为它具有唯一的数值常数。

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

匹配步骤

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

标识符

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

说开源项目试图在编译后的二进制文件中隐藏它们的存在与事实相去甚远。这些库不仅通常包含唯一的字符串，简短的谷歌搜索可以识别为原始库的线索，它们通常包含不必要的信息。这是一个来自libpng它是一个使用二进制文件编译的字符串：

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

虽然识别阶段还有其他解决方案，例如Google的零项目最近的博客文章，但似乎很难与这种基本但有效的简单字符串搜索竞争。依靠标识符的出色结果，我们决定将大部分精力集中在匹配逻辑上，保持标识符简洁明了。

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

锚点搜索

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

*一旦比赛开始，整个配置就会被加载到内存中。这消除了使用更流行的sqlite数据库的需要，因为我们没有关于配置的查询。这种从sqlite到json的转换导致配置文件的大小（KBs而不是MBs）大大减少。

文件边界

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

使用文件提示

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

定位代理

代理是本地唯一的功能。它也可以称为本地锚。在其文件中，它是一个锚点，但它包含的常量比全局锚点所需的要弱。每个定位的文件都尝试匹配其自己的代理，同样具有相对较高的真阳性率。

匹配回合

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

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

●函数必须仅与来自同一文件的函数匹配。

●静态函数不能被其他文件中的函数引用。

●编译器倾向于保持局部性，这意味着相邻的源函数也倾向于以二进制形式保持相邻。

这些基于位置的启发式方法中的每一个都已被证明可以显着改善真实案例场景中的匹配结果。可以在Karta的read-the-docs文档中找到匹配启发式技巧的完整列表，该文档可从我们的Github存储库。

链接器优化

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

实际上，当我们最初尝试在Adob​​e PDF的一个二进制文件(2d.x3d)中匹配libtiff时，我们得到的结果并不理想：只有176/500个函数被匹配。经过简短的调查，链接器似乎将具有相同二进制结构的功能组合在一起。例如，一个函数以不同的名称或在不同的名称范围（来自不同文件的静态函数）实现了两次。

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

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

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

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

正如我们所见，Karta确定了链接器对函数_TIFFNoFixupTags的优化：

匹配结果

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

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

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

**实际上，事实证明，Karta比我们的手动分析更准确，因为在大多数冲突中，结果证明我们错了，并且Karta在标记函数方面做得更好。

注意#1：重要的是要注意，由于Karta致力于功能的规范表示，它与架构无关。我们用于上述比较的配置是在x86 32位设置上使用gcc编译的，后来匹配到Big-Endian ARM Thumb模式二进制文件。

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

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

与已知Bin-Diffing工具的比较

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

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

BinDiff：“BinDiff是一个二进制文件的比较工具，它可以帮助漏洞研究人员和工程师快速发现反汇编代码中的异同。

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

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

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

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

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

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

比较参数为：

●开源——该工具是开源的吗？（是）还是闭源？（不）

●架构不可知论——它可以比较两个样本，而不管它们最初编译到的架构是什么？

●支持大型二进制文件——它是否支持大型二进制文件？

●源代码辅助——它是否利用源代码中的信息来提高匹配率？

●识别版本——它是否识别比较样本的版本？它是在匹配之前还是之后执行此操作？

 这是我们的结果表：

注意：虽然BinDiff和Diaphora可用于比较(bin-diff)两个二进制文件，例如，用于补丁差异，但Karta的开发目标是匹配已知开源的二进制符号。虽然这限制了Karta可以使用的用例，但其重点目标使其能够使用更简单的比较启发式方法来提高匹配率。

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

研究者：Eyal Itkin

原文地址：https://research.checkpoint.com/2019/karta-matching-open-sources-in-binaries/