Skip to content

Research: Heros-inspired IFDS/IDE feasibility for interprocedural ownership facts (bounded spike) #434

Open
Open
Research: Heros-inspired IFDS/IDE feasibility for interprocedural ownership facts (bounded spike)#434

Description

@PhysShell
PhysShell
opened on Oct 24, 2026

Classification

Why investigate?

Own.NET already has flow-sensitive resource states, method/effect summaries, Roslyn→OwnIR and Python/Rust core implementations. Heros is interesting for its algorithmic boundaries:

  • IFDS handles interprocedural, context-sensitive propagation of finite distributive sets of facts via normal/call/return/call-to-return flow functions.
  • IDE extends this with edge functions over a value lattice.
  • IDESolver uses path edges, end summaries and reusable jump functions; JumpFunctions provides indexed lookup.
  • Heros includes field-sensitive and bidirectional variants, but their existence does not establish complete C# aliasing or correct disposal/exception semantics.

A useful Own.NET question is not “could we implement a more sophisticated solver?”, but:

Do existing, independently verified ownership failures specifically arise from missing context-sensitive propagation or summary reuse, and are those cases faithfully representable as IFDS/IDE without weakening the conservative correctness contract?

S5 previously stopped with STOP-SOUNDNESS and showed no established incremental utility over C01 on the evaluated real programs. Complexity alone is not a product outcome.

Research questions

  1. Which of the existing acquire/release/use/escape, event +=/-=, ownership-transfer, loan/permission, and method-summary facts genuinely fit a finite distributive IFDS formulation? Which require correlated facts, richer typestate/IDE values, may/must separation, or cannot be faithfully encoded within a bounded domain?
  2. If a concrete interprocedural diagnostic error remains after Research: SootUp-inspired OwnIR/ICFG semantic-fidelity and incomplete-call audit (bounded spike) #430's source→OwnIR fidelity checks, is the first divergence in call/return propagation or summary computation, rather than missing call facts (Canonical first-party call facts: preserve interprocedural calls instead of collapsing them into frontend release/use/escape guesses #382), alias precision (Research: WALA-inspired demand-driven alias precision for ownership diagnostics (bounded spike) #429), method models (Heap-effect summaries for external code (BCL / annotations) so calls like logging can be proven harmless inside a protocol region #394/Research: OpenTaint-style contract tests and engine-gap triage for method-effect models #425), path feasibility (Research: COVA-inspired targeted path-condition oracle for ownership soundness (bounded spike) #431), or an invalid oracle?
  3. Can an independent, tiny offline tabulation reference catch a transfer/summary defect or explain a confirmed missed finding without silently turning unknown/incomplete into safe? How much does it cost?

Bounded plan

0. Pin sources, inspect existing engine, preregister cases

1. Formal expressibility audit (paper first, no code)

Write down the actual abstract domain and transfer semantics for 1–2 narrow resource protocols (e.g. disposable resource state, or event subscription with release):

  • Fact identity and zero fact, normal/call/return/call-to-return transfers; direct vs unresolved/virtual calls, recursion, return into caller and explicit source/receiver mapping.
  • Check the IFDS requirement f(A ∪ B) = f(A) ∪ f(B) on representative counterexamples, not just trivial Gen/Kill examples. Do not assume a mutually dependent ownership predicate is distributive merely by encoding it as a string. Explicitly account for correlation loss and any finite-domain explosion when using product facts.
  • If IDE is warranted, define a finite value domain, edge-function composition/join and the correctness of its lattice operations. Otherwise prefer the simpler IFDS case.
  • Document may/must and unknown semantics, alias/resource-identity requirements, bounded access paths, loops and join points. Test the difference between “witness exists” and “all feasible exits release.”
  • Enumerate unsupported C# constructs (particularly using/await using, try/finally and exceptional control flow, dynamic/virtual dispatch, opaque external effects, async/cancellation), explicitly distinguishing a missing model from a solver bug.
  • Produce an expressibility matrix: faithful IFDS, possible IDE/composite-fact trade-off, requires upstream facts/models, out of scope/unknown. “Not currently expressible” is an acceptable result.

2. Conditional minimal differential experiment

Only if phase 1 identifies an eligible, independently reproducible gap and a faithful small fact domain:

  • Build a test-only isolated reference using existing OwnIR facts/minimized ICFG, rather than touching production Rust/Python diagnostic authority. A simple hand-audited tabulation solver is preferred; do not port or depend on Heros.
  • Exercise direct calls, a wrapper/helper chain, recursion or mutual recursion, multiple callers, call-to-return bypass, distinct instances and must/may aliases, a branch join, and an exceptional cleanup path where faithfully represented.
  • Check path edges, return-context restoration, summary reuse, gen/kill, zero fact, join/edge-function laws, termination and deterministic outputs. Do not claim exception semantics based only on a CFG API with return sites.
  • Reuse Research: semantic mutation testing harness for Own.NET analyzer coverage (bounded pilot) #405's semantic mutants/metamorphic tests; use P-022 diagnostics: normalized AnalysisTrace and first-divergence minimizer for Python↔Rust shadow mode #269's first-divergence instrumentation where available. Do not build another full mutation harness, an alias-analysis framework, an SMT solver or an evidence schema.

3. Soundness and adversarial controls

  • Unresolved/opaque calls, missing callee body, incomplete CFG/ICFG, recursion/context/state budget exhaustion, timeout, unsupported C# lowering or failed analysis are never proof of safety. Preserve separate UNKNOWN/INCOMPLETE/UNSUPPORTED as appropriate within existing evidence conventions (Research: evaluate Bifrost for C# code intelligence, agent navigation, and evidence contracts #426).
  • Force an omitted call edge and a truncated worklist. Confirm the prototype does not return a complete negative/safe result.
  • Prevent both spurious “must release” claims from joined may paths and false negatives from incorrectly killing facts at calls/returns.
  • Independently adjudicate each putative TP/FP against executable/source-level C# semantics where practical, not against the reference solver's own output.
  • Keep previously confirmed positive controls and Python/Rust parity intact. No auto-suppression and no promoted confidence from prototype agreement.

4. Costs and decision

  • Compare per case: source-level oracle, current Own.NET result/evidence, prototype result, first demonstrated divergence, TP/FP/FN/unknown/completeness, worklist iterations, facts/path edges, summaries, elapsed time and peak memory (only if code is run).
  • Include at least one small pinned real-OSS slice if an eligible gap exists. No synthetic aggregate precision/recall marketing from a tiny curated corpus.
  • State what specifically is better: new independently confirmed bug, removed verified FP, repaired unjustified safe verdict, improved evidence, or merely an alternative implementation of existing behavior.
  • End with STOP / RESEARCH ONLY / FOLLOW-UP CANDIDATE. Open a separate production implementation issue only if a validated product-relevant gain outweighs cost and passes adversarial/negative controls.

Acceptance criteria

Non-goals / guardrails

No Java/Heros dependency in Own.NET, no SootUp/Jimple port, no new C# frontend, no generic IFDS/IDE or whole-program points-to platform, no wholesale ownership lattice rewrite, no reopening frozen lifecycle scope (#304), no changes to production diagnostics or default CI. Any implementation work must be independently justified by a real semantic failure, not elegance.

References

Desired outcome: a falsifiable answer about whether IFDS/IDE fixes an actual Own.NET interprocedural correctness gap. If it finds no additional real bug or precision/soundness defect, STOP; a more sophisticated solver is not itself progress.

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions