SBOM Lineage Graph Architecture

Technical architecture for the SBOM lineage graph in the Stella Ops release control plane. Audience: backend and frontend engineers building or consuming lineage queries, plus auditors who need to trace how SBOM and VEX evidence evolves across image versions. For the owning service, persistence, and API authorization model, see the SBOM Service architecture.

Overview

The SBOM Lineage Graph provides a Git-like visualization of container image ancestry with hover-to-proof micro-interactions. It enables auditors and developers to explore SBOM and VEX deltas across artifact versions, turning evidence into an explorable experience.

This document describes the lineage data model, persistence, query APIs, caching, and real-time streaming. The lineage code ships in the StellaOps.SbomService.Lineage library and its MVC controllers; the host-level minimal-API routes and the canonical authorization model are owned by the SBOM Service and documented in the parent architecture doc.

Core Concepts

Lineage Graph

A directed acyclic graph (DAG) where:

• Nodes represent artifact versions (SBOM snapshots)
• Edges represent relationships between versions

Edge Types

Node Attributes

┌─────────────────────────────────────┐
│ Node: sha256:abc123...              │
├─────────────────────────────────────┤
│ Artifact: registry/app:v1.2         │
│ Sequence: 42                        │
│ Created: 2025-12-28T10:30:00Z       │
│ Source: scanner                     │
├─────────────────────────────────────┤
│ Badges:                             │
│  • 3 new vulns (🔴)                 │
│  • 2 resolved (🟢)                  │
│  • signature ✓                      │
├─────────────────────────────────────┤
│ Replay Hash: sha256:def456...       │
└─────────────────────────────────────┘

Data Flow

┌──────────────┐     ┌─────────────────┐     ┌──────────────────┐
│   Scanner    │────▶│   SbomService   │────▶│   VexLens        │
│              │     │                 │     │                  │
│ • OCI Parse  │     │ • Ledger Store  │     │ • Consensus      │
│ • Ancestry   │     │ • Edge Persist  │     │ • Delta Compute  │
│ • SBOM Gen   │     │ • Diff Engine   │     │ • Status Track   │
└──────────────┘     └─────────────────┘     └──────────────────┘
        │                    │                       │
        └────────────────────┼───────────────────────┘
                             ▼
                    ┌─────────────────┐
                    │   Lineage API   │
                    │                 │
                    │ • Graph Query   │
                    │ • Diff Compute  │
                    │ • Export Pack   │
                    └─────────────────┘
                             │
                             ▼
                    ┌─────────────────┐
                    │   Frontend UI   │
                    │                 │
                    │ • Lane View     │
                    │ • Hover Cards   │
                    │ • Compare Mode  │
                    └─────────────────┘

Component Architecture

1. OCI Ancestry Extractor (Scanner)

Extracts parent/base image information from OCI manifests.

public interface IOciAncestryExtractor
{
    ValueTask<OciAncestry> ExtractAncestryAsync(
        string imageReference,
        CancellationToken cancellationToken);
}

public sealed record OciAncestry(
    string ImageDigest,
    string? BaseImageDigest,
    string? BaseImageRef,
    IReadOnlyList<string> LayerDigests,
    IReadOnlyList<OciHistoryEntry> History);

public sealed record OciHistoryEntry(
    string CreatedBy,
    DateTimeOffset Created,
    bool EmptyLayer);

Implementation Notes:

• Parse OCI image config history field
• Extract FROM instruction from first non-empty layer
• Handle multi-stage builds by tracking layer boundaries
• Fall back to layer digest heuristics when history unavailable

2. Lineage Edge Repository (SbomService)

Persists relationships between artifact versions.

public interface ISbomLineageEdgeRepository
{
    ValueTask<LineageEdge> AddAsync(
        LineageEdge edge,
        CancellationToken cancellationToken);

    ValueTask<IReadOnlyList<LineageEdge>> GetChildrenAsync(
        string parentDigest,
        Guid tenantId,
        CancellationToken cancellationToken);

    ValueTask<IReadOnlyList<LineageEdge>> GetParentsAsync(
        string childDigest,
        Guid tenantId,
        CancellationToken cancellationToken);

    ValueTask<LineageGraph> GetGraphAsync(
        string artifactDigest,
        Guid tenantId,
        int maxDepth,
        CancellationToken cancellationToken);
}

