文件标题：在堆中寻找针：结合二进制分析技术触发免费使用

在堆中寻找针：结合二进制分析技术触发免费后使用乔斯林·费斯特引用此版本：乔斯林·费斯特。在堆中寻找针：结合二进制分析技术触发免费后使用。密码学和安全学[cs.CR]。格勒诺布尔阿尔卑斯大学，2017年。英语。NNT：2017GREAM016。电话：01681707v2HAL ID：电话：01681707https://theses.hal.science/tel-01681707v2提交日期：2018年HAL是一个多学科的开放存取档案馆，用于存放和传播科学研究论文，无论它们是否被公开。论文可以来自法国或国外的教学和研究机构，也可以来自公共或私人研究中心。L’archive ouverte pluridisciplinaire他们是要获得的等级格勒诺布尔阿尔卑斯山的共同点Specialit e：在规范中2016年5月25日我的朋友们乔斯林·费斯特E大学玛丽-洛尔·P·奥特和洛朗·穆尼尔著在Verima g中进行预处理和博士学校数学，科学和技术的l’information,在堆中寻找针：结合二进制分析技术触发免费使用2017年12月29日，他的妻子去世了，她去世了。菲利普·艾尔巴兹-文森特Prof esseur，Univ ersit e Grenob le Alpes，Pre sident伊芙丝·勒·特里昂Prof esseur，Univ ersitedu Lux embourg，Rappor teur文森特·尼科米特图卢兹INSA教授，报告员帕斯卡尔·库克TrustInSoft科学总监-巴黎，审查员奥雷利安·弗朗西斯Eurecom-Sophia-Antipoli会计硕士，审查员萨拉·泽诺空客集团创新研发项目负责人-Suresnes，审查员玛丽-劳尔·波特Prof Esseur，Grenob le INP，直接冰由the' se劳伦特·莫尼耶来自Confrences，Univ ersiteGrenob le Alpes的Mtre，the se的联合主任23摘要安全性正成为软件开发中的一个主要问题，无论是软件发行商、最终用户还是政府机构。一个典型的问题是漏洞检测，它包括在代码中发现可能使攻击者获得一些不可预见的特权（如读取或写入敏感数据）的错误，甚至劫持程序执行。因此，发现漏洞的问题是一个主要问题，但在没有安全规则的软件中检测漏洞是一项艰巨的任务。自动化程序分析技术的使用有助于安全研究人员减少检测工作量。本文提出了一种实用的方法来检测一种特定类型的漏洞，称为释放后使用，当堆内存块在释放后被使用时会出现这种漏洞。释放后使用漏洞是最近许多漏洞利用的根源，其中大多数是在Web浏览器中。这种缺陷很难发现，需要专门的方法和模型来很好地说明。当前检测它们的系统通常基于一种特定的方法，并且太窄而不能找到其触发背后的复杂模式，或者太昂贵而不能扩展和应用于安全目的。在本文中，我们建议将两种众所周知的程序技术分析、静态分析和动态符号执行结合起来，以利用每一种技术的优点而不存在它们的缺点。更具体地说，我们设计了一个粗糙的颗粒和无声的静态分析器，称为GUEB，建立是有效的，当应用于二进制代码。我们提供的内存模型非常适合跟踪在释放后使用中涉及的堆操作（分配、释放和使用）。这导致了包含要进一步分析的潜在候选者的程序切片。我们的静态分析通过在多个现实世界应用程序中发现以前未发现的漏洞来证明其优势。在该方法的第二步中，在Binsec平台内开发的专用引导动态符号执行用于检索具体的程序输入，以触发这些免费后使用。虽然动态符号执行往往会迷失在程序的许多可能的执行路径中，但这种组合允许引导探索直接走向释放后的使用。这种关联的有效性通过其在现实世界程序中的应用得到证明。我们的方法既可扩展又精确，足以应用于真实的二进制文件。所有工具链都在运行x86二进制代码的开源45谢谢你如果没有许多人的帮助和支持，这个th'ese，这是几年前一个tr a v ail的fruit，是不可能成功的首先，我要感谢我的教练、Marie-LaureP Otet和Lau rentMounier，感谢他们这些年来的经验和建议。 此外，我还要感谢菲利普·埃尔巴兹-文斯、P·阿斯卡尔·库o q、Au réelien Francillon、伊夫·勒特拉翁、文森特·尼科梅特和莎拉·曾努，他们通过不断的反馈和问题，使我能够改进我的手稿。我的感谢自然也是我的朋友和朋友的Verimag。 特别是Gust avoGrieco，他从一开始就帮助我并分享他的知识，Ozgun Pinarer，没有他，这将是一个更困难的测试，Ma r iuca和Mihail As a v oae，一个和我在一起的人，没有太多的时间（和其他人），卢伊的杜罗伊，我和他一起探索了这个国家的历史，T a Thanh Dinh，我们的讨论和马克西姆·普伊斯，他在我担任首席执行官的最后几个月里一直支持我。我有一个操作portunitedeparticiperactivemetaSecurimagdurantmeseesdethese. 因此，我感谢所有使协会得以生存的人感谢的名单太长了，但我想感谢卡里姆·霍森在Securimag和我的travaux中的帮助，以及FranckDeGoerpav在我不能再这样做的时候接受了他的帮助我也很感谢弗洛朗·奥特罗，他在无数次的喷气式飞机上支持我。如果没有他的帮助，过去的岁月会更加艰难。如果没有伊琳娜·尼古拉的帮助，这份手稿就不会有同样的质量，我也感谢她对这些冗长的文章的支持。最后，我对我所有的公关人员和家人都有一个很好的评价，他们并不总是支持我和我的家人。我特别感谢我的父母，他们通过不懈的努力，为我的父亲、姐姐和我自己，在我们的生活选择和决定中看到了自由。67内容。1引言11.1程序漏洞11.2自动发现漏洞：背景21.3论文目的31.4论文大纲4我触发免费后使用：概念和贡献2 堆漏洞72.1堆特性72.2 免费后使用112.3 检测和防止免费使用：最新技术3 说明全球方法193.1贡献概述193.2 激励性论文示例203.3 用于检测免费后使用的静态分析213.4 引导式动态符号执行243.5 真实世界分析25静态分析27静态分析：大纲294 实用二进制水平静态分析4.1价值集分析：概念和基础314.2 对二进制代码的静态检测释放后使用的要求4.3 循环解卷334.4 内联功能4.5 分析二进制代码的启发式方法4.6 内存型号394.7VSA作为前向数据流分析464.8 结果的有效性4.9 与最新技术4.10 结论535免费后使用检测555.1具有分配状态55的85.2 免费后使用检测605.3 免费后使用变体615.4 自由使用后表示和分组645.5堆状态建模的相关工作705.6 结论716 GUEB：实施和基准726.1设计736.2 GUEB在测试案例74中的验证6.3 查找新漏洞776.4 案例研究：gnome-nettool786.5 GUEB79的可伸缩性6.6 局限性和前景83静态分析：贡献摘要85III引导式动态符号执行87引导式动态符号执行：大纲897引导式动态符号执行917.1动态符号执行：背景917.2WS-GuidedDSE957.3Oracle检测免费后使用1037.4指导性EHR：结果的7.5指导DSE：相关工作1077.6结论1078 精炼DSE勘探1098.1替代距离评分：随机步行1098.2 探索调整：库1148.3 路径预测改进：C/S策略1168.4 路径预测改进：初始内存1178.5 结论1199 指导性EHR：初步结果1219.1BINSEC/SE . ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...1219.2全球方法的验证9.3JasPer：案例研究1239.4实验局限性1269.5结论和观点126指导性EHR：贡献摘要129IV结论131参考书目137工具参考145附录147激励性示例1499B Gnome-Nettool151C Gnome-nettool：stub1531第一章简介1.1程序漏洞一个计算机程序被设计来执行一组特定的任务，它的行为取决于给予它的输入。在一个完美的世界里，程序总是以它的开发者所预期和用户所期望的方式做出反应。不幸的是，在现实世界中，程序包含bug，因此，有时程序并不像预期的那样。自从计算机科学非常开始[Sha87]以来，开发人员无意中设计了包含错误的程序。虽然一些行业，特别是那些使用关键系统的行业，投入了大量的资金和精力来设计可靠的软件，并验证和保护其组件，但大多数开发人员在编程时并不遵循严格的规则。因此，软件中的错误数量总体上是巨大的。例如，在撰写本文时，Ubuntu中打开的bug数量超过120，000个。修复一个bug是非常耗时的，而且有这么多bug，修复所有bug是不现实的。错误可以根据其影响进行分类，我们可以区分：• 良性错误（对程序行为几乎没有影响）• 更改程序功能或性能的错误• 降低系统安全性的错误称为漏洞。本文重点介绍了漏洞。OWASP将漏洞定义为[OWA]漏洞是应用程序中的漏洞或弱点，可能是设计缺陷或实现错误，使攻击者能够对应用程序的利益相关者造成伤害。有几种类型的漏洞。例如，密码图形算法设计中的错误可能导致加密无用。在另一种方法中，注入攻击（如SQL注入）的存在是因为缺乏对用户输入的验证，而用户输入在某个点上被解释为命令或查询。这种注入攻击可能导致读取、修改系统数据，甚至直接在系统中执行命令。一类特殊的漏洞侧重于与程序关联的内存中发生的错误;这些错误称为内存损坏。本文中研究的漏洞属于这一类。利用内存损坏可能会导致严重后果，其中最典型的是：• 系统不可用（例如：拒绝服务攻击）;• 关键信息泄漏（如加密密钥）在最坏的情况下，整个系统可能会受到损害（例如：如果漏洞利用导致执行未经授权的代码）。恶意软件还经常使用内存损坏来感染主机，并允许它们传播到所有未修复的系统。一些漏洞在过去几年中因其影响而广为人知;例如，Dirty Cow [Gooa]、Stagefright [Fin]或Heartbleed[McM]是最近的·2这些漏洞影响了大量的系统，甚至引起了主流新闻媒体的注意。漏洞会给开发人员带来成本。弄清楚如何修复它们需要时间，更重要的是，部署适当的修复程序可能会很昂贵。此外，当它们影响程序的用户时，它们也会影响开发者或公司的公众形象，并降低用户对其产品的信心。然而，未修复漏洞的实际成本很难评估。另一方面，现在有一个买卖漏洞的市场，为它们支付的价格正在稳步上升。 例如，越来越多的公司通过漏洞奖励计划为报告的漏洞提供补偿。一些公司（如Zerodium1）甚至将其业务模式建立在采购和转售漏洞的基础上。他们中的一些人愿意为他们中的一些人支付数百万美元。脆弱性市场不再它只涉及软件出版商，但也涉及政府机构和武装部队。由于使用包含漏洞的程序所带来的危险，查找这些程序的能力是一个重要问题。1.2自动发现漏洞：背景手动查找漏洞既复杂又耗时。如今，安全研究人员使用程序分析技术来帮助他们发现漏洞。这些技术通常分为两类：1. 动态分析，如模糊子[SGA07]。这个想法是为了产生投入，用于给项目带来压力，从而引发脆弱性;2. 静态分析，包括分析程序而不实际执行它。静态分析喜欢模拟运行时可能出现的行为。通过创建输入，Fuzzers探索程序的具体执行。由于可能的不同执行的数量可能很大，并且由于模糊器是在有限的时间内应用的，因此这种分析导致只探索被测程序的可能行为的一部分。Fuzzers属于对可能的程序行为执行次近似的然而，在安全行业中，模糊器被广泛使用，并在检测漏洞方面显示出实用的效率。例如，开源模糊器有一个广泛的发现漏洞列表，其中我们提到了AFL [Zal]、radamsa [Hel]、quickfuzz [GCB]。静态分析被广泛用作技术验证;特别是，静态分析的一个关键特性是它可以证明不存在错误。然而，静态分析有一个主要问题：错误警报的数量增加。大多数静态分析器都是基于对程序可能行为的过度近似而构建的这种过度近似导致考虑实际上不可行的可能路径。大多数基于静态分析的工具都声称可以在没有漏洞的地方找到漏洞。此外，由于其性质，静态分析受到不可判定问题的限制[Lan 02];然后需要假设和限制。因此，在安全社区中采用静态分析更加困难。在过去的十年里，我们目睹了试图在静态和动态分析之间实现折衷的新技术动态符号执行（DSE）就是其中之一DSE是一种程序路径探索方法，它将程序的动态执行与符号推理相结合。此技术为每个探索的路径生成输入，并且类似于模糊处理器，仅探索程序可能行为的一部分。每个技术分析程序都有其优点和缺点;越来越多的方法试图结合不同的技术，以受益于其优点而不受其缺点的影响。二进制分析的必要性在实践中，程序的源代码并不总是可用的。此外，虽然源代码可能可用，但它的库不需要它。在这种情况下，提供直接在二进制代码上工作的程序分析技术的能力变得至关重要。动态分析本质上通常适用于程序的二进制版本。另一方面，静态分析在大多数情况下被设计为在源代码上工作。虽然在二进制级别上工作会给分析带来一些困难（因为一些信息丢失），但它也有其优点：1https://www.zerodium.com3可以使用未定义的语言行为编写程序。两个不同的编译器可以生成两个具有不同行为的不同二进制文件。通过分析二进制代码，我们考虑了对这些未定义行为的实际解释;当应用于二进制文件时，不同技术（如静态和动态分析）的组合是很容易的;我们不依赖于源代码的任何假设或表示，所分析的代码自始至终都是相同的。1.3论文目标一些类型的内存损坏，如缓冲区溢出或整数溢出，已经得到了很好的研究。相比之下，最近的漏洞类别，如免费后使用或类型混淆，没有得到太多的关注。本文的重点是前一个：免费后使用。更具体地说，它喜欢在二进制代码上使用自动程序分析技术触发免费后使用触发而不仅仅是检测它是使自动程序分析对安全研究人员具有吸引力的要求，因为通过实际触发漏洞，我们证明了它的真实性。为了实现这一目标，我们的方法基于两种形式化方法的结合：静态分析和动态符号执行。本文旨在填补理论与实践之间的空白。因此，我们特别努力使我们的方法适应现实世界的例子。我们选择了两种经典的形式化方法，静态分析和动态符号执行，并研究了如何将它们用于安全目的，以及如何将它们应用于免费使用。我们根据实际观察设计了几种启发式方法，使我们的分析适用于现实环境。因此，我们的贡献属于实验科学的范畴;我们正在失去标准形式方法的健全性，但我们方法的适用性是我们的主要动机之一。如前所述，静态分析是一种功能强大的方法，但其用于安全目的的采用仍然有限。此外，"免费使用后"是堆中出现的漏洞。对这样的结构建模是静态分析的一项复杂任务;处理它通常需要付出近似的代价。我们在静态分析方面的工作可以分为两个轴。第一个重点是如何设计一个静态分析器在二进制代码级别上工作，以在精度和可扩展性之间保持可接受的权衡第二个解决了堆模型和当前的免费后使用检测。更具体地说，我们的方法适用于检测具有可接受数量的误报的漏洞，这由使用我们的静态分析器在六个不同的现实世界程序上动态符号执行的目标动态符号执行是一个活跃的研究领域。然而，在现实世界的应用中使用这种方法仍然具有挑战性，并且基于这种技术的工具通常需要调整才能适用。在本文中，我们通过使用来自静态分析的信息来增强动态符号执行此组合允许快速触发目标漏洞。我们还为我们开发的动态符号执行提供了几种重新排序启发式，使我们的工具在现实世界程序上工作。为了证明我们的方法的适用性，我们使用它来创建一个输入，触发与我们的静态分析器发现的以前未知的漏洞相对应的释放后使用。虽然自动化漏洞查找工具已成为一个活跃的研究领域，但安全社区仍然缺乏可用的解决方案。大多数工具从未发布，但尚未生效，程序分析工具需要大量的工程工作。更重要的是，为了有效，实验科学需要一种方法来复制已发表的实验;然而，由于工具从未发表，实验通常是不可复制的。通过将工具作为开源项目共享，并为我们的实验提供所有文件，我们希望积极参与开放漏洞检测活动，并促进更好地获得这些技术。··41.4论文大纲本文分为四个部分：首先，第一部分解释了免费后使用，并概述了我们在二进制代码上触发此漏洞的方法。它介绍了本文所研究的主题，并提供了用于检测或防止免费使用的技术的详细现状然后，通过一个激励性的例子来说明我们将静态分析与动态符号执行相结合的整体第二部分重点介绍了为检测免费后使用而构建的静态分析它详细介绍了静态分析所使用的模型，并将我们对检测此漏洞的贡献形式化提供了关于静态分析实施的信息，以及关于现实世界示例的基准测试，显示了我们方法的有效性。然后，第三部分详细介绍了为与静态分析结合使用而开发的引导式动态符号执行。这种组合是我们方法的核心。此外，这一部分提供了几个贡献，使动态符号执行更有效地应用于现实世界的背景。最后，第四部分讨论了我们对这项工作的贡献和可能的扩展。工作假设我们在本文档的其余部分做出以下假设：分析的二进制文件是使用经典编译器从C程序构建的。二进制不包含混淆或自修改技术。所分析的二进制文件的体系结构是Intel的x86，但我们的贡献可能适用于其他体系结构;通过直接在二进制代码上工作，我们的技术也在用C++编写的程序上工作，但在这样的程序中效率很低·······5第一部分触发免费后使用：概念和贡献7第二章堆漏洞本章旨在介绍一些概念，这些概念是充分理解本文所研究的主题所必需的。在内存损坏中，有一类特殊的漏洞涉及堆中发生的错误。这些漏洞与其他漏洞的不同之处在于它们与动态内存管理相关。虽然常见的内存损坏（如缓冲区溢出或使用未初始化的内存）可能会同时占用堆内存和非堆内存，但动态内存管理带来了新类型的漏洞和新类型的利用。大纲 本章的其余部分组织如下：第2.1节回顾了一些关于程序内存的概念，并详细介绍了与分析堆漏洞相关的问题• 第2.2节详细介绍了本论文中研究的漏洞：免费后使用;最后，第2.3节描述了检测或防止此漏洞的技术和工具的最新状态。2.1堆特性本节提供了理解处理堆的程序分析所需的概念和概念。2.1.1内存布局程序的内存布局被拆分为多个部分。我们通常区分五个部分（如图2.1所示）。图2.1：内存部分表示。"文本"部分包含程序的已执行指令。在DATA部分中，定位程序使用的常量变量。BSS包含静态和全局变量。动态分配位于HEAP内部，并在下面进行描述。最后，堆栈是存储函数局部变量的内存部分··8无论何时调用函数，其局部变量所需的内存都将在堆栈中分配。堆栈向较低的地址增长，表示最后分配的变量具有最低的地址。堆栈中属于函数的部分称为其堆栈框架。由于函数的局部变量的数量是有限的，因此在编译1期间计算堆栈框架的大小。在x86体系结构中，当前函数的堆栈帧由两个特定寄存器分隔：分别用于基指针和堆栈指针的ebp和esp前一个指向堆栈帧的开始，而后一个指向其结束（因此EBP的值高于ESP）。一些其他特定的值被保存在堆栈帧中，例如函数参数、函数返回后要执行的指令的地址，或者对应于调用方堆栈帧的ebp值。图2.2显示了堆栈帧布局的示例。这里，函数f1包含一个局部变量a;它的堆栈框架如图2.2b所示。在调用f2期间，局部变量buf[8]的空间在堆栈中被分配，就像f2的返回地址和ebp的先前值一样，如图2.2c所示。请注意，要在返回后执行的指令的地址（保存在两个堆栈帧之间）是在缓冲区溢出的上下文中利用程序的主要目标，因为更改此值允许直接控制执行流。1空洞f2（）{2[8][3]45空洞f1（）{6inta;7f2（）;8}(a) 源代码。（b）在f2之前（c）在f2期间（）图2.2：堆栈框架示例。动态变量动态变量（也称为堆变量）在运行时在HEAP部分中分配与局部变量不同，它们的大小可以在运行时计算，并且此内存部分向更高的地址增长。glibc库中的malloc或calloc等函数分配这些变量。2.1.2分配器策略可用于程序的计算机内存是有限的，因此堆栈和堆是有界的。不再使用的内存部分需要释放，以便可用于其他分配。对于堆栈，这是在函数返回时隐式完成的：函数的堆栈框架被释放。对于堆，这可以使用垃圾收集器自动完成，也可以由开发人员负责。从安全的角度来看，垃圾收集器提供了一个更安全的动态内存管理方案，但它们带来了开销，使它们不适用于所有用途。在[HB06]中可以找到垃圾收集器和手动堆管理之间的性能比较管理动态变量发布的函数由标准库提供，在glibc库中免费提供C11标准[INC12a]参考：注意，一些函数（如alloca）可以动态地将新变量分配给堆栈帧，从而更改其大小。9-未指定对对齐的alloc、calloc、malloc和realloc函数的连续调用所分配的存储的顺序和邻接性。因此，没有关于如何处理动态存储器的规范。存在几种不同的策略，它们的区别在于它们的速度和所需的内存空间之间的权衡。当遇到特定属性时，例如多线程编程或实时时，一些也更适合。为了了解它们之间的差异，我们考虑了处理堆时的一个常见问题：碎片化。图2.3a表示由18个可能的块组成的堆存储器，其中执行了5个块的3个连续分配：A、B和C。(a) A、B和C已分配。B是自由的。(c)天真的分配器。最佳配合分配器。图2.3：堆碎片示例在下一步中，块B被释放，如图2.3b所示。假设我们现在要分配一个大小为3的块如果我们考虑一个简单的分配器，它返回第一个具有足够可用空间的位置，我们得到一个状态如图2.3c所示的堆。这样的决定阻止了未来大于3的分配。如果我们现在考虑一个更聪明但速度更慢的策略，它试图找到最适合请求大小的位置，那么堆就处于图2.3d所示的状态。在这种情况下，虽然可以进行大小为5的分配，但找到正确位置所花费的时间较长。在处理实际应用程序时，这种权衡至关重要，正确的策略在很大程度上取决于应用程序。[Wil+95;Fer+11]中关于几种分配策略的设计和绩效的研究。为了说明建模分配策略的复杂性，我们概述了glibc使用的ptmallocv2。ptmallocv2基于dlmal-loc[Lea 00]。与dlmalloc相比，主要的改进之一是支持多线程应用程序。下面的说明详细介绍了ptmallocv2和dlmalloc，线程机制除外。由这些策略分配的每个块包含元数据，位于块的可用区域之前。因此，当malloc返回地址X时，元数据被定位为X大小。此元数据包含块的大小。当一个块被释放时，它会被放入一个自由列表中。自由列表用于跟踪自由块，并通过链接列表进行处理。此免费列表通过写入用户数据直接存储在免费块中。注意，此技术可用于漏洞利用：写入自由指针将重写这些地址，从而损坏自由列表。自由块按其大小分组并保存在箱子中。有几个bins：快速bin（大小为80字节的块）、未排序bin（最近释放的块）、小bin（大小>80和512字节的块）和大bin（大小>512字节的块）。<<每个bin都有自己的数据结构（快速bin使用单链接列表，而其他bin使用循环双链接列表）和特定行为（如拆分、合并等）。为了处理多线程应用程序（在ptmallocv 2中），每个线程都保存其堆段和空闲列表;此机制称为每个线程竞技场。有关ptmallocv 2的更多详细信息，请参见[Fer 07;FFM 12;spl 15]。如前所述，分配器是复杂的系统;它们结合了不同的结构和行为。有几种标准分配策略，包括：• OpenBSD使用的phkmalloc[Kam98]。• 由Google开发并在Chrome中使用的tcmalloc[San]• FreeBSD[Eva 06]和Facebook [Eva 11]使用的jemalloc• Microsoft Windows中使用的低碎片堆[Val 10;RSI 12]• Hoard，设计用于多个操作系统[Ber+00]。