정규표현식 (Regular Expression)

정규표현식(Regular Expression, regex)의 기본 문법부터 NFA/DFA 엔진 내부 동작, 백트래킹과 ReDoS 위험, 리눅스 커널의 lib/glob.c 패턴 매칭과 ftrace 필터, 사용자 공간 도구(grep, sed, awk)의 BRE·ERE·PCRE까지 폭넓게 다룹니다.

정규표현식 개요

정규표현식(Regular Expression)은 1956년 수학자 스티븐 클리니(Stephen Kleene)가 정규 집합(Regular Set)을 기술하기 위해 제안한 표기법에서 유래합니다. 1968년 켄 톰프슨(Ken Thompson)이 이를 텍스트 편집기 QED에 구현하면서 컴퓨터 과학에 도입되었고, 이후 ed, grep(Global Regular Expression Print), sed, awk를 거쳐 POSIX 표준과 Perl 확장으로 발전했습니다.

형식 언어 이론에서의 위치

촘스키 계층(Chomsky Hierarchy)에서 정규표현식은 Type-3 정규 언어(Regular Language)를 기술합니다. 유한 오토마톤(Finite Automaton)으로 인식할 수 있는 언어의 집합과 정확히 대응하며, 문맥 자유 언어(Context-Free Language, Type-2)보다 표현력이 제한됩니다. 단, 현대 정규표현식 엔진(PCRE 등)은 역참조(Backreference)와 전후방 탐색(Lookaround) 같은 확장을 포함하여, 이론적 정규 언어의 범위를 넘어섭니다.

정규표현식 메타문자 참조표

메타문자(Metacharacter)

메타문자(Metacharacter)는 정규표현식에서 특별한 의미를 가지는 문자입니다. 리터럴(literal) 문자가 자기 자신만을 나타내는 것과 달리, 메타문자는 매칭 규칙을 제어합니다.

핵심 메타문자 12종

연산자 우선순위(Precedence)

정규표현식의 메타문자에는 프로그래밍 언어의 연산자처럼 우선순위가 있습니다. 우선순위를 이해하지 못하면 예상과 다른 매칭 결과가 나올 수 있습니다.

메타문자별 동작 예제

# . (점): 줄바꿈 제외 임의 한 문자
echo -e "cat\ncar\ncab" | grep 'ca.'
# 출력: cat, car, cab (모두 매칭)

# [] 문자 클래스 vs . 와일드카드
echo -e "cat\ncar\ncab\nca9" | grep 'ca[tr]'
# 출력: cat, car만 (cab, ca9 제외)

# | 대안: 우선순위 주의
echo "catdog" | grep -E 'cat|dog'     # "cat" 또는 "dog" 포함
echo "catdog" | grep -E '^cat|dog$'   # "cat으로 시작" 또는 "dog으로 끝남"
echo "catdog" | grep -E '^(cat|dog)$' # 전체가 "cat" 또는 "dog"

# ^ 의 이중 의미: 줄 시작 vs 부정
echo "abc123" | grep -o '[^0-9]'     # 숫자 아닌 문자: a, b, c
echo "abc123" | grep '^abc'           # "abc"로 시작하는 줄

이스케이프 규칙

메타문자를 문자 그대로 매칭하려면 백슬래시(\)를 앞에 붙입니다. 셸과 프로그래밍 언어의 문자열 이스케이프가 중첩되므로 주의가 필요합니다. 특히 C 언어에서 정규표현식을 사용할 때는 이중 이스케이프가 필요한 경우가 많습니다.

# 셸에서 grep 사용 시 이스케이프 계층
grep '192\.168\.1\.1' /var/log/syslog     # 작은따옴표: 셸 이스케이프 없음
grep "192\\.168\\.1\\.1" /var/log/syslog   # 큰따옴표: 셸 + regex 이중 이스케이프

# 커널 모듈 C 코드에서의 이스케이프
const char *pattern = "192\\.168\\.1\\.1";  /* C 문자열 + regex 이중 이스케이프 */

# 자주 이스케이프가 필요한 문자들
grep 'price: \$[0-9]\+' shop.txt          # $ 리터럴
grep 'version [0-9]\+\.[0-9]\+' log.txt    # . 리터럴
grep -E '^\[ERROR\]' syslog                # [ ] 리터럴

문자 클래스(Character Class)

문자 클래스(Character Class)는 대괄호 [...] 안에 매칭할 문자들의 집합을 나열하는 구문입니다.

기본 문법

POSIX 문자 클래스

POSIX 표준은 로캘(Locale)에 독립적인 문자 분류를 제공합니다. grep의 [[:class:]] 구문으로 사용합니다.

# POSIX 문자 클래스 사용 예 (grep)
grep '[[:digit:]]\{3\}-[[:digit:]]\{4\}' contacts.txt    # 전화번호 패턴 000-0000
grep '[[:xdigit:]]\{8\}' dmesg.log                       # 8자리 16진수 (주소값)
grep '[[:upper:]][[:lower:]]*' names.txt                   # 대문자로 시작하는 단어

# ERE에서는 중괄호 이스케이프 불필요
grep -E '[[:digit:]]{3}-[[:digit:]]{4}' contacts.txt

수량자(Quantifier)

수량자(Quantifier)는 앞의 요소가 몇 번 반복되어야 하는지를 지정합니다. 수량자의 기본 동작은 탐욕적(Greedy)으로, 가능한 한 많이 매칭하려 합니다.

수량자 종류

탐욕적 vs 게으른 매칭

탐욕적 수량자는 최대한 많은 문자를 먼저 소비한 후, 전체 패턴이 매칭되지 않으면 하나씩 되돌리며(백트래킹) 시도합니다. 게으른 수량자는 반대로 최소한의 문자부터 시도합니다.

