基于层次隐马尔科夫模型和变长语义模式的入侵检测方法

段雪涛，贾春福,2，刘春波

(1. 南开大学 信息技术科学学院，天津 300071；2. 国家计算机病毒应急处理中心，天津 300457)

1 引言

入侵检测是计算机信息系统安全保障的关键技术之一，是位于防火墙和访问控制之后重要的安全防护措施。Forrest[1,2]等人将人工免疫的思想引入到入侵检测技术中，构造计算机系统的正常行为模式库，并通过比对系统运行时的模式与正常行为模式库的方法来判断系统是否异常或被入侵。

目前，大多数研究人员通常都利用一组定长的系统调用短序列模式来描述进程的正常运行状态。使用定长短序列方法的一个主要局限就是很难合理地选择短序列的长度。一般来说，定长短序列的长度通常是根据经验来选择，序列的长度一般选取为4至8之间。短序列模式越长，入侵检测系统就越倾向于捕获更多的异常，但同时模式库的规模会越大，算法的执行效率也会降低，而且更重要的是误报率也会增加，对建库和检测都会造成困难[3]。而采用短的序列会造成区分度降低，增大漏报率。这样使得定长序列的检测方法难以两全，很难在存储空间方面和检测效率方面都较好地满足实时检测的需要。Lee[4]等人利用条件熵模型来求最优短序列的长度，然而系统调用序列的局部模式好比进程的基因片断，这样的局部模式可以认为是一个功能片段，它代表了一个有特定意图的操作流程，同时也蕴涵了进程的行为方式。由于文献[4]的条件熵模型在系统调用序列的收集过程中跨越整个进程的执行过程，忽略了进程执行语义的阶段性以及不同进程执行语义的差异性。因此，笔者认为在整个数据集上采用条件熵模型通过构造定长序列模式来描述进程行为并不合理。但是变长模式的抽取算法过于复杂，目前的算法[5～8]复杂度过高。

可以注意到，每个程序都是由很多子函数组成，而程序中的子函数恰如一个个有着特殊意义的语义基因片段，这些片段呈现出明显的层次特征和语义关系。在本文中，将利用进程堆栈中的函数返回地址链来抽取系统调用的变长序列模式，并使用层次隐马尔科夫模型（HHMM， hierarchical hidden Markov model）来构造一种能够利用变长模式语义关系的新入侵检测模型。

2 变长语义模式的提取

根据操作系统中函数调用的原理，在向操作系统内核发起系统调用请求时，所有与之相关联的函数调用的返回地址均存放在进程堆栈中，通过解析进程堆栈可以获取与系统调用相关联的函数返回地址。本文使用函数返回地址来表示对应的函数调用，从而得到系统调用序列的函数返回地址链。

理论上来说，对于一个进程，其系统调用序列对应的函数返回地址链均有相同的尾链，即 main函数的返回地址。相邻的一段系统调用，如果它们均是由某一个上层函数调用衍生，则它们对应的地址链的后几个节点相同。可以根据地址链信息之间的关联关系，对所有系统调用的函数返回地址链进行关联。以地址链的尾节点为起始端，对所有的地址链信息进行归并，得到一个与进程对应的树形函数地址结构。图1是进程执行的一个简单程序转化为函数调用树形结构的例子。其中，A～F代表函数调用的返回地址；S1～S9代表依次执行的系统调用。因此，中间叶节点分支处的系统调用可以构成一条变长系统调用短序列模式。

进程堆栈中的函数返回地址链反映了程序内部函数依次调用的关系，从一定程度上反映了程序结构。这种利用函数返回地址链来提取变长序列模式方法的基本思想是根据产生系统调用的不同函数来分解系统调用序列从而得到变长模式。与其他寻找变长模式的方法相比，这种方法中的每个模式分别代表了程序按某一路径执行的函数产生的系统调用序列，在功能上表征了某一个程序的函数访问系统内核资源的情况。

图1 函数返回地址树形结构

3 基于HHMM的入侵检测模型

由于提出的变长系统调用模式提取方法构造出的短序列具有明显的层次结构和状态转移特性，而这种结构特征恰与统计方法中的HHMM模型相吻合，由此，希望能够构造出一种适合于入侵检测的HHMM模型。

3.1 HHMM模型简介

HHMM是隐马尔科夫模型[9,10]的一种扩展，是一种结构化的多层次随机过程[11]。HHMM 并不直接辐射出观测符号，它拥有一个根状态节点，并且由根状态节点辐射出一系列子状态，而这些子状态又可以独立地被看作是一个 HHMM，并且以迭代的方式向下层子节点辐射。这种迭代的辐射方式最终将终结于一类特殊的状态节点，称为输出状态，这种输出状态将向外放射出类似于 HMM 的观测符号。而其他没有放射出观测符号的状态，称为抽象状态或中间状态。定义由中间状态传递到其子状态的过程，称之为垂直转移。定义在同一层次的状态之间的转移为水平转移。因此，整个HHMM可以抽象为一个树形结构，树的根节点就是HHMM的根状态，树的叶节点就是HHMM的输出状态。