public sealed record LineageEdge(
    Guid Id,
    string ParentDigest,
    string ChildDigest,
    LineageRelationship Relationship,
    Guid TenantId,
    DateTimeOffset CreatedAt);

public enum LineageRelationship
{
    Parent,
    Build,
    Base
}

3. VEX Delta Repository (SbomService Lineage)

Tracks VEX status changes between artifact versions. The lineage graph uses its own IVexDeltaRepository in StellaOps.SbomService.Lineage/Repositories/, distinct from the like-named repository in the Concelier/Excititor persistence library.

public interface IVexDeltaRepository
{
    ValueTask<VexDelta> AddAsync(
        VexDelta delta,
        CancellationToken cancellationToken);

    ValueTask<IReadOnlyList<VexDelta>> GetDeltasAsync(
        string fromDigest,
        string toDigest,
        Guid tenantId,
        CancellationToken cancellationToken);

    ValueTask<IReadOnlyList<VexDelta>> GetDeltasByCveAsync(
        string cve,
        Guid tenantId,
        int limit,
        CancellationToken cancellationToken);
}

public sealed record VexDelta(
    Guid Id,
    string FromArtifactDigest,
    string ToArtifactDigest,
    string Cve,
    VexStatus FromStatus,
    VexStatus ToStatus,
    VexDeltaRationale Rationale,
    string ReplayHash,
    string? AttestationDigest,
    Guid TenantId,
    DateTimeOffset CreatedAt);

public sealed record VexDeltaRationale(
    string Reason,
    string? EvidenceLink,
    IReadOnlyDictionary<string, string> Metadata);

4. SBOM-Verdict Link Repository (SbomService)

Links SBOM versions to VEX consensus decisions.

public interface ISbomVerdictLinkRepository
{
    ValueTask LinkAsync(
        SbomVerdictLink link,
        CancellationToken cancellationToken);

    ValueTask<IReadOnlyList<SbomVerdictLink>> GetVerdictsBySbomAsync(
        Guid sbomVersionId,
        Guid tenantId,
        CancellationToken cancellationToken);

    ValueTask<IReadOnlyList<SbomVerdictLink>> GetSbomsByCveAsync(
        string cve,
        Guid tenantId,
        int limit,
        CancellationToken cancellationToken);
}

public sealed record SbomVerdictLink(
    Guid SbomVersionId,
    string Cve,
    Guid ConsensusProjectionId,
    VexStatus VerdictStatus,
    decimal ConfidenceScore,
    Guid TenantId,
    DateTimeOffset LinkedAt);

5. Lineage Graph Service (SbomService)

Orchestrates lineage queries and diff computation.

public interface ILineageGraphService
{
    ValueTask<LineageGraphResponse> GetLineageAsync(
        string artifactDigest,
        Guid tenantId,
        LineageQueryOptions options,
        CancellationToken cancellationToken);

    ValueTask<LineageDiffResponse> GetDiffAsync(
        string fromDigest,
        string toDigest,
        Guid tenantId,
        CancellationToken cancellationToken);

    ValueTask<LineageCompareResponse> CompareAsync(
        string digestA,
        string digestB,
        Guid tenantId,
        CancellationToken cancellationToken);
}

public sealed record LineageQueryOptions(
    int MaxDepth = 10,
    bool IncludeVerdicts = true,
    bool IncludeBadges = true);

Database Schema

Schema namespace. The DDL below uses unqualified table names for readability. In the live StellaOps.SbomService.Lineage EF Core migration these tables are schema-qualified and carry row-level-security tenant-isolation policies: sbom.sbom_lineage_edges, sbom.sbom_verdict_links, and vex.vex_deltas. They are distinct from the host-owned sbom.lineage_edges / sbom.verdict_links tables. See SBOM Service — Durable state for the authoritative table inventory.

sbom_lineage_edges

CREATE TABLE sbom_lineage_edges (
    id UUID PRIMARY KEY DEFAULT gen_random_uuid(),
    parent_digest TEXT NOT NULL,
    child_digest TEXT NOT NULL,
    relationship TEXT NOT NULL CHECK (relationship IN ('parent', 'build', 'base')),
    tenant_id UUID NOT NULL,
    created_at TIMESTAMPTZ NOT NULL DEFAULT NOW(),
    UNIQUE (parent_digest, child_digest, tenant_id)
);

