Evil regexek

...szóval, mikor is baj az a backtrack.

Az egrep (és talán a tcl) regex motorja rendes, véges automatás elvű, az $O(n\cdot m)$ időigényét nem lehet semmilyen regexszel (eek) és/vagy inputtal legyalázni, kb minden más programozási környezetét (kivéve a hírek szerint a C++11 <regex> könyvtárát, amit még nem volt érkezésem kipróbálni - ha a hírek igazak, az a ma létező legjobb cucc. Részletek később) viszont igen, mert azok backtracket használnak.

A backtracking illesztés nem csak azt mondja meg, hogy az input regexre illeszkedik-e a text, de azt is, hogy hol van az illeszkedés. Dióhéjban:

1. A specifikáció szerint a legelső illeszthető pozíción kell kezdődjön a visszaadott illeszkedés. Ezért a regex motorok lényegében egy forciklussal végigpróbálgatják szépen először az első, majd a második, stb. karakternél kezdve illeszteni az egész regexet.
2. Alternatívákat balról jobbra próbál végig. Így például az $(a|aa|b)$ regexnél előbb az $a$, majd az $aa$, ha az $a$-val nem sikerült, végül ha azzal sem, a $b$ alternatívát próbálja.
3. Az $*$ iteráció és a $?$ opcionális operátorok mohók. Ha tehát aktuálisan a jelenlegi pozíciótól egy $R?$ subregexet akarunk illeszteni, akkor oda először is megpróbálja illeszteni az $R$ regexet (azt is olyan hosszan, ahogy csak lehet), ha sikerül, akkor megy tovább az engine. Ha ezek után az egész regex maradék része nem illeszkedik a maradék textre, akkor az $R$ regexet rövidebb substringre akarja illeszteni, ha úgy sem, még rövidebbre, végül ha sehogy nem áll össze, akkor az $R?$-nek az opcionális, kihagyó ágára fut rá, és úgy próbálja befejezni az illesztést. Ha így se sikerül, akkor ebből az állapotból is visszalépés a keresésben.

Ezt a hármas pontot egy-két példával szemléltetném inkább: van mondjuk az $ab?b$ regexet, és illesszük az $aab$ textre.

• Először az $ab?b$-t az első $a$-ra próbálja illeszteni. Az $a$ stimmel. Most $b?b$-t illeszti a fennmaradó $ab$-re. A $b?$ részt ilesztve az $ab$-re először $b$-t illeszt $ab$-re, nem illeszkedik, mert $a$-val kezd. Akkor a $b?$ subregexet üres stringgel oldja meg (tehát kihagyja), és már csak a regex végén lévő $b$-t illeszti az $ab$-re. Nem sikerül. Visszalépés.
• Most az $ab?b$-t a második $a$-nál kezdve próbálja illeszteni. Az $a$ oké, $b?b$-t akar illeszteni a fenmaradó $b$-re, akkor először kipróbálja, hogy ha a $b?$-beli $b$-t illeszti, mi történik. Sikerül, a regex maradék $b$-jét kell a.. elfogyott a text. Akkor ez így nem jó, visszalép. Most a $b?$-et skippeléssel illeszti, és a regex maradék $b$-jét a text maradékára, $b$-re próbálja illeszteni, sikerül, mindenki boldog, illeszkedik a regex: a második pozíción kezdve, mégpedig úgy, hogy a $b?$ skippeli az opcionálist.

Mindenki boldog, kivéve, hogy mikor a Jeffrey Friedl könyvében ezt olvastam, az arcomon egy apró ideg elkezdett rángatózni... aztán kisétáltam az udvarra, felástam egy részét, és nem volt ezzel gondom.

Ahogy mondtam, a csillag is mohó operátor, annyiszor próbál illeszteni, ahányszor csak tud, azon belül pedig minden egyes iterációban amilyen hosszút csak tud. Ha rájön, hogy túl hosszan illesztett, akkor az utolsó iterációt rövidíti, majd elengedi, stb.

Ez még nem hangzik olyan veszélyesnek, igaz?

plain wrong

dehogynem.

Illesszük mondjuk az.. $(a^*)^*b$ regexet az $a^n$ textre, valamilyen $n$-re! Érzi remélem mindenki, hogy nem kéne illeszkedjen? Pastebin itt. Ideone.com output:

On a, .find run in 2451933 nanoseconds.
On aa, .find run in 69710 nanoseconds.
On aaa, .find run in 75366 nanoseconds.
On aaaa, .find run in 121180 nanoseconds.
On aaaaa, .find run in 419257 nanoseconds.
On aaaaaa, .find run in 421194 nanoseconds.
On aaaaaaa, .find run in 1158488 nanoseconds.
On aaaaaaaa, .find run in 2692903 nanoseconds.
On aaaaaaaaa, .find run in 1265485 nanoseconds.
On aaaaaaaaaa, .find run in 377794 nanoseconds.
On aaaaaaaaaaa, .find run in 672745 nanoseconds.
On aaaaaaaaaaaa, .find run in 1399777 nanoseconds.
On aaaaaaaaaaaaa, .find run in 2746695 nanoseconds.
On aaaaaaaaaaaaaa, .find run in 5498918 nanoseconds.
On aaaaaaaaaaaaaaa, .find run in 10948008 nanoseconds.
On aaaaaaaaaaaaaaaa, .find run in 21770596 nanoseconds.
On aaaaaaaaaaaaaaaaa, .find run in 43556607 nanoseconds.
On aaaaaaaaaaaaaaaaaa, .find run in 86682752 nanoseconds.
On aaaaaaaaaaaaaaaaaaa, .find run in 172915112 nanoseconds.
On aaaaaaaaaaaaaaaaaaaa, .find run in 345402683 nanoseconds.
On aaaaaaaaaaaaaaaaaaaaa, .find run in 653601295 nanoseconds.
On aaaaaaaaaaaaaaaaaaaaaa, .find run in 1266362512 nanoseconds.

és a szokásos timeout. Megint $a^{10}$ környékére ficcent be a hotspot, utána szépen duplázódott az időigény, $a^{22}$-re még sikerült illessze, aztán elszállt.

Miért is?

Az első menetben $a^{20}$-ra (mondjuk nézzük ezt) illeszti $(a^*)^*b$-t. Ehhez először $(a^*)^*$-ot illeszt a legelső karaktertől. Ahhoz $a^*$-ot illeszt a legelső karaktertől. Itt iterációban szépen megpróbál annyi $a$-t benyelni, amennyit csak lehet: az $a^*$ rész megeszi az egész inputot. Elfogyott az input, most ide próbálná illeszteni a $b$-t, nem sikerül, visszalép.

Most az az eset jön, mikor a belső $a^*$ már szerényebben csak $a^{19}$-et nyel le. Ezután az $(a^*)^*$-on futó motor azt mondja, hogy oké, akkor egy iterációban a belső rész lenyelt $19$ darab $a$-t, próbáljunk meg még egy iterációt! Illeszti az $a^*$-ra a maradék $a$-t, betalál, elfogyott az input, jé, megint nincs a végén $b$. Akkor ezt a második iterációt elfelejtjük, és a text utolsó $a$-jára illesztjük a regexet záró $b$-t. Hm, nem sikerült. Akkor az első iterációs $a^*$ még szerényebb, már csak $18$ karaktert nyel le, marad $aa$ a textből, amin a motor továbbra is az $(a^*)^*b$-t próbálja illeszteni. Először a belső $a^*$-gal lenyeleti az egész textet, elfogy, nem passzol a $b$, oké, akkor a belső $a^*$-gal csak az első $a$-t nyeleti be, és a maradék $a$-ra illeszti tovább az $(a^*)^*b$-t, a belső $a^*$-gal először lenyeleti az egész $a$-t, elfogy, nem passzol a $b$, akkor skippeli az $a^*$-ot, rájön, hogy a $b$ nem illeszkedik az $a$-ra, visszalép, akkor az $aa$-ra illeszti $(a^*)^*b$-t úgy, hogy az egész csillag üres stringre illjen, jé, a $b$ nem illeszkedik az $aa$-ra se, visszalépek, az első iterációs $a^*$ már csak $17$ karaktert szeretne, akkor $(a^*)^*b$-t illesztjük $aaa$-ra úgy, hogy először $3$, majd $2+1$, majd $2$, majd $1+2$, majd $1+1+1$, majd $1+1$, majd $1$, végül $0$ darab $a$-t akarunk lenyeletni, de persze az a $b$ egyszer se lesz ott...

...ha kiszámoljuk, ez azt jelenti, hogy a regex illesztő backtracking motor $(a^*)^*b$-t $a^n$-re illesztéskor $\Theta(2^n)$ idő alatt jön rá, hogy ez bizony nem illeszkedik. (És ahogy a fenti ideone logot láthatjuk, ez Javában is így megy...)

Mikor ezt olvastam a Jeffrey Friedl könyvében, becsuktam a könyvet, kimentem a fejszémért, kivágtam egy (kiszáradt) fát, ittam egy sört, visszamentem olvasni és megállapítottam, hogy valaki elég kókány munkát végzett valamikor.

