Software Engineering and Applications
Vol.05 No.02(2016), Article ID:17231,10 pages
10.12677/SEA.2016.52011

Clustering Analysis and Anomaly Detection Based on the Detour Path

Lei Liu, Peidong Zhu, Shuang Yan, Wei Fu

College of Computer Science, National University of Defense Technology, Changsha Hunan

Received: Mar. 8th, 2016; accepted: Mar. 22nd, 2016; published: Mar. 29th, 2016

Copyright © 2016 by authors and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

ABSTRACT

In this paper, the detour path is defined firstly. Through the observation of AS_PATH property of the routing table, we sum up the six forms of the detour path, i.e., continuously repeated AS, loop, around the neighbor AS, around the country, around the border and around the multinational company. Moreover, we did the clustering analysis of the manifestation of detour path and put forward the routing anomaly detection method based on the detour path. The method can detect the continuous repeated AS, routing loop, domestic traffic leaked, forged path, garbled path with such anomalies. Experiments show that the proposed method can effectively detect abnormal routing behavior and also suggest that one of the main reasons for the average shortest path of Internet traffic which becomes longer is the existence of the detour paths.

Keywords:BGP, Detour Path, Clustering Analysis, Anomaly Detection

基于绕行路径的聚类分析与异常检测

刘磊,朱培栋,闫爽,富威

国防科学技术大学计算机学院,湖南 长沙

收稿日期:2016年3月8日;录用日期:2016年3月22日;发布日期:2016年3月29日

摘 要

本文对BGP路由中的绕行路径作了定义,通过观察路由表的AS_PATH属性,总结归纳了绕行路径的六种表现形式,即连续重复AS、环路、绕邻居AS、绕国、绕境、绕跨国企业。同时,对绕行路径的表现形式进行了聚类分析,并提出了基于绕行路径的连续重复AS、路由环路、国内流量外泄、路径伪造、路径篡改等异常路由检测方法。实验表明,本文所提方法能够有效检测异常路由行为,同时揭示了绕行路径的存在是使得网络流量传递平均最短路径变长的主要原因之一。

关键词 :BGP,绕行路径,聚类分析,异常检测

1. 引言

在互联网关键基础应用迅速蓬勃发展的今天,互联网安全越来越发地成为一个被人们所关注的领域。BGP [1] 作为域间路由的实际运行协议,协调着各AS间路由可达性信息的有序交换,对于互联网的正常运行起到了至关重要的作用。然而,由于BGP协议设计之初缺乏足够多的安全机制的考虑,无法对传播的路由信息进行完整性和真实性的有效验证 [2] ,使得网络的高效运转倍受域间路由的错误配置和攻击行为所扰 [2] [3] 。例如2014年以来的Amazon的MITM事件 [4] 、加拿大ISP的前缀劫持事件 [5] 以及印度 [6] 、马来西亚 [7] 的路由泄露事件,这些安全事件都对BGP路由系统的可用性和稳定性造成了极大的影响。

目前,路由异常主要包括前缀异常和路径异常两大类。前缀异常主要是前缀劫持,是指一个 AS(Autonomous System, AS)对外通告了一个未获授权的前缀,即前缀属于其他AS所有或者该段地址空间尚未分配,AS违反授权对外通告非法的前缀将直接造成流量劫持的发生,甚至网络的瘫痪 [8] 。路径异常则主要通过对路由的AS-PTH属性进行攻击。而在这两类路由异常类型中,路径异常相比更加隐蔽,不容易检测。因此,针对路径的异常检测一直是路由安全系统的研究重难点之一。

