pip / distlib — CWE-407 Analysis
==================================

.. contents:: :local:

Overview
--------

``pip`` is the standard Python package installer. It bundles ``distlib``, a low-level library
for package distribution operations. ``distlib`` contains a Tarjan SCC implementation in
``distlib/util.py`` that is used for dependency cycle detection during package resolution.
One CWE-407 defect site was found. It is unpatched.

This defect is present in both the bundled copy of distlib inside pip (``pip/_vendor/distlib/``)
and the standalone ``distlib`` package (versions 0.3.8 and 0.4.0, confirmed).

Defect Sites
------------

distlib-0001
~~~~~~~~~~~~

**File:** ``distlib/util.py:1180,1204``

**Pattern:**

.. code-block:: python

   # Tarjan SCC — 'successor in stack' where stack is a list
   def strong_connections(graph):
       stack = []
       lowlinks = {}
       index = {}
       sccs = []

       def strongconnect(v):
           index[v] = lowlinks[v] = len(index)
           stack.append(v)             # stack is a plain list
           for w in graph.get(v, []):
               if w not in index:
                   strongconnect(w)
                   lowlinks[v] = min(lowlinks[v], lowlinks[w])
               elif w in stack:        # O(|stack|) — list membership
                   lowlinks[v] = min(lowlinks[v], index[w])
           if lowlinks[v] == index[v]:
               scc = []
               while True:
                   w = stack.pop()
                   scc.append(w)
                   if w == v:
                       break
               sccs.append(scc)

       for v in graph:
           if v not in index:
               strongconnect(v)
       return sccs

**Why this is O(n):** ``w in stack`` where ``stack`` is a Python list; O(|stack|) per call.
This runs during ``pip install`` on every package with circular or conditional dependencies.

**Complexity:** ``O(V²)`` where V = number of packages in the dependency graph

**Patch:**

.. code-block:: python

   def strong_connections(graph):
       stack = []
       on_stack = set()    # companion set for O(1) membership
       lowlinks = {}
       index = {}
       sccs = []

       def strongconnect(v):
           index[v] = lowlinks[v] = len(index)
           stack.append(v)
           on_stack.add(v)
           for w in graph.get(v, []):
               if w not in index:
                   strongconnect(w)
                   lowlinks[v] = min(lowlinks[v], lowlinks[w])
               elif w in on_stack:    # O(1)
                   lowlinks[v] = min(lowlinks[v], index[w])
           if lowlinks[v] == index[v]:
               scc = []
               while True:
                   w = stack.pop()
                   on_stack.discard(w)
                   scc.append(w)
                   if w == v:
                       break
               sccs.append(scc)

       for v in graph:
           if v not in index:
               strongconnect(v)
       return sccs

**Data structure change:** ``list`` stack + ``in`` → ``set`` on_stack + ``in``

**Status:** Unpatched

Benchmark Results
-----------------

.. TODO: benchmark pending patch

Complexity Proof
----------------

Let V = number of packages. ``w in stack`` where ``stack`` holds up to V elements: O(V) per
check. One check per edge in DFS: O(V²) total in worst case. Companion ``set`` tracks the same
membership: O(1) per check, O(V+E) total. QED.

References
----------

* Defect ticket: ``tools/tickets/defects/distlib-0001.md``
* Affects: ``pip/_vendor/distlib/util.py`` (bundled) and ``distlib/util.py`` (standalone)
* Versions confirmed: distlib 0.3.8, 0.4.0; pip 23.x, 24.x (bundled vendor copy)
