백트래킹(Backtracking) 방식의 함정: 정규 표현식(Regular Expression) 성능 저하의 주범
by DD
5개월 전
조회수 14
백트래킹(Backtracking) 방식의 정규 표현식 엔진은 특정 패턴에서 지수적 시간 복잡도(Exponential Time Complexity)를 보이며 성능 저하를 유발함.
톰슨 NFA(Thompson NFA) 기반 엔진은 이러한 문제를 해결하며, 선형 시간 복잡도(Linear Time Complexity)를 보장하여 빠른 성능을 제공함.
Java, Perl, PHP, Python, Ruby 등 많은 언어에서 백트래킹 방식을 사용하며, 이는 성능 병목(Performance Bottleneck)의 원인이 됨.
DFA(Deterministic Finite Automaton) 캐싱을 통해 톰슨 NFA의 성능을 더욱 향상시킬 수 있으며, 실제 구현(Real Implementation)에 적용 가능함.
백트래킹(Backtracking) 방식의 취약점
본문에서는 Perl, Python, PHP, Ruby 등에서 사용되는 백트래킹(Backtracking) 방식의 정규 표현식 엔진이 특정 패턴에서 심각한 성능 저하를 겪는다고 지적한다. 특히 `a?nan`과 같은 정규 표현식에서 `a?` 부분이 여러 번 중첩될 경우, 지수적 시간 복잡도(Exponential Time Complexity)를 가지며, 입력 문자열의 길이가 증가함에 따라 실행 시간이 급격히 증가하는 문제점을 보여준다. 이러한 문제는 DoS(Denial of Service) 공격에 악용될 수 있다.
톰슨 NFA(Thompson NFA) 알고리즘의 우수성
반면, 톰슨 NFA(Thompson NFA) 기반의 정규 표현식 엔진은 를 보장하여 백트래킹 방식의 문제를 해결한다. 톰슨 NFA는 정규 표현식을 NFA(Non-deterministic Finite Automaton)로 변환하고, 이를 통해 문자열을 매칭하는 방식으로 작동한다. 이러한 방식은 입력 문자열을 한 번만 읽으면서 매칭을 수행하므로, 백트래킹 방식에 비해 훨씬 빠르고 예측 가능한 성능을 제공한다. 특히, 을 통해 성능을 더욱 향상시킬 수 있다.
