March 27, 2025
Volume 23, issue 1

Download PDF version of this article PDF

The Surprise of Multiple Dependency Graphs

Dependency resolution is not deterministic.

Josie Anugerah and Eve Martin-Jones

There are many advantages to open source software, but like all software, it can contain bugs and vulnerabilities. Projects that depend on open source can inherit those problems, often inadvertently. In 2024, three years after the Log4Shell vulnerability, 13 percent of all Log4j package downloads were for vulnerable versions. Furthermore, 94.9 percent of vulnerable open source downloads were old versions of packages that had since been patched.

It seems like it should be easy to avoid installing vulnerable open source software, but dependency graphs are surprisingly complex. At the time of writing, the latest version of the popular npm tool webpack has millions of potential dependency graphs depending on circumstances during its resolution. The exact graph chosen for a given package can depend on what other software is being built, what kind of system is building it, and even the state of the ecosystem on a given day. As a result, the developer and user of a package may end up with very different dependency graphs, which can lead to unexpected vulnerabilities.

This article explains why dependency graphs are so complex and makes some observations about what that implies for SBOMs (Software Bill of Materials) and development practices generally.

What is a Dependency Graph?

A dependency of a software project is defined as a separate piece of software that is imported by a project for the build. A dependency is sometimes referred to as a library, package, or import. The intention of importing a dependency into a project is to save developer resources by reusing code that is already well-tested and documented.

A dependency may be versioned. Most open source packaging ecosystems (npm, Maven, PyPI, etc.) adhere at least somewhat to SemVer (specifically, Semantic Versioning 2.0).

Dependency management includes the processes used to obtain dependencies, store the dependency code, and monitor the health of these dependencies. Dependency management may be relatively easy for a project with a handful of dependencies, but modern software projects may depend on hundreds or even thousands of open source packages.

Dependencies are often specified by a list of name-requirement pairs in a requirements file, which usually has a syntax similar to that shown in figure 1.

The Surprise of Multiple Dependency Graphs

A requirement specifies a range of accepted versions for the named dependency, using a notation particular to the packaging system. For example, in npm the requirement react/^16.13.1 specifies any version of the react package greater than or equal to 16.13.1 and less than 17.0.0. SemVer defines a total ordering of versions; however, most ecosystems diverge from SemVer requiring additional rules to define this total ordering.

The way requirements are specified varies widely between ecosystems. While many ecosystems follow SemVer for versioning, there is no universally accepted way of specifying requirements.

A dependency resolution tool decides which version of each dependency should be used in the build to satisfy all the requirements (see figure 2). The usual approach is to read a requirements file and choose a version for each package that satisfies the requirements, then download these package versions from an external package registry such as npmjs.org.

The tool needs to select versions for transitive dependencies—the dependencies of dependencies—in addition to direct dependencies. This is because dependencies have their own dependency requirements, which may have their own dependency requirements, and so on. The output of the dependency resolution process is called the dependency graph.

There are Many Dependency Graphs

Intuition suggests that the requirements for a package will result in a single dependency graph. In practice, however, this is not true, and even resolving a single package's requirements could, in general, result in many dependency graphs. To see how, the popular npm module bundler webpack serves as an example.

Webpack is downloaded millions of times each week. At the time of writing (mid-2024), the latest version of webpack (5.94.0) has no known vulnerabilities. Furthermore, the dependency graph for webpack/5.94.0 as resolved by the deps.dev project also contains no vulnerabilities. This doesn't mean, however, that any installation of webpack/5.94.0 is guaranteed to have no vulnerabilities. To see how this is possible, let's analyze the process of resolving the dependency requirements of webpack/5.94.0.

The requirements file of webpack/5.94.0 mentions 23 other packages, shown in figure 3.

These are just the direct dependencies, but the resolution process, after examining all the transitive dependencies, may add many more.

