基于模式匹配算法的文件类型识别技术的研究

论文摘要

恶意篡改文件格式信息达到掩盖文件的真实类型是计算机犯罪中最常用的手段,为了打击犯罪,正确识别文件真实格式的技术显得更加重要。本文主要围绕文件格式识别技术和文件格式识别技术的支撑算法——模式匹配算法展开研究,分别提出了模式匹配算法的改进算法、文件特征的提取算法以及设计了文件格式识别模型、未知文件识别系统并且通过实验进行了有效的验证,主要内容如下:(1)提出了一种适应较长模式串的匹配算法。由于长模式串字符分布具有显著的统计特性,而现有算法往往忽略了此特性,导致算法效率没有达到最优化;因此,本算法通过使用位置转移链表和平均分段技术,充分利用模式串本身特性,加速模式在非匹配下的跳跃速度和跳跃距离,减少匹配次数,从而达到在模式串较长的条件下提高匹配速度的效果。理论分析和实验测试表明,本算法时间复杂度较低,匹配效率较高。(2)提出了一种基于机器字长的位并行算法。由于现有算法更多的关注于时间复杂度的最优化,而忽略了挖掘机器本身的潜能,使得实际应用中实际的算法加速没有达到最优化,因此,本算法在利用模式串本身特性的基础上,使用位并行技术,充分挖掘机器本身的潜能,从而达到最大加速算法的效果。理论分析和实验测试表明,本算法时间复杂度较低,在一个机器字长范围内匹配效率较高。(3)提出了一种基于篡改方式的近似多模式匹配算法。由于现有的算法在多模式近似匹配时,对于容错率和耦合度的要求很高,当容错率较低或者耦合度较大时,算法的效率将会快速下降,更为严重的是,现有的算法大多都非常复杂,因此,结合本课题,针对文件被篡改的特点,即在对文件格式修改方式中,多是使用篡改而非删改,结合位置转移链表和位并行技术的使用,实现可以最多同时匹配机器字长单位的特征数,并有效的解决了容错率较低和耦合度较高的问题。理论分析和实验测试表明,本算法在同类算法中构造较为简单,时间复杂度较低,实践应用效果较好。(4)提出了一种可以全面求解文件公共子序列的算法。因为现有最长公共子序列算法只是求解两文本数据间最长的公共的子序列,一个且只有一个,但是在实际应用中我们发现,相关主要信息并不一定都在这唯一的一个最长公共子序列中,在其它的公共子序列中叶可能存在大量有用信息,因此,为了可以更加全面的得出文件的特征,实现多特征综合定位文件类型,结合模式匹配算法的应用,通过使用位置转移链表和有效剪枝技术,从而得出文本间的有效公共子序列。理论分析和实验测试表明,本算法时间复杂度较低,实践应用效果较好。(5)设计了文件特征模型。通过对已有特征的有效分类和有机组织,实现特征的层次化应用,为建立文件识别模型提供坚实的基础。(6)设计完成了未知文件类型识别系统。通过对模式匹配算法和特征提取算法的综合利用,结合文件特征模型的使用,设计了一个未知文件识别系统。本系统通过对于几个常用文件类型,即ppt、doc、xls及pdf的进实验,结果表明,本系统对于文件后缀名被篡改可以达到100%、文件内容被篡改15%仍旧可以达到80%左右的识别率,从而实现了未知文件的有效识别。最后,最整体的工作进行了总结,并对下一步的工作做出了展望,并提出了进一步研究的方向。

论文目录

• 表目录
• 图目录
• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景
• 1.2 研究现状及发展趋势
• 1.2.1 文件类型识别方法和技术
• 1.2.2 模式匹配算法
• 1.3 研究的必要性
• 1.4 研究的主要成果
• 1.5 论文章节安排
• 第二章 模式匹配算法的研究
• 2.1 模式识别
• 2.1.1 模式识别的概念
• 2.1.2 特征匹配与模式匹配算法
• 2.2 模式匹配算法的分类
• 2.3 单模式精确匹配算法
• 2.3.1 BM 算法
• 2.3.2 BNDM 算法
• 2.3.3 Sunday 算法
• 2.3.4 算法对比
• 2.4 多模式精确匹配算法
• 2.4.1 AC 算法
• 2.4.2 WM 算法
• 2.4.3 两算法复杂度对比
• 2.5 概率（近似）匹配算法
• 2.5.1 算法介绍
• 2.5.2 动态规划算法
• 2.5.3 基于自动机的方法
• 2.5.4 过滤匹配算法
• 2.6 QLP 算法
• 2.6.1 算法描述
• 2.6.2 算法测试
• 2.6.3 算法分析
• 2.7 QBP 算法
• 2.7.1 算法描述
• 2.7.2 算法测试
• 2.7.3 算法分析
• 2.8 多模式近似算法的改进算法
• 2.8.1 动态规划算法的改进
• 2.8.2 位并行近似多模式匹配算法
• 2.9 本章小结
• 第三章 文件格式类型识别技术的研究
• 3.1 基于文件后缀名的文件类型识别
• 3.2 基于文件魔数信息的文件类型识别
• 3.3 基于文件二进制内容的文件类型识别
• 3.3.1 基于字节值频率分布的方法
• 3.3.2 基于统计分析的方法
• 3.3.3 二进制内容识别技术的缺点
• 3.4 全面求解公共子序列的算法
• 3.4.1 相关定义
• 3.4.2 现有算法的未及之处
• 3.4.3 新的算法
• 3.4.4 有效公共子序列的生成规则
• 3.4.5 时间复杂度
• 3.5 本章小结
• 第四章 文件格式识别系统的构造
• 4.1 系统的现实意义
• 4.2 特征模型
• 4.2.1 文件特征的分类
• 4.2.2 特征的结构特点
• 4.2.3 特征模型的设计
• 4.2.4 本节小结
• 4.3 系统构造预备
• 4.3.1 特征描述方式的选择
• 4.3.2 算法的选择
• 4.3.3 特征模型的设计
• 4.4 系统的构造
• 4.5 系统的测试
• 4.5.1 后缀名类型识别测试
• 4.5.2 未篡改文件内容的类型识别测试
• 4.5.3 篡改文件内容的类型识别测试
• 4.5.4 与现有工具比较
• 4.6 本章小结
• 结束语
• 全文总结
• 下一步工作展望
• 参考文献
• 作者简历 作者攻读硕士学位期间完成的主要工作
• 致谢