基于k_means算法的DNS查询模式分析

2017-03-27

31481

CN 11 2223/N 清华大学学报(自然科学版) 2010年第50卷第4期J T sing hua Un iv (Sci &Tech) , 2010, V o l. 50, N o. 427/36

CN 11 2223/N 清华大学学报(自然科学版) 2010年第50卷第4期J T sing hua Un iv (Sci &Tech) , 2010, V o l. 50, N o. 427/36601 604, 608

基于k means 算法的DNS 查询模式分析

季成1, 3, 李晓东3, 袁坚1, 尉迟学彪2, 3, 山秀明1

(1. 清华大学电子工程系, 复杂工程系统实验室, 北京100084; 2. 中国科学院研究生院, 北京100049;

3. 中国科学院计算机网络信息中心, 中国互联网络信息中心, 北京100190)

摘要:为了研究互联网用户对网站的访问模式, 借助中国互联网络信息中心负责管理的国家域名系统资源, 选取了一整天CN 域名权威服务器的日志。提出了域名规约的方法, 将日志中的域名合并为二级域名或者CN 下41个类别和行政区的三级域名。该方法不仅保留了用户对网站的访问信息, 而且能够达到压缩数据的目的。采用k means 算法对所提取的IP 和域名的时间行为特征矢量进行聚类。结果表明:根据时间行为模式的不同, IP 地址有3个主要类别, 即攻击者、主要I SP 的递归服务器和非主流递归服务器; 域名有4个主要类别, 对其中大量访问的域名进一步分类, 找到了真正体现绝大多数用户网络访问需求的域名集合。关键词:聚类; DNS 服务器; 日志分析; 时间行为模式; k

means 算法

中图分类号:T P 391

文章编号:1000 0054(2010) 04 0601 04

文献标识码:A

T he further clusterin g of the domain nam es queried by large nu mber of users finds th e domain names truly reflecting the need of the

majority of th e users. Key words:clusterin g; DNS

behavior; k means

server;

log

analysis;

tem poral

602清华大学学报(自然科学版) 2010, 50(4)

的特点, 提出了数据预处理的方法, 然后给出了对DNS 数据的特征提取方案和聚类个数k 的选择方法, 最后分析域名和IP 特征矢量的聚类结果。

被查询的总次数:1d 内域名被查询的总次数。

IP 数:查询此域名的IP 的数量。反映提交域名请求的IP 分布情况。

被同一IP 重复查询的次数(最小、最大、平均, 方差) 。

域名被查询的间隔时间(最小、最大、平均间隔时间和间隔时间方差) 。

了解用户查询域名的时间特征有助于实现网络、计算资源的优化配置, 查询间隔(最小、最大、平均, 方差) 就是一种查询行为的时间特征。查询的总次数反映了IP(域名) 的活跃程度, 查询的重复情况反映了IP(域名) 查询的行为特征, 可以对为域名和解析请求实现有效的分层管理提供依据。2. 2. 2 k means 算法

k means 算法是一种基于划分的方法, 将N 个数据对象划分为k 个聚类使得:同一聚类中的对象相似度较高而不同聚类中的对象相似度较小。其基本思想就是根据各模式到各个中心的距离分配到某一类中, 之后不断计算类心和调整各模式的类别。设待分类的模式特征矢量集为{x 1, x 2, ! , x N }, 被分为k 类(事先选定) , 步骤如下。

(0)

1) 任选k 个模式矢量作为初始聚类中心:z 1, z 2, ! , z k , 令t =0。

2) 将待分类的模式矢量逐个按最小距离原则分划给k 类中的某一类, 即:

若d il =min j {d ij }, i =1, 2, ! , N, 则x i ∀ l 式中d ij 表示x i 和 j

(t)

(t 1)

(0)

[8]

1 原始数据预处理

一条典型DN S 记录如下:

queries:info:client #1418:query: .

