论文部分内容阅读
摘要：在安全审计的数据挖掘系统的基础上，提出一个异常检测模型，该模型通过关联分析提取正常行为的关联模式，根据属性的重要性定义每个行为模式，在给每个行为模式进行编码后，通过定义一个相异度函数来计算已知关联模式和当前模式的相异度，根据相异度判断当前模式是否为异常行为，并通过一个特定的审计数据的分析来描述模型工作的过程。目前该模型已成功应用在几个关键业务领域的监控系统和入侵检测系统中。
关键词：安全审计；数据挖掘；异常检测；关联分析；关键业务
中图分类号：TP311.131文献标识码：A 文章编号：1009-3044(2008)23-950-04
Design on Outlier Detection Model Based on Security Audit
Shi Hai-feng
(College of Software, Nanjing College of Information Technology, Nanjing 210046, China)
Abstract: From one data mining systerm on the security audit, this paper presents one outlier detection model, the model picks up the association patterns of the normal action by association analysis, defines every action pattern by the essentiality of the properties, and codes the patterns, then uses a dissimilarity-function getting the dissimilarity between one association pattern and current pattern, and estimate the current pattern by dissimilarity, last describes the working process of the model by given audit data. The model has be applied successfully in some monitor and intrusion detection systems of the key operation domain.
Key words: security audit; data mine; outlier detection; association analysis; key operation
1 引言
目前安全审计已越来越多地成为防火墙、入侵检测和网络监控等系统支持的功能特性，特别当这些系统应用在关键业务领域（如银行，证券等）中时。安全审计的一个重要目的是发现系统或用户行为中的入侵或异常。而如何在大量的审计数据中提取出具有共性的系统特征模式，用于对程序或用户行为作出全面、准确的描述，是实现安全审系统的关键。作为数据挖掘的一个重要部分，异常检测可以从大量冗余信息的数据中提取出隐藏的、有效的模式，如果将其应用于安全审计数据的处理，可以有效地解决海量审计数据的分析问题，为系统和用户行为的判定提供依据。
异常是在数据集中与众不同的数据，使人怀疑这些数据并非随机偏差，而是产生于完全不同的机制[1]。异常检测中对异常的定义是：异常是既不属于聚类也不属于背景噪声的点，他们的行为与正常的行为有很大不同。异常检测通常建立在聚类分析和关联分析的基础上，从方法上可以分为基于统计（statistical-based）、基于距离 (distance-based) [2,3]、基于偏离(deviation-based) [4]和基于密度(density-based) [5]的方法。另外针对异常在高维空间中难以确定，有人提出一个高维数据异常检测的方法[6]，该方法采用遗传优化算法，把高维数据集映射到低维子空间，根据子空间映射数据的稀疏程度来确定异常数据是否存在，算法获得良好的计算性能。
本文提出一个基于安全审计的异常检测模型，该模型中异常检测方法借鉴基于偏离的算法，将该算法中未知的“序列异常”中各个子集间的相异度计算转化为已知的正常行为模式和未知行为模式的相异度计算，算法为每个判定对象定义一个行为模式，模式中各属性按其重要性降序排列，并利用模式中字段值在审计数据库中的信息，对每个模式进行编码，再通过定义一个相异度函数来计算模式间的相异度，根据相异度和设定阈值的比较来判断模式是否为异常。
下面首先介绍在一个基于安全审计的数据挖掘系统中构建异常检测模型的构建过程，并详细分析该模型的工作过程，最后通过一个特定的审计数据来描述异常检测的处理过程。
2 异常检测模型设计
2.1 数据挖掘系统框架
本模型是基于一个安全审计的数据挖掘系统的基础上实现，该系统结构图如图1所示。由于传统的安全审计系统在数据采集规则和报警规则等方面，都是采用预先定义的规则库，自适应性较差，该数据挖掘系统针对此而提出，另外该系统应用于关键业务应用领域里，通常产生的审计数据都比较完整、可靠和高质量，这使得数据源的预处理比较简易。
系统中数据挖掘源数据为业务数据库，分析器可以完成特定的分析功能，可看作是对源数据必要的预处理，分析器通常归类特定数据，提取重点数据，使数据挖掘数据选择更有针对性。分析器一般提供以下几种类型的分析：数据值范围、大小和长度分析；审计事件发生的频率分析；事件发生的地点和属主分析(比如数据生成点和作案地点)；事件发生的时间段和时间点分析。根据各个分析器功能，可分为通用、频率、阈值和时间分析器等。
2.2 异常检测设计
异常检测关键在于正常模式的建立及利用该模式对当前行为进行比较和判断。正常模式的建立可以通过关联规则挖掘实现，比如在对用户行为的异常检测，可以对用户审计数据进行关联模式的挖掘，在规则库中建立每个用户的历史行为模式，再利用该历史行为模式与当前用户操作行为进行模式比较，通过两者的相异程度来判断用户行为是否为异常行为，并通过检测过程进行模式学习，更新模式库中用户模式。模式库的更新通过待学习知识库经过交互完成。结合上述各种分析器，该异常检测流程如图2所示。
3 异常检测实现原理
3.1 关联模式挖掘
异常检测的前提是正常行为的关联模式的获取，这一步通过关联分析完成。关联分析主要任务是挖掘关联模式知识，目前关联模式挖掘算法的研究已取得了很多研究成果，众多算法中以Agrawal等人提出的Apriori[7]算法最为著名，其后的算法大多数建立在Apriori算法基础上，或进行改进，或衍生变种。本模型采用了Apriori算法。算法分为两个步骤：第一步，从事务数据库或安全审计数据库D中找出所有支持度不小于用户指定的最小支持度闭值(min_sup)的频繁项目集；第二步，使用频繁项目集产生所期望的关联模式，产生关联模式的基本原则是其置信度必须不小于用户指定的最小置信度闭值(min_conf)。
由于第二步较为容易和直观，因此挖掘出所有频繁项目集是该算法的核心，占据整个计算量的大部分，因此，有时仅考虑挖掘频繁项目集。
3.2 异常检测设计
系统通过根据审计数据各属性重要性的次序定义用户行为关联模式AMi的集合，并为每个模式进行编码，同时对当前待分析用户操作行为模式AM进行相应的编码，再通过定义一个相异度函数计算每个AMi和AM的相异度，相异度函数是通过对AMi和AM相应的编码来进行计算的。如果任意AMi和AM的相异度值都大于某一个阈值 ，则认为AM行为可能是异常行为，下面详细描述该设计过程。
3.2.1 行为模式
定义行为模式AM=(AM1=v1,AM2=v2,…,AMk=vk)，AMi(i=1,2,…k)为待挖掘审计事件的记录表中的某一属性。如果k=n-1(n为记录表的属性数)，则称AM是完备模式。如果AM的属性是按其重要性降序排列的，则称模式AM是有序模式。同时满足上述两条件的模式称为有序完备模式。显然，对于模式库中的任意模式AM=(AM1=v1,AM2=v2,…,AMk=vk)，AMi(i=1,2,…k)，均可以通过以下两步将其转换成有序完备模式：1）对于任何不属于AM的属性Ai(i=1,2,…n-1),令Ai=null，并将其插入到AM中；2）将AM的属性按其重要性降序列排列。因此，在以下的讨论中可以仅考虑有序完备模式。
3.2.2 模式编码
每个用户模式相应的编码过程如下：
设定v_seti存放属性Ai值的集合，v_propi存放v_seti中每个Ai值的在数据库中的比例值，即包含该Ai值的记录数与所有记录数的比值，该值表达了该Ai值在表中出现的频繁度，这样v_seti中每个值根据其对应的比例值由大到小排放，每个v_seti对应一个c_seti，记录v_seti中元素的个数。v_seti的初始值由初始的关联模式的值决定。
用户模式AMi每个属性值vj都对应一个编码vj_code，AMi对应的编码值通过AMi中每个属性值vj求得，vj_code计算过程如下：
1）若vj=0，则vj_code=0；
2）判断vj是否在对应的v_setj中，如果在，则计算vj对应的编码值，设vj在v_setj的顺序为sj，则对应vj的编码值计算过程如下：
3）若vj不在v_setj中，则判断vj值在在数据库中的比例值p_vj是否大于某个比例值MinProp，若p_vj小于MinProp，则vj=9；若p_vj大于则将vvj根据p_vj在v_propi的顺序加入到v_setj相应的位置中，同时根据公式(1)计算vj对应的编码值vj_code。
这样每个属性值对应的编码值为[0,9]内的整数值，模式AMi对应的编码值由v1_code、v2_code … vn-1_code组成。(n为记录表表属性数)
3.2.3 相异度函数
相异度函数可以是满足如下条件的任意函数：当给定一组对象时，如果对象间相似，返回值就较小；对象间的相异度越大，函数返回值就越大。可能的相异度函数有集合中对象的方差，或者模式字符串的形式(例如包含通配符)，根据审计表中各个属性的重要性定义相异度函数为：
该函数计算的相异度由模式编码各位的编码值的差值和属性个数决定，取值范围为[0,1]，该函数对两类数据非常敏感，(1)编码值的差值比较大；(2)存在差值的编码在模式中对应的属性的重要性比较大。
4 数据分析
4.1 审计数据
下面通过审计端审计人员的操作行为数据描述关联模式的挖掘过程，首先通过审计数据库中审计员操作记录表来约定待挖掘审计事件的记录表的定义，如表1所示，该表中每个属性都是根据其在审计事件重要性降序排列的，表2对各个属性进行了描述。
其中A2（操作类型）取值为1/2/3/4/5/6/7，分别代表：1查看终端录像，2修改或删除终端信息，3修改或删除主机信息，4新增、修改或删除控制码信息，5新增、修改或删除用户信息，6授权、修改或删除某用户权限，7其他操作。
为了使实验数据具有代表性，随机地从数据库中抽取两个用户的审计记录，数据如表3，并使用算法Apriori分别对这二个用户的行为模式进行了挖掘，部分挖掘结果如表3所示。
4.2 关联模式数据
4.3 异常检测数据及分析结论
通过表3中User1的操作行为记录，以及User1的关联模式，设定MinProp=0.01，计算User1用户模式的编码值，如表4所示。
其中：v_set1=(172.16.15.5)，v_prop1=(99.900%)，c_set1=1；
v_set2=(1,2)，v_prop2=(91.000%,8.400%)，c_set2=2；
v_set3=(Check,Modify)，v_prop3=(91.000%,8.100%)，c_set3=2；
v_set4=(002)，v_prop4=(99.900%)，c_set4=1；
v_set5=(012, 011)，v_prop5=(51.100%,48.700%)，c_set5=2；
v_set6=(am,pm,after)，v_prop6=(44.600%,40.400%,10.900%)，c_set6=3。
设定阈值?着=0.2，下面给出两个当前行为模式判断该行为是否为异常行为。表5给出了比较情况及异常分析的结论。
5 结束语
本文在一个安全审计的数据挖掘系统的基础上实现了异常检测模型的构建过程，同时通过审计数据的分析来描述模型工作的过程。针对关键业务领域审计数据特征，异常检测可以用于多种规则的挖掘，比如用户操作行为顺序规则、本地用户非法提升权限规则和远程用户获取本地权限规则等。目前该模型已成功应用在几个关键业务领域的监控系统和入侵检测系统中。
参考文献：
[1] Hawkins D. Identification of Outliers[M]. Chapman and Hall, London, 1980.
[2] Knorr E M, Ng E T. Algorithms for Mining Distance-based Outliers in Large Datasets[A]. In:24th Int. Conf. on Very Large Data Bases[C]. New York, NY, 1998: 392-403.
[3] Ramaswamy S, Rastogi R, Shim K. Efficient Algorithms for Mining Outliers from Large Data Sets[A]. In:ACM SIGMOD Conference Proceedings[C], 2000.
[4] Agrawal R, Ragaran P. A Linear Method for Deviation Detection in Large Databases[A]. In:KDD Conference Proceedings[C], 1995.
[5] Breunig M M, Kriegel H P, Ngetal R. LOF:Identifying Density-Based Local Outliers[A]. In: Proc of ACM SIGMOD Conference Proceedings[C], 2000.
[6] Aggarwal C C, Yu P. Outlier Detection for Hight Dimensional Data[A]. In:Proc of ACM SIGMOD Conference Proceedings[C], 2001.
[7] Agrawal R, Srikant R. Mining Association Rules Between sets of Items in Large Databases,[A] In: Proc of ACM SIGMOD International Conference Management of Date[C], Washington DC,1993,207-216.
[8] 李炎,李皓,钱肖鲁,等.异常检测算法分析[J]. 计算机工程,2002,28(6):5-6,32.
[9] HAN Jia-wei, Kambr M,著,范明,孟小峰,译.数据挖掘概念与技术[M].北京:机械工业出版社,2004:152-158,251-257.
关键词：安全审计；数据挖掘；异常检测；关联分析；关键业务
中图分类号：TP311.131文献标识码：A 文章编号：1009-3044(2008)23-950-04
Design on Outlier Detection Model Based on Security Audit
Shi Hai-feng
(College of Software, Nanjing College of Information Technology, Nanjing 210046, China)
Abstract: From one data mining systerm on the security audit, this paper presents one outlier detection model, the model picks up the association patterns of the normal action by association analysis, defines every action pattern by the essentiality of the properties, and codes the patterns, then uses a dissimilarity-function getting the dissimilarity between one association pattern and current pattern, and estimate the current pattern by dissimilarity, last describes the working process of the model by given audit data. The model has be applied successfully in some monitor and intrusion detection systems of the key operation domain.
Key words: security audit; data mine; outlier detection; association analysis; key operation
1 引言
目前安全审计已越来越多地成为防火墙、入侵检测和网络监控等系统支持的功能特性，特别当这些系统应用在关键业务领域（如银行，证券等）中时。安全审计的一个重要目的是发现系统或用户行为中的入侵或异常。而如何在大量的审计数据中提取出具有共性的系统特征模式，用于对程序或用户行为作出全面、准确的描述，是实现安全审系统的关键。作为数据挖掘的一个重要部分，异常检测可以从大量冗余信息的数据中提取出隐藏的、有效的模式，如果将其应用于安全审计数据的处理，可以有效地解决海量审计数据的分析问题，为系统和用户行为的判定提供依据。
异常是在数据集中与众不同的数据，使人怀疑这些数据并非随机偏差，而是产生于完全不同的机制[1]。异常检测中对异常的定义是：异常是既不属于聚类也不属于背景噪声的点，他们的行为与正常的行为有很大不同。异常检测通常建立在聚类分析和关联分析的基础上，从方法上可以分为基于统计（statistical-based）、基于距离 (distance-based) [2,3]、基于偏离(deviation-based) [4]和基于密度(density-based) [5]的方法。另外针对异常在高维空间中难以确定，有人提出一个高维数据异常检测的方法[6]，该方法采用遗传优化算法，把高维数据集映射到低维子空间，根据子空间映射数据的稀疏程度来确定异常数据是否存在，算法获得良好的计算性能。
本文提出一个基于安全审计的异常检测模型，该模型中异常检测方法借鉴基于偏离的算法，将该算法中未知的“序列异常”中各个子集间的相异度计算转化为已知的正常行为模式和未知行为模式的相异度计算，算法为每个判定对象定义一个行为模式，模式中各属性按其重要性降序排列，并利用模式中字段值在审计数据库中的信息，对每个模式进行编码，再通过定义一个相异度函数来计算模式间的相异度，根据相异度和设定阈值的比较来判断模式是否为异常。
下面首先介绍在一个基于安全审计的数据挖掘系统中构建异常检测模型的构建过程，并详细分析该模型的工作过程，最后通过一个特定的审计数据来描述异常检测的处理过程。
2 异常检测模型设计
2.1 数据挖掘系统框架
本模型是基于一个安全审计的数据挖掘系统的基础上实现，该系统结构图如图1所示。由于传统的安全审计系统在数据采集规则和报警规则等方面，都是采用预先定义的规则库，自适应性较差，该数据挖掘系统针对此而提出，另外该系统应用于关键业务应用领域里，通常产生的审计数据都比较完整、可靠和高质量，这使得数据源的预处理比较简易。
系统中数据挖掘源数据为业务数据库，分析器可以完成特定的分析功能，可看作是对源数据必要的预处理，分析器通常归类特定数据，提取重点数据，使数据挖掘数据选择更有针对性。分析器一般提供以下几种类型的分析：数据值范围、大小和长度分析；审计事件发生的频率分析；事件发生的地点和属主分析(比如数据生成点和作案地点)；事件发生的时间段和时间点分析。根据各个分析器功能，可分为通用、频率、阈值和时间分析器等。
2.2 异常检测设计
异常检测关键在于正常模式的建立及利用该模式对当前行为进行比较和判断。正常模式的建立可以通过关联规则挖掘实现，比如在对用户行为的异常检测，可以对用户审计数据进行关联模式的挖掘，在规则库中建立每个用户的历史行为模式，再利用该历史行为模式与当前用户操作行为进行模式比较，通过两者的相异程度来判断用户行为是否为异常行为，并通过检测过程进行模式学习，更新模式库中用户模式。模式库的更新通过待学习知识库经过交互完成。结合上述各种分析器，该异常检测流程如图2所示。
3 异常检测实现原理
3.1 关联模式挖掘
异常检测的前提是正常行为的关联模式的获取，这一步通过关联分析完成。关联分析主要任务是挖掘关联模式知识，目前关联模式挖掘算法的研究已取得了很多研究成果，众多算法中以Agrawal等人提出的Apriori[7]算法最为著名，其后的算法大多数建立在Apriori算法基础上，或进行改进，或衍生变种。本模型采用了Apriori算法。算法分为两个步骤：第一步，从事务数据库或安全审计数据库D中找出所有支持度不小于用户指定的最小支持度闭值(min_sup)的频繁项目集；第二步，使用频繁项目集产生所期望的关联模式，产生关联模式的基本原则是其置信度必须不小于用户指定的最小置信度闭值(min_conf)。
由于第二步较为容易和直观，因此挖掘出所有频繁项目集是该算法的核心，占据整个计算量的大部分，因此，有时仅考虑挖掘频繁项目集。
3.2 异常检测设计
系统通过根据审计数据各属性重要性的次序定义用户行为关联模式AMi的集合，并为每个模式进行编码，同时对当前待分析用户操作行为模式AM进行相应的编码，再通过定义一个相异度函数计算每个AMi和AM的相异度，相异度函数是通过对AMi和AM相应的编码来进行计算的。如果任意AMi和AM的相异度值都大于某一个阈值 ，则认为AM行为可能是异常行为，下面详细描述该设计过程。
3.2.1 行为模式
定义行为模式AM=(AM1=v1,AM2=v2,…,AMk=vk)，AMi(i=1,2,…k)为待挖掘审计事件的记录表中的某一属性。如果k=n-1(n为记录表的属性数)，则称AM是完备模式。如果AM的属性是按其重要性降序排列的，则称模式AM是有序模式。同时满足上述两条件的模式称为有序完备模式。显然，对于模式库中的任意模式AM=(AM1=v1,AM2=v2,…,AMk=vk)，AMi(i=1,2,…k)，均可以通过以下两步将其转换成有序完备模式：1）对于任何不属于AM的属性Ai(i=1,2,…n-1),令Ai=null，并将其插入到AM中；2）将AM的属性按其重要性降序列排列。因此，在以下的讨论中可以仅考虑有序完备模式。
3.2.2 模式编码
每个用户模式相应的编码过程如下：
设定v_seti存放属性Ai值的集合，v_propi存放v_seti中每个Ai值的在数据库中的比例值，即包含该Ai值的记录数与所有记录数的比值，该值表达了该Ai值在表中出现的频繁度，这样v_seti中每个值根据其对应的比例值由大到小排放，每个v_seti对应一个c_seti，记录v_seti中元素的个数。v_seti的初始值由初始的关联模式的值决定。
用户模式AMi每个属性值vj都对应一个编码vj_code，AMi对应的编码值通过AMi中每个属性值vj求得，vj_code计算过程如下：
1）若vj=0，则vj_code=0；
2）判断vj是否在对应的v_setj中，如果在，则计算vj对应的编码值，设vj在v_setj的顺序为sj，则对应vj的编码值计算过程如下：
3）若vj不在v_setj中，则判断vj值在在数据库中的比例值p_vj是否大于某个比例值MinProp，若p_vj小于MinProp，则vj=9；若p_vj大于则将vvj根据p_vj在v_propi的顺序加入到v_setj相应的位置中，同时根据公式(1)计算vj对应的编码值vj_code。
这样每个属性值对应的编码值为[0,9]内的整数值，模式AMi对应的编码值由v1_code、v2_code … vn-1_code组成。(n为记录表表属性数)
3.2.3 相异度函数
相异度函数可以是满足如下条件的任意函数：当给定一组对象时，如果对象间相似，返回值就较小；对象间的相异度越大，函数返回值就越大。可能的相异度函数有集合中对象的方差，或者模式字符串的形式(例如包含通配符)，根据审计表中各个属性的重要性定义相异度函数为：
该函数计算的相异度由模式编码各位的编码值的差值和属性个数决定，取值范围为[0,1]，该函数对两类数据非常敏感，(1)编码值的差值比较大；(2)存在差值的编码在模式中对应的属性的重要性比较大。
4 数据分析
4.1 审计数据
下面通过审计端审计人员的操作行为数据描述关联模式的挖掘过程，首先通过审计数据库中审计员操作记录表来约定待挖掘审计事件的记录表的定义，如表1所示，该表中每个属性都是根据其在审计事件重要性降序排列的，表2对各个属性进行了描述。
其中A2（操作类型）取值为1/2/3/4/5/6/7，分别代表：1查看终端录像，2修改或删除终端信息，3修改或删除主机信息，4新增、修改或删除控制码信息，5新增、修改或删除用户信息，6授权、修改或删除某用户权限，7其他操作。
为了使实验数据具有代表性，随机地从数据库中抽取两个用户的审计记录，数据如表3，并使用算法Apriori分别对这二个用户的行为模式进行了挖掘，部分挖掘结果如表3所示。
4.2 关联模式数据
4.3 异常检测数据及分析结论
通过表3中User1的操作行为记录，以及User1的关联模式，设定MinProp=0.01，计算User1用户模式的编码值，如表4所示。
其中：v_set1=(172.16.15.5)，v_prop1=(99.900%)，c_set1=1；
v_set2=(1,2)，v_prop2=(91.000%,8.400%)，c_set2=2；
v_set3=(Check,Modify)，v_prop3=(91.000%,8.100%)，c_set3=2；
v_set4=(002)，v_prop4=(99.900%)，c_set4=1；
v_set5=(012, 011)，v_prop5=(51.100%,48.700%)，c_set5=2；
v_set6=(am,pm,after)，v_prop6=(44.600%,40.400%,10.900%)，c_set6=3。
设定阈值?着=0.2，下面给出两个当前行为模式判断该行为是否为异常行为。表5给出了比较情况及异常分析的结论。
5 结束语
本文在一个安全审计的数据挖掘系统的基础上实现了异常检测模型的构建过程，同时通过审计数据的分析来描述模型工作的过程。针对关键业务领域审计数据特征，异常检测可以用于多种规则的挖掘，比如用户操作行为顺序规则、本地用户非法提升权限规则和远程用户获取本地权限规则等。目前该模型已成功应用在几个关键业务领域的监控系统和入侵检测系统中。
参考文献：
[1] Hawkins D. Identification of Outliers[M]. Chapman and Hall, London, 1980.
[2] Knorr E M, Ng E T. Algorithms for Mining Distance-based Outliers in Large Datasets[A]. In:24th Int. Conf. on Very Large Data Bases[C]. New York, NY, 1998: 392-403.
[3] Ramaswamy S, Rastogi R, Shim K. Efficient Algorithms for Mining Outliers from Large Data Sets[A]. In:ACM SIGMOD Conference Proceedings[C], 2000.
[4] Agrawal R, Ragaran P. A Linear Method for Deviation Detection in Large Databases[A]. In:KDD Conference Proceedings[C], 1995.
[5] Breunig M M, Kriegel H P, Ngetal R. LOF:Identifying Density-Based Local Outliers[A]. In: Proc of ACM SIGMOD Conference Proceedings[C], 2000.
[6] Aggarwal C C, Yu P. Outlier Detection for Hight Dimensional Data[A]. In:Proc of ACM SIGMOD Conference Proceedings[C], 2001.
[7] Agrawal R, Srikant R. Mining Association Rules Between sets of Items in Large Databases,[A] In: Proc of ACM SIGMOD International Conference Management of Date[C], Washington DC,1993,207-216.
[8] 李炎,李皓,钱肖鲁,等.异常检测算法分析[J]. 计算机工程,2002,28(6):5-6,32.
[9] HAN Jia-wei, Kambr M,著,范明,孟小峰,译.数据挖掘概念与技术[M].北京:机械工业出版社,2004:152-158,251-257.