A Logic based Network Security Analyzer

MulVAL：基于逻辑推理的攻击图生成及风险评估工具

官网 论文 仓库

MulVAL

基本概念

• 背景和需求：如何帮助 系统管理员 自动化漏洞评估和安全措施的选择 （主要是运维阶段+策略验证）
  • 漏洞数量增长：由于每年不断发现新的安全漏洞，系统管理员很难在所有网络机器上确保软件完全没有漏洞
  • 日常任务：系统管理员需要从不同的来源（如 CERT、BugTraq 等）阅读漏洞报告，并判断哪些漏洞是网络中实际存在的安全问题
  • 漏洞评估：对于新发现的漏洞，管理员需要评估这些漏洞对网络的安全影响，从而决定采取哪些应对措施（例如打补丁、重启、重新配置防火墙等）

根据汽车行业标准（例如 ISO/SAE 21434 中的定义），TARA（Threat Analysis and Risk Assessment，威胁分析与风险评估）是一个贯穿 全生命周期 的过程，而不仅仅局限于概念阶段或特定阶段

• 概念阶段

  • 在车辆开发的早期阶段，TARA 用于识别资产、威胁场景和潜在风险
  • 在这一阶段的目标是为网络安全设计奠定基础，确定需要保护的关键资产和可能面临的威胁

• 开发阶段

  • 在开发过程中，TARA 持续更新，以评估新发现的威胁和漏洞
  • 包括详细的攻击路径分析和风险评估，确保安全措施能够覆盖所有识别出的风险

• 验证阶段

  • 验证阶段会结合 TARA 确保已实施的安全措施有效降低风险
  • 此阶段重点验证是否实现了预期的风险减缓效果

• 运营阶段

  • 在车辆运营期间，TARA 需要持续应用，以应对新出现的威胁和漏洞
  • 随着时间推移，资产和威胁场景可能会变化，需要定期更新评估

• 维护和退役阶段

  • 即使在车辆的维护或退役阶段，也需要考虑 TARA 的应用，尤其是针对遗留系统的安全风险

根据 ISO 26262 标准，HARA（Hazard Analysis and Risk Assessment，危害分析与风险评估） 是在 概念阶段 进行的核心活动

HARA 的主要目标是在概念阶段识别潜在的危害，评估其风险，并为后续的功能安全开发制定适当的安全目标和安全要求

虽然 HARA 主要在概念阶段进行，但其结果会贯穿整个开发生命周，安全目标和要求会传递到系统、硬件、软件开发阶段，确保整个系统的功能安全设计

HARA vs TARA 的比较

• 漏洞分析工具有效的前提
  • 能够自动整合来自漏洞报告社区的 正式漏洞规范
  • 且其分析能力能够扩展到包含数千台机器的网络中
  • 这两个问题在之前的相关工作中尚未得到解决（ - 2005）
• MulVAL 是一个端到端的框架和推理系统，用于 多主机、多阶段 的网络漏洞分析
  • “端到端”（end-to-end）指的是 MulVAL 能够覆盖漏洞分析的整个过程，从输入到输出结果，无需依赖其他外部工具或模块
  • 采用 Datalog 作为分析中元素的建模语言（如漏洞规格、配置描述、推理规则、操作系统权限和特权模型等）
  • 漏洞报告社区提供的漏洞数据库信息、每台机器及网络的配置信息以及其他相关信息都被编码为 Datalog 事实
  • 一旦收集到所有信息，对于拥有数千台机器的网络，其分析可以在几秒内完成
  • MulVAL 分析的输入包括以下内容
    • 公告信息（Advisories）：已报告的漏洞有哪些？这些漏洞是否存在于我的机器上？
    • 主机配置（Host configuration）：我的主机上运行了哪些软件和服务？它们是如何配置的？
    • 网络配置（Network configuration）：我的网络路由器和防火墙是如何配置的？
    • 主体（Principals）：谁是我网络的用户？
    • 交互（Interaction）：这些组件之间的交互模型是什么？
    • 策略（Policy）：我希望允许哪些访问权限？

形式化表示

MulVAL 包括两个主要模块：扫描器（scanner）和 分析器（analyzer）

• 扫描器在 每台 主机上异步运行，并大范围利用现有工具（如 OVAL）
• 分析器在接收到来自扫描器的新信息时，在 单台 主机上运行

漏洞公告（Advisories）

开放漏洞评估语言（OVAL） 用于 标准化如何识别计算机系统上的漏洞，OVAL 扫描器基于这些标准化的漏洞定义，对主机进行测试并检查是否存在漏洞，将这些测试结果转化为 Datalog 子句，例如：

1

vulExists(webServer, 'CAN-2002-0392', httpd).

这里表示扫描器在 webServer 主机上发现了编号为 CAN-2002-0392 的漏洞，该漏洞涉及到服务器程序 httpd

然而，OVAL 并未正式化（形式化）描述 漏洞的利用方式及其后果，ICAT，由美国国家标准与技术研究院（NIST）开发的漏洞数据库，提供了有关漏洞影响的信息，将 ICAT 中的相关信息转化为 Datalog 子句，例如：

1

vulProperty('CAN-2002-0392', remoteExploit, privilegeEscalation).

表示该漏洞使远程攻击者能够以程序的全部权限执行任意代码

主机配置（Host Configuration）

OVAL 扫描器还可以被配置为提取主机的配置信息，例如输出服务程序的配置信息（包括端口号、权限等），将其输出转化为 Datalog 子句，例如：

1

networkService(webServer, httpd, TCP, 80, apache).

这表示程序 httpd 在主机 webServer 上以用户 apache 的身份运行，并监听 TCP 协议的 80 端口

网络配置（Network Configuration）

MulVAL 使用抽象的 主机访问控制列表（HACL） 来建模网络（路由器和防火墙）的配置。相关信息可以通过防火墙管理工具（如 Smart Firewall）提供，以下是一个 HACL 条目示例，表示允许从互联网发送 TCP 流量到 webServer 的 80 端口：

