我们在网络大挑战中的表现 - Trail of Bits博客

Artem Dinaburg
2015年7月15日
cyber-grand-challenge, darpa, mcsema

网络大挑战资格赛于6月3日东部时间正午举行。那一刻，我们的网络推理系统（CRS）收到了131个故意构建的不安全程序。在接下来的24小时内，我们的CRS成功识别了其中65个程序的漏洞，并重写了94个程序以消除代码中的缺陷。这无疑证明，将优秀软件审计员的行动自动化不仅是可能的，而且是可实现的。

尽管我们的CRS在发现和修补漏洞方面取得了成功，但我们未能获得明年决赛的资格。一个致命缺陷使我们的总分降至第9名，低于第7名的晋级门槛。在本博客文章中，我们将讨论我们的CRS如何工作、它与竞争对手系统的表现、导致得分失败的原因以及我们接下来的计划。

网络大挑战背景

网络大挑战（CGC）的目标是将自动化的速度和规模与人类专家的推理能力相结合。多个团队创建网络推理系统（CRS），这些系统能够自主推理任意网络程序，证明这些程序中的缺陷存在，并自动制定针对这些缺陷的有效防御措施。这些系统的效果通过头对头锦标赛式竞争进行评估。

比赛有两个主要事件：资格赛和决赛。资格赛于2015年6月3日举行，决赛定于2016年8月举行。只有资格赛前7名的竞争者才能进入决赛。

在资格赛中，每位竞争者都收到了相同的131个挑战，即故意构建的易受攻击程序，每个程序至少包含一个故意漏洞。在24小时内，竞争的CRS相互对抗，并根据四个标准评分。完整细节见CGC规则，但以下是快速总结：

CRS必须在无人干预的情况下工作。任何使用人工协助的团队将被取消资格。
CRS必须修补挑战中的错误。成功修补每个错误都会获得分数。未修补错误的挑战得零分。
CRS可以证明挑战中存在错误。如果CRS能生成导致挑战崩溃的输入，则修补挑战的分数会翻倍。
修补后的挑战必须功能正常，性能几乎与原始程序相同。根据修补挑战的性能和功能损失扣分。

DARPA提供了资格赛所有得分和用于制作本文图表的其他数据的电子表格（Trail of Bits是第9名团队）。考虑到评分标准，让我们回顾Trail of Bits CRS的架构和我们做出的设计决策。

准备工作

我们是一家拥有分布式劳动力的小公司，因此无法物理托管大量服务器。自然，我们选择云计算进行处理；具体来说是Amazon EC2。那些看到我们推文的人知道我们使用了大量的EC2时间。大部分使用纯粹出于谨慎。

我们不知道资格赛会有多少挑战——只知道“超过100个”。我们为1000个挑战做准备，每个挑战附带多GB的网络流量捕获。我们还担心EC2区域范围的故障，因此我们配置了三个不同的CRS实例，每个位于美国的不同EC2区域，亲切地命名为Biggie（us-east-1）、Tupac（us-west-2）和Dre（us-west-1）。

结果资格赛只有131个挑战，没有巨大的网络捕获。在资格赛期间，所有EC2区域正常工作。我们本可以用17个c4.8xlarge EC2实例舒适地完成资格赛，但我们使用了297个。出于过度谨慎，我们超额配置了约17倍。

错误发现

Trail of Bits CRS在发现的已验证错误数量方面排名第二（图1）。考虑到我们从零开始，而其他几个团队在CGC之前已有现有的错误发现系统，这一结果令人印象深刻。

图1：资格赛中按发现错误数量排名的团队。橙色条表示决赛选手。

我们的CRS采用多管齐下的策略来发现错误（图2）。首先是模糊测试。我们的模糊测试器使用自定义动态二进制翻译器（DBT）实现，能够在单个64位地址空间中运行多个32位挑战。这对于具有多个二进制文件相互通信的挑战是理想的。模糊测试器的插桩和变异是分离的，允许可插拔的变异策略。DBT框架还可以在执行过程中的任何点对二进制文件进行快照。这大大提高了模糊测试速度，因为可以在探索新输入空间时避免重放先前的输入。

