貝葉斯預(yù)測下的域間路由信任機(jī)制

王 偉，楊本朝，吳 濤

(1.信息工程大學(xué)數(shù)學(xué)工程與先進(jìn)計(jì)算國家重點(diǎn)實(shí)驗(yàn)室，河南鄭州 450002;2.安徽大學(xué)數(shù)學(xué)科學(xué)學(xué)院，安徽合肥 230039)

BGP［1］協(xié)議是不同域之間交換信息的路由協(xié)議，是互聯(lián)網(wǎng)中不同自治系統(tǒng)間的協(xié)議標(biāo)準(zhǔn).與其他網(wǎng)絡(luò)協(xié)議一樣，BGP協(xié)議在安全問題上也存在設(shè)計(jì)缺陷［2］，由于這些缺陷，惡意攻擊者可以進(jìn)行前綴劫持、路徑縮短、路徑填充等攻擊［3］，嚴(yán)重威脅網(wǎng)絡(luò)的安全性.

為了提高BGP的安全性，多位國內(nèi)外學(xué)者提出了各種BGP安全方案，其中有Kent等［4］提出的S－BGP(secure border gateway protocol)，White等［5］提出的 So－BGP(secure origin BGP).這些方案都依賴PKI(public key infrastructure)技術(shù)來保證信息的可信性，雖然具有良好的安全性，但計(jì)算開銷過大，至今這些方案都沒有在網(wǎng)絡(luò)中得到實(shí)際規(guī)模部署.Wan等［6］提出的psBGP(pretty secure BGP)是在BGP更新消息中添加前綴信息和AS號綁定的方法來實(shí)現(xiàn)異常檢測.該方案需要集中的機(jī)構(gòu)或設(shè)施作為支撐，且檢測的時(shí)效性和可靠性難以得到保證.部分學(xué)者也提出了根據(jù)信任機(jī)制來提高BGP抵御虛假路由攻擊的方案，如胡寧等［7］提出了基于構(gòu)建各AS的信譽(yù)，根據(jù)AS信譽(yù)值的大小有選擇地抑制信譽(yù)值小的AS提供的路由，該方法雖然提高了路由的可信性，但AS信譽(yù)值是如何具體計(jì)算和更新的，沒有具體描述;譚晶等［8］提出了基于Chord環(huán)的域間路由機(jī)制，但Chord環(huán)節(jié)點(diǎn)是如何選取和退出的也沒有具體描述，而且該方案是一個(gè)集中式的計(jì)算方法，且涉及證據(jù)理論中的集合運(yùn)算，因而計(jì)算效率不高.

1 域間路由節(jié)點(diǎn)信任度的計(jì)算

1.1 節(jié)點(diǎn)信任度的定義

在Internet中以自治系統(tǒng)為信任實(shí)體，借鑒社會科學(xué)領(lǐng)域?qū)π湃蔚拿枋觯?］，并結(jié)合域間自治系統(tǒng)自身的特點(diǎn)和安全需求，將不同自治系統(tǒng)間的信任度定義為:自治系統(tǒng)A在t時(shí)刻對鄰居自治系統(tǒng)B的信任度是指A根據(jù)B轉(zhuǎn)發(fā)的歷史路由通告的統(tǒng)計(jì)結(jié)果，對B未來通告真實(shí)路由的概率預(yù)測.

在文中，路由通告的統(tǒng)計(jì)結(jié)果是指B轉(zhuǎn)發(fā)給A的真實(shí)路由和虛假路由的歷史統(tǒng)計(jì).自治系統(tǒng)對其每個(gè)鄰居都維護(hù)和更新路由的統(tǒng)計(jì)情況(為了簡便，論文將自治系統(tǒng)也簡稱為節(jié)點(diǎn)).

1.2 節(jié)點(diǎn)信任度的計(jì)算

