Thanks Harald for those links, really useful . More inline ..
(2) the actual implementation; see http://swtch.com/~rsc/regexp/ > Strictly speaking about regular languages, the conversion from RE to > executable DFA leads to exponentially many states (space). To safe space > and time for this conversion, most implementations use backtracking and > therefore shift the problem to runtime. The assumption is that > nondeterminism in practical REs is limited but this does not hold — DoS > becomes possible. Just look at implementations and you will understand. > > Imagining there are no back references. For example , How do we fix simple evil regex's<https://www.owasp.org/index.php/Regular_expression_Denial_of_Service_-_ReDoS>like the one mentioned here say (a+)+ Does this simple regular expression match Regular grammar ? or CFG or CSG ? Since they are causing ReDOS attacks , can we say they are CSG or above ? Also how can we determine (programmatically) whether given a regex it's equivalent grammar is CSG or above (thus undecidable) and can potentially cause REDOS ? Regards, Sashank > Cheers, Harald > > _______________________________________________ > langsec-discuss mailing list > [email protected] > https://mail.langsec.org/cgi-bin/mailman/listinfo/langsec-discuss > >
_______________________________________________ langsec-discuss mailing list [email protected] https://mail.langsec.org/cgi-bin/mailman/listinfo/langsec-discuss
