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. 清華大學電子工程系, 復雜工程系統(tǒng)實驗室, 北京100084; 2. 中國科學院研究生院, 北京100049;

3. 中國科學院計算機網(wǎng)絡信息中心, 中國互聯(lián)網(wǎng)絡信息中心, 北京100190)

摘 要:為了研究互聯(lián)網(wǎng)用戶對網(wǎng)站的訪問模式, 借助中國互聯(lián)網(wǎng)絡信息中心負責管理的國家域名系統(tǒng)資源, 選取了一整天CN 域名權威服務器的日志。提出了域名規(guī)約的方法, 將日志中的域名合并為二級域名或者CN 下41個類別和行政區(qū)的三級域名。該方法不僅保留了用戶對網(wǎng)站的訪問信息, 而且能夠達到壓縮數(shù)據(jù)的目的。采用k means 算法對所提取的IP 和域名的時間行為特征矢量進行聚類。結果表明:根據(jù)時間行為模式的不同, IP 地址有3個主要類別, 即攻擊者、主要I SP 的遞歸服務器和非主流遞歸服務器; 域名有4個主要類別, 對其中大量訪問的域名進一步分類, 找到了真正體現(xiàn)絕大多數(shù)用戶網(wǎng)絡訪問需求的域名集合。關鍵詞:聚類; 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)

的特點, 提出了數(shù)據(jù)預處理的方法, 然后給出了對DNS 數(shù)據(jù)的特征提取方案和聚類個數(shù)k 的選擇方法, 最后分析域名和IP 特征矢量的聚類結果。

被查詢的總次數(shù):1d 內(nèi)域名被查詢的總次數(shù)。

IP 數(shù):查詢此域名的IP 的數(shù)量。反映提交域名請求的IP 分布情況。

被同一IP 重復查詢的次數(shù)(最小、最大、平均, 方差) 。

域名被查詢的間隔時間(最小、最大、平均間隔時間和間隔時間方差) 。

了解用戶查詢域名的時間特征有助于實現(xiàn)網(wǎng)絡、計算資源的優(yōu)化配置, 查詢間隔(最小、最大、平均, 方差) 就是一種查詢行為的時間特征。查詢的總次數(shù)反映了IP(域名) 的活躍程度, 查詢的重復情況反映了IP(域名) 查詢的行為特征, 可以對為域名和解析請求實現(xiàn)有效的分層管理提供依據(jù)。2. 2. 2 k means 算法

k means 算法是一種基于劃分的方法, 將N 個數(shù)據(jù)對象劃分為k 個聚類使得:同一聚類中的對象相似度較高而不同聚類中的對象相似度較小。其基本思想就是根據(jù)各模式到各個中心的距離分配到某一類中, 之后不斷計算類心和調(diào)整各模式的類別。設待分類的模式特征矢量集為{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)

(t)

(t)

(t 1)

(0)

(0)

[8]

1 原始數(shù)據(jù)預處理

一條典型DN S 記錄如下:

queries:info:client #1418:query: .

其中的有效信息為:時間、IP 和域名。為了壓縮數(shù)據(jù), 將DN S 日志文件中出現(xiàn)的所有域名地址統(tǒng)一進行合并處理, 歸約為二級域名或者CN 下41個類別和行政區(qū)的三級域名。例如, 日志中對門戶網(wǎng)站新浪的訪問w w w. sina. com. cn 、finance. sina. co m. cn 、m ail. sina. com. cn 等都被歸納為三級域名sina. co m. cn 。域名規(guī)約不僅保留了用戶對網(wǎng)站的訪問信息, 而且能夠達到壓縮數(shù)據(jù)的目的。經(jīng)過以上預處理后, 1d 的DNS 查詢?nèi)罩景?95247134條CN 域名查詢記錄, 來自1521237個IP 地址, 對7265685個CN 域名的訪問。

2 聚類分析

DNS 數(shù)據(jù)中蘊藏了豐富的信息, 將其加以分類, 可以了解用戶對互聯(lián)網(wǎng)的訪問模式, 為域名和解析請求實現(xiàn)有效的分層管理, 實現(xiàn)網(wǎng)絡、計算資源的優(yōu)化配置提供依據(jù)。由于k m eans 算法是對于特征矢量的聚類, 因此首先要從預處理之后的數(shù)據(jù)中提取特征, 生成特征向量。然后選擇類數(shù)k , 進行聚類分析。

