Skip to content

CVE-2007-4772-tcl-regex-nfa-error-propagation-infinite-loop.md

Latest commit

 

History

History
189 lines (144 loc) · 9.18 KB

CVE-2007-4772-tcl-regex-nfa-error-propagation-infinite-loop.md

File metadata and controls

189 lines (144 loc) · 9.18 KB
Raw

Tcl 정규식 NFA 복제의 오류 전파 누락으로 인한 무한 루프 (CVE-2007-4772)

메타데이터

항목 내용
CVE ID CVE-2007-4772
영향 제품/버전 Tcl 8.4.16 이하, PostgreSQL 7.4.18/8.0.14/8.1.10/8.2.5 이하의 Tcl-derived 정규식 코드
취약 지점 generic/regc_nfa.c::duptraverse()가 재귀 NFA 복제 실패 후 오류 상태를 확인하지 않고 arc 복사를 계속함
CWE CWE-399 (Resource Management Errors, NVD 분류)
CVSS CVSS v2 4.0 Medium — AV:N/AC:L/Au:S/C:N/I:N/A:P
공개일 2007-10-07
수정 버전 Tcl 8.4.17, PostgreSQL 7.4.19 / 8.0.15 / 8.1.11 / 8.2.6
주요 수정 Tcl 8.4.17의 regc_nfa.c error-state propagation 및 regexp-22.1 회귀 테스트

개요

Tcl 정규식 컴파일러는 입력 패턴을 NFA 상태와 arc 그래프로 바꾼 뒤, 최적화 과정에서 그래프 일부를 복제한다. 취약 버전의 duptraverse()는 대상 상태 복제가 실패해 전역 오류 상태가 세워져도, 바로 반환하지 않고 방금 복제하려던 상태의 tmp 포인터가 존재한다고 가정한 채 arc 복사를 계속했다.

특수하게 만든 정규식은 이 경로에서 복잡한 순환 제약 또는 과도한 상태 생성을 유발할 수 있었다. 그 결과 컴파일 단계가 끝나지 않거나 과도한 CPU를 사용해 서비스 거부로 이어졌다. PostgreSQL은 당시 Tcl 정규식 엔진에서 파생된 코드를 사용했기 때문에 같은 취약점의 영향을 받았다.

Tcl 8.4.17의 패치는 duptraverse()가 재귀 호출 뒤 NISERR()를 다시 검사하고, 오류가 있으면 현재 arc 복사를 중단하게 했다. 같은 릴리스는 상태 수 추적을 추가하고, 순환 constraint arc 제거 및 회귀 테스트 regexp ($|^X)* {}도 포함했다.

사전 지식

정규식 컴파일러는 문자열을 그래프로 바꾼다

정규식 엔진은 패턴 문자열을 직접 매칭하지 않는다. 먼저 패턴을 파싱해 상태와 전이로 구성된 NFA 그래프를 만든다. 상태는 "현재 정규식의 어느 위치에 있는가"를 나타내고, arc는 다음 상태로 넘어가는 조건을 나타낸다.

정규식 패턴
    │
    ▼
parser/compiler
    │
    ▼
NFA 그래프
    ├─ state
    ├─ arc: 문자 소비
    └─ arc: ^, $, lookahead 같은 제약

컴파일러는 이 그래프를 단순화하거나 특정 변환을 적용하면서 상태를 복제한다. Tcl의 duptraverse()는 원본 상태 s를 방문하고, 각 outgoing arc의 목적지 상태도 재귀적으로 복제한 뒤, 원본 arc를 복제된 상태 사이에 다시 만든다.

원본 그래프
  s ──arc──> to

복제 절차
  1. s->tmp 생성
  2. to->tmp 생성
  3. cparc(..., s->tmp, to->tmp)

복제 그래프
  s' ──arc'──> to'

여기서 중요한 불변식은 "arc를 복사하려면 목적지 상태의 복제본이 반드시 있어야 한다"는 점이다.

오류 상태는 즉시 전파되어야 한다

NFA 복제 중 새 상태를 만들 수 없거나 상태 수 제한을 넘으면 Tcl 정규식 컴파일러는 NERR(...)로 오류를 기록하고, NISERR()로 그 상태를 확인한다. 오류가 발생한 뒤에는 중간 구조가 완성되지 않았을 수 있으므로, 호출자는 다음 구조 변경을 멈춰야 한다.

정상
duptraverse(to)
    └─ to->tmp 생성 완료
          ▼
      cparc(s->tmp, to->tmp) 안전

오류
duptraverse(to)
    └─ 오류 상태 설정, to->tmp 없음
          ▼
      cparc(s->tmp, to->tmp) 호출 금지

이 계약이 깨지면 assert가 켜진 빌드에서는 단언 실패가 날 수 있고, 꺼진 빌드에서는 불완전한 그래프를 대상으로 후속 변환이 계속되어 진행하지 않는 루프나 과도한 반복으로 이어질 수 있다.

취약점 분석

패치 전: 재귀 호출이 실패해도 현재 arc 복사를 계속했다

