有向复杂网络软件异常交互执行行为挖掘算法

段雪莹，王立君

(1. 吉林警察学院 信息工程系，吉林 长春 130012；2. 长春工业大学 信息传播工程学院，吉林 长春130012)

1 引言

有向复杂网络软件具备较高的稳定性与可靠性，可以提升软件抵抗攻击能力，确保软件信息不被破坏。软件的稳定性差、安全性低[1-3]，会提升企业的经济损失，最严重的可能导致企业破产。计算机技术快速发展，带动了软件的发展，明显增加了软件数量，互联网模式下，软件间的交互越来越频繁，频繁的交互过程导致该过程中出现异常交互执行行为的概率随之提升[4]。挖掘存在异常交互执行行为的关键节点，能够降低异常交互执行行为的出现概率[5]，提升软件的安全性。王倩等人依据结构熵的思想，按照节点出入度，求解上下结构熵均值，排序符合要求的关键节点，完成关键节点挖掘[6]，实验结果表明：该算法可有效挖掘关键节点；项英倬等人依据用户通信行为塑造通信网络软件模型，利用Flow Mine算法求解该模型，得到模型参数的近似估计值，完成节点信息流挖掘[7]，实验结果表明：该算法具备较快收敛性，有效挖掘节点信息流。上述两种算法仅适用于无向复杂网络软件，无法直接应用于有向复杂网络软件内，并未考虑缺陷传播节点与被缺陷影响的节点，无法挖掘存在异常交互执行行为的关键节点。为此研究有向复杂网络软件异常交互执行行为挖掘算法，精准挖掘存在异常交互执行行为的关键节点，为后续提升软件安全性提供科学参考。

2 异常交互执行行为挖掘

2.1 有向复杂网络软件异常交互行为区域确定

通过社交网络形式描述有向复杂网络，依据社区相似性，确定有向复杂网络软件异常交互行为区域，令图内社区是G，通过社区内节点集合V与边集合E构建G，若G内两个节点间具备边，代表这两个节点具备交互行为，则多节点间的连接被当成多节点的交互行为。

2.1.1 社区特征提取

mV=αMVT+(1-α)VT+α(1-α)Vc

(1)

令i的质量分数是mi，社区图内i和邻近节点连接交互边的特征值如下

(2)

式中，和i邻近的节点数量是num(a(i))；将节点质量得分与边缘质量得分分别当成节点与边缘的特征值。

利用局部哈希法提取社区图特征，特征提取的中心思想是：令包含n个节点的R变更成一组加权特征集合F={(ki，ti)}，特征ki属于R内节点标记，ti属于R内融合节点与边的质量分数后的特征值[9]，i∈{1，…，n}。将F当成输入，利用局部散列获取h位特征数组，在{-ti，+ti}内随机选取h个元素，在h维空间内任意投影各ti。通过散列函数操作投影，得到各ki变换后的特征值数组。数组长度只能是h位。令存在各个1的+ti和存在各个0的-ti元素彼此连接[10]。由全部h维向量融合成长度是h的单个向量σ，并将σ变更成位串形成数组指纹。若σ的第i个值是1，则σ为正值；若σ的第i个值是0，则σ为负值。设两个社区图分别存在σ与σ′，则两个社区图的相似度为σ与σ′内一致元素数量在元素总长度中的占比。

利用局部散列估计F与F′的相似度，公式如下

(3)

式中，F与F′的h位二进制数值向量为σ与σ′；σ与σ′变更的最小变更次数是H(σ，σ′)。完全相似度的值是0，最佳相似度的值是1。

通过函数Φ变更R，获取加权集，即Φ(R)=F。Φ为各R获取一组描绘该R属性的加权特征。通过Φ描绘R与R′的相似度，公式如下

Z(R，R′)=ZHash(Φ(R)，Φ(R′))

(4)

加权特征代表R内多节点间的连接关系，为节点对(u，v)分配节点v的质量，通过节点u的nout获取其特征值。只存在节点C的R内，F与H的子图R′的一组加权特征如下

F(R′)={(C，a)，(CF，a)，(F，a×b)，(FC，a×b)，

(FH，a×b)，(H，a)，(HF，a)}

(5)

式中，常数为a与b；遍历C全部交互边与节点求解S。

