利用改进的MajorClust算法实现异常用户行为定位
2019-12-04罗文华
罗文华,张 艳
(中国刑事警察学院 网络犯罪侦查系,沈阳 110035)
1 引 言
检测数据集中的异常是一项至关重要的任务,在安全、财务、司法等领域具有高影响力的应用.传统入侵行为检测的目的在于及时发现网络或系统中存在的违反安全策略的行为和被攻击的迹象,以便积极主动地进行安全防护.基于此类目的的入侵检测技术更加侧重于实践通用性,强调利用模式特征通过统计分析、数据挖掘、机器学习等方法予以实现[1],通常并不针对特定类型的主机及网络日志进行深入剖析.信息技术的飞速发展催生了层出不穷的新型犯罪,随着涉网犯罪案件的逐年增多,很多情况下需要将行为痕迹转化为电子证据.传统检测技术难以在发现入侵迹象的同时,精准定位嫌疑人的犯罪行为,无法完整重现犯罪过程并构建证据链条,在日渐增多的司法应用需求面前显得力不从心.因此,将数据集的内容特征与语义情境纳入证据考量范畴就显得尤为必要.
聚类分析是常用的异常检测方法,其实质是把整体数据集按照特定规则划分为若干数据子集,划分于同一子集中的数据拥有更多的相似性.以典型聚类算法K-Means为例,该算法首先会选定k作为最终确定的簇数目,先是随机生成K个簇并选定各簇中心,之后将节点分配给离其最“近”的簇中心,通过迭代完善簇中心及簇中的节点,最终实现理想的分类效果.该算法的优势在于实现简单,并在处理大规模数据时展现出较高效率,成为目前应用最为广泛的聚类算法之一[2].但也存在诸多缺陷,如K值需事先给定,但实践中却难以估计.另外,中心的选择是随机的,处理结果可能每次并不完全相同,确定最佳处理结果由此成为难题.K-Means过于注重针对节点进行考虑,却忽略了对图形自身属性(如权重与规模)的考量,特别是在不同类别间不存在确切边界的情况下,K-Means之类的算法无法取得理想的聚类效果.
MajorClust是1999年由Benno Stein与Oliver Niggemann发明的基于密度的聚类算法[3],目前已发展成为无监督文档聚类中最有前途和最成功的算法之一.MajorClust能够自动地对数据进行分类,不必像K-Means算法那样事先给定簇的数目,而是通过计算簇间节点的联结度,进而改变簇的形状以提升聚类效率.该算法根据“最大吸引制胜”原则,以边权重为量度将节点迭代传到簇中.首先初始集中的每个点会被分配到其原始所属的簇中;在重新标记步骤中,在其“邻居的加权和最大值”范围内的节点使用相同的簇标签;如果存在多个满足条件的簇,则随机选择其中一个;直到没有节点再需要改变其簇成员资格,算法结束.其在聚类推导过程中,由于只考虑节点的邻居,从而拥有了良好的运行时效率.
MajorClust也并非十全十美,由于其总是忽略诸如连通性之类的全局准则,因此并不能保证总是找到最优解.特别是应用于行为证据发现时,单次MajorClust的处理结果显得较为粗糙,对于异常行为抽象出的规律不够明显,也无法快速准确定位核心关键节点.但MajorClust侧重于对图形自身属性进行考量的特性却为进行行为检测提供了崭新的思路.为此特意对原有的MajorClust算法进行了改进,实验结果表明改进后的算法不仅能够检测数据对象中是否有异常行为的存在,同时还可以实现关键异常点的准确定位,从而满足更为深入具体的司法取证需求.
Hudan Studiawan、Christian Payne等人改进了Majorcluter[4]:通过使用改进的Marjorcluter来实现聚类,并对聚类结果中的每个簇计算异常参数,引入阈值来检测异常,但在判断入侵行为存在的同时却无法实现关键行为信息的定位.
本文对Marjorcluter算法进行了进一步改进,着重强调了如何在异常检测的同时实现异常行为的定位.本文按如下结构进行组织,除“引言”部分外,在第1节将介绍基于取证需求的数据集处理方法与注意事项,并说明了数据节点相似度计算的具体步骤;第2节重点说明改进MajorClust算法的原因与具体方法;第3节描述如何通过阈值的设定进行异常行为的检测;第4节依靠找寻簇中心点实现核心证据的定位;第5节总结了本文的主要工作,并提出了未来研究的方向.
2 数据集预处理与相似度计算
与传统行为检测强调功能通用性不同[5],司法取证强调的是对象针对性,需要结合具体的格式、内容甚至语义特征才能挖掘出真正有价值的信息.数据集的深入分析有助于提升聚类乃至异常入侵检测的准确性,以Linux操作系统环境下的用户认证日志auth.log1SecRepo.com: Security Data Samples Repository. URL:http://www.secrepo.com/.为例,其通常包含有日期(date)、时间(time)、进程名称(process name)与ID(PID)、主机名称(hostname)以及具体的事件(event)信息,异常入侵行为会在其中(特别是事件信息)表现出较强的特征.表1描述了当非法用户尝试越权登陆系统时其操作可能表现出的行为特征.
从表1可以看出事件信息会对行为予以充分描述,提供了更为充分的线索帮助在海量信息中进行行为检测.同时因为事件信息中有的已经包含了日期、事件、用户名等,因此考虑将数据集中每条记录作为节点[6],并以节点中的事件内容作为聚类主要依据,进而实现异常行为检测.
表1 auth.log中的异常行为特征
Table 1 Abnormal behavior characteristics in auth.log
特点说明事件信息示例用户操作通常具有关联性与顺序性嫌疑人尝试用户认证,系统会记录连接失败Invaliduserxxxfromxxxinput_userauth_request:invaliduserxxxReceiveddisconnectfromxxx:ByeBye用户操作多次重复且时间连续嫌疑人会尝试通过不同的用户登录系统Dec2302:41:39ip-172-31-27-153sshd[7463]:InvaliduserPlcmSpIpfrom218.77.121.69Dec2302:41:48ip-172-31-27-153sshd[7465]:Invaliduservyattafrom218.77.121.69Dec2302:41:51ip-172-31-27-153sshd[7467]:Invaliduserubntfrom218.77.121.69服务器与用户产生交互用户多次无效登陆,服务器会反向检查地址信息Invaliduserftpuserfrom211.72.198.126reversemappingcheckinggetaddrinfofor211-72-198-126.hinet-ip.hinet.net[211.72.198.126]failed-POSSIBLEBREAK-INATTEMPT!
传统方式在预处理时会把字符串中出现的常见词作为停用词(Stopword)去掉.实验发现,基于MajorClust算法的聚类分析[7]受停用词的影响较大,需要针对特定的日志内容选择其适合的停用词.图1所示即为处理auth.log数据集时是否将单词“from”作为停用词的处理结果比较.当“from”作为停用词时,数据集的处理结果显示只形成了一个由数目众多的节点构成的聚类(图1(a));但当“from”不作为停用词时,数据集却形成了两个类似的聚类(图1(b)),从而直接影响了后续的处理分析.因此在确定停用词时,除传统选择外,对于不能认定效果的停用词最好通过实验验证后再抉择.本文所讨论的预处理是将preauth、from、for、port、sshd、ssh、root作为停用词并连同日期、时间一并去除.日期、时间等虽然信息暂时不在聚类的考虑范畴内,但在后续的异常检测及阀值设定中会重新综合曾经被忽略的信息.
之后使用TF-IDF算法计算每个节点的数字表征.对于特定词w,其在记录r中词频被定义为该词在记录中出现的次数与该记录中所有词出现的总次数之商,即tfw,r=tf/len(r).常规的逆文档频率定义为数据集中的记录总数与微调后包含该词的记录数之商的对数,即idfw=log(N/dfw+1).此处分母之所以需要加1,目的在于规避特定词不在语料库内而出现的除数为0情况.基于收集证据与线索目的的聚类分析针对的是具体日志内容,不会出现特定词存在于语料库范围之外的情况,在此将逆文档频率计算进行简化,即idfw=log(N/dfw).分别计算完tfw,r与idfw之后,再依据公式TF-IDF=tfw,r*idfw计算每个节点的表征.
图1 停用词的不同造成处理结果的巨大差异Fig.1 Differences in stop words cause huge differences in processing results
鉴于节点事件信息中语句长度通常较短,由此采用cos相似度计算方法,依据节点表征得到节点间的相关系数[8].之后利用相关系数构造图G=
图2 依据cos相似度算法计算事件节点间的相关系数Fig.2 Calculating the correlation coefficient between event nodes based on the cos similarity algorithm
3 MajorClust算法的逐步改进
传统的MajorClust算法强调依靠权重实现节点聚合,逐次迭代筛选目标数据集中拥有最大权重和的节点,并将其与直接连接的节点形成聚类.但这种算法存在一个明显缺陷就是,拥有最大权重和的节点往往可能是因为其个别连接边的权重大,强制了其他与该节点关联并不紧密的节点被聚类于该节点,由此对异常检测的判断造成严重干扰.为此需要通过提供额外的要求来改进MajorClust算法,即当前群集与最重的邻居节点不同时,强制节点跟随最重的群集.在找寻到权重和最大的节点之后,如果存在对权重和起绝对影响的边,则将该边对应的节点单独聚类,其方程式如下:
(1)
其中s是考虑附加检查的当前簇,h是具有最大边权重的邻居节点,并且s(h)是h的簇标签,si是第i个簇,s*是具有最大权重的聚合.通过这样部署,事件将仅跟随最相似的事件,而不是跟随其他那些并不非常相似但却被强制关联的事件.
经初步改进后,节点间的关系得到进一步明确,强关联的事件被聚合成簇.但由此却引发了另一问题,即聚类后的生成的簇中节点数量过少,往往只有2到3个,很难基于这样的聚类挖掘行为模式.为此针对图形进一步凝练,将簇抽象为单一节点,节点的事件内容为原有簇中节点事件内容的最长子句.比如原有簇由三个节点组成,事件信息分别为“Invalid user admin 221.208.245.210”、“Invalid user admin 187.12.80.202”、“Invalid user admin 122.205.109.208”,则其新抽象出的节点事件信息即为“Invalid user admin”;之后再对二次生成的图形依据第1节算法做MajorClust处理,进而得到关于事件关系的新图示.抽象的同时要保留原有节点的属性信息,以便追溯使用;节点处理之后即被标记,之后便转入其他节点的处理,从而保证了在有限步骤内完成图形处理.
改进的MajorClust算法完整步骤描述如下:
输入:日志记录集L;
输出:聚类处理之后生成的若干簇;
Step 1.根据日志记录集的“事件”域进行去重,只取去重后的“事件”域生成新的记录集Ln;
Step 2.依据TF-IDF算法计算数据集Ln中每个节点的数字表征;
Step 3.根据节点的数字表征计算节点间的cos相关系数,并将相关系数作为权重赋值给节点之间的连接边;
Step 4.计算每个节点与其他节点的连接边权重之和,并筛选出拥有最大权重和的节点;
Step 5.将该节点与其最大权重边对应的节点聚类,如果存在多条边的最大权重相等,则将这些节点一同聚类;
Step 6.将已完成聚类的节点从数据集Ln中去除,针对剩余的节点循环Step4与Step5直至目标函数收敛;
Step 7.生成的每一个聚类都使用一个节点来替代,节点的内容信息为聚类中“事件”信息的“最长子串”;
Step 8.针对抽象出的节点使用TF-IDF算法其数字表征;
Step 9.根据数字表征计算节点间的cos相关系数,将相关系数作为权重赋值给节点间的连接边,生成最终的图形.
图3所示即为Security Repository数据集中2014年11月30日当天的日志记录最终处理结果.基于事件信息处理后形成了多个簇,其中节点数量最多的簇由含有“invalid user”子串的日志记录组成,含有“pam_unix(cron:session)”字样的记录构成的簇中节点数量是最少的,只有两个节点.关联度高的事件聚类之后,便可通过算法检测与阈值设定判别事件中是否存在异常.
图3 改进的MajorClust算法处理2014年11月30日当天日志记录的最终结果Fig.3 Improved MajorClust algorithm to process the final results of the log on November 30,2014
4 异常检测与阈值设定
聚类时只重点针对事件内容信息进行了考察,在确定是否存在异常时则需要将事件的时间间隔、频度纳入考量范畴.有的检测方法依靠聚类中节点的数量推断是否有异常存在[9],但这种方法能够适用的现实场景较少,并且未涉及至关重要的时间因素.异常行为事件组成的簇总是在特定方面体现出与正常行为簇的不同,传统观点认为异常簇中节点的数量一定会小于正常的簇,但实验发现并非如此.因此不能单纯依靠节点数量判断是否存在异常,节点数目过多或过少都有可能是异常行为造成的结果[10].
为更准确地进行异常检测,需要针对两次MajorClust聚类处理后生成簇的频率进行深度分析.簇中每个节点在原始数据集中的出现频度是易得的(即出现次数之和除以总记录数),将簇的频度μc定义为簇中节点频度之和与节点对应事件之和的商,这样定义的μc在一定程度上表现出该簇整体上的频度特征.鉴于μc未将时间因素纳入考量,由此定义簇的到达区间(Inter-arrival)比率Ic为簇中节点频度之和与簇的整体时间间隔(即末次事件发生时间与首次事件发生时间之差,以秒计)之商.在μc与Ic的基础上将簇的异常参数定义为:
(2)
∂′=(∂-Min∂)/(Max∂-Min∂)
(3)
依照前述计算步骤,针对Security Repository数据集中前20天的日志记录运用改进的MajorClust算法进行了处理,得到当日每个簇的异常参数值.实验发现,invalid user 、received disconnect from 以及reverse mapping checking getaddrinfo for failed-possible break-in attempt!这三类事件的异常参数大于其他事件的概率较大;connection closed和pam_unix(cron:session):session for user root这两类事件的异常参数通常很小.事实上,这也符合日常经验的认知,非法用户往往通过不断地连接与登陆尝试实现系统入侵[11].
表2 异常参数最高与次高的事件类型及具体参数值
Table 2 Highest and second highest event type and specific parameter value of the abnormal parameter
日期最高异常参数次高异常参数对应事件参数值对应事件参数值November30,2014invaliduser1.0didnotreceiveidentificationstringfrom0.039December1,2014invaliduser1.0receiveddisconnectfrom0.4283December2,2014receiveddisconnectfrom1.0invaliduser0.9587December3,2014invaliduser1.0receiveddisconnectfrom0.8825December4,2014invaliduser1.0receiveddisconnectfrom0.0057December5,2014invaliduser1.0receiveddisconnectfrom0.0077December6,2014receiveddisconnectfrom1.0invaliduser0.5649December7,2014invaliduser1.0reversemappingcheckinggetaddrinfoforfailed-possiblebreak-inattempt!0.8168December8,2014invaliduser1.0didnotreceiveidentificationstringfrom0.0872December9,2014invaliduser1.0receiveddisconnectfrom0.4172December10,2014invaliduser1.0receiveddisconnectfrom0.0350December11,2014invaliduser1.0receiveddisconnectfrom0.3191December12,2014invaliduser1.0receiveddisconnectfrom0.0939December13,2014invaliduser1.0receiveddisconnectfrom0.0563December14,2014receiveddisconnectfrom1.0reversemappingcheckinggetaddrinfoforfailed-possiblebreak-inattempt!0.2707December15,2014receiveddisconnectfrom1.0reversemappingcheckinggetaddrinfoforfailed-possiblebreak-inattempt!0.0021December16,2014invaliduser1.0receiveddisconnectfrom0.1526December17,2014reversemappingcheckinggetaddrinfoforfailed-possiblebreak-inattempt!1.0invaliduser0.2949December18,2014invaliduser1.0receiveddisconnectfrom0.0436December19,2014invaliduser1.0receiveddisconnectfrom0.1752
表2列出了20天记录中异常参数最高与次高的事件类型及其对应的异常参数(因为已对异常参数做了标准化处理,所以最高异常参数值总为1).从表2可以看出,拥有最高异常参数的事件多为“invalid user”,之后是“received disconnect from”和“reverse mapping checking getaddrinfo for failed-possible break-in attempt!”;另外,次高的异常参数变动幅度较大,从0.0021跨越到0.9587.传统异常检测只是考量单一事件的异常参数是否超过预设阈值,但事实上异常行为所催生的事件往往是相互关联的,真正有威胁的事件产生时必然会引发多个事件的.因此综合考虑多个事件的异常参数将更有利于提升检测的准确度.如果某日的次高异常参数大于0.5,则该日出现异常入侵行为的概率是极大的.
5 通过簇中心点定位关键证据
判断出存在异常行为之后,需要挖掘出重点异常事件与核心证据线索.虽然根据阈值可以推测哪个簇存在异常行为的可能[12],但异常簇往往由多个节点构成,很多情况下节点数量会超出人工分析所能承受的范围.为此需要进一步确定簇的中心点以实现快速准确定位关键证据或线索的目的[13].选择三种类型的节点作为簇中心点的备选,分别是簇中频率最高的节点、到达率最高的节点以及MajorClust算法核心处理的节点(即邻边权重之和最大的节点).在Security Repository数据集的30天记录中共出现了6次次高异常参数大于0.5的情况,表3梳理出了这6天记录形成的“invalid user”簇中三种类型节点的分布情况.
实验发现,虽然频率最高的节点与邻边权重之和最大的节点(即改进MajorClust算法核心处理节点)的计算依据完全不同,但算出的节点指向却出现了重合,由此可以把此类节点当作簇的中心点予以着重关注.在改进MajorClust算法进行处理时已经保留了邻边权重之和最大的节点信息,因此无需再另行计算频率最高的节点,即可实现关键证据的定位.
表3 三种类型节点在“invalid user”簇中的分布情况
Table 3 Distribution of three types of nodes in the "invalid user" cluster
日期频率最高达到率最高邻边权重之和最大December 2,2014input_userauth_request:invalidusertest[preauth]invalidusernagiosfrom218.25.17.234input_userauth_request:invaliduseruser[preauth]December 3,2014input_userauth_request:invaliduseradmin[preauth]input_userauth_request:invaliduseradmin[preauth]input_userauth_request:invaliduseradmin[preauth]December 6,2014input_userauth_request:invalidusertest[preauth]invalidusertestfrom61.197.203.243input_userauth_request:invalidusertest[preauth]December 7,2014input_userauth_request:invaliduseradmin[preauth]input_userauth_request:invaliduserftp_user[preauth]input_userauth_request:invaliduseradmin[preauth]December20,2014input_userauth_request:invaliduseradmin[preauth]invaliduserxbmcfrom211.25.49.250input_userauth_request:invaliduseradmin[preauth]December21,2014input_userauth_request:invaliduseradmin[preauth]input_userauth_request:invaliduserpostgres[preauth]input_userauth_request:invaliduseradmin[preauth]
表4 异常参数最高与异常参数次高簇的核心节点的信息相互印证
Table 4 Information of the cluster core node with the highest abnormal parameter and the second highest abnormal parameter is mutually confirmed
异常参数最高与异常参数次高簇的核心节点还可以实现相互印证关系,如在invalid user簇中确定出的具体用户名信息也会体现在其他簇的核心节点中,同时其他记录内容的独立性还会辅助提供IP等重要信息.具体情况如表4所示.
6 总结与展望
异常行为检测一旦涉及特定的记录内容分析挖掘,势必会增添大量的额外工作量[14],以至于目前并未得到广泛的现实应用.但本文的实验结果充分说明在面向司法应用的取证分析中,针对内容与语境的分析至关重要,有助于快速准确地定位关键证据或线索.传统步骤往往是在探测到异常行为之后,再针对可疑数据集进行深度分析,以发现核心异常点.使用改进后的MajorClust算法不仅可以判断出异常行为是否存在,并在处理过程中能够自动筛选出最核心的证据与线索,以满足司法应用需求.在关联度计算的基础上,经过两次MajorClust算法处理更精准地挖掘出了记录间的关系,综合多个簇的异常参数实现了异常行为的检测,并通过簇核心点的定位,在海量记录中挖掘出最有价值的信息.同时,本论文提出的方法并没有沿袭传统的以单一异常参数进行判定的思路,而是基于异常行为之间的关联特性连带次高异常参数予以综合判断,进一步提升了检测结果的可信度.
本论文虽然以Auth日志为处理分析对象,但所描述的方法也适用于多种操作系统环境下的其他类型日志.论文实验则主要依托自编的Python脚本实现,使用了Python自带的函数及插件功能[15].处理时间主要消耗在计算事件记录相似度、第一次MajorClust抽象、基于“最长子句”生成新节点、第二次MajorClust抽象等四个步骤.实验证明这些步骤的计算时长与数据增长呈线性关系,其中“第一次MajorClust抽象”这个环节最为耗时,在Intel Core I7-6500U及8GB RAM的硬件条件下处理10万条以上的记录消耗时间需要以小时计,未来需要进一步完善数据结构与优化算法,以提升处理效率.
