Capture the dependency graph in CycloneDX BOMs

[sschuberth]

Since the CycloneDX 1.2 spec, the dependency graph moved from an extension to a core feature. So after #3897 is merged, we could make use of it as the hierarchy of dependencies is valuable additional information.

[mawl]

Hey,

we really would like to see see that this feature gets implemented.

• Trivy can already generate CycloneDX SBOMs with a dependency graph included: https://trivy.dev/latest/docs/supply-chain/sbom/#generating
• Since 2021 Dependency-Track can visualise dependency graphs: https://docs.dependencytrack.org/2021/03/17/v4.2.0/

[mawl]

@sschuberth: Thanks for your work.

Unfortunately I get a stackoverflow error with ort v43.0.0 - maybe because of a lot of definition files?

 ______________________________                                                
/        \_______   \__    ___/ The OSS Review Toolkit, version 43.0.0,        
|    |   | |       _/ |    |    built with JDK 21.0.5+11-LTS, running under Jav
|    |   | |    |   \ |    |    Executing 'analyze' as 'ort' on Linux          
\________/ |____|___/ |____|    with 8 CPUs and a maximum of 8192 MiB of memory
...
Found in total 14 definition file(s) from the following 8 package manager(s):
        GoMod, Maven, NPM, NuGet, PIP, PNPM, Poetry, Yarn
...

 ______________________________                                                
/        \_______   \__    ___/ The OSS Review Toolkit, version 43.0.0,        
|    |   | |       _/ |    |    built with JDK 21.0.5+11-LTS, running under Jav
|    |   | |    |   \ |    |    Executing 'report' as 'ort' on Linux           
\________/ |____|___/ |____|    with 8 CPUs and a maximum of 8192 MiB of memory
                                                                               
Environment variables:                                                        
ORT_CONFIG_DIR = /home/ort/.ort/config                                        
ORT_DATA_DIR = /builds/compliance/license-scanning/.ort                
HOME = /home/ort                                                              
JAVA_HOME = /opt/java/openjdk                                                 
ANDROID_HOME = /opt/android-sdk                                               
                                                                              
Looking for ORT configuration in the following file:
        /home/ort/.ort/config/config.yml
Generating the 'WebApp' report in thread 'DefaultDispatcher-worker-1'...
Generating the 'CycloneDX' report in thread 'DefaultDispatcher-worker-3'...
Generating the 'PlainTextTemplate' report in thread 'DefaultDispatcher-worker-4'...
Exception in thread "main" java.lang.StackOverflowError
	at org.ossreviewtoolkit.model.DependencyRefCursor.visitDependencies(DependencyGraphNavigator.kt:165)
	at org.ossreviewtoolkit.model.DependencyGraphNavigator.packageDependencies$traverse(DependencyGraphNavigator.kt:104)
	at org.ossreviewtoolkit.model.DependencyGraphNavigator.packageDependencies$traverse$lambda$8(DependencyGraphNavigator.kt:105)
	at org.ossreviewtoolkit.model.DependencyRefCursor.visitDependencies(DependencyGraphNavigator.kt:165)
...
	at org.ossreviewtoolkit.model.DependencyGraphNavigator.packageDependencies(DependencyGraphNavigator.kt:110)
	at org.ossreviewtoolkit.model.OrtResult.getDependencies(OrtResult.kt:241)
	at org.ossreviewtoolkit.plugins.reporters.cyclonedx.BomExtensionsKt.addDependencies(BomExtensions.kt:66)
...
        at org.ossreviewtoolkit.plugins.reporters.cyclonedx.BomExtensionsKt.addDependencies(BomExtensions.kt:67)

[mawl]

Same Issue with 16GiB RAM:

 ______________________________                                                
/        \_______   \__    ___/ The OSS Review Toolkit, version 43.0.0,        
|    |   | |       _/ |    |    built with JDK 21.0.5+11-LTS, running under Jav
|    |   | |    |   \ |    |    Executing 'report' as 'ort' on Linux           
\________/ |____|___/ |____|    with 16 CPUs and a maximum of 16384 MiB of memory
                                                                               
Environment variables:                                                        
ORT_CONFIG_DIR = /home/ort/.ort/config                                        
ORT_DATA_DIR = /builds/compliance/license-scanning/.ort                
HOME = /home/ort                                                              
JAVA_HOME = /opt/java/openjdk                                                 
ANDROID_HOME = /opt/android-sdk                                               
                                                                              
Looking for ORT configuration in the following file:
        /home/ort/.ort/config/config.yml
Generating the 'WebApp' report in thread 'DefaultDispatcher-worker-2'...
Generating the 'CycloneDX' report in thread 'DefaultDispatcher-worker-3'...
Generating the 'PlainTextTemplate' report in thread 'DefaultDispatcher-worker-4'...
Exception in thread "main" java.lang.StackOverflowError
	at org.ossreviewtoolkit.model.DependencyGraphNavigator.packageDependencies$traverse$lambda$8(DependencyGraphNavigator.kt:270)
	at org.ossreviewtoolkit.model.DependencyRefCursor.visitDependencies(DependencyGraphNavigator.kt:165)
	at org.ossreviewtoolkit.model.DependencyGraphNavigator.packageDependencies$traverse(DependencyGraphNavigator.kt:104)

[mnonnenmacher]

Even large dependency trees should not cause a stackoverflow, if size was a problem I would expect an out of memory error.
@sschuberth Could there be an endless recursion if dependency graphs have circles?

[sschuberth]

@sschuberth Could there be an endless recursion if dependency graphs have circles?

I was quite sure that the dependency graph implementation breaks cycles, but I'll double-check.

[sschuberth]

I was quite sure that the dependency graph implementation breaks cycles, but I'll double-check.

So when build-ing natively dependency graphs, cycles get removed automatically (see the last line):

ort/model/src/main/kotlin/utils/DependencyGraphBuilder.kt

Lines 176 to 189 in dcc97a0

	fun build(checkReferences: Boolean = true): DependencyGraph {
	if (checkReferences) checkReferences()
	val (sortedDependencyIds, indexMapping) = constructSortedDependencyIds(dependencyIds)
	val (nodes, edges) = references.toGraph(indexMapping)
	return DependencyGraph(
	sortedDependencyIds,
	sortedSetOf(),
	constructSortedScopeMappings(scopeMapping, indexMapping),
	nodes,
	edges.removeCycles()
	)
	}

But I'm not sure how it is for package managers that have not been converted yet, and that use a graph that is just converted from the tree...

@mawl which package managers does the analyzer find in your case?

[mawl]

@mawl which package managers does the analyzer find in your case?

@sschuberth:

Found in total 14 definition file(s) from the following 8 package manager(s):
        GoMod, Maven, NPM, NuGet, PIP, PNPM, Poetry, Yarn

It's a test CI Job where we have collected show cases for different scenarios and issues in the past. There are "14 files defining 977 unique dependencies within 11 scopes and 22 dependency levels."

I will write unique test jobs for the package managers mentioned above, to find out in which package manager it occurs.

[sschuberth]

GoMod, Maven, NPM, NuGet, PIP, PNPM, Poetry, Yarn

Out of these, GoMod, NuGet and PIP / PNPM / Poetry do not use the dependency graph yet. Probably a good reason to continue working on #3825.

[sschuberth]

Anyway, please direct any further comments to #9587.