面向APT攻击调查的溯源图冗余结构压缩

Provenance Graph Redundant Structure Compression for APT Attack Investigation

摘要: 面向系统审计日志的溯源图分析已经是APT攻击调查的主要手段。溯源图节点代表系统实体(包括进程、文件和网络)，边代表系统实体之间的依赖关系。攻击调查是在溯源图上追踪攻击源头并构建完整的攻击路径。依赖爆炸导致溯源图规模庞大，将为攻击调查带来巨大的存储开销和时间开销。为解决该问题，本文提出进程重复模式压缩和文件重复模式压缩去减小溯源图规模。其中，进程重复模式代表系统在不同时间调用相同进程执行相同的文件读写任务，而文件重复模式代表多个文件被相同进程处理。这些模式均表示重复的行为，不会带来更多有价值的信息，因此压缩它们不会影响攻击调查。本文在6个真实攻击数据集(约1948万个系统事件)进行实验验证，结果指出溯源图节点和边的压缩率平均分别为56.5%和58.0%。此外，在压缩前和压缩后的溯源图上分别执行攻击调查，结果证明本文的压缩方法不会影响攻击调查结果。

Abstract: A provenance graph analysis of system audit logs has become a primary method for investigating APT attacks. The nodes in the provenance graph represent system entities (including processes, files, and network activities), while the edges denote dependency relationships between these entities. Attack investigation involves tracing the attack origin and reconstructing the complete attack path on the provenance graph. However, dependency explosion leads to excessively large provenance graphs, imposing significant storage and computational overhead on attack investigations. To address this issue, this paper proposes process repetition pattern compression and file repetition pattern compression to reduce the scale of provenance graphs. Specifically, process repetition patterns refer to cases where the system repeatedly invokes the same process to perform identical file read/write operations at different times. File repetition patterns describe scenarios where multiple files are processed by the same process. Since these patterns represent redundant behaviors and do not provide additional valuable information, compressing them does not affect attack investigations. Experiments were conducted on six real-world attack datasets (comprising approximately 19.48 million system events). The results demonstrate an average compression rate of 56.5% for nodes and 58.0% for edges in the provenance graph. Furthermore, attack investigations (using Nodoze and DepComm) were performed on both the original and compressed provenance graphs, confirming that the proposed compression method does not compromise investigation accuracy.

1. 引言

高级持续威胁(APT)是一种多步渐进式攻击，具有攻击手段多样、隐蔽性强、持久性高等特点，可以长期潜伏在目标系统中，对系统造成敏感数据泄漏和可用性破坏等危害，已经成为企业和政府机构中主机系统的主要威胁之一。截至目前，APT攻击已经造成6万亿美元的经济损失[1]。因此，有效防御APT攻击已经成为全球性重要课题。

攻击调查取证是APT防御的重要环节之一。某一攻击事件被检测(POI事件)，针对该事件的溯源取证被启动，找出攻击源头，构建完整的攻击路径，同时分析对系统的后续影响。系统调用日志记录了系统实体(包括进程，文件和IP等)之间的交互行为(如读取、写入和进程创建等)。相比于应用层日志，系统调用日志记录更为全面，而且很难被篡改，是最常用的分析数据[2]。目前主要的取证方法是采用因果分析技术[2] [3]将日志数据转换为系统依赖关系图，之后以POI事件为起点，利用回溯算法[2]构建与该事件存在因果依赖关系的溯源图。最后采用信息流追踪[4]-[8]、异常检测[9]和机器学习[10]-[14]等技术在溯源图上进行分析，移除不相关事件呈现完整的攻击路径。

长时进程(如bash，firefox等)的运行通常会产生大量系统事件，导致依赖爆炸，使得溯源图规模庞大(平均50万事件/24小时) [15] [16]。存储这些溯源图必然导致巨大的开销。最重要的是，在如此庞大的溯源图中分析攻击路径将会带来巨大的时间开销。因此，在不影响攻击调查的情况下减小溯源图规模十分必要。目前，已有的溯源图压缩工作是针对不影响依赖关系结构的节点或重复的平行边进行合并或移除[17]-[21]，虽然达到较高的压缩率，但并没有考虑冗余的子结构信息。这些冗余子结构代表相同的系统行为(如计划任务和配置文件更新)。由于重复的行为不能带来更多有价值的信息，因此，本文提出一套针对冗余子结构的压缩方法。