图2：我们的错误发现架构。它是一个基于反馈的架构，使用模糊测试和符号执行探索程序的状态空间。

除了模糊测试，我们还有两个符号执行引擎。第一个操作于原始未修改的二进制文件，第二个操作于从mcsema翻译的LLVM。每个符号执行引擎都有自己的优势，两者都对错误发现有所贡献。

模糊测试器和符号执行引擎通过我们称为MinSet的系统在反馈循环中操作。MinSet使用分支覆盖来维护一组最小最大覆盖输入。输入来自任何能够生成它们的源：PCAP、模糊测试、符号执行等。每个工具从MinSet获取原始输入，并将任何新生成的输入反馈到MinSet。这个反馈循环让我们能够并行使用模糊测试器和符号执行探索可能的输入状态。在实践中，这非常有效。我们记录崩溃的来源，大多数看起来像：

网络捕获 ⇒ 模糊测试器 ⇒ SymEx1 ⇒ 模糊测试器 ⇒ 崩溃

一些错误只有在输入重放先前的随机数时才能触发，这在每次执行挑战时都会不同。我们的错误发现系统可以生成基于程序输出的变量输入，使我们的CRS能够处理这种情况。

此外，我们的符号执行器能够识别哪些输入在崩溃点影响程序状态。这是任何参加决赛的团队成功的关键要求，因为它使CRS能够创建更受控的崩溃。

修补

我们的CRS的修补效果，以安全分数衡量，排名第四（图3）。

图3：资格赛中按修补效果（安全分数）排名的团队。橙色条表示决赛选手。

我们的CRS通过使用mcsema将挑战翻译成LLVM位码来修补错误。修补应用于LLVM位码，优化后转换回可执行代码。实际的修补工作是通过在检测到无效内存访问时优雅终止挑战来完成的。修补挑战的LLVM位码表示为我们提供了巨大的能力和灵活性：

我们可以轻松验证任何内存访问并跟踪所有内存分配。
使用LLVM编译器基础设施，复杂算法（如数据流跟踪、支配树、死存储消除、循环检测等）非常容易实现。
我们的修补方法可以用于现实世界的软件，而不仅仅是CGC挑战。

我们创建了两种主要的修补策略：通用修补和基于错误的修补。通用修补是一种基于排除的策略：它首先假设每个内存访问必须被验证，然后排除可证明安全的访问。通用修补的好处是它能修补挑战中所有可能的无效内存访问。基于错误的修补是一种基于包含的策略：它首先假设只有一个内存访问（CRS发现错误的地方）必须被验证，然后包含可能不安全的附近访问。每种修补策略都有多种启发式方法来确定哪些访问应包含或排除在验证之外。

包含和排除启发式方法生成具有不同安全/性能权衡的修补挑战。这些启发式方法生成的修补挑战经过性能和安全性测试，以确定哪种启发式方法在修复错误的同时表现最佳。对于资格赛，我们评估了通用和基于错误的修补，但最终选择了仅通用修补策略。基于错误的修补性能稍好，但通用修补更全面，它修补了我们的CRS无法发现的错误。

功能和性能

功能和性能分数结合创建可用性分数。可用性分数用作通过修补和错误发现获得的分数的缩放因子。这个缩放因子只对成功修补的挑战重要，因为只有这些挑战才能得分。以下图表仅考虑成功修补挑战的功能和性能。

功能

在我们的CRS成功修补的94个挑战中，56个保留了完整功能，30个保留了部分功能，8个无法运行。在资格赛前10名团队中，我们的CRS在完全功能修补挑战方面排名第5（图4）。我们怀疑修补挑战失去功能是由于mcsema（我们的x86到LLVM翻译器）中的问题。一旦DARPA开源资格赛挑战，我们希望验证并解决这些问题。