The npm tool resolves these requirements and those of the transitive dependencies into specific package versions, producing a dependency graph. Recall that dependency resolution means taking a requirement such as browserslist/^4.21.10 and selecting a version of browserslist that matches this requirement. As is often the case, many versions satisfy this requirement of browserslist. For example, 4.21.10, 4.21.11 and 4.22.0 are all valid choices.

The browserslist package also has four transitive requirements in its package.json file that must also be satisfied (figure 4). Just as there were many choices for the version of browserslist, there are many valid versions to choose from for each of its dependencies.

Enumerating all combinations of valid dependency versions that satisfy all direct and all possible transitive requirements of webpack/5.94.0 yields approximately 6.2 x 10⁴?—zillions—of possible dependency graphs.

This profusion means that any given project likely has multiple valid dependency graphs. As is explained in the next section, two different people resolving the same package could in practice get different dependency graphs. With a different dependency graph comes a different attack surface, different behavior, a different set of licenses, and a different set of vulnerabilities.

Why Don't Tools Always Produce the Same Dependency Graph for Each Package?

You might expect that the tools produce the same dependency graph every time for the same set of requirements, even though there may be zillions of valid graphs satisfying these requirements. However, this is not the case.

Due to changes in the context in which the tool is run, there are many reasons why tools don't produce the same graph. The following sections describe various mechanisms that can cause this to happen.

Dependencies aren't resolved in isolation

Most projects depend on multiple packages. Running a query on the deps.dev BigQuery dataset revealed that the average npm project has more than 85 direct and transitive dependencies, while the average Maven project has more than 20 (figure 5).

Because projects usually have multiple dependencies, the outcome of resolving one dependency alone is different from resolving that same dependency with the same requirement among other dependencies.

To take an example, suppose package A has a requirement >=1.0.0 on package B, which has three available versions: 1.0.0, 1.0.1, and 1.0.2. All three versions satisfy >=1.0.0, and so the Python pip dependency tool will choose the latest matching version, in this case, 1.0.2.

If package A were also to depend on package X, and X depends on B, the result of B may be different. If package X depends on package B with requirement =1.0.1, there would now be two constraints on B: >=1.0.0 and =1.0.1. The pip tool will try to find a version that satisfies all requirements, choosing 1.0.1 (see figure 6).

This isn't the only valid way tools handle this situation. The Node tool npm allows multiple versions of a package to be installed. Figure 7 shows how the same requirements on B are resolved differently in pip versus npm.

If you're using pip or npm, the version of B selected is different depending on the requirement context of the rest of the graph. It's not just your direct requirements that affect the versions chosen but transitive ones.

Resolutions change over time

When multiple versions satisfy a requirement, there are two main strategies that tools use for choosing between valid versions.

Tools such as Maven, Go, and NuGet (by default) choose the lowest version so that users get new features, fixes, and bugs only when they choose to update the requirement. Other tools such as npm, Cargo, and pip choose the latest version so that users automatically get new fixes, features, and bugs.

Choosing the latest version means that over time the resolution can change. As new versions are published, a new dependency graph can result (figure 8).

Because the new version (B/1.0.3) might have different dependencies from the old version (B/1.0.2), this can affect the dependency graph beyond just which version of B is selected, causing a surprising proportion of the graph to change.

The analysis from deps.dev data shows that it's common for dependency graphs to change daily. The npm ecosystem sees an average of 6.22 percent of its packages' graphs change daily, while PyPI sees a 4.63 percent change.

This churn results from the individual packages publishing new versions. While the tool itself may be deterministic, the inputs to the tool are not, as the corpus of package versions available on the registry is constantly changing.

Different tools produce different dependency graphs

Different tools often exist within an ecosystem, and these tools make different resolution decisions. For example, three different JavaScript dependency-management tools (npm, yarn, and pnpm) produce three different resolution results for the same set of npm dependencies (figures 9a and 9b).

These changes can be subtle (you might get a slightly different version of the same package installed in your graph) or dramatic (whole dependencies may not appear in one graph), but they are, nonetheless, different results.

