[2025-09-29] Lemon

🦥 본문

Existing System

DownStream 탐지 방식

현재는 다운스트림 서버나 스위치에 DDoS 탐지 시스템이 배치되어 피해자 근처의 탐지 방식

• 문제점 : 공격 트래픽이 탐지기에 도달하기 전에 대응하지 못하고 피해자에게 가는 라우팅 리소스 낭비

Upstream 탐지 방식

ISP 같은 업스트림에서 네트워크의 전반적인 상태를 보는 것이 이상적.

모든 패킷을 기록하는 자세히 기록하는 것 대신 압축된 데이터 구조를 통한 스케치 기반의 측정 방식.

기록한 소형 플로우는 공간 효율적인 비트맵에 큰 플로우는 HyperLogLog 유닛에 기록.

• 문제점

  

  • Packet over-counting :하나의 패킷이 여러 측정 경로를 지나다녀 측정 지점에 여러 번 기록. 중복 계산으로 원래의 플로우보다 더 큰 플로우로 오탐하게 됨.
  • Stage mis-allocating : 각각 측정 지점은 트래픽의 분산된 일부만 관찰하게 되고 큰 플로우를 작은 플로우로 착각하여 작은 플로우처럼 처리할 수 있음. 또한 해당 측정 지점에서 임계점이 낮아서 탐지를 못할 수 있음.

  → 해결하기 위해서는 네트워크 토폴로지와 라우팅에 대한 사전 지식이 필요하지만 라우팅은 동적이기 때문에 사실상 힘듦

• 목표

  1. 라우팅 구애 받지 않는 측정

     중복 계산과 오배치 문제 극복

  2. 자원 효율적

     측정 지점들은 제한된 하드웨어 자원을 가지기 때문에 자원을 효율적으로 사용하는 데이터 구조가 필요

  3. 높은 확장성

     시스템은 측정 작업과 다양한 감지 알고리즘을 유연하게 제공해야 함.

Lemon

각 측정 지점에서 데이터 영역 내에 스케치가 있고 패킷과 플로우들을 기록. 제어 영역에서는 각 측정 지점에서 스케치들을 모아서 전역 Lemon 스케치로 통합하는 방식

Lemon Data Plane

플로우 식별자를 통해 플로우의 볼륨을 얻을 수 있음. 전역적인 일관된 업데이트 연산을 사용하여 라우팅에 구애받지 않음

Lemon Sketch Design

• 3개의 해시 함수

  Hd는 업데이트 될 레이어를 선택. Hs는 업데이트 될 유닛을 선택. Hb는 유닛 내의 비트맵 비트를 업데이트하는 데 사용

• 전역적으로 일관된 업데이트

  모든 측정 지점이 같은 방식으로 데이터를 처리하여 패킷 중복 계산 문제 해결. 같은 해시 함수와 동일한 종류의 키 사용

• 동작 흐름
  1. 패킷 고유키를 Hd 해시 함수에 넣고 결과에 따라 레이어를 선택
     • 이 때 각 레이어의 임계값은 다음과 조건을 만족
     \[T_{i-1} > T_{i} \\T_{i-2} - T_{i-1} > T_{i-1} - T_{i}\]

     낮은 계층일 수록 범위가 더 큼

  2. 정해진 레이어에서 플로우 키를 Hs 해시 함수에 넣고 해시 결과를 유닛 수로 나머지 연산하여 유닛을 결정
  3. 정해진 유닛에서 Hb 해시 함수에 패킷 고유키를 넣어서 비트맵에서 사응하는 비트를 업데이트

• 알고리즘

    Input: Packet with flow key key f low and packet key keypkg
    Output: Updated Lemon sketch
    1 hslot ← Hs(key flow)
    2 hlayer ← Hd(keypkg)
    3 hbitmap ← Hb(keypkg)
    4 for each layer of Lemon sketch layeri do
    5   if hlayer ∈ [Ti,Ti−1) then
    6     indexslot ← hslot % S(s-i)
    7     indexbitmap ← hbitmap % S(b-i)
    8     bitmap ← layeri[index slot]
    9     if bitmap[indexbitmap] == 0 then
    10      bitmap[indexbitmap] ← 1
    11    end
    12   end
    13 end
    14 if hlayer ≤ Th then
    15   index(h-slot) ← hslot % Heavy.size
    16   Heavy[index(h-slot)] ← key f low
    17 end
  

  1~3번째 줄까지 해싱을 다 해놓음

  4~5번째 줄에서 레이어를 찾음

  6번째 줄에서 해당 유닛의 인덱스를 찾고

  7번째 줄에서 해당 비트맵의 인덱스를 찾음. 만약 해당 비트맵의 비트가 0이면 1로 변경함.

  만약에 레이어를 결정하는 해싱 값이 특정 임계값보다 작다면 Heavy 레이어로 가서 해당 플로우 키를 넣음

