5.3 基于入侵关联图的入侵模式发现
入侵模式发现实际上就是根据收集到的多源信息，发现一次入侵所包含的攻击行为，并将这些行为有机联系在一起，重构出能反映入侵过程的攻击场景。准确地重构出入侵过程有利于提高安全事件分析和判断的准确性，能够描述出入侵者的入侵行为模式，对证明计算机犯罪具有非常重要的意义。
描述入侵场景的工具方法有很多，图5-8是比较常见的一种，主要分析攻击之间的因果关联，因此这些分析的前提是只考虑相同源、目的主机之间的攻击的关联，即认为入侵者最初的踩点扫描，到最后入侵到目标系统实施一些具体的操作这期间的入侵行为都是同源同目的，这种方法无法表示和发现Connection-chain类型的攻击问题。
【图1】
【图2】
需要注意的是，在入侵关联图中，两个顶点之间可能会存在多条边，因为一个主机向另一个主机发起的攻击行为可能不止一个。这是入侵关联图与我们通常意义上所说的图的一个比较大的不同。另外，考虑到取证的目标以及实际的发生概率，我们不考虑两个顶点之间会有两条反向的边。
【图3】
【图4】
对于取证目的而言，我们关心的是针对某些特定的关键主机的入侵发现和分析取证，而涉及到其他无关主机的行为可以不在我们的考虑范围之内，因此引入“关键路径”的定义。关键路径的意义在于发现某些不会通过任何方式攻击到关键主机，也不会被关键主机影响到的主机。
【图5】
通常我们只考察关联路径的路径威胁度，路径威胁度的意义在于识别哪些入侵过程具有较高的威胁程度，从而加以关注，发现其是否具有计算机犯罪的行为。
5.3.2 入侵关联图的构造与合并算法
LCA获取的原始日志经过格式标准、聚合、去除冗余和误告警等处理之后，形成了能体现真正实用信息的告警Alert,入侵关联图就是在Alert为数据源的基础之上构成的。入侵关联图的元素包括节点和节点之间的边，也就是说构造入侵关联图必须有相应的主机以及在主机之间发生的攻击行为的信息，因此从Alert中提取主机信息和事件信息来构造入侵关联图。
【图6】
这样，就形成了一个反映了关键主机被入侵或者参与入侵的入侵关联图，通过这个图可以很直观地发现主机之间的入侵关联情况，更可以很直观地描述出涉及到多台主机的跳板攻击和蠕虫类的攻击情况。
入侵关联图的存储可以采用邻接表的方式，占用的存储单元个数只与图中顶点的个数有关，比邻接矩阵节省空间。对于图G中的每个顶点v,,该方法把所有邻接于v;的顶点V}链成一个带头结点的单链表，这个单链表就称为顶点V}的邻接表。单链表中的每个结点至少包含两个域，一个为邻接点域（adjvex），它指示与顶点v,邻接的顶点在图中的位序，另一个为链域（next），它指示与顶点v,邻接的下一个顶点。为了表示出边的信息以及两个顶点之间可能有多条边，单链表的每个结点还应扩充一个平行边域，它指示同顶点的多条边，构成了扩展邻接表。为了表述边上的信息，单链表的每个结点还有多个信息域：边的S9信息，边的T9信息以及时间信息，信息域可以扩充。
图5-10的扩展邻接表如图5-11（a）所示，实际上也是图5-10的一个出边表。为了查找路径中上游节点方便，还可以构造扩展逆邻接表来存储入侵关联图的信息，如图5-11（b）所示，逆邻接表的邻接点域（adjvex）和链域（next）均指向路径反方向上的邻接顶点。有n个顶点和e条边的入侵关联图的邻接表的空间复杂度为O（n+e）。
【图7】
构造图的过程就是构造其扩展邻接表的过程。构造算法中AddNode函数中还包含了一个遍历图的过程，对于n个事件来说，图中最多有2n个顶点和n条边，遍历过程的时间复杂度为。（n），因此，图的构造算法的时间复杂度为O（n2）o用于构造一个入侵关联图的Alert集合实际上是一个Alert的序列，因此是按照时间顺序加入到图当中，为了防止入侵关联图的规模太大，我们限定Alert序列的长度L以时间跨度为约束，即假如时间跨度闭值为T,则要求Alert序列满足}Alert.time-Alert}.time5T,超过这个时间跨度的Alert只能归入下一个Alert序列，构造成下一个入侵关联图。
这样，时间上先后生成的两个入侵关联图中可能存在相关联的主机以及入侵，但由于时间跨度的原因被分隔在两个入侵关联图里，因此在构造出一个新的入侵关联图之后，可以考虑从上一个入侵关联图里找到相关的顶点和边，合并到新的图当中，来丰富新产生的入侵关联图的信息。为了防止合并操作的时间开销过大，提出以下合并原则：
1.只对相邻顺序产生的两个入侵关联图进行合并；
2.只对新的入侵关联图中入度为0的顶点进行合并处理；
3.只对处于关键路径上的边进行合并处理。
【图8】
通过合并我们发现，新的告警可能是对已有入侵模式中缺失部分的补全，经过合并操作，入侵模式更为完整，如图5-10中Path（C,D）本不是关键路径，但从合并之后的图5-15可以看出，<C,D>可能是<D,E>的前奏，因此Path（C,D）也变为关键路径。通过这个例子我们还会发现合并会造成一定的冗余，但这个冗余相对于能发现更完整的入侵模式来说，是可以接受的。
返回本篇论文目录查看全文 上一章：入侵检测系统Snort的告警日志 下一章：入侵模式挖掘方法
