# walkabout — CWE-407 Disclosure Brief
**2026-03-27 · Patch available — awaiting upstream merge**

**Security contact:** pylons-project-security@googlegroups.com

## Finding

Four defects in walkabout's `TopologicalSorter` — the same quadratic and O(E²) patterns found in Pyramid/util.py, which descended from this implementation. All patched. Patches ready for upstream review.

## The Defects

**walkabout-0001 (PATCHED — MEDIUM):** `walkabout/__init__.py:111`

```python
# In TopologicalSorter.add() — called per tween/view registration:
if name in self.names:   # O(N) list scan — self.names is a plain list
```

`self.names` is a `list` (line 65). Every call to `add()` does an O(N) scan. **O(N²) total** for N items. **334× speedup** with `set`.

**walkabout-0002 (PATCHED — MEDIUM):** `walkabout/__init__.py:178,186`

```python
# In TopologicalSorter.sorted():
root = roots.pop(0)         # O(n) — list shift
roots.insert(0, child)     # O(n) — list shift
```

`roots` is a plain list. `pop(0)` and `insert(0, ...)` are O(n) each. Fix: `collections.deque` for O(1) `popleft()`. **176× speedup.**

**walkabout-0003 (PATCHED — MEDIUM):** `walkabout/__init__.py:84-85,89-90`

```python
# In TopologicalSorter.remove() — per edge removal:
for u in after:
    self.order.remove((u, name))   # O(E) list scan per edge

for u in before:
    self.order.remove((name, u))   # O(E) list scan per edge
```

`self.order` is a list (line 71). Removing E edges: **O(E²)**. Fix: `set.discard()`. **845× speedup.**

**walkabout-0004 (PATCHED — MEDIUM):** `walkabout/__init__.py:159`

```python
# In TopologicalSorter.sorted() edge loop:
for a, b in order:
    if a in names and b in names:   # O(N) × 2 per edge
```

Local `names` list scanned twice per edge across E edges: **O(N×E)**. Fix: pre-built `set`. **248× speedup.**

## Complexity Proof

**walkabout-0001:** N items × O(N) list scan: **O(N²)**. **334× op reduction.**

**walkabout-0002:** N nodes × O(n) deque ops: **O(N²)**. **176× op reduction.**

**walkabout-0003:** E edges × O(E) list remove: **O(E²)**. **845× op reduction.**

**walkabout-0004:** E edges × O(N) list scan × 2: **O(N×E)**. **248× op reduction.**

## Impact

walkabout is the original `TopologicalSorter` implementation used throughout the Pylons ecosystem for ordering tweens, views, and derivers. Applications that register many views or tweens (large Pyramid apps built on walkabout) maximize N on every startup. The same defects were also patched in Pyramid/util.py (pylons-0001/0002/0003, pyramid-0004) — walkabout is the upstream source.

## The Fix

**walkabout-0001:** Shadow set for O(1) membership:

```python
# CWE-407 fix: shadow set for O(1) membership instead of O(N) list scan.
if name in self._names_set:
    ...
```

**walkabout-0002:** `collections.deque` for O(1) popleft:

```python
# CWE-407 fix: deque for O(1) popleft; shadow set for O(1) membership.
from collections import deque
roots = deque()
roots.popleft()
```

**walkabout-0003:** `set.discard()` instead of `list.remove()` in loop:

```python
# CWE-407 fix: set of tuples for O(1) discard instead of O(E) list scan per edge.
self._order_set.discard((u, name))
```

**walkabout-0004:** Pre-built set before edge loop:

```python
# CWE-407 fix: set for O(1) membership instead of O(N) list scan per edge.
names_set = set(names)
for a, b in order:
    if a in names_set and b in names_set:
```

## Patch

Fix available: `defects/walkabout/patch/walkabout-0001-0004-names-set-deque.patch`

Four-location patch in `walkabout/__init__.py`. Unit test: 4/4 pass. walkabout-0001: **334×**. walkabout-0002: **176×**. walkabout-0003: **845×**. walkabout-0004: **248×**.

## What We Ask

Patches are ready for review. Please send replies to **pylons-project-security@googlegroups.com**.

1. Confirm receipt and assign a Pylons tracker or GitHub issue reference.
2. Assess severity — these are startup-time costs for every walkabout-based application.
3. Coordinate a disclosure date — we are targeting 90 days from first contact.
4. We will credit the walkabout/Pylons team in the public disclosure. Preferred acknowledgment format welcome.

This brief is confidential until coordinated disclosure. Full report: https://undefect.com
