Incremental verification of attack paths for progressively evolving penetration testing scenarios.
IncPath is a Datalog-based incremental computation framework that verifies how attack paths evolve across iterative scenario changes, avoiding costly full attack-graph rebuilds. It uses provenance-semiring tracking to retract invalidated facts precisely and a semi-naive incremental fixed-point to derive new facts, then labels each evolution step with one of four biologically inspired patterns: stable inheritance, acquired mutation, substitutive mutation, or degeneration.
This repository contains the IncPath core library and a self-contained demo. The full experimental harness (1,720 evolution steps, MulVAL comparison data, paper figures) lives in a separate archive; contact the authors for access.
- Two orders of magnitude faster than MulVAL full rebuild on the paper's 1,720-step experiment (raw median ≈ 499×, effective median ≈ 91× after subtracting MulVAL's XSB startup cost).
- Provably correct: 100 % path-level agreement with MulVAL ground truth across all 1,720 steps in the paper.
- Zero third-party dependencies for the core library. Pure Python 3.8+, standard library only.
- Optional MulVAL integration for head-to-head reproduction; the demo runs in two modes (see below).
git clone https://github.com/Xing0710/incpath.git
cd incpath
python3 demo/run_demo.pyThe demo loads three representative bundles (10, 50, and 100 hosts), replays their evolution sequences through IncPath, and verifies that the output exactly matches the bundles' ground-truth path sequences and evolution-mode labels. Total runtime is 1–2 minutes on a commodity laptop. Expected output:
================================================================
IncPath Demo
Mode A: IncPath vs bundle ground truth (always)
Mode B: disabled (pass --with-mulval to enable)
================================================================
[Bundle: scale10_seed12] scale=10, steps=8
----------------------------------------------------------------
initial: 3 paths, load= 7.8 ms vs bundle (3) [PASS]
step 1/8 mode=stable paths= 3 t_inc= 2.8 ms [PASS]
step 2/8 mode=acquisitive paths= 5 t_inc= 2.5 ms [PASS]
step 3/8 mode=substitutive paths= 5 t_inc= 5.8 ms [PASS]
step 4/8 mode=degradation paths= 4 t_inc= 1.5 ms [PASS]
step 5/8 mode=stable paths= 4 t_inc= 2.0 ms [PASS]
step 6/8 mode=acquisitive paths= 5 t_inc= 5.2 ms [PASS]
step 7/8 mode=substitutive paths= 5 t_inc= 5.5 ms [PASS]
step 8/8 mode=degradation paths= 4 t_inc= 1.1 ms [PASS]
----------------------------------------------------------------
summary: initial PASS, steps 8/8 PASS, final PASS
per-step apply time: median 2.8 ms, sum 0.027 s
... (scale50_seed18 and scale100_seed24 follow) ...
================================================================
MODE A SUMMARY
================================================================
bundles run: 3
bundles fully passing: 3/3
steps passing: 24/24 (100.0%)
If you have MulVAL installed and want to reproduce the speedup numbers locally:
export MULVALROOT=/path/to/mulval # adjust to your install
python3 demo/run_demo.py --with-mulvalThis additionally invokes MulVAL's graph_gen.sh on every step of every bundle and reports per-step raw and effective speedups. Total runtime ~5 minutes; expect speedups in the same order of magnitude as the paper, though absolute numbers depend on your machine.
See demo/README.md for installation prerequisites, troubleshooting, and details on what each mode verifies.
incpath/
├── incpath/ Core library (zero third-party deps)
│ ├── __init__.py
│ ├── engine.py Datalog inference engine + semi-naive increment + provenance retraction
│ ├── evolution.py Four-pattern evolution labeling
│ ├── incpath.py IncPath orchestrator (load_scenario, apply_change)
│ ├── paths.py Attack-path extraction
│ ├── rules.py Default MulVAL-equivalent rule set
│ ├── scenario.py Scenario / ChangeSet data classes
│ └── terms.py Term unification primitives
├── demo/
│ ├── README.md
│ ├── run_demo.py Single-command entry point (Mode A / Mode B)
│ ├── _bundle_loader.py
│ ├── _mulval_runner.py (only imported when --with-mulval)
│ └── bundles/ Three representative bundles (scales 10, 50, 100)
├── README.md
├── LICENSE Apache License 2.0
├── CITATION.cff
├── requirements.txt
└── .gitignore
The demo bundles are a representative subset chosen to fit within a few minutes of local runtime. The full experimental dataset used in the paper consists of 1,720 evolution steps across 80 main-experiment bundles and 500 RQ3 bundles, together with paired MulVAL runs that produced figures 1, 2, 4, 5, and 6.
Due to size (≈ 1 GB total) and to keep this repository focused on the IncPath library itself, the full dataset, the MulVAL output traces, the CSV result tables, and the figure-rendering scripts are not included here. Please contact the authors for access to the experiment archive.
If you use IncPath in your research, please cite the paper:
[Author et al.], "IncPath: Incremental verification of attack paths for progressively evolving penetration testing scenarios," [Venue], 2026.
For software citation, refer to this repository directly:
A machine-readable CITATION.cff is provided in the repository root.
Apache License 2.0. See LICENSE for the full text.
For questions about the paper, the demo, or access to the full experiment archive, please open an issue on this repository.