libcpg

A Rust library for constructing and analyzing Code Property Graphs (CPGs). A CPG (Yamaguchi et al. 2014) merges complementary views of a program — the Abstract Syntax Tree (AST), the Control Flow Graph (CFG), and the Data Flow Graph (DFG) — into one unified petgraph-backed graph, and adds the Program Dependence Graph (PDG) on top for program slicing. On this substrate it offers Type-1 through Type-4 function clone detection, subgraph-isomorphism pattern matching, Gang-of-Four design pattern detection, algorithm/complexity analysis, and graph-neural-network embeddings.

Architecture at a glance

The defining idea: one shared node set carries several typed edge overlays — the same nodes are simultaneously an AST, a CFG, and a DFG (and, on demand, a PDG). A query can therefore mix syntax, control flow, and data flow freely.

Figure — the unified CPG for a small function. Source: docs/diagrams/cpg-overlay.dot.

Capabilities

• CPG construction from source via tree-sitter (TreeSitterCpgBuilder), either parsing internally (build, requires the matching lang-* feature) or from a caller-supplied parse tree (build_from_tree — "Mode B" — so a host that already parsed a file can reuse its own grammar and avoid a second parse).
• CFG extraction — structural control-flow edges (14 CfgEdgeKind variants) for block/if/while/for/loop/match/return/break/continue/try/throw/call.
• Strongly-connected components — exact, deterministic decomposition of per-function CFGs and the resolved whole-CPG call graph, including loop/recursion classification and the condensation DAG.
• Condensation-DAG analytics — canonical longest-path levels, SCC-size weighted critical paths, level width, and deterministic width-bounded Coffman–Graham scheduling with explicit caps and malformed-input handling.
• Architectural layering — bottom-first reversal of condensation longest- path levels with deterministic cyclic-component, downward-skip, and upward dependency witnesses.
• Architectural smells — advisory multi-node cycles, two-sided dependency hubs, Martin-instability violations, and module-size outliers with stable node and numerical evidence.
• Design Structure Matrix analytics — bounded transitive visibility fan-out/fan-in, propagation cost, deterministic median core–periphery roles, and largest cyclic-group evidence over any graph projection.
• Martin package metrics — deterministic afferent/efferent coupling, instability, abstractness, main-sequence distance, and witnessed Stable Dependencies Principle violations over explicit module assignments.
• Code metrics — deterministic CK and LCOM1–5 reports over resolved method–field/call evidence, plus language-independent Halstead, cyclomatic, cognitive-complexity, and maintainability-index function summaries.
• Reflexion-model conformance — pure ordered path-to-layer mapping with deterministic convergence, divergence, unlayered, realized-pair, and declared-absence evidence.
• WL structural clones — deterministic directed-degree labels and ordered Weisfeiler–Lehman clone-candidate classes over validated graph projections.
• Function clone detection — strongest Type-1/2 ordered AST fingerprints, Type-3 kind/name multiset similarity, and bounded Type-4 PDG WL/VF2 verification with all-or-error pair, graph-size, and invocation budgets.
• Multi-file program composition — deterministic collision-free merging, ordered per-file scopes, and evidence-bounded import/export overlays that disambiguate cross-file calls without language-specific reparsing.
• IFDS/IDE procedure summaries — feature-free generic facts and summary lattices, validated callee-first SCC scheduling, bounded recursive fixed points, and explicit external/unresolved/capped evidence.
• Datalog fact export — feature-free deterministic EDB relations for every represented CPG overlay, plus lossless edge snapshots and caller-owned Soufflé buffers; external engines retain rule evaluation and fixed points.
• Interprocedural effect summaries — feature-free global, parameter, and field read/write places; transitive purity; parameter-to-return flow; and checked constant returns over the same bounded call-SCC schedule, with source-depth state held by explicit heap continuation machines.
• Advisory taint and maybe-null analysis — feature-free, data-driven source, sink, sanitizer, external-model, and dereference findings with deterministic interprocedural witnesses and explicit completeness evidence.
• Compositional heap analysis — feature-free separation-logic anti-frames and postconditions over call SCCs, with qualified null-dereference, use-after-free, and leak evidence plus an optional typed Heap overlay.
• System dependence and interprocedural slicing — feature-free labeled summary edges plus deterministic node/depth-capped two-pass backward and forward slices that preserve represented call context.
• Channel topology and linearity — feature-free typed send/receive event extraction, def-use-resolved channel identity, orphan/blocked topology, and advisory linear-consumption contention.
• Communication and lock-order deadlocks — feature-free initially blocked wait-for SCCs, typed read/write lock-order SCCs, transitive acquisition summaries, and statement-precise advisory witnesses.
• May-happen-in-parallel relation — feature-free typed parallel-operand cross-products with canonical symmetric statement pairs, nested-region composition, and an explicit quadratic-output cap.
• Race and atomicity candidates — feature-free exact field/index/channel identity, statement-lifted MHP conflicts, typed locksets, and witnessed read-modify-write release/reacquire gaps.
• Advisory session-protocol sketches — Rholang-gated, definition-resolved endpoint traces with three-valued binary direction and payload-type duality.
• Finite-state typestate analysis — feature-free allocation-site object identities, typed event/alias evidence, deterministic CFG may-facts, canonical forbidden-transition witnesses, and explicit completeness bounds.
• Advisory bug detectors — feature-free resource-leak projection, binder-aware uninitialized-use evidence, bounded interprocedural exception summaries, uncaught root witnesses, and dead-catch findings.
• Population anomaly detectors — feature-free taint-selected missing-check inference plus call-order and return-check beliefs with exact rational support, canonical evidence, and explicit incomplete-result qualification.
• Clone and feasibility advisories — feature-free exact Type-2/3 clone divergence evidence plus SCCP/interval proofs for infeasible branches, redundant guards, and integer contradictions.
• API-usage and temporal protocol mining — feature-free centered typed API Usage Graphs, exact strict-majority following/argument/receiver/control patterns, advisory deviations, and named finite-state temporal properties.
• Declarative CWE-template analysis — feature-free bounded VF2 structural qualification composed with shared taint, null-flow, typestate, interval, and typed-literal evidence for ten shipped weakness families, with explicit completeness and immutable advisory reports.
• Cryptographic and security-policy analysis — feature-free CrySL-style crypto misuse, high-entropy/name-hinted secret flow to governed sinks, and exact peer-inferred missing authN/authZ guards with typed completeness.
• Vulnerability extrapolation — feature-free ranking from a labeled seed through shared-vocabulary PDG WL cosine and bounded relaxed VF2 confirmation, with deterministic order and explicit incomplete-result evidence.
• Virtual-call type refinement — feature-free immutable CHA/RTA/VTA target sets over typed receivers, hierarchy edges, normalized allocations, and reaching definitions, with a tested monotone precision lattice.
• Projection centrality — deterministic PageRank variants, vertex/edge betweenness, eigenvector, Katz, closeness, harmonic, HITS, and Burt structural-hole scores with explicit iteration and traversal budgets.
• Community detection — deterministic multi-level Louvain over weighted undirected projection views, canonical node-aligned partitions, and checked connected-community refinement with explicit pass and level ceilings.
• Cohesion and robustness — deterministic k-core and k-truss peeling, iterative articulation/bridge analysis, two-edge-connected blocks, bounded weighted global minimum cut, degree assortativity, and ordered attack traces.
• Spectral connectivity — deterministic combinatorial-Laplacian algebraic connectivity, aligned Fiedler vectors, sign partitions, exact disconnected certificates, and bounded sparse iteration with residual evidence.
• Bounded simple cycles — feature-free SCC-pruned enumeration of canonical directed cycle witnesses with explicit length/count ceilings and a concrete first-omission witness when the result cap binds.
• Directed motif census — the complete sixteen-class Davis–Leinhardt triad taxonomy plus bounded bidirected-clique and out-star graphlets, with explicit size budgets and no silently partial results.
• CFG reachability — feature-free, deterministic reachable/unreachable partitions and structural dead-branch evidence without graph mutation.
• Basic-block CFGs — deterministic, id-preserving block partitions, typed block edges, entry/exits, and iterative post-order/RPO traversal views.
• Monotone data-flow framework — feature-free forward/backward Kildall solving over basic blocks, canonical fact universes, may/must bit domains, loop-header widening, bounded narrowing, and per-node state replay.
• Variable liveness and dead stores — deterministic backward-May liveness with sorted per-node states and conservative, advisory dead-write evidence.
• Expression optimization evidence — forward-Must available expressions, backward-Must anticipability, and dominance-backed advisory CSE/PRE candidates.
• Sparse conditional constant propagation — coupled executable-edge and value-cell fixed points, checked scalar folding, and proof-backed reachability refinement.
• Interval value ranges — forward abstract interpretation with comparison refinement, loop-header widening, bounded narrowing, and canonical immutable block-entry reports; typed heap continuations keep expression depth off the native call stack.
• Relational abstract domains — feature-free integer octagons and static reduced products plus abstract-domains-gated exact arbitrary-precision rational polyhedra; closure and projection use iterative heap machines.
• Loop invariants and induction variables — DFG-backed invariant fixed points, unique latch-dominating additive/affine IVs, conservative hoist candidates, and counted-trip evidence; typed postorder and expression machines keep candidate and constant depth off the native stack.
• DFG extraction — intraprocedural, stack-safe AST-ordered reaching definitions (Kildall 1973) and def-use chains (13 DfgEdgeKind variants).
• PDG + program slicing — control-dependence edges via the reverse dominance frontier (Ferrante–Ottenstein–Warren 1987; Cytron et al. 1991) plus data-dependence edges, with bounded backward/forward Weiser slices (PdgBuilder, backward_slice, forward_slice).
• Deterministic CPG diff — feature-free bounded-GED node alignment, exact translated node/typed-edge edit scripts, and represented-PDG change classification under complete-or-error node/edge/edit budgets.
• Function clones and subgraph isomorphism — feature-free pattern::detect_clones, deterministic stack-safe VF2 pattern matching (pattern::Vf2Matcher), and graph similarity (Jaccard, cosine, stable Weisfeiler-Lehman, and bounded bipartite graph-edit upper bounds with explicit cap evidence).
• Design-pattern detection (23 Gang-of-Four patterns) and algorithm / complexity analysis, behind the design-patterns and algorithm-detection features. The default algorithm detector grounds loop cost in validated CFG nesting and DFG-backed induction/bound evidence, with an exact AST-heuristic fallback when those overlays are absent.
• Optional GNN embeddings (gnn) and serde serialization (serde).
• F1R3FLY.io languages — Rholang and MeTTa are supported through Mode B (build_from_tree); their node mappers are implemented (features rholang / metta).
• MeTTa rewriting evidence — metta adds stack-safe dependency-pair termination, exact critical-pair joinability, qualified unknown outcomes, and transactional RewriteDep overlays over normalized rules.

