图论在网络安全中的应用

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. 为什么安全问题就是图的问题

漏洞扫描器产出的是一份清单。它告诉你这台主机运行着过时的库，那台暴露了管理界面，第三台有一个弱服务账户。每一项都有一个严重等级，清单排好序，排在最前面的被修复。

攻击者读这份清单的方式和防御者不同。一次入侵是一个序列：在某个无关紧要的地方站稳脚跟，在那里窃取一个凭据，一个信任该凭据的服务，一个信任该服务的共享，最终到达真正重要的东西。每一步单独看都可能毫不起眼。组合起来才是入侵。

这种差异恰恰就是集合与图的差异。一份弱点清单没有结构；一组弱点加上它们之间的转移，就是一张有向图，而图一旦存在，防御者关心的问题就变成了标准算法。哪条路线最容易？最短路径。哪些控制能切断所有路线？最小割。一次失陷能到达哪里？可达性。恶意软件何时不再自行消亡？邻接矩阵的最大特征值。

这在文献中并不是新想法。Phillips 和 Swiler 在 1998 年提出了基于图的漏洞分析，Sheyner 等人在 2002 年用模型检测实现了攻击图的自动生成，此后这一方法一直是研究中的标准做法。新的是工具终于跟上了：现代环境大到没人能把所有路径记在脑子里，而这种规模的图可以在毫秒内求解。

本文的每个数字都是通过求解模型算出来的，而不是估计的。如果你对图的术语还不熟悉，图论入门涵盖了这里用到的定义。

2. 攻击图：节点、弧与权重

有三个建模决策承担了主要分量，每个都有一个实实在在的取舍。

什么是节点？最简单而有用的选择是主机，本文就是这样做的。研究模型通常更细：一个节点是一个状态，即一台机器与一个权限级别的组合，这样“web01 上的普通用户”和“web01 上的 root”就是不同的顶点。这更贴近实际，但规模也大得多，因为状态空间会成倍增长。也有更粗的模型，一个节点就是一整个子网。选择你的控制措施所作用的粒度，因为模型的存在就是为了比较控制措施。

什么是弧？攻击者可以完成的一次转移：一个可利用的服务、一段信任关系、一个被复用的凭据、一次共享挂载、一个钓鱼目标。弧是有向的，因为失陷只朝一个方向流动。一台挂载了文件共享的工作站给你的是一条指向共享的弧，而不是从共享出发的弧，方向一旦弄错，所有结果都会颠倒。

弧上放什么？至少一个数字，而这个选择决定了“最短”的含义：

• 攻击者代价，即一个难度分数。这时最短路径就是最容易的入侵。本文使用的就是代价。
• 成功概率。沿路径相乘而不是相加，或者把负对数相加，原样使用同一个最短路径算法。
• 控制成本。消除这条弧的缓解措施的价格。在这些数字上求最小割，就是切断所有路线的最便宜方式，这是第 6 节的内容。

这些数字从哪里来？通常来自 CVSS 可利用性这类评分体系，再由熟悉环境的人校准。它们是估计值，诚实的立场是排序远比绝对值可靠。即使你无法为 3 分还是 4 分辩护，你也能为“公开的 Web 漏洞利用比窃取域管理员凭据更容易”辩护，而下面的结果正是由这种先后顺序决定的。

3. 贯穿全文的网络

贯穿全文的示例是一家小企业，刻意选得很普通。互联网可以到达三个暴露的系统：一台公共 Web 服务器、一个邮件网关和一个 VPN 集中器。它们后面是两台工作站和一台应用服务器，然后是一台文件服务器和一个数据库，最后是攻击者想要的域控制器。

十六条弧中的每一条都带有一个攻击者代价和一个控制成本。代价分数表明：利用公共 Web 应用需要 3，从 DMZ 到应用层的一次内部服务调用需要 2，而从工作站窃取缓存的域管理员凭据需要 8，这很难但并非不可能。这些相对判断就是模型唯一真正的输入。

在运行任何算法之前先说明一个结构特点：这张图没有环，因为每条弧都让攻击者更深入一步。真实的攻击图确实有环，因为攻击者可以来回横向移动，下面用到的每个算法都能处理环。无环的情形只是让示例更容易手工核对。

4. 最容易的入口：最短攻击路径

第一个问题是渗透测试人员要花两周手工回答的问题：从互联网到域控制器最容易的路线是哪条？弧上放的是代价时，这就是一个最短路径问题，而 Dijkstra 算法能一次性为所有资产给出答案。

答案是 internet → web01 → app01 → db01 → dc01，总代价为 12。看看这些步骤：利用公共 Web 应用（3），借助受信任的内部服务调用进入应用层（2），到达应用有权查询的数据库（3），再利用数据库服务账户攻击域控制器（4）。

这个结果中有两点比数字本身更重要。

这四个步骤单独看没有一个令人警觉。一个评分为 3（满分 10）的 Web 应用漏洞不会排在风险登记表的前列。两个本就应该互相通信的系统之间的一次服务调用也不会。这条路线作为组合才危险，而任何按主机给出的严重等级都无法表达组合。这是支持攻击图的根本论点，由 Phillips 和 Swiler 在 1998 年提出，此后每篇论文都在重复。

最容易的路线避开了人。钓鱼是讨论最多的初始访问手段，而这里通往域控制器的钓鱼路线代价是 14，不是 12。模型并不是说钓鱼不重要；它说的是在这个环境、这些评分下，服务器路径更便宜。求出攻击者最便宜的选项，而不是防御者最害怕的选项，正是这个算法的用途。

同样的计算还给出了到达其他每个资产的代价：web01 为 3，app01 为 5，文件服务器为 8，数据库为 8。这些就是应该摆在审计委员会面前的数字，他们想知道边界离核心资产到底有多远。

5. 十六条入侵路线，以及由哪台主机承载

最便宜的路径只是一个答案。封堵它算不上策略，因为攻击者只会换下一条。有用的问题是总共有多少条路线，它们经过哪些资产。

在这张图上枚举从互联网到域控制器的所有简单路径，得到 16 条不同的路线，代价在 12 到 25 之间，中位数为 18.5。十六之所以是个小数目，正是因为这个例子很小；一个有几千台主机的真实环境，攻击路径的数量常常多到根本不值得去数，因此枚举只是教学手段，下面的指标才是生产中使用的技术。

统计这些路线中有多少条经过每台主机，就得到一个排名，而这个排名和边界报告给出的排名不同。

文件服务器位于 16 条路线中的 12 条上，占四分之三。公共 Web 服务器是大多数组织中受到最严密审视的机器，却只位于 3条路线上。在外部扫描中，文件服务器没有任何值得标记的地方：它没有暴露，没有运行什么特殊的东西，只是用来存放文档。它之所以关键，是因为它在图中的位置，而只有图才能说明这一点。

枚举也是这种方法不再能扩展的地方，值得看清原因。十台主机、十六条弧产生了十六条路线。再加一台两台工作站都能到达的文件服务器，路线数大约翻倍；一个有几千台机器、内部网络扁平的真实环境，路径数的位数多到没人会去读。下面的指标都避开了枚举，这正是它们能在真实网络上使用的原因。

这个度量是安全领域特有的、介数中心性的近亲。介数中心性由 Freeman 在 1977 年提出，统计经过某个顶点的最短路径所占比例。所有顶点对上的介数是网络科学的标准度量，用 Brandes 算法可在 O(nm) 内算出。对防御而言，统计真正相关的那一对之间的路径，即攻击者的入口和你关心的资产之间的路径，通常更具可操作性：它回答的是“如果我加固一台机器，会打乱多少条路线”，而不是“它总体上有多中心”。

Noel 和 Jajodia 在 2008 年就传感器部署提出了同样的观点：把检测放在攻击路径汇聚的地方，而不是最有价值的资产所在的地方，因为汇聚点才能让每个传感器获得最大的覆盖面。

6. 切断所有路线：最小割

对主机排名告诉你该看哪里。更有力的问题是，哪一组控制能一次切断所有路线，以及最少要花多少钱。

给每条弧赋予消除它的控制成本，然后计算互联网与域控制器之间的最小割。最大流最小割定理保证，最便宜的这样一组弧恰好就是最小割，而算法能在多项式时间内返回它。同样的机制在网络流、最大流与最小割中有详细介绍。

答案是三项控制，总计 7：阻止 DMZ 中的 Web 服务器调用应用层（3），阻止邮件附件在工作站上执行（2），让 VPN 用户接入受限网段而不是与工作站同处一处（2）。实施之后重新枚举路径，结果为零。

注意割落在哪里。三项控制都位于边界与内部的交界处，没有一项触及域控制器、数据库或文件服务器。先加固核心资产的直觉并不是数学给出的建议：最便宜的完整修复位于图中最窄的地方，而在这里就是向内的第一跳。

同样的问题换成机器而不是链路时，要用到节点拆分技巧。把每台主机换成一个入口副本和一个出口副本，两者之间用容量为 1 的弧相连，真实的弧设为无穷大容量，最小割此时统计的就是主机而不是链路。这里的答案是 3 台主机：web01、mail01 和 vpn，恰好是面向互联网的那三台。在小例子上这是一个令人放心的合理性检查，在大例子上则是真正有用的计算，因为那时对应的集合很少一目了然。

7. 单项控制究竟能换来什么

预算很少能同时资助三项控制，所以实际问题是先买哪一项。依次移除每条弧并重新求解，就能得到答案，而这个答案令人清醒。

最好的单项控制把攻击者的代价从 12 提高到 14。仅此而已。在这个网络上，没有哪一项措施能带来超过两点的难度提升，因为图的连接非常丰富，攻击者只需换到下一条最便宜的路线。这是一条熟悉的安全真理的量化版本：纵深防御不是口号，而是这样一个事实的结果：在稠密图中，单独的切割作用甚微。

这张表还表明你选择的指标会改变排名。封堵从邮件网关到工作站的转移，会把路线数量减半，从 16 条降到 8 条，却完全不影响攻击者代价为 12 的最容易路径。如果你的董事会汇报的是“消除的攻击路径”，你会称这项控制为成功；如果汇报的是“攻击者代价”，你会说它毫无用处。两个数字都是真实的，衡量的东西不同，只引用其中一个，正是安全项目最终优化了错误指标的原因。

这张表中性价比最高的是封堵数据库到域控制器的路线：成本 5，代价升到 14，路线降到 7 条。它是唯一一项能显著改善两个指标的控制，任何直觉都不会找出它。

8. 爆炸半径：一次失陷能到达哪里

攻击路径问的是入侵者如何进来。与之互补的问题是，一旦他们进入某处，会发生什么，而这是一个简单的可达性计算：从一台失陷主机出发，最终能到达哪些资产？每台主机做一次遍历，就能在线性时间内回答。

这个排名与暴露程度的排名正好相反。公共 Web 服务器是环境中暴露最多的机器，却只能到达 4 个资产。邮件网关能到达 6个。一台工作站能到达 5个。暴露程度衡量的是谁能到达你；爆炸半径衡量的是你能到达谁，同一张图会由此得出两份不同的优先级清单。

应该让会议停下来的数字是这个：十台主机中有九台最终都能到达域控制器。只有域控制器自己不能，因为它后面什么也没有。在真实环境中，这个数字是整个分析最有用的产出，因为它把“我们的网络是扁平的”从一种看法变成了一项测量。

爆炸半径也让事件响应中的遏制决策变得可行。当一台主机被确认失陷时，需要调查的机器集合就是它的前向可达集，而可能感染了它的机器集合是它的后向可达集，在反向图上计算。两者都只需一次遍历，而且都远比凭直觉隔离整个子网精确。

9. 蔓延有多快：流行病阈值

勒索软件和蠕虫不沿单一路径前进，它们会扩散。建模这种情况需要另一个问题：给定一个网络，以及一种在邻居之间传播、并以一定速率被清除的感染，它会消亡，还是会占领整个环境？

