-
-
[原创]Fuzz学习记录
-
发表于: 2022-4-27 18:43
-
用kmeans聚类算两个种子之间的距离需要花的时间太长，考虑一下该如何优化择种算法
减少大数中的无效位数：比如所有的种子都没有访问过的基本块下标可以视作无效，以及访问过完全相同的基本块的种子可以只留一个
重复的文件读入：自定义的距离算法里面有多次打开文件，据同学测试，很耗时间，可以考虑预处理一次，打开所有的文件，读取大数存在某个地方（numpy的array好像存不下）
crashes是使得程序崩溃的数据，会被记录在我们fuzz的输出文件夹内
有些文件能够直接点开那就直接点开
xxd + filename 打开二进制文件的
前 4 项属于非 dumb mode(-d) 和主 fuzzer(-M) 会进行的操作（dump 即 AFL 也支持无脑变异，即没有规律的变异），由于其变异方式没有随机性，所以也称为 deterministic fuzzing；havoc 和 splice 是随机的，是所有 fuzzing 都会进行的操作，无论是否是 dumb mode 或者主从 fuzzer，都会进行此步骤。
用户提供初始化语料库，afl会不断调用语料库中的数据来试探程序的运行流，记录产生crash的数据和种类，并通过afl-as汇编时插桩的代码统计代码覆盖率，同时通过变异策略更新语料库的数据，如此循环进行漏洞的挖掘。
直接贴博客了，这个写的真的很
-ee -vv -nnr 是tcpdump的命令行选项
@@是让afl-fuzz以文件的形式读取程序的输入
得出的结论——cmin之后的效果不如接着跑的效果
原因？cmin是把产生相同路径的种子只保留一个，打个比方，我们到一个地方有坐飞机（为3月21日东航遇难者默哀）和拖拉机两种方式，cmin只管我们到了，不管这里面花费了多少时间，所以有可能保留的是坐拖拉机而不是飞机。这就需要我们设计一个算法择种了。
arg符号表示使得后面的式子取最小时i的下标
可以看出流程就是初始化k个聚类中心，然后归类，更新聚类中心再重复操作
但是会很吃初始化的聚类中心，如果选取不好就会得到局部最优解
后来有了sklearn优化和kmeans++，多了对k的评判和聚类中心初始化
引入了一个记号（inertial）E来表示聚合程度
右边的范数如何理解，其实就是各项的平方和，有点类似最小二乘法来估计方差
显然，E的值越小聚类效果越好，那么我们可以多次聚类，选择E最小的作为最终聚类效果
从上面的分析可以看出，k-means是随机的分配k个初始聚类中心。而聚类的结果高度依赖质心的初始化。如果初始聚类中心选的不好，k-means算法最终会收敛到一个局部最优值，而不是全局最优值。为了解决这个问题，引入了k-means++算法，它的基本思想就是：初始的聚类中心之间的相互距离要尽可能的远。而且在计算过程中，我们通常采取的措施是进行不止一次的聚类，每次都初始化不同的中心，以inertial最小的聚类结果作为最终聚类结果
通过阅读源码，我们了解到，可以用afl-showmap显示单个种子的信息——这个种子能到的基本块的id以及到达的次数。
linux下的命令如下：
运行后的效果是：
那么一个种子其实就对应的是一个二进制数，一个N位二进制数可以形象化为一个N维向量，N维向量更具体点就是N度空间的一个点。kmeans算法是根据种子之间的距离来聚类的，那么种子之间的距离如何计算呢？这里就要引入一个按bit位的差异运算二进制数样本距离的模型——hamming距离
简单引用一下百度百科上的介绍，我们主要运用的是它的几何意义
计算也很简单比如0001和1000，它们之间的hamming距离就是4
怎么算的呢，算a和b之间的距离就是a xor b，然后统计运算结果bit位上的1的个数，总数就是海明距离
大体上思路就是对每一个种子都进行一次showmap得到一个信息文本文件，然后对信息再进行处理，将处理的结果以文本形式保存
下面分布详细记录过程
python获得当前目录下所有文件名：
python调用afl-showmap得到每个种子对应的信息文本文件
为了方便，转换的文件名是按1开始编号的
今天在导师的创新实践课上突发奇想，想到python近乎无敌的大数处理，然后写了个demo简单试了试
发现不到1s就跑出来了，果然快
再试试两个大数的按位或运算
也很快
那干脆直接用大数统计算了
跑2的100万次方确实有点卡，但是10万很快，而10万已经绰绰有余了
这个库相较于skit-learn库，是纯粹的传入自定义的函数，个人认为相对来说更方便一点，于是就在简单地学习一下这个库怎么用
下面的代码是最简单的对二维散点的基于欧几里得距离的kmeans++聚类
挺好理解的就直接贴代码了
预计跑一次1万个种子以及100个聚类中心要跑27小时
对于杭州子科技大（没有电也没有学），长达一个月的断电那我们肯定跑不了了
那就只有挂自己的服务器上跑了，也挺简单的，主要是学学screen命令的用法
Screen，相当于手机上的分屏。就是那个完美解决你打某某荣耀的时候你的女朋友突然发消息，你可以单手拿宫本一个大五个创造奇迹，另一手回她
Sklearn之KMeans算法_半路转行程序员的博客-CSDN博客_kmeans sklearn
sudo suecho core >/proc/sys/kernel/core_pattern
sudo suecho core >/proc/sys/kernel/core_pattern
afl-fuzz -i fuzz_in -o fuzz_out ./tcpdump -ee -vv -nnr @@
afl-fuzz -i fuzz_in -o fuzz_out ./tcpdump -ee -vv -nnr @@
afl-showmap -o mapfile ./tcpdump -ee -vv -nnr ./queue/id:000000,orig:small_capture.pcap
afl-showmap -o mapfile ./tcpdump -ee -vv -nnr ./queue/id:000000,orig:small_capture.pcap
000087:1
000142:1
000248:1
000928:1
001092:1
001322:1
001382:1
002101:4
002141:1
002184:1
002346:1
002403:2
002589:1
003031:2
003072:1
003160:2
003220:1
003251:1
003567:1
003574:2
003827:1
003984:2
004084:1
004178:4
000087:1
000142:1
000248:1
000928:1
001092:1
001322:1
001382:1
002101:4
002141:1
002184:1
002346:1
002403:2
002589:1
003031:2
003072:1
003160:2
003220:1
003251:1
003567:1
003574:2
003827:1
003984:2
004084:1
004178:4
import os
path = "文件目录"
datanames = os.listdir(path)
for i in datanames:
print(i)
import os
path = "文件目录"
datanames = os.listdir(path)
for i in datanames:
print(i)
import os
inpath = "./tcpdump/queue"
outpath= "./tcpdump/save_showmap"
datanames = os.listdir(inpath)
a=1
##print(cmd)for i in datanames:
outname=outpath+'/'+str(a)
inname=inpath+'/'+i
cmd="afl-showmap -o {} ./tcpdump/tcpdump -ee -vv -nnr {}".format(outname,inname)
os.system(cmd)
a=a+1
import os
inpath = "./tcpdump/queue"
outpath= "./tcpdump/save_showmap"
datanames = os.listdir(inpath)
a=1
##print(cmd)for i in datanames:
outname=outpath+'/'+str(a)
inname=inpath+'/'+i
cmd="afl-showmap -o {} ./tcpdump/tcpdump -ee -vv -nnr {}".format(outname,inname)
os.system(cmd)
a=a+1
import os
inpath='./tcpdump/save_showmap'
outpath='./tcpdump/save_binary'
file_path = inpath
datanames = os.listdir(file_path)
a=1
for i in datanames:
inname=inpath+'/'+str(a)
outname=outpath+'/'+str(a)
f_in=open(inname,'r')
f_out=open(outname,'w')
line=f_in.readline()
last_number=1 while line:
now_number=int(line[:6])
##print(now_number)
for j in range(last_number,now_number):
f_out.write(str(0)+'\n')
f_out.write(str(1)+"\n")
last_number=now_number+1
line=f_in.readline()
f_in.close()
f_out.close()
a+=1
import os
inpath='./tcpdump/save_showmap'
outpath='./tcpdump/save_binary'
file_path = inpath
datanames = os.listdir(file_path)
a=1
for i in datanames:
inname=inpath+'/'+str(a)
outname=outpath+'/'+str(a)
f_in=open(inname,'r')
f_out=open(outname,'w')
line=f_in.readline()
last_number=1 while line:
now_number=int(line[:6])
##print(now_number)
for j in range(last_number,now_number):
f_out.write(str(0)+'\n')
f_out.write(str(1)+"\n")
last_number=now_number+1
line=f_in.readline()
f_in.close()
f_out.close()
a+=1
a=1<<1000000
print(a)
a=1<<1000000
print(a)
a=1
b=11
c=((a<<100000)-1) | (b<<100000)
print(c)
a=1
b=11
c=((a<<100000)-1) | (b<<100000)
print(c)
a=1
b=11
c=((a<<100000)-1) | (b<<100000)
def count_one(x):
s=0
while(x):
if (x & 1):
s+=1
x=x>>1
return s
print(count_one(c))
a=1
b=11
c=((a<<100000)-1) | (b<<100000)
def count_one(x):
s=0
while(x):
if (x & 1):
s+=1
[注意]传递专业知识、拓宽行业人脉——看雪讲师团队等你加入！
|
|
|---|---|
|
|
|
|
|
|
|
|
https://bbs.pediy.com/thread-273639.htm这位大佬写的挺不错的，然后Sakura师傅的AFL-fuzz源码详解也很好 |
