Bit Table

全局Fuzzing用来统计每轮的覆盖情况,用于判断是否有新的覆盖率。

https://s3-us-west-2.amazonaws.com/secure.notion-static.com/9675efba-926e-4155-a0b3-69e5a5b87ff5/_2020-04-26_2.59.52.png

Bit Map

统计一轮运行中每条Branch的执行次数。

使用64KB(2^16)的共享内存,每个bytes表示一条Branch。

https://s3-us-west-2.amazonaws.com/secure.notion-static.com/ff590546-7cbd-4247-8253-d95fdfb18281/_2020-06-12_10.44.19.png

AFL插桩框架

cur_location = <COMPILE_TIME_RANDOM>; // 如何记录这个随机
shared_mem[cur_location ^ prev_location]++; 
prev_location = cur_location >> 1;

line1:随机产生。

line2:由于Branch数量可能很多,所以

line3:将prev更新为新的cur(但执行右移再保存到prev)

https://s3-us-west-2.amazonaws.com/secure.notion-static.com/62ab28d7-82c1-4160-9c1c-548f63e6d5c2/Untitled.png

为了简化连接复杂对象的过程和保持XOR输出平均分布,当前位置是随机产生的。

share_mem[]数组是一个调用者传给被instrument程序的64KB的共享内存区域,数组的元素是Byte。数组中的每个元素,都被编码成一个(branch_src, branch_dst),相当于存储路径的bitmap。这个数组的大小要应该能存2K到10K个分支节点,这样即可以减少冲突,也可以实现毫秒级别的分析。 这种形式的覆盖率,相对于简单的基本块覆盖率来说,对程序运行路径提供了一个更好的描述。以下面两个路径产生的tupes为例: A -> B -> C -> D -> E (tuples: AB, BC, CD, DE) A -> B -> D -> C -> E (tuples: AB, BD, DC, CE) 这更有助于发现代码的漏洞,因为大多数安全漏洞经常是一些没有预料到的状态转移,而不是因为没有覆盖那一块代码。

最后一行右移操作是用来保持tuples的定向性。如果没有右移操作,A ^ B和B ^ A就没办法区别了,同样A ^ A和B ^ B也是一样的。Intel CPU缺少算数指令,左移可能会会导致级数重置为0,但是这种可能性很小,用左移纯粹是为了效率。