其中的有效信息为:时间、IP 和域名。为了压缩数据, 将DN S 日志文件中出现的所有域名地址统一进行合并处理, 归约为二级域名或者CN 下41个类别和行政区的三级域名。例如, 日志中对门户网站新浪的访问w w w. sina. com. cn 、finance. sina. co m. cn 、m ail. sina. com. cn 等都被归纳为三级域名sina. co m. cn 。域名规约不仅保留了用户对网站的访问信息, 而且能够达到压缩数据的目的。经过以上预处理后, 1d 的DNS 查询日志包括995247134条CN 域名查询记录, 来自1521237个IP 地址, 对7265685个CN 域名的访问。

2 聚类分析

DNS 数据中蕴藏了丰富的信息, 将其加以分类, 可以了解用户对互联网的访问模式, 为域名和解析请求实现有效的分层管理, 实现网络、计算资源的优化配置提供依据。由于k m eans 算法是对于特征矢量的聚类, 因此首先要从预处理之后的数据中提取特征, 生成特征向量。然后选择类数k , 进行聚类分析。

2. 2. 1 特征提取

每一条DNS 查询都可以抽象成IP 地址访问目标域名这一行为动作。因此, 本文主要研究域名查询记录中的2个主体的特征:资源主体域名和行为主体IP 。首先需要提取特征描述IP 和域名, 对这2个主体进行向量表示。

1) IP 行为特征描述。

查询的次数:1d 内向系统提交域名查询的总次数。

查询的域名数:用户向系统提交不同的查询的数量, 反映提交的域名请求分布情况。对同一个域名的重复查询数(最小、最大、平均, 方差) 。

查询的间隔时间(最小、最大、平均间隔时间) 。

2) 域名特征描述。

的中心z j

(t)

的距离, 上角标

(t 1)

表示迭代次数。于是产生新的聚类 j ! , k 。

3) 计算重新分类后的各类心。z j

式中n

(t 1)

, j =1, 2,

(t 1) j x ∀

x i , j =1, 2, ! , k.

(t 1)

为

(t 1) j

类所含的模式个数。

(t)

4) 如果z j

(t 1)

=z j , j =1, 2, ! , k, 则结束; 否

则t =t 1, 转至2) 。

k means 算法明显的优势是运算量小, 能用于处理庞大的样本数据, 因此本文采用k means 算法。2. 2. 3 k 的选取

k 的选择对于聚类结果的影响非常大, 通常的方法是让类数k 逐步增加, 对每个k 分别使用该算法。显然, 准则函数J 是随k 的增加而单调减少。在k 增加的过程中, 总会出现使本来较密集的一些

季成, 等: 基于k means 算法的DN S 查询模式分析 603

模式点再被分划开的情况, 此时J 虽然减小, 但减小速度将变缓。如果作一条J k 曲线, 其曲率变化的最大点对应的类数是比较接近从模式几何分布上看最优的类数。然而, 这样不仅计算量巨大, 而且在许多情况下, 曲线并无这样明显的点。

本文采取的方法是利用问题的先验知识选取合理的聚类数, 然后分析聚类的结果, 对于特征近似的某几类进行合并; 对于矢量过多且特征不明显的某一类, 再进一步分类。其次对于作者比较关心的一些类(比如热点的域名) 也需要进一步分类。

定义类内距离函数J Inside 和类间离函数J Outside :

J in side =

i=1

|x i -m j |2n j ,

(j )

J Outside =|m i -m j |2.

其中m i 、m j 为第i 类和第j 类的中心向量。如果某一类的类内距离函数较大, 应该再次分类; 如果两个类的类间距离很小, 就应该合并。

3 聚类结果及分析

3. 1 IP 访问模式

采用k m eans 算法对1521237个IP 地址向量的进行聚类, 首先选择k =12, 结果见表1。

表1 全天IP 访问模式

类123456789101112

IP 数459771126019124341524642512793846421165271832086765619128

请求的次数12. 4279. 05569204. 01413. 0812. 226. 5190437. 92. 5621417. 514. 41389. 72. 4

不同的请求数

6. 127. 610. 0402. 1142. 513. 21. 21. 5170055. 87. 0521. 51. 4

重复数(最大/最小/平均)

4. 4/1. 6/2. 177. 5/2. 1/7. 75569082. 0/1. 0/556920. 4

