MulVAL: A Logic-based Network Security Analyzer MulVAL: A Logic-based Network Security Analyzer

Problem & Motivation 问题与动机

Determining the security impact of software vulnerabilities on a network requires considering interactions among multiple network elements across multiple hosts, but existing tools fail to automatically integrate formal vulnerability specifications from bug-reporting communities and do not scale to networks with thousands of machines.

确定软件漏洞对网络的安全影响需要考虑跨多个主机的多个网络元素之间的相互作用，但现有工具无法自动集成来自漏洞报告社区的形式化漏洞规范，且无法扩展到拥有数千台机器的网络。

With the number of vulnerabilities discovered each year growing rapidly, system administrators cannot keep all machines free of security bugs. They need automated tools that can integrate vulnerability databases (OVAL, ICAT) with network and host configurations to reason about multihost, multistage attack paths and assess overall network security posture. Previous work in network vulnerability analysis did not address automatic integration of formal vulnerability specifications or scalability to large networks.

随着每年发现的漏洞数量迅速增长，系统管理员无法保证所有机器都免受安全漏洞的影响。他们需要自动化工具，能够将漏洞数据库（OVAL、ICAT）与网络和主机配置集成，以推理多主机、多阶段的攻击路径，并评估整体网络安全态势。以往的网络漏洞分析工作未能解决形式化漏洞规范的自动集成问题，也未能解决大型网络的扩展性问题。

Threat Model 威胁模型

The attacker is modeled as a principal originating from a part of the network where malicious users may exist (e.g., the internet). The analysis assumes the monotonicity property of network attacks: gaining privileges does not hurt an attacker's ability to launch more attacks. The attacker can exploit known vulnerabilities (from OVAL/ICAT databases) and chain exploits across multiple hosts using network connectivity defined by host access control lists (HACLs).

攻击者被建模为一个源自网络中可能存在恶意用户部分（例如互联网）的主体。分析假设了网络攻击的单调性：获得特权不会损害攻击者发起更多攻击的能力。攻击者可以利用已知漏洞（来自OVAL/ICAT数据库），并利用由主机访问控制列表（HACL）定义的网络连接性在多台主机之间串联利用程序。

Methodology 核心方法

MulVAL adopts Datalog as its modeling language to encode vulnerability information (from OVAL and ICAT), host configurations, network topology (as Host Access Control Lists), security policies, and interaction rules that capture operating system behavior and multi-hop network access. An OVAL scanner runs on each host to collect vulnerability and configuration data, which is converted to Datalog facts. The Datalog interaction rules encode general attack methodologies (remote/local exploits, compromise propagation, Trojan horse installation, NFS-based attacks) independently of specific vulnerabilities. All facts and rules are loaded into the XSB Prolog environment, which uses tabling (dynamic programming) for efficient evaluation. The analysis runs in two phases: attack simulation (deriving all possible data accesses from multistage attacks) followed by policy checking (comparing derived accesses against administrator-defined security policies).

MulVAL采用Datalog作为其建模语言，以编码漏洞信息（来自OVAL和ICAT）、主机配置、网络拓扑（作为主机访问控制列表）、安全策略以及捕捉操作系统行为和多跳网络访问的交互规则。每个主机上运行一个OVAL扫描器来收集漏洞和配置数据，并将其转换为Datalog事实。Datalog交互规则独立于具体漏洞，编码了通用的攻击方法（远程/本地利用、危害传播、木马安装、基于NFS的攻击）。所有事实和规则都加载到XSB Prolog环境中，该环境使用表格化（tabling，即动态规划）进行高效评估。分析分为两个阶段：攻击模拟（推导多阶段攻击中所有可能的数据访问）和策略检查（将推导出的访问与管理员定义的安全策略进行对比）。

Architecture 架构设计

The MulVAL framework consists of: (1) OVAL scanners running on each host that detect vulnerabilities and extract configuration information, producing Datalog tuples; (2) ICAT database integration that provides vulnerability effect classification (exploitable range and consequences) as Datalog clauses; (3) network configuration represented as Host Access Control Lists (HACLs) from firewall management tools; (4) administrator-specified principal/data bindings and security policies; (5) Datalog interaction rules encoding attack semantics; (6) the XSB Prolog reasoning engine that performs tabled evaluation of all rules and facts to detect policy violations and generate attack traces.

MulVAL框架由以下部分组成：(1) 在各主机上运行的OVAL扫描器，用于检测漏洞并提取配置信息，产生Datalog元组；(2) ICAT数据库集成，提供漏洞影响分类（可利用范围和后果）作为Datalog子句；(3) 由防火墙管理工具提供的主机访问控制列表（HACL）表示的网络配置；(4) 管理员指定的外部主体/数据绑定和安全策略；(5) 编码攻击语义的Datalog交互规则；(6) XSB Prolog推理引擎，对所有规则和事实进行表格化评估，以检测策略违规并生成攻击追踪。