近年来,针对路径异常的检测已经有了很多研究。如Kruegel,Mutz,Robertson等人 [9] 提出了一种基于AS拓扑结构的异常检测方法。他们将边缘AS层划分为不同的簇,认为一条合法的AS路径只能包含一个核心层AS,并且连续边缘AS应履同一个簇或两个非常相近的簇。实验验证了上述方法检测路径异常的有效性,但算法需要实时更新拓扑信息,边缘层AS的分簇也会对异常检测的结果造成很大影响。Li等人 [10] 提出了基于伙伴的路径异常检测方法,认为路径遭到攻击后,异常路径与其伙伴的相似性将破坏,此方法具有良好的鲁棒性和实时性,但伙伴的判断依据的准确性有待进一步加强,并且能始终找到足够数量的异常路径的伙伴进行验证,路径异常检测的效果不佳。上述路径异常的检测方法主要针对路径异常中的伪造路径异常进行检测分析,很少对路径异常进行做进一步的聚类研究,同时,检测处理的数据量较大,方法较为复杂。Cha等人 [11] 利用指纹来检测路径异常,该需要处理大量的数据信息,而且他们认为检测前出现在网络中的边均是合法的,并未考虑到边的动态性,使检测结果缺乏一定的准确性。针对上述问题,本文从路径绕行的角度出发,将绕行路径分为连续重复的AS、环路、绕邻居AS、绕国、绕境、绕跨国企业六种路径异常表现形式。同时,本文以AS邻接关系为基础,提出了基于绕行路径的连续重复AS、路由环路、国内流量外泄、路径伪造、路径篡改等异常现象的检测方法。实验结果表明,该方法能够有效地检测路径异常行为。

2. 绕行路径聚类分析

路径属性AS_PATH是BGP协议的公认必遵属性,它用一系列有序AS号来描述AS间的路径或NLRI(Network Layer Reachability Information)。当运行BGP协议的路由器发起或转发一条路由更新时,它便将自己的AS号附加到AS_PATH属性的最前面,而后再传递给自己的上游或对等AS。AS_PATH描述了一条从本地AS到宣告前缀AS所经过的自治系统的顺序,即去往目标前缀网络的一条路径。由于BGP协议设计之初并没有任何验证AS_PATH属性真实性的机制,致使域间路由系统及其上的AS节点极易受到路径伪造、路径篡改、国内流量外泄、路由黑洞、路由泄露、路由中间人等等攻击,造成网络的不可达、拥堵或数据的窃取、篡改,致使域间网络笼罩在各种安全威胁之下,而路径的绕行表征可能是造成上述威胁的潜在表现。

绕行路径是指从源AS到目标AS的一条AS_PATH路径本可以最短路径到达目标AS网络,而出于商业利益、流量工程考虑或攻击所致,导致实际到达目标AS网络的路径比最短路径要长的一条异常路径。通过对routeviews项目上的2015年9月27日22时的路由数据进行观察分析,绕行路径通常有以下六种表现形式:

1) 连续重复AS

在AS_PATH路径中出现连续且相同的AS,使得本应短的路径变长。一个影响是流量在重复AS内绕行,延迟流量到达时间;再一个影响是攻击者可以通过减少路径中重复AS的数量,增加攻击AS,并且使得篡改后的路径长度小于篡改前的路径,达到中间人攻击的目的 [12] 。例如:AS_PATH路径13030 852 852 53359与AS_PATH路径852 7922 33287 33560 33560 33560均在路径中的中间和末尾处出现了连续重复的AS 852和AS 33560,攻击者可以伪造一条路径852 7922 XXX 33287 33560,伪造的路径可以正常转发流量到目标网络,但其路径长度明显短于原来的路径,可被其它AS优先选取,而可能造成路由攻击。

2) 环路

在AS_PATH路径中出现重复且不连续的AS,使得路径中存在环路和本应短的路径变长。流量在几个AS间绕行,甚至造成无限绕行而无法摆脱AS的束缚,使得流量不能够到达目标网络。例如:AS_PATH路径8492 6939 2711 6167 22394 6167中,AS 6167出现两次且中间经过AS 22394,按常理流量第一次到达目标AS 6167后不应该再流出到AS 22394后回到AS 6167,环路的出现,使得AS 22394可以截获去往AS 6167的流量。

3) 绕邻居AS

