第一章 绪论
1.1 研究背景与研究意义
1.1.1 研究背景
随着全球信息化的不断发展和进步，网络信息技术已经逐渐在国际政治、经济、文化、军事等领域造成了不同程度的影响，计算机网络已经出现在人类生活的各个方面，深刻的改变了人类的生活习惯、思维模式以及行为方式。
根据 Facebook 在 2016 年发布的全球互联网接入报告，到 2016 年底全球接入网络中的人数大约有 34 亿，比 2015 年增加了 2 亿人。同时报告中还指出，在过去的 10 年中，全球上网人数每年增长约为 2 到 3 亿。随着计算机网络和计算机技术的高速发展，网络安全防护需求也日益增加。根据我国互联网应急中心 2016 年的报告，当前我国的总体网络安全指数为“良趋中”。当前的网络状况从表面上看似良好，但实际上网络安全威胁：漏洞、病毒、恶意代码等层出不穷。根据应急中心 2016 年的月报显示，平均每个月有大约 260 万台电脑感染网络病毒，接近 5000 家网站的主页被篡改，1000 多个系统安全漏洞被发现以及海量的隐私信息被暴露。
据国家互联网络信息中心（CNNNIC）发布的《第 41 次中国互联网络发展统计报告》[1]，截至 2017 年 12 月，我国网民规模达到 7.72 亿，互联网普及率超过了 55.8%，计算机网络已经渗透到了社会的各个层次和领域。网络给人类带来了巨大的便利的同时，随之而来的是网络犯罪、攻击、泄密等诸多的安全隐患。报告中提到，2017 年,国家互联网应急中心（CNCERT）共检测我国境内感染网络病毒终端累计 2095 万个，境内被篡改网站累计 60684 个，政府网站被篡改 1065 个；国家信息安全漏洞共享平台收集了 15981 个漏洞，其中高危漏洞累计 5678个。我国作为发展中的网络大国，网络安全形势异常严峻。
........................
（1）数据存储的优化
..........................
第二章 日志相关概念
1.2 国内外研究现状
关联规则挖掘技术是数据挖掘技术中最成熟的研究方向之一，目前用于关联规则分析的算法主要分为两类，分别是经典的 Apriori 算法和 FP-growth 算法。Apriori 算法是由 RakeshAgrawal 和 Ramakrishnan Skrikant 在 1990 年提出的，刚提出时较为简单，是一种使用逐层搜索的迭代算法，易于理解。但是在产生候选项集时，产生的组合太多，空间复杂度高；对事务数据库多次扫描，I/O 开销大，时间复杂度高。这两方面的原因导致了采用 Apriori 算法进行关联规则挖掘时效率低下。为了提高挖掘的效率，出现了各种思路的改进算法，FP-growth算法就是其中之一。FP-growth 算法是韩家炜等人提出的使用前缀树的分治算法，将频繁项集全部压缩到频繁模式树中，不会产生候选项集，整个挖掘过程扫描两次事务数据库，从时、空两个方面对 Apriori 算法进行了改进，挖掘效率得到了显著的提升。
数据挖掘技术经过发展到现在已经比较成熟了，关联规则挖掘作为其中的一个重要的分支，也出现了很多改进的算法用于对日志的挖掘。这些改进的算法大体上是从以下几个方面来做的改进：关联规则挖掘技术是数据挖掘技术中最成熟的研究方向之一，目前用于关联规则分析的算法主要分为两类，分别是经典的 Apriori 算法和 FP-growth 算法。Apriori 算法是由 RakeshAgrawal 和 Ramakrishnan Skrikant 在 1990 年提出的，刚提出时较为简单，是一种使用逐层搜索的迭代算法，易于理解。但是在产生候选项集时，产生的组合太多，空间复杂度高；对事务数据库多次扫描，I/O 开销大，时间复杂度高。这两方面的原因导致了采用 Apriori 算法进行关联规则挖掘时效率低下。为了提高挖掘的效率，出现了各种思路的改进算法，FP-growth算法就是其中之一。FP-growth 算法是韩家炜等人提出的使用前缀树的分治算法，将频繁项集全部压缩到频繁模式树中，不会产生候选项集，整个挖掘过程扫描两次事务数据库，从时、空两个方面对 Apriori 算法进行了改进，挖掘效率得到了显著的提升。
（1）数据存储的优化
传统的数据挖掘技术是将数据直接读取到内存，在这种情况下，如果数据量很小，那么挖掘出的规则可能没有意义，如果数据量较大，那么可能出现内存放不下这么多数据或者会占用大量的系统资源的情况。尤其是使用 Apriori 算法生成频繁项集时，产生了大量候选项集的组合，这将占用极大的内存空间，很可能因为内存不够而导致挖掘失败。文献[4]提出了一种改进思路，即将原始数据的水平数据结构转换成垂直对应的事务 ID 和数据项的数据结构，以此来解决经典 Apriori 算法存在的占用大量内存的问题，并且在进行数据结构转换的同时，对数据的存储格式进行分类标记，从而减少候选项集的数量，提高了挖掘的效率。文献[5]中采用双数组存储的方式对数据存储进行优化，从而在时间复杂度和空间复杂度上都有一定的提高。
（2）结构化挖掘
结构化挖掘的主要改进思路是通过构建图、树等数据结构来进行优化挖掘过程，使挖掘过程变得清晰化。如 FP-growth 算法中构建的前缀树 FP-Tree，是由事务数据库转换成的一棵特殊的前缀树，进行挖掘频繁项集时，直接对 FP-Tree 进行挖掘即可，而不必反复访问事务数据库。文献[6]中提到了一种基于 Hash 的关于 FP-growth 算法的优化思路，这个改进思路解决了建立频繁模式树时，由于循环比较，造成的时间复杂度较高的问题。文献[7]中提出了一种不同于 FP-Tree 的树结构，这种树结构是将用户访问的 URL 进行编码，有相同前缀的 URL放到同一颗子树上。文献[8-13]分别从不同的角度基于 FP-growth 算法提出自己的改进策略，效果均有一定程度的提升。..........................
第二章 日志相关概念
2.1 日志的概念
日志数据的核心是日志消息，日志消息就是计算机系统、设备、软件等在某种刺激下反应生成的东西，确切的刺激在很大程度上取决于日志消息的来源[26]。例如，Unix 操作系统会记录用户登录和注销的消息，防火墙将记录 ACL 通过和拒绝的消息，磁盘存储系统在故障发生或者在某些系统认为将会发生故障的情况下生成日志信息，通过网站日志可以清楚的得知用户在什么 IP、什么时间、用什么操作系统、什么浏览器、什么分辨率显示器的情况下访问了你网站的哪个页面，是否访问成功。
日志数据的核心是日志消息，日志消息就是计算机系统、设备、软件等在某种刺激下反应生成的东西，确切的刺激在很大程度上取决于日志消息的来源[26]。例如，Unix 操作系统会记录用户登录和注销的消息，防火墙将记录 ACL 通过和拒绝的消息，磁盘存储系统在故障发生或者在某些系统认为将会发生故障的情况下生成日志信息，通过网站日志可以清楚的得知用户在什么 IP、什么时间、用什么操作系统、什么浏览器、什么分辨率显示器的情况下访问了你网站的哪个页面，是否访问成功。
尽管日志没有一个统一的标准格式，但可以从以下几个概念来初步了解日志。
1.事件（event）：是在某个环境之下发生的事情，通常涉及改变状态的尝试。事件通常包括时间、发生的事情，以及与事件或者环境相关的任何可能有助于解释或者理解事件原因及效果的细节。
事件分类根据一种或者多种分类方法为事件分组。分类方法的例子包括根据事件期间发生的情况、涉及各方、影响的设备类型等分类。
2.事件字段（event field）：描述了事件的某个特征。事件字段的例子包括日期、时间、源 IP 地址、用户标识以及主机标识。
3.事件记录（event record）是事件字段的一个集合，这些字段共同描述了某个事件。与事件记录同义的术语包括“审计记录”（audit record）和“日志条目”（log entry）。
4.日志（log）是一个“事件记录”的集合。“数据日志”、“活动日志”、“审计日志”、“审计跟踪”、“日志文件”以及“事件日志”等术语常常与日志的意义相同。
...........................
2.2 日志的格式和类型
理解基本的日志格式会使我们更加容易地识别和处理在所处环境里新的或者以前没有见过的日志数据，任何日志记录机制都可以从逻辑上分为三个部分：日志传输、日志语法与格式、日志记录的设置（配置与建议）。
1.日志传输
日志传输就是将日志消息从一个地方转移到其他地方的方式。事件传输协议有许多种，例如 syslog、WS-Mangement 和许多专有的产品特定的日志传输协议，还有一些日志记录机制没有自己的传输方法（例如，只有本地日志文件）。合格的日志传输机制必须既能保证日志数据的完整性、可用性以及机密性（如果有需求的话），又能维护日志的格式和意义并使发生的所有事件都能得到正确的表示，具备正确的时间和事件顺序。日志传输中最重要的需求是保证各个日志（事件记录）以及整个事件流／日志的完整性气更重要的是保存每个日志条目的正确时间戳。
1.事件（event）：是在某个环境之下发生的事情，通常涉及改变状态的尝试。事件通常包括时间、发生的事情，以及与事件或者环境相关的任何可能有助于解释或者理解事件原因及效果的细节。
事件分类根据一种或者多种分类方法为事件分组。分类方法的例子包括根据事件期间发生的情况、涉及各方、影响的设备类型等分类。
2.事件字段（event field）：描述了事件的某个特征。事件字段的例子包括日期、时间、源 IP 地址、用户标识以及主机标识。
3.事件记录（event record）是事件字段的一个集合，这些字段共同描述了某个事件。与事件记录同义的术语包括“审计记录”（audit record）和“日志条目”（log entry）。
4.日志（log）是一个“事件记录”的集合。“数据日志”、“活动日志”、“审计日志”、“审计跟踪”、“日志文件”以及“事件日志”等术语常常与日志的意义相同。
...........................
2.2 日志的格式和类型
理解基本的日志格式会使我们更加容易地识别和处理在所处环境里新的或者以前没有见过的日志数据，任何日志记录机制都可以从逻辑上分为三个部分：日志传输、日志语法与格式、日志记录的设置（配置与建议）。
1.日志传输
日志传输就是将日志消息从一个地方转移到其他地方的方式。事件传输协议有许多种，例如 syslog、WS-Mangement 和许多专有的产品特定的日志传输协议，还有一些日志记录机制没有自己的传输方法（例如，只有本地日志文件）。合格的日志传输机制必须既能保证日志数据的完整性、可用性以及机密性（如果有需求的话），又能维护日志的格式和意义并使发生的所有事件都能得到正确的表示，具备正确的时间和事件顺序。日志传输中最重要的需求是保证各个日志（事件记录）以及整个事件流／日志的完整性气更重要的是保存每个日志条目的正确时间戳。
一些知名的日志传输机制如：syslog UDP、syslog TCP、加密 syslog、SOAP over HTTP、SNMP、传统文件传输方式（FTPS 或 SCP）。
2.日志语法与格式
日志语法与格式定义日志消息形成、传输、存储、审核以及分析的方式。在最简单的情况下，每条事件记录可以作为文本字符串看待，事件的消费者可以在日志中执行全文搜索，期望文本具有一致性。但为了进行可靠的自动化事件分析，事件的消费者和生产者对事件记录语法的理解和认同就显得十分必要。
2.日志语法与格式
日志语法与格式定义日志消息形成、传输、存储、审核以及分析的方式。在最简单的情况下，每条事件记录可以作为文本字符串看待，事件的消费者可以在日志中执行全文搜索，期望文本具有一致性。但为了进行可靠的自动化事件分析，事件的消费者和生产者对事件记录语法的理解和认同就显得十分必要。
一些知名的日志格式：W3C 扩展日志文件格式、Apache 访问日志、Cisco SDEE/CIDEE、syslog、IDME（基于 XML 格式）。现在的大部分日志依然没能遵循任何指定或预定的格式（或者说只有消息的一小部分遵循，例如时间戳），它们仍然被认为是自由格式的文本。
...........................
...........................
3.1 数据挖掘技术...............................13
3.1.1 数据挖掘概述....................................13
3.1.2 数据挖掘常用技术...................................14
第四章 关联规则挖掘算法的改进.............................27
4.1 关联规则算法的改进......................................27
4.2 改进的算法描述..................................28
第五章 算法实现与实验仿真对比分析.........................35
5.1 改进算法的实现..................................35
5.2 对比实验设计.................................36
第五章 算法实现与实验仿真对比分析
5.1 改进算法的实现
本文在第三章中详细描述了基于 FP-growth 算法的改进算法，并且结合实例对改进算法的挖掘过程进行了介绍，根据这个过程并结合 FP-growth 算法的代码，将改进算法分成四个模块实现。
（1）D-Tree 的建立：对经过预处理后的数据集进行一次扫描，将数据集中的每一个事务分别作为一条路径，建立 D-Tree。并且为 D-Tree 中的每个节点分别进行计数，记录其在树中出现的次数，最后将树中重复节点的计数相加求和，得到的就是事务数据库中每一项的支持度计数，如表 4-2 所示。
（2）新 FP-Tree 的构建：对 D-Tree 进行扫描，得到 D-Tree 中的每条路径，根据表 4-2所示的支持度计数，过滤掉小于最小支持度阈值的项，剩余项按照支持度递减的方式，对每条路径中剩余的项进行排序，使得每条路径中最频繁的项始终在第一个位置，将排序后的路径依次插入到新 FP-Tree 中，并保存相应节点出现的次数。同时，建立一个节点表，将每次插入时已经存在于新 FP-Tree 中的新建节点和不包含最频繁的项的路径中的所有项全部放入节点表。
（3）生成频繁项集：
将新 FP-Tree 中各个节点出现的次数，即算法 4-2 中的频数 F 与设置的最小支持度阈值 S进行比较，根据比较会出现的三种情况分别从当前项的节点、中间节点、父节点和最频繁节点中生成相应的组合，得到的就是频繁项集。并根据比较得到的结果，采取不同的计算方式计算出频繁项集各自的支持度计数。
（4）提取规则：在得到的频繁项集中采用最小置信度约束，得到满足要求的规则。因为Weka 工具不支持设定最小置信度，所以按照 Weka 工具本身根据置信度从高到低的顺序依次输出规则即可。
............................
第六章 总结与展望
6.1 总结
本研究针对用于对日志进行的关联规则分析从研究背景、意义、目的进行阐述，并对用于关联规则挖掘的两种经典算法结合实例进行了详细的描述，针对两种经典算法存在的缺陷提出了一种基于 FP-growth 算法的改进算法，并对改进的算法的挖掘过程进行了详细的描述和实例分析。对三种算法 Apriori 算法、FP-growth 算法和改进算法进行分析和实现，进行了对比实验。实验重点从关联规则挖掘的速度和挖掘规则的准确性两个方面对改进算法的性能进行评估。
实验结果表明，改进算法在挖掘的速度和精确度上这两个方面与 Apriori 算法相比，都有很大的提高，并且在不降低精确度的情况下，比 FP-growth 算法挖掘所需要的时间更短，且时间差会随着数据量的进一步增大而增大。所以总的来说，改进的算法在性能上是优于两种经典的关联规则挖掘算法的。
通过对日志进行挖掘发现正常事件的规则并建立起正常事件规则库，可作为发现网络中的攻击事件的一个重要方式。一旦发现不是正常规则的事件发生时，可以及时做出应对措施。若最后得出该事件是正常的行为，则对规则库进行补充，将其加入规则库；若是攻击事件，则因为是在最短的时间内做出的反应，所以能够最大程度的降低攻击事件给系统带来的影响和损失。在实际的应用中便于实时的处理海量数据，对系统进行监控，及时发现攻击事件，有重要的研究意义。
参考文献（略）
参考文献（略）