Tool Integration 工具集成

Memory Mechanism 记忆机制

knowledge-graph

Attack Phases Covered 覆盖的攻击阶段

Evaluation 评估结果

The MulVAL reasoning engine can analyze networks with thousands of hosts in seconds (e.g., 200 hosts in 0.22s, 1000 hosts in 3.85s, 2000 hosts in 15.8s). The framework covers 84% of Red Hat Linux bugs reported in OVAL (those with privilege escalation or denial-of-service consequences). On a real network with hundreds of users, the tool detected a policy violation caused by a remotely exploitable libpng vulnerability enabling a multistage attack, leading administrators to patch the bug.

MulVAL推理引擎可以在几秒钟内分析拥有数千个主机的网络（例如，200个主机需0.22秒，1000个主机需3.85秒，2000个主机需15.8秒）。该框架涵盖了OVAL中报告的84%的Red Hat Linux漏洞（那些具有权限提升或拒绝服务后果的漏洞）。在一个拥有数百名用户的真实网络上，该工具检测到由远程可利用的libpng漏洞引起的策略违规，该漏洞可导致多阶段攻击，促使管理员修复了该漏洞。

Environment 评估环境

Metrics 评估指标

Baseline Comparisons 基准对比

• Model checking approaches (Ritchey and Ammann)
• Attack graph generation (Sheyner et al.)
• Topological Vulnerability Analysis (TVA, Jajodia et al.)
• Graph-based approaches (Ammann et al.)

Scale 评估规模

Real-world 3-host network with 700 users; synthetic benchmarks up to 2000 hosts; distributed scanning on 33 PlanetLab hosts across 10 countries

Contributions 核心贡献

• End-to-end framework (MulVAL) for multihost, multistage vulnerability analysis that automatically integrates formal vulnerability specifications from OVAL and ICAT into a Datalog-based reasoning engine
• Adoption of Datalog as a unified modeling language that cleanly separates vulnerability data, configuration information, interaction rules, and security policies, enabling straightforward integration of off-the-shelf tools
• Scalable reasoning engine using XSB Prolog with tabling that achieves polynomial-time analysis and handles networks with thousands of hosts in seconds
• Hypothetical vulnerability analysis capability that can reason about the security impact of undiscovered future vulnerabilities (what-if analysis)
• Demonstrated practical deployment on a real network where the tool discovered an actual policy violation leading to remediation
• Attack trace generation that produces detailed, human-readable derivation trees showing the chain of exploits leading to policy violations

• 开发了一个用于多主机、多阶段漏洞分析的端到端框架（MulVAL），该框架可自动将来自OVAL和ICAT的形式化漏洞规范集成到基于Datalog的推理引擎中
• 采用Datalog作为统一建模语言，清晰地分离了漏洞数据、配置信息、交互规则和安全策略，实现了与现成工具的简单集成
• 使用带有表格化技术的XSB Prolog实现了可扩展的推理引擎，达到了多项式时间分析复杂度，并能在几秒钟内处理拥有数千个主机的网络
• 具备假设性漏洞分析能力，可以推理尚未发现的未来漏洞的安全影响（“如果……会怎样”分析）
• 展示了在真实网络上的实际部署，工具发现了实际的策略违规并促成了修复
• 实现了攻击追踪生成功能，可产生详细的、人类可读的推导树，展示导致策略违规的漏洞利用链

Limitations 局限性

• Cannot reason about confidentiality loss or integrity loss vulnerabilities; only handles privilege escalation and denial-of-service (covering 84% of OVAL-reported bugs)
• ICAT database lacks precise information about what confidential information may be leaked or what information may be modified, limiting the types of exploit consequences that can be modeled
• Requires manual specification of principal bindings, data bindings, and security policies by the system administrator
• The OVAL scanner is overloaded with both configuration collection and vulnerability detection; ideally these should be separated so new advisories can be checked against pre-collected configuration data
• Does not model unmanaged hosts or hosts with non-malicious but untrusted users in the same framework
• Network configuration (HACL) may not capture dynamic environments with DHCP, wireless networks, or complex firewall rule interactions
• Currently only supports Red Hat Linux, Windows, and Solaris platforms for OVAL scanning

