Level-2: integrate Jelly (drop CodeQL), build taint analysis, add LICENSE

[rahlk]

Summary

Replace the (stubbed, never-implemented) CodeQL-based level-2 enrichment with Jelly (Aarhus University), and build taint analysis on top of it. Jelly is a pure-TypeScript static analyzer (call graph + flow-insensitive points-to + access paths) — BSD-3-Clause, zero native dependencies — so unlike CodeQL or Joern it can be embedded in-process inside the bun --compile cants binary, preserving the single-self-contained-binary goal.

This issue tracks three pieces of work: (1) full Jelly integration with a taint layer, (2) removing CodeQL from the codebase/docs, and (3) adding the missing LICENSE.

---

1. Full Jelly integration (level-2 enrichment + taint)

Why Jelly: pure JS/TS (Babel-based), no node-gyp/native addons, BSD-3-Clause (compatible with our Apache-2.0), direct TypeScript support, JSON call-graph output. Embeddable in cants — no JVM, no sidecar.

Known friction (from evaluation):

• CLI-only, no public library API → vendor src/ and hook the solver internals.
• Parses with Babel (type-stripping, not type-aware), whereas our level-1 uses the tsc resolver → two foundations to reconcile.
• Output is location-based; our call_graph is keyed by canonical callable signatures that byte-match symbol_table keys → needs an identity-mapping layer.
• Jelly gives call graph + points-to, not taint → we build the taint layer.
• Node >=22 engine / Bun compatibility unverified → must test under Bun.

Tasks

• Spike: install Jelly, run it on test/fixtures/sample-app, capture its cg.json schema, locate the constraint-graph data structures (FragmentState/AnalysisState subset edges + tokens), and confirm it runs under Bun.
• Vendor Jelly (src/) under e.g. src/semantic_analysis/jelly/; preserve its BSD-3-Clause notice.
• Build the identity-mapping layer from Jelly's location-based nodes → our canonical signature keys (shared by both the call-graph merge and taint).
• Merge Jelly's call graph into the existing call_graph (provenance jelly), via mergeEdges.
• Verify end-to-end inside the compiled cants binary (in-process, no external runtime).

