安春林,馬 迪,王 偉2,,毛 偉2,

1(中國(guó)科學(xué)院 計(jì)算機(jī)網(wǎng)絡(luò)信息中心,北京 100190)

2(中國(guó)科學(xué)院大學(xué),北京 100190)

3(互聯(lián)網(wǎng)域名系統(tǒng)北京市工程研究中心,北京 100190)

RPKI是一種用于保障互聯(lián)網(wǎng)基礎(chǔ)碼號(hào)資源(包含IP地址,AS號(hào))安全使用的公鑰基礎(chǔ)設(shè)施[1].通過(guò)對(duì)X.509公鑰證書進(jìn)行擴(kuò)展,RPKI依托資源證書實(shí)現(xiàn)了對(duì)互聯(lián)網(wǎng)基礎(chǔ)碼號(hào)資源使用授權(quán)的認(rèn)證,并以路由源聲明(Route Origin Authorization,ROA)的形式幫助域間路由系統(tǒng),驗(yàn)證某個(gè)AS針對(duì)特定IP地址前綴的路由通告是否合法[2].

RPKI體系可以分為三個(gè)組成部件:認(rèn)證權(quán)威(Certificate Authority,CA)、依賴方(Relying Party,RP)和資料庫(kù)(Repository).分別負(fù)責(zé)簽發(fā)、驗(yàn)證、存儲(chǔ)各類數(shù)字對(duì)象(包括各種簽名對(duì)象和證書)來(lái)彼此協(xié)作,共同完成RPKI的功能;其中CA簽發(fā)的各類簽名對(duì)象分為資源證書(Resource Certificate,RC)、ROAs[3]、Manifests[4]、Ghostbusters[5].資料庫(kù)負(fù)責(zé)收集保存所有的簽名對(duì)象,同時(shí)當(dāng)有新的簽名對(duì)象被創(chuàng)建時(shí)也要上傳到資料庫(kù),以供全球RPs同步下載[6].RP負(fù)責(zé)從資料庫(kù)中同步下載資源證書和簽名對(duì)象,并驗(yàn)證資源證書和簽名對(duì)象的有效性,而后將有效的ROA處理成IP地址塊和AS號(hào)的真實(shí)授權(quán)關(guān)系,用于指導(dǎo)BGP路由.

同時(shí),RP端作為同步和驗(yàn)證INR分配/授權(quán)關(guān)系與實(shí)際BGP路由之前溝通的橋梁,RP的運(yùn)行效率影響著整個(gè)RPKI體系的效率.針對(duì)RP同步簽名對(duì)象的效率研究,有htsync[7]和Delta協(xié)議[8].目前RPKI體系中的RP在驗(yàn)證證書的過(guò)程中,將已經(jīng)處理過(guò)的證書信息保存到數(shù)據(jù)庫(kù)中,而后在驗(yàn)證當(dāng)前證書的時(shí)候,通過(guò)循環(huán)查詢數(shù)據(jù)庫(kù)來(lái)完成當(dāng)前證書到信任錨點(diǎn)(Trust anchor,TA)的證書鏈的構(gòu)建,并將構(gòu)建好的證書鏈交由OpenSSL處理來(lái)完成整個(gè)驗(yàn)證證書的過(guò)程[9].因此數(shù)據(jù)庫(kù)查詢的操作影響著整個(gè)驗(yàn)證證書過(guò)程的效率.