1

hacl(internet, webServer, TCP, 80).

主体（Principals）

主体绑定（principal binding）将主体符号映射到其在网络主机上的用户账户。管理员可以定义这些主体绑定，例如：

1
2

hasAccount(user, projectPC, userAccount).
hasAccount(sysAdmin, webServer, root).

交互（Interaction）

在多阶段攻击中，漏洞的语义和操作系统的行为决定了攻击者在每个阶段的选项。我们用 Horn 子句（即 Prolog 子句）对其进行编码，其中第一行是结论，其余是启用条件。例如：

1
2
3
4
5
6

execCode(Attacker, Host, Priv) :-
    vulExists(Host, VulID, Program),
    vulProperty(VulID, remoteExploit, privilegeEscalation),
    networkService(Host, Program, Protocol, Port, Priv),
    netAccess(Attacker, Host, Protocol, Port),
    malicious(Attacker).

这条规则的意思是，如果某程序在某主机上存在可远程利用的漏洞，并且该漏洞会导致权限提升；且程序运行在特定协议和端口上，而攻击者能够通过网络访问该服务，则攻击者可以以该程序的权限在目标主机上执行任意代码。这条规则适用于任何匹配该模式的漏洞。

策略（Policy）

在 MulVAL 中，策略描述了哪些主体可以访问哪些数据。任何未明确允许的操作都被禁止。例如，以下是一个简单的策略：

1
2

allow(Everyone, read, webPages).
allow(sysAdmin, write, webPages).

其中 Everyone 是一个 Prolog 变量，可以匹配任何用户

分析框架（Analysis Framework）

由于 Datalog 是 Prolog 的子集，编码的信息可以直接加载到 Prolog 环境中执行。MulVAL 使用 XSB 作为运行环境，因为它支持 Prolog 程序的表格化执行（tabling），表格化是一种动态规划技术，可以避免重复计算已得出的事实。此外，表格化还提供了完全声明式的逻辑编程，因为规则的顺序不会影响执行结果

MulVAL 框架：

• OVAL 扫描器在每台机器上运行，并输出漏洞报告和相关的配置信息
• 扫描器的元组、网络配置（以 HACL 表示）、推导规则和管理员定义的安全策略被加载到 XSB 环境中
• Prolog 查询可用于搜索策略违规情况，并生成详细的攻击树

漏洞规范

一个安全漏洞的规范通常包括两个部分：

1. 如何在系统中识别漏洞的存在
2. 漏洞对系统造成的影响

识别规范 仅用于主机扫描，而 影响规范 则用于漏洞分析推理过程。漏洞报告社区已经开始以正式、机器可读的格式提供这些信息

OVAL（一种用于识别漏洞的正式语言）

开放漏洞评估语言（OVAL） 是一种基于 XML 的语言，用于指定机器配置的检测规则。当发现新的软件漏洞时，OVAL 定义可以描述如何检查机器是否存在该漏洞。OVAL 定义文件可以被 OVAL 兼容的扫描器使用，执行指定的测试并报告结果。

目前，OVAL 漏洞定义适用于 Windows、Red Hat Linux 和 Solaris 平台，并且 OVAL 兼容扫描器可用于 Windows 和 Red Hat Linux 平台。自 2002 年以来，OVAL 漏洞定义不断更新，截至 2005 年 1 月 31 日，每个平台的定义数量如下：

例如，使用最新的 OVAL 定义文件对某台机器运行了 OVAL 扫描器，发现了以下漏洞：

1
2
3
4
5
6
7

OVAL Id    CVE Id
-------------------------
OVAL2819   CAN-2004-0427
OVAL2915   CAN-2004-0554
OVAL2961   CAN-2004-0495
OVAL3657   CVE-2002-1363
-------------------------

将 OVAL 扫描器的输出转换为 Datalog 子句，例如：

1

vulExists(webServer, 'CVE-2002-0392', httpd).

除了生成漏洞列表，OVAL 扫描器还可以按照系统特征模式（System Characteristics Schema）输出详细的机器配置信息。其中一些信息在分析多阶段攻击时非常有用。例如：

• 服务程序监听的协议和端口
• 与防火墙规则和网络拓扑结合，可确定攻击者是否能向某个易受攻击的程序发送恶意数据包

以下关于机器配置的谓词用于 MulVAL 推理引擎：

1
2
3
4
5
6

networkService(Host, Program, Protocol, Port, Priv).
clientProgram(Host, Program, Priv).
setuidProgram(Host, Program, Owner).
filePath(H, Owner, Path).
nfsExport(Server, Path, Access, Client).
nfsMountTable(Client, ClientPath, Server, ServerPath).

• networkService：描述服务程序监听的端口号、协议以及程序的用户权限
• clientProgram：描述客户端程序的权限
• setuidProgram：指定系统中的一个 setuid 可执行文件及其所有者
• filePath：描述文件系统中某路径的所有者
• nfsExport：描述 NFS 服务器向客户端导出的文件系统部分
• nfsMountTable：描述客户端机器上的 NFS 挂载表条目

MulVAL 的扫描器通过增强标准的 OVAL 扫描器实现，它不仅报告漏洞的存在，还以上述谓词的形式输出机器配置信息

ICAT（一种描述漏洞影响的数据库）

关于漏洞的详细信息可以在 OVAL 的网站上找到。例如，漏洞 OVAL2961 的描述是：

1

Linux kernel 2.4 和 2.6 中的多个未知漏洞允许本地用户提升权限或访问内核内存……

这种非正式的简短描述强调了漏洞的影响（例如如何被利用以及可能的后果）。如果存在机器可读的数据库来提供类似的信息，例如 “漏洞 2961 仅能被本地利用”，就可以正式证明一些属性，例如 “如果所有本地用户都是可信的，那么网络将免受远程攻击者的威胁”。

遗憾的是，OVAL 未以机器可读的形式呈现漏洞影响的信息。不过，ICAT 数据库 通过两个维度对漏洞的影响进行分类：

