一篇关于系统级溯源图的综述初稿，知乎上有[作者n0nam3的文章][https://zhuanlan.zhihu.com/p/145941567]。
介绍
随着信息技术的发展，网络空间的边界越来越宽，暴露出越来越多的漏洞给攻击者。传统的基于缓解的防御策略难以应对当前复杂的形势。安全从业者迫切需要更好的工具来描述和模拟防御攻击。溯源图似乎是一种理想的威胁建模方法，具有强大的语义表达能力和攻击历史关联能力。本文首先介绍了系统级溯源图的基本概念，提出了基于溯源图的威胁检测和调查的典型系统结构。一个全面的基于溯源图的威胁检测系统可以分为三个模块，即“数据收集模块”、“数据管理模块”和“威胁检测模块”。每个模块包含几个组件，并涉及许多研究问题。我们系统地分析了所涉及的算法和设计细节。通过比较，给出了技术选择的策略。此外，我们指出了现有工作的不足之处，以供今后改进。
如图1所示，溯源图通过带时序的有向图表示系统中主体(如进程、线程等)和对象(如文件、注册表、网络套接字)之间的控制流和数据流之间的关系。溯源图可以将系统中的因果事件联系起来，而不考虑事件之间的时间。
溯源图表示为系统对象之间的交互来显示系统执行情况，非结构化的信息也能转化为溯源图。
溯源图保留了历史信息。APT攻击具有长期和隐蔽的特点，分析此类攻击需要了解系统的历史信息。
溯源图有很强的表示信息的能力，具有丰富的语义。
溯源图定义
系统级溯源图将所有系统级实体关系视为顶点，将实体之间的所有操作视为边。这些操作由审计工具收集，并生成带有时间戳的事件流。事件的顺序影响语义，事件是定向的，指示数据或控制的流。因此，溯源图具有很强的时空属性。这种性质被称为溯源图的因果关系。相应的，溯源图也称为因果图。下面给出了一系列相关的基本定义：
定义一：主体Subject和客体Object
主体和客体分别由u和v表示。
需要注意的是，主体和客体是相对的，一个操作的主体可以是另一事件的客体。 主体可以是进程，线程等。客体可以是文件，套接字等。 对于不同的操作系统，主题和客体的类型可能不同。 例如，Windows具有唯一的注册表对象和COM对象。 但是，用更多类型的对象和对象扩展源图并不复杂。
定义二：事件Event
事件是指系统中实体之间的操作。 事件包括四个主要属性：执行操作的主体，正在操作的对象，事件发生的时间以及操作的特定内容。 因此，事件可以用quad < subject; object; time; operation >（或简称为<u; v; t; o>。）
定义三：溯源图
源头图是所有主题、对象、事件的集合，表示为G = (S;O;E)，其中S表示主题的集合，O表示对象的集合，E表示事件的集合。
在溯源图中，主体和客体都被重新表示为节点，而事件被表示为边。时间或操作不同的两个节点之间可以有多条边。
定义四：因果关系
如果v1 = u2 ^ t1 < t2，则认为两个事件e1 =（u1; v1; t1）和e2 =（u2; v2; t2）具有因果依赖关系。
因果关系表明两个事件之间可能存在数据和控制流。 但是，两个事件是因果关系相关的，并不一定意味着它们之间存在数据或控制流。 因此，与污染分析相比[23]，对因果关系的分析将引入更多的虚假依赖关系，并导致更严重的爆炸问题。
定义五：后向跟踪
从单个检测点(例如，一个可疑的文件)开始，后向跟踪试图找到起源图中对检测点有影响的所有节点。
定义六：前向跟踪
从单个检测点开始，前向跟踪过程将尝试在出处图中查找因果关系取决于检测点的所有节点。 向后和向前跟踪广泛用于攻击调查中，以找到切入点并分析攻击的影响。
基于溯源图的检测系统
数据收集模块用于收集系统对象之间的操作，粗粒度的起源信息可以通过内置的审计系统获得，这些系统适用于当今的大多数操作系统，例如ETW [24] (Windows的事件跟踪)和Linux审计系统[10]。更细粒度的信息还需要额外的基础设备，例如公共库或连接到系统调用。
数据管理模块应用不同的数据缩减算法过滤冗余事件，以减少后续的检测和开销。
威胁检测模块是最重要的部分。对于威胁检测，最大的挑战是处理实时生成的大量数据，另一个问题是如何发现可疑事件。
综上所述，一个基础溯源图的威胁检测系统，需要考虑以下问题：
RQ1.缓慢又隐蔽的高级持续性威胁的检测难题：高级持续性威胁（Advanced Persistent Threat）往往采用隐蔽的攻击形式，在很长的一段时间内缓慢的渗透入目标系统并长期潜伏以达到攻击目的。因为其缓慢又隐蔽的特性，传统的防御手段往往很难对其实施有效的监控。正所谓“我设置阈值过高，就会错过攻击；我设置阈值过低，就没空保护系统（误报太多）”。
RQ2.用什么数据什么结构准确度表示一个威胁行为的问题：用什么方式表示一个威胁或攻击行为一直以来被研究者关注。不同的表示方式都有其优点与缺点，很难给出一个绝对的判断，应该根据不同场景做不同选择。举例来说，现在常用的威胁情报（IoC）使用非常简单的数据，包括恶意的IP、恶意文件的Hash，几乎没有任何鲁棒性可言，但却是现实中常用的安全工具，有效的保护了许多系统的安全。其他常见的方式还包括，系统调用的序列、API调用树、代码动态执行图等。一般而言，简单的结构意味着更高的效率，但表达能力更差，误报的概率更高。而复杂的结构，表达能力更好的同时检测效率却受到影响。
RQ3.如何设计检测算法权衡威胁检测的响应速度与检测精度矛盾：威胁检测的系统的响应速度很大程度的影响了该系统的应用场景和价值。响应速度越快，就能越早的定位并阻止进一步的攻击发生，从而尽可能的减小损失。但是鱼与熊掌往往不可得兼，效率高、响应速度快的速度在检测能力上往往不如响应速度慢、收集数据更加全面的系统。现有的系统都尝试在响应速度和检测精度之间找到一个行之有效的平衡点。
RQ4.如何设计存储系统以权衡存储空间与查询效率之间的矛盾：如前面所说，高级持续性威胁往往是“low and slow”的，攻击的周期可能长达几十天。此外，为了保护系统安全，日志系统往往需要保存很长一段时间内的日志以便事后的取证（Digital Forensic）分析。因此系统有很强的存储的日志的需求。对一个大公司来说，这可能以为着PB级的存储以及百万美元的开销。因此日志存储系统的设计和针对性的数据压缩算法也是必不可少的。
目前的两个趋势，第一个是溯源图更加的细粒度，第二个是研究人员越来越重要事实的检测，比如利用streaming graph-based detection
本文主要贡献
- 对现有论文中使用的各种代表性技术进行分类，并描述了当前基于起源的威胁检测系统的典型架构设计。
- 使用各种性能指标系统地比较几十个现有的检测系统。在此基础上，确定了现实世界中技术选择的策略。
数据收集模块
目标主机上部署的收集器通常有两种：
粗粒度收集器，专注于系统级信息流，例如文件读取，进程间通信等；
细粒度收集器，涉及进程内信息流跟踪。
Coarse-grained Provenance Collection
粗粒度数据收集器只跟踪系统级对象之间的起源，也称为系统级收集器。系统级来源可以从多个不同的来源获得。目前大多数操作系统都有内置的审计系统，可以在系统级对象之间提供必要的信息流。
除了操作系统本身的系统，还有一些第三方的收集器，FUSE，CamFlow，SPADE等。
下面是一些例子。
CamFlow[26]采用LSM[39]和NetFilter[40]在Linux上挂钩内核对象安全数据结构。
Ma等人提出[9]从windows内置审计系统ETW[24]中获取系统事件。
SPADE[11]为不同的系统提供了多个收集器模块，如Linux上通过Auditd[10]挂钩系统调用。
Mac OS上通过MacFUSE[41]挂钩系统调用等。
对于不同的操作系统和审核工具，事件列表可能会有所不同。
Fine-grained Provenance Collection
因果关系建模图会产生一个“依赖爆炸问题”，细粒度的源收集器可以通过更精确地关联输入和输出来解决这一点，简单来说，就是降低两个节点之前不必要的边。
待补充，根据上图不同的分类进行细粒度的总结。
数据管理模块
在本节中，我们将从3个方面介绍如何设计理想的数据管理模块：数据存储机制，数据缩减算法和查询接口。
并尝试回答 有两个研究问题，即RQ1：如何在保持语义的同时尽可能减小数据存储的大小，以及RQ2：如何在证明图存储的空间效率与查询的时间效率之间取得平衡？
数据存储机制
一个直接的想法是使用图数据库存储溯源图，它存储所有数据作为节点和边，并提供带有节点和边的语义查询接口。 因此，执行图形算法（例如回溯和图形对齐）相对容易。但是现有的图数据库需要将整个图形数据库加载到主内存中才能启用查询。
但是在大型系统中，对于长时间运行的攻击活动，需要加载TB级的数据。 即使可以分配如此大的内存，但这种方法仍会产生大量的I / O开销。 为了缓解这一挑战，安全研究人员设计了检测算法[3]，[4]，[6]，[47]，该算法仅检测流中的每个事件一次，并采用存储在缓存中的状态来表示事件历史。 与存储在内存中的缓存图相对应，我们将这种方法的输入称为流图。
以关系数据库为基础的以顶点为中心的数据库将所有条目存储为<K; V>对，其中K是代表顶点（节点）的标识符，V是几个条目的列表，例如父节点，子节点和规则[5]。 这种存储机制可以轻松地计算节点之间的交互，因此广泛用于基于异常分析的检测系统中。 此外，关系数据库可以存储在磁盘中，并可以通过内存中的缓存进行加速，因此比基于图形数据库的方法更可行。
数据缩减算法
溯源图的数据主要包括两部分：节点（Subject和Object）和边（Event）。 压缩来源图的本质是在保持尽可能多的语义的同时，尽可能多地删除不必要的节点和边缘。 具体来说，需要考虑三个问题：
1）如何定义需要维护的语义？
2）压缩算法的计算复杂度是多少？
3）压缩算法的效果如何？
考虑到这三个问题，下面将讨论如何分别压缩节点和边。
压缩边
在操作系统中，进程和文件对象将存在一段时间，并在它们之间生成大量操作。因此，在大多数溯源图中，边的数量要比节点的数量大得多。
Causality-Preserving Reduction (CPR)
CPR的做法是对于有多条读写关系的节点对，只保留一条读和一条写这样的关系。这样的做法可以保留图的拓扑结构，并且大多数检测算法对于这样的图仍然有效，但却但是丢失了统计信息，比如访问频率等。
Full Dependence-Preserving Reduction (FDR) and Source Dependence-Preserving Reduction (SDR)
CPR对于边的减少比较有限，FDR和SDR保留的边更少，这两种方式只考虑了溯源图的可达性。
我个人的理解是，不区分操作，比如“写”和“读”只保留一条边。
压缩节点
一些工作才用了网络图压缩算法对溯源图进行压缩，但这些方法开销很大，并且系统级的溯源图信息增长迅速，因此需要轻量级的压缩算法。
Lee等人设计了garbage collecting算法，用于删除孤立节点。
Tang等人设计了nodemerge算法，采用增强的FP-growth算法在程序初始化过程中查找常见的访问模式。
查询接口Query Interface
大多数检测方法倾向于使用一般的数据库查询接口和固定的数据结构来确保通用性。 但是，对于特定的攻击调查要求，单纯的查询接口可能不够灵活。 为了填补这一研究空白，研究人员提出了一系列溯源图查询系统。
Causality Tracking
溯源图具有较强的时空特性，不同于普通图。向后和向前跟踪应该考虑这些属性，这被称为因果关系。这样的跟踪操作是发现和影响分析取证中的常见任务。
Provenance Graph Pattern Matching
图形模式匹配是图形查询的核心。对于基于起源图的威胁检测，可以使用图模式来表示具有丰富语义的攻击行为。因此，模式匹配相当于威胁检测。
Shu等人[57]指出，理想的模式匹配系统应该能够将模式视为值，并基于其他模式组合更大的模式，从而实现模式的重用和抽象。为了实现这一目标，Shu等人采用了设计良好的查询语言和打字系统。
Stream-based Query
威胁检测是一项至关重要的任务。 为了减少攻击与调查和响应之间的延迟，Gao提出了SAQL [56]，它可以将多个主机聚合的实时事件源作为输入并提供丰富的接口。 他们在Siddhi [60]的顶部构建了查询引擎，以利用其成熟的流管理引擎。 为了解决可伸缩性挑战，他们设计了一个依赖于主机的查询方案，该方案标识兼容的查询并将它们分组以使用单个副本。
Anomaly Analysis
安全日志审计和威胁检测很大程度上依赖于专家经验。为了利用专家提供的领域知识来表达异常，Gao提供了一种领域特有的查询语言SAQL[56]，该语言允许分析人员针对：
- (1) rule-based anomalies,
- (2) time-series anomalies
- (3) invariant-based anomalies
- (4) outlier-based anomalies
总而言之，查询系统为分析人员提供了全面的攻击调查功能。 这些系统通常建立在成熟的流处理系统或数据库上，但会通过专门设计的数据模型和查询语言来考虑出处图的特殊属性。
威胁检测模块
简单的回溯算法很难区分正常数据流和恶意控制流。 存在依赖爆炸的问题，因此准确性非常低。
在本节中，会首先介绍溯源图的威胁检测研究中常用的模型。然后，我们对现有的入侵检测系统进行比较，并尝试回答两个研究问题：RQ3：如何设计一种有效而强大的入侵检测算法并最大程度地减少误报？ 和RQ4：如何尽可能缩短检测或可追溯性取证的响应时间？
攻击模型
Multi-Stage APT Attack (APT) Model
APT攻击具有先进性，复杂性，隐蔽性和持久性的特征。 如ATT＆CK指标[67]所示，典型的APT攻击可分为多个阶段。 每个阶段都有一个特定的目标，以及实现该目标的各种不同技术。 现实世界中的攻击通常涉及三个或更多阶段。 因此，即使缺少了一些阶段，安全分析人员仍然可以识别威胁，并使用数字取证技术来完成缺失的部分。
Information Leakage (Leakage) Model
很多APT攻击的表示是使目前的信息泄漏，与多阶段APT攻击模型不同，信息泄漏模型不针对特定的攻击技术，而是针对系统中的信息流，并持续监视敏感信息是否流向未授权点。
General Attack (General) Model
一般的攻击方式更加多样化。有像APT这样的低强度和潜行攻击，也有像勒索软件这样的快速和公开攻击。目标可能是窃取信息，但也可能是纯粹的破坏。因此，需要更通用和详细的攻击模型来检测这类攻击。
威胁检测和威胁调查系统的设计
溯源图能够将系统中的事件与因果关系联系起来，从而对整个攻击有一个全面的了解。回溯是King等人提出的最早也是最基本的针对源头图的攻击调查方法。给定一个检测点，回溯能够遍历系统执行的整个历史上下文。然而，单纯的回溯需要完整的源头图和人工干预，因此既不及时也不有效。
一个理想的威胁检测系统需要同时考虑三个属性：快速响应、高效率和高精度。然而，即使经过缩减，一个来源图的大小也是非常大的，会带来较大的空间和计算的开销。为了找到这三个属性之间的平衡，研究者们做了很多尝试。这些方法根据主要检测设计可分为3类。
基于标签传播的方法
这种做法将系统执行历史增量存储在标签中，并利用标签传播过程来追踪因果关系。这些算法具有大致线性的时间复杂度。 而且，他们可以将流图作为输入并快速响应。
基于标签传播的检测可以分为两个阶段，即标签初始化和标签传播。 在标签初始化阶段，将标签分配给节点。 节点的数量远少于边。 因此，存储和更新标签是有效的。 在标签传播阶段，标签会根据预先设计的规则沿边传递。 在这个阶段，不同的标签可以在同一个节点相遇，并一起进行未来的分流计算。
Jiang等人[65]提出的过程着色是一种简化的基于标记的方法。在标记初始化阶段，标记(颜色)被分配给每个远程可访问的服务器或进程。然后，在标签传播阶段，标签可以由生成的子进程继承，也可以通过进程动作间接扩散。因此，分析人员可以快速识别插入点，而无需繁琐的回溯。
后续工作采用更复杂的标签设计来实现更多功能。 SLEUTH [3]利用两种类型的标签，即可信赖性标签（t-tags）和机密性标签（c-tags）来实现策略执行框架。 简而言之，当可信度低的节点访问机密性较高的节点时，会触发警报。 具体地，在标签初始化阶段，分别根据预定义的可信度和机密性将t标签和c标签分配给节点。 在标签传播阶段，传播可信性和机密性，并且将捕获违反策略的访问。
但是，基于标签传播的方法也存在“依赖爆炸”的问题。 如果没有额外的控制，单个标签会传播到任何地方，并导致许多误报。
为了解决这一问题，Milajerdi等人。 提出了HOLMES，它通过要求更多标签的聚集来提高检测阈值。 在标签初始化阶段，HOLMES仅为处理可疑行为分配较少的标签。 这些可疑行为包含许多误报。 因此，在标签传播阶段，HOLMES需要多个标签来聚合并达到预定义的阈值，然后对警报进行分类。 避免依赖关系爆炸问题的另一种方法是使影响随着传输回合数量的增加而减小。
总之，基于标签传播的方法具有以下优点。首先，标签初始化和传播过程替代了计算开销较大的图匹配算法，降低了开销。其次，基于标签传播的方法每次只处理一个事件，并相应地更新状态，自然支持流式图输入，响应速度快。最后，利用标签中存储的信息可以快速定位入侵点，避免了繁琐的回溯算法。
通过异常检测识别节点之间的异常交互
这些方法将通过收集历史数据或来自并行系统的数据来对正常行为进行建模。
具体来说，Pagoda [5]考虑了单个出处路径和整个出处图的异常程度。 他们的子序列工作P-Gaussian [8]可以使用高斯分布方案检测变异。 PrioTracker [64]和NoDoze [7]根据事件的可疑程度调整事件的可疑程度。
与基于图形的异常检测相比，基于异常评分的检测具有更少的参数可调整，因此更易于实现和部署。 同时，基于异常分数的检测通常采用以向量为中心的关系数据库，该数据库比图形数据库快得多。
基于图匹配的方法
这种做法通过匹配图中的子结构来识别可疑行为。 然而，图匹配计算很复杂，所以研究人员尝试通过图形嵌入或图形草图算法来提取图形的特征，或使用类似的方法。
基于溯源图的图表示可以使检测算法有很强的鲁棒性。彼此靠近的节点更有可能发挥相同的功能。 因此，利用社区检测算法，分析人员能够在相同的攻击场景下关联节点。
溯源图的子结构可以完全描述恶意行为。 然而，直接进行图匹配是NP完全问题，因此，研究人员提出了许多近似方法。
Milajerdi等提出了POIROT，利用从威胁情报中手动提取的查询图和图对齐算法，可以快速地在源图中定位威胁。但是，提取查询图需要大量的手工工作。因此，很难覆盖各种形式的高级攻击。
图嵌入被广泛用于将图特征提取到向量中，同时最大程度地保留图结构和信息之类的属性。 利用图嵌入，研究人员可以通过将恶意和良性日志条目划分为不同的集群并识别恶意集群来有效地检测威胁。 但是，此类方法通常在缓存图上工作，因此响应速度较慢； 同时，它需要大量训练数据，因此不适合高级攻击。log2vec
Han等人提出了UNICORN，它采用历史图素描的方法来构建一个可递增更新的、固定大小的、纵向的图数据结构。因此，当图形结构发生变化时，它们可以发现威胁。但这是一种基于异常检测的方法，存在异常检测的局限性。（蛮有意思的）
未来挑战
Empirical Parameter Setting
为了区分恶意行为与良性行为，基于源图的威胁检测和调查系统涉及许多参数，其调整会严重影响系统的准确性和效率。 但是，参数是根据经验确定的。 例如，Holmes [4]对每种恶意行为和经验预警阈值采用经验数字评分； NoDoze [7]等采用经验衰减因子。 但是，要确保这些参数适用于所有场景并不容易，因为不同系统的行为可能非常不同。 即使对于同一主机，行为在不同时间也可能是多种多样的。 因此，为主机调整的一组参数可能无法在另一个参数上很好地工作。
因此，一个可能的解决方案方向是为每个不同的主机few-shot learning或zero-shot learning等新技术。
Manual Signature Extraction
带标签的数据很稀缺。 一方面，学术界和工业界都缺乏标记良好的真实世界的攻击图数据； 另一方面，提取典型的模式和相应的语义很费力。
例如，Poirot对所有不同的攻击采用了手动提取和预处理的查询图。 提取过程需要大量劳动。 尽管如此，准确性仍未得到保证。 如果查询图太详细，它们可能会错过各种类似的攻击。 相反，如果查询图缺少详细信息，则会有很多误报。
作者说越来越多的安全公司开始提供带有攻击图的威胁情报，可以关注一下。