答案是网络科学中最有用的结果之一，而且是精确的。对于非常广泛的一类传播模型，临界点只取决于一个数：邻接矩阵的最大特征值，记作 λ₁。传播与清除之比低于 1 / λ₁ 的感染会自行消亡；高于它，就会成为地方性流行。Wang、Chakrabarti、Wang 和 Faloutsos 在 2003 年证明了这一点，Chakrabarti 等人在 2008 年将其推广。

在这里的横向移动图上，九台主机、十三条链路，λ₁ 为 3.573，所以阈值为 0.280。以该比值的 40% 模拟一次感染，对 600 轮取平均，它在第 21 步前灭绝。当比值为阈值的四倍时，它稳定在 9 台中的 5.5 台，并一直保持下去。阈值在任何一次模拟运行之前就预测了这两个结果。

让这一点在运维上变得有意思的是，λ₁ 是你可以改变的东西。把文件服务器与工作站和应用层隔离，会移除三条链路，把 λ₁ 从 3.573 降到 2.570，阈值从 0.280 提高到 0.389。这是一个大了 39% 的余量：原本会扎根的感染，现在会自行消亡。

有两个事实让特征值比初看起来更容易推理。它总是介于图的平均度和最大度之间，这里就是介于 2.889 和 5 之间，而 3.573 正好落在其中。它还由网络最稠密的部分主导，所以降低它的最快方式，就是减少连接最多的那台主机的连接。上面的网段隔离做的正是这件事：文件服务器的度为 5，是环境中最高的，切断它的三条链路后，它的度降到 2，整张图的最大度也从 5 降到 3。连接最多的机器就是要隔离的那台，而度只需一行计算，在碰任何特征值代码之前就能算出来。

这改变了看待网段隔离的方式。“对网络做分段”通常靠讲故事来论证；在这里，它是对一个可计算量的干预，有前有后。这个思路可以追溯到 Kephart 和 White，他们在 1991 年为 IEEE Security and Privacy 构建了计算机病毒的有向图流行病模型，以及 Staniford、Paxson 和 Weaver，他们 2002 年对蠕虫传播的分析表明，图越稠密，曲线变化得越快。

10. Active Directory：攻击者早已在用的图

到目前为止，一切都是防御者构建的模型。企业安全中影响最大的图早已存在，没人刻意设计过它，而攻击者已经查询它多年：Active Directory。

无论有没有人把它画出来，AD 环境都是一张图。用户是顶点，组是顶点，计算机是顶点，而弧就是目录本来就存储的关系：是成员、是管理员、可重置密码、有会话、拥有、有 GenericWrite 权限。每一种关系都是攻击者可以利用的一次转移。

2016 年，Robbins、Vazarkar 和 Schroeder 发布了 BloodHound，并做了为这项技术命名的演讲“Six Degrees of Domain Admin”。它的洞见正是本文的洞见：单独无害的事实会组合起来。一个帮助台组可以重置另一个组的密码，而那个组里恰好有一个用户在某台服务器上有活动会话，上周二又有一位域管理员登录过那台服务器，这就是一条通往全面失陷的四跳路径，而其中没有哪一环看起来像是配置错误。

BloodHound 所做的，就是收集这些关系并在上面运行最短路径查询。这就是 Dijkstra，只不过是在一张没人想到要画的图上。结果改变了防御实践，因为它揭示的路径既真实存在，又对当时使用的所有其他工具不可见。

有三条经验适用于任何环境：

• 数据早已存在。目录关系、云 IAM 策略、Kubernetes 角色绑定和 SaaS 共享权限都是存放在数据库里的图，等着被当作图来查询。
• 会话也是弧。一次登录会话会从那台机器向该身份的权限建立一条临时边，这就是为什么“谁登录在哪里”是一个安全问题，而不是资产盘点问题。
• 清理就是编辑图。移除一个嵌套的组成员关系就可能删掉成千上万条路径，而没有图就无法看出这一点。

11. 检测：溯源图与关联定罪

攻击图用于预防。另外两种图技术用于检测，它们使用的是完全不同的图。