本文将冗余子结构分为两种重复模式：进程重复模式和文件重复模式。进程重复模式代表计算机系统在不同时间调用相同进程执行相同的文件读写任务(例如，linux系统在每次执行定时任务时守护进程cron会调用子进程cron读写/proc/self/loginuid文件)。针对进程重复模式，本文基于溯源图构建进程世系树，之后将进程执行的网络和文件信息关联到该进程节点，最后采用满子树搜索算法[22]搜索重复的子树结构，将重复结构进行合并。文件重复模式代表多个文件被相同进程处理(如firefox进程对多个配置文件进行更新)。针对文件重复模式，本文在压缩进程重复模式后搜索由相同进程节点连接的文件节点，之后将这些文件节点进行合并。

文本在6个真实场景的攻击数据集进行评估。评估数据共有1948万个系统事件，生成的溯源图平均有5300个节点和1,909,019条边。本文压缩方法的节点压缩率平均56.5%，边压缩率平均58.0%，压缩执行时间平均0.146秒，表现出较高的压缩效率。为了评估压缩后的溯源图对攻击调查的影响，本文采用Nodoze [9]和DepComm [11]攻击调查方法在原始溯源图和压缩后溯源图分别进行分析，检测出的攻击路径均达到100%的相似性，而且在压缩后溯源图上的调查时间分别平均降低了73.9%和64.1%。因此，本文的压缩方法不仅没有影响攻击调查结果，而且降低了调查时间。

2. 相关工作

2.1. APT攻击调查

为找出APT攻击源头和构建完整的攻击路径，针对系统审计日志的攻击溯源图被King等[2]提出。依赖爆炸问题导致构建的溯源图规模庞大，含有大量不相关的系统事件。基于节点分割技术的细粒度溯源分析方法被提出[15] [16] [23]-[27]，能够缩小溯源图规模。由于这些方法需要对系统内核和程序源代码进行改写，具有较差的适用性。为此，一些工作采用信息流追踪技术[4]-[8]、异常检测技术[9]和机器学习算法[10]-[14]在溯源图中直接搜索相关的攻击事件和滤除不相关事件。本文提出的溯源图压缩算法，可以为这些攻击调查方法提供更简洁的溯源图，提高分析效率。

2.2. 溯源图压缩

为减少溯源图分析带来的时间和存储开销，一些工作提出了有效的压缩方法。Lee等[17]识别和移除只被一个进程访问的临时文件，如此的文件不能对其它进程产生影响，被认为是冗余的。Xu等[18]通过合并系统实体之间重复的依赖关系，以达到节省系统依赖图的存储开销。Hossain等[19]利用全局图信息对溯源图节点间重复的边进行合并。Tang等[20]对不影响依赖关系分析的系统链接库，资源和配置等只读文件节点进行移除。Fei等[21]在以上工作的基础上，同时考虑对溯源图节点和边进行压缩，此外考虑与write和execute事件相关的系统实体节点的压缩。尽管这些方法达到了很高的压缩效果，但是并没有考虑冗余子结构的压缩。本文基于上述压缩结果，对冗余子结构进行压缩，可以进一步减少溯源图规模。

3. 背景与动机

3.1. 系统审计日志和溯源图

由Linux Audit [28]，Sysdig [29]和Windows ETW [30]等监控系统生成的系统审计日志记录了系统实体(包括进程、文件和网络)之间的交互行为，即系统事件。根据文献[2] [3]的定义，系统事件表示成3元组：<主体，操作，客体>，代表主体对客体执行某一操作(如进程cp写入文件list.txt)，其中主体只包括进程。而根据客体类型不同系统事件可以进一步分为进程事件(客体 = 进程)、文件事件(客体 = 文件)和网络事件(客体 = 网络)。

