第一章 绪论
1.1 研究背景和意义
大数据和云计算的普及为按需服务提供了服务导向。现有 Web 服务具有丰富的功能和“即插即用”的属性，使得越来越多的开发人员用来构建自己的系统。然而，尽管基于系统开发的 Web 服务非常简便，Web 服务管理对于服务提供商和用户而言都是一个巨大的挑战。现代计算机系统不断增加的复杂性是系统发展和管理的一个明显限制因素，在许多系统中能够产生告警信息和即时处理成为系统管理的一个基本要求。特别地，服务提供者希望向大量的用户提供无差错的服务，同样的，用户需要高效地管理接受的服务。在这样的背景下，基于日志分析的使用服务日志实现自动或半自动服务管理的服务管理技术被广泛讨论。
1.1 研究背景和意义
大数据和云计算的普及为按需服务提供了服务导向。现有 Web 服务具有丰富的功能和“即插即用”的属性，使得越来越多的开发人员用来构建自己的系统。然而，尽管基于系统开发的 Web 服务非常简便，Web 服务管理对于服务提供商和用户而言都是一个巨大的挑战。现代计算机系统不断增加的复杂性是系统发展和管理的一个明显限制因素，在许多系统中能够产生告警信息和即时处理成为系统管理的一个基本要求。特别地，服务提供者希望向大量的用户提供无差错的服务，同样的，用户需要高效地管理接受的服务。在这样的背景下，基于日志分析的使用服务日志实现自动或半自动服务管理的服务管理技术被广泛讨论。
几乎每个系统或软件都会将服务运行信息写入到系统日志里。由许多组件组成的系统，例如 Web 服务、复杂的企业应用程序，将这些事件从其许多组件收集到日志文件中。这些日志旨在用于记录开发阶段和正常操作，以便调试和理解复杂系统的行为，因此成为公司收集日志的主要推动力[1]。
日志数据通常是记录服务运行信息的唯一可获得的数据源。总体而言，一条日志信息是开发者所编写的打印日志状态的一行文本，包含了诸如使用模式、执行路径、程序运行状态等信息。因此，利用数据挖掘技术获悉系统行为的日志分析技术被广泛应用于服务管理中以增强系统的稳定性、安全性和可用性。日志分析技术可以用于事件相关规则的发掘、检测系统错误[2]和网络异常、事件相关模式可视化、识别网络流量模式、诊断系统性能[3]以及自动化建立 IDS 告警分类。对于服务提供商，日志分析技术广泛用于异常检测[4]、程序验证[7]、故障诊断[9]。对于服务使用者而言，日志分析技术则被应用于商业模式挖掘，以及用户行为分析中。
..............................
1.2 国内外研究现状
传统的日志分析方法主要靠人工检验，但是随着网络的发展，这样的方法无疑是耗费劳动力且容易出差错。近年来国内外研究学者对日志解析的研究主要可以分为基于强规则解析日志、离线自动化解析日志和在线自动化解析日志三个方面。
1.2.1 基于强规则解析日志
早期日志解析依赖于正则表达式方法[13]，该方法由开发者设计并亲自维护。然而正则匹配法由于增长迅速的日志体积、千奇百怪的日志格式、频繁更新的日志状态三个方面的原因并不适用于现代服务产生的日志。Xu 等人[14]设计了一个基于源代码自动化生成正则表达式的方法，然而源代码通常是不可获取的。通过专家经验/源代码人工构建相关的正则表达式解析日志，尽管可以获得非常准确的日志主干，然而该方法因上述因素而大大受限。
1.2.2 离线自动化解析日志
..............................
1.2 国内外研究现状
传统的日志分析方法主要靠人工检验，但是随着网络的发展，这样的方法无疑是耗费劳动力且容易出差错。近年来国内外研究学者对日志解析的研究主要可以分为基于强规则解析日志、离线自动化解析日志和在线自动化解析日志三个方面。
1.2.1 基于强规则解析日志
早期日志解析依赖于正则表达式方法[13]，该方法由开发者设计并亲自维护。然而正则匹配法由于增长迅速的日志体积、千奇百怪的日志格式、频繁更新的日志状态三个方面的原因并不适用于现代服务产生的日志。Xu 等人[14]设计了一个基于源代码自动化生成正则表达式的方法，然而源代码通常是不可获取的。通过专家经验/源代码人工构建相关的正则表达式解析日志，尽管可以获得非常准确的日志主干，然而该方法因上述因素而大大受限。
1.2.2 离线自动化解析日志
近年来，国内外对离线日志解析研究进行了多方面的尝试和探索。离线日志解析需要一个日志收集过程。该阶段主要可以细分为六个方面：基于启发式规则、基于聚类、基于频繁项集、基于神经网络、基于遗传进化、基于层次化聚类。
（1）基于启发式规则的日志解析方法
简单日志文件聚类工具（SLCT）[15]已知的最早自动化日志解析工具。受关联规则的启发，SLCT 主要分成步骤构建包含单词位置和频率的词典表、通过词典表构建聚类的候选集和生成事件签名三个步骤。在聚类过程中，SLCT 将匹配相同模式的日志放在相同的类中，为了在日志数据集中发现类别，SLCT 提供了支持阈值 s 来定义每一个类中的最少数目。通过输入数据集 SLCT 进行聚类算法以识别出至少出现 s 次的频繁单词。当前一个操作执行完毕时，那些至少出现 s 次的单词条目被重新拼接成该日志的事件格式。SLCT 存在许多缺点，首先，SLCT 无法检测出日志中存在的通配符；其次，由于单词的位置也被编码，该算法因单词位置和分隔符噪声而变得敏感；最后，低的支持阈值 s 会导致过拟合现象。为了解决因单词位置和分隔符噪声产生的问题，Reidemeister[16]用 Levenshtein 距离函数的单连接聚类算法来替代原始 SLCT 中的聚类方法，最后的结果被转化为位向量，构建一个决策树以用于未来的日志事件错误识别。
（1）基于启发式规则的日志解析方法
简单日志文件聚类工具（SLCT）[15]已知的最早自动化日志解析工具。受关联规则的启发，SLCT 主要分成步骤构建包含单词位置和频率的词典表、通过词典表构建聚类的候选集和生成事件签名三个步骤。在聚类过程中，SLCT 将匹配相同模式的日志放在相同的类中，为了在日志数据集中发现类别，SLCT 提供了支持阈值 s 来定义每一个类中的最少数目。通过输入数据集 SLCT 进行聚类算法以识别出至少出现 s 次的频繁单词。当前一个操作执行完毕时，那些至少出现 s 次的单词条目被重新拼接成该日志的事件格式。SLCT 存在许多缺点，首先，SLCT 无法检测出日志中存在的通配符；其次，由于单词的位置也被编码，该算法因单词位置和分隔符噪声而变得敏感；最后，低的支持阈值 s 会导致过拟合现象。为了解决因单词位置和分隔符噪声产生的问题，Reidemeister[16]用 Levenshtein 距离函数的单连接聚类算法来替代原始 SLCT 中的聚类方法，最后的结果被转化为位向量，构建一个决策树以用于未来的日志事件错误识别。
..........................
第二章 相关背景知识介绍
2.1 系统日志数据挖掘内容
系统日志中的数据挖掘的过程中，其主要内容可以分为以下几类： 事件生成。事件生成旨在从包含许多细节信息的文本日志转化成离散化或结构化的事件。该部分是本文研究的重点内容，相关工作见 1.2 节。
多维数据分析。多维数据分析旨在汇总和整理数据，通过对数据自身或者结合业务的规律进行分析得到有用的结果。文献[31]将 ELK 日志分析平台应用到有线网中，对有线网日志进行统计分析，提供日志查询和可视化功能。
关联分析。关联分析旨在寻找数据之间的共现关系进而获取数据内在的关联规则。文献[32]对 IDS 告警日志进行因果关联分析，提出基于可疑队列的多源攻击图的入侵检测方法。
分类和预测。分类和预测旨在对现有的日志数据进行归纳和总结，并对未来的日志数据进行预判的过程。文献[33]通过对告警日志数据进行分析，从而进行网络的故障预测。 时间序列分析
时间序列分析旨在挖掘时序数据直接的相关性。文献[34]阐述了在实际应用中时序和事件之间相关性问题的重要性，并提出了同时识别连续事件序列数据以及时序事件数据见的相关性方法。
事件摘要。事件摘要旨在对给定系统的日志进行总结和归纳，以便于日志分析人员理解整个系统的信息。事件摘要结果有不同的表现形式，如分段模型[35]、隐马尔科夫模型[36]、图[1]和事件关系网[37]等等。
...........................
2.2 系统日志格式探究
2.2.1 系统日志数据的格式
系统日志是由系统或者软件组件生成，用于描述系统或软件组件操作、状态、警告、错误或者关于系统或软件其他信息的半结构化数据。
尽管控制台日志以自由文本形式呈现，由于它们是通过系统中相对较小的一组日志打印语句打印而成，实际上它们都是半结构化的。图 2.1 显示了两条日志信息以及产生它们的源代码[38]。可以看出，日志生成代码中隐含着某些固定的日志表达格式。以图 2.1 中的例子而言，CLog 类的功能是将信息写入到日志文件中。CLog 的 info 函数输入参数包括字符串“starting”和参数 txn，由此看出字符串“starting”可是个固定项，可以被认为是个常量，而txn 作为表征 Transaction 类的一个对象则被视作变量。toString 函数中则分别将常量“xact”、变量“id”、常量“is”和变量“state”连接起来。文献[39]将产生日志数据的源代码认为是日志的一种模式，可以从该模式中推断出生成的日志结构。可以利用这种日志模式来确定每一个日志信息的事件类型，除此之外，也可以提取变量值作为事件的相关属性[38]。
...........................
第二章 相关背景知识介绍
2.1 系统日志数据挖掘内容
系统日志中的数据挖掘的过程中，其主要内容可以分为以下几类： 事件生成。事件生成旨在从包含许多细节信息的文本日志转化成离散化或结构化的事件。该部分是本文研究的重点内容，相关工作见 1.2 节。
多维数据分析。多维数据分析旨在汇总和整理数据，通过对数据自身或者结合业务的规律进行分析得到有用的结果。文献[31]将 ELK 日志分析平台应用到有线网中，对有线网日志进行统计分析，提供日志查询和可视化功能。
关联分析。关联分析旨在寻找数据之间的共现关系进而获取数据内在的关联规则。文献[32]对 IDS 告警日志进行因果关联分析，提出基于可疑队列的多源攻击图的入侵检测方法。
分类和预测。分类和预测旨在对现有的日志数据进行归纳和总结，并对未来的日志数据进行预判的过程。文献[33]通过对告警日志数据进行分析，从而进行网络的故障预测。 时间序列分析
时间序列分析旨在挖掘时序数据直接的相关性。文献[34]阐述了在实际应用中时序和事件之间相关性问题的重要性，并提出了同时识别连续事件序列数据以及时序事件数据见的相关性方法。
事件摘要。事件摘要旨在对给定系统的日志进行总结和归纳，以便于日志分析人员理解整个系统的信息。事件摘要结果有不同的表现形式，如分段模型[35]、隐马尔科夫模型[36]、图[1]和事件关系网[37]等等。
...........................
2.2 系统日志格式探究
2.2.1 系统日志数据的格式
系统日志是由系统或者软件组件生成，用于描述系统或软件组件操作、状态、警告、错误或者关于系统或软件其他信息的半结构化数据。
尽管控制台日志以自由文本形式呈现，由于它们是通过系统中相对较小的一组日志打印语句打印而成，实际上它们都是半结构化的。图 2.1 显示了两条日志信息以及产生它们的源代码[38]。可以看出，日志生成代码中隐含着某些固定的日志表达格式。以图 2.1 中的例子而言，CLog 类的功能是将信息写入到日志文件中。CLog 的 info 函数输入参数包括字符串“starting”和参数 txn，由此看出字符串“starting”可是个固定项，可以被认为是个常量，而txn 作为表征 Transaction 类的一个对象则被视作变量。toString 函数中则分别将常量“xact”、变量“id”、常量“is”和变量“state”连接起来。文献[39]将产生日志数据的源代码认为是日志的一种模式，可以从该模式中推断出生成的日志结构。可以利用这种日志模式来确定每一个日志信息的事件类型，除此之外，也可以提取变量值作为事件的相关属性[38]。
...........................
3.1 基本签名生成算法框架 ........................................... 12
3.1.1 日志预处理过程 .......................................... 13
3.1.2 根据日志长度划分日志 ................................ 14
第四章 层次化日志解析算法 ............................ 30
4.1 基本签名生成树生成算法 ............................................ 30
4.1.1 构建字段向量 ........................................... 31
4.1.2 构建签名向量 .............................................. 33
第五章 细粒度事件依赖关系的挖掘 ............................................ 42
5.1 细粒度事件依赖关系挖掘过程 ................................................ 42
5.1.1 基于模板重定义的基本签名生成算法 ................................... 42
5.1.2 基于 T-pattern 的事件过程挖掘算法 .................................... 43
第五章 细粒度事件依赖关系的挖掘
5.1 细粒度事件依赖关系挖掘过程
5.1.1 基于模板重定义的基本签名生成算法
具有不同语义或频繁参数值的类似消息应当位于不同的事件中。在现有的大多数日志解析方法里，它们都基于日志本身结构分析而设计的模型，忽略语义特征最终导致不同语义或频繁参数值的类似的消息被认为是相同的事件[1]。
为了在这种情况下产生期望的结果，将日志解析方法应用到实际生产环境中，本文提出了改进的基本签名生成算法（Improved Basic Signature Generation, IBSG），该方法基于基本签名生成算法 BSG，在合并事件消息签名工作之前，设计了基于最大基尼分割的模板重定义算法（Cluster Refinement based on Maximum Gini Split，CRMGS），该算法基于消息中的单词位置的熵和每个位置内的单词来分割事件簇，以在单词位置中考虑参数的簇的成员之间保持低熵。为了加速计算，最终考虑采用最大基尼指数来作为最低熵的近似。
表 5.1 显示了 CRMGS 的算法伪代码：
..........................
..........................
第六章 总结与展望
6.1 研究结论
随着云计算和大数据的普及，越来越多的开发人员构建自己的系统，大数据、精细化运营成为网络运营的重要发展方向。本课题对日志提取和应用方面进行了研究，并取得了一定的研究成果。
本课题首先通过系统日志的特点进行分析，提出一个自适应在线日志解析方法，该方法能够针对不同的系统日志进行参数的自适应调整，通过挖掘日志之间的相似结构来达到提取事件的目的，通过与其它四种解析方法在六种日志数据集上的解析结果进行比较，验证了该方法的有效性和高效性。
本课题在自适应在线日志解析方法的基础上，提出事件层次化的概念，通过构建事件层次树为运营人员提供从粗略到精细的视图，并结合日志对象的异常检测方法提供了在事件层次上选择事件节点的方法。通过与包含第三章提出的日志解析方法在内的六种日志解析方法进行比较发现，该方法可以进行一步解决事件具有不同长度日志的问题，同时通过异常检测实例验证事件节点选择方法的合理性。
本课题最后将日志解析方法进行了简单应用。一方面考虑到上述两种方法的不足对自适应在线日志解析方法进行了补充，该算法在企业级测试中具有良好的表现。另一方面对解析事件应用到实际的生产环境中，通过分析和改进 T-pattern 的不足来获取事件之间的依赖关系和对应的时滞区间，在实际应用中通过检测该图来检测异常事件。
参考文献（略）