驯服文件解析风险：PolyFile与PolyTracker双工具解析

解析文件很困难，即使文件格式有明确规范。但当规范存在歧义时，会导致解析器和解释器出现意外和奇怪的行为，使文件格式容易受到安全漏洞的影响。如果我们能自动生成任何文件格式的“安全”子集，以及相关的经过验证的解析器，会怎样？这是我们参与Sergey Bratus博士的DARPA SafeDocs项目的共同目标。

但首先，为什么解析如此困难？像嵌入式脚本语言、复杂的上下文相关语法以及允许对象间任意依赖的对象模型等设计决策，可能看起来是丰富格式的好方法，但它们增加了解析器的攻击面，导致忘记或绕过安全检查、拒绝服务、隐私泄漏、信息隐藏，甚至隐藏恶意负载。

这个问题的两个例子是多语言文件和分裂文件。多语言文件可以有效地被解释为两种不同的格式。你是否曾经阅读过一个PDF文件，然后惊讶地发现它也是一个有效的ZIP文件？或者编辑一个HTML文件，却发现它也是一个Ruby脚本？恭喜，你发现了一个多语言文件。这不要与分裂文件混淆：分裂文件是指两个解析器以不同方式解释同一个文件，例如，你的PDF在Adobe Acrobat或Foxit Reader中打开时显示不同的内容，或者你的HTML页面在Chrome和Internet Explorer中渲染不同。

我们开发了两个新工具，可以减轻解析的痛苦并使文件格式更安全：

PolyFile：一个支持多语言的文件识别工具，带有手动插桩的解析器，可以分层语义标记文件的字节；
PolyTracker：一个自动插桩框架，通过程序执行高效跟踪输入文件的污点。

collectively，这些工具实现了自动词法注释和解析器导航（Automated Lexical Annotation and Navigation of Parsers），这是一个反向首字母缩略词，专门为了将它们称为ALAN解析器项目而设计。

在深入了解细节之前，我们先谈谈为什么这些工具是必要的。

Ceci N’est Pas Un PDF

请起立，打开你的赞美诗集到第541页，诵读第7章第6节：

…文件没有内在意义。文件的意义——它的类型、有效性、内容——对每个解析器或解释器来说可能不同。 —Ange Albertini

你可以坐下。

Trail of Bits研究员Evan Sultanik的这次演讲给出了许多例子，说明多语言文件和诱导分裂不仅仅是巧妙的客厅把戏。例如：

Android APK/Dex多语言文件已被用于绕过代码签名检查；
一个PDF也可以是一个有效的PostScript文件，当打印时，会覆盖你的打印机固件；
一个精心制作的tarball也可以是一个有效的.tar.gz文件，包含完全不同的内容。

一个PDF甚至可以是一个有效的git仓库，当克隆时，包含生成PDF的LaTeX源代码和自身的副本。Ange Albertini还有一个优秀的系列视频介绍古怪的文件技巧。

理解一个流行文件格式需要什么，该格式在20多年中不断积累功能（和缺陷）？PDF正好提供了这样的挑战。

嵌入式图灵完备编程语言？👌
允许内存和计算拒绝服务的流解码器任意链？👌
指定流对象长度的多种、冗余且可能冲突的方式？👌
文件前后允许任意数据？👌
多种隐写嵌入数据的方式，包括任意长度的二进制块？👌
基于图的文档对象模型，允许并在某些情况下需要循环？👌
数十年历史，规范模糊或不完整，导致数十个冲突的实现，其中一些发出不合规的畸形文档？👌
解析器实现必须对畸形具有弹性，但也可以自由地以不同方式处理它们？👌
规范阻碍了在Coq中创建形式验证解析器，因为Coq无法证明一个试图尽力检查间接引用的解析器在恶意制作的文件上会终止？👌