• 可利用范围（exploitable range）：

  • 本地（local）

  • 远程（remote）

• 后果（consequence）：

  • 机密性丧失（confidentiality loss）

  • 数据完整性丧失（integrity loss）

  • 服务拒绝（denial of service）

  • 权限提升（privilege escalation）

• 例如

  • 本地利用 表示攻击者需要已在主机上获得某种访问权限
  • 远程利用 则不需要这种前提条件
  • 最常见的漏洞后果是权限提升和服务拒绝

目前，所有 OVAL 定义均有对应的 ICAT 条目（通过 CVE Id 可交叉引用）。如果 OVAL 和 ICAT 能够合并为单一数据库，将能同时提供两类信息。

将 ICAT 数据库中的分类转化为 Datalog 子句，例如：

1

vulProperty('CVE-2004-00495', localExploit, privEscalation)

推理系统

MulVAL 推理系统的规则被声明为 Datalog 子句，在 Datalog 的形式主义中，一个 literal，$p(t_1,\ldots,t_k)$ 是一个谓词应用于其参数，每个参数要么是一个常量要么是一个变量（在 Datalog 中，变量是一个以大写字母开头的标识符，常量则是以小写字母开头的）

设 $L_0,\ldots,L_n$ 是 literal，MulVAL 中的一个句子被表示为一个 Horn 子句：$L_0 \coloneqq L_1, \ldots, L_n$

语义上，这意味着如果 $L_1,\ldots,L_n$ 是真的，那么 $L_0$ 也是真的，左边被称为 head，右边被称为 body，一个空 body 的子句被称为 事实，一个非空 body 的子句被称为规则

推理规则

MulVAL 推理规则指定了不同类型的漏洞利用、妥协传播和多跳网络访问的语义，其被精心设计以便将关于特定漏洞的信息分解到从 OVAL 和 ICAT 生成的数据中，交互规则描述了一般的攻击方法（例如“特洛伊木马客户端程序”），而不是特定的漏洞，因此，即使新的漏洞频繁报告，规则也不需要经常改变。

Example

论文使用 Example（示例） 还是 Case Study（案例研究），取决于作者希望传达的重点：

如果论文聚焦于 方法或理论的描述和初步验证，更适合用 example

如果论文聚焦于 实践中的实际应用和深度分析，更适合用 case study

两者也可以结合使用，例如先用 example 快速解释理论或方法，再用 case study 深入分析实际应用，增强理论的说服力和实用性

假设性分析

性能和可扩展性

源码分析

系统架构

核心文件

MulVAL 目录

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

├── bin # src目录下功能文件编译后存放该目录下
│   ├── adapter
│   └── metrics
├── doc # 说明文档
├── docker # 构建镜像
├── kb # 默认规则目录
├── lib # 库文件
├── src # 功能实现
│   ├── adapter
│   ├── analyzer
│   ├── attack_graph
│   └── metrics
├── testcases # 测试案例
│   └── 3host
└── utils # 部分调用脚本，功能脚本

技术细节

参考：MulVAL: 基于逻辑推理的攻击图生成及风险评估工具

案例分析

基本使用

1
2
3

❯ pwd
/root/Desktop/mulval/testcases/3host
❯ graph_gen.sh input.P -v -p

• graph_gen.sh 用来生成攻击图，指定了 input.P 作为输入文件，并使用了 -v 和 -p 选项

• -v：表示生成视觉化的攻击图，并输出为 PDF 格式（即 AttackGraph.pdf）

• -p：这个选项通常用于深度修剪攻击图的复杂性，使得生成的攻击图更加简洁（在生产环境中不推荐使用，因为会显著降低生成速度），它仅用于提高图形的可视化效果

1

❯ probAssess.sh

• 这个脚本用于执行基于 Wang 等人的算法的风险评估。它将生成攻击图并基于攻击图计算网络中的潜在风险
• 在脚本的最后，probAssess.sh 还会生成一个新的 VERTICES.CSV 文件，该文件包含了攻击图中的各个顶点及其度量值

脚本分析

• 输入文件 input.P

  • 输入文件 input.P 定义了 网络拓扑、服务配置、漏洞信息 等内容，这些信息会作为 MulVAL 分析的基础
  • 攻击者位置：attackerLocated(internet)，即假设攻击者位于互联网
  • 攻击目标：attackGoal(execCode(workStation,_))，即目标是执行工作站上的代码
  • 网络连接规则（hacl）：描述了不同主机之间的访问控制规则，如工作站与其他服务器的连接
  • 漏洞和服务配置：
    • 文件服务器（fileServer）：包括了 mountd 服务的漏洞信息，和与工作站及 Web 服务器的网络服务配置
    • Web 服务器（webServer）：有一个 httpd 漏洞（CAN-2002-0392），这是一个远程执行代码的漏洞
    • 工作站（workStation）：配置了 NFS 挂载信息，允许从文件服务器读取数据
  • 这些信息构成了 MulVAL 用来生成攻击图的基础，根据这些定义，MulVAL 将推理出可能的攻击路径和相应的风险

• graph_gen.sh 脚本

  • 脚本首先会检查所有必要的参数和环境变量（如 MULVALROOT 和 MULVALROOT/bin/attack_graph）

  • 然后基于输入文件创建一个 Prolog 脚本 (run.P)，通过 XSB 引擎进行推理计算

  • 该脚本的主要作用是生成攻击图并输出相关数据，主要文件有：

    • AttackGraph.txt 是攻击图的文本表示，列出了可能的攻击路径
    • AttackGraph.pdf 是攻击图的视觉化表示，通过 GraphViz 生成，帮助可视化攻击路径
    • VERTICES.CSV 包含 节点 的相关信息，文件中的每一行至少包含以下信息：
      • 节点 ID：唯一标识节点
      • 类型：每个节点都有一个类型字段，包括 "LEAF"、"AND"、"OR" 等，这决定了该节点的计算方式
      • 其他信息：文件可能还包含其他节点的描述信息，比如节点的风险度、权重等
    • ARCS.CSV 描述了节点之间的连接关系，即攻击图中的 边，文件的每一行包含以下信息：
      • 源节点（Source Node）：边的起点，表示攻击图中某个节点
      • 目标节点（Target Node）：边的终点，表示另一个节点，攻击从源节点指向目标节点

  • 通过 Graphviz 进行可视化

    • 如果启用了可视化选项，graph_gen.sh 脚本会调用 render.sh 来渲染攻击图
    • render.sh 通过根据不同选项选择适当的模板文件
    • 使用 sed 命令对 VERTICES.CSV 和 ARCS.CSV 中的节点和边数据进行格式化，将它们转换为 Graphviz 的 Dot 格式
    • 根据 AttackGraph.dot 文件，通过 Graphviz 工具（dot）生成攻击图的可视化输出

