Hybrid Reachability Attestation (Graph + Edge-Bundle)

Decision date: 2025-12-11 · Owners: Scanner Guild, Attestor Guild, Signals Guild, Policy Guild

Audience: Scanner, Attestor, Signals, and Policy contributors producing or verifying signed reachability evidence, plus auditors validating it offline.

This guide defines how Stella Ops seals reachability evidence with DSSE at two levels — a required graph-level envelope and optional, selective edge-level bundles — and how producers, consumers, and verifiers handle each. It includes the CAS layout, deployment-tier budgets, CLI verification UX, and offline replay steps.

0. Context: Four Capabilities

This document supports Signed Reachability — one of four capabilities Stella Ops combines that few competitors offer together:

1. Signed Reachability – Every reachability graph is sealed with DSSE; optional edge-bundle attestations for runtime/init/contested paths. Both static call-graph edges and runtime-derived edges can be attested—true hybrid reachability.
2. Deterministic Replay – Scans run bit-for-bit identical from frozen feeds and analyzer manifests.
3. Explainable Policy (Lattice VEX) – Evidence-linked VEX decisions with explicit “Unknown” state handling.
4. Sovereign + Offline Operation – FIPS/eIDAS/GOST/SM/PQC profiles and offline mirrors as first-class toggles.

All evidence is sealed in Decision Capsules for audit-grade reproducibility.

1. Purpose

• Guarantee replayable, signed reachability evidence with graph-level DSSE for every scan while enabling selective edge-level DSSE bundles when finer provenance or dispute handling is required.
• Keep CI/offline bundles lean (graph-first), but allow auditors/regulators to quarantine or prove individual edges without regenerating whole graphs.
• Support hybrid reachability by attesting both static call-graph edges and runtime-derived edges.

2. Attestation levels

• Level 0 (Graph DSSE) — Required
  • Payload: canonical richgraph-v1 (nodes, edges, roots, graph_hash, analyzer metadata, policy_hash).
  • Signature: one DSSE envelope per graph; submit digest to Rekor (or mirror) always.
  • CAS: cas://reachability/graphs/{blake3} (body) + cas://reachability/graphs/{blake3}.dsse (envelope).
• Level 1 (Edge-Bundle DSSE) — Optional/Selective
  • Payload: batch of edges (size ≤ 512) with per-edge reason, evidence hashes, symbol_digest, purl, confidence, and phase.
  • Criteria to emit bundles:
    • Edge reason is runtime, init_array/constructors/TLS callbacks, or comes from third-party provenance.
    • Edge is contested/flagged in Unknowns registry or under policy quarantine.
  • Signature: one DSSE envelope per bundle; Rekor submission configurable (default on for contested/high-risk bundles, off for bulk benign bundles in sealed mode).
  • CAS: cas://reachability/edges/{graph_hash}/{bundle_id} JSON + .../{bundle_id}.dsse.

3. Producer responsibilities

• Scanner
  • Always emit Level 0 graph + manifest.
  • When criteria match, emit Level 1 bundles; include bundle_reason (e.g., runtime-hit, init-root, third-party, disputed).
  • Canonicalise JSON (sorted keys/arrays) before hashing; BLAKE3 as graph hash, SHA-256 inside bundles.
  • For hybrid reachability: tag edges with source: static or source: runtime to distinguish call-graph derived vs. runtime-observed edges.
• Attestor/Signer
  • Apply DSSE for both levels; respect sovereign crypto modes (FIPS/GOST/SM/PQC) from environment.
  • Rekor: push graph envelope digests; push edge-bundle digests only when rekor_publish=true (policy/default for high-risk bundles).

4. Consumer responsibilities

• Signals
  • Ingest graph DSSE as the canonical source; ingest edge-bundles when present and attach to the same graph_hash.
  • Store per-edge DSSE metadata for quarantine/override flows; surface missing edges as Unknowns only when absent from both graph and bundles.
• Policy
  • Default trust path: graph DSSE + CAS object.
  • When an edge is quarantined/contested, drop it from consideration if an edge-bundle DSSE marks it revoked=true or if the Unknowns registry lists it with policy quarantine flag.
  • For “evidence-required” rules, require either (a) graph DSSE + policy_hash match or (b) edge-bundle DSSE that covers the vulnerable path edges.
• Replay/Bench/CLI
  • stella graph verify should accept --graph {hash} and optional --edge-bundles to validate deeper provenance offline.

5. Verification and quarantine flows

• Happy path: verify graph DSSE → verify Rekor inclusion (or mirror) → hash graph body → match graph_hash in policy/replay manifest → accept.
• Dispute/quarantine: mark specific edge_id as revoked in an edge-bundle DSSE; Policy/Signals exclude it, recompute reachability, and surface delta in explainers.
• Offline: retain graph DSSE and selected edge-bundles inside replay pack; Rekor proofs cached when available.
• Sovereign Verification Mode: Even with no internet, all signatures and transparency proofs can be locally verified using Offline Update Kits.

6. Performance & storage guardrails

• Default: only graph DSSE is mandatory; edge-bundles capped at 512 edges per envelope and emitted only on criteria above.
• Rekor flood control: cap edge-bundle Rekor submissions per graph (config reachability.edgeBundles.maxRekorPublishes, default 5). Others stay CAS-only.
• Determinism: bundle ordering = stable sort by (bundle_reason, edge_id); hash before signing.

7. Hybrid Reachability Details

Stella Ops provides true hybrid reachability by combining:

Why hybrid matters:

• Static analysis catches code paths that may not execute during observed runtime
• Runtime analysis catches dynamic dispatch, reflection, and framework-injected paths
• Combining both provides confidence across build and runtime contexts
• Each edge type is separately attestable for audit and dispute resolution

Evidence linking: Each edge in the graph or bundle includes evidenceRefs pointing to the underlying proof artifacts (static analysis artifacts, runtime traces), enabling evidence-linked VEX decisions.

8. Decisions (Frozen 2025-12-13)

8.1 DSSE/Rekor Budget by Deployment Tier

Budget enforcement:

• Graph DSSE: Always submit digest to Rekor (or offline checkpoint for air-gapped)
• Edge-bundle DSSE: Submit to Rekor only when bundle_reason is disputed, runtime-hit, or security-critical
• Cap enforced by reachability.edgeBundles.maxRekorPublishes config (per tier defaults above)

8.2 Signing Layout and CAS Paths

cas://reachability/
  graphs/
    {blake3}/                  # richgraph-v1 body (JSON)
    {blake3}.dsse              # Graph DSSE envelope
    {blake3}.rekor             # Rekor inclusion proof (optional)
  edges/
    {graph_hash}/
      {bundle_id}.json         # Edge bundle body
      {bundle_id}.dsse         # Edge bundle DSSE envelope
      {bundle_id}.rekor        # Rekor inclusion proof (if published)
  revisions/
    {revision_id}/             # Revision manifest + lineage

Signing workflow:

1. Canonicalize richgraph-v1 JSON (sorted keys, arrays by deterministic key)
2. Compute BLAKE3-256 hash -> graph_hash
3. Create DSSE envelope with stella.ops/graph@v1 predicate
4. Submit digest to Rekor (online) or cache checkpoint (offline)
5. Store graph body + envelope + proof in CAS

8.3 CLI UX for Selective Bundle Verification

# Verify graph DSSE only (default)
stella graph verify --hash blake3:a1b2c3d4...

# Verify graph + all edge bundles
stella graph verify --hash blake3:a1b2c3d4... --include-bundles

# Verify specific edge bundle
stella graph verify --hash blake3:a1b2c3d4... --bundle bundle:001

# Offline verification with local CAS
stella graph verify --hash blake3:a1b2c3d4... --cas-root ./offline-cas/

# Verify Rekor inclusion
stella graph verify --hash blake3:a1b2c3d4... --rekor-proof

# Output formats
stella graph verify --hash blake3:a1b2c3d4... --format json|table|summary

8.4 Golden Fixture Plan

Fixture location: tests/Reachability/Hybrid/

Required fixtures:

CI integration:

• .gitea/workflows/hybrid-attestation.yml runs verification fixtures
• Size gate: Graph body < 10MB, individual bundle < 1MB
• Time gate: Full verification < 5s for standard tier

8.5 Implementation Status

9. Verification Runbook

This section provides step-by-step guidance for verifying hybrid attestations in different scenarios.

9.1 Graph-Only Verification

Use this workflow when only graph-level attestation is required (default for most use cases).

