浅谈模糊测试基础技术——变异策略及变异方法

    PATA[7]使用具有路径感知特性的污点分析方法，它可以有效避免过污染和欠污染问题。该方法主要包括三个部分：①确定代表变量。②确定关键字节。③变异。下文将详细介绍这种变异策略。

图 1 PNG文件结构

图 2 处理PNG图片所用的代码片段

    假设种子文件是一个PNG文件，其格式如图一所示，包含头部块IHDR和数据块IDAT。图二所示的代码片段以该PNG文件为输入，循环读取每一块数据并执行对应的代码块。在每一次循环中，首先获取块的长度和块名（即0x0c-0x0f和0x25-0x28的内容），然后执行两个if条件语句。第一个if语句判断块名是否为IDAT，若是则进入到其代码块中，进一步根据png_ptr对象的mode属性判断在IDAT前是否找到了IHDR，如果没有的话就报错（因为IHDR必须在IDAT前面），否则执行第一个判断语句内部代码块的剩余部分。第二个if语句判断块名是否为IHDR，若是则执行内部的代码块，其中会根据IHDR设置png_ptr对象的mode属性。

    上述代码段中的每一个条件语句都可以被表示为一个条件变量，形式为二元组(V,P)，其中V包括条件语句的左值和右值，如图二中的第一个if语句对应的条件变量v1，V中存储的左值为当前块的chunk_name，右值为预定义值png_IDAT；P表示条件语句的操作符，如第一个if语句对应的“==”。条件变量可以用来表示条件语句的判断结果。为了实现具有路径感知特性的污点分析，PATA需要进行以下几个步骤。

确定代表变量

    所谓代表变量就是具有代表性的条件变量。为了找到代表变量，PATA首先收集程序按正常路径运行时遇到的所有条件变量，并将收集到的条件变量放入代表变量序列(Representative Variable Sequence，RVS)中。但是这个范围太大了，因此PATA对RVS中的条件变量进行了筛选，只保留那些可以直接被输入影响到的条件变量。

    有两类比较典型的无法直接被输入影响到的条件变量。第一个是包含逻辑运算符的条件语句，即包含与运算“&&”或者或运算“||”之类的逻辑运算符的语句。由于此类语句往往是由多个基本的比较语句结合起来，通过多个比较语句进行逻辑运算最终得到布尔型条件变量。这种布尔型条件变量就很难被输入直接影响到，PATA处理它的方法为逆向溯源影响此类布尔型条件变量的其他类型条件变量。

图 3 布尔型条件变量对应的条件语句

    图三所示的条件语句由两个条件语句组成，其中前者判断png文件的color_type，后者判断png文件的mode，显然这两个条件语句对应的条件变量都可以通过修改png文件直接被改变，因此PATA会使用这两个条件变量来替换由他们俩组成的布尔型条件变量。

    第二种是包含字节数组比较的条件语句。程序往往会使用比较函数来比较两个字符串，使用得到的结果作为条件语句的条件变量，此类条件变量也很难被输入直接影响，PATA的处理方法是用函数条件变量替代它，从而记录函数的参数来提供更多信息。（论文没有给出函数条件变量的细节）

    除了无法直接被输入影响的条件变量外，还有部分条件变量在相同输入下，在不同循环中会出现不同的值，这种变量也是不会被记录到RVS中的。这样可以避免过度污染。

    将RVS中所有类似上述情况的条件变量都进行替换，就得到了我们需要的代表变量序列。

确定关键字节

    PATA对输入进行字节级的变化，记录每次变化后输入对应的RVS。为了更有效率的比较程序执行路径中发生的变化，PATA提出了一种数据结构Variable Occurrence Subsequence（VOS）。它是代表变量名称和代表变量值序列之间的映射。所谓的代表变量值序列是指同于条件语句对应的代表变量在不同迭代中拥有的不同值。举个例子：正常情况下，图二中代码片段对应的RVS是[v1,v2,v1,v2]，那么v1的VOS就是[IHDR, IDAT]。如果将0x0c由I改为J，则RVS就变为了[v1, v2, v1]，因为第二次访问条件变量v1后会引发报错，此时v1的VOS变为[JHDR, IDAT]。为了确定关键字节，PATA首先匹配不同输入下的RVS，找到他们的最长相同前缀，如上述例子中两个RVS的前三个代表变量[v1, v2, v1]是相同的。然后比较不同RVS最长相同前缀中代表变量的VOS，如上述例子中，两个RVS中v1对应的的VOS的第一个值是不同的，第二个值是相同的，因此可以确定0x0c对于v1的第一次出现来说是关键的，而对于v1的第二次出现来说是不关键的。循环这一过程就可以找到影响所有代表变量每一次出现情况的关键字节。