• probAssess.sh 脚本

  • 该脚本的目的是通过 MulVAL 生成的攻击图来计算风险度量，并生成包含顶点和度量信息的 CSV 文件
  • 它依赖于一个名为 independentAlgoSumm 的 Java 类来执行风险评估过程，其输入数据来源：
    • VERTICES.CSV：这个文件包含图中所有节点的基本信息，如节点的 ID 和类型
    • ARCS.CSV：这个文件定义了节点之间的连接关系，即节点的前驱和后继节点
    • config.txt：该文件包含了数据库连接信息，用于在需要时查询数据库
    • 数据库查询：constructConProb()方法中的查询逻辑通过数据库中的数据计算条件概率
  • 脚本将生成 VERTICES_METRICS.CSV 文件并重命名为 VERTICES.CSV，并调用 render.sh 来生成相应的攻击图

README

Multi host, multi stage Vulnerability Analysis tool - 多主机、多阶段漏洞分析工具

配置编译

1. 安装 XSB 逻辑引擎
2. 安装 GraphViz
3. 确保都在 PATH 路径

设置环境变量 MULVALROOT 应指向此软件包的根文件夹。在 PATH 中包含 $MULVALROOT$/bin 和 $MULVALROOT/utils。键入 make 来编译所有内容。可以直接运行 MulVAL 攻击图生成器，如果已经有了一个输入文件；或者您可以运行相应的适配器来创建输入文件，然后运行攻击图生成器。

基本使用

1

graph_gen.sh INPUT_FILE [OPTIONS]

在 testcases/3host 文件夹中有一个简单的输入文件 input.P, 这个输入文件用于 MulVAL 文献中的 3 主机示例 [1,2]，可以运行它来检查攻击图生成器是否正常工作

1

graph_gen.sh input.P -v -p

这将生成与论文中描述的攻击图匹配的图。请注意，-p 选项 不应 在生产环境中使用，因为它会指数级地减慢攻击图生成过程，而且它的唯一作用是使攻击图在视觉上更加可读（不加 -p 选项尝试上面的命令）

默认情况下，MulVAL 会输出文本格式的攻击图（AttackGraph.txt）和 XML 格式的攻击图（AttackGraph.xml），这些格式的意义是显而易见的。当使用 -v 选项时，MulVAL 会通过 GraphViz 生成攻击图的可视化版本，并输出到 AttackGraph.pdf，如果已设置了 PDF_READER 环境变量，则程序会自动打开该 PDF 文件。

当指定适当的选项时（见下文），MulVAL 还会将攻击图信息输出为 CSV 格式：VERTICES.CSV 和 ARCS.CSV。这些 CSV 文件可以由渲染程序用于后续生成攻击图的各种视图。

MulVAL 还会在程序运行的文件夹中输出一些其他临时文件，因此最好在单独的文件夹中运行，以避免混乱。

参数说明

• 图生成选项：

  • -l：以 CSV 格式输出攻击图

  • -v：以 CSV 和 PDF 格式输出攻击图

  • -p：对攻击图执行深度修剪以改善可视化效果（不要在生产环境中使用）

• 推理选项：

  • -r | --rulefile RULE_FILE：使用 RULE_FILE 作为交互规则集

  • -a | --additional ADDITIONAL_RULE_FILE：在指定的交互规则集之外，还使用 ADDITIONAL_RULE_FILE

  • -g | --goal ATTACK_GOAL：指定一个单一的攻击目标

  • --cvss：使用输入文件中包含的 CVSS 信息

  • -ma：使用输入文件中包含的 CVSS 信息，并对输入文件进行分组，使用此选项时，输入文件必须包含分组信息（参见下文）

• 渲染选项：

  • --arclabel：为攻击图的弧输出标签

  • --reverse：反向输出弧的顺序

  • --nometric：不显示度量信息

  • --simple：不显示顶点事实标签，当攻击图过大时使用此选项

  • --nopdf：不生成 PDF。当你只需要 DOT 文件而不需要 PDF 时使用此选项

在运行 graph_gen.sh 脚本后，你还可以调用 render.sh 来使用不同的渲染选项。只需在相同的目录中执行命令：

1

render.sh [RENDERING OPTIONS]

适配器使用

这部分内容的目标是通过自动化工具采集网络中的漏洞信息，转换为 MulVAL 所需要的 Datalog 格式，然后生成用于安全分析的攻击图。转换过程包括从 NVD、OVAL 和 Nessus 扫描报告中获取漏洞数据，并将其存入数据库，最终为 MulVAL 提供攻击图所需的输入。

高级用法

创建自定义规则集

开发自己的交互规则，可以创建新的规则文件，如 my_interaction_rules.P，并使用 -r 或 -a 选项加载你的规则文件，默认规则文件可以在包中的 kb/ 文件夹中找到。

规则文件的开始部分，必须声明原始和派生谓词，并对所有派生谓词进行表格化。与交互规则相关的每个谓词都必须声明为“原始”或“派生”，否则在评估时会出现“未定义谓词”的错误，生成攻击图时可能会失败，并给出警告信息，提示缺少的谓词声明。

