首页
社区
课程
招聘
问答 CTF 排行榜 知识库 工具下载 看雪峰会 看雪商城 证书查询
  1. 看雪社区
  2. Pwn
    3. 发新帖
[原创]Fuzz学习记录
2022-4-27 18:43 20004

[原创]Fuzz学习记录

Nameless_a 活跃值
5
2022-4-27 18:43
20004

当前需要解决的问题

用kmeans聚类算两个种子之间的距离需要花的时间太长，考虑一下该如何优化择种算法

优化思路

减少大数中的无效位数：比如所有的种子都没有访问过的基本块下标可以视作无效，以及访问过完全相同的基本块的种子可以只留一个

 

重复的文件读入：自定义的距离算法里面有多次打开文件，据同学测试，很耗时间，可以考虑预处理一次，打开所有的文件，读取大数存在某个地方（numpy的array好像存不下）

AFL

优化思路

crashes如何打开

crashes是使得程序崩溃的数据，会被记录在我们fuzz的输出文件夹内

 

有些文件能够直接点开那就直接点开

 

xxd + filename 打开二进制文件的

afl-fuzz的变异策略

img

 

前 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的生成

直接贴博客了，这个写的真的很

报错的初始化配置：

1
2
sudo su
echo core >/proc/sys/kernel/core_pattern

指令：

1
afl-fuzz -i fuzz_in -o fuzz_out ./tcpdump  -ee -vv -nnr  @@

-ee -vv -nnr 是tcpdump的命令行选项

 

@@是让afl-fuzz以文件的形式读取程序的输入

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

数据一

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

img

跑了23个小时的数据（cmin后）

img

数据二

跑了23个小时后的数据重新跑（未cmin）ubnutu18

img

跑了23个小时后的数据重新跑（cmin后）ubnutu18

img

 

得出的结论——cmin之后的效果不如接着跑的效果

 

原因？cmin是把产生相同路径的种子只保留一个，打个比方，我们到一个地方有坐飞机（为3月21日东航遇难者默哀）和拖拉机两种方式，cmin只管我们到了，不管这里面花费了多少时间，所以有可能保留的是坐拖拉机而不是飞机。这就需要我们设计一个算法择种了。

择种算法

sklearn的kmeans算法

kmeans

img

 

arg符号表示使得后面的式子取最小时i的下标

 

可以看出流程就是初始化k个聚类中心，然后归类，更新聚类中心再重复操作

 

但是会很吃初始化的聚类中心，如果选取不好就会得到局部最优解

 

后来有了sklearn优化和kmeans++，多了对k的评判和聚类中心初始化

聚类效果评判

引入了一个记号（inertial）E来表示聚合程度

 

img

 

右边的范数如何理解，其实就是各项的平方和，有点类似最小二乘法来估计方差

 

img

 

显然，E的值越小聚类效果越好，那么我们可以多次聚类，选择E最小的作为最终聚类效果

kmeans++

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

 

img

关于种子的模型

通过阅读源码，我们了解到，可以用afl-showmap显示单个种子的信息——这个种子能到的基本块的id以及到达的次数。

 

linux下的命令如下：

1
afl-showmap -o mapfile ./tcpdump -ee -vv -nnr  ./queue/id:000000,orig:small_capture.pcap

运行后的效果是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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

那么一个种子其实就对应的是一个二进制数，一个N位二进制数可以形象化为一个N维向量，N维向量更具体点就是N度空间的一个点。kmeans算法是根据种子之间的距离来聚类的，那么种子之间的距离如何计算呢？这里就要引入一个按bit位的差异运算二进制数样本距离的模型——hamming距离

hamming距离

img

 

简单引用一下百度百科上的介绍，我们主要运用的是它的几何意义

 

计算也很简单比如0001和1000，它们之间的hamming距离就是4

 

怎么算的呢，算a和b之间的距离就是a xor b，然后统计运算结果bit位上的1的个数，总数就是海明距离

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

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

 

