24. 중첩 컨테이너 재귀 역직렬화 (깊이 제한 부재 / 노드 예산 부재)

난이도 상

내 리뷰 · C#

내 리뷰 · C++

해설 · C#

해설 — 중첩 컨테이너 재귀 역직렬화 (깊이 제한 부재 / 노드 예산 부재)

난이도: 상

요약

ParseValue 는 List 를 만나면 자식마다 자기 자신을 재귀 호출(A) 하지만 깊이 상한이 없다. 공격자가 List(count=1) 을 수천 단계 중첩한 작은 패킷을 보내면 호출 스택이 선형으로 깊어져 StackOverflowException 이 난다 — .NET 에서 이 예외는 catch 할 수 없고 프로세스를 즉시 종료시킨다(원격 DoS). 또한 (B)의 count 와 (C)의 new List<Value>((int)count) 가 신뢰 불가 값이라, count 를 거대하게 주면 과대 선할당(OOM) 또는 (int)count 음수 캐스트로 인한 예외가 나고, 전체 노드 수에 상한이 없어 메모리/CPU 를 고갈시킬 수 있다.

문제점

1. (스택 고갈) 재귀 깊이 무제한 — (A)

증상: 중첩 깊이만큼 스택 프레임이 쌓여 한계를 넘으면 StackOverflowException. .NET 에서는 try/catch 로 처리 불가, 호스트 프로세스가 그대로 죽는다(서버 전체 다운).
재현조건: [2][01 00 00 00](List, count=1) 블록을 N번 이어 붙이고 끝에 [1][int]. N 수천이면 충분.
근본원인: 깊이를 추적·제한하는 인자가 없다. "정상 2~3단계" 가정만 있고 강제가 없다.

2. (메모리 증폭 / 캐스트 결함) count 기반 선할당 — (B)(C)

증상: new List<Value>((int)count) 에서 count=0x7FFFFFFF 면 거대 용량 선할당 시도 → OutOfMemoryException. count >= 0x80000000 이면 (int) 캐스트가 음수가 되어 ArgumentOutOfRangeException(또는 unchecked 환경에 따라 다른 실패). 실제 자식 바이트가 없어도 선할당만으로 자원 소모.
근본원인: 선언 개수를 남은 바이트와 대조하지 않고 신뢰. 부호 없는 와이어 값을 int 로 무검증 캐스트.

3. (CPU/노드 폭증) 전체 노드 총량 무제한

얕고 넓은 트리(자식 매우 많음)로도 노드 수·파싱 시간을 폭증시킬 수 있다.

수정안

깊이 한도와 노드 예산을 파서에 명시하고, count 를 남은 바이트로 상한한다.

public readonly struct ParseLimits { public int MaxDepth=>32; public int MaxNodes=>100_000; }

static Value ParseValue(ref ByteReader r, int depth, ref int nodes)
{
    if (depth > 32) throw new FormatException("too deep");
    if (++nodes > 100_000) throw new FormatException("too many nodes");

    var v = new Value { Tag = (Tag)r.ReadU8() };
    if (v.Tag == Tag.Int) { v.IntVal = r.ReadI32(); return v; }
    if (v.Tag != Tag.List) throw new FormatException("bad tag");      // 미지 태그 거절

    uint count = r.ReadU32();
    if (count > (uint)r.Remaining)                                    // 자식당 최소 1바이트
        throw new FormatException("count exceeds input");
    v.Children = new List<Value>(Math.Min((int)count, 1024));        // 점진 확장
    for (uint i = 0; i < count; i++)
        v.Children.Add(ParseValue(ref r, depth + 1, ref nodes));     // 깊이 +1
    return v;
}

MaxDepth(32~64)로 스택 오버플로 차단, MaxNodes 로 폭/총량 차단.
count > Remaining 으로 거대 선할당 거부. (int) 캐스트 전에 범위 검증.
미지 태그는 화이트리스트로 즉시 거절.

더 나은 설계

재귀를 명시적 스택(반복 루프)으로 바꾸면 콜스택 대신 힙 컬렉션을 쓰고 그 크기를 직접 상한할 수 있어, 잡을 수 없는 StackOverflow 위험을 구조적으로 없앤다.
깊이/노드/바이트/문자열 길이 등 메시지 전체 리소스 예산을 파서 진입점에서 한 번 정의해 공유.
포맷 스펙에 최대 중첩 깊이를 명시하고 게이트웨이에서 1차 검증.

면접 포인트

.NET 의 StackOverflowException 은 catch 불가 — 깊이 무제한 재귀 파서는 작은 입력으로 서버를 죽이는 원격 DoS 다. 발생 자체를 깊이 한도로 막아야 한다.
와이어의 개수/길이는 항상 남은 입력으로 상한하고, 부호 없는 값을 int 로 캐스트하기 전 범위를 검증한다.
신뢰 불가 입력 파서는 깊이·노드·메모리 예산을 명시하고, 가능하면 재귀를 반복+명시 스택으로 전환한다.

해설 · C++

해설 — 중첩 컨테이너 재귀 역직렬화 (깊이 제한 부재 / 노드 예산 부재)

