feat(sbom): add Parent Contains Relationship for Orphan OS Packages #9007

masahiro331 · 2025-06-07T17:29:19Z

Description

Add Parent Contains Relationship for Orphan OS Packages

Problem

During the encoding phase, some OS packages were correctly identified and added to the BOM as components, but they were not linked to their parent OS component. These "orphan" packages resulted in an incomplete dependency graph in the final SBOM.

Solution

A new recursive function, traverseRelationship, has been added to encode.go. This function traverses the dependency graph to identify all components that are already linked to a parent.
Any OS packages that are not part of this graph are considered orphans.
The encodePackages function now explicitly adds a Contains relationship from the parent component (e.g., the OS component) to each of these identified orphan packages.

Checklist

I've read the guidelines for contributing to this repository.
I've followed the conventions in the PR title.
I've added tests that prove my fix is effective or that my feature works.
I've updated the documentation with the relevant information (if needed).
I've added usage information (if the PR introduces new options)
I've included a "before" and "after" example to the description (if the PR is a user interface change).

masahiro331 · 2025-06-10T15:37:42Z

@DmitriyLewen
Sorry, could you update golden files for sbom integration tests?

DmitriyLewen · 2025-06-11T04:52:22Z

integration/testdata/fluentd-multiple-lockfiles.cdx.json.golden

@@ -8639,6 +8639,7 @@
        "pkg:deb/debian/base-passwd@3.5.46?arch=amd64&distro=debian-10.2",
        "pkg:deb/debian/bash@5.0-4?arch=amd64&distro=debian-10.2",
        "pkg:deb/debian/bsdutils@2.33.1-0.1?arch=amd64&distro=debian-10.2&epoch=1",
+        "pkg:deb/debian/ca-certificates@20190110?arch=all&distro=debian-10.2",


reason why pkg:deb/debian/ca-certificates@20190110?arch=all&distro=debian-10.2 is not related with an OS component:

{ "ref": "pkg:deb/debian/ruby2.5@2.5.5-3%2Bdeb10u1?arch=amd64&distro=debian-10.2", "dependsOn": [ "pkg:deb/debian/libc6@2.28-10?arch=amd64&distro=debian-10.2", "pkg:deb/debian/libgmp10@6.1.2%2Bdfsg-4?arch=amd64&distro=debian-10.2&epoch=2", "pkg:deb/debian/libruby2.5@2.5.5-3%2Bdeb10u1?arch=amd64&distro=debian-10.2", "pkg:deb/debian/rubygems-integration@1.11?arch=all&distro=debian-10.2" ] }, { "ref": "pkg:deb/debian/ruby@2.5.1?arch=amd64&distro=debian-10.2&epoch=1", "dependsOn": [ "pkg:deb/debian/ruby2.5@2.5.5-3%2Bdeb10u1?arch=amd64&distro=debian-10.2" ] }, { "ref": "pkg:deb/debian/rubygems-integration@1.11?arch=all&distro=debian-10.2", "dependsOn": [ "pkg:deb/debian/ca-certificates@20190110?arch=all&distro=debian-10.2" ] },

DmitriyLewen · 2025-06-11T04:53:23Z

@masahiro331
I updated golden file - d59c5cc
Also i refactored a little - 49e4b78
can you re-check these changes?

masahiro331 · 2025-06-11T05:05:43Z

Thank you.
I think it is a very great change.

DmitriyLewen

LGTM.
@knqyf263 you also worked on belongToParent function.
Can you take a look? Perhaps we missed something.

knqyf263 · 2025-06-11T17:11:30Z

Actually, we may want to revert the logc to add CONTAINS relationships as we already got a complaint.
#8245

Then, it would be simple.

diff --git a/pkg/sbom/io/encode.go b/pkg/sbom/io/encode.go
index 8f395c150..9eb5faf55 100644
--- a/pkg/sbom/io/encode.go
+++ b/pkg/sbom/io/encode.go
@@ -251,37 +251,6 @@ func (e *Encoder) encodePackages(parent *core.Component, result types.Result) {
 			e.bom.AddRelationship(c, nil, "")
 		}
 	}