下面分布详细记录过程

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

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

1
2
3
4
5
import os
path = "文件目录"
datanames = os.listdir(path)
for i in datanames:
    print(i)

python调用afl-showmap得到每个种子对应的信息文本文件

1
2
3
4
5
6
7
8
9
10
11
12
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

为了方便，转换的文件名是按1开始编号的

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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

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

今天在导师的创新实践课上突发奇想，想到python近乎无敌的大数处理，然后写了个demo简单试了试

1
2
a=1<<1000000
print(a)

发现不到1s就跑出来了，果然快

 

再试试两个大数的按位或运算

1
2
3
4
a=1
b=11
c=((a<<100000)-1) | (b<<100000)
print(c)

也很快

 

那干脆直接用大数统计算了

1
2
3
4
5
6
7
8
9
10
11
12
13
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))

跑2的100万次方确实有点卡，但是10万很快，而10万已经绰绰有余了

将种子转换成大数的脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import os
inpath='./tcpdump/save_showmap'
outpath='./tcpdump/save_bignum'
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')
 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++聚类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#以下代码为：生成随机散点图
from turtle import color
import numpy as np
import matplotlib.pyplot as plt
from pyclustering.cluster.center_initializer import kmeans_plusplus_initializer
from 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中的k
x=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()

img

上手用自定义距离聚类

挺好理解的就直接贴代码了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#以下代码为：生成随机散点图
from turtle import color
import os
import numpy as np
import matplotlib.pyplot as plt
from pyclustering.utils.metric import distance_metric, type_metric
from pyclustering.cluster.kmeans import kmeans, kmeans_visualizer
from pyclustering.cluster.center_initializer import kmeans_plusplus_initializer
from pyclustering.cluster import cluster_visualizer
from pyclustering.samples.definitions import FCPS_SAMPLES
from 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]=1
print(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=100
initial_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，相当于手机上的分屏。就是那个完美解决你打某某荣耀的时候你的女朋友突然发消息，你可以单手拿宫本一个大五个创造奇迹，另一手回她

创建

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

img

连接

1
2
3
screen -r [ID]
 
ps:如果连不上，先screen -d[ID]再-r

删除

1
screen -X -S [ID] quit

参考文献

Sklearn之KMeans算法_半路转行程序员的博客-CSDN博客_kmeans sklearn

 

海明距离_百度百科 (baidu.com)


[CTF入门培训]顶尖高校博士及硕士团队亲授《30小时教你玩转CTF》，视频+靶场+题目！助力进入CTF世界

最后于 2022-5-10 11:05 被Nameless_a编辑 ，原因：
收藏
点赞・6
打赏
分享
打赏 + 50.00雪花
Editor
打赏次数 1 雪花 + 50.00
 
赞赏  Editor   +50.00 2022/05/23 恭喜您获得“雪花”奖励，安全圈有你而精彩！
最新回复 (3)
suuuuu
雪    币： 1036
活跃值： (4999)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
suuuuu 2022-5-4 19:10
2 楼
0
u秀
ttmusic
雪    币： 200
活跃值： (19)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
ttmusic 2022-8-18 16:14
3 楼
0
请问fuzz入门有什么推荐的课程或者书籍吗？苦于没有入门的资料，谢谢！
Nameless_a
雪    币： 6308
活跃值： (10514)
能力值： ( LV12，RANK：400 )
在线值：
发帖
回帖
粉丝
私信
Nameless_a 5 2022-8-18 17:10
4 楼
0
ttmusic 请问fuzz入门有什么推荐的课程或者书籍吗？苦于没有入门的资料，谢谢！
https://bbs.pediy.com/thread-273639.htm这位大佬写的挺不错的，然后Sakura师傅的AFL-fuzz源码详解也很好
游客
登录 | 注册 方可回帖
　回帖　 表情 雪币赚取及消费
高级回复
返回