SETTINGS and stream-0 WINDOW_UPDATE frames trigger quadratic work over blocked streams in Bandit

Summary

Inefficient Algorithmic Complexity vulnerability in the HTTP/2 implementation of mtrudel bandit allows an unauthenticated remote attacker to exhaust server CPU via small SETTINGS or connection-level WINDOW_UPDATE frames. The attacker opens thousands of streams whose responses block on the connection send window, then sends cheap frames that each make the server walk the whole queue of blocked sends. In the reporter's run, with 3,000 blocked streams a single 9-byte SETTINGS frame took 133 ms to process.

do_pending_sends/2 in lib/bandit/http2/connection.ex retries every queued send and, before each retry, removes that entry from the queue with List.delete/2, so one frame costs O(n²) list operations for n blocked streams. max_concurrent_streams defaults to :infinity, so the attacker chooses n.

This issue affects bandit: from 0.3.4 before 1.14.0.

Details

1. Blocked sends

A response that outruns the connection send window is queued in pending_sends. With max_concurrent_streams defaulting to :infinity and no connection-level WINDOW_UPDATE from the client, every one of n streams ends up queued.

2. Trigger (lib/bandit/http2/connection.ex)

Every non-ACK SETTINGS frame and every WINDOW_UPDATE on stream 0 calls do_pending_sends/2. SETTINGS handling also sends deliver_send_window_update to every stream even when the window delta is 0, so unread messages pile up in the mailboxes of blocked streams.

3. Quadratic drain

do_pending_sends/2 walks the queue and calls List.delete/2 on the whole list before retrying each entry, putting it back at the front if the send is still blocked. One frame therefore costs O(n²) list operations, about 10^8 at n = 10,000.

Proof of concept

1. On one HTTP/2 connection, send 3,000 requests to an endpoint with a 20 KB response body, and send no connection-level WINDOW_UPDATE, so the responses queue in pending_sends.
2. Send an empty SETTINGS frame followed by a PING.
3. Time the PING acknowledgement. In the reporter's run, the single 9-byte SETTINGS frame delayed it by 133 ms. Repeating the frame keeps the connection process busy.

Impact

An unauthenticated remote client that keeps thousands of HTTP/2 response streams blocked makes each 9-byte SETTINGS or stream-0 WINDOW_UPDATE frame cost the server quadratic CPU work. A steady trickle of such frames keeps the connection process, and the scheduler running it, busy for as long as the attacker continues.

Workarounds

From 1.9.0, bound the number of streams a client can open, for example with http_2_options: [default_local_settings: [max_concurrent_streams: 100]], which bounds the work each frame can cause. From 0.7.0, disabling HTTP/2 with http_2_options: [enabled: false] removes the vulnerable path.