Quick start

// requires: features = ["lang-rust"]
use libcpg::{TreeSitterCpgBuilder, CpgBuilder, PdgBuilder, backward_slice, Language};

let builder = TreeSitterCpgBuilder::new();
let source = "fn f(x: i32) -> i32 { let y = x + 1; if y > 0 { y } else { 0 } }";
let mut cpg = builder.build(source, Language::Rust)?;

// Add Program Dependence Graph edges for the first function, then slice.
let func = cpg.functions().map(|n| n.id).next().expect("a function node");
PdgBuilder::new().build(&mut cpg, func);
let slice = backward_slice(&cpg, func, 256);
println!("{} nodes in the backward slice", slice.len());
# Ok::<(), libcpg::Error>(())

With the default feature set (default = []) no grammars are compiled in, so build returns Error::UnsupportedLanguage; enable a lang-* feature (as above) or use the feature-free build_from_tree path. See docs/usage/00-getting-started.md.

The feature-free population anomaly example exercises both exact oracles:

cargo run --example population_anomalies --no-default-features

See the I6/I7 usage guide for catalog policy, peer scopes, exact thresholds, reports, and completeness.

The feature-free I8/I9 example exercises both clone and path advisories:

cargo run --example clone_feasibility_advisories --no-default-features

See the I8/I9 usage guide for typed witnesses, SCCP/interval proof sources, resource bounds, and report qualification.