-
-	// Add relationships between the parent and the orphaned packages
-	// For OS packages, packages with circular dependencies are not added as relationships to the parent component in belongToParent.
-	// To resolve this, we add relationships between these circularly dependent packages and the parent component.
-	// cf. https://github.com/aquasecurity/trivy/issues/9011
-	if result.Class == types.ClassOSPkg {
-		e.addOrphanedPackagesRelationships(parent, components)
-	}
-}
-
-// addOrphanedPackagesRelationships adds relationships between the parent and the orphaned packages
-func (e *Encoder) addOrphanedPackagesRelationships(parent *core.Component, components map[string]*core.Component) {
-	pkgs := lo.MapKeys(components, func(c *core.Component, _ string) uuid.UUID {
-		return c.ID()
-	})
-	orphans := e.traverseRelationship(parent.ID(), pkgs)
-	for _, c := range orphans {
-		e.bom.AddRelationship(parent, c, core.RelationshipContains)
-	}
-}
-
-func (e *Encoder) traverseRelationship(id uuid.UUID, components map[uuid.UUID]*core.Component) map[uuid.UUID]*core.Component {
-	for _, rel := range e.bom.Relationships()[id] {
-		_, ok := components[rel.Dependency]
-		if !ok {
-			continue
-		}
-		delete(components, rel.Dependency)
-		components = e.traverseRelationship(rel.Dependency, components)
-	}
-	return components
 }
 
 // existedPkgIdentifier tries to look for package identifier (BOM-ref, PURL) by component name and component type