Prerequisites:

• Access to CAS storage (local or remote)
• stella CLI installed
• Optional: Rekor instance access for transparency verification

Steps:

1. Retrieve graph DSSE envelope:

   stella graph fetch --hash blake3:<graph_hash> --output ./verification/
   

2. Verify DSSE signature:

   stella graph verify --hash blake3:<graph_hash>
   # Output: ✓ Graph signature valid (key: <key_id>)
   

3. Verify content integrity:

   stella graph verify --hash blake3:<graph_hash> --check-content
   # Output: ✓ Content hash matches BLAKE3:<graph_hash>
   

4. Verify Rekor inclusion (online):

   stella graph verify --hash blake3:<graph_hash> --rekor-proof
   # Output: ✓ Rekor inclusion verified (log index: <index>)
   

5. Verify policy hash binding:

   stella graph verify --hash blake3:<graph_hash> --policy-hash sha256:<policy_hash>
   # Output: ✓ Policy hash matches graph metadata
   

9.2 Graph + Edge-Bundle Verification

Use this workflow when finer-grained verification of specific edges is required.

When to use:

• Auditing runtime-observed paths
• Investigating contested/disputed edges
• Verifying init-section or TLS callback roots
• Regulatory compliance requiring edge-level attestation

Steps:

1. List available edge bundles:

   stella graph bundles --hash blake3:<graph_hash>
   # Output:
   # Bundle ID          Reason          Edges  Rekor
   # bundle:001         runtime-hit     42     ✓
   # bundle:002         init-root       15     ✓
   # bundle:003         third-party     128    -
   

2. Verify specific bundle:

   stella graph verify --hash blake3:<graph_hash> --bundle bundle:001
   # Output:
   # ✓ Bundle DSSE signature valid
   # ✓ All 42 edges link to graph_hash
   # ✓ Rekor inclusion verified
   

3. Verify all bundles:

   stella graph verify --hash blake3:<graph_hash> --include-bundles
   # Output:
   # ✓ Graph signature valid
   # ✓ 3 bundles verified (185 edges total)
   

4. Check for revoked edges:

   stella graph verify --hash blake3:<graph_hash> --check-revoked
   # Output:
   # ⚠ 2 edges marked revoked in bundle:002
   #   - edge:func_a→func_b (reason: policy-quarantine)
   #   - edge:func_c→func_d (reason: revoked)
   

9.3 Verification Decision Matrix

10. Rekor Guidance

10.1 Rekor Integration Overview

Rekor provides an immutable transparency log for attestation artifacts. StellaOps integrates with Rekor (or compatible mirrors) to provide verifiable timestamps and inclusion proofs.

10.2 What Gets Published to Rekor

10.3 Rekor Configuration

# etc/signals.yaml
reachability:
  rekor:
    enabled: true
    endpoint: "https://rekor.sigstore.dev"  # Or private mirror
    timeout: 30s
    retry:
      attempts: 3
      backoff: exponential
  edgeBundles:
    maxRekorPublishes: 5  # Per graph, configurable by tier
    publishReasons:
      - disputed
      - runtime-hit
      - security-critical

10.4 Private Rekor Mirror

For air-gapped or regulated environments:

reachability:
  rekor:
    enabled: true
    endpoint: "https://rekor.internal.example.com"
    tls:
      ca: /etc/stellaops/ca.crt
      clientCert: /etc/stellaops/client.crt
      clientKey: /etc/stellaops/client.key

10.5 Rekor Proof Caching

Inclusion proofs are cached locally for offline verification:

cas://reachability/graphs/{blake3}.rekor    # Graph inclusion proof
cas://reachability/edges/{graph_hash}/{bundle_id}.rekor  # Bundle proof

Proof format:

{
  "logIndex": 12345678,
  "logId": "c0d23d6ad406973f9559f3ba2d1ca01f84147d8ffc5b8445c224f98b9591801d",
  "integratedTime": 1702492800,
  "inclusionProof": {
    "logIndex": 12345678,
    "rootHash": "abc123...",
    "treeSize": 50000000,
    "hashes": ["def456...", "ghi789..."]
  }
}

11. Offline Replay Steps

11.1 Overview

Offline replay enables full verification of reachability attestations without network access. This is essential for air-gapped deployments and regulatory compliance scenarios.