挑战接受！公平地说，PDF在定义更简单、缩减的格式子集方面处于领先地位。PDF/A旨在确保PDF文档可长期保存解析，已移除了一些有问题的功能。而且，这些问题绝非PDF特有：它们普遍存在于文档格式中。例如，Microsoft Office的OOXML做得并不更好，存在严重的在野利用的外部实体攻击，更不用说基于XML的漏洞，如十亿笑攻击。即使解析JSON也比想象中困难，UTF-8也是如此。

但在编程语言领域，至少一切应该都好，因为它们的解析器是由经典算法和经过验证的工具从明确规范自动生成的。并非如此：这个Empire Hacking演讲给出了例子，说明即使没有恶意，设计不良的语言也会导致解析问题。一个人不能简单地走进调车场！

但回到数据格式。鉴于上述挑战，我们不再关注规范，而是检查规范的事实解释：解析器实现。我们的基本假设是，文件格式的“不安全”部分将存在于解析器接受语法的对称差中。文件格式中要保留的部分是所有实现等效接受和解释的部分。

PolyFile：文件语义的基础真值标注

文件识别工具大体上是愚蠢的，因为它们只是将文件与各种格式的魔法字节签名进行比较。而且，这些工具在找到第一个匹配项后终止，不会递归识别嵌入的文件类型或不从字节偏移零开始的文件。一旦文件被分类，通常几乎没有关于文件内容的信息。它是一个PDF，但它包含多少对象？它是一个ZIP，但它的文件内容是什么？

我们的新PolyFile项目解决了这些问题，并提供：

识别输入中嵌入的任何和所有文件，不一定从字节偏移零开始；
对于有插桩解析器的文件格式，应完全解析，发出输入内容的分层语义映射；
交互式文件资源管理器，供人检查其内容和结构；
计算机可读输出，可用于为输入文件的每个字节分配语义含义（例如，字节x对应PDF流对象中的第一个字节，以及JPEG/JFIF头的开始）。

一个相当理想的文件识别工具，不是吗？

Ange Albertini的SBuD项目在精神上接近，但目前只支持几种图像格式。即使流行的Unix file命令也只支持几百种文件签名。相比之下，PolyFile支持超过10,000种文件格式，并可以递归识别文件中的它们，发出分层映射作为SBuD JSON格式的扩展。它还支持基于Kaitai Struct声明性文件格式规范对文件进行语义标记。

此外，PolyFile可以选择发出一个自包含的HTML文件，带有交互式十六进制查看器和语义标记资源管理器。这里是Evan Sultanik提交给Trail of Bits的简历的HTML输出示例。除了是一个显示自身MD5哈希的PDF外，它还是一个有效的任天堂娱乐系统ROM，当模拟时，是一个可玩显示PDF MD5哈希的游戏。它也是一个有效的ZIP文件，包含除其他外，一个PDF，该PDF是一个包含其LaTeX源代码和自身副本的git仓库。

PolyFile是免费和开源的。你可以在https://github.com/trailofbits/polyfile下载副本。

解析器插桩

现在我们有了PolyFile提供基础真值，我们需要一种方式通过解析器传播语义标签；程序等效于在CT扫描中使用对比染料跟踪大脑中的血流。因此，我们需要一种自动方式插桩解析器以跟踪这些标签，目标是将函数与它们操作的输入文件的字节偏移关联起来。由于PolyFile可以告诉我们这些偏移背后的语义含义，这将让我们推断解析器函数的目的。例如，如果PDF解析器中的一个函数总是操作与JFIF流对象关联的字节，我们可以假设它负责处理嵌入的JPEG。

有几个现有项目使用各种方法做这种污点跟踪。最好维护和最容易使用的是AUTOGRAM和TaintGrind。然而，前者限于JVM上的分析，后者Valgrind插件在每次跟踪几个字节时遭受不可接受的运行时开销。例如，我们使用TaintGrind在中等大小PDF语料库上运行mutool（muPDF项目中的一个实用程序），在每种情况下，工具必须在超过24小时执行后停止，而这些操作在没有插桩时通常在几毫秒内完成。

