Research on Document Comparison Algorithm Based on Modified Fuzzy Hash

doi:10.3969/j.issn.1671-1122.2016.11.003

Abstract

Abstract:

Fuzzy hash was widely used in homologous files’ investigation, malicious code detection and digital forensics. Based on the file length and content detection, fuzzy hash segmented a file firstly. Then the Hash value of each file segment was calculated by a rolling hash algorithm. The finger print of the whole file was eventually formed by concatenating all segments’ hash values. Hence the approximate nearest neighbor search problem could be solved by fuzzy hash with the locality sensitive feature. A modified fuzzy hash algorithm was proposed in this paper to overcome the drawbacks of classical fuzzy hash algorithm, such as the segment length depends on file length, triggered condition has no close contact with segment content, and the length of rolling window determines operational performance. The two main modifications were variant length segments triggered by keywords and a rolling hash method based on simhash. The experiments on different corpus show that almost identical documents could be efficiently detected; meanwhile the multi-level comparison with different granularity could be supported by this algorithm.

Key words: fuzzy hash, locality sensitive, document comparison, rolling hash

CLC Number:

TP309

Hongyu DI, Jing ZHANG, Yi YU, Lianyin WANG. Research on Document Comparison Algorithm Based on Modified Fuzzy Hash[J]. Netinfo Security, 2016, 16(11): 12-18.

Figures/Tables 7

References 17

[1]	胡雪,封化民,李明伟,等. 数据挖掘中一种增强的Apriori算法分析[J]. 信息网络安全,2015(11):77-83.
[2]	ZAMORA J, MENDOZA M, ALLENDE H.Hashing-based Clustering in High Dimensional Data[J]. Expert Systems with Applications, 2016, 62(15): 202-211.
[3]	KHAN S, GANI A, WAHAB A W A, et al. Network Forensics: Review,Taxonomy,Open Challenges[EB/OL]., 2016-3-20.
[4]	李亚萌,何泾沙. 基于Hash的YAFFS2文件各版本恢复算法研究[J]. 信息网络安全,2016(5):51-57.
[5]	CHRISTIAN W, MARKUS S, YORK Y.F2S2: Fast Forensic Similarity Search through Indexing Piecewise Hash Signatures[J]. Digital Investigation, 2013, 10(4): 361-371.
[6]	王建峰. 基于哈希的最近邻查找[D]. 合肥:中国科学技术大学,2015.
[7]	INDYK P, MOTWANI R.Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality[C]//ACM. 30th Annual ACM Symposium on Theory of Computing, May 24-26, 1998, Dallas, Texas, USA. New York: ACM, 1998: 604-613.
[8]	BREITINGER F, BAIER H.Performance Issues about Context-triggered Piecewise Hashing[C]//EAI. Third International ICST Conference, October 26-28, 2011, Dublin, Ireland. Heidelberg: Springer, 2011: 141-155.
[9]	CHARIKAR M S.Similarity Estimation Techniques from Rounding Algorithms[C]//ACM. 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montreal, Quebec, Canada. New York: ACM, 2002: 380-388.
[10]	刘禹. 中文新闻分类语料库[EB/OL]. , 2016-6-20.
[11]	尚海,罗森林,韩磊,等. 基于句义成分的短文本表示方法研究[J]. 信息网络安全,2016(5):64-70.
[12]	李荣陆. 文本分类语料库(复旦)[EB/OL]. , 2016-6-21.
[13]	BREITINGER F, STIVAKTAKIS G, BAIER H.FRASH: A Framework to Test Algorithms of Similarity Hashing[J]. Digital Investigation, 2013, 10(10): 1066-1069.
[14]	National Institute of Standards and Technology. National Software Reference Library[EB/OL]. , 2016-6-21.
[15]	PAULEVE L, JEGOU H, AMSALEG L.Locality Sensitive Hashing: A Comparison of Hash Function Types and Querying Mechanisms[J]. Pattern Recognition Letters, 2010, 31(11): 1348-1358.
[16]	KORNBLUM J.Identifying Almost Identical Files Using Context Triggered Piecewise Hashing[J]. Digital Investigation the International Journal of Digital Forensics & Incident Response, 2006, 3(3): 91-97.
[17]	史记,曾昭龙,杨从保,等. Fuzzing测试技术综述[J]. 信息网络安全,2014(3):87-91.