[NOTE] REDQUEEN: Fuzzing with Input-to-State Correspondence (NDSS 19)

Fuzz中两个重要的问题是magic byte和checksum。很多fuzzer采用污点分析和符号执行的方法去处理,但是具有overhead过高、要求可以获得源代码的缺点。本文基于对输入和程序运行时状态(寄存器与内存)值联系的观察,提出了一种轻量的方法来处理magic byte和checksum。

(对于magic byte的处理)(步骤1) 当一个输入开始fuzz前,先单独运行一次并hook所有的比较指令及它们的参数。(步骤2)由于在运行时无法获得比较指令的类型是等于、大于还是小于,因此通过对参数加减1的方式获得观察值(observed)的variation(步骤3)其次,由于程序中比较指令的参数不一定和输入完全一致,而是输入经过了某种编码,因此,本文还为REDQUEEN设置了一些常见的编码。(步骤4)if(a > 123456)为例,假设a直接来自输入,且不经过编码,本次运行的输入为233,则可以得到运行时的observed value <233,123456>和variation <233, 123455>、<233, 123457>,第四步就是将输入中233对应的二进制部分替换为数字对右侧的值。

上述即为对于magic byte的大致处理流程。不过,假设上述if(a > 123456)的运行时观察值是一个一字节的0,恰巧当前输入中一字节的0又特别普遍,那么步骤4的替换就需要做很多次,且很多都是没有意义的。为了解决这个问题,本文通过用随机字节替换输入的某些部分来增加输入的熵值,并且只在目标替换位置在很多个输入中都出现时,才进行步骤4的替换。

REDQUEEN不仅hook比较指令,还观察以至少两个指针为参数的函数。并以假设(1)函数要比较指针所指的前n个字节(n∈{4,5,…,32})或假设(2)函数要比较指针所指处直到遇到第一个空字节来获得比较的操作数。

(对于checksum的处理)由于已经hook了比较指令,REDQUEEN通过一些标准猜测某比较指令是否属于checksum。对于符合的,对其进行patch运行,如果确实产生了新路径,再采用类似于magic byte的处理方式试图使输入能够自然到达该新路径。

No Comments

Leave a Reply

Your email address will not be published. Required fields are marked *