Tcl 8.4.16의 duptraverse()는 먼저 현재 상태의 복제본을 만들고, outgoing arc 목록을 순회한다. 루프 조건에는 !NISERR()가 있지만, 문제는 루프 본문 내부의 재귀 호출 직후에 오류를 다시 확인하지 않았다는 점이다.

for (a = s->outs; a != NULL && !NISERR(); a = a->outchain) {
    duptraverse(nfa, a->to, (struct state *)NULL);
    assert(a->to->tmp != NULL);
    cparc(nfa, a, s->tmp, a->to->tmp);
}

duptraverse(nfa, a->to, NULL)가 실패하면 NISERR()는 참이 되고 a->to->tmp는 없을 수 있다. 그러나 같은 반복 본문은 계속 실행되어 assert(a->to->tmp != NULL)와 cparc()까지 도달한다. 루프 조건의 !NISERR()는 다음 반복으로 넘어갈 때만 평가되므로 이미 늦다.

[패치 전]

duptraverse(s)
    │
    ├─ s->tmp 생성
    │
    └─ 각 outgoing arc a 순회
          │
          ▼
      duptraverse(a->to)
          │
          ├─ 정상: a->to->tmp 생성
          │      └─ cparc(s->tmp, a->to->tmp)
          │
          └─ 오류: NISERR 설정, tmp 미생성 가능
                 │
                 ▼
           현재 본문이 계속 진행
                 │
                 ▼
           assert/cparc가 불완전한 NFA 상태를 사용
                 │
                 ▼
           정규식 컴파일 비진행 또는 과도한 CPU 사용

NVD와 배포판 권고는 crafted regular expression으로 infinite loop가 가능하다고 설명한다. upstream 회귀 테스트는 regexp ($|^X)* {}를 추가했다. 이 패턴은 빈 문자열 시작/끝 제약과 반복을 조합해, 그래프 복제와 제약 처리 경로를 자극한다.

PostgreSQL 영향은 Tcl-derived regex 코드 때문이다

PostgreSQL 7.4/8.0/8.1/8.2 계열도 같은 취약점으로 공지됐다. 핵심은 PostgreSQL SQL 권한이 운영체제 권한과 같다는 뜻이 아니라, SQL에서 정규식 연산자를 실행할 수 있는 사용자가 backend 프로세스에 비싼 정규식 컴파일을 시킬 수 있다는 점이다.

SQL 정규식 조건
    │
    ▼
PostgreSQL regex compiler
    │ Tcl-derived NFA code
    ▼
crafted pattern compile
    │
    └─ backend CPU 점유/응답 지연

따라서 권고의 CVSS는 인증 필요(Au:S)와 가용성 부분 영향(A:P)으로 평가됐다.

수정 방법

Tcl 8.4.17의 핵심 패치는 재귀 복제 직후 오류 상태를 다시 확인하는 두 줄이다. 오류가 있으면 현재 arc 복사를 중단하므로, a->to->tmp가 없을 수 있는 상태에서 cparc()가 호출되지 않는다.

 for (a = s->outs; a != NULL && !NISERR(); a = a->outchain) {
     duptraverse(nfa, a->to, (struct state *)NULL);
+    if (NISERR())
+        break;
     assert(a->to->tmp != NULL);
     cparc(nfa, a, s->tmp, a->to->tmp);
 }

패치 후 흐름은 오류를 "현재 반복 본문 안"에서 끊는다.

[패치 후]

duptraverse(a->to)
    │
    ├─ 정상
    │    ├─ a->to->tmp 존재
    │    └─ cparc()로 arc 복사
    │
    └─ 오류
         ├─ NISERR() 확인
         └─ break → 불완전한 tmp를 사용하지 않음

같은 compare에는 NFA 상태 수를 size로 추적해 REG_MAX_STATES를 넘으면 REG_ETOOBIG으로 멈추는 변경, pull()/push()에서 자기 자신을 가리키는 constraint arc를 제거하는 변경도 포함됐다. 이 보강은 crafted regex가 상태 폭증이나 순환 constraint로 컴파일러를 비정상 경로에 밀어 넣는 것을 줄인다.

운영자는 Tcl을 8.4.17 이상으로, PostgreSQL은 7.4.19 / 8.0.15 / 8.1.11 / 8.2.6 이상으로 올려야 한다. PostgreSQL 서버에서는 패치 전 임시 완화로 신뢰되지 않은 사용자의 정규식 연산 사용 경로를 제한할 수 있지만, SQL 기능 전반에 영향을 줄 수 있으므로 업그레이드를 대체하지 않는다.

미해결/불확실 지점

  • 공개 diff는 duptraverse() 오류 전파와 regexp-22.1 테스트를 명확히 보여준다. 다만 오래된 tracker의 상세 토론은 현재 접근성이 제한적이어서, 이 보고서는 tracker 문장보다 upstream diff와 배포판 권고를 기준으로 분석했다.
  • PostgreSQL은 이후 릴리스에서도 정규식 복잡도 제한과 관련한 별도 수정이 여러 차례 있었다. CVE-2007-4772의 직접 수정은 2007년 유지보수 릴리스 범위로 한정해 보는 것이 안전하다.

참고 자료