정규표현식은 어떻게 동작할까? (백트래킹과 성능의 세계)

개발자라면 누구나 한 번쯤 이메일 검증이나 문자열 파싱을 위해 **정규표현식(Regular Expression)**을 사용해 본 경험이 있을 것입니다.

매우 강력하고 편리한 도구지만, 잘못 작성된 정규표현식 하나가 서버 전체를 마비시킬 수도 있다는 사실을 알고 계신가요?

이 글에서는 정규표현식 엔진의 내부 동작 원리를 파헤치고, 성능 문제의 주범인 **백트래킹(Backtracking)**에 대해 알아보겠습니다.

1. 정규표현식 엔진의 종류

정규표현식 엔진은 크게 두 가지로 나뉩니다.

1. DFA (Deterministic Finite Automaton): 텍스트 기반으로 동작하며 빠르지만, 역참조(Backreference) 같은 고급 기능을 지원하지 않습니다. (예: awk, lex)
2. NFA (Nondeterministic Finite Automaton): 패턴 기반으로 동작하며 다양한 기능을 지원하지만, 최악의 경우 성능이 매우 느려질 수 있습니다. (예: Java, Python, Ruby, JavaScript 등 대부분의 언어)

우리가 주로 사용하는 언어들은 대부분 NFA 방식을 사용합니다. 그리고 NFA의 핵심 메커니즘이 바로 백트래킹입니다.

2. 백트래킹(Backtracking)이란?

백트래킹은 정규표현식 엔진이 패턴 매칭을 시도하다가 실패했을 때, "다시 돌아가서 다른 길을 찾아보는" 과정입니다.

예를 들어, 패턴 /A.*B/를 문자열 A...BC에 매칭한다고 가정해 봅시다.

1. A를 찾습니다. (성공)
2. .*는 가능한 한 많이 매칭하려 하므로(Greedy), 문자열 끝까지(...BC) 먹어 치웁니다.
3. 이제 B를 찾아야 하는데, 이미 문자열 끝에 도달했으므로 실패합니다.
4. 백트래킹 발생: 엔진은 .*가 먹었던 마지막 문자(C)를 뱉어내고 다시 시도합니다.
5. 여전히 B가 아니므로 또 뱉어냅니다.
6. B를 만날 때까지 이 과정을 반복합니다.

3. 재앙의 시작: ReDoS

만약 패턴이 복잡하고 문자열이 길다면, 백트래킹 횟수는 기하급수적으로 늘어날 수 있습니다.

특히 (a+)+와 같은 중첩된 수량자(Nested Quantifiers)를 사용할 때, 특정 입력값에 대해 검사 시간이 폭발적으로 증가하는 현상을 **ReDoS (Regular Expression Denial of Service)**라고 합니다.

공격자가 이를 악용하여 서버에 악의적인 문자열을 보내면, CPU 사용량이 100%로 치솟아 서비스가 중단될 수 있습니다.

ReDoS 예방 팁

1. 중첩 수량자 피하기: (a+)+ 대신 a+를 사용하세요.
2. Lazy 수량자 사용: .* 대신 .*?를 사용하여 필요한 만큼만 매칭하도록 유도하세요.
3. 구체적인 패턴 사용: .* (모든 문자) 보다는 [^"]* (따옴표가 아닌 문자) 처럼 범위를 제한하세요.

결론

정규표현식은 '양날의 검'입니다.

잘 쓰면 수십 줄의 코드를 한 줄로 줄여주는 마법을 부리지만, 원리를 모르고 쓰면 시한폭탄이 될 수 있습니다.

복잡한 정규표현식을 작성할 때는 반드시 내부적으로 얼마나 많은 백트래킹이 발생할지 고민하고, 성능 테스트를 거치는 습관을 들여야 합니다.