基于系统审计日志的溯源分析已经成为APT攻击调查的主要方法。首先采用因果分析技术[2] [3]推断系统事件之间的因果关系，构建系统依赖图$G(E,V)$ ，其中节点$V$ 代表系统实体(即进程、文件和网络)，有向边代表系统事件$e(u,v)$ ，其中$u\in V$ ，$v\in V$ ，$e\in E$ ，边的方向代表数据流方向(即$u\to v$ )。在没有特殊说明的情况下，本文的溯源图中的进程节点用矩形表示，文件节点用椭圆表示，网络节点用平行四边形表示。此外，一个事件记录了开始时间$e.st$ 和结束时间$e.et$ 。给定两个事件$e_1(u_1,v_1)$ 和$e_2(u_2,v_2)$ ，如果$v_1=u_2$ 并且$e_1.st\le e_2.et$ 则$e_1$ 和$e_2$ 存在因果依赖关系。给定一个告警事件(即POI事件)，以该事件为起点，沿着边的反方向迭代遍历与POI事件存在因果依赖关系的早期事件，将这些事件构建溯源图。溯源图完整描绘了生成POI事件的路径。

3.2. 动机例子

(a) (b)

Figure 1. Example of process repetitive pattern compression. (a) Uncompressed, (b) Compressed

图1. 进程重复模式压缩例子。(a) 压缩前，(b) 压缩后

(a) (b)

Figure 2. Example of file repetitive pattern compression. (a) Uncompressed, (b) Compressed

图2. 文件重复模式压缩例子。(a) 压缩前，(b) 压缩后

进程重复模式压缩例子：本文以攻击者频繁改写目标文件为例阐述进程重复模式压缩的动机。具体的说，攻击者利用Linux计划服务定期执行恶意脚本xxx.sh对目标文件../userlist.xlsx进行多次恶意篡改。该恶意行为被完整记录到系统审计日志中。本文将改写../userlist.xlsx事件作为POI事件，通过溯源分析构建溯源图。图2展示了溯源图的一部分。从图中可以看到计划服务进程cron多次调用进程sh，进程sh又多次调用进程sed对同一目标文件../usrlist.xlsx执行写操作。这些结构(虚线框所示)均表现出重复的进程行为，不会带来更多有价值的信息。本文将这些重复进程模式进行压缩，得到图2(b)，其中蓝色部分为压缩后的节点和边。节点从原来的6个减少到2个，边从原来的12条减少到4条，极大减小了图的规模。此外为了防止事件信息的丢失，本文将原事件的信息(包括进程号，开始时间和结束时间)整合到压缩后的节点和边中。例如，压缩后的进程节点sh的进程号由原进程号5739和8901组成。

文件重复模式压缩例子：图2(a)为溯源图中文件重复模式例子。firefox应用程序的多个临时文件(虚线框所示)同时被不同时间的firefox进程改写。这些文件的读写被看作是平行行为，压缩它们不会影响溯源图结构。压缩后的溯源图如图2(b)所示，其中蓝色部分为压缩后的节点和边，节点由原来的3个变为1个，边由原来的9条变为3条，极大减小了图的规模。此外，本文将原文件事件信息(包括文件目录、文件名、开始时间和结束时间)保留并整合到压缩后的节点和边中。

4. 本文方法

4.1. 溯源图生成与预处理

Table 1. System entity and event attribute information

表1. 系统实体和事件属性信息

	属性
进程	PID，进程名
文件	目录，文件名
网络	IP，Port
事件	开始时间，结束时间，操作类型

溯源图生成：本文采用Sysdig [29]系统监控工具在主流操作系统(如Windows和Linux)上采集系统审计日志，包括进程事件、文件事件和网络事件。其中每个采集的实体和事件记录了重要的属性信息，如表1所示。利用因果分析技术对采集的日志进行依赖分析，构建依赖关系图，其中每一个节点被赋予唯一的ID号。之后，基于POI事件，通过backtrack算法[2]反向迭代追踪与POI事件存在因果依赖关系的早期事件，将这些事件构成该POI事件的溯源图。

