1地址解析的兩個相關問題研究

宋廣佳 季振洲

摘 要：地址解析協(xié)議由于缺少認證機制而容易受到攻擊，比如中間人攻擊，DoS攻擊等，

因此其安全問題長久以來一直受到人們的關注。本文對地址解析有關的兩個問題就行了研究.首先，證明了地址解析問題的不可判定性，這表明所有采用判定的方式來保障地址解析過程的方法都是不完美的；其次，證明了地址解析過程與重復地址檢測過程的等價性。這個結論表明地址解析過程與重復地址檢測過程可以互相替代，甚至由同一過程來完成，這將大大簡化地址解析協(xié)議的設計與實現(xiàn)。

關鍵詞：網(wǎng)絡安全；地址解析；重復地址檢測；不可判定；等價性

中圖分類號：TP393.1 文獻標識碼：A 文章編號：2095-2163（2015-）02-

Research on Two Problems related to Address Resolution

SONG Guangjia， JI Zhenzhou

（School of Computer Science and Technology， Harbin Institute of Technology， Harbin 150001， China）

Abstract：Given the lack of authentication mechanisms， the address resolution protocols （ARPs） （address resolution protocol， neighbor discovery protocol， and so on） are vulnerable to attack， such as man in the middle and denial of service among others. Therefore， the safety problem of the address resolution （AR） has been significantly given focus， and， in this paper， two problems related to AR have been investigated. First， the indecisiveness of the AR is proven. Therefore， all decision methods adopted to ensure the AR are imperfect； second， the equivalence between the AR and the duplicate address detection （DAD） process is proven. Thus， the AR and the DAD process can be replaced by each other， and can even be completed by the same process which will significantly simplify the design and implementation of the ARPs.

Keywords：Network Security； Address Resolution； Duplicate Address Detection； Undecidable Problem； Equality

0引 言

現(xiàn)有的網(wǎng)絡體系結構是分層的，因為計算機網(wǎng)絡的目的是進行信息交換，而交換兩端的計算機可能是完全不同的，比如使用不同的硬件結構，不同的操作系統(tǒng)，采用不同的文件格式。因此雙方在通信時必須要達成一致，并且還需進行一系列的格式轉換等。這就要求在通信過程中雙方達到高度的協(xié)調(diào)，而這樣的協(xié)調(diào)顯然是一個龐大而且復雜的問題。分層的方法是處理這種問題的有效手段，即將一個大而且復雜的問題劃分成多個簡單的容易處理的問題，每一層專注處理本層的問題[1]。

比如典型的5層體系結構：物理層（layer 1）、數(shù)據(jù)鏈路層（layer 2）、網(wǎng)絡層（layer 3）、傳輸層（layer 4）、應用層（layer 5），OSI體系結構則為7層。為進行網(wǎng)絡數(shù)據(jù)交換，人們制定了一系列標準、約定與規(guī)則，即網(wǎng)絡協(xié)議。既然網(wǎng)絡分成了多個層次，則每一層只需完成兩個主要任務即可，即如何與對端的對等層進行信息交換；為上層提供服務，從而簡化了網(wǎng)絡協(xié)議的設計。

1地址映射的不可判定性

1.1 通信屬性與地址解析

真正在進行信息交換的是主機中運行的進程。在進行交換時，數(shù)據(jù)在每層都要進行封裝然后再發(fā)送給下一層。目的主機在收到這個經(jīng)過多次封裝的數(shù)據(jù)后，每一層都要進行解封，讀取對本層有意義的信息，然后將數(shù)據(jù)交給上一次，最后交給對應的進程。圖1描述了進程p1與p2之間的數(shù)據(jù)交換。

圖1 進程間的數(shù)據(jù)交換過程

Fig.1 Data exchange between the processes

發(fā)送出去的信息必須要有明確的接收地址，因此在網(wǎng)絡中，每一層都要有自己的通信標識，用來唯一標識接收信息的實體，比如傳輸層，要考慮對端是哪個進程接收數(shù)據(jù)，而網(wǎng)絡層則考慮哪個主機接收這個數(shù)據(jù)，而數(shù)據(jù)鏈路層則考慮將數(shù)據(jù)發(fā)送至哪個接口（MAC）。這里，即將這種標識稱為通信屬性，定義如下：

通信屬性：在網(wǎng)絡中能夠唯一標識接收信息實體的屬性。

這里的實體指的是進程、主機、接口等。比如在傳輸層中，可以視為進程的通信屬性[2]；在網(wǎng)絡層，IP可以視為主機通信屬性[3]；在數(shù)據(jù)鏈路層，MAC可以視為網(wǎng)卡的通信屬性[4-5]。

由于各個層采用的是不同的通信屬性，因此在進行信息傳輸時，各層的通信屬性之間要有明確的對應關系。比如在三層與二層之間。三層在數(shù)據(jù)包頭部填入目的IP地址后交至二層，而二層需要知道目的MAC地址才能發(fā)送數(shù)據(jù)，因此對于主機來說，IP地址與MAC地址之間必須要有明確的對應關系，否則二層協(xié)議將無法正常工作。如何由一個IP地址獲得其對應的MAC地址呢？這個過程由地址解析協(xié)議來完成。

描述如下：主機要與一個IP地址進行通信時，假設該地址為IPY，主機自身的地址為IPX。如果IPX與主機自身的IP地址不在同一個地址段，則將數(shù)據(jù)包發(fā)送至默認網(wǎng)關[6]；如果IPY與IPX屬于同一個地址段，則檢查地址緩存；進一步地，如果緩存中有IPY的MAC地址，將直接發(fā)送數(shù)據(jù)，如果沒有就會發(fā)起一次廣播，請求擁有IPY的主機進行應答，回復其MAC地址。同一個LAN內(nèi)的主機都可以收到該廣播，如果IPY存在，則會進行一次應答，其他主機則保持沉默[4-5]。

1.2地址映射的不可判定性

地址解析在IPv4中是用ARP協(xié)議來完成，在IPv6中使用鄰居發(fā)現(xiàn)協(xié)議來完成，ND協(xié)議在功能上對ARP進行了擴展，鄰居發(fā)現(xiàn)協(xié)議還提供了前綴發(fā)現(xiàn)、鄰居不可達檢測、重復地址檢測、無狀態(tài)地址自動配置等功能。地址解析過程存在的主要問題是安全，因為地址解析協(xié)議設計過程是以效率優(yōu)先，而沒有去考慮安全威脅。但在實際應用中，安全是一個不可忽略的問題。因為地址解析要解決的就是二層與三層通行屬性對應問題，有關對應問題的主要攻擊手段是冒充，即發(fā)送虛假的對應關系。比如中間人攻擊，但主機A對IPY（主機B）進行解析時，主機C進行了應答，比如而主機A對這種應答是無法分辨真假的，只能接受。比如典型的中間人攻擊，或者DoS攻擊等[7]，這兩種攻擊都能給局域網(wǎng)造成巨大的威脅[8]。

針對欺騙攻擊，很多學者展開了研究。文獻[9]與文獻[10]使用入侵檢測系統(tǒng)中的離散事件系統(tǒng)（discrete event system， DES）對LAN中所有的ARP報文進行監(jiān)聽，如果發(fā)現(xiàn)有ARP 請求出現(xiàn)，則使用active probe報文對發(fā)送請求的原地址進行解析，然后根據(jù)探索的結果來判斷是否存在欺騙。因為如果有欺騙行為出現(xiàn)，DES會收到一個以上的應答，導致事件時序上與正常情況下不同。文獻[11]與文獻[12]同樣是對收到的ARP報文，尤其是廣播的ARP報文并不直接信任，而是采用ICMP報文進行逆向探索，即利用ICMP echo request報文測試發(fā)包的源地址是否是真實的，再根據(jù)測試結果決定是否信任。

Gouda等人提出了一種新的地址解析架構，包括一個安全的服務器和兩種新協(xié)議：邀請-接受和請求-應答。其中，邀請-接受協(xié)議用于主機向安全服務器注冊其地址映射，而請求-應答協(xié)議則用于主機向安全服務器請求局域網(wǎng)中其他主機的MAC地址[13]。Brushi等人提出的S-ARP協(xié)議是一種ARP的改進方案，該方法主要利用非對稱加密技術來對ARP報文進行認證，以防止ARP欺騙，該協(xié)議需要在網(wǎng)絡中部署一個權威密鑰分發(fā)服務器（authoritative key distribution，AKD），用來存放局域網(wǎng)中每臺主機的IP地址和公鑰。運行S-ARP協(xié)議的主機需要連接到AKD服務器獲得發(fā)送ARP報文主機的公鑰，對收到的ARP報文進行驗證，主機也可以緩存公鑰以提高速度[14]。Issac等人提出了一種與DHCP協(xié)議相結合的單播ARP協(xié)議（S-UARP）[15]，這種方法是利用DHCP服務器，并對其進行擴展使其支持地址解析。

