Simhash在安全应用中的思考

前言

最近和相似度杠上了，今天和大家分享一下周末研究的东西：SimHash。记得看到最后哟。

大家如果喜欢我的分享，一定要点在看和分享到朋友圈。现在公众号是信息流模式，对于无法天天更新的原创号来说是不利的，希望大家能与我一起坚持下去。

有你们的坚持，才有更好的世界。

一.背景

理理思路

近年来，恶意代码数量的飞速增长，人工分析恶意代码效率太低，除非特别新的技巧需要人工，其他时候人工的投入远远赶不上木马病毒的产生。

聚类算法用于恶意代码新家族检测越来越重要，很多木马病毒都是新瓶装老酒。因此从恶意代码本身的相似性来进行聚类分析，从而实现由已知到未知的检测。但是有一个问题：数据量太大，我们需要对数据特征进行降维。

google提供了一个好办法，那就是simhash算法。这个算法本身是为了海量网页去重准备的，一个网页几千字，通过这个算法可以浓缩为几个字节的特征，通过这几个字节特征的相似性进行判重。当然也可以用于恶意代码分析。

二.simhash的算法思想

实践出真知

假设我们有海量的文本数据，我们需要根据文本内容将它们进行去重。对于文本去重而言，目前有很多NLP相关的算法可以在很高精度上来解决，但是我们现在处理的是大数据维度上的文本去重，这就对算法的效率有着很高的要求。

而局部敏感hash算法可以将原始的文本内容映射为数字（hash签名），而且较为相近的文本内容对应的hash签名也比较相近。SimHash算法是Google公司进行海量网页去重的高效算法，它通过将原始的文本映射为64位的二进制数字串，然后通过比较二进制数字串的差异进而来表示原始文本内容的差异。

三.simhash的实现流程

Simhash是由 Charikar 在2002年提出来的， 为了便于理解尽量不使用数学公式，分为这5步:

1. 分词，把需要判断文本分词形成这个文章的特征单词。最后形成去掉噪音词的单词序列并为每个词加上权重，我们假设权重分为5个级别（1~5）。比如：“ 美国“51区”雇员称内部有9架飞碟，曾看见灰色外星人 ” ==> 分词后为 “ 美国（4） 51区（5） 雇员（3） 称（1） 内部（2） 有（1） 9架（3） 飞碟（5） 曾（1） 看见（3） 灰色（4） 外星人（5）”，括号里是代表单词在整个句子里重要程度，数字越大越重要。
2. hash，通过hash算法把每个词变成hash值，比如“美国”通过hash算法计算为 100101,“51区”通过hash算法计算为 101011。这样我们的字符串就变成了一串串数字，还记得文章开头说过的吗，要把文章变为数字计算才能提高相似度计算性能，现在是降维过程进行时。
3. 加权，通过 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 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”。这里作为示例只算了两个单词的，真实计算需要把所有单词的序列串累加。
5. 降维，把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

首先，python是有现成的simhash的包，项目地址：

https://github.com/leonsim/simhash

安装命令：

pip install simhash

1. 英文

(1) 查看simhash值

>>> from simhash import Simhash
>>> print('%x' % Simhash(u'How are you? I am fine. Thanks.'.split()).value)
6a8987771e0cfc67

(2) 计算两个simhash值距离

>>> hash1 = Simhash(u'How are you? I am fine. Thanks.'.split())
>>> hash2 = Simhash(u'How are u? I am fine.     Thanks.'.split())
>>> print(hash1.distance(hash2))

11

对于短文本，改变一些对于相似性的改变还是挺大的。

2. 中文

看到所有的例子都是英文的，不知道 simhash对中文的支持怎么样？但是细想了一下，simhash支持分词完的列表作为输入数据，所以这完全不影响对simhash包的使用，完全可以使用jieba分词之后，在使用simhash进行计算。

import jieba
from simhash import Simhash

words1 = jieba.lcut('腾讯洋葱反入侵防御系统，很厉害！', cut_all=True)
words2 = jieba.lcut('腾讯洋葱反入侵防御系统，果然很厉害！', cut_all=True)

print(Simhash(words1).distance(Simhash(words2))) 

>> 6

核心代码：

计算文本的hash值

# 说明: self.f 为simhash的长度；
#      self.value 为当前实例的simhash值；
#      self.hashfunc 为计算hash的函数，默认是md5；

# 计算文本的hash值
def build_by_features(self, features): 
    """
    `features` might be a list of unweighted tokens (a weight of 1
                will be assumed), a list of (token, weight) tuples or
                a token -> weight dict.
    """
    v = [0] * self.f
    masks = [1 << i for i in range(self.f)]  #生成从1位到f位的mashs值，用于每个位的匹配操作
    if isinstance(features, dict):
        features = features.items()
    # h是计算的hash值， w是权重(词频)
    for f in features:
        if isinstance(f, basestring):
            h = self.hashfunc(f.encode('utf-8'))
            w = 1
        else:
            assert isinstance(f, collections.Iterable)
            h = self.hashfunc(f[0].encode('utf-8'))
            w = f[1]
        for i in range(self.f):
            v[i] += w if h & masks[i] else -w  # 位操作，位值为1，则为w，位值为0，则为-w；
    ans = 0
    for i in range(self.f):
        if v[i] > 0:
            ans |= masks[i]  # 合并所有计算结果
    self.value = ans

计算两个hash值的距离

def distance(self, another):
    assert self.f == another.f
    x = (self.value ^ another.value) & ((1 << self.f) - 1)
    ans = 0
    while x:
        ans += 1
        x &= x - 1
    return ans

六.Simhash与安全的结合

虽然simhash是针对文档去重的应用提出来的，但它的思想完全可以用在其他大规模规模样本的聚类上，我们从上文中可以看到simhash的流程分为5步：

1. 分词，把需要判断文本分词形成这个文章的特征单词。
2. hash，通过hash算法把每个词变成hash值。
3. 加权。
4. 合并，把上面各个单词算出来的序列值累加，变成只有一个序列串。
5. 降维，形成我们最终的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/