적응형 측정기 재구성

주어진 플로우에 대해 최적의 레이어를 찾아서 플로우의 추정된 양을 계산하는 과정. 단계 오배치 문제를 해결.

• 동작 흐름
  1. 모든 레이어에서 플로우키와 해당하는 유닛을 검색하고 비트맵을 수집
  2. 바텀업 방식으로 비트맵의 0의 수를 체크. 0의 갯수를 Zi라고하고 임계값을 Tz라고 할 때, 다음 공식을 충족하는 첫번째 비트맵을 찾아냄
  \[Z_{i} \ge T_{z} \cdot S_{i}^{b}\]

  즉, 0이 충분히 많아 비트맵이 포화되지 않아 신뢰성있게 추정할 수 있는 비트맵을 찾아냄

1. 플로우 추정 양을 다음과 같이 계산

\[E = -S_i^b \cdot ln(Z_i/S_i^b) \cdot \frac{H_{d.max}()}{T_{i-1} - T_i}\]

해당 비트맵의 레이어를 추정 레이어, 해당 샘플링 비율을 최적 샘플링 비율이라고 함

만족하는 비트맵이 발견되지 않으면, 최대 추정 범위를 넘어선 것. 더 작은 샘플링 비율을 설정하거나 더 큰 비트맵 크기를 설정하여 피할 수 있음

• 알고리즘

    Input: Flow identifier key flow
    Output: Estimated flow size E and allocated layer L
    1 hslot ← Hs(key flow)
    2 bitmaps ← nlayer size empty list
    3 Tbitmap ← pre-defined threshold
    4 for each layer of Lemon sketch layeri do
    5   if hlayer ∈ [Ti,Ti−1) then
    6     indexslot ← hslot % S(s-i)
    7     bitmaps[i] ← layeri[indexslot ]
    8   end
    9 end
    10 for i = 1 : nlayer do
    11   Zi ← bitmaps[i].Count_0()
    12   if Zi ≥ Tz · S(b-i) then
    13     E ← −S(b-i)·ln(Zi/S(b-i)
    14     E ← E · Hd .max()/(Ti−1−Ti)
    15     L ← i
    16     return E, L
    17   end
    18 end
    19 return overflow
    20 # avoiding by setting large enough bitmap for layern
  

  1~9번재 줄은 플로우 키를 통해서 유닛을 얻음.

  10행은 아래 계층 부터 바텀업

  11행은 각 비트맵의 0의 갯수 Zi를 구함

  12행은 만약 Zi ≥Tz x S(b-i)을 만족하면 플로우 추정량을 계산하고 해당 레이어와 추정량을 리턴

  만약 조건에 비트맵을 발견하지 않는다면 overflow를 리턴

충돌 제거

낮은 레이어에서는 여러 개의 유닛이 높은 레이어에서는 같은 유닛으로 업데이트 될 수 있어 충돌이 발생.

• 동작 흐름
  1. i-1에서는 다른 유닛이 i에서는 같은 유닛으로 충돌.
  • 서로 다른 최적 샘플링 비율을 가지면 제거 가능
  • 위에서는 f1이 더 큰 플로우라고 가정하고 layer i에서 최적 샘플링 비율을 가진다고 가정하고 f2는 layer i-2에서 최적 샘플링 비율을 가짐
    1. f1의 추정값은 f1과 f2의 합. 그렇기 때문에 f1에서 f2를 뺀 값을 통해 오류를 제거. 추정 계층이 같으면 추정 불가하지만 그럴 일은 거의 없음

• 충돌 보정 알고리즘

  

  1~2 : 추정된 양과 할당된 계층을 얻음. 그리고 해당 유닛을 얻음

  3 : f1에 영향을 미쳤을 하위 계층을 탐색

  4 : 하위 계층에 있는 잠재적 충돌 유닛의 인덱스 계산

  5~7 : 만약 하위 계층에서도 같은 유닛이면 패스

  8~9 : 잠재적 충돌 유닛의 비트맵을 가져오고 0의 갯수를 셈

  10 : 비트맵이 충분히 비어 있으면(추정 가능한 상태)

  11 : 오차 계산

  12 : 원래 합에서 오차를 뺌

분석

• 충돌이 발생할 확률

  플로우에서 레이어 i에서 최적 추정 비율을 얻을 확률

  \[Pr_i = \left(1 - \sum_{j=0}^{i-1} Pr_j\right) \cdot \left(1 - \sum_{j=0}^{T_z \cdot S_i^b} \binom{j}{S_i^b} B^j \cdot (1-B)^{S_i^b - j}\right)\] \[B = \left(1 - \frac{1}{S_i^b}\right)^{N \cdot \frac{T_{i-1} - T_i}{H_{d.max}()}}\]

  플로우가 레이어 i에서 추정 결과를 얻기 위해서는 두 조건을 만족해야 함

  1. 해당 계층이 충분히 비어 있어야 함
     • 0이 많아야 함.
     • 레이어 i에 대해 해당 비트맵에서 Ni 번 업데이트 된 후(즉 Ni는 샘플링된 패킷의 수) x 번째 비트가 0일 확률
     \[B = Pr[bitmap[x] = 0] = \left(1 - \frac{1}{S_i^b}\right)^{N_i}\] \[N_i = {N \cdot \frac{T_{i-1} - T_i}{H_{d.max}()}}\]
     • 비트맵 0의 개수. 이항 분포
     \[Pr[Z_i > T_z \cdot S_i^b]= \left( 1 -\sum_{j=0}^{\lfloor T_z \cdot S_i^b \rfloor}\binom{S_i^b}{j}B^j \cdot (1-B)^{S_i^b - j}\right)\]

  2. 하위 레이어가 최적의 샘플링 비율이 아니어야 함.

     \[Pr[\text{not in lower layer}]= \left( 1 -\sum_{j=0}^{i-1} Pr_j\right)\]

  충돌이 발생할 확률

  \[Pr[\text{collision in layer}_i]= 1 - \left( \frac{N_i}{S_i^s} + 1 \right)e^{-\frac{N_i}{S_i^s}}\]

  $N_i$는 계층 i보다 높은 계층에 추정 계층이 있는 플로우의 수. 하위 계층에서 추정된 플로우들의 영향은 계층 i에서 제거될 수 있음. 적절한 매개변수 설정하에, 충돌 비율은 낮은 수준으로 유지될 수 있음. $\frac{N_i}{S_i^s}$이 0.1인경우

• 사례 연구

  

  레이어를 5 계층으로 구성.

  임계값 Ti 16,384, 4,096, 1,024, 256, 0

  유닛 수 $S_i^s$는 524,288, 65,536, 8,192, 2,048, 1,024개

  비트맵 크기 $S_i^b$은 8, 32, 32, 32, 512

  위의 그림을 보면 다양한 크기의 플로우들이 각 계층에 효과적으로 분리

  충돌 확률에 대한 연구

  20만개가 넘는 플로우로 실험

  큰 계층에서 추정되는 플로우 수)는 순서대로 222,470, 6,463, 360, 183, 99개입니다.

  계층의 충돌확률은 각 계층의 충돌 확은 순서대로 7.2%, 0.55%, 0.29%, 0.86%, 0.44%입니다.

  계층 1은 자잘한 트래픽을 처리하는 입구 역할로 이 정도 충돌은 허용 가능.

  계층 1을 제외하고는 1프로 미만이므로 무시할만한 수준.

Lemon Control Plane

Results Collecting and Aggregation

• 동작 흐름
  1. 각 데이터 영역으로부터 Lemon Sketch들을 모음
  2. 같은 레이어와 같은 유닛끼리 비트맵의 OR 연산을 하고 global Lemon Sketch에 배치함
  3. Heavy 해시 테이블에 저장된 플로우 키에 대해서는 전역 스케치에 그대로 저장.

  만약 측정 지점마다 플로우 키가 다른 경우에는 각 측정 지점에서 추정된 값이 더 큰 플로우 키를 통합

Measurement Tasks configuration

제어 영역에서 마스킹 값을 수정하여 플로우 키와 패킷 고유 키의 정의를 커스텀할 수 있음

→ 상황에 맞게 유연하게 제공하여 높은 확장성을 지님

DDoS Detection

Volume-based detection : 비정상적으로 높은 패킷 볼륨에 노출된 DDoS 피해자를 식별. 플로우 키를 dest IP로 패킷 키를 패킷 ID로 설정. 높은 볼륨을 가진 잠재적 피해자를 Heavy 테이블에 저장

Cardinality-based detection : 동일한 dest IP에 컨택하려는 고유한 src IP의 카디널리티가 증가. Lemon은 플로우 키는 dest IP로 패킷 키를 src IP로 , 잠재적 피해자를 Heavy 테이블에 저장.

Entropy-based detection : src 주소의 엔트로피가 증가. 플로우 키는 src IP. 가능한 유닛을 순회 후 후속 조회 연산을 사용. 주소 빈도 분포를 얻어서 엔트로피 계산

이외에도 기존의 매커니즘을 유연하게 지원

DDoS Mitigation

• 네트워크 내부 완화 전략 : rate-limiting, packet drop
• 기존 매커니즘과의 통합
  • 특정 포인트에서 트래픽 클리닝 서비스를 배치. Lemon이 의심스러운 트래픽을 해당 클리닝 서비스로 재라우팅하여 트래픽 정화 수행
  • 이미 발생한 디도스에 대응 매커니즘인 피해자 근처 매커니즘과 결합하여 Lemon을 통해 조기 탐지를 하고 피해자 근처 매커니즘을 미리 실행시켜서 방어하는 전략

Evaluation

• Setup

  프로그래밍 가능한 스위치 하드웨어를 통해 Lemon 프로토타입을 구축. 파이썬을 사용하여 제어 영역 구현

  background 트래픽 : 백그라운드 트래픽 + 디도스 공격을 통해 성능 평가. 리얼 월드 ISP 네트워크로부터 트레이스를 백그라운드 트래픽으로 사용. 에포크당 500만개. 20만 개의 플로우

  디도스 공격 : UDP flooding 공격. 볼륨을 다양하게 변화(전체 트래픽의 0.1%에서 10%). 배경 트래픽에서 무작위로 선택한 동일한 피해자 주소를 대상으로 공격. 공격 트래픽은 무작위 소스.

  genericity 실험에서는 소스 스푸핑이 피해자 탐지에 미치는 영향을 조사하기 위해 공격 출발지 수를 수정. 데스티네이션 스푸핑을 평가하기 위해 단일 IP에서 서브넷으로 수정

  토폴로지와 측정 지점 : 제어 영역이 라우트를 모름. 모든 노드가 측정 지점 역할 수행. 측정 시스템이 라우팅 장치와 통합되기 때문. 디도스 오류가 발생하는 원인을 설명하기 위한 4개의 토폴로지와 실제 ISP 토폴로지(Abilne and CANARIE)

  T1 : 단일 지점. 네트워크에 하나의 측정 지점. 모든 패킷이 딱 한 번 통과

  T2 직렬 지점 : 두개가 직렬. 모든 패킷이 두 지점 모두 통과 (중복 계산 문제)

  T3 : 병렬 지점 : 두개가 병렬. 모든 패킷이 균등하게 통과 (트래픽의 일부만 관찰)

  T4 : 병렬 + 직렬의 3지점

  Abilne : 12개의 측정 지점. 진입 지점을 무작위로 선택후 최대 5홉까지 무작위 전달 (소규모+ 복잡 )

  CANARIE : 28개 측정 지점. 진입 지점. 진입 지점 무작위 선택 후 최대 15홉까지 무작위 전달(대규모 + 더 복잡 )

  평가 지표 : 탐지 성능은 F1 점수. 정확도는 상대 오차 사용

  플로우 별 정확도는 WAPE 사용. (상대 오차는 전체 볼륨)

  비교군

  • Jaqen : UnivMon-based 디도스 탐지 시스템. 볼륨 베이스. Jaqen 측정 결과를 합산해서 네트워크 전반 시야를 확인
  • Couper : 플로우별 카디널리티 추정을 목표로 하는 다단계 시스템. 소형 플로우는 비트맵으로. 큰 플로우는 HyperLogLog로 처리. 실험을 위해 Lemon과 같이 계층 1~5로 설정
  • Lemon : 임계값 16,384, 4,096, 1,024, 256, and 0. 유닛 수 524,288, 65,536, 8,192, 2,048, and 1,024. 비트맵 크기 8, 32, 32, 32, and 512. 플로우 키는 desti IP. 패킷 키는 유니크. 볼륨 기반.