還有學者提出了源地址驗證技術（source address validation architecture，SAVA），其主要思想是根據(jù)數(shù)據(jù)包中的源地址信息對其進行過濾，這樣做的好處是一方面可以從源頭直接阻止攻擊，另一方面是便于源地址的追蹤、溯源以及網(wǎng)絡診斷與管理[16-17]。

綜合以上研究表明，采用對網(wǎng)絡中的地址解析報文進行監(jiān)視判定-過濾的方式在很大程度上增強了地址解析安全性，但也存在一些問題，比如誤判率。是否有一個系統(tǒng)可以判定任何一個給定的對應是否合法呢？下面將證明不存在這樣的系統(tǒng)，也即對應是否合法是一個不可判定的問題。

前提條件：

（1）在網(wǎng)絡中，網(wǎng)卡的MAC地址是不重復的。

（2）如果一個映射w=在網(wǎng)絡中不存在，即沒有主機配置了這個映射，則w是非法的。

證明：

假設存在算法p可以判定每個映射w=合法性，那么任取一個映射w=作為輸入，如果p輸出為false，即w非法的，如果p輸出為true，表示w是合法的。作如下操作：

首先在網(wǎng)絡中隨機地選擇一臺主機Z，確保其IP地址不與其他節(jié)點沖突，然后記錄其映射為w=。而后將w作為p的輸入，觀察p的輸出結果，如果p輸出false，那么這顯然是錯誤的，因為w是一臺真實主機擁有的映射。如果p輸出是true，則可將主機Z徹底粉碎掉。為此網(wǎng)絡中將不再存在w這個映射（因為MAC是不重復的），也即w應該是非法的。

由于p是一個算法，所以對于固定的輸入w，只能輸出一個固定的結果，而此一結果隨時可能與事實不符合。這就可以判定任意w是否合法的p是不存在的。以上結論表明，任何企圖對地址映射進行判定的系統(tǒng)都是不完美的。

2重復地址檢測與地址解析過程的等價性

地址解析協(xié)議一般由三部分組成：

（1）地址解析過程：解析一個IP地址對應的MAC地址的過程。

（2）重復地址檢測過程：每當節(jié)點配置一個IP地址后，檢測該地址是否與其他節(jié)點地址沖突。

（3）數(shù)據(jù)維持階段：維持主機的地址緩存，對地址條目的新建、刪除、更新等。

直觀上看，如果主機A對網(wǎng)絡地址IPB進行解析，如果收到一個應答，則意味著存在一個主機B，其地址映射為，除此之外，如果主機進行重復地址檢測，檢測的目的地址是IPB，那么主機B也會進行應答，告訴A地址沖突。由此可見重復地址檢測與地址解析具有某種程度上的等價性，下面將證明這種等價性。

基本假設：

（1）網(wǎng)絡上的節(jié)點都是誠實的，即不會出現(xiàn)虛假的地址解析報文；

（2）網(wǎng)絡通信是可靠的，即不會發(fā)生數(shù)據(jù)包丟失現(xiàn)象；

（3）主機A與主機B在同一LAN內(nèi)，LAN內(nèi)的IP地址，MAC地址都是不重復的。

定理1：主機A對IPX進行地址解析有應答的充分必要條件是存在一個主機B，其地址為IPX。

證明：

命題L：主機A對IPX進行地址解析有應答

命題M：存在一個主機B，其地址映射為IPx

命題N：主機A對IPX進行重復地址檢測有應答

充分性，由地址解析過程的定義，如果主機A對IPX進行地址解析有應答，說明地址解析成功了，表明同一個LAN存在一臺主機B，擁有地址IPX，L。

必要性，如果在LAN內(nèi)有主機B，其地址為IPX，根據(jù)地址解析定義，如果主機A在進行地址解析時，而且解析的目的地址是IPX，則B必然會進行應答，根據(jù)假設2，主機A必然會收到這個應答，即。

所以有，證明完畢。

定理2：主機A對IPX進行重復地址檢測有應答的充分必要條件是存在一個主機B，其地址映射為IPX。

充分性，由重復地址檢測過程的定義，如果主機A對IPX進行重復地址檢測有應答，表明地址有沖突，即同一個LAN存在一臺主機B，擁有地址IPX，即。

必要性，如果在LAN內(nèi)有主機B，其地址為IPX，根據(jù)重復地址檢測過程的定義，如果主機A在重復地址檢測時，并且檢測的目的地址是IPX，則B必然會進行應答，根據(jù)假設2，主機A必然會收到這個應答，即。

所以有，證明完畢。

因為，且，所以有，因此有定理3成立。