变异

图4 图2所示代码段的控制流图

    在得到RVS和关键字节等信息后，PATA就可以结合这些信息实现感知路径的变异策略。观察图四，对于正常的输入来说，我们有RVS[v1, v2, v1’, v2’]，对应的代码块序列为[B4,B2,B5,B1,B3] 。这里的v1和v1’是同一个代表变量，只不过在不同迭代中具有不同的值，此处为了便于描述使用上标来进行区分。通过第二步的操作，我们现在已经知道了这一RVS中每个代表变量对应的关键字节为0x0c-0x0f, 0x0c-0x0f,0x25-0x28, 0x25-0x28。沿着RVS中代表变量出现的顺序，路径感知的变异策略进行以下操作：①对于v1，将0x0c-0x0f由IHDR改为IDAT，这样可以探索到新代码块序列[B5, B6]。②对于v2,将0x0c-0x0f由IHDR改为其他值随机值，假如是AAAA，那么就可以探索到新代码块序列[B4, B3, B5, B6]。③对于v1’，将0x25-0x28由IDAT更改为随机值如AAAA，可以探索到新代码块序列[B4, B2, B4, B3]。④对于v2’，将0x25-0x28由IDAT改为IHDR就可以按照新代码块序列[B4, B2, B4, B3]运行程序。

    显然，上述过程就是具有路径感知特性的污点分析过程。相比之下，不具有路径感知特性的污点分析会把v1和v1’当成相同的条件变量，这样只会按照v1后一次出现的情况，得到0x25-0x28是影响v1的关键字节而忽略了第一轮循环中的情况。这样一来，仅对0x25-0x28进行变异，则只能探索到新路径[B4, B2, B4, B3]而忽略了[B5, B6]。

    SNIPUZZ是一个物联网固件自动黑盒模糊测试器，它使用了一种新颖的基于消息片段的变异方法[9]。物联网设备通过发送消息进行通信，从而达到特定的功能，而片段就是指通信消息中的一串连续的字节。通常来说，物联网固件可以被视为具有严格输入语法要求的软件程序。因此，使用基于字节的随机变异方法生成的输入很少能满足语法要求。SNIPUZZ所使用的变异方法根据物联网固件接收消息后发送的执行反馈（即响应）优化变异方法，使得变异生成的输入能够以更高概率满足固件的语法要求。