在AS_PATH路径中出现本应能够直接相连接的两个邻居AS却被其它AS隔断,使得路径变长。例如:AS_PATH路径11537 10764 513 12654中,AS 11537与AS 513是相互连接的邻居,可以直接从AS 11537到达AS 513,但此路径中却被AS 10764的隔开,使得从AS 11537去往AS 513的流量流经AS 10764。

4) 绕国

在AS_PATH路径中,同一国家的AS中间出现其它国家的AS,按常理同一个国家的AS应是相互连接的,且流量应首选本国的AS进行传递后再经其它国家传递,而此类型的路径绕行可能造成国家流量外泄,致命国家层面上面临着重大威胁。例如:AS_PATH路径23673 38726 7497 11537 22388 7660 24287 24489 23911 9401中,AS 7497、AS 24489、AS 23911、AS 9401所属国家为中国,而其中间的AS 11537、AS 22388所属国家分别为美国,AS 7660、AS 24287所属国家为日本。路径片段7497 11537 22388 7660 24287 24489 23911 9401中,流量从中国(AS 7497)经由美国和日本后,又回到中国,这种行为显然是不合理的,因为从AS 7497出去的流量本应直接到达国内的其它AS而不需要经过其它国外AS。

5) 绕境

在AS_PATH路径中,在同一国家的不同境内外的AS间来回进行流量的传递。例如:AS_PATH路径3277 3267 20388 7497 4641 4641 24151中,AS 7497和AS 24151属中国大陆拥有AS,AS 4641属中国香港AS。流量从中国内陆AS 7497本应直接传递到内陆AS 24151,而不应经由境外香港AS 4641后回到内陆AS 24151。

6) 绕跨国企业

在AS_PATH路径中,在本国AS与本国跨国企业的它国的AS间进行的流量传递。例如:AS_PATH路径852 2914 4134 36678 55992中,AS 4134和AS 55992均属中国AS,AS 36678属美国所有,但AS 36678注册组织为中国电信美国分公司。

通过对上述绕行路径的表现形式的分析可以看出,路径绕行的共同特征是增加了路径的长度,使得本来短的路径变长,这其中的原因可能是基于流量工程或利益的考量,异或是攻击行为所致,因此,对于路径的绕行行为应着重对待。

3. 基于绕行路径的异常检测

绕行路径的异常检测基于AS基本信息表、AS邻接点对集、AS间商业关系等基本知识库,主要检测路径绕行中可能存在的路由环路、国内流量外泄、路径伪造(也可能是路由黑洞)、路径篡改(甚至可能是中间人攻击)等异常现象。这些异常现象的产生极有可能导致流量导向非正确网络或数据内容遭到窃取篡改。如果由于路由泄露将大量流量导向特定网络将可能会造成大规模的拒绝服务式攻击,如果由于路径伪造将流量引向伪造AS内且丢弃将可能会造成路由黑洞攻击,如果由于路径篡改将流量引入篡改AS内后再将流量转发至目标网络将造成数据被窃取或篡改,这些都将给网络和用户造成严重的影响。因此,需要一种路径异常检测的方法来有效防范或预警异常现象的发生,尽量减少路径异常所带来的损失。

3.1. 基本知识库的构建

AS基本信息主要从网络上公开的信息中获取,包括注册ISP名称、国家及城市等基本信息;AS间的邻居信息主要从routeviews.org公开的路由表中获得,将出现在AS_PATH属性中的相邻AS记作邻居关系,其具体算法如算法1所示;由于AS商业关系是ISP的商业机密,非公开的,无法从公共网络上直接获得,本文采用文献 [13] 所提的方法进行AS商业关系的推断。

3.2. 异常检测

主要对路径绕行中可能存在的路由环路、国内流量外泄、路径伪造(也可能是路由黑洞)、路径篡改(甚至可能是中间人攻击)等异常进行检测。

3.2.1. 重复AS异常的检测

重复AS的异常包括连续重复AS的异常和路由环路异常两种情况。给定路径,其中,p1至pn代表AS号。如果在P中出现两个及以上相同AS号,则为重复AS异常,进一步考虑,令,如果 =,则为连续重复AS异常,反之,则为路由环路异常。

3.2.2. 国内流量外泄异常的检测