定理3：主機A對IPX進行重復地址檢測有應答的充分必要條件是主機A對IPX進行重復地址檢測有應答。

定理4：主機A對IPX進行重復地址檢測有應答等價于主機A對IPX進行重復地址檢測有應答。

證明：觀察真值表1，當L為T時，表明解析IPX有主機應答，那么對IPX進行重復地址檢測也必然有應答，即N不可能為F，否則將與重復地址檢測過程的定義以及基本假設矛盾。同理，N為F時，意味著對IPX進行重復地址檢測時沒有收到應答，也即網(wǎng)絡中不存在一臺主機擁有地址IPX，那么對IPX解析也不會收到應答，即L不可能為T。所以，真值表中的第二行以及第三行的真值指派不會出現(xiàn)，也即的值始終為T，為永真式，從而。

表1 真值表

Tab.1 Truth table

L

N

1

T

T

T

2

T

F

F

3

F

T

F

4

F

F

T

至此，可以說地址解析過程與重復地址檢測過程具有等價性。而且定理4也進一步表明，地址解析過程與DAD過程可以互相替代，也可以由一個過程來完成。比如主機要對地址IPX進行地址解析，主機可以發(fā)起DAD檢測IPX在網(wǎng)絡上是否沖突，如果有應答，那么應答的主機就是擁有地址IPX的主機，地址解析也隨之而宣告完成。同樣，要檢測一個地址IPX是否重復，可以發(fā)起對該地址的解析，如果解析過程有應答，則表明IPX地址在網(wǎng)絡上是重復的。

比如在移動IP中，節(jié)點是可以自用移動的，每當一個移動節(jié)點移動到一個外界網(wǎng)絡（visit network）時，為了繼續(xù)保持與外界的通信，移動節(jié)點可以根據(jù)新路由器RA（router advertisement）公告中的前綴信息配置一個屬于visit network的新地址，即轉交地址（care of address），而新的地址需要經(jīng)過DAD后才能使用。由于DAD需要約1秒的時間，這種延遲對于很多實時性較高的通信是難以接受的，所以很多文獻提出了如何實現(xiàn)快速切換（hand over）的方法[18-20]。且有定理表明，在具體的網(wǎng)絡中，如果地址解析過程需要的時間少于DAD需要的時間，那么可以用地址解析過程代替DAD；如果有可以縮短DAD所需時間的方法，那么也可以將其用到地址解析過程中。

現(xiàn)有的網(wǎng)絡體系中，地址解析過程與重復地址檢測過程都是分開描述的，采用不同的包格式，比如RFC5227 ACD協(xié)議[21]。定理4提出這種情況可以大為簡化，就是使用一個協(xié)議進行描述，采用一種實現(xiàn)方法即可達成目的，比如將地址解析與重復地址檢測統(tǒng)稱為地址探測過程。

3結束語

地址解析過程與重復地址檢測過程容易受到攻擊的原因在于檢測目的地址的暴露，目前現(xiàn)有的檢測方式都是將檢測的目的地址以廣播（多播）的方式進行公開，所有的節(jié)點（包括惡意節(jié)點）都能收到，因此惡意的節(jié)點可以很容易地進行攻擊。采用判定、認證等方法雖然可以大幅提升地址解析的安全性，但地址映射的不可判定性表明，這種方法是不完善的。除此之外，這也給出了一個提示，就是如果地址映射是可以判定的，那么也就不需要地址解析過程了，因為給定一個IP地址，主機只要對所有可能與該IP匹配的MAC地址一一進行判定即可，直至找到一個合法的地址映射。地址解析過程與重復地址檢測過程的等價性表明，在下一代網(wǎng)絡中，地址解析協(xié)議的設計將得到簡化，設計安全協(xié)議的方式來提升地址解析過程與重復地址檢測的安全性，安全的鄰居發(fā)現(xiàn)協(xié)議就是一個很好的開端[22]。

參考文獻：

[1] Fall K R， Stevens W R. TCP/IP Illustrated， Volume 1： The Protocols[M]. Addison-Wesley， 2011.

[2] GOLDWASSER， SHAFI， MICALI S. Probabilistic encryption[J]. Journal of computer and system sciences，1984， 28（2） ： 270-299.

[3] DEERING S， HINDEN R. RFC 2460： Internet Protocol， Version 6 （IPv6） Specification （1998）[J]. URL： http：//www. ietf. org/rfc/rfc2460. txt， 2006.

[4] PLUMMER D. Ethernet address resolution protocol： Or converting network protocol addresses to 48. bit Ethernet address for transmission on Ethernet hardware[J]. RFC826，1982.

