Che cos'è un attacco ReDoS e come difendersi

In un programma alcune operazioni sulle stringhe spesso si effettuano utilizzando le espressioni regolari poichè sono veloci da eseguire e capaci di gestire logiche complesse. Ma questi pregi possono anche rappresentare un pericolo per la sicurezza

Un'espressione regolare (abbreviata in regex o regexp) è una sequenza di caratteri (chiamati token) che descrivono il pattern, ossia lo schema, che una stringa deve avere. I suoi campi di applicazione sono molteplici: validazione dei dati, ricerca in un testo, parsing, scraping, ecc..

Eccone un esempio:

/^(https?:\/\/)?([\da-z\.-]+)\.([a-z\.]{2,6})([\/\w \.-]*)*\/?$/

Questa espressione regolare può essere usata per verificare l'url di un sito. Usando una sola line di codice siamo in grado di verificare pattern molto complessi in poco tempo.

Un attacco ReDoS (Regular expression Denial of Service) sfrutta alcuni anti-pattern nelle regex per riuscire ad aumentarne il tempo di valutazione e ad esaurire le risorse di un sistema.

Esempio di un attacco

Prendiamo in esame questo semplice codice Javascript che utilizza la regex vista prima. Puoi provarlo al volo copia-incollandolo nella console del tuo browser.

var validUrlRegex = /^(https?:\/\/)?([\da-z\.-]+)\.([a-z\.]{2,6})([\/\w \.-]*)*\/?$/;
var url = 'https://google.com/';

console.time('regex evaluation time');

if (url.match(validUrlRegex)) {
    console.log(url + ' is a valid url');
} else {
    console.log(url + ' is not a valid url');
};

console.timeEnd('regex evaluation time');

L'output dovrebbe essere:

https://google.com/ is a valid url
regex evaluation time: 2ms

Ma ora vedi cosa succede se eseguiamo la stessa regex sulla stessa stringa ma alterata.

var validUrlRegex = /^(https?:\/\/)?([\da-z\.-]+)\.([a-z\.]{2,6})([\/\w \.-]*)*\/?$/;
var badUrl = 'https://google.com/aaaaaaaaaaaaaaaaaaaaaaaa@';

console.time('regex evaluation time');

if (badUrl.match(validUrlRegex)) {
    console.log(badUrl + ' is a valid url');
} else {
    console.log(badUrl + ' is not a valid url');
};

console.timeEnd('regex evaluation time');

Risultato:

https://google.com/aaaaaaaaaaaaaaaaaaaaaaaa@ is not a valid url
regex evaluation time: 2196ms

Come puoi notare, il tempo di esecuzione della regex è stato aumentato di 1000 volte semplicemente aggiungendo alla stringa 25 caratteri. Vediamo perchè

Come funziona un motore per le espressioni regolari

Un motore per le regex è un automa a stati finiti non deterministico (ASFND). In informatica è un tipo di macchina che, data in input una stringa (ad esempio l'url che abbiamo visto prima), ne processa un carattere alla volta e, in base al carattere corrente e allo stato in cui viene a trovarsi in quel momento, può procedere nelle operazioni in diversi modi.

Quando il motore inizia a processare una stringa, prova ad applicare il pattern descritto dalla regex a partire dal primo carattere. Dal momento che ci possono essere vari percorsi (in inglese paths) in cui si può procedere per verificare la regex, il motore deve provarli tutti e restituire come risultato il primo che riesce a verificarla. Se non riesce a trovarne uno valido, prova ad applicare il pattern della regex partendo dal secondo carattere e così via fino a quando trova una corrispondenza o termina la stringa.

Osserva questa regex

/(a+)+c/

e questa stringa da verificare

aaaac

La regex è verificata per ogni stringa formata a un qualsiasi numero di "a" seguite da "c", perciò la nostra stringa di esempio è valida. Dal momento che però abbiamo usato due quantificatori +, ci sono diversi percorsi che il motore può seguire per trovare una corrispondenza tra la stringa e il pattern dell'espressione regolare (ogni gruppo di caratteri rappresenta un'unita in cui è suddivisibile la stringa in base alla regex).

  • aaaa c
  • aa aa c
  • aa a a c
  • a a a a c

e così via. Il motore prova a seguire tutti i percorsi fino a trovare il primo valido. In questo caso sarà il primo della lista poichè il motore tende a computare prima i gruppi con più caratteri (in questo caso "aaaa") rispetto a quelli con meno. Per questo si dice che è avido.

