Precomputing reachability to identify exploitable vulnerabilities

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.

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.