Game-Theoretic Modeling of Stealthy Intrusion Defense against MDP-Based Attackers

이 논문은 공격자가 MDP 기반으로 행동하는 고급 지속 위협 (APT) 에 대응하여, 공격자의 정보 수준 (Stackelberg, 무지, 확률적 신념) 에 따라 공격 그래프 상에서의 은밀한 침입을 방어하기 위한 게임 이론적 최적 방어 전략을 제시합니다.

핵심

🏰 비유: 성을 지키는 경비대장과 지능형 해커

이 연구는 한 성 (네트워크) 을 지키는 **경비대장 (방어자)**과 성을 뚫으려는 지능형 해커 (공격자) 사이의 게임을 상상해 보세요.

1. 상황 설정: 보이지 않는 적

• 해커의 특징: 해커는 이미 성 안 어딘가에 숨어 있습니다. 그는 단순히 한 번에 모든 문을 부수는 게 아니라, 천천히, 은밀하게, 그리고 여러 경로를 통해 보물 (중요 자산) 에 도달하려 합니다.
• 경비대장의 딜레마: 경비대장은 해커가 정확히 어디에 있는지 모릅니다. 하지만 해커가 발견되면 즉시 문 (시스템) 을 잠그고 수리 (패치) 해야 합니다. 문제는 경비대장이 언제 감시할지는 알 수 있지만, 해커가 그 사이 몇 걸음이나 더 나아갈지 알 수 없다는 점입니다.

2. 게임의 세 가지 시나리오 (해커가 얼마나 아는가에 따라)

이 논문은 해커가 경비대장의 전략을 얼마나 알고 있는지에 따라 세 가지 상황을 나누어 분석했습니다.

① 스택엘버그 게임 (완벽한 정보)

• 상황: 해커가 경비대장의 모든 계획을 미리 다 알고 있습니다. ("아, 경비대장은 A 문을 지키고 있구나. 그럼 B 문을 뚫자!")
• 결과: 해커는 경비대장이 지키지 않는 가장 약한 길을 찾아냅니다. 이는 경비대장에게 최악의 상황입니다.
• 해결책: 경비대장은 해커가 어떤 길로 올지 예측하고, 그 길들을 미리 차단하는 '최악의 경우'를 대비한 전략을 세워야 합니다.

② 맹인 공격 (전혀 모르는 상황)

• 상황: 해커는 경비대장이 어디를 지키는지 전혀 모릅니다. 그냥 "어디든 확률적으로 있을 거야"라고 추측하며 무작위로 움직입니다.
• 결과: 해커는 모든 문을 고르게 의심하며 움직입니다.
• 해결책: 경비대장은 해커가 무작위로 움직일 것이라고 가정하고, 가장 빈번하게 방문될 법한 핵심 지점들을 막아야 합니다.

③ 믿음 기반 게임 (부분적인 정보)

• 상황: 해커는 경비대장의 계획을 완전히 알지는 못하지만, "경비대장은 보통 이쪽을 자주 지키는 것 같아"라는 **추측 (믿음)**을 가지고 있습니다.
• 핵심 아이디어 (디리클레 전략): 경비대장은 이 '추측'을 이용해 해커를 속일 수 있습니다. 예를 들어, 해커가 "A 문을 자주 지키겠지"라고 생각하게끔 일부러 A 문을 자주 지키는 척하는 정보를 흘려, 해커가 A 문을 피하게 만든 뒤, 실제로는 A 문 옆의 B 문을 지키는 교묘한 속임수를 쓸 수 있습니다.
• 결과: 이 방법은 해커가 가진 '잘못된 믿음'을 역이용하여, 완벽한 정보를 가진 해커를 상대할 때보다 더 좋은 방어 효과를 낼 수 있음을 보여줍니다.

3. 실험 결과: 어떤 성이 더 중요할까?

연구진은 실제 로봇 (MARA, MiR100) 과 가상 네트워크 (Unguard) 를 대상으로 실험했습니다.

• 케이스 1: 좁고 막힌 길 (MiR100 로봇)

  • 성으로 들어가는 길이 딱 하나뿐이거나, 중요한 지점 (병목 지점) 이 명확한 경우입니다.
  • 결과: 해커가 정보를 얼마나 가지고 있든 상관없이, 그 중요한 지점 하나만 막으면 됩니다. 복잡한 게임 이론보다는 '중요한 곳'을 찾는 것이 핵심입니다.

• 케이스 2: 복잡하고 여러 갈래 길이 있는 성 (Unguard 네트워크)

  • 성으로 들어가는 길이 수십 개이고, 해커가 여러 갈래로 우회할 수 있는 경우입니다.
  • 결과: 단순히 가장 짧은 길만 막는다면 해커는 다른 길로 우회합니다. 이때 게임 이론을 적용한 최적의 전략을 쓰면, 해커의 성공 확률을 3 배 이상 낮출 수 있었습니다.
  • 교훈: 길이 복잡할수록, 해커가 무엇을 생각할지 예측하는 '게임 전략'이 단순한 '무작위 방어'보다 훨씬 강력합니다.