2.1.2 基于社区相似度的异常交互行为区域确定

通过式(5)能够获取两个社区图间的相似性差距，还需对比分析R′和其余社区图，得到最终相似性，将式(5)变更成

(6)

(7)

2.2 基于局部中心性的异常交互执行行为挖掘算法

确定完有向网络软件异常交互执行行为的R″后，依据局部中心性，挖掘软件异常交互执行行为的关键节点，通过调用函数X与被调函数Y描绘各关键节点的两个不同角色。在函数节点是X角色情况下，可按照一定的概率积累Y节点的缺陷；在函数节点是Y角色情况下，可按照一定概率传播自身缺陷至调用者。

2.2.1 定义

定义1：调用深度CaD(Call depth)：令包含一个函数间的有序的调用序列是(o1

定义2：出边邻居NOD(Nearest neighbors on out-direction)：在函数调用者检查调用函数节点q情况下，q的NOD是以q为起始点，q的CaD是1的节点集合，公式如下

NOD(q)={w|CaD(q，w)=1}

(8)

定义3：入边邻居NID(Nearest neighbors on in-direction)：利用Y检查q情况下，出入边邻居属于一个函数节点集合[11-13]，这个集合内随机一个节点至q的CaD都是1，公式如下

NID(q)={w|CaD(w，q)=1}

(9)

定义4：NOD最近与次近邻居NNOD(Nearest and next nearest neighbors on out-direction)：若q是函数调用者，那么NNOD(q)是一个函数节点集合，令q至该集合内随意一个函数节点的CaD均未超过2，公式如下

NNOD(q)={w|CaD(q，w)=1∨CaD(q，w)=2}

(10)

定义5：NID最近与次近邻居NNID(Nearest and next nearest neighbors on in-direction)：利用Y检查q情况下，那么NNID(q)是一个函数节点集合，令该集合内随机一个节点至q的CaD均未超过2，公式如下

NNID(q)={w|CaD(w，q)=1∨CaD(w，q)=2}

(11)

定义6：软件异常交互执行行为关键节点KN(Key Node)：令函数依赖G″内全部节点积累缺陷(传播缺陷能力)的均值是Avg；如果q的积累缺陷能力(传播缺陷能力)超过2倍的Avg，那么将q当成关键X节点(Y节点)。

令R″内被调函数节点p为q出边中的最近邻节点p∈NOD(q)，那么实际源码内q调用(依赖)p。若p存在缺陷，那么q会因其与p间的调用(依赖)关系积累p的缺陷，同时积累(传播)概率是Wq→p，即有向边权重。p内存在的缺陷为通过调用其余函数节点积累获取，主要来源是NOD(p)与{NNOD(w)|w∈NOD(p)}。Wq→p与q调用p的频繁程度成正比，与缺陷传播概率成正比[14]。

2.2.2 挖掘算法实现

已知调用函数节点q与被调函数节点p，以及有向边权重Wq→p，那么q积累因p传播获取的缺陷可能性即q通过u积累缺陷的能力A，公式如下

(12)

q积累其全部被直接调用函数节点的缺陷能力是q总的积累缺陷能力Atotal，公式如下

(13)

有向复杂网络软件异常交互执行行为挖掘算法共包含两个过程，分别是求解A(q，p)与Atotal(q)；具体步骤如下

步骤1：初始化Atotal(q)=0；

步骤2：求解q的NOD(q)；

步骤3：累加NOD(q)内各p的A，累加至内Atotal(q)；

步骤4：求解p的NOD(p)；

步骤5：求解和p存在调用关系同时CaD低于3的节点数量B；

步骤6：令Wq→p乘上B，得到A(q，p)；

步骤7：排序全部节点的A；

步骤8：求解R″内全部函数节点A的均值；

步骤9：挖掘满足关键函数节点条件的q，添加至节点集合内[15]；

步骤10：按照Atotal(q)对集合内函数节点的重要程度排序挖掘到的函数节点。

p通过q传播缺陷的能力A′公式如下

(14)

p的总传播缺陷能力A′total公式如下

(15)

p的挖掘过程与q的挖掘步骤一致。

3 仿真研究

3.1 仿真环境与数据来源

为符合用户使用的各方面需求，数个网络软件通常需要融合到一起，融合后的网络软件会存在交互关系，网络软件间的调用存在随机特征，易出现网络软件异常交互执行行为。利用Simulation Software仿真软件进行软件异常交互执行行为挖掘。将有向复杂网络开源软件Cflow与Tar作为仿真对象，令这两个软件应用过程中产生的交互信息作为两个数据集，展开仿真，Cflow为C程序分析工具，能够获取C程序内函数的调用过程，Tar为文件压缩与解压工具。利用本文算法挖掘两个数据集内的异常交互执行行为，验证本文算法挖掘的有效性。

3.2 性能分析

利用本文算法先确定两个数据集内的存在异常交互执行行为的社区，即确定数据集内异常交互执行行为区域，将两个数据集分别划分成99与91个社区，存在异常交互执行行为的社区确定结果如图1所示。

根据图1可知，本文算法可有效确定数据集内存在异常交互执行行为的社区，其中Cflow数据集内存在异常交互执行行为的社区数量明显高于Tar数据集，说明Tar数据集的安全性高。

图1 存在异常交互执行行为的社区确定结果

确定完数据集内存在异常交互执行行为的社区后，在挖掘社区内异常交互执行行为的关键节点，在两个数据集内异常社区内各随机选取一个社区，记作社区1与社区2，利用本文算法对这两个异常社区进行异常交互执行行为关键节点挖掘，有向边权重直接影响本文算法的挖掘效果，通过调整兰德系数仿真分析本文算法在不同有向边权重取值时的挖掘效果，选取最佳有向边权重取值，调整兰德系数指挖掘结果与实际结果间的接近程度，取值区间为[0，1]，其值越大，挖掘结果和实际结果越接近，仿真分析结果如图2所示。

根据图2可知，随着有向边权重取值的增长，本文算法在挖掘两个社区内异常交互执行行为关键节点时的调整兰德系数变化趋势基本相同，均呈先上升后下降的趋势，在挖掘社区1时，有向边权重为0.4与0.5时的调整兰德系数最高，在挖掘社区2时，有向边权重为0.4时的调整兰德系数最高，综合分析可知，在有向边权重取值为0.4时，本文算法的挖掘结果与实际结果最为接近，此时挖掘异常交互执行行为关键节点的效果最佳。

图2 不同有向边权重时的挖掘效果

本文算法的有向边权重值为0.4时，仿真分析本文算法挖掘社区1与社区2异常交互执行行为关键调用函数节点与被调用函数节点的结果，按照总积累缺陷能力与总传播缺陷能力对函数节点的重要程度综合排序关键调用函数节点与被调用函数节点挖掘结果，前十名关键函数节点挖掘结果如表1所示。

表1 关键函数节点挖掘结果

根据表1可知，本文算法可有效挖掘异常交互执行行为的调用函数节点与被调用函数节点，并有效依据总积累缺陷能力与总传播缺陷能力对函数节点的重要程度综合排序关键调用函数节点与被调用函数节点，排名越高的函数节点，其对有向复杂网络软件的影响力越大，及时控制这些节点，可有效提升有向网络软件的可靠性。仿真结果证明，本文算法可有效挖掘有向复杂网络软件存在异常交互执行行为的关键调用函数节点与被调用函数节点。

软件之间调用次数越多，出现异常交互执行行为的概率越高，仿真分析本文算法在不同软件间调用次数时挖掘存在异常交互执行行为的关键函数节点，挖掘结果如图3所示。

根据图3可知，软件调用次数越多，两个数据集内存在异常交互执行行为的关键函数节点数量越多，本文算法的挖掘结果与实际结果非常接近，说明本文算法能够精准挖掘存在异常交互执行行为的关键函数节点。

图3 不同软件调用次数时异常关键函数节点挖掘结果

4 结论

挖掘网络软件存在异常交互执行行为的关键节点，属于改善有向复杂网络软件稳定性与可靠性的关键步骤，为此研究有向复杂网络软件异常交互执行行为挖掘算法，依据社区相似度确定网络软件存在异常交互执行行为的社区，根据局部中心性挖掘社区内存在异常交互执行行为的关键函数节点。仿真结果表明：本文算法可精准挖掘存在异常交互执行行为的关键函数节点，为改善有向复杂网络软件稳定性与可靠性提供科学参考。