A regex, ami megfektette a fél internetet – a V8-ban ott a gyógyszer, csak ki van kapcsolva

2019. július 2-án 27 percre elment a fél internet. Nem BGP-hiba volt, nem DDoS, még csak nem is egy markológép: a Cloudflare WAF-jába aznap került be egy új szabály, benne egy regexszel, amelynek a közepén ez a részlet ült: .*.*=.*. A világ összes Cloudflare-szerverén 100%-ra ugrott a HTTP-forgalmat kiszolgáló CPU, a forgalom nagyjából 80%-ot esett, és amíg kiderült, ki a tettes, a fél web 502-t dobált. A hivatalos post mortem azóta kötelező olvasmány – nem a bűnbánat, hanem a mellékelt regexelmélet-gyorstalpaló miatt.

A kényelmetlen igazság, hogy ehhez a produkcióhoz nem kell Cloudflare-méretű színpad. Elég egy ártatlannak látszó minta és egy balszerencsés – vagy szándékosan rosszindulatú – input. Megmértem, mekkora a robbanás egy mai Node-on, és közben találtam valamit, amiről kevesebb szó esik: a V8-ban évek óta ott lapul egy második regexmotor, ami az egészet megoldaná. Csak épp ki van kapcsolva.

Diagram: balra a regex backtracking exponenciálisan szétágazó piros fája, jobbra a lineáris motor egyenes, zöld pontokból álló útja

Mitől robban?

A JavaScript regexmotorja – a V8-ban ez az Irregexp – backtrackinggel dolgozik, ahogy a PCRE, a Java és a Python motorja is: ha egy illesztési útvonal zsákutca, visszalép, és kipróbálja a következőt. A gond az egymásba ágyazott kvantoroknál kezdődik. A ^(a+)+$ mintában a belső a+ és a külső + ugyanazt a betűsort exponenciálisan sokféleképpen tudja felosztani, és ha az input végén ott egy oda nem illő karakter, a motor az összes felosztást végigpróbálja, mielőtt kimondja, hogy nem illeszkedik.

const re = /^(a+)+$/;
for (const n of [24, 26, 28, 30]) {
  const input = 'a'.repeat(n) + '!';
  const t0 = process.hrtime.bigint();
  re.test(input);
  console.log(n, Number(process.hrtime.bigint() - t0) / 1e6, 'ms');
}

Node 22 (V8 12.4) alatt nálam ez jött ki: 24 karakter – 92 ms, 26 karakter – 379 ms, 28 karakter – 1,6 s, 30 karakter – 6,2 másodperc. Két plusz karakter mindig megnégyszerezi a futásidőt; 40 karakternél már fél napnál tartanánk. Harminc darab a betű tehát hat másodpercre lefoglal egy teljes CPU-magot – és mivel a regex szinkron fut, ilyenkor a Node event loopja is áll. Ez a katasztrofális backtracking, az erre építő támadás neve pedig ReDoS, amelynek az OWASP külön oldalt szentel.

Nem kell hozzá exponenciális

A Stack Overflow 2016-os, 34 perces leállását egy ennél is unalmasabb minta okozta: a ^[\s\u200c]+|[\s\u200c]+$, egy sima Unicode-trim. Valaki beküldött egy posztot, amelyben egy sor végén nagyjából 20 000 szóköz állt, a poszt kikerült a címlapra, a regex pedig minden címlapletöltésnél kvadratikusan – körülbelül 200 millió karakterellenőrzés árán – bizonyította be, hogy a szóközök után sajnos nem az input vége jön. A post mortem csattanója, hogy a load balancer health checkje pont a címlapot kérdezgette: amikor az belassult, a healthy szerverek is kiestek a rotációból. Nem kellett tehát exponenciális robbanás – egy O(n²)-es trim is elég volt.

És ez nem múzeumi műfaj: az npm-ökoszisztéma ma is termeli az ilyen CVE-ket. A semver csomag new Range() hívása 2023-ig ReDoS-olható volt (CVE-2022-25883) – az a semver, amelyre fél npm-világ támaszkodik, és amelynek sok szerver felhasználói inputot ad át. Tipikus találkozási pontok: validátorok, query- és route-parsolás, markdown-feldolgozás, User-Agent-elemzés, logfeldolgozó pipeline-ok. Bárhol, ahol regex fut olyan sztringen, amit nem te írtál.

