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

[masahiro331]

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

• https://github.com/aquasecurity/trivy/discussions/9006
• https://github.com/aquasecurity/trivy/issues/9011

Checklist

• [x] I've read the guidelines for contributing to this repository.
• [x] I've followed the conventions in the PR title.
• [x] I've added tests that prove my fix is effective or that my feature works.
• [x] 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]

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

[DmitriyLewen]

@masahiro331 I updated golden file - https://github.com/aquasecurity/trivy/pull/9007/commits/d59c5cc757a41b2edf1bdc2e086e97b26cef72c8 Also i refactored a little - https://github.com/aquasecurity/trivy/pull/9007/commits/49e4b7851041438a67bbae3cca7b78567a1327fb can you re-check these changes?

[masahiro331]

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

[knqyf263]

Actually, we may want to revert the logc to add CONTAINS relationships as we already got a complaint. https://github.com/aquasecurity/trivy/discussions/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]

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

[knqyf263]

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

[masahiro331]

Thank you.

[knqyf263]

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

[masahiro331]

Looks like it's not work...

[masahiro331]

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

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

[github-actions[bot]]

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

[github-actions[bot]]

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