中国指挥与控制学会会刊 
随着网络服务的发展,业务系统呈现模块化、服务化趋势,需要通过调用不同服务完成系统功能,因此,业务系统间服务调用日趋复杂。如何在复杂的网络中寻找系统服务的关键点,成为网络空间作战中攻击者的首要任务,相应的网络防御者也需要找出这些关键点及其相关服务进行加固,以最小代价确保武器系统安全运行。但是当前网络拓扑构建主要以设备类型、操作系统等信息进行设备标注,难以反映设备服务间的从属关系,因此无法找出系统服务的关键点。社群结构是很多复杂网络中实际存在的,其结构为组内节点连接较为紧密,而组间节点的连接较为稀疏[1]。研究网络服务的社群有助于发现网络服务核心点及服务特征,为探究网络拓扑特性及系统运行链路描述具有重要意义。服务社群发现算法能够清晰地划分出节点间的服务映射关系,帮助网络防御者发现网络服务关键节点及关联关系。
1 相关研究现状
针对复用服务与关键节点的关系描述,可以利用重叠社群的描述方法进行服务划分,首先,基于模糊聚类分析的算法通过计算节点与社群间的模糊隶属度,实现节点划分,结合模糊数学求出隶属度矩阵[7];其次,基于边聚类算法[8],如SLPA(Speaker-Listener Label Propagation Algorithm)[9]采用边传播策略对历史信息进行读取分析。上述方法解决了复用节点与服务社群间关系问题,但是难以根据节点类型进行重要度区分,无法还原网络服务的社群结构。因此,基于核心节点扩散的思想能够满足网络服务关系描述的需求,其中,LFM(Local Fitness Maximization)算法[10]能够随机选取核心节点,通过观察删除节点后适应度变化寻找新的社群及交叉区域。
针对上述问题,利用重叠社群发现思想,本文提出了一种基于服务映射的网络服务节点划分算法,既能够适应多平台调用造成的多归属的现实问题,又能实现网络异构平台的高效划分。基于服务间调用关系不断完善社群划分,主要工作有:
1) 提出一种基于服务映射的网络服务节点表示模型Service Map-Community,用于描述网络内服务节点之间的服务划分和通联关系,帮助网络防御者描述服务节点间的关联程度。
2) 提出服务映射算法(Service Mapping Algorithm, SMA),在全局变量中引入局部服务映射关系,分布式迭代,提高社群挖掘效率,通过关键服务节点实现高效的服务社群划分。
3) 在服务映射算法得到的服务社群基础上,提出了能够反映服务节点对全局网络影响度和对所在服务社群影响度的影响度算法(Degree of influence Algorithm),该算法能够定量给出服务节点的重要程度及演化规律,找寻高价值节点。
2 基于服务映射的重叠社群发现
本文认为网络主要由平台节点和服务节点共同组成,平台节点通过调用服务提供综合服务,因此作为社群核心节点构建网络社群图,其中平台ki(i=1,2,…)为核心节点,连接相关服务vij(j=1,2,…, m)形成网络结构子群,服务网络可以表示为一个五元组W:
W=(G(V,E),D,P)
其中,图G由服务节点集V及其关联边集E组成,其中节点分为平台节点和服务节点。节点V=Vk∪Vu,其中Vk={k1,k2…kn}表示平台节点,Vu={vi1,vi2…vim}表示服务节点。
D为网络图G中的社群D={C1,C2…CP},其中Ci表示网络中第i个子群,p为子群个数。
如图1 所示,当服务vq6和vq9被另一个核心服务调用时,可以作为以平台Kq+1为核心的社群Cq+1与社群Cq间存在交叉区域, Kq和Kq+1作为服务社群的平台节点是整个系统的核心,应受到最高的关注,业务系统成员vq1,vq2,…vq9为其提供服务资源。而对社群Cq和Cq+1不断更新和拓展操作,最终会形成一个复杂的服务网络(圈内节点为不同社群的服务网络,圆圈表示重叠调用服务)。
根据描述,给出如下定义:
定义1 社群核心节点发现,定义初始网络G,求网络中的平台节点Vk。
服务重叠社群发现算法需要获取核心服务节点。当Ci∩Ci+1=Vi,i+l且Vi,i+l≠ϕ时,Vi,i+l为社群重叠节点集合,l为Ci和Ci+l相交区域内节点个数。
定义2 给定G及其对应的平台节点Vk,求核心服务为中心的社群划分D及重叠区域集V'。
P为隶属度函数,用于表示服务相对于平台的隶属度矩阵,具体将在第4节进行介绍。
根据模型描述,社群主要由关键服务节点、关联节点及其映射关系组成,其中平台角色(Platform Enterprise, CE)为关键服务节点,服务角色(Service Enterprise,SE)为关联节点,节点映射关系表示关键服务节点映射规则。提取与平台节点具有调用关系的服务节点过程如下:
定义3 直接映射。节点v到节点v'之间存在直接映射f,即v'直接调用v的服务,关系如下:
f:v→v',v∈N
定义4 间接映射。节点v和节点v'不相邻,但节点v通过中间节点xi与v'构建映射关系,即v'通过调用xi中的v服务形成映射关系,关系如下:
g:v|→v'
定义5 节点映射平台社群。在服务网络中存在平台pe和调用服务se存在直接映射关系pe→ce和间接映射pe|→se,则记为以pe为中心点的社群
Map-Communitype=
基于上述定义构建Service Map-Community模型。
3 服务映射算法
服务社群发现节点算法包含边过滤、关键服务节点发现、社群扩展和社群分割四个阶段。
3.1 边过滤
通过边过滤,消减不参与重叠社群发现的非平台节点,进而聚焦重叠社群区域,关于边过滤问题,定义如下:
定义6 双连通图。网络图中G(V,E)存在一个极大图G'(V',E'),若G'中任何顶点间不存在连接点,则称图G'为双连通图。
定义7 双连通核心图。设Es为单边双连通图集合,则双连接核心图Gc=(Vc,Ec)是E剔除Es后极大连通子图,表示为G″=(V,E▷Es)。
定义8 桥。所有直接连接双连通核心图的割边集合为桥,记作Er,且Er⊆Es。
定义9 连接极大子图。通过桥与双连通核心图连接的极大子图为连接极大子图P=(Vp,Ep),通过删除桥降低双连通核心图连通度。
将桥及非双向连通图的节点构建图GD,所有与Gc相连的连接极大子图P属于GD,则表示如下:
∀GD=(VD,ED),V▷Vc
如图2 所示,大圆代表顶点相关的双连通核心图区域,虚线圆形部分表示连接极大子图,其中两部分的连线为桥。通过将连接极大子图删除,获取双向连通核心图的核心部分V={vi,vi+1,vi+2,vi+3,vi+4},且连接极大子图之间无重叠,不需要进行社群重叠发现。
3.2 关键服务节点选择
需要从双连通核心图的节点中提取核心服务节点,具体定义如下。
定义10 根据节点间的关系构建n×n阶临界矩阵A,其中节点i与节点j间的连通度aij表示如下:
aij=
定义11 对于节点u,与其他节点连接的边定义为节点u的度数D(u),可以利用度衡量节点u与周围节点的通联度。
定义12 用关联度I描述两个节点间的关联程度,定义如下:
I(u,v)= =
其中,d(u,v)表示节点u和节点v的关联度,与jaccard系数互补[13],即d(u,v)=1-jaccard(u,v)。当jaccard系数越小,则节点u对节点v的映射影响越小,二者属于同一社群的可能性越小。
通过节点u遍历图中相邻节点,计算节点间的映射度,根据映射度建立映射函数F(u),定义如下:
F(u)= I(u,v)=
根据上式可知F(u)越大,说明该节点与周围节点的关联度越大,其显著性越强,因此,候选节点u成为关键服务节点的可能性越大。
关键服务节点选择过程中,首先,对候选节点进行两两关联度计算,获取节点关联度I,根据I计算每个服务节点的映射度。在同一个社群的节点中,存在某个服务节点映射度高于其他相邻节点,则认为该节点为平台节点。
算法1 社群内关键服务节点选择算法 |
| 输入:双连通核心图Gc=(Vc,Ec) 输出:关键服务节点Vc |
|---|
| 1 For u∈Vc and (u,v)∈Ec |
| 2 compute I |
| 3 compute F(u) |
| 4 end for |
| 5 for u∈Vc |
| 6 if v∈N(u) and F(u)≥F(v) |
| 7 Vk←Vk∪{u} |
| 8 end if |
| 9 end for |
| 10 return Vc |
3.3 社群扩展
根据Service Map-Community模型可知,任意节点u的直接映射节点为相邻节点N(u),选取u任意相邻节点v,利用其相邻节点集合N(v)寻找间接映射节点,以此为条件遍历所有可能的映射节点。以映射值最大的关键点作为出发点,遍历度量其关联节点的映射值,以此作为社群发现的依据。该遍历过程通过比较节点间的映射强度确定社群归属,判断条件如下:
定义13 直接映射判断。在双连通图Gc中,选择两个联通节点u和节点v,根据其映射值判断节点间的映射关系,确定节点所在社群,映射规则如下:
F(u)?F(v)
利用文献[14]方法进行映射判断,存在节点u的社群Cq,若F(u)>F(v),则节点v属于社群Cq,若F(u)≤F(v),则节点u可能从属节点v,也可能分属不同社群,故结果取空。
定义14 间接映射判断。存在(v,y)∈G,计算v和y映射度占节点y映射度的比重,进而推导与v有直接映射关系节点间u与y的映射关系,具体计算如下:
map(v,y)=
当map(v,y)=1时,节点u与节点y具有强间接映射关系,且同属一个社群;当ε≤map(v,y)<1,节点u与节点y具有的间接映射关系同属一个社群,其中ε为自定义阈值影响间接映射稀疏程度,ε越大,节点间接映射关系越强,节点越密集。当map(v,y)<ε时,节点u与节点y不存在明显间接映射关系。
依据2.2节获得关键服务节点集合,在此基础上扩展关联节点构建社群。首先,选择关键服务节点集合中最大函数映射值节点k,并构造节点k的相邻节点集合N(k)。然后,在N(k)中找寻关键服务节点,根据直接映射计算公式,找出k的直接映射点,并判断社群归属。最后,非关键服务节点利用直接映射点和map公式找出间接映射点和社群归属,算法具体过程如下:
算法2 社群扩展算法 |
| 输入:节点集合V及函数映射值F(u) 输出:社群Ck及Ck集合D |
|---|
| 1 If (n(V')=n(V)) |
| 2 /* V'表示已被扩展节点集合,F'表示未被扩展节点*/ |
| 3 /* n(V')表示已被扩展点的数量,n(V)表示节点总数* |
| 4 return D |
| 5 end if |
| 6 *寻找最大函数映射值节点k,并以此为核心创建社群C'k */ |
| 7 Ck←ø |
| 8 k←max(F(u)); |
| 9 Ck←Ck∪{k} |
| 10 D.put(k,Ck) |
| 11 V'←status(k) |
| 12 for each v∈N(k) and F'=status(v) do |
| 13 /*直接扩展*/ |
| 14 F(u)?F(v) |
| 15 Ck.put(k,Ck) |
| 16 V'←status(v) |
| 17 end for |
| 18 for each y∈N(v) and F'=status(v) |
| 19 /*间接扩展*/ |
| 20 if map(v,y)<ε |
| 21 continue; |
| 22 end if |
| 23 Ck=Ck.get(k) |
| 24 Ck←Ck∪{y} |
| 25 Ck.put(k,Ck) |
| 26 D.put(k,Ck) |
| 27 V'←status(y) |
| 28 end for |
| 29 return D |
3.4 社群边界划分
在双联通核心图中,通过关键服务节点选择和社群扩展阶段完成基本服务社群分割。但是社群间的边界还未划分,因此,利用边过滤产生的连接极大子图中的节点和双连通图的映射距离进行边界确定。
假设服务网络为无向图,其邻接矩阵An×n对称,用L(Ci,Cj)(i,j=1,2,3…n,其中n为节点个数)表示社群i,j的边权和,利用三个测度要素进行社群分割判断。
定义15 割组值。社群Ci及其补元的V▷Ci的边权和,记为cut。
cut(Ci)=L(Ci,V▷Ci)
定义16 传导。社群Ci及其补元V▷Ci中的较小边权一方离开社群的概率。
P(Ci)=
定义17 归一化切割。
ncut(Ci)=
设Ci相连桥为 ,相连的连接极大子图 ,其中 =( , ),wj=(Vj,Ej), = Vj, = Ej。
社群边界划分在原有社群Ci的基础上扩展值C'i,当存在可连接的桥,则|Ci|≥|C'i|,否则|Ci|=|C'i|。此时cut(C'i)=cut(Ci)-L( ,Ci),C'i割组满足ncut(C'i)≤ncut(Ci)。具体过程如下:
算法3 社群边界划分算法 |
| 输入:原图G=(V,E),双连通核心图Gc=(Vc,Ec),社群划分结果D 输出:划分完成社群G'i |
|---|
| 1 while(Ci∈C) |
| 2 Ci detect |
| 3 for bj∈ do |
| 4 bj detect wi |
| 5 C'i←Ci∪Vj |
| 6 end for |
| 7 end |
| 8 return G'i |
4 网络服务社群隶属关系影响度算法
为了研究网络服务关系演化过程,需要从全局层面上给出网络服务相对于社群的隶属关系。隶属矩阵经常用于描述个体相对于总体的关系[15],因此,在本文中将N个服务节点N(c)相对于社群Ck的隶属关系表示如下:
P=[aij]N×k,0≤aij≤1, aij=1
上述公式可以用于描述具有重叠聚类网络服务的隶属关系。但是,上述公式无法正确反映隶属程度。
因此为了适应网络服务隶属度及明确社群在全网的地位,需要对社群隶属度矩阵进行改进,使其具有以下特征:
1)由于整个网络社群服务在网络中的关注度与其系统规模呈正相关,即服务社群规模决定隶属度矩阵权值。
2)一个网络系统往往是由一个管理服务和几个关键服务共同组成,其节点连通度往往最多,而大量附加服务通过他们形成整个系统社群,因此,节点在社群中的核心度与其社群隶属度呈正相关。
3)为了实现隶属度计算归一化,可假设网络外部设置一个虚拟社群,核心节点的隶属度为1,具有映射关系的节点提供服务部分参与至虚拟社群中,假设其所在社群的隶属度为δ<1,而虚拟社群的隶属度为1-δ,通过调节δ,实现个体在整个网络中的关键程度分析。基于上述分析,定义改进隶属矩阵如下:
定义18 在由N个网络节点组成的具有k个社群C1,C2…Ck的网络G,其中|Ck|为第k个社群的成员个数,w(u)作为社群节点u的核心度值,社群Ck的全局影响权值为log|Ck|,基于社群Ck的全局影响力值定义为w(ei)log|Ck|,根据上述分析,单个节点对于全社群影响力为
w(u)=(F1(u)log|C1|,…,Fk(u)log|Ck|)
其中Fk(u)为节点u与社群Ck中节点的映射值。
定义19 作为具有最大影响力节点,网络G全体成员的社群隶属度向量为
= ,k=1,…,N
其中‖.‖1表示向量1-范式。经归一化后,网络中所有核心节点的社群隶属度之和‖ ‖1=1,其余节点社群隶属度之和均小于等于1。
定义20 设 为节点u相对于k个社群的隶属度向量,δi=‖ ‖1,矩阵P为网络G的隶属矩阵:
P=
其中, , ,…, 是N个k维向量,表示N个节点对k个社群的隶属度,1-δ1,1-δ2,…,1-δN表示对k个社群的隶属度的其余分量。
上述隶属矩阵在与传统隶属矩阵保持一致的前提下,能够反映个体在整个网络中的作用和地位,在矩阵中每一列表示一个社群,社群隶属度取值不仅与社群的规模有关,还与节点的重要程度有关。
5 仿真实验及分析
为了验证网络服务重叠发现社群及隶属矩阵的有效性,从LFR(Lancichinetti-Fortunato-Radicchi)算法敏感度、网络性能测试及仿真实验三方面对其进行评估。
5.1 LFR网络实验
LFR是由Lancichinetti提出的用于检验社群发现算法有效性的测试网络[16],能够根据需求进行网络拓扑形态设置,通过计算,可设置的参数如表1 所示。
表1 LFR参数Tab.1 LFR parameters |
| 序号 | 符号 | 解释 |
|---|---|---|
| 1 | n | 网络节点数 |
| 2 | k | 平均节点度 |
| 3 | kmax | 网络中最大节点度 |
| 4 | om | 社群数量 |
| 5 | on | 社群重叠节点数 |
| 6 | Cmax | 社群最大规模 |
| 7 | Cmin | 社群最小规模 |
| 8 | T | 社群度与社群容量的幂律分布指数 |
| 9 | u | 社群内外节点边数与节点度数的比值 |
利用规范互信息(Normalized Mutual Information,NMI)进行衡量[17],定义如下:
NMI(Ca,Cb)=
其中,Ca表示LFR网络社群结构,Cb表示通过算法获得社群划分,N为混淆矩阵,Nij表示第i个社群在第j个算法中节点情况,Ni·N·j表示矩阵第i行和第j列的和。NMI(Ca,Cb)为[0,1]上相似函数,且随着NMI(Ca,Cb)值的增加,其算法生成的社群与LFR网络社群结构一致性越高,表明算法有效性越好。
5.1.1 算法敏感度实验
由于直接映射通过固定值进行比较获得,因此,对算法结果无影响,故不存在变量。间接映射判断中存在阈值ε用于圈定社群,由于ε≤map(v,y)<1,ε越大节点越难以进行映射关联,社群节点越少。因此在给定的LFR网络静态参数n=2 000,k=20,kmax=50,om=5,on=20,Cmax=50,Cmin=10,u=0.2下研究ε与NMI(Ca,Cb)值的关系,通过改变幂律分布指数T改变网络分布,结果如图4 所示。
从图中可知,不同的T下其NMI值均在0.83以上,说明不同阈值下算法皆有较好的适应性。当T=-2时,表明网络中存在少数过饱和节点,此时网络节点差异度较高,因此,该算法同样使用于度分布不均的网络。
5.1.2 算法性能对比实验
将该算法与常用算法进行比较,利用NMI对算法效率和算法准确度进行分析。选取LFM、COPRA(Community Overlap PRopagation Algorithm)、FA(Firefly Algorithm)3类基于核心节点的社群发现算法,不同算法时间复杂度对比结果如表2 所示。
表2 不同算法时间复杂度Tab.2 Time complexity of different algorithms |
| 算法 | 算法复杂度 | 解释 |
|---|---|---|
| SMA | o(m+2n+nk) | k社群数 |
| LFM | o(ncs2) | nc社群数,s社群平均节点数 |
| COPRA | o(Tlg(vm/n)) | T标签代数,v标签数 |
| FA | o(mh) | h初始节点数 |
由于LFM算法、COPRA算法与社群的划分方式有关,算法复杂度随社群平均节点数呈正相关,FA算法只与初始图相关且算法效率较低。而SMA算法复杂度主要由社群数量决定,在大规模低社群数量的图中算法复杂度具有优势,满足服务网络组内节点连接较为紧密,而组间节点的连接较为稀疏的特点。
在k=20,kmax=50,om=9,T=-2,on=20,Cmax=50,Cmin=10静态参数下,通过改变n和u的取值构造不同规模和分布的LFR网络,n分别取值2 000和10 000,分别取值0.3和0.6,通过对比不同社群数量下不同算法的MNI值,并进行算法有效性对比分析,结果如图5 所示。
当n不变,u值从0.3到0.6变化过程中所有算法的NMI值下降,表示产生的社群区分度下降,由于COPRA算法利用节点间隶属度进行划分,当社群区分度不明显时,隶属度差距较小,故NMI下降较大。当u不变时,n从2 000到10 000的变化过程中MNI下降不明显,由于算法皆是以核心节点为起始点进行社群扩展,受全局变量影响较小,所以算法对节点数量不敏感。从划分结果看,该算法相较于其他算法在区分程度上效果更好。
5.2 算法仿真
为了验证算法实际有效性,利用mininet根据Internet2 OS3E[18]网络拓扑构建具有38个节点42条链路的仿真网络,如图6 所示。在网络中有控制器、交换机、服务器和终端共4类服务节点,地图上每个节点表示一个服务群(包含5-15个终端或服务器),在无权无向网络中运行5个不同服务。利用开放端口号和协议类型进行服务模拟,相同端口号和协议号代表一类服务。
根据算法获得1、11、8、16、35共5个核心服务节点,以部分节点社群划分为例,进行算法具体过程描述,如图7 所示,由于连接边不存在桥,故无须进行边过滤。
首先计算节点映射值,计算结果如表3 所示。
表3 节点映射值Tab.3 Node mapping values |
| 节点 | 映射值 | 核心节点 | 节点 | 映射值 | 核心节点 |
|---|---|---|---|---|---|
| 5 | 8 | 否 | 8 | 467.33 | 是 |
| 2 | 27 | 否 | 10 | 87 | 否 |
| 1 | 345.72 | 是 | 13 | 85 | 否 |
| 4 | 49 | 否 | 14 | 34 | 否 |
| 9 | 15 | 否 | 20 | 13 | 否 |
| 3 | 144 | 否 | 14 | 26 | 否 |
| 6 | 157 | 否 |
设阈值ε=0.5,根据表3 结果进行社群直接映射关系迭代,根据计算结果,社群{C1,C8}的重叠区域为节点3和节点6,结果如图8 所示。
继续利用SMN算法进行社群划分计算,最终结果如图9 所示。
通过上述仿真,生成以1、11、8、16、35为核心的5个服务社群,记作{C1,C11,C8,C16,C35},其中{C1,C11}重叠区域为节点5,{C1,C8}重叠区域为节点3、6,根据实验结果,依次向以16节点为核心的网络服务社群中节点发送20 000个长度为1 232byte的UDP包,模拟DDos攻击统计节点失陷率,结果如图10 所示。根据结果可知,核心节点16作为整个服务社群的核心,其对整个社群的影响较大,攻击或保护该节点能够取得最大的收益,且直接映射关系节点对网络影响大于间接映射的节点。
由实验结果可推知以下结论:
1) 根据社群内的高联结度可知,5个核心节点决定异构环境的社群归属结构,且其节点隶属度最高,保护核心节点能够最大限度保护当前网络服务运行。直接映射节点由于直接向核心节点提供服务,往往与其他服务社群关联较小,其全局隶属度较低,破坏直接映射节点影响范围较小。
2) 根据服务社群间的低联结度可知,不同服务间的互动较少,难以通过破坏某几个节点实现所有服务的毁瘫,服务间关联往往存在于间接映射节点中,因此破坏间接映射节点能够影响服务范围最大。
3) 利用全局影响度可知,核心节点的影响度最高,因此保护核心节点的收益最大。
6 结束语
本文针对网络服务节点关系提出了服务映射算法,用于梳理相关服务节点间的核心关系和不同服务的社群节点划分。SMN算法利用节点发现和关系映射算法获取网络服务,能够帮助运维人员在繁杂的网络中找寻关键服务节点。本文同时提出了网络服务社群隶属关系影响度算法,该算法能够给出节点的全局隶属度和服务节点的定量分析,为服务节点演化分析提供了基础。利用LFR基准网络对不同算法进行算法敏感度和性能对比分析,结果表明SMN算法性能最佳,且适应度较好。后续将在该算法的基础上,进行服务节点演化分析,用于捕获服务迁移对网络服务社群的影响。