Merhaba
Regular Expression hemen hemen her uygulamanın içerisinde en az 1 kere kullanılan önemli yapı taşlarından bir tanesidir. Özellikle yazılı güvenliği konusunun önemli aşamalarından bir tanesi olan “Input Validation” için regex oldukça sık kullanılmaktadır.
DFA ve NFA
Regular Expression, bilgisayar mühendisliği lisans eğitiminde de konu olarak yer alan “Biçimsel Diller” içerisinde yer alan DFA (Deterministic Finite Automaton) ve NFA (Non-deterministic Finite Automaton) isimli iki temel ifade ile ele alınır. DFA ve NFA, sonlu bir karakter serisinin belirlenen dil kuralları için geçerli olup olmadığını kontrol etme yaklaşımlarıdır.
ReDoS konusuna gelmeden önce, ReDoS’a sebeb olan regex’in alt yapısının anlaşılabilmesi adına basit biçimsel dil ifadesini bu iki “otomat” ile ifade edilişine bakıp, farklarını ele alacağız.
L = (a+b)*b dil kuralı, ∑ = {a,b} karakter kümesinden oluşan karakter serileri için geçerli olsun. Tanımlanan bu yeni dil için aşağıdaki karakter serileri “true” sonuç verecektir.
- ab
- abab
- aaaab
- bbbbbb
- …
Bunun sebebi, L isimli dil; “a veya b’ birden fazla gelebilir ama dizi her zaman b karakteri ile son bulacaktır.” anlamına geliyor olmasıdır. Şimdi L dilini DFA ve NFA şemaları ile ifade edelim.
Non-Deterministic Finite Automaton
Sol taraftan gelen OK işareti START noktasını ifade etmektedir. İç içe olan halka ise otomatın final durumunu gösterir. Verilen string ifadenin belirlenen dil için geçerli olması için, karakter setinin iterasyonu yapıldığında, son durum final durumuna tekabûl etmelidir.
Bu şartlar altında sol tarafta verilen şema;A ve B karakterleri istediği kadar kullanılabilir. Son karakter B olmadan final durumuna geçiş yoktur. Cümlesini ifade etmektedir.
Deterministic Finite Automaton
A
ynı dilin DFA ile ifade edilişi yan tarafta şematize edilmiştir. NFA’a göre daha karmaşık duran DFA şeması NFA şemasında bir arada verilmiş olan (a,b) loop durumunun açılmış haline ihtiva eder. Çünkü DFA sistemlerinde bir durum, yalnızca 1 karakter için yeni duruma geçiş yapabilir.
Özetlemek gerekirse, NFA bir durumdan birden fazla duruma geçiş imkanı sunarken, DFA’da her durum sadece ve sadece 1 adet yeni duruma geçiş yapabilir.
Programlama Dilleri ve Regex Engine
Programlama dilleri regular expression için kütüphanelere, modüllere sahiptirler. Her programlama dili birbirinden farklı regex engine’ine sahip olabilir. Her engine ise NFA, DFA veya POSIX NFA yaklaşımından birini temel almış olabilir.
Örneğin;
- Microsoft .NET Framework System.Text.RegularExpression sınıfı NFA engine kullanmaktadır.
- Python NFA to DFA işlemi gerçekleştiren bir engine kullanmaktadır.
- GNU egrep komutu DFA engine kullanmaktadır.
- …
Regex engine’ler hakkında yeteri kadar bilgi sahibi olduk, şimdi ise ReDoS kavramını öğrenip bazı testler gerçekleştireceğiz.
ReDoS Zafiyeti
ReDoS yani Regular Expression Denial-of-Service zafiyetleri, yazılım geliştiriciler tarafından dikkatsizce oluşturulan regex pattern’lerinde oluşur. ReDoS zafiyetine sahip bir Regex pattern’i sadece ve sadece 1 adet input ile sistemin saatlerce işlem yapmasına neden olabilir.
Örneğin = (a|aa)*b
Okuması son derece kolay olan bu regex ReDoS zafiyeti barındırmaktadır. Regex pattern’ini görsel olarak ifade ettiğimizde bu zafiyetin var olduğu yer göze çarpacaktır.
Pattern’in ifade ettiği yapı sözlü olarak şöyle ifade edilebilir; A veya AA ikili karakterleri bir yada birden fazla kez peş peşe gelebilir. Aynı zamanda A veya AA kombinasyonlarından oluşan karakter grup veya grupları, kendi başlarına tekerrür edebilir. En nihayetinde tüm stringler B karakteri ile son bulmalıdır.
Şimdi 3 regex engine’i için bu regex’in kontrolünü gerçekleştirirken ne kadar zaman harcadıklarını test edelim.
.NET ( NFA Engine )
Aşağıda ki kaynak .NET kodu çalıştırılacaktır.
//Title of this code
//Rextester.Program.Main is the entry point for your code. Don't change it.
//Compiler version 4.0.30319.17929 for Microsoft (R) .NET Framework 4.5
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;
using System.Diagnostics;
namespace Rextester
{
public class Program
{
public static void Main(string[] args)
{
Stopwatch stopwatch = new Stopwatch();
// Iterations
for (int i = 0; i < 40; i+=2)
{
stopwatch.Restart();
var regex = new Regex("(a|aa)*b");
string input = new String('a', i);
input = input + "c";
var b = regex.IsMatch(input);
stopwatch.Stop();
// Write result. E.g input = aaaaaaaaaaaaaaaaaac
Console.WriteLine("--- Input Lenght ={0}, seconds = {1} --- ", i,stopwatch.Elapsed);
}
}
}
}
Sonuç ise aşağıdaki gibi olmuştur. OSX üzerinde .NET compiler’ım olmadığı için testi malesef online compiler firmalarından birinde gerçekleştirilmiştir. ( http://rextester.com/runcode )
--- Input Lenght =0, seconds = 00:00:00.0463351 --- --- Input Lenght =2, seconds = 00:00:00.0097138 --- --- Input Lenght =4, seconds = 00:00:00.0001959 --- --- Input Lenght =6, seconds = 00:00:00.0000332 --- --- Input Lenght =8, seconds = 00:00:00.0000697 --- --- Input Lenght =10, seconds = 00:00:00.0001380 --- --- Input Lenght =12, seconds = 00:00:00.0002854 --- --- Input Lenght =14, seconds = 00:00:00.0007328 --- --- Input Lenght =16, seconds = 00:00:00.0018972 --- --- Input Lenght =18, seconds = 00:00:00.0049157 --- --- Input Lenght =20, seconds = 00:00:00.0184165 --- --- Input Lenght =22, seconds = 00:00:00.0527575 --- --- Input Lenght =24, seconds = 00:00:00.1168303 --- --- Input Lenght =26, seconds = 00:00:00.3000577 --- --- Input Lenght =28, seconds = 00:00:00.7565060 --- --- Input Lenght =30, seconds = 00:00:01.9937712 --- --- Input Lenght =32 Process killed because it exceeded given resources. Cpu time used 5.0544324 sec, absolute running time 5 sec, memory used 23 Mb, nr of threads 7
Görüldüğü üzere Input uzunluğu 30 karakterde 2 saniye süren işlem, 32 karakter input için 5 saniye civarı sürmüştür.
Python ( NFA/DFA Engine )
Python ile .NET için gerçekleştirilen testin bire-bir aynısını aşağıdaki şekilde gerçeklenebilir.
import re
import time
regex = "(a|aa)*b"
for c in xrange(0,40,2):
input = "a"*c+"c"
start_time = time.time()
try:
re.search(regex, input)
except Exception as e:
pass
print("--- Input Lenght = %s, seconds = %s ---" % (c, time.time() - start_time))
Bu testi kişisel bilgisayarda gerçekleştirildiği için Python daha performansı yüksek gözükebilir. Lakin bizim için önemli olan Python’un regex engine’ın ReDoS zafiyetine karşı tepkisidir. Sonuçlar aşağıdaki gibidir.
--- Input Lenght = 0, seconds = 0.000174999237061 --- --- Input Lenght = 2, seconds = 6.19888305664e-06 --- --- Input Lenght = 4, seconds = 5.00679016113e-06 --- --- Input Lenght = 6, seconds = 9.05990600586e-06 --- --- Input Lenght = 8, seconds = 2.00271606445e-05 --- --- Input Lenght = 10, seconds = 7.79628753662e-05 --- --- Input Lenght = 12, seconds = 0.000174999237061 --- --- Input Lenght = 14, seconds = 0.00032114982605 --- --- Input Lenght = 16, seconds = 0.000745058059692 --- --- Input Lenght = 18, seconds = 0.00188684463501 --- --- Input Lenght = 20, seconds = 0.0052649974823 --- --- Input Lenght = 22, seconds = 0.0136420726776 --- --- Input Lenght = 24, seconds = 0.0387358665466 --- --- Input Lenght = 26, seconds = 0.0969049930573 --- --- Input Lenght = 28, seconds = 0.263334035873 --- --- Input Lenght = 30, seconds = 0.66898393631 --- --- Input Lenght = 32, seconds = 1.8068780899 --- --- Input Lenght = 34, seconds = 4.60749197006 --- --- Input Lenght = 36, seconds = 12.4079041481 --- --- Input Lenght = 38, seconds = 33.0103201866 ---
Görüldüğü üzere Input lenght 38 için regex kontrolü 33 saniye sürmüştür! “aaaaaaaaaaaaaaaaaaaaaaaaaaaaac” input’u için 33 saniye süren bir işlem üzerinden son derece yüksek etkileri olan DoS saldırısı gerçekleştirilebilir.
GNU Egrep ( DFA Engine )
Sıra geldi GNU Egrep komut satırı aracına. Bu testte farklı input uzunluklarında string’i test etmek yerine direk 999 karakter uzunluğunda stringi kullanacağız.
➜ time egrep '(a|aa)*b' <<< $(python -c "print 'a'*999+'c'") # Sonuc egrep '(a|aa)*b' <<< $(python -c "print 'a'*999+'c'") 0.02s user 0.01s system 91% cpu 0.034 total
İşlem tam olarak 0.034 saniye sürdü.
Diğer regex engine’lerinde 30-35 karakterlik inputlar 1 dakika civarı sürede sonuçlanırken, neden DFA engine’de 999 karakterlik input 0.034 saniyede sonuçlanmıştır ? Google keyword = NFA backtracking.
Evil Regex Tespiti
Görülen o ki, tek bir aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab string ifadesi evil regex zafiyeti olan bir regex pattern’inde 1 dakika civarı bir sürede tamamlanmakta. Bu durumda güvenlik testi uzmanının gerçekleştirdiği denetimde evil regex tespiti’de var olmalıdır. Ele alınan (a|aa)*b regex’i gözle tespit etmesi son derece kolay bir evil regex, şimdi lütfen şansınızı aşağıdaki regex’de deneyin :)
/^([a-zA-Z0-9_\.\-])+\@(([a-zA-Z0-9\-])+\.)+([a-zA-Z0-9]{2,4})+$/
Microsoft SDL Regex Fuzzer
Microsoft tarafından ReDoS zafiyeti tespit etmek için geliştirilmiş aracı (https://www.microsoft.com/en-us/download/details.aspx?id=20095) adresinden indirebilirsiniz. Fuzzing tekniğini kullanarak regex’in çalışması için harcadığı zamanı kontrol ederek DoS’a sebeb olup olmayacağını kontrolünü gerçekleştiren bu araç son derece kullanışlı ve kullanımı kolaydır.
Kaynakça
http://en.wikipedia.org/wiki/Talk%3AReDoS
http://www.csd.uwo.ca/~moreno//CS447/Lectures/Lexical.html/node3.html
https://swtch.com/~rsc/regexp/regexp1.html