The feature-free CWE-template example exercises the complete ten-template registry on a represented request-to-SQL flow:

cargo run --example cwe_templates --no-default-features

See the CWE-template usage guide for custom role catalogs, resource policy, evidence interpretation, and complete versus incomplete report handling.

Features

default = [] — nothing is enabled by default. Opt in to exactly what you need.

Feature	Enables
lang-rust, lang-python, lang-javascript, lang-typescript, lang-go, lang-java, lang-c, lang-cpp, lang-json, lang-html, lang-css, lang-bash, lang-toml, lang-yaml, lang-markdown, lang-ruby	the tree-sitter grammar for that language (each enables internal build)
lang-systems / lang-scripting / lang-web / lang-config / lang-all	grammar groups
design-patterns	Gang-of-Four detection (patterns::)
algorithm-detection	algorithm-family recognition + complexity (algorithms::)
abstract-domains	exact arbitrary-precision rational convex polyhedra
serde	Serialize / Deserialize derives
gnn	graph-neural-network embeddings (gnn::CpgGnn)
ml-linfa / ml-rules	ML- / rule-based pattern classification
rholang	the dependency-free Rholang Mode-B mapper and NameFlow analyses
metta	the grammar-free MeTTa Mode-B mapper and exact libdictenstein-indexed rewrite analyses
full	gnn + design-patterns + algorithm-detection + abstract-domains + serde + ml-rules + lang-all