CREATE INDEX idx_lineage_edges_parent ON sbom_lineage_edges(parent_digest, tenant_id);
CREATE INDEX idx_lineage_edges_child ON sbom_lineage_edges(child_digest, tenant_id);
CREATE INDEX idx_lineage_edges_created ON sbom_lineage_edges(tenant_id, created_at DESC);

vex_deltas

CREATE TABLE vex_deltas (
    id UUID PRIMARY KEY DEFAULT gen_random_uuid(),
    from_artifact_digest TEXT NOT NULL,
    to_artifact_digest TEXT NOT NULL,
    cve TEXT NOT NULL,
    from_status TEXT NOT NULL,
    to_status TEXT NOT NULL,
    rationale JSONB NOT NULL DEFAULT '{}',
    replay_hash TEXT NOT NULL,
    attestation_digest TEXT,
    tenant_id UUID NOT NULL,
    created_at TIMESTAMPTZ NOT NULL DEFAULT NOW(),
    UNIQUE (from_artifact_digest, to_artifact_digest, cve, tenant_id)
);

CREATE INDEX idx_vex_deltas_to ON vex_deltas(to_artifact_digest, tenant_id);
CREATE INDEX idx_vex_deltas_cve ON vex_deltas(cve, tenant_id);
CREATE INDEX idx_vex_deltas_created ON vex_deltas(tenant_id, created_at DESC);

sbom_verdict_links

CREATE TABLE sbom_verdict_links (
    sbom_version_id UUID NOT NULL,
    cve TEXT NOT NULL,
    consensus_projection_id UUID NOT NULL,
    verdict_status TEXT NOT NULL,
    confidence_score DECIMAL(5,4) NOT NULL,
    tenant_id UUID NOT NULL,
    linked_at TIMESTAMPTZ NOT NULL DEFAULT NOW(),
    PRIMARY KEY (sbom_version_id, cve, tenant_id)
);

CREATE INDEX idx_verdict_links_cve ON sbom_verdict_links(cve, tenant_id);
CREATE INDEX idx_verdict_links_projection ON sbom_verdict_links(consensus_projection_id);

API Endpoints

GET /api/v1/lineage/{artifactDigest}

Returns the lineage graph for an artifact.

Response:

{
  "artifact": "sha256:abc123...",
  "nodes": [
    {
      "id": "550e8400-e29b-41d4-a716-446655440000",
      "digest": "sha256:abc123...",
      "artifactRef": "registry/app:v1.2",
      "sequenceNumber": 42,
      "createdAt": "2025-12-28T10:30:00Z",
      "source": "scanner",
      "badges": {
        "newVulns": 3,
        "resolvedVulns": 2,
        "signatureStatus": "valid"
      },
      "replayHash": "sha256:def456..."
    }
  ],
  "edges": [
    {
      "from": "sha256:parent...",
      "to": "sha256:abc123...",
      "relationship": "parent"
    }
  ]
}

GET /api/v1/lineage/diff

Returns component and VEX diffs between two versions.

Query Parameters:

• from - Source artifact digest
• to - Target artifact digest

Response:

{
  "sbomDiff": {
    "added": [
      {"purl": "pkg:npm/lodash@4.17.21", "version": "4.17.21", "license": "MIT"}
    ],
    "removed": [
      {"purl": "pkg:npm/lodash@4.17.20", "version": "4.17.20", "license": "MIT"}
    ],
    "versionChanged": [
      {"purl": "pkg:npm/axios@1.6.0", "fromVersion": "1.5.0", "toVersion": "1.6.0"}
    ]
  },
  "vexDiff": [
    {
      "cve": "CVE-2024-1234",
      "fromStatus": "affected",
      "toStatus": "not_affected",
      "reason": "Component removed",
      "evidenceLink": "/evidence/abc123"
    }
  ],
  "reachabilityDiff": [
    {
      "cve": "CVE-2024-5678",
      "fromStatus": "reachable",
      "toStatus": "unreachable",
      "pathsRemoved": 3,
      "gatesAdded": ["auth_required"]
    }
  ],
  "replayHash": "sha256:ghi789..."
}

POST /api/v1/lineage/export

Exports a signed lineage evidence pack for artifact(s).

Fail-closed. Export succeeds only when both durable export storage and a real signer are configured (SbomService:LineageExport:StorageRootPath plus a registered StellaOps.Provenance.Attestation.ISigner). Otherwise the endpoint returns 501 sbom_lineage_export_unsupported. The service never emits synthetic download URLs or zero-byte packs. A 50 MB payload cap applies (413). See SBOM Service — Truthful unsupported surface.

