Skip to content

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

Closed
masahiro331 wants to merge 17 commits intoaquasecurity:mainfrom
masahiro331:fix/orphan-os-pkgs
Closed

feat(sbom): add Parent Contains Relationship for Orphan OS Packages#9007
masahiro331 wants to merge 17 commits intoaquasecurity:mainfrom
masahiro331:fix/orphan-os-pkgs

Conversation

@masahiro331
Copy link
Copy Markdown
Contributor

@masahiro331 masahiro331 commented Jun 7, 2025

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.

Related

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
Copy link
Copy Markdown
Contributor Author

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

@@ -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",
Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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
Copy link
Copy Markdown
Contributor

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

@masahiro331
Copy link
Copy Markdown
Contributor Author

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

@masahiro331 masahiro331 marked this pull request as ready for review June 11, 2025 05:14
@masahiro331 masahiro331 requested a review from knqyf263 as a code owner June 11, 2025 05:14
@masahiro331 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
Copy link
Copy Markdown
Contributor

@DmitriyLewen DmitriyLewen left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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

@knqyf263
Copy link
Copy Markdown
Collaborator

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
Copy link
Copy Markdown
Contributor Author

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

@knqyf263
Copy link
Copy Markdown
Collaborator

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

@masahiro331
Copy link
Copy Markdown
Contributor Author

Thank you.

Comment thread pkg/sbom/io/encode.go Outdated
masahiro331 and others added 8 commits June 13, 2025 03:32
…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 34e2935a2d6f86c917deb42aa3c37f445d815b2f.
- add lint to issue into comment
- use lo.MapKeys
- change place in code for traverseRelationship
- add wantVulns to fix unit test
@knqyf263
Copy link
Copy Markdown
Collaborator

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

Comment on lines +297 to +308
"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"
Copy link
Copy Markdown
Contributor Author

@masahiro331 masahiro331 Jun 14, 2025

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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

Copy link
Copy Markdown
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

@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?

Copy link
Copy Markdown
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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

Comment thread integration/testdata/npm-cyclonedx.json.golden
@@ -557,6 +557,7 @@ func TestMarshaler_MarshalReport(t *testing.T) {
{
Ref: "3ff14136-e09f-4df9-80ea-000000000004",
Dependencies: &[]string{
"3ff14136-e09f-4df9-80ea-000000000005",
Copy link
Copy Markdown
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Investigate if this change is correct.

Copy link
Copy Markdown
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

@masahiro331
Copy link
Copy Markdown
Contributor Author

Looks like it's not work...

@masahiro331
Copy link
Copy Markdown
Contributor Author

@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
Copy link
Copy Markdown
Contributor

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

Comment thread pkg/sbom/io/encode.go Outdated
Comment on lines +428 to +431
if pkg.Relationship == ftypes.RelationshipUnknown && len(parents[pkg.ID]) != 0 {
return !hasRoot
}
if pkg.Relationship == ftypes.RelationshipDirect || pkg.Relationship == ftypes.RelationshipUnknown {
Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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?

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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

@github-actions
Copy link
Copy Markdown
Contributor

github-actions Bot commented Sep 2, 2025

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

@github-actions 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 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
@github-actions
Copy link
Copy Markdown
Contributor

github-actions Bot commented Nov 2, 2025

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

@github-actions github-actions Bot added the lifecycle/stale Denotes an issue or PR has remained open with no activity and will be auto-closed. label Nov 2, 2025
@DmitriyLewen DmitriyLewen removed the lifecycle/stale Denotes an issue or PR has remained open with no activity and will be auto-closed. label Nov 3, 2025
Copy link
Copy Markdown
Contributor

@DmitriyLewen DmitriyLewen left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I think we can go back to the previous approach: link unknown components to their parent when there’s no root component. (#9007 (comment))

@knqyf263 if you don’t have any objections, I’ll merge this PR.

@github-actions
Copy link
Copy Markdown
Contributor

github-actions Bot commented Jan 3, 2026

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

@github-actions github-actions Bot added the lifecycle/stale Denotes an issue or PR has remained open with no activity and will be auto-closed. label Jan 3, 2026
@DmitriyLewen DmitriyLewen removed the lifecycle/stale Denotes an issue or PR has remained open with no activity and will be auto-closed. label Jan 12, 2026
@masahiro331 masahiro331 closed this Mar 6, 2026
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

3 participants