在常用的PKI身份認(rèn)證中,計(jì)算代價(jià)由終端用戶負(fù)載.如圖1,在訪問(wèn)https網(wǎng)站的過(guò)程中,首先目標(biāo)網(wǎng)站(https://a.com)會(huì)將向CA(如CA1)申請(qǐng)的證書a.cer發(fā)送給終端用戶,然后終端用戶會(huì)通過(guò)本地保存的CA1.cer(通常由系統(tǒng)內(nèi)置)來(lái)驗(yàn)證a.cer的有效性,以此來(lái)驗(yàn)證目標(biāo)網(wǎng)站的身份真實(shí)性.在此過(guò)程中,驗(yàn)證證書的計(jì)算代價(jià)由終端用戶(通常是瀏覽器)負(fù)擔(dān).

而在RPKI運(yùn)行機(jī)制中,終端用戶為BGP路由器,而為了減輕BGP路由器的負(fù)擔(dān),優(yōu)化效率,需要將證書驗(yàn)證的計(jì)算代價(jià)轉(zhuǎn)移.如圖2,RPKI將計(jì)算代價(jià)轉(zhuǎn)移到一個(gè)單獨(dú)的服務(wù)器(RP服務(wù)器),RP服務(wù)器負(fù)責(zé)同步資料庫(kù)和驗(yàn)證證書,而終端用戶(BGP路由器)只需要向RP服務(wù)器發(fā)起源驗(yàn)證請(qǐng)求并根據(jù)RP服務(wù)器返回的驗(yàn)證結(jié)果更新路由表即可,有效的減輕了BGP路由器的負(fù)擔(dān).

圖1 https驗(yàn)證過(guò)程

圖2 RPKI運(yùn)行機(jī)制

基于這種特點(diǎn),結(jié)合“空間換時(shí)間”的思想,針對(duì)RP服務(wù)器在構(gòu)建證書鏈?zhǔn)切什蛔愕膯?wèn)題,本文設(shè)計(jì)并實(shí)現(xiàn)了一種基于哈希表的RPKI證書驗(yàn)證優(yōu)化方法.通過(guò)將證書的主體標(biāo)識(shí)(subject)和簽發(fā)人標(biāo)識(shí)(issuer)當(dāng)作一個(gè)鍵值對(duì)(key-value)保存到哈希表中,來(lái)實(shí)現(xiàn)時(shí)間復(fù)雜度為O(1)的查詢操作.本文基于上述的原理,設(shè)計(jì)實(shí)現(xiàn)了構(gòu)建證書鏈的程序,并設(shè)計(jì)實(shí)驗(yàn)對(duì)比基于數(shù)據(jù)庫(kù)查詢和基于哈希表的性能.實(shí)驗(yàn)結(jié)果表明,與基于數(shù)據(jù)庫(kù)查詢的方法相比,基于哈希表的方法耗時(shí)更短,在當(dāng)前RPKI部署環(huán)境下,3種實(shí)驗(yàn)場(chǎng)景中,平均時(shí)間加速比分別為99.03%、98.45%和97.48%,有效的減少了構(gòu)建證書鏈的時(shí)間消耗.

1 背景

1.1 基于數(shù)據(jù)庫(kù)查詢的原理

現(xiàn)有RP端的實(shí)現(xiàn)(Relying Party Security Technology for Internet Routing,RPSTIR)中,構(gòu)建證書鏈采用的策略為數(shù)據(jù)庫(kù)查詢,假設(shè)當(dāng)前待驗(yàn)證證書A的主體標(biāo)識(shí)為A.subject、簽發(fā)人標(biāo)識(shí)為A.issuer、待驗(yàn)證證書鏈CTX,具體的過(guò)程如算法1.

?

上述過(guò)程為向上構(gòu)建證書鏈并驗(yàn)證自身的過(guò)程.

但是,在驗(yàn)證證書的過(guò)程中,證書加載的順序并非是嚴(yán)格的由上而下進(jìn)行,因此在完成向上構(gòu)建證書鏈并完成驗(yàn)證有效之后還需要向下構(gòu)建證書鏈并驗(yàn)證.過(guò)程與向上構(gòu)建證書鏈類似,假設(shè)當(dāng)前驗(yàn)證為有效的證書為A,具體過(guò)程如算法2.

1.2 基于數(shù)據(jù)庫(kù)查詢方法的弊端

數(shù)據(jù)庫(kù)是為了方便用戶或系統(tǒng)對(duì)數(shù)據(jù)進(jìn)行存儲(chǔ)和管理,但在構(gòu)建證書鏈的過(guò)程中需要頻繁的涉及到數(shù)據(jù)的查詢,并且還需要對(duì)前一次的查詢結(jié)果進(jìn)行遞歸查詢.而在這種情況下,數(shù)據(jù)庫(kù)查詢效率的弊端就會(huì)更加凸顯出來(lái).

截止2017年05月,RPKI全球部署率僅僅7.36%(如圖3),證書文件總量19897個(gè) (.cer文件,包括ROA等簽名對(duì)象中的EE證書).

