一种基于隐马尔可夫模型的IDS异常检测新方法
摘 要：提出一种新的基于隐马尔可夫模型的异常检测方法，主要用于以shell命令或系统调用为审计数据的入侵检测系统。此方法对用户（或程序）行为建立特殊的隐马尔可夫模型，根据行为模式所对应的序列长度对其进行分类，将行为模式类型同隐马尔可夫模型的状态联系在一起，并引入一个附加状态。由于模型中各状态对应的观测值集合互不相交，模型训练中采用了运算量较小的的序列匹配方法，与传统的Baum-Welch算法相比，大大减小了训练时间。根据模型中状态的实际含义，采用了基于状态序列出现概率的判决准则。利用Unix平台上用户shell命令数据进行的实验表明，此方法具有很高的检测准确性，其可操作性也优于同类方法。
关键词：入侵检测；隐马尔可夫模型；异常检测；序列匹配
中图分类号：TP18；TP393.08 文献标识码：A
A New Anomaly Detection Method Based on Hidden Markov Models for IDS
Abstract： A new anomaly detection method based on hidden Markov models is presented for Intrusion Detection Systems with shell commands or system calls as audit data. The method constructs specific hidden Markov models to represent the behavior profiles of users or programs, and associates the classes of behavior patterns with the states of the models. Because the collections of observations corresponding to different states are mutually disjoint, the parameters of the models can be estimated by a sequence matching algorithm which is much simpler than the classical Baum-Welch algorithm. This reduces the computational complexity to a great extent. A decision rule based on the probabilities of short state sequences is adopted while the particularity of the states is taken into account. The performance of the method is tested by computer simulation with Unix users’ shell command data. The results show it maintains higher detection accuracy and practicability than other alternative approaches.
Key words： intrusion detection； hidden Markov model； anomaly detection； sequence matching
1 引言
网络入侵检测技术主要有两种类型，即误用检测和异常检测。异常检测是目前IDS（入侵检测系统）研究的主要方向，其优点是不需要过多关于系统缺陷的知识，具有较强的适应性，并且能够检测出未知入侵，但它存在虚警概率高的缺点。异常检测的关键问题是如何建立系统或用户的正常行为模式（库）以及如何利用该模式（库）对当前行为进行比较和判断。
国内外已经开展了神经网络、数据挖掘、机器学习等技术在异常检测中的应用研究，研究目标主要是提高检测系统的准确性、实时性、高效性以及自适应性。本文提出一种新的基于隐马尔可夫模型（HMM）的异常检测方法，它在建模、HMM训练以及判决准则的选取等方面与现有的HMM方法均有较大不同。实验表明，此方法具有很高的检测准确率和较强的可操作性。
2 现有的两种HMM方法
IDS的输入数据主要有两类，分别是主机数据和网络数据。在基于系统调用和shell命令等主机数据的异常检测研究中，HMM方法是一个重要的研究方向。新墨西哥大学的Warrender C等人
基于系统调用数据，进行了针对程序行为的异常检测[2]。其方法是对每种程序（如sendmail、login）的正常行为建立一个HMM，将程序所用的互不相同的系统调用个数作为HMM的状态数，采用Baum-Welch算法训练模型，并利用先验知识对模型参数进行初始化；检测时对数据流中的每个系统调用分别作一次判决。普渡大学的Lane T则基于Unix平台上的shell命令数据，进行了针对用户行为的异常检测研究和实验[1]。其方法是用单个HMM代表一个合法用户的行为轮廓，通过反复实验来确定HMM的最佳状态个数；模型的训练中同样采用了Baum-Welch算法。检测时，利用近似的前向后向算法并根据贝叶斯准则对用户行为进行判别。
以上两种方法是HMM在分类问题中较为的典型用法，在训练数据充足的情况下能够获得比较高的检测准确率，但是，模型的训练和工作中所需要的计算量很大（特别是对于程序行为异常检测），检测的实时性不高，这在很大程度上限制了它们的应用。
3 一种新的基于HMM的异常检测方法
3.1 HMM概念及基本问题的描述
HMM是双重随机过程，其中一个是隐含的有限状态马尔可夫链，它描述状态的转移；另一个随机过程描述状态与观测值之间的统计对应关系。HMM一般有三个假设：当前状态只同上一状态相关；状态之间的转移概率同状态所处的具体时间无关；观测值只与当前状态有关。这三个假设大大降低了模型的复杂度。设观测值序列为，相应的状态序列为，其中,，和分别表示观测值集合和状态集合。HMM通常用五元组来表示，为状态转移概率矩阵，,其中
（1）
为观测值概率矩阵，，其中
，
（2）
为初始状态概率矢量，，其中
（3）
训练、解码和评估是HMM的三个基本问题。训练是指给定观测值序列，确定模型参数，使得最大；解码是对于给定的和，求使最大的状态序列；评估则是指给定模型参数，求观测值序列的出现概率。HMM训练、解码和评估的经典算法分别是Baum-Welch算法、Viterbi算法和前向后向算法。应当指出，HMM的训练，或称参数估计问题，是HMM在异常检测中应用的关键问题；Baum-Welch算法只是解决这一问题的经典方法，但并不是唯一的，也不是最完善的方法[3]。
3.2 基于HMM的异常检测新方法
我们提出一种基于HMM的异常检测新方法，主要用于Unix和Linux平台上以shell命令为审计数据的用户行为异常检测，也可用于以系统调用为审计数据的程序行为异常检测。下面以用户行为异常检测为例，按照建模、训练、检测的顺序对这一方法进行介绍。
（1）建立两个HMM，其中一个HMM用于描述一个或一组合法用户的正常行为，另一个HMM用于描述（入侵者或合法用户的）异常行为。（在对异常行为缺乏了解的情况下，可以只建立一个HMM来描述合法用户的正常行为。）两个HMM的状态集合以及各状态对应的观测值集合相同，其状态对应于合法用户的行为模式类型。按照行为模式所对应的shell命令序列的长度对其进行分类，并根据合法用户的正常训练数据（历史上的正常行为）确定每个状态对应的观测值集合。
入侵检测中行为模式是指用户操作或程序执行过程中体现出的某种规律性。在以shell命令为审计数据的用户行为异常检测中，用户的行为模式通常用shell命令序列来表示[2]。（根据Lane T的实验结论[1]，长度在1到15之间的shell命令序列能够表示一般的用户行为模式。）这里，我们将shell命令序列的长度作为行为模式分类的依据，把长度相同的shell命令序列所表示的行为模式划为同一种类。建模的首要问题是确定合法用户正常行为模式的种类个数，以及相应的shell命令序列长度集合，其中表示第类正常行为模式对应的shell命令序列的长度，且。和对检测性能有直接影响，在选择它们时，需充分考虑合法用户的行为特点，同时还要考虑模型的复杂度及检测效率（和越大，检测系统的存储量和工作中的运算量也会越大）。我们将HMM的状态个数设为，状态集合设为，其中前个状态同合法用户的类正常行为模式一一对应，第个状态为附加状态，它对应于合法用户的正常历史行为（正常训练数据）中未出现过的行为模式（类型），并规定这类行为模式对应的命令序列长度。
和确定之后，需根据合法用户的正常训练数据确定HMM各状态对应的观测值集合，其中为状态对应的观测值集合，即第类行为模式对应的命令序列集合，它包含若干个长度为的命令序列；这里，HMM状态所对应的观测值（或称观测事件）是命令序列。设一个合法用户的正常训练数据为，它是该用户在正常操作时所执行的长度为的shell命令流，其中表示按时间顺序排列的第个shell命令；对应的长度为（）的命令序列流可表示为，其中命令序列。我们设定一个概率门限，将（）中出现概率大于的命令序列视为合法用户的（正常）行为模式，即由这些命令序列组成（一个序列的出现概率是指此序列在相应序列流中的出现次数与该序列流中的序列总数之比）。附加状态对应的观测值集合包括两部分，一部分是由正常训练数据中未出现过的命令组成的长度为1的序列，另一部分则有所区别，当时(此时)，它是中出现概率小于或等于的序列，当时，它是中的所有序列。当时（），，即不同状态对应的观测值集合是不相交的，这和一般的HMM不同，也是此方法的一个主要特点。需要指出，合法用户可以只有一个，也可以有多个；当有多个合法用户时，可将这些用户的正常训练数据组合在一起构成总的训练数据。
（2）利用序列匹配方法计算两个HMM的参数。
设描述合法用户正常行为的HMM参数为，其中和的计算方法如下：
第一步：根据得到（）。设定，，，，。
第二步：如果,将与进行比较；否则，,跳至第五步。
第三步：如果，且，则，，，返回执行第二步；如果，且，则，，，，，，，返回执行第二步；如果，则。
第四步：如果，返回执行第二步；如果(此时)，且，则，，，返回执行第二步；如果，且，则，，，，，，，返回执行第二步。
第五步：对于，。对于，。
上述的计算过程是采用序列匹配的方法，按照时间顺序逐个找出中的行为模式及其对应的状态，同时对每个状态的出现次数和状态之间的转移次数进行统计，从而得到状态转移概率矩阵和初始状态概率矢量。参数计算时假设了HMM中个状态的隐含马尔可夫链是一个各态历经过程。由于检测时不需要用到观测值概率矩阵，其计算方法不再赘述。
设描述异常行为的HMM参数为，异常训练数据为，它是入侵者（非法用户）或合法用户在非法操作或误操作时所执行的shell命令流，和可根据同样采用以上的序列匹配方法进行计算。在缺乏异常训练数据时，可不用计算此HMM的参数。
（3）检测时，利用计算出的HMM参数，基于状态序列出现概率对被监测用户的行为进行判决。
设被监测用户在被监测时间内所执行的shell命令流为。检测时要利用前面参数计算中的序列匹配方法，由得到状态序列及其对应的观测值序列，其中为中的状态总数，，表示按时间顺序排列的第个状态，表示与对应的观测值(命令序列)，的长度为（）。
为了实时监测用户的行为，我们用滑动窗在中截取短序列，以短序列为数据单元进行分析。设短序列为，其中表示短序列的长度（），。相应的状态短序列为。和对应的短序列流可分别表示为和。
按照传统准则，应根据对被监测用户行为进行判决，其计算公式为：
（4）
这里，我们没有采用传统准则，而是将作为判决依据：
（5） 我们之所以用而不用作为判决依据，主要基于以下考虑：
一、观测值集合与状态集合之间有明确的映射（满射）关系，每个状态所对应的观测值集合是根据合法用户的正常训练数据（正常历史行为）确定的，因而状态本身以及状态之间的转移能够反映正常行为与异常行为之间的行为差别。
二、的计算量比小，它只用到了HMM参数中的初始状态概率矢量和状态转移概率矩阵。
三、在
（4）式中，对的计算假设了观测值之间是相互独立的，即观测值只与当前状态有关，根据我们的实验和分析，这一假设并不是很符合用户的实际情况，因而，根据
（4）式得到的不宜作为判决依据。
考虑到用户在短时间内的行为可能会偏离其历史行为，检测中我们并不直接利用对被监测用户的行为进行判决，而是对其做了如下的加窗平滑处理：
（6）
此外，在没有异常训练数据，无法得到参数和的情况下（此时只建立描述合法用户正常行为的HMM），可以只对进行变换和加窗处理，得到如下判决值：
（7）
（6）、
（7）两式中，表示状态序列对应时刻的判决值，，为窗长度（中第个状态短序列及其后面的每个短序列所对应的时间点上都有一个判决值输出）。对设定一个门限，若它大于这个门限，将被监测用户的当前行为判为正常行为（或将此用户判为合法用户），否则，将其判为异常行为（或将此用户判为非法用户）。是一个重要参数，它决定了从被监测用户行为发生到检测系统对其行为做出判断的最短时间（即检测时间）。在不考虑计算时间的情况下，检测时间为个状态持续时间。
3.3 特点分析
以上基于HMM的用户行为异常检测方法主要有以下几个特点：
（1）它是一种异常检测方法，这主要体现在描述正常行为和异常行为的HMM状态以及各状态对应的观测值集合都是根据合法用户的正常训练数据确定的，描述正常行为的HMM参数也是根据此训练数据计算得到的。在计算描述异常行为的HMM参数时，需要用到异常训练数据；但是，当采用
（7）式计算判决值时，无需考虑该HMM的参数。
（2）在Lane T的方法中，HMM状态对应的观测值是用户的shell命令，最佳状态个数是通过反复实验确定的。而此方法中，HMM状态对应的观测值（或称观测事件）不是shell命令，而是长度可变的shell命令序列，状态本身具有明确的含义。模型中，状态的“隐含”是指观测数据（用户shell命令流）中的状态不是直接可见的，而是需要通过序列匹配得到。
（3）根据HMM状态的特点及实际含义，采用了基于状态序列出现概率的判决准则，减小了判决中的计算量，提高了检测的实时性。
（4）HMM的训练和解码均采用了序列匹配方法，同Lane T的传统方法相比，较大程度地减小了计算量，缩短了训练和解码的时间。
4 实验设计及结果分析
实验中，我们采用了普渡大学Lane T网上公布的shell命令实验数据[1]，其数据库包含八个Unix用户在两年时间内的活动记录。每个用户的数据文件中均滤除了用户名、主机名、网址等标识信息，仅保留了shell命令的名称及参数；用户命令流中的命令按照在shell会话中的出现次序进行排列，不同的shell会话按照时间顺序进行连接，每个会话开始和结束的时间点上插入了标识符；实验数据的详细说明可参见文献[1]。 检测时，在user4的后5000个命令中共出现1748个状态，状态对应的命令序列（观测值）的平均长度为2.9；在user
1、user
2、user3的后5000个命令中，分别出现34
9
7、34
3
6、2943个状态（其中相当一部分为附加状态），状态对应的命令序列的平均长度为1.5，这表明长度为5和3的命令序列所表示的合法用户的正常行为模式在三个非法用户的测试数据中较少出现。图1给出了由
（6）式计算的user4和user1的判决值曲线，图2给出了根据
（7）式计算的两条判决值曲线（为绘图方便，对横坐标做了平移）。由两图可见，合法用户（user4）和非法用户（user1）的判决值曲线具有良好的可分性。
实验中，通过调整判决门限可以得到不同虚警概率条件下对三个非法用户的异常行为（或用户类别）的平均检测概率。表1给出了
（6）式和
（7）式两种判决值计算方法对应的实验结果。
表1 两种判决值计算方法对应的实验结果
虚警概率 0 0.001 0.005 0.010 0.050
（6）式对应的
平均检测概率 0.929 0.932 0.939 0.944 0.996
（7）式对应的
平均检测概率 0.933 0.938 0.953 0.960 0.992
根据实验结果，当虚警概率为0时，两种判决值计算方法对应的平均检测概率均可达到90%以上。而且，在虚警概率较低的区间，
（7）式对应的平均检测概率与
（6）式非常接近，这说明仅利用描述正常行为的HMM参数即可获得良好的检测性能。因而，在无法得到异常训练数据及相应HMM参数的情况下，我们可以只建立一个描述合法用户正常行为的HMM来进行异常检测。
5 结束语
本文提出一种新的基于HMM的IDS异常检测方法。实验表明，此方法具有很高的检测准确率和较强的可操作性。根据实验结果，当参数（特别是W和C）设置不同时，检测性能会有一定的变化，因而，根据具体用户的行为特点选择合适的参数是实际应用中提高检测性能的重要途径。此外，本文的方法还适用于以系统调用为审计数据的程序行为异常检测，但是，同用户行为相比，程序行为具有一些不同的特点，所以具体的操作方式及检测性能还有待分析和验证。
参考文献
[2] Warrender C，Forrest S，Pearlmutter B. Detecting intrusions using system calls: alternativedata models[A]. Proceedings of the 1999 IEEE Symposium on Security and Privacy[C]. Berkely，California，USA：IEEE Computer Society，1999：133-145.[3] Rabiner L R，Juang B H. An introduction to hidden Markov models[J]. IEEE ASSP Magazine，1986
(1)：4-16.
