金山微特征的原型——————fuzzy hash（模糊哈希）算法

显示全部楼层 · 发表于 2011-6-12 21:29:04

本帖最后由 jefffire 于 2011-7-19 12:49 编辑

鉴于最近看到某些人吹微特征能查杀未知，特意顶上来

最近看一篇paper，无意中看见了一种模糊哈希算法——fuzzy hash算法。于是立刻去翻阅相关资料，整理出如下文章。

  首先说说哈希算法。
   大家都知道函数实际上就是一种映射，本质是将一个集合通过对应法则f映射到另一个集合。而哈希算法是一个特殊的函数，他具有的特点是，定义域是一个不确定的无限集合而值域是一个有限集合。简单来说,哈希算法就是将一个任意大的数据项（如计算机文件）映射为固定长度（比原数据短的多）的二进制位串，也就是哈希值。就目前而言，哈希算法依然能够确保它是原始数据的唯一标识，就像人的指纹可以唯一地标识一个人，因此哈希算法还具有精确匹配的特性。

常见的哈希算法包括：MD5、sha1、sha256、crc32等等。就不多说了

好了，对哈希算法有了基本概念，就来谈谈由此发展而来的fuzzy hash（模糊哈希）算法。

上文提及了哈希算法具有精确匹配的特性，具体来说就是，原文件哪怕仅仅只是一个字节的变化也会导致最后的哈希值发生明显的变化。这个特性使得哈希算法能够确定一个文件是否被修改过，然而这也带来了很大的局限性，那就是无法分辨内容稍有不同的同类文件。这对我们的反病毒过程来说是很不利的，因为一个样本的变种是数量最多的。

  于是我们为了解决这个问题，发明了模糊哈希算法。该模糊哈希的算法与模糊逻辑搜索很像，它可以寻找相似但不完全相同的文档，即所谓的同源性文件。模糊哈希算法是基于哈希算法的，和哈希算法的不同点在于，哈希算法是将整个文件作为定义域来求算结果，而模糊哈希算法则是先对文件进行分块，计算每一块的哈希值，然后将得到的一系列哈希值利用比较函数于其他哈希值进行比较，来确定相似程度。
简而言之就是：分块——》对每个分块分别计算哈希——》结果比较

分析一下这样的算法有什么优势：比如我把一个文件的某一小部分进行了修改，如果是传统哈希由于是对整个文件进行计算，因此这一点改变就导致了结果的不同。而模糊哈希由于先对文件进行了分块，因此仅仅对某一部分进行修改只会导致某一或某几个分块的哈希值发生变化，而其他分块的哈希值并不变化，通过对比就可以很容易发现相似性。

目前模糊哈希算法，有开源研究项目ssdeep：http://ssdeep.sourceforge.net/

然后我们来看看金山的微特征，通过对国家专利局的检索，我们发现了金山的微特征提取专利：http://211.157.104.87:8080/sipo/ ... xin=fmzl&title=

摘要如下：

本发明涉及计算机杀毒软件领域，尤其涉及一种对病毒文件自动提取特征的方法和装置。对病毒文件自动提取特征的方法，在病毒文件中选取N个适合提取病毒特征的固定位置，每个固定位置分配一个位置ID号，以其中M个固定位置的位置ID号和这M个固定位置所对应的特征值作为病毒特征；所述特征值是指以某个所述固定位置为起点，取长度为L的一段二进制数据来计算的HASH值；其中N≥2，M≥2且M≤N，L＞0。本发明方法和装置所提取的病毒特征大大提高了文件扫描的速度；而且可以用一个病毒特征匹配大量的相似或者相同的病毒文件。

从摘要就能总结出金山微特征具有如下特点：首先它是基于hash值的，并且是取固定长度的文件块来计算哈希值，且对一个文件提取了多个分块。
简而言之就是：确定分块位置并记录——》分块——》对每个分块计算哈希值——》结果比较

和模糊哈希的理论基础以及整个流程如出一辙

显示全部楼层 · 发表于 2011-6-12 21:30:37

补充链接

http://211.157.104.87:8080/sipo/zljs/hyjs-yx-new.jsp?recid=CN200910213641.4&leixin=fmzl&title=对病毒文件自动提取特征的方法和装置&ipc=G06F21/02(2006.01)I

复制代码

显示全部楼层 · 发表于 2011-6-12 21:30:42

看样子不久就有anti方法了

显示全部楼层 · 发表于 2011-6-12 21:31:09

学习了，虽然不是很明白

显示全部楼层 · 发表于 2011-6-12 21:31:58

其实还是以前的那种说法。只不过现在更加透明的显示了具体实现形式罢了。

显示全部楼层 · 发表于 2011-6-12 21:32:03

申请(专利权)人：珠海市君天电子科技有限公司

这个是金山滴？莫非俺火星？

显示全部楼层 · 发表于 2011-6-12 21:56:49

这种做法的实现形式还是很严谨的。已经经历了1年多的打击，看的出还是有非常强的强度。
你最多制造出未知文件，想要制造白文件，几乎不太可能。

另外再补充几句，这个和fuzzy hash的实现手段是不同的。看上去理念和实现的效果是相似的，技术手段还是有差异的
金山的做了大量的服务端交互，和服务端一一匹配成功才可以成功提取特征，否则失败就会提取MD5、并完整上传文件

有兴趣的同学建议使用专利浏览器查看实现细节和它一一比对

显示全部楼层 · 发表于 2011-6-12 21:59:38

本帖最后由 qwe12301 于 2011-6-12 22:06 编辑

金山的这种做法，要求拥有大量白文件、黑文件。并且在此基础上进行大量的分析，提取出最合适的特征，建立最全的文件特征库

感觉这套做法很精妙，确实对文件的识别有非常积极的作用

显示全部楼层 · 发表于 2011-6-12 22:02:09

MagicFuzzX 发表于 2011-6-12 21:30
看样子不久就有anti方法了

见我回复。

显示全部楼层 · 发表于 2011-6-12 22:04:34

广谱性连传统的特征码都比不上

特征码可以人工提取难以修改的代码，增加免杀难度

这个的优势只是可以自动提取特征吗，速度快，但是免杀难度比传统的特征码还低

[讨论] 金山微特征的原型——————fuzzy hash（模糊哈希）算法

评分