溯源图记录系统上实际发生的事情：进程、文件、套接字，以及它们之间的因果关系。一个进程读一个文件，写另一个文件，启动一个子进程，打开一个连接。King 和 Chen 在 2003 年的 SOSP 上通过 BackTracker 系统提出了回溯方法：从一个检测点出发，例如一个可疑文件，反向遍历因果图，找出它是如何到达那里的。从入口点做前向遍历告诉你损害范围；从症状做后向遍历告诉你根本原因。两者都是在同一个记录结构上的图遍历。

现代版本会把这些流与已知的攻击者行为进行关联。2019 年发表于 IEEE Security and Privacy 的 HOLMES，把溯源图中的可疑信息流映射到攻击生命周期的战术和技术上，当信息流的模式更像入侵而不是正常活动时就发出告警。工程上的难点在于规模：在一台繁忙的主机上，溯源图每小时会增加数百万条边，这使得高效的压缩和查询本身就成了全部的研究问题。

关联定罪是第二种技术，它是图上的推断而不是遍历。构建一张机器与文件的二部图：一台机器与它见过的每个文件相连。大多数文件和机器没有标签，但少数已知是良性的，少数已知是恶意的。信念传播随后沿着边扩散这些标签，其假设是：出现在许多受感染机器上的文件是可疑的，而含有许多恶意文件的机器已经失陷。

这就是 Chau、Nachenberg、Wilhelm、Wright 和 Faloutsos 在 2011 年构建的 Polonium，它运行在一张来自赛门铁克遥测数据、约 600 亿条机器与文件之间的边的图上，报告的真阳性检测率约为 85%。这项技术之所以重要，是因为它既不需要特征码也不需要沙箱：一个从未被分析过的文件，可以凭它所处的“圈子”来判断。同样形式的计算，即二部图加标签传播，也驱动着支付领域的欺诈检测和社交平台上的滥用检测。

12. 软件供应链图

最后一张图是你的构建系统所遍历的图。一个现代应用声明少量直接依赖，每个依赖又声明自己的依赖，传递闭包通常会达到数百甚至数千个包。这个闭包是一张有向无环图，也是一个攻击面。

安全问题是一个可达性问题。如果图中深处的某个包被攻破，你的哪些应用会执行它的代码？这就是在反向依赖图中从被攻破节点出发的前向可达性，也是每个组织在供应链事件发生后的第一个小时里都在手忙脚乱地回答的查询。维护了软件物料清单的团队几秒钟就能回答；没有的团队要花好几天用 grep 搜索。

这张图的两个性质让它的危险程度是一份清单无法揭示的。深度隐藏风险：一个你从未选择过的包，位于你选择的某个包之下三层，却以与你自己的代码相同的权限运行。流行度集中风险：入度最高的包是价值最高的目标，因为攻破其中一个就能同时波及成千上万个下游项目，这正是 Ohm、Plate、Sykosch 和 Meier 在 2020 年对真实开源供应链攻击的综述中所记录的模式。

有用的防御指标就是图指标。统计传递闭包的大小，而不是直接依赖的数量。按有多少个应用会到达某个依赖来给依赖排名。留意那些只有一名维护者却有很大入度的包，这正是几起最知名事件背后的风险特征。这项技术与第 8 节中的爆炸半径计算完全相同，只是换了一张图。

13. 什么容易，什么困难

攻击图分析在安全技术中不同寻常，它有一个清晰的复杂度图景，知道一个问题落在界线的哪一侧，可以省下大量白费的功夫。

规律是熟悉的：关于流与连通性的问题很便宜，关于要改变哪些离散的东西的问题很昂贵。枚举是夹在中间的陷阱。它直观，每次演示都在用，而简单路径的数量会随网络规模呈指数增长，这就是为什么严肃的工具会在图上计算指标，而不是列出它的路径。Ammann、Wijesekera 和 Kaushik 在 2002 年正是这样论证的，他们提出了一种紧凑的单调表示，以多项式方式扩展，而不是去枚举。

一个值得记住名字的指标是 k 零日安全性，由 Wang、Jajodia、Singhal、Cheng 和 Noel 在 2014 年提出。它问的是攻击者需要多少个不同的未知漏洞才能到达一个资产，从而绕开了每个漏洞利用有多大可能成功这个无法回答的问题。它是在另一种权重下的图距离，也是这个领域更好的直觉的一个例证：衡量结构，而不是概率。

