Precomputing reachability to identify exploitable vulnerabilities

1 . A method comprising:

receiving an alert of a vulnerability within an application;

determining, for the application, a set of dependent packages by referencing a knowledge graph storing a dependency chain for the application having a node for each package within the dependency chain;

for each vulnerable node of the dependency chain having the vulnerability:

identifying a set of node pairs having a direct link between an upstream node and the vulnerable node;

determining whether the vulnerable node is reachable by each upstream node of the set of upstream nodes; and

responsive to determining that the vulnerable node is not reachable by a respective upstream node, annotating its respective direct link as unreachable;

for upstream nodes that are able to reach the vulnerable node, iteratively determining whether a respective further upstream node is able to reach respective ones of their respective directly connected downstream nodes;

generating a pruned dependency chain for the application by determining a boundary of the dependency chain, the boundary separating reachable vulnerable nodes from unreachable vulnerable nodes; and

analyzing reachable dependencies of the application for the vulnerability using the pruned dependency chain.

2 . The method of claim 1 , wherein determining whether a given downstream node is reachable by a given upstream node having a direct link with the given downstream node comprises determining whether the upstream node executes code referencing the downstream node.

3 . The method of claim 1 , further comprising pre-computing the reachable dependencies responsive to a request.

4 . The method of claim 3 , wherein the request comprises receiving a request to scan the application for vulnerabilities.

5 . The method of claim 3 , wherein the request comprises detecting a Common Vulnerabilities and Exposures (CVE) alert that is associated with the vulnerability.

6 . The method of claim 1 , further comprising storing the reachable dependencies as a reachable dependency graph in a cache.

7 . The method of claim 6 , wherein, responsive to a future request to scan the application for vulnerabilities, the reachable dependency graph is retrieved and used to scan the pruned dependency chain without performing a redetermination of reachability.

8 . A non-transitory computer-readable medium comprising memory with instructions encoded thereon, the instructions, when executed by one or more processors, causing the one or more processors to perform operations, the instructions comprising instructions to:

receive an alert of a vulnerability within an application;

determine, for the application, a set of dependent packages by referencing a knowledge graph storing a dependency chain for the application having a node for each package within the dependency chain;

for each vulnerable node of the dependency chain having the vulnerability:

identify a set of node pairs having a direct link between an upstream node and the vulnerable node;

determine whether the vulnerable node is reachable by each upstream node of the set of upstream nodes; and

responsive to determining that the vulnerable node is not reachable by a respective upstream node, annotate its respective direct link as unreachable;

for upstream nodes that are able to reach the vulnerable node, iteratively determine whether a respective further upstream node is able to reach respective ones of their respective directly connected downstream nodes;

generate a pruned dependency chain for the application by determining a boundary of the dependency chain, the boundary separating reachable vulnerable nodes from unreachable vulnerable nodes; and

analyze reachable dependencies of the application for the vulnerability using the pruned dependency chain.

9 . The non-transitory computer-readable medium of claim 8 , wherein the instructions to determine whether a given downstream node is reachable by a given upstream node having a direct link with the given downstream node comprise instructions to determine whether the upstream node executes code referencing the downstream node.

10 . The non-transitory computer-readable medium of claim 8 , the instructions further comprising instructions to pre-compute the reachable dependencies responsive to a request.

11 . The non-transitory computer-readable medium of claim 10 , wherein the request comprises receiving a request to scan the application for vulnerabilities.

12 . The non-transitory computer-readable medium of claim 10 , wherein the request comprises detecting a Common Vulnerabilities and Exposures (CVE) alert that is associated with the vulnerability.

13 . The non-transitory computer-readable medium of claim 8 , the instructions further comprising instructions to store the reachable dependencies as a reachable dependency graph in a cache.

14 . The non-transitory computer-readable medium of claim 13 , wherein, responsive to a future request to scan the application for vulnerabilities, the reachable dependency graph is retrieved and used to scan the pruned dependency chain without performing a redetermination of reachability.

15 . A system comprising:

memory with instructions encoded thereon; and

one or more processors that, when executing the instructions, are caused to perform operations comprising:

receiving an alert of a vulnerability within an application;

determining, for the application, a set of dependent packages by referencing a knowledge graph storing a dependency chain for the application having a node for each package within the dependency chain;

for each vulnerable node of the dependency chain having the vulnerability:

identifying a set of node pairs having a direct link between an upstream node and the vulnerable node;

determining whether the vulnerable node is reachable by each upstream node of the set of upstream nodes; and

responsive to determining that the vulnerable node is not reachable by a respective upstream node, annotating its respective direct link as unreachable;

for upstream nodes that are able to reach the vulnerable node, iteratively determining whether a respective further upstream node is able to reach respective ones of their respective directly connected downstream nodes;

generating a pruned dependency chain for the application by determining a boundary of the dependency chain, the boundary separating reachable vulnerable nodes from unreachable vulnerable nodes; and

analyzing reachable dependencies of the application for the vulnerability using the pruned dependency chain.

16 . The system of claim 15 , wherein determining whether a given downstream node is reachable by a given upstream node having a direct link with the given downstream node comprises determining whether the upstream node executes code referencing the downstream node.

17 . The system of claim 15 , the operations further comprising pre-computing the reachable dependencies responsive to a request.

18 . The system of claim 17 , wherein the request comprises receiving a request to scan the application for vulnerabilities.

19 . The system of claim 17 , wherein the request comprises detecting a Common Vulnerabilities and Exposures (CVE) alert that is associated with the vulnerability.

20 . The system of claim 19 , the operations further comprising storing the reachable dependencies as a reachable dependency graph in a cache.