阅读本文大概需要 6 分钟。
”2020年 第 21 篇文章 ,flag 继续
每周至少更一篇
大家如果喜欢我的分享,一定要点在看和分享到朋友圈。现在公众号是信息流模式,对于无法天天更新的原创号来说是不利的,希望大家能与我一起坚持下去。
有你们的坚持,才有更好的世界。
下面是我的微信号,想进行技术交流的可以加我,备注公众号,卖货的,伸手党不要加我,谢谢。
理理思路
近年来,恶意代码数量的飞速增长,人工分析恶意代码效率太低,除非特别新的技巧需要人工,其他时候人工的投入远远赶不上木马病毒的产生。
聚类算法用于恶意代码新家族检测越来越重要,很多木马病毒都是新瓶装老酒。因此从恶意代码本身的相似性来进行聚类分析,从而实现由已知到未知的检测。但是有一个问题:数据量太大,我们需要对数据特征进行降维。
google提供了一个好办法,那就是simhash算法。这个算法本身是为了海量网页去重准备的,一个网页几千字,通过这个算法可以浓缩为几个字节的特征,通过这几个字节特征的相似性进行判重。当然也可以用于恶意代码分析。
实践出真知
Simhash是由 Charikar 在2002年提出来的, 为了便于理解尽量不使用数学公式,分为这5步:
分词,把需要判断文本分词形成这个文章的特征单词。最后形成去掉噪音词的单词序列并为每个词加上权重,我们假设权重分为5个级别(1~5)。比如:“ 美国“51区”雇员称内部有9架飞碟,曾看见灰色外星人 ” ==> 分词后为 “ 美国(4) 51区(5) 雇员(3) 称(1) 内部(2) 有(1) 9架(3) 飞碟(5) 曾(1) 看见(3) 灰色(4) 外星人(5)”,括号里是代表单词在整个句子里重要程度,数字越大越重要。
hash,通过hash算法把每个词变成hash值,比如“美国”通过hash算法计算为 100101,“51区”通过hash算法计算为 101011。这样我们的字符串就变成了一串串数字,还记得文章开头说过的吗,要把文章变为数字计算才能提高相似度计算性能,现在是降维过程进行时。
加权,通过 2步骤的hash生成结果,需要按照单词的权重形成加权数字串,比如“美国”的hash值为“100101”,通过加权计算为“4 -4 -4 4 -4 4”;“51区”的hash值为“101011”,通过加权计算为 “ 5 -5 5 -5 5 5”。
合并,把上面各个单词算出来的序列值累加,变成只有一个序列串。比如 “美国”的 “4 -4 -4 4 -4 4”,“51区”的 “ 5 -5 5 -5 5 5”, 把每一位进行累加, “4+5 -4+-5 -4+5 4+-5 -4+5 4+5” ==》 “9 -9 1 -1 1 9”。这里作为示例只算了两个单词的,真实计算需要把所有单词的序列串累加。
降维,把4步算出来的 “9 -9 1 -1 1 9” 变成 0 1 串,形成我们最终的simhash签名。如果每一位大于0 记为 1,小于0 记为 0。最后算出结果为:“1 0 1 0 1 1”。
整个过程的流程图如下:
( 注:事例摘自Lanceyan的博客《海量数据相似度计算之simhash和海明距离》)
我们把库里的文本都转换为simhash签名,并转换为long类型存储,空间大大减少。现在我们虽然解决了空间,但是如何计算两个simhash的相似度呢?难道是比较两个simhash的01有多少个不同吗?
对的,其实也就是这样,我们通过海明距离(Hamming distance)就可以计算出两个simhash到底相似不相似。两个simhash对应二进制(01串)取值不同的数量称为这两个simhash的海明距离。
计算海明距离的一种方法,就是对两个位串进行异或(xor)运算,并计算出异或运算结果中1的个数。例如110和011这两个位串,对它们进行异或运算,其结果是:
110⊕011=101
异或结果中含有两个1,因此110和011之间的海明距离就等于2
首先,python是有现成的simhash的包,项目地址:
https://github.com/leonsim/simhash
安装命令:
1pip install simhash
(1) 查看simhash值
1>>> from simhash import Simhash
2>>> print('%x' % Simhash(u'How are you? I am fine. Thanks.'.split()).value)
36a8987771e0cfc67
(2) 计算两个simhash值距离
1>>> hash1 = Simhash(u'How are you? I am fine. Thanks.'.split())
2>>> hash2 = Simhash(u'How are u? I am fine. Thanks.'.split())
3>>> print(hash1.distance(hash2))
4
511
对于短文本,改变一些对于相似性的改变还是挺大的。
看到所有的例子都是英文的,不知道 simhash对中文的支持怎么样?但是细想了一下,simhash支持分词完的列表作为输入数据,所以这完全不影响对simhash包的使用,完全可以使用jieba分词之后,在使用simhash进行计算。
1import jieba
2from simhash import Simhash
3
4words1 = jieba.lcut('腾讯洋葱反入侵防御系统,很厉害!', cut_all=True)
5words2 = jieba.lcut('腾讯洋葱反入侵防御系统,果然很厉害!', cut_all=True)
6
7print(Simhash(words1).distance(Simhash(words2)))
1>> 6
1# 说明: self.f 为simhash的长度;
2# self.value 为当前实例的simhash值;
3# self.hashfunc 为计算hash的函数,默认是md5;
4
5# 计算文本的hash值
6def build_by_features(self, features):
7 """
8 `features` might be a list of unweighted tokens (a weight of 1
9 will be assumed), a list of (token, weight) tuples or
10 a token -> weight dict.
11 """
12 v = [0] * self.f
13 masks = [1 << i for i in range(self.f)] #生成从1位到f位的mashs值,用于每个位的匹配操作
14 if isinstance(features, dict):
15 features = features.items()
16 # h是计算的hash值, w是权重(词频)
17 for f in features:
18 if isinstance(f, basestring):
19 h = self.hashfunc(f.encode('utf-8'))
20 w = 1
21 else:
22 assert isinstance(f, collections.Iterable)
23 h = self.hashfunc(f[0].encode('utf-8'))
24 w = f[1]
25 for i in range(self.f):
26 v[i] += w if h & masks[i] else -w # 位操作,位值为1,则为w,位值为0,则为-w;
27 ans = 0
28 for i in range(self.f):
29 if v[i] > 0:
30 ans |= masks[i] # 合并所有计算结果
31 self.value = ans
1def distance(self, another):
2 assert self.f == another.f
3 x = (self.value ^ another.value) & ((1 << self.f) - 1)
4 ans = 0
5 while x:
6 ans += 1
7 x &= x - 1
8 return ans
虽然simhash是针对文档去重的应用提出来的,但它的思想完全可以用在其他大规模规模样本的聚类上,我们从上文中可以看到simhash的流程分为5步:
分词,把需要判断文本分词形成这个文章的特征单词。
hash,通过hash算法把每个词变成hash值。
加权。
合并,把上面各个单词算出来的序列值累加,变成只有一个序列串。
降维,形成我们最终的simhash签名。
第一步的分词,对于文档的来说,其实是一个提取特征的过程。
假如我们把分词替换成从恶意代码中提取的特征,这样就可以无缝使用simhash算法,因此我们只需要准备好特征及权重即可,然后按照simhash算法的流程进行hash、加权、合并、降维,最后对每一个样本都生成对应的simhash签名。
本文主要对原理,应用进行了比较详细的讲解,与安全的结合只是进行了思想启发,没有给大家分享具体的项目,等我找到一个合适不敏感的项目再给大家拆解。
我的知乎号:七夜,有问题的话,大家可以在知乎上给我提,我有时间的话,会给大家回答的。或者在微信号中给我提也是可以的。
原创不易,希望大家能
积极分享,点在看
https://www.cnblogs.com/maybe2030/p/5203186.html#_label3 https://www.jianshu.com/p/1187fb7c59c5
https://www.cnblogs.com/-wenli/p/11150476.html
https://leons.im/posts/a-python-implementation-of-simhash-algorithm/
沙盒syscall监控组件:strace and wtrace
无"命令"反弹shell-逃逸基于execve的命令监控(上)
如果大家喜欢这篇文章的话,请不要吝啬分享到朋友圈,并置顶公众号。
关注公众号:七夜安全博客
回复【11】:领取Sandboxie源码
回复【1】:领取 Python数据分析 教程大礼包
回复【2】:领取 Python Flask 全套教程
回复【3】:领取 某学院 机器学习 教程
回复【4】:领取 爬虫 教程
回复【5】:领取编译原理 教程
回复【6】:领取渗透测试教程
回复【7】:领取人工智能数学基础
回复【8】:领取 python神经网络 教程
回复【9】:领取 安卓逆向 教程