RFC: merging multiple CycloneDX documents #320

jkowalleck Oct 13, 2023
Maintainer Author

it is okay to leave this wall of text for context, but for discussion and focus purpose,
please split ask individual questions and topics. so could you extract each individual question and post it as a single item?

PS: 🔍 the original request and its details are still there and can be expanded and read by clicking the "show comment" button above".

jimklimov
Oct 13, 2023

data model:
- the JSON schema says it has a "ref" that follows "refLinkType" definition, and a "dependsOn" list of unique direct-dependency "refLinkType"s -- this is inherently a two-layer schema (ref and its dep names)
- the XML schema, and C# codebase, define the "dependencyType" as having a "ref" that follows "refLinkType" definition, and sequence of "dependency" elements that contain further "dependencyType" entries -- this potentially allows unlimited layering, only limited to two-layer by description and possibly by code implementation, but not by formal schema

1 reply

jkowalleck Oct 13, 2023
Maintainer Author

XML's (enhanced) data model of "nested" dependencies can be flattened, so it would match the one of JSON - without data loss.

jimklimov
Oct 13, 2023

list constraints:
- The array/list is to be composed of "unique" items per JSON schema.
- I did not find any xs:unique regarding dependency definitions in XML schema.

1 reply

jkowalleck Oct 13, 2023
Maintainer Author

if the dependency model was flattened, every "ref" in it MUST be unique.

jimklimov
Oct 13, 2023

type constraints:
- in JSON, specs v1.2, 1.3 and 1.4 Bom.Dependencies dealt with "components" only
- in XML since 1.2, and in JSON since 1.5, with "components or services"

1 reply

jkowalleck Oct 13, 2023
Maintainer Author

Components and services it is, for now (as of CycloneDX 1.5).
This might advance in the future.

jimklimov
Oct 13, 2023

When a particular value is mentioned in a dependency (as "ref" or as a sub-list item), MUST a component-or-service with this "bom-ref" value exist in the same Bom document?
Or may there be "dangling" references (anticipating a merge of further document, or something like a bomLinkElementType to point to an entity in a specified other Bom document)?

1 reply

jkowalleck Oct 13, 2023
Maintainer Author

MUST a component-or-service with this "bom-ref" value exist in the same Bom document?

Yes. That is the idea. Dependencies act on local references, not BOM-links.

jimklimov
Oct 13, 2023

Are dependencies required (intended even if not formalized in current schema file wordings) to be unique in terms that the list of Bom.Dependencies may only mention each value of "ref" attribute once?
OR may there be several list items with same "ref" and different "dependsOn" sub-lists?

Some precedents from experience in the field:

DependencyTrack seems to handle several copies of same refs with different sub-lists, albeit poorly - e.g. it shows them in vulnerability alerts but can not place them on a graph
cyclonedx-maven-plugin generates varying "dependsOn" sub-lists for same "ref"s, e.g. when building a maven project with a parent and some modules and having each generate an aggregate sbom file according to ecosystem-wide inherited maven recipe -- they tend to have some populated third-party dep lists for one and empty for others, or sometimes one list is a non-empty strict subset of another... I don't think I've seen it generate a dependsOn: null list so maybe dependsOn: [] is its poor placeholder for the actually unknown/"didn't care to recurse"?

2 replies

jkowalleck Oct 13, 2023
Maintainer Author

Are dependencies required (intended even if not formalized in current schema file wordings) to be unique in terms that the list of Bom.Dependencies may only mention each value of "ref" attribute once?

yes.

@wkoot

wkoot Sep 19, 2024

cyclonedx-maven-plugin generates varying "dependsOn" sub-lists for same "ref"s, e.g. when building a maven project with a parent and some modules and having each generate an aggregate sbom file according to ecosystem-wide inherited maven recipe -- they tend to have some populated third-party dep lists for one and empty for others, or sometimes one list is a non-empty strict subset of another... I don't think I've seen it generate a dependsOn: null list so maybe dependsOn: [] is its poor placeholder for the actually unknown/"didn't care to recurse"?

Why not simply omit a dependsOn placeholder, avoiding complicating type check?
Since it's optional in the spec, there already needs to be a lookup instead of assuming that the field exists.
I would strongly prefer omitting all optional fields that aren't populated; why else are they optional?

jimklimov
Oct 13, 2023

For the purposes of coherent merging, is it correct to treat an existing Dependency item as a sort of extra-corporal part of a Component or Service which it refers to? Meaning: when we compare if two Components in two Boms being merged are equivalent, should equivalence of known Dependency lists which "ref" these Components also be considered - more so if a "ref" must be specified only once?
- Is it a valid operation to merge Dependency sub-lists ("ref"ing allegedly same/mergeable Component entities in respective source Bom documents), at least if one is a strict subset of another (including explicit empty lists)? Or does the spec imply that any such non-null list is to be treated as final and immutable (does not explicitly say so, but description around "empty elements" is worded quite loudly at least)?
- The merge strategy we are after does allow for squashing together certain entries (e.g. to add license info where missing, or more hash algos+values), although my initial PRs were a bit naive about this - the real rabbit hole goes too deep as shown by nuances like these here.

3 replies

jkowalleck Oct 13, 2023
Maintainer Author

this is a critical point, people could argue.

I am far from giving a proper answer to this. I have an opinion on it:
I implemented CycloneDX data models in a way, that the set of dependencies are an actual property of component/service, meaning that components are equal, only if those dependencies are equal.

practical: if two component utilized different versions of libXML, they behave differently and are not the same, even though that the same code was used to compile those components.
So from a technical standpoint, my approach might be the correct one.

I could imagine that others would not understand why a dependency graph should matter when equality is described. So whatever solution one chose, please document it outside of the code, why you implemented it and what the benefits of that are.

jimklimov Oct 13, 2023

Ok, given the desire to not impose opinions, I guess this (consideration or not of back-refs from any dependency as part of a component/serice) will also become a toggle in BomEntityListMergeHelperStrategy :)

While at it: do you know of any other element types that behave similarly (are external but potentially behave as intimately as properties of components etc.?) I probably will not cover everything in my PRs, but might try to lay some design foundations to help future evolution (e.g. single toggles or lists of types?) :)

@wkoot

wkoot Sep 19, 2024

