Fuzz学习记录
2022-5-21 17:59:34 Author: mp.weixin.qq.com(查看原文) 阅读量:49 收藏


本文为看雪论坛优秀文章
看雪论坛作者ID:Nameless_a

用kmeans聚类算两个种子之间的距离需要花的时间太长,考虑一下该如何优化择种算法。
减少大数中的无效位数:比如所有的种子都没有访问过的基本块下标可以视作无效,以及访问过完全相同的基本块的种子可以只留一个。
 
重复的文件读入:自定义的距离算法里面有多次打开文件,据同学测试,很耗时间,可以考虑预处理一次,打开所有的文件,读取大数存在某个地方(numpy的array好像存不下)

优化思路

crashes如何打开

crashes是使得程序崩溃的数据,会被记录在我们fuzz的输出文件夹内。
 
有些文件能够直接点开那就直接点开,xxd + filename 打开二进制文件的。

afl-fuzz的变异策略

 
前 4 项属于非 dumb mode(-d) 和主 fuzzer(-M) 会进行的操作(dump 即 AFL 也支持无脑变异,即没有规律的变异),由于其变异方式没有随机性,所以也称为 deterministic fuzzing;havoc 和 splice 是随机的,是所有 fuzzing 都会进行的操作,无论是否是 dumb mode 或者主从 fuzzer,都会进行此步骤。

个人对afl-fuzz的理解

用户提供初始化语料库,afl会不断调用语料库中的数据来试探程序的运行流,记录产生crash的数据和种类,并通过afl-as汇编时插桩的代码统计代码覆盖率,同时通过变异策略更新语料库的数据,如此循环进行漏洞的挖掘。

fuzz tcpdump

fuzz目标tcpdump的生成

