基于复杂网络理论的互联网病毒传播的控制技术分析

郭海鸥，李 静

(1.河南教育学院学报编辑部，河南郑州 450014;2.黄河科技学院现代教育技术中心，河南郑州 450063)

基于复杂网络理论的互联网病毒传播的控制技术分析

郭海鸥1，李 静2

(1.河南教育学院学报编辑部，河南郑州 450014;2.黄河科技学院现代教育技术中心，河南郑州 450063)

以具有小世界和无标度的拓扑结构特征的互联网为研究对象，在流行病学模型基础上进一步考虑了网络连接、关联性等因素，利用复杂网络理论细致分析了互联网病毒传播的局域控制技术.

复杂网络;互联网;计算机病毒;小世界;无标度

0 引言

0.1 复杂网络

近年来，复杂网络的研究已越来越深入，研究者有数学、物理学、计算机网络等不同领域的学者.在复杂网络中把个体直接抽象为顶点，相互作用视为边，把网络的统计性质称为静态几何量;把具有特定几何性质的网络机制的探索称为网络演化机制模型;把建立在网络上的一些模型，例如传染病等动态过程称为网络上的动力学性质;把各种攻击网络的方式与响应称为网络的结构稳定性［1］.统计物理与图论都是研究复杂网络的有力工具.

0.2 互联网结构

目前主要有两种描绘互联网的结构的方式.一种基于路由器，把每一个路由器看做节点，边表示路由器之间的连接.另一种基于自治系统(AS)，AS的子网络采用不同内部路由算法.每个AS代表一个节点，BGP对等连接两个AS，则表示这两个AS之间有一条边相连.互联网是一种非均匀网络并且节点的度有很大的波动性，表现出很强的幂律分布的特点.目前互联网拓扑主要是基于Barabási和Albert提出来的复杂网络的BA演化模型及其改进型的局部演化模型［2］，有路由器和自治域两种不同层次来描述计算机网络的拓扑结构.

0.3 基于流行病学传播模型的计算机病毒传播模型

生物学中对病毒传播的研究是一个重要研究领域，已经建立了流行病学传播模型.在20世纪90年代初期一些科学家就注意到病毒(生物病毒及计算机病毒)有一些共性，在流行病学模型基础上考虑网络连接、关联性等因素，把生物学中流行病学传播模型引入到计算机病毒的研究之中，基于网络的拓扑结构分析计算机病毒的传播，流行病学模型的基本思想是计算机病毒传播模型的重要基础［3］.

1 基于复杂网络理论的互联网安全技术研究

在互联网安全研究领域中，病毒防范的研究，主要采取合理的反病毒和预防策略，通过一定措施减慢病毒传播、切断病毒传播链、降低病毒危害，目前还是一个没有解决的问题.

1.1 复杂网络中的病毒防范技术

复杂网络中的病毒传播是当前复杂网络研究的一个热点问题［4］.复杂网络具有小世界和无标度的拓扑结构，互联网对随机错误有很强的鲁棒性，不过在恶意攻击下表现得比较脆弱.有时仅仅只是很微少的病毒感染源，如果不加以认真控制，就可能产生大规模的病毒流行.目前，针对免疫策略做了许多研究，根据节点的度来选择重要的免疫节点.典型的免疫控制策略有随机免疫(网络中免疫节点完全随机选取)，目标免疫(对少量度大的节点免疫)，熟人免疫(免疫节点是随机选出的节点的邻居).不过即使对网络的大量节点进行免疫，仍不能彻底阻止病毒的传播.

无论哪种免疫策略，都以节点的度为标准.实际上可以从另外一个角度出发，从感染源出发，不考虑节点的度.在感染源周围进行局域控制，控制范围如何选择成为关键.控制包含预防、隔离、免疫、杀毒等各种应对措施.在理想小世界网络、无标度网络和随机图网络中，要抑制病毒的大范围传播，只要对距离感染源d步范围内的节点进行控制即可，一般存在很小的路径长度范围d.小世界网络在d=3时通过少量的控制节点就可以达到零感染的最优效果.对于距离相对近的节点较集中时，网络拓扑在相当程度上可以抑制病毒的传播，局域控制的效果更好.

各种网络模型所产生的结构与真实网络的拓扑结构一般会存在一些差异，有关互联网局域免疫模型实证研究目前尚无报道.在规模较小的互联网中，具有无标度和小世界的拓扑结构特征的互联网局域免疫模型自身特点鲜明，应用复杂网络理论研究互联网的局域免疫模型有重要价值.

1.2 基于复杂网络理论的流行病学模型

Newman等人研究了小网络上的传染病模型［5］，在这个模型中，感染者比例存在一个阈值，但要比规则网络小很多.而对于无标度网络上传染病模型，无论SIS还是SIR模型，没有类似的阈值［2］，即只要有传染病发生，就会大范围传播.因此，不能完全依赖于医疗卫生水平的提高来控制这种网络上的传染病，需要改变网络拓扑结构，典型方法是隔离传染源，即强行阻断某些联接，去掉一些顶点.通常网络中去边与去点称为对网络的攻击，所以，不同攻击方式下的网络结构稳定性是与网络物理模型密切相关的.随机性的增加使网络中流行病的传播阈值降低，有利流行病的传播.在随机网络的增长中，随着网络尺寸的增大，流行病的传播阈值逐渐减小，其衰减速率也逐渐变小，表现收敛的趋势.

如果无标度网络尺寸无限大，网络的结构在空间或时间上将无序，度分布具有幂律性，流行病传播阈值将不存在.