乍一看，我们的目标似乎由AFL-analyze满足，这是一个与AFL fuzzer捆绑的工具。在某种意义上，我们的目标实际上是创建它的对应物。AFL-analyze使用模糊测试从解析器逆向工程文件格式。在我们的案例中，我们有文件格式的基础真值，并想逆向工程解析器。

尽管用于模糊测试，Angora的污点分析引擎具有许多必要功能来跟踪执行期间的字节索引。事实上，如以下部分所述，我们建立在Angora的许多算法进步之上，同时提高计算和内存效率。Angora建立在LLVM数据流消毒剂（dfsan）之上，我们也利用它用于PolyTracker。以下部分描述dfsan的操作、限制，以及我们如何改进dfsan和Angora。

LLVM和数据流消毒剂

我们选择建立在LLVM上的静态插桩方法，因为这允许我们插桩任何能够用LLVM编译的解析器，并最终插桩闭源解析器（例如，通过使用Remill或McSema将其二进制文件提升到LLVM）。

LLVM有一个用于传播污点的插桩工具，称为数据流消毒剂（dfsan），也被Angora使用。然而，dfsan对程序执行期间跟踪的总污点数施加了严重限制，这意味着，在实践中，我们一次只能跟踪几个输入字节。要了解原因，考虑一个解析器执行以下操作：

1
2
3
4


fd = fopen("foo.pdf", "rb");
a = fgetc(fd);
b = fgetc(fd);
c = a + b;

在这种情况下，dfsan将用字节偏移0标记变量a，用污点偏移1标记变量b。字节c将被字节0和字节1标记。这里的组合挑战是有2^n种可能的污点，其中n是输入文件中的字节数。因此，使用位集存储污点的朴素方法将不可行，即使对于少量输入，即使使用压缩位集。

dfsan通过在其称为“联合表”的数据结构中存储污点来源来解决表示问题，这是一种计算高效的方式存储污点联合的二进制森林。每个污点获得一个唯一的16位标签。然后，在上面的例子中，a的污点与b联合创建c，dfsan将记录union_table[a的标签][b的标签] = c的标签。

此后，如果a和b再次联合，c的污点标签可以重用。这允许常数时间联合表检查；然而，表本身需要O(n^2)存储。这非常浪费，因为表几乎总是非常稀疏。这也是为什么需要使用16位污点标签，因为使用更大的标签会指数增加联合表的大小。这意味着dfsan最多只能跟踪65,536个污点 throughout execution，包括从联合创建的所有新污点。这不足以一次跟踪多个输入字节。

介绍PolyTracker：高效二进制插桩用于通用污点跟踪

我们新颖的污点跟踪数据结构和算法——以及许多减少计算开销的启发式方法——体现在我们的新PolyTracker工具中。它是clang和clang++的包装器，允许你插桩任何可执行文件。只需在正常构建过程中用PolyTracker替换你的编译器。生成的可执行文件将创建一个JSON文件，包含函数到每个函数操作的输入文件字节偏移的映射。而且，由于PolyTracker构建为LLVM传递，它可以用于任何已提升到LLVM/IR的黑盒二进制文件，即使源代码不可用。

我们保持了dfsan的影子内存概念及其用于跟踪污点的插桩框架。然而，我们摆脱了联合表，并实现了一个可扩展的数据结构，能够利用污点联合中固有的稀疏性。这通过污点联合的二进制森林增强，取代了dfsan的标签数组，允许我们将污点标签的大小增加到16位以上。PolyTracker的二进制森林数据结构使用内存布局算法，消除了对Angora式污点标签到位向量查找表的需求，同时提供常数时间插入。这将内存需求从指数减少到输入文件大小加上解析器执行的指令数的线性，代价是在后处理中进行O(n log n)图遍历以解析污点。在实践中，这对大多数PDF来说导致可忽略的执行开销。

PolyTracker是免费和开源的。你今天可以在https://github.com/trailofbits/polytracker下载副本。

易于开始

PolyFile可以用这个快速命令安装：

1

pip3 install polyfile

PolyTracker需要LLVM的工作构建。然而，我们通过