根據(jù)目前關(guān)于路由檢測的手段以及對無效路由的分析［10］，通過監(jiān)測系統(tǒng)可以得到虛假路由的統(tǒng)計(jì)情況、論文根據(jù)路由統(tǒng)計(jì)情況，由貝葉斯預(yù)測計(jì)算自治系統(tǒng)的信任度.

將節(jié)點(diǎn)是否收到真實(shí)路由看成是二項(xiàng)事件，則節(jié)點(diǎn)在△t時(shí)間內(nèi)收到真實(shí)路由的個(gè)數(shù)服從二項(xiàng)分布，設(shè)為b(n，p)，其中p為收到真實(shí)路由的概率.若在tn時(shí)刻節(jié)點(diǎn)A共收到來自B的N個(gè)路由，其中r個(gè)真實(shí)路由，根據(jù)貝葉斯預(yù)測［11－12］知，節(jié)點(diǎn)A在未來接收到B的k個(gè)路由中，有z個(gè)真實(shí)路由的后驗(yàn)預(yù)測分布為m(z|r)，若取p的先驗(yàn)分布為均勻分布，則

在tn時(shí)刻節(jié)點(diǎn)A對節(jié)點(diǎn)B的信任度TA，B(tn)定義如下

由(3)式可以看出，A對B的信任度由A對B的歷史信任度和A對B下一時(shí)刻通告真實(shí)路由的預(yù)測值兩部分組成.TA，B(tn)的定義保證了所有歷史數(shù)據(jù)參與了計(jì)算，且使得離當(dāng)前時(shí)刻越遠(yuǎn)的歷史信任度對當(dāng)前信任度的貢獻(xiàn)愈小，即離當(dāng)前時(shí)刻越遠(yuǎn)的行為，其對當(dāng)前時(shí)刻的信任度的影響越小，即信任具有時(shí)間遺忘性.而貝葉斯預(yù)測值SA，B(tn)則是對信任度TA，B(tn)的修正.若在tn時(shí)刻，A收到了鄰居節(jié)點(diǎn)B發(fā)送過來虛假路由，為了符合“信任失去容易、得到難”的一般原則，采用如下信任度更新方法

其中:β∈(0，1)為懲罰因子.可以看出，β取值大小反映了對發(fā)送虛假路由節(jié)點(diǎn)的懲罰力度，這樣不僅能提高信任更新的計(jì)算效率，還能及時(shí)抑制虛假路由的擴(kuò)散.

2 基于節(jié)點(diǎn)信任度的域間路由機(jī)制

對BGP路由算法進(jìn)行了擴(kuò)展，在BGP選路過程中加入對節(jié)點(diǎn)和路徑的信任度的考慮，構(gòu)建了一個(gè)新的域間路由機(jī)制N－BGP.增加一個(gè)新的路徑屬性ASpath Trust，表示節(jié)點(diǎn)對一條路徑的信任度，路徑的信任度包括節(jié)點(diǎn)對鄰居的信任度和鄰居對該路徑的信任度兩部分組成，并且每個(gè)節(jié)點(diǎn)計(jì)算出路徑的信任度后都修改ASpath Trust值，表示節(jié)點(diǎn)對該路徑的信任度.由于網(wǎng)絡(luò)中每個(gè)AS并不一定都部署N－BGP，因此設(shè)定ASpath Trust屬性為可選屬性.

2.1 路徑信任度的計(jì)算

(1)若n=0，則A與AS0為鄰居，其對路徑P的信任度即當(dāng)前時(shí)刻A對AS0的節(jié)點(diǎn)信任度，，并將 AS path Trust屬性值設(shè)定為

(2)若n＞0，此時(shí)路徑P的AS path Trust屬性值為，則節(jié)點(diǎn)A對路徑P的信任度為

2.2 BGP 選路算法