为了描述HHMM，需要定义以下符号或变量：

∑：表示有限符号集。

∑*：表示∑中所有可能出现的组合。表示 ∑*中出现过的一个观察序列。表示HHMM中的一个状态，i表示该状态编号，d表示该状态的层次编号。根状态节点的层次编号为 1，输出状态的层次编号为D。

|qd|：表示一个中间状态所拥有的自状态数

i量。在i明确时，可以直接用 qd表示。使用以上符号，HHMM可以定义为

图2是一个4层的HHMM抽象图。粗线的箭头表示垂直状态转移，黑色的箭头表示水平状态转移，虚线的箭头表示本层终止状态返回上一层父状态。为了简化表示，输出状态在本图中被省略。

图2 HHMM的抽象描述图

3.2 HHMM序列概率计算与参数估计算法

HHMM是一种具有层次结构的HMM。可以使用动态规划Baum-Welch算法来计算序列产生的概率。定义“前向”概率为

也就是，“前向”概率表示在t时刻由状态 qd-1产生局部观测符 ot… ot+k，且在t+k时刻生成 qd的概率。通过计算在d层所有这样的状态概率之和，可以得到：

与此类似，可以得到HHMM的“后向”概率为

为了能够对HHMM的参数进行估计，需要添加与垂直方向状态转移过程相对应的路径变量。定义以下变量：

和

其中， ξ (t,qid,qdj ,qd-1)：表示在时刻 t生成观测符号 ot之后，且生成观测符号 ot+1之前，由状态 qid到状态 qdj的水平状态转移概率。表示在生成观测符号 ot之前，向状态 qid的水平状态转移概率。表示在生成观测符号 ot之后，离开状态 qid的水平状态转移概率。表示经由状态 qid在时刻 t生成观测符号 ot之前，状态 qd-1的概率。

基于这些关于路径的变量定义，可以得到如下参数重估算法：

为了能够找到模型的一组最佳参数，迭代计算χ以及辅助路径变量，之后利用以上方程来计算新的参数。

3.3 HHMM入侵检测模型

HHMM适用于多种应用环境，如文本分类、手写识别等。在本文提出的基于 HHMM 的入侵检测方法中，将利用进程堆栈中的函数调用地址链构造 HHMM 的状态集，并使用变长系统调用序列来构造 HHMM 的观测符号集。与传统的HMM 相比，这种模型的构造方法对于描述进程语义结构更加适合，对于变长系统调用短序列的切分也更加合理。

该HHMM模型分为2个阶段：训练阶段和检测阶段。

在训练阶段，利用进程堆栈中的函数调用地址链信息来切分变长系统调用短序列，定义每条函数调用地址链组成HHMM的状态，并定义各进程在相应状态链下产生的系统调用短序列为HHMM的观测符号，以此来构造HHMM的树形模型结构。

下面以一个简单的程序为例，说明该模型树形结构的构造方法。程序代码如下：void func1(FILE *fp) {

char str1[20];

memcpy(str1, "cantoluna", 10);

fwrite(str1, 10, 1, fp);

printf("cantoluna is record in the object file! ");

}

void func2(FILE *fp) {

char str2[20];

memcpy(str2, "pastorale", 10);

fwrite(str2, 10, 1, fp)

printf("pastorale is record in the object file! ");

}void main(void) {

FILE *fp = fopen("secret_garden.txt", w+);

int i = getc();

if (i ＞ '0')

func1(fp);else (i ＜= '0')

func2(fp);fclose(fp);}

这段程序包括一个主程序以及2个子程序，实现的功能是根据输入条件在指定文件中写入不同的字符串。根据函数调用关系，main函数是根，对应 HHMM 的根状态；main函数直接调用的函数fopen、getc、func1、func2和 fclose分别对应 HHMM的第2层状态；func1和func2 这2个函数所调用的memcpy等函数则对应HHMM的第3层状态。第2层的fopen、getc和fclose以及第3层的memcpy等函数是库函数，不再调用其他函数，因而对应HHMM 的输出状态。再考虑到同一层函数执行时的逻辑顺序，并将每条函数调用地址链对应的系统调用短序列作为相应输出状态的观测符号，即可构造出如图3所示的HHMM树形结构。

在生成模型的树形结构后，再采用上文给出的推广的Baum-Welch算法对HHMM进行参数估计。

在检测阶段，仍然根据进程堆栈中的函数调用地址链获得进程在实际运行环境中的变长语义模式，并按照上文给出的HHMM序列概率计算方法计算出该模型下变长序列出现的概率。如果计算出的 (|)POλ小于预先设定的阈值，则判定为异常入侵行为；否则，认为是正常进程行为。

