基于Web资源聚类分析的异常行为检测

1、基于Web资源聚类分析的异常行为检测1谢逸,余顺争中山大学电子与通信工程系,广东广州(510275摘要:本文针对大型活动网站的入侵检测,提出一种基于隐半马尔可夫模型(HSMM的Web资源聚类方法,与传统的基于Web页面内容的聚类不同,该方法仅需要用户的HTTP 请求序列,而不需要网站和页面的相关信息;利用该模型,我们得到用户对各个Web资源子集的访问特征,我们进一步引入逻辑行为来描述这种用户访问特征,并通过分析用户的逻辑行为实现异常访问行为的检测。文章详细介绍了模型建立的理论依据和方法,推导出模型参数的估计算法,及一种快速的模型参数实时更新算法。并指出了如何把该模型应用于实际的网络环境。最后使

2、用World Cup 1998实际采集的数据验证了模型的有效性。结果表明该方法不但可以很好地实现用户行为分类,而且可以有效识别出异常的用户行为,从而起到入侵检测的作用。关键词:聚类,用户行为,异常检测,隐半马尔可夫模型中图分类号:TP31.引言随着Internet的普及,网络上共享的计算机资源成为主要的攻击目标,网络入侵数量的增加及其所带来的严重危害,使计算机安全成为人们关注的焦点。入侵检测系统(Intrusion Detection System, IDS是用于检测正在发生的攻击和试图进行攻击的计算机系统。异常入侵检测(Anomaly Intrusion Detection 是目前使用的主要

3、手段之一。它是根据用户行为与活动轮廓存在的偏离程度来判断是否发生入侵,常用的方法有神经网络、模式预测、机器学习、统计分析等1。与一般的入侵检测系统所关注的对象不同,本文主要研究大型活动网站(例如:体育比赛、重大商务/政治活动、大型文艺表演等对分布式拒绝服务(Distributed Denial-of-Service, DDoS攻击的检测。大型活动网站具有与一般网站不同的特点:第一,访问时间集中。由于活动网站的信息内容受活动时间表的影响很大,这导致它的访问量集中在某些特定的时间段,而其余时间的访问量则很低;第二,访问内容集中。在特定时段内(例如某一场比赛,与该时段中进行的活动有关的页面会被高频率

4、访问,而其它页面的访问量则较低;第三,访问峰值持续时间短。通常情况下,各种现场活动的持续时间一般都在2-3小时内,因此网站的访问峰值区不会持续很长时间。因此,总的来说,大型活动网站具有峰值时段业务量非常巨大、突发性强的特点。这些特点与DDoS的的洪水式(flooding攻击类似,因此使用一1本课题得到高等学校博士学科点专项科研基金(项目编号:20040558043资助.- 1 -般的异常检测方法2难以有效区分突发性强的、业务量大的正常流和异常攻击流,从而导致高误检率和高漏检率。而目前用于防御DDoS攻击的主要思路是基于分组的检测和过滤3。这种方法首先检测出攻击流或攻击分组,然后对这些分组实行过

5、滤,它最大的缺陷是很容易把正常的分组误判为DDoS攻击分组,从而造成正常数据的丢失。与现有的DDoS检测不同,本文从应用层出发,首先根据用户的HTTP请求对服务器上的Web资源(页面及各种可被用户请求的对象进行聚类,于是用户的一系列HTTP请求就变成是对不同Web资源子集的请求,我们进一步引入逻辑访问行为来表述用户在不同Web资源子集上的跳转关系,由于逻辑访问行为在一定程度上反映了用户的真实行为,因此可以根据用户逻辑访问行为的统计特征来进行异常检测。为此,本文将采用隐半马尔可夫模型(Hidden semi-Markov Model, HSMM4,5,6来实现Web资源聚类与描述用户逻辑访问行为

6、的随机变化过程,最终实现异常行为检测的目的。2.用户行为与Web资源聚类模型从用户进入网站到获取目的页面的这一个过程是用户在该Web服务器上的浏览过程。从用户端看,用户的浏览过程是用户根据网页上提供的链接一页一页往下浏览的过程,它主要体现在用户对页面的点击行为上;而从服务器端看,用户的这个浏览过程是通过一系列的HTTP请求/响应构成的。由于一个页面通常包含多个内嵌的链接,例如:图片、广告条、背景音乐和框架页面等,因此用户的每一次浏览行为(例如:点击页面链接、前进、后退、刷新等都会触发浏览器发出一系列的HTTP请求,这些HTTP请求到达服务器后除了使目标服务器做出响应(返回对应的对象以外,其属性

7、(源地址、请求时间、请求对象等也会记录在服务器的日志文件中。因此从理论上讲,如果知道网站的页面结构,就可以通过log文件的记录分析出用户的浏览行为(点击序列,也就是说log文件中的HTTP请求记录是反映用户浏览行为的“轨迹”。但是在实际的网络环境中,一般无法从log文件中的记录精确地获取用户的访问行为。这是由于log无法区分用户点击所产生的HTTP请求和浏览器自动发出的HTTP请求,因此从log记录无法精确知道用户的点击行为;其次,网络中的各级代理(proxy、缓存(cache和用户主机本身的缓存也会对用户的HTTP请求做出响应,因此用户浏览行为触发浏览器发出的HTTP请求可能不会全部到达We

8、b服务器。也就是说即使完全相同的用户浏览(或点击行为,由于用户主机及中间各级缓存程度的不同,log记录的用户浏览器发出的HTTP请求序列会存在差异;另外,对于同时打开多个浏览器窗口的用户,其不同点击行为所产生的HTTP请求在log文件中的记录是相互交叠在一起,因此更加难以区分出用户的行为。因此,用户的真实访问行为是“隐藏”在log记录下的随机变量。为此,本文不直接研究用户真实的访问行为,而是按下述方法间接得到用户访问行为的统计特征:Web资源聚类。考虑到用户对活动网站的访问具有很强的目的性,例如:某一场足球比赛、某一个重大会议、某一特定内容。即在特定时段内,正常用户的访问总是和该时段内网站的活

9、动主题相关。按活动主题的不同,可以把服务器的Web资源分为若干子集,每一个子集内的Web资源对应一个活动主题。这样,对于某个特定的网站活动时间段,正常用- 2 - 3 -户向目的服务器发出的HTTP 请求的内容大部分将落在那些与活动主题相关的Web 资源子集上。传统的Web 页面聚类方法,通常都需要预先为每个聚类定义一个主题,然后根据Web 页面的文本内容进行数据挖掘,然后实现聚类。这种方法计算量大,不适合在线运算;而且它需要预先知道网站的主题结构并采集每一Web 页面的文本,这为实际应用带来了不便;更重要的是,由于我们最终目标是利用异常行为检测来发现网络攻击,而非研究用户感兴趣的主题是什么,

10、因此我们不需要知道网站的主题和页面的内容。所以我们根据用户的访问对服务器上的Web 资源进行分类:把正常用户的HTTP 请求序列中经常在一起出现的请求对象聚为一个Web 资源子集。 HTTP 请求序列Web Web 资源聚类图1 Web 资源聚类与HTTP 请求序列定义逻辑访问行为。Web 资源聚类后,每个Web 资源子集对应一类近似的主题,使用一个符号表示(如图1的s 1,s 2,s 3,s 4。根据Web 资源的聚类结果,用户的HTTP 请求序列可以转化为Web 资源子集符号序列(如图1的s 2s 1s 3。因此与HTTP 请求对应的Web 资源子集可以反映出用户当前的访问焦点(主题、目的

11、和兴趣特征,而用户在子集间的跳转关系则反映了该用户的访问特征的变化,进一步揭示了用户的访问行为及其变化。因此,我们可以进一步认为一个Web 资源子集对应(或等价一种典型的用户逻辑访问行为,并用对应的Web 资源子集符号表示。从物理含义上看,一个逻辑访问行为并不等价于用户的一次真实访问行为(例如用户对某个页面的点击,它可以是用户的一次点击行为,也可以是用户对某个特定主题连续几次点击行为的组合;从内容上看,一个逻辑访问行为既代表一类近似的用户访问行为也代表与某一个主题相关的Web 资源的集合(Web 资源子集,它把Web 资源聚类与用户行为联系在一起。 用户行为特征分析。通过上述处理后,我们可以把

12、用户访问网站后在log 留下的HTTP 记录整理为一个逻辑访问行为序列。通过分析用户的逻辑访问行为序列(包括逻辑访问行为的编号及其在序列中的次序,可以知道用户当前的访问主题及用户访问焦点的变化。因此,逻辑访问序列间接反映了用户真实行为的轮廓。由于分类后的Web 资源子集(逻辑行为个数远小于网站的总体Web 资源的个数,所以计算复杂度也随之降低;而且由于每一个Web 资源子集都对应一类近似的主题和用户行为,具有明确的含义,因此分析用户在Web 资源子集间的跳转关系更具有实际意义,而且比直接分析页面间的跳转关系更好地反映出用户浏览行为的变化趋势。 引入Web 资源聚类和用户逻辑访问行为是为了可以更

13、清晰、简练地提取出用户的浏览行为特征及其变化。而对用户行为特征的分析则可以进一步实现从正常数据流中检测异常流的目的。 由于用户对大型活动网站的访问具有很强的目的性。因此大部分用户的浏览行为的统计特征(点击速度、浏览的内容或请求对象、浏览时间、浏览过程等具有一定的相似性,因此从log文件中分析出来的不同用户的逻辑访问行为序列也应该具有一定的统计相似性。我们可以把这种统计特征看作是用户的正常的、合法的行为。对于攻击者来说,为了达到攻击的目的,就必须设法使大量的数据发向目标主机,因此,从服务器端来看,攻击者在不同逻辑访问行为上的切换频率远大于普通正常用户,这是时间间隔上的差异;另一方面,攻击者一般比

14、较难同步模拟正常用户的浏览行为,比较容易而又常见的是,攻击者随机生成一些简单的数据流来形成攻击流。即使攻击者能够选择当前用户高频访问的对象来形成攻击流,这些数据流所形成的序列的先后次序也难以模拟正常用户浏览行为的次序关系,这就使得攻击者和正常用户在请求的内容和先后次序上存在差异,这些请求上的差异最终导致攻击者的逻辑访问序列不同于正常用户。利用这些统计特征上的差异,通过与代表正常行为的HSMM模型的比较,可以从用户访问行为的角度区分出攻击流。基于上述考虑,本文选取以下两个观测量来描述用户的逻辑访问行为:(1 用户向服务器请求的对象序列;(2到达服务器的相邻HTTP请求的时间间隔。由于正常用户的访

15、问行为一般仅与其前后的访问行为有关,因此假定用户的逻辑访问行为符合马尔科夫链的特性。考虑到用户逻辑访问行为是一个被“隐藏”了的、即不能直接观测到的随机变量,以及用户每一个逻辑访问行为使服务器收到HTTP请求的个数是一个随机变量,本文使用HSMM来建立正常用户的逻辑访问行为模型。设一个用户的多个逻辑访问行为(例如点击一系列的页面可以用一个状态链来表示,一个状态代表用户的一种逻辑访问行为,不同的状态代表不同类型的逻辑访问行为,所有状态的集合表示为S=1,2,M;每一类逻辑访问行为使浏览器发出的、且到达服务器的HTTP 请求是不同的,这些HTTP请求可以看作是模型在给定状态下的观测值,对于给定的状态

16、它以一定的概率出现,其集合表示为V=1,2,K;来自于该用户的相邻HTTP请求之间的时间间隔是给定状态下的另一个独立随机变量,它可以看作是模型在给定状态下的另一个观测值,为了分析方便并考虑到实际的Web服务器都是以秒为单位记录HTTP请求到达的时间,我们将时间间隔离散为整数,并将其集合表示为I=1,2,;对于用户的某一逻辑访问行为,服务器能够收到的HTTP请求的个数是另外一个随机变量,它可以认为是模型在给定状态下,输出的观测值的个数,其集合表示为1,2,D。把用户发出的HTTP请求序列表示为O=(r1,1, (r2,2, (r T,T,其中r tV表示用户向Web服务器请求的对象,tI表示服务

17、器收到HTTP请求r t与r t-1之间的时间间隔,O是模型的二维观测值序列。用B=b m(v,q表示模型的输出概率矩阵,b m(v,q表示在mS状态所对应的逻辑访问行为下Web服务器收到请求r t=v且与前一个到达请求之间的时间间隔为t=q的概率,其中vV,qI,且满足v,q b m(v,q=1。用P=p m(d表示在给定状态m下模型输出观测值个数为d1,2,D的概率,它代表在mS状态所对应的浏览行为下,由用户浏览器发出的、且到达服务器的HTTP请求的个数,且满足d p m(d=1,即,P相当于HSMM模型中的状态停留时间概率矩阵。用=i表示模型初始状态的概率向量,i表示初始状态为iS的概率

18、。用A=a mn表示模型的状态转移概率矩阵,a mn表示从状态mS转移到nS的概率,也即用户从与状态m对应的逻辑访问行为跳转到与状态n对应的另一逻辑访问行为的概率。- 4 - 5 - 图2 模型系统框图模型的建立与实测方法见图2所示。首先采集用户HTTP 请求数据作为模型的观测序列,经过预处理后形成模型的训练序列对模型进行训练(即Web 资源聚类;模型参数确定后可以用于实测,实测数据通过预处理后进入模型,并输出平均对数或然概率及用户的逻辑访问序列(状态序列;在正常度判决模块中比较当前数据与模型训练数据的平均对数或然概率从而得到该用户行为的正常度值,如果该用户的正常度处于正常范围,则用户数据将被

19、加入到训练数据集中,否则将交给后续模块处理。通过改进7中的算法,该模型还可以快速地实时更新模型参数。考虑到在二维观测值序列中r t 和t 相互独立,即:(,|Pr,|Pr,|,Pr,(q b v b m s q m s v r m s q v r q v b m m t t t t t t t m =(1其中,(P B A =为HSMM 模型参数,S m I q V v 且满足v b m (v =1和q b m (q =1。 通过对5的前向-反向(forward-backward算法做少量扩展,可以得到多观测序列下模型的参数重估算法。用o t 代表模型的第t 个观测向量,它包括第t 个请求对象

20、r t 和r t 与r t -1之间的时间间隔t ,即o t =(r t ,t 。b ao 代表从第a 个到第b 个观测向量序列,T o 1则代表整个观测向量序列,其长度为T 。s t 代表模型在t 时刻所处的状态;t 代表当前状态还将输出观测值的个数,1t T 。L 代表观测序列的个数。首先,分别定义前后向变量为:|,Pr,(1=d m s o d m t t t t (2,|Pr,(1=+d m s o d m t t T t t (3进一步可以得到t (m ,d 和t (m ,d 的递推公式:前向过程(Forward procedure :(,(1d p b r b d p o b d

21、m m t m t m m m t m m =(4(1,(1,(,(11d p b r b a n b r b d m d m m t m t m m n nm t t m t m t t += ,.,2,1,.2,1,T t D d S n m = (5后向过程(Backward procedure: 1,(=d m T (6- 6 -+=mn d t n t n t n mn t d n d p b r b a m 1111,(1,(71,1,(,(111>=+d d m b r b d m t t m t m t , ,.,2,1,.2,1,T t D d S n m =(8(1

22、或然概率计算L l d m o dm l T lT l ,.,2,1,(|Pr,(1=(9本文使用平均的对数或然概率l T T o l |Prlog 1,l=1,2,L (即熵作为观测序列l 与模型符合程度的度量。(2 状态序列估计 定义,|Pr(1(=l t T t l o m s m ,(10其中1t T l , m S, l=1,2,L则第l 个观测序列在t 时的状态可以按如下方法估计:(max arg (m s l t Sm l t=, 1t T l , l=1,2,L , (11(3 输出概率在多观测序列下b m (v 和b m (q 的最大或然概率估计:=Ll T t l L l

23、T vr t l mltlt t m m v b 11(1:(12=Ll T t l Ll T qt l mltlt tm m q b 11(1:(13其中m S , v V , q I ,(4状态转移概率: 定义:=1(11(,(1,(,Pr,(1d l n t n t n mn l t t T l d n d p b r b a m n s m s o n m tt l t (14其中m ,n S, l=1,2,L , t =1,2,T 可以得到多观测序列下:=L l T t Mn l L l T t l mn l tl t n m n m a1111(111(,(,(15(5 状态驻留时

24、间概率 定义:,(1,(,Pr,(11(1d m d p b r b a n d m s m s o d m l m t m t m m n nm l t t t T l tt lt =, m S, d 1,2,D , l =1,2,L , t =1,2,T(16由此可得:- 7 -=L l T t Dd l L l T t l m l tl t d m d m d p1111(111(,(,(,其中i S ,d 1,2,D ,l=1,2,L(17(6 初始状态概率估计=L l Mm l Ll l m m m 11(1(11,m S ,(18考虑到在Web 访问中,用户的访问焦点一般会随着时间

25、的变化而变化,如果用于描述Web 访问行为的模型不能自适应地随之变化,则模型会逐渐失效,并把一些新的、正常的Web 访问行为误判为异常,从而导致错误的结论。因此在实际应用中应该尽量避免这种情况出现。7介绍了一种基于HMM 的算法可以用于实时更新模型参数。本文在上述多观测序列HSMM 模型参数重估的基础上,通过对该算法的扩展,可以得到一种实时更新HSMM 模型参数的快速算法,具体如下:设(,(,(d p v b a Lm k L m L m L mn L =是有L 个观测序列的HSMM 的模型参数;(,(,(d p v b a l m k l m l m l mn l =是第l 个观测序列单独训

26、练的模型的参数,使用上述多观测序列HSMM 模型的参数重估方法,可以得到:1(1111111111111(11111(11,(1,(,(,(,(,(,|,|,+=+=+=+=+=+=+=L ijL l L ij L l L l L l L l L l T t jT l j t i t L l T t T l j t i t L ijal i states L i states a l i states l i states l i states l j i trans o s q s q p o s q s q p a l lll (19其中i ,j S , l =1,2,L 。trans (

27、i ,j ,l表示在第l 个观测序列中,从状态i 跳转到状态j 的频数;states (i ,l是第l 个观测序列中,从状态i 出现的频数。由上式可以得到1+L ij a 近似等于Lij a 和1(+L ij a 的线性组合。按照类似的方法,我们可以得到其它参数的近似估计:(,(1,(,(,(1(1111k L i l k L i l Ll k L i v b l i states L i states v b l i states l i states v b +=+ (20(,(,(,(,(1(1111111111d p l i q i q turnin l i q i q turnin

28、d p l i q i q turnin l i q i q turnin d p L i L l t t t t L i L l t t Ll t t L i +=+=+=+=, (21其中i S ,d 1,2,D ,l =1,2,L ;turning (q t -1i ,q t =i ,l 表示在第l 个观测序列中,从其它状态跳转到i 状态的频数。(1(11(1(+L i L i L i L L L L ,i S ,(22由(16、(17、(18和(19得到:在系数给定的前提下,L +1可以由L 和 (L +1估计获得。另外,注意到上述四式中的系数仅与状态i 出现的频数(即: =Ll l

29、i states 1,(, i =1,2,M 及由其它状态跳转到状态i 的频数(即: =Ll t t l i q i q turnin 11,(, i =1,2,M 有关。因此,我们只需要计算出=Ll l i states 1,( 和=Ll t t l i q i q turnin 11,(的值,就可以获得所有的系数并实现HSMM 模型参数的更新。由于这种参数估计算法的复杂度远低于对整个模型重新进行参数估计,因此适合用于在线计算。但是,由于上述算法是不断根据新的观测数据来实现动态的模型参数更新,如果不加判- 8 -断地利用所有进入服务器的Web 访问序列和上述算法来更新模型参数,则很容易使模型

30、逐渐被一些恶意的攻击者所训练,从而丧失异常检测的能力。为此,在我们的模型系统框图中(图2,采用如下方法进行处理:对于一个新的观测序列(记为L +1,首先通过L 来判断它的正常度,如果正常度处于正常范围内,则可以使用上述算法估计出模型新的参数L +1;否则就交给异常处理模块进行处理。这样,可以避免模型被攻击者所训练。3. 模型的应用上述模型可以在真实网络环境下应用,具体的使用步骤如下:(1 建立模型A. 选择一组(L 个用户的HTTP 请求序列作为模型的训练数据TD 。B. 对数据进行预处理,形成L 个二维观测序列L l r r r O l T l T l l l l l l l ,.,2,1,

31、(,(,(2(2(1(1(=L C. 初始化模型参数集合。D. 根据(4、(5分别计算前后向变量,(d m l t 和,(d m l t ,l =1,2,L 。E. 由(7、(11、(13分别计算(m l t 、,(n m l t 和,(n m l t ,l =1,2,L 。F. 由(9、(10、(12、(14和(15分别估计出模型的各个参数G. 重复DF ,直到模型的平均对数或然概率收敛到预定的区间。 (2 实测用户序列模型参数确定后可应用于实际用户的HTTP 请求序列的统计异常检测,即计算各个请求序列对于给定模型的或然概率:A. 当收到第l 个用户t 时刻发来的Web 请求时,记录下r t

32、 ,并计算出t 。B. 通过前向算法,利用,(,(,(2(2(1(1(l t l t l l l l l r r r O L =可以得到,(d m l t ,由,(d m l t 及(6可以算出该用户在1, t 区间内对应于该模型的平均对数或然概率。C. 模型实时更新。D. 重复A 、B 和C 。 (3 正常度判断本文以训练数据集内的所有序列的平均对数或然概率的均值lkh 作为正常行为的参考点。当某个用户l 的HTTP 请求序列达到一定长度时,可得到该用户的平均对数或然概率lkh (l。通过比较lkh (l和lkh ,可以得到该用户相对于训练数据的正常度。差值越小的,正常度越高,优先权也越高;

33、差值越大的,正常度越低,优先权也越低。依据正常度,可以将该用户的后续Web 请求送入相应的队列进行排队服务。最低优先权的Web 请求分组,在网络资源不够时,将被过滤掉。由此达到保护正常Web 请求和化解攻击流的目的。(4 逻辑访问序列给定模型的状态数与模型最大停留次数,模型根据训练数据集对访问行为分类。分类的结果体现在模型的输出概率矩阵B 和状态停留时间概率矩阵P 上,用户在不同逻辑访问行为上的转换体现在状态转移概率矩阵A 上。在进行实测时,模型根据训练数据得到的模型参数计算出用户序列的逻辑访问序列(即状态序列。实际上,由于模型的状态是用户真实行为的高度抽象,可以进一步使用其它的序列分析方法(

34、例如数据挖掘分析模型输出的状态序列,从而估计出用户当前的访问主题、访问兴趣变化及访问行为特征等。由于模型的状态数远小于网站的页面数,对逻辑访问序列的挖掘分析不但计算量小,而且结果更加简单、明了。4.模型的验证本文使用World Cup 19988的实际流验证模型的有效性。我们选取了两场比赛各自前后2.5小时的用户Web访问记录作为模型验证数据。经过数据预处理与随机抽选,最终形成4组数据集:DS1、DS2、DS3和DS4。其中DS1、DS2和DS3都随机(不重叠选自一场比赛,DS1和DS2是小流量用户,DS3是大流量用户。DS1用于模型的训练,DS2和DS3用于测试。DS4是选自另外一场比赛的用户,用于模型测试。 (a (b (c (d图3 Web用户行为分类由于World Cup 1998是一个体育网站,用户访问的特点受赛事的时间表影响大。不同比赛期间,用户关注的焦点对象也不同,即用户的浏览行为也不同。由前文可知,HSMM 的状态跳转可以近似模拟用户的逻辑访问行为的变化,为此,我们通过分析各个数据集中各个状态的分布情况,可以了解用户的行为特点。对一个采用10状态、最大停留时间为10的HSM