在给的路径中,如果存在pi与pj同属一个国家C,且,令pi与pj之间的AS序列为,扫描新的序列Q,如果发现其中存在不属于国家C的AS,则路径判断为国内流量外泄异常。

Algorithm 1. AS adjacent relation extraction

算法1. AS邻居关系提取

3.2.3. 邻居绕行异常的检测

在给的路径中,如果存在P的子集序列,如果存在q1与qn具有邻居关系,即在其它的路径中存在q1与qn直接相连的情况,则有理由相信去往qn的流量可以直接从q1到达qn而不需要经过其中间的若干个AS。若出现此种情况,则判断为邻居绕行异常。

3.2.4. 路径伪造异常的检测

通常情况下,路径伪造使数据流向伪造AS内,造成数据被窃听或被丢弃,在邻居绕行异常的路径片段序列中,q1与qn是邻居关系,那么,如果序列中存在qi,且qi是邻居关系,而qi为非邻居关系,如果,流量传递到qi不再继续延着进行传递,可能造成的威胁行为是窃听数据或丢弃数据,如果大量的数据流量都转向了这类伪造的路径,使得流量不能正确的进行传递,很可能形成路由黑洞。

3.2.5. 路径篡改异常的检测

路径篡改较路径伪造而言,它不会造成数据流量的丢弃,而是通过改变路径传递方向,使流量传递到攻击者的AS内,进行流量的截获或修改,而后再将流量转发到正确的目标网络,对流量的发起方和接收方并没有产生可观察到的影响,近年来,比较凸显的路由中间人攻击就是以这种形式进行攻击的,这使得网络管理人员很难发现此类异常行为,从绕行路径的角度来看,路径的篡改或中间人攻击行为的表现形式就是在原本可直接到达的两个AS间插入了若干AS,使流量经同插入的AS后传递到目标网络,显然路径绕行具有以上行为的基本特征,如果在邻居绕行异常的路径片段序列中,q1与qn是邻居关系,那么,如果序列中存在qi均是邻居关系,即序列是一条通路,且没有违反AS间的商业关系,则判断此为路径篡改异常。

3.3. 异常检测流程

基于路径绕行的异常检测首先根据路径本身的表现形式特点检测重复AS的异常,而后依据AS所属国家信息检测国内流量外泄异常,同时,根据路由表推断出各AS的邻居关系,进而检测邻居绕行的异常,并在邻居绕行路径的基础上进行路径伪造和路径篡改异常的检测。其流程图如图1所示。

判定规则:

1) AS-PATH中出现重复的AS;

2) 非连续重复AS;

3) 邻居绕行:形如A-C-D-B路径中,存在A-B的路径且A!=B!=C;

4) 国内流量外泄:形如A-C-D-B路径中,存在A、B属于同一国家,而路径序列C-D中存在AS属于另一国家;

5) 绕行AS在AS-PATH中与其相连的AS均是邻居关系;

6) 绕行AS在AS-PATH中与其相连的上游AS是邻居关系,而与其下游AS甚少有一个是非邻居关系;

7) 违反AS间商业关系。

注:所谓绕行AS是指两个互为邻居的AS中间的AS。

4. 实验结果与分析

实验数据来自开源项目routeviews上2015年11月1日至30日,每日0点的路由更新,通过对路由数据进行基于绕行路径的部分异常检测结果如表1表4所示。

Figure 1. Flow chart of anomaly detection

图1. 异常检测流程图

Table 1. The abnormality of continuous repeated AS

表1. 连续重复AS异常

Table 2. The abnormality of forged path

表2. 路径伪造异常

Table 3. The abnormality of garbled path

表3. 路径篡改异常

Table 4. The abnormality of domestic traffic leaked

表4. 流量外泄异常

