regex와 reDoS

old_dorim·2022년 7월 29일

regex

특정한 규칙을 가진 문자열의 집합을 표현하는 형식이다. 비밀번호를 만들 때 몇 개의 숫자, 몇 개의 영어 대소문자, 특수문자를 포함해야한다 이런 내용을 적는 것을 경험해보았을 것이다. 문자열에서 특정 문자 패턴을 검색(검사) 하는 것이다.

/pattern/[Flag]

식으로 작성한다. 안이 문자의 패턴, 밖에 flag 부분이 어떻게 검색되는 것인지 알 수 있다.

Flags

flag는 설정하지 않으면 해당 문자열을 한번 찾는다
g- global, 해당 문자열을 전부 찾는다
i- ignore case, 대소문자 전부 구분
m- multi line, 문자열 행이 바뀌어도 찾는다

/pattern/g

위에 3개말고도 많은데 mdn 웹 독스에 많이 나와있다.

Patterns

간단하게 적고 예시 하나씩만 들겠다

Groups and ranges

범위 내에서 검색

|, (), [], [^], (?:)
[1-3],[a-g]식으로 범위 안에 속한 것을 검색한다, 1,2,3 검색, abcdefg 검색하게 된다.

Quantifiers

수량자, 검색 수량 정하기

?, *, +, {n}, {min,}, {min,max}

{3}하면 3개 찾는다.

Boundary-type

문자 위치를 제한한다

\b, \B, ^, $
\b string의 중간이나 맨 끝만 검색한다(문자열이 아닌 것과 붙은 문자열만 검색)

Character classes

글자 타입을 제한한다

\, ., \d, \D, \w, \W, \s, \S
\ 특수문자가 아닌 문자

reDOS

대부분의 언어에서 기본으로 제공하는 Regexp 엔진은 Backtracking(하다가 막히면 돌아감)으로 정규표현식 처리 시 가능한 모든 경로를 탐색하는데, 이로 인해 비효율적인 작업을 여러번 시도하게 된다. 이는 서버나 처리에 큰 무리를 줄 수가 있다.
어떤 경우에는 aaaaX일 때는 16번의 검색, aaaaaaaaaaaaaaaaX가 들어오면 65536번의 검색이 필요해진다.
이 regex 처리를 이용하여 DOS 공격을 할 수도 있다.(당할 수도 있다...) stackoverflow가 이것 때문에 털린 적이 있다.

이를 막기 위해서는
1. 아예 다른 처리 방식의 외부 Regex 엔진을 쓴다.
2. Regexp 패턴을 체크해보고 반복적인 작업이 발생할 수 있는지 테스트하고 보완한다.
3. ReScue, SafeRegex 같은 ReDOS 탐지 도구를 통해서 ReDOS의 가능성을 체크해볼 수 있다.