4 实验

4.1 实验数据介绍

采用 LKM[12]技术来截获操作系统产生的系统调用以及进程在运行时的堆栈信息。通过模拟用户的正常行为来收集正常行为模式，通过恶意代码与入侵脚本的攻击来收集异常行为模式。在收集系统调用短序列的时候，只记录与操作系统服务进程相关的行为模式。在实验过程中，使用80%的正常行为模式来训练该入侵检测模型，并使用其余20%的正常数据以及所有的异常数据作为检测数据。表1给出了ftpd和sendmail守护进程的实验数据收集情况。

图3 根据函数调用地址链构造的HHMM树形结构实例

表1 实验数据源描述

4.2 实验结果

在实验中，比较了传统的HMM模型与HHMM模型的入侵检测效果，对比结果采用ROC（receiver operating characteristic）图[13]来描述，如图4和图5所示。显然，不论对 ftpd进程，还是对 sendmail进程，HHMM 模型与传统的HMM模型相比，都具有更好的检测效果，在误报率较低的情况下，能提供更高的检测率。

通过对实验结果的分析还发现，这种HHMM模型不仅状态数较少，并且其观测符号集数量也控制在一定范围之内。这是由于其观测值也可以理解为由一段段变长系统调用序列所构成的语义模式片断。

图4 HHMM与HMM针对ftpd守护进程的测试结果比较

图5 HHMM与HMM针对sendmail守护进程的测试结果比较

5 结束语

与定长系统调用短序列方法不同，本文提出了一种使用变长系统调用短序列的入侵检测思路。这种思路以进程执行语义为出发点，对采集到的系统调用按照语义行为切分短序列。此外，由于变长系统调用短序列之间具有严格的层次结构和状态转移关系，因此本文提出了一种基于HHMM的变长模式入侵检测方法。实验证明这种方法具有良好的检测效果。

[1] FORREST S, HOFMEYR S A, SOMAYAJI A, et al. A sense of Unix processes[A]. Proceedings of the 1996 IEEE Symposium on Research in Security and Privacy[C]. 1996.120-128.

[2] FORREST S, PERELSON A S, ALLEN L, et al. Self-nonself discrimination[A]. Proceedings of the 1994 IEEE Symposium on Research in Security and Privacy[C]. 1994. 202-212.

[3] LEE W, STOLFO S J. Data mining approaches for intrusion detec-tion[A]. Proceedings of the 7th USENIX Security Symposium[C]. San Antonio, Texas, 1998.

[4] LEE W, XIANG D. Information theoretic measures for anomaly detection[A]. Proceedings of the 2001 IEEE Symposium on Research in Security and Privacy[C]. Oakland, California, 2001.130-134.

[5] KOSORESOW A P, HOFMEYR S A. Intrusion detection via system call trace[J]. IEEE Software, 1997, 14(5)∶ 35-42.

[6] WESPI A, DACIER M, DEBAR H. Intrusion detection using variable-length audit trace patterns[A]. Proceedings of Workshop on Recent Advances in Intrusion Detection[C]. Toulouse, France, 2000.110-129.

[7] ZHANG X H, LI J W, JIANG Z H, et al. Black-box extraction of functional structures system call traces for intrusion detection[A]. Advanced Intelligent Computing Theories and Applications with Aspects of Contemporary Intelligent Computing Techniques[C]. Springer, Berlin Heidelberg, 2007. 135-144.

[8] WESPI A, DEBAR H, DACIER M, et al. Fiexed vs. variable-length patterns for detecting suspicious process behavior[A]. Proceedings of the 5th European Symposium on Research in Computer Security[C].2004. 1-15.

[9] RABINER L R, JUANG B H. An introduction to hidden Markov models[J]. IEEE ASSP Magazine, 1986, 3(1)∶ 4-16.

[10] ZHONG A M, JIA C F. Study on the application of hidden Markov models to computer intrusion detection[A]. Proceedings of the 5th World Congress on Intelligent Control and Automation[C]. Hangzhou,2004. 4352-4356.

[11] FINE S, SINGER Y, TISHBY N. The hierarchical Markov model∶analysis and application[J]. Machine Learning, 1998, 32(1)∶ 41-62.

[12] 徐伟,贾春福. 扩充Linux系统功能的LKM技术[J]. 计算机应用研究, 2003, 20(4)∶ 100-102.XU W, JIA C F. LKM∶ a technology to enhance functionalities of Linux kernel[J]. Application Research of Computers, 2003, 20(4)∶ 100-102.

[13] FAN J, UPADHYE S, WORSTER A. Understanding receiver operating characteristic (ROC) curves[J]. Canadian Journal of Emergency Medicine, 2006, 8(1)∶ 19-20.