基于 CVSS 和 MulVAL 攻击图计算风险度量

提供了一个基于 Wang 等人 [4] 提出的定量风险评估算法。它结合了 CVSS 度量和攻击图来计算企业网络的 概率风险度量，要运行度量程序，输入以下命令，其中攻击图的输出位置如下：

1

probAssess.sh

此外，还有一个脚本将多个步骤集成在一起，创建 MulVAL 攻击图、运行风险度量算法并显示带有度量的攻击图：

1

riskAssess.sh INPUT [OPTIONS]

这个脚本将始终使用 -ma 选项来生成攻击图，请使用 summ_oval.P（由 oval_translate.sh 生成）或 summ_nessus.P（由 nessus_translate.sh 生成）作为输入

参考文献

1. Xinming Ou, Wayne F. Boyer, and Miles A.McQueen. A scalable approach to attack graph generation. In 13th ACM Conference on Computer and Communications Security (CCS), 2006.
2. Xinming Ou, Sudhakar Govindavajhala, and Andrew W. Appel. MulVAL: A logic-based network security analyzer. In 14th USENIX Security Symposium, 2005.
3. Su Zhang, Xinming Ou, and John Homer. Effective network vulnerability assessment through model abstraction. In Eighth Conference on Detection of Intrusions and Malware & Vulnerability Assessment (DIMVA), Amsterdam, The Netherlands, 2011.
4. Lingyu Wang, Tania Islam, Tao Long, Anoop Singhal, and Sushil Jajodia. An attack graph-based probabilistic security metric. In Proceedings of The 22nd Annual IFIP WG 11.3 Working Conference on Data and Applications Security (DBSEC’08), 2008.

Datalog

基于 Datalog 的知识推理方法具有多种应用，特别是在知识补全和一致性检查等领域，通过 Datalog，可以从现有的知识库中推理出新的事实，或检查新知识是否与已有的知识冲突。

Prolog

Datalog 和 Prolog 都是基于一阶逻辑的编程语言，广泛应用于知识推理和人工智能领域。两者在基本构成上相似，都有 事实、规则 和 目标 的概念，但 Datalog 更专注于数据库查询和知识库推理，且其结构比 Prolog 更为简化。

• Prolog 的基本组成

  • 事实：表示已知的关系，如 妻子(姚明, 叶莉) 表示姚明的妻子是叶莉
  • 规则：表示事实之间的依赖关系，如 bird(x) :- animal(x), has(x, feather)，表示凡是动物且有羽毛，那么它是鸟
  • 目标：用于查询的目标，如 ?- student(bill) 查询 Bill 是否是学生

• Datalog 的基本组成

  • 事实、目标
  • Datalog 的 规则 形式更为简化，且不允许函数作为谓词的自变量，一般由三部分组成：
    • 规则头：关系原子（如 student(x)）
    • 蕴含符号：表示逻辑关系的符号 :-，可以读作“如果…则…”
    • 规则体：一个或多个子目标（如 P1, P2, ..., Pn），相当于逻辑“与”（AND）连接

XSB

XSB 是实现 Datalog 查询和推理的一个工具平台，它提供了基于 Datalog 的推理引擎，能够高效地处理复杂的推理任务

• XSB 是一个支持 Datalog 的逻辑编程系统，它不仅能够执行基于规则的 Datalog 查询，还对递归查询进行了优化，提供了高效的推理能力
• Datalog 是一种简单的逻辑编程语言，通常用于知识表示、推理、查询等场景
• XSB 是 Datalog 的实现平台之一，它通过扩展和优化提供了一个高效的推理引擎，适合大规模数据的处理和推理任务

XSB 对 Datalog 的关系类似于 GCC 对 C 语言，这种类比在某些方面是成立的，因为 XSB 和 GCC 都是各自语言的实现工具，提供了执行和优化功能。唯一的区别在于，GCC 是一个 编译器，负责将高级程序语言转化为机器语言，而 XSB 是一个 推理引擎，负责执行逻辑推理和查询。

推理规则

Datalog 的推理规则可以描述各种逻辑操作，如交、并、差等。以下是几种常见的 Datalog 规则类型：

• 交 (Intersection)，交操作表示两个关系的共同部分，通常通过“与”逻辑（AND）来表示。

  • 规则：Q(x1, x2, ..., xn) :- R(x1, x2, ..., xn), S(x1, x2, ..., xn)

  • 例子：智能手机(x) :- 手机(x), 智能设备(x)，表示某个物品既是手机又是智能设备时，它是智能手机

• 并 (Union)，并操作表示两个关系的合并，可以用两个规则表示。

  • 规则：Q(x1, x2, ..., xn) :- R(x1, x2, ..., xn) Q(x1, x2, ..., xn) :- S(x1, x2, ..., xn)

  • 例子：Q(x) :- R(x), S(x)，表示 Q 可以从 R 和 S 中得到

• 差 (Difference)，差操作表示从一个关系中排除另一个关系的部分，通常通过“非”操作来实现。

  • 规则：Q(x1, x2, ..., xn) :- R(x1, x2, ..., xn), NOT S(x1, x2, ..., xn)

  • 例子：弟弟(X, Y) :- 兄弟(X, Y), NOT 哥哥(X, Y)，表示 X 是 Y 的弟弟，前提是 X 和 Y 是兄弟，但 X 不是 Y 的哥哥

• 选择 (Selection)，选择操作表示对满足特定条件的实例进行筛选。

  • 规则：Q(x1, x2, ..., xn) :- R(x1, x2, ..., xn), x > 10

  • 例子：哥哥(X, Y) :- 弟弟(Y, X), 性别(Y, a), a = '男'，表示 Y 是男弟弟时，X 是其哥哥

• 投影 (Projection)，投影操作表示从一个关系中选择特定的列

  • 规则：Q(x1, x2, ..., xn) :- R(x1, x2, ..., xn)

  • 例子：memberOf(X, Y) :- member(Y, X)，表示如果 Y 是 X 的成员，则 X 是 Y 的成员