Ora però proviamo ad applicare la stessa regex ad una stringa che non rispetta il pattern:

aaaasc

Così come prima, ci sono diversi percorsi che il motore può percorrere per verificare la regex (nella parentesi quadra c'è il carattere che rende la stringa non compatibile con il pattern)

  • aaaa [s] c
  • aa aa [s] c
  • a a a a [s] c

e così via. Abbiamo detto che il motore prova tutti i percorsi disponibili fino a trovarne uno valido. Dal momento che in questo caso non c'è n'è uno valido, il motore li dovrà provare tutti prima di terminare la computazione della stringa.

Questo significa che il tempo e la potenza di calcolo che la macchina deve impiegare per la verifica della regex possono aumentare in maniera esponenziale in base al numero di percorsi da provare.

Possiamo misurare le perfomance di una regex su una determinata stringa contando il numero di step. Ogni volta che il motore valuta una stringa e cambia il carattere da cui applicare la regex, il numero di step aumenta. Il numero di step quindi è direttamente proporzionale al tempo necessario per la valutazione.

Qui di seguito una tabella che mostra alcuni benchmark della regex precedente applicata su diverse stringhe.

Stringa Valida Tempo Step
aaaaaaaaaac S ~0ms 6
aaaaaaaaaaaaaaaac S ~1ms 6
aaaaaaaaasc N ~4ms 3057
aaaaaaaaaaasc N ~19ms 12271
aaaaaaaaaaaaasc N ~62ms 49133
aaaaaaaaaaaaaaasc N ~244ms 196587

Come difendere la tua applicazione da un attacco ReDoS

Abbiamo visto che basta una regex e/o una stringa sbagliata per provocare un ReDoS e bloccare un sistema. Il peggior problema è che ci sono diversi scenari in cui questo può verificarsi: un attacco informatico, un errore nella sintassi dell'espressione regolare, una stringa non validata ecc. Per questa ragione ci sono diverse cose che dovresti fare per mettere al sicuro la tua applicazione.

Controlla gli anti pattern nella tua regex

Dovresti fare attenzione quando usi più quantificatori (*, +, {1,}, ?) e/o più alterazioni (|) insieme. Qualche esempio di anti pattern da evitare:

  • (a+)+
  • ([a-zA-Z]+)*
  • (a|aa)+
  • (a|a?)+

Pensa all'input che la tua regex dovrebbe verificare e usa le regole più rigide possibili per scriverla. Prediligi un quantificatore con un limite (per esempio {1,4}) dove possibile. Prendi anche in considerazione l'uso di metodi stringa se il tuo caso lo permette.

Sanitizza e filtra i dati inviati dall'utente

Questa è una regola valida anche per altri tipi di attachi. Dal momento che l'attacco può essere causato da una stringa sbagliata, sanitizza e filtra gli input inviati dall'utente per evitare che un errore o un attacco volontario mettano a rischio la tua applicazione.

Scopri le vulneribilità con il fuzz testing

Alcune regex sono davvero complesse e non è facile scoprire in un primo momento tutte le sue vulnerabilità. Come ulteriore livello di sicurezza puoi usare il fuzz testing per scoprirle prima di caderne vittima. È sufficiente testare la tua regex con stringhe casuali e prestare attenzione quando il tempo in cui vengono verificate cambia drasticamente perchè potrebbe essere sintomo di una vulnerabilità.

Come utilizzare la Background Tasks API in Javascript

Come utilizzare la Background Tasks API in Javascript

In Javascript è spesso difficile capire quando schedulare ed eseguire operazioni con bassa priorità efficientemente. Questa API può aiutarti nell'intento.

Come creare un'applicazione Node.js con Docker, Parte 1: Deploy

Come creare un'applicazione Node.js con Docker, Parte 1: Deploy

In questo articolo vedremo come utilizzare Docker per eseguire un'applicazione Node.js senza più temere lunghe e difficoltose configurazioni.

Come creare un'applicazione Node.js con Docker, Parte 2: Sviluppo

Come creare un'applicazione Node.js con Docker, Parte 2: Sviluppo

Docker è un ottimo strumento non solo per il deploy delle applicazioni ma anche per tutte le altri fasi del ciclo di vita di un software. In questa seconda parte vedremo il suo utilizzo nello sviluppo della nostra applicazione web Node.js.