1地址解析的两个相关问题研究

摘 要：地址解析协议由于缺少认证机制而容易受到攻击，比如中间人攻击，DoS攻击等，

因此其安全问题长久以来一直受到人们的关注。本文对地址解析有关的两个问题就行了研究.首先，证明了地址解析问题的不可判定性，这表明所有采用判定的方式来保障地址解析过程的方法都是不完美的；其次，证明了地址解析过程与重复地址检测过程的等价性。这个结论表明地址解析过程与重复地址检测过程可以互相替代，甚至由同一过程来完成，这将大大简化地址解析协议的设计与实现。

关键词：网络安全；地址解析；重复地址检测；不可判定；等价性

中图分类号：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引 言

现有的网络体系结构是分层的，因为计算机网络的目的是进行信息交换，而交换两端的计算机可能是完全不同的，比如使用不同的硬件结构，不同的操作系统，采用不同的文件格式。因此双方在通信时必须要达成一致，并且还需进行一系列的格式转换等。这就要求在通信过程中双方达到高度的协调，而这样的协调显然是一个庞大而且复杂的问题。分层的方法是处理这种问题的有效手段，即将一个大而且复杂的问题划分成多个简单的容易处理的问题，每一层专注处理本层的问题[1]。

比如典型的5层体系结构：物理层（layer 1）、数据链路层（layer 2）、网络层（layer 3）、传输层（layer 4）、应用层（layer 5），OSI体系结构则为7层。为进行网络数据交换，人们制定了一系列标准、约定与规则，即网络协议。既然网络分成了多个层次，则每一层只需完成两个主要任务即可，即如何与对端的对等层进行信息交换；为上层提供服务，从而简化了网络协议的设计。

1地址映射的不可判定性

1.1 通信属性与地址解析

真正在进行信息交换的是主机中运行的进程。在进行交换时，数据在每层都要进行封装然后再发送给下一层。目的主机在收到这个经过多次封装的数据后，每一层都要进行解封，读取对本层有意义的信息，然后将数据交给上一次，最后交给对应的进程。图1描述了进程p1与p2之间的数据交换。

图1 进程间的数据交换过程

Fig.1 Data exchange between the processes

发送出去的信息必须要有明确的接收地址，因此在网络中，每一层都要有自己的通信标识，用来唯一标识接收信息的实体，比如传输层，要考虑对端是哪个进程接收数据，而网络层则考虑哪个主机接收这个数据，而数据链路层则考虑将数据发送至哪个接口（MAC）。这里，即将这种标识称为通信属性，定义如下：

通信属性：在网络中能够唯一标识接收信息实体的属性。

这里的实体指的是进程、主机、接口等。比如在传输层中，可以视为进程的通信属性[2]；在网络层，IP可以视为主机通信属性[3]；在数据链路层，MAC可以视为网卡的通信属性[4-5]。

由于各个层采用的是不同的通信属性，因此在进行信息传输时，各层的通信属性之间要有明确的对应关系。比如在三层与二层之间。三层在数据包头部填入目的IP地址后交至二层，而二层需要知道目的MAC地址才能发送数据，因此对于主机来说，IP地址与MAC地址之间必须要有明确的对应关系，否则二层协议将无法正常工作。如何由一个IP地址获得其对应的MAC地址呢？这个过程由地址解析协议来完成。

描述如下：主机要与一个IP地址进行通信时，假设该地址为IPY，主机自身的地址为IPX。如果IPX与主机自身的IP地址不在同一个地址段，则将数据包发送至默认网关[6]；如果IPY与IPX属于同一个地址段，则检查地址缓存；进一步地，如果缓存中有IPY的MAC地址，将直接发送数据，如果没有就会发起一次广播，请求拥有IPY的主机进行应答，回复其MAC地址。同一个LAN内的主机都可以收到该广播，如果IPY存在，则会进行一次应答，其他主机则保持沉默[4-5]。

1.2地址映射的不可判定性

地址解析在IPv4中是用ARP协议来完成，在IPv6中使用邻居发现协议来完成，ND协议在功能上对ARP进行了扩展，邻居发现协议还提供了前缀发现、邻居不可达检测、重复地址检测、无状态地址自动配置等功能。地址解析过程存在的主要问题是安全，因为地址解析协议设计过程是以效率优先，而没有去考虑安全威胁。但在实际应用中，安全是一个不可忽略的问题。因为地址解析要解决的就是二层与三层通行属性对应问题，有关对应问题的主要攻击手段是冒充，即发送虚假的对应关系。比如中间人攻击，但主机A对IPY（主机B）进行解析时，主机C进行了应答，比如而主机A对这种应答是无法分辨真假的，只能接受。比如典型的中间人攻击，或者DoS攻击等[7]，这两种攻击都能给局域网造成巨大的威胁[8]。

