Vulnerability of Package Dependency Networks

Abstract

Software reuse by importing packages from centralised repositories is an efficient and increasingly widespread way to develop software. Given the transitivity of dependencies, defects introduced in the repository can have extensive effects on the software ecosystem. Drawing from complex network theory, we define a model of repository vulnerability based on the statistically expected damage that the repository sustains from the random introduction of software defects. We test the model in stylized networks derived from real repositories, PyPI, Maven and npm, and show that the existence of a giant strongly connected component (SCC) explains most of the vulnerability. Indeed, we found that theoretical protection (immunization) of this entire component would remove almost all vulnerability from the network. Since repositories and their communities have limited resources to mitigate issues, we further model the problem of how to best apply these resources, finding sets much smaller than the giant SCC whose protection is nearly as good. Furthermore, we prove that the optimal selection of sets of given size is NP-hard but can be approached with heuristics, yielding respectable results. Our model contributes to a better understanding of software package repositories and could also be applied to other systems with a similar structure.