bug(sbom): Packages with infinite loop dependencies are not associated with an OS component

[DmitriyLewen]

Description

If there are 2 (or more) components that depend on each other (infinite loop):
Trivy thinks the component has a parent component and does not link it to the root component (OS component):

trivy/pkg/sbom/io/encode.go

Lines 412 to 433 in 3b1426a

	func (*Encoder) belongToParent(pkg ftypes.Package, parents map[string]ftypes.Packages, hasRoot bool) bool {
	// Case 1: Relationship: known , DependsOn: known
	// Packages with no parent are included in the parent
	// - Relationship:
	// - Root: true (it doesn't have a parent)
	// - Workspace: false (it always has a parent)
	// - Direct:
	// - No root dependency in the project: true (e.g., poetry.lock)
	// - Otherwise: false (Direct dependencies should belong to the root/workspace)
	// - Indirect: false (it always has a parent)
	// Case 2: Relationship: unknown, DependsOn: unknown (e.g., conan lockfile v2)
	// All packages are included in the parent
	// Case 3: Relationship: known , DependsOn: unknown (e.g., go.mod without $GOPATH)
	// All packages are included in the parent
	// 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 {
	return !hasRoot
	}
	return len(parents[pkg.ID]) == 0

this results in these packages being orphans (and Trivy decoding them incorrectly).
See example in #9006 (comment)

Discussed in #9006

[masahiro331]

@DmitriyLewen
Could you share your plan for resolving this issue?
I'm thinking of modifying both the encoding and decoding logic to address the problem.

[DmitriyLewen]

As i wrote in #9006 (reply in thread) - i think we need to start from encoding logic.

---

I was thinking about this yesterday.
It seems that detecting orphan packages when we add relationships for packages is impossible task(possible many moments that we should handle).
So I found one way:
After adding relationships, we need to traverse dependency tree of parent component (here OS component) and collect all packages related to the parent component.
Compare all components with this list and add relationships for the missed packages (between the root component and this package).
I think it should be here:

trivy/pkg/sbom/io/encode.go

Line 253 in 3b1426a

}

wdyt?

[masahiro331]

For the future, I thought it would be better to implement a cycle detection algorithm in belongToParent, but I will use the proposed process.

trivy/pkg/sbom/io/encode.go

Lines 412 to 434 in 3b1426a

	func (*Encoder) belongToParent(pkg ftypes.Package, parents map[string]ftypes.Packages, hasRoot bool) bool {
	// Case 1: Relationship: known , DependsOn: known
	// Packages with no parent are included in the parent
	// - Relationship:
	// - Root: true (it doesn't have a parent)
	// - Workspace: false (it always has a parent)
	// - Direct:
	// - No root dependency in the project: true (e.g., poetry.lock)
	// - Otherwise: false (Direct dependencies should belong to the root/workspace)
	// - Indirect: false (it always has a parent)
	// Case 2: Relationship: unknown, DependsOn: unknown (e.g., conan lockfile v2)
	// All packages are included in the parent
	// Case 3: Relationship: known , DependsOn: unknown (e.g., go.mod without $GOPATH)
	// All packages are included in the parent
	// 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 {
	return !hasRoot
	}
	return len(parents[pkg.ID]) == 0
	}

[DmitriyLewen]

yeah, i wanted that too.
But it seems like we can't detect orphan components until we add all relationships in belongsToParent.
But if you have any ideas - let's try