A V8 rejtett lineáris motorja

Most jön a rész, amire azt mondtam: na, ezt nem tudtam. A V8-ba 2021 eleje óta be van építve egy második, nem backtrackelő regexmotor. Nem mélységi kereséssel próbálgatja az útvonalakat, hanem szélességi bejárással egyszerre lépteti az automata összes lehetséges állapotát – így garantáltan lineáris időben fut az input hosszához képest. Kísérleti V8-flagek mögött ül, de Node-ból ma is elérhető:

$ node --enable-experimental-regexp-engine
> const re = new RegExp('^(a+)+$', 'l');  // 'l' mint linear
> re.test('a'.repeat(30) + '!')   // 6200 ms helyett 0,01 ms
> re.test('a'.repeat(100000) + '!')  // 7,7 ms

A nem szabványos l flag azt jelenti: ezt a mintát mindig a lineáris motor futtassa. Ugyanaz az input, amely a backtrackelő motort 6,2 másodpercre küldte padlóra, itt 0,01 ms alatt végez, és a százezer karakteres változat is 7,7 ms. Van egy még érdekesebb üzemmód is: a --enable-experimental-regexp-engine-on-excessive-backtracks flaggel a V8 minden sima regexnél számolja a visszalépéseket, és 50 000 backtrack után (a küszöb a --regexp-backtracks-before-fallback flaggel állítható) menet közben átvált a lineáris motorra. A 34 karakteres gonosz input, ami extrapolálva bő másfél percig futott volna, ezzel a flaggel 1,6 ms alatt lefutott nálam.

Hol a csapda?

Ha ez ilyen jó, miért nem ez a default? Mert a lineáris garancia nem ingyen van. Elméleti korlát, hogy backreference és lookahead/lookbehind ezzel a megközelítéssel nem támogatható – ugyanezért nem tud ilyet a Google RE2 könyvtára sem, amelyre egyébként a Cloudflare is váltott a leállás után. A gyakorlat viszont ennél is szigorúbb: Node 22 alatt az l flag jelenleg még az i és u flaggel sem kombinálható – a new RegExp('abc', 'il') egyszerűen SyntaxErrort dob, azzal az üzenettel, hogy „Cannot be executed in linear time”. Kipróbáltam, mert nem hittem el. Egy case-insensitive e-mail-validátort tehát ma nem tudsz átrakni a lineáris motorra; egy trimet, egy tokenizálót, egy log-parsert viszont igen.

Mit csinálj ehelyett productionben?

Vágd le az inputot, mielőtt regexet engedsz rá. Egy 254 karakteres limit az e-mail-mező előtt unalmas, de a fenti táblázat szerint az unalom itt kifejezetten erény.
Kerüld az egymásba ágyazott kvantorokat és az egymást átfedő mohó részmintákat – a (a+)+ és a .*.*=.* ugyanannak a hibának a két arca.
Tedd CI-be az eslint-plugin-regexp no-super-linear-backtracking szabályát: statikusan kiszúrja a robbanásveszélyes mintákat, a fenti példáimat is mind elkapja.
Ahol tényleg ellenséges input megy regexbe, ott használj RE2-t (Node alatt a node-re2 csomag) – natív lineáris garancia, JS-kompatibilis API, cserébe le kell mondanod a backreference-ekről.

A V8-flageket productionben én ma nem kapcsolnám be: kísérletiek, bármelyik minor Node-verzióban változhatnak, és a fallback-üzemmód átváltási költségét senki sem méri helyetted. A lint + inputlimit + kritikus helyen RE2 kombó viszont olcsó, és pont azt a hibaosztályt zárja ki, amelyik a Cloudflare-nél 27 percbe, a Stack Overflow-nál 34 percbe került. A mondat, amit érdemes megjegyezni: a regex nem konstans idejű stringművelet, hanem program, ami a te CPU-dón fut – az inputját viszont néha az írja, aki nem kedvel téged.