2. 2. 1 特征提取

每一條DNS 查詢都可以抽象成IP 地址訪問目標域名這一行為動作。因此, 本文主要研究域名查詢記錄中的2個主體的特征:資源主體域名和行為主體IP 。首先需要提取特征描述IP 和域名, 對這2個主體進行向量表示。

1) IP 行為特征描述。

查詢的次數(shù):1d 內(nèi)向系統(tǒng)提交域名查詢的總次數(shù)。

查詢的域名數(shù):用戶向系統(tǒng)提交不同的查詢的數(shù)量, 反映提交的域名請求分布情況。 對同一個域名的重復查詢數(shù)(最小、最大、平均, 方差) 。

查詢的間隔時間(最小、最大、平均間隔時間) 。

2) 域名特征描述。

,

的中心z j

(t)

的距離, 上角標

(t 1)

表示迭代次數(shù)。于是產(chǎn)生新的聚類 j ! , k 。

3) 計算重新分類后的各類心。z j

式中n

(t 1)

, j =1, 2,

=

n

(t 1) j x ?

i

j

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

(t 1)

j

為

(t 1) j

類所含的模式個數(shù)。

(t)

4) 如果z j

(t 1)

=z j , j =1, 2, ! , k, 則結束; 否

則t =t 1, 轉至2) 。

k means 算法明顯的優(yōu)勢是運算量小, 能用于處理龐大的樣本數(shù)據(jù), 因此本文采用k means 算法。2. 2. 3 k 的選取

k 的選擇對于聚類結果的影響非常大, 通常的方法是讓類數(shù)k 逐步增加, 對每個k 分別使用該算法。顯然, 準則函數(shù)J 是隨k 的增加而單調(diào)減少。在k 增加的過程中, 總會出現(xiàn)使本來較密集的一些

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

n

模式點再被分劃開的情況, 此時J 雖然減小, 但減小速度將變緩。如果作一條J k 曲線, 其曲率變化的最大點對應的類數(shù)是比較接近從模式幾何分布上看最優(yōu)的類數(shù)。然而, 這樣不僅計算量巨大, 而且在許多情況下, 曲線并無這樣明顯的點。

本文采取的方法是利用問題的先驗知識選取合理的聚類數(shù), 然后分析聚類的結果, 對于特征近似的某幾類進行合并; 對于矢量過多且特征不明顯的某一類, 再進一步分類。其次對于作者比較關心的一些類(比如熱點的域名) 也需要進一步分類。

定義類內(nèi)距離函數(shù)J Inside 和類間離函數(shù)J Outside :

J in side =

i=1

j

|x i -m j |2n j ,

(j )

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

其中m i 、m j 為第i 類和第j 類的中心向量。如果某一類的類內(nèi)距離函數(shù)較大, 應該再次分類; 如果兩個類的類間距離很小, 就應該合并。

3 聚類結果及分析

3. 1 IP 訪問模式

采用k m eans 算法對1521237個IP 地址向量的進行聚類, 首先選擇k =12, 結果見表1。

表1 全天IP 訪問模式

類123456789101112

IP 數(shù)459771126019124341524642512793846421165271832086765619128

請求的次數(shù)12. 4279. 05569204. 01413. 0812. 226. 5190437. 92. 5621417. 514. 41389. 72. 4

不同的請求數(shù)

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

重復數(shù)(最大/最小/平均)

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, 合并相似的類, 可以發(fā)現(xiàn)IP 的訪問模式主要有以下幾個大類。

1) 錯誤數(shù)據(jù)(類3和7) 。特征是訪問次數(shù)大, 重復數(shù)量也很大。這些IP 都是在短時間內(nèi)連續(xù)發(fā)出相同的查詢請求。其原因可能是:a) 病毒或攻擊; b) 主機防火墻配置不當, 導致收不到DN S 服務器的返回。此類查詢占總量的1. 40。

2) 主要ISP 的遞歸服務器(類9) 。特征是訪問數(shù)量很大, 但是重復少。例如: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) 企業(yè)級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

域名數(shù)6857665864329211

被請求次數(shù)40. 11578817. 81198630. 2

3. 2329888. 039250650. 0

IP 數(shù)27. 03774. 0151035. 12. 41. 0436575. 0