💡 핵심 요약

1. 은밀한 해커는 천천히 움직입니다: 한 번에 다 뚫는 게 아니라, 시간을 두고 은밀하게 이동합니다.
2. 정보의 차이가 승패를 가릅니다: 해커가 방어 계획을 얼마나 아는지에 따라 최적의 방어 전략이 달라집니다.
3. 속임수의 힘: 방어자가 해커의 '추측'을 이용해 속이면, 해커를 더 효과적으로 막을 수 있습니다.
4. 구조가 중요하다: 네트워크 구조가 단순하면 '중요한 지점'만 막으면 되지만, 복잡하면 '게임 이론'을 써서 지능적으로 방어해야 합니다.

결론적으로, 이 논문은 단순히 "방화벽을 세우자"가 아니라, **"해커가 어떻게 생각하고 움직일지 예측하여, 가장 효율적인 곳에 자원을 투입하자"**는 지능형 사이버 방어 전략을 제시합니다.

기술 요약

논문 요약: MDP 기반 공격자에 대한 은밀한 침입 방어를 위한 게임 이론적 모델링

1. 문제 정의 (Problem Definition)

• 배경: 인터넷 사용의 급증으로 사이버 위협, 특히 **지속적 위협 (APTs, Advanced Persistent Threats)**이 증가하고 있습니다. APT 는 은밀성, 장기화, 다단계 공격 특성을 가지며, 고가 자산 (Critical Assets) 을 목표로 합니다.
• 핵심 문제: 방어자는 공격자의 위치와 진행 상황에 대한 정보가 제한적이며, 공격자는 네트워크를 탐색 (Reconnaissance) 하고 취약점을 악용하여 백도어를 설치하는 등 적응적으로 이동합니다.
• 기존 모델의 한계: 기존 연구 (Cut-The-Rope 게임 등) 는 공격자가 게임 시작 전 하나의 공격 경로를 고정적으로 선택한다고 가정했습니다. 그러나 실제 APT 는 방어자의 대응을 관찰하고 상황에 따라 경로를 동적으로 변경하는 적응형 행동을 보입니다.
• 목표: 방어자가 무작위 간격으로 침입 탐지 센서를 배치하고 공격자를 차단하는 상황에서, **공격자의 정보 수준 (완전 정보, 부분 정보, 무 정보)**에 따른 최적의 방어 전략을 도출하는 것입니다.

2. 방법론 (Methodology)

가. 모델링 프레임워크

• 게임 설정: 공격자와 방어자 간의 제로섬 (Zero-sum) 게임으로 모델링하며, 전장은 **공격 그래프 (Attack Graph, $G=(V, E)$)**로 표현됩니다.
• 시간적 역학:
  • 방어자: 포아송 과정 (Poisson process) 에 따라 무작위 시간 간격 ($\lambda_D$) 으로 네트워크를 스캔하고 센서를 배치합니다.
  • 공격자: 방어자가 스캔하지 않는 동안 (지연 시간), 포아송 분포 ($\lambda$) 를 따르는 수의 단계를 이동합니다.
  • 결과: 공격자가 방어자가 돌아오기 전에 취할 수 있는 단계 수 ($N$) 는 기하급수적 분포 (Geometric distribution) 를 따릅니다.
• 공격자 행동 모델 (MDP): 공격자의 행동을 **마르코프 결정 과정 (MDP)**으로 모델링하여, 각 노드에서 방어자의 배치 상태를 고려한 동적 경로 선택을 가능하게 합니다.
  • 상태 ($S$): 현재 위치와 이동한 단계 수.
  • 보상 ($R$): 목표 자산 도달 시 1, 탐지 시 0.

나. 세 가지 정보 regime (Information Regimes)
논문은 공격자의 정보 수준에 따라 세 가지 시나리오를 분석합니다.

1. 스택엘버그 게임 (Stackelberg Game - 완전 정보):

   • 공격자가 방어자의 전략을 완벽하게 알고 최적의 대응 (Best Response) 을 합니다.
   • 방어자는 최악의 경우 (Worst-case) 를 가정하여 공격자의 성공 확률을 최소화하는 전략을 수립합니다.
   • 해법: 이진 계획법 (MILP) 을 사용하여 최적의 센서 배치를 계산합니다.

2. 무지한 공격자 (Blind Attacker - 무 정보):

   • 공격자는 방어자의 행동을 전혀 알지 못하며, 모든 가능한 방어 전략에 대해 균일한 확률 (Uniform belief) 을 가집니다.
   • 공격자는 기대 성공 확률을 최대화하는 경로를 선택합니다.
   • 해법: 공격자의 균일 믿음 하에서 최적 경로를 먼저 계산한 후, 이에 대한 방어자의 최적 배치를 탐색합니다.

