HTTP wildcard detection can stall an entire scan for tens of minutes in compare_body (quadratic DeepDiff pairing, holds the GIL)

[liquidsec]

Describe the bug

A single HttpCompare.compare_body call can run for tens of minutes, holding the GIL, which
stalls the whole scan: queues drain to empty, no events are produced, one module sits in
processing, and the scan never reaches its finishing stage. Expected: a body comparison
completes in bounded time, or is skipped.

BBOT Command

No specific command required — the path is reached from is_http_wildcard_host during
ordinary web probing, so any scan that probes a large catch-all host can hit it. Observed on a
scan whose enabled modules included no HttpCompare user at all
(aggregate, cloudcheck, csv, dnsresolve, excavate, http, hunt, js_unpacker, json, ntlm, python, speculate, sslcert, txt, unarchive, wayback). A standalone reproduction that needs no
network is included below.

OS, BBOT Installation Method + Version

OS: Linux, installation: pip from git, BBOT version: 3.0.1
(bleeding-edge @ e7ad6941f3348c3e57664b71cd2491d69f67b91f), CPython 3.13, deepdiff 9.1.0.

Logs/Screenshots

Status output repeated unchanged for over ten minutes with totals frozen, all queues empty,
one module in processing, and the process pegged at ~97% CPU on one core. The py-spy dump
below is more informative than the logs and is included in place of them.

---

Summary

HttpCompare.compare_body calls DeepDiff(..., ignore_order=True, threshold_to_diff_deeper=0)
on two HTTP bodies. For non-XML bodies the inputs are lists of lines
(response.text.split("\n")). When the two bodies are highly similar but differ on many
lines, DeepDiff's ignore_order pairing runs, and its cost is quadratic in the number of
differing lines, constructing a nested DeepDiff per candidate pair.

Measured below with BBOT's exact arguments: 400 differing lines takes 18 seconds, 800 takes
73 seconds, and 1600 does not finish within two minutes.

The comparison is pure Python and never releases the GIL, but it runs via
run_in_executor_cpu, whose documented contract is "short CPU-bound work that releases the
GIL". So one slow comparison does not merely delay its caller — it starves the event loop
driving the whole scan. Observed: a scan sat for over fifteen minutes at ~97% CPU on one
core with every module queue empty, no events produced, one module stuck in processing,
and the scan unable to reach its finishing stage.

What makes this more than a corner case is where the call comes from. The comparison is
reached from is_http_wildcard_host in the web helper, not from a module, so it can fire on
ordinary web probing regardless of which modules are enabled — the scan where this was
observed had no HttpCompare-using module in its module set. And the input shape it produces
is the worst case for the algorithm, for a structural reason described below.

Environment

• bbot 3.0.1, bleeding-edge @ e7ad6941f3348c3e57664b71cd2491d69f67b91f
• deepdiff 9.1.0
• CPython 3.13, Linux

Where the time goes

py-spy dump of a stalled scan process; the only active thread, trimmed to the relevant
frames:

Thread (active+gil): "ThreadPoolExecutor-1_0"
    __init__ (deepdiff/diff.py:403)
    _get_rough_distance_of_hashed_objs (deepdiff/diff.py:1364)
    _get_most_in_common_pairs_in_iterables (deepdiff/diff.py:1531)
    _diff_iterable_with_deephash (deepdiff/diff.py:1730)
    _diff_iterable (deepdiff/diff.py:862)
    _diff (deepdiff/diff.py:2206)
    __init__ (deepdiff/diff.py:407)
    compare_body (bbot/core/helpers/diff.py:242)
    _compare_sync (bbot/core/helpers/diff.py:345)
    run (concurrent/futures/thread.py:59)

__init__ appears twice: _get_rough_distance_of_hashed_objs builds a fresh DeepDiff for
each candidate pair it scores.

Why this shape is the worst case, and why wildcard detection produces it

Three things combine.

1. Bodies are compared as lists of lines. core/helpers/diff.py:332-334 — XML is parsed,
and everything else becomes response.text.split("\n"). An HTML page is therefore a list of
a few thousand strings.

2. ignore_order=True makes DeepDiff pair unmatched items by distance.
core/helpers/diff.py:242:

ddiff = DeepDiff(
    content_1,
    content_2,
    ignore_order=True,
    view="tree",
    exclude_paths=self.ddiff_filters,
    threshold_to_diff_deeper=0,
)

