브라우저를 죽이는 한 줄짜리 코드 (Nested quantifiers and runaway backtracking)

발생일: 2011.1.13

문제:

언제였더라? 프렌드 홍이 얘기해줬던가?

어떤 면접에서 면접관이 JVM 을 죽이는 한 줄짜리 코드를 작성해보라고 했다는 이야기가 생각났다.

그럼 브라우저를 죽이는 한 줄짜리 자바스크립트 코드는 어떤 게 있을까?

해결책:

며칠 전 정규식의 중첩 수량자(nested quantifier)와 역추적 폭주(runaway backtracking)에 관한 부분을 보고,

위에서 얘기했던 한 줄짜리 코드 이야기가 생각나서 재밌는 부제(?)를 달아봤다.^^;

아래 코드는 대상문자열인 "AAAAA..." 가 /(A+A+)+B/ 에 매치되는지 테스트하는 정규식 구문이다.

/(A+A+)+B/.test("AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA");

위 코드는 중첩 수량자에 의해 매치가 실패되는 것을 확인하기까지 340억 번 이상의 백트래킹을 시도하게 되며,

사파리를 제외한 모든 브라우저에서 위 코드를 수행하기 위해 10분 이상 소요된다. (즉, 브라우저를 죽인다)

사파리 최신 버전의 경우에만, 순환되는 정규식을 탐지해 매칭을 중지한다.

Runaway Backtracking 에 대한 자세한 내용은 아래 링크를 참고.

http://www.regular-expressions.info/catastrophic.html