fuzz学习记录

Posted on by Nameless

当前需要解决的问题

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

优化思路

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

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

AFL

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

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

报错的初始化配置：

sudo su
echo 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: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距离

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

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

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

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

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

下面分布详细记录过程

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

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


import os
path = "文件目录"
datanames = os.listdir(path)
for i in datanames:
    print(i)

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

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脚本，将信息文本文件转换为二进制数并以文本形式保存

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简单试了试

a=1<<1000000
print(a)

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

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

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))

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

将种子转换成大数的脚本

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++聚类

#以下代码为：生成随机散点图
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()

上手用自定义距离聚类

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

#以下代码为：生成随机散点图
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，相当于手机上的分屏。就是那个完美解决你打某某荣耀的时候你的女朋友突然发消息，你可以单手拿宫本一个大五个创造奇迹，另一手回她

创建

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

连接

screen -r [ID]

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

删除

screen -X -S [ID] quit

发表回复