由于路徑的信任度由節(jié)點(diǎn)對鄰居的信任和鄰居對該條路徑的信任度兩部分組成，因此可設(shè)定一個(gè)閾值θ.當(dāng)節(jié)點(diǎn)對鄰居節(jié)點(diǎn)的信任度小于θ時(shí)，直接抑制該條路徑，不作為備選路由，否則計(jì)算路徑的信任度，再根據(jù)路徑信任度的大小選取最優(yōu)路徑.此外當(dāng)有路由需要向鄰居廣播時(shí)，也根據(jù)閾值θ確定廣播的對象，當(dāng)鄰居的信任度小于θ時(shí)，不向其廣播路由.因?yàn)楣?jié)點(diǎn)對鄰居節(jié)點(diǎn)信任度很小時(shí)，則該鄰居節(jié)點(diǎn)可能在當(dāng)前時(shí)刻受到攻擊或變?yōu)閻阂夤?jié)點(diǎn)，若此時(shí)向其廣播新的路徑更新，則該鄰居節(jié)點(diǎn)可能會產(chǎn)生虛假路由，不利于虛假路由的抑制.

當(dāng)節(jié)點(diǎn)A收到鄰居ASn發(fā)送的路徑，BGP的選路流程如下:

步驟1 查看A對ASn的信任度是否大于θ，若是，按(5)式計(jì)算路徑P的信任度，并將P的AS path Trust屬性值改為，轉(zhuǎn)入步驟2;若否，抑制該路由，轉(zhuǎn)入處理下一條路由.

步驟2 若Loc－RIB(local routing information base)中沒有路徑P所表示的目的前綴，則將P加入Loc－RIB中，若有則轉(zhuǎn)入步驟3.

步驟3 依次比較Loc－RIB中與路徑P相同目的前綴的路徑，選擇最優(yōu)的加入Loc－RIB中(依次比較LocalPref，AS path Trust等屬性值).

步驟4 若在Adj－RIB－Out(adjacent routing information base，incoming)中有路由需要對鄰居廣播，若對鄰居的信任度大于θ，則對其進(jìn)行路由廣播，否則不廣播.

3 試驗(yàn)仿真

采用網(wǎng)絡(luò)仿真工具SSFNET對域間路由機(jī)制進(jìn)行評估，網(wǎng)絡(luò)測試拓?fù)溆删W(wǎng)絡(luò)拓?fù)渖善鰾RITE產(chǎn)生，其中每個(gè)節(jié)點(diǎn)代表一個(gè) AS.默認(rèn)信任參數(shù)設(shè)為:α=0.6，β=0.7，θ=0.6.文中配置了一個(gè)38節(jié)點(diǎn)的網(wǎng)絡(luò)拓?fù)?為了考察N－BGP抑制虛假路由的能力，用抑制率作為協(xié)議性能指標(biāo)，抑制率是指當(dāng)BGP收斂后，網(wǎng)絡(luò)中被抑制掉的虛假路由數(shù)目與總的虛假路由數(shù)目之比，抑制率越大，說明虛假路由抑制效果越好.

在BGP運(yùn)行之初，將BGP路由總數(shù)的10%作為虛假路由注入網(wǎng)絡(luò)中，并配置3%，5%，8%，11%，13%的節(jié)點(diǎn)為惡意節(jié)點(diǎn)發(fā)布虛假路由，分別考察BGP和N－BGP抑制虛假路由的能力，結(jié)果如圖1所示.由圖1可以看出，隨著網(wǎng)惡意節(jié)點(diǎn)比例的增加，網(wǎng)絡(luò)對虛假路由的抑制能力在逐步下降，這說明網(wǎng)絡(luò)中惡意節(jié)點(diǎn)越多就越難以防范，而BGP中的虛假路由會一直存在，因?yàn)槠錄]有抑制虛假路由的能力.

