Egy hosszú post-mortem írás egy rövid kiesésről

Internet, Közösségi média

Idén július 2-án, a Cloudflare CDN egy rövidebb időre leállt. Pontosabban - mint a később jelzett posztban leírják - nem állt le, csak a forgalom 80%-át nem tudták kiszolgálni. A hiba oka egy hibás reguláris kifejezés volt, ami teljesen leterhelte a WAF-ot futtató rendszerek CPU-ját.

Pár napja megjelent egy nagyon részletes leírás az esetről. A blogbejegyzés röviden bemutatja a Clodflare-en belüli csapatokat, az egyes folyamatok működését. Részletesen feltárja a hiba okát és a végén egy kis regex tutorial is helyet kapott.

Apró érdekesség, hogy pár hónapja, az elsősorban a ModSecurity-hez készült CRS-ben is hasonló hibát találtak, amit nemrég javítottak. Az említett Cloudflare hibának nincs köze ehhez: saját WAF-ot használ, ami ugyan a CRS-re épül, de egy régebbi verzió a ruleset alapja.

( khiraly | 2019. 07. 15., h – 15:30 )

tuti evidens, de azert:

Mi az amit a .*.*=.* megfog, de a .*=.* nem?

A masik, hogy eletben nem gondolnek .*=.* ot hasznalni, ha tudom, hogy az = jel benne van a .* szabalyban.
Akkor mar inkabb [^=]*= -ot hasznalnek.

Mondjuk ha nem ezzel akkor egy masik regexppel borul a bili. Vegulis valami 4000et hasznalnak.

---
Saying a programming language is good because it works on all platforms is like saying anal sex is good because it works on all genders....

Lehet, hogy valami regex buildert (is) használnak, és ami a végén kijön, azt feltétel nélkül elfogadják. Főleg, ha a teszteken átmegy... :).

Amúgy a catastrophic backtracking-et elég nehéz felismerni algoritmussal, erre lehet, hogy jobb figyelni a CPU terhelést a tesztek futtatása során (amit a blogposzt is ír, hogy itt épp elmaradt).

> Szerintem a [^=]*= regexp ugyan az, mint az = regexp. Ez utóbbi pedig tovább nem egyszerűsíthető.

'x=x' sztringre (ami a fenti cikkben is van)

.*.*=.* regexp 12 lépést ír:
https://regex101.com/r/gU6XyA/1

A [^=]*=.* pedig 4 lépést ír:
https://regex101.com/r/wwYafN/2

A másik példájukra (eredeti cikk) 'x=xxxxxxxxxxxxxxxxxxxx' még durvább az eltérés:
4 lépés vs. 278 lépés

Szóval még mindig áll a kérdés, hogy mi a tökért volt szükség .*.* -ra a .* vagy [^=]* helyett.

---
Saying a programming language is good because it works on all platforms is like saying anal sex is good because it works on all genders....

A cikket nem olvastam, szigorúan csak a regex részről beszélek:

Példa: Alma=Jonatán

Regexnél különböző dolgokról beszélünk:

- van-e egyáltalán illeszkedés - ebben az értelemben a [^=]*= regexp és az = regexp ugyanazt adja: van illeszkedés

- hol van az illeszkedés eleje (definíció szerint a megtalálásnál az előrébb lévőt találjuk meg, kivéve ha valami módosítóval mást nem kérünk, pl: vi ":s/izé/mizé/2")- itt már eltérés van a két regex között, mert a "hosszabban leírt" rögtön a sztring elején elkezd illeszkedni, míg a rövidebb csak az 5. karakter pozíciójában illeszkedik

- és milyen hosszúság az illeszkedés (ami ugye definíció szerint csak akkor érdekes ha azonos pozícióban találuunk különböző hosszúsűgú regexet), itt szintén bekavarhat hogy alapértelmezés szerinti mohó regex, vagy valami módosító ezt korlátozza; - ebben megint eltér a kétféle regex.

De abban egyetértek az előttem szólóval, hogy ha csak ennyi a regex (és semmi más), hogy: .*.*=.* , akkor erősen nem tudom, hogy ez miben tér el a .*=.* regextől. A semmi más alatt azt értem, hogy nincs benne backreference vagy épp (csoportosítás) .

(Szóval lehet, hogy el kéne olvasni a cikket :-) )

=====
tl;dr
Egy-két mondatban leírnátok, hogy lehet ellopni egy bitcoin-t?

Válaszolok magamnak:

A cikkből egyértelműen kiderül, hogy noha a magyarázatban végig csak a .*.*=.* szerepel, ezt a regexet azért így írták meg, mert van benne csoportosítás - azaz nagy eséllyel egy általunk már nem ismert részben hivatkoznak ezekre a (zárójellel körülvett) részekre. Azaz technikailag .*(.*=.*) szerepel, ez pedig nem illeszkedik másra, mint a zárójel nélküli forma, de a zárójelek miatt lehet más az eredménye - ha például a logokba betesz dolgokat arról, hogy a waf mit fogott meg.

Mutatom (nagyon bugyuta perl kód, bocsánat):


$ perl -n -e 'print $1 ."\n" if m/.*(.*=.*)/;' << q
> Alma=Jonatán
> q
=Jonatán
$

Míg ha kihagyjuk a zárójeleket, akkor:

$ perl -ne 'print $1 ."\n" if m/.*.*=.*/;' << q
> Alma=Jonatán
> q

$

Összefoglalva: minden bizonnyal van oka, hogy az eredeti regexet így írták meg, de mivel a zárójelezés sem az illeszkedés tényét, sem a helyét, sem a hosszát - de leginkább az illeszkedés megkeresésénél a backtracking lépések számát nem befolyásolja (csak azt, hogy a megtalált sztringből megjegyez-e valamit későbbi feldolgozásra), a magyarázatban már törölte a szerző.

=====
tl;dr
Egy-két mondatban leírnátok, hogy lehet ellopni egy bitcoin-t?

(A megjegyzés megjegyzése)

Még tovább gondolkodva, a zárójelen belüli rész (az egyenlőségjelig) fel kellett volna tűnni, hogy a mimta túl van specifikálva. Mivel gyárilag a * egy mohó operátor, az első .* biztosan elvisz mindent, tehát fölösleges leírni a másodikat - még akkor is, ha a zárójel miatt kell (látszóag később felhasználják). Tippre az lehet, hogy a .*(.*=.*) minta zárójelek közötti része és a zárójelen kívüli rész nem ugyanakkor került a mintába, így nem tűnt fel, hogy az első tag kiüti a második felét.

Az érdekes, hogy az eset hatására váltottak PCRE-ről re2-re, holott egyértelműen emberi figyelmetlenség eredménye, hogy átment az ellenőrzésen egy "túlragozott" regexp. (Ráadásul a re2 saját doksija szerint bizonyos Perl / PCRE konstrukciókat nem is támogat. Akkor mind a 4000 regexpjüket újravizsgálják, valamint mostantól ezeket a hiányzó konstrukciókat kidodják az elméjükből?)

És akkor még nem beszéltem arról, hogy a (?: ) kontrukció olyan capture buffer-t hoz létre (vajon hogy van ez magyarul?), amire később nem lehet hivatkozni. (Már ha jól értem a perlre doksiban szereplő infót.) Fenti példám is módosul:

$ perl -n -e 'print $1 ."\n" if m/.*(?:.*=.*)/;' << q
> Alma=Jonatán
> q

$

NEM ÉRTEM.

=====
tl;dr
Egy-két mondatban leírnátok, hogy lehet ellopni egy bitcoin-t?