Request:

{
  "artifactDigests": ["sha256:abc123..."],
  "includeAttestations": true,
  "sign": true
}

Response: The downloadUrl compatibility field carries the durable content-addressed cas://sbom-lineage-export/... URI also returned in storageUri; it is not a direct download endpoint.

{
  "downloadUrl": "cas://sbom-lineage-export/sha256:bundle...",
  "storageUri": "cas://sbom-lineage-export/sha256:bundle...",
  "bundleDigest": "sha256:bundle...",
  "expiresAt": "2025-12-28T11:30:00Z"
}

GET /api/v1/lineage/stream

Subscribe to real-time lineage updates via Server-Sent Events (SSE).

Query Parameters:

• watchDigests (optional): Comma-separated list of digests to filter updates.

Response: SSE stream with events:

event: lineage-update
data: {"id":"uuid","type":"SbomAdded","digest":"sha256:...","timestamp":"...","data":{...}}

Event Types:

• SbomAdded - New SBOM version created
• VexChanged - VEX status changed for a component
• ReachabilityUpdated - Reachability analysis completed
• EdgeChanged - Lineage edge added/removed
• Heartbeat - Keep-alive ping

GET /api/v1/lineage/{artifactDigest}/optimized

Get paginated and depth-pruned lineage graph for performance.

Query Parameters:

• maxDepth (optional, default: 3): Maximum traversal depth
• pageSize (optional, default: 50): Nodes per page
• pageNumber (optional, default: 0): Zero-indexed page number
• searchTerm (optional): Filter nodes by name

Response:

{
  "centerDigest": "sha256:abc123...",
  "nodes": [...],
  "edges": [...],
  "boundaryNodes": [
    {"digest": "sha256:...", "hiddenChildrenCount": 5, "hiddenParentsCount": 0}
  ],
  "totalNodes": 150,
  "hasMorePages": true,
  "pageNumber": 0,
  "pageSize": 50
}

GET /api/v1/lineage/{artifactDigest}/levels

Progressive level-by-level graph traversal via SSE.

Query Parameters:

• direction (optional, default: “Children”): Traversal direction (Children/Parents/Center)
• maxDepth (optional, default: 5): Maximum depth to traverse

Response: SSE stream with level events:

event: level
data: {"depth":0,"nodes":[...],"isComplete":true}

event: level
data: {"depth":1,"nodes":[...],"isComplete":true}

event: complete
data: {"status":"done"}

GET /api/v1/lineage/{artifactDigest}/metadata

Get cached metadata about a lineage graph.

Response:

{
  "centerDigest": "sha256:abc123...",
  "totalNodes": 150,
  "totalEdges": 175,
  "maxDepth": 8,
  "computedAt": "2025-12-28T10:30:00Z"
}

Caching Strategy

Hover Card Cache (Valkey)

• Key: lineage:hover:{sha256(tenantId)}:{sha256(normalizedFullFromDigest)}:{sha256(normalizedFullToDigest)}
• TTL: 5 minutes
• Invalidation: Tenant-fenced pattern deletion for either digest position on new SBOM version or VEX update
• Latency objective: <150ms cached response time; requires live acceptance proof
• Runtime binding: production-like hosts register this cache only when SbomService:HoverCache:UseDistributed=true. It consumes the single StellaOps.Messaging.Abstractions.IDistributedCacheFactory registered by the signed Router messaging transport; it does not compose a second Valkey client. The in-memory implementation is restricted to the explicit Development/Testing local harness (SbomService:LocalHarness:Enabled=true or the DevelopmentLocalHarness / TestingLocalHarness host environments).

Compare Cache (Valkey)

• Key: lineage:compare:{sha256(tenantId)}:{sha256(normalizedFullFromDigest)}:{sha256(normalizedFullToDigest)}; the from -> to order is preserved
• TTL: 10 minutes
• Invalidation: Tenant-fenced pattern deletion on new VEX data for either artifact, plus whole-tenant invalidation
• Runtime binding: production-like hosts register this cache only when SbomService:CompareCache:UseDistributed=true and use the same signed Router messaging factory as hover cards. The in-memory implementation is restricted to the explicit Development/Testing local harness (SbomService:LocalHarness:Enabled=true or the DevelopmentLocalHarness / TestingLocalHarness host environments).
• Failure behavior: Read errors are misses and fall through to authoritative computation. Invalidation errors propagate and do not increment the successful-invalidation counter. Enabling either distributed cache without an admitted messaging factory does not select an implicit standalone backend.