177. 5/9. 5/17. 2

132. 7/2. 6/7. 86. 4/1. 4/2. 3

190385. 6/99020. 2/124948. 1

2. 1/2. 0/2. 0

19422. 6/2. 9/190. 0

5. 2/1. 7/2. 670. 8/1. 8/4. 82. 0/1. 9/1. 9

间隔时间(最小/最大/平均) /s 118. 3/3276. 7/739. 5336. 6/86052. 0/31434. 20. 0/86400. 0/24875. 02. 4/85973. 4/5267. 445. 8/85532. 6/15583. 3522. 9/11747. 2/1974. 10. 0/86400. 0/6398. 330373. 4/37657. 0/33948. 80. 0/86400. 0/4209. 01098. 8/32432. 1/8782. 6137. 4/81452. 4/7759. 679751. 1/80994. 0/80487. 3

分析表1, 合并相似的类, 可以发现IP 的访问模式主要有以下几个大类。

1) 错误数据(类3和7) 。特征是访问次数大, 重复数量也很大。这些IP 都是在短时间内连续发出相同的查询请求。其原因可能是:a) 病毒或攻击; b) 主机防火墙配置不当, 导致收不到DN S 服务器的返回。此类查询占总量的1. 40。

2) 主要ISP 的递归服务器(类9) 。特征是访问数量很大, 但是重复少。例如:202. 101. 224. 69(dns. jxdx. net. cn, CH INANET 江西省) , 70. 84. 138. 226(e2. 8a. 5446. static. theplanet. co m, T he

Planet. com Internet 接入服务公司) 。此类查询占总量的31. 89。

3) 企业级DNS 服务器(类2、4、5、11) 。特征是访问量比较大, 但比类9少很多。此类查询占总量的65. 56。

4) 普通用户端(类1、6、8、10、12) 。特征是访问量非常小。此类查询占总量的1. 16。3. 2 域名查询模式分析

采用k m eans 算法对7265685个域名向量进行聚类, 首先选择k =16, 结果见表2。

表2 全天的域名聚类结果

类123456

域名数6857665864329211

被请求次数40. 11578817. 81198630. 2

3. 2329888. 039250650. 0

IP 数27. 03774. 0151035. 12. 41. 0436575. 0

重复请求数(最大/最小/平均/方差) 5. 7/1. 5/2. 1/1. 2

486253. 6/346. 0/13035. 4/28746. 3

42058. 9/1. 0/8. 2/187. 8

1. 8/1. 3/1. 6/0. 3329888. 0/329888. 0/329888. 0/0. 05558206. 0/1. 0/89. 9/9156. 2

间隔时间(最大/最小/平均/方差) /s 123. 8/13090. 7/2665. 3/3393. 5

0. 0/1614. 0/1. 3/11. 30. 0/3. 4/0. 1/0. 2

12990. 6/45661. 6/28712. 5/21826. 8

0. 0/68. 5/0. 3/1. 50. 0/0. 1/0. 0/0. 0

604清华大学学报(自然科学版) 2010, 50(4) (续表)

类78910111213141516

域名数902887243180574481150491249071943686393741261554105402

被请求次数687. 65. 63. 28. 94. 19276563. 3

3. 39. 727. 14. 2

IP 数238. 44. 21. 96. 73. 1352986. 52. 57. 019. 72. 7

重复请求数(最大/最小/平均/方差)

32. 1/2. 1/3. 2/2. 52. 2/1. 3/1. 6/0. 52. 3/2. 0/2. 1/0. 22. 7/1. 2/1. 7/0. 71. 9/1. 3/1. 6/0. 4177125. 5/1. 0/28. 7/510. 5

1. 7/1. 3/1. 5/0. 3

2. 9/1. 3/1. 8/0. 74. 4/1. 3/1. 9/1. 02. 3/1. 7/2. 0/0. 4

间隔时间(最大/最小/平均/方差) /s

26. 4/2992. 7/455. 3/587. 51108. 1/29533. 5/12727. 1/13376. 623663. 6/31976. 7/27787. 7/5671. 8116. 1/45883. 7/9392. 8/17047. 61388. 2/46612. 0/19604. 1/25287. 00. 0/0. 4/0. 0/0. 0