重復請求數(shù)(最大/最小/平均/方差) 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) (續(xù)表)

類78910111213141516

域名數(shù)902887243180574481150491249071943686393741261554105402

被請求次數(shù)687. 65. 63. 28. 94. 19276563. 3

3. 39. 727. 14. 2

IP 數(shù)238. 44. 21. 96. 73. 1352986. 52. 57. 019. 72. 7

重復請求數(shù)(最大/最小/平均/方差)

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, 合并相似的類, 可以發(fā)現(xiàn)域名的查詢模式主要有以下幾個大類。

1) 中國電信的IP 反向解析地址(類6, 163data. com. cn) :動態(tài)反向解析主要是為了防止垃圾郵件, 減少黑客攻擊等。此類查詢占總量的3. 97。

2) 負責解析很多流行CN 域名的權威名字服務器的域名(類12) :特征是被查詢數(shù)量非常大, 被重復請求的數(shù)量很大。例如: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) 網(wǎng)絡熱點(類7) :特征是被多個IP 請求。此類查詢占總量的62. 72。

4) 具有地域性、專業(yè)性的網(wǎng)站, 或者個人網(wǎng)站(類4、8 11、13、14、16) :特征是被查詢次數(shù)比較少。如:g sfic. or g. cn (甘肅省工商業(yè)聯(lián)合會) , smlight. cn (盛貿(mào)燈飾) , cao ke. com. cn (炒客論壇) 等。這一類體現(xiàn)了有特定興趣的用戶訪問需求, 不是大多數(shù)用戶的需求。

5) 錯誤數(shù)據(jù)(類5) :只有1個錯誤域名(2ihep. ac. cn) , 是主機配置錯誤造成的。

其中的網(wǎng)絡熱點(類7) 是作者最為關心的一類, 因此對其進行第二次分類, 結果見表3。

表3 類7的再次分類結果

類7. 17. 27. 37. 4

域名數(shù)7323565120876329568

被請求次數(shù)6. 1824. 1133274. 1116. 4

IP 數(shù)2. 2309. 018780. 373. 3

重復請求數(shù)(最大/最小/平均/方差)

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類域名是真正體現(xiàn)絕大多數(shù)用戶網(wǎng)絡訪問需求的部分。例如: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 。

大量訪問的網(wǎng)站具有不同的時間特征, 進一步的分析, 又得到了真正體現(xiàn)絕大多數(shù)用戶網(wǎng)絡訪問需求的域名集合。

本文提出的方法, 能夠在一定程度上發(fā)現(xiàn)用戶和域名特征的分組。較之其他聚類方法, k means 算法明顯的優(yōu)勢是運算量小, 能處理龐大的數(shù)據(jù)。但其缺點是:聚類結果為局部最優(yōu)而非全局最優(yōu), 并且對于噪聲和孤立點敏感。因此下一步工作可以利用k means 算法進行聚類預處理, 然后對得到的重要分類采取其他聚類方法(層次聚類等) , 對向量子集進行進一步分解和劃分。

(下轉第608頁)

4 結束語

通過聚類分析, 發(fā)現(xiàn)用戶訪問模式存在巨大差異, 主要分為3個類別:1) 攻擊或者垃圾郵件發(fā)送者; 2) 主要ISP 的遞歸服務器; 3) 其他的非主流DNS 遞歸服務器。通過對域名時間行為的聚類分析, 權威名字服務器的域名(域名主機) 和網(wǎng)絡用戶

608清華大學學報(自然科學版)

[3]

2010, 50(4)

4 結 論

本文研究了多用戶上行OFDM A 系統(tǒng)比例公平的資源分配算法。文中通過理論分析給出了OFDM A 上行比例公平資源分配的最優(yōu)解, 隨后提出了一種上行PF 資源分配算法。仿真結果表明:相比Rate M ax 算法, 本文算法雖然增加了復雜度, 但是大幅度提高了吞吐量和系統(tǒng)公平性; 相比上行Max m in 公平算法, 本文算法雖然損失了部分公平性, 但是卻提高了吞吐量、降低了復雜度?？梢? 該算法在吞吐量、公平性和實現(xiàn)復雜度3個方面取得了更好的折中, 是一種有效的上行OFDM A 系統(tǒng)資源分配算法。

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

in

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]

孫即祥. 現(xiàn)代模式識別[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