russell@unturf.com 9934133dcf whitepaper: 312 sites / 151 ecosystems — wave2+3 defect tables and PDF rebuild

Add 88 new defect entries to HIGH and MEDIUM tables:
  HIGH: mysql-0001/0002, mariadb-0001, redis-0001/0002, valkey-0001/0002, openvpn-0001,
        vlc-0001, prometheus-0001, otel-collector-0001, cockroachdb-0001..0004,
        tidb-0001..0008, kubernetes-0001/0002, go-0001, kotlin-0002, scala-0001,
        allegro5-0001, sdl2-0001, grafana-0001, clickhouse-0001, duckdb-0001,
        mongodb-0001, envoy-0001, istio-0001, cilium-0001, linkerd2-0001,
        linux-0001/0002/0003, tor-0002/0003, curl-0001, julia-0001, lua-0001,
        perl5-0001, nats-0001, spring-0003/0004, tomcat-0001, onos-0002, odl-0002

  MEDIUM: helm-0001, mariadb-0002, openssl-0001/0002, memcached-0001,
          cassandra-0001..0004, flink-0001, storm-0001/0002, zookeeper-0001..0003,
          pip-0001, gradle-0001, nginx-0001, haproxy-0001, caddy-0001, varnish-0001,
          ffmpeg-0001, gstreamer-0001, raylib-0001, love2d-0001, php-0001/0002,
          r-source-0001, cpython-0002, ruby-0001, rabbitmq-0003/0004, activemq-0001,
          ovs-0001, onos-0003, odl-0002, jetty-0001

PDF: 976K

2026-03-27 15:23:43 -04:00

2.1 KiB

Raw Permalink Blame History

haproxy-0001: pat_match_bin list walk below LRU threshold

Target: haproxy File: src/pattern.c Function: pat_match_bin (also pat_match_sub, pat_match_end, pat_match_beg) Lines: 559–588 Severity: HIGH CWE: CWE-407 (Inefficient Algorithmic Complexity)

Description

HAProxy evaluates ACL patterns on every request. pat_match_bin walks a linked list of binary patterns with list_for_each_entry on every call:

list_for_each_entry(lst, &expr->patterns, list) {
    pattern = &lst->pat;

    if (pattern->ref->gen_id != expr->ref->curr_gen)
        continue;

    if (pattern->len != smp->data.u.str.data)
        continue;

    if (memcmp(pattern->ptr.str, smp->data.u.str.area,
               smp->data.u.str.data) == 0) {
        ret = pattern;
        break;
    }
}

The LRU cache (pat_lru_tree) only activates when entry_cnt >= 20. Below that threshold — the common case for most HAProxy ACL files — every request triggers a full O(P) list walk. With R requests/second and P patterns, total work is O(P × R).

The same defect exists in pat_match_sub, pat_match_end, and pat_match_beg (all use list_for_each_entry with no tree fallback and LRU threshold ≥ 20). pat_match_regm has no LRU at all.

pat_match_str and pat_match_beg already have an ebst_lookup / EB-tree fast path for exact/prefix matches but only when patterns were inserted into the tree; the list fallback still executes for patterns not in the tree.

Impact

Every ACL binary-match expression with 1–19 patterns: O(P) per request.
Production ACLs: 4–16 backend-selection rules, evaluated on every request.
10 000 RPS × 10 patterns = 100 000 list-node traversals/second.

Fix

Lower the LRU activation threshold from 20 to 1 for pat_match_bin. Alternatively, use a fixed-size hash map (key = length-prefixed binary value, value = pattern pointer) built at configuration commit time, consulted O(1) at request time.

Patch

See defects/haproxy/patch/haproxy-0001.patch

Unit Test

See defects/haproxy/unit/HaproxyPatMatchBinAlgorithmTest.java

2.1 KiB Raw Permalink Blame History Unescape Escape