基于图论分析恶意代码传播过程

2020-02-01米昂

电子技术与软件工程 2020年10期

米昂

（国家计算机网络应急技术处理协调中心上海分中心上海市 200000）

1 构建传播过程图

我们将网络中的终端、服务器作为图的节点，对于通过流量分析等相关网络安全检测手段发现的攻击行为，可以形成从源节点到目的节点的一条有向边，并最终形成一张有向图[2]，我们称之为传播过程图G(V,E)，其中V 为网络中节点的集合，E 为根据检测攻击形成的有向边的集合。对于每一条有向边e∈E，附加属性t(e)表示该攻击行为被检测到的时间，即每条有向边使用e(vi,vj,t(e))进行标识[3]。如图1、表1，即是恶意代码传播过程图的示例。

由于实际网络空间中，存在网络安全检测手段覆盖不全面，以及恶意代码传播过程中有多个源节点且感染过程并非覆盖全部节点等情况，所以形成的传播过程图必然存在多个联通分量。对于非常小的联通分量，甚至是孤点，并没有分析的价值，所以对于此种情况，我们设定联通分量包含的节点数量阈值D，当联通分量包含的节点数量少于阈值时，舍弃该联通分量不进行后续分析。

通过上述构建过程，我们获得了该恶意代码的传播过程图。

2 传播过程图的分析

2.1 感染判定

由于蠕虫类恶意代码的传播性是其基本特征，受感染的节点一定会发出相关攻击载荷。而节点的出度为0，说明在接收到攻击载荷后，节点并未向外继续发送攻击载荷，则可证明该节点未被感染成功，反之则可确认成为沦陷节点。我们定义以vi 为源节点的所有有向边集合为Es(vi)，则vi 节点的感染状态hacked(vi)为：

结合全部沦陷节点的操作系统、应用等软硬件信息普，可以快速分析出该恶意程序感染主机的共性，从而关联发现网络内潜在的其他危险主机。

2.2 社区发现

沦陷节点的相邻沦陷节点越多，则证明该蠕虫对此节点相邻节点的攻击成功次数越高，而由于同一款恶意代码在攻击中利用的漏洞列表相对固定，由此基本可以判定这些节点在软硬件环境方面趋同，所以从传播过程图中沦陷节点的聚集行为即可判断该子网络为一个社区，从而有针对性的制定处置方案，较为常见的场景有服务器集群、数据中心、云平台、办公终端网络等。

2.3 传播路径与重要节点

由于沦陷节点对相邻节点的探测攻击是无差别的，即存在重复感染的情况，从而在上述构建传播过程图的过程中，必然存在大量重复边与环路等情况，为后续的分析带来不必要的复杂度，所以在进行进一步分析之前，需要先进行预处理。

2.3.1 预处理

表1：传播过程图示例数据

如果两条边有相同的源节点和目的节点，而作为附加属性的时间不同，我们可称其为重复边，对应的实际情况包括恶意代码在沦陷主机上定期不间断的扫描攻击周边节点或该节点被重复感染等。由于每条有向边代表着一次尝试的扫描感染行为，所以我们仅需保留最有可能成功的一次即可。而感染成功的网络特征是目标主机也开始对外发送感染行为，所以我们需要保留的就是距离目标主机第一次向外发送攻击行为之前、时间最近的一次受到攻击感染的行为。所以，我们对于重复边的处理方法是：

（1）定义以vj 为源节点的所有有向边集合Es(vj)，其中有向边附加属性中的最小时间值，称为节点vj 的最早向外攻击时间Δt(vj)，即：

（2）对于节点vi 发出至节点vj 的所有重复边集合E(vi,vj)，仅保留时间属性早于且最近于vj 节点最早对外攻击时间Δt(vj)的有向边。具体算法如图2所示。

通过对重复边的裁剪，我们也可以有效去除图中的环路。如图3所示，假设我们自v0 进行裁剪后，剩余的边e0、e1、el，必然存在t(e0)

1.在对E(vk,v0)进行裁剪时，若vk 至v0 的所有有向边时间都晚于v0的Δt(v0)，则E(vk,v0)中的所有边均会被移除，从而消除环路;

2.若E(vk,v0)中存在时间早于Δt(v0)的边，则按照上述方法保留合适的有向边ek(vk,v0,t)，且可知t(ek)t(e0)>t(ek)，所以按照上述裁剪算法，el 边将被裁剪，从而消除环路。

2.3.2 基于图论的分析

经过上述预处理过程，将传播过程图进行有效简化，从而使得基于图论对恶意代码传播过程的分析变得易于进行，相关分析维度可包含：

2.3.2.1 关键节点分析

定义以vi 为目的节点的有向边集合为Ed(vi)，vi 节点的入度InD(vi)取值如下：

InD(vi)=[ Ed(vi) ]

由此可知，传播过程图中入度为0 的节点存在两种情况，一种是该节点未接收到过任何主机发来的攻击行为，另一种是由于其接收到攻击行为的时间晚于自身发出攻击行为的时间，所以在预处理过程中接收感染的行为被裁剪。由环路裁剪过程分析可知，第二种情况下，该节点在形成的传播路径中所发出的攻击行为时间最早，所以这两种情况都可以反映出，该类节点是联通分量中较早受到感染的节点，甚至是感染源头。

2.3.2.2 传播路径分析

使用改造的深度优先算法可以找到任意两点间的全部路径，具体算法这里不再赘述。而结合该算法，遍历所有以入度为0 的节点为源点、以出度为0 的节点为终点的组合，可以找出该恶意代码的全部传播路径，算法过程如图4所示。再结合实际中主机节点的软硬件、使用日志等相关信息，即可进行有效的传播溯源。

同时，利用全部传播路径可以获得平均路径长度值，该值可以反映出该恶意代码在传播感染过程中所使用漏洞的普遍性。平均路径长度数值越大，说明恶意代码的可传播性越强，而该网络中相关主机有效的防御能力越弱。

2.3.2.3 关键路径

传播过程图做为有向图，其中传播路径上的必经边是关键的传播路径，必经点集合也同样是传播的关键节点，通过传统的Tarjan算法即可将其找出。结合实际网络情况，有效的对必经点集合中的主机节点进行网络安全加固，切断必经边，就能够有效的阻止恶意代码的蔓延，为进一步抵抗恶意代码传播提供防御加固的参考。