• 乘积 (Product)，乘积操作表示两个关系的笛卡尔积。

  • 规则：P(a, b, c, x, y, z) :- R(a, b, c), S(x, y, z)

  • 例子：表示 a, b, c 的关系与 x, y, z 的关系组合

• 连接 (Join)，连接操作表示基于共同字段将两个关系连接起来。

  • 规则：P(a, b, c) :- R(a, b), S(b, c)

  • 例子：岳父(X, Z) :- 妻子(X, Y), 父亲(Y, Z)，表示 X 是 Z 的岳父，前提是 X 的妻子 Y 是 Z 的父亲的女儿

推理示例

通过一个简单的推理示例来展示 Datalog 的推理过程

• 规则：岳父(X, Z) :- 妻子(X, Y), 父亲(Y, Z)
• 事实：妻子(姚明, 叶莉)、父亲(叶莉, 叶大)
• 推理过程：
  1. 根据规则 岳父(X, Z) :- 妻子(X, Y), 父亲(Y, Z)，可以推理出 岳父(姚明, Z)，条件是 妻子(姚明, 叶莉) 和 父亲(叶莉, Z) 成立
  2. 将事实 妻子(姚明, 叶莉) 和 父亲(叶莉, 叶大) 代入规则，得到 岳父(姚明, 叶大)
  3. 最终推理得出：岳父(姚明, 叶大)

CVSS

• CWE (Common Weakness Enumeration)

  • 定义：CWE 是一个列出了软件开发过程中可能出现的脆弱点的列表，它侧重于描述潜在的弱点，而不是具体的漏洞，CWE 分类并提供了脆弱点的标准定义，旨在帮助开发人员识别和解决系统中的安全弱点
  • 作用：CWE 更多聚焦于软件开发过程中的设计、编码和配置中的潜在问题（例如：缓冲区溢出、SQL 注入等），它为漏洞的根本原因提供了标准化的分类

• CVE (Common Vulnerabilities and Exposures)

  • 定义：CVE 是漏洞的公开标识系统，每个漏洞都有一个唯一的编号和描述，它是一个全球共享的漏洞标识符数据库，帮助不同的安全工具、数据库和服务统一识别漏洞
  • 作用：CVE 的目的是为每个已知的安全漏洞提供一个唯一的标识符，方便各种安全产品和服务之间的共享和沟通。例如，CVE-2021-34527 是一个常见的 Windows PrintNightmare 漏洞的唯一标识符

• CVSS (Common Vulnerability Scoring System)

  • 定义：CVSS 是一个用于量化漏洞严重性的评分系统，它通过一套标准化的指标评估漏洞的危害性（例如，攻击的可行性、影响范围等），CVSS 分数帮助用户根据漏洞的严重性来优先修复
  • 作用：CVSS 为每个 CVE 分配一个分数（通常在 0 到 10 之间），并提供一个评估方法，使得组织能够量化并优先处理最严重的漏洞。例如，一个高 CVSS 分数（如 9.0 或更高）表示漏洞的危害性较大，需要尽快修复

• **NVD (National Vulnerability Database)**：

  • 定义：NVD 是美国国家安全局（NIST）维护的一个漏洞数据库，它不仅提供 CVE 的信息，还结合了 CVSS 分数和对漏洞的风险分析，NVD 提供了详细的漏洞描述、影响分析和其他相关信息
  • 作用：NVD 提供更全面的信息，涵盖漏洞的技术细节、可能的攻击方式、漏洞的解决办法等，它通过与 CVE 标识符相结合，提供了漏洞的深入分析和评分系统，帮助用户更好地理解漏洞的风险并做出决策

• 总结来说，CWE、CVE、CVSS 和 NVD 之间的关系如下：

  • CWE 侧重于描述软件中的潜在弱点
  • CVE 提供具体漏洞的唯一标识符，并进行归档
  • CVSS 用于量化 CVE 漏洞的严重性
  • NVD 是一个综合性的漏洞数据库，整合了 CVE、CVSS 等信息，为漏洞管理提供详细分析

V2.0 指标

• 基本评分（Base Metrics）
  • AV（Access Vector，访问向量）
    • Network（网络）：攻击者通过网络进行攻击，分值为 1.0（最高可利用性）
    • Adjacent Network（邻接网络）：攻击者位于受影响系统的邻接网络中，分值为 0.646
    • Local（本地）：攻击者需要在本地访问系统，分值为 0.395
  • AC（Access Complexity，访问复杂度）
    • Low（低）：攻击容易实施，分值为 0.71（最高可利用性）
    • Medium（中）：攻击有一定复杂度，分值为 0.61
    • High（高）：攻击非常复杂，分值为 0.35
  • AU（Authentication，认证要求）
    • None（无）：无需认证即可利用，分值为 0.704（最高可利用性）
    • Single（单一）：需要一次认证，分值为 0.56
    • Multiple（多重）：需要多次认证，分值为 0.45
  • C（Confidentiality Impact，机密性影响）
    • None（无）：无机密性影响，分值为 0.0
    • Partial（部分）：部分机密性泄露，分值为 0.275
    • Complete（完全）：完全机密性泄露，分值为 0.660
  • I（Integrity Impact，完整性影响）
    • None（无）：无完整性影响，分值为 0.0
    • Partial（部分）：部分完整性破坏，分值为 0.275
    • Complete（完全）：完全完整性破坏，分值为 0.660
  • A（Availability Impact，可用性影响）
    • None（无）：无可用性影响，分值为 0.0
    • Partial（部分）：部分可用性破坏，分值为 0.275
    • Complete（完全）：完全可用性破坏，分值为 0.660
• 临时评分（Temporal Metrics）
• 环境评分（Environmental Metrics）

CVSS 3.0 或 3.1，以下是它们与 CVSS 2.0 的主要区别：

