Repository navigation
Quadratic time in scheme-less domain scan on crafted plain text #115
Description
With url_must_have_scheme(false), LinkFinder::links runs in time quadratic to the input length on certain plain-text inputs. Every . becomes a trigger, so for each dot the domain scanner runs. find_domain_start walks back only to the nearest label boundary, but find_authority_end then walks forward across the whole following run of authority characters. A character such as ~ sets maybe_host = false and does not break the forward scan, so the scan reads to end of input and then fails, which leaves rewind unmoved, and the next dot repeats the same full forward walk. Tested against linkify 0.11.0.
An input built from the repeating unit a.a~ shows 4x growth in wall-clock time per doubling of input size, measured on a --release build:
bytes links ms ratio
49152 0 417.06 -
98304 0 1703.13 4.08
196608 0 6711.25 3.94
393216 0 27017.38 4.03
A 192 KB input already takes about 6.7 seconds. Plain prose, a plain letter run, and a dotted chain such as a.a. scale linearly on the same harness (about 2x per doubling) and finish in well under a millisecond at these sizes.
Reproducer
Cargo.toml:
[dependencies]
linkify = "0.11.0"src/main.rs, run with cargo run --release:
use linkify::LinkFinder;
use std::time::Instant;
fn main() {
let mut finder = LinkFinder::new();
finder.url_must_have_scheme(false);
for k in [48usize, 96, 192, 384] {
let n = k * 1024;
let unit = "a.a~";
let mut input = unit.repeat(n / unit.len() + 1);
input.truncate(n);
let t = Instant::now();
let count = finder.links(&input).count();
println!("{:>7} bytes {:>3} links {:>9.2} ms", n, count, t.elapsed().as_secs_f64() * 1000.0);
}
}Scope
An application that turns on the scheme-less domain mode and feeds it text from an outside source can be pushed into seconds of CPU per request with an input under 200 KB, and worse with a larger one. The growth is quadratic, so a small increase in input size produces a large increase in processing time. That gives a cheap denial-of-service lever against any service scanning user-supplied text in this configuration.
Activity
robinst commentedon Aug 23, 2026
Thanks for raising this. Did you have a proposed solution for fixing it?
andrewsuperlegit commentedon Aug 23, 2026
@robinst i looked into it last night and started reading about search implementations that use Aho-Corasick algo + State Machine that would move the complexity from quadratic time to constant or linear time but itd require a pretty substantial rewrite i think. like... we'd have to get a pretty exhaustive list of top level domains and delimiters and match those and i think we'd have to reverse the direction of search or something.
i think for the list of top level domains itself we'd want to look into see if theres a crate that's job it is to keep track of all the new tlds as they come out; i wouldnt want to hardcode every possible tld in this crate and keep it updated bc i dont know how often they add new tlds.
hey-jj commentedon Aug 24, 2026
yes, it's a one-line early break in
find_authority_end. in src/domains.rs, at the top of thefor (i, c) in s.char_indices()loop:the quadratic behavior is on the scheme-less path: every
.is a trigger, and each trigger scans forward over the whole authority run._or~setsmaybe_host = falsewithout stopping the scan, so the loop walks to the end of the input just to return(None, None)... and the next.repeats the walk.the break is safe because once that condition holds, the function is COMMITTED to returning
(None, None).maybe_hostcan only come back true via the@arm, and that arm already returns early when userinfo isn't allowed. so the break changes how far the loop scans, not which links are found. the!userinfo_allowedclause is what keeps~/_usable in userinfo, sohttps://user~name@example.com/still parses. with the guard, the scan over the reported input is linear.happy to open a PR with the change and a regression test.