[review#22] Cost-effective moving target defense against DDoS attacks using trilateral game and multi-objective Markov decision processes_2020

by

1. 서론

MTD 메커니즘의 전략이 방어자에게 최적이 아닐 수 있다고 주장하는데, 그 이유는 어떤 경우에는 방어 비용이 그 유용성을 평가할 때 무시되었기 때문이다.

이전 연구( Zhou et al., 2019 )에서 공격자와 방어자 간의 게임을 모델링하고 게임 프로세스와 게임 보상을 논의하여 방어자가 보호된 시스템에 대한 다양한 MTD 전략의 영향을 분석하도록 안내했다.
다목적 마르코프 결정 프로세스 ( Hahn et al., 2019 )를 활용하여 MTD 셔플링의 효과와 비용 간의 상충 문제를 해결했다.

이 작업은 비용 효율성 균형 문제애 대한 중요한 단계를 나타내지만 몇 가지 제한 사항이 있다.

첫째, Zhou et al. 에서 보여준 것처럼 셔플링 기반 MTD 메커니즘은 합법적 사용자에게 값비싼 오버헤드를 발생시키고 서비스 요청 백로그를 유발할 수 있는데, 이는 이전 연구에서 셔플링 결정과 관련하여 무시되어 왔다.
따라서 사용자는 필연적으로 이 게임의 제3자가 되며, MTD 메커니즘을 구축할 때 이들의 오버헤드를 고려해야 한다.

둘째, 이전 연구에서 두 플레이어의 게임 전략은 사전에 설계되었기 때문에 실제 전략과 일치하지 않을 수 있다. 실제 상황 과 의사 결정에 편향이 발생한다.

셋째, 이전에 제안된 셔플링 알고리즘은 모든 조건을 고려하지 못하며, 부하가 높은 여러 VM에 대해 극단적인 결정을 내릴 수 있다. 이로 인해 해당 사용자들이 공격을 받게 될 수 있다.

본 논문에서는 MTD 셔플링의 비용 효율성 균형을 최적화하기 위해, 합법적 사용자를 게임의 특별 참여자로 참여시킬 수 있는 새로운 삼자 게임 이론을 소개한다.
모든 게임 플레이어의 의사 결정 상황을 정확하게 반영하기 위해 기존 연구의 모든 플레이어에 대한 휴리스틱 전략을 대체하는 휴리스틱 전략을 사용했다. 또한 셔플링 기반 MTD의 효과와 비용의 균형을 이루는 최적의 전략을 찾기 위해 새로운 비용 효율적인 셔플링 알고리즘을 제안했다.

기여
  1. 휴리스틱 전략을 가진 3자 참여자 간의 상호작용을 순차적 게임 으로 모델링한 다음, 마르코프 의사 결정 프로세스 (MOMDP)를 활용한다.
  2. 제안된 방법의 적용성을 높이기 위해 MTD 셔플링 시나리오를 제안하며, 이는 다양한 게임 플레이어의 세부적인 보상을 추가로 분석하고 정량적으로 평가하는 데 도움이 될 수 있다.
  3. 일련의 결정에 대한 최적의 전략을 찾고 MTD의 효과와 비용 간의 균형을 맞추는 동시에 합법적인 사용자의 서비스 접근을 보장하기 위한 새로운 3자 게임 비용 효율적 셔플링 알고리즘(TCS)을 제시한다.
  4. 최신 기법들에 비해 본 제안 방법은 제한된 비용으로 효과적으로 셔플링할 수 있고, DDoS 공격에 대한 저항성도 우수하다.

2절: 위협 모델을 제안
3절: 모델 명세 및 게임에 대한 상세 분석을 제시
4절: 셔플링 시나리오와 알고리즘에 대한 설명
5절: 시뮬레이션 및 실험을 통해 제안하는 방법의 성능 평가
6절: 논문 마무리

2. 연구 관련

2.1. MTD 셔플링 메커니즘

시간이 지남에 따라 네트워크 속성을 동적으로 재구성한다.
기존의 MTD 셔플링 메커니즘은 대부분 방어자의 관점에서 작동한다. 공격자의 행동에 대한 설명이 부족하기 때문에, 공격자에게 대상 네트워크가 불완전한지 또는 노이즈가 많은지 여부를 알 수 없다.

2.2. DDoS 공격에 대한 MTD

MTD 기반 방법은 DDoS 공격에 저항하는 시스템의 능력을 향상시킬 수 있지만 극단적인 경우에는 성능이 약할 수 있지만 오버헤드가 많다.

2.4. 게임 기반 MTD 전략

Feng et al.(2017)은 방어자의 신호 전략을 모델링하는 베이지안 스태켈버그 게임을 통해 방어적 이점을 확립할 수 있음을 이론적으로 증명했다.

2.5. 토론

일부 연구에서 MTD의 효과성을 평가하기 위한 다양한 모델을 제안했지만, 제안된 솔루션의 대부분은 MTD의 방어 비용을 무시한 채 평가에 추상적인 모델을 적용하기 때문에 타당성과 보편성을 충족하지 못한다.
이와는 반대로, 본 연구에서는 특정 셔플링 시나리오를 사용하여 평가 모델을 구축하고 매개변수를 결정함으로써 제안의 효과성과 비용을 정량적으로 평가할 수 있다.

3. 모델 위협

3.1. 공격자 동작

전략적이고 합리적인 공격자는 성공적인 공격을 시작하기 전에 항상 방어자에 대한 몇 가지 민감한 매개변수를 얻어야 한다.
보호되는 시스템에 대한 정보를 얻기 위해 공격자는 시간, 컴퓨팅 및 금전적 리소스를 사용하여 수동적(예: 인터페이스 스니핑) 또는 능동적(예: 호스트 ping)일 수 있는 정찰 작업을 수행할 수 있다.

방어자에 대한 충분한 정보를 얻으면 현재 시스템 상태와 방어 조치에 따라 체계적으로 결정되는 특성을 가진 공격이 시작된다. 탐지 및 공격 시작을 포함한 전체 절차에는 상당한 비용이 발생한다.
예를 들어, DDoS 공격을 시작하는 비용은 이전 IP 주소 스캐닝, 은밀한 포트 스캐닝에 소모된 리소스 및 공격이 발생할 때 사용된 클라이언트 수와 관련이 있다.

3.2. 방어기제

시스템을 해킹이나 파괴로부터 보호하기 위해 방어자는 전체 시스템에 대한 정보와 위험을 초래할 수 있는 의심스러운 정찰 행위를 수집해야 한다. 이동 표적 방어를 사용하여 시스템을 보호할 때, 방어자는 공격 표면을 변경하기 위한 셔플(shuffle)을 수행하고 공격자에 대한 기타 필요한 조치를 취해야 한다. 각 셔플은 사용되는 컴퓨팅 및 네트워크 리소스로 인해 셔플 비용이 발생한다. DDoS 공격 발생은 쉽게 탐지될 수 있으며, 방어자는 매우 짧은 시간 내에 감염된 클라이언트에 대한 정보를 획득할 수 있다고 가정한다. 본 논문에서는 네트워크 수준에서 구현 가능한 셔플 기반 MTD(Multiple Detection) 기술에 중점을 두며, DDoS 탐지 기술은 본 논문의 범위를 벗어난다.

방어 메커니즘의 정의
  • 포트 호핑: 특정 서비스의 포트 번호가 동적이고 지속적으로 변경되는 현상이다.
  • IP 호핑: 방어자는 가상 머신(VM)의 IP 주소를 동적이고 끊임없이 변경한다.
  • 마이그레이션: 방어자는 공격을 받는 애플리케이션이나 서비스를 VM 간에 마이그레이션한다.

3.3. 사용자 행동

셔플 기반 MTD 방식은 네트워크 시스템을 주기적으로 재구성 하거나 손상된 VM을 마이그레이션하는데, 이는 합법적 사용자에게 막대한 비용 부담을 초래하고 서비스 요청 백로그를 유발할 수 있다.
기존의 수동적 방어와는 달리, 빈번한 셔플로 인해 발생하는 오버헤드는 방어자가 셔플링 결정을 내리는 데 상당한 부담을 준다. 또한, 전체 셔플 프로세스 중 높은 서비스 지연 시간이나 중단으로 인해 사용자는 다른 서버를 선택해야 하므로 시스템 과부하가 발생할 수 있다. 따라서 사용자 행동을 고려하는 것이 중요하며, 사용자는 다음과 같은 역량을 갖추고 있다고 가정한다.

  • 사용자는 공격자와 방어자의 행동과 결정을 알 수 없다.
  • 사용자는 방어 기술을 보유하지 않으며 서비스 상태와 시스템 성능 에만 관심이 있다.
  • 서비스 지연이 예상 임계값을 초과하거나 중단이 발생하면 사용자는 다른 것을 선택한다.

3.4. 목표

본 논문의 목적은 삼자간 비용 효율적인 셔플링 MTD 방식에 관한 것으로, 사이버 방어자가 방어자, 공격자, 사용자 등 세 당사자 간의 셔플링/공격 비용, 효과성, 그리고 서비스 오버헤드를 고려하여 최적의 의사결정 방식을 모색하는 것이다.

본 논문에서는 셔플링 의사결정을 내리는 가장 좋은 방법은 무엇이며, 비용과 효과성 간의 최적의 균형을 찾는 방법을 모색하고자 한다.

4. MTD 게임 모델

필수적인 MTD 문제 중 하나는 적응 선택 문제, 즉 “적응 방법”이다. 그러나 많은 MTD의 주요 단점은 보호 시스템의 효과성을 개선하는 적응만을 추구한다는 점이다.
이 순차적 게임 에서 방어자는 네트워크를 통해 리소스를 이동시켜 공격자가 리소스의 실제 위치를 파악하기 어렵게 하는 MTD 전략을 채택한다.
반면 공격자는 네트워크 트래픽을 모니터링하여 방어자의 행동을 관찰할 수 있다. 이 전략을 알고 있지만 구현 방식은 모르는 공격자는 어떤 VM에 DDoS 공격을 수행할지, 어떤 IP 주소를 선택할지 결정한다.

Definition 1: 시스템 상태 S
  • S는 보호 시스템이 경험할 수 있는 모든 가능한 공격 표면을 포함하는 유한한 상태 집합이다.
  • St(v): 시간 t에서 특정 VM v의 상태를 나타낸다.
    • St(v) = 0: VM이 안전한 상태
    • St(v) = 1: VM이 DDoS 공격을 받고 있는 상태
Definition 2: 공격자의 관찰 O
  • O는 공격자가 관찰한 보호 시스템의 상태를 나타낸다.
  • Ot(v): 시간 t에서 공격자가 관찰한 VM v의 상태를 나타낸다.
    • Ot(v)는 St(v)와 동일한 값을 가질 수 있지만, 공격자는 전체 VM을 한 번에 탐색할 수 없으므로 Ot는 St의 부분 집합이다.
Definition 3: 행동 집합 A
  • 게임에서 모든 플레이어가 자신의 보상을 극대화하기 위해 취해야 하는 유한한 행동 집합이다.
  • <A, D, U, t>로 구성되며, 각각 공격자, 방어자, 사용자 행동과 시간 단계 t를 나타낸다.
    • At(v): 시간 t에서 공격자 VM v에 대해 수행하는 행동 집합 (예: 스니핑, 스캐닝, 공격)
    • Dt(v): 시간 t에서 방어자 VM v에 대해 수행하는 행동 집합
    • Ut(v): 시간 t에서 사용자가 VM v에 대해 수행하는 행동 집합
Definition 4: 효과 함수 E
  • \(f_E^{A/D/U}(v)\): 플레이어가 VM v에 대해 특정 행동을 취했을 때 얻을 수 있는 효과 값을 결정하는 함수이다.
  • \(f_E^{A/D/U}(v): S \times A/D/U \times S \rightarrow E\)
  • E는 행동 전후의 VM 상태와 플레이어의 행동에 따라 달라진다.
Definition 5: 비용 함수 C
  • \(f_C^{A/D/U}(v)\):플레이어가 VM v에 대해 특정 행동을 취했을 때 발생하는 비용을 나타내는 함수이다.
  • \(f_E^{A/D/U}(v): A/D/U \rightarrow C\)
  • C는 플레이어의 행동에 따라 달라지며, 각 플레이어(A/D/U)에 대해 별도로 정의된다.

4.1. Game process

게임이 시작될 때, 시스템 상태 \(S_0\), 공격자 행동 \(A_0\), 방어자 행동 \(D_0\), 사용자 행동 \(U_0\)은 모두 비어 있는 상태로 초기화된다.
초기에는 아무런 행동도 하지 않았고, VM의 상태도 설정되지 않았기 때문에 모든 값은 공집합(∅)으로 시작한다.

방어자는 매 시점에서 전체 시스템 상태를 완전히 파악할 수 있는 반면, 공격자는 관측을 통해 일부 상태 \(O_t\)만 파악할 수 있다.
방어자는 ‘전체 그림’을 보지만, 공격자는 ‘부분적으로만’ 보면서 공격 판단을 해야 한다. 따라서 초기 공격자의 관측값도 공집합(\(O_0 = \emptyset\))으로 설정된다.

각 시간 단위 t+1에서, 공격자는 임의의 VM v를 선택하여 성공 확률 p(v)로 DDoS 공격을 시도할 수 있다.
동시에 방어자는 어떤 VM을 셔플링할지 결정하여 공격자의 확산을 막으려 하며, 이 과정에서 사용자들은 서비스 지연을 겪을 수 있다.

게임은 시간 단위로 다음과 같은 순서로 진행된다.

(1) 방어자는 시스템 전체 상태 \(S_t\)를 보고, 공격자는 일부 상태 \(O_t\)만 관측한다.
(2) 방어자와 공격자는 각각 전략에 따라 행동 \(A_{t+1}, D_{t+1}\)을 선택한다.
(3) 사용자는 방어자와 공격자의 행동이 적용된 이후, 서비스 품질을 보고 \(U_{t+1}\) 행동 (예: 다른 VM으로 이동)을 취한다.
(4) 시스템은 Algorithm 1의 상태 전이 함수에 따라 \(S_{t+1}\) 상태로 이동한다.
(5) 각 참여자는 해당 시간 단위에서의 보상과 비용을 계산한다. 단, 사용자는 보상을 갖지 않는다.
(6) 게임은 \(t=T\)에 도달할 때까지 다음 시간 단계로 계속 진행된다.

if O_t(v) ⊆ S_t(v) = 0 then
    A_{t+1}(v) ← 1

Line 1-2: 공격자가 관측한 VM에 공격을 시도함 (공격자는 v를 안전한 VM으로 인식하고 있기 때문에)

if v ∈ D_{t+1}(v) ∩ v ∉ U_{t+1}(v) then
    S_{t+1}(v) ← 0

Line 3-4: 방어자가 해당 VM을 셔플링했고 사용자는 그 VM을 떠나지 않았다면, 성공적인 방어로 간주 (→ 상태는 안전(0))

else
    with probability p(v), S_{t+1}(v) ← 1
    with probability p(v′), S_{t+1}(v′) ← 1

Line 5-7: 셔플링이 실패하거나 늦으면 VM이 손상되거나(공격이 성공하거나) 인접한 VM으로 공격이 퍼질 수도 있음 (→ 확률적으로 손상)

S_{t+1}(v) ← S_t(v)
if v ∈ D_{t+1}(v) ∩ v ∈ A_{t+1}(v) ∩ v ∉ U_{t+1}(v) then
    S_{t+1}(v) ← 0

Line 10-12: 공격자가 관측하지 못했거나 이미 손상된 경우 상태가 유지됨 (→ 성공적 방어)

if v ∉ D_{t+1}(v) ∩ v ∈ A_{t+1}(v) then
    with probability p(v), S_{t+1}(v) ← 1

Line 14-15: 방어자가 셔플링하지 않으면 위험 상태로 전이됨 (방어하지 않았는데 공격자가 행동하여, 확률적으로 공격 성공)

else
    for v ∉ D_{t+1}(v) ∩ v ∉ A_{t+1}(v) do
        with probability p(v′, v), S_{t+1}(v) ← 1

Line 16-18: 공격과 무관한 VM도, 인접 VM으로부터 감염될 수 있음

with probability p(v′), S_{t+1}(v′) ← 1

Line 21: 인접 VM v’도 감염될 수 있음

return S_{t+1} with probability distribution p

Line 24: 모든 VM의 상태 정보를 포함한 확률 분포 형태로 S_{t+1}을 반환

정리
상황결과
공격자가 감시하지 않음공격 시도
방어자 셔플 & 사용자 남아 있음성공적 방어 → 안전 상태
방어 안함 + 공격감염 확률 ↑
아무도 신경 안 씀주변에서 감염될 가능성 존재

→ 이 알고리즘은 각 시간 t+1에서 누가 어떤 행동을 했는지에 따라, 각 VM이 감염되는지, 안전한지, 감염이 전파되는지를 확률적으로 결정하는 함수이다. 삼자 상호작용을 세밀하게 반영한 게 이 논문의 핵심 강점이다.

4.2. Game payoff

시스템 상태 \(S_t\): 시간 t에서 전체 VM의 상태
게임 히스토리 \(H_t\): 시간 0부터 t까지의 상태와 행동 순서 기록

\(H_t = \{(S_0, A_0), (S_1, A_1), …, (S_t, A_t)\}\)

보상 함수의 정의

각 참여자는 다음과 같은 구조로 payoff를 계산함:

\(P^D_{t+1} = E^D(H_{t+1}) – C^D(H_{t+1})\)

\(E^D\): 방어 효과 (DDoS 차단, 시스템 보호 등), \(C^D\): 셔플링 비용 (VM 마이그레이션, 리소스 사용 등)

\(P^A_{t+1} = E^A(H_{t+1}) – C^A(H_{t+1})\)

\(E^A\): 공격 성공 효과 (VM 손상 등), \(C^A\): 공격 수행 비용 (리소스, 시간 등)

\(P^U_{t+1} = -C^U(H_{t+1})\)

사용자는 보상을 받지 않음, 셔플링에 의한 피해(QoS 저하)만 받음, 따라서 항상 음수 payoff

4.3. Game strategy

게임 참여자들의 전략은, 현재 시점과 게임 이력 \(H_t\)에 따라 어떤 VM에서 어떤 행동을 언제 실행할지 결정하는 정책이다.
단일한 행동 유형만 고려하더라도 가능한 전략 공간은 매우 방대하다. 이러한 전략 공간을 직접 탐색하지 않고 게임 과정을 보다 정밀하게 분석하기 위해, ‘시간에 따른 규칙적 구조와 행동 패턴으로 정의되는 휴리스틱 전략(heuristic strategies)’에 집중한다.

게임 과정에서 모든 참여자들의 행동을 체계적으로 기술한다. MTD에서 휴리스틱 전략은 일반적으로 다음 세 가지 유형으로 나뉜다:
시간 기반(time-based), 사건 기반(event-based), 보상 기반(payoff-based)

* 휴리스틱 전략: 불충분한 시간이나 정보로 인하여 합리적인 판단을 할 수 없거나, 체계적이면서 합리적인 판단이 굳이 필요하지 않은 상황에서 사람들이 빠르게 사용할 수 있게 보다 용이하게 구성된 간편추론의 방법
– ‘논리적 추론’이 아닌 ‘직관적 판단’

시간 기반 (Time-based strategies)

특정 시간 간격에 따라 결정론적으로 실행되거나, 갱신 프로세스(renewal process)에 따라 확률적으로 실행된다.
예를 들어, 공격자는 정기적으로 공격 표면을 스캔하거나 탐색하여 대상 시스템에 대한 중요한 정보를 획득할 수 있다.

사건 기반 전략 (Event-based strategies)

단일 VM에 대한 관측, 혹은 시스템 전체의 여러 관측값 조합을 기반으로 특정 행동을 유발한다.
예를 들어, 사용자가 사용하던 VM 서비스 중단을 경험했을 경우, 다른 VM으로 이동을 선택할 수 있다.

보상 기반 전략 (Payoff-based strategies)

보상 기반 전략은 방어자와 공격자 사이에서만 존재하며, 주로 현재 시간 단계의 마지막에서 실행된다.
방어자와 공격자는 해당 시간 동안의 행동 보상(payoff)을 평가하고, 다음 시간 단계에서 어떤 VM을 셔플하거나 공격할지 결정하게 된다.

→ 전략 선택의 초점: 세 참여자 간 상호작용이 복잡하므로, ‘방어자와 공격자의 휴리스틱 전략 선택을 설명하기 위해 보상 기반 전략(payoff-based strategies)’에 집중한다.

일반 사용자는 payoff 자체에 관심을 두지 않고, 서비스 지연이나 중단과 같은 돌발 상황에 반응하여 행동을 취하는 경향이 있다.
따라서 실제 상황에 부합하도록, 사용자의 행동은 사건 기반 휴리스틱 전략(event-based heuristic strategy)을 통해 설명하는 것이 적절하다.

4.3.1. Attacker strategy

보상 기반 선택 전략(payoff-based selection strategy)으로 정의되는 두 가지 형태의 휴리스틱 공격자 전략을 고려한다.
공격자는 시간 단계 t+1에서 관측 정보 \(O_t\)를 기반으로, 시스템 상태를 변화시킬 수 있는 VM \(v \in V\)만을 고려하여 공격 대상을 선택해야 한다.

공격자는 초기 시스템 상태 \(S_0\)만 알고 있으며, 모든 VM \(v \in V\)에 대해 \(O_0(v) = S_0(v) = 0\)으로 설정된다. 따라 서 시간 t+1에서의 잠재적 공격 대상은 \(\alpha(O_t)\)으로 표현된다.

(1) VM v를 직접 공격 대상으로 지정하는 경우
(2) 다른 VM v’를 공격하여, 확률적으로 VM v에 영향을 주는 경우

\(\alpha(O_t) = \{v \in V \mid O_t(v) = 0\} \cup \{v{\prime} \in V \mid O_t(v{\prime}) = 0, \, p(v{\prime}, v) > 0\} \tag{2}\)

보상 기반 게임 전략의 핵심 아이디어는, 각 시간 단계에서 이전 시스템 상태를 바탕으로 공격자의 잠재적 보상을 극대화할 수 있는 대상 VM을 선택하는 것이다.
그러나, 이 시간 단계에서 방어자의 행동을 알 수 없기 때문에, 공격자가 계산하는 잠재적 보상은 공격자의 일방적인 정보에 기초한 편향된 추정값이 된다.

4.3.2. Defender strategy

보상 기반 전략들 중에서도, VM을 선택하기 위한 두 가지 기준을 탐색한다.
방어자는 매 시간 단계마다 실제 시스템 상태를 완벽히 파악할 수 없기 때문에, 방어 행동을 취하기 전에 관측 정보를 바탕으로 가능한 시스템 상태를 추론하는 것이 중요하다.

방어자는 자신의 관측값뿐만 아니라,공격자의 전략에 대한 가정도 고려하여 현재 시스템 상태에 대한 이해를 형성해야 한다. 이와 유사하게, 우리는 시간 t+1에서의 잠재적 방어 대상을 \(\beta(S_t)\)로 정의하며, 이는 다음과 같은 두 부분으로 구성된다:

(1) 방어자가 관측한 시스템 상태 \(S_t\)에 따라, 직접 방어할 VM v
(2) 이전 시간 단계에서 셔플링하지 않았던 VM v

위의 분석을 바탕으로, \(\beta(S_t)\)는 다음과 같이 정의된다:

\(\beta(S_t) = \{v \in V \mid S_t(v) = 1\} \cup \{v \in V \mid S_t(v) = 0 \land v \notin D_t(v)\} \tag{3}\)

방어자가 결정을 내리기 전에, 합리적인 방어자는 다가오는 행동에 대해 게임 보상(game payoff)을 잠재적으로 평가할 필요가 있다. 방어자의 입장에서 이 보상에 대한 잠재적 평가(potential assessment)는 다음 시간 단계에서 공격자의 악의적인 행동에 얼마나 잘 대응할 수 있는지를 나타내는 전략의 품질을 의미한다.

→ 방어자의 시각에서 볼 때, 이 잠재적 보상의 값이 높을수록 해당 방어 전략의 효과가 높다고 간주할 수 있다.

4.3.3. User strategy

삼자 게임의 특별 참여자로, 일반 사용자는 시스템에 접속할 때의 서비스 성능과 품질을 기준으로 행동을 유도하는 전략을 선택하는 것으로 간주된다.
사용자는 공격자나 방어자의 행동이나 결정을 알 수 없으며, 오직 서비스 상태와 시스템 성능만에 주의를 기울인다.

방어자와 공격자가 보상 기반의 휴리스틱 전략을 선택하는 것과 달리, 사용자는 자신의 payoff를 평가해서 행동을 결정하지 않으며, 시스템 이벤트로 인한 성능 변화에 따라 반응적으로 행동을 취한다.

사용자가 서비스 품질 및 성능 요소에 더 민감하게 반응한다는 점을 고려하여, 우리는 시간 t에서 사용자의 행동을 나타내는 두 가지 휴리스틱 전략 유형을 \(\delta(S_t)\)로 정의한다:

(1) 현재 VM v가 사용자의 요구 서비스를 계속 제공하는 경우 → 해당 VM에 연결 유지
(2) 동일한 서비스를 제공하는 다른 온라인 VM v′로 이동

\(\delta(S_t) = \begin{cases} \delta(S_{t-1}), & \text{if } 0 \leq t_t < T \\
v^{\prime} \in V \setminus \delta(S_{t-1}), & \text{그 외 경우} \end{cases} \tag{4}\)

\(t_t\)는 해당 시간 단계 t에서 공격자와 방어자로 인해 발생한 서비스 지연(time overhead)을 의미하고,
T는 일반 사용자가 시스템 서비스에서 감내할 수 있는 지연 한계(threshold)를 뜻한다.

사건 기반 전략(event-based strategies)은 특정 이벤트의 발생에 따라 사용자가 결정을 내리는 것을 요구하므로, 사용자는 각 시간 단계의 마지막에 전략을 선택한다. 즉, 다른 두 참여자(공격자, 방어자)의 행동이 모두 끝난 후에 사용자가 자신의 행동을 취하게 되는 것이다.
시스템 서비스가 양호한 상태로 유지되는 경우, 사용자는 현재 연결을 유지한다.
그러나 서비스 지연이 심하거나 시스템이 중단된 경우, 사용자는 현재 연결을 끊고 자발적으로 다른 VM에 접속하는 행동을 취한다.

5. Trilateral game cost-effective shuffling method

정의한 게임 모델의 진행 과정과 전략들이, 방어자에게 바람직하지 않은 균형 상태에 도달할 수 있다.

따라서 본 연구에서는, 방어자와 사용자에게 더 유리한 결과를 도출하고, 셔플링 비용과 방어 효과 간의 최적 균형점을 달성하기 위해,
위협 모델(threat model)과 게임 이론(game theory)을 결합하여
상황에 따라 서로 다른 셔플링 유형을 채택하는 삼자 게임 기반 비용 효율적인 셔플링 방법(trilateral game cost-effective shuffling method)을 제안한다.

5.1. MTD shuffling scenario

기존의 정적 방어(static defense) 시나리오와 달리, MTD 환경에서는 서비스나 VM이 DDoS 공격을 받을 경우, 방어자가 사용 중인 포트, IP, 혹은 VM 자체를 여분의 자원을 통해 제어하고 재배치한다.
하지만 여러 번의 셔플링 수행 과정에서는 네트워크 자원 소모, 서비스 지연 증가 등 추가적인 오버헤드가 발생하게 된다.

따라서 우리의 목표는, MTD 기반 셔플링 기법을 최적으로 구현함으로써,
방어 효과를 극대화하고, 사용자에게 발생하는 오버헤드를 최소화하며, 동시에 공격자의 보상(payoff)을 제한하는 것이다.

Given:
사용자 집합: q명
온라인 VM: n개
네트워크 세그먼트: r개 (VM들이 연결되어 있는 네트워크 공간 또는 논리적 영역)
포트 수: u개
각 VM은 동일 자원을 가진 사용자 m명을 수용 가능
전체 사용자 수는 m x n = q

Output:
IP 셔플링 행렬: \(X_0, X_1, …, X_T, where X_t \in \{0,1\}^{r \times n}\)
포트 셔플링 행렬: \(Y_0, Y_1, …, Y_T, where Y_t \in \{0,1\}^{u \times n}\)
VM 마이그레이션 행렬: \(Z_0, Z_1, …, Z_T, where Z_t \in \{0,1\}^{q \times n}\)

IP 셔플링 관련:

  • (5a): \(\sum_{i=1}^{n} x_{ij} = 1 \quad \text{for } j = 1,…,r\) → 각 네트워크 세그먼트(j)는 최소 하나의 VM을 소유해야 한다
  • (5b): \(\sum_{j=1}^{r} x_{ij} = 1 \quad \text{for } i = 1,…,n\) → 각 VM(i)은 정확히 하나의 네트워크 세그먼트에 할당되어야 한다

same as 포트 셔플링, VM 마이그레이션

포트 셔플링: 최대 n개의 VM이 동일한 포트 번호를 공유할 수 있음
VM 마이그레이션 관련: 각 사용자는 정확히 하나의 VM에 할당되어야 한다, 각 VM은 정확히 m명의 사용자를 수용해야 한다

5.2. MTD shuffling objectives

방어자 payoff 극대화

MTD(이동표적 방어)의 목표는 최소한의 방어 비용으로 VM이 손상되는 수를 제한하는 것이다. 이를 위해 우리는 시간 구간 T 내에서 셔플링의 payoff 값을 매 시간 단계의 효과와 비용의 차이에 할인 계수 \(\gamma^t\)를 곱하여 정량화한다. 이 할인 계수는 시간이 지남에 따라 방어자의 보상이 점차 감소하도록 반영해준다.

공격자 payoff 최소화

MTD 셔플링은 공격자가 성공적인 공격을 수행하는 것을 더욱 어렵게 만들어 공격 비용을 증가시켜 포기하도록 유도한다. 이를 위해 공격자의 payoff를 게임 이력과 할인 계수를 이용해 정량화하고, 최소화 목적 함수를 정의한다.

사용자 비용 최소화

일반 사용자들은 직접적으로 게임에 참여하지 않지만, 공격으로 인한 VM 손상 또는 방어자의 셔플링으로 인해 서비스 이용이 일시적으로 제한될 수 있다.

  • 공격 → 서비스 불안정
  • 셔플링 → 일시적 서비스 중단
  • 서비스 지연이 임계치를 넘으면 → 사용자는 다른 VM에 접속하기도 함

5.3. Decision problem modeling

마르코프 결정 프로세스(MDP, Markov Decision Process)는 성능 분석과 시스템 최적화를 위한 대표적인 모델로,
환경 내에서 의사결정 주체(agent)의 행동을 기반으로 추론할 수 있는 이론적 프레임워크를 제공한다.

그동안 이 분야에 대해 많은 연구가 이루어졌지만, 실제 세계의 다양한 순차적 의사결정 문제들에 대해 MDP만으로는 충분하지 않은 경우가 많다.
그 가장 큰 이유 중 하나는, 실제 상황에서는 하나의 목적만이 아니라 여러 목적(objectives)이 동시에 존재하며, 이는 인간의 행동 선택이 복수의 동기에 의해 결정되기 때문이다.
예를 들어, 컴퓨터 네트워크에서 우리는 성능을 극대화하면서도 동시에 전력 소비를 최소화하고자 할 수 있다 (Roijers and Whiteson, 2017).

이러한 다목적 의사결정 문제(Multi-Objective Decision Making)를 공식화하고 해결하기 위해,
우리는 본 논문에서 Multi-Objective Markov Decision Process (MOMDP)를 활용하여 의사결정 문제를 모델링한다.

MOMDP 모델 정의

목적: 방어자의 보상 최대화, 사용자의 오버헤드 최소화, 공격자의 보상 최소화
구성요소: 6개의 구성요소로 이루어진 튜플 \((S, X, \pi, p, R, \gamma)\)

제약 조건

모든 게임 참여자의 전략은 휴리스틱 전략을 따름

5.4. Trilateral game cost-effective shuffling algorithm

Value Iteration은 구현이 간단하다는 장점이 있지만, 일부 경우에서는 수렴 속도가 느릴 수 있다.
이를 해결하기 위해 우리는 셔플링 효율을 높이고 계산 속도를 향상시키고자,
방어자의 보상 최대화, 사용자의 오버헤드 최소화, 공격자의 보상 최소화라는 세 가지 목적을 고려하여 새로운 삼자 게임 기반 비용 효율적인 셔플링 알고리즘(TCS)을 제안한다.

초기 단계

초기 할당 단계에서, 셔플링 시나리오 내에서 q명의 사용자, r개의 네트워크 세그먼트, u개의 포트가 n개의 온라인 VM에 무작위로 할당된다.
이후 t번째 셔플링 단계에서는 손상된 VM의 수를 반복적으로 줄이는 방식으로 셔플링이 진행된다.
시간 t에서의 시스템 상태는 사용자, 네트워크 세그먼트, 포트의 할당 상태 및 손상된 VM 여부를 상태 전이 함수(STF, Algorithm 1)를 통해 나타낸다.

TCS는 초기 할당 이후 각 시간 단계에서 실행되며, 불필요한 비용을 줄이도록 설계되었다.

  • \(S_t(v_i)\): 시간 t의 각 VM \(v_i\)의 상태 (1 = 감염됨, 0 = 안전)
  • \(X_t, Y_t, Z_t\): 각각 IP, 포트, 사용자 할당을 나타내는 이진 행렬
  • \(\eta_t(v_i)\): VM \(v_i\)에 접속 중인 사용자 수
  • Output \(X_{t+1}, Y_{t+1}, Z_{t+1}\): 다음 시간 단계의 셔플링 결과
for S_t(v_i) = 1, 1 ≤ i ≤ n do:

Line 1: 현재 시스템 상태를 기반으로 손상된 VM을 전체적으로 파악

if η_t(v_i) = 0:
    Set x = 0, y = 0, z = 0

Line 2–3: 감염됐지만 해당 VM에 접속 중인 사용자가 없으면 해당 VM에 대해 셔플링 생략

if 0 < η_t(v_i) ≤ ⌊m/2⌋:
    Randomly set x, y

Line 5-6: 접속 사용자 수가 절반 이하일 경우, 다음 시간에 사용할 새로운 IP 및 포트를 무작위로 설정

if ∃ 0 < η_t(v_i′) ≤ ⌊m/2⌋ and S_t(v_i′) = 0:
    Set z ← η_t(v_i)

Line 7-8: 셔플링 기준이 되는 임계값 설정 (보안된 다른 VM이 수용 가능하면 그쪽으로 사용자 마이그레이션)

else:
    for i′ s.t. S_t(v_i′) = 0:
        분산 재배치 수행

Line 9–10: 대상 VM에 수용 공간이 부족할 경우 → 여러 VM으로 분산 재배치

else:
    Set x ∩ x_t = 0, y ∩ y_t = 0, z = z_t

Line 14-15: 사용자가 과반 이상 접속된 경우 → VM 이동 대신 IP 및 포트만 완전히 변경

return 모든 xt+1, yt+1, zt+1

Line 19: 다음 시간 단계에서의 전체 셔플링 결과 반환

정리
감염됨 & 사용자 없음아무 셔플링 안 함
감염됨 & 사용자 수 ≤ 절반
→ 수용 가능한 보안 VM 있으면 이동
→ 없으면 분산 이동
감염됨 & 사용자 수 > 절반IP/포트만 변경, VM은 유지

6. Evaluations and results

시뮬레이션 및 실험을 통해 제안된 TCS 알고리즘의 DDoS 공격에 대한 효과와 비용을 평가하고 분석한다.

6.1. Simulation

SDN (소프트웨어 정의 네트워크)
– 제어 평면(control plane), 데이터 평면(data plane) 분리 → MTD 구현 유연함

가상 네트워크 시뮬레이션: Mininet 사용 (OpenFlow 스위치와 호스트 생성)
중앙 컨트롤러: OpenDaylight 사용
하드웨어 사양: 3.6GHz Intel Core CPU, 32GB RAM, Ubuntu 16.04 (64-bit)

알고리즘 비교 대상

  • TCS (제안): 다중 목적(MOMDP), 사용자 행동 포함
  • RRT (2016): Renewal Reward Theory 기반, 사용자 고려 안함(VM의 온라인 사용자 수에 무관)
  • CSA (2017): Cost-effective Shuffling Algorithm, 사용자 절반만 이주(한 번의 셔플로 마이그레이션할 사용자의 절반을 무작위로 선택함)
  • CES (2019): Cost-effective Shuffling Method, 사용자 수를 고려하지만 개별 보상을 계산하지 않고 방어 보상에 합침(온라인 사용자 수에 주목하지만, 사용자 보수를 별도로 계산하지 않음)

RRT(Renewal Reward Theory)( Wang et al., 2016 ),
CSA(Cost-effective Shuffling Algorithm)( Lin et al., 2017 ),
CES(Cost-Effective Shuffling Method)( Zhou et al., 2019 )

m=20, n=50, q=1000, r=20, u=100

세 가지 방어 메커니즘의 총 비용은 1로 설정하고, IP 호핑, 포트 호핑, 마이그레이션 셔플링에 대한 가중치 설정

셔플링 유형별 가중치: IP: 0.2, port: 0.1, migration: 0.7
플레이어별 가중치: 방어자: 0.6, 공격자: 0.3, 사용자: 0.1
성공 시 보상: 1
할인율 γ: 0.9 (미래 보상의 현재 가치 감소 반영)
평균 오버헤드: \(t_d, t_a, t_u\) 각 1.5, 2, 1 (각 참여자의 행동 비용)

TCS만 사용자 전략을 고려하고, RRT, CSA, CES는 사용자 전략이 없어 \(t_u = 0\)으로 설정

RRT, CSA, CES 비교 분석

Fig 1: 시간 증가에 따른 성능 변화
설정: 각 VM에 초기 10명의 사용자, 최대 50개의 VM 셔플링 가능
축: x축 = 시간(step), y축 = 방어자/공격자/사용자 보상(payoff)

  • Fig 1(a): 방어자 보상
    초기에 시간 증가 → 방어 보상 증가, 하지만 4~5 스텝 이후 감소
    셔플링 비용은 계속 발생하지만, 시스템은 이미 완성된 상태이므로 효과는 줄어듦
  • Fig 1(b): 공격자 보상
    게임 초반: 공격 보상 증가
    셔플링이 활성화되면 급격히 하락
  • Fig 1(c): 사용자 보상
    시간 흐름에 따라 계속 감소 → 셔플링과 공격 때문에 서비스 품질 저하
    최종적으로 안정된 보상값으로 수렴

Fig 2: 사용자 수 증가에 따른 성능 변화
설정: 10번째 시간 스텝에서 각 VM에 0~20명의 사용자 할당

  • Fig 2(a): 방어자 보상
    사용자 수 증가 → 방어자 보상이 선형 증가하지 않음
    이유: 사용자 수가 많을수록 재배치가 어려움
  • Fig 2(b): 공격자 보상
    사용자 수 증가 → 공격자 보상 선형 증가
    이유: 사용자 많을수록 공격 효과가 커짐
  • Fig 2(c): 사용자 보상
    사용자 수 많을수록 서비스 지연 및 불안정 → 피해 증가
    거의 선형적으로 하락, 하지만 TCS는 셔플링으로 인한 사용자 피해까지 고려하므로, 다른 기법보다 나음

→ TCS의 성능이 뛰어난 이유

  1. 정교한 상태 전이 모델링
    TCS는 상태 간 상관관계를 고려한 확률 기반 전이, RRT/CSA는 구체적 전이 설명 없음, CES는 보안 자원만 고려함
  2. 3종 셔플링 전략 사용
    TCS는 IP hopping, Port hopping, Migration 모두 사용, RRT/CSA는 Migration만 사용
  3. 사용자 고려 포함
    TCS는 삼자 게임 모델로 사용자 전략까지 포함, 다른 방법들은 사용자 보상/오버헤드를 고려하지 않음

→ TCS는 시간에 따라 안정적이고, 사용자 수가 많을수록도 더 강력한 셔플링 효과를 보인다.
방어자 보상을 극대화하면서, 공격자 보상을 최소화하고, 사용자 피해까지 통제할 수 있는 비용 효율적 MTD 전략으로 유의미한 성능 우위를 가진다.

6.2. Experimental settings

제안된 TCS 알고리즘을 실제 SDN 기반 네트워크 환경에서 구현 및 평가

하드웨어 구성

장비: Dell PowerEdge R720 / 수량: 5대 / 사양: 32GB RAM, 4TB HDD, 12-core CPU
– 가상 네트워크 서버: VM 실행 및 네트워크 구성 (OpenStack 기반)
장비: Dell PowerEdge R430 / 수량: 1대 / 사양: 16GB RAM, 1TB HDD, 4-core CPU
– 컨트롤 서버: ODL 컨트롤러 + Laravel 웹 프론트엔드

총 6대 서버로 테스트베드 구성

소프트웨어 구성

OpenDayLight (ODL): 오픈소스 SDN 컨트롤러. 셔플링 규칙 설치, TCS 알고리즘 모듈 포함
PHP Laravel: 사용자 인터페이스 구현용 프론트엔드 프레임워크
OpenStack: 클라우드 자원 오케스트레이션 (VM 생성, 네트워크 설정 등)
Open vSwitch (OVS): 각 VM을 제어하는 가상 스위치, SDN 컨트롤러와 연동됨

가상 네트워크 구성
  • VM 수: 총 50개
  • 할당 구조: 5개 서버에 각각 10개 VM씩 배치
  • 사용자 수: 각 VM당 최대 20명 할당
  • 자원 배분: 모든 VM에 동일한 CPU/RAM 자원
  • IP/포트 다양성: 각 VM은 고유한 IP와 포트를 가짐
공격자와 방어자 구성

공격자: DDoS 공격 도구로 VM에 과부하 공격 수행
방어자: 필요 시 각 VM에 대해 복제본(replica) 생성 가능

→ 단순 시뮬레이션이 아니라, 실제 분산 서버와 SDN 아키텍처 상에서 TCS가 작동함을 보여주는 실험

6.3. Results

Static strategy (정적 전략), Deterministic pure strategy (결정론적 순수 전략), Random strategy (랜덤 전략)

–

TCS 알고리즘 한계 (Limitations of TCS)
  1. 중앙 집중형 SDN 아키텍처: TCS는 단일 SDN 컨트롤러 기반임
    – 대규모 네트워크나 분산 환경에서의 확장성과 장애 복원력 부족
    – SPOF (Single Point of Failure) 문제
  2. 공격자 모델의 단순화
    공격자가 정해진 확률로 공격에 성공하는 모델을 사용함
    – 적응형 공격자, 지능형 DDoS, 우회 전략은 고려되지 않음
  3. 사용자 모델의 정태성
    – 사용자는 수동적으로 피해만 입는 객체로 모델링됨
    – 실제로는 사용자도 동적으로 행동하고, QoS 기반 이탈/재접속 등의 전략적 반응이 존재함
  4. 리소스 최적화 부족
    – 셔플링할 때 VM 복제만 고려됨
    – CPU, 메모리, 네트워크 대역폭 등 멀티 리소스 최적화가 부족함
  5. 실시간성 미흡
    – 상태 전이와 셔플링 결정이 선계산된 확률 모델 기반
    – 실시간으로 동적으로 적응하는 온라인 강화학습 기반 셔플링이 아님
Future Developments

다중 컨트롤러 SDN(Multi-Controller SDN) 환경으로 확장

공격자 모델 정교화: Stackelberg 게임 기반의 공격-방어 동적 전략 설계

사용자 전략 모델링: 사용자 이탈 모델, QoE 기반 Utility 모델 설계

학습 기반 전략 최적화: 강화학습(RL) 또는 DRL을 활용한 동적 셔플링 전략 학습, MOMDP를 Approximate Solver로 대체하여 스케일업

리소스 관리 통합: VM뿐 아니라 네트워크 트래픽, 대역폭, 스토리지 등 포함한 통합 셔플링 정책

7. Conclusions

MTD는 최근 사이버 보안 분야에서 게임 체인저가 될 수 있는 주제로 주목받고 있다. 기존의 정적(static) 방어 환경에서는 공격자가 본질적으로 유리한 위치에 있었지만, MTD는 이러한 구도를 방어자에게 유리하게 바꿀 수 있는 가능성을 지닌다.
이러한 이유로, MTD는 DDoS 공격 완화와 같은 사이버 보안 문제 해결 방안으로 활발히 연구되고 있다.

하지만 지금까지의 많은 MTD 관련 기법들은,
전략의 합리성(rationality)을 충분히 입증하지 못했고, 경우에 따라 방어 비용을 고려하지 않은 채 MTD 전략의 유용성을 평가한 한계가 있다.
특히, MTD 기법의 방어 효과성과 비용 간의 균형(balance) 문제는 충분히 다뤄지지 않았으며,
비용 효율적인(cost-effective) MTD 메커니즘은 여전히 부족한 실정이다.

우리의 초기 연구(Zhou et al., 2019)는 이러한 한계에 대응하기 위한 첫 번째 중요한 시도였으며,
이번 논문은 그 연구를 다음 단계로 확장한 것이다.

본 논문에서는 다음과 같은 기여를 하였다:

  1. 사용자의 오버헤드까지 고려할 수 있는 새로운 삼자 게임 이론(trilateral game theory)을 제안하였다.
  2. 공격자, 방어자, 사용자 각각의 행동을 설명하기 위한 휴리스틱 기반 전략을 설계하고, 이들 사이의 상호작용을 순차적 게임(sequential game)으로 모델링하였다.
  3. 다목적 마르코프 결정 프로세스(MOMDP)를 도입하여, MTD의 오버헤드 및 성능 영향을 정량적으로 분석하였다.
  4. 마지막으로, 비용과 효과성 사이의 최적 균형점을 찾기 위한 TCS 알고리즘을 제안하였다.

우리가 제안한 접근법의 비용 효율성은 시뮬레이션을 통해 평가되었으며, 기존의 알고리즘(RRT, CSA, CES) 대비 우수한 성능을 보였다.
또한, SDN 기반 셔플링 테스트베드에서 TCS 알고리즘을 실제로 배치하고, 시스템 오버헤드 및 방어 성능 측면에서 그 효과를 검증하였다.

기타 전략들과의 비교를 통해, 제안한 알고리즘의 주요 강점이 입증되었다:

  • 첫째, 낮은 CPU 사용률과 빠른 복구 시간을 통해 알고리즘의 실용성과 QoS 보장을 확인하였다.
  • 둘째, 시스템 전체 보안 향상과 DDoS 공격에 대한 효과적인 대응 측면에서 TCS 알고리즘의 유용성이 명확히 드러났다.

–

공격이 감지되었다는 가정 하에 셔플링을 수행, 탐지 실패나 지연에 대한 고려
SDN 기반 테스트베드에서 수행된 실험 (정적인 환경에서 이루어짐) -> 실시간 적용성
제안된 TCS는 더 복잡한 공격자 모델을 가정하지 않음

MTD 전략 최적화

References:

Zhou, Yuyang, et al. “Cost-effective moving target defense against DDoS attacks using trilateral game and multi-objective Markov decision processes.” Computers & Security 97 (2020): 101976.
TCS – https://www-sciencedirect-com-ssl.oca.korea.ac.kr/science/article/pii/S0167404820302492

Wang, Huangxin, Fei Li, and Songqing Chen. “Towards cost-effective moving target defense against ddos and covert channel attacks.” Proceedings of the 2016 ACM Workshop on Moving Target Defense. 2016.
RRT – https://dl.acm.org/doi/10.1145/2995272.2995281

Lin, Yi-Hui, et al. “A cost-effective shuffling-based defense against HTTP DDoS attacks with SDN/NFV.” 2017 IEEE International Conference on Communications (ICC). IEEE, 2017.
CSA – https://ieeexplore.ieee.org/document/7997190

Zhou, Yuyang, et al. “A cost-effective shuffling method against ddos attacks using moving target defense.” Proceedings of the 6th ACM Workshop on Moving Target Defense. 2019.
CES – https://dl.acm.org/doi/10.1145/3338468.3356824

Leave a Comment