Taking too much time to verify the SPDX tag-value SBOM

[boravinod145]

Description

An invalid Tag value SBOM contains large relationships and has thousands of SPDX warnings taking exponential time to verify.

Example

To generate this issue download the attached spdx tag value file is an invalid SBOM and try to verify it:

SBOM: issued.zip

java -jar tools-java-1.1.8-jar-with-dependencies.jar Verify ./issued.spdx

I waited for 5 hours and it is still not validated. After debugging this, found verifying elements in relationships in line L1489 in spdx-java-tagvalue-store lib is taking too much time to verify the relationships.

To verify this I've created a new jar by commenting lines L1488C3-L1490C4, is verified the same SBOM within 1 min.

[goneall]

Thanks @boravinod145 for the detailed analysis.

I took a look at the code and it wasn't obvious to me how it got stuck - likely some kind of (nearly) infinite recursion.

The verify for relationship will include a verification of the element being referenced.

There is code in the library to avoid infinite recursion as relationships can form cycles in valid SPDX documents.

We could avoid validating the element by changing the code on L1489 to:

			verifyElement(entry.getValue().verify(new HashSet<>(Arrays.asList(new String[] {entry.getValue().getRelatedSpdxElement().get().getId()})), 
					this.specVersion), "Relationship", entry.getKey());

It feels a bit hacky and I'm a bit concerned I'm not completely understanding the error - but this would a marginally better than removing the check.

[bact]

With 2.0.0-RC1, does this one still an issue?

[goneall]

I just tried verifying the SPDX file in the issued.zip file and it took 14 minutes on my laptop. It is still quite a long time, but there are 41,000 relationships to verify which is what is taking the time.

Note that this is primarily an issue with the tag/value parser since it needs to validate each relationship inside the tag/value parser. Other formats should take about half the time.

I'll go ahead and close it. @boravinod145 - if you still are running into a performance problem, please open a new issue.