Franck De Goër de Herve. Reverse-engineering of binaries in a single execution : a lightweight function-grained dynamic analysis. Programming Languages [cs.PL]. Université Grenoble Alpes, 2017. English.NNT : 2017GREAM058. tel-018363110HAL Id: tel-018363110https://theses.hal.science/tel-018363110提交日期：2018年7月12日0HAL是一个多学科开放获取档案库，用于存储和传播科学研究文献，无论其是否发表。这些文献可以来自法国或国外的教育和研究机构，也可以来自公共或私人研究中心。0L’archive ouverte pluridisciplinaire HAL，旨在存储和传播法国或国外的教育和研究机构以及公共或私人实验室发表或未发表的研究级科学文献。0以单次执行进行二进制程序的逆向工程：一种轻量级的函数级动态分析0Franck De Goër de Herve0引用此版本：�0博士学位论文 以获得DOCTEUR DE LA COMMUNAUTE UNIVERSITEGRENOBLE ALPES 专业：计算机科学0部长令：2016年5月25日0由Franck de Goër de Herve提出0由Roland Groz教授指导，INP，由LaurentMounier副教授共同指导，Université Grenoble Alpes0在Grenoble计算机实验室内准备，属于数学、科学和信息技术学院的博士学位课程0以单次执行进行二进制程序的逆向工程0于2017年10月20日公开支持，由KavéSalamatian先生主持，委员会成员包括：0Monsieur Roland Groz 教授，Grenoble INP，博士导师 MonsieurLaurent Mounier 副教授，Université Grenoble Alpes，博士共同导师 Monsieur Kavé Salamatian 教授，Université Savoie，主席 MadameValérie Viet Triem Tong 副教授，Centrale Supelec，评阅人Monsieur Jacques Klein 高级研究科学家，Luxembourg大学，评阅人Monsieur Andy King 教授，肯特大学，考官 Madame SarahZennou 研究工程师，空中客车集团，考官 Madame Marion Videau 副教授，LORIA，考官20致谢谢谢你们。为了填字游戏、分享电影和书籍，为了滑雪和攀岩，为了千层蛋糕，为了帮助。为了纸牌游戏，为了热情好客，为了冷笑话，为了长时间的讨论。为了旅行，为了饮料。谢谢你们的音乐。谢谢你们的耐心。为了你们的时间，为了你们的建议，为了无尽的问题。谢谢你们的酸奶。450扩展摘要0在计算机科学中，分析程序的行为可能是重要的，用于集成、测试，以及现在经常用于安全目的（检测合法程序中的漏洞，检测恶意程序等）。从源代码进行程序分析（通常）比在二进制级别更容易，因为分析人员可以直接获得更多的信息，但有时我们只有一个二进制文件。这可能是商业产品和恶意软件的情况。此外，二进制文件包含另一种在源代码中没有嵌入的信息（例如，具体地址，编译器选择等）。最后，在某些情况下，人们更喜欢二进制级别，因为它包含实际由机器执行的代码。由于“你所看到的并不是你所执行的”现象，它可能与源代码中表达的不同（特别是如果编译器执行了优化）。出于这三个原因，已经开发了在没有依赖源代码的情况下从二进制文件工作的方法。0本文介绍了一种分析二进制程序的新的动态方法。我们在逆向工程的背景下提出了与安全相关的动机：在程序中找到漏洞，了解它们的内存管理和使用等。我们专注于检索两种高级信息：函数级别的结构信息和行为信息。对于结构信息，我们目标是包括参数的元数和类型在内的函数原型。对于行为信息，我们分析参数在函数之间的数据流，特别是与地址相关的数据流。我们方法的主要创新之处在于提出了一种在单次执行中进行分析的方法，仅需轻微的仪器化，并基于启发式方法。我们的方法根据三个主要标准进行设计。首先，它依赖于弱假设：它既不依赖于程序的源代码，也不依赖于程序的符号表，因此可以应用于闭源剥离的二进制文件。此外，它不限于特定类型的机器代码。我们称这个标准为“普适性”。其次，我们提出了一种轻量级的方法，以实现可扩展性：我们的方法可以应用于常见的程序，如PDF查看器和文本编辑器，而开销有限。第三，我们旨在提出一种准确的方法，并在可能的情况下，优先考虑准确性而不是完整性：我们所做的启发式方法可能会导致错误，但它们旨在避免误报。60我们的实验结果表明，我们的方法是准确的：平均而言，元数检测的成功率为93％，类型检测（尽管我们只检索了一部分类型）在参数上的成功率为96％，在返回值上为91％，并且我们可以在使用标准libc分配器以及在几个嵌入了自己的分配器的程序中检索分配器。最后，它是可扩展的，因为我们可以在大多数情况下在几秒钟内对常见程序进行分析。0我们的第一个贡献是提出一种方法，以便从二进制文件中检索结构信息，特别是函数原型，因为它们可能存在于源代码级别。由于我们不假设要分析的二进制文件是由编译产生的，所以需要在汇编级别上定义函数、调用和返回、输入和输出参数的概念。我们在这项工作中提出了这样的定义，此外，这些定义与编译程序的源代码级别中相应的概念是一致的，但也包括其他二进制文件（例如，手写汇编代码和甚至没有静态表示的二进制文件）。我们的工作的第二个贡献是提供与内存相关的行为信息的检索方法。我们引入了一个我们称之为“耦合”的新概念，强调了函数之间的交互。更具体地说，耦合描述了两个函数之间的地址数据流。从一次执行中，我们根据耦合率检索函数对。我们还解决了从二进制文件中检索分配器的问题，特别是当它嵌入了自定义分配器而不是使用标准分配器（例如，libc中的malloc和free）时。我们提出了资源分配器的通用定义（例如，时间分配器、多进程调度器等），以及一种基于启发式的方法来检索二进制文件中的内存分配器。最后，我们提出了我们方法的开源实现，名为scat，可在GitHub上找到（请参阅https://github.com/Frky/scat）。Scat实现了本文中提到的每个分析，以及用于测试目的的附加功能：我们在本文中提出的每个实验结果都可以使用scat进行重播（我们提供了我们的基准测试，以及用于获得结果和图表的命令）。0我们的实验结果表明，我们的方法是准确的：平均而言，元数检测的成功率为93％，类型检测（尽管我们只检索了一部分类型）在参数上的成功率为96％，在返回值上为91％，并且我们可以在使用标准libc分配器以及在几个嵌入了自己的分配器的程序中检索分配器。最后，它是可扩展的，因为我们可以在大多数情况下在几秒钟内对常见程序进行分析。70论文分为三个部分。在第一部分中，我们介绍了我们所研究的逆向工程的背景。在第1章中，我们介绍了逆向工程的概念。在第2章中，我们重点讨论了二进制反向工程：其特点、需要检索的信息类型以及该领域中的一些现有工作。第3章介绍了分析二进制文件的两种主要方法：静态分析和动态分析。第4章阐述了我们要解决的问题。在第二部分中，我们介绍了我们的方法。在第5章中，我们定义了我们要目标的元素（函数、参数、耦合、分配器）。第6章介绍了我们相对于结构推断的分析（即恢复函数的元数和类型）。在第7章中，我们提出了与地址数据流相关的分析（即耦合和分配器检索）。这四个分析中的每一个都基于一次执行，并且是一个两步分析：在线步骤中，我们执行一个带有仪器的执行来收集数据，然后在离线步骤中从收集的数据中检索目标信息。对于每个分析，我们详细介绍了我们使用的启发式方法和专用算法。在第三部分中，我们介绍了我们方法的实现，包括有关如何执行仪器化和收集实际数据的技术细节。这个实现在第8章中介绍。此外，我们在第9章中提出了详细的实验，包括我们基准测试的描述，以及数值和图形结果，以评估我们方法的准确性、精确性和可扩展性，以及某些参数的影响和结果的可变性，这取决于所分析程序的输入。890目录.............................................................0I 逆向工程的艺术....................................................1501 引言 17 1.1 实例化过程和逆向工程..........................................1801.2 动机............................................................1901.2.1 使用案例......................................................1901.2.2 目标...........................................................2001.3 逆向工程计算机程序...............................................2101.3.1 计算机科学中的动机...............................................2101.3.2 实例化过程概述..................................................2201.3.3 反转实例化过程..................................................2302 逆向工程二进制文件 27 2.1 在二进制文件上工作的特殊性.............................2702.2 从二进制中学习...................................................2802.3 从二进制到汇编...................................................2802.3.1 反汇编.......................................................2902.3.2 问题...........................................................2902.3.3 方法...........................................................2902.3.4 假设...........................................................3202.4 结构信息.......................................................3402.4.1 函数...........................................................3402.4.2 变量...........................................................3802.4.3 数据结构.......................................................4002.4.4 面向对象程序(OOP).............................................4102.5 控制流..........................................................4102.5.1 基本块........................................................413.2.1Instrumentation . . . . . . . . . . . . . . . . . . . . . . .643.2.2Observation vs. Modification . . . . . . . . . . . . . . . .653.2.3Strategies . . . . . . . . . . . . . . . . . . . . . . . . . .663.2.4Limitations. . . . . . . . . . . . . . . . . . . . . . . . .673.2.5Dynamic taint analysis for automatic detection, analysis,and signature generation of exploits on commodity software[NS05] . . . . . . . . . . . . . . . . . . . . . . . . . . . .683.2.6Howard: A Dynamic Excavator for Reverse EngineeringData Structures [SSB11] . . . . . . . . . . . . . . . . . .694Problems addressed734.1Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .734.1.1Short-term: find points of interest in a program . . . . . .734.1.2Long-term: automatically detect vulnerabilities . . . . . .73010 目录............................................................02.5.2 控制流图(CFG)................................................4202.5.3 调用图........................................................4202.6 数据流..........................................................4302.6.1 数据跟踪.......................................................4302.6.2 内存访问.......................................................4502.6.3 漏洞检测.......................................................4502.7 栈管理...........................................................5002.7.1 调用约定.......................................................5002.7.2 栈帧...........................................................5202.8 杂项...........................................................5302.8.1 分析...........................................................5402.8.2 代码覆盖率.....................................................5403 静态和动态分析 55 3.1 静态分析.................................................5503.1.1 抽象域........................................................5603.1.2 前向和后向分析.................................................5803.1.3 应用...........................................................5803.1.4 限制...........................................................6003.1.5 WYSINWYX [BR10]...............................................6103.1.6TIE：二进制程序中类型的原则性逆向工程[LAB11].............................................6203.2 动态分析........................................................63CONTENTS114.1.3Criteria. . . . . . . . . . . . . . . . . . . . . . . . . . .744.1.4Accuracy. . . . . . . . . . . . . . . . . . . . . . . . . .744.1.5Universality . . . . . . . . . . . . . . . . . . . . . . . . .744.1.6Scalability . . . . . . . . . . . . . . . . . . . . . . . . . .754.2Design choices . . . . . . . . . . . . . . . . . . . . . . . . . . . .754.2.1Dynamic analysis . . . . . . . . . . . . . . . . . . . . . .754.2.2Function-grained approach . . . . . . . . . . . . . . . . .754.2.3Passive instrumentation. . . . . . . . . . . . . . . . . .764.2.4Online and Offline steps. . . . . . . . . . . . . . . . . .764.2.5A single execution. . . . . . . . . . . . . . . . . . . . .76IIDynamic analysis of binaries795Definitions815.1Generalities. . . . . . . . . . . . . . . . . . . . . . . . . . . . .815.1.1Instruction. . . . . . . . . . . . . . . . . . . . . . . . .825.1.2Execution . . . . . . . . . . . . . . . . . . . . . . . . . .825.1.3Binary . . . . . . . . . . . . . . . . . . . . . . . . . . . .835.1.4Memory location . . . . . . . . . . . . . . . . . . . . . .845.1.5Program counter . . . . . . . . . . . . . . . . . . . . . .845.2Structure. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .855.2.1Function . . . . . . . . . . . . . . . . . . . . . . . . . . .855.2.2Memory location and parameters . . . . . . . . . . . . . .905.2.3Parameter and return value . . . . . . . . . . . . . . . . .915.2.4Arity . . . . . . . . . . . . . . . . . . . . . . . . . . . . .985.3Behavior . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1045.3.1Number of calls . . . . . . . . . . . . . . . . . . . . . . . 1045.3.3Def-use . . . . . . . . . . . . . . . . . . . . . . . . . . . 1055.4Allocator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1075.4.1Resource. . . . . . . . . . . . . . . . . . . . . . . . . . 1075.4.3Fragmentation. . . . . . . . . . . . . . . . . . . . . . . 10805.2.5 类型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9905.3.2 数据流 . . . . . . . . . . . . . . . . . . . . . . . . . . 10505.3.4 耦合 . . . . . . . . . . . . . . . . . . . . . . . . . . . 10705.4.2 块 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10805.4.4 投影 . . . . . . . . . . . . . . . . . . . . . . . . . . . 10912CONTENTS5.4.5Fragmented state of a resource. . . . . . . . . . . . . . 1095.4.6Allocator of resources. . . . . . . . . . . . . . . . . . . 1096Structure inference1136.1Arity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1136.1.1Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 1136.1.2Criteria. . . . . . . . . . . . . . . . . . . . . . . . . . . 1146.1.3Arity over one execution . . . . . . . . . . . . . . . . . . 1156.1.4Heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . 1186.1.5Generalization to answer Problem 1 . . . . . . . . . . . . 1206.1.6Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . 1216.2Types. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1216.2.1Set of types . . . . . . . . . . . . . . . . . . . . . . . . . 1226.2.2Refinement of the problem . . . . . . . . . . . . . . . . . 1236.2.3Criteria. . . . . . . . . . . . . . . . . . . . . . . . . . . 1236.2.4Type over one execution . . . . . . . . . . . . . . . . . . 1246.2.5Heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . 1266.2.6General answer to Problem 3 . . . . . . . . . . . . . . . . 1286.2.7Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . 1287Inference of address flow1357.1Coupling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1357.1.1Intuitions. . . . . . . . . . . . . . . . . . . . . . . . . . 1357.1.2Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 1367.1.3Criteria. . . . . . . . . . . . . . . . . . . . . . . . . . . 1377.1.4Coupling over one execution . . . . . . . . . . . . . . . . 1377.1.5Heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . 1397.1.6Generalisation to answer Problem 4 . . . . . . . . . . . . 1407.1.7Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . 1417.2Memory allocator . . . . . . . . . . . . . . . . . . . . . . . . . . 1417.2.1Motivations . . . . . . . . . . . . . . . . . . . . . . . . . 1417.2.2Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 1427.2.3Criteria. . . . . . . . . . . . . . . . . . . . . . . . . . . 1427.2.4Allocator over one execution . . . . . . . . . . . . . . . . 1437.2.5Retrieve ALLOC . . . . . . . . . . . . . . . . . . . . . . . 1457.3Arity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15707.2.6 检索 FREE . . . . . . . . . . . . . . . . . . . . . . . . 1527.4Type . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1577.5Couple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1587.6Memory allocator . . . . . . . . . . . . . . . . . . . . . . . . . . 1587.6.1ALLOC . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1587.6.2FREE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158IIIExperiments1598.1.2Scope . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1638.1.4Technical choices . . . . . . . . . . . . . . . . . . . . . . 1678.2Arity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1738.2.1Combined analysis. . . . . . . . . . . . . . . . . . . . . 1738.2.2Practical heuristics . . . . . . . . . . . . . . . . . . . . . 1738.2.3Instrumentation . . . . . . . . . . . . . . . . . . . . . . . 1758.2.4Detection . . . . . . . . . . . . . . . . . . . . . . . . . . 1788.3Type . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1798.3.1Context . . . . . . . . . . . . . . . . . . . . . . . . . . . 1798.3.2Base point. . . . . . . . . . . . . . . . . . . . . . . . . 1808.3.3Combined analysis. . . . . . . . . . . . . . . . . . . . . 1808.3.4Practical heuristic . . . . . . . . . . . . . . . . . . . . . . 1808.3.5Instrumentation . . . . . . . . . . . . . . . . . . . . . . . 1828.3.6Detection . . . . . . . . . . . . . . . . . . . . . . . . . . 1848.4Coupling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1858.4.1Context . . . . . . . . . . . . . . . . . . . . . . . . . . . 1858.4.2Base point. . . . . . . . . . . . . . . . . . . . . . . . . 1858.4.3Two-steps analysis . . . . . . . . . . . . . . . . . . . . . 1868.4.4Instrumentation . . . . . . . . . . . . . . . . . . . . . . . 1868.4.5Detection . . . . . . . . . . . . . . . . . . . . . . . . . . 1888.5Allocators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1888.5.1Context . . . . . . . . . . . . . . . . . . . . . . . . . . . 1888.5.2Base point. . . . . . . . . . . . . . . . . . . . . . . . . 1898.5.3Practical heuristics . . . . . . . . . . . . . . . . . . . . . 1890目录 1308 实现 161 8.1 Scat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161 8.1.1 一般介绍 . . . .. . . . . . . . . . . . . . . . 16208.1.3 从一个执行到另一个执行的标识符 . . . . . . . . . . 16614CONTENTS8.5.4Instrumentation . . . . . . . . . . . . . . . . . . . . . . . 1908.5.5Detection . . . . . . . . . . . . . . . . . . . . . . . . . . 1909Evaluation2019.1Methodology. . . . . . . . . . . . . . . . . . . . . . . . . . . . 2019.1.1Open-source programs compiled from C . . . . . . . . . . 2019.1.2Production of an oracle . . . . . . . . . . . . . . . . . . . 2049.1.3Measurements. . . . . . . . . . . . . . . . . . . . . . . 2049.1.4Reproductibility of experiments . . . . . . . . . . . . . . . 2069.1.5Platform . . . . . . . . . . . . . . . . . . . . . . . . . . . 2069.2Arity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2069.2.1Metric . . . . . . . . . . .
我的内容管理
收起
我的收益 登录查看自己的收益
我的积分
登录查看自己的积分
我的C币
登录后查看C币余额
我的收藏 
我的下载 
下载帮助 
