Mihir4U-avi/GraphGulo

# GraphGulo [](https://www.python.org/downloads/) [](https://www.rust-lang.org/) GraphGulo 是一个研究原型，它将原始的 PCAP 捕获数据和网络流日志转换为带索引的时序图，然后在普通商用硬件上以亚秒级到低秒级的延迟响应时间相关的遍历查询。该引擎由 Python 编写，其核心使用 Rust 编写并通过 PyO3 编译，目前已在一个 14 GB 的 PCAP 文件上进行了验证，生成了跨越 **2130 万个节点**的 **1.096 亿条边**。 ## 动机 标准的图处理库并非为时序网络遥测数据而设计： | 库 | 局限性 | |---|---| | NetworkX | Python 的每条边对应一个对象的模型；超过约 3000 万条边时会发生 OOM | | igraph | 没有原生的时序语义；仅支持静态邻接 | | Neo4j / JanusGraph | 时序查询需要外挂的 Cypher 变通方案；存在 JVM 开销 | | Spark GraphX | 需要集群环境；每次查询延迟在分钟级 | 它们都无法回答威胁猎人实际提出的问题： GraphGulo 将此作为原生的首要查询方式。 ## 特性 - **原生时序遍历** — 每次 BFS 和 Dijkstra 遍历都强制执行时间先后约束：只有当 `t ≥ arrival_time(u)` 时，边 `(u → v, t)` 才会被遍历。 - **自适应 5 层内存** — 节点根据度和访问频率进行分类，并自动路由到内存效率最高的结构中。 - **通过 PyO3 实现的 Rust 核心** — BFS、Dijkstra、并行排序和窗口查询在原生 Rust 中执行，采用零拷贝 NumPy FFI。 - **双通道摄入** — 接受原始 PCAP 文件（通过 Rust 解析器）和 CSV/流日志（通过 PyArrow），并具备自动列检测功能。 - **LRU 查询缓存** — 在活跃子图上重复进行的遍历可避免重新遍历的开销。 ## 架构 ``` ┌──────────────────────────────────────────────────────────────────┐ │ Python Layer │ │ Ingestion · Tier Router · LRU Cache · Benchmarks · Scripts │ ├──────────────────────────────────────────────────────────────────┤ │ Rust Core (PyO3 FFI) │ │ Parallel Sort · Temporal BFS · Temporal Dijkstra │ │ Window Query · PCAP Parser │ ├──────────────────────────────────────────────────────────────────┤ │ Adaptive 5-Tier Storage │ │ │ │ Hot (degree > 10k) → Scipy CSR matrix │ │ Warm (degree 100–10k) → Roaring Bitmap │ │ Cool (degree < 100, → Contiguous NumPy block │ │ frequently hit) │ │ Cold-Low (rare) → Parquet + LZ4 (disk) │ │ Cold-High (never) → Parquet + Brotli (disk) │ └──────────────────────────────────────────────────────────────────┘ ``` ### 摄入流水线 ``` PCAP / CSV │ ▼ Rust PCAP Parser ──or── PyArrow CSV Reader │ ▼ IP → Integer Node Mapping │ ▼ Parallel Sort by (src, timestamp) ← Rust / Rayon │ ▼ node_ptr index (CSR-style offset array) │ ├──▶ Hot Tier (Scipy CSR) ├──▶ Warm Tier (Roaring Bitmap) ├──▶ Cool Tier (NumPy) └──▶ Cold Tier (Parquet, disk) │ ▼ Temporal Query Engine BFS · Dijkstra · Window ``` ## 基准测试 所有数据均为来自 `results/benchmarks/phase5_benchmarks_20260728_211050.json` 的真实测量结果。 硬件：Intel Core i7（12 线程，消费级 CPU），Windows 11，NVMe SSD。 数据集：MAWI PCAP 2024-04-10（`202404101400.pcap`，14 GB）。 ### 数据集 | 属性 | 数值 | |---|---| | 边数 | 109,649,651 | | 节点数 | 21,285,798 | | 平均度 | 5.15 | | 时间跨度 | ~900 秒（15 分钟捕获） | ### 存储分层（构建后） | 层级 | 节点数 | 结构 | |---|---|---| | Hot | 1,184 | Scipy CSR | | Warm | 24,206 | Roaring Bitmap | | Cool | 1,908,735 | Sorted NumPy | | Cold-Low | 剩余部分 | Parquet + LZ4 (磁盘) | | Cold-High | 剩余部分 | Parquet + Brotli (磁盘) | ### 性能表现 | 指标 | 结果 | |---|---| | **图构建时间** (PCAP → 索引引擎) | ~100 秒 | | **内存中的边数组 (RAM)** | 1,315 MB | | **node_ptr 索引** | 170 MB | | **数组总占用** | ~1.49 GB | | **时序 BFS** (15 分钟窗口，到达 1830 万个节点) | 3,956 ms | | **时序 Dijkstra** (源节点 → 目标节点，16 跳路径) | 1,453 ms | | **窗口查询 P50** (15 分钟切片，~11.5 万条边) | ~15 ms | ## 算法 ### 时序 BFS 标准 BFS 忽略了时间。GraphGulo 的 BFS 使用按到达时间排序的最小堆： ``` heap = [(t_start, source)] while heap: t_arrive, node = heappop(heap) if node in visited: continue visited[node] = t_arrive # Binary search within this node's sorted edge block for each neighbor v, edge_time t where t_arrive ≤ t ≤ t_end: push (t, v) ``` `node_ptr` 索引使得每个节点的二分查找复杂度为 O(log degree)。Rust 实现 (PyO3) 会根据时间戳的数据类型分派到 `temporal_bfs_rust_u16/u32/u64`，从而实现零开销 FFI。 ### 时序 Dijkstra 查找从源节点到目标节点的**最早到达路径**。成本 = 到达每个节点的到达时间。完全由 Rust 实现，使用 `BinaryHeap` (最小堆) 和 `best_arrival: HashMap` 来修剪密集多重图中的冗余数据包，防止内存爆炸。 ### 窗口查询 使用 Rust 跨所有 `node_ptr` 块的并行扫描，返回在 `[t_start, t_end]` 范围内处于活跃状态的所有边。借助 Rayon 并行性，复杂度为 O(V + E_window)。在拥有 1.09 亿条边的图上执行 15 分钟窗口查询的 P50 延迟为：~15 ms。 ## 分层存储设计 自适应分层路由器在构建时对每个节点进行分类： ``` if degree > 10_000: # Hot — massive hubs store as Scipy CSR elif degree >= 100: # Warm — high connectivity store as Roaring Bitmap elif access_count > rarely: # Cool — regular nodes store as sorted NumPy array elif access_count > never: # Cold-Low — rarely touched write to Parquet + LZ4 else: # Cold-High — archival write to Parquet + Brotli ``` 分层分配通过 NumPy 进行向量化处理 (`degrees = node_ptr[1:] - node_ptr[:-1]`) — 无需 Python 循环。对于 2100 万个节点，构建过程在 ~3 秒内完成。 ## 仓库结构 ``` GraphGulo/ ├── graphgulo/ │ ├── algorithms/ │ │ ├── temporal_bfs.py # BFS variants (Phase 1 & 3) │ │ ├── temporal_dijkstra.py # Dijkstra (Python + Rust dispatch) │ │ ├── bidirectional_bfs.py # Bidirectional BFS │ │ └── tier_router.py # Per-node tier dispatch │ ├── ingestion/ │ │ ├── csv_ingest.py # PyArrow CSV reader │ │ ├── pcap_ingest.py # PCAP ingestion via Rust │ │ └── timestamp_parser.py # Timestamp normalization │ ├── storage/ │ │ ├── csr_builder.py # Sorted edge array + node_ptr construction │ │ └── tier_builder.py # Adaptive 5-tier builder │ ├── cache/ │ │ └── lru_cache.py # LRU traversal cache │ └── common/ # Memory, timer, node ID utilities ├── rust/ │ ├── graphgulo_core/ # PyO3 extension: BFS, Dijkstra, window query │ └── pcap_parser/ # Rust binary PCAP parser ├── scripts/ │ ├── run_pipeline.py # Main entrypoint (PCAP or CSV) │ ├── verify_consistency.py # Graph consistency checker │ └── demo_security_scenarios.py # 5 threat hunting demos ├── tests/ │ └── test_v1_edge_cases.py # Edge cases: empty graphs, self-loops, disconnected ├── results/ │ └── benchmarks/ # Raw JSON benchmark outputs ├── config/ # YAML configuration ├── requirements.txt ├── pyproject.toml └── LICENSE ``` ## 快速开始 ### 前置条件 - Python 3.14+ - Rust 1.75+ （用于 `graphgulo_core` PyO3 扩展） ### 安装 ``` # Clone git clone https://github.com/Mihir4U-avi/GraphGulo.git cd GraphGulo # 创建虚拟环境 python -m venv .venv .venv\Scripts\activate # Windows # source .venv/bin/activate # Linux / macOS pip install -r requirements.txt # 编译 Rust 核心 cd rust/graphgulo_core maturin develop --release cd ../.. ``` ### 运行 ``` # Inest 一个 PCAP 文件并运行所有 benchmark python scripts/run_pipeline.py --file datasets/pcap/capture.pcap # Ingest 一个 CSV flow log python scripts/run_pipeline.py --file datasets/csv/traffic.csv # 如果已构建 .parquet 则跳过 Phase 1 ingestion python scripts/run_pipeline.py --file datasets/csv/traffic.csv --phase 2 # 运行安全调查 demo python scripts/demo_security_scenarios.py ``` ### 示例输出 ``` BUILDING ADAPTIVE TIERS ... Build time : 3.21 sec Hot : 1,184 nodes (Scipy CSR) Warm : 24,206 nodes (Roaring Bitmap) Cool : 1,908,735 nodes (Sorted NumPy) Cold : disk (Parquet LZ4 / Brotli) [BFS] nodes_reached=18,309,253 latency=3,956 ms algorithm=TemporalBFSRust [Dijk] path_hops=16 latency=1,453 ms algorithm=TemporalDijkstraRust [Win] edges=118,469 latency=13.3 ms window=15-min ``` ## 安全调查场景 ``` python scripts/demo_security_scenarios.py ``` | # | 场景 | 方法 | |---|---|---| | 1 | 端口扫描检测 | 时间窗口内的出度激增 | | 2 | 横向移动 | 时序 Dijkstra 最短路径 | | 3 | 数据窃取 | 边权重聚合 (字节数) | | 4 | C2 信标检测 | 高入站时序中心性 | | 5 | 攻击时间线 | 分窗口时序重构 | ## 后续工作 该原型确立了一个可行的基础。我们为未来的开发确定了以下方向： ### 性能 - **并行图构建** — 通过 Rayon 将边排序和分层构建分配到多个 CPU 核心上执行；预计可将构建速度提升 4–8 倍 - **采用 SIMD 解码的压缩 CSR** — 对邻居列表进行增量编码；通过 AVX2/AVX512 向量化弥补解码开销（减少约 30–50% 的 RAM 占用） - **增量时间戳压缩** — 存储边之间的时间增量，而不是绝对的 epoch 值（可将时间戳数组大小减少约 30–70%） - **持久化图缓存** — 构建完成后将完全索引的图序列化到磁盘；在随后的冷启动中跳过约 100 秒的构建过程 ### 正确性与完整性 - **增量边插入** — 无需完全重新构建即可追加新边；这是对实时流量进行运营使用的必要条件 - **Cold 层 Rust 遍历** — 扩展 Rust BFS 路径，使其能够透明地解压并遍历 cold Parquet 节点 ### 规模化 - **GPU 遍历后端** — 将 BFS 前沿扩展移植到 CUDA，适用于度分布有利于大规模并行处理的图 - **分布式执行** — 针对超出单机内存容量的数据集，将图划分到多个节点上处理 ### 研究扩展 - **时序 PageRank** — 根据时序影响力而非静态连通性对节点进行排名 - **时序介数中心性** — 在按时间排序的攻击链中识别关键的继电器节点 - **流式 PCAP 摄入** — 实时摄入 Zeek/Suricata 日志，而无需暂停正在进行的遍历 ## 局限性 (V1 原型) - **构建后不可变** — 图无法增量更新；新增边需要重新摄入。 - **单进程** — 不支持分布式执行；仅限单机运行。 - **无 GPU 后端** — 所有计算均受限于 CPU。 - **BFS 期间不遍历 Cold 层** — Rust BFS 完全在内存中的排序数组上运行；cold Parquet 节点可通过 Python 分层路由器访问，但无法通过快速的 Rust 路径访问。 - **已在 Windows NVMe 上测试** — Linux 性能可能有所不同；尚未在 ARM 架构上进行基准测试。 ## 依赖项 | 库 | 用途 | |---|---| | [PyO3](https://pyo3.rs/) | Rust ↔ Python FFI | | [Rayon](https://github.com/rayon-rs/rayon) | Rust 中的数据并行 | | [PyArrow](https://arrow.apache.org/docs/python/) | 零拷贝列式摄入 | | [Roaring Bitmaps](https://roaringbitmap.org/) | 压缩的邻居集合 | | [SciPy](https://scipy.org/) | CSR 稀疏矩阵 (hot 层) | | [NumPy](https://numpy.org/) | 连续数组存储 | | [psutil](https://psutil.readthedocs.io/) | RSS 内存测量 |

标签：PyO3, Rust, 可视化界面, 图计算引擎, 时序图, 网络安全, 网络流量审计, 逆向工具, 防御绕过, 隐私保护