SPDX SBOMs packages, relationsships, and "the graph"

[ctron]

Right now (only considering SPDX SBOMs) we take an SBOM and extract the contained packages, if they declare a PURL. We store each PURL as "package" in a hierarchical data structure like this: qualified -> versioned -> base.

We also record the fact that packages (qualified) are present in an SBOM and that there are relationships between packages in the context of an SBOM.

There is also a bit of special handling our what "describes" the SBOM. For that we do extract the "document describes" information from the document's metadata . We do this for CPEs and PURLs.

This roughly gives the following structure:

erDiagram

QualifiedPackage {
    uuid id PK
    uuid package_version_id FK
    
    json qualifiers
}

PackageVersion {
    uuid id PK
    uuid package_id FK
    
    version string
}

Package {
    uuid id PK

    string type UK
    string namespace UK "Optional"
    string name UK
}

SbomPackage {
    int sbom_id PK, FK
    uuid package_id PK, FK "Qualified package"
}

SbomPackageRelation {
    int sbom_id FK
    uuid left FK "Qualified package"
    enum relationship
    uuid right FK "Qualified package"
}

Sbom {
    int id PK
}

SbomDescribesCpe {
    int sbom_id FK
    int cpe_id FK
}

SbomDescribesPackage {
    int sbom_id FK
    int qualified_package_id FK
}

QualifiedPackage 1+ to 1 PackageVersion : references
PackageVersion 1+ to 1 Package : references
        
SbomPackage 1+ to 1 Sbom: contains
SbomPackage 1+ to 1 QualifiedPackage: contains

SbomPackageRelation 1+ to 1 Sbom: contains
SbomPackageRelation 1+ to 1 QualifiedPackage: left
SbomPackageRelation 1+ to 1 QualifiedPackage: right

Sbom 1 to 0+ SbomDescribesCpe: describes
Sbom 1 to 0+ SbomDescribesPackage: describes

Loading

Thinking of this as a graph, in the context of an SBOM this would give us:

flowchart TD;
    SBOM-->PURL_A;
    PURL_A-->PURL_B;
    SBOM-->CPE;

Loading

Outside an SBOM, we know nothing because no relationships exist outside an SBOM.

Problem 1

We don't handle the "describes" thing correctly. There's a "document describes" field, which lists IDs (packages inside a SBOM), which the SBOM declares as "defining packages". First of all, that field may be missing. Second, that information could also come in from a relationship of the type DESCRIBES to the SPDXRef-DOCUMENT element. Currently, we do ignore this.

Problem 2

Inside a SPDX SBOM there are "packages" and "relationships". However, packages are not necessarily PURLs. They could also be CPEs, or file hashes. Also, could a relationship exist between a package and the document itself (SPDXRef-DOCUMENT).

Even more complex, a reference to an external document could exist.

Relationship: SPDXRef-DOCUMENT AMENDS DocumentRef-SPDXA:SPDXRef-DOCUMENT

Declared by (where DocumentRef-SPDXA would be DocumentRef-spdx-tool-1.2 here):

ExternalDocumentRef:DocumentRef-spdx-tool-1.2 https://spdx.org/spdxdocs/spdx-tools-v1.2-3F2504E0-4F89-41D3-9A0C-0305E82C3301 SHA1: d6a770ba38583ed4bb4525bd96e50461655d2759

We are completely ignoring this at the moment.

Also see: https://spdx.github.io/spdx-spec/v2.3/relationships-between-SPDX-elements/#1111-description
and https://spdx.github.io/spdx-spec/v2.3/document-creation-information/#66-external-document-references-field

Ideas

Assuming we keep the tree of qualified/versioned/base for PURL-based packages. We might convert this
into a graph, supporting the following nodes/edges:

SBOM -[references]-> SBOM
SBOM -[contains]-> Package

Package -[relationship]-> Package

Package --> PURL
Package --> CPE
Package --> Hash

Where Package is a package of the SBOM, and PURL is a "qualified package" without an SBOM context.

So we might have something like this (where -> denotes a reference rather than ownership):

sbomA:
  packageA1:
    -> purl1
    -> cpe1
  packageA2:
    -> sbomC
    -> packageB2[testOf]
  -> sbomB

sbomB:
  packageB1:
    -> purl1
    -> packageB2[contains]
  packageB2:
    -> purl2

sbomC:

Now what?

I don't have concrete proposals. I only think that we don't fully understand the problem yet. This is all based on SPDX, and I think that CycloneDX will be similar, bit with subtle differences.

Also, I did not check into SPDX 3.0, which indeed might be different. It looks like they go even more in that direction with RDF.

[ctron]

After some tests, here's an update:

erDiagram
    Sbom {
        int sbom_id PK "inherited"
        string id "inherited"
        string name "inherited"
        string namespace "inherited"

        uuid sha256
    }

    Package {
        int sbom_uid FK "inherited"
        string id "inherited"
        string name "inherited"
        string namespace "inherited"
    }

    Node {
        int sbom_id
        string id
        string namespace
    }
    
    Edge {
        int sbom_id
        
        string left_id
        option~string~ left_namespace
        
        enum~relationship~ type
        
        string right_id
        option~string~ right_namespace
    }

    Sbom 1 to 0+ Package : contains

    BasePurl {
        uuid id
        string type
        string name
        option~string~ namespace
    } 
    VersionedPurl {
        string version
    }
    QualifiedPurl {
        jsonb qualifiers
    }
    
    QualifiedPurl 0+ to 1 VersionedPurl: refines
    VersionedPurl 0+ to 1 BasePurl: refines
    
    CPE
    
    Package 1 optionally to 0+ QualifiedPurl: references
    Package 1 optionally to 0+ CPE: references
    
    Node 1 to zero or one Package: inherits
    Node 1 to zero or one Sbom: inherits
    
    Edge 1 to zero or one Node: left
    Edge 1 to zero or one Node: right

Loading

Most notable changes:

• We keep an "SBOM ID" which we assign to ensure we can use multiple versions of SBOMs using the same namespace
• Drop the "describes" tables, as those come with the "describes" relationship
• Create a common sbom_node table, having sbom and sbom_package inherit from those
• Have the package_relates_to_package reference entries in sbom_node

Unresolved issues:

• A relationship can point outside the current SBOM. That's indicated by the left_namespace and right_namespace:
  • It might be that both ends are external to this document. I don't think we should support this, even if the spec might.
  • How do we handle the case where the relationship points to a target for which we have multiple SBOMs?