• 无法推理机密性丢失或完整性丢失的漏洞；仅处理权限提升和拒绝服务（涵盖OVAL报告漏洞的84%）
• ICAT数据库缺乏关于哪些机密信息可能泄露或哪些信息可能被修改的精确信息，限制了可建模的漏洞利用后果类型
• 需要系统管理员手动指定主体绑定、数据绑定和安全策略
• OVAL扫描器同时承担配置收集和漏洞检测任务，负担过重；理想情况下这两者应分离，以便根据预先收集的配置数据检查新的安全公告
• 未在同一框架内建模非受控主机，或在同一网络中存在非恶意但不可信用户的主机
• 网络配置（HACL）可能无法捕捉具有DHCP、无线网络或复杂防火墙规则交互的动态环境
• 目前仅支持Red Hat Linux、Windows和Solaris平台的OVAL扫描

Research Gaps 研究空白

• Need for a unified vulnerability database that combines OVAL recognition specifications with ICAT effect classifications in a single machine-readable format
• Formal characterization of when groups of identical hosts can be collapsed into equivalence classes for analysis, reducing network size from thousands to dozens of host types
• Modeling normal software behavior (e.g., sudo, setuid programs) requires extending interaction rules for each new program, calling for a systematic approach
• Integration of fine-grained single-host vulnerability models (e.g., Ramakrishnan and Sekar, Fithen et al.) as interaction rules in the network-level framework
• Handling dynamic network environments where firewall rules change based on DHCP, authentication state, or wireless connectivity

• 需要一个统一的漏洞数据库，将OVAL识别规范与ICAT影响分类组合成单一的机器可读格式
• 对何时可以将一组相同的主机折叠为等价类进行分析进行形式化表征，从而将分析的网络规模从数千个主机减少到几十种主机类型
• 建模正常的软件行为（例如sudo、setuid程序）需要为每个新程序扩展交互规则，这需要一种系统化的方法
• 将细粒度的单主机漏洞模型（例如Ramakrishnan和Sekar，Fithen等人的工作）作为交互规则集成到网络级框架中
• 处理基于DHCP、身份验证状态或无线连接而改变防火墙规则的动态网络环境

Novel Techniques 新颖技术

• Using Datalog as a unified modeling language for network vulnerability analysis that cleanly factors vulnerability data from interaction rules, enabling automatic integration of vulnerability databases
• Two-phase analysis algorithm separating attack simulation (Datalog evaluation) from policy checking (Prolog with negation), allowing richer policy languages without affecting attack simulation complexity
• Hypothetical vulnerability analysis using Prolog backtracking to systematically inject pairs of hypothetical bugs and check security impact
• Monotonicity assumption for network attacks enabling efficient Datalog-based reasoning (facts are accumulated, never retracted) instead of exponential state-space model checking
• Attack trace generation via meta-interpreter that produces human-readable derivation trees

• 使用Datalog作为网络漏洞分析的统一建模语言，将漏洞数据从交互规则中清晰分离，实现了漏洞数据库的自动集成
• 采用两阶段分析算法，将攻击模拟（Datalog评估）与策略检查（带否定的Prolog）分离，允许更丰富的策略语言而不影响攻击模拟的复杂性
• 使用Prolog回溯机制进行假设性漏洞分析，系统性地注入成对的假设漏洞并检查安全影响
• 对网络攻击采用单调性假设，实现了高效的基于Datalog的推理（事实是累积的，永不撤销），而非指数级状态空间的模型检测
• 通过元解释器生成攻击追踪，产生人类可读的推导树

Open Questions 开放问题

• How can the Datalog-based reasoning approach be extended to handle vulnerabilities with complex, context-dependent effects beyond privilege escalation?
• Can the interaction rules be automatically learned or generated (e.g., by LLMs) rather than manually written?
• How should the framework handle networks with a mix of managed and unmanaged hosts, or networks where trust boundaries are unclear?
• What is the optimal granularity for modeling host configurations -- when is the network-level abstraction insufficient and single-host detailed models are needed?

• 如何扩展基于Datalog的推理方法，以处理权限提升之外的具有复杂、上下文相关影响的漏洞？
• 交互规则能否自动学习或生成（例如通过LLM），而不是手动编写？
• 框架应如何处理受控与非受控主机混合的网络，或信任边界不清晰的网络？
• 建模主机配置的最佳粒度是什么——何时网络级抽象不足，需要单主机详细模型？

Builds On 基于前人工作

• OVAL (Open Vulnerability Assessment Language)
• ICAT vulnerability database (NIST)
• XSB Prolog system
• Ritchey and Ammann - model checking for network vulnerability analysis
• Sheyner et al. - automated attack graph generation
• Ammann et al. - graph-based network vulnerability analysis
• Topological Vulnerability Analysis (TVA) by Jajodia, Noel, and O'Berry

Open Source 开源信息

No

Tags