整個(gè)RPKI證書體系又可以看作5個(gè)(5個(gè)RIR的TA證書為根)N叉樹,而經(jīng)過(guò)對(duì)數(shù)據(jù)庫(kù)中數(shù)據(jù)的分析,發(fā)現(xiàn)66.25%左右的證書處于整個(gè)證書樹的第3層(假設(shè)根為第0層),32.81%左右的證書處于證書樹的第2層.基于數(shù)據(jù)庫(kù)查詢的方法構(gòu)建證書鏈的原理是通過(guò)循環(huán)遍歷逐個(gè)向上查詢父證書,直到找到TA證書,因此整個(gè)RPKI體系中構(gòu)建證書鏈過(guò)程的時(shí)間復(fù)雜度可以近似為O(n4).如果RPKI在全球廣泛部署(部署率超過(guò)80%),則整個(gè)RPKI體系中證書文件量預(yù)計(jì)將會(huì)超過(guò)26萬(wàn)個(gè),此時(shí)構(gòu)建證書鏈的時(shí)間將會(huì)急劇增大,將會(huì)影響整個(gè)RP服務(wù)器運(yùn)行的效率.

圖3 RPKI全球部署情況

由此可以看出,由于證書驗(yàn)證過(guò)程的特殊性(需要逐層遞歸查詢),數(shù)據(jù)庫(kù)查詢的方法并不完全適合RPKI體系.

同時(shí),RPKI機(jī)制中的RP服務(wù)器相對(duì)于使用PKI的瀏覽器有更高的性能,因此可以使用犧牲空間換時(shí)間的方式優(yōu)化構(gòu)建證書鏈的過(guò)程.根據(jù)上述的原理,本文實(shí)現(xiàn)了一個(gè)基于哈希表的RPKI證書驗(yàn)證優(yōu)化方法.

2 基于哈希表的證書鏈構(gòu)造方法

哈希表是一種根據(jù)“鍵”來(lái)直接訪問(wèn)在內(nèi)存存儲(chǔ)位置的數(shù)據(jù)結(jié)構(gòu).也就是說(shuō),它通過(guò)計(jì)算一個(gè)關(guān)于鍵值的函數(shù),將所需查詢的數(shù)據(jù)映射到表中一個(gè)位置來(lái)訪問(wèn)記錄,這加快了查找速度.這個(gè)映射函數(shù)稱為散列函數(shù),存放記錄的數(shù)組稱作哈希表.

而在本文中,實(shí)驗(yàn)是基于Python實(shí)現(xiàn)的,使用的數(shù)據(jù)結(jié)構(gòu)即為Python中的哈希表—字典(Dictionary).

字典是Python中最常用的數(shù)據(jù)類型之一,它是一個(gè)鍵值對(duì)的集合,字典通過(guò)“鍵”來(lái)索引,關(guān)聯(lián)到相對(duì)的值,理論上它的查詢復(fù)雜度是O(1).因此,本文實(shí)現(xiàn)的基于哈希表的證書鏈構(gòu)造方法將會(huì)大大的減少耗時(shí),從而顯著的提高RP的效率.

2.1 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

在實(shí)際應(yīng)用場(chǎng)景下,數(shù)據(jù)結(jié)構(gòu)應(yīng)該包含證書的所有信息,并增加一個(gè)區(qū)別證書有效性的字段.在證書驗(yàn)證的過(guò)程中逐層的向上查找待驗(yàn)證證書的“有效父證書”,構(gòu)建一個(gè)完整的證書鏈,然后調(diào)用OpenSSL驗(yàn)證構(gòu)建的證書鏈的有效性.當(dāng)驗(yàn)證為有效后,遞歸查找所有“待驗(yàn)證子證書”,并驗(yàn)證其有效性.

由于本文主要針對(duì)構(gòu)建證書鏈的過(guò)程的優(yōu)化,所以為了排除調(diào)用OpenSSL驗(yàn)證證書鏈的時(shí)間消耗以及其他的干擾項(xiàng),特將證書驗(yàn)證的過(guò)程簡(jiǎn)化為逐層向上查找“父證書”而非“有效父證書”,直到查找到TA或者找不到“父證書”,然后遞歸查找所有“子證書”而非“待驗(yàn)證子證書”,直到查找失敗.也即盡可能的向上查找父證書和向下查找子證書,忽略證書的有效性和調(diào)用OpenSSL驗(yàn)證證書鏈的過(guò)程.

