russell@unturf.com
0a580b313d
Authors: russell@unturf.com · brackishbert@gmail.com · foxhop.net · TimeHexOn.com Patches, unit tests, benchmarks, whitepaper, and outreach briefs. Public domain — no copyright claimed. Use freely.
104 lines
4 KiB
ReStructuredText
104 lines
4 KiB
ReStructuredText
Composer — CWE-407 Analysis
|
||
============================
|
||
|
||
.. contents:: :local:
|
||
|
||
Overview
|
||
--------
|
||
|
||
Composer is the de facto PHP package manager, used by virtually all PHP projects.
|
||
Its dependency resolver uses a CDCL/SAT-based solver (``DependencyResolver/``) with
|
||
a pool of package objects. It also provides display and diagnostic commands
|
||
(``composer why``, ``composer show --tree``, ``composer depends``) that traverse the
|
||
installed dependency graph.
|
||
|
||
**Status: 2 confirmed defects — MEDIUM severity, both unpatched**
|
||
|
||
The installation solver is CLEAN. The defects are in the graph traversal code used
|
||
for display and diagnostic commands.
|
||
|
||
Confirmed Defects
|
||
-----------------
|
||
|
||
.. list-table::
|
||
:header-rows: 1
|
||
:widths: 15 40 20 10 15
|
||
|
||
* - ID
|
||
- File:Line
|
||
- Pattern
|
||
- Complexity
|
||
- Severity
|
||
* - composer-0001
|
||
- ``Repository/RepositoryUtils.php:46``
|
||
- ``in_array($candidate, $bucket)`` in ``filterRequiredPackages`` foreach
|
||
- O(N²) + O(N³) recursive
|
||
- MEDIUM
|
||
* - composer-0002
|
||
- ``Repository/InstalledRepository.php:128,154,167,180``
|
||
- ``in_array($pkg, $packagesInTree)`` × 4 in ``getDependents``
|
||
- O(N² × L × K)
|
||
- MEDIUM
|
||
|
||
Defect Detail — composer-0001
|
||
-------------------------------
|
||
|
||
``RepositoryUtils::filterRequiredPackages()`` finds all transitively required packages
|
||
using a PHP array ``$bucket`` for the result/visited set::
|
||
|
||
foreach ($packages as $candidate) { // O(N) packages
|
||
foreach ($candidate->getNames() as $name) {
|
||
if (isset($requires[$name])) {
|
||
if (!in_array($candidate, $bucket, true)) { // O(|bucket|) = O(N) worst case
|
||
$bucket[] = $candidate;
|
||
$bucket = self::filterRequiredPackages($packages, $candidate, ...);
|
||
|
||
``in_array()`` on a PHP array is a sequential scan — O(n). ``$bucket`` grows to O(N)
|
||
as packages are found. Top-level cost is O(N²); with recursive calls for transitive
|
||
dependencies, O(N³) worst case.
|
||
|
||
For a Symfony project with 200 installed packages, this is 40,000 comparisons per
|
||
``composer why`` call.
|
||
|
||
**Fix:** Replace ``$bucket`` array with an associative hash keyed on ``spl_object_id($candidate)``;
|
||
use ``isset()`` for O(1) membership. Return ``array_values($bucket)`` at the boundary.
|
||
|
||
Defect Detail — composer-0002
|
||
-------------------------------
|
||
|
||
``InstalledRepository::getDependents()`` traverses the dependency graph for
|
||
``composer show --tree`` and ``composer depends --tree``::
|
||
|
||
foreach ($this->getPackages() as $package) { // O(N)
|
||
...
|
||
foreach ($links as $link) { // O(L links/package)
|
||
foreach ($needles as $needle) { // O(K needles)
|
||
if (in_array($source, $packagesInTree)) { // O(|tree|) = O(N) growing
|
||
|
||
``$packagesInTree`` is a PHP array that grows as packages are added with
|
||
``$packagesInTree[] = $link->getSource()``. Four call sites (lines 128, 154, 167, 180)
|
||
all scan this same growing array.
|
||
|
||
**Fix:** Thread a ``$packagesInTreeSet`` associative array alongside ``$packagesInTree``;
|
||
replace ``in_array($x, $packagesInTree)`` with ``isset($packagesInTreeSet[$x])``.
|
||
|
||
Solver Core — CLEAN
|
||
--------------------
|
||
|
||
The CDCL/SAT dependency solver (``DependencyResolver/Solver.php``,
|
||
``DependencyResolver/RuleSet.php``, ``DependencyResolver/Pool.php``) is clean:
|
||
|
||
- Package lookup by name: ``$this->packages`` via associative hash — O(1)
|
||
- Rule propagation: integer-indexed arrays, O(1) access by package ID
|
||
- ``Pool::isUnacceptableFixedOrLockedPackage()``: O(n) scan on
|
||
``$this->unacceptableFixedOrLockedPackages``, but this list is bounded to
|
||
single digits in practice (explicit lock overrides only). Not flagged.
|
||
|
||
The defects are entirely in the display/diagnostic layer, not the solver.
|
||
|
||
Scan Details
|
||
------------
|
||
|
||
* Scanner: ``tools/scans/composer.sh``
|
||
* Scan result: ``tools/scan-results/composer.txt`` — 29 candidates; 2 confirmed
|
||
* Scanned: ``DependencyResolver/``, ``Package/``, ``Repository/``, ``Util/``
|