phylum-dev/vuln-reach

Failing assertion in topological sorting

Closed this issue · 3 comments

andreaphylum commented

In the topological sorting function, the non-cyclicity of the dependency graph fails for some inputs.

We should investigate whether it is a genuine case of circular dependencies, there are issues with the way we load modules, or the sorting algorithm is incorrect.

How to reproduce

Run this file in the vuln-reach-cli. Adjust the tarballs = ... property if necessary.

cd vuln-reach/vuln-reach-cli
gunzip /path/to/fastify.toml.gz
cargo run --release -- fastify.toml
andreaphylum commented

A few hypotheses:

  • Some packages vendor some of their dependencies in their releases (it's the case of mocha-qunit-ui). If those dependencies aren't properly accounted for in package.json, maybe there could be be gaps in the tree?
  • Some packages may have failing/unparseable modules that would normally import dependencies, but those being skipped leads to the imports not being recognized and thus missing edges in the tree. The QUnit example in #27 could be one of such cases.
  • Some packages may have correctly parseable modules that aren't actually part of the package -- say, template files or something similar (same QUnit example if the preamble were a whole, parseable script).
  • There may be some sort-of-circular dependencies, i.e. package A@2.0.0 depends on B@1.0.0 which depends on A@1.0.0. I'm not sure if this is supported by npm, but we don't have a way to support this case yet (see #31) anyway.
andreaphylum commented

The algorithm is working correctly.

The following cycles were found in the dependency graph:

['@fastify/fast-json-stringify-compiler', 'fastify']
['@fastify/ajv-compiler', 'fastify', 'light-my-request']
['@fastify/ajv-compiler', 'fastify']
['babel-register', 'babel-core']

babel-register and babel-core were manually verified and indeed their respective package.json file reference each other. It is not an issue of multiple versions (see #31) because the cyclical import happens with the same version of both babel-register and babel-core.

The only way to solve this would be to understand what are the intended semantics for dependency cycles in npm and implement the same resolution algorithm.

andreaphylum commented

Closing this in favor of #56. The assertion works as intended, but the overall approach is not conducive to working with dependency cycles.