3. 신념 기반 방어 (Belief-based Defense - Dirichlet 불확실성):

   • 공격자는 방어자의 행동을 완전히 알지는 못하지만, 관찰된 빈도 등을 바탕으로 **디리클레 분포 (Dirichlet distribution)**를 따르는 확률적 신념 (Belief) 을 가집니다.
   • 방어자는 공격자의 신념 분포를 조작 (Deception) 하여 공격자가 잘못된 경로를 선택하도록 유도할 수 있습니다.
   • 해법: 몬테카를로 샘플링을 통해 다양한 공격자 신념 시나리오에 대한 기대 성공 확률을 최소화하는 강건한 (Robust) 전략을 도출합니다.

3. 주요 기여 (Key Contributions)

1. MDP 기반 공격자 모델링 확장: 기존 CTR(Cut-The-Rope) 모델을 확장하여, 공격자가 방어자의 배치를 인지하고 **상태 의존적 (State-dependent)**으로 경로를 동적으로 선택하는 MDP 모델을 도입했습니다. 이는 실제 APT 의 적응적 행동을 더 정확히 반영합니다.
2. 세 가지 정보 regime 에 대한 최적 전략 도출:
   • 완전 정보 (Stackelberg), 무 정보 (Blind), 부분 정보 (Dirichlet) 세 가지 시나리오에 대해 각각 최적의 방어 전략을 수학적으로 유도하고 최적화 문제 (LP, MILP) 로 정식화했습니다.
3. 디리클레 기반 강건 전략의 이론적 증명:
   • Stackelberg 전략이 항상 최선은 아니며, 공격자의 신념 분포를 고려한 Dirichlet-robust 전략이 특정 조건에서 공격자의 기대 성공 확률을 Stackelberg 전략보다 더 낮출 수 있음을 이론적으로 증명했습니다 (Theorem 1).
4. 실제 사례를 통한 검증:
   • **MARA (모듈형 로봇 팔), MiR100 (이동 로봇), Unguard (가상 클라우드 네트워크)**의 실제 공격 그래프를 사용하여 알고리즘을 검증했습니다.

4. 실험 결과 (Results)

• MARA (복잡도 낮음, 단일 진입점):
  • 최적 전략이 휴리스틱 (최단 경로, 무작위) 보다 공격 성공 확률을 현저히 낮췄습니다.
  • 특히 Dirichlet 시나리오에서는 Stackelberg 전략을 그대로 적용할 경우 방어 성능이 저하될 수 있음을 보여줌.
• MiR100 (병목 현상 명확):
  • 그래프 구조상 주요 병목 지점 (Bottleneck, 예: 노드 15) 이 명확하여, 세 가지 게임 이론적 프레임워크 (Stackelberg, Blind, Dirichlet) 모두 동일한 최적 방어 전략을 도출했습니다.
  • 네트워크 토폴로지가 정보 가정보다 우세한 경우, 병목 지점만 차단하면 전략적 이점을 얻을 수 있음.
• Unguard (고복잡도, 다중 경로):
  • 여러 독립적인 공격 벡터와 중복 경로가 존재하여 병목 지점이 명확하지 않음.
  • 이 경우 세 프레임워크는 서로 다른 최적 전략을 도출했습니다.
  • 성과: 게임 이론적 최적 전략은 휴리스틱 (최단 경로) 대비 공격 성공 확률을 **약 3 배 (0.275 → 0.09)**까지 감소시켰습니다.
  • 통찰: 중복 경로가 많은 네트워크에서는 단일 경로 차단이 아닌, 여러 공격 경로에 공통으로 영향을 미치는 노드를 선별하여 방어하는 것이 핵심입니다.

5. 의의 및 결론 (Significance)

• 전략적 자원 할당의 중요성: 방어 리소스가 제한적일 때, 무작위 배치나 단순 최단 경로 차단보다 게임 이론적 최적화를 통해 공격 성공 확률을 획기적으로 낮출 수 있음을 입증했습니다.
• 정보 불확실성의 관리: 공격자의 정보 수준 (완전/부분/무 정보) 에 따라 최적 방어 전략이 달라지며, 특히 디리클레 기반의 신념 조작 (Deception) 전략은 공격자의 인지 편향을 이용하여 방어 효율을 높일 수 있는 새로운 가능성을 제시합니다.
• 실무적 시사점:
  • 네트워크 토폴로지가 단순하고 병목이 명확한 경우: 병목 지점 식별 및 보호가 최우선.
  • 네트워크가 복잡하고 중복 경로가 많은 경우: 공격자의 행동 모델링과 게임 이론적 접근이 필수적이며, 단순 휴리스틱은 큰 비용 손실을 초래할 수 있음.
• 한계점: 현재 모델은 방어자가 공격자의 위치를 실시간으로 추적하지 못하고 (완전한 불확실성), 탐지 센서의 신뢰도를 100% 로 가정하고 있어, 실제 환경의 노이즈와 오검출을 고려한 확장 필요성이 있습니다.

이 논문은 APT 와 같은 지능형 공격에 대응하기 위해, 네트워크 구조와 공격자의 정보 수준을 종합적으로 고려한 게임 이론 기반의 동적 방어 체계의 필요성과 효과를 수학적으로 rigorously 증명했다는 점에서 의의가 큽니다.