表1展示了部分连续重复AS异常的路径。如路径11537 2603 2603 2603 2603 1103 12654的第2至第5个AS均为2603,使得流量在AS2603内连续跳转4次才流出AS2603,这样的行为让始于AS11537通向AS12654的流量在网络上行走时间延长。这样的路径,多半是ISP为了本流量工程所采用的一种常见的配置策略。然而,这样的配置亦可成为路由攻击的一种手段,攻击者可能为了攻击而找到这样一条路径将其修改为11537 2603 2603XXX 1103 12654,其中,“XXX”为攻击者所在AS,这样修改后,攻击者添加了自己的AS而又使路径长度由原来7变为现在的6,根据路径选择的原则,变短后的路径将后取代原来的路径成为路由,这样攻击者便能够达到攻击的目的。

表2展示了部分路径伪造的异常路径。如路径11537 10764 6509 376,AS11537和AS6509在路由表中存在一条互为邻居的路径11537 6509 376,而中此异常路径中,二者被AS10764所分开,致使流量本应从AS11537直接流向AS6509而不需要经过AS10764,这样的异常路径称作绕行路径。此外,路径的伪造还体现在AS11537和AS10764具有邻居关系,而AS10764和AS6509并非邻居关系,也就是说AS10764没有到达AS6509的路径,因此,这样的路径是不正常的,从表象上来看,符合路径伪造的特征。

表3展示了部分的路径篡改路径。可知路径11537 10764 513 12654中,AS11537和AS513、AS10746均是邻居关系,且AS10746和AS513亦是邻居关系,这样,本可以从AS11537直接流向AS513的流量却经过了AS10746,使得流量的流转绕道了,正常情况下,这种路径是不应该出现的。可能的原因是错误的路由配置所导致,或是路径篡改的攻击的行为所致,不管是哪种都是一种路径遭到篡改的异常表现,都值得关注。

表4展示了部分的流量外泄异常的路径。如其中一条路径11537 22388 7660 9264 7497 4635 38345,AS7497和AS38345均属于中国内陆所有,而AS4635属于中国香港所有,按理说,由中国大陆AS出发的流量应该有直接到达中国大陆内目标AS的路径,而不需要经过境外到达香港后再流回境内。又如路径11686 3356 4134 36678 55992 55992,中国AS4134、AS55992中间流经美国AS36678,此种情况属流经外国AS,从国家安全的角度来考虑,这种流量外泄的路径异常行为可能造成国内流量受到侦听或篡改,亦是倍受关注的重点异常行为之一。

通过对实验的路由异常数据的统计可得,连续重复AS异常数量平均占比29.6%,路由环路异常数量平均占比0%,邻居绕行异常数量平均占比35.3%,路径伪造异常数量平均占比5.3%,路径篡改异常数量平均占比31.6%,国内流量外泄数量平均占比0.8%。上述异常数量统计情况如表1所示,从表1中可以看出,路由环路异常出现次数为0,是因为路由环路容易被发现,且出现环路的危害比较大,这在路由配置策略中做了很好的预防。

图2中异常路径和路径数量的变化情况还可以发现,在2日至7日这段期间内,虽然路径的数量变化曲线明显,但其异常路径数量却没有太明显的变化,说明此段时间内的路由更新量比较大,而18至22日这段时间内,异常路径数量较前后时间急剧增多,这样情况可能是路由攻击的征兆,因为在正常情况下,路径异常的数量会维持在一个相对稳定的状态。当有新的路径异常路由的出现后会将此异常路由传播给更多的AS进行路径选择,而出现这种异常路径急剧增加的情况,说明受到影响的路由也急剧增加,推测可能受到范围比较广的路由攻击。

此外,如图3所示,提取出绕行路径并计算出其平均最短路径的值为4.02,同时,去除绕行路径中绕行的部分并重新计算,其最短路径的值为2.06,而路由更新表的平均最短路径为4.02,可见由于绕行路径的存在使得流量传播的最短平均路径增加了近2倍,无论此种现象是基于商业利益或流量工程的考虑,还是人为的恶意攻击行为所致,都不仅给网络的承载能力带来了极大的负担,也让网络中受到攻击的可能性极大增加。

Figure 2. Statistical chart of anomaly detection

图2. 异常统计图

Figure 3. Statistical chart of average path length

