1.本发明涉及威胁检测技术领域，具体而言，涉及一种基于系统溯源图搜索匹配攻击模式的在线系统及服务器。
背景技术：2.目前，长时间、大规模、持续隐秘的apt攻击在网络安全攻防中扮演着核心角色，这种攻击会利用多种技术手段，隐秘地长时间潜伏在设备中。由于它使用的技术手段多样，潜伏期长，简单的基于文件名或者文件哈希的病毒或木马检测很难生效，因此必须在更加基础的层面，结合底层的系统行为进行检测。为了实现这一目的，就需要对系统底层行为进行记录。
3.系统溯源图将底层系统行为建模为一个有向无环图，它可以用于后续的威胁检测。一般的系统溯源图由实体与实体之间的关系组成，对于系统底层行为而言，实体用于指代系统的进程、套接字、文件描述符、网络流数据或内存数据等对象，实体之间的关系包括了进程的创建和销毁、文件读写等事件。通过记录系统底层对象及其变化，系统溯源图使得安全人员可以查看、追踪并最终确认系统的状态和导致相应状态的原因。
4.现有技术中一些工作会使用控制流或者应用日志作为威胁检测的基础，但是这些信息不够全面，容易被apt攻击绕过，而底层系统行为可以提供更加丰富全面和完整的信息，也更加难以被绕过，可以作为对复杂攻击的威胁检测的基础。lfs(lineagefilesystem)是系统溯源领域较为早期的一项工作，它提出了一个新的文件系统，不仅储存文件和文件相关的标准属性，同时会将文件的世系信息储存下来，这些信息可以用于重新创建文件本身。hi-fi基于linuxkernel提供的lsm(linuxsecuritymodule)，提供了系统级别的溯源能力，但是它与其他的lsm模块如selinux不兼容。camflow克服了这一缺陷，它也作为linux的一个安全模块提供，用户可以自主选择是否开启。其工作原理依赖lsm提供的钩子和netfilter模块。钩子使其在一个内核对象被创建或访问时被调用，进而记录内核对象的变更信息。netfilter则保证了对网络传输数据的记录。camflow提供了全系统溯源的能力，并且易于使用，可以在云上部署。
5.大部分网络威胁情报并没有在威胁检测实践中得到有效利用，目前的利用方式存在以下缺点：
6.·
cti情报的种类和数量都日渐增长，越来越多，仅以cve漏洞库为例，截止2022年3月31日，全部条目数就达到了172930条。由于cti情报数众多，仅仅凭借人力是难以了解全部的攻击情报的，当然也就不能在实际工作中进一步使用这些情报。
7.·
对于攻击行为模式的记录和描述实践中难以直接利用，特别是自动化的利用威胁情报。目前普遍利用的自动化的威胁检测使用到的威胁情报过于具体和细节，对于较为一般化的网络攻击行为模式，大多数时候只能作为安全专家的经验进行转化，利用效率不高。
技术实现要素：8.本发明提供一种基于系统溯源图搜索匹配攻击模式的在线系统及服务器，用以克服现有技术中存在的至少一个技术问题。
9.本发明提供的一种基于系统溯源图搜索匹配攻击模式的在线系统，部署在集群服务器上，所述在线系统基于python开发，所述在线系统包括：
10.输入层，用于输入攻击图以及系统溯源图；
11.攻击模式匹配运算层，用于
12.利用攻击图拆分算法对攻击图进行划分，获得攻击子图；
13.根据系统溯源图与攻击图对应拓扑关系，使用候选图匹配算法搜索在所述系统溯源图中查找与攻击子图匹配的候选子图；
14.使用子图同构算法对候选子图进行图压缩，得到完整候选图；
15.利用相似度排序方法对每个完整候选图与系统溯源图的相似度进行排序；
16.根据排序第一的完整候选图，确定是否需要输出威胁告警；
17.输出层，用于输出威胁告警。
18.第二方面，本发明提供的一种服务器，部署第一方面基于系统溯源图搜索匹配攻击模式的在线系统。
19.本发明实施例的创新点包括：
20.1、本发明提供了一种基于系统溯源图搜索匹配攻击模式的在线系统，部署在服务器上，本发明的攻击模式匹配层具备良好的检测能力，能够有效帮助安全人员检测系统内是否存在与给定攻击模式类似的行为。
21.2.本发明的攻击模式匹配运算层可以将攻击图划分为多个互不重叠、规模更小的攻击子图，这可以缓解图匹配问题的复杂程度随图节点规模呈现指数级上升的问题，并且提供了对攻击图的模糊匹配能力，从而允许匹配结果中缺失部分节点。
22.3.本发明的在线系统可以从与攻击子图同构的溯源图子图中恢复得到候选图，这是攻击模式匹配层的重点为实际网络运行环境提供高效的威胁检测。是本发明实施例的创新点之一。
附图说明
23.为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。
24.图1为本发明提供的一种基于系统溯源图搜索匹配攻击模式的在线系统的内部示意图；
25.图2为本发明提供的节点导出子图同构示意图；
26.图3为本发明提供的weisfeiler-lehman图哈希算法示意图；
27.图4为本发明提供的系统溯源图节点的度数分布图。
具体实施方式
28.下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有付出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
29.需要说明的是，本发明实施例及附图中的术语“包括”和“具有”以及它们任何变形，意图在于覆盖不排他的包含。例如包含了一系列步骤或单元的过程、方法、系统、产品或设备没有限定于已列出的步骤或单元，而是可选地还包括没有列出的步骤或单元，或可选地还包括对于这些过程、方法、产品或设备固有的其它步骤或单元。
30.本发明的系统基于python进行开发，版本为3.9.7，包括三个核心部分：攻击图划分模块、候选图匹配模块和相似度排序模块，共计3600多行代码实现。如图1所示，本发明提供的一种基于系统溯源图搜索匹配攻击模式的在线系统，部署在集群服务器上，所述在线系统包括：
31.输入层，用于输入攻击图以及系统溯源图；
32.其中，所述系统溯源图根据linuxaudid、windowsetw日志以及应用程序日志生成。
33.攻击模式匹配运算层，用于
34.利用攻击图拆分算法对攻击图进行划分，获得攻击子图；
35.根据系统溯源图与攻击图对应拓扑关系，使用候选图匹配算法搜索在所述系统溯源图中查找与攻击子图匹配的候选子图；
36.使用子图同构算法对候选子图进行图压缩，得到完整候选图；
37.利用相似度排序方法对每个完整候选图与系统溯源图的相似度进行排序；
38.根据排序第一的完整候选图，确定是否需要输出威胁告警；
39.输出层，用于输出威胁告警。
40.值得说明的是：攻击图划分模块的主要作用是将攻击图拆分成多个连通子图称为攻击子图，候选图匹配模块的主要作用是在系统溯源图中找到攻击子图的匹配并按照系统溯源图节点的可达性将其合并为一个完整的连通的候选图，相似度排序模块的主要作用是对候选图和攻击图的相似度打分，按照相似程度排序输出结果。最终，如果相似度大于一定程度，就生成告警，后续将进行详细说明。
41.本发明提供的一种基于系统溯源图搜索匹配攻击模式的在线系统及服务器，包括输入层，用于输入攻击图以及系统溯源图；攻击模式匹配运算层，用于利用攻击图拆分算法对攻击图进行划分，获得攻击子图；根据系统溯源图与攻击图对应拓扑关系，使用候选图匹配算法搜索在系统溯源图中查找与攻击子图匹配的候选子图；使用子图同构算法对候选子图进行图压缩，得到完整候选图；利用相似度排序方法对每个完整候选图与系统溯源图的相似度进行排序；根据排序第一的完整候选图，确定是否需要输出威胁告警；输出层，用于输出威胁告警。本发明的攻击模式匹配层具备良好的检测能力，能够有效帮助安全人员检测系统内是否存在与给定攻击模式类似的行为。
42.参考图1，攻击模式匹配运算层包括攻击图划分模块，用于
43.步骤a：在攻击图中选择若干个度数最高的节点作为预选节点；
44.步骤b：根据其他节点与预先节点之间的最短距离，利用攻击图划分基准算法给每
个节点赋予属性；
45.步骤c：按照不同类别标签下不存在相同的节点原则，将攻击图中的节点进行不重叠的划分，获得不同类别标签下的节点集合；
46.步骤d：将同一类别标签下的节点集合中的节点连同，形成攻击子图。
47.对于攻击图划分模块而言，其目的主要是将攻击图的所有节点不重叠地划分为若干个类别，同时保证同属一类的两个节点相互之间一定是可达的。因此，一种比较直接的思路就是随机选择若干个节点作为初始分类，从这些节点同时开始进行广度优先遍历操作，将在遍历时遇到的节点赋予相应类别属性，直到所有节点遍历完成。这一做法可以保证所有节点被不重叠地划分，同时也可以保证同属一类的两个节点相互之间一定是可达的，因此满足要求。另一个比较直观的做法是不随机选择节点，而是选择度数最高的若干个节点，这样可以更好地让节点在各个类别均匀分布。
48.在实际计算时，可以不使用广度优先遍历，而是计算其他节点到预选节点的最短距离，按此赋予相应类别属性。具体来说，本发明使用下述算法如表1中算法4.1所示，作为攻击图划分的基准算法进行比较。
49.表1攻击图划分基准算法的流程代码表
[0050][0051]
然而，上述算法的缺陷在于它需要预先设定好将攻击图划分为多少个子图，不能自适应地得到划分数目，所得到的攻击子图因而也就很难或不能反应出攻击图所包含的攻击步骤的区别。因此，在攻击图划分模块，本发明引入现有的社区发现算法用来对攻击图进行划分。
[0052]
labelpropagation是一种基于标签传播的局部社区发现算法，这一算法的主要思路在开始时给每个节点都赋予一个唯一的标签，并在迭代过程中将其更新为这一节点所有邻居节点中数量最多的一个标签。随着迭代不断进行，密集分布在一起的节点会得到相同的标签。最终具有同样标签的节点会被分为一类。这一算法的优势在于运行速度快，几乎是线性时间的算法。
[0053]
gemsec是一种基于图嵌入技术的社区发现算法。这一算法同时对嵌入向量和节点分类进行学习和训练，从而可以利用节点分类的结果对模型向量嵌入的能力进行提升，也可以利用向量嵌入的结果提升模型节点分类的能力。具体来说，gemsec基于节点序列进行训练，首先通过随机游走对图进行采样得到由节点组成的序列，进一步通过skipgram模型对这些节点组成的序列进行学习，得到节点对应的向量表示。但其特殊之处在于在损失函数加入了聚类损失，进而使模型获得了分类能力，也使得模型的嵌入向量和节点分类能力可以互相提高。
[0054]
leiden算法可以保证其生成的分类结果是连通的，特别是保证算法最终收敛的结果会达到局部最优。算法首先对节点进行随机初始化，然后按照一定条件不断地将节点移动到一个分类，直到所有节点分类完毕得到一个初始的划分。然后根据分类质量函数在此基础上不断进行迭代一直到不能再提高为止。leiden算法在分类速度和精度上都有比较出色的表现。
[0055]
系统基于karateclub对以上算法做了封装和实现。karateclub是一个旨在提供图数据挖掘算法的python开源框架。其中，karateclub中提供了labelpropagation算法和gemsec算法的实现，但并不包含其他算法的实现，系统按照karateclub中的接口标准对于上面提及的社区发现算法和用于比较的基准算法做了统一实现和封装。
[0056]
候选图匹配模块，用于
[0057]
步骤a：对于系统溯源图，通过节点属性合并算法和同类节点合并算法，进行图压缩，得到简化后的系统溯源图；
[0058]
步骤b：对攻击子图以及系统溯源图分别进行节点属性到边属性的转化，生成攻击子图对应的线图以及系统溯源图对应的线图；
[0059]
步骤c：利用vf2算法对每一个攻击子图线图与系统溯源图线图进行搜索，得到对应的候选子图线图；
[0060]
其中，候选子图线图为边属性导出子图；
[0061]
步骤d：对搜索得到的候选子图线图进行恢复，得到对应的候选子图；
[0062]
步骤e：将恢复得到的候选子图和其对应攻击子图进行图同构测试，得到候选子图和攻击子图之间的节点映射关系；
[0063]
步骤f：按照所述系统溯源图的拓扑关系、所述攻击图的拓扑关系以及候选子图和攻击子图之间的节点映射关系，对该攻击图的候选子图进行拼接，得到与该攻击图对应的完整候选图。
[0064]
本发明可以针对每个攻击图，按照攻击子图的类型遍历所有候选子图的可能组合，得到多条路径节点集合；根据系统溯源图、攻击图以及候选子图与攻击图之间的节点可达性连接节点集合中的节点，得到完整的连通候选图作为完整候选图。
[0065]
本发明可以针对每个攻击图，按照攻击子图的类型遍历所有候选子图，得到连接
不同攻击子图的边在系统溯源图中的对应目标节点；将每个路径上的目标节点组成形成一个路径节点集合。将最短路径的路径节点集合找那个的节点与候选子图合并，得到完整的连通候选图作为完整候选图。
[0066]
值得说明的是：候选图匹配模块的一个重要部分是子图同构算法，子图同构算法用于在系统溯源图中找到与攻击子图相匹配的候选子图，是得到候选图的一个前提条件。另一方面，子图同构算法的效率也决定了候选图匹配模块的运行速度，因为在得到候选子图以后，将它们拼接起来这一操作最多是o(n2)的，但是子图同构算法是一个np完全问题，因而其运行效率就十分关键。本发明选择使用vf2子图同构算法。vf2算法运行效率较快，得到了广泛应用，boost(c++)库和networkx(python)库中的子图同构算法使用的就是这一算法，本发明选择基于networkx提供的vf2算法进行候选图匹配模块的实现，因此下面的提到的特性以此版本为准。vf2算法的基本思想是从空图开始进行匹配，因为空图与空图总是满足匹配条件的，然后开始添加节点，例如节点v和v1，v2匹配，那么首先匹配节点v和v1，在此基础上采用基于回溯的机制不断进行迭代匹配，具体的匹配过程与深度优先遍历过程类似。但是为了对匹配过程进行加速，算法会根据图的结构信息来进行剪枝，比如利用节点的出度信息和入度信息去除不符合条件的节点。对于异构图而言，这一过程也可以通过节点的属性匹配进行加速。
[0067]
需要说明的是，vf2算法的输出为系统溯源图与攻击图节点的映射，由此得到的子图属于节点导出子图(node-inducdedsubgraph)，不同于边导出子图(edgeinducedsubgraph)。这里补充两者定义：
[0068]
定义4.1(节点导出子图)：对于图g＝(v,e)和图g＝(v
′
,e
′
)，它们是节点导出子图，如果并且有并且有
[0069]
定义4.2(边导出子图)：对于图g＝(v,e)和图g＝(v
′
,e
′
)，它们是边导出子图，如果并且有
[0070]
步骤b：将所述候选子图进行节点属性至边属性的转换，得到边属性的候选子图；
[0071]
vf2算法考虑的是节点导出子图而非边导出子图，意味着即便g的一个子图g0与g
′
同构，但是由于g0中的节点生成的导出子图中包含了多余的边，那么g0也不被视为是一个正确的结果。换言之，这要求溯源图系统匹配子图节点的度要与攻击图中的节点也相同。这同本发明的目的是相悖的，如果一次攻击中某两个攻击节点之间的交互与攻击图的描述有一点不够符合，多出了一条或若干条边就不将其视为一次攻击，这不符合算法的需要。如图2所示，图b中虽然存在图a的子图同构，但是由于图b中的外围节点与图a相比，多了边连接，节点度数不一致，因而对于这种情况，vf2算法不能得到期望结果，也就是说不能给出一个匹配结果。因此需要进一步将边导出子图同构问题转化为节点导出子图同构问题再来使用vf2算法解决线图(linegraph)，又称表示图，是一种特殊的可以表示图的边连接关系的图，下文中为了方便辨认，使用linegraph指代线图。linegraph的定义如下：
[0072]
定义4.3(linegraph)：对于图g＝(v,e)，它的linegraph记作l(g)，并且：
[0073]
·
l(g)的每个节点对应g的一条边。
[0074]
·
l(g)的两个节点之间有边连接当且仅当它们对应的g的边共享同一个节点。
[0075]
对于linegraph，有如下定理：
[0076]
定理4.1(whitney同构定理)：对于连通图g1和连通图g2，如果它们的linegraphl(g1)和l(g2)同构，那么图g1和图g2同构，除了完全图k3和星形图k1,3的情形。
[0077]
借助linegraph和whitney同构定理，本发明将基于vf2算法这一用于解决节点导出子图同构问题的算法解决边导出子图同构问题。具体的过程如表2中算法4.2所示。
[0078]
表2边导出子图同构算法代码流程表
[0079][0080]
算法4.2的输入为系统溯源图gp和攻击子图gq，用于在溯源图中搜索得到攻击子图的精确匹配，输出为与攻击子图同构的系统溯源图子图。算法首先将系统溯源图和攻击子图都转化为linegraph，并基于linegraph使用vf2算法查找子图同构。然而正如上文中提及的，vf2算法给出的结果为节点导出子图，这导致匹配结果的度必须完全和攻击图节点的度一致。在输入转化为linegraph后，vf2算法给出的结果就是linegraph的节点导出子图，根据linegraph的定义，lg(g)的节点就是g的边，此时vf2算法给出的结果就是v(lgq)和的一个映射，表示为一个字典，也就是算法4.2中的node_mapping。这一字典的键为v(lgq)中的一个节点，也就是e(gq)中的一条边，值为中的一个节点，也就是e(gp)中的一条边。进而通过这一字典恢复得到系统溯源图gp的一个边导出子图h，这样就完成了节点导出子图同构算法到边导出子图同构算法的转换。
[0081]
然而，本发明中涉及的图均为异构图，这意味着节点和边均有对应的属性。当一个图g转化为对应linegraphlg(g)以后，其节点属性转化为边属性，边属性转化为节点属性，这一过程中由于lg(g)的边的生成特征，导致如果简单地将lg(g)的边属性设置为对应的g中的共享节点的属性，那么部分g中的节点是不对应到lg(g)的边的。另一方面，在算法4.2生成边导出子图h以后，依然需要进一步给出h和攻击子图gq的节点映射，而这不能简单的
从node_mapping生成，原因是可以确定两条边共享节点的对应，但是对于两个非共享节点，如何确定其映射是一个比较复杂的问题。因此，为了对上述两个问题进行简化，又考虑到攻击子图规模较小，对小规模的图进行图同构测试一般不会花费太长时间，因此算法4.2会进一步通过图同构算法对h和攻击子图gq进行图同构测试，并给出其节点映射。
[0082]
然而linegraph的引入会带来新的问题，这是因为对于普通的图来说，其边数会远多于节点数，因此对于图g来说，对应的lg(g)会比图g大很多，而边数的增加还要严重得多。由于g中每两条共享节点的边对应一个lg(g)的边，因此lg(g)的边数与g的节点度数有关。如果图g中某个节点的度数为d，那么意味着有d条图g中的边共享了这一节点，进而这d条边两两对应一个lg(g)的边，从而lg(g)中要对应生成(d2)条边。如果图g中的节点集中度较高，存在度数极高的节点，那么lg(g)的边数就会极为庞大。对此，本发明提出两项措施进行处理：节点属性合并和同类节点合并。这两项技术主要应用于系统溯源图
[0083]
节点属性合并指将图g的节点属性相应转化为其linegraphlg(g)的节点属性，这里的问题在于图g的节点与图lg(g)的节点并不对应，图lg(g)的一个节点对应的是图g的一个边，因此如果图g中的边没有属性，此时对图lg(g)而言，寻找特定模式的速度要大为下降。另外，图g中的一个节点可能对应多个属性，如果在搜索时不对节点属性做一一比较，能够通过一次比较就完成节点匹配，同样可以提高匹配速度。因此本发明提出，可以在匹配前对图g进行预处理，将节点属性转化为整数，对于单个节点的所有属性，将其值相乘进而将多个复杂的不同类别的属性转化为单个的整数类型的属性，以此进行匹配过程的加速。在此基础上，需要将图g中的节点属性相应转化为lg(g)的节点属性。对于图lg(g)的一个节点，如果其对应的是图g的边(u,v)，方便起见，本发明将其记作节点[u,v]，其属性可以通过节点u∈v(g)和v∈v(g)的属性相乘生成。这部分算法如表3中4.3所示。
[0084]
表3节点属性合并算法代码流程表
[0085][0086]
其中，lv(v,unified)表示节点v∈v对应的属性unified的值，lv(lg(g))([u,v],unified)表示图g的边(u,v)对应的lg(g)的节点[u,v]的属性unified的值。这种做法会导致利用子图同构算法得到的映射虽然一定包含了真实结果，但也会有一部分结果，虽然合并后的属性是匹配的，但实际上并不匹配，因此需要对结果进行进一步的图匹配来过滤这部分假阳性结果。在算法4.2中，为了处理引入linegraphlg(g)带来的重新确定节点映射的需要，已经包含了图同构测试，因此算法4.3中就不需要再重复图同构测试了。
[0087]
同类节点合并是指对于属性完全相同，而且其邻居节点也完全相同的节点进行合并，这是系统溯源图压缩的常用策略。在系统溯源图中，大量节点实际上代表着完全相同的系统活动。比如说，对于系统内运行的mysql进程会重复读写很多次，进而溯源图中会出现大量重复的系统调用和文件读写相关的节点和边，在其读写文件和访问的进程相同的情况下，这些节点的作用是完全一致的，不会对一般的威胁检测任务或者本发明进行的攻击模式匹配任务带来贡献，因此完全可以去除。具体算法细节如表4中算法4.4所示。
[0088]
表4同类节点合并算法代码流程表
[0089][0090]
算法4.4首先遍历v(g)中的每个节点，对每个节点v得到其属性集合d，如果d尚未被字典all_attrs记录，说明之前没有记录过同类节点，将其加入字典。否则进一步查询字典all_attrs[d]，确认已经记录的同类节点是否存在其邻域与v完全相同的，如果存在，说明这是一个冗余节点，需要去除。但是为了保证整体系统溯源图的连通性，需要计算去除该节点后系统溯源图是否连通，如果去除该节点不影响系统溯源图的连通性，那么之后就去除该节点和与节点连接的边。
[0091]
参考图1，攻击模式匹配运算层还包括：相似度排序模块，用于
[0092]
步骤a：对于完整候选图，利用lehman算法给每个节点赋予不同标签；
[0093]
步骤b：针对每个节点，根据其邻居节点的标签更新自身节点的标签；
[0094]
步骤c：使用blake2b哈希函数对所有节点标签进行聚合，生成完整候选图整体的标签；
[0095]
步骤d：对所有节点的k近邻图生成对应哈希，则对完整候选图的每个节点就重新生成了一个哈希；
[0096]
步骤e：通过jaccard相似度来衡量完整候图与系统溯源图之间的相似度；
[0097]
步骤f：根据相似度对完整候选图进行排序；
[0098]
步骤g：根据排序第一的完整候选图，确定是否需要输出威胁告警。
[0099]
本发明首先通过weisfeiler-lehman算法得到每个节点的标签，通过这一方式得
到的这些节点标签就可以作为图的一种嵌入表示，通过对两个图的节点标签集合的相似度进行计算即可得到图的相似度。weisfeiler-lehman算法的主要思路类似于标签传播，示意图如3。weisfeiler-lehman算法首先给每个节点赋予不同标签，然后根据其邻居节点的标签更新自身节点。具体来说，算法会对每一个节点聚合其相邻节点的特征值作为自身的标签，重复多次直到收敛为止，如图所示，最终可以得到图中的每个节点都会被赋予一个新的标签，这一标签将作为后续步骤的基础。在每个节点都生成对应标签后，算法使用blake2b哈希函数对所有节点标签进行聚合，生成图整体的标签。
[0100]
weisfeiler-lehman图哈希算法保证了对同构的图生成相同的哈希，保证不同构的图具有不同哈希。然而，仅仅只得到图的哈希不足以对两个图的相似度进行评价，因此本发明在此基础上，对于所有节点的k近邻图生成对应哈希，进而对图的每个节点就重新生成了一个哈希，利用这一哈希反映出图整体的内部子结构分布状况，可以看出有多少个节点的k近邻图是同构的，进而可以对图的局部信息进行刻画。在完成上述步骤后，图就可以被表示为一系列标签的集合，进而可以通过jaccard相似度来衡量两个图的相似度。jaccard相似系数是衡量两个集合的相似度一种指标。其计算公式为：
[0101][0102]
其中，a是一个图所有节点标签的集合，b是一个图所有节点标签的集合。jaccard分数越大，说明两个图越相似，本发明为了与其他指标保持一致，在计算时使用以下公式，注意在此种计算方式下，jaccard分数越小，两个图越相似。
[0103][0104]
参考图1，本发明的攻击模式匹配运算层还包括：相似度排序模块，用于
[0105]
步骤a：基于图谱的相似度或基于最短路长度分布的相似度，计算完整候图与系统溯源图之间的相似度；
[0106]
步骤b：根据相似度对完整候选图进行排序；
[0107]
步骤c：根据排序第一的完整候选图，确定是否需要输出威胁告警。
[0108]
上述哈希只考虑了图的局部信息，而没有考虑图整体的信息，如图的拓扑结构和节点的连接关系，为了利用这些信息，本发明进一步根据图谱和图的最短路分布对图的相似度进行刻画。
[0109]
定义4.4(邻接矩阵)：对于图g＝(v,e)，其节点集合v的大小|v|＝n，那么图g的邻接矩阵adj(g)是一个n
×
n的矩阵，其中的元素aij∈adj(g)表示对于节点vi和节点vj有边连接，即(vi,vj)∈e(g)。
[0110]
定义4.5(图谱(spectrum))：对于图g＝(v,e)的邻接矩阵adj(g)是一个n
×
n的实对称矩阵，因此该矩阵有n个实特征值，不失一般性的，将其记作λ1≥λ2≥λ3
…
≥λn，这些特征值的集合被称为图的谱(spectrum)图的邻接矩阵记录了图节点的连接关系，反映了图的拓扑结构，而图谱则是对邻接矩阵的一种刻画，如果两个图的相似，其邻接矩阵也会比较相似，进而图谱也会比较接近。不过不同大小的图其邻接矩阵的特征值数目与节点数量相关，因此为了能适应不同规模的图，本发明选择取前10大的特征值作为对邻接矩阵的刻画，并按照l1距离计算相似度，具体算法如表5中算法4.5所示。
[0111]
表5基于图谱的相似度计算代码流程表
[0112][0113]
其中l1距离的计算公式为：
[0114][0115]
另外，考虑到各个攻击步骤不可能零散地分布在溯源图的不同地方，相互之间必定存在紧密的联系，因此攻击图的各个节点之间的路径不会太长，本发明提出了一种基于路径长度衡量图相似度的方式。为了避免暴露，攻击者在系统内的活动要保持隐秘，因此攻击路径不会太长，同时也为了避免图中出现环，因此基于最短路长度进行衡量是一种自然的想法。本发明对于图g中所有节点之间的最短路长度进行统计，进而可以在此基础上比较两个图的所有节点间最短路的长度分布。kullback
–
leiblers散度是一种常用于衡量分布相似程度的指标，它是一个概率指标，衡量指定概率分布q，与参考概率分布p的差异程度。当两个概率分布一致，那么其值为0，具体的计算公式为：
[0116][0117]
从公式中可以看到，kullback
–
leiblers散度是不对称的，也就是说d
kl
(p,q)≠d
kl
(q,p)，但本发明中相似度衡量用于衡量攻击图和候选图之间的相似度，因而是在给定攻击图最短路长度分布的情况计算候选图最短路长度分布的差异度，对于这种对称性没有要求。具体的算法细节如表6中4.6算法所示。
[0118]
表6基于最短路长度分布的相似度计算代码流程表
[0119][0120]
其中，histogram函数的作用是将所有最短路长度按照(v_min,v_max)的范围划分为十份，统计每一个区间内对应长度出现的频率，作为相应最短路长度的分布概率。这是因为kullback
–
leiblers散度要求使用概率分布作为输入，不能直接接受最短路长度作为输入。所以需要通过histogram函数计算两个节点之间最短路的长度处于某个区间的概率，最终得到图所有节点之间最短路长度的分布概率，使用kullback
–
leiblers散度衡量攻击图和候选图在这一概率分布上的差异，通过最短路长度的分布差异衡量图的相似程度。这种思路主要建立在攻击者为了避免暴露，攻击图会比较集中的假设下，进而有理由认为攻击图所有节点之间的最短路长度会比较一致的偏短，而候选图的最短路分布应该尽可能与之吻合。
[0121]
本发明提供的一种服务器，部署如基于系统溯源图搜索匹配攻击模式的在线系统。
[0122]
接下来通过实验对本发明提出的方法进行验证，主要考虑对以下方面进行考虑：
[0123]
·
攻击模式匹配流程的有效性。本发明提出的攻击模式匹配流程是否能有效地在大规模的系统溯源图中找到给定攻击模式的匹配是实验部分的核心，其中，结果的正确性和匹配速度均需要纳入考虑。
[0124]
·
攻击模式匹配算法受哪些因素的影响。
[0125]
特别的，考虑到随着图规模的上升，图匹配问题的复杂程度也随之上升，因此有必要确定攻击图和溯源图规模对检测效果的影响。
[0126]
本发明对攻击模式匹配算法的效果进行评估，首先对不同规模下算法的表现进行
评分，分别对不同规模的攻击图和不同规模系统溯源图下算法的表现进行实验。此处的规模指图节点集合的大小。之后对其他影响算法表现的因素进行讨论。如无特殊说明，以下实验均在合成数据集的基础上进行。
[0127]
本发明讨论随着攻击图规模的上升，算法的性能表现发生的变化。主要分为对指标，即精度和召回率，以及对运行时间的影响。实验时，取系统溯源图规模为10000，数据集中攻击副本数设置为4，攻击图划分算法使用基线方法，相似度排序算法使用基于图哈希的相似度算法。由于基线方法需要给定划分的分类数目，这里设置为k表示攻击图规模。这样设置的原因是确保不会将攻击图划分太细，将每个攻击子图的规模限制在25左右。
[0128]
表7中反映了在不同攻击图规模下，攻击模式匹配算法给出的结果。表中各列，候选图规模指算法搜索得到的所有可能和攻击图匹配的候选图个数，注意到对于攻击图规模较小的情况，算法给出的候选图数目不足10个或100个，此时计算top100或top10指标时，分母按照候选图规模计算。
[0129]
表7不同攻击图规模对指标影响
[0130][0131]
从表7中可以看出，随着攻击图规模的上升，算法给出的候选图数目也逐渐上升，整体精度和召回率都比较稳定，保持在一个很高的水准。从精度来看，虽然在攻击图规模上升的情况下，一些情况下精度有一定波动，部分生成的候选图可能与攻击图并不相似，但是大部分排序算法依然能保证这些结果不排在前面，使得top100和top10精度保持稳定。这说明算法对于不同规模的攻击图都适用。注意到在攻击图规模为50的情况下，算法的性能有较大程度下降，分析发现这是由于用了基线算法作为攻击图划分算法，对于节点规模不足25的攻击图不会拆分，因此其查询结果不受候选子图连接过程的影响，而节点规模大于50时，虽然在子图连接过程中混入了与攻击无关的节点，但是由于攻击图整体规模大，因此满足攻击节点大于80％的要求，这就使得在攻击图规模为50的情况出现了异常下降。
[0132]
表8不同攻击图规模对运行时间影响
[0133]
[0134][0135]
表8中反映了在不同攻击图规模下，攻击模式匹配算法的运行时间。
[0136]
从表8中可以看到，随着攻击图节点数的增多，算法的运行时间出现明显上升，与候选图的数目关系不大。注意到运行时间的增长与攻击图规模近似呈线性增长，说明攻击图规模不会明显影响算法性能，从而说明算法可以很好的支持复杂查询。
[0137]
本发明讨论随着系统溯源图规模的上升，算法的性能表现发生的变化。主要分为对指标，即精度和召回率，以及对运行时间的影响。实验时，取攻击图规模为100，数据集中攻击副本数设置为4。攻击图划分算法使用基线方法，相似度排序算法使用基于图哈希的相似度算法。基线方法的分类数目，这里设置为k表示攻击图规模。
[0138]
表9不同系统溯源图规模对指标影响
[0139][0140]
表9中反映了在不同系统溯源图规模下，攻击模式匹配算法给出的结果。
[0141]
从表9中可以看到，随着系统溯源图规模的上升，算法的精度会不断下降，在溯源图规模达到50000时后明显下降，整体检测准确率只有不到60％，说明随着系统溯源图规模上升，其中可能包含的干扰节点也逐渐有明显上升。不过虽然整体精度下降，但是top100精度和top10精度依然都保持在一个比较高的水平，说明相似度排序机制可以有效降低结果中的假阳性率，减轻安全人员的负担。总的来说，虽然在溯源图规模较大时算法性能有一定下降，但是在合成数据集上的实验结果显示算法最终的输出结果依然可以有效帮助安全人员进行分析，找到和定位系统溯源图中可能包含的攻击。总的来说，算法面对较大范围内不同规模的溯源图输入，都可以有效工作。
[0142]
本实验使用的各项配置与上一小节相同。表10中反映了在不同系统溯源图规模下，攻击模式匹配算法的运行时间。从表10中可以看到，系统溯源图规模的上升与算法运行时间大致呈线性关系，说明算法具备较好的可扩展性，可以适用于大规模的系统溯源图。
[0143]
表10不同系统溯源图规模对运行时间影响
[0144][0145]
本发明对攻击图划分技术的有效性进行评估。首先从分类本身的质量对不同攻击图划分算法进行测试，接着从攻击模式匹配的效果出发讨论不同算法的影响。
[0146]
对于攻击图划分技术，如果需要评价其分类质量，不能简单地使用精度和召回率这类指标进行评价，因为此时给某一个节点赋予的标签类别本身并不重要，重要的是该节点和哪些节点被分为同一类节点，也就是说，单个节点的标签并不重要，重要的是对整体的划分。本发明使用归一化互信息(normalizedmutualinformation，nmi)和调整兰德指数(adjustedrandindex，ari)对攻击图划分算法的分类质量进行评价。接下来对这两个指标的计算方式进行简要介绍。
[0147]
nmi的计算公式为：
[0148][0149]
i是互信息，计算公式为：
[0150][0151]
其中，p(wk)是某个节点被分类为wk的概率，p(cj)是某个节点属于cj分类的概率，p(wk)p(cj)是某个节点属于cj分类但被分类为wk的联合概率。
[0152]
式中h的定义如下：
[0153][0154]
nmi是一种有效的分类评价指标，通过熵h的引入，它可以避免在单纯使用互信息评价时分类越少评分越高的问题。nmi的取值在0和1之间，当分类结果是完全随机地给出时，分数为0，当分类结果与真实标签完美吻合时，分数为1。
[0155]
不同于nmi这样从信息论的角度评估，ari从决策角度对分类质量进行评估。ari是对ri(randindex，兰德指数)的调整，反映了一个随机分类模型给出的分类结果与当前分类结果的质量差异。ri的计算公式如下：
[0156]
[0157]
其中，a、b、c、d定义如下：
[0158]
a＝|s
*
|，s
*
＝{(oi，oj)|oi，oj∈xk，oi，oj∈y
l
}
[0159][0160][0161][0162]
而ari的计算公式如下：
[0163][0164]
其中，n
ij
指真实标签为i但被分类为j的节点数量，ai表示真实标签为i的节点数量，bj表示被分类为j的节点数量。
[0165]
对于算法的分类效果，分别在lfr数据集和合成数据集生成的攻击图上进行测试。lfr数据集是一个专门为社区发现任务设计的合成数据集，它是社区发现领域的一个常用测试数据集。
[0166]
表11和表12分别反映了lfr数据集和合成数据集下不同攻击图划分算法的分类效果及运行时间。其中，两个数据集均生成节点数为400的图进行测试。对于基线方法，按照划分数k＝10进行测试。
[0167]
表10lfr数据集下不同攻击图划分算法的分类效果及运行时间比较
[0168][0169]
表11合成数据集下不同攻击图划分算法的分类效果及运行时间比较
[0170][0171]
可以看到，各个方法在两个数据集下的表现比较一致。综合考虑，leiden算法的效果最好，不仅在nmi和ari两项指标上表现出色，同时在时间上也是最快的。同时可以看到，除了leiden算法以外，其他三个算法的表现并没有质的区别，依然处于可以互相比较的区间内。
[0172]
本发明讨论不同攻击图划分算法对匹配结果的影响。实验时，取攻击图规模为
100，系统溯源图规模为100000，数据集中攻击副本数设置为4。对于基线方法，划分数目为k表示攻击图规模。从表5.8中来看，labelpropagation和gemsec由于将攻击图划分过于细碎，因此导致在候选图匹配阶段生成了过多候选图，进而不能在可接受的时间内得到结果，效果较差。而基线方法和leiden方法生成的结果就好得多，分别只有256和1024个候选图。可见攻击图划分算法对攻击模式匹配的效果具有决定性影响，由于社区发现算法不能很好的控制分类数量，因此如果其分类数量过多，那么就会生成过多候选图进而导致算法运行速度下降到一个不可能接受的程度。此时需要事先给定分类数量的基线算法反而要更优越。
[0173]
总的来说，leiden算法的top100效果要好于基线方法，但是这两个算法得到的top10精度和召回率都为1，因此对于分析人员来说，这两个算法区别不大，由于上面提及的原因，这里的基线方法事实上在很多情况下会强于leiden算法。最后注意到对于基线方法，其top100精度要高于整体精度，top10精度高于top100精度；对于leiden算法，其top100精度要高于整体精度，这些数据说明相似度排序算法可以有效的提高模型精度。
[0174]
图4是真实数据集系统溯源图同类节点合并前后度数最高的100个节点其节点具体的概率分布。图中横轴代表节点的度数，纵轴代表相应度数节点所占的百分比。粗线条的pdf(probabilitydensityfunction)曲线指概率密度函数，曲线上面的点代表度数等于横坐标的节点所占百分比，细线条的cdf(cumulativedistributionfunction)曲线指累计分布函数，曲线上面的点代表度数小于或等于横坐标的节点所占百分比。
[0175]
从图4中可以看到，在同类节点合并前，有很多节点的度数都超过了10000，这意味在转化为linegraph以后，由这些节点生成的边数会达到千万至亿数量级，度数最高的节点其度数超过了90000，对边数的贡献会达到3.6亿左右，这会导致生成的linegraph过于庞大，因此不可能使用同类节点合并前的系统溯源图直接进行匹配。在同类节点合并后，可以看到度数top100节点的度数整体下降了一个数量级，最高度数不超过20000，此时linegraph会由于节点度数生成过多的边，为了在有限内存的情况下进行实验，本发明的后续实验中不会将同类节点合并后的溯源图转化为linegraph再匹配，而是直接使用溯源图进行匹配。不过虽然如此，图4依然说明同类节点合并技术对系统溯源图规模的缩减是十分有效的。
[0176]
本领域普通技术人员可以理解：附图只是一个实施例的示意图，附图中的模块或流程并不一定是实施本发明所必须的。
[0177]
本领域普通技术人员可以理解：实施例中的系统中的模块可以按照实施例描述分布于实施例的系统中，也可以进行相应变化位于不同于本实施例的一个或多个系统中。上述实施例的模块可以合并为一个模块，也可以进一步拆分成多个子模块。
[0178]
最后应说明的是：以上实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明实施例技术方案的精神和范围。
技术特征：1.一种基于系统溯源图搜索匹配攻击模式的在线系统，部署在集群服务器上，其特征在于，所述在线系统基于python开发，所述在线系统包括：输入层，用于输入攻击图以及系统溯源图；攻击模式匹配运算层，用于利用攻击图拆分算法对攻击图进行划分，获得攻击子图；根据系统溯源图与攻击图对应拓扑关系，使用候选图匹配算法搜索在所述系统溯源图中查找与攻击子图匹配的候选子图，并对候选子图进行拼接得到完整候选图；利用相似度排序方法对每个完整候选图与系统溯源图的相似度进行排序；根据排序第一的完整候选图，确定是否需要输出威胁告警；输出层，用于输出威胁告警。2.根据权利要求1所述的一种基于系统溯源图搜索匹配攻击模式的在线系统，其特征在于，所述系统溯源图根据linuxaudid、windowsetw日志以及应用程序日志生成。3.根据权利要求1所述的一种基于系统溯源图搜索匹配攻击模式的在线系统，其特征在于，攻击模式匹配运算层包括攻击图划分模块，用于在攻击图中选择若干个度数最高的节点作为预选节点；根据其他节点与预先节点之间的最短距离，利用攻击图划分基准算法给每个节点赋予属性；按照不同类别标签下不存在相同的节点原则，将攻击图中的节点进行不重叠的划分，获得不同类别标签下的节点集合；将同一类别标签下的节点集合中的节点连同，形成攻击子图。4.根据权利要求1所述的一种基于系统溯源图搜索匹配攻击模式的在线系统，其特征在于，攻击模式匹配运算层还包括：候选图匹配模块，用于对于系统溯源图，通过节点属性合并算法和同类节点合并算法，进行图压缩，得到简化后的系统溯源图；对攻击子图以及系统溯源图分别进行节点属性到边属性的转化，生成攻击子图对应的线图以及系统溯源图对应的线图；利用vf2算法对每一个攻击子图线图与系统溯源图线图进行搜索，得到对应的候选子图线图；其中，候选子图线图为边属性导出子图；对搜索得到的候选子图线图进行恢复，得到对应的候选子图；将恢复得到的候选子图和其对应攻击子图进行图同构测试，得到候选子图和攻击子图之间的节点映射关系；按照所述系统溯源图的拓扑关系、所述攻击图的拓扑关系以及候选子图和攻击子图之间的节点映射关系，对该攻击图的候选子图进行拼接，得到与该攻击图对应的完整候选图。5.根据权利要求4所述的一种基于系统溯源图搜索匹配攻击模式的在线系统，其特征在于，所述按照所述系统溯源图的拓扑关系、所述攻击图的拓扑关系以及候选子图和攻击子图之间的节点映射关系，对该攻击图的候选子图进行拼接，得到与该攻击图对应的完整候选图包括：针对每个攻击图，按照攻击子图的类型遍历所有候选子图的可能组合，得到多条路径
节点集合；根据系统溯源图、攻击图以及候选子图与攻击图之间的节点可达性连接节点集合中的节点，得到完整的连通候选图作为完整候选图。6.根据权利要求5所述的一种基于系统溯源图搜索匹配攻击模式的在线系统，其特征在于，所述针对每个攻击图，按照攻击子图的类型遍历所有候选子图的可能组合，得到组合候选子图包括：针对每个攻击图，按照攻击子图的类型遍历所有候选子图，得到连接不同攻击子图的边在系统溯源图中的对应目标节点；将每个路径上的目标节点组成形成一个路径节点集合。7.根据权利要求6所述的一种基于系统溯源图搜索匹配攻击模式的在线系统，其特征在于，所述根据系统溯源图的连接关系连接节点集合，得到完整的连通候选图作为完整候选图包括：将最短路径的路径节点集合找那个的节点与候选子图合并，得到完整的连通候选图作为完整候选图。8.根据权利要求1所述的一种基于系统溯源图搜索匹配攻击模式的在线系统，其特征在于，攻击模式匹配运算层还包括：相似度排序模块，用于对于完整候选图，利用lehman算法给每个节点赋予不同标签；针对每个节点，根据其邻居节点的标签更新自身节点的标签；使用blake2b哈希函数对所有节点标签进行聚合，生成完整候选图整体的标签；对所有节点的k近邻图生成对应哈希，则对完整候选图的每个节点就重新生成了一个哈希；通过jaccard相似度来衡量完整候图与系统溯源图之间的相似度；根据相似度对完整候选图进行排序；根据排序第一的完整候选图，确定是否需要输出威胁告警。9.根据权利要求1所述的一种基于系统溯源图搜索匹配攻击模式的在线系统，其特征在于，攻击模式匹配运算层还包括：相似度排序模块，用于基于图谱的相似度或基于最短路长度分布的相似度，计算完整候图与系统溯源图之间的相似度；根据相似度对完整候选图进行排序；根据排序第一的完整候选图，确定是否需要输出威胁告警。10.一种服务器，其特征在于，部署如权利要求1至权利要求9任一项所述的基于系统溯源图搜索匹配攻击模式的在线系统。
技术总结本发明提供的一种基于系统溯源图搜索匹配攻击模式的在线系统及服务器，包括输入层，用于输入攻击图以及系统溯源图；攻击模式匹配运算层，用于利用攻击图拆分算法对攻击图进行划分，获得攻击子图；根据系统溯源图与攻击图对应拓扑关系，使用候选图匹配算法搜索在系统溯源图中查找与攻击子图匹配的候选子图；对候选子图进行拼接得到完整候选图；利用相似度排序方法对每个完整候选图与系统溯源图的相似度进行排序；根据排序第一的完整候选图，确定是否需要输出威胁告警；输出层，用于输出威胁告警。本发明的攻击模式匹配层具备良好的检测能力，能够有效帮助安全人员检测系统内是否存在与给定攻击模式类似的行为。在与给定攻击模式类似的行为。在与给定攻击模式类似的行为。
技术研发人员：赵曦滨 王瑞华 彭贻豪 万海
受保护的技术使用者：清华大学
技术研发日：2022.07.12
技术公布日：2022/11/1