[5] NARTEN T， NORDMARK E， SIMPSON W， et al. RFC 4861-Neighbor discovery for IP version 6 （IPv6）， 2007[J]. URL http：//www. ietf. org/rfc/rfc4861. txt. Updated by RFC， 2011， 5942.

[6] Matsumoto A， Fujisaki T， Hiromi R. K. Kanayama，" Problem Statement for Default Address Selection in Multi-Prefix Environments： Operational Issues of RFC 3484 Default Rules[R]. RFC 5220， July， 2008.

[7] NIKANDER P， KEMPF J， NORDMARK E. IPv6 neighbor discovery （ND） trust models and threats[J]. RFC3756， Internet Engineering Task Force， 2004， 99.

[8] JINHUA G， KEJIAN X. ARP spoofing detection algorithm using ICMP protocol[C]//Computer Communication and Informatics （ICCCI）， 2013 International Conference on. Coimbatore， INDIA：IEEE， 2013： 1-6.

[9] BARBHUIYA， FERDOUS A.， BISWAS S， et al. An active des based ids for arp spoofing[C]//Systems， Man， and Cybernetics （SMC）， 2011 IEEE International Conference on. Alaska，USA：IEEE， 2011.

[10] NEMINATH H， BISWAS S， ROOPA S， et al. A DES approach to intrusion detection system for ARP spoofing attacks[C]//Control & Automation （MED）， 2010 18th Mediterranean Conference on.Marrakech， Morocco： IEEE， 2010： 695-700.

[11] PANDEY P. Prevention of ARP spoofing： A probe packet based technique[C]//Advance Computing Conference （IACC）， 2013 IEEE 3rd International. AKGEC， India：IEEE， 2013： 147-153.

[12] GOUDA M G， HUANG C T. A secure address resolution protocol[J]. Computer Networks， 2003， 41（1）： 57-71.

[13] BRUSCHI D， ORNAGHI A， ROSTIi E. S-ARP： a secure address resolution protocol[C]//Computer Security Applications Conference， 2003. Proceedings. 19th Annual. Las Vegas， NV， USA：IEEE， 2003： 66-74.

[14] ISSAC B， MOHAMMED L A. Secure unicast address resolution protocol （S-UARP） by extending DHCP[C]//Networks， 2005. Jointly held with the 2005 IEEE 7th Malaysia International Conference on Communication.， 2005 13th IEEE International Conference on.[S.l.]： IEEE， 2005， 1-6.

[15] WU J， BI J， LI X， et al. Rfc5210： A source address validation architecture （sava） testbed and deployment experience[J]. 2008.

[16] WU J， REN G， LI X. Source address validation： Architecture and protocol design[C]//Network Protocols， 2007. ICNP 2007. IEEE International Conference on. Beijing， China： IEEE， 2007： 276-283.

[17] LI Z， LI L， HUANG Y. Research on handover in hierarchical mobile IPv6 based on the fast DAD mechanism in visual domain[C]//Computer Science and Computational Technology， 2008. ISCSCT'08. International Symposium on. Shanghai， China： IEEE， 2008， 2： 277-280.

[18] TSENG C C， WONG Y C， YEN L H， et al. Proactive dad： A fast address-acquisition strategy for mobile ipv6 networks[J]. Internet Computing， IEEE， 2006， 10（6）： 50-55.

[19] HONG Y， PAWLIKOWSKI K， SIRISENA H. DAD-Less MIPv6 for Reduced Handover Latency[C]//Innovative Mobile and Internet Services in Ubiquitous Computing （IMIS）， 2011 Fifth International Conference on.[S.l.]： IEEE， 2011： 353-360.

[20] 陳魏鑫， 韓國棟， 劉洪波， 等. 基于快速 DAD 的分層移動 IPv6 切換算法[J]. 通信學報， 2008， 29（1）： 115-120.

[21] Cheshire S. IPv4 Address conflict detection[J]. RFC5227，2008.

[22] Arkko J， Kempf J， Zill B， et al. Secure neighbor discovery （SEND）[R]. RFC 3971， March， 2005.

1 基金項目：國家自然科學基金（61173024）。

作者簡介：宋廣佳（1981-），男，黑龍江哈爾濱人，博士研究生，主要研究方向：網(wǎng)絡安全、IPv6技術、學術信譽評價；

季振洲（1965-），男，黑龍江哈爾濱人，博士，教授，博士生導師，主要研究方向：先進系統(tǒng)結構、并行計算、網(wǎng)絡QoS、網(wǎng)絡安全等。