因此,數(shù)據(jù)結(jié)構(gòu)中只需要保存構(gòu)建證書鏈需要的信息,即證書的主題標(biāo)識(shí)subject和簽發(fā)人標(biāo)識(shí)issuer.而查找父證書和子證書的方法與基于數(shù)據(jù)庫(kù)查詢的方法相同.

考慮到驗(yàn)證證書不僅需要完成向上構(gòu)建證書鏈的過(guò)程,還需要完成向下構(gòu)建證書鏈,因此本文設(shè)計(jì)實(shí)現(xiàn)了兩個(gè)數(shù)據(jù)結(jié)構(gòu):chain_up和chain_down,分別用于向上和向下構(gòu)建證書鏈.

chain_up用來(lái)保存向上構(gòu)建證書鏈需要用到的信息.向上構(gòu)建證書鏈即為查找一條滿足B.subject=A.issuer條件的記錄(A為待驗(yàn)證證書),因此chain_up中的每條記錄的“鍵”為每個(gè)證書的主體標(biāo)識(shí)subject,“值”為對(duì)應(yīng)證書的簽發(fā)人標(biāo)識(shí)issuer.且由于每個(gè)證書的主體標(biāo)識(shí)具有唯一性,因此chain_up數(shù)據(jù)結(jié)構(gòu)中不存在“鍵”沖突的情況.

chain_down用來(lái)保存向下構(gòu)建證書鏈需要用到的信息.向下構(gòu)建證書鏈即為查找每一個(gè)滿足B.issuer=A.subject條件的記錄(A為待驗(yàn)證證書),因此chain_down中每條記錄的“鍵”為每個(gè)證書的簽發(fā)人標(biāo)識(shí)issuer.而由于父證書與子證書的對(duì)應(yīng)關(guān)系為1:N,所以存在一個(gè)“鍵”(issuer)對(duì)應(yīng)多個(gè)“值”(subject)的情況,所以“值”應(yīng)該為所有簽發(fā)人標(biāo)識(shí)issuer等于“鍵”的所有證書的主體標(biāo)識(shí)subject的數(shù)組集合.

假設(shè)證書結(jié)構(gòu)如圖4所示.

根據(jù)前文的描述,chain_up應(yīng)該如下所示:

{"A":"A","B":"A","C":"A","D":"B","E":"C","F":"C","G":"C"}

chain_down應(yīng)該如下所示:

{"A":["A","B","C"],"B":["D"],"C":["E","F","G"]}

圖4 證書結(jié)構(gòu)

2.2 向上構(gòu)建證書鏈

為了排除其他實(shí)驗(yàn)項(xiàng)對(duì)結(jié)論的影響,本文實(shí)驗(yàn)僅涉及證書鏈的構(gòu)建,并不對(duì)證書鏈進(jìn)行有效性驗(yàn)證.因此向上構(gòu)建證書鏈的算法只進(jìn)行逐層查找父證書的功能.

基于哈希表的向上構(gòu)建證書鏈算法如算法3.

算法3.哈希表向上構(gòu)建證書鏈輸入:RPKI資料庫(kù)證書文件A,chain_up文件(Json格式)1.令變量subject=A.subject,issuer=A.issuer.2.若subject=issuer,說(shuō)明已經(jīng)逐層向上找到根節(jié)點(diǎn),即TA證書,跳轉(zhuǎn)第6步;若subject!=issuer,繼續(xù)第3步.3.令subject=issuer,issuer=chain_up[issuer].4.若第3步出現(xiàn)錯(cuò)誤:KeyError,說(shuō)明在進(jìn)行chain_up[issuer]時(shí)出錯(cuò),表明當(dāng)前字典chain_up中沒有“鍵”=issuer的數(shù)據(jù),跳轉(zhuǎn)第6步.5.若第3步?jīng)]有錯(cuò)誤出現(xiàn),以在第3步中重新賦值的subject和issuer跳轉(zhuǎn)第2步.6.向字典chain_up中插入新數(shù)據(jù)chain_up[A.subject]=A.issuer;結(jié)束.

