主要思想
AFLGO缺点
1、耗时
AFLGO通过seed到target的distance分配power,而这需要对程序预先处理,例如插桩、编译、调用CG和CFG等计算distance,这会消耗大量时间。
作者举例:
①对于libming预处理:aflgo花费2h,而afl花费40s
②对于libxml2预处理:aflgo花费4h,而afl花费1m44s
注:我记得有篇论文里作者大概意思是预处理对模糊测试效率影响不大,毕竟一次模糊就几十个小时。
2、target设定
每次更换target就要重新来一遍预处理,计算distance等信息。
本文方法
手动提供或者用工具生成到达target的语句s,把s放到程序中运行,记录下运行的基本块路径序列(BLS),用数组把这些序列存起来,按照seed运行的基本块路径覆盖BLS的程度给予power。
本文贡献
1、提出轻量级的定向模糊技术SCDF,以及基于该技术的power调度策略
2、基于afl实现了LOLLY这个fuzzer
3、实验评估了LOLLY
实现细节
流程图
序列覆盖率计算
BLSeqi=基本块序列=<B0,B1,…,Bn> #BLS=<BLSeq1,BLSeq2,…BLSeqn>
exeTrace=seed的执行路径=<t1,t2,…tn>
论文里写的文字流程第一遍没看懂,然后去看了下伪代码,其实就是计算最长公共子序列的意思。
注:不过这里如果BLS里面基本块有重复的可能会有异常情况
比如举个例子BLS是<b0,b1,b2,b0,b3>,其中b0会在不同位置都遍历到,但是如果按照论文中计算流程,假如当前seed运行轨迹在b0处,按照第一个bo和第二个bo开始计算最长序列结果肯定是不同的,应该会造成一些影响。
论文中例子如下:最长为3,<b1,b3,b5>,覆盖率=3/4
覆盖率=最大子序列长度/BLSeqi的长度
权重分配
按照上面的方法计算seed在BLS中所有BLSeqi上的覆盖然后取平均值,赋予权重。
作者也借鉴了AFLGO中使用模拟退火调整权重的策略,用来防止降低局部最佳。
实验
作者选取了libming 0.4.8作为测试程序,AFLGo作为对照,实验结果表明LOLLY效果要好于AFLGo。
同样在漏洞复现选取BugRedux和AFLGo作为对照,同样效果要好
还发现了些新bug
总结
比较轻量级的定向模糊方法,而且效果挺好的,不足点就是需要手动选择语句来生成BLS等,而且循环路径可能对LOLLY产生影响。