A fenti "catastrophic backtracking" (mikor sikerül kicsalni egy exponenciális futásidőt egy alkalmasan megválasztott texten való futtatással) viselkedést mutatni képes regexeket (mint amilyen az $(a^*)^*b$ is) Evil (vagy malicious) Regexnek hívják :) ha ne adj'Isten egy webszerveren a user inputot egy evil regexre illesztik, az egy remek kiindulópontja a ReDoS (regular expression denial of service) támadásnak (ld még itt): a usernek más dolga nincs is, csak egy megfelelően craftolt stringet beírni a form megfelelő input fieldjébe, amit ha a szerver elkezd illeszteni, azzal garantáltan elfoglalkozik egy darabig :D

Az előző post $(a?)^na^n$ regexe az nem ilyen volt, mert az exponenciális viselkedéshez a regexet is egyre hosszabbra kellett venni. Ha szervert támadsz, akkor az azon levő adott regexhez kell megfelelő textet gyártani. De ha a regexedben van olyan $R^*$ vagy $R^+$ alakú rész, hogy az $R$ illeszkedik valami $u$ (nemüres) szóra és annak egy hatványára is (pl. $a$-ra is és $aa$-ra is, vagy $aba$-ra és $abaabaaba$-ra is stb), akkor ezt a regexet egy olyan text, amiben sok áll egymás után ebből az $u$-ból ezen a helyen (és melyre a regex nem illeszkedik, hogy végig kelljen tekernie a backtracket), catastrophic backtrackingbe fogja küldeni. They are all evil, period.

Egyszerű példák evil regexekre:

• $(a^*)^*$ - ez egy iteráció, aminek a belseje illeszkedik $a$-ra is és $aa$-ra is, és ahogy láttuk, $a^{30}$ már elszállítja ideone.on
• $(a|aa)^*$ - ugyanez
• $([a-zA-Z]^+)^*$ - "karaktersorozatok egymás után", szeparátor nélkül? nem jó, szintén $a$ és $aa$ is illeszkedik belül
• $(.^*,?)^+$ - vesszőkkel elválasztott szavak, gondolom ilyesmi akart volna lenni, utolsó vessző elhagyható, ezért opcionális. Ez több sebből is vérzik, de eleve a $.^*$ regexet jó ötlet kerülni, amennyire csak lehet. Belül így illeszkedik pl. $a$-ra és $aa$-ra is, de ha a vessző nem is lenne opcionális, még akkor is a $,$ és $,,$ szavakra is illeszkedik... A $.^*$ regex pedig a korábbiak szerint ha idefut a backtrack, először is szépen benyeli az input teljes maradék részét, utána egyet, még egyet, ... visszaad a regex további részének. Ez elég időigényes tud lenni (bár "csak" egy $N$-es szorzó, a text hosszával szorzódik, de az se kevés)
• $(a|a?)^+$ - ez evil, de nem a fenti ökölszabály miatt. A backtracking motor először az $a$-t próbálja illeszteni, ha az nem sikerül, akkor az $a?$-et, melyet is először úgy, hogy $a$-t, majd úgy, hogy üres stringet illeszt. Ezt a három lehetőséget aztán végigpörgeti az összes további $a$-ra is...
• Guglizva emailcím regexre meg lehet kapni akár ezt. Ennek a közepén van egy ilyen: $(([-.]|[\_])^?[a-zA-Z0-9]^+)^*$, azaz mínusz, pont vagy underscore ESETLEG ($?$), utána alfanumerikus nemüres string, ezt ismételjük. Itt ugye a gond a $?$, amiatt az első csoport akár üresre is illeszthető és az iterált rész matchel bármilyen alfanumerikussal. Pl $a$, $aa$... ne írjunk soha ilyesmit: $(R_1?R_2^*R_3?)^*$, mert ebbe belefér az $(R_2^*)^*$ is akár, amiről tudjuk, hogy rossz ötlet
• Itt van ez, hogy mi egy Java osztály neve: $([a-z]^+.)^+[A-Z][a-z]^+$, azaz (kisbetűk, akármi)párszor, nagybetű, megint kisbetűből néhány.  A "kisbetűk, akármi" részre illeszkedik $aa$ is és $aaaa$ is...

Szerencsére általában ezeket a regexeket (már ha észrevesszük, hogy a regexünk nem éppen hatékony ;) ) át lehet transzformálni olyan alakúra, amin a backtracking motor nem tölt el annyira sok időt, mint ezeken az evil formokon tölthet.

Ahogy az idő telt, egyre több és több szintaktikus elem került be a legtöbb regex motorba, amivel a backtracket irányíthatjuk (ha már automatánk nincs ugye..), legközelebb ezekről beszélek majd.

És arról is, hogy mi lehet az oka annak, hogy én magam se automatával, hanem backtrackkel próbálnék mai regexet illeszteni.

folytköv

mekkora cliffhanger

remélem, erre senki nem számított