• 指标名称和分类的变化，CVSS 3.0/3.1 中，部分指标名称和分类发生变化。例如：
  • AV 变为 Attack Vector
  • AC 变为 Attack Complexity
  • AU 被替代为 Privileges Required（PR） 和 User Interaction（UI）
• 新增指标
  • CVSS 3.0/3.1 增加了 Scope（影响范围） 等指标，以更全面地评估漏洞的影响
• 分值调整
  • 各指标的分值范围和计算方式有所调整，以提高评分的准确性和一致性
• 描述和指南的改进
  • CVSS 3.1 对 CVSS 3.0 的一些定义和指南进行了澄清和修正，减少了歧义，提升了评分的一致性

V3.1 指标

CVSS (Common Vulnerability Scoring System) 是用于量化漏洞严重性的重要工具，它通过几个关键指标来评估一个漏洞的威胁程度。这些指标分为三类：基本指标（Base Metrics）、时间指标（Temporal Metrics） 和 环境指标（Environmental Metrics）。这些指标的组合形成一个漏洞的最终评分，通常在 0 到 10 之间。

• 基本指标（Base Metrics），基本指标是 CVSS 评分的核心，它描述了漏洞本身的 严重性，并且是评分的主要依据

  • 攻击向量（Attack Vector，AV），这个指标衡量攻击者需要通过什么方式才能成功利用漏洞，攻击向量越复杂，漏洞的严重性越高。取值：
    • 网络（Network）：攻击者可以通过网络直接利用漏洞
    • 邻接网络（Adjacent Network）：攻击者需要在同一物理或逻辑网络中才能利用漏洞
    • 本地（Local）：攻击者需要访问目标系统的本地环境才能利用漏洞（如物理访问、登录）
    • 物理（Physical）：攻击者需要直接物理访问设备才能利用漏洞
  • 攻击复杂度（Attack Complexity，AC），衡量利用漏洞的难度，攻击复杂度越高，漏洞的严重性越低，取值：
    • 低（Low）：攻击者只需少量的条件或低复杂度的手段。
    • 高（High）：攻击者需要特定条件或复杂的操作步骤才能成功利用漏洞。
  • 特权要求（Privileges Required，PR），描述攻击者利用漏洞时，所需的权限级别。特权要求越低，漏洞的严重性越高。取值：
    • 无（None）：攻击者不需要任何权限即可成功利用漏洞
    • 低（Low）：攻击者需要低级别权限（如普通用户权限）
    • 高（High）：攻击者需要管理员或高级权限
  • 用户交互（User Interaction，UI），衡量攻击是否需要用户的交互。没有用户交互的漏洞通常更加严重。取值：
    • 无（None）：不需要任何用户交互即可利用漏洞
    • 必需（Required）：攻击者需要诱使目标用户进行交互（如点击恶意链接）
  • 影响范围（Scope，S），衡量漏洞对系统影响的范围，是描述漏洞对其他系统或组件影响的关键指标。取值：
    • 未改变（Unchanged）：漏洞影响的仅限于受影响的组件
    • 改变（Changed）：漏洞影响整个系统，可能导致系统的全面破坏或控制。
  • 机密性影响（Confidentiality Impact，C），评估漏洞对机密性（数据泄露）的影响程度。取值：
    • 无（None）：没有泄露机密信息
    • 低（Low）：信息被部分泄露（例如泄露一些敏感数据）
    • 高（High）：信息完全泄露或数据丢失
  • 完整性影响（Integrity Impact，I），评估漏洞对系统数据完整性的影响，表示数据是否能够被篡改。取值：
    • 无（None）：数据未被篡改
    • 低（Low）：数据可能部分被篡改
    • 高（High）：数据完全可以被篡改，导致完整性损坏
  • 可用性影响（Availability Impact，A），评估漏洞对系统可用性的影响，表示系统的正常运行是否受到破坏。取值：
    • 无（None）：系统的可用性没有受到影响
    • 低（Low）：部分可用性受损，系统或服务可能会变慢或变得不稳定
    • 高（High）：系统或服务完全不可用

• 时间指标（Temporal Metrics），时间指标描述漏洞在生命周期中的变化，它基于漏洞的实际情况和时间推移所带来的影响，主要包括以下三个方面：

  • 攻击者可用性（Exploit Code Maturity，E），衡量漏洞是否已经有成熟的攻击代码公开。取值：

    • 未公布（Not Defined）：未定义
    • 未利用（Unproven）：没有已知的攻击代码或工具
    • 可利用（Proof-of-concept）：有已知的攻击代码或概念验证代码
    • 利用（Functional）：攻击代码是功能完整的，可以被黑客广泛使用
    • 成熟（High）：攻击代码已被广泛使用并且能够自动化

  • 修补状态（Remediation Level，RL），评估漏洞是否已有可用的修补措施。取值：

    • 未定义（Not Defined）：未定义

    • 解决方案（Official Fix）：发布了官方修补程序

    • 临时解决方案（Temporary Fix）：已发布临时修补程序，但并非永久修复

    • 无法修复（Workaround）：提供了可行的规避方案

    • 没有解决方案（Unavailable）：没有任何修复或解决方案

  • 报告可信度（Report Confidence，RC），衡量漏洞报告的可靠性和漏洞的确认情况。取值：

    • 未定义（Not Defined）：未定义
    • 低（Unknown）：漏洞报告的可信度不高
    • 高（Confirmed）：漏洞已被确认，且其描述与实际一致

• 环境指标（Environmental Metrics），环境指标根据漏洞对特定环境的影响来进行评分，允许用户根据实际环境对漏洞评分进行调整，考虑了组织的特定风险配置。它主要包括以下指标：

  • 安全需求（Security Requirements，CR）：
    • 根据组织的安全需求评估漏洞对机密性、完整性和可用性的影响。具体评分可能会有所不同，取决于组织的需求。
    • 取值：低、中、高。
  • 环境影响（Environmental Impact，EI）：
    • 衡量漏洞对组织特定环境的潜在影响，可能对评分有所加权。
    • 取值：低、中、高。

计算公式