在程序的初始情況下,字典chain_up應(yīng)該為空,隨著程序的不斷執(zhí)行,在程序?qū)⑺械腞PKI資料庫(kù)中的證書文件全部遍歷完全之后,chain_up應(yīng)該包含每一個(gè)RPKI資料庫(kù)證書的主體標(biāo)識(shí)和簽發(fā)人標(biāo)識(shí).

由于Json文件的特性(鍵值對(duì)),且Python對(duì)Json文件的解析結(jié)果即為Python中的字典,因此在程序退出之前,應(yīng)該將最終的chain_up保存成Json文件,以供下一次使用.

2.3 向下構(gòu)建證書鏈

與向上構(gòu)建證書鏈類似,向下構(gòu)建證書鏈的算法也只實(shí)現(xiàn)循環(huán)遍歷所有子證書的功能.

基于哈希表的向下構(gòu)建證書鏈算法如算法4.

算法4.哈希表向下構(gòu)建證書鏈輸入:RPKI資料庫(kù)證書文件A,chain_down文件(Json格式存儲(chǔ))1.令變量subject=A.subject,issuer=A.issuer.2.令臨時(shí)變量subject_arrary=chain_down[subject],issuer=subject.3.若第2步出現(xiàn)錯(cuò)誤:KeyError,說(shuō)明在進(jìn)行chain_down[subject]時(shí)出錯(cuò),表示當(dāng)前字典chain_down中沒有“鍵”=subject的數(shù)據(jù),跳轉(zhuǎn)至第6步.

與向上構(gòu)建證書鏈類似,字典chain_down在初始情況下應(yīng)該為空,隨著程序的不斷進(jìn)行而不斷的填充數(shù)據(jù).在程序完成所有RPKI資料庫(kù)中證書文件的遍歷之后,chain_down應(yīng)該包含所有位于證書樹中的非葉子節(jié)點(diǎn)的證書的主體標(biāo)識(shí)和對(duì)應(yīng)的所有子證書的主體標(biāo)識(shí).

同樣,在程序退出之前應(yīng)該將字典chain_down保存成Json文件.

總的來(lái)說(shuō),本文實(shí)驗(yàn)分為兩大步驟:使用基于數(shù)據(jù)庫(kù)查詢的方法實(shí)現(xiàn)類似算法3和算法4的構(gòu)建證書鏈方法;使用基于哈希表的方法構(gòu)建證書鏈.

在基于數(shù)據(jù)庫(kù)查詢的方法中,首先遍歷整個(gè)RPKI資料庫(kù),并過(guò)濾出所有的證書文件.然后對(duì)每一個(gè)證書文件,使用 Python中的 OpenSSL庫(kù)pyOpenSSL解析文件,并提取出證書文件的主體標(biāo)識(shí)A.subject和簽發(fā)人標(biāo)識(shí)A.issuer.接著查詢數(shù)據(jù)庫(kù)中滿足條件B.subject=A.issuer的記錄,并遞歸查詢,完成向上構(gòu)建證書鏈的過(guò)程.然后查詢數(shù)據(jù)庫(kù)中滿足條件B.issuer=A.subject的所有子證書,并遞歸的對(duì)每一個(gè)子證書執(zhí)行向下構(gòu)建證書鏈的過(guò)程.

在基于哈希表的方法中,同樣先遍歷整個(gè)RPKI資料庫(kù),并過(guò)濾出所有證書文件,對(duì)每一個(gè)證書完成向上和向下構(gòu)建證書鏈的過(guò)程.

假設(shè)RPKI資料庫(kù)中證書文件的個(gè)數(shù)為N,且證書樹的結(jié)構(gòu)與當(dāng)下情況類似,如圖5.

證書最深層數(shù)為5,且有66.25%的證書處于證書樹的第3層(圖5中TA為1層).那么,構(gòu)建證書鏈的時(shí)間復(fù)雜度為:

N*(O(向上構(gòu)建)+O(向下構(gòu)建))