14. 建模错误

一张错误的攻击图比没有更糟，因为它会产生自信、具体而错误的优先级。以下是反复出现的失误。

• 把弧的方向弄反。一台挂载共享的工作站会产生一条指向共享的弧。把它反过来，文件服务器看起来就很安全，工作站看起来很关键，而输出中没有任何地方看起来出了错。
• 风险在身份上，却对主机建模。如果真正的转移是一个在三个地方都能用的凭据，两台机器之间的一条弧就无法刻画它。这就是为什么第 10 节中的 Active Directory 图是一个独立的模型，而不是对这个模型的细化。
• 把评分当作测量。代价数字是判断。相信顺序，不要相信小数点后第三位，并检验结论在扰动评分后是否依然成立。如果一个 3 变成 4 时推荐的控制就变了，就把这一点说出来。
• 忘了图只是一张快照。一台笔记本接入 VPN 会增加弧；一台服务器下线会移除弧；迁移期间的一个临时防火墙例外，可能会打开一条任何图纸都没记录过的路线。攻击图的时效性取决于它背后的资产清单。
• 在真实环境中枚举路径。在十台主机上效果很好，在一万台主机上永远算不完。改为计算割、中心性和可达性，它们都是多项式的。
• 只报告一个指标。第 7 节展示了一项把攻击路径数量减半、却丝毫没有拖慢攻击者的控制。把攻击者代价和路线数量一起公布，否则项目就会去优化恰好出现在幻灯片上的那一个。
• 忽略无法移除的弧。有些转移本身就是业务：应用必须查询数据库。模型应该把它们标为固定的，这样优化器就不会再提出永远不会被批准的控制。

15. 从模型到实践

有四件事把一张能在会议上让人眼前一亮的图，与一个能改变决策的模型区分开来。

用你已有的数据构建图。防火墙规则集、云安全组定义、漏洞扫描输出、Active Directory 关系和 EDR 遥测都描述了边。在研讨会上手工拼出来的模型，研讨会后一周就过时了；由配置生成的模型每晚都会重新生成。

从可达性开始，而不是从攻击路径开始。最便宜的有价值结果是第 8 节中的爆炸半径表，因为它根本不需要对漏洞利用打分，只需要连通性。“我们十台主机中有九台能到达域控制器”是一个能引起重视的发现，而且在任何人争论 CVSS 之前你就能给出它。

使用现有的工具。 MulVAL 是 Ou、Boyer 和 McQueen 在 2006 年发表的可扩展攻击图生成器，至今仍是研究中的参考实现。BloodHound 覆盖身份图。一旦有了边，NetworkX 或图数据库就能完成分析。本文中的算法没有一个需要从零写起，而任何算法教材的图论章节都涵盖了那些确实需要写的。

重新求解，而不是争论。本文的每一个结论都是模型在几毫秒内得出的：最容易的路线避开了工作站，文件服务器承载的路线是 Web 服务器的四倍，最好的单项控制只带来两点代价，网段隔离把流行病阈值提高了 39%。对网络的直觉恰恰在最关键的情形下靠不住，而构建这张图的全部价值就在于你不再需要依赖直觉。

16. 下一步

内化这些内容最快的方法，是亲手构建一张图，而不是读关于图的文章，而且门槛比看起来要低。本文只用了十台主机和十六条弧，放进一个文本文件就够了，上面的每个结果都来自几十行普通代码。

学习这些组成部分的合理顺序是：先熟悉广度优先搜索和深度优先搜索，因为可达性和爆炸半径不过是带记账的遍历。然后是最短路径算法，它给出最容易路线的分析，而在弧上使用负对数时，也能给出最可能路线的分析。然后是最大流与最小割，这就是第 6 节和第 7 节的全部内容，也是防御安全中最未被充分利用的结果。

此后，有用的方向更偏结构而不是算法：有向图与无向图能解决数量惊人的建模争议，而图的表示方法决定了当环境变大时你的分析是运行一秒还是一小时。第 13 节中的复杂度界限，在图算法与复杂度中有更一般的阐述。