可利用性子分数（Exploitability Sub Score）

$Exploitability=8.22×AV×AC×PR×UI$

影响子分数（Impact Sub Score）

$ISCBase =1-[(1- Impact_ {Con} f) \times (1- Impact_ {Integ} ) \times (1- Impact_ {Avain} )]$

$Impact_{Conf/Integ/Avail}$：机密性、完整性、可用性的影响值（High = 0.56，Low = 0.22，None = 0）

基础评分计算公式

$Base Score=Roundup(min(Impact+Exploitability,10))$

Roundup 规则：向最接近的十分位取整（如 4.02 → 4.1，4.0 → 4.0）

CVE-2024-8355：CVSS:3.1/AV:P/AC:L/PR:N/UI:N/S:U/C:H/I:H/A:H

参数分解与取值

Exploitability（可利用性）：$Exploitability=8.22×0.20×0.77×0.85×0.85=0.915$（满分 10 分中的 9.15% 权重）

Impact（影响程度）：$Impact=6.42×[1−(1−0.56)(1−0.56)(1−0.56)]=6.42×[1−0.443]≈6.42×0.915=5.88$

基础分数：$Base Score=Roundup(0.915+5.88)=Roundup(6.795)=6.8$

风险评估

• 可行性（基于 CVSS 可利用性的 贝叶斯攻击图概率计算）

  • 将 CVSS v3.1 的 $\text{Exploitability Sub Score}$（范围 0-10）归一化为概率值（0-1）

    • $P_{\mathrm{exploit}}=\frac{\text{Exploitability Score}}{10}$（可利用性转概率）

  • 构建贝叶斯攻击图

    • 叶子节点：初始漏洞（如 CVE-2024-8355），概率为 $P_{exploit}$
    • 中间节点：攻击步骤（如提权、横向移动），依赖前置节点
    • 目标节点：攻击最终目标（如控制发动机 ECU）

  • 父节点独立且状态为二值：$P_{\mathrm{AND}}=\prod \limits_{Parent}P_\text{Parent}$、$P_{\mathrm{OR}}=1-\prod \limits_{Parent}{(1-P_\text{Parent})}$

  • 叶子节点（LEAF）的初始概率

    • 数据内容：每个叶子节点（如漏洞、物理访问条件）的基础被利用概率
    • 数据来源：CVSS 评分、根据环境调整

  • 非叶子节点的逻辑关系与条件概率表（CPT）

    • 数据内容：
      • AND 节点：定义所有父节点被攻陷时，子节点成功的概率
      • OR 节点：定义任一父节点被攻陷时，子节点成功的概率

  • 逻辑规则节点的附加概率

    • 数据内容：中间规则节点（如 RULE 2、RULE 1）的执行成功率
    • 数据来源：
      • 攻击技术库（如 MITRE ATT&CK）：参考类似攻击技术的成功率
      • 历史数据：根据渗透测试或红队演练结果设定

  • 环境依赖的调整参数

    • 数据内容：网络防护措施对概率的影响权重

  • 攻击目标定义

    • 数据内容：明确最终攻击目标节点

  场景	是否需要 CPT	原因
  父节点独立且状态为二值	❌	可直接通过 AND/OR 公式计算
  父节点存在复杂依赖关系	✔️	需显式定义条件概率
  节点状态非二值	✔️	需描述多状态或连续值分布
  规则成功率动态变化	✔️	需灵活调整条件概率
  父节点数量多且组合复杂	✔️	需系统化描述所有状态组合
  使用贝叶斯网络工具	✔️	工具要求 CPT 作为标准输入格式

  • 贝叶斯攻击图通过条件概率传递，从初始漏洞节点（叶子节点）逐层推导到目标节点，最终得出攻击成功的整体概率

  • 攻击目标概率是完全基于网络结构、初始概率和逻辑规则计算得出的数值结果，只需提供：

    • 叶子节点的初始概率（CVSS + 环境调整）
    • AND/OR 节点的逻辑关系
    • 规则节点的附加概率（如 RULE 的成功率）
    • 环境调整参数（如有）
    • CPT 的具体数值会根据父节点概率和逻辑关系自动生成，但需基于上述输入参数

• 影响（基于 CVSS 影响并考虑 技术影响和业务影响）

  • 目标节点的严重性由其技术影响和业务影响决定
  • CVSS 的 $\text{Impact Sub Score}$ 已量化漏洞对系统的技术影响，可映射到目标节点的技术影响权重
    • $Impact =\frac{\text{Impact Sub Score}}{10}$
  • 根据目标节点在业务中的重要性，定义资产关键性系数 $K$
    • 关键资产（如发动机控制单元）：$K = 1.0$
    • 重要资产（如车载网关）：$K = 0.7$
    • 普通资产（如信息娱乐系统）：$K = 0.3$
  • 目标节点严重性计算公式
    • $\mathrm{Severity}_{\mathrm{target}}=K\times\left(\max_\text{Path}{\text{Impact Sub Score}}\right)\quad\text{OR}\quad\sum_\text{Path}{\text{Impact Sub Score}}$
  • 严重性传递
    • 累积效应模型
      • $\mathrm{Severity}{\mathrm{target}}=K\times\left(\sum{i=1}^n\mathrm{Impact}_i\times\alpha^{d_i}\right)$
      • $\alpha\in(0,1)$：距离衰减因子（如 0.9），表示远离目标的漏洞影响衰减，$d_i$ 漏洞节点到目标的跳数
    • 最薄弱环节模型
      • $\mathrm{Severity}_{\mathrm{target}}=K\times\max(\mathrm{Impact}_1,\mathrm{Impact}_2,…,\mathrm{Impact}_n)$

• 风险值

  • $\mathrm{Risk}=\text{Feasibility}\times\mathrm{Impact}_{\mathrm{target}}$（可利用性 × 影响）
  • $\mathrm{Risk}=\text{Probability}\times\mathrm{Severity}_{\mathrm{target}}$（概率 × 严重性）