物理学报 Acta Phys. Sin. Vol. 62, No. 20 (2013) 200203
基于元胞自动机的复杂信息系统安全风险传播研究*
李钊1)2)† 徐国爱1)2) 班晓芳3) 张毅3) 胡正名1)2)
1) (北京邮电大学信息安全中心,北京 100876 )
2) (北京邮电大学,灾备技术国家工程实验室,北京 100876 )
3) (中国信息安全测评中心,北京 100085 )
( 2013年5月2日收到; 2013年6月17日收到修改稿 )
基于元胞自动机建立复杂信息系统安全风险传播模型,研究复杂信息系统安全风险在最近邻耦合网络、随机
网络, Watts-Strogatz 小世界网络和 Barabasi-Albert无标度网络四种网络拓扑下的传播问题.通过研究安全风险
传播模型在四种网络拓扑下安全风险的传播阈值,与现有的传播阈值研究成果进行比较,验证模型的正确性,并分
析验证网络拓扑结构中度分布的异质化程度越高传播阈值越小的结论.通过对安全风险的传播演化趋势进行研究,
分析验证网络度分布的异质化程度越高、安全风险影响范围越小、传播速度越快的结论,并指出度分布的异质化程
度越高、模型后期的免疫机制对控制安全风险传播的效果越缓慢. 通过对安全风险在传播最早期就趋于消亡的情
况进行研究,分析得出安全风险在传播之初就趋于消亡的消亡率与传播率之间呈现近似负指数的关系,并且初期的
感染源越多安全风险的消亡率越低. 分析了影响复杂信息系统安全风险传播的关键要素,对复杂信息系统中安全风
险传播的控制具有指导作用.
关键词: 复杂信息系统,安全风险传播,元胞自动机
PACS: 02.50.�r, 05.65.+b, 05.70.Jk DOI: 10.7498/aps.62.200203
1 引 言
随着计算机技术与网络技术的快速发展,传统
信息系统不断向大的、复杂的系统演化,这种演化
过程导致了大型复杂信息系统的出现. 复杂信息系
统是呈现高度复杂性的信息系统,其系统规模大、
复杂性高并且结构和功能都具备复杂的网络特性,
是一种具有复杂网络结构的信息系统.社会信息化
的不断发展使得复杂信息系统已经逐渐融入社会
生活的各个方面,复杂信息系统的安全性也显得尤
为重要. 同时, 针对复杂信息系统的恶意攻击也逐
渐复杂化和多样化,其中网络计算机病毒借助系统
软件的安全弱点,以自动化的方式来蔓延扩散并攻
击复杂信息系统 [1];而一些组织也在不断地发布各
种信息系统的安全弱点数据,为针对复杂信息系统
的攻击提供了便利 [2]. 此类不安全因素正在严重地
危及着复杂信息系统的安全. 为了维护复杂信息系
统的安全和稳定,需要适用于复杂信息系统的风险
分析及评估技术来对系统进行安全防范,识别复杂
信息系统中潜在的安全威胁,根据其安全态势及需
求来指定安全策略,避免安全事件的发生.
复杂信息系统是一种具有复杂网络结构的信
息系统,迅速发展的复杂网络理论正快速地增进人
们对生物病毒和计算机病毒大规模爆发流行的传
染机理的认识. 复杂信息系统中安全风险的传播与
计算机病毒和生物病毒在传播的行为上是类似的,
复杂信息系统中受害节点的安全风险可能会 “传
染”原本不直接具有安全风险的节点,使后者受到
安全威胁,即 “感染”安全风险,例如攻击者攻破系
统中的某个节点后,就有可能接着攻击与其相邻的
节点, 因此相邻的节点就受到安全威胁, “感染”安
全风险;同时具有安全风险的节点也在通过更新安
全策略或增加安全防护措施等方式以一定概率消
除安全风险,即 “恢复健康”. 研究生物病毒传播的
*国家自然科学基金 (批准号: 60970135, 61170282)和教育部博士点基金 (批准号: 20120005110017)资助的课题.
†通讯作者. E-mail: lizhaoabc@gmail.com
c
2013 中中中国国国物物物理理理学学学会会会 Chinese Physical Society http://wulixb.iphy.ac.cn
200203-1
物理学报 Acta Phys. Sin. Vol. 62, No. 20 (2013) 200203
数学方法可用于研究计算机病毒的传播,同样可用
于研究复杂信息系统中安全风险的传播.
Kephart等 [3]基于生物传染病学模型对计算机
病毒和蠕虫的传播进行了一系列研究. Hiroyuki等
[4] 基于病毒传播的节点行为建立随机模型,研究蠕
虫传播的概率行为. Zou等 [5]分析 E-mail网络拓扑
对 E-mail病毒传播行为的影响,提出了 E-mail病毒
的传播模型,并且基于人为对抗和网络拥塞等因素
提出了蠕虫模型 [6]. 宋玉蓉和蒋国平 [7] 基于元胞
自动机对复杂网络恶意软件传播动力学行为进行
了一系列研究,但是其模型忽视了现实中节点在健
康状态也可通过人工途径获得免疫的这一事实,并
且该文章中用来验证和研究所建立模型的模拟仿
真网络规模较小,无法充分反映出真实复杂网络中
的传播动力学行为.王亚奇和蒋国平 [8;9] 研究了传
播延迟对复杂网络病毒传播过程的影响. Jin等 [10]
基于元胞自动机提出一种新的传播模型,研究了病
毒的流行程度与元胞邻居大小之间的关系. 此外,
元胞自动机作为研究复杂系统的有效工具,不仅能
够预测病毒的传播趋势,还能够
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
现传播中的概率
事件,因此越来越受到人们的重视 [11�17].
本文参照文献 [7]的方法, 基于元胞自动机建
立复杂信息系统中的安全风险传播模型, 分析安
全风险在多种网络拓扑下的概率传播行为.模型按
照免疫机理类型分为无免疫机理模型、随机免疫
机理模型和熟人免疫机理模型,针对复杂信息系统
节点之间全局交互的特点,建立各自元胞自动机的
元胞空间、有限状态集、元胞邻域以及状态转换
规则.将提出的三种模型用于分析研究最近邻耦合
网络 (nearest-neighbor coupled network, NC), Erdos-
Renyi(ER)随机网络 [18], Watts-Strogatz(WS)小世界
网络 [19] 和 Barabasi-Albert(BA) 无标度网络 [20] 等
多种网络拓扑下的安全风险传播问题.本文提出的
模型不仅能反映复杂信息系统中安全风险传播的
平均趋势,而且可以描述安全风险的消亡等稀有概
率事件,有效地克服了基于马尔可夫链建立的随机
模型不适合描述安全风险传播动态演化特征的缺
陷 [7],也克服了基于平均场方法的确定性模型只能
够反映安全风险传播的平均趋势,只适合对安全风
险传播做整体预测的局限性 [7]. 本文还在多种网络
拓扑中对安全风险的传播阈值、传播演化以及传
播消亡等指标和过程进行了比较研究,分析影响安
全风险传播的关键要素,对复杂信息系统中安全风
险传播的控制和防范具有参考价值和指导意义.
2 安全风险随机传播模型
本文使用元胞自动机建立复杂信息系统安全
风险传播的随机模型. 一个元胞自动机可以通过一
个四元组来表示:
CA= (C;Q;V; f ) ; (1)
(1)式中 C表示元胞空间, Q表示有限状态集, V 表
示元胞邻域, f 表示状态转换规则.考虑免疫机理的
类型,本文建立了三种模型,分别是: 无免疫机理模
型、随机免疫机理模型和熟人免疫机理模型.
2.1 无免疫机理模型
该模型考虑系统中节点状态只能处于安全状
态即健康状态 (susceptible)和风险状态即感染状态
(infected)之一,节点状态变换关系如图 1所示.
图 1 无免疫机理模型状态转换图
其中健康状态表示节点在复杂信息系统网络
中不具有安全风险;感染状态表示节点在复杂信息
系统网络中具有安全风险. 本文将这种模型命名为
Risk-SIS模型,简称 R-SIS模型.
考虑复杂信息系统网络 G = (N;E),其中 N 表
示网络中所有节点的个数, E 表示网络中所有边的
集合.令 A表示网络 G的邻接矩阵,来反映网络的
拓扑结构. 根据元胞自动机的四个模型要素,建立
R-SIS模型如下.
元胞空间 C: 建立包含 N 个元胞的一维元胞空
间,空间中的一个元胞表示复杂信息系统网络中的
一个节点.
有限状态集 Q: R-SIS模型考虑节点的健康状
态和感染状态. 令 Q = f0;1g, 0 表示健康状态, 1
表示感染状态. 节点 i在时刻 t 的状态变量用 si(t)
(si(t) 2 Q)表示,则有:
si(t) =
8<:0;节点 i在时刻 t 状态为 susceptible1;节点 i在时刻 t 状态为 infected :
(2)
元胞邻域 V : R-SIS 模型中以网络的邻接矩阵 A
来定义元胞之间的邻居关系. 邻接矩阵 A 中的第
i 行的向量表示节点 i 的邻居 Vi, 即 Vi = fai jjai j 2
200203-2
物理学报 Acta Phys. Sin. Vol. 62, No. 20 (2013) 200203
A; j = 1;2; � � � ;Ng. 若 ai j = 1,表示节点 i和 j之间
存在通信连接.
状态转换规则 f : R-SIS模型中任何节点仅能
被其邻居感染, 节点 i 在离散时间 t 的状态 si(t)
取决于节点 i在上一时刻 (时刻 t� 1)的自身状态
si(t� 1)和其邻居的状态 svi(t� 1). 每个时间间隔
内感染节点以概率 a 感染其邻居,同时每个单位时
间内感染节点也以概率 b 恢复健康. 状态装换规则
如下所示:
si(t+1) =
8<:si(t); g> 0si(t); g6 0 ; (3)
其中上横线表示取反操作; g为状态转换判断
函
关于工期滞后的函关于工程严重滞后的函关于工程进度滞后的回复函关于征求同志党风廉政意见的函关于征求廉洁自律情况的复函
数,
具体定义如下:
g= si(t)
�
1� (1�a)mi(t)� r
�
+ si(t)(b � r) ; (4)
(4)式中考虑到节点 i在时刻 t 分别为健康状态和
感染状态的两种情况. 当节点 i在时刻 t 为健康状
态时, si(t) = 0,则 (4)式中的第一项起作用,即
g= 1� (1�a)mi(t)� r; (5)
(5)式用来判断在时刻 t 处于健康状态的节点 i,经
过一个离散时间后状态是否改变.模型中一个健康
节点受到感染的概率随着与其相邻的感染节点数
量的增加而增加. 在时刻 t 处于健康状态的节点 i
在下一时刻受到感染的概率为 1� (1�a)mi(t), 其
中 mi(t)表示在时刻 t 与节点 i相邻的感染节点的
数量:
mi(t) =
N
å
j=1
ai js j(t): (6)
(5)式中的 r 为 (0, 1)之间的随机数, 用来与时刻 t
处于健康状态的节点 i在下一时刻受到感染的概率
1� (1�a)mi(t) 进行比较,判断节点 i是否会受到感
染: 若 1� (1�a)mi(t) 大于 r, 即 (5) 式中 g > 0, 则
节点 i受到感染,状态改变, si(t+1) = si (t);反之若
1� (1�a)mi(t) 小于等于 r, 即 (5)式中 g 6 0, 则节
点 i没有受到感染,保持健康状态, si(t+1) = si(t).
因此, 在时刻 t 为健康状态的节点 i (si(t) = 0)
的状态转换规则符合 (3)式中定义的规则 (结论 1).
当节点 i 在时刻 t 为感染状态时, si(t) = 1, 则
(4)式中的第二项起作用,即
g= b � r; (7)
(7)式用来判断在时刻 t 处于感染状态的节点 i,经
过一个离散时间后状态是否改变.模型中一个感染
节点以概率 b 恢复健康, (7)式中的 r为 (0, 1)之间
的随机数, 用来与时刻 t 处于感染状态的节点 i在
下一时刻恢复健康的概率 b 进行比较,判断节点 i
是否会恢复健康: 若 b 大于 r,即 (7)式中 g> 0,则
节点 i恢复健康,状态改变, si(t+1) = si(t);反之若
b 小于等于 r,即 (7)式中 g6 0,则节点 i没有恢复
健康,保持感染状态, si(t+1) = si (t).
因此, 在时刻 t 为感染状态的节点 i (si(t) = 1)
的状态转换规则符合 (3)式中定义的规则 (结论 2).
由结论 1和结论 2可知, R-SIS模型中节点 i的
状态转换规则符合 (3)式中定义的状态装换规则.
用 S(t)表示在时刻 t网络中健康节点在所有节
点中所占的比率,用 I(t)表示在时刻 t 网络中感染
节点在所有节点中所占的比率,那么模型中有以下
结果 [7]:
I(t) =
1
N
N
å
i=1
si(t); (8)
S(t)+ I(t) = 1: (9)
2.2 随机免疫机理模型
随机免疫是指在网络中随机的选取一部分节
点进行免疫. 引入随机免疫机理后的复杂信息系统
安全风险传播模型中, 节点的状态分为健康状态、
感染状态和免疫状态,节点状态变换关系如图 2所
示.
图 2 随机免疫机理模型状态转换图
其中健康状态表示节点在复杂信息系统网络
中没有安全风险;感染状态表示节点在复杂信息系
统网络中具有安全风险;免疫状态表示节点在复杂
信息系统网络中因为进行了安全隔离或者采取了
持续的安全防护措施,从而免于感染安全风险. 本
200203-3
物理学报 Acta Phys. Sin. Vol. 62, No. 20 (2013) 200203
文将这种模型命名为 Risk-SIR-Random模型,简称
R-SIR-R模型. R-SIR-R模型基于随机免疫机理和
生物传染病学中的 SIR模型建立,在传播的初始状
态 (时刻 0) 对网络中的各节点以一定概率进行随
机免疫, 之后依照 SIR模型, 节点在治愈的同时以
一定概率获得免疫.
需要注意的是,免疫状态的节点不会再被感染
节点传染安全风险,也不会向健康节点传染安全风
险. 因此一旦节点被免疫, 免疫节点所连接的边就
应该从网络中去除 [7], 同时需要修改网络 G 的邻
接矩阵 A. 根据元胞自动机的四个模型要素,建立
R-SIR-R模型如下.
元胞空间 C: 建立包含 N 个元胞的一维元胞空
间,空间中的一个元胞表示复杂信息系统网络中的
一个节点.
有限状态集 Q: R-SIR-R 模型考虑节点的
健康状态、感染状态和免疫状态. 令 Q =
f(0;0);(1;0);(0;1);(1;1)g, (0, 0) 表示健康状态; (1,
0)表示感染状态; (0, 1)表示免疫状态 [7]. 节点 i在
时刻 t 的状态变量用向量 si(t) (si(t) 2 Q)表示,向
量 si(t)包含两个分量: si(t) = (six(t);siy(t)),其中分
量 six(t)用来表示节点是否感染,分量 siy(t)用来表
示节点是否免疫,则有 [7]:
si(t)=
8>>>>>><>>>>>>:
(0;0); 节点 i在时刻 t 状态为 susceptible
(1;0); 节点 i在时刻 t 状态为 infected
(0;1); 节点 i在时刻 t 状态为 removed
(1;1); 状态不存在
;
(10)
元胞邻域 V :R-SIR-R模型中以网络在时刻 t 的邻接
矩阵A(t)来定义在时刻 t 元胞之间的邻居关系.邻
接矩阵 A(t)中的第 i行的向量表示节点 i在时刻
t 的邻居 Vi(t), 即 Vi(t) =
�
ai j(t)
��ai j(t) 2 A(t); j =
1;2; � � � ;N . 若 ai j(t) = 1,表示节点 i和 j之间在时
刻 t 存在可传播安全风险的连接.
状态转换规则 f : 在 R-SIR-R 模型中, 状态转
换规则分为两个部分. 第一部分是在初始阶段 (即
时刻 t = 0), 对网络中的各节点以概率 g 进行随机
免疫. 第一部分的状态装换规则如下所示:
six(0) = 0; (11)
siy(0) =
8<:1; g> 00; g6 0 ; (12)
其中 g为状态转换判断函数,定义如下:
g= g� r: (13)
(11)和 (12)式用来判断节点 i在初始阶段是否被选
中接受免疫. (12)式中的 r 为 (0, 1)之间的随机数,
用来与免疫概率 g 进行比较,判断节点 i是否转换
为免疫状态:若 g大于 r,即 (12)式中 g> 0,则节点 i
转换为免疫状态, six(0) = 0, siy(0) = 1, si(0) = (0;1);
反之若 g 小于等于 r, 即 (12) 式中 g 6 0, 则节点
i 没有免疫, 保持健康状态, six(0) = 0, siy(0) = 0,
si(0) = (0;0). 同时需要修改网络 G 的初始邻接
矩阵 A(0), 若 si(0) = (0;1), 则 ai j(0) = a ji(0) = 0,
j = 1;2; � � � ;N.
状态转换规则的第二部分用于传播的演化阶
段 (时刻 t > 0),在演化阶段中,每个时间间隔内感
染节点以概率 a 感染它的邻居,同时每个单位时间
内感染节点也以概率 b 恢复健康;感染节点若在下
一时刻恢复健康,则该节点在恢复健康的同时以概
率 d 获得免疫. 第二部分的状态装换规则如下所
示:
six(t+1) =
8>>><>>>:
six(t); gx > 0^ siy (t) = 0
six(t); gx 6 0^ siy (t) = 0
0; siy(t) = 1
;
siy(t+1) =
8<:1; gy > 0_ siy(t) = 10; gy 6 0^ siy(t) = 0 ; (14)
当节点 i时刻 t 的状态为免疫状态,即 si(t) = (0;1)
时, si(t+ 1) = (0;1), 表示节点一旦免疫, 就保持免
疫状态不变. (13)式中上横线表示取反操作; gx, gy
为状态转换判断函数,具体定义如下:
gx = six(t)
�
1� (1�a)mi(t)� r
�
+ six(t)(b � r) ; (15)
gy = six(t)six(t+1)(d � r) : (16)
(14)式的解释同 (4)式类同,需要做细微调整 [7] 的
地方是 mi(t). (14)式中用来表示在时刻 t 与节点 i
相邻的感染节点的数量 mi(t)调整为
mi(t) =
N
å
j=1
ai j(t)s jx(t); (17)
并且若 si(t) = (0;1), 则有 ai j(t) = a ji(t) = 0; j =
1;2; � � � ;N.
(15) 式用来判断在时刻 t 为感染状态并在时
刻 t+1恢复健康的节点 i是否转换为免疫状态, 其
200203-4
物理学报 Acta Phys. Sin. Vol. 62, No. 20 (2013) 200203
中 r 为 (0, 1)之间的随机数,用来与免疫概率 d 进
行比较. (15)式中当 six(t)为 1, six (t+1)为 0并且
(d � r) > 0时, gy¿0,表示节点 i在时刻 t 为感染状
态,在时刻 t+1恢复健康并获得免疫;其他情况 gy
均小于等于 0,表示节点 i没有获得免疫.
用 S(t)表示在时刻 t网络中健康节点在所有节
点中所占的比率, I(t)表示在时刻 t 网络中感染节
点在所有节点中所占的比率, R(t)表示在时刻 t 网
络中免疫节点在所有节点中所占的比率,那么模型
中有以下结果 [7]:
I(t) =
1
N
N
å
i=1
six (t); (18)
R(t) =
1
N
N
å
i=1
siy (t); (19)
S(t)+ I(t)+R(t) = 1: (20)
2.3 熟人免疫机理模型
熟人免疫是指在网络中随机第选出一定比例
的节点,再从每一个被选出的节点中随机选择一个
邻居节点进行免疫. 引入熟人免疫机理后的复杂信
息系统安全风险传播模型中,节点的状态分为健康
状态、感染状态和免疫状态,节点状态变换关系如
图 3所示.
图 3 熟人免疫机理模型状态转换图
熟人免疫机理模型中各节点状态表示的意义
与 R-SIR-R模型中的说明相同.本文将这种模型命
名为 Risk-SIR-Acquaintance模型,简称 R-SIR-A模
型. R-SIR-A模型基于熟人免疫机理和生物传染病
学中的 SIR模型建立,在传播的初始状态 (时刻 0)
对网络进行熟人免疫, 之后依照 SIR模型, 节点在
治愈的同时以一定概率获得免疫.
同样,免疫状态的节点不会再被感染节点传染
安全风险, 也不会向健康节点传染安全风险. 因此
R-SIR-A模型中一旦节点被免疫,免疫节点所连接
的边就应该从网络中去除,同时需要修改网络 G的
邻接矩阵 A. 根据元胞自动机的四个模型要素,建
立 R-SIR-A模型. 其中元胞空间 C、有限状态集 Q
以及元胞邻域 V 的定义与 R-SIR-R模型相同.下面
定义 R-SIR-A模型中的状态转换规则 f .
状态转换规则 f : 在 R-SIR-A 模型中, 状态转
换规则同样分为两个部分. 第一部分是在初始阶段
(即时刻 t = 0),在网络中以概率 p随机的选择节点,
然后从每一个被选出的节点中随机选择一个邻居
节点进行免疫. 第一部分的状态装换规则如下.
首先对于每一个节点 i判断是否以概率 p被选
中,用 hi来表示: hi = 1表示节点 i被选中, hi = 0表
示节点 i没有被选中. 定义 hi的规则如下:
hi =
8<:1; p� r > 00; p� r 6 0 ; (21)
其中 r 为 (0, 1)之间的随机数,用来与概率 p进行
比较,判断节点 i是否被选中.
若 hi = 1, 表示节点 i 被选中, 接下来需要
在节点 i 的邻居中随机选择一个进行免疫. 由
模型中元胞邻域 V 的定义可知, 向量 Vi (0) =�
ai j(0)
��ai j(0) 2A(0); j = 1;2; �;N 表示节点 i 在
初始时刻和其他节点的邻接状态. 集合 vi(0) 表
示初始时刻节点 i 的所有邻居的集合, vi(0) =�
j
��ai j(0) = 1; ai j(0) 2A(0) . 若 vi(0) = /0,则跳过
节点 i, 继续对其他节点进行是否选中的判断. 若
vi(0) 6= /0,则从 vi(0)中随机选取一个元素 jr进行免
疫,使 s jr(0) = (0;1).
若 hi = 0,表示节点 i没有被选中,则跳过节点
i,继续对其他节点进行是否选中的判断.
同时需要修改网络 G 的初始邻接矩阵 A(0),
若 si(0) = (0;1),则 ai j(0) = a ji(0) = 0, ( j= 1;2; �;N).
状态转换规则的第二部分用于传播的演化阶
段 (时刻 t > 0). 在演化阶段中,每个时间间隔内感
染节点以概率 a 感染它的邻居,同时每个单位时间
内感染节点也以概率 b 恢复健康;感染节点若在下
一时刻恢复健康,则该节点在恢复健康的同时以概
率 d 获得免疫. R-SIR-A模型中状态装换规则的第
二部分与 R-SIR-R 模型中演化阶段的状态转换规
则相同,这里就不再赘述.
用 S(t)表示在时刻 t网络中健康节点在所有节
点中所占的比率, I(t)表示在时刻 t 网络中感染节
200203-5
物理学报 Acta Phys. Sin. Vol. 62, No. 20 (2013) 200203
点在所有节点中所占的比率, R(t)表示在时刻 t 网
络中免疫节点在所有节点中所占的比率, R-SIR-A
模型也具有 R-SIR-R模型中 (17)—(19)式的结果.
3 传播阈值研究
本文参照文献 [7]的方法对 R-SIS模型进行验
证, 在其基础上改进了网络生成参数, 使得仿真验
证环境更加符合复杂信息系统中复杂网络拓扑的
实际情况. 通过仿真的方式研究 R-SIS模型在 NC,
ER, WS 和 BA 四种网络拓扑下感染率与传播率
l = a=b 之间的对应关系,与传统 SIS模型进行比
较分析;研究 R-SIS模型在四种网络拓扑下的风险
传播阈值,与三种常见的方法 [3;21;22] 得到的传播阈
值进行比较分析.
用来比较的三种常见的传播阈值计算方法分
别为
l1 = 1=hki; (22)
l2 = hki=hk2i; (23)
l3 = 1=t1;A; (24)
(21) 式中 hki 表示网络中各节点的平均度 [3]; (22)
式中 hki表示网络中各节点的平均度; hk2i表示网
络的平均均方度, 反映网络的异质化程度, 对于均
匀网络 hk2i = hki2,节点度分布越不均匀 hk2i值越
高 [21]; (23)式中 t1;A 表示网络邻接矩阵 A的最大
特征根 [22].
根据 NC 网络定义、ER 随机网络模拟算法
[23], WS 小世界网络模拟算法 [19] 和 BA 无标度网
络模拟算法 [20],生成这四种典型的网络,各网络参
数如表 1所示.
表 1 仿真网络参数
参数类型 NC网络 ER随机网络 WS小世界网络 BA无标度网络
节点数量 N 1000 1000 1000 1000
生成参数 — per = 6=999 pws = 0:2 m0 = 8, m= 3, p0 = 6=7
平均度 hki 6 6.0140 6 6.0040
平均均方度 hk2i 36 42.4320 37.0700 86.7560
聚类系数 C 0.6000 0.0060 0.3072 0.0326
邻接矩阵最大特征根 t1;A 6 7.2274 6.2373 15.1722
表 1中 per 表示 ER随机图中两个顶点之间有
边的概率; pws 表示WS小世界网络构造中的随机
重连概率.
图 4 R-SIS模型感染率与传播率的对应关系
在这四种仿真网络中研究 R-SIS 模型的传播
阈值, 传播参数的取值为: a 初始值为 0, 以步长
0.01线性增长到 0.8; b = 0:8; I(0) = 1=N. 已知传播
率 l = a=b , 在以上传播参数的设置下运行 R-SIS
模型, 统计运行 100 次中时刻 t = 250 时的感染率
的平均值,建立感染率与传播率 l 的对应关系,如
图 4所示.
从 图 4 中 可 以 看 出, R-SIS 模 型 在 四
种 网 络 拓 扑 中 的 传 播 阈 值 大 小 情 况 为:
BA< ER
(hk2iER)> (hk2iWS)> (hk2iNC),
说明网络拓扑中度分布的异质化程度越高,传播阈
值越小,符合文献 [7]. 并且图 4与传统 SIS模型感
染率与传播率的对应关系曲线 [24] 有着相似的符
合,这点也与文献 [7]一致.图 4中 NC网络有着最
大的传播阈值, 但随着传播率 l 的增大, NC 网络
逐渐有了较大的感染率.说明安全风险在 NC网络
中最不容易爆发. 此现象是由 NC网络的拓扑结构
所决定的: NC网络中节点之间的交互具有很强的
局域性,导致风险在扩散过程中能有效感染的邻居
数目受到局域交互特征的限制,因此传播阈值较大.
而同样是因为这种稳定而规则的局域特性,使得传
播率较大时 NC 网络中的风险影响规模依然能够
随着传播率的逐渐增大而不断扩大,最终感染率较
200203-6
物理学报 Acta Phys. Sin. Vol. 62, No. 20 (2013) 200203
高. 图 4中 BA网络有着最小的传播阈值,但随着传
播率 l 的增大, BA网络的感染率变得最小. 说明安
全风险在 BA网络拓扑中最容易爆发,但传播率较
大时, 影响规模较小. 此现象是由 BA 网络拓扑的
无标度特性所决定的: 在传播率较低时, 度数很大
的部分节点依然会比较容易受到感染,进而感染其
邻居节点, 导致安全风险的爆发. 因此 BA 网络中
的传播阈值较低. 但是当传播率较高时, BA网络中
度数小的部分节点受到感染的概率依然比较低,因
此 BA网络中安全风险最终的影响规模相对较小.
表 2 统计了四种网络拓扑下三种常见的传播
阈值计算方法的结果以及 R-SIS 模型中的传播阈
值.
表 2 传播阈值比较
传播阈值 NC网络 ER随机网络 WS小世界网络 BA无标度网络
l1 = 1=hki 0.1667 0.1663 0.1667 —
l2 = hki=hk2i 0.1667 0.1417 0.1619 0.0692
l3 = 1=t1;A 0.1667 0.1384 0.1603 0.0659
lR-SIS 0.2625 0.1375 0.1750 0.0875
Dl = jlR-SIS�l2j 0.0958 0.0042 0.0131 0.0183
Dl=l2 57.47% 2.96% 8.09% 26.45%
表 2将已有的三种方法得到的传播阈值与 R-
SIS模型得到的仿真阈值在数值上进行比较,可以
看出 ER网络、WS网络与 BA网络中的阈值与第
二种方法得到的阈值差异较小,其中 BA网络中的
阈值与第二种方法在数量上相差并不大,但是因为
BA网络中的阈值较小, 因此差异的百分比显得较
大.而 NC网络中的阈值与第二种方法得到的阈值
差异相对较大,这是因为虽然 NC网络中的度分布
十分均匀,但其节点的局域交互特性使得 NC网络
中传播阈值显著增加 [7].
4 传播演化研究
安全风险在复杂信息系统中一旦流行,其传播
速度及影响规模会受到多种因素的影响.在这一部
分本文侧重研究四种不同的网络拓扑对安全风险
传播的影响.图 5,图 6和图 7分别描述了 R-SIS模
型、R-SIR-R模型以及 R-SIR-A模型下安全风险在
NC网络、ER网络、WS网络和 BA网络中的传播
趋势及影响规模,网络参数仍如表 1所示.
在图 5中, R-SIS模型安全风险传播稳定后的
感染率 BA< ER ER>WS> NC, 说
明网络拓扑中度分布的异质化程度越高,安全风险
传播的速度越快,符合文献 [7]中的结论.这种现象
是因为网络拓扑中度分布的异质化程度越高,网络
中就存在着越多度数非常大的节点. 这些节点比较
容易受到感染,进而使得其相邻的节点也容易受到
感染,导致安全风险的传播速度较快.
图 5 R-SIS 模型安全风险传播趋势 (a = 0:3; b = 0:5;
I(0) = 2=N) (a) 为 R-SIS 模型中安全风险在 NC 网络中
的传播趋势; (b) R-SIS模型中安全风险在 ER网络、WS网络
和 BA网络中的传播趋势
200203-7
物理学报 Acta Phys. Sin. Vol. 62, No. 20 (2013) 200203
图 6 R-SIR-R 模型安全风险传播趋势 (a = 0:3; b = 0:5;
g = 0:01; d = 0:1; I(0) = 2=N)
图 7 R-SIR-A 模型安全风险传播趋势 (a = 0:3; b = 0:5;
p= 0:01; d = 0:1; I(0) = 2=N)
从图 6 和图 7 中 R-SIR-R 模型与 R-SIR-A 模
型安全风险传播趋势可以看出,在考虑免疫机制的
条件下, NC网络风险消亡的速度非常缓慢,但是免
疫机制能够将 NC 网络中安全风险的影响控制在
一个很小的范围内.这是因为模型中的免疫机制能
够将 NC网络演化成一种类似于群落网络的结构,
这种拓扑结构中群落内的连接较多而群落之间的
连接很少. 安全风险不容易从一个群落传播到其他
群落,因此能够将安全风险的影响控制在一个很小
的范围内.但是安全风险在各个群落内依然存在并
传播,因此风险消亡的速度非常缓慢. 在另外三种
网络拓扑中,安全风险消亡的速度 BA< ER
本文档为【基于元胞自动机的复杂信息系统安全风险传播研究】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。