由于基于數(shù)據(jù)庫(kù)查詢的方法,每一次查找父證書或查找子證書都相當(dāng)于遍歷一次數(shù)據(jù)庫(kù)表,因此基于數(shù)據(jù)庫(kù)查詢的方法復(fù)雜度就近似為O(N*(N3+N2)),也即O(N4).而基于哈希表的方法,對(duì)于每一個(gè)查詢操作的復(fù)雜度在最優(yōu)情況下(所有的“鍵”的散列值均不同)為O(1),最差的情況下(所有的“鍵”的散列值都相同)為O(N).因此基于哈希表的方法,在最優(yōu)情況下的復(fù)雜度為O(N),最差情況下與基于數(shù)據(jù)庫(kù)查詢的方法相同,為O(N4).

圖5 RPKI證書結(jié)構(gòu)

3 實(shí)驗(yàn)分析

3.1 實(shí)驗(yàn)設(shè)計(jì)

RP服務(wù)器在驗(yàn)證RPKI資料庫(kù)中證書文件時(shí),可能存在三種場(chǎng)景:初始驗(yàn)證、增量驗(yàn)證和無(wú)更改驗(yàn)證.

初始驗(yàn)證:RP服務(wù)器在收到RPKI資料庫(kù)之后從無(wú)到有的驗(yàn)證每一個(gè)證書;

增量驗(yàn)證:RP服務(wù)器已經(jīng)完成RPKI資料庫(kù)中的證書的驗(yàn)證,此次驗(yàn)證時(shí)RPKI資料庫(kù)有新的證書文件;

無(wú)更改驗(yàn)證:RPKI資料庫(kù)沒有任何變化,重新完成一遍驗(yàn)證過(guò)程.

當(dāng)RP服務(wù)器第一次啟動(dòng)時(shí),RP服務(wù)器沒有任何RPKI資料庫(kù)文件,因此會(huì)發(fā)生“初始驗(yàn)證”,此時(shí)RP服務(wù)器的數(shù)據(jù)庫(kù)中也沒有任何數(shù)據(jù),哈希表chain_up和chain_down也為空,需要下載RPKI資料庫(kù)并完成驗(yàn)證;當(dāng)RPKI資料庫(kù)中有新的證書文件時(shí),RP服務(wù)器將會(huì)進(jìn)行“增量驗(yàn)證”,遍歷新的RPKI資料庫(kù),對(duì)新的證書文件進(jìn)行驗(yàn)證;當(dāng)RPKI資料庫(kù)沒有任何變動(dòng)的時(shí)候,RP服務(wù)器將會(huì)進(jìn)行“無(wú)更改驗(yàn)證”,此時(shí)RP服務(wù)器將會(huì)遍歷RPKI資料庫(kù),并檢查每一個(gè)證書是否已經(jīng)被記錄到數(shù)據(jù)庫(kù)或chain_up和chain_down中.

根據(jù)以上三種情況設(shè)計(jì)實(shí)驗(yàn)對(duì)比基于數(shù)據(jù)庫(kù)查詢和基于哈希表的時(shí)間消耗.實(shí)驗(yàn)環(huán)境如表1所示.實(shí)驗(yàn)數(shù)據(jù)來(lái)自全球RPKI資料庫(kù),實(shí)驗(yàn)數(shù)據(jù)截止到2017年5月9日,共19 897個(gè)證書文件.

表1 實(shí)驗(yàn)環(huán)境

3.2 實(shí)驗(yàn)結(jié)果

3.2.1 初始驗(yàn)證

設(shè)定RPKI資料庫(kù)大小分別為2000、5000、8000、11 000、14 000、17 000、19 897個(gè)證書文件.7種環(huán)境下的RP服務(wù)器中的已驗(yàn)證證書個(gè)數(shù)均為0.基于數(shù)據(jù)庫(kù)查詢(Database)和基于哈希表(Hash)的性能對(duì)比如表2所示.

表2 初始驗(yàn)證性能對(duì)比

可以看出,基于哈希表的方法在時(shí)間上明顯更少,且隨著證書文件個(gè)數(shù)的增多,時(shí)間加速比呈線性增大,也即證書文件越多,基于哈希表的方法就相對(duì)越有效.7種環(huán)境下的平均時(shí)間加速比為99.03%.

3.2.2 增量驗(yàn)證