Taint analysis layer (build on Jelly's value-flow graph)

Taint = labeled reachability over Jelly's inclusion/points-to edges, seeded at sources, blocked at sanitizers, checked at sinks. Flow-insensitive + context-insensitive → cheap and over-approximate (sound-leaning, FP-prone), which is the desired default; precision knobs below.

• Models-as-data spec for sources / sinks / sanitizers / passthrough — full CLI + schema design in the Configurable taint models subsection below.
• Built-in propagators: string +, template literals, property read/write.
• Labeled monotone worklist fixpoint over the value-flow graph (bitset of taint kinds per node); source-kind ↔ sink-kind matching.
• Path reconstruction (BFS over predecessor edges) for source→sink explanations.
• Over-approximation knobs (flags): --taint-assume-passthrough (unmodeled call ⇒ taint passes through), collapse containers, field-insensitive mode, optional ignore-sanitizers.
• New taint_flows section in analysis.json (source/sink models, locations, path, sanitized flag); optionally tag carrier call_graph edges.

Configurable taint models (sources / sinks / sanitizers as args)

Models are data the analyzer consumes, never hardcoded: ship sensible built-ins that the user can extend, override, or fully replace at invocation. The engine (fixpoint) is decoupled from where a model came from.

CLI surface (extends the commander setup in src/cli.ts):

--taint                    enable taint (or implied by -a 2)
--taint-config <path>      JSON model file ('-' = stdin)
--source <spec>            inline source     (repeatable)
--sink <spec>              inline sink        (repeatable)
--sanitizer <spec>         inline sanitizer   (repeatable)
--taint-builtins <on|off>  load the bundled default pack (default on)

Precedence (later extends/overrides earlier): built-in pack → --taint-config file → inline --source/--sink/… flags. File = real, versionable specs; inline flags = quick one-offs.

Spec schema:

{
  "sources":     [{ "id": "express-query", "kind": "user-input",
                    "match": { "accessPath": "express.request.query" } }],
  "sinks":       [{ "id": "child-exec", "kind": "command-injection",
                    "match": { "callee": "child_process.exec", "args": [0] } }],
  "sanitizers":  [{ "match": { "callee": "encodeURIComponent" } }],
  "passthrough": [{ "match": { "callee": "JSON.parse" }, "from": [0], "to": "return" }],
  "rules":       [{ "from": "user-input", "to": "command-injection", "id": "cmd-injection" }],
  "disable":     ["builtin:eval-sink"]
}

match keys — dual identity so users can target both library and first-party code:

match key	targets	resolved via
accessPath	library values/props (express.request.query)	Jelly access paths
callee (wildcards ok, *.query)	called functions	Jelly call graph → resolved target
qualifiedName / signature	first-party funcs the user marks	our symbol_table canonical keys
args / receiver	which param/this is the tainted slot	argument position at the call

• Define + JSON-Schema-validate the spec (fail fast — it's user input).
• Resolver: map each match to Jelly constraint-graph nodes (access path → token; callee → call-arg nodes; signature → mapped node) to seed the fixpoint.
• Merge precedence + disable-by-id; ship a built-in default model pack.
• --taint-config - (stdin) so the python-sdk can forward user-defined models without a temp file; report the matching source/sink/rule id per flow for explainability.

Suggested staging

1. MVP — call-graph-only taint: intraprocedural def-use from ts-morph (already in-tree) + Jelly's call graph for inter-procedural arg→param/return→caller. Ships without Jelly-internals surgery.
2. v2 — points-to-backed propagation over Jelly's constraint graph (alias-aware).
3. v3 — models-as-data so sources/sinks are user-extensible without recompiling (Configurable taint models above).

Implementation guide & learning path

The order below keeps each step independently testable; the reading list is so the design rests on first principles rather than copied recipes.

Build order:

1. Spike Jelly (task above) — get its call graph + constraint graph in hand on a real fixture.
2. Identity-mapping layer (Jelly locations ↔ symbol_table signatures).
3. MVP taint — call-graph-only propagation (no points-to); prove one source→sink flow end-to-end on a fixture.
4. Swap the substrate to Jelly's points-to constraint graph (alias-aware).
5. Configurable models: CLI flags + schema + validator (above).
6. Precision knobs + path reconstruction + taint_flows output.

Concepts worth reading first:

• Andersen-style (inclusion-based) points-to analysis — the substrate Jelly computes; taint rides the same subset edges. (Start here; it's the mental model for everything else.)
• Taint as graph reachability / IFDS — Reps–Horwitz–Sagiv, "Precise Interprocedural Dataflow Analysis via Graph Reachability" (POPL '95). The canonical framing even though our MVP is flow-insensitive.
• Access paths — how Jelly models library values (express.request.query) without analyzing the library; this is what your match.accessPath keys off.
• Flow- vs context-sensitivity tradeoffs — why flow-insensitive = cheap + over-approximate (more FPs, sound-leaning).
• Jelly's lineage — the JAM / TAPIR / ACG papers linked from its README: what its points-to actually models and its known unsoundness (dynamic eval, reflection, etc.).
• Reference model designs (for what to model, not how): CodeQL's JS/TS sources & sinks and Semgrep's taint mode.

Reading Jelly's source: begin at the solver/constraint state (FragmentState / AnalysisState) — its subset edges + tokens are the value-flow graph you'll propagate taint over.

---

2. Drop CodeQL mentions

CodeQL was only ever a stub; retarget all references to Jelly.

• src/semantic_analysis/codeql/codeql.ts → jelly/ (rename dir + buildCodeqlCallGraph → buildJellyCallGraph).
• src/core.ts — import + the level-2 enrich call/comment (lines ~4, ~29, ~31).
• src/cli.ts — --analysis-level help text (2 = + CodeQL enrichment → Jelly).
• src/options/options.ts — level-2 doc comment.
• src/semantic_analysis/callGraph.ts and src/semantic_analysis/index.ts — comments.
• README.md — --help block + "Deeper analysis" example + level-2 prose (lines ~77, ~115, ~122).

---

3. Add a LICENSE (and resolve the licensing thread)

The LICENSE file is missing — the README links to ./LICENSE and both package.json and pyproject.toml declare Apache-2.0, but no file exists.

• Add a verbatim Apache-2.0 LICENSE (matches the codeanalyzer-python/-java siblings).
• No restrictive-license caveat needed. It was prompted by CodeQL's proprietary terms; switching level-2 to Jelly (BSD-3-Clause) removes that concern entirely — we'd be Apache-2.0 invoking/embedding permissively-licensed code.
• When Jelly is vendored, include its BSD-3-Clause notice (e.g. a NOTICE or third-party license file) for attribution.

---

Context: this supersedes the original CodeQL level-2 plan. The single-binary goal is the driver — Jelly is the only credible engine that runs in pure JS and can live inside the cants binary (Joern/CodeQL are external JVM/proprietary tools).

[rahlk]

Design track: a CPG + reachableByFlows taint engine (and how it reconciles with the single-binary goal)

Follow-up to the taint section above, sketching a concrete engine design based on Joern's CPG / reachableByFlows mechanics. The issue body (rightly) rejected Joern as a runtime — JVM/external, breaks the bun --compile single-binary goal. The key realization: we can borrow Joern's design (demand-driven backward data-flow over a Code Property Graph) without shipping its JVM. That gives us two options, and the recommendation flips depending on the single-binary constraint.

Two integration options

Option A — Joern as an external engine. Emit a Joern-compatible CPG protobuf (cpg.proto) from ts-morph + Jelly, load it into Joern, and run its dataflowengineoss.reachableByFlows.

• ✅ Reuse a mature, Apache-2.0 interprocedural engine + path witnesses for free.
• ❌ Breaks the single-binary goal (needs a JVM + Joern alongside cants), plus a location↔signature mapping layer and the full frontend-contract surface.

Option B — reimplement reachableByFlows in-process (recommended). Build a CPG-shaped graph in TS (AST + CFG + DDG) from ts-morph, use Jelly for call resolution + alias precision, and run a small in-process backward data-flow solver. We copy Joern's algorithm, not its runtime.

• ✅ Stays pure-JS / in the cants binary — consistent with this issue's driver.
• ✅ Flow-sensitive + native path witnesses (a strict upgrade over the flow-insensitive labeled-reachability sketch in the issue body — see "relationship to the staging plan" below).
• ❌ We own the engine (the work below).

The rest of this comment specs Option B (with the CPG model being exactly what Option A would serialize, so the work isn't wasted if we ever want to hand a CPG to Joern for cross-checking).

---

1. The CPG data model (minimal subset reachableByFlows needs)

// Nodes (Joern-aligned names so a protobuf export is mechanical later)
type NodeKind =
  | "METHOD" | "METHOD_PARAMETER_IN" | "METHOD_PARAMETER_OUT" | "METHOD_RETURN"
  | "BLOCK"  | "CALL" | "IDENTIFIER" | "LITERAL" | "FIELD_IDENTIFIER"
  | "RETURN" | "LOCAL" | "MEMBER" | "TYPE_DECL" | "NAMESPACE_BLOCK" | "FILE"

interface CpgNode {
  id: number
  kind: NodeKind
  code: string
  // CALL-specific:
  methodFullName?: string         // resolved callee (Jelly fills dynamic ones)
  dispatchType?: "STATIC" | "DYNAMIC"
  // ordering / args:
  order?: number                  // position among AST siblings
  argumentIndex?: number          // 0 = receiver, 1..n = args
  typeFullName?: string           // from the tsc checker
  signature?: string              // OUR canonical signatureOf() key (the bridge)
  line?: number; col?: number
}

type EdgeKind =
  | "AST" | "CFG" | "CALL" | "REF" | "ARGUMENT" | "RECEIVER"
  | "REACHING_DEF"              // the DDG — taint rides this
  | "CONTROL_DEP"              // optional: only if we ever do implicit flows

interface CpgEdge { src: number; dst: number; kind: EdgeKind; varName?: string }

The single most important property is signature on METHOD/CALL nodes: it ties every CPG node back to a symbol_table canonical key, so taint_flows can be reported in our own schema (and is the same identity-mapping layer the issue body already calls for).

2. ts-morph → CPG mapping

ts-morph node	CPG emission
SourceFile	FILE + NAMESPACE_BLOCK
Function/Method/Arrow/Constructor	METHOD + one METHOD_PARAMETER_IN per param + METHOD_RETURN (+ METHOD_PARAMETER_OUT for mutated by-ref params)
ClassDeclaration	TYPE_DECL + MEMBER per field
Block	BLOCK
CallExpression	CALL (set methodFullName,dispatchType); ARGUMENT edges to args, RECEIVER edge to this
BinaryExpression('+'), template literal	CALL <operator>.addition / .formatString with operands as ARGUMENT (uniform propagator handling)
PropertyAccess	CALL <operator>.fieldAccess + FIELD_IDENTIFIER
Assignment / VariableDeclaration	LOCAL + CALL <operator>.assignment (lhs=arg0, rhs=arg1)
Identifier (var ref)	IDENTIFIER + REF edge to its LOCAL/PARAMETER_IN
Literal	LITERAL
ReturnStatement	RETURN

Modeling operators/assignments as CALLs (Joern's convention) means taint propagation has one rule — "flow from arguments to result per a semantic" — instead of a special case per syntax form.

3. Where Jelly plugs in

• CALL.methodFullName for dynamic dispatch. ts-morph's checker resolves static calls; for callbacks / higher-order / polymorphic calls it returns nothing useful. Fall back to Jelly's points-to to get the concrete callee set, emit a CALL edge per target, and mark dispatchType = DYNAMIC. This is the precision that makes the interprocedural backward step actually cross the edges Joern's own jssrc2cpg misses.
• Alias/field precision in the DDG (v2): use Jelly's access paths to refine REACHING_DEF through object properties and aliases.

4. Pseudocode

(a) Emit the CPG

function emitCpg(project: TsProject): Cpg {
  const cpg = new Cpg()
  for (const sf of project.sourceFiles()) {
    const file = cpg.add("FILE", sf.path)
    for (const decl of sf.topLevel()) emitAst(cpg, decl, file)   // AST + nodes
  }
  for (const m of cpg.methods()) buildCfg(cpg, m)                 // CFG in eval order
  resolveCalls(cpg, project)                                      // step (b)
  for (const m of cpg.methods()) reachingDefs(cpg, m)            // step (c) -> REACHING_DEF
  return cpg
}

(b) Resolve calls (tsc first, Jelly for the dynamic tail)

function resolveCalls(cpg: Cpg, project: TsProject) {
  const jelly = runJelly(project)                  // points-to + call graph
  for (const call of cpg.calls()) {
    let targets = tscResolve(call)                 // exact static dispatch
    if (targets.length === 0) targets = jelly.calleesOf(call.line, call.col)
    call.methodFullName = targets[0]?.fullName ?? "<unresolved>"
    call.dispatchType = targets.length > 1 || jelly.isDynamic(call) ? "DYNAMIC" : "STATIC"
    for (const t of targets) cpg.addEdge(call, t.methodNode, "CALL")
  }
}

(c) Reaching definitions → DDG (REACHING_DEF edges)

function reachingDefs(cpg: Cpg, m: Method) {
  // standard forward gen/kill fixpoint over the method CFG
  const gen = new Map(), kill = new Map()
  for (const n of m.cfgNodes()) { gen.set(n, defsAt(n)); kill.set(n, defsOfSameVarsAs(n)) }
  const IN = new Map(), OUT = new Map()
  let changed = true
  while (changed) {
    changed = false
    for (const n of m.cfgNodes()) {
      const inN  = union(cfgPreds(n).map(p => OUT.get(p) ?? emptySet))
      const outN = union(gen.get(n), difference(inN, kill.get(n)))
      if (!eq(outN, OUT.get(n))) { OUT.set(n, outN); IN.set(n, inN); changed = true }
    }
  }
  for (const use of m.uses())                       // emit def -> use edges
    for (const def of IN.get(use) ?? [])
      if (def.varName === use.varName) cpg.addEdge(def, use, "REACHING_DEF", use.varName)
}

(d) reachableByFlows — demand-driven backward, interprocedural

interface Ctx { maxCallDepth: number; semantics: Map<string, FlowSemantic>;
                isSanitizer: (n: CpgNode) => boolean }

function reachableByFlows(sinks: CpgNode[], sources: Set<number>, ctx: Ctx): Path[] {
  const results: Path[] = []
  const seen = new Set<string>()                                   // (node @ depth) memo
  const work: { n: CpgNode; path: CpgNode[]; depth: number }[] =
    sinks.map(s => ({ n: s, path: [s], depth: 0 }))

  while (work.length) {
    const { n, path, depth } = work.pop()!
    if (sources.has(n.id)) { results.push(path); continue }        // reached a source
    if (ctx.isSanitizer(n)) continue                               // prune sanitized path
    const key = `${n.id}@${depth}`; if (seen.has(key)) continue; seen.add(key)
    const push = (m: CpgNode, d = depth) => work.push({ n: m, path: [m, ...path], depth: d })

    for (const pred of ddgIn(n)) push(pred)                        // intraprocedural data dep

    if (isCallResult(n)) {                                         // value came out of a call
      const call = ownerCall(n)
      if (hasBody(call) && depth < ctx.maxCallDepth)
        for (const callee of calleesOf(call))                      // step into callee (Jelly-resolved)
          for (const exit of taintExits(callee)) push(exit, depth + 1)  // RETURN / PARAMETER_OUT
      else                                                         // library: use a semantic instead
        for (const inIdx of ctx.semantics.get(call.methodFullName)?.inputsFor(n) ?? defaultPassthrough(call))
          push(argAt(call, inIdx))
    }
    if (isParameterIn(n))                                          // jump out to callers' args
      for (const cs of callersOf(method(n))) push(argAt(cs, n.index), depth - 1)
  }
  return dedupeByEndpoints(results)
}

(e) Wiring sources / sinks / sanitizers / semantics (reuses the Configurable taint models spec already in the issue body)

const sources  = resolveSpecsToNodes(cpg, models.sources)         // accessPath/callee/signature -> node ids
const sinks    = resolveSpecsToNodes(cpg, models.sinks)
const ctx: Ctx = {
  maxCallDepth: opts.maxCallDepth ?? 6,
  semantics: buildSemantics(models.passthrough, /* + TASER-derived library summaries */),
  isSanitizer: nodeMatchesAny(models.sanitizers),
}
const flows = sinks.flatMap(sink =>
  reachableByFlows([sink], new Set(sources.map(s => s.id)), ctx)
    .filter(p => ruleAllows(models.rules, sourceKind(p), sinkKind(p))))   // source-kind ↔ sink-kind
emit("taint_flows", flows.map(toAnalysisJson))                    // path + ids + sanitized flag

5. Implementation checklist (Option B)

• CPG core — Cpg structure + emitAst for the mapping table above (AST + node properties incl. signature bridge).
• CFG builder — per-method control-flow edges in evaluation order (operators/assignments as CALLs).
• Call resolution — tsc-first, Jelly fallback for dynamic dispatch; CALL edges + dispatchType.
• DDG pass — reaching-definitions fixpoint → REACHING_DEF edges (step c).
• Backward solver — reachableByFlows (step d): intraprocedural DDG walk + interprocedural arg↔param↔return + call-depth bound + memoization + path dedupe.
• Semantics layer — FlowSemantic per library method; default pass-through; later ingest TASER summaries (the issue's models-as-data resolver feeds this).
• Sanitizers — path-filter predicate from the models spec.
• Reporting — taint_flows in analysis.json with the reconstructed path, matched ids, and sanitized flag (path witnesses come for free from the backward search).
• (stretch) CPG protobuf export — serialize to cpg.proto so the same graph can be cross-checked against real Joern (Option A) for validation.

Relationship to the staging plan above

This is an alternative realization of the engine task ("labeled monotone worklist fixpoint"). The issue body's sketch is flow-insensitive labeled reachability over Jelly's points-to edges; this is flow-sensitive demand-driven reachability over a DDG. They share the models-as-data front end and the identity-mapping layer. Suggested reconciliation:

• MVP (issue stage 1) can ship either engine; the flow-insensitive one is less code.
• This CPG/reachableByFlows design is the natural stage-2/3 upgrade: flow sensitivity + first-class path witnesses + a graph we could hand to Joern for differential testing.

Open questions / risks

• CFG/DDG cost in pure TS on large projects — the backward, demand-driven shape (only the sinks' backward slice) is the mitigation; cap with maxCallDepth.
• Default semantic for unmodeled libraries (optimistic = false negatives vs pessimistic pass-through = false positives) — same knob as --taint-assume-passthrough in the body.
• jssrc2cpg parity not required — since we build the CPG from ts-morph (type-aware) + Jelly, we avoid Joern's weakest component; the precision ceiling becomes Jelly's points-to, not Babel.
• Implicit flows — out of scope for v1 (data-dependence only); CONTROL_DEP edges left as a hook.

[rahlk]

Implementation: the reaching-definitions DDG (flow-sensitive substrate)

This fleshes out the REACHING_DEF / DDG step from the CPG design comment. Key decision already settled in that thread: we get flow sensitivity from reaching-definitions (kills baked into the edge set), not SSA — Joern's ReachingDefPass does exactly this, so no TS SSA generator is needed (the only real one, WALA, is JVM/EPL and breaks the single-binary goal). We build the DDG from a CFG with the textbook forward dataflow.

Pipeline:

CFG (per function) → symbol-resolved def/use → GEN/KILL (strong/weak) → bitset worklist fixpoint → def→use edges

Step 0 (prerequisite): CFG from the AST

Reaching-defs is a forward dataflow over control flow, so build a per-function CFG from the ts-morph AST first (ENTRY/EXIT + sequencing, if/else, loops while/for/for-of/for-in/do, switch, try/catch/finally, early exits return/throw/break/continue, short-circuits && || ?? ?:).

Language-agnostic — replicable for codeanalyzer-python. AST→CFG is not TS-specific. Python's stdlib ast plus existing builders (staticfg, py2cfg, Google's python_graphs — which also emits data flow) give the same starting point, so this whole CFG→DDG→taint substrate ports to the Python backend. Worth a sibling issue; the only swaps are the parser (ts-morph → ast) and the points-to helper (Jelly → PyCG/Pyre).

Step 1 — symbol-resolved def/use

Variable identity = ts-morph symbol, never the name string (identifier.getSymbol()), so shadowing / hoisting / var vs let scoping are correct.

type VarId = string        // stable key from the resolved Symbol
type DefId = number        // stable per-def id (its AST node id)

interface Def { id: DefId; varId: VarId; valueNode: AstId; strong: boolean; cfgNode: NodeId }
interface Use { varId: VarId; node: AstId; cfgNode: NodeId }

A def writes a location; a use reads one:

construct	def	use
let x = e / x = e	x (strong)	uses in e
x += e, x++	x (strong) and use of x
destructuring [a,b]=e, {a}=e	a, b (strong)	e
params, for (const v of e), catch (err)	binding (strong)
obj.p = e, arr[i] = e	access-path obj.p (weak)	obj, e
identifier r-value		use

Precompute defsByVar: Map<VarId, Set<DefId>> (needed for KILL).

Step 2 — GEN / KILL with the strong/weak discipline (the soundness lever)

const GEN  = (n: NodeId): Set<DefId> => new Set(defsAt(n).map(d => d.id))
const KILL = (n: NodeId): Set<DefId> => {
  const k = new Set<DefId>()
  for (const d of defsAt(n)) {
    if (!d.strong) continue                       // weak update kills NOTHING
    for (const other of defsByVar.get(d.varId)!)  // strong: kill all other defs of same var
      if (other !== d.id) k.add(other)
  }
  return k
}

• Strong update (assignment to a local scalar x = …): definitely overwrites → kills all other defs of x.
• Weak update (property/array writes, aliased or call-mutated locations): adds a def, kills nothing — you can't prove it's the same cell.
• Default to weak whenever unsure — over-approximates, which is the right bias for taint. This is where Jelly's points-to pays off: a singleton points-to target lets you promote obj.p = … to a strong update; otherwise stay weak.

Step 3 — bitset worklist fixpoint (forward, union)

IN[n] = ⋃ OUT[p], OUT[n] = GEN[n] ∪ (IN[n] \ KILL[n]). Back the sets with a Uint32Array bitset (def-id → bit index) so union/diff are word-wise.

function reachingDefs(cfg: Cfg): Map<NodeId, BitSet> {
  const IN = new Map<NodeId, BitSet>(), OUT = new Map<NodeId, BitSet>()
  for (const n of cfg.nodes) { IN.set(n, new BitSet()); OUT.set(n, GEN(n)) }

  const work = new Worklist(cfg.reversePostorder)   // RPO ⇒ fast convergence
  while (!work.isEmpty()) {
    const n = work.pop()
    const inN = BitSet.unionAll(cfg.preds(n).map(p => OUT.get(p)!))
    const outN = GEN(n).union(inN.difference(KILL(n)))
    IN.set(n, inN)
    if (!outN.equals(OUT.get(n)!)) { OUT.set(n, outN); work.pushAll(cfg.succs(n)) }
  }
  return IN
}

Step 4 — emit def→use (REACHING_DEF) edges

function buildDDG(cfg: Cfg, IN: Map<NodeId, BitSet>, ddg: Graph) {
  for (const n of cfg.nodes)
    for (const use of usesAt(n))
      for (const defId of IN.get(n)!.members())
        if (defOf(defId).varId === use.varId)
          ddg.addEdge(defOf(defId).valueNode, use.node, "REACHING_DEF", { var: use.varId })
}

Edge origin = the def's valueNode (the RHS expression), so taint rides expression→expression. Multiple reaching defs at a use ⇒ multiple incoming edges — the union is the join, so no φ-nodes.

ts-morph landmines

• Closures / captured vars: nested function reading an outer var = use; calling something that may mutate a captured var = weak def of it.
• By-reference mutation: object passed to a callee ⇒ weak def of that object at the call site (unless a semantic / Jelly says single-target).
• Hoisting/TDZ: handled by symbol resolution — don't reconstruct scope from names.
• Aliasing/properties: the weak-update default keeps it sound; Jelly's access paths tighten specific cases to strong updates.

Worked check

let x = source();    // d1: strong def x (taint)
x = sanitize(x);     // d2: strong def x  → KILL d1
sink(x);             // use x  →  IN = {d2} only

Only edge is d2 → sink; d1 is killed, so the sink is not reached — sanitizer honored flow-sensitively, zero SSA. Change line 2 to obj.x = sanitize(...) (weak) and d1 survives — correctly conservative.

Tasks

• CFG builder over the ts-morph AST (constructs listed in Step 0); ENTRY/EXIT, RPO ordering.
• Def/use extraction with ts-morph symbol-resolved VarId; defsByVar index; per-def strong/weak flag (table above).
• BitSet (Uint32Array-backed) with union/difference/equals/members.
• Reaching-defs fixpoint (worklist, RPO) → IN per node.
• DDG emission — REACHING_DEF edges from def valueNode → use, labeled by var.
• Strong/weak promotion via Jelly — use points-to singletons to upgrade property writes to strong updates.
• Unit fixtures: sanitize-before-sink (killed), property weak-update (survives), loop-carried def, branch join (two reaching defs).

Where this slots in

This is the intraprocedural flow-sensitive substrate. Interprocedural stitching (call-site-labeled arg→param / return→result edges + matched-paren traversal) stays a separate layer per the CPG comment. Once the DDG is emitted as part of analysis.json (the "persisted DFG enrichment" decision), the SDK answers flows-to by plain reachability over REACHING_DEF edges — flow-sensitive for free.

[rahlk]

Decision: CFG/DDG storage layout — flat top-level, keyed by signature (not nested under Callable)

Refines the "persisted DFG enrichment vs. derived flows" direction. Settles where the CFG and DDG live in analysis.json.

Decision: store CFG and DDG as flat, top-level graph sections keyed by callable signature — the same shape as call_graph — not as a payload nested inside each TSCallable. Each Callable keeps only a thin pointer + the existing CFG-derived summary.

"symbol_table": {
  "src/h.ts": { "...": { "callables": {
    "src/h.handler": {
      "cyclomatic_complexity": 3,                                   // CFG-derived summary (already present)
      "cfg": { "entry": "src/h.handler#n0", "exit": "src/h.handler#nX" }  // pointer only, no payload
    }
  }}}
},
"cfg":        { "nodes": [ /* flat */ ], "edges": [ /* flat CFG edges */ ] },
"data_flow":  [ /* flat REACHING_DEF + interprocedural arg→param/return→result edges */ ]

Rules:

• Node IDs are signature-prefixed: "<callable-sig>#<local-id>" (e.g. src/h.handler#n12). The table stays flat/SDK-friendly, ownership is recoverable from the ID (no separate owner field), and "the CFG of callable X" is a prefix filter.
• Per-Callable keeps only cfg.entry/cfg.exit (+ cyclomatic_complexity, already there). No graph payload nested.
• cfg/data_flow are gated behind level-2 / --taint so level-1 output is byte-for-byte unchanged.

Rationale:

1. A CFG/DDG is a graph of relationships — by the schema's own split (nested symbol_table = structure; flat call_graph = relationships) it belongs at top level as an edge list, like call_graph.
2. Interprocedural edges need a flat node space. arg→param / return→result edges cross callables; nesting siloes them. One flat node/edge space makes them just more rows.
3. The SDK loads one graph. Flat nodes+edges go straight into networkx; nested-under-Callable forces a tree-walk + flatten first.
4. Optionality/size. CFG+DDG ≫ symbol table and only exists at level-2; a separate section can be gated/lazy/split-to-a-sibling-file without bloating level-1.
5. Canonical-schema hygiene. TSCallable is part of the cross-language Callable shape; a heavy TS-specific graph blob inside it diverges that shape.

Bonus: this flat, signature-keyed layout is also what makes the artifact graph-DB-ready (Neo4j/LPG: node-id → node, edge → relationship, edge-kind → rel type) — a nested layout would need flattening before export.

[rahlk]

Decision: representation = SDG + symbol_table (not a full CPG)

Supersedes the layout in the previous "CFG/DDG storage" decision — replaces the separate cfg + data_flow sections with a single sdg section anchored to the existing symbol_table. We do not materialize a full Code Property Graph.

The mapping (a CPG is AST + CFG + PDG; we reassign the layers):

CPG layer	Our design
AST / syntax	symbol_table (already canonical + cross-language)
PDG + interprocedural	SDG — data-dependence + control-dependence + actual/formal params + summary edges
CFG	transient — built to derive the SDG, not persisted by default

Why: a CPG's full AST is largely redundant with a symbol table (Joern materializes it only because it's a generic syntactic-query engine). We already emit the canonical declaration index; duplicating it as an AST layer buys little, and SDG summary edges give us the context-sensitive interprocedural precision a raw CPG leaves to the query engine.

Rules:

• SDG nodes are value-level (def/use, actual/formal params, call results), each carrying kind + code + source span — a lightweight syntactic tag, not a sub-AST.
• Identity is the linchpin. Signature-prefixed node IDs (<callable-sig>#<local-id>); every SDG node back-refs its owning callable; actual-param/call-result nodes reference symbol_table.call_sites, formal-param nodes reference callable.parameters. The two artifacts join into one logical graph.
• CFG is scaffolding — needed transiently for control-dependence + reaching-defs; persisted only behind a debug flag.
• Gated behind level-2 / --taint.

Tradeoff (accepted): no deep sub-expression syntactic pattern-matching (Joern-style AST subtree queries). Our query surface is structure (symbol_table) + flow (sdg), which covers taint / slicing / flows-to / declaration patterns. Source spans are kept, so a consumer can re-parse a span on demand for the rare syntactic case.

Implementation impact (details in thread)

Stays: CFG construction from the ts-morph AST; symbol-resolved def/use; reaching-defs → data-dependence edges; strong/weak update discipline; Jelly points-to for call resolution + alias precision; bitset worklist fixpoint.

Removed / demoted: no AST layer emitted (reuse symbol_table); CFG not persisted; no separate cfg/data_flow output sections; the analyzer-side on-demand reachableByFlows engine is no longer required — with summary edges precomputed, the SDK answers flows-to by plain (context-sensitive) reachability.

Added:

• Parameter model — formal-in/out per callable, actual-in/out per call site, + parameter-in/out edges (anchored to symbol_table).
• Summary-edge computation (the headline new algorithm) — per callable, which formal-in reaches which formal-out (intraprocedural reachability over the PDG), materialized as actual-in → actual-out edges at every call site; recursion handled by fixpoint. This is the IFDS/SDG tabulation step and is what makes persisted reachability context-sensitive.
• Control-dependence edges (post-dominance frontiers) — for the full PDG; deferrable to the implicit-flow phase.
• Cross-reference/identity wiring SDG ↔ symbol_table as a first-class step.

Revised staging

1. MVP — SDG with data-dependence + parameter edges, no summary edges. Plain reachability is flow-sensitive (reaching-defs kills) but context-insensitive (over-approximate — fine as the default).
2. + summary edges → context-sensitive flows-to by plain traversal (analyzer does more at build time; SDK does less at query time).
3. + control-dependence edges → implicit-flow taint.

Net: build-time cost shifts up (summary computation + recursion fixpoint), query-time drops (SDK plain traversal), and the persisted artifact is leaner (no AST, no CFG) despite the added param/summary nodes.

[rahlk]

Operational: parallel + incremental summary-edge computation

Both concerns are governed by the same call-graph dependency that makes summaries interprocedural (C's summary depends on its callees' summaries). They're two views of one fixpoint.

Parallel schedule (it's not embarrassingly parallel)

The per-callable independence in the Phase-2 pseudocode is an illusion: "over C's intraprocedural PDG" embeds call sites whose effect needs the callee's summary. So tasks are ordered by the call graph, not a flat map.

Correct frame — make -j over the call graph:

1. Tarjan SCC on the call graph → condense to a DAG (most nodes are singletons).
2. Reverse-topological schedule (callees before callers); a worker pool pulls any SCC whose callee-SCCs are done (the "ready set").
3. Across independent SCCs at the same depth → genuinely parallel. The leaf wave (callables that only call already-summarized/library functions) is embarrassingly parallel and is the bulk of the work in shallow, mostly-DAG call graphs.
4. Within an SCC (recursion cluster) → iterate to fixpoint. Usually tiny.

Monotonicity escape hatch: summaries only grow, so by Kildall the fixpoint converges in any order. A chaotic / async variant — compute all callables in parallel, repeat rounds until no new edges — is maximally parallel and trivial to schedule, trading redundant recomputation for zero topological coordination. Dial between SCC-ordered (min work) and chaotic-rounds (max parallelism).

Bun note: JS is single-threaded → real parallelism = Worker threads, per-SCC isolated. But this is build-time + cached, so measure first; sequential reverse-topo is likely fine except on huge monorepos. Prior art: concurrent/parallel IFDS tabulation.

Incremental (diff-based) — yes

Incrementality reuses the exact same fixpoint, just seeded with the changed cone instead of all callables. Invalidation propagates up the call graph (changed callee → its transitive callers) — the mirror of the batch build's callees-before-callers order.

Pipeline for a diff:

1. Diff → changed callables. Git line ranges ∩ symbol_table callable line spans → the dirty seed set (+ added/deleted callables). Extends the existing --target-files / content-hash cache.
2. Intraprocedural layers (CFG / PDG / reaching-defs / control-dep) are function-local → recompute only changed callables; unchanged ones keep cached CFG/PDG. Trivially incremental.
3. Summary fixpoint, incrementally: mark changed callables dirty; recompute their summaries; propagate dirtiness to transitive callers only if the summary actually changed (early cutoff — monotone, and most body edits don't change the summary, so the cone usually collapses fast). Reverse-topo within the dirty set.
4. Taint flows: re-derive only flows whose path touches a changed SDG edge (or, in the persisted-SDG model, just re-ship the delta and let the SDK re-traverse).

Cache shape: extend the per-file symbol cache to per-callable {CFG, PDG, local formal-in→formal-out contribution, final summary}, keyed by hash(body) + hash(consumed callee summaries). A summary is reused iff its body and every callee summary it folded in are unchanged.

The hard direction — deletions. Adds/edits are monotone (incremental fixpoint up-propagates cleanly). Removing code can shrink summaries/points-to, which a monotone framework can't do by addition → recompute the affected cone from scratch (invalidate dirty-node ∪ transitive callers, rebuild).

The non-local wildcard — points-to / call graph. Jelly is whole-program flow-insensitive Andersen: an edit can shift points-to sets non-locally. Incremental Andersen is add-easy / delete-hard. Pragmatic options: recompute points-to whole-program (likely the cheap part, measure), or restrict to the changed files' dependency region and conservatively dirty any call site whose target set changed.

Prior art: Reviser (Arzt & Bodden, ICSE '14) does exactly this — incrementally updating IFDS/IDE data-flow (FlowDroid taint) in response to program changes; also IncA and the incremental-IFDS line. The summary-edge dependency is precisely what they re-tabulate.

Net: function-local layers are free to incrementalize; the summary layer is an incremental fixpoint over the dirty cone (cheap for typical edits, full-cone rebuild on deletion); points-to is the only genuinely non-local piece and bounds how tight the incrementality gets. Same machinery as the parallel batch build — seed = dirty set instead of all nodes.

[rahlk]

Reviser-style incremental analysis (detailed)

Expands the incremental bullet in the parallel+incremental note. Reviser (Arzt & Bodden, ICSE '14) is the canonical method for updating IFDS/IDE taint (it ships in FlowDroid) on program changes; we adopt its structure for our SDG summary edges. Key property: incremental results are identical to from-scratch — it's an optimization, not an approximation.

Two-phase update: clear → recompute

A diff yields changed / added / removed callables. Reviser's core insight: additions are monotone (easy — just keep solving), but removals are non-monotone (you must retract derived facts). So the update splits:

Phase 1 — clear (retract) the affected region.

• For each changed/removed callable C: drop C's cached PDG + summary.
• Using a dependency map calleeSig → {callers that consumed its summary}, transitively clear the summaries of callers that folded in C's old summary — bounded by reverse reachability in the call graph, not the whole program.
• Removed callable → also delete its SDG nodes/edges and dirty its callers.

Phase 2 — recompute (delta).

• Recompute the intraprocedural PDG for changed/added callables only.
• Re-run the summary fixpoint seeded with the cleared set, in reverse-topo order, reusing every still-valid cached summary.
• Early cutoff: when a recomputed summary equals the cleared one, stop propagating to its callers — the change didn't escape.

Why removal is the hard direction

Adds/edits grow the analysis (monotone) → continue the worklist from new seeds. Removing code/edges can shrink a summary, which monotone propagation can't undo — hence clear-then-recompute over the bounded cone. Reviser's contribution is doing this precisely (dependency-tracked) instead of reanalyzing everything; we inherit that precision from the dependency map + the hash(body) + hash(consumed callee summaries) cache key.

Enabling data structures

• Reverse dependency map calleeSig → set<callerSig> — which callers consumed each summary; built during the batch fixpoint.
• Per-callable cache keyed hash(body) + hash(consumed callee summaries). A summary is reused iff its body and all consumed callee summaries are unchanged.
• Diff → callables: git line ranges ∩ symbol_table callable spans → the dirty seed set.

Granularity choice

Reviser operates at CFG-edge granularity within methods; we go callable-granularity (recompute a changed callable's whole PDG) for simplicity — coarser but functions are small, and it avoids intra-method delta bookkeeping. Revisit only if single huge functions dominate runtime.

Net: same fixpoint as the parallel batch build; incremental = run Phase-1 retraction, then seed Phase-2 with the dirty cone. Soundness and precision identical to full reanalysis; points-to refresh (Jelly) remains the non-local caveat noted earlier.

[rahlk]

Rounded-out design + how taint runs on the SDK side

Design summary

Concern	Decision
Representation	SDG + symbol_table (no full CPG): symbol_table = AST/declaration layer, SDG = PDG + summary edges, CFG transient
Engine	reaching-defs DDG (flow-sensitive, kills baked in) + control-dependence (implicit flows, deferred) + SDG summary edges (context-sensitive interprocedural); Jelly for call resolution + points-to
Storage	flat top-level sdg section, signature-prefixed node IDs, per-callable pointers; graph-DB-ready (Neo4j/Kùzu LPG mapping is mechanical)
Concurrency	call-graph-scheduled parallel (SCC-DAG, reverse-topo; leaf wave embarrassingly parallel; monotone chaotic-rounds option)
Incrementality	Reviser-style dirty-cone fixpoint; function-local layers free; deletion = clear+recompute cone; points-to = non-local bound
Models	models-as-data (sources/sinks/sanitizers/rules); shared CLDK schema across the TS + Python backends

How taint runs on the SDK side

Division of labor: the analyzer builds the SDG once (expensive, cached, incremental); the SDK applies models + traverses (cheap, flexible). Models live SDK-side, so changing what counts as a source needs no re-analysis.

Two modes coexist:

• (A) Convenience / zero-config: analyzer also emits taint_flows for a default model pack → SDK reads them directly.
• (B) Primary / flexible: analyzer ships the SDG; the SDK applies user models and traverses.

Mode (B), step by step in CLDK:

1. Load sdg + symbol_table into a networkx.DiGraph — nodes carry kind / code / span / owning-callable signature; edges typed DATA_DEP / PARAM_IN / PARAM_OUT / SUMMARY / CONTROL_DEP / CALL.
2. Resolve models → nodes: match source/sink/sanitizer specs against node metadata (callee, access path, signature) → sets of source / sink / sanitizer nodes; load the source-kind→sink-kind rule table.
3. Reachability over taint-carrying edges: multi-source BFS following DATA_DEP + PARAM_IN/OUT + SUMMARY, not descending through CALL into callee bodies — the SUMMARY edge already represents the callee's effect, which is what keeps it context-sensitive. Drop paths through sanitizer nodes.
4. Filter by rules: keep a flow only if source.kind → sink.kind is an allowed rule.
5. Witnesses: the BFS path is the explanation. SUMMARY edges carry provenance (the intra-callee path that justified them), so the SDK can expand a summary into the full inter-procedural path on demand. Map nodes → symbol_table locations for reporting.

The traversal rule that preserves context-sensitivity: follow summary edges across call sites; never step into a callee body via CALL. This mirrors Horwitz–Reps–Binkley two-phase SDG slicing — with summaries materialized, a source→sink existence check collapses to plain reachability over dep + param + summary edges.

Proposed CLDK API (thin wrappers over networkx):

a = CLDK(language="typescript").analysis(
        project_path="…", analysis_level=AnalysisLevel.call_graph)

dfg   = a.get_data_flow_graph()                     # networkx.DiGraph, like get_call_graph()
flows = a.taint_flows(sources=SRC, sinks=SNK,       # models applied HERE, at query time
                      sanitizers=SAN)               # sensible defaults if omitted
a.flows_to(node)                                    # nx.ancestors over DATA_DEP/SUMMARY

The same query is expressible as Cypher if the SDG is exported to Neo4j/Kùzu.

Net: the analyzer does the heavy, language-specific, context-sensitive work once (and incrementally); the SDK is a thin, language-agnostic, model-driven traversal re-runnable with different specs at zero analysis cost. That is the CLDK thesis applied to taint — and because the model schema is shared, the same SDK call shape works against the Python backend (codeanalyzer-python#31).