预处理：本文的预处理涵盖了已有的溯源图压缩工作，包括平行边合并、只读文件节点移除和临时文件节点移除。Xu等[18]指出进程节点和文件/网络节点之间存在多条平行边，这些平行边代表重复的读/写操作，并没有提供更多有价值的信息。因此，本文直接将具有相同操作类型的平行边合并为一条。Tang等[20]指出只读文件通常为用于系统初始化的配置文件和库文件。由于这些只读文件没有被写入，所以不含有攻击注入的信息。本文将溯源图中不含入射边的文件节点从溯源图中移除。Lee等[17]指出一个文件如果只被一个进程读取和写入，则该文件被看作是不可达实体，将它移除不会影响溯源分析。本文将只有一个邻居进程节点的文件节点从溯源图中移除。

4.2. 进程重复模式压缩

进程重复模式代表一个进程多次创建相同子进程，由这些子进程对相同文件执行相同操作。本文是在预处理后的溯源图上执行如此模式的识别，之后合并其中相同的节点和边。该过程包括两个阶段：重复模式识别和重复模式压缩。

重复模式识别：这个过程包括如下步骤：

步骤1：建立进程世系树。在预处理后的溯源图上，本文通过遍历进程节点构建进程世系树。具体来说，将没有父进程的进程节点作为根，以根为起点沿着进程事件之间的依赖关系向前遍历溯源图，之后将得到的进程节点添加到树中。进程世系树呈现了进程之间的创建关系。

步骤2：划分层级。本文对构建的进程世系树从根节点开始划分层级。具体地，所有根节点为层级1，根节点的所有子节点为层级2，该子节点的所有子节点为层级3，依次类推，直到树的最底层为层级N。如图1所示，进程cron作为根节点为层级1，其两个子进程sh为层级2，sh的子进程sed为层级3，sed没有子进程，因此最大层级数为3。

步骤3：关联访问的文件和网络。为捕获进程世系树中进程与文件和网络的交互行为，本文将进程在溯源图中直接连接的文件节点、网络节点和边属性信息关联到进程世系树节点中。具体为，将进程名、父进程名和PID、访问的文件名、访问的网络IP、对文件和网络的操作类型作为进程世系树节点的属性信息。如图1(a)所示，进程节点sh (5739)关联的属性包括：sh、cron (112)、xxx.sh、read。

步骤4：提取子树。进程重复模式中的每一次进程调用行为在进程世系树中是一颗满子树[22]。满子树包括一个节点和它的所有后代。具体为，以层级n (n ≥ 2)的进程作为子树的根节点，采用自上向下层次遍历算法遍历所有后代，得到一颗满子树。

步骤5：挖掘重复模式。进程重复模式是一组完全相同的满子树，包括相同的结构和节点属性。首先，对提取的满子树进行前续遍历。之后，根据节点访问次序和关联的节点属性，将子树编码为字符串，并标识相同的字符串，即重复的子树。最后转到下一层级，即n = n + 1，返回步骤4继续搜索，直到最高层级(即n = N)。

重复模式压缩：这里将重复子树中相同位置的节点和边进行合并。为了保留原节点和边属性信息，本文将其整合到压缩后的节点和边中。对于节点属性，压缩后的PID是原节点PID的并集。对于边属性，压缩后的起始时间为原边起始时间的最小值，结束时间为原边结束时间的最大值。

4.3. 文件重复模式压缩

文件重复模式代表多个文件被相同进程处理。本文首先从溯源图中提取每一个文件节点的一阶邻居子图。例如，图2(a)中文件../xx1.tmp的一阶邻居子图由进程firefox (1390)、firefox (3721)和firefox (4670)及相连的边构成。最后，识别具有相同邻居和边操作类型的子图，将这些子图的中心文件节点和边合并。为了防止原信息丢失，本文将原文件节点和边属性整合到压缩后的节点和边中。具体地，压缩后节点的文件名是原节点文件名的并集，边的起始时间为原边起始时间的最小值，边的结束时间为原边结束时间的最大值。