图4：资格赛前10名团队提交的完全功能、部分功能和无法运行挑战的数量。橙色条表示决赛选手。

性能

修补挑战的性能是我们的CRS从胜利口中夺取失败的原因。在资格赛前10名团队中，我们的CRS在修补挑战性能方面排名最后（图5）。

图5：资格赛前十名参与者的平均和中位数性能分数。橙色条表示决赛选手。

我们的CRS生成慢速二进制文件有两个原因：技术原因和操作原因。技术原因是我们的修补挑战性能是我们修补过程的产物，该过程将挑战翻译成LLVM位码，然后重新发出为可执行二进制文件。操作原因是我们的修补开发较晚，并针对错误的性能测量进行了优化。

那么，为什么我们针对错误的性能测量进行了优化？官方的CGC性能测量工具被保密，因为组织者希望确保没有人可以通过操纵性能测量来作弊。因此，我们必须自己测量性能，我们的指标显示修补挑战的CPU开销通常可以忽略不计。我们观察到的主要缺陷是我们的修补挑战使用了太多内存。因此，我们花费时间和精力优化修补以使用更少内存，而不是使用更多CPU时间。

结果我们优化了错误的东西，因为我们的自我测量与官方测量工具不一致（表1）。在自我测量时，我们性能最差的修补方法中位数CPU开销为33%，中位数内存开销为69%。官方资格赛测量我们的CPU开销为76%，内存开销为28%。显然，我们的自我测量与官方测量有显著差异。

表1：自我测量的CPU和内存开销与官方资格赛的CPU和内存开销。

测量	中位数CPU开销	中位数内存开销
最差自我测量修补方法	33%	69%
官方资格赛	76%	28%

我们的CRS使用自己的性能指标测量其总分。我们CRS的自我测量分数是106，这将使我们排名第二。实际总分是21.36，使我们排名第九。

软件开发的一个重要方面是选择集中精力的地方，我们选择得很差。CGC参与者在一年中的两次评分事件中可以访问官方测量系统，一次在2014年12月，一次在2015年4月。我们应该在这两次评分事件中彻底评估我们的修补系统。不幸的是，我们的修补在第二次评分事件之后才完全运行，因此我们无法验证自我测量的准确性。我们修补的性能损失不是一个基本问题。如果我们知道它有多糟糕，我们会修复它。然而，根据我们自己的测量，修补是可接受的，因此我们将精力集中在其他地方。

下一步计划？

根据CGC常见问题解答（问题46），团队在资格赛后允许合并。我们希望与另一个获得CGC决赛资格的团队合作，利用我们双方技术的最佳部分获胜。我们CRS背后的技术将为任何与我们合作的团队提供显著优势。如果您想讨论CGC决赛的潜在合作，请通过cgc@trailofbits.com联系我们。

如果我们找不到CGC决赛的合作伙伴，我们将集中精力使我们的CRS适应自动发现和修补现实软件中的漏洞。我们的系统能够胜任这项任务：它已经证明可以发现错误，并且其所有核心组件都源自适用于真实Linux二进制文件的软件。几个组件甚至支持Windows和64位，添加对其他平台的支持是可能的。如果您对我们技术的商业应用感兴趣，请通过cgc@trailofbits.com与我们联系。

最后，我们计划为我们CRS中使用的开源项目贡献修复和更新。我们在开发过程中使用了众多开源项目，并进行了几个自定义修复和修改。我们期待将这些贡献回社区，让每个人从我们的改进中受益。

如果您喜欢这篇文章，请分享： Twitter LinkedIn GitHub Mastodon Hacker News

网络大挑战中的漏洞自动化攻防实战

Trail of Bits团队在网络大挑战资格赛中采用多策略漏洞发现与LLVM位码修补技术，成功自动化识别65个漏洞并修复94个程序，详解其CRS系统架构与性能优化教训。