設(shè)定RP服務(wù)器已驗(yàn)證的證書個(gè)數(shù)分別為2000、5000、8000、11 000、14 000、17 000 個(gè),在增量驗(yàn)證的實(shí)驗(yàn)中,RPKI資料庫(kù)發(fā)生更新,有新的證書文件,增量均為3000個(gè)(17000個(gè)文件的初始環(huán)境下的增量為2897個(gè)).基于數(shù)據(jù)庫(kù)查詢和基于哈希表的性能對(duì)比如表3所示.

表3 增量驗(yàn)證性能對(duì)比

可以看出,基于哈希表的方法仍然優(yōu)于基于數(shù)據(jù)庫(kù)查詢的方法,6種環(huán)境下的平均時(shí)間加速比為98.45%.

3.2.3 無(wú)更改驗(yàn)證

設(shè)定RP服務(wù)器的資料庫(kù)證書個(gè)數(shù)分別為2000、5000、8000、11 000、14 000、17 000和 19 897 個(gè)時(shí),RPKI資料庫(kù)未發(fā)生變化,RP服務(wù)器此時(shí)進(jìn)行無(wú)更改驗(yàn)證,僅需要對(duì)資料庫(kù)中的每一個(gè)證書文件進(jìn)行一次查詢是否存在于數(shù)據(jù)庫(kù)或chain_up和chain_down中即可.兩種方法的性能對(duì)比如表4所示.

表4 無(wú)更改驗(yàn)證性能對(duì)比

可以看出,基于哈希表的方法仍優(yōu)于基于數(shù)據(jù)庫(kù)查詢的方法,且加速比有隨著文件個(gè)數(shù)增大而增大的趨勢(shì).7種環(huán)境下的平均時(shí)間加速比為97.48%.

4 結(jié)語(yǔ)

針對(duì)RPKI中RP服務(wù)器使用基于數(shù)據(jù)庫(kù)查詢的方法進(jìn)行證書鏈構(gòu)建時(shí)效率低下的問(wèn)題,本文結(jié)合了RPKI運(yùn)行機(jī)制中將計(jì)算代價(jià)轉(zhuǎn)移至RP服務(wù)器的特點(diǎn)和“空間換時(shí)間”的思想,設(shè)計(jì)實(shí)現(xiàn)了一種基于哈希表的RPKI證書驗(yàn)證優(yōu)化方法,有效的提升RP服務(wù)器在驗(yàn)證證書時(shí)的性能.實(shí)驗(yàn)結(jié)果表明,與基于數(shù)據(jù)庫(kù)查詢的方法相比,基于哈希表的方法在構(gòu)建證書鏈時(shí)效率顯著提升,在設(shè)計(jì)的3種實(shí)驗(yàn)場(chǎng)景下,平均時(shí)間加速比分別為99.03%、98.45%和97.48%,有效的減少了驗(yàn)證證書的時(shí)間消耗.

1Phokeer AD.Interdomain routing security:Motivation and challenges of RPKI.Timss Technical Report RHUL-MA-2014-14,Egham,UK:Royal Holloway,University of London,2014.

2馬迪.RPKI概覽.電信網(wǎng)技術(shù),2012,(9):30-33.

3Lepinski M,Kent S,Kong D.RFC 6482:A profile for route origin authorizations (ROAs).IETF,2012.

4Austein R,Huston G,Kent S,et al.RFC 6486:Manifests for the resource public key infrastructure (RPKI).IETF,2012.

5Bush R.RFC 6493:The resource public key infrastructure(RPKI)ghostbusters record.IETF,2012.

6Huston G,Loomans R,Michaelson G.RFC 6481:A profile for resource certificate repository structure.IETF,2012.

7許圣明,馬迪,毛偉,等.基于有序哈希樹的RPKI資料庫(kù)數(shù)據(jù)同步方法.計(jì)算機(jī)系統(tǒng)應(yīng)用,2016,25(6):141-146.[doi:10.15888/j.cnki.csa.005203]

8Bruijnzeels T,Muravskiy O,Weber B,et al.Draft-ietf-sidrdelta-protocol,2014.

9Reynolds MC,Kent S.A high performance software architecture for a secure internet routing PKI.Proceedings of Cybersecurity Applications &Technology Conference for Homeland Security.Washington,DC,USA.2009.49-53.