5. 实验评估

本文在一台具有两颗Intel Xeon Gold 6226R 2.9 GHz CPU和256 GB内存的服务器上评估压缩方法。评估数据集是在实验环境中使用系统监控工具采集的6种攻击数据。这里主要评估所提方法的压缩效果，压缩后的溯源图对攻击调查的影响及压缩算法的运行时间。

5.1. 数据集

本文在6台Linux主机上部署系统监控工具Sysdig [29]去采集系统审计数据。在监控期间，本文基于已知的系统漏洞和Kill Chain框架[31]在这些主机上执行6种APT攻击，具体的攻击行为信息如下：

攻击email服务器(A1)：某公司内部的一名员工将恶意代码段写入到正常软件中，并将其上传到公司内部的资源网站。之后，该软件被一名员工下载并执行，此时恶意代码段将创建与攻击者远程服务器之间的后门通道，并监控发送的电子邮件内容。

破坏编译系统(A2)：攻击者将恶意C源代码上传到内部资源网站。当受害者下载并编译恶意源代码时，编译过程将改写编译器配置文件，导致编译系统崩溃。

篡改敏感数据(A3)：攻击者在一天时间里多次使用窃取的密码登录目标主机，然后收集并篡改敏感数据。最后，攻击者通过电子邮件传回这些敏感数据

泄露敏感文件(A4)：攻击者利用Shellshock漏洞[32]侵入目标主机，并建立后门通道。之后，攻击者通过后门发送恶意软件并执行，该恶意软件能够扫描并传回敏感文件。

破解密码(A5)：攻击者通过后门向目标主机发送密码破解器payload并执行获取root密码。然后，攻击者利用root权限渗透同一网段内的其它主机。

VPN Filter(A6)：VPN Filter [33]是一种执行APT攻击的模块化软件。攻击者使用VPN Filter渗透目标主机，建立后面通道，窃取敏感数据。

这些被监视的主机拥有10个活跃用户，执行日常的系统任务(如，网页浏览、文本编辑和数据分析等)。在一天内，Sysdig收集的日志事件共有1,948万个。本实验在采集的日志数据上执行因果分析，并构建依赖关系图，之后针对上述6个攻击行为在依赖关系图上分别执行溯源分析，并构建溯源图，其节点数和边数在表2中第2列所示。

5.2. 压缩效果评估

Table 2. Compression results of 6 attack provenance graphs

表2. 6个攻击溯源图的压缩结果

攻击场景	溯源图		预处理		进程重复模式压缩		文件重复模式压缩
	节点数	边数	节点数	边数	节点数	边数	节点数	边数
A1	527	89,020	167	414	158	402	103	260
A2	461	20,505	223	573	174	502	154	326
A3	6584	10,726,103	505	1291	381	1017	258	709
A4	1105	111,759	128	362	104	316	99	259
A5	173	22,675	38	69	32	62	31	59
A6	22,953	484,050	595	1549	79	185	75	175
平均	5300	1,909,019	276	710	155	414	120	298

本文所提的进程重复模式和文件重复模式压缩是在预处理后的溯源图上执行的。预处理包括已有的压缩过程：合并平行边[18]、移除只读文件节点[20]、移除不可达文件节点[17]。本节实验是验证所提压缩方法能否在已有的压缩工作基础上进一步减小溯源图规模。表2给出了在6个攻击溯源图上的压缩结果。针对进程重复模式，压缩后的节点数和边数相比压缩前(预处理后)分别平均减少了121个和296条，平均压缩率为43.84%和41.69%，最大压缩率为86.72%和88.06% (A6)。文件重复模式压缩是在进程重复模式压缩后进行，其压缩后的节点数和边数相比压缩前(进程重复模式压缩后)分别平均减少了35个和116条，平均压缩率为22.59%和28.02%，最大压缩率为32.28%和30.29%。由此可见，进程重复模式压缩和文件重复模式压缩在已有压缩工作基础上再一次减小了溯源图规模。

