Static Analysis for Regular Expression Exponential Runtime via Substructural Logics
作者： Hayo Thielecke , Asiri Rathnayake
DOI:
关键词:
摘要: Regular expression matching using backtracking can have exponential runtime, leading to an algorithmic complexity attack known as REDoS in the systems security literature. In this paper, we build on a recently published static analysis that detects whether given regular runtime for some inputs. We systematically construct more accurate by forming powers and products of transition relations thereby reducing problem reachability. The correctness is proved substructural calculus search trees, where branching tree causing blowup characterized form non-linearity.
harvard.edu
arxiv.org
128.84.21.199参考文章(27)
James Kirrage, Asiri Rathnayake, Hayo Thielecke, Static Analysis for Regular Expression Denial-of-Service Attacks Network and System Security. pp. 135- 148 ,(2013) , 10.1007/978-3-642-38631-2_11
悦朗 守屋, J.E.Hopcroft, J.D. Ullman 著, "Introduction to Automata Theory, Languages, and Computation", Addison-Wesley, A5変形版, X+418, \6,670, 1979 情報処理. ,vol. 21, pp. 802- 803 ,(1980)
Ravi Sethi, Jeffrey D. Ullman, Alfred V. Aho, Compilers: Principles, Techniques, and Tools ,(1986)
Scott A. Crosby, Dan S. Wallach, Denial of service via algorithmic complexity attacks usenix security symposium. pp. 3- 3 ,(2003)
Alain Frisch, Luca Cardelli, Greedy Regular Expression Matching Automata, Languages and Programming. ,vol. 3142, pp. 618- 629 ,(2004) , 10.1007/978-3-540-27836-8_53
Matthew Hennessy, Robin Milner, On Observing Nondeterminism and Concurrency international colloquium on automata, languages and programming. pp. 299- 309 ,(1980) , 10.1007/3-540-10003-2_79
Jens Palsberg, Andrew W. Appel, Modern Compiler Implementation in Java ,(1997)
Samin Ishtiaq, Peter W. O'Hearn, BI as an assertion language for mutable data structures ACM SIGPLAN Notices. ,vol. 46, pp. 84- 96 ,(2011) , 10.1145/1988042.1988050
Cristiano Calcagno, Philippa Gardner, Uri Zarfaty, Context logic and tree update symposium on principles of programming languages. ,vol. 40, pp. 271- 282 ,(2005) , 10.1145/1040305.1040328
Satoshi Sugiyama, Yasuhiko Minamide, Checking Time Linearity of Regular Expression Matching Based on Backtracking Ipsj Online Transactions. ,vol. 7, pp. 82- 92 ,(2014) , 10.2197/IPSJTRANS.7.82