Abstrakt. Regelbundna uttryck är ett koncist men ändå uttrycksfullt språk för att uttrycka mönster. I nätverksbaserad programvara används de till exempel för indatavalidering och detektion av intrång. Men vissa allmänt utplacerade reguljära uttryck matchers baserat på bakåtspårning är själva sårbara för överbelastning attacker, eftersom deras körtid kan vara exponentiellt för vissa inmatning strängar. I detta dokument presenteras en statisk analys för att upptäcka sådana sårbara reguljära uttryck. Löptiden för analysen jämförs positivt med verktyg baserade på fuzzing, det vill säga slumpmässigt generera ingångar och mäta hur lång tid det tar att matcha dem. Till skillnad från fuzzers, analysen anger källan till sårbarheten och genererar eventuella skadliga indata för programmerare att använda i säkerhetstester. Dessutom har analysen en fast teoretisk grund i abstrakta maskiner. Att testa analysen på två stora databaser med reguljära uttryck visar att analysen kan hitta ett betydande antal sårbara reguljära uttryck på några sekunder.
Kirrage m.fl. utvecklat en metod för att kontrollera om körtiden för ett reguljärt uttryck matchning är exponentiellt REF.
Static Analysis for Regular Expression Denial-of-Service Attacks
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}