摘 要：网络弹性研究的是网络在节点失效或被有意攻击下所表现出来的特征。分析Gnutella网络的网络弹性，包括对于随机攻击的容错性和对于选择性攻击的抗攻击性，并与ER模型和EBA模型进行了对比。Gnutella网络对于随机攻击具有很好的容错性，但是对于选择性攻击却显得脆弱。最后对网络弹性进行了理论分析，给出了网络在出现最大集团临界点之前的平均集团大小的公式解。
关键词：对等网络；无标度；网络弹性；脆弱性
中图分类号： TP393.02文献标识码：A
文章编号：1001-9081(2007)04-0784-04
0 引言
在过去的40多年里，科学家习惯于将所有复杂网络看作是随机网络。随机网络中绝大部分节点的连结数目会大致相同。1998年开展的一个描绘互联网的项目却揭示了令人惊诧的事实：基本上，互联网是由少数高连结性的页面串联起来的，80%以上页面的连结数不到4个，而只占节点总数不到万分之一的极少数节点，例如门户网Yahoo和搜索引擎Google等类似网站，却高达上百万乃至几十亿个链接。研究者把包含这种重要集散节点的网络称为无标度网络[1]。
具有集散节点和集群结构的无标度网络，对意外故障具有极强的承受能力，但面对蓄意的攻击和破坏却不堪一击[2]。在随机网络中，如果大部分节点发生瘫痪，将不可避免地导致网络的分裂。无标度网络的模拟结果则展现了全然不同的情况，随意选择高达80%的节点使之失效，剩余的网络还可能组成一个完整的集群并保持任意两点间的连接，但是只要5%—10%的集散节点同时失效，就可导致互联网溃散成孤立无援的小群路由器。
许多复杂网络系统显示出惊人的容错特性，例如复杂通信网络也常常显示出很强的健壮性，一些关键单元的局部失效很少会导致全局信息传送的损失。但并不是所有的网络都具有这样的容错特性，只有那些异构连接的网络，即无标度网络才有这种特性，这样的网络包括WWW、因特网、社会网络等。虽然无标度网络具有很强的容错性，但是对于那些有意攻击，无标度网络却非常脆弱。容错性和抗攻击性是通信网络的基本属性，可以用这两种属性来概括网络弹性。
对等网络技术和复杂网络理论的进展促使对现有对等网络的拓扑结构进行深入分析。对网络弹性的认识可以使从网络拓扑的角度了解网络的脆弱点，以及如何设计有效的策略保护、减小攻击带来的危害。本文研究Gnutella网络的网络弹性，并与ER模型和EBA模型进行了比较，对比不同类型的复杂网络在攻击中的网络弹性。当网络受到攻击达到某一个临界值时，网络中已不存在最大集团了，节点分散于许多相互独立的小集团里，分析了这些小集团大小的分布及平均大小，并对于攻击对网络造成的损害进行了定量的理论分析。
1 网络的容错性和抗攻击性
对一般网络的攻击方式可以选择去点与去边两种方式，从选择的方式上分为随机攻击和选择性攻击两种类型[3]，抵抗这两种攻击的能力分别称为网络的容错能力与抗攻击能力。
随机攻击，顾名思义就是在一个网络中随机选择一些节点，并去掉这些节点，攻击者不知道这些节点在整个网络拓扑结构中的位置。选择性攻击才可以理解为真正意义的对网络的攻击，比如计算机网络中的黑客攻击。对网络攻击脆弱性的研究表明，攻击者为了最大化攻击效果，往往想挑选那些网络中最重要的节点进行攻击，这需要事先知道整个网络的拓扑结构，但这在真实网络环境下是不太可能的。然而，为了深入了解不同攻击行为对网络造成的影响，往往是在知道网络的全局拓扑的情况下对各种攻击行为进行分析。选择性攻击使用两种不同方式：第一种攻击使用基于节点度的策略，即按顺序去掉网络中那些节点度高的节点；第二种攻击使用基于节点介数的策略，即去掉网络中那些介数比较大的节点。
研究表明[2,3]，无标度网络具有很强的容错性，但是对于基于顶点的度值或介数的选择性攻击抗攻击能力较差，对于基于边的介数的攻击也非常敏感。文献[2]不仅讨论了网络的最短距离等几何性质在去边去点攻击下的改变，还讨论了节点度与介数等几何量的相关性。一些文献对代谢网络、食物链网络、Email网络[4]和Internet[5,6]等网络的网络弹性进行了深入讨论。
1.1 Gnutella网络的弹性分析
Gnutella是一份用于文件共享的内容分发和分布式检索的协议。虽然该协议也支持传统的客户端/中心服务器的检索规范，但它更主要是支持点对点的，没有中心的检索。
根据Gnutella的协议规范，在Gnutella网络中为了找到需要的信息，一个节点将请求消息发送给其邻节点，邻节点首先查找自己是否有与请求消息匹配的信息。如果存在匹配信息则发送响应消息，然后检查请求消息中的TTL (Time—To—Live)是否小于零；如果没有超过则继续转发请求消息，否则停止转发。
接下来介绍怎样通过PING、PONG命令和TTL值来探测Gnutella网络的拓扑结构。当探测节点发送一个TTL值为2的PING命令给其邻节点时，邻节点收到PING命令后将TTL字段值减1，此时TTL值为1，邻节点再将PING命令转发至下一层邻节点，下一层邻节点收到PING命令后同样将TTL值减1，此时TTL值为0，因此不再转发PING命令，而只将PONG命令返回给探测节点。这样探测节点可以收集到与它相邻的第二层邻节点的IP地址信息，然后探测节点又发送TTL值为2的PING命令至第二层邻节点，这样又可以得到第三层邻节点的信息，按照这种广度优先的搜索方式，最后就可以得到整个网络的拓扑结构。通过分析Gnutella网络的拓扑结构来考察网络弹性。随机性攻击的情况比较简单，这里使用随机选择去掉某些节点来模拟真实网络环境中节点失效的情况。
任何一个网络的互联性从本质上可以由它的网络直径和平均最短路径长度来描述。网络直径描述了网络中两个节点相互通信的能力：直径越小那么两点间期望的通信长度就越短。一个网络就算拥有大量的节点也可能具有很小的网络直径，比如拥有80亿个节点的WWW网络，它的网络直径大约为19。
设想当一个完整的网络(即所有节点都是连通的)在受到攻击后，网络的拓扑结构势必会受到很大的影响，以至网络中的某些边也会消失，从而导致整个网络分裂成很多相互独立的子图，这些子图之间没有连接。反映到真实网络情况就是说某些节点之间的通信无法进行，从而使网络的通信受到影响。因此，下面将基于最大集团，网络紧中心性和网络直径三个拓扑属性来分析Gnutella网络的网络弹性。最大集团指的是相对大小，即最大集团中的节点数与网络中所有节点数的比值。紧中心性定义为：d(x,y)，这里d(x,y)表示节点x和y之间的最短路径长度，U是所有节点的集合。
在试验时，为了观察随机失效给网络带来的影响，这里随机选择去掉网络中的一小部分节点，用百分比f表示。同样对于模拟选择性攻击，首先去掉网络中节点度最高的节点，然后按照节点度降序的规则选择被去掉的节点。图1—图3描述了最大集团相对大小、网络紧中心性和网络直径在随机攻击(Failure)、基于度的攻击(DAttack)和基于介数的攻击(BAttack)三种情况下的变化过程。在对Gnutella网络拓扑进行探测时，经过大量的数据分析发现，在Gnutella网络中超级节点所占的比例大约是3.3%，这种节点是使用基于度的攻击方法时的目标节点，因此上述三个图中x轴的变化范围限定在[0,0.05]。
如图1—图3所示，Gnutella网络对于随机攻击显示出很好的容错性：最大集团的相对大小变化非常缓慢，到去掉4％左右的节点时，S大小仍然在0.85左右，见图1；网络的紧中心性在整个过程基本上保持不变，只有微小的波动，见图2；网络直径的变化也不明显，在区间[0, 0.04]内保持不变，到f为5％时才增加1，见图3。然而，Gnutella网络在基于度的攻击和基于介数的攻击时却显得非常脆弱。
如图1所示，对于基于度的攻击(DAttack)，当f趋于2%时，最大集团相对大小S趋向于0，这说明这时网络中已经不存在最大子图，大部分节点都分散在很多小的子图里，或者某些节点已经成为孤立的节点；基于介数的攻击(BAttack)时，情况要比DAttack时好一些，当f趋于3.3%左右时S才趋于0，这说明在Gnutella网络中,基于度的攻击比基于介数的攻击对于网络的危害更大一些。
如图2所示，对于基于度的攻击(DAttack)，f趋于1%时网络的紧中心性达到最小值0.145，对于基于介数的攻击(BAttack)，f趋于3%时网络紧中心性达到最小值0.145，这里的情况跟选择性攻击对最大集团的影响相似，基于度的攻击比基于介数的攻击危害性要大一些。
图2中另外一个有趣的现象是，当紧中心性达到最小值后，在两种攻击情况下，紧中心性又开始逐渐增大。这是因为网络紧中心性是针对网络中的最大集团来计算的，攻击刚开始时，网络中的最大集团大小相比整个网络节点数目来说较大，攻击发生后去掉了一些关键节点导致某些关键路径也从网络中去掉，影响了节点间通信的平均最短路径，确切地说是增大了平均最短路径，从而导致紧中心性的减小；然而随着攻击的增加，网络中的最大集团大小越来越小，即网络被分成了许多独立的小的子图，而这时最大集团中的平均最短路径也会变小，集团中的节点间通信平均来说会更快，相应地紧中心性会增大。
图3给出了攻击对网络直径的影响，在大图的坐标范围内无法看到网络直径的变化过程，所以放大了区间[0, 001]，如小图所示。图3表明两种攻击对网络直径的影响很大，与前面两种情况类似，基于度的攻击对网络直径的影响比基于介数的攻击要大。
综上所述，Gnutella网络对于随机攻击具有很强的容错性，而对选择性攻击却显得比较脆弱；在遭受攻击时测量网络得到的相关参数表明，基于度的攻击均比基于介数的攻击对网络造成的危害性更大。
1.2 ER模型和EBA模型的网络弹性分析
复杂网络的理论研究始于20世纪60年代，著名数学家Erdfis和Renyi提出了ER模型，一个由n个节点组成的随机图中，每两个节点被一条边连接起来的概率为p。鉴于实际网络的情况，Barabasi和Albert的第二个关于无标度网络的机制模型考虑了加点、加边和重连三种事件，扩充了原有的BA模型，即EBA（Extended BA）模型。下面通过ER模型和EBA模型来比较与Gnutella网络弹性的异同。图4—图6分别描述了在ER模型中随机攻击和两种选择性攻击对最大集团大小、网络紧中心性和网络直径的影响。与Gnutella网络不同，对于ER模型，随机攻击和选择性攻击对于网络的影响基本上是相同的，正如图中所绘的曲线基本是重叠的。
如图4，对于基于介数的攻击，当f趋于32%时，S趋于0；而对于基于度的攻击和随机攻击，当f趋于38%时，S趋于0，这说明基于介数的攻击危害性要大一些。如图5，对于基于介数的攻击，当f趋于15%时，CC趋于最小值；对于基于度的攻击和随机攻击，当f分别趋于17%和18%时，CC趋于最小值。基于介数的攻击使网络紧中心性下降得更快，比其他两种攻击更加具有危害性。如图6，这几种攻击对于网络直径的影响也跟上面的情况类似，影响由大到小的顺序是：基于介数的攻击，基于度的攻击，随机攻击。
图7—图9分别描述了在EBA模型中随机攻击和两种选择性攻击对最大集团大小、网络紧中心性和网络直径的影响。从图中曲线的变化可以看出，EBA模型与Gnutella网络具有比较大的相似性。
如图7，对于基于介数的攻击，当f趋于22%时，S趋于0；而对于基于度的攻击和随机攻击，当f趋于24%时，S趋于0。
如图8，对于基于介数的攻击，当f趋于9%时，CC趋于最小值；对于基于度的攻击，当f趋于11%时，CC趋于最小值。EBA模型与ER模型的一个相似之处是它们对于两种不同的选择性攻击具有相同的反映，从图中BAttack和DAttack的变化快慢可知，基于介数的攻击比基于度的攻击危害更大，这刚好跟Gnutella网络中的情况相反。因为从f变化范围可以看出，Gnutella网络中大度节点(ultrapeer)所占比例要小于EBA模型中大度节点所占比例，并且小度节点(叶子节点)非常依赖于大度节点，通常小度节点只与三个左右的ultrapeer相连，小度节点之间基本上没有连接，这样就使得网络在受到基于度的攻击时，会比受到基于介数的攻击更加脆弱。
2 网络弹性的理论模型
通过试验分析了Gnutella网络在随机攻击和选择性攻击发生时，网络的三种拓扑属性的变化情况，并ER模型和EBA模型做了对比。最大集团大小，网络紧中心性和网络直径这三种拓扑属性当中，对于实际系统最有意义最直观的就是最大集团大小。当网络受到攻击后，一般最关心的是这个网络最大范围内有多少节点仍然可以相互通信。从另一个方面考虑，当网络受到攻击达到某一个临界值(f趋于某个值)，整个网络已经不存在最大集团了，网络节点都分散于许多相互独立的小集团里，那么这些小集团大小的分布情况及平均大小是多少？这些对于攻击对网络造成损害的定量分析非常重要，下面将进行理论分析。
在分析攻击临界点发生后集团大小的分布和集团平均大小时，为了便于理论分析，可以按如下思路来考虑。在攻击临界点发生后，网络被分散成许多独立的小集团，由于攻击的方法是去掉网络中的某些节点，那可以反过来思考网络的形成过程。开始时网络由一些单个节点组成，随着其他节点的加入和边的形成，网络会逐渐演化生长，到某一个临界点时网络中的最大集团开始形成，这里的临界点与攻击使得最大集团消失的临界点是相同的，只是它们的表述方式不同而已。因此可以用这种方法来分析最大集团形成前(即临界点之前)网络中集团的大小分布和集团的平均大小。
在一个网络图中随机选择一条边，设想沿着这条边指向它的一个端点并且通过这个端点可以到达其他节点，就称通过这条随机选择的边的一端可达的节点集合为一个集团。令H1(x)为这些集团大小分布的生成函数。沿着一条随机选择的边，与它相连的可能只是一个单一的节点，没有其他边与这个节点相连；也可能是有多条边连接的一个节点，每条边又连接其他的集团，这些集团的大小分布也是由H1(x)生成。通过一条边访问某个节点时，与这个节点相连的其他边的数目(不包含访问次节点所用到的那条边)的分布生成函数可以由下式来表示：
从上面的分析看出，要求得所有阶的集团大小的概率分布(Ps)的公式解是非常困难的，但是可以计算集团大小概率分布的期望值。最简单的是一阶期望值，即平均集团大小。平均集团大小< s >可对生成函数求导数得到：
计算集团大小的概率分布(Ps)的公式解比较困难，可以计算集团大小概率分布的一阶期望值，即平均集团大小，式(11)给出了攻击临界点发生后或者网络在出现最大集团临界点之前的平均集团大小的公式解。
3 结语
本文对Gnutella网络的网络弹性，即对于随机攻击的容错性和对于选择性攻击抗攻击性进行了详细的分析，并且与ER模型和EBA模型进行了对比。发现Gnutella网络与EBA模型在很多方面表现出相似性，它们对于随机攻击具有很好的容错性，但是对于选择性攻击却显得非常脆弱。另外Guntella网络与EBA模型的一个重要不同点是，它们对于基于节点度的攻击和基于节点介数的攻击具有不同的表现，Gnutella网络中基于节点度的攻击更具破坏性，而EBA模型中却恰好相反。最后对网络弹性进行了理论分析，并给出了网络在出现最大集团临界点之前（等价于网络受到攻击的最大集团消失临界点）的平均集团大小的公式解。未来的工作是针对网络在不同攻击下的特征，提出网络自修复机制和策略，增强网络的抗攻击性能。
本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。