图3. 平均路径长度统计图

5. 结束语

本文首先对绕行路径作了定义,表明实际路由表中的路由本可以更短的路径到达目标网络进行流量的传递。针对路径异常进行了基于绕行路径的聚类分析,以AS邻接关系为先验知识,根据路径绕行的行为方式将绕行路径的表现形式分为连续重复AS、环路、绕邻居AS、绕国、绕境、绕跨国企业。同时提出了基于绕行路径的异常检测方法及流程。实验表明,本文所提方法能够有效检测出连续重复AS、路由环路、国内流量外泄、路径伪造、路径篡改等路由异常行为,能够对域间路由安全威胁做出预警,提高网络安全性,同时,实验还表明,由于绕行路径的存在,使得路由平均最短路径长度变长,使得网络的安全性受到威胁。

基金项目

国家自然科学基金(编号:61572514)。

文章引用

刘 磊,朱培栋,闫 爽,富 威. 基于绕行路径的聚类分析与异常检测
Clustering Analysis and Anomaly Detection Based on the Detour Path[J]. 软件工程与应用, 2016, 05(02): 93-102. http://dx.doi.org/10.12677/SEA.2016.52011

参考文献 (References)

  1. 1. Vohra, Q. and Chen, E. (2007) RFC 4893: BGP Support for Four-octet AS Number Space. Internet Engineering Task Force (IETF).

  2. 2. Bono, J.V. (1997) 7007 Explanation and Apology. NANOG.

  3. 3. Lad, M., Oliveira, R., Zhang, B. and Zhang, L. (2007) Understanding Resiliency of Internet Topology against Prefix Hijack Attacks. Proceedings of 37th Annual IEEE/IFIP International Conference on Dependable Systems and Networks, 2007, DSN’07, Edinburgh, 25-28 June 2007, 368-377.

  4. 4. Toonk, A. BGP Optimizer Causes Thousands of Fake Routes. http://www.bgpmon.net/bgp-optimizer-causes-thousands-of-fake-routes/

  5. 5. Toonk, A. The Canadian Bitcoin Hijack. http://www.bgpmon.net/the-canadian-bitcoin-hijack/

  6. 6. Toonk, A. Large Scale BGP Hijack Out of India. http://www.bgpmon.net/large-scale-bgp-hijack-out-of-india/

  7. 7. Toonk, A. Massive Route Leak Causes Internet Slowdown. http://www.bgpmon.net/massive-route-leak-cause-internet-slowdown/

  8. 8. 黎松, 诸葛建伟, 李星. BGP安全研究[J]. 软件学报, 2013, 24(1): 121-138.

  9. 9. Kruegel, C., Mutz, D., Robertson, W. and Valeur, F. (2010) Topology-Based Detection of Anomalous BGP Messages. In: Recent Advances in Intrusion Detection, Springer, Berlin Heidelberg, 17-35. http://dx.doi.org/10.1007/978-3-540-45248-5_2

  10. 10. Li, J., Ehrenkranz, T. and Elliott, P. (2012) Buddyguard: A Buddy System for Fast and Reliable Detection of IP Prefix Anomalies. 2012 20th IEEE International Conference on Network Protocols (ICNP), Austin, 30 October-2 November 2012, 1-10.

  11. 11. Hong, S.C., Hong, J.W.K. and Ju, H. (2011) IP Preifx Hijacking Detection Using the Collection of AS Characteristics. 2011 13th Asia-Pacific Network Operations and Management Symposium (APNOMS), Taipei, 21-23 September 2011 1-7.

  12. 12. Zhang, Y. and Pourzandi, M. (2012) Studying Impacts of Prefix Interception Attack by Exploring BGP AS-PATH Prepending. Proceedings of 2012 IEEE 32nd International Conference on Distributed Computing Systems (ICDCS), Macau, 18-21 June 2012, 667-677.

  13. 13. 刘磊, 朱培栋, 胡照明. 一种基于时空可信度推断AS商业关系的方法[J]. 软件工程与应用, 2016, 5(1): 38-46.

期刊菜单