1、模糊测试中的静态插桩技术王明哲姜宇孙家广（清华大学软件学院北京100084）（）Static Instrumentation Techniques in Fuzzing TestingWangMingzhe,JiangYu,andSunJiaguang（School of Software,Tsinghua University,Beijing 100084）AbstractFuzzingtestingisawell-establishedmethodfordetectingsoftwaredefects.Itsbasicideaisgeneratingalargenumberofrandom
2、inputstoexploretheprogrambehaviorextensivelyandthentomonitorthecrashesandrevealthesoftwaredefectsbehindthecrashes.Obviously,purelyrandominputscannotexploreprogrambehaviorefficientlyandalargenumberofprogramdefectscanhardlyleadtocrashes.Tofurtherenhancetheeffectivenessoffuzzingtesting,staticinstrument
3、ationtechniquesareoftenintroducedinfuzzingtestingtospeeduptheexplorationoftheprogramstatespaceandimprovetheabilityofdefectdetection.Asaresult,usingstaticinstrumentationhasbecomeadefactopracticeinfuzzingtestingnowadays.Inthispaper,wefocusontheinstrumentationrequirementsunderthebackgroundoffuzzingtest
4、ing.Besidesintroducingthebasicsofstaticinstrumentation,wesystematicallyanalyzethetypicalschemesofstaticinstrumentationfromtwoperspectives,i.e.,securityhardeningandguidancecollection.Inaddition,weinvestigatethechallengeofexecutionoverhead.Specifically,foracomprehensivesetofinstrumentationschemes,weme
5、asuretheexecutionspeedoftheinstrumentedprogramandcompareittonon-instrumentedprogramsofthebaseline.Finally,basedontheaboveanalysesandmeasurements,weprovideaprimitiveanalysisovertheoptimizationdirectionsofstaticinstrumentation.Key wordsstaticinstrumentation；fuzzingtesting；softwaredefects；programanalys
6、is；overhead摘要模糊测试是一种行之有效的软件缺陷检测方法.其基本思想是生成大量随机输入，从而广泛探索程序行为，并以此发现程序崩溃和崩溃背后的软件缺陷.显然，纯随机的输入无法高效探索程序行为，大量程序缺陷也难以导致崩溃.为了进一步提升模糊测试的有效性，模糊测试往往引入静态插桩技术，用于加快探索程序状态空间速度，提升发现缺陷的能力.因此，引入静态插桩已经成为当下模糊测试的经典实践.聚焦于模糊测试场景下的插桩需求，除了介绍静态插桩技术的基本原理外，从安全特性强化和导向信息收集两个视角出发，系统性地分析了当下静态插桩的典型方法.同时，针对插桩的额外开销问题，全面地测量了不同插桩方案下的程序的
7、执行速度，并与基线的未插桩程序进行比对.最后基于上述分析和测量，初步展望了静态插桩的优化方向.关键词静态插桩；模糊测试；软件缺陷；程序分析；额外开销中图法分类号TP311收稿日期：20221021；修回日期：20221213基金项目：国家重点研发计划项目（2022YFB3104000）；国家自然科学基金项目（62022046，92167101，U1911401）；微众学者计划（20212001829）ThisworkwassupportedbytheNationalKeyResearchandDevelopmentProgramofChina(2022YFB3104000),theNation
8、alNaturalScienceFoundationofChina(62022046,92167101,U1911401),andWebankScholarProject(20212001829).通信作者：姜宇（）计 算 机 研 究 与 发 展DOI：10.7544/issn1000-1239.202220883JournalofComputerResearchandDevelopment60（2）：262273，2023大量系统软件侧重于性能，往往使用 C/C+等具有底层控制能力的程序设计语言编写.然而，这些程序设计语言若存在不规范的使用，会产生数组越界、数据竞争等不安全行为，导致软件缺陷
9、.部分缺陷会进而引发安全问题，产生任意代码执行等重大安全影响.因此，有必要识别和修复这些缺陷.模糊测试是一种自动化的软件缺陷发现方法.不同于传统软件测试依靠人编写测试用例，模糊测试自动生成输入并以此执行程序.测试工具在程序运行时监控崩溃或超时等异常行为，从而发现异常行为背后的软件缺陷.由于构造的输入内容具有高度的随机性，能够触发开发人员难以想象的边界条件，这些条件包含了大量容易触发异常的场景.此外，自动的输入生成允许模糊测试进行动辄数千万次的测试，广泛探索程序的状态空间.在实际的模糊测试实践中，使用静态插桩技术作为辅助已成为事实上的标准.静态插桩技术包含 2个阶段；1）在源程序编译的过程中，编
10、译器在程序的关键位点插入额外的逻辑（即桩点）；2）在程序运行时桩点被触发，从而收集执行的动态信息或改变程序的行为.在模糊测试的场景下，静态插桩技术主要用于安全特性强化和导向信息收集.该技术能够显著提升软件缺陷的发现能力，加快程序状态空间的探索速度.安全特性强化插桩旨在提升软件缺陷的发现能力.模糊测试检测软件缺陷的方法主要依赖程序崩溃等操作系统的信号机制.然而，程序中出现的不安全行为仅有少部分会触发硬件异常（例如内存保护、除零错误）且被操作系统捕获.大部分类型的缺陷，例如绝大多数的单字节缓冲区溢出和有符号数的算术溢出，均不会触发硬件的保护机制.为了解决这些问题，静态插桩在潜在的风险位点进行额外的
11、安全检查，从而在发生问题时通知模糊测试工具.导向信息收集插桩旨在加快程序状态空间的探索速度.模糊测试生成的输入是随机的，因此存在难以有效探索程序的状态空间的问题，且该问题在输入高度结构化的程序和具有大量逻辑的复杂系统上尤为显著.为了解决此问题，有必要引入导向信息，使得模糊测试工具侧重于探索具有更高价值的程序状态，同时高效求解复杂约束.例如，动态测试技术发现软件缺陷的前提是触发缺陷所在的代码，所以，可以引入代码覆盖，从而将模糊测试导向尚未触发的代码位点.此外，静态插桩引入了额外的逻辑.在提升模糊测试效果的同时，静态插桩也不可避免地降低了程序的执行速度，从而影响了模糊测试的整体吞吐量.一般地，插桩
12、的能力越强，桩点数量越多，逻辑越复杂，带来的额外开销越大.由于模糊测试的整体效果依赖于海量执行对程序状态空间的探索，在模糊测试中使用静态插桩时，应合理取舍插桩能力和测试吞吐量.目前，静态插桩研究主要有 2 类，一是提出了新的插桩特性，二是降低了已有方法的额外开销.这些工作尽管十分有效，但都局限于单一的插桩策略，缺乏对功能和性能的系统性分析和梳理.为此，本文面向模糊测试场景下静态插桩技术，从功能和性能 2方面入手，系统性分析了典型的插桩技术，测量了它们的额外开销，并由此展望了插桩技术的发展趋势.本文的主要贡献有 3 方面：1）系统性地分析了静态插桩技术.对于安全特性强化插桩，本文从程序语言规范的
13、角度说明了缺陷的根源，并详细分析了检测技术的核心思想.对于导向信息收集插桩，本文总结了编译期的桩点部署策略，以及运行时对导向信息的利用策略.2）测量了插桩的额外开销.本文选取了有代表性的静态插桩方案，使用典型的模糊测试项目统计了这些插桩方案的额外开销.其中，选取的插桩方案涵盖了控制流特征采集、比较操作数收集、安全特性强化 3 个最常见的插桩需求.3）分析了静态插桩技术的优势、局限和优化方向.基于分析和测量，本文结合学术界的最新工作，讨论了模糊测试场景下静态插桩技术的优化方向.1研究背景 1.1模糊测试模糊测试起源于 20 世纪 90 年代，其最初目的是测试 UNIX 实用程序1.在此工作中，模
14、糊测试工具Fuzz 生成随机输入，接着将输入通过标准输入传递给目标程序，或通过终端仿真程序 ptygig 传递给交互式的目标程序，与此同时，测试工具等待程序的异常信号，生成输入、执行、等待异常的过程被脚本不断重复，从而发现软件缺陷.上述过程中，测试工具无需侵入目标程序，因此被称为黑盒模糊测试.2008 年 Godefroid 等人2提出了白盒模糊测试.之所以被称为白盒模糊测试是因为测试工具深入观察目标程序内部，从而系统性地探索程序的状态空间.具体地，模糊测试工具 SAGE 使用符号执行技术，王明哲等：模糊测试中的静态插桩技术263首先收集程序执行路径上的约束，接着对约束逐个取反并使用求解器生成
15、新的输入，从而探索不同的分支.包括 SAGE 在内的大量白盒测试工作尽管对程序有系统性的探索，但受制于约束收集和求解的性能，其发现软件缺陷的效果依然十分有限.2014 年提出的 AFL 是首个灰盒模糊测试工具3.不同于高开销的白盒测试，灰盒模糊测试工具 AFL使用轻量级插桩技术，统计程序的控制流特征并以此作为导向信息.具体地，程序执行轨迹的时空特征被映射到一个 64KiB 的位图上.通过分析位图背后隐含的控制流特征，模糊测试工具能够识别出尚未发现的全新程序行为，从而继续深入探索.基于导向信息的灰盒模糊测试十分成功，发现了大量的软件缺陷和安全漏洞.因此，灰盒模糊测试获得了包括谷歌4、微软5、Ad
16、obe6在内的工业界的广泛应用.1.2静态插桩和模糊测试在实际的模糊测试实践中，静态插桩已成为事实上的标准7.例如，OSS-Fuzz4是谷歌发起的模糊测试持续集成服务，囊括了大量被广泛使用的基础软件项目.其中，全部的测试项目都使用了至少一种静态插桩技术.具体地，表 1 显示了 OSS-Fuzz 项目中启用模糊测试的 771 个测试项目中静态插桩的使用情况.Table 1Usage Statistics of Static Instrumentation in OSS-Fuzz表 1 OSS-Fuzz 项目的静态插桩使用统计插桩方案类型目标数量CmpLog导向信息收集收集比较的操作数411CompCov导向信息收集将整数比较拆分为多个比较411Ctx2导向信息收集收集上下文敏感的边覆盖411SanitizerCoverage导向信息收集收集边覆盖率和其他信息768AddressSanitizer8安全特性强化检查内存安全问题771UndefinedSanitizer安全特性强化检查未定义行为485MemorySanitizer9安全特性强化检查对未初始化内存的读取188ThreadSan