针对欺骗攻击，很多学者展开了研究。文献[9]与文献[10]使用入侵检测系统中的离散事件系统（discrete event system， DES）对LAN中所有的ARP报文进行监听，如果发现有ARP 请求出现，则使用active probe报文对发送请求的原地址进行解析，然后根据探索的结果来判断是否存在欺骗。因为如果有欺骗行为出现，DES会收到一个以上的应答，导致事件时序上与正常情况下不同。文献[11]与文献[12]同样是对收到的ARP报文，尤其是广播的ARP报文并不直接信任，而是采用ICMP报文进行逆向探索，即利用ICMP echo request报文测试发包的源地址是否是真实的，再根据测试结果决定是否信任。

Gouda等人提出了一种新的地址解析架构，包括一个安全的服务器和两种新协议：邀请-接受和请求-应答。其中，邀请-接受协议用于主机向安全服务器注册其地址映射，而请求-应答协议则用于主机向安全服务器请求局域网中其他主机的MAC地址[13]。Brushi等人提出的S-ARP协议是一种ARP的改进方案，该方法主要利用非对称加密技术来对ARP报文进行认证，以防止ARP欺骗，该协议需要在网络中部署一个权威密钥分发服务器（authoritative key distribution，AKD），用来存放局域网中每台主机的IP地址和公钥。运行S-ARP协议的主机需要连接到AKD服务器获得发送ARP报文主机的公钥，对收到的ARP报文进行验证，主机也可以缓存公钥以提高速度[14]。Issac等人提出了一种与DHCP协议相结合的单播ARP协议（S-UARP）[15]，这种方法是利用DHCP服务器，并对其进行扩展使其支持地址解析。

还有学者提出了源地址验证技术（source address validation architecture，SAVA），其主要思想是根据数据包中的源地址信息对其进行过滤，这样做的好处是一方面可以从源头直接阻止攻击，另一方面是便于源地址的追踪、溯源以及网络诊断与管理[16-17]。

综合以上研究表明，采用对网络中的地址解析报文进行监视判定-过滤的方式在很大程度上增强了地址解析安全性，但也存在一些问题，比如误判率。是否有一个系统可以判定任何一个给定的对应是否合法呢？下面将证明不存在这样的系统，也即对应是否合法是一个不可判定的问题。

前提条件：

（1）在网络中，网卡的MAC地址是不重复的。

（2）如果一个映射w=在网络中不存在，即没有主机配置了这个映射，则w是非法的。

证明：

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

首先在网络中随机地选择一台主机Z，确保其IP地址不与其他节点冲突，然后记录其映射为w’=。而后将w’作为p的输入，观察p的输出结果，如果p输出false，那么这显然是错误的，因为w’是一台真实主机拥有的映射。如果p输出是true，则可将主机Z彻底粉碎掉。为此网络中将不再存在w’这个映射（因为MAC是不重复的），也即w’应该是非法的。

由于p是一个算法，所以对于固定的输入w，只能输出一个固定的结果，而此一结果随时可能与事实不符合。这就可以判定任意w是否合法的p是不存在的。以上结论表明，任何企图对地址映射进行判定的系统都是不完美的。

2重复地址检测与地址解析过程的等价性

地址解析协议一般由三部分组成：

（1）地址解析过程：解析一个IP地址对应的MAC地址的过程。

（2）重复地址检测过程：每当节点配置一个IP地址后，检测该地址是否与其他节点地址冲突。

（3）数据维持阶段：维持主机的地址缓存，对地址条目的新建、删除、更新等。

直观上看，如果主机A对网络地址IPB进行解析，如果收到一个应答，则意味着存在一个主机B，其地址映射为，除此之外，如果主机进行重复地址检测，检测的目的地址是IPB，那么主机B也会进行应答，告诉A地址冲突。由此可见重复地址检测与地址解析具有某种程度上的等价性，下面将证明这种等价性。

基本假设：

（1）网络上的节点都是诚实的，即不会出现虚假的地址解析报文；

（2）网络通信是可靠的，即不会发生数据包丢失现象；

（3）主机A与主机B在同一LAN内，LAN内的IP地址，MAC地址都是不重复的。

定理1：主机A对IPX进行地址解析有应答的充分必要条件是存在一个主机B，其地址为IPX。