11.2 Creating an Offline Replay Pack

Step 1: Export graph and bundles

stella graph export --hash blake3:<graph_hash> \
  --include-bundles \
  --include-rekor-proofs \
  --output ./offline-pack/

Step 2: Include required artifacts The export creates:

offline-pack/
├── manifest.json              # Replay manifest v2
├── graphs/
│   └── <blake3>/
│       ├── richgraph-v1.json  # Graph body
│       ├── graph.dsse         # DSSE envelope
│       └── graph.rekor        # Inclusion proof
├── edges/
│   └── <graph_hash>/
│       ├── bundle-001.json
│       ├── bundle-001.dsse
│       └── bundle-001.rekor
├── runtime-facts/
│   └── <hash>/
│       └── runtime-facts.ndjson
└── checkpoints/
    └── rekor-checkpoint.json  # Transparency log checkpoint

Step 3: Bundle for transfer

stella offline pack --input ./offline-pack/ --output offline-replay.tgz

11.3 Verifying an Offline Pack

Step 1: Extract pack

stella offline unpack --input offline-replay.tgz --output ./verify/

Step 2: Verify manifest integrity

stella offline verify --manifest ./verify/manifest.json
# Output:
# ✓ Manifest version: 2
# ✓ Hash algorithm: blake3
# ✓ All CAS entries present
# ✓ All hashes verified

Step 3: Verify attestations offline

stella graph verify --hash blake3:<graph_hash> \
  --cas-root ./verify/ \
  --offline
# Output:
# ✓ Graph DSSE signature valid (offline mode)
# ✓ Rekor proof verified against checkpoint
# ✓ 3 bundles verified offline

11.4 Offline Verification Trust Model

┌─────────────────────────────────────────────────────────┐
│                   Offline Pack                          │
├─────────────────────────────────────────────────────────┤
│  ┌──────────────┐   ┌──────────────┐   ┌─────────────┐ │
│  │ Graph DSSE   │   │ Edge Bundle  │   │ Rekor       │ │
│  │ Envelope     │   │ DSSE         │   │ Checkpoint  │ │
│  └──────┬───────┘   └──────┬───────┘   └──────┬──────┘ │
│         │                  │                  │        │
│         ▼                  ▼                  ▼        │
│  ┌──────────────────────────────────────────────────┐  │
│  │           Local Verification Engine              │  │
│  │  1. Verify DSSE signatures against trusted keys  │  │
│  │  2. Verify content hashes match DSSE payloads    │  │
│  │  3. Verify Rekor proofs against checkpoint       │  │
│  │  4. Verify policy hash binding                   │  │
│  └──────────────────────────────────────────────────┘  │
└─────────────────────────────────────────────────────────┘

11.5 Air-Gapped Deployment Checklist

• [ ] Trusted signing keys pre-installed
• [ ] Rekor checkpoint from last sync included
• [ ] All referenced CAS artifacts bundled
• [ ] Policy hash recorded in manifest
• [ ] Analyzer manifests included for replay
• [ ] Runtime-facts artifacts included (if applicable)

12. Release Notes

12.1 Version History

12.2 Breaking Changes

None. Hybrid attestation is additive; existing graph-only workflows remain unchanged.

12.3 Migration Guide

From graph-only to hybrid:

1. No migration required for existing graphs
2. Enable edge-bundle emission in scanner config:

   scanner:
     reachability:
       edgeBundles:
         enabled: true
         emitRuntime: true
         emitContested: true
   

3. Signals automatically ingests edge bundles when present

13. Cross-References

• Sprint: docs/implplan/SPRINT_0401_0001_0001_reachability_evidence_chain.md (Tasks 53–56)
• Contracts: richgraph-v1; edge-bundle-v1 (contract pending — see flagged note below).
• Implementation:
  • Scanner: src/Scanner/__Libraries/StellaOps.Scanner.Reachability/EdgeBundle*.cs
  • Signals: src/Signals/StellaOps.Signals/Ingestion/EdgeBundleIngestionService.cs
  • Policy: src/Policy/StellaOps.Policy.Engine/Gates/PolicyGateEvaluator.cs
• Related docs:
  • Function-level evidence guide
  • Reachability lattice
  • Deterministic Replay
  • Architecture Overview