26. 시퀀스 번호 랩어라운드와 시리얼 산술 (최신/과거 판정 붕괴)

난이도 상

내 리뷰 · C#

내 리뷰 · C++

해설 · C#

해설 — 시퀀스 번호 랩어라운드와 시리얼 산술 (최신/과거 판정 붕괴)

난이도: 상

요약

최신 판정 (A)와 윈도우 판정 (B)가 시퀀스를 선형 정수처럼 비교한다(seq > _lastSeq, _lastSeq - seq). 16비트 시퀀스는 65535 다음 0으로 순환하므로, 경계를 넘는 순간 "더 큰 수 = 더 최신"이라는 가정이 깨진다. 정상적으로 도착한 직후 패킷이 과거로 오판돼 버려지거나(세션 정지), 오래된 리플레이가 최신으로 둔갑한다. 해법은 시리얼 넘버 산술(RFC 1982) — 모듈러 뺄셈으로 "최신/과거"를 판정하는 것.

문제점

[랩어라운드 오판 / 부호 없는 순환 비교 결함]
- 증상 1 (세션 정지): _lastSeq = 65535인 상태에서 진짜 다음 패킷 seq = 0이 오면, (A) 0 > 65535는 거짓이라 최신이 아님. (B) 65535 - 0 = 65535 <= 256? ushort - ushort는 int로 승격돼 65535가 되고 윈도우(256)를 한참 벗어나 폐기. 이후 0,1,2,…가 모두 같은 식으로 버려져 수신이 영영 막힌다. _lastSeq는 65535에 고정.
- 증상 2 (리플레이를 최신으로 오인): _lastSeq = 0(방금 wrap)일 때 늦게 도착한 옛 패킷 seq = 65535는 (A) 65535 > 0이 참이라 최신으로 처리되고 _lastSeq가 65535로 되돌아간다 → 진짜 최근 패킷들이 다시 과거로 밀린다.
- 재현 조건: 세션이 충분히 오래 유지돼 시퀀스가 한 바퀴(65536개) 도는 경계. 1초에 수십 패킷이면 분 단위면 도달.
- 근본 원인 (A)(B): 순환하는 양을 전순서(total order) 인 정수 대소로 비교했다. 순환 공간에서는 "a가 b보다 최신"이 절대 크기가 아니라 두 점 사이의 모듈러 거리(어느 방향이 더 가까운가) 로 정의돼야 한다.
[묵시적 정수 승격]
- _lastSeq - seq에서 ushort는 int로 승격된다. 그래서 0 - 1이 -1이 아니라 65535도 아닌 -1(int), 65535 - 0은 65535로, 의도한 16비트 모듈러 결과가 아니다. wrap을 다루려면 결과를 다시 ushort로 잘라야 한다.

수정안

RFC 1982의 시리얼 산술을 쓴다. "a가 b보다 최신"은 wrap 한 뺄셈 결과가 공간의 절반(0x8000) 미만인지로 판정한다.

// a 가 b 보다 최신인가? (16비트 순환)
static bool IsNewer(ushort a, ushort b) => (ushort)(a - b) < 0x8000;

// b 기준으로 a 가 얼마나 과거인가(0..65535, wrap 반영)
static ushort Distance(ushort newer, ushort older) => (ushort)(newer - older);

public bool Accept(ushort seq)
{
    if (!_hasAny) { _hasAny = true; _lastSeq = seq; _recent.Add(seq); return true; }

    if (IsNewer(seq, _lastSeq))                 // 모듈러 최신 판정
    {
        _lastSeq = seq;
        if (!_recent.Add(seq)) return false;
        Trim();
        return true;
    }

    // 과거 쪽: 윈도우 안의 재정렬만 허용 (wrap 반영 거리)
    if (Distance(_lastSeq, seq) <= WindowSize)
    {
        if (!_recent.Add(seq)) return false;
        Trim();
        return true;
    }
    return false;
}

검증:

_lastSeq=65535, seq=0 → (ushort)(0-65535) = 1 < 0x8000 → 최신으로 수용. 정상.
_lastSeq=0, seq=65535(옛 리플레이) → (ushort)(65535-0)=65535, < 0x8000? 아니오 → 최신 아님. Distance(0,65535)=(ushort)(0-65535)=1 <= 256 → 윈도우 안 과거로 보고 중복 체크. _lastSeq는 0 유지. 정상.

핵심은 (ushort) 캐스팅으로 16비트 모듈러를 강제하고, 0x8000(공간 절반)을 기준으로 최신/과거를 가르는 것. 더 견고하게는 비트마스크 슬라이딩 윈도우로 중복을 O(1)에 거른다.

더 나은 설계

비트마스크 윈도우: _lastSeq와 ulong bitmap(최근 64개 수신 여부)로, 새 시퀀스가 오면 shift = Distance 만큼 비트맵을 밀고 해당 비트로 중복을 판정. HashSet보다 빠르고 메모리 일정. (QUIC/DTLS의 anti-replay 윈도우 방식.)
시퀀스 폭 키우기: 32비트(혹은 64비트)면 실사용 세션에서 wrap이 거의 안 일어나 위험 창이 사라진다. 단 모듈러 비교는 폭과 무관하게 항상 적용하는 게 안전(언젠가는 wrap).
트레이드오프: 16비트는 헤더가 작지만 wrap 주기가 짧아 모듈러 비교가 필수. 32/64비트는 안전마진↑·헤더 바이트↑. 윈도우 크기는 재정렬 허용 범위와 메모리의 절충.

면접 포인트

"순환하는 시퀀스는 정수 대소로 비교하면 안 된다" — RFC 1982 시리얼 산술과 0x8000(절반) 기준을 설명할 수 있는가.
부호 없는 정수의 묵시적 승격(ushort→int)이 wrap 로직을 어떻게 망치는지, 왜 다시 캐스팅이 필요한지.
안티-리플레이 윈도우(비트마스크)의 동작과 QUIC/DTLS에서의 쓰임.

해설 · C++

해설 — 시퀀스 번호 랩어라운드와 시리얼 산술 (최신/과거 판정 붕괴)

난이도: 상

요약

최신 판정 (A)와 윈도우 판정 (B)가 시퀀스를 선형 정수처럼 비교한다(seq > last_seq_, last_seq_ - seq). 16비트 시퀀스는 65535 다음 0으로 순환하므로 경계를 넘는 순간 "더 큰 수 = 더 최신" 가정이 깨진다. 정상 도착 패킷이 버려져 수신이 멈추거나, 옛 리플레이가 최신으로 둔갑한다. 해법은 시리얼 넘버 산술(RFC 1982) — 모듈러 뺄셈 판정.

문제점

[랩어라운드 오판 / 부호 없는 순환 비교 결함]
- 증상 1 (수신 정지): last_seq_=65535에서 진짜 다음 seq=0 → (A) 0 > 65535 거짓. (B) 65535 - 0은 uint16_t가 int로 승격돼 65535, 윈도우(256) 초과로 폐기. 이후 0,1,2,…가 모두 버려져 영영 막힌다. last_seq_는 65535 고정.
- 증상 2 (리플레이를 최신으로): last_seq_=0일 때 옛 seq=65535 → (A) 65535 > 0 참 → 최신 처리, last_seq_가 65535로 후퇴.
- 재현 조건: 세션이 오래 유지돼 시퀀스가 한 바퀴 도는 경계.
- 근본 원인: 순환 양을 전순서(정수 대소)로 비교. 순환 공간에선 "더 최신"이 절대 크기가 아니라 모듈러 거리(어느 방향이 가까운가) 다.
[묵시적 정수 승격]
- last_seq_ - seq에서 uint16_t는 int로 승격된다. 0 - 1은 uint16_t의 65535가 아니라 int -1, 65535 - 0은 65535. 16비트 모듈러를 원하면 결과를 static_cast<uint16_t>로 잘라야 한다.

수정안

// a 가 b 보다 최신인가? (16비트 순환)
static inline bool is_newer(std::uint16_t a, std::uint16_t b) {
    return static_cast<std::uint16_t>(a - b) < 0x8000;
}
// newer 기준 older 까지의 wrap 반영 거리
static inline std::uint16_t distance(std::uint16_t newer, std::uint16_t older) {
    return static_cast<std::uint16_t>(newer - older);
}

bool accept(std::uint16_t seq) {
    if (!has_any_) { has_any_ = true; last_seq_ = seq; recent_.insert(seq); return true; }

    if (is_newer(seq, last_seq_)) {                 // 모듈러 최신 판정
        last_seq_ = seq;
        if (!recent_.insert(seq).second) return false;
        trim();
        return true;
    }
    if (distance(last_seq_, seq) <= kWindowSize) {   // wrap 반영 윈도우
        if (!recent_.insert(seq).second) return false;
        trim();
        return true;
    }
    return false;
}

검증:

last_seq_=65535, seq=0 → (uint16_t)(0-65535)=1 < 0x8000 → 최신 수용. 정상.
last_seq_=0, seq=65535(리플레이) → (uint16_t)(65535-0)=65535, <0x8000 아님 → 최신 아님. distance(0,65535)=1 <= 256 → 윈도우 과거. last_seq_ 0 유지. 정상.

핵심: static_cast<uint16_t>로 16비트 모듈러 강제 + 0x8000(절반) 기준.

더 나은 설계

비트마스크 슬라이딩 윈도우: last_seq_ + uint64_t bitmap으로 최근 64개 수신 여부를 O(1) 판정(QUIC/DTLS anti-replay). unordered_set보다 빠르고 메모리 일정.
시퀀스 폭 확대: 32/64비트면 실사용에서 wrap이 사실상 안 일어난다. 그래도 모듈러 비교는 항상 적용(언젠가는 wrap).
트레이드오프: 16비트는 헤더 작음·wrap 주기 짧음 → 모듈러 필수. 32/64비트는 안전마진↑·헤더↑. 윈도우 크기는 재정렬 허용 vs 메모리.

면접 포인트

순환 시퀀스는 정수 대소 비교 금지 — RFC 1982와 0x8000 기준.
uint16_t의 int 승격이 wrap 로직을 깨는 메커니즘과 캐스팅 필요성.
안티-리플레이 비트마스크 윈도우 동작.

← 문제로 돌아가기