• 디도스 탐지 및 정확성 : 성능에 대한 지표는 F1 점수를 사용. 정확성은 상대 오차 사용. Lemon이 효과적으로 디도스를 탐지하고 정확한 공격 볼륨 추정

  • 전체적인 성능(디도스 볼륨 0.5 초과)

    

  • 공격 볼륨에 대한 성능(디도스 볼륨 0~0.1)

    

  • 공격 볼륨 추정 성능

    

• Address Spoofing 방어 : 카디널리티 기반과 엔트로피 기반 같은 다중 탐지 방법을 통합하여 방어

  • source spoofing : 공격 src를 수정하는 spoofing

    

    100개 이하는 카디널리티가 크게 변하지 않아 탐지를 못하지만 1000개를 초과하면 성능이 좋음.

    엔트로피는 특정 피해자를 식별하지 않고 전체 상태를 반영하여 위장된 IP 주소의 수가 증가하면 엔트로피가 상승하여 탐지

  • destination spoofing : 공격대상을 단일 IP 대신 서브넷에 속한 수많은 IP 주소로 트래픽을 분산하여 전송

    

  플로우 키를 도착지 IP가 아닌 도착지 서브넷으로 변경하여 대응. 서브넷이 확장될 수록 모든 방법의 정확도가 감소하지만 LEMON이 우수함

• 플로우 별 볼륨 추정

  복잡한 플로우 키와 다양한 플로우 크기를 사용하여 복잡도가 증가하고 충돌이 증가함

  

  • 플로우 키 복잡성에 따른 정확도

  

  (a) 복잡한 플로우 키 : five-tuple같이 플로우가 복잡해지면, 네트워크 내 고유 플로우 수 증가 → 충돌 증가 → 오차(WAPE) 발생

  Lemon은 충돌이 증가해도 위 그림처럼 낮은 오차를 보여줌.

  (b) 트래픽 왜곡도 : 플로우의 개수가 250만개. 크기 분포가 편향(소수의 대형 플로우와 다수의 소형 플로우) → 오배치 문제발생 가능성이 높음. 레몬은 가장 낮은 오차를 보여줌. 왜곡도 2.5에서도 성능을 유지

  • 플로우 크기 별 정확도 : 서로 다른 플로우 키 설정하에 플로우 크기별 추정 오차. 중간 크기 에서 couper 대비 현저한 우위

    

  • 메모리 사용량에 따른 정확도 (a) 및 네트워크 크기 별 정확도 (b~d) : 메모리 사용량에 따른 성능 변화. 메모리 사용량이 작을 때, 유닛수 부족으로 WAPE가 최대임. 그래도 지속적으로 더 나음

    

  • 계층별 작업 부하: 하위 계층에서 많은 충돌. (계층 이상에서의 플로우 수/유닛수)상위 계층에서는 최소한의 충돌로 더 큰 플로우를 효과적으로 처리. 배포시에는 하위 계층에 많은 유닛을 추가해야 함

  

• 자원 효율성 : 최소한의 자원 소비만으로 자원 제약 조건 충족

  

  하드웨어 자원 제약 충족. 다른 네트워크 기능들을 위한 충분한 자원이 남아있음

Discussion

• 중복 패킷 탐지 : 공격자가 동일한 패킷 식별자를 가진 중복 패킷을 섞어서 회피하는 경우 CM 스케치를 섞어서 플로우별 패킷 계수를 위해 배포. 자원 사용량을 고려할 때 추가적인 데이터 구조 배포 가능함.

  → 최종 추정 식

  총 패킷 수 / 고유 패킷수 = 평균적으로 몇 번 복제 됐는 지에 대한 비율. 그리고 평균

  \[E'_{net} = \frac{E_{net}}{n} \cdot \sum_{i=1}^{n} \frac{C_i}{E_i}\]

• 기존 매커니즘 강화

  • Patronum : 엔트로피 변화(봇넷으로부터 공격 탐지)와 볼륨 변화(대형 공격자 탐지) 측정.
  • 머신러닝 또는 LLM을 통한 탐지 : 플로우 별 특징 수집

Conclusion

네트워크 전반의 디도스 탐지는 상류에서 탐지하고 완화를 하여 좋음. 기존 방식은 패킷 중복 계산과 처리단계 오배치 문제 발생하지만 Lemon은 라우팅에 구애받지 않고 자원 효율적이며 확장성이 뛰어난 디도스 탐지 제안. 정확한 플로우 별 측정도 가능 .