证明：

命题L：主机A对IPX进行地址解析有应答

命题M：存在一个主机B，其地址映射为IPx

命题N：主机A对IPX进行重复地址检测有应答

充分性，由地址解析过程的定义，如果主机A对IPX进行地址解析有应答，说明地址解析成功了，表明同一个LAN存在一台主机B，拥有地址IPX，L。

必要性，如果在LAN内有主机B，其地址为IPX，根据地址解析定义，如果主机A在进行地址解析时，而且解析的目的地址是IPX，则B必然会进行应答，根据假设2，主机A必然会收到这个应答，即。

所以有，证明完毕。

定理2：主机A对IPX进行重复地址检测有应答的充分必要条件是存在一个主机B，其地址映射为IPX。

充分性，由重复地址检测过程的定义，如果主机A对IPX进行重复地址检测有应答，表明地址有冲突，即同一个LAN存在一台主机B，拥有地址IPX，即。

必要性，如果在LAN内有主机B，其地址为IPX，根据重复地址检测过程的定义，如果主机A在重复地址检测时，并且检测的目的地址是IPX，则B必然会进行应答，根据假设2，主机A必然会收到这个应答，即。

所以有，证明完毕。

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

定理3：主机A对IPX进行重复地址检测有应答的充分必要条件是主机A对IPX进行重复地址检测有应答。

定理4：主机A对IPX进行重复地址检测有应答等价于主机A对IPX进行重复地址检测有应答。

证明：观察真值表1，当L为T时，表明解析IPX有主机应答，那么对IPX进行重复地址检测也必然有应答，即N不可能为F，否则将与重复地址检测过程的定义以及基本假设矛盾。同理，N为F时，意味着对IPX进行重复地址检测时没有收到应答，也即网络中不存在一台主机拥有地址IPX，那么对IPX解析也不会收到应答，即L不可能为T。所以，真值表中的第二行以及第三行的真值指派不会出现，也即的值始终为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进行地址解析，主机可以发起DAD检测IPX在网络上是否冲突，如果有应答，那么应答的主机就是拥有地址IPX的主机，地址解析也随之而宣告完成。同样，要检测一个地址IPX是否重复，可以发起对该地址的解析，如果解析过程有应答，则表明IPX地址在网络上是重复的。

比如在移动IP中，节点是可以自用移动的，每当一个移动节点移动到一个外界网络（visit network）时，为了继续保持与外界的通信，移动节点可以根据新路由器RA（router advertisement）公告中的前缀信息配置一个属于visit network的新地址，即转交地址（care of address），而新的地址需要经过DAD后才能使用。由于DAD需要约1秒的时间，这种延迟对于很多实时性较高的通信是难以接受的，所以很多文献提出了如何实现快速切换（hand over）的方法[18-20]。且有定理表明，在具体的网络中，如果地址解析过程需要的时间少于DAD需要的时间，那么可以用地址解析过程代替DAD；如果有可以缩短DAD所需时间的方法，那么也可以将其用到地址解析过程中。

现有的网络体系中，地址解析过程与重复地址检测过程都是分开描述的，采用不同的包格式，比如RFC5227 ACD协议[21]。定理4提出这种情况可以大为简化，就是使用一个协议进行描述，采用一种实现方法即可达成目的，比如将地址解析与重复地址检测统称为地址探测过程。

3结束语

地址解析过程与重复地址检测过程容易受到攻击的原因在于检测目的地址的暴露，目前现有的检测方式都是将检测的目的地址以广播（多播）的方式进行公开，所有的节点（包括恶意节点）都能收到，因此恶意的节点可以很容易地进行攻击。采用判定、认证等方法虽然可以大幅提升地址解析的安全性，但地址映射的不可判定性表明，这种方法是不完善的。除此之外，这也给出了一个提示，就是如果地址映射是可以判定的，那么也就不需要地址解析过程了，因为给定一个IP地址，主机只要对所有可能与该IP匹配的MAC地址一一进行判定即可，直至找到一个合法的地址映射。地址解析过程与重复地址检测过程的等价性表明，在下一代网络中，地址解析协议的设计将得到简化，设计安全协议的方式来提升地址解析过程与重复地址检测的安全性，安全的邻居发现协议就是一个很好的开端[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-），男，黑龙江哈尔滨人，博士研究生，主要研究方向：网络安全、IPv6技术、学术信誉评价；

季振洲（1965-），男，黑龙江哈尔滨人，博士，教授，博士生导师，主要研究方向：先进系统结构、并行计算、网络QoS、网络安全等。