Azért az ilyen bonyxolultságú regexeket szoktam (volt) érteni. :-(

Itt nekem az a nem világos, hogy miért írok le egy ilyet: (?:akármi). És ugyanis úgy gondolnám, hogy akkor zárójelezek, ha KELL:

- vagy mert valamely operátorral a kombinált kifejezést szeretném megetetni; itt ez nem áll fenn
- vagy mert a megjegyzett találattal csinálnék valamit: de itt ez sem állhat fenn, ha egyszer a ?: miatt nem jegyzi meg.

Vajon mi lehet az a harmadik ok, amiről nem tudunk. Mármint eltekintve a macskától.

=====
tl;dr
Egy-két mondatban leírnátok, hogy lehet ellopni egy bitcoin-t?

Csak partvonalrol:
lehet, hogy a regexpet kellene dobni.

Ez a usecase erosen hasonlit arra, amikor html-t ertelmez az ember regexppel.

En barmikor kezdtem regexppel mindig allapotgep es tokenizalonal kotottem ki. De az allapotgep is tok ritka am a librarykben.
(nekem csak adott reszt kellett megtalalnom es felturboznom).

---
Saying a programming language is good because it works on all platforms is like saying anal sex is good because it works on all genders....

Érdemes ránézni erre a RE2-re. Ez speciel egy állapotgép alapú regex-library, és mint ilyen pont nem lehet úgy túlhajtani, mint ezeket a backtracking algoritmussal operáló megvalósításokat. (A kiinduló cikkben is pont ezt írják, hogy ezért váltanak/váltottak.

=====
tl;dr
Egy-két mondatban leírnátok, hogy lehet ellopni egy bitcoin-t?

Azért az ilyen bonyxolultságú regexeket szoktam (volt) érteni. :-(

Valszeg félreértettél - és akkor bocsánat, nem a te tudásodat akartam minősíteni. Azt hittem a kép megmagyarázza (a poént).

Itt nekem az a nem világos, hogy miért írok le egy ilyet: (?:akármi). És ugyanis úgy gondolnám, hogy akkor zárójelezek

Remélem nem úgy tűnik, hogy én vágom az egészet :), de szerintem a "nem jegyzi meg" nem biztos, hogy úgy van, ahogy te érted.

Itt van két példa:

https://regex101.com/r/CkOIUY/1 - ez, bár zárójelezve van, egy találatnak minősül (full match)
https://regex101.com/r/ilrGZJ/1 - itt pedig van egy full match, és egy group match.

Hogy a group match-al mit csinál az alkalmazás, az passz.

A macskát nem értem.

Nincs probléma, értettem. Válaszaim

- a cikbben emlegetett PCRE neve (Perl Compatible Regex) nekem elegendő ahhoz, hogy ha valami számomra ismeretlen vagy épp homályos egy regex-ben, akkor elővegyem a Perl doksiját. A "man perlre" pontosan azt tárgyalja, hogy a hagyományos (ed/sed/grep/egrep/awk/lex) készlethez képest (aminek azért tudom a jelentését) pontosan miket is vezetett be Larry a Perl írásakor - azaz azokat a konstrukciókat, amiket sajnos nekem még szoknom kell. Ilyen volt pl. ez a (?: ) konstrukció is. A doksiban pedig ez áll (a Regular expressions rész Extended patterns szövegében) : kerek zárójelekkel csoportosításokat hozunk létre, un. capture group-okat (vagy capture buffer-eket), amelyekre a jól ismert backreference konstrukcióval lehet hivatkozni. Régebben ez volt a \1 .. \9, aztán ez Perlben ki lett bővítve, és többek között megjelent a $1 .. $9 forma (meg most olvasom, hogy más forma is). A keresett kifejezésről pedig szó szerint ez áll a man-ban:
====
"(?:pattern)"

This is for clustering, not capturing; it groups subexpressions like "()", but doesn't make backreferences as "()" does.
====
Azaz a csoportosítást megcsinálja (azaz gondolom lehet mögé * / + / ? / {n,m} sokszorozót írni), de nem jegyzi meg az illeszkedő sztringet - tehát később nem hivatkozhatsz rá a \1 (vagy $1) backreference segítségével. (A perlre man ír mindenféle egyebet is - teljesítményről, erőforrásfelhasználásról is, de nyilván azok itt most nem számítanak.)

(A regex101.com -os linkjeid szntén - szerintem - engem igazolnak azzal kapcsolatban, hogy (?:pattern) esetén nincs megjegyzett szövegrész - jobb közép ablakban: Group: sor nincs, csak a Full match.)

És ami az én bajom: ez szerepel a cikkben, mint problémás regex

(?:(?:\"|'|\]|\}|\\|\d|(?:nan|infinity|true|false|null|undefined|symbol|math)|\`|\-|\+)+[)]*;?((?:\s|-|~|!|{}|\|\||\+)*.*(?:.*=.*)))

És ugye itt agyalok már második este a kifejezés legvégén, ahol jól láthatóan az utolsó (?:.*=.*) mögött nincs sokszorozó (tehát e miatt nem kéne zárójelezni; és mivel a ?:-tal letiltom az illeszkedő sztring megjegyzését is, következésképpen az se lehet, hogy megjegyezném mondjuk a log-hoz az illeszkedő szöveget, tehát akkor mi a fenéért is zárójeleztem, ha a zárójelezés 2 funkciója közül egyiket se használom????

Azaz érzésre az ominózus regex végén ez kellene - és ugyanazt jelentené:

.*.*=.*))

- ennél viszont már talán feltűnne, hogy az egymást követő két .* egész egyszerűen redundáns, mert a első példány mohón elnyel mindent a második elől, és így lehetne csak .*=.* formában írni - ezzel pedig valszeg egy vagon visszalépést meg lehetne spórolni az illeszkedés megkeresésekor. (Aminek szerintem simán lehet az a következménye, hogy a Cloudflare sokkal később borult volna meg.)

(A macska az általad linkelt képen a regex-generátor és arra utaltam, hogy ha csak nem így állt elő a problémás kifejezés, akkor nem értem, hogy miért nem tűnt fel a QA során, hogy redundáns a minta.)

=====
tl;dr
Egy-két mondatban leírnátok, hogy lehet ellopni egy bitcoin-t?

Ja egy érdekesség a (?pattern) tipusú kifejezésekről, szintén a man perlre doksiból. Larry ugyan figyelmezteti a világot, de mint látszik, hiába:

===
A question mark was chosen for this and for the minimal-matching construct because 1) .... 2) whenever you see one, you should stop and "question" exactly what is going on. That's psychology....
===

Hát a Cloudflare mérnökeinek nem jött be ez a megállás és elgondolkodás.

=====
tl;dr
Egy-két mondatban leírnátok, hogy lehet ellopni egy bitcoin-t?

A keresett kifejezésről pedig szó szerint ez áll a man-ban:
====
"(?:pattern)"

This is for clustering, not capturing; it groups subexpressions like "()", but doesn't make backreferences as "()" does.
====
Azaz a csoportosítást megcsinálja (azaz gondolom lehet mögé * / + / ? / {n,m} sokszorozót írni), de nem jegyzi meg az illeszkedő sztringet - tehát később nem hivatkozhatsz rá a \1 (vagy $1) backreference segítségével. (A perlre man ír mindenféle egyebet is - teljesítményről, erőforrásfelhasználásról is, de nyilván azok itt most nem számítanak.)

(A regex101.com -os linkjeid szntén - szerintem - engem igazolnak azzal kapcsolatban, hogy (?:pattern) esetén nincs megjegyzett szövegrész - jobb közép ablakban: Group: sor nincs, csak a Full match.)

Mivel engem sem hagy békén ez a dolog (bár én még ott tartok, hogy miért kell a non-capture group), ezért megkérdeztem a PCRE egyik fejlesztőjét (aki egyébként magyar :)), és annyit válaszolt, hogy pusztán a sebesség miatt szokták a non-capture group-okat használni. (Az általam küldött mintákból nekem is kiderült, hogy a másodiknál nincs group match, csak nem tudtam, mire jó ha van - a ModSecurity nem használ group match-et, sem a 2-es, sem a 3-as verzió.)

