OmniBOR is an application of the git DAG, a widely used merkle tree with a flat-file storage format, to the challenge of creating build artifact dependency graphs in today's language-heterogeneous open source environments.
By generating artifact dependency graphs at build time, embedding the hash of the graph in produced artifacts, and referencing that hash in each subsequent build step, OmniBOR will enable the creation of verifiable and complete artifact dependency graphs while requiring no effort from, or changes in, most open source projects. Furthermore, it will enable efficient correlation of vulnerability databases against a concise representation of the artifact dependency graph within run-time environments, if vulnerability databases can be correlated to source files or intermediary packages or libraries. These benefits would also accrue to closed-source projects that use the same build tools, and provide insights which span both open and closed source components in a consistent manner.
It is desirable to enable efficient launch-time comparison of the verifiable and complete build tree of any executable component [1] against a then-current list of undesirable source files [2] which are known to be undesirable, where such a build tree contains unique referents for all sources from which the given executable object was composed.
[1]: binary, dynamically-linked library, container image, etc.
[2]: because vulnerabilities may be discovered between the time an executable is created and the time when it is run, these processes must be decoupled
In an ideal scenario, an open source consumer would have available to them a complete artifact dependency graph, tracing dependencies to their ultimate depth. Even if we do not achieve this ideal, we should seek a solution with the lowest cost of adoption so as to enable the greatest buy-in across all open source ecosystems and communities.
For this reason we propose two areas of work:
Following from (1), this approach will require minimal to no effort on the part of open source project maintainers, thus significantly increasing its chances of widespread adoption as compared to any approach which requires maintainers to perform additional actions (e.g., implementing substantive changes in their CI/CD or package build pipeline to generate an SBOM).
Following from (2), this on-disk format provides an efficient and already well-understood method for cross referencing artifacts and source files by a deterministically-generated UUID (SHA1 or SHA256).
┌─────────────────────────────-┐
│ Build Time: Graph Generation │
│ │
│ ┌────────┐ ┌────────┐ │
│ │ Src A │ │ Src B │ │
│ └───┬────┘ └──┬─────┘ │
│ │ │ │
│ ▼ │ │
│ ┌───────┐ │ │
│ │ Obj A │ │ │
│ └─────┬─┘ │ │
│ │ │ │
│ ▼ ▼ │
│ ┌─────────────┐ │
│ │ Compilation │ │
│ │ & Signing │ │
│ └─────┬───────┘ │
│ │ │
└──────────────┼──────────────-┘
│
┌──▼─┐
▼ ▼
┌──────────┐ ┌──────--┐
│ [header] ├──►│omnibor │
│executable│ │ graph │
└──────┬───┘ └┬─────--┘
│ │
┌───────┼────────┼────────────────────────────┐
│ │ │ Run Time: Comparison │
│ │ │ │
│ ▼ ▼ ┌────────────┐ │
│ ┌───────────────┐ │ Public │ │
│ │ Policy │◄─────►│ Vuln │ │
│ │ Enforcement │ │ Database │ │
│ └─┬─────────────┘ └────────────┘ │
│ │ | │
│ ▼ ▼ │
│ ┌─────────────┐ ┌────────────┐ │
│ │ Runtime | | Scanning | |
| | Environment │◄─────►│ Tools | │
│ └─────────────┘ └────────────┘ │
│ │
└─────────────────────────────────────────────┘
OmniBOR is an approach which has the following properties:
[]byte(artifact1) == []byte(artifact2).Two artifacts are equivalent if []byte(artifact1) == []byte(artifact2).
Two artifacts are said to be equivalent if and only if they are byte-for-byte identical. This implies that OmniBOR is not concerned with questions of provenance, origination, licensure, or many others aspects which are encompassed by a software bill of materials, and which could differ between byte-equivalent artifacts.
Independent parties, presented with equivalent artifacts, derive the same artifact identity.
This implies that a deterministic hashing function may be used to derive artifact identity, such as SHA256.
An identified artifact cannot be modified without also changing its identity. Non-equivalent artifacts have distinct identities.
"An identified artifact" means an artifact whose identity has been determined. "Can not be modified without also changing its identity" means that the deterministic hashing function has no collisions, and therefore any change to the artifact results in a change to its identity. In this way, the relationship between artifact and identity is immutable.
An artifact can have precisely one artifact identity graph. All equivalent artifacts have the same graph.
This implies that we must not include build tooling in the artifact dependency graph, as doing otherwise would violate the Uniqueness requirement. For example, two reproducible build systems which rely on different auxiliary libraries (e.g., zlib) and result in byte-equivalent outputs must yield identical OmniBORs.
For further exploration of this topic, see Wheeler's work on reproducibility as a means to verify trustability: Countering Trusting Trust through Diverse Double-Compiling
{{% notification type="info" %}} Note the implication that for any artifact, there can only be one artifact identity graph, but the reverse is not true. Each artifact identity graph may generate multiple artifacts (e.g., if different build parameters are used, or it is compiled on a different architecture, or different metadata, such as compile time, were embedded in the built artifact). {{% /notification %}}
Artifacts and associated metadata may be obfuscated when sharing the artifact identity graph, while preserving other properties.
Metadata about artifacts and their associated artifact dependency graphs may have varying levels of sensitivity. OmniBOR allows the supplier to reveal as little or as much as they, in negotiation with their consumers, choose. The OmniBOR graph itself is just a merkle tree of opaque hashes. This provides transparency about the artifact dependency graph and its structure, while allowing supplier modulated levels of opaequeness about the metadata.
Artifacts may be associated, through their identity, to independently generated metadata stored outside of the artifact identity graph, such as an SBOM containing license and provenance metadata.
There are many many many use cases that could use OmniBORs. An incomplete list would include:
Undoubtably, more will arise. Independence of metadata independent permissionless innovation around each use case without the need for cross domain coordination. This lowers the cost of innovation and thus allows more productive innovation in this space.
{{% notification type="info" %}} OmniBOR is not an SBOM standard. {{% /notification%}}
From the OmniBOR perspective, any SBOM document is a type of artifact which could be referenced in an artifact dependency graph.
From an SBOM perspective, OmniBOR is a common precise way to identify artifacts and their artifact dependency graphs, and nothing more. This makes OmniBOR incapable of fulfilling many of the objectives of SBOMs, such as recording provenance, origination, build environment information, licensure, and other qualities.
{{% notification type="info" %}} Speaking strictly from an SPDX 3.0-draft perspective, OmniBOR is a lossy serialization format that only includes the minimum metadata field of "Identifier". {{% /notification %}}
Current metadata formats, such as SPDX 2.x, as well as current systems to sign and transport metadata documents, do not efficiently support our use case in the general case. They may well, however, support this use case in a specialized case, which we will discuss.
An argument can be made that current metadata formats can enable run-time analysis of the complete artifact dependency graph. Achieving this would require (1) that generation of SBOM metadata be performed using compatible tooling by every project within the graph, (2) the documents' distrubion be consistent, and, crucially, (3) that a separate system exist to recursively fetch and parse metadata documents for all related projects and index them in a manner enabling efficient search.
Let us look briefly at these three adoption requirements in more detail to understand the implications for (and, at least, one motivation for hesitancy in uptake of) volunteer-maintained open source projects.
Current tooling to generate SBOM documents requires effort on the part of every OSS project maintainer to integrate with their build systems. While full SBOM generation could be integrated into compilers and linkers, as we propose for OmniBOR, many view the complexity as overly burdensome on small projects, creating a source of friction that has and may continue to hamper adoption. On the other hand, due to the pervasiveness of Git itself, we believe a minimalist approach that already feels familiar will be better received by this long tail of OSS projects.
One obstacle in the distribution and adoption of SBOMs has been competing standards (see the "Landscape" document for examples in addition to SPDX). By proposing to capture only the bare minimum metadata necessary to enable this scenario, we believe this proposal will avoid the ongoing debates about competing standards. N.B.: Early socialization of this idea has received fairly wide support for the principle of a minimalist disk-based representation of the artifact dependency graph.
Run-time comparison, as described in the Objective, must be within the capabilities of even small and independent consumers of open source. A proposal which required large investments in infrastructure (e.g., that an operator maintain a database containing complete SBOM documents for the totality of open source) will not be seen as a reasonable requirement for smaller and independent organizations (even though it may make for a very compelling product offering, were someone to build and license it!).
TODO
TODO: Santiago
Imagine we have the following two files:
hello.c has gitoid c64efd8bd8bceca8c69f9b5b7647cf0ff61fed59 and includes stdio.h
stdio.h has gitoid c0f35b8ae567f5348df3711496fdc0ef6f634169
From these two inputs, we compile hello.o. The resulting OmniBOR is a document (text file) containing the lexically ordered sequence of the gitoids of each input artifact related to this build step:
blob⎵c0f35b8ae567f5348df3711496fdc0ef6f634169\n
blob⎵c64efd8bd8bceca8c69f9b5b7647cf0ff61fed59\n
The gitoid of the resulting document is 85322091b1d50a23d1c2a0f5933788a2a958f2ad, and this document is written out to disk in a directory in the build environment, e.g.:
./.bom/object/85/322091b1d50a23d1c2a0f5933788a2a958f2ad
The compiler would also embed this gitoid in a new elf section of the resulting hello.o binary; this adds a total of 89 bytes when accounting for elf section formatting.
Imagine we have the following Dockerfile:
FROM <baseimage>:<release>
RUN <command to install package>
We calculate the hash of <baseimage>:<release>, which is: 000TODO.
Things get a little trickier when we go to calculate the hash of the next layer.
Also, we want to produce an artifact dependency graph that can reference the omnibor of any artifacts added to that layer, not merely a hash of the whole layer. We'll do that by ... TODO ...
Combining these together, we produce the following OmniBOR document:
blob_000TODO
blob_000TODO
... and embed the gitoid of this omnibor in the image manifest's annotations field, like so:
{
"schemaVersion": 2,
"config": {...},
"layers": [ {...}, {...} ],
"annotations": {
"omnibor”: “sha256:abc123TODO”
}
}
{{% notification type="info" %}} NOTE: The annotation type 'omnibor' is not yet standardized or accepted to OCI. In the above snippet, 'omnibor' is merely an example. {{% /notification %}}
TODO
TODO
TODO: Replace / reformat examples as a specification
TODO
I must thank Ed Warnicke, who pitched this idea to me one sunny summer afternoon in 2021 while I was stuck in Puget Sound traffic, and who graciously accomodated my awkward schedule throughout the rest of the year, most often while both of us were in a car.
I must also thank everyone who provided input and feedback to my "Open Source Landscape" document in 2021, which I have since migrated to a github repo. The knowledge I gained through those discussions allowed me to identify a tool that was missing from my "supply chain backpack": the OmniBOR.