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

网络大挑战资格赛于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：资格赛前10名参与者的平均和中位数性能分数。橙色条表示决赛选手。

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

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

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

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

我们的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中使用的开源项目贡献修复和更新。我们在开发过程中使用了众多开源项目，并进行了几个自定义修复和修改。我们期待将这些贡献回社区，以便每个人都能从我们的改进中受益。