Spell: Streaming Parsing of System Event Logs (paper reading)

文章最后更新时间为：2019年12月18日 15:24:12

在以数据为基础的主机威胁检测中，系统日志扮演了重要的角色。但是面对繁多，复杂，多样的日志，人工查看显然是不合适的，所以对系统日志进行自动化分析，从而检测威胁活动，是很有现实意义的事情。

近年来，由于机器学习的发展，对系统日志进行分析是也取得了很大的成果。分析系统日志的第一步往往是日志解析，现在存在很多系统日志解析工具，面对不同的机器学习方法，不同的日志解析方法各有其优越性，本文记录一下我对Spell解析工具的理解。

Spell是李飞飞等人在论文Spell Streaming Parsing of System Event Logs中提出来的，论文地址在此

1. 介绍

该论文提出了一种在线实时动态解析日志的方法，名为Spell，基于LCS(最长公共子序列)的方式。实现了动态接受日志输入，实时处理输入，不断生成新的日志模板。

据论文中的研究表明，即使与离线方法相比，Spell在效率和有效性方面仍然是牛逼的。

一般来说，每个日志都是由固定程序输出的，那么其输出格式一定有个模板，比如日志：

Temperature (41C) exceeds warning threshold

那么其一定是类似于以下程序输出的:

printf("Temperature %s exceeds warning threshold\n", tmp);

我们可以提取到其模板为

Temperature * exceeds warning threshold

参数为(41C)。

所以所有的日志都可以解析成模板(日志键)和参数，从而对日志进行归类。

我们的目标就是解析出日志的模板和参数，那么接下来就是怎么实现这种算法了。

我们先大致了解一下parper介绍的算法，细节之后再考虑：

1. 初始化程序，首先定义一个日志对象LCSObject，对象包括日志键(LCSseq)属性和行数列表(lineIds)，还定义一个日志对象列表LCSMap，用于保存每个日志对象。
2. 输入log文件，按行读取。(实现了流式)
3. 读取一行日志，然后遍历LCSMap，看列表中是否已经有LCSObject拥有和其一样的LCSseq(日志键)，如果存在这样的LCSObject，则将这个日志的lineIds添加到LCSObject的lineIds。如果没有，则生成新的LCSObject到LCSMap中。
4. 不断读取日志，直到结束。

似乎是很简单的，那么问题来了，假如输入一个新的日志条目比如：

Temperature (41C) exceeds warning threshold

我怎么去提取出其中的日志键，然后和其他LCSObject的日志键去比较是否相同呢？

这里就体现了其实时动态的优点了。

Spell的思想是不直接提取其中的日志键，而是比较中提取。举个Paper中的例子：

假设现在输入的日志条目为

Temperature (43C) exceeds warning threshold

然后遍历LCSMap，发现有一个LCSObject的LCSseq为

Temperature (41C) exceeds warning threshold

那么我们计算出其LCS(最大公共子序列)为

Temperature exceeds warning threshold

当最大公共子序列的长度在输入条目长度的1/2倍到1倍之间时，则判断这属于同一个日志键，于是将其合并，将此日志条目的linelds增加到LCSObject的linelds属性中。

其过程如下图所示：

2. 代码实现

代码实现可以看这个项目：https://github.com/nbigaouette/spell-rs，其中rust、python、java版本都有。

我是看的源码https://github.com/bave/pyspell，直接跑一下还是很容易理解的。

我参考上面项目注释了大部分代码，并且修改了部分逻辑，可参考我为此新建的的项目 https://github.com/saucer-man/Dlog。

train.log:
this is a pen
this is the pen
this is a pen
i am gun
i am bebe
i am gun and bebe
i am a and b


test.log:
this is test_a pen
this is test_the pen
this is test_a pen
i am test_gun
i am test_bebe
i am test_gun and test_bebe
i am test_a and test_b

之后会更新很多关于主机日志检测的项目在上面，欢迎关注。