直接贴博客了(https://blog.csdn.net/qq_42931917/article/details/112788201)

报错的初始化配置:

sudo suecho core >/proc/sys/kernel/core_pattern

指令:

afl-fuzz -i fuzz_in -o fuzz_out ./tcpdump  -ee -vv -nnr  @@
-ee -vv -nnr 是tcpdump的命令行选项。
 
@@是让afl-fuzz以文件的形式读取程序的输入

探究种子的重新筛选对fuzz的运行效率有无影响

数据一

跑了23个小时后的数据重新跑(未cmin) 操作系统ubnutu20

跑了23个小时的数据(cmin后)

数据二

跑了23个小时后的数据重新跑(未cmin)ubnutu18

跑了23个小时后的数据重新跑(cmin后)ubnutu18

 
得出的结论——cmin之后的效果不如接着跑的效果。
 
原因?cmin是把产生相同路径的种子只保留一个,打个比方,我们到一个地方有坐飞机(为3月21日东航遇难者默哀)和拖拉机两种方式,cmin只管我们到了,不管这里面花费了多少时间,所以有可能保留的是坐拖拉机而不是飞机。这就需要我们设计一个算法择种了。

sklearn的kmeans算法

kmeans

 
arg符号表示使得后面的式子取最小时i的下标。
 
可以看出流程就是初始化k个聚类中心,然后归类,更新聚类中心再重复操作。
 
但是会很吃初始化的聚类中心,如果选取不好就会得到局部最优解。
 
后来有了sklearn优化和kmeans++,多了对k的评判和聚类中心初始化。

聚类效果评判

引入了一个记号(inertial)E来表示聚合程度。
 
 
右边的范数如何理解,其实就是各项的平方和,有点类似最小二乘法来估计方差。
 
 
显然,E的值越小聚类效果越好,那么我们可以多次聚类,选择E最小的作为最终聚类效果。

kmeans++

从上面的分析可以看出,k-means是随机的分配k个初始聚类中心。而聚类的结果高度依赖质心的初始化。如果初始聚类中心选的不好,k-means算法最终会收敛到一个局部最优值,而不是全局最优值。为了解决这个问题,引入了k-means++算法,它的基本思想就是:初始的聚类中心之间的相互距离要尽可能的远。而且在计算过程中,我们通常采取的措施是进行不止一次的聚类,每次都初始化不同的中心,以inertial最小的聚类结果作为最终聚类结果。
 

关于种子的模型

通过阅读源码,我们了解到,可以用afl-showmap显示单个种子的信息——这个种子能到的基本块的id以及到达的次数。
 
linux下的命令如下:
afl-showmap -o mapfile ./tcpdump -ee -vv -nnr  ./queue/id:000000,orig:small_capture.pcap
运行后的效果是:
000087:1000142:1000248:1000928:1001092:1001322:1001382:1002101:4002141:1002184:1002346:1002403:2002589:1003031:2003072:1003160:2003220:1003251:1003567:1003574:2003827:1003984:2004084:1004178:4
那么一个种子其实就对应的是一个二进制数,一个N位二进制数可以形象化为一个N维向量,N维向量更具体点就是N度空间的一个点。kmeans算法是根据种子之间的距离来聚类的,那么种子之间的距离如何计算呢?这里就要引入一个按bit位的差异运算二进制数样本距离的模型— hamming距离

hamming距离

简单引用一下百度百科上的介绍,我们主要运用的是它的几何意义。
 
计算也很简单比如0001和1000,它们之间的hamming距离就是4。
 
怎么算的呢,算a和b之间的距离就是a xor b,然后统计运算结果bit位上的1的个数,总数就是海明距离。

如何将种子转换为二进制数并且保存

大体上思路就是对每一个种子都进行一次showmap得到一个信息文本文件,然后对信息再进行处理,将处理的结果以文本形式保存。
 

下面分布详细记录过程:

步骤一:通过python读取文件名,然后对每一个文件调用showmap得到信息文本文件

python获得当前目录下所有文件名:

import ospath = "文件目录"datanames = os.listdir(path)for i in datanames:    print(i)
python调用afl-showmap得到每个种子对应的信息文本文件。
import osinpath = "./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
为了方便,转换的文件名是按1开始编号的。

步骤二:通过python脚本,将信息文本文件转换为二进制数并以文本形式保存

import osinpath='./tcpdump/save_showmap'outpath='./tcpdump/save_binary'file_path = inpathdatanames = os.listdir(file_path)a=1for 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

新思路:将种子对应成一个大数

今天在导师的创新实践课上突发奇想,想到python近乎无敌的大数处理,然后写了个demo简单试了试。
a=1<<1000000print(a)
发现不到1s就跑出来了,果然快。
 
再试试两个大数的按位或运算:
a=1b=11c=((a<<100000)-1) | (b<<100000)print(c)
也很快,那干脆直接用大数统计算了。
a=1b=11c=((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))
跑2的100万次方确实有点卡,但是10万很快,而10万已经绰绰有余了。

将种子转换成大数的脚本

import osinpath='./tcpdump/save_showmap'outpath='./tcpdump/save_bignum'file_path = inpathdatanames = os.listdir(file_path)a=1for i in datanames: inname=inpath+'/'+str(a) outname=outpath+'/'+str(a) f_in=open(inname,'r') f_out=open(outname,'w') big_number=0 line=f_in.readline()        while line:     now_number=int(line[:6])     big_number+=1<<now_number     line=f_in.readline()     f_out.write(str(big_number)) f_in.close() f_out.close() a+=1

pyclusring库下的kmeans聚类

这个库相较于skit-learn库,是纯粹的传入自定义的函数,个人认为相对来说更方便一点,于是就在简单地学习一下这个库怎么用。

先造个沙堡!

下面的代码是最简单的对二维散点的基于欧几里得距离的kmeans++聚类
#以下代码为:生成随机散点图from turtle import colorimport numpy as npimport matplotlib.pyplot as pltfrom pyclustering.cluster.center_initializer import kmeans_plusplus_initializerfrom pyclustering.cluster.kmeans import kmeans ## 前面是安装的库cluster_num=20 def draw_line(a,b):    a_x=a[0]    a_y=a[1]    b_x=b[0]    b_y=b[1]    plt.plot([a_x,b_x], [a_y,b_y],linewidth=1,color='green') def add_line_between_center_and_members(cs,group,x): # cs:聚类中心 group:二维数组表示的分组情况 x:原始的二维数组    for i in range(0,cluster_num):        for j in group[i]:            draw_line(cs[i],x[j]) def draw_initial_point(x):    x1=[]    y1=[]    for i in x:        x1+=[i[0]]        y1+=[i[1]]    plt.plot(x1,y1, 'o',color='b') ## 画初始的点,把一个二维数组拆成一维 def draw_center(cs):    x1=[]    y1=[]    for i in cs:        x1+=[i[0]]        y1+=[i[1]]    ###print(x1)    plt.plot(x1,y1, 'o',color='r')       ##plt.scatter(i[0],i[1],'o',color='r') ## 画聚类中心## 聚类个数 kmeans中的kx=np.random.randint(0,100,(100,2)) print("初始数据:")print(x) ## 随机一个二维数组draw_initial_point(x)initial_centers = kmeans_plusplus_initializer(x, cluster_num).initialize()kmeans_instance = kmeans(x, initial_centers)kmeans_instance.process()clusters = kmeans_instance.get_clusters()cs = kmeans_instance.get_centers() ## 详见:https://segmentfault.com/a/1190000039785725 print("聚类中心:")print(cs)draw_center(cs)print("分类情况:")print(clusters)print("test:")##plt.plot(x1,y1, 'o',color='b')add_line_between_center_and_members(cs,clusters,x)plt.show()

上手用自定义距离聚类

挺好理解的就直接贴代码了。
#以下代码为:生成随机散点图from turtle import colorimport osimport numpy as npimport matplotlib.pyplot as pltfrom pyclustering.utils.metric import distance_metric, type_metricfrom pyclustering.cluster.kmeans import kmeans, kmeans_visualizerfrom pyclustering.cluster.center_initializer import kmeans_plusplus_initializerfrom pyclustering.cluster import cluster_visualizerfrom pyclustering.samples.definitions import FCPS_SAMPLESfrom pyclustering.utils import read_sample ## 前面是安装的库inpath = "./save_bignum"datanames = os.listdir(inpath)slen=len(datanames)x=np.random.randint(0,1,(slen,2))mp=np.random.randint(0,1,(slen+1000,slen+1000)) for i in range(0,slen):    x[i,0]=i+1    x[i,1]=1print(x) def my_manhattan(p1,p2):    print(str(p1[0])+"  "+str(p2[0]))    if mp[p1[0]][p2[0]]:        return mp[p1[0]][p2[0]]    f1=open(inpath+'/'+str(p1[0]))    f2=open(inpath+'/'+str(p2[0]))    s1=int(f1.read())    s2=int(f2.read())    f1.close()    f2.close()    s=s1 ^ s2    ans=0    while(s):        if(s&1):            ans+=1        s>>=1    mp[p1[0]][p2[0]]=mp[p2[0]][p1[0]]=ans    return ans  my_metric = distance_metric(type_metric.USER_DEFINED, func=my_manhattan) cluster_num=100initial_centers = kmeans_plusplus_initializer(x, cluster_num).initialize()kmeans_instance = kmeans(x, initial_centers,metric=my_metric)kmeans_instance.process()clusters = kmeans_instance.get_clusters()cs = kmeans_instance.get_centers()
预计跑一次1万个种子以及100个聚类中心要跑27小时。
 
对于杭州子科技大,长达一个月的断电那我们肯定跑不了了。
 
那就只有挂自己的服务器上跑了,也挺简单的,主要是学学screen命令的用法。

Screen用法

Screen,相当于手机上的分屏。就是那个完美解决你打某某荣耀的时候你的女朋友突然发消息,你可以单手拿宫本一个大五个创造奇迹,另一手回她。

创建

screen -S [Name] ##创造一个名字为Name的screenscreen -ls ##看查当前所有screen和编号

连接

screen -r [ID] ps:如果连不上,先screen -d[ID]-r
删除
screen -X -S [ID] quit

参考文献

1、Sklearn之KMeans算法_半路转行程序员的博客-CSDN博客_kmeans sklearn(https://blog.csdn.net/guihenao4010/article/details/85159661)
 
2、海明距离_百度百科 (baidu.com)

看雪ID:Nameless_a

https://bbs.pediy.com/user-home-943085.htm

*本文由看雪论坛 Nameless_a 原创,转载请注明来自看雪社区

# 往期推荐

1.从零开始复现 DIR-815 栈溢出漏洞

2.Typora解密之跳动的二进制

3.海莲花glitch样本去混淆

4.记录一次对某CMS漏洞挖掘

5.Android APP漏洞之战—验证码漏洞挖掘详解

6.CTF 中 glibc堆利用及 IO_FILE 总结

球分享

球点赞

球在看

点击“阅读原文”,了解更多!


文章来源: http://mp.weixin.qq.com/s?__biz=MjM5NTc2MDYxMw==&mid=2458446969&idx=2&sn=07cf330c5edb8950cf11e13d102324cd&chksm=b18fdcf386f855e5d09479fcbc97aa4b7dd33b967a0d9d62ab234d1455d0948591906bb68e78#rd
如有侵权请联系:admin#unsafe.sh