為了考察不同信任參數(shù)對網(wǎng)絡(luò)抑制率的影響，分別對α，β，θ進(jìn)行考察，當(dāng)考察其中一個(gè)參數(shù)時(shí)，另2個(gè)設(shè)定為默認(rèn)值，結(jié)果如圖2所示.由圖2可以看出，α對抑制率的影響不是很大;而隨著β的增大，即對惡意節(jié)點(diǎn)的懲罰力度減小，網(wǎng)絡(luò)抑制率迅速減小;對于θ，隨著其增大，網(wǎng)絡(luò)抑制率也增大，因?yàn)閻阂夤?jié)點(diǎn)的信任度一旦小于θ，則其宣告的虛假路由就被過濾掉了，因而閾值θ越大，抑制率越高，但過大不利于BGP的收斂.根據(jù)試驗(yàn)結(jié)果，信任度參數(shù)一般在區(qū)間(0.5，0.7)中選取較為適宜.

圖1 抑制率Fig.1 Inhibition rate

圖2 參數(shù)對抑制率的影響Fig.2 The influence of parameters on the inhibition rate

4 結(jié)束語

根據(jù)社會行為中的信任關(guān)系設(shè)計(jì)了一種基于節(jié)點(diǎn)信任度的域間路由機(jī)制，該機(jī)制根據(jù)節(jié)點(diǎn)歷史的交互數(shù)據(jù)，由貝葉斯統(tǒng)計(jì)計(jì)算出節(jié)點(diǎn)對鄰居節(jié)點(diǎn)的信任度，從而根據(jù)節(jié)點(diǎn)信任度計(jì)算出路徑的信任度，并根據(jù)路徑信任度的大小選擇其中最優(yōu)的路徑.由于節(jié)點(diǎn)信任度的計(jì)算為分布式計(jì)算，因而計(jì)算簡單，計(jì)算代價(jià)小，且節(jié)點(diǎn)只需要維護(hù)鄰居節(jié)點(diǎn)的信任度，因而可進(jìn)行增量式部署，具有良好的可擴(kuò)展性.最后試驗(yàn)結(jié)果表明，擴(kuò)展后的BGP協(xié)議能夠有效抑制虛假路由的傳播.

［1］Rekhter Y，Li T，Hares S.A border gateway protocol 4(BGP－4)［EB/OL］.(2006－03－01)［2013－03－06］https://datatracker.ietf.org/doc/rfc4271/?include_text=1.

［2］Murphy S.BGP security vulnerabilities analysis［EB/OL］.(2006 －03 －03)［2013 －03 －06］https://datatracker.ietf.org/doc/rfc4272/?include_text=1.

［3］AT＆T Labs.A survey of BGPsecurity［R］.San Antonio:AT＆T Labs，2005.

［4］Kent S，Lynn C，Seo K.Secure border gateway protocol(S － BGP)［J］.IEEE Journal on Selected Areas in Commun-ications，2000，18(4):582 －592.

［5］White R.Securing BGP through secure origin BGP［J］.The Internet Protocol Journal，2003，6(3):15 －22.

［6］Wan T，Kranakis E，Oorschot PC.On inter－ domain routing security and pretty secure BGP(psBGP)［J］.ACM Transactions on Information and System Security(TISSEC)，2007，10(3):1 －41.

［7］胡寧，鄒鵬，朱培棟.基于域間信譽(yù)機(jī)制的路由安全協(xié)同管理方法［J］.軟件學(xué)報(bào)，2010，21(3):505－515.

［8］譚晶，羅軍舟，李偉，于楓.基于可信度的域間路由機(jī)制［J］.計(jì)算機(jī)學(xué)報(bào)，2010，33(9):1763－1773.

［9］University of Oxford.Can we trust trust［R］.Oxford:University of Oxford，2000.

［10］Siganos G，F(xiàn)aloutsos M.Analyzing BGPpolicies:Methodology and tool［C］∥The 23rdAnnual joint Conference of the IEEE Computer and Communications Societies.Hong Kong:IEEE，2004:1640 －1651.

［11］茆詩松.貝葉斯統(tǒng)計(jì)［M］.北京:中國統(tǒng)計(jì)出版社，1999:35－71.

［12］Carleton University.Secure routing protocols using consistency checks and S － RIP［R］.Ottawa:Carleton University，2003.