FlowLog: Re-thinking Datalog for Fast and Extensible Static Analysis

Source: arXiv:2607.23971 · Published 2026-07-27 · By Zhenghong Yu, Hangdong Zhao, Wanzhu Hou, Paraschos Koutris

TL;DR

FlowLog addresses the well-known tradeoff in Datalog-based static analysis engines between efficiency and extensibility. Current engines excel either at runtime performance or at supporting incremental maintenance and extensions, but rarely both. FlowLog innovates by compiling Soufflé-style Datalog programs into executable dataflows based on Differential Dataflow (DD), combined with a novel relational intermediate representation (IR). This IR separates recursive control flow from logical query plans and enables multiple powerful rewrites and optimizations.

Evaluated on 24 real-world benchmarks including DOOP points-to and Polonius borrow-checking analyses, FlowLog outperforms state-of-the-art engines (Soufflé, DDlog, Ascent) by significant margins in runtime—median speedup of 3.9–5.9× vs Soufflé and 13–22× vs DDlog—while using comparable or less memory. The system scales more effectively using DD’s asynchronous parallel runtime. Moreover, FlowLog’s design supports extensible workflows: incremental maintenance yields a 320× speedup for a fact retraction compared to full recomputation, and a built-in profiler lets users diagnose and tune expensive join orders. Extensions beyond standard Datalog, such as non-monotonic iterative rules, are also demonstrated with a k-core computation example.

Overall, FlowLog introduces a compelling approach that unifies efficient one-shot evaluation, incremental updates, and extensibility in Datalog-based static analysis, balancing high throughput, memory efficiency, and user-friendly tooling.

Key findings

• FlowLog shows a median runtime speedup of 3.9× over Soufflé (range 1.5–4.3×), 22× over DDlog (16–27×), and 14× over Ascent (4.4–41×) on DOOP points-to benchmarks (Fig. 3 top right).
• On Polonius borrow-check benchmarks, FlowLog runs 5.9× faster than Soufflé (range 5.1–7.0×), 13× faster than DDlog (9.5–35×), and 3.3× faster than Ascent (2.9–5.3×) (Fig. 3 top left).
• FlowLog uses about 6.3× less peak memory than DDlog across workloads, due to subplan sharing that reduces redundant intermediate state materialization (Fig. 3 bottom).
• Compared to Soufflé, FlowLog uses roughly 1.3–2.8× more memory on DOOP and about 1.1× on Polonius, trading some memory for incremental maintenance readiness.
• Incremental retraction of one LoadInstanceField fact in DOOP takes approximately 7ms in FlowLog, compared to 2.23s for full recomputation—about 320× faster (Section 4.1).
• FlowLog scales better with parallelism than competitors, achieving up to 15× speedup on Polonius with 32 threads, while others barely improve beyond single-threaded performance (Fig. 4).
• FlowLog’s profiler enables visualization and identification of costly join orders; fixing a deliberately bad join order improved runtime from 6.5s to 2.2s on tomcat (Section 4.2).
• The extended semantics feature supports non-monotonic iterative computations (e.g., k-core decomposition), which standard Datalog cannot express (Section 4.3).

Threat model

n/a — This work focuses on improving Datalog-based static analysis runtime and extensibility, not on defending against an adversary or security threat actors.

Methodology — deep read

1. Threat model and assumptions: The paper targets static analysis workloads run by developers or researchers with full access to source Datalog programs and input facts. The “adversary” is essentially performance overheads and lack of extensibility, not a malicious attacker.

2. Data: The evaluation uses 24 real-world static analysis workloads derived mainly from DOOP (Java points-to analysis) running on DaCapo Java benchmarks (e.g., tomcat, eclipse) and Polonius (Rust borrow checker) on real Rust crates (e.g., clap-rs). The benchmarks are standard open-source programs commonly used for evaluation.

3. Architecture / algorithm: FlowLog accepts input programs in Soufflé-style Datalog, with extensions such as recursive aggregation and richer types. The compiler stratifies rules and lowers them into a custom relational intermediate representation (IR), which decomposes rules into a tree of operators like SemiJoin and Join, connected by tuple schemas. The IR allows pushing down projections and filters, sideways semijoin reductions (Yannakakis-style), and subplan sharing to optimize join orders and minimize intermediate state. The IR is compiled into Differential Dataflow operators in Rust, supporting recursive fixpoint computations and incremental updates efficiently.

4. Training / execution regime: Not applicable (static analysis tool). The FlowLog executable is run in either one-shot mode or incremental mode with logical timestamps. Incremental updates can retract or add facts interactively. For benchmarking, programs were run on a CloudLab VM with AMD EPYC 7543 processors (32 cores per socket, hyper-threading enabled) and 256GB RAM. Runs used 32 threads for parallelism.

5. Evaluation protocol: Metrics reported include total runtime to fixpoint, peak RAM usage, and scalability speedup up to 32 threads. Results exclude compilation time to isolate runtime performance. Baselines include Soufflé (state-of-the-art compiled Datalog), DDlog (compiles to same DD backend but without FlowLog IR optimizations), and Ascent (Rust macro-embedded Datalog). Output cardinalities were verified to be identical across engines. Scalability was measured by speedups relative to single-threaded runs on two representative program-data pairs.

6. Reproducibility: FlowLog is open source at https://github.com/flowlog-rs/flowlog, with tutorials, benchmarks, and a profiler visualizer. Benchmarking scripts and engine versions are publicly archived, supporting full reproduction of the results. The dataset consists of public benchmarks like DaCapo and Rust crates.

Example walk-through: The DOOP points-to analysis is parsed into FlowLog’s IR with explicit SemiJoin and Join operators (Fig. 2). The compiler applies Datalog-aware pushdown and semijoin reduction to reduce intermediate sizes. FlowLog generates Rust code invoking Differential Dataflow operators that run fixpoint iteration asynchronously and in parallel. Profiling instrumentation records per-operator costs, enabling users to diagnose a deliberately bad join order that slows execution. Incremental mode lets users retract a fact (e.g., a LoadInstanceField tuple) interactively; FlowLog recomputes only affected derived facts in milliseconds, greatly reducing update latency compared to full re-execution.

Technical innovations

• Introduction of a relational intermediate representation (IR) that separates recursive control flow from rule logical plans, enabling targeted optimizations and extensibility beyond standard Datalog engines.
• Integration of Datalog-aware rewrite optimizations like pushdown projections and filters, sideways semijoin reduction (Yannakakis-style), and subplan sharing to reduce intermediate state size and improve runtime performance.
• Compilation of Soufflé-style Datalog programs into Differential Dataflow executables supporting both efficient one-shot fixpoint evaluation and incremental maintenance with low latency.
• Built-in profiler and visualization tools tightly integrated with the IR that expose per-operator runtime and memory costs, allowing users to diagnose and tune execution bottlenecks without invasive engine changes.
• Extensions to support controlled non-monotonic and iterative semantics (e.g., k-core computation) within the same dataflow pipeline, going beyond classical monotonic Datalog capabilities.

Datasets

• DOOP-based Java points-to analysis — 24 benchmarks from DaCapo suite (e.g., tomcat, eclipse) — public
• Polonius Rust borrow checker workloads — 24 benchmarks from Rust crates (e.g., wgpu, clap-rs) — public

Baselines vs proposed

• Soufflé: runtime median = baseline; FlowLog: 3.9× faster on DOOP, 5.9× faster on Polonius
• DDlog: runtime median = baseline; FlowLog: 22× faster on DOOP, 13× faster on Polonius
• Ascent: runtime median = baseline; FlowLog: 14× faster on DOOP, 3.3× faster on Polonius
• DDlog: peak memory median = baseline; FlowLog uses 6.3× less memory median
• Soufflé: peak memory median = baseline; FlowLog uses 1.3–2.8× more memory on DOOP, ~1.1× on Polonius

Figures from the paper

Figures are reproduced from the source paper for academic discussion. Original copyright: the paper authors. See arXiv:2607.23971.

Fig 1: FlowLog architecture.

Fig 5: FlowLog profiler views for the target rule under the

Limitations

• Evaluation primarily focuses on static program analyses; generalizability to other Datalog workloads or non-program-analysis domains is not shown.
• The scalability experiments are limited to commodity server hardware with up to 32 threads; distributed or cloud-scale performance is not evaluated.
• While incremental maintenance is demonstrated, no adversarial or heavily dynamic update workloads are benchmarked to stress test real-time responsiveness.
• Extended semantics beyond standard Datalog are illustrated only through a single k-core example; broader support and automation of complex non-monotonic semantics are not fully explored.
• Memory comparisons versus Soufflé show some increase due to materializing all indexes; trade-offs between memory use and responsiveness could be workload-dependent.

Open questions / follow-ons

• How well do FlowLog’s incremental maintenance and profiling features perform under highly dynamic, adversarial update patterns, e.g., in live continuous analysis?
• Can the relational IR and optimization framework be extended to support richer Datalog extensions like probabilistic logic or temporal logic?
• How does FlowLog compare against other newer Datalog engines in distributed or cloud environments with multi-node scaling?
• What is the impact of FlowLog’s increased memory footprint for very large-scale analyses, and can further memory optimizations be applied?

Why it matters for bot defense

This paper is highly relevant to bot-defense and CAPTCHA practitioners utilizing static analysis or declarative logic for program or policy verification. FlowLog’s advances offer a practical path to faster and more scalable evaluation of complex Datalog queries underlying static analysis tasks, including those used in bot-detection heuristics or anomaly detection frameworks. Its incremental update capabilities enable rapid re-analysis after small changes, a common need during iterative tuning and deployment of security rules. The built-in profiling tools facilitate performance debugging without intrusive instrumentation, which can accelerate optimization cycles for engineers maintaining large logic-based defenses.

Moreover, FlowLog’s capability to extend beyond standard Datalog semantics may inspire more expressive security policies that require non-monotonic or iterative reasoning, potentially overcoming limitations in classical declarative bot-detection languages. However, practitioners should weigh FlowLog’s additional memory use against their environment’s constraints and verify that its current capabilities align with their scalability and real-time update requirements.

Cite

@article{arxiv2607_23971,
  title={ FlowLog: Re-thinking Datalog for Fast and Extensible Static Analysis },
  author={ Zhenghong Yu and Hangdong Zhao and Wanzhu Hou and Paraschos Koutris },
  journal={arXiv preprint arXiv:2607.23971},
  year={ 2026 },
  url={https://arxiv.org/abs/2607.23971}
}

Read the full paper

• arXiv:2607.23971 (abstract)
• arXiv:2607.23971 (PDF)