Wyrażenie regularne które specjalnie jest wolne

1

Witam!

Próbuję zrobić benchmark mojej biblioteki do wyrażeń regularnych, ale są inconclusive - nie mogę dostać czystego wyniku, ponieważ operacje są wykonywane za szybko.

Szukam jakiegoś wyrażenia regularnego które specjalnie jest zaprojektowane tak żeby było wolne, im "gorsze" tym lepsze, najlepiej takie żęby miało dużo backtrackingu ale nie za dużo, dużo grup, dużo lookaheadów, tak żęby mieliło silnik do czerwoności.

Ma ktoś jakiś przykład wraz ze stringiem który może go złapać?

5

^(a+)+$

aaaaaaaaaaaaaaa=aaaaaaaaaaaaaaaaaaaa;

screenshot-20220429162811.png

Przy większej liczbie wystąpień a toole rzucają

Catastrophic backtracking has been detected and the execution of your expression has been halted. To find out more and what this is, please read the following article: Runaway Regular Expressions

src: https://sekurak.pl/zabilo-cale-cloudflare-przerywamy-spotkanie-wszystkie-rece-do-konsol/

3
TomRiddle napisał(a):

Witam!

Próbuję zrobić benchmark mojej biblioteki do wyrażeń regularnych, ale są inconclusive - nie mogę dostać czystego wyniku, ponieważ operacje są wykonywane za szybko.

Nawet nie napisałeś, w jaki sposób robisz ten benchmark. Trudno w jakikolwiek sposób pomóc.

Są do tego odpowiednie narzędzia, ale nie napisałeś co konkretnie chcesz zrobić poza lakonicznym "zrobić benchmark mojej biblioteki do wyrażeń regularnych".

Szukam jakiegoś wyrażenia regularnego które specjalnie jest zaprojektowane tak żeby było wolne, im "gorsze" tym lepsze, najlepiej takie żęby miało dużo backtrackingu ale nie za dużo, dużo grup, dużo lookaheadów, tak żęby mieliło silnik do czerwoności.

Ta twoja biblioteka samodzielnie implementuje te regexy, czy tylko "owija" gotowe rozwiązanie:

  • jeśli samodzielnie, a nie masz ważnego powodu, to: NIH - moim zdaniem należy skorzystać z gotowego rozwiązania

  • jeśli "owijasz" istniejące rozwiązanie, to taki benchmark należy robić dla możliwie najszybciej wykonujących się regexów, o ile rzeczywiście chcesz zmierzyć wydajność twojego wrappera, a nie wykorzystanej pod spodem biblioteki

Ma ktoś jakiś przykład wraz ze stringiem który może go złapać?

Tak, ktoś ma.

Jednak Twoje pytanie wygląda mi na XY

0

Widziałem, nawet przeglądałem kod, ale co z tego?

Dla mnie właśnie zaczął się dlugi weekend, którego nie chcę spędzić przeglądając kod T-Regx celem ustalenia, o co @TomRiddle chodziło, zwłaszcza że PHP nie znam xD

0

@1a2b3c4d5e: Dzięki, ale mi nie chodzi o catastrophic backtracking. Chciałbym żęby silnik mielił długo, ale jednak znalazł match. Z Twoim przykładem będzie 0 matchy.

@pms_enable_synaptics: Nie chce mi się tlumaczyć dokładnie do czego tego potrzebuje, bo nie chcę marnować dwudziestu stron żeby Ci to wyjaśnić. Mam konkretny benchmark już dwóch rozwiązań w wewnętrznej implementacji biblioteki, i mam duże powody przypuszczać, że ten benchmark będzie bardziej wiarygodny na bardzo nieoptymalnym wyrażeniu regularnym, dlatego takiego szukam. Możesz sobie to uważać za X/Y, I don't care. To jest coś co wynika z tego że muszę podjąć pewną decyzję, ta decyzja jest podparta kilkoma czynnikami, gdybym teraz powiedział co to za decyzja, to wyjechałbyś z pomysłami nad którymi się zastanawiam od miesięcy. Wydestylowałem odpowiedź na to pytanie do benchmarku libki, ale na razie jest on nie miarodajny, przez to że silnik łapie matcha za szybko, dlatego potrzebuje wyrażenia które specjalnie jest słabe. Więc albo rzuć pomysł niewydajnego wyrażenia regularnego, które znajduje match'a, albo nie zaśmiecaj tematu.

Dziękuję.

Nawet nie napisałeś, w jaki sposób robisz ten benchmark. Trudno w jakikolwiek sposób pomóc.

Bo to nie ma znaczenia, wiem co robię.

Są do tego odpowiednie narzędzia, ale nie napisałeś co konkretnie chcesz zrobić poza lakonicznym "zrobić benchmark mojej biblioteki do wyrażeń regularnych".

To też nie ma znaczenia w tym wątku.

jeśli "owijasz" istniejące rozwiązanie, to taki benchmark należy robić dla możliwie najszybciej wykonujących się regexów, o ile rzeczywiście chcesz zmierzyć wydajność twojego wrappera, a nie wykorzystanej pod spodem biblioteki