난이도: 상

요약

parseValue 는 LIST 를 만나면 자식마다 자기 자신을 재귀 호출(A) 하는데, 재귀 깊이 상한이 없다. 공격자가 [LIST,count=1][LIST,count=1][LIST,count=1]... 처럼 한 자식만 가진 LIST 를 수천~수만 단계 중첩하면 호출 스택이 선형으로 깊어져 스택 오버플로가 난다 — C++에서는 정의되지 않은 동작이자 사실상 즉시 크래시(서버 다운, 원격 DoS). 작은 입력(수 KB)으로도 가능하다. 더해 (B)의 count 와 (C)의 reserve(count) 는 신뢰 불가 값이라, count 를 거대하게 주면 과대 선할당(OOM) 이, 전체 노드 수에 상한이 없어 메모리·CPU 고갈이 가능하다.

문제점

1. (스택 고갈) 재귀 깊이 무제한 — (A)

증상: 중첩 깊이에 비례해 스택 프레임이 쌓여 가드 페이지를 넘으면 스택 오버플로. C++ 에서는 잡을 수 없고(예외 아님) 프로세스가 죽는다.
재현조건: [2][00000001] (LIST, count=1) 블록을 N번 이어 붙인 뒤 마지막에 [1][int]. N이 수천이면 충분(프레임당 수십~수백 바이트 × 기본 스택 수 MB).
근본원인: 깊이를 추적·제한하는 파라미터가 없다. "정상은 2~3단계"라는 가정만 있고 강제가 없다.

2. (메모리 증폭 / OOM) count 기반 선할당 — (B)(C)

증상: reserve(count) 에 count=0xFFFFFFFF 를 주면 거대한 벡터를 미리 잡으려다 bad_alloc/OOM. 실제 자식 바이트가 없어도 선할당 자체가 자원을 먹는다.
근본원인: 선언된 개수를 남은 바이트와 대조하지 않고 신뢰. (참고: 배치 디코딩 결함과 같은 계열의 "신뢰 불가 길이 선할당".)

3. (CPU/노드 폭증) 전체 노드 총량 무제한

깊이가 아니라 폭으로도 공격 가능: 얕지만 자식이 매우 많은 트리로 노드 수를 폭증시켜 파싱 시간·메모리를 고갈.

수정안

깊이 한도와 노드 예산을 파서에 명시적으로 싣고, count 를 남은 바이트로 상한한다.

struct ParseLimits { int maxDepth = 32; size_t maxNodes = 100000; };

std::unique_ptr<Value> parseValue(ByteReader& r, const ParseLimits& lim,
                                  int depth, size_t& nodes) {
    if (depth > lim.maxDepth)      throw std::runtime_error("too deep");
    if (++nodes > lim.maxNodes)    throw std::runtime_error("too many nodes");

    auto v = std::make_unique<Value>();
    v->tag = static_cast<Tag>(r.readU8());
    if (v->tag == TAG_INT) { v->intVal = r.readI32(); return v; }
    if (v->tag != TAG_LIST) throw std::runtime_error("bad tag");   // 미지 태그 거절

    uint32_t count = r.readU32();
    // 자식은 최소 1바이트(tag) 이상 → 남은 바이트보다 많을 수 없다. 선할당 상한.
    if (count > r.remaining()) throw std::runtime_error("count exceeds input");
    v->children.reserve(std::min<uint32_t>(count, 1024));          // 점진 확장
    for (uint32_t i = 0; i < count; ++i)
        v->children.push_back(parseValue(r, lim, depth + 1, nodes)); // 깊이 +1
    return v;
}

maxDepth(예: 32~64)로 스택 고갈 차단, maxNodes 로 폭/총량 차단.
count > remaining() 으로 거대 선할당 거부, reserve 는 실측 상한으로만.
미지 태그는 즉시 거절(화이트리스트).

더 나은 설계

재귀를 명시적 스택(반복)으로 전환하면 호스트 콜스택 대신 힙 자료구조를 쓰고, 그 크기를 직접 상한할 수 있어 스택 오버플로를 구조적으로 제거한다.
깊이/노드/총바이트/문자열길이 같은 리소스 예산을 파서 진입점에서 한 번 정의해 모든 하위 파싱이 공유하게 한다(메시지 전체 예산).
포맷 차원에서 최대 중첩 깊이를 스펙으로 못박고, 게이트웨이에서 1차 검증.

면접 포인트

신뢰 불가 입력의 재귀 파서는 반드시 깊이 제한을 둔다 — 깊이 무제한 재귀는 작은 입력으로 스택을 터뜨리는 원격 DoS(이른바 "중첩 폭탄").
선언된 개수/길이는 항상 남은 입력 크기로 상한해 선할당 증폭을 막는다.
C++ 스택 오버플로는 예외가 아니라 UB/크래시다 — try/catch 로 못 막으므로 발생 자체를 깊이·노드 예산으로 예방해야 한다. 가능하면 재귀를 반복+명시 스택으로 바꾼다.

← 문제로 돌아가기