一句话：提出 Pacsolve 框架与 Maxnpm，用 Max-SMT 将依赖求解建模为可定制约束与多目标优化问题，替代 NPM 的贪心算法。
NPM 依赖求解器的贪心策略存在多个问题：无法安装最新版本依赖、产生重复依赖与代码膨胀、漏洞修复算法可能引入新漏洞、重复依赖会破坏有状态框架，而现有工具要么脆弱、要么事后修改依赖树、要么不保证最优或不可组合。本文提出 Pacsolve，一个支持可定制约束与优化目标的统一依赖求解框架，将依赖管理建模为 Max-SMT 问题；在其上构建 Maxnpm，作为 NPM 的完整即插即用替代品，允许开发者在安装依赖时组合多个优化目标。作者在 NPM 生态的大规模包样本上进行评估，结果显示 Maxnpm 在 33% 的情况下比 NPM 审计工具减少更多漏洞依赖，在 14% 的情况下选择更新的依赖，在 21% 的情况下选择更少的依赖。所有代码与数据均开源。
Package managers such as NPM have become essential for software development. The NPM repository hosts over 2 million packages and serves over 43 billion downloads every week. Unfortunately, the NPM dependency solver has several shortcomings. 1) NPM is greedy and often fails to install the newest versions of dependencies; 2) NPM's algorithm leads to duplicated dependencies and bloated code, which is particularly bad for web applications that need to minimize code size; 3) NPM's vulnerability fixing algorithm is also greedy, and can even introduce new vulnerabilities; and 4) NPM's ability to duplicate dependencies can break stateful frameworks and requires a lot of care to workaround. Although existing tools try to address these problems they are either brittle, rely on post hoc changes to the dependency tree, do not guarantee optimality, or are not composable. We present Pacsolve, a unifying framework and implementation for dependency solving which allows for customizable constraints and optimization goals. We use Pacsolve to build Maxnpm, a complete, drop-in replacement for NPM, which empowers developers to combine multiple objectives when installing dependencies. We evaluate Maxnpm with a large sample of packages from the NPM ecosystem and show that it can: 1) reduce more vulnerabilities in dependencies than NPM's auditing tool in 33% of cases; 2) chooses newer dependencies than NPM in 14% of cases; and 3) chooses fewer dependencies than NPM in 21% of cases. All our code and data is open and available.
@inproceedings{PinckneyCGBCG23,
title = {Flexible and Optimal Dependency Management via Max-SMT},
author = {Donald Pinckney and Federico Cassano and Arjun Guha and Jonathan Bell and Massimiliano Culpo and Todd Gamblin},
booktitle = {ICSE},
year = {2023},
doi = {10.1109/icse48619.2023.00124}
}