@@ -457,7 +426,7 @@ func (*Encoder) belongToParent(pkg ftypes.Package, parents map[string]ftypes.Pac
 	// Case 4: Relationship: unknown, DependsOn: known (e.g., GoBinaries, OS packages)
 	//         - Packages with parents: false. These packages are included in the packages from `parents` (e.g. GoBinaries deps and root package).
 	//         - Packages without parents: true. These packages are included in the parent (e.g. OS packages without parents).
-	if pkg.Relationship == ftypes.RelationshipDirect {
+	if pkg.Relationship == ftypes.RelationshipDirect || pkg.Relationship == ftypes.RelationshipUnknown {
 		return !hasRoot
 	}
 
diff --git a/pkg/sbom/io/encode_test.go b/pkg/sbom/io/encode_test.go
index ef4bc74d4..b6bebfaf4 100644
--- a/pkg/sbom/io/encode_test.go
+++ b/pkg/sbom/io/encode_test.go
@@ -520,6 +520,10 @@ func TestEncoder_Encode(t *testing.T) {
 					},
 				},
 				uuid.MustParse("3ff14136-e09f-4df9-80ea-000000000002"): {
+					{
+						Dependency: uuid.MustParse("3ff14136-e09f-4df9-80ea-000000000003"),
+						Type:       core.RelationshipContains,
+					},
 					{
 						Dependency: uuid.MustParse("3ff14136-e09f-4df9-80ea-000000000004"),
 						Type:       core.RelationshipContains,

masahiro331 · 2025-06-11T17:39:07Z

RelationshipUnknown is in such a wonderful value. This is the best.

knqyf263 · 2025-06-12T06:27:45Z

You can see this PR to know what needs to be reverted.
https://github.com/aquasecurity/trivy/pull/8104/files

masahiro331 · 2025-06-12T13:12:35Z

Thank you.

pkg/sbom/io/encode.go

…manager - Implement functionality to merge multiple PackageInfo with the same package manager (rpm, deb) - Add merge process in Decode function - Add logic to merge PackageInfo using package manager type as key

…package manager" This reverts commit 34e2935.

- add lint to issue into comment - use lo.MapKeys - change place in code for traverseRelationship - add wantVulns to fix unit test

knqyf263 · 2025-06-12T18:37:34Z

https://proxy.golang.org seems unstable now.

masahiro331 · 2025-06-14T12:32:08Z

integration/testdata/npm-cyclonedx.json.golden

+        "pkg:npm/asap@2.0.6",
        "pkg:npm/jquery@3.3.9",
+        "pkg:npm/js-tokens@4.0.0",
+        "pkg:npm/loose-envify@1.4.0",
+        "pkg:npm/object-assign@4.1.1",
        "pkg:npm/promise@8.0.3",
+        "pkg:npm/prop-types@15.7.2",
+        "pkg:npm/react-is@16.8.6",
        "pkg:npm/react@16.8.6",
-        "pkg:npm/redux@4.0.1"
+        "pkg:npm/redux@4.0.1",
+        "pkg:npm/scheduler@0.13.6",
+        "pkg:npm/symbol-observable@1.2.0"


The npm modules' relationships are unknown.
So, all packages have parent relationships.

@knqyf263
The npm package lock v1 does not have a dependency identifier(relationship.Unknown).
I think it would be difficult to solve all problems with a common process.
Do you have any good ideas?

I think it would be a good idea to fix the implementation on the npm parser side, but what do you think?

Hi @masahiro331
Sorry for the wait.

We already used this logic (unknown relationships are always related to parents) and users didn't complain.
We just wanted to improve our logic, but as you can see, we didn't cover all cases.

About npm v1. The latest version v6 (since v7 lockfile uses v2 scheme) was released in 2022 - https://docs.npmjs.com/cli/v6/using-npm/changelog
So I think we can leave it as is
I think most users have already migrated to newer versions

integration/testdata/npm-cyclonedx.json.golden

masahiro331 · 2025-06-14T12:47:36Z

pkg/sbom/cyclonedx/marshal_test.go

@@ -557,6 +557,7 @@ func TestMarshaler_MarshalReport(t *testing.T) {
 					{
 						Ref: "3ff14136-e09f-4df9-80ea-000000000004",
 						Dependencies: &[]string{
+							"3ff14136-e09f-4df9-80ea-000000000005",


Investigate if this change is correct.

https://github.com/aquasecurity/trivy/pull/8104/files#diff-c7e1fc266c7df3ffce122539e69fef4d4702c07755dfcaabaa221a5087bc9bd1L562

masahiro331 · 2025-06-15T02:54:38Z

Looks like it's not work...

This reverts commit f8ef0b56fff2df6ea1750037074f371ccb4cb586.

masahiro331 · 2025-06-26T02:53:56Z

@knqyf263
The npm package lock v1 does not have a dependency identifier(relationship.Unknown).
I think it would be difficult to solve all problems with a common process.
Do you have any good ideas?

I think it would be a good idea to fix the implementation on the npm parser side, but what do you think?

DmitriyLewen · 2025-06-26T07:26:10Z

Hi @masahiro331
Sorry for the delay.
We are focused on another higher priority task.
We will try to check it next week.

DmitriyLewen · 2025-06-30T07:26:59Z

pkg/sbom/io/encode.go

+	if pkg.Relationship == ftypes.RelationshipUnknown && len(parents[pkg.ID]) != 0 {
+		return !hasRoot
+	}
+	if pkg.Relationship == ftypes.RelationshipDirect || pkg.Relationship == ftypes.RelationshipUnknown {


Suggested change

if pkg.Relationship == ftypes.RelationshipUnknown && len(parents[pkg.ID]) != 0 {

return !hasRoot

}

if pkg.Relationship == ftypes.RelationshipDirect || pkg.Relationship == ftypes.RelationshipUnknown {

if pkg.Relationship == ftypes.RelationshipDirect || pkg.Relationship == ftypes.RelationshipUnknown {

It can be simpler, or am i missing any case?

I updated logic - 3b5a83e
tell me if this logic doesn’t cover some cases

github-actions · 2025-09-02T00:07:44Z

This PR is stale because it has been labeled with inactivity.

masahiro331 force-pushed the fix/orphan-os-pkgs branch from e252811 to a3eaaa9 Compare June 10, 2025 15:16

DmitriyLewen approved these changes Jun 11, 2025

View reviewed changes

masahiro331 marked this pull request as ready for review June 11, 2025 05:14

masahiro331 requested a review from knqyf263 as a code owner June 11, 2025 05:14

masahiro331 changed the title ~~feat(sbom): add functionality to merge PackageInfo with same package~~ feat(sbom): add Parent Contains Relationship for Orphan OS Packages Jun 11, 2025

DmitriyLewen approved these changes Jun 11, 2025

View reviewed changes

masahiro331 commented Jun 12, 2025

View reviewed changes

pkg/sbom/io/encode.go Outdated Show resolved Hide resolved

masahiro331 and others added 8 commits June 13, 2025 03:32

feat(sbom): add functionality to merge PackageInfo with same package …

2b0e87a

…manager - Implement functionality to merge multiple PackageInfo with the same package manager (rpm, deb) - Add merge process in Decode function - Add logic to merge PackageInfo using package manager type as key

fix(sbom): fix sbom encoder, add parent relationship for orphan packages

9f4702c

Revert "feat(sbom): add functionality to merge PackageInfo with same …

1a1a961

…package manager" This reverts commit 34e2935.

fix(sbom): add comment

8b9759b

fix(sbom): fix lint

e174047

refactor: small changes:

06c7400

- add lint to issue into comment - use lo.MapKeys - change place in code for traverseRelationship - add wantVulns to fix unit test

test(integration): update fluentd-multiple-lockfiles.cdx.json.golden

c6dcd0b

fix(sbom): use RelationshipsUnknown

418f60a

masahiro331 force-pushed the fix/orphan-os-pkgs branch from 39bff3f to 5b8e9e4 Compare June 12, 2025 18:32

masahiro331 force-pushed the fix/orphan-os-pkgs branch from 5b8e9e4 to d7dae5e Compare June 13, 2025 04:15

masahiro331 commented Jun 14, 2025

View reviewed changes

masahiro331 force-pushed the fix/orphan-os-pkgs branch from d7dae5e to 157f28d Compare June 14, 2025 12:41

masahiro331 commented Jun 14, 2025

View reviewed changes

integration/testdata/npm-cyclonedx.json.golden Show resolved Hide resolved

masahiro331 commented Jun 14, 2025

View reviewed changes

masahiro331 force-pushed the fix/orphan-os-pkgs branch from 26ad5cf to 38b46e5 Compare June 15, 2025 03:56

masahiro331 added 3 commits June 15, 2025 15:01

fix(sbom): fix test

05c9200

fix(sbom): changed packages with no parent are related to root

989f795

Revert "fix(sbom): changed packages with no parent are related to root"

58ae63c

This reverts commit f8ef0b56fff2df6ea1750037074f371ccb4cb586.

masahiro331 force-pushed the fix/orphan-os-pkgs branch from 38b46e5 to 58ae63c Compare June 15, 2025 06:01

masahiro331 added 2 commits June 16, 2025 01:21

fix(sbom): wip encode sbom

419545c

fix(sbom): wip encode sbom

5e05942

DmitriyLewen reviewed Jun 30, 2025

View reviewed changes

DmitriyLewen added 2 commits July 3, 2025 13:04

refactor(sbom): simplify logic

3b5a83e

test(integration): update golden files

9061b86

github-actions bot added the lifecycle/stale Denotes an issue or PR has remained open with no activity and will be auto-closed. label Sep 2, 2025

DmitriyLewen removed the lifecycle/stale Denotes an issue or PR has remained open with no activity and will be auto-closed. label Sep 2, 2025

DmitriyLewen mentioned this pull request Sep 10, 2025

fix(vex): don't suppress vulns for packages with infinity loop #9465

Open

6 tasks

feat(sbom): add Parent Contains Relationship for Orphan OS Packages #9007

Are you sure you want to change the base?

feat(sbom): add Parent Contains Relationship for Orphan OS Packages #9007

Uh oh!

Conversation

masahiro331 commented Jun 7, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Description

Problem

Solution

Related

Checklist

Uh oh!

masahiro331 commented Jun 10, 2025

Uh oh!

Choose a reason for hiding this comment

Uh oh!

DmitriyLewen commented Jun 11, 2025

Uh oh!

masahiro331 commented Jun 11, 2025

Uh oh!

DmitriyLewen left a comment

Choose a reason for hiding this comment

Uh oh!

knqyf263 commented Jun 11, 2025

Uh oh!

masahiro331 commented Jun 11, 2025

Uh oh!

knqyf263 commented Jun 12, 2025

Uh oh!

masahiro331 commented Jun 12, 2025

Uh oh!

Uh oh!

knqyf263 commented Jun 12, 2025

Uh oh!

masahiro331 Jun 14, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

masahiro331 commented Jun 15, 2025

Uh oh!

masahiro331 commented Jun 26, 2025

Uh oh!

DmitriyLewen commented Jun 26, 2025

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

github-actions bot commented Sep 2, 2025

Uh oh!

Uh oh!

masahiro331 commented Jun 7, 2025 •

edited

Loading

masahiro331 Jun 14, 2025 •

edited

Loading