ReDoS 발생 원인 및 기존 해결 방법의 한계점 분석
An Analysis of the Causes of ReDoS and the Limitations of the Current Solutions
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
정규 표현식은 패턴 일치가 사용되는 모든 분야에서 광범위하게 사용되고 있다. 하지만 정규 표현식은 서비스 거부 공격의 매개체가 될 수 있는 위험성을 가지고 있다. 정규 표현식을 통한 서비스 거부 공격을 ReDoS 공격이라 하며, 이러한 현상이 발생하는 것은 정규 표현식 엔진의 역추적 기능이 비효율적으로 구현되었기 때문이다. 본 논문에서는 정규 표현식 엔진을 역추적 엔진과 역추적 없는 엔진으로 분류하고, 각 엔진의 구조와 동작 방식을 설명한다. 그 후 역추적 기능이 비효율적임을 보이며, 연구된 ReDoS 해결 방안을 조사하고 한계점을 분석한다. 결과적으로는 ReDoS의 발생 원인과 현황을 토대로 정규 표현식의 문법을 사용하고 연구하는데 고려되어야 할 시사점을 제시하고자 한다.
Abstract
Regular expressions are widely used in many fields for pattern matching. However, regular expressions have a risk of denial-of-service attacks. The denial-of-service attacks using regular expressions are called ReDoS attacks, which occurs because of the inefficiency of backtracking regular expression engines. We classify regular expression engines into two engines: backtracking engines and non-backtracking engines. We describe the structure and operations of each engine and show that the backtracking function is indeed inefficient. We also study the known ReDoS solutions and analyze their limitations. It is important that one has to be careful in selecting regular expression engines and patterns to avoid such attacks. Finally, we mention a few crucial issues that should be considered for the use and study of regular expressions.
참고문헌 (21)
- 국가기록원, "20년 제3차 기록관리 정책포럼 개최 결과 보고" (2020), 국가기록원
- Berglund, M, "Regular Expressions with Backreferences Reexamined", pp.30~41 (2017), Stringology
- "Regular Expression Matching Can Be Simple And Fast" (2007)[URL]
- "Regular Expression Matching in the Wild" (2010)[URL]
- Denial of Service Through Regular Expressions, "sby, S", USENIX, ~, pp.USENIX Security work in progress report, 28 (2003)
- Davis, J. C, "Why Aren’t Regular Expressions a Lingua Franca? An Empirical Study on the Re-Use and Portability of Regular Expressions", pp.2019, ESEC
- Davis, J. C, "Testing Regex Generalizability And Its Implications: A Large-Scale Many-Language Measurement Study", pp.427~439 (2019), ASE
- Friedl, J. E, "Mastering regular expressions" (2006), O'Reilly Media, Inc
- Kleene, S. C, "Representation of Events in Nerve Nets and Finite Automata" (1951)
- Li, Y, "FlashRegex: Deducing Anti-ReDoS Regexes from Examples", pp.659~671 (2020), ASE
- Michael, L. G, "Regexes are Hard: DecisionMaking, Difficulties, and Risks in Programming Regular Expressions", pp.415~426 (2019), ASE
- Petsios, T, "SlowFuzz: Automated DomainIndependent Detection of Algorithmic Complexity Vulnerabilities", CCS, 8, pp.2155~2168 (2017)
- Static Analysis for Regular Expression Exponential Runtime via Substructural Logics, "Rathnayake, A", CoRR, ~, pp.abs (2014), 1405.7058
- "Regular expression Denial of Service – ReDoS" (2012)[URL]
- Shen, Y, "ReScue: Crafting Regular Expression DoS Attacks", pp.225~235 (2018), ASE
- Spencer, H, "Software solutions in C", pp.35~71 (1994)
- "Outage Postmortem" (2016)[URL]
- Thompson, K, "Programming Techniques : Regular Expression Search Algorithm", Communications of the ACM, 11(6), pp.419~422 (1968)
- Van Der Merwe, B, "Turning Evil Regexes Harmless", SAICSIT, pp.1~10 (2017)
- Weideman, N, "Analyzing Matching Time behavior of Backtracking Regular Expression Matchers by Using Ambiguity of NFA", pp.322~334 (2016), CIAA
- Wüstholz, V, "Static Detection of DoS Vulnerabilities in Programs that Use Regular Expressions", TACAS, (2), pp.3~20 (2017)