Tak, taki już zrobiłem. Teraz chcę zrobić drugi, dla najwolniejszych.

0
TomRiddle napisał(a):

(...) rzuć pomysł niewydajnego wyrażenia regularnego, które znajduje match'a (...)

@import[cunit]@invoke[cunit]

Matchuje kod źródłowy jednostki kompilacji C i potrafi trochę "pomielić" dla większych jednostek kompilacji.

Działa na SYSVRE w trybie VRE z flagą UNSAFE, wymaga zainstalowanego systemowego devkitu.

Tylko, że SYSVRE to komponent całkiem niszowego systemu operacyjnego, więc nie wiem czy się przyda.

0

Byc moze wyrazenie regularne ktore ma duzo lookaheadow, a jednoczesnie nie ma grup atomicznych byloby dobre (tzn zle :D Ale dobre w tym sensie, ze jest wolne i jest tym czego szukam).

2

@hauleth: kiedyś na discordzie wrzucił.

"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa".match(/(a*)*b/)

https://regexr.com/6kpi1

screenshot-20220502145558.png

0
several napisał(a):

@hauleth: kiedyś na discordzie wrzucił.

"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa".match(/(a*)*b/)

https://regexr.com/6kpi1

screenshot-20220502145558.png

Dzięki, ale zauważ, że ten regexp też nie złapał matcha, bo jest error.

Ja szukam takiego, który owszem trwa długo, ale jednak się wykona. Tylko po prostu będzie skrajnie nieoptymalny.

3
TomRiddle napisał(a):

@1a2b3c4d5e: Dzięki, ale mi nie chodzi o catastrophic backtracking. Chciałbym żęby silnik mielił długo, ale jednak znalazł match. Z Twoim przykładem będzie 0 matchy.

Jak na kogoś kto się zajmuje biblioteką do regexów wydaje się że mało wiesz o regexach. Catastrophic backtracking występuje jeśli jest za dużo backtrackingu, ale jeśli chcesz żeby długo mieliło to musi być dużo backtrackingu albo rekurencji (?R). To czy backtracking jest catastrophic czy nie zależy głównie od danych. Jeśli chcesz ograniczyć to zamiast

^(a+)+$

możesz ograniczyć do jakiejś ilości trafień grup np:

^(a+){1,6}$
24 842 steps

jeśli chcesz żeby mieliło długo a potem coś znalazło to wystarczy że dasz alternatywną grupę która da rezultat np:

^((a+){1,6}|a+=a+;)$

Albo dasz takie dane żeby regex się dużo namęczył a na końcu znalazł dopasowanie.
Przykładowo zamiast ^ i $ możesz dać inny ogranicznik, dajmy na to literkę ""b"" i potem kopiować grupy otoczone tym znakiem żeby zmęczyć silnik a na końcu dać mu satysfakcję dając działające przypasowanie:

Regex: b((a+){1,5})b
Dane:

baaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabaaaaaaaaaaaaaaaaa=aaaabaaaaaaaa=aaaabaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaa=aaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab

1 match (16 631 465 steps, 546ms)
Czas sobie możesz dowolnie regulować kopiując dane lub ilość alternatywnych grup w regexie (mogą być takie same bo wygląda na to że silniki regexa tego nie optymalizują i po prostu sprawdzają od zera).

Ogólnie szukaj pod hasłami "evil regex" / "ReDoS"
Możesz użyć przykładu z życia - trefnego regexa ustawionego na firewallu cloudflare który doprowadził do jego awarii w 2019:

https://blog.cloudflare.com/details-of-the-cloudflare-outage-on-july-2-2019/

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

To nie regex jest najważniejszy tylko dane na jakich operuje.

3

Zrób test pierwszości i łatwo to będziesz skalował
https://theabbie.github.io/blog/Primality-Test-Using-Regex

2

@kamil kowalski: Pracuję w firmie w którym jest jeden side-projekt w PHPie rozwijany od 8-9 lat, już nie pamiętam, było tam trochę użyć wyrażeń regularnych, ale strasznie nam przeszkadzało to że błędy w funkcjach PHP nie były w żaden sensowny sposób pokazywane (tylko albo null, albo jakiś false albo -1, a niektóre przypadki z preg_last_error()) więc napisałem wrapper który nigdy nie zwraca null/false etc. tylko zawsze rzuca odpowiednie wyjątki, tak powstała pierwsza wersja. Biblioteka nadal jest używana u nas w firmie, a jako że jest open-source to jeszcze kilka użytkowników się załapało.

Jak projekt powstawał to nie było (i w sumie nadal nie ma) żadnej dostępnej implementacji regexpów w PHP, tak dobrej jak jest np w Javie. Najbliższe co jest to jakieś cienkie wrapery (cienkie mam na myśli że nie są odpowiednie odcouple'owane od PHP'owej implementacji). Można powiedzieć że biblioteka "wyrosła" na naszych potrzebach.

1 użytkowników online, w tym zalogowanych: 0, gości: 1