The merge strategy we are after does allow for squashing together certain entries (e.g. to add license info where missing, or more hash algos+values), although my initial PRs were a bit naive about this - the real rabbit hole goes too deep as shown by nuances like these here.

Should this really be part of a merge operation? Sounds more like a consolidate or "fix data" operation, overcomplicating merge.
I see licencing (but also vulnerability) information more as data enrichment than "materials", the primary objective of the bom.
Merging might be more straightforward if these could be two separate operations.

jimklimov
Oct 13, 2023

Is it safe to assume that these collections are unordered sets for the purpose of comparison (and may be reshuffled e.g. alphabetically to ensure minimal diffs in processed Bom files)?

2 replies

jkowalleck Oct 13, 2023
Maintainer Author

yes, in general they are sets (unordered collection of unique items), not lists(ordered collection of items).

❗ I know people argue that licenses should be an exception, because the order in that licenses are applied would matter. I am no expert on this specific license topic. @pombredanne taught me that lesson.

This comment was marked as off-topic.

jimklimov
Oct 13, 2023

Since CDX 1.5, XML schema and C# implementation for Workflow.TaskDependencies, Workflow.RuntimeTopologies and WorkflowTask.RuntimeTopologies are also each of a List<Dependency> type... Do they inherit the constraint of referring to "component or service", or may refer to some other types - e.g. (only?) to other tasks, or to any referable entity at all?

4 replies

jkowalleck Oct 13, 2023
Maintainer Author

Can you answer this, @CycloneDX/net-maintainers ?

@mtsfoni

mtsfoni Oct 20, 2023

I just discussed this with @jkowalleck. We are not completely sure what constraint you are referring to. We didn't see relevant constraints in the xsd. Might be possible that there is such a constraint in the dotnet library, then it's likely that it comes from a time, when the dependency type was used much less and was only relevant for components and services.

In that case, it might be an idea for the future to remove the constraint from the dotnet library. Feel free to create an issue there.

andreas-hilti Oct 20, 2023

AFAIK it is not specified as a constraint in the schemas. However, from the comments
https://cyclonedx.org/docs/1.5/json/#dependencies_items_dependsOn

The bom-ref identifiers of the components or services that are dependencies of this dependency object.

it is clear that at least in this place, it is constrained to components and services.

jkowalleck Oct 20, 2023
Maintainer Author

if you find the documentation wrong or confusing, please open a report here https://github.com/CycloneDX/specification/issues/new
and explain what part of the documentation needs improvement.
thank you in advance

prabhu
Oct 13, 2023

My humble request is that the specification be un-opinionated. Merging strategies require assumptions and positions, so best to leave it to the individual cli and tools for implementation.

1 reply

jimklimov Oct 13, 2023

I agree, so to the best extent possible (my first foray into C# and all that) I'm trying to make the merge strategies configurable.

The already-proposed PR bits include a class BomEntityListMergeHelperStrategy https://github.com/CycloneDX/cyclonedx-dotnet-library/pull/245/files#diff-ddf3af01de76d967741a9492ec55e00cd29ce804736a38d8f090624dc24d9b56R75 to pass around the caller's specific desires for the current merge operation (e.g. conflate identical items and leave others "as is", or drill into derived-class implementations of BomEntity.MergeWith(), etc.)

I hope this would prove extensible enough to add more toggles (and their handling) in the future as people would imagine more strategies and corner cases. And possibly CLI/YAML/whatever handling to pass the choice of toggles from tools and other consumers into these library calls.

Eventually, I think, the current Merge.cs methods could become selectable implementations of Bom.MergeWith() - but currently overwhelmed with more practical goals to think about that sort of refactoring :)

This comment has been hidden.

jimklimov Oct 13, 2023

Thanks for the suggestion. Looked at it as much as a mobile during commute allows, and https://github.com/interlynk-io/sbomasm/blob/main/pkg/assemble/spdx/merge.go says "flat merge not implemented", but the readme details one.

Anyhow, a quick search in https://github.com/CycloneDX/cyclonedx-go does not seem that it would mention "merge" at all, so any contribution there would be helpful, I suppose.

The tricky part I'm banging my head at for the past few months is the flat merge, as generic for the hordes of data types and their constraints as possible, and as un-opinionated as I can (or nowadays rather easy to fix into having codepaths configurable). And with many Boms explaining same components - either identically (so trivial to discard extras after checking constraints like different back-references from depenency-lists etc.), or appending info to squash into one entity (e.g. one tool reports the technical structure of a component, and another overlays the license used for intended audience), or some fully conflicting data (e.g. components can be marked required/excluded/optional and those are not just gradations to turn up the dial)... And I'm dealing closely with just components! Pile on the other dozens of types with their idiosyncracies, and go wonder about your choices in life ;)

In cyclonedx-dotnet-library a HierarchicalMerge() is available as well as a FlatMerge() (quite naive, so IMHO only somewhat usable so far - working on improvements, hence the discussion). Hierarchical seems rather trivial - in that case just the bomref (and hopefully back-refs) of each original-Bom entity is renamed to include the trail in the name, as they are nested into the new document, so all the input objects are retained in the new Bom, just under different names: no conflicts to solve, no additional data from different sources to squash, and no duplicates to benefit from by removal of extras.

For our use-case, building a "release bundle SBOM" for the end-user bundle comprised of about 600 input component BOMs (some referencing the same code as dependencies) a hierarchical merge ends up with some 26K components and thousands of copies of same alert when a vuln is found (assigned to each unique component ID) - this is unfeasible to manage and e.g. assign "we would fix this, ignore that"... I have seen the arguments in favour of in fact having the ultimate dependency tree with explicitly independent copies of same components, because in fact their place in the dependency tree makes them unique (e.g. using log4j in one component is a trouble to fix, but not in another because it is configured differently), and end up assigning different verdicts to same "log4j" component depending on its use-cases - so to each their own.

jkowalleck Oct 14, 2023
Maintainer Author

@riteshnoronha added ✔️

andreas-hilti
Oct 15, 2023

In terms of use-cases, this is what I'm using BOM merges for:

Hierarchical merge

I have BOMs for a couple of components which I'm aggregating, and thus, the new BOM describes the aggregate and has the other components as dependencies.

