Java: Matcher.find utilizzando elevato utilizzo della CPU

Question

Sto usando regole di sicurezza mod https://github.com/SpiderLabs/owasp-modsecurity-crs per disinfettare i dati di input dell'utente. Sto affrontando cpu sparare e ritardare nel corrispondere l'input dell'utente con le espressioni regolari della regola di sicurezza mod. Nel complesso contiene 500+ espressione regolare per controllare diversi tipi di attacchi (XSS, badrobots, generico e SQL). Per ogni richiesta, analizzo tutti i parametri e controllo tutte queste 500 espressioni regolari. Sto usando Matcher.find per controllare i parametri. In questo caso alcuni parametri cadono in loop infinito, l'ho affrontato usando la tecnica di sotto.

Cancelling a long running regex match?.

disinfettare una richiesta dell'utente sono voluti circa ~ 500 ms e CPU% spara alto. Ho analizzato utilizzando visualvm.java.net con il mio runner di test suite.

Cpu profilo di destinazione

favore mi aiuti a ridurre il% e carico medio di utilizzo della CPU?

Answer 1

Evita expresions con:

• multilinea
• case insensitive
• ecc

Forse si può considerare il raggruppamento espressioni regolari e applicare un determinato gruppo di esprimono tutti regolari in base all'input dell'utente .

Answer 2

Se possibile, compilare tuoi regex una volta e tenerli in giro, piuttosto che più volte (implicitamente) la compilazione (in particolare all'interno di un ciclo).
Vedi java.util.regex - importance of Pattern.compile()? per maggiori informazioni.

Answer 3

Se si dispone di un numero così elevato di regex, è possibile raggruppare (almeno alcune di esse) utilizzando un algoritmo trie (http://en.wikipedia.org/wiki/Trie).
L'idea è che se si hanno per esempio regex come /abc[0-9-]/, /abde/, /another example/, /.something else/ e /.I run out of ideas/, si possono combinare in un'unica espressione regolare

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

In questo modo, il matcher deve eseguire una sola volta invece di quattro volte, e si evita un sacco di backtracking, a causa di come le parti iniziali comuni sono state scritte nella regex di cui sopra.

Answer 4

vi consiglio di dare un'occhiata a questo documento: "Towards Faster String Matching for Intrusion Detection or Exceeding the Speed of Snort"

ci sono modi migliori per fare la corrispondenza che descrivi. Praticamente si prendono i 500 pattern che si desidera abbinare e si compila in un singolo albero di suffisso che può abbinare in modo molto efficiente un input a tutte le regole contemporaneamente.

Il documento spiega che questo approccio è stato descritto come "Approccio di Boyer-Moore all'Esact Set Matching" di Dan Gusfield.

Boyer-Moore è un algoritmo noto per la corrispondenza delle stringhe. Il documento descrive una variazione su Boyer-Moore per Set Matching.

Answer 5

Ci deve essere un sottoinsieme di regex problematiche tra queste 500. I.e. tale regex

String s = "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAB"; 

    Pattern.compile("(A+)+").matcher(s).matches(); 

richiederà anni per essere completato.

Quindi nel tuo caso registrerei tutte le regex problematiche con i loro input problematici. Una volta individuati, è possibile riscrivere manualmente queste regex problematiche e verificarle rispetto all'originale. I regex possono sempre essere riscritti con funzioni java più semplici e più leggibili.

Un'altra opzione, sebbene non risolva il problema di cui sopra, è che è possibile utilizzare anche una regex più veloce (x20 in alcuni casi) e più limitata library. È disponibile in Maven Central.

Answer 6

Penso che questa è la radice del problema, non la prestazione regex per-sé:

Per ogni richiesta, mi passare attraverso tutti i parametri e controllare contro tutti questi 500 espressioni regolari

Non importa quanto sia veloce il tuo regex, questo è ancora molto lavoro. Non so quanti parametri hai, ma anche se ce ne sono solo pochi, controlla ancora migliaia di espressioni regolari per richiesta. Questo può uccidere la tua CPU.

A parte le cose ovvie come migliorare il rendimento regex per precompilare e/o semplificare, si possono fare le seguenti cose per ridurre la importo di controllo regex:

1. Usa positiva validazione dei input dell'utente basato sul tipo di parametro. Per esempio. se alcuni parametri devono essere un numero semplice, non perdere tempo a controllare se contiene script XML dannoso. Basta controllare se corrisponde a [0-9] + (o qualcosa di simile allo stesso modo). Se lo fa, va bene - salta il controllo di tutte le 500 espressioni regolari.

2. Cerca di trovare espressioni regolari semplici che possano eliminare l'intera classe di attacchi: trova le cose comuni nelle tue espressioni regolari. Se ad es. hai 100 verifiche regex per verificare la presenza di determinati tag HTML, controlla se il contenuto contiene almeno un tag HTML. In caso contrario, si salva immediatamente il controllo di 100 espressioni regolari.

3. Risultati della cache. Molti parametri generati nelle applicazioni web si ripetono. Non controllare più volte lo stesso contenuto, ma ricorda solo il risultato finale della convalida. Fai attenzione a limitare la dimensione massima della cache per evitare attacchi DOS.

Si noti inoltre che la convalida negativa di solito è facile da ignorare. Qualcuno cambia semplicemente alcuni caratteri nel loro codice malevolo e le tue espressioni regolari non corrispondono. Dovrai far crescere il tuo "database" di espressioni regolari per proteggere dai nuovi attacchi. La validazione positiva (whitelist) non ha questo svantaggio ed è molto più efficace.