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.