Flat merge

I have a BOM for component A, but the BOM is incomplete, thus I want to expand it using information from other BOMs (i.e. BOM editing).
In many cases, this is because I'm using different package management systems and the BOM tools typically can handle only one system.

Examples

I have a C# application using NuGet, but it uses also some C++ libraries managed using conan. Thus, I need to expand the "NuGet" BOM with the "conan" BOM (adding all the components into the BOM and add them either as toplevel dependencies or as dependencies of a particular NuGet package).
Similarly, this could happen when creating a Python application using PyPI, using some C++ libraries (again managed by conan).
I have a C++ application based on conan package management, but some libraries are directly included using submodules (for which I'm manually creating BOMs).

In many cases, I used the flat merge, but then I actually had to modify the dependencies manually.
Duplicated components in the BOM happen sometimes, but eliminating exact duplicates is enough (i.e. I don't have variations in the duplicated components).

(As written previously, for me the sematics for the hierarchical merge are quite clear, but for the flat merge this is not true.)

What are your use cases?

3 replies

jimklimov Oct 15, 2023

Detailed a number of times earlier, but to keep birds of a feather in one cage - here goes: I am making a script for $dayjob which coordinates creation of a "release SBOM" for the bundle delivered to this or that user/market, so often customized. The product is comprised of a few dozen tools and daemons/containers, built on top of a hundred or so components made by us, and a few hundred third-party dependencies (often same or similar, like the Java String framework parts used dozens of times). This singular release SBOM can be delivered to customers per requirements, as well as used internally with a Dependency-Tracker server to watch out for appearance of newly-discovered vulnerabilities that may impact something that we have delivered in the past and still support.

My script parses what is effectively a top-level manifest of a delivered bundle (the Kubernetes/Helm YAML which lists the components and their versions relevant for the particular bundle), collects a number of original Bom documents (e.g. some from build artifacts where they are placed by component-release publishing - currently for the PoC that's just cyclonedx-maven-plugin, but later there will be silos from C#, docker, etc. so potentially in different BOM formats originally and converted into CycloneDX somehow; some from other systems like the overlay with licensing relevant for certain contracts, etc.) and as one of many steps - it calls cyclonedx-cli to merge them (historically largely due to it being touted as the OWASP-made reference tool for the job :) )

Production of these merges proved complicated because use of a single Bom document with 30-60K original components (e.g. after a hierarchical merge) is not practically feasible for us. When a vulnerability is reported, we get hundreds or thousands of notifications for different uses of the same component, often behind several layers of third-party dependencies (so we can only moderately impact this), and formally each should have been inspected and a verdict made - hundreds of times. With a smallish team, that would not be possible even to click through them all.

Yes, we know the arguments about dependencies' situations being potentially different (e.g. log4j used in several places, but only in some with the error-prone config - so the error can be verdicted as "ack" in some, "ignore" in others), but this is not for us at this time.

So the flat merge for us has several goals:

overlay certain object types (generally "all", but gotta start somewhere - like the components, which are our practical use-case) with additional information from same-identifying entities (licensing, hashes, issuer/author info especially where absent in older release artifacts with incomplete recipe metadata);
generally to reduce the amount of entities in the resulting Bom document and in some cases to maximize their informativeness - and for that:
- identify objects that are identical (definition varies) to just dedup them,
- objects that describe same real-life entities and squash them (possibly adding non-conflicting info from one to another),
- while NOT squashing similar objects that end up describing different aspects of the same real-life entity (e.g. debug vs release builds, dependencies of a library and its optional tests vs. production use as part of an app...)

Maybe there was more to it, but it's late here and so much I did remember :)

@fnxpt

fnxpt Nov 6, 2023

I also have the same issue, the current specification works perfectly for single applications, but if for some reason we need to merge sboms like for a bundle (we used to describe a bundle of micro services) will lead to issues since the applications have different compile times that could lead to different dependency versions..
For instance
App A is compiled with
LibA 1.0 that has dependency on LibB 1.0
App B is compiled with
LibA 1.0 that has dependency on LibB 1.1

When merging if we put libB 1.0 and libB 1.1 as dependencies of libA will lead to
AppA -> LibA -> LibB 1.0 and 1.1
AppB-> LibA -> LibB 1.0 and 1.1

I was wondering if its possible to add something to the structure of dependencies that would help us to implement it without adding false positives or without duplicating the complete graph in order to do a merge without losing data

jkowalleck Nov 7, 2023
Maintainer Author

re: #320 (reply in thread)
this should be no issue when using hierarchical merge instead of flat merge.
read #320 (comment)

jkowalleck
Nov 7, 2023
Maintainer Author

❗ ❗ ❗ ❗ ❗

The following is a (probably outdated) unfinished and unpublished pamphlet "Standardization of BOM merging algorithms" - is still work in progress; the original authors agreed to publish the snapshot here.

❗ ❗ ❗ ❗ ❗

Summary

This is a proposal for a set of standardized merging algorithms for CycloneDX Bill of Materials.

Motivation

Why should we do this?

With SBOM adoption ramping up, a lot of use cases have surfaced that require merging multiple BOMs into one. While it's trivial to merge BOM objects on a technical level, it may introduce inconsistencies or cause ambiguities. We need one or more merging algorithms that we consider to be correct and accurate.

Another factor is that we offer tooling for SBOM generation and transformation, as well as libraries for multiple ecosystems. When it comes to functionalities like merging, it's important that our offering behaves the same across our portfolio, and produces consitent results.

What use cases does this support?

Use case 1

I have a web app. It has NPM packages for client side JavaScript, and NuGet
packages for the backend C# .NET code. The whole thing is built by a single team.

When I'm generating the SBOM for it, I need to use the CycloneDX Node implementation
and the .NET implementation to get all my dependencies. But I want to represent it
as a single piece of assembled software in a single SBOM.

Use case 2

I have a web app. It has NPM packages for a SPA frontend, NPM packages for the
web API, and Go packages for some background batch processing services.

I want to generate a single SBOM that retains the individual system components.
The user facing SPA, user facing API, and the background services.

Each of these components has a different threat model. The same vulnerability for
the "same" component in the SPA and API could have very different contexts.

Additionally, each of these components is managed by a different team.

Use case 3

I've gone all in on micro-services. I now have so many micro-services I don't
even know how many I have.

I want a view of my entire product and the dependency relationships (services)
between micro-services. But to merge and include all the information into a
single SBOM could get quite unwieldy. Additionally, micro-services in our
environment can change multiple times per day. Whereas micro-services being
added/removed from the environment happens at a much slower cadence.

Each micro-service team generates a new SBOM for each build.
And publishes it to our central SBOM store for every deployment.

I want an SBOM that represents all the individual micro-services in our
environment. But includes the reference to the individual micro-service SBOMs
for the detailed information.

What is the expected outcome?

Definition of merging algorithms that produce valid and correct BOMs in a reproducible way
Consensus on at least one merging algorithm

What it is

This RFC proposes three merging algorithms, each of which targets a different use case.

Use Case #	Merge Algorithm
1	Flat
2	Hierarchic
3	Reference

How it Works

Overview

In general, merging only affects top-level collections, not the elements within them.
We may choose to add merging or deduplication of individual elements in a later RFC.

Merge functions adhere to the following signature:

def merge(subject: Optional[Component], boms: Sequence[BOM]) -> BOM

subject can be provided as top-level component of the merged BOM
boms is a collection of the BOMs to be merged. The collection MUST be ordered

Further, the following constraints apply:

BOM values MUST NOT be null
BOMs MUST have a valid serial number
BOMs MUST be provided in a quantity of two or more
Input values of a merge function MUST NOT be modified
- (Deep) copies SHOULD be created as needed, prior to modification
BOM references, if present, MUST be namespaced (see BOM reference namespacing)

BOM reference namespacing

Namespacing is done to indicate the origin of a component or service, as well as to prevent reference collisions.
In case a component or service doesn't have a BOM reference, no reference is created and no namespace is applied.

See #7 for the namespace format definition.

<!-- Not namespaced -->
<component bom-ref="pkg:maven/com.acme/acme-lib@1.2.3" type="library">
<!-- Namespaced -->
<component bom-ref="urn:cyclonedx:a48a8f21-afe9-4cde-bb43-9c61c6409927/3#pkg%3Amaven%2Fcom.acme%2Facme-lib%401.2.3" type="library">

The following constraints apply to namespacing:

A BOM reference MUST NOT be created if it doesn't exist
A BOM reference MUST NOT be namespaced if it doesn't exist
A BOM reference MUST NOT be namespaced again if is namespaced already

Algorithms

The algorithms in this document are written in Python for readability's sake.
However, there's also a Go reference implementation in cyclonedx-go.

Reproducability

In order to make results reproducible, merge algorithms are subject to the following additional constraints:

Algorithms MUST NOT add any dynamic data (serial numbers, timestamps, etc.)
BOMs MUST be processed in the order they're provided in
Order of elements within a collection MUST be retained from their source

Namespacing

To accomodate for the namespacing requirements detailed above, merge algorithms make use
of utility functions that perform this task. Implementation of these is not part of this
RFC and is intentionally left out. Their function signatures, as well as a brief description,
is provided here for completeness sake.

def namespace(bom_ref: Optional[str], src: BOM) -> Optional[str]:
 """Namespace a BOM reference."""
 pass
def namespace_component(component: Component, src: BOM) -> None:
 """Namespace a component's BOM reference (and that of its sub-components)."""
 pass
def namespace_service(service: Service, src: BOM) -> None:
 """Namespace a component's BOM reference (and that of its sub-services)."""
 pass
def namespace_dependency(dependency: Dependency, src: BOM) -> None:
 """Namespace a dependency's BOM reference (and that of its dependencies)."""
 pass
def namespace_composition(composition: Composition, src: BOM) -> None:
 """Namespace a composition's BOM references."""
 pass

Flat merge

Description

The flat merge algorithm creates an aggregate of all elements within the provided BOMs.
Everything gets merged into the top-level collections of the resulting BOM.

Merged elements

Element	Merge?	Annotation
`metadata/tools`	✅	-
`metadata/authors`	❔	Still unclear if this makes sense
`metadata/component`	✅	Merged into `components`
`metadata/licenses`	❔	Still unclear if this makes sense
`metadata/properties`	✅	-
`components`	✅	-
`services`	✅	-
`externalReferences`	✅	-
`dependencies`	✅	-
`compositions`	✅	-
`properties`	✅	-

Code

def flat_merge(subject: Optional[Component], boms: Sequence[BOM]) -> BOM:
 if len(boms) < 2:
 raise MergeError("merging requires at least two boms")
 for bom in boms:
 if not bom:
 raise MergeError("bom must not be None")
 if not bom.serial_number:
 raise MergeError("bom must have a serial number")
 tools: List[Tool] = []
 metadata_properties: List[Property] = []
 components: List[Component] = []
 services: List[Service] = []
 external_references: List[ExternalReference] = []
 dependencies: List[Dependency] = []
 compositions: List[Composition] = []
 properties: List[Property] = []
 subject_dependencies: List[Dependency] = []
 for bom in boms:
 if bom.metadata:
 if bom.metadata.tools:
 tools.extend(bom.metadata.tools)
 if bom.metadata.component:
 component = bom.metadata.component
 namespace_component(component, bom)
 components.append(component)
 if subject.bom_ref and component.bom_ref:
 subject_dependencies.append(Dependency(ref=component.bom_ref))
 if bom.metadata.properties:
 metadata_properties.extend(bom.metadata.properties)
 
 if bom.components:
 for component in bom.components:
 namespace_component(component, bom)
 components.append(component)
 
 if bom.services:
 for service in bom.services:
 namespace_service(service, bom)
 services.append(service)
 
 if bom.external_references:
 external_references.extend(bom.external_references)
 
 if bom.dependencies:
 for dependency in bom.dependencies:
 namespace_dependency(dependency, bom)
 dependencies.append(dependency)
 
 if bom.compositions:
 for composition in bom.compositions:
 namespace_composition(composition, bom)
 compositions.append(composition)
 
 if bom.properties:
 properties.extend(bom.properties) 
 if subject and subject_dependencies:
 dependencies.append(Dependency(
 ref=subject.bom_ref,
 dependencies=subject_dependencies
 ))
 result = BOM()
 result.metadata = Metadata(
 tools=tools, 
 component=subject,
 properties=metadata_properties
 )
 result.components = components
 result.services = services
 result.external_references = external_references
 result.dependencies = dependencies
 result.compositions = compositions
 result.properties = properties
 return result

Hierarchical merge

Description

The hierarchical merge algorithm mostly behaves just like the flat merge, with the exception of components:
Component hierarchy is retained by treating top-level-components of all input BOMs as assemblies.
It is thus required that all input BOMs have a top-level component.

Merged elements

Element	Merge?	Annotation
`metadata/tools`	✅	-
`metadata/authors`	❔	Still unclear if this makes sense
`metadata/component`	✅	Merged into `components`
`metadata/licenses`	❔	Still unclear if this makes sense
`metadata/properties`	✅	-
`components`	✅	Included as sub-components of the respective `metadata/component`
`services`	✅	-
`externalReferences`	✅	-
`dependencies`	✅	-
`compositions`	✅	-
`properties`	✅	-

Code

def hierarchical_merge(subject: Optional[Component], boms: Sequence[BOM]) -> BOM:
 if len(boms) < 2:
 raise MergeError("merging requires at least two boms")
 
 for bom in boms:
 if not bom:
 raise MergeError("bom must not be None")
 if not bom.serial_number:
 raise MergeError("bom must have a serial number")
 if not bom.metadata or not bom.metadata.component:
 raise MergeError("bom must have a top-level component")
 tools: List[Tool] = []
 metadata_properties: List[Property] = []
 components: List[Component] = []
 services: List[Service] = []
 externalReferences: List[ExternalReference] = []
 dependencies: List[Dependency] = []
 compositions: List[Composition] = []
 properties: List[Property] = []
 subject_dependencies: List[Dependency] = []
 for bom in boms:
 if bom.metadata.tools:
 tools.extend(bom.metadata.tools)
 if bom.metadata.properties:
 metadata_properties.extend(bom.metadata.properties)
 
 main = bom.metadata.component
 if bom.components:
 main.components.extend(component)
 namespace_component(main, bom)
 components.append(main)
 if subject.bom_ref and main.bom_ref:
 subject_dependencies.append(Dependency(ref=main.bom_ref))
 if bom.services:
 for service in bom.services:
 namespace_service(service, bom)
 services.append(service)
 if bom.external_references:
 external_references.extend(bom.external_references)
 if bom.dependencies:
 for dependency in bom.dependencies:
 namespace_dependency(dependency, bom)
 dependencies.append(dependency)
 if bom.compositions:
 for composition in bom.compositions:
 namespace_composition(composition, bom)
 compositions.append(composition)
 if bom.properties:
 properties.extend(bom.properties) 
 if subject and subject_dependencies:
 dependencies.append(Dependency(
 ref=subject.bom_ref,
 dependencies=subject_dependencies
 ))
 result = BOM()
 result.metadata = Metadata(
 tools=tools, 
 component=subject,
 properties=metadata_properties
 )
 result.components = components
 result.services = services
 result.external_references = external_references
 result.dependencies = dependencies
 result.compositions = compositions
 result.properties = properties
 return result

Reference merge

Description

The reference merge extracts the top-level component of each provided BOM,
and merges it into the resulting BOM's components collection.

An externalReference of type bom, pointing to the source BOM's serial number, is added to each component.

Fields of the components that are not essential to identifying them are stripped.
The following fields are considered essential:

bom-ref
type
group
name
version

This is done to reduce redundancies, as well as ensuring consiceness of the resulting BOM.

TODO: Should external references have BOM versions and hashes?

Merged elements

Element	Merge?	Annotation
`metadata/tools`	❌	Defined in referenced BOMs
`metadata/authors`	❌	Defined in referenced BOMs
`metadata/component`	✅	Merged into `components`
`metadata/licenses`	❌	Defined in referenced BOMs
`metadata/properties`	❌	Defined in referenced BOMs
`components`	❌	Defined in referenced BOMs
`services`	❌	Defined in referenced BOMs
`externalReferences`	❌	Defined in referenced BOMs
`dependencies`	❌	Defined in referenced BOMs
`compositions`	❌	Defined in referenced BOMs
`properties`	❌	Defined in referenced BOMs

Code

def reference_merge(subject: Optional[Component], boms: Sequence[BOM]) -> BOM:
 if len(boms) < 2:
 raise MergeError("merging requires at least two boms")
 for bom in boms:
 if not bom:
 raise MergeError("bom must not be None")
 if not bom.serial_number:
 raise MergeError("bom must have a serial number")
 if not bom.metadata or not bom.metadata.component:
 raise MergeError("bom must have a top-level component")
 components: List[Component] = []
 subject_dependencies: List[Dependency] = []
 for bom in boms:
 component = Component(
 bom_ref=namespace(bom.metadata.component.bom_ref, bom),
 type=bom.metadata.component.type,
 group=bom.metadata.component.group,
 name=bom.metadata.component.name,
 version=bom.metadata.component.version,
 external_references = [
 ExternalReference(type="bom", url=bom.serial_number)
 ]
 )
 
 components.append(component)
 if subject.bom_ref and component.bom_ref:
 subject_dependencies.append(Dependency(ref=component.bom_ref))
 if subject and subject_dependencies:
 dependencies.append(Dependency(
 ref=subject.bom_ref,
 dependencies=subject_dependencies
 ))
 dependencies.extend(subject_dependencies)
 result = BOM()
 result.metadata = Metadata(component=subject)
 result.components = components
 result.dependencies = dependencies
 return result

Examples

Inputs

To keep this document manageable, we're assuming a fixed set of inputs for all merge operations.
Examples are limited to metadata, components and dependencies for the same reason.

BOM A

This BOM describes the Java application acme-backend.

<?xml version="1.0" encoding="UTF-8"?>
<bom xmlns="http://cyclonedx.org/schema/bom/1.3" serialNumber="urn:uuid:c337a0f7-82b6-49bf-abd2-95e37c7476c8" version="1">
 <metadata>
 <tools>
 <tool>
 <name>cyclonedx-maven-plugin</name>
 <version>2.5.3</version>
 </tool>
 </tools>
 <component bom-ref="pkg:maven/com.acme/acme-backend@1.0.0" type="application">
 <group>com.acme</group>
 <name>acme-backend</name>
 <version>1.0.0</version>
 </component>
 </metadata>
 <components>
 <component bom-ref="pkg:maven/com.fasterxml.jackson.core/jackson-databind@2.12.4" type="library">
 <group>com.fasterxml.jackson.core</group>
 <name>jackson-databind</name>
 <version>2.12.4</version>
 </component>
 </components>
 <dependencies>
 <dependency ref="pkg:maven/com.acme/acme-backend@1.0.0">
 <dependency ref="pkg:maven/com.fasterxml.jackson.core/jackson-databind@2.12.4"/>
 </dependency>
 <dependency ref="pkg:maven/com.fasterxml.jackson.core/jackson-databind@2.12.4"/>
 </dependencies>
</bom>

BOM B

This BOM describes the JavaScript application acme-frontend.

<?xml version="1.0" encoding="UTF-8"?>
<bom xmlns="http://cyclonedx.org/schema/bom/1.3" serialNumber="urn:uuid:12151f5b-4001-4835-a734-42fafde0a852" version="1">
 <metadata>
 <tools>
 <tool>
 <group>@cyclonedx</group>
 <name>bom</name>
 <version>v3.1.1</version>
 </tool>
 </tools>
 <component bom-ref="pkg:npm/%40acme/acme-frontend@1.0.0" type="application">
 <group>@acme</group>
 <name>acme-frontend</name>
 <version>1.0.0</version>
 </component>
 </metadata>
 <components>
 <component bom-ref="pkg:npm/vue@2.6.12" type="library">
 <name>vue</name>
 <version>2.6.12</version>
 </component>
 </components>
 <dependencies>
 <dependency ref="pkg:npm/%40acme/acme-frontend@1.0.0">
 <dependency ref="pkg:npm/vue@2.6.12"/>
 </dependency>
 <dependency ref="pkg:npm/vue@2.6.12"/>
 </dependencies>
</bom>

Subject

This component describes the top-level component acme-app of the merged SBOM.

<component bom-ref="com.acme/acme-app@1.0.0" type="application">
 <group>com.acme</group>
 <name>acme-app</name>
 <version>1.0.0</version>
</component>

Flat merge

<?xml version="1.0" encoding="UTF-8"?>
<bom xmlns="http://cyclonedx.org/schema/bom/1.3" serialNumber="urn:uuid:f120a825-fb11-4fe6-a6cd-f8a6a3874756" version="1">
 <metadata>
 <tools>
 <tool>
 <name>cyclonedx-maven-plugin</name>
 <version>2.5.3</version>
 </tool>
 <tool>
 <group>@cyclonedx</group>
 <name>bom</name>
 <version>v3.1.1</version>
 </tool>
 </tools>
 <component bom-ref="com.acme/acme-app@1.0.0" type="application">
 <group>com.acme</group>
 <name>acme-app</name>
 <version>1.0.0</version>
 </component>
 </metadata>
 <components>
 <component bom-ref="urn:cyclonedx:c337a0f7-82b6-49bf-abd2-95e37c7476c8#pkg:maven%2Fcom.acme%2Facme-backend%401.0.0" type="application">
 <group>com.acme</group>
 <name>acme-backend</name>
 <version>1.0.0</version>
 </component>
 <component bom-ref="urn:cyclonedx:c337a0f7-82b6-49bf-abd2-95e37c7476c8#pkg:maven%2Fcom.fasterxml.jackson.core%2Fjackson-databind%402.12.4" type="library">
 <group>com.fasterxml.jackson.core</group>
 <name>jackson-databind</name>
 <version>2.12.4</version>
 </component>
 <component bom-ref="urn:cyclonedx:12151f5b-4001-4835-a734-42fafde0a852#pkg:npm%2F%40acme%2Facme-frontend%401.0.0" type="application">
 <group>@acme</group>
 <name>acme-frontend</name>
 <version>1.0.0</version>
 </component>
 <component bom-ref="urn:cyclonedx:12151f5b-4001-4835-a734-42fafde0a852#pkg:npm%2Fvue%402.6.12" type="library">
 <name>vue</name>
 <version>2.6.12</version>
 </component>
 </components>
 <dependencies>
 <dependency ref="com.acme/acme-app@1.0.0">
 <dependency ref="urn:cyclonedx:c337a0f7-82b6-49bf-abd2-95e37c7476c8#pkg:maven%2Fcom.acme%2Facme-backend%401.0.0"/>
 <dependency ref="urn:cyclonedx:12151f5b-4001-4835-a734-42fafde0a852#pkg:npm%2F%40acme%2Facme-frontend%401.0.0"/>
 </dependency>
 <dependency ref="urn:cyclonedx:c337a0f7-82b6-49bf-abd2-95e37c7476c8#pkg:maven%2Fcom.acme%2Facme-backend%401.0.0">
 <dependency ref="urn:cyclonedx:c337a0f7-82b6-49bf-abd2-95e37c7476c8#pkg:maven%2Fcom.fasterxml.jackson.core%2Fjackson-databind%402.12.4"/>
 </dependency>
 <dependency ref="urn:cyclonedx:c337a0f7-82b6-49bf-abd2-95e37c7476c8#pkg:maven%2Fcom.fasterxml.jackson.core%2Fjackson-databind%402.12.4"/>
 <dependency ref="urn:cyclonedx:12151f5b-4001-4835-a734-42fafde0a852#pkg:npm%2F%40acme%2Facme-frontend%401.0.0">
 <dependency ref="urn:cyclonedx:12151f5b-4001-4835-a734-42fafde0a852#pkg:npm%2Fvue%402.6.12"/>
 </dependency>
 <dependency ref="urn:cyclonedx:12151f5b-4001-4835-a734-42fafde0a852#pkg:npm%2Fvue%402.6.12"/>
 </dependencies>
</bom>

Hierarchical merge

<?xml version="1.0" encoding="UTF-8"?>
<bom xmlns="http://cyclonedx.org/schema/bom/1.3" serialNumber="urn:uuid:f120a825-fb11-4fe6-a6cd-f8a6a3874756" version="1">
 <metadata>
 <tools>
 <tool>
 <name>cyclonedx-maven-plugin</name>
 <version>2.5.3</version>
 </tool>
 <tool>
 <group>@cyclonedx</group>
 <name>bom</name>
 <version>v3.1.1</version>
 </tool>
 </tools>
 <component bom-ref="com.acme/acme-app@1.0.0" type="application">
 <group>com.acme</group>
 <name>acme-app</name>
 <version>1.0.0</version>
 </component>
 </metadata>
 <components>
 <component bom-ref="urn:cyclonedx:c337a0f7-82b6-49bf-abd2-95e37c7476c8#pkg:maven%2Fcom.acme%2Facme-backend%401.0.0" type="application">
 <group>com.acme</group>
 <name>acme-backend</name>
 <version>1.0.0</version>
 <components>
 <component bom-ref="urn:cyclonedx:c337a0f7-82b6-49bf-abd2-95e37c7476c8#pkg:maven%2Fcom.fasterxml.jackson.core%2Fjackson-databind%402.12.4" type="library">
 <group>com.fasterxml.jackson.core</group>
 <name>jackson-databind</name>
 <version>2.12.4</version>
 </component>
 </components>
 </component>
 <component bom-ref="urn:cyclonedx:12151f5b-4001-4835-a734-42fafde0a852#pkg:npm%2F%40acme%2Facme-frontend%401.0.0" type="application">
 <group>@acme</group>
 <name>acme-frontend</name>
 <version>1.0.0</version>
 <components>
 <component bom-ref="urn:cyclonedx:12151f5b-4001-4835-a734-42fafde0a852#pkg:npm%2Fvue%402.6.12" type="library">
 <name>vue</name>
 <version>2.6.12</version>
 </component>
 </components>
 </component>
 </components>
 <dependencies>
 <dependency ref="com.acme/acme-app@1.0.0">
 <dependency ref="urn:cyclonedx:c337a0f7-82b6-49bf-abd2-95e37c7476c8#pkg:maven%2Fcom.acme%2Facme-backend%401.0.0"/>
 <dependency ref="urn:cyclonedx:12151f5b-4001-4835-a734-42fafde0a852#pkg:npm%2F%40acme%2Facme-frontend%401.0.0"/>
 </dependency>
 <dependency ref="urn:cyclonedx:c337a0f7-82b6-49bf-abd2-95e37c7476c8#pkg:maven%2Fcom.acme%2Facme-backend%401.0.0">
 <dependency ref="urn:cyclonedx:c337a0f7-82b6-49bf-abd2-95e37c7476c8#pkg:maven%2Fcom.fasterxml.jackson.core%2Fjackson-databind%402.12.4"/>
 </dependency>
 <dependency ref="urn:cyclonedx:c337a0f7-82b6-49bf-abd2-95e37c7476c8#pkg:maven%2Fcom.fasterxml.jackson.core%2Fjackson-databind%402.12.4"/>
 <dependency ref="urn:cyclonedx:12151f5b-4001-4835-a734-42fafde0a852#pkg:npm%2F%40acme%2Facme-frontend%401.0.0">
 <dependency ref="urn:cyclonedx:12151f5b-4001-4835-a734-42fafde0a852#pkg:npm%2Fvue%402.6.12"/>
 </dependency>
 <dependency ref="urn:cyclonedx:12151f5b-4001-4835-a734-42fafde0a852#pkg:npm%2Fvue%402.6.12"/>
 </dependencies>
</bom>

Reference merge

<?xml version="1.0" encoding="UTF-8"?>
<bom xmlns="http://cyclonedx.org/schema/bom/1.3" serialNumber="urn:uuid:f120a825-fb11-4fe6-a6cd-f8a6a3874756" version="1">
 <metadata>
 <component bom-ref="com.acme/acme-app@1.0.0" type="application">
 <group>com.acme</group>
 <name>acme-app</name>
 <version>1.0.0</version>
 </component>
 </metadata>
 <components>
 <component bom-ref="urn:cyclonedx:c337a0f7-82b6-49bf-abd2-95e37c7476c8#pkg:maven%2Fcom.acme%2Facme-backend%401.0.0" type="application">
 <group>com.acme</group>
 <name>acme-backend</name>
 <version>1.0.0</version>
 <externalReferences>
 <reference type="bom">
 <url>urn:uuid:c337a0f7-82b6-49bf-abd2-95e37c7476c8</url>
 </reference>
 </externalReferences>
 </component>
 <component bom-ref="urn:cyclonedx:12151f5b-4001-4835-a734-42fafde0a852#pkg:npm%2F%40acme%2Facme-frontend%401.0.0" type="application">
 <group>@acme</group>
 <name>acme-frontend</name>
 <version>1.0.0</version>
 <externalReferences>
 <reference type="bom">
 <url>urn:uuid:12151f5b-4001-4835-a734-42fafde0a852</url>
 </reference>
 </externalReferences>
 </component>
 </components>
 <dependencies>
 <dependency ref="com.acme/acme-app@1.0.0">
 <dependency ref="urn:cyclonedx:c337a0f7-82b6-49bf-abd2-95e37c7476c8#pkg:maven%2Fcom.acme%2Facme-backend%401.0.0"/>
 <dependency ref="urn:cyclonedx:12151f5b-4001-4835-a734-42fafde0a852#pkg:npm%2F%40acme%2Facme-frontend%401.0.0"/>
 </dependency>
 <dependency ref="urn:cyclonedx:c337a0f7-82b6-49bf-abd2-95e37c7476c8#pkg:maven%2Fcom.acme%2Facme-backend%401.0.0"/>
 <dependency ref="urn:cyclonedx:12151f5b-4001-4835-a734-42fafde0a852#pkg:npm%2F%40acme%2Facme-frontend%401.0.0"/>
 </dependencies>
</bom>

Prior Art

merge command in CycloneDX/cyclonedx-cli
--append flag in CycloneDX/cyclonedx-node-module@v2
defenseunicorns/sbom-cli

3 replies

andreas-hilti Nov 11, 2023

A couple of comments from my side (for the moment):

IMHO you should not use bom-refs that look like bom-links, i.e. you should do the namespacing differently. A bom-ref "urn:cyclonedx:..." looks like you are referring to an external component, but schemantically, a bom-ref is referring to an entity inside the same document. There are two entites which could be referred to by the same string (once interpreting it as a bom-ref and once as a bom-link), and further modifications could then lead to inconsistencies.
In addition, if you are merging two boms that contain the same namespaced entity, you will have this entity defined twice in the merged bom (in particular for entities that are not top-level), leading to a violation of the bom-ref uniqueness.
I would formulate this differently: "Algorithms MUST NOT add any dynamic data", maybe: There MUST be an option that the algorithm does not add any dynamic data. If you think of a command line tool, etc. I would expect that it adds timestamps by default.
I think the reference merge is valuable, as you should avoid creating SBOMs all the time from scratch, in particular of components that you don't own. It is an important use-case to combine SBOMs from your suppliers.
Using a urn in a url field sounds wrong to me (as a url locates stuff whereas a urn identifies stuff).
I'm still a bit unsure what the exact meaning of "dependency" and "assembly" is in particular for the different component types, but this is probably a separate discussion, even though a better understanding would be crucial. (In many cases, I would expect that most components would have to end up as subcomponents of the metadata component rather than in the top-level components collection...)

andreas-hilti Nov 12, 2023

In addition,

Just to stress my point about dynamic data: the examples actually contain new serialNumbers.
Tools need to be namespaced by now as well, given that they contain components or services.
Don't constraint how the algorithm needs to work, but on what it delivers: reformulate this "BOMs MUST be processed in the order they're provided in"; in particular, this prevents parallelism.
I wonder whether conceptually, it would be easier to describe the algorithm such that it namespaces the complete input BOMs and then starts combining them. (I'm not saying that it should/needs to be implemented like this; it just makes arguing more easily.)
In my opinion, exact duplicates (after namespacing) in lists (e.g. externalReferences) should be eliminated. (But due to the namespacing, this will happen quite rarely.)

andreas-hilti Nov 12, 2023

Last but not least one should also constraint that the input BOMs (or their serialNumbers) are different. This is a rather theoretical constraint though. In practice, it will be very uncommon to merge the same BOM twice. But it is needed to formally guarantee uniqueness.

fnxpt
Nov 7, 2023

@jkowalleck it seems that the examples don't show scenario where you have different versions of same dependency in different BOMs, to me this is the biggest issue and I don't think any of the solutions will work without losing data or duplicating the information

9 replies

jkowalleck Nov 9, 2023
Maintainer Author

just wondering if we have the possibility to review the spec [...]

what are you referring to? Spec is all here: https://github.com/CycloneDX/specification/
feel free to review, comment, annotate.

For the flat merge you lose the graph of the dependencies since you are merging everything into the top-level collections of the resulting BOM

I do not see this. What data are you loosing? Please provide the resulting merge from your given example and point to the data loss.

@fnxpt

fnxpt Nov 9, 2023

what are you referring to? Spec is all here: https://github.com/CycloneDX/specification/ feel free to review, comment, annotate.

Yes, thats what I was trying to say... maybe it would also be better if we could improve the specification to avoid having to duplicate everything

I do not see this. What data are you loosing? Please provide the resulting merge from your given example and point to the data loss.

You lose the relations between the dependencies since you put all the dependencies under the top level

jkowalleck Nov 10, 2023
Maintainer Author

You lose the relations between the dependencies since you put all the dependencies under the top level

I do not see this. Please provide the resulting merge from your given example and point to the data loss.

@fnxpt

fnxpt Nov 10, 2023

from the 2 boms I posted before you will have something like this, losing the relationship after level 2

<?xml version="1.0" encoding="UTF-8"?>
<bom xmlns="http://cyclonedx.org/schema/bom/1.3" serialNumber="urn:uuid:c337a0f7-82b6-49bf-abd2-95e37c7476c8" version="1">
 <metadata>
 <tools>
 <tool>
 <name>cyclonedx-maven-plugin</name>
 <version>2.5.3</version>
 </tool>
 </tools>
 <component bom-ref="pkg:maven/com.acme/acme-app@1.0.0" type="application">
 <group>com.acme</group>
 <name>acme-app</name>
 <version>1.0.0</version>
 </component>
 </metadata>
 <components>
 <component bom-ref="pkg:maven/com.acme/acme-backend@1.0.0" type="application">
 <group>com.acme</group>
 <name>acme-backend</name>
 <version>1.0.0</version>
 </component>
 <component bom-ref="pkg:maven/com.acme/acme-backend2@1.0.0" type="application">
 <group>com.acme</group>
 <name>acme-backend2</name>
 <version>1.0.0</version>
 </component>
 <component bom-ref="pkg:maven/com.fasterxml.jackson.core/jackson-databind@2.12.4" type="library">
 <group>com.fasterxml.jackson.core</group>
 <name>jackson-databind</name>
 <version>2.12.4</version>
 </component>
 <component bom-ref="pkg:maven/com.fasterxml.jackson.core/jackson-annotations@2.12.4" type="library">
 <group>com.fasterxml.jackson.core</group>
 <name>jackson-annotations</name>
 <version>2.12.4</version>
 </component>
 <component bom-ref="pkg:maven/com.fasterxml.jackson.core/jackson-annotations@2.12.5" type="library">
 <group>com.fasterxml.jackson.core</group>
 <name>jackson-annotations</name>
 <version>2.12.5</version>
 </component>
 </components>
 <dependencies>
 <dependency ref="pkg:maven/com.acme/acme-app@1.0.0">
 <dependency ref="pkg:maven/com.acme/acme-backend@1.0.0"/>
 <dependency ref="pkg:maven/com.acme/acme-backend2@1.0.0"/>
 </dependency>
 <dependency ref="pkg:maven/com.acme/acme-backend@1.0.0">
 <dependency ref="pkg:maven/com.fasterxml.jackson.core/jackson-databind@2.12.4"/>
 <dependency ref="pkg:maven/com.fasterxml.jackson.core/jackson-annotations@2.12.4"/>
 </dependency>
 <dependency ref="pkg:maven/com.acme/acme-backend2@1.0.0">
 <dependency ref="pkg:maven/com.fasterxml.jackson.core/jackson-databind@2.12.4"/>
 <dependency ref="pkg:maven/com.fasterxml.jackson.core/jackson-annotations@2.12.5"/>
 </dependency>
 </dependencies>
</bom>