Gondolom valamilyen módon bele akarták venni az "=" karaktert, hogy annak mindenképp kell szerepelnie benne.

A macska így már világos :)

>bár én még ott tartok, hogy miért kell a non-capture group
A cloudflares példában, vagy úgy egyáltalán?

Ha utóbbi, akkor pl.: ezt:
Lorem ipsum (?:alma|banán|körte)? dolor sit amet
hogyan írnád meg másképpen? Persze lehetne capturing grouppal is, csak az érezhetően lassabb (ha nincs szükség a capturing funkciójára).

Visszakérdezek:

azt állítod, hogy ha csoportosítást használok egy regexpben, akkor érdemesebb (? -tal kezdeni, mert ezzel ugyan az olvashatóságot csökkentem, de érzékelhetően spórolok az erőforrással? Ez számomra meglepetés, de készséggel elhiszem - mérni se kedvem, se türelmem :-).

=====
tl;dr
Egy-két mondatban leírnátok, hogy lehet ellopni egy bitcoin-t?

Ha nincs szükséged külön a groupban matchelt részre backreferenceként, vagy a match eredményeként, szvsz érdemes mindig (?: -vel kezdeni. Az "olvashatóságot" valahol rontja persze, hogy több karakter az egyébként is zaj jellegű kódba, olyan szempontból viszont nagyban javítja, hogy ránézésre lehet tudni, valójából mit akart a költő. :)

Ha kell normális capturing group backreference/capture miatt, akkor se rossz, hogy azok a groupok, amiknél nincs erre szükség nem "szemetelnek" a groupok közé, pl.:
asdas (?:ló|fütty)? asd ([0-9]+) asd \1
esetében a backreference a '([0-9]+)' blokkra hivatkozik, nem a fófüttyre.

És akkor e mellé még "grátisz" sebességben is jobb a non capturing használata, a regex motornak nem kell a match letárolásával bíbelődnie. Alapesetben nincs nagy különbség, viszont több optimalizációra enged teret, összetettebb esetekben bizony már mérhető lehet. Mindezt két plusz karakter "költségén".

A cloudflare-es példában.

De ahogy írtam, közben konzultáltam egy PCRE fejlesztővel, aki annyit írt, hogy a non-capture group-ok gyorsabban illeszthetőek, memóriát keveset nyerünk vele, az elhanyagolható.

Szóval valszeg az van, amit írtál példát, csak itt az "=" volt, aminek mindenképp szerepelnie kell a mintában.

Köszi.

( sabe v | 2019. 07. 15., h – 15:45 )

Imádom ezeket, egy csomó érdekességet lehet tanulni, köszi!

( joco01 v | 2019. 07. 15., h – 17:26 )

Nálunk is nagy divatja van ennek (blameless post-mortem culture, vagy mi). Még más csapatok post-mortemjeit is szívesen olvasom, rengeteg általános igazságot lehet belőle tanulni rendszertervezés témakörben (RAMS az idevágó rövidítés).