图 5 SNIPUZZ架构图

    在物联网中，物联网设备在接收到指令消息后会根据固件的执行情况发送一个响应信息，告知消息发送者程序的执行情况。这使得来自物联网设备的响应与固件程序执行路径是具有一定相关性的。基于根据响应可以推断消息片段与程序执行路径相关性这一设想，SNIPUZZ设计了如图五所示的模糊测试流程，下面我们主要讨论其中的变异方法。

    SNIPUZZ作为客户端对物联网设备发送测试消息。这些消息会让物联网固件根据自身程序完成一组动作。此时，对符合固件语法要求的消息进行逐字节变异并发送给固件，就可以收到许多不同的响应。如果对消息中的两个不同位置进行变异，结果得到了同样的响应，那么就可以认为这两个位置有较大概率与固件程序中实现相同功能的代码片段有关。因此，具有相同响应的连续字节可以被合并到一个片段中。这种推断消息片段的方法可以清楚的反应发送给固件的信息中每个字节的实用性。此外，基于消息片段的变异可以大大减少搜素空间，提高模糊测试的效率。

    SNIPUZZ使用了启发式算法和分层聚类方法来确定消息中的片段。正如前文所说，消息片段的本质是消息中的连续字节，它使得固件能够执行特定的代码段。SNIPUZZ首先使用启发式算法将每条消息大致划分为初始片段，其核心思想是通过删除原始消息中的某个字节来生成质询消息，将质询消息发送给物联网固件得到响应，对每个质询消息对应的响应进行分类，将具有相同响应结果的质询消息分为一类，则同一类质询消息中连续的被删除的字节就构成了一个片段。然而，经过上述分类操作得出的分类有可能不准确：得到相同语义响应的质询消息有可能被分到不同类别中。为了弥补这一缺陷，SNIPUZZ使用分级聚类算法来细化消息片段。其中心思想是持续合并两个具有高相似性的聚类，直至只剩下一个聚类。首先，将响应转化为特征向量，计算每对向量之间的距离，然后，将两个距离最近的向量合并，形成聚类。每次形成新的聚类后，就根据当前的聚类结果生成新片段，将新片段添加到片段分类结果中，并进一步用于突变。

    在进行上述操作后，就得到了许多片段。此时，以片段为对象进行变异，就可以在满足固件语法要求的基础上提升物联网黑盒模糊测试的效率。

    首先回顾一下AFL使用的基于字典的变异方法。基于字典的变异方法位于AFL确定性变异阶段的末端，它根据用户提供或者自动生成的token字典来替换要进行变异的内容。它具有以下三个子阶段：user extras(over)，user extras(insert)，auto extras(over)。通过名字不难理解：user extras(over)的目的是将用户提供的tokens依次替换到种子文件中；user extras(insert)将用户提供的tokens依次插入到种子文件中；auto extras(over)将自动生成的tokens依次替换到种子文件中。在上述过程中，token将被插入到种子文件的两个字节之间，或者替换与token长度相同的字节序列。这种变异方法可以在一定程度上保护输入文件的语法结构，但是效率较为低下，而且大部分输入的语法结构会遭到破坏。

图 6 基于字典变异方法的变异方法

    与上述AFL使用的基于字典的变异方法不同，Superion[10]提出的基于字典变异方法的变异方法抓住了一个极为关键的点：结构化输入文件中的token通常都是由字母和数字组成的。如图六所示，该算法首先使用迭代的方式检查种子文件的当前字节和下一字节是否都为字母或数字，这样可以定位种子文件中token的边界。然后该变异方法使用插入和替换两种方法对种子文件进行变异。插入将字典中的所有token插入到每一个定位到的边界处，这样避免了把token插入到连续的字母和数字序列中间，从而极大程度地避免了不必要的插入操作。与插入类似，替换操作将字典中的每个token替换到定位到的两个边界之间，从而极大地减少了替换的次数。这种插入和替换方法不仅使输入文件保留了结构性，而且减少了变异生成的输入文件的数量，极大程度地提升了模糊测试的效率。

    除了改进的字典变异方法这种隐式感知输入文件语法的方式外，Superion还提出了一个显示式感知输入文件语义的变异方法，这样可以生成具有有效语义的输入文件。这一方法被称为基于语法树的变异方法。该变异方法利用种子文件的语法信息生成对应的抽象语法树，通过替换抽象语法树的子树达到变异的效果。

    首先，根据指定的语法G生成待变异种子文件tar的抽象语法树tar_tree。如果这一过程中出现了错误，就说明种子文件不具有有效语法，因此不采用基于语法树的变异方法对种子文件进行变异。如果没有出现错误，就把tar_tree中所有的子树保存在集合S中。然后，从种子文件队列中随机选取一个种子文件pro，使用和处理tar类似的方式生成pro的抽象语法树pro_tree并将其所有的子树保存在集合S中。此时，集合S就可以用来提供变异所需的材料。将tar_tree的每一个子树都替换为S中的所有子树，这样就生成了一个变异后的抽象语法树。这一过程如图七所示。根据得到的抽象语法树可以得到输入文件。举个例子，比如说tar_tree有100个子树，pro_tree有500个子树，那么进行替换变异后tar_tree将具有100x(100+500)个子树。

图 7 基于语法树的变异方法

    一般情况下，这种看上去就很暴力的替换方法都会给算法带来效率上的问题，上述方法也不例外。如果简单地进行上述替换，tar_tree会变得非常大，这会给模糊器带来巨大的负担，降低效率。为了解决这一问题，作者提出了三个原则来限制子树的大小：

① 限制种子文件的尺寸。如果种子文件的大小超过10,000字节，就表明该变异方法不适用于此种子文件。类似的，如果从种子队列中随机选取的种子文件pro超过10,000字节，那就不用pro的子树作为变异的材料。