5.3. 攻击调查影响评估

为了评估本文压缩算法是否会影响后续的攻击调查，本实验选择两个已有的攻击调查方法Nodoze [9]和DepComm [11]分别在压缩前和压缩后的溯源图上执行攻击调查，并比较检测出攻击事件的相似性。Nodoze首先维护一个良性事件库，该库记录了良性事件频率信息，之后根据库中的良性事件频率计算溯源图中每个路径的异常分数，具有较高异常分数的路径为攻击路径。DepComm将溯源图根据行为任务阶段划分社区，之后根据关键特征(如事件唯一性、时间跨度等)提取能代表社区的重要行为路径，该路径已包含攻击事件。表3指出Nodoze和DepComm方法在压缩前和压缩后的6个溯源图上调查出的攻击事件的相似性均为100%。由此可见，本文提出的压缩方法不会影响后续的攻击调查，归因于被压缩的结构是重复的不会带来更多有价值的信息，而且重复结构中的重要信息如进程号、文件名、时间等被保留在压缩后的节点和边中。

Table 3. Similarity of attack events investigated on uncompressed and compressed provenance graphs

表3. 在压缩前和压缩后溯源图上调查出攻击事件的相似性结果

攻击调查方法	A1	A2	A3	A4	A5	A6
Nodoze	100%	100%	100%	100%	100%	100%
DepComm	100%	100%	100%	100%	100%	100%

为了评估压缩后的溯源图是否会减少攻击调查时间，本实验统计了Nodoze和DepComm方法分别在压缩前和压缩后溯源图上的运行时间(图3所示)。Nodoze方法在6个压缩前溯源图上的平均运行时间为4.190秒，压缩后的平均运行时间为1.092，平均减少了73.9%。DepComm方法在6个压缩前溯源图上的平均运行时间为373.535秒，压缩后的平均运行时间为134.112，平均减少了64.1%。因此，本文提出的压缩方法能够有效减小攻击调查时间。

(a) (b)

Figure 3. Runtime of attack investigation execution on uncompressed and compressed provenance graphs. (a) Nodoze, (b) DepComm

图3. 在压缩前和压缩后溯源图上执行攻击调查的运行时间对比。(a) Nodoze，(b) DepComm

5.4. 运行时间评估

Table 4. Runtime

表4. 运行时间

攻击场景	溯源图	预处理	进程重复模式压缩	文件重复模式压缩
A1	60.890	17.523	0.036	0.034
A2	17.585	3.866	0.053	0.041
A3	614.540	2946.905	0.155	0.105
A4	255.498	21.717	0.034	0.026
A5	228.755	4.644	0.006	0.005
A6	4692.534	97.983	0.357	0.022
平均	978.300	515.440	0.107	0.039

为评估运行时间，本实验针对6个攻击溯源图统计了每个阶段的运行时间(如表4所示)。具体来说，溯源图构建平均用时978.300秒，预处理平均用时515.440秒，进程重复模式压缩平均用时0.107秒，文件重复模式压缩平均用时0.039秒。由此可见，本文提出的压缩方法总用时(重复模式压缩时间 + 文件重复模式压缩时间)不超过0.2秒，用时较少，不会占用更多攻击调查时间。

6. 总结与展望

本文发现从系统审计日志构建的溯源图存在大量重复的冗余结构，这些冗余结构被分为进程重复模式和文件重复模式，并提出有效的压缩方法。本文通过进程世系树构建，文件和网络信息关联，重复满子树遍历完成进程重复模式压缩。本文通过一阶邻居相似性搜索实现文件重复模式压缩。最后，本文通过实验在真实数据集上进行压缩效果评估、攻击调查影响评估和运行时间评估，证明所提压缩方法的有效性。

基金项目

国家自然科学基金(62362038)，博士启动基金(205200100654)。