对于WS模型，流行病的传播呈现出明显的相变行为，阈值非零，不依赖于网络的尺寸;然而，在随机增长网络中，传播阈值将依赖于网络的尺寸大小，随着网络尺寸的增大而逐渐减小，其衰减的速率也变小.对有限尺寸的网络，也有非零的传播阈值.传播阈值随着系统尺寸的增大也是逐渐减小的.

1.3 基于复杂网络理论的流行病学模型的互联网反病毒技术

在生物学流行病学模型中，模型基本的状态包括3部分:S:易染状态;I:被感染状态;R:被移除状态(免疫状态).常常用状态之间的转换过程来命名模型.SIR模型:易染群体被感染，然后恢复健康并具有免疫性.SIS模型:如果易染群体被感染后，又返回到易染状态.网络拓扑结构严重影响传播速率，在局域(local)和稀疏(sparse)两种结构的图中病毒的传播有许多不同之处.病毒传播速率在稀疏结构中慢，病毒传播扩散的概率也小，病毒传播也没有优先方向.

计算机之间经常通过电子邮件等进行程序或文档的交换，这些交换关系通常是在一个组群中的，这种网络连接存在非均匀性，对数据交换有重要影响.计算机病毒的传播在这种网络中是有优先方向的，显然这里是局域结构.这种模型是一种分析计算机病毒传播的很有效模型.随机网络上的传播行为与小世界网络上的十分相似.在幂律网络中，可能是幂律分布网络的平均路径长度较小和节点的度差异较大，病毒的传播速率要快得多.病毒一开始都是感染度大的节点，这些度大的节点会迅速传播更多的病毒副本，从而产生“放大效应”.幂律分布网络在非重复感染的情况下最终未被感染的节点比随机网络和小世界网络多.这3类不同拓扑结构的网络具有接近的平均度，不过幂律网络被感染的概率较小，幂律网络最终被感染的节点数较少，这是因为幂律网络小于平均度的节点更多.互联网是关联网络，互联网的传播生命期通常比非关联网络长，不过对于有限大小企业内部关联网络，其传播速率临界值要比互联网大一些，它们都比非关联网络有更强的鲁棒性.抑制互联网病毒的一种重要方法是免疫.目前这仍是一个没有解决的问题.选择免疫(目标免疫)和随机免疫(均匀免疫)是目前主要的两种互联网病毒免疫策略.随机免疫对度小的节点(相对安全)和度大的节点(被感染的风险高)是平等对待的，通常适合随机网络，进行免疫时没有优先顺序，随机地选择节点.随机免疫法在小世界网络中作用非常有限，随机免疫法能够局部抑制感染，但速度慢.在无限小世界网络中，不存在临界问题，临界值g=1，随机免疫法要免疫所有节点才能达到免疫彻底，这是无法实现的，随机免疫不能保证最终消灭感染.互联网是一种小世界网络，采用随机免疫即使对其上多数节点都进行随机免疫，也不能阻止计算机病毒的发生.

目标免疫利用互联网络的非均匀性特点选择节点，呈现小世界网络特征的互联网，具有一些度大的节点，选取这些度大的节点进行目标免疫，它们所连的众多边就可以从网络中去掉，重构了互联网网络的结构，从而阻止大部分网络病毒的传播.目标免疫的免疫临界值要比随机网络的免疫临界值小很多.

当前互联网一些反病毒软件的生命期还是相当长的，文件扫描和防病毒更新的过程是一种随机免疫过程，由于互联网的小世界特征，在整个互联网中，就是众多节点都被免疫，从上面的分析，这些反病毒软件也不能根除互联网病毒的传播.采用目标免疫法是一种较好的方法，单采取上面方法获取互联网中各节点的度，特别是那些中心节点的度，以便对其进行免疫，对于复杂的互联网来说，这不是一件容易的事情.

在互联网中，有少量的中心节点对互联网的运行起着重要的作用，这些节点的安全性是至关重要的，然而正是这些节点存在着很大的安全漏洞，这使得针对高节点度的中心节点的智能攻击有时显得很容易，从而互联网显得非常脆弱.实验表明只要5%～10%的中心节点同时受到攻击并失效，整个互联网将成一些相互隔绝的“信息孤岛”，整个互联网也就此瘫痪.互联网动力学机制是什么呢?这个问题至今还没有一个圆满的答案，否则就有可能根据需要，设计出一个安全性更高、性能更为优越的网络.

2 总结

对具有小世界和无标度拓扑结构特征的互联网，在流行病学模型基础上考虑到网络连接、关联性等因素，可利用复杂网络理论来研究计算机病毒传播的临界值问题.将是今后互联网网络安全研究的重要领域.

［1］ 汪小帆，李翔，陈关荣.复杂网络理论及其应用［M］.北京:清华大学出版社，2006.

［2］ BARABÁSI A L，ALBERT R.Emergence of scaling in random networks［J］.Seience，1999，286(5439):509-512.

［3］ 徐丹，李翔，汪小帆.复杂网络理论在互联网病毒传播研究中的应用［J］.复杂系统与复杂性科学，2004，1(3):10-26.

［4］ 徐丹，李翔，汪小帆.复杂网络病毒传播的局域控制研究［J］.物理学报，2007，56(3):1313-1317.

［5］ 吴金闪，狄增加.从统计物理学看复杂网络研究［J］.物理学进展，2004，24(1):18-46.

TP393.08

A

1007-0834(2011)02-0040-02

10.3969/j.issn.1007-0834.2011.02.014

2011-03-12

河南省科技攻关项目(112102310377)

郭海鸥(1964—)男，河南灵宝人，河南教育学院学报编辑部副教授，主要研究方向:复杂网络.