② 限制变异次数。如果tar_tree和pro_tree的子树总量超过10, 000，那么就随机抛弃S中的子树，仅保留10, 000个。

③ 限制子树大小。抛弃S中那些大小超过200字节的子树。

    Superion提出的这种基于AST的变异方法仍然存在一些问题：在进行子树替换的过程中，Superion从种子队列中随机选取了另一个种子并将其解析为AST，并以此作为替换子树的材料。这种方法并没有同时保证随机性和有效语义，而且用于替换的子树并不一定适用于当前子树。也就是说，这种方法导致子树源具有参差不齐的质量和较小的体量，而且也无法直接被控制，这有可能导致模糊测试的效率具有较大的波动。比如图八所示XML文件的抽象语法树，如果将element下的子树替换给content，则会导致语法错误。

图 8 解析XML文件得到的抽象语法树

    为了解决这一问题，[11]提出了基于随机变异的子树池。在模糊测试循环中，将种子文件的各个节点按照类型记录在不同子树集合中，所有子树集合便构成了子树池。对AST节点进行变异时，在子树池中选取对应类型的节点，找到以该节点为根节点的子树并完成替换。子树池的优点在于同时兼顾了变异的随机性和种子文件的语义正确，而且随着模糊测试的进行，子树池中的内容也会不断扩充，最终能够根据节点类型提供正确的高质量子树。

    通过上文不难看出，对于变异策略的改进虽然方法众多，但是核心思想都是更精细的确定需要进行变异的位置，在增强种子文件语法、语义对于变异方法的影响的同时提升变异方法的效率。而对于变异方法的优化主要有两个方向，其一是借鉴几种常见的基本编译方法，针对特定的场景对其进行修改，比如用于协议模糊测试的变异方法、用于物联网固件模糊测试的变异方法等；其二是考虑种子的语法语义结构，以一个语法单元为对象进行变异，进一步保障变异生成文件的语法有效性。

[1]. Michal Zalewski. 2019. American Fuzzy Lop.[OL] http://lcamtuf.coredump.cx/afl/ technical_details.txt.

[2]. Stephens N, Grosen J, Salls C, et al. Driller: Augmenting fuzzing through selective symbolic execution[C]//NDSS. 2016, 16(2016): 1-16.

[3]. Yun I, Lee S, Xu M, et al. {QSYM}: A practical concolic execution engine tailored for hybrid fuzzing[C]//27th USENIX Security Symposium (USENIX Security 18). 2018: 745-761.

[4]. Rawat S, Jain V, Kumar A, et al. VUzzer: Application-aware Evolutionary Fuzzing[C]//NDSS. 2017, 17: 1-14.

[5]. Chen P, Chen H. Angora: Efficient fuzzing by principled search[C]//2018 IEEE Symposium on Security and Privacy (SP). IEEE, 2018: 711-725.

[6]. Gan S, Zhang C, Chen P, et al. {GREYONE}: Data flow sensitive fuzzing[C]//29th USENIX Security Symposium (USENIX Security 20). 2020: 2577-2594.

[7]. Liang J, Wang M, Zhou C, et al. PATA: Fuzzing with Path Aware Taint Analysis[C]//2022 2022 IEEE Symposium on Security and Privacy (SP)(SP). IEEE Computer Society, Los Alamitos, CA, USA. 2022: 154-170.

[8]. Zong P, Lv T, Wang D, et al. {FuzzGuard}: Filtering out Unreachable Inputs in Directed Grey-box Fuzzing through Deep Learning[C]//29th USENIX Security Symposium (USENIX Security 20). 2020: 2255-2269.

[9]. Feng X, Sun R, Zhu X, et al. Snipuzz: Black-box fuzzing of iot firmware via message snippet inference[C]//Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security. 2021: 337-350.

[10]. Wang J, Chen B, Wei L, et al. Superion: Grammar-aware greybox fuzzing[C]//2019 IEEE/ACM 41st International Conference on Software Engineering (ICSE). IEEE, 2019: 724-735.

[11]. Deng J, Zhu X, Xiao X, et al. Fuzzing With Optimized Grammar-Aware Mutation Strategies[J]. IEEE Access, 2021, 9: 95061-95071.