如果你更愿意从安全这一侧入手，通往真实结果的最短路径是导出你的 Active Directory 关系并加以查询，因为这张图已经存在，无需任何人去建模。随之而来的发现通常与本文的结尾相同：最终能到达域控制器的机器数量，远远超出在场任何人的预期。

18. 参考文献

奠定这些技术的论文，按时间顺序排列。

1. Ford, L. R. and Fulkerson, D. R. (1956). “Maximal flow through a network.” Canadian Journal of Mathematics, 8, 399–404.
2. Freeman, L. C. (1977). “A set of measures of centrality based upon betweenness.” Sociometry, 40(1), 35–41.
3. Kephart, J. O. and White, S. R. (1991). “Directed-graph epidemiological models of computer viruses.” Proceedings of the IEEE Symposium on Security and Privacy, 343–359.
4. Phillips, C. and Swiler, L. P. (1998). “A graph-based system for network-vulnerability analysis.” Proceedings of the New Security Paradigms Workshop, 71–79.
5. Ammann, P., Wijesekera, D. and Kaushik, S. (2002). “Scalable, graph-based network vulnerability analysis.” Proceedings of the 9th ACM Conference on Computer and Communications Security, 217–224.
6. Sheyner, O., Haines, J., Jha, S., Lippmann, R. and Wing, J. M. (2002). “Automated generation and analysis of attack graphs.” Proceedings of the IEEE Symposium on Security and Privacy, 273–284.
7. Jha, S., Sheyner, O. and Wing, J. (2002). “Two formal analyses of attack graphs.” Proceedings of the 15th IEEE Computer Security Foundations Workshop, 49–63.
8. Staniford, S., Paxson, V. and Weaver, N. (2002). “How to own the Internet in your spare time.” Proceedings of the 11th USENIX Security Symposium, 149–167.
9. King, S. T. and Chen, P. M. (2003). “Backtracking intrusions.” Proceedings of the 19th ACM Symposium on Operating Systems Principles, 223–236.
10. Wang, Y., Chakrabarti, D., Wang, C. and Faloutsos, C. (2003). “Epidemic spreading in real networks: an eigenvalue viewpoint.” Proceedings of the 22nd International Symposium on Reliable Distributed Systems, 25–34.
11. Ou, X., Boyer, W. F. and McQueen, M. A. (2006). “A scalable approach to attack graph generation.” Proceedings of the 13th ACM Conference on Computer and Communications Security, 336–345.
12. Chakrabarti, D., Wang, Y., Wang, C., Leskovec, J. and Faloutsos, C. (2008). “Epidemic thresholds in real networks.” ACM Transactions on Information and System Security, 10(4), 1–26.
13. Noel, S. and Jajodia, S. (2008). “Optimal IDS sensor placement and alert prioritization using attack graphs.” Journal of Network and Systems Management, 16(3), 259–275.
14. Chau, D. H., Nachenberg, C., Wilhelm, J., Wright, A. and Faloutsos, C. (2011). “Polonium: tera-scale graph mining and inference for malware detection.” Proceedings of the SIAM International Conference on Data Mining, 131–142.
15. Wang, L., Jajodia, S., Singhal, A., Cheng, P. and Noel, S. (2014). “k-zero day safety: a network security metric for measuring the risk of unknown vulnerabilities.” IEEE Transactions on Dependable and Secure Computing, 11(1), 30–44.
16. Robbins, A., Vazarkar, R. and Schroeder, W. (2016). “Six degrees of Domain Admin.” DEF CON 24.
17. Milajerdi, S. M., Gjomemo, R., Eshete, B., Sekar, R. and Venkatakrishnan, V. N. (2019). “HOLMES: real-time APT detection through correlation of suspicious information flows.” Proceedings of the IEEE Symposium on Security and Privacy, 1137–1152.
18. Ohm, M., Plate, H., Sykosch, A. and Meier, M. (2020). “Backstabber's knife collection: a review of open source software supply chain attacks.” Detection of Intrusions and Malware, and Vulnerability Assessment (DIMVA), 23–43.