Solving the indirect vulnerability enigma – fixing indirect vulnerabilities without breaking your dependency tree

Fixing indirect vulnerabilities is one of those complex,
tedious and, quite frankly, boring tasks that no one really wants
to touch. No one except for Debricked, it seems. Sure,
there are lots of ways to do it manually, but can it be done
automatically with minimal risk of breaking changes? The Debricked
team decided to find out.^[1]

A forest full of fragile trees

So, where do you even start?

Firstly, there needs to be a way to fix the vulnerability,
which, for indirect dependencies, is no walk in the park. Secondly,
it needs to be done in a safe way, or, without anything
breaking.

You see, indirect dependencies are introduced deep down the
dependency tree and it’s very tricky to get to the exact version
you want. As Debricked’s Head of R&D once put it, “You are
turning the knobs by playing around with your direct dependencies
and praying to Torvalds that the correct indirect packages are
resolved. When Torvalds is in your favour, you have to sacrifice
some cloud storage to uncle Bob to make sure the updates don’t
break your application.”

In other words, there really should be an easier, less
stressful, way to do it.

In this article, we’ll walk you through how solving transitive
vulnerabilities can be done manually and, towards the end, show you
the Debricked solution, which allows you to do it automatically.
If you’re really just interested in the solution, I suggest you
start scrolling.

Precision surgery on your dependency tree

During the research phase of the graph-database project^[2], or, how Debricked today
fixes your open source vulnerabilities at the speed of light, the
team stumbled upon some articles^[3]
explaining how to fix indirect vulnerabilities in NPM.

As stated in the article, the `minimist` package is affected by
vulnerabilities, namely CVE-2021-44906^[4]
and CVE-2020-7598^[5].

These are both “Prototype Pollution” vulnerabilities, meaning
that arguments are not properly sanitized. Luckily, the maintainers
of `minimist` fixed these vulnerabilities in version 1.2.6.

Unfortunately, `mocha` version 7.1.0 resolves `minimist` 0.0.8,
which is within the vulnerable range of these vulnerabilities. As
suggested by the author of this article^[6], these vulnerabilities
can be fixed in a few different ways.

But! What about breaking changes?

The first suggestion is to simply trigger an update of all
“indirect dependencies”, meaning that we won’t actually change the
version of `mocha`. To perform this update, simply run `npm
update`, delete your `npm.lock` file, and run `npm install`. This
regenerates the dependency tree with the latest possible version
(according to constraints) of your indirect dependencies. With this
method, the risk of breaking changes is very low as you actually
don’t update any of your root dependencies, just your indirect
ones.

Breaking changes occur when the package functionality or
interface is not forward compatible, meaning that an update to the
package could cause your application to break. Common breaking
changes are class/function-removal, change of arguments to a
function, or licence-change (watch out for that one!).

But life is not always this easy, and this simple update of the
tree will not solve the vulnerability. The problem is that `mkdirp`
has actually locked their version of
`minimist` to 0.0.8^[7]. This means that the
contributors of `mkdirp` have come to the conclusion that they are
not compatible with newer versions of `minimist`, and forcing the
update of `minimist` may introduce breaking changes between
`mkdirp` and `minimist`.

Think… graphs!

So, the million-dollar question is: what version of `mocha`
should be used, that in turn trickles down to a safe version of
`minimist` without breaking the dependency tree? This is actually a
graph problem, which has been described in this article^[8].

What graph algorithm would solve this problem? How NPM resolves
dependencies can be a bit complicated, as they are allowed to
“split” the dependency tree. This means that they can have multiple
versions of one dependency to make sure that we always have a tree
that is compatible. To solve the vulnerability, we need to make
sure that all instances of `minimist` are safe by updating all
roots that can trickle down to `minimist`.

The algorithm used to solve this problem is called “All Max
Paths Safe”. By walking down the dependency graph and keeping the
max versions, all while pruning all other versions of that package
in each intersection, we can create an approximate representation
of our dependency tree. If the approximation is safe, that means
that our real tree will be safe as well!

By performing this algorithm for all potential versions of
`mocha`, we find the smallest upgrade to fix this vulnerability. To
get the speed we wanted for this algorithm, the team had to build a
custom Neo4j procedure^[9], which can handle
searching over 100 root versions with a search depth of 30+ in ~150
milliseconds. Speedy, huh?

In this case, we don’t have to search very far… as 7.1.1 of
`mocha` is safe! This is only a patch update, which indicates that
the risk of breaking changes is very low. For less complex cases
(like this example), ‘npm audit’ can help you with their fantastic
‘npm audit fix’ command.

Don’t be ad-hoc, enter the pub-sub-human way of working!

Now, if you got this far (congratulations, very impressive) and
thought, “this sounds really complex and like an awful lot of
work,” don’t worry – you’re not the only one. Luckily, all this
happens completely automatically in the Debricked tool when
clicking this little button:

As of right now, this is available for Javascript. Soon, the
support will be extended to Java, Golang, C#, Python and PHP.

If you’re not yet a Debricked^[10] user, what are you
waiting for? It’s free for single devs, smaller teams and open
source projects (and if you’re a larger organization, fear not.
There’s a generous free trial). Sign up for free
here^[11].