A tool may change its behavior

Different versions of the same tool may also produce different graphs. Such algorithm changes are often done intentionally.

Versions of the NuGet tool before version 2.8 would prefer the lowest major and minor versions, but the highest patch version. Then in 2014, the NuGet team changed to the lowest-version philosophy, reasoning that it would increase the chance that users would get the same result upon running the tool again. Later versions of the tool, therefore, preferred matching the lowest version for all parts: major, minor, and patch.

Since then, many algorithmic changes have been made in NuGet. All of the tools observed at deps.dev have gone through algorithmic revisions. NuGet helpfully announces and documents these changes, but in other ecosystems these changes often go unannounced.

Resolutions differ based on system architecture

Finally, packages may specify different dependencies for different system architectures and operating systems. This means that the dependency graph may vary with the specifics of the machine in which the dependency tool is run.

For example, figure 10 shows the list of requirements for the PyPI tensorflow/2.18.0 package for Windows and Linux.

Dependency graphs that differ based on machine specifics can lead to a situation where the graph produced in the development environment is being diligently maintained, but issues in the production graph are never addressed.

Suppose the developers of a project are using Linux, but the production build is configured to run on Windows. When developers build the software project, the dependencies installed are specific to Linux. But when the program is built for production, a different set of Windows-specific dependencies may be installed.

This means that developers can scan the development build as much as they want for licensing issues and vulnerabilities, but this will not uncover certain issues in the production build. No issues may be detected in the development graph, but issues may still exist in the production graph.

That means it's crucial to scan not just what is running in the development environment, but also what is actually being deployed to production. It's also important to make the development environment as close to the production one as possible, where possible.

Development graphs differing from production graphs is not the only way this can manifest. The maintainer of the package may be managing dependencies on the platform they're developing on—say, Linux—but never think to address issues in the Windows dependency graph. Maintainers should be managing issues in the graphs for every system architecture and operating system to be supported.

Dependency graphs, not the dependency graph

For all these reasons, package-management tools may produce different dependency graphs, even if the list of dependencies is relatively small. As the dependencies grow, the number of possible resolutions grows even faster.

Users and maintainers of open source software are managing more dependency graphs than they might be aware of. There is not just one dependency graph for a package or project, but many dependency graphs. We believe this multiplicity is not widely appreciated.

SBOMs Are Not the Solution

The idea of an SBOM is often suggested as a solution to understanding dependencies. As we will see, however, SBOMs are useful only for complete binary builds; they are useless for constraining the dependencies of a downloaded package.

SBOMs work well when distributing executable applications because all the application's components are known to and controlled by the author. These components include the open source software packages that have been built into the application.

The author can list these components in an SBOM and distribute them alongside the application. Potential users can then scan the components to identify risks such as security vulnerabilities or licensing conflicts.

Open source library maintainers, however, are unable to know or control what will be installed when a user consumes their library. When the user installs the library, their package-management tool will re-resolve the dependencies of that library in the user's resolution context, disregarding the SBOM.

A library maintainer publishing an SBOM containing their dependency graph is, therefore, useless to users. Furthermore, if the library SBOM reports no vulnerabilities or issues, it gives a false sense of security. The library may still be unsafe because there is no guarantee that the user won't pull in vulnerable versions when resolving the library's dependencies in their resolution context.

Those who advocate for open source library SBOMs mistakenly assume that libraries have a single dependency graph. Multiple dependency graphs make it hard to know what vulnerabilities and licenses an open source software package is composed of. There is no easy way to address this complexity.

Dependency-Management Recommendations

Like all aspects of engineering, dependency management requires careful thought and judgment. Most engineers do code review, unit testing, integration testing, and presubmit testing on code that they write, but how often is that same level of rigor applied when assessing the code that belongs to their dependencies?

Library maintainers should evaluate the dependency complexity they may be passing on to their users. Library users should consider their chosen dependencies carefully.