Graph Metadata Cache (Valkey)

• Key: lineage:metadata:{tenantId}:{centerDigest}
• TTL: 10 minutes
• Contents: Node count, edge count, max depth
• Invalidation: On lineage edge changes via DELETE /api/v1/lineage/{digest}/cache

Optimization Cache

The LineageGraphOptimizer uses IDistributedCache to store:

• Pre-computed metadata for large graphs
• BFS distance calculations
• Pagination state for consistent paging

Real-Time Streaming Architecture

LineageStreamService

Provides Server-Sent Events (SSE) for real-time lineage updates:

public interface ILineageStreamService
{
    IAsyncEnumerable<LineageUpdateEvent> SubscribeAsync(
        Guid tenantId,
        IReadOnlyList<string>? watchDigests = null,
        CancellationToken ct = default);

    Task NotifySbomAddedAsync(Guid tenantId, string artifactDigest, 
        string? parentDigest, SbomVersionSummary summary, CancellationToken ct);

    Task NotifyVexChangedAsync(Guid tenantId, string artifactDigest, 
        VexChangeData change, CancellationToken ct);

    Task NotifyReachabilityUpdatedAsync(Guid tenantId, string artifactDigest, 
        ReachabilityUpdateData update, CancellationToken ct);

    Task NotifyEdgeChangedAsync(Guid tenantId, string fromDigest, 
        string toDigest, LineageEdgeChangeType changeType, CancellationToken ct);
}

Implementation:

• Uses Channel<T> for tenant-scoped subscription management
• Bounded channels with DropOldest policy to handle slow consumers
• Optional digest filtering for targeted subscriptions
• Automatic subscription cleanup on disconnect

LineageGraphOptimizer

Optimizes large graphs for UI performance:

public interface ILineageGraphOptimizer
{
    OptimizedLineageGraph Optimize(LineageOptimizationRequest request);

    IAsyncEnumerable<LineageLevel> TraverseLevelsAsync(
        string centerDigest,
        ImmutableArray<LineageNode> nodes,
        ImmutableArray<LineageEdge> edges,
        TraversalDirection direction,
        int maxDepth = 10,
        CancellationToken ct = default);

    Task<LineageGraphMetadata> GetOrComputeMetadataAsync(
        Guid tenantId, string centerDigest,
        ImmutableArray<LineageNode> nodes,
        ImmutableArray<LineageEdge> edges,
        CancellationToken ct);
}

Optimization Features:

1. Depth Pruning: BFS-based distance computation from center node
2. Search Filtering: Case-insensitive node name matching
3. Pagination: Stable ordering with configurable page size
4. Boundary Detection: Identifies nodes with hidden children for expand-on-demand UI
5. Level Traversal: Progressive rendering via async enumerable

Determinism Guarantees

1. Node Ordering: Sorted by sequenceNumber DESC, then createdAt DESC
2. Edge Ordering: Sorted by (from, to, relationship) lexicographically
3. Component Diff: Components sorted by purl (ordinal)
4. VEX Diff: Sorted by cve (ordinal)
5. Replay Hash: SHA256 of deterministically serialized inputs

Security Considerations

1. Tenant Isolation: All live host queries apply unconditional tenant_id predicates. The host-owned lineage tables currently rely on application-level predicates rather than PostgreSQL RLS; the persistence tests prove cross-tenant read/traversal/delete isolation.
2. Digest Validation: Verify artifact digest format before queries.
3. Rate Limiting: Apply per-tenant rate limits on graph queries.
4. Export Authorization: The live minimal-API POST /api/v1/lineage/export route requires the authenticated Sbom.Attest policy (sbom:attest) and binds the request tenant to the canonical stellaops:tenant claim. The obsolete unmapped MVC lineage controllers were removed in BL-3. See SBOM Service - Authentication and authorization model.

Metrics

Error Handling

Related Documentation

• SBOM Service Architecture — owning service, persistence, and authorization model
• SBOM Lineage Ledger Guide — version history, deterministic diffs, and lineage edges
• Lineage Graph UI Architecture — lane view, hover cards, and compare mode
• SBOM Sources Architecture — ingestion pathways feeding the lineage graph