# 탐욕적 vs 게으른 실전 비교
echo '<b>bold</b> and <i>italic</i>' | grep -oP '<.*>'
# 출력: <b>bold</b> and <i>italic</i>  (전체 하나)

echo '<b>bold</b> and <i>italic</i>' | grep -oP '<.*?>'
# 출력:
# <b>
# </b>
# <i>
# </i>

그룹과 캡처(Group & Capture)

괄호 ()는 두 가지 역할을 합니다: 하위 표현식을 그룹화하여 수량자를 적용하고, 매칭된 부분 문자열을 캡처하여 역참조(Backreference)에 사용합니다.

그룹 종류

캡처 그룹 번호 매기기

캡처 그룹 번호는 여는 괄호 (가 나타나는 순서대로 1부터 할당됩니다. 중첩된 그룹에서는 바깥 괄호가 먼저 번호를 받습니다. 이 규칙을 이해하지 못하면 역참조에서 엉뚱한 값을 참조하게 됩니다.

비캡처 그룹의 성능 이점

비캡처 그룹 (?:...)은 그룹화만 수행하고 매칭 결과를 저장하지 않습니다. 캡처가 불필요한 곳에서는 비캡처 그룹을 사용하면 엔진이 매칭 결과를 메모리에 저장하는 오버헤드가 없어 성능이 향상됩니다. 특히 반복이 많은 패턴에서 차이가 큽니다.

# 캡처 그룹 vs 비캡처 그룹 비교
# 나쁜 예: 캡처할 필요 없는데 캡처 그룹 사용
grep -P '(https?|ftp)://(\w+\.)+\w+' urls.txt

# 좋은 예: 비캡처 그룹으로 변경 (같은 매칭, 더 빠름)
grep -P '(?:https?|ftp)://(?:\w+\.)+\w+' urls.txt

역참조(Backreference)

캡처 그룹이 매칭한 텍스트를 동일 패턴 내에서 \1, \2 등으로 다시 참조할 수 있습니다. 이는 정규 언어의 범위를 넘어서는 기능으로, DFA로는 구현할 수 없고 NFA 백트래킹이 필요합니다. 역참조는 "앞에서 매칭한 것과 동일한 텍스트"를 요구하므로, 같은 패턴이 아니라 같은 결과를 반복 매칭합니다.

# 역참조: 반복되는 단어 찾기
echo "the the quick fox fox" | grep -oP '\b(\w+)\s+\1\b'
# 출력: the the
#       fox fox

# sed에서 캡처 그룹 활용: 날짜 형식 변환
echo "2026-03-23" | sed -E 's/([0-9]{4})-([0-9]{2})-([0-9]{2})/\3\/\2\/\1/'
# 출력: 23/03/2026

# 명명된 그룹 (Python 구문, grep -P)
echo "error: file not found" | grep -oP '(?P<level>\w+): (?P<msg>.+)'
# 출력: error: file not found

앵커(Anchor)

앵커(Anchor)는 문자를 소비하지 않고 위치만 매칭하는 제로 너비 단언(Zero-width Assertion)입니다. 일반 문자나 메타문자가 "이 문자를 매칭하라"는 의미라면, 앵커는 "이 위치에 있어야 한다"는 조건을 부여합니다. 앵커는 입력 포인터를 전진시키지 않으므로 매칭 결과에 문자가 포함되지 않습니다.

\b 와 \B의 차이

단어 경계(Word Boundary) \b는 커널 소스 코드 검색에서 매우 유용합니다. 예를 들어 int 타입을 검색할 때 printf, uint32_t, interrupt 같은 단어 안의 "int"를 제외하려면 단어 경계가 필수적입니다. \b는 \w(단어 문자: [a-zA-Z0-9_])와 \W(비단어 문자) 사이의 경계를 의미하며, \B는 정확히 반대로 같은 유형의 문자 사이(단어 내부)를 의미합니다.

# \b: 단어 경계 — "int" 단어만 매칭
echo "int printf uint32_t interrupt" | grep -oP '\bint\b'
# 출력: int (하나만)

# \B: 비단어 경계 — 단어 내부의 "int"만 매칭
echo "int printf uint32_t interrupt" | grep -oP '\Bint\B'
# 출력: (printf 안의 "int") — pr[int]f

# 단어 경계 활용: "int"라는 단어만 찾기 (printf, uint 등 제외)
grep -w 'int' kernel_source.c        # grep -w = \bint\b 와 동일
grep '\bint\b' kernel_source.c

MULTILINE 모드의 영향

기본적으로 ^와 $는 전체 입력 문자열의 시작과 끝만 매칭합니다. MULTILINE 모드((?m) 또는 grep의 기본 동작)에서는 \n 뒤의 각 줄 시작과 \n 앞의 각 줄 끝을 매칭합니다. PCRE의 \A와 \z는 MULTILINE 모드와 무관하게 항상 전체 문자열의 절대적 시작과 끝을 매칭합니다.

# MULTILINE: 각 줄의 시작에서 #include 찾기
grep -P '(?m)^#include' header.h

# 전체 줄이 주석인 라인만 찾기
grep -E '^[[:space:]]*(//|/\*)' source.c

# 빈 줄 찾기
grep -c '^$' source.c                 # 빈 줄 개수

# 줄 전체가 특정 패턴인 경우만
grep -E '^[[:space:]]*return[[:space:]]+0;[[:space:]]*$' *.c

# \A vs ^: 여러 줄 문자열에서 차이
# \A는 첫 줄의 시작만, ^는 MULTILINE에서 매 줄 시작
printf "line1\nline2\nline3" | grep -cP '^line'   # 3 (매 줄)
printf "line1\nline2\nline3" | grep -cP '\Aline'  # 1 (첫 줄만)

전방탐색/후방탐색(Lookaround)

전방탐색(Lookahead)과 후방탐색(Lookbehind)은 앵커처럼 문자를 소비하지 않으면서 주변 컨텍스트를 확인하는 제로 너비 단언입니다. PCRE와 대부분의 프로그래밍 언어에서 지원하지만, POSIX BRE/ERE에서는 지원하지 않습니다.

# 실전 활용: 커널 로그에서 특정 함수 뒤의 에러 코드 추출
grep -oP '(?<=kmalloc failed: )-?\d+' /var/log/kern.log

# 비밀번호 검증: 대문자, 소문자, 숫자 모두 포함 확인
echo "P4ssWord" | grep -P '^(?=.*[A-Z])(?=.*[a-z])(?=.*\d).{8,}$'

# C 코드에서 함수 호출만 찾기 (선언/정의 제외)
grep -P '(?<!^)\b\w+\s*\([^)]*\)\s*;' kernel_module.c

복합 Lookaround 패턴

여러 lookaround를 연결하면 복합 조건을 표현할 수 있습니다. 긍정과 부정 탐색을 조합하여 "A 뒤에 있지만 B 뒤는 아닌" 같은 정교한 조건을 만들 수 있습니다.

# 복합 lookaround: 여러 조건 동시 검증
# "숫자이면서 뒤에 px가 아닌 것" (CSS 값에서 단위 없는 숫자 찾기)
echo "100px 200 300em 50" | grep -oP '\b\d+(?!px|em|rem|%)\b'
# 출력: 200, 50

# 커널 로그에서: "error" 포함하되 "corrected" 뒤에 오는 것은 제외
grep -P '(?<!corrected )error' /var/log/kern.log

# 숫자를 3자리마다 콤마 삽입 (천 단위 구분자)
echo "1234567890" | sed -E ':a;s/([0-9])([0-9]{3})(,|$)/\1,\2\3/;ta'
# PCRE lookaround으로 같은 것: (?<=\d)(?=(\d{3})+(?!\d))

Lookaround 성능 고려사항

Lookaround는 제로 너비이지만 무비용은 아닙니다. 특히 가변 길이 후방탐색(variable-length lookbehind)은 엔진이 현재 위치에서 역방향으로 탐색해야 하므로 비용이 높습니다. POSIX ERE가 lookaround를 지원하지 않는 이유 중 하나이며, 일부 엔진(JavaScript ES2018 이전, RE2)은 후방탐색을 아예 지원하지 않습니다. PCRE에서도 후방탐색 패턴의 길이는 고정되어야 합니다((?<=ab)은 가능하지만 (?<=a+)은 불가).

정규표현식 엔진: NFA vs DFA

정규표현식 엔진은 크게 NFA(Nondeterministic Finite Automaton)와 DFA(Deterministic Finite Automaton) 두 가지 방식으로 나뉩니다. 엔진 선택은 성능과 기능 사이의 근본적인 트레이드오프를 결정합니다.

Thompson NFA vs 백트래킹 NFA

톰프슨이 제안한 원래 NFA 시뮬레이션은 모든 가능한 상태를 동시에 추적하여 O(nm) 시간을 보장합니다. 반면, Perl/PCRE 등의 백트래킹(Backtracking) NFA는 역참조 같은 확장 기능을 지원하기 위해 한 번에 하나의 경로만 탐색하고, 실패 시 되돌아가는 방식을 사용합니다.

백트래킹(Backtracking)

백트래킹(Backtracking)은 NFA 기반 정규표현식 엔진의 핵심 메커니즘입니다. 패턴의 특정 지점에서 여러 선택지가 있을 때, 하나를 시도하고 실패하면 이전 지점으로 돌아가 다른 선택지를 시도합니다. 이 과정은 재귀적 깊이 우선 탐색(DFS)과 동일하며, 엔진 내부에서 호출 스택이나 명시적 스택을 사용하여 "되돌아갈 지점"을 기록합니다.

백트래킹이 발생하는 상황

백트래킹은 다음 세 가지 상황에서 발생합니다:

• 수량자 선택 — a*가 문자를 소비하는 횟수. 탐욕적 수량자는 최대부터, 게으른 수량자는 최소부터 시도하며, 실패 시 하나씩 되돌립니다.
• 대안 선택 — a|b|c에서 어느 분기를 선택할지. 왼쪽부터 순서대로 시도하며, 실패 시 다음 대안으로 넘어갑니다.
• 선택적 요소 — a?가 매칭할지 건너뛸지. 두 가지 선택지를 순서대로 시도합니다.

스택 깊이와 한계

백트래킹 NFA는 각 선택 지점마다 스택 프레임을 생성합니다. 깊은 중첩 패턴이나 긴 입력에서는 스택 오버플로가 발생할 수 있으며, 이것이 PCRE2의 pcre2_set_depth_limit()이나 Python의 re 모듈 재귀 제한이 존재하는 이유입니다.

백트래킹 최적화 기법

엔진 수준에서 백트래킹을 줄이는 대표적인 최적화 기법들입니다:

# 백트래킹이 많은 패턴 vs 최적화된 패턴
# 나쁜 예: .*가 불필요하게 많이 백트래킹
echo "name=value;name2=value2" | grep -oP '.*=(.*);'

# 좋은 예: [^=]* [^;]* 로 범위 한정
echo "name=value;name2=value2" | grep -oP '[^=]*=([^;]*);'

# 소유적 수량자 (PCRE): 백트래킹 없이 실패 시 즉시 종료
echo "aaaaaab" | grep -P 'a++b'    # 매칭 (a를 모두 소비 후 b 확인)
echo "aaaaaa" | grep -P 'a++b'     # 실패 (a 반환 없이 즉시 실패)

ReDoS(Regular Expression Denial of Service)

ReDoS(Regular Expression Denial of Service)는 악의적으로 설계된 입력이 백트래킹 NFA 엔진에서 지수적 시간 복잡도를 유발하여 서비스 거부를 일으키는 공격입니다. 웹 애플리케이션의 입력 검증, WAF 규칙, 로그 파싱 등에서 발생할 수 있습니다.

취약 패턴 유형

방어 기법

실제 ReDoS 사례

ReDoS는 이론적 위협이 아닌 실제 운영 환경에서 반복적으로 발생하는 문제입니다:

• Cloudflare 장애 (2019-07-02) — WAF 규칙의 (?:(?:\"|'|\]|\}|\\|\d|(?:nan|infinity|true|false|null|undefined|symbol|math)|\`|\-|\+)+[)]*;?((?:\s|-|~|!|{}|\|\||\+)*.*(?:.*=.*))) 패턴이 전 세계 서비스를 약 30분간 중단시켰습니다. 백트래킹 폭발이 CPU 사용률을 100%로 올렸습니다.
• Stack Overflow 장애 (2016) — 정규표현식 기반 HTML 파싱에서 중첩 패턴이 지수적 백트래킹을 유발하여 서비스가 중단되었습니다.
• Node.js 보안 권고 — ua-parser-js, marked 등 인기 npm 패키지에서 ReDoS 취약점이 여러 차례 발견되었습니다.

ReDoS 방어 전략 상세

Atomic 그룹 (?>...)은 그룹 내부에서 매칭이 완료되면 그 결과를 "잠금"하여 백트래킹을 허용하지 않습니다. 이는 소유적 수량자(++, *+)와 동일한 효과이며, 중첩 수량자 패턴에서 지수적 폭발을 근본적으로 차단합니다.

# Atomic 그룹으로 ReDoS 방어
# 취약: (a+)+$ — 백트래킹 폭발
time echo 'aaaaaaaaaaaaaaaaaaaaa!' | grep -P '(a+)+$'
# → 수 초~수십 초 소요 (입력 길이에 따라 지수적 증가)

# 방어: (?>a+)+$ — Atomic 그룹으로 백트래킹 차단
time echo 'aaaaaaaaaaaaaaaaaaaaa!' | grep -P '(?>a+)+$'
# → 즉시 실패 (백트래킹 없음)

# 근본적 해결: 패턴 단순화
# (a+)+$ → a+$ (동일한 매칭, 중첩 제거)
time echo 'aaaaaaaaaaaaaaaaaaaaa!' | grep -P 'a+$'
# → 즉시 실패

커널 glob 패턴 매칭 (lib/glob.c)

리눅스 커널은 정규표현식 대신 lib/glob.c에 구현된 단순한 glob 패턴 매칭을 사용합니다. glob_match() 함수는 *(임의 문자열), ?(임의 한 문자), [charclass](문자 클래스) 세 가지 와일드카드만 지원합니다.

glob_match() 지원 구문

/* lib/glob.c — glob_match() 핵심 구현 (v6.x 간략화) */
bool glob_match(char const *pat, char const *str)
{
    for (;;) {
        unsigned char c = *pat++;

        switch (c) {
        case '*':
            /* 연속 * 건너뛰기 */
            while (*pat == '*')
                pat++;
            if (!*pat)
                return true;  /* 패턴 끝이 *면 항상 매칭 */
            /* str의 각 위치에서 나머지 패턴 매칭 시도 */
            while (*str) {
                if (glob_match(pat, str))
                    return true;
                str++;
            }
            return !*pat;

        case '?':
            if (!*str++)
                return false;
            break;

        case '[': {
            /* 문자 클래스 매칭: [!...] 부정, [a-z] 범위 지원 */
            bool inv = (*pat == '!');
            /* ... 범위/개별 문자 비교 로직 ... */
            break;
        }

        default:
            if (c == '\\')
                c = *pat++;
            if (*str++ != c)
                return false;
            break;
        }
    }
}

ftrace 필터와 glob

ftrace는 커널 함수 추적 도구로, set_ftrace_filter와 set_ftrace_notrace 파일에 glob 패턴을 써서 추적 대상 함수를 선택합니다. 내부적으로 lib/glob.c의 glob_match()를 사용합니다.

# ftrace glob 필터 실전 사용
cd /sys/kernel/debug/tracing

# 스케줄러 관련 함수만 추적
echo 'sched_*' > set_ftrace_filter

# 여러 패턴 추가 (>> 사용)
echo '*lock*' >> set_ftrace_filter

# 특정 모듈의 함수만
echo ':mod:ext4' > set_ftrace_filter

# 제외 필터: irq 관련 함수 제외
echo '*irq*' > set_ftrace_notrace

# 현재 필터 확인
cat set_ftrace_filter

# 사용 가능한 함수 목록에서 글로브 검색
grep 'sched_' available_filter_functions | head -20

perf probe 이벤트 필터링

perf 도구도 이벤트와 함수 필터링에 glob 패턴을 활용합니다. ftrace와 유사하게 커널 내부 glob_match()를 거쳐 동작합니다.

# perf probe: glob 패턴으로 함수 검색
perf probe -F 'sched_*'         # sched_ 접두사 함수 목록
perf probe -F '*alloc*'        # alloc 포함 함수

# 함수 진입점에 프로브 추가
perf probe 'schedule'
perf probe 'do_sys_open filename:string'

# perf stat: 이벤트 필터링
perf stat -e 'sched:sched_switch' -- sleep 1

# perf record: 특정 함수 호출 기록
perf record -g -e 'probe:schedule' -- sleep 5

# tracepoint 필터 표현식 (정규표현식 아닌 비교 연산)
perf record -e 'sched:sched_switch' --filter 'prev_comm == "nginx"'

tracepoint 필터 표현식

perf의 --filter 옵션은 정규표현식이 아닌 비교 연산 기반 필터를 사용합니다. 이는 커널 내부에서 tracepoint 데이터를 효율적으로 필터링하기 위한 설계로, 정규표현식의 복잡도 위험을 피합니다.

# tracepoint 필터 사용 예
perf record -e 'sched:sched_switch' --filter 'prev_comm == "nginx" || next_comm == "nginx"' -- sleep 5

# glob 패턴 필터 (~ 연산자)
perf record -e 'sched:sched_switch' --filter 'next_comm ~ "kworker*"' -- sleep 5

# 우선순위 기반 필터
perf record -e 'sched:sched_switch' --filter 'prev_prio < 100' -- sleep 5

# 커널 함수 glob 검색 후 정규표현식으로 정밀 필터링
perf probe -F '*alloc*' | grep -E '(kmalloc|vmalloc|kzalloc)'
perf probe -F '*lock*' | grep -vE '(unlock|clock)'   # unlock, clock 제외

grep: BRE vs ERE

grep은 리눅스에서 가장 많이 사용되는 정규표현식 도구입니다. POSIX 표준은 BRE(Basic Regular Expression)와 ERE(Extended Regular Expression) 두 가지 문법을 정의하고, GNU grep은 추가로 PCRE를 지원합니다.

# BRE: 메타문자에 이스케이프 필요
grep '\(error\|warning\): .\+' build.log

# ERE: 이스케이프 불필요 (권장)
grep -E '(error|warning): .+' build.log

# PCRE: 고급 기능 사용 가능
grep -P '(?<=ERROR:\s)\d{4,}' syslog              # 후방탐색
grep -P '\b0x[[:xdigit:]]{8,16}\b' dmesg.log        # 커널 주소

# 고정 문자열 검색 (정규표현식 아님, 가장 빠름)
grep -F 'CONFIG_PREEMPT=y' /boot/config-$(uname -r)

# 유용한 grep 옵션 조합
grep -rn 'TODO\|FIXME\|HACK' --include='*.c' .    # 재귀 + 줄번호 + 파일 필터
grep -c '^#include' *.h                             # include 개수 카운트
grep -l 'mutex_lock' kernel/*.c                      # 매칭 파일 이름만

sed/awk에서의 정규표현식

sed (Stream Editor)

sed는 스트림 편집기로, 정규표현식 기반의 텍스트 변환에 특화되어 있습니다. 기본적으로 BRE를 사용하며, -E 옵션으로 ERE를 활성화합니다.

# 기본 치환: s/패턴/대체/
sed 's/oldtext/newtext/' file.txt                  # 각 줄의 첫 매칭만
sed 's/oldtext/newtext/g' file.txt                 # 모든 매칭 (global)

# ERE 모드 (-E)
sed -E 's/([0-9]+)\.([0-9]+)/\2.\1/g' version.txt  # 캡처 그룹으로 순서 바꾸기

# 커널 소스 관련 실전 예제
# CONFIG 옵션 값 추출
sed -n 's/^CONFIG_\(.*\)=y/\1/p' .config

# include 경로 변환
sed -E 's|#include <linux/(.*)>|#include "linux/\1"|' source.c

# 주석 제거 (C 스타일 한줄 주석)
sed 's|//.*$||' source.c

# 여러 줄 패턴: 빈 줄 연속 제거
sed '/^$/N;/^\n$/d' file.txt

# 특정 패턴 사이의 텍스트만 출력
sed -n '/^START$/,/^END$/p' log.txt

awk (패턴-액션 언어)

awk는 ERE를 사용하며, 패턴 매칭과 필드 처리를 결합한 텍스트 처리 언어입니다.

# 기본 패턴 매칭
awk '/error|warning/' build.log                    # error 또는 warning 포함 줄
awk '!/^#/' config.txt                              # 주석 아닌 줄만

# 필드 기반 정규표현식
awk -F: '$3 ~ /^[0-9]+$/ && $3 >= 1000' /etc/passwd  # UID >= 1000 사용자

# 커널 로그 분석
dmesg | awk '/\[[[:space:]]*[0-9]+\.[0-9]+\].*error/i {print NR": "$0}'

# /proc/meminfo 파싱
awk '/^(MemTotal|MemFree|MemAvailable):/ {printf "%-16s %d MB\n", $1, $2/1024}' /proc/meminfo

# 커널 모듈 의존성 분석
lsmod | awk 'NR>1 && $3>0 {printf "%-20s used by %d modules: %s\n", $1, $3, $4}'

커널 빌드 시스템에서의 활용

커널 빌드 과정에서 Kconfig 파일, Makefile, 커널 설정(.config)을 처리할 때 sed/awk가 빈번하게 사용됩니다.

# .config에서 활성화된 모듈만 추출
grep -E '^CONFIG_.*=m$' .config | sed 's/^CONFIG_//;s/=m$//' | sort

# Kconfig에서 depends on 의존성 트리 추출
grep -A1 'config [A-Z]' drivers/net/Kconfig | awk '/^config/{name=$2} /depends on/{print name": "$0}'

# Makefile에서 obj-$(CONFIG_*) 규칙 파싱
grep -E 'obj-\$\(CONFIG_' drivers/net/Makefile | sed -E 's/obj-\$\(CONFIG_([^)]+)\)\s*\+=\s*(.*)/\1 -> \2/'

# 커널 빌드 로그에서 경고 요약
make -j$(nproc) 2>&1 | grep -E 'warning:' | sed -E 's/.*\/([^/]+):[0-9]+:.*/\1/' | sort | uniq -c | sort -rn | head -20

# /proc 파일 일괄 읽기 및 포맷팅
for f in /proc/sys/kernel/sched_*; do
  awk '{printf "%-40s %s\n", FILENAME, $0}' FILENAME="$(basename $f)" "$f"
done

sed vs awk vs grep 선택 가이드

PCRE(Perl Compatible Regular Expressions)

PCRE(Perl Compatible Regular Expressions)은 Perl 5의 정규표현식 문법을 C 라이브러리로 구현한 것입니다. POSIX BRE/ERE를 크게 확장하며, 현대 프로그래밍 언어 대부분의 정규표현식 엔진이 PCRE에 영향을 받았습니다.

PCRE 전용 확장 기능

PCRE vs PCRE2 차이

JIT 컴파일 메커니즘

PCRE2의 JIT(Just-In-Time) 컴파일러는 정규표현식 패턴을 네이티브 기계어로 변환합니다. 일반 인터프리터 모드 대비 5~10배 빠른 매칭 속도를 제공하며, 동일 패턴을 반복적으로 사용하는 경우(로그 분석, 네트워크 패킷 필터링 등)에 특히 효과적입니다.

# PCRE 확장 기능 예제

# Atomic 그룹: ReDoS 방지
echo "aaaaaaaaab" | grep -P '(?>a+)+b'        # 즉시 매칭

# 유니코드 한글 매칭
echo "Linux 커널 개발" | grep -P '\p{Hangul}+'  # "커널", "개발"

# 재귀 패턴: 중첩 괄호 매칭 (정규 언어 초월)
echo "func(a, (b, c))" | grep -oP '\((?:[^()]*|(?R))*\)'

# 인라인 모드 변경
echo "Hello WORLD" | grep -P '(?i)hello'     # 대소문자 무시
echo -e "line1\nline2" | grep -P '(?s)line1.line2'  # DOTALL: . 이 \n 매칭

# 복잡한 패턴에 주석 달기 (확장 모드)
grep -P '(?x)
  \b                # 단어 경계
  [0-9]{1,3}        # 1~3자리 숫자
  (\.[0-9]{1,3}){3} # .숫자 3번 반복
  \b                # 단어 경계
' access.log

라이브러리 가용성 확인

# 시스템에서 PCRE/PCRE2 확인
pcre2-config --version 2>/dev/null || echo "PCRE2 미설치"
pkg-config --modversion libpcre2-8 2>/dev/null

# grep이 사용하는 PCRE 버전
grep -P --version 2>&1 | head -1

# PCRE2 설치 (Debian/Ubuntu)
# apt install libpcre2-dev

# PCRE2 설치 (RHEL/Fedora)
# dnf install pcre2-devel

실전 패턴 예제

커널 개발과 시스템 관리에서 자주 사용하는 정규표현식 패턴을 모았습니다.

네트워크 패턴

# IPv4 주소 (단순 버전)
grep -E '[0-9]{1,3}\.[0-9]{1,3}\.[0-9]{1,3}\.[0-9]{1,3}' syslog

# IPv4 주소 (엄격한 검증: 0-255 범위)
grep -P '\b(?:(?:25[0-5]|2[0-4]\d|[01]?\d\d?)\.){3}(?:25[0-5]|2[0-4]\d|[01]?\d\d?)\b' syslog

# MAC 주소
grep -iE '([0-9a-f]{2}:){5}[0-9a-f]{2}' dmesg.log

# IPv6 주소 (축약형 포함, 간략 버전)
grep -iE '[0-9a-f:]{2,39}' ip6tables.log

커널 로그 패턴

# dmesg 타임스탬프 + 에러 추출
dmesg | grep -E '^\[[[:space:]]*[0-9]+\.[0-9]+\].*([Ee]rror|[Ff]ail|[Ww]arn)'

# 커널 주소 (16진수 8~16자리)
grep -P '\b0x[0-9a-fA-F]{8,16}\b' /var/log/kern.log

# OOM killer 로그
grep -E 'Out of memory|oom-kill|Killed process' /var/log/kern.log

# 커널 패닉/Oops
grep -E 'kernel panic|BUG:|Oops:|Call Trace:' /var/log/kern.log

소스 코드 패턴

# 함수 정의 찾기 (C)
grep -EnP '^[a-zA-Z_]\w*\s+\**[a-zA-Z_]\w*\s*\([^)]*\)\s*\{' *.c

# TODO/FIXME/HACK 주석
grep -rn '(TODO|FIXME|HACK|XXX)(\([^)]*\))?:' --include='*.c' .

# #define 매크로와 값 추출
grep -E '^#define\s+\w+\s+.+' include/linux/*.h

# 구조체 정의
grep -P '^struct\s+\w+\s*\{' include/linux/sched.h

보안 패턴

보안 감사나 침입 탐지에서 사용하는 정규표현식 패턴입니다. 로그 분석이나 소스 코드 리뷰에서 잠재적 보안 문제를 찾는 데 활용됩니다.

# SSH 브루트포스 시도 탐지
grep -E 'Failed password for (invalid user )?(\w+) from [0-9.]+' /var/log/auth.log

# SQL injection 시도 패턴 (웹 로그)
grep -iE "(union\s+select|or\s+1\s*=\s*1|'\s*or\s*'|drop\s+table)" access.log

# 소스 코드에서 잠재적 버퍼 오버플로 함수 찾기
grep -rn '\b(strcpy|strcat|sprintf|gets)\s*(' --include='*.c' .

# 하드코딩된 비밀번호/토큰 탐지
grep -rnE '(password|token|secret|api_key)\s*=\s*"[^"]+"' --include='*.c' .

시스템 관리 패턴

# systemd 서비스 상태에서 실패한 것만
systemctl --failed | grep -E '^\s*●\s+\S+\.service'

# 디스크 사용량 80% 이상인 파티션
df -h | awk 'NR>1 && +$5 >= 80 {print $0}'

# 네트워크 인터페이스 IP 추출
ip addr | grep -oP 'inet \K[0-9.]+(?=/)'

# crontab에서 스케줄 주기 파싱
crontab -l | grep -vE '^(#|$)' | awk '{printf "%s %s %s %s %s → %s\n", $1,$2,$3,$4,$5, substr($0,index($0,$6))}'

Git 패턴

Git은 정규표현식과 고정 문자열 검색을 모두 지원합니다. -G는 정규표현식으로 diff를 검색하고, -S는 고정 문자열의 추가/삭제를 검색합니다(pickaxe). 두 옵션의 차이를 이해하는 것이 중요합니다.

# -G (regex): diff에서 패턴 매칭 (추가 또는 삭제 줄에 포함)
git log -G 'mutex_lock' --oneline

# -S (pickaxe): 문자열 출현 횟수가 변한 커밋 (추가/삭제된 경우)
git log -S 'mutex_lock' --oneline

# 커밋 메시지 패턴 검색
git log --grep='fix.*race' -i --oneline

# 특정 파일 패턴의 변경 이력
git log --all -- '**/sched*.c'

# git grep: 워킹 트리에서 정규표현식 검색 (매우 빠름)
git grep -nE '(WARN|BUG)_ON\(' -- '*.c'

# git blame과 결합: 특정 패턴이 있는 줄의 마지막 수정자
git blame -L '/mutex_lock/,+5' kernel/sched/core.c

시간 복잡도 분석

정규표현식 매칭의 시간 복잡도는 엔진 유형과 패턴 구조에 따라 크게 달라집니다. 여기서 n은 입력 문자열 길이, m은 패턴 길이입니다.

언제 어떤 도구를 쓸 것인가

올바른 도구 선택은 성능에 큰 영향을 줍니다. 커널 소스 트리(수만 개 파일, 수천만 줄)에서의 검색은 도구 선택에 따라 수초에서 수분까지 차이가 날 수 있습니다.

유니코드와 정규표현식

현대 정규표현식 엔진은 유니코드(Unicode) 문자를 처리할 수 있지만, 바이트 기반 매칭과 코드포인트(Code Point) 기반 매칭은 동작이 크게 다릅니다. 특히 한글, CJK, 이모지 처리에서는 유니코드 인식이 필수적입니다.

유니코드 속성 \p{}

PCRE와 대부분의 현대 엔진은 \p{Property} 구문으로 유니코드 문자 속성에 기반한 매칭을 지원합니다. 이는 [a-zA-Z]로는 처리할 수 없는 다국어 텍스트에 필수적입니다.

# 유니코드 속성 기반 매칭 (PCRE)
echo "Linux 커널 개발 가이드 v2.0" | grep -oP '\p{Hangul}+'
# 출력: 커널, 개발, 가이드

# 한자 매칭
echo "漢字 テスト" | grep -oP '\p{Han}+'
# 출력: 漢字

# 모든 문자(숫자/공백/구두점 제외) 추출
echo "Hello, 안녕 123!" | grep -oP '\p{L}+'
# 출력: Hello, 안녕

# UTF-8 바이트 경계 주의
# 한글 '가' = 0xEA 0xB0 0x80 (3바이트)
# 바이트 수준 . 은 1바이트만 매칭하므로 유니코드 모드 필요
echo "가나다" | grep -P '.'     # 유니코드: "가"(한 코드포인트)
echo "가나다" | grep -Pa '.'    # ASCII: 0xEA(한 바이트) — 깨진 출력

정규표현식 컴파일과 캐싱

정규표현식은 사용 전에 내부 표현(NFA, DFA 또는 바이트코드)으로 컴파일되어야 합니다. 이 컴파일 비용을 이해하면 성능 최적화에 도움이 됩니다.

컴파일 비용과 캐싱 전략

정규표현식 컴파일은 한 번만 수행하고 결과를 재사용하는 것이 핵심 최적화입니다. grep은 내부적으로 패턴을 한 번 컴파일한 후 각 줄에 재사용합니다. 프로그래밍에서는 루프 바깥에서 컴파일하거나, 컴파일된 객체를 전역으로 유지해야 합니다.

# 나쁜 예 (의사 코드): 매번 컴파일
for line in input:
    if re.match('pattern', line):  # 매 반복마다 컴파일
        process(line)

# 좋은 예: 한 번 컴파일, 재사용
compiled = re.compile('pattern')
for line in input:
    if compiled.match(line):      # 컴파일된 패턴 재사용
        process(line)

보안과 정규표현식

정규표현식은 입력 검증의 핵심 도구이지만, 잘못 작성된 패턴은 오히려 보안 취약점이 됩니다. ReDoS 외에도 정규표현식과 관련된 보안 고려사항이 있습니다.

입력 검증 시 주의사항

커널 보안에서의 패턴 매칭

# auditd 규칙에서 패턴 매칭
# 특정 경로 접근 감시 (glob 패턴)
auditctl -w /etc/shadow -p rwa -k shadow_access
auditctl -w /etc/passwd -p wa -k passwd_change

# audit 로그에서 패턴 검색
ausearch -k shadow_access | grep -E 'type=SYSCALL.*comm="[^"]+"'

# seccomp 프로필에서 syscall 필터링
# (seccomp은 정규표현식이 아닌 syscall 번호 기반)
# 하지만 프로필 생성 시 strace 출력을 regex로 분석
strace -f -o trace.log ./target_program
grep -oP '(\w+)\(' trace.log | sort -u   # 사용된 syscall 목록 추출

정규표현식 테스트와 디버깅

복잡한 정규표현식은 반드시 테스트해야 합니다. 패턴이 의도대로 동작하는지, 엣지 케이스에서 실패하지 않는지, 성능 문제가 없는지 검증하는 방법을 소개합니다.

단계별 매칭 추적

# grep -c: 매칭 줄 수 카운트 (빠른 검증)
grep -cP 'pattern' test_input.txt

# grep -o: 매칭된 부분만 출력 (패턴 정확도 확인)
echo "test string 123 and 456" | grep -oP '\d+'
# 출력: 123
#       456

# grep --color: 매칭 위치 시각화
echo "Hello World Hello" | grep --color=always 'Hello'

# 패턴 디버깅: 단계적으로 복잡도 높이기
# 1단계: 기본 구조 확인
echo "192.168.1.1" | grep -oP '[0-9]+'
# 2단계: 구분자 추가
echo "192.168.1.1" | grep -oP '[0-9]+\.[0-9]+'
# 3단계: 전체 패턴
echo "192.168.1.1" | grep -oP '[0-9]+\.[0-9]+\.[0-9]+\.[0-9]+'

엣지 케이스 체크리스트

정규표현식을 작성한 후에는 다음 엣지 케이스들을 테스트해야 합니다:

커널 glob 셀프테스트

CONFIG_GLOB_SELFTEST=y를 설정하면 부팅 시 glob_match()의 정확성을 자동 검증합니다. 총 51개의 테스트 케이스가 와일드카드, 문자 클래스, 이스케이프, 엣지 케이스를 포괄합니다.

# glob 셀프테스트 활성화 및 확인
# menuconfig에서: Library routines → glob_match() selftest
grep 'CONFIG_GLOB_SELFTEST' /boot/config-$(uname -r)

# 부팅 후 셀프테스트 결과 확인
dmesg | grep 'glob:'
# 정상: "glob: 51 self-tests passed, 0 failed"

커널 설정

정규표현식 및 패턴 매칭과 관련된 커널 설정 옵션입니다. 이 옵션들 사이의 의존 관계를 이해하면 커널 구성을 더 정확하게 할 수 있습니다.

# 현재 커널의 관련 설정 확인
grep -E 'CONFIG_(GLOB|TEXTSEARCH|FTRACE|NETFILTER_XT_MATCH_STRING)' /boot/config-$(uname -r)

# glob 셀프테스트 결과 확인 (CONFIG_GLOB_SELFTEST=y 일 때)
dmesg | grep 'glob:'

# 텍스트 검색 모듈 로딩 확인
lsmod | grep 'ts_'
# ts_kmp, ts_bm, ts_fsm이 로드되었는지 확인

# 런타임 시 textsearch 모듈 수동 로드
modprobe ts_kmp    # KMP 알고리즘
modprobe ts_bm     # Boyer-Moore 알고리즘

# iptables -m string 사용 시 자동 로드
iptables -A INPUT -m string --algo kmp --string "malware" -j DROP

관련 문서

정규표현식 및 패턴 매칭과 관련된 주제를 더 깊이 이해하려면 다음 문서를 참고하세요.

• Text Search (lib/textsearch) — 커널 텍스트 검색 프레임워크, KMP·Boyer-Moore·FSM 알고리즘
• ftrace — 커널 함수 추적, set_ftrace_filter glob 필터
• perf — 성능 분석 도구, 이벤트 필터링과 프로브
• Bash — 셸 스크립트, [[ $s =~ regex ]] 패턴 매칭
• Netfilter — 패킷 필터링, xt_string 문자열 매칭 모듈
• eBPF 보안 — eBPF 기반 네트워크 필터링과 패턴 매칭
• Git — git log -G regex 검색, git grep

참고 자료

• POSIX 정규표현식 명세 — IEEE Std 1003.1 Chapter 9: Regular Expressions (opengroup.org)
• regex(7) — POSIX.2 정규표현식 리눅스 man 페이지 (man7.org)
• regcomp(3) — POSIX 정규표현식 컴파일·매칭 API (man7.org)
• PCRE2 공식 문서 — Perl Compatible Regular Expressions (pcre.org)
• PCRE2 문법 요약 — 메타문자·수량자·어설션 빠른 참조 (pcre.org)
• Regular-Expressions.info — 정규표현식 종합 튜토리얼 및 레퍼런스 (regular-expressions.info)
• 정규표현식 엔진 비교표 — BRE·ERE·PCRE·JavaScript·Python 등 기능 비교 (regular-expressions.info)
• GNU grep 매뉴얼 — BRE·ERE·PCRE 모드와 옵션 (gnu.org)
• GNU sed 매뉴얼 — 스트림 에디터 정규표현식 치환 (gnu.org)
• GNU awk 매뉴얼 — 정규표현식 챕터 (gnu.org)
• Python re 모듈 — 정규표현식 라이브러리 공식 문서 (docs.python.org)
• Python 정규표현식 HOWTO — 단계별 튜토리얼 (docs.python.org)
• perlre — Perl 정규표현식 공식 문서 (perldoc.perl.org)
• perlretut — Perl 정규표현식 튜토리얼 (perldoc.perl.org)
• regex101 — 온라인 정규표현식 테스트·디버깅 도구 (regex101.com)
• Regular Expression Matching Can Be Simple And Fast — NFA 기반 매칭의 우수성, Russ Cox (swtch.com)
• Regular Expression Matching: the Virtual Machine Approach — VM 기반 regex 엔진 설계, Russ Cox (swtch.com)
• Regular Expression Matching in the Wild — 실전 regex 엔진 구현, Russ Cox (swtch.com)
• RE2 문법 레퍼런스 — Google RE2 엔진 지원 정규표현식 문법 (github.com/google/re2)
• 커널 소스 — lib/glob.c 글로브 패턴 매칭 구현 (Bootlin Elixir)
• 커널 소스 — lib/ts_kmp.c KMP 텍스트 검색 알고리즘 (Bootlin Elixir)
• 커널 소스 — lib/ts_bm.c Boyer-Moore 텍스트 검색 알고리즘 (Bootlin Elixir)
• 커널 공식 문서 — ftrace: Function Tracer, 글로브 필터 문법 (kernel.org)
• LWN.net — Glob matching improvements in the kernel (lwn.net)