2185. 2/63797. 4/30402. 4/41081. 1609. 3/19358. 7/7153. 3/7253. 018. 8/29967. 6/3999. 1/7848. 810113. 3/23246. 4/16198. 0/7201. 2

分析表2, 合并相似的类, 可以发现域名的查询模式主要有以下几个大类。

1) 中国电信的IP 反向解析地址(类6, 163data. com. cn) :动态反向解析主要是为了防止垃圾邮件, 减少黑客攻击等。此类查询占总量的3. 97。

2) 负责解析很多流行CN 域名的权威名字服务器的域名(类12) :特征是被查询数量非常大, 被重复请求的数量很大。例如:capital online. co m. cn 、cnnic. cn 、dns. com. cn 、ename. cn 、fz. fj. cn 、guang zhou. gd. cn 、hetsptt. net. cn 、sdjnptt. net. cn 、sdqdptt. net. cn 、tpt. net. cn 、w uhan. net. cn 等。此类查询占总量的17. 81。

3) 网络热点(类7) :特征是被多个IP 请求。此类查询占总量的62. 72。

4) 具有地域性、专业性的网站, 或者个人网站(类4、8 11、13、14、16) :特征是被查询次数比较少。如:g sfic. or g. cn (甘肃省工商业联合会) , smlight. cn (盛贸灯饰) , cao ke. com. cn (炒客论坛) 等。这一类体现了有特定兴趣的用户访问需求, 不是大多数用户的需求。

5) 错误数据(类5) :只有1个错误域名(2ihep. ac. cn) , 是主机配置错误造成的。

其中的网络热点(类7) 是作者最为关心的一类, 因此对其进行第二次分类, 结果见表3。

表3 类7的再次分类结果

类7. 17. 27. 37. 4

域名数7323565120876329568

被请求次数6. 1824. 1133274. 1116. 4

IP 数2. 2309. 018780. 373. 3

重复请求数(最大/最小/平均/方差)

4. 4/3. 9/4. 1/0. 429. 7/1. 5/2. 6/2. 59940. 5/708. 0/806. 8/310. 0

10. 5/1. 3/2. 1/1. 8

间隔时间(最大/最小/平均/方差) /s 3994. 5/2447. 0/3170. 8/876. 11317. 9/2. 8/131. 5/194. 73530. 8/0. 0/9. 6/61. 85840. 9/13. 2/951. 2/1256. 1

可以看到:7. 3类域名是真正体现绝大多数用户网络访问需求的部分。例如:g oog le. cn 、beijing olym. com. cn 、bm w brilliance. cn 、nankai. edu. cn 等。7. 2类与7. 3类相似, 流行度稍有降低。带有一定地域性或者面向特定受众群体, 例如:shao s han. go v. cn 、shang haizo o. cn 。

大量访问的网站具有不同的时间特征, 进一步的分析, 又得到了真正体现绝大多数用户网络访问需求的域名集合。

本文提出的方法, 能够在一定程度上发现用户和域名特征的分组。较之其他聚类方法, k means 算法明显的优势是运算量小, 能处理庞大的数据。但其缺点是:聚类结果为局部最优而非全局最优, 并且对于噪声和孤立点敏感。因此下一步工作可以利用k means 算法进行聚类预处理, 然后对得到的重要分类采取其他聚类方法(层次聚类等) , 对向量子集进行进一步分解和划分。

(下转第608页)

4 结束语

通过聚类分析, 发现用户访问模式存在巨大差异, 主要分为3个类别:1) 攻击或者垃圾邮件发送者; 2) 主要ISP 的递归服务器; 3) 其他的非主流DNS 递归服务器。通过对域名时间行为的聚类分析, 权威名字服务器的域名(域名主机) 和网络用户

608清华大学学报(自然科学版)

[3]

2010, 50(4)

4 结论

