Quadratic time in scheme-less domain scan on crafted plain text

[hey-jj]

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.

[robinst]

Thanks for raising this. Did you have a proposed solution for fixing it?

[andrewsuperlegit]

@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]

yes, it's a one-line early break in find_authority_end. in src/domains.rs, at the top of the for (i, c) in s.char_indices() loop:

if require_host && !userinfo_allowed && !maybe_host {
    break;
}

the quadratic behavior is on the scheme-less path: every . is a trigger, and each trigger scans forward over the whole authority run. _ or ~ sets maybe_host = false without 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_host can 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_allowed clause is what keeps ~/_ usable in userinfo, so https://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.