Static analysis of regular expressions

[摘要] ENGLISH ABSTRACT : Regular expressions are widely used throughout the programming community.In most cases, regular expressions allow for pattern matching tasks to be performedefficiently, but in some instances regular expression matching can beextremely slow. The exploit of the potential slowness of regular expressionmatching, is known as a regular expression denial of service attack. We investigateregular expression denial of service attacks, by approaching it froma computational complexity and automata theoretic point of view. A methodfor accurately modeling the matching time behaviour of a backtracking regularexpression matcher, by using automata theoretic methods, is presented.We analyze our models by using the concept of ambiguity in nondeterministicfinite-state automata. Our approach is evaluated on repositories of regularexpressions often used in practice. Techniques for mitigating the vulnerabilityof backtracking regular expression matchers are investigated as a means tothwart regular expression denial of service attacks.

[发布机构] Stellenbosch University