本文研究了多用户上行OFDM A 系统比例公平的资源分配算法。文中通过理论分析给出了OFDM A 上行比例公平资源分配的最优解, 随后提出了一种上行PF 资源分配算法。仿真结果表明:相比Rate M ax 算法, 本文算法虽然增加了复杂度, 但是大幅度提高了吞吐量和系统公平性; 相比上行Max m in 公平算法, 本文算法虽然损失了部分公平性, 但是却提高了吞吐量、降低了复杂度。可见, 该算法在吞吐量、公平性和实现复杂度3个方面取得了更好的折中, 是一种有效的上行OFDM A 系统资源分配算法。

Jalali A, Pad ovani R, Pan kai R. Data through put of CDM A H DR a h igh efficiency h igh data rate pers on al comm unication w irless netw orks [C]//Proc IEEE VTC2000 Spring. 2000:1854 1858.

[4]Kim H, H an Y. A proportional fair sch edulin g for mu ltiuser tran smis sion systems [J]. IE EE Communications L etters , 2005, 9(3) :210 212.

[5]Nguyen T D, H an Y. A proportional fairnes s algorithm w ith QoS provision in dow nlin k OFDM A sys tems [J ]. IEE E Communaliz ations L etter s, 2006, 10(11) :760 762.

[6]

M a Y. Rate max imization for downlink OFDM A w ith proportional fairness [J]. IEE E Tr ans Vehicular T ech nolog y , 2008, 57(5) :3267 3274.

Kim K, H an Y, Kim S L. Joint su bcarrier and pow er allocation

u plink

OFDM A

systems

[J].

IEE E

Communications L e tters , 2005, 9(6) :526 528.

[7]

[8]Ng C Y, Sung C W. Low complexity subcarrier and pow er allocation for u tility maximiz ation in uplink OFDM A s ystem s [J].

IE EE

T r ans

W ireless

Communic ations ,

2008,

参考文献 (References)

[1]

W ong C Y, Cheng R S, Lataief K B, et al. M u ltiuser OFDM w ith adaptive s ubcarrier, bit, an d pow er allocation [J]. IE EE J Se lec t A reas Commu n, 1999, 17(10) :1747 1758. [2]

J ang J, Lee K B. T ran smit pow er adaptation for multius er OFDM sy stems [J]. IE EE J S eclect Ar eas Commun, 2003, 21(2) :171 178.

7(5) :1667 1675.

(上接第604页)

[5]

Jun g J, Sit E, Balakris hnan H , et al. DNS perform ance and the effectiveness of caching [J ]. IE EE /ACM T rans on N etw or king , 2002, 10(5) :589 603. [6]

Ishibash i K, T oyono T , M atsuoka H , et al. M easu rem ent of DNS

traffic cau sed by DDoS attack [C]//

Proc the

Symp os ium on Applications and the In ternet W orksh ops. Wash ington , 2005:118 121. [7]

Ishibash i K,

T oyono T ,

T oyama K,

et al.

Detecting

mass mailing w orm in fected hosts by mining DNS traffic data [C]//Proc th e 2005ACM SIGCOM M W orksh op on M in ing Netw ork Data. Philadelphia, 2005:159 164. [8]

孙即祥. 现代模式识别[M ]. 长沙:国防科技大学出版社, 2002:31 33.

参考文献 (References)

[1]

Dan zig P B, Obraczk a K, Ku mar A. An analysis of wide area n ame server traffic:A study of the internet domain name s ystem [C]//ACM SIGCOM M Compu ter Communication Review. New York, 1992, 22(4) :281 292. [2]

W es sels D, Fom enkov M. W ow , that s a lot of pack ets [C]//Proc Passive and [3]

Active Netw ork

M easurement

W orks hop (PAM ) . San Diego, 2003.

Brow nlee N, Claffy K, Nem eth E. DNS measurements at a r oot server [C]//6th Global Internet An tonio, T X, 2001. [4]

Xu W, Kirkpatrick B, Lacoste Ju lien S. Analyzing root DNS traffic [EB/OL](2004) . http://w w w. eecs. b erk eley. edu/~bb kirk/papers/cs 262a 2004. pdf.

Symposiu m.

S an

相关推荐