Java: Matcher.find przy użyciu wysokiego cpu

Question

Używam reguł bezpieczeństwa mod https://github.com/SpiderLabs/owasp-modsecurity-crs do sanityzacji danych wejściowych użytkownika. Mam do czynienia z wyskakującym cpu i opóźnieniem w dopasowaniu danych wprowadzanych przez użytkownika za pomocą wyrażeń regularnych mod mod. Ogólnie zawiera ponad 500 wyrażeń regularnych, aby sprawdzić różne typy ataków (xss, badrobots, ogólne i sql). Dla każdego żądania przechodzę przez wszystkie parametry i sprawdzam wszystkie te 500 wyrażeń regularnych. Używam Matcher.find, aby sprawdzić parametry. W tym przypadku niektóre parametry padają w nieskończonej pętli, rozwiązałem to za pomocą poniższej techniki.

Cancelling a long running regex match?.

Dezynfekcja żądania użytkownika zajęła około ~ 500 ms, a procesor% wystrzelił. Przeanalizowałem, używając visualvm.java.net, z moim zestawem testowym runner.

Cpu profil wyjściowy

Proszę mi pomóc zmniejszyć użycie procesora% i obciążenia średnio?

Answer 1

Unikaj expresions z:

• wielowierszowego
• sprawa niewrażliwe
• itp

Być może można rozważyć grupowania wyrażeń regularnych i zastosować daną grupę regex'ów zależności od danych wejściowych użytkownika .

Answer 2

Jeśli to możliwe, kompiluje swoje wyliczenie raz i zachowuje je dookoła, zamiast powtarzać (niejawnie) kompilowanie (szczególnie wewnątrz pętli).
Aby uzyskać więcej informacji, patrz java.util.regex - importance of Pattern.compile()?.

Answer 3

Jeśli masz tak dużą liczbę wyrażeń regularnych, możesz pogrupować (przynajmniej niektóre) za pomocą algorytmu trie (http://en.wikipedia.org/wiki/Trie).
Chodzi o to, że jeśli na przykład regexes jak /abc[0-9-]/, /abde/, /another example/, /.something else/ i /.I run out of ideas/, można połączyć je w pojedynczym regex

/a(?:b(?:c[0-9-]|de)|nother example)|.(?:I run out of ideas|something else)/ 

W ten sposób dopasowujący musi uruchomić tylko raz zamiast cztery razy, a ty unikasz wielu cofnięć, ponieważ w powyższym wyrażeniu zostały napisane wspólne początkowe części.

Answer 4

Proponuję spojrzeć na ten papier: "Towards Faster String Matching for Intrusion Detection or Exceeding the Speed of Snort"

Są lepsze sposoby wykonywania opisać pasujący. Zasadniczo bierzesz 500 wzorców, które chcesz dopasować i kompilujesz je w jedno drzewo przyrostków, które może bardzo skutecznie dopasować dane wejściowe do wszystkich reguł naraz.

W artykule wyjaśniono, że to podejście zostało opisane jako "Boyer-Moore Approach to Exact Set Matching" autorstwa Dana Gusfielda.

Boyer-Moore to dobrze znany algorytm dopasowywania ciągów. Artykuł opisuje odmianę Boyer-Moore dla Set Matching.

Answer 5

Wśród tych 500 musi być podzbiór problematycznych wyrażeń regularnych. takie wyodrębnienie będzie wymagało wielu lat.

Tak więc w twoim przypadku zapisałbym wszystkie problematyczne wyliczenia z ich problematycznymi danymi wejściowymi. Po ich znalezieniu można ręcznie przepisać te kilka problematycznych wyrażeń regularnych i przetestować je w porównaniu do oryginału. Regeksy zawsze można przepisać za pomocą prostszych i bardziej czytelnych funkcji java.

Inną opcją, chociaż nie rozwiąże problemu powyżej, jest możliwość użycia szybciej (x20 w niektórych przypadkach) i bardziej restrykcyjnego regex library. Jest dostępny w Maven Central.

Answer 6

myślę, że to jest źródłem problemu, nie regex wydajność per-SE:

dla każdego żądania, idę przez wszystkich parametrów i sprawdzić z tych wszystkich 500 wyrażeń regularnych

Bez względu na to, jak szybkie będzie twoje regex, wciąż jest dużo pracy. Nie wiem, ile masz parametrów, ale nawet jeśli jest ich tylko kilka, to wciąż sprawdzam tysiące wyrażeń regularnych na żądanie. To może zabić twój procesor.

Oprócz oczywistych rzeczy, jak poprawić skuteczność regex przez prekompilacja i/lub ich uproszczenia, można wykonać następujące czynności, aby zmniejszyć ilość sprawdzania regex:

1. Zastosowanie pozytywnej walidacji dane wejściowe użytkownika na podstawie typu parametru. Na przykład. jeśli jakiś parametr musi być prostym numerem, nie marnuj czasu na sprawdzanie, czy zawiera złośliwy skrypt XML. Po prostu sprawdź, czy pasuje [0-9] + (lub coś podobnego prostego). Jeśli tak, to jest ok - pomiń sprawdzanie wszystkich 500 wyrażeń regularnych.

2. Spróbuj znaleźć proste wyrazy regularne, które mogą wyeliminować całe klasy ataków - znajdź wspólne rzeczy w swoich wyrażeń regularnych. Jeśli np. masz 100 wyrażeń regularnych sprawdzających istnienie określonych znaczników HTML, sprawdź, czy zawartość zawiera co najmniej jeden tag HTML. Jeśli tak nie jest, natychmiast oszczędzasz na sprawdzaniu 100 regexps.

3. Wyniki pamięci podręcznej. Wiele parametrów generowanych w aplikacjach internetowych powtarza się. Nie sprawdzaj tej samej zawartości w kółko, ale pamiętaj o ostatecznym wyniku sprawdzania poprawności. Uważaj, aby ograniczyć maksymalny rozmiar pamięci podręcznej, aby uniknąć ataków DOS.

Należy również pamiętać, że negatywne sprawdzanie poprawności jest zwykle łatwe do ominięcia. Ktoś po prostu zmienia kilka znaków w ich złośliwym kodzie, a twoje wyrazy regularne nie będą się zgadzać. Będziesz musiał rozbudować "bazę" wyrażeń regularnych, aby chronić się przed nowymi atakami. Pozytywna walidacja (biała lista) nie ma tej wady i jest znacznie bardziej efektywna.