Using a dependency comes with tradeoffs. It's important to evaluate these tradeoffs rigorously, based on the profile of the specific project or organization.

Consider the cost of each dependency

There is a Go proverb that says, "A little copying is better than a little dependency." Importing a dependency may not be worth the cost to maintain it and its dependencies.

If the feature you need is simple, it may be easier and safer to write and maintain a few lines of code than to maintain a larger set of dependencies. The same feature may also be available in a smaller library with fewer dependencies.

Similarly, it's useful to evaluate whether existing dependencies can be replaced or removed.

Scan what you ship

Scan the dependencies that are installed in the final production context. Don't trust that the results of SBOM scans or scans performed in a development environment apply to the production environment. Try to make the development environment as similar to the production environment as possible.

Have a dependency-management strategy

Use the requirement features provided by package-management tooling to develop a dependency strategy. This strategy may depend on whether you are a library maintainer or an application maintainer.

A strategy for maintainers is to choose requirements that accept a range of versions (open requirements). This way, when a vulnerability is reported in one of the library's dependencies, users don't need to wait for an update to the library's requirements to move off the affected version.

Application maintainers may choose to have open requirements, but also commit to regularly rebuilding the project to identify and scan new versions that are being brought into the application's dependency graph. Another approach may be to use pinned requirements to create stability in their dependency graph and upgrade those requirements only after vetting new versions.

All strategies require continuous work, but it's important to agree on and enforce a strategy for each project.

Publish clear metadata for libraries

While libraries should not publish SBOMs—because they are misleading—publishing clear metadata (like authorship, contact information, where to file bug reports, and a clear license) is extremely useful for library users.

Any components that are bundled together with the package should also be documented. These components won't change because they have already been resolved; however, documenting them clearly is important for allowing users to identify and scan them.

Unfortunately, low metadata quality affects many open source libraries across almost every ecosystem. For example, many ecosystems have provenance and authorship information as an optional free-text field, which means this metadata is often missing or incorrect. Package registries should consider automatically populating/verifying this information and/or integrating with projects such as Sigstore/SLSA (Supply-chain Levels for Software Artifacts) to give users the option to provide higher-quality provenance data.

Make open source tools that are simple and predictable

Software development can easily cause the dependency graph to change through algorithmic improvements, different architectures, version upgrades, and so on. But these changes can also cause unexpected changes to the dependency graph, and these changes need to be included in the cost of development. As the software adds dependencies, either directly or indirectly, it becomes more difficult to understand the dependency graph, which, in turn, makes it more difficult to maintain control over the graphs produced by resolution. Ecosystem maintainers should consider the features their tools provide, and whether the added complexity is worthwhile.

Resolution algorithms should be defined precisely. As it stands, the code is the only accurate documentation of how resolution works in most ecosystems. The more unpredictable or baffling the dependency graph, the harder it is to understand and maintain it.

An underappreciated problem

Despite what is widely believed, dependency resolution is not deterministic. Two actors resolving the same set of requirements may get different results.

Resolution is rarely a hermetic process. While the tools are deterministic, the inputs to these tools are not. The body of package versions available from the registry, machine architecture, operating system, and tool version are all factors that result in different resolution graphs.

Automated dependency-management tools may make users feel that the problem of dependency management is solved, but in reality, it isn't even addressed.

As the software industry's use of open source software grows, it must address the fundamental problems that the modern development model brings. One of the most underappreciated areas is the problem of dependency management and the need to work toward a set of best practices to manage that problem—in the interest of better quality and security of software projects.

Josie Anugerah is a software engineer at Google working on the Google Open Source Security Team. In particular, she works on the deps.dev project, where she leads the NuGet, container image, and artifact hash efforts.

Eve Martin-Jones is a software engineer at Google working on the Google Open Source Security Team, in particular, the deps.dev project, analyzing open source software dependencies.

Originally published in Queue vol. 23, no. 1—
Comment on this article in the ACM Digital Library