(gpu is reserved for future work and wires no code yet.)

Supported languages

Sixteen languages are parsed internally via feature-gated tree-sitter grammars: Rust, Python, JavaScript, TypeScript, Go, Java, C, C++, JSON, HTML, CSS, Bash, TOML, YAML, Markdown, Ruby. Rholang and MeTTa (F1R3FLY.io) are built through Mode B (build_from_tree) with a caller-supplied grammar; see docs/usage/06-f1r3fly-rholang-metta.md.

Documentation

Comprehensive documentation lives under docs/:

• Theory — the CPG model, control/data flow, program dependence & slicing, multi-file composition, subgraph isomorphism, similarity, pattern detection, complexity, and GNNs, with proofs, math, and citations.
• Architecture — module map, the graph data model, construction & analysis pipelines, and language frontends.
• Design decisions — ADR-style records for load-bearing graph, construction, analysis, and feature choices.
• API reference — graph/program/projection/block-CFG/SCC/condensation/layering/architectural-smell/DSM/Martin/code-metric/reflexion/centrality/community/cohesion/reachability, builder, and pattern/algorithm/GNN reference.
• Components — graph projections, basic blocks, dominators, SCC/condensation/layering/architectural-smell/DSM/Martin/code-metric/reflexion/centrality/community/cohesion analytics, reachability, heterogeneous export, fuzzing distance, builders, patterns, algorithms, and GNN internals.
• Usage guides — task-oriented how-tos.
• Engineering · Analysis-expansion matrix · Scientific validation · Security · Taint-analysis usage · Bug-detector usage.
• Glossary and the diagram catalog.

License

Licensed under either of Apache License, Version 2.0 or MIT license at your option.

References

• Yamaguchi, F., Golde, N., Arp, D., Rieck, K. (2014). Modeling and Discovering Vulnerabilities with Code Property Graphs. IEEE S&P. DOI: 10.1109/SP.2014.44
• Ferrante, J., Ottenstein, K. J., Warren, J. D. (1987). The Program Dependence Graph and Its Use in Optimization. ACM TOPLAS. DOI: 10.1145/24039.24041
• Cytron, R., et al. (1991). Efficiently Computing Static Single Assignment Form and the Control Dependence Graph. ACM TOPLAS. DOI: 10.1145/115372.115320
• Weiser, M. (1984). Program Slicing. IEEE TSE. DOI: 10.1109/TSE.1984.5010248
• Cordella, L. P., et al. (2004). A (Sub)graph Isomorphism Algorithm for Matching Large Graphs. IEEE TPAMI. DOI: 10.1109/TPAMI.2004.75
• Kildall, G. A. (1973). A Unified Approach to Global Program Optimization. POPL. DOI: 10.1145/512927.512945
• Wegman, M. N., Zadeck, F. K. (1991). Constant Propagation with Conditional Branches. ACM TOPLAS. DOI: 10.1145/103135.103136
• Cousot, P., Cousot, R. (1977). Abstract Interpretation: A Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints. POPL. DOI: 10.1145/512950.512973
• Kahn, A. B. (1962). Topological sorting of large networks. Communications of the ACM. DOI: 10.1145/368996.369025
• Coffman, E. G., Jr., Graham, R. L. (1972). Optimal scheduling for two-processor systems. Acta Informatica. DOI: 10.1007/BF00288685
• MacCormack, A., Rusnak, J., Baldwin, C. Y. (2006). Exploring the Structure of Complex Software Designs: An Empirical Study of Open Source and Proprietary Code. Management Science. DOI: 10.1287/mnsc.1060.0552
• Baldwin, C. Y., MacCormack, A., Rusnak, J. (2014). Hidden Structure: Using Network Methods to Map System Architecture. Research Policy. DOI: 10.1016/j.respol.2014.05.004
• Martin, R. C. (1994). OO Design Quality Metrics: An Analysis of Dependencies. Object Mentor technical report. Archived report PDF. No DOI assigned.
• Fontana, F. A., Pigazzini, I., Roveda, R., Tamburri, D. A., Zanoni, M., Di Nitto, E. (2017). Arcan: A Tool for Architectural Smells Detection. DOI: 10.1109/ICSAW.2017.16
• Fontana, F. A., Pigazzini, I., Roveda, R., Zanoni, M. (2016). Automatic Detection of Instability Architectural Smells. DOI: 10.1109/ICSME.2016.33