If every line differs, DeepDiff's intersection cutoff declines to pair anything and the
diff is cheap. If most lines match and a subset differs, the cutoff is satisfied, pairing
runs across the unmatched items on both sides, and cost grows with the square of that subset.
threshold_to_diff_deeper=0 also removes the escape hatch that would report a wholesale
replacement rather than recursing.

3. Wildcard detection deliberately manufactures that shape.
core/helpers/web/web.py:699 _probe_wildcard_host fetches two random nonexistent paths as
a baseline, then compares the site root against it to decide whether the host answers
everything identically. On a catch-all host — the case the check exists to detect — all three
responses are the same large page, differing only where the requested path, a token, or a
timestamp is echoed into it. That is precisely "highly similar, many differing lines". The
bigger the catch-all page, the worse it gets, and the check is reached from the web helper
rather than from a module, so enabling no fuzzing modules does not avoid it.

Reproduction

repro.py (below) uses BBOT's exact DeepDiff arguments on two line-lists that are identical
except for a leading subset:

  lines  differing      pairs    seconds
   2000        100      10000       1.29
   2000        200      40000       4.14
   2000        400     160000      17.99
   4000        800     640000      73.47
   8000       1600    2560000    >120  (did not finish)

Doubling the differing-line count multiplies the time by roughly four.

Shapes that do not reproduce it, which are worth knowing when triaging:

• every line differing (2000 lines): 0.31s — the intersection cutoff skips pairing
• a single differing line in 2000: 0.11s
• lists of dicts with all values differing (3200 items): 2.7s

import time
from deepdiff import DeepDiff

DEEPDIFF_ARGS = dict(ignore_order=True, view="tree", threshold_to_diff_deeper=0)


def page(total_lines, differing_lines, salt):
    lines = []
    for i in range(total_lines):
        if i < differing_lines:
            lines.append(f'  <div class="row r{i}" data-token="{salt}{i}"><span>item {i}{salt}</span></div>')
        else:
            lines.append(f'  <div class="row r{i}"><span>item {i}</span></div>')
    return lines


print(f"{'lines':>7} {'differing':>10} {'seconds':>10}")
for total, differing in ((2000, 100), (2000, 200), (2000, 400), (4000, 800), (8000, 1600)):
    a, b = page(total, differing, "a"), page(total, differing, "b")
    start = time.monotonic()
    DeepDiff(a, b, **DEEPDIFF_ARGS)
    took = time.monotonic() - start
    print(f"{total:>7} {differing:>10} {took:>10.2f}", flush=True)
    if took > 120:
        break

Suggested directions

Any one of these breaks the quadratic behaviour; the first two look cheapest.

• Bound the input before diffing. Skip or truncate bodies past a line or byte threshold.
  A body large enough to be slow here is also one where a full structural diff earns little
  over a cheaper signal.
• Give DeepDiff a budget. max_passes, max_diffs or cutoff_intersection_for_pairs
  let it stop; today it has no limit.
• Reconsider ignore_order=True for text bodies. Line order in an HTML response is
  meaningful, and order-insensitive pairing is what invokes the expensive path. For the
  question actually being asked — did the body change — a sequence or set comparison would
  answer it far more cheaply.
• Do not run it on the GIL-bound pool, or bound it in time. Even with the above, a
  pure-Python comparison dispatched through run_in_executor_cpu can stall the loop; that
  helper's own docstring reserves it for work which releases the GIL.

A related note: once such a comparison is running, it cannot be cancelled. A scan stopped or
abandoned while a comparison is in flight leaves the thread burning CPU and holding the GIL
for as long as the diff takes, which affects anything else sharing that interpreter.

Affected callers

is_http_wildcard_host / _probe_wildcard_host in core/helpers/web/web.py reach it during
ordinary web probing. Beyond that, everything built on HttpCompare: paramminer_headers,
url_manipulation, bypass403, webbrute, nowafpls, and lightfuzz with its sqli,
cmdi, path, crypto and serial submodules.

Evidenced vs inferred

Evidenced: the stack, the code path, the timing table, the GIL and executor mismatch, and a
fifteen-minute stall with idle queues in a scan whose enabled modules included no
HttpCompare user.

Inferred: that the specific stalled comparison was a wildcard probe against a large catch-all
page. That is the only enabled path to compare_body in that scan, but the two bodies were
not captured. Logging body size and elapsed time around compare_body would confirm it and
would be worth having regardless.