기술 요약: 능동적 디렉토리 보안 강화를 위한 실용적 그래프 최적화 및 AI 기반 모델

1. 문제 정의

Microsoft Active Directory (AD)는 포춘 500대 기업의 약 90%에서 핵심적인 ID 및 액세스 관리 시스템 역할을 수행합니다. 이러한 보편성에도 불구하고, AD 환경은 빈번하게 침해되며, 침투 테스트 수행 시 네트워크의 최대 82%에서 전체 권한 탈취가 발생하는 것으로 나타납니다. 주요 취약점은 "불안정한 드리프트(insecure drift)"에서 기인하는데, 이는 일상적인 운영 과정(예: 권한이 낮은 워크스테이션에 특권 관리자가 로그인하는 행위)이 "클린 소스 원칙(Clean Source Principle)"을 위반하는 교차 계층 공격 경로를 생성하기 때문입니다.

방어자들은 전통적으로 공격 그래프(예: BloodHound으로 생성된 그래프)를 사용하여 이러한 경로를 시각화합니다. 그러나 기존의 보안 강화 방식은 다음과 같은 세 가지 결정적인 한계점에 직면해 있습니다:

1. 정적 가정 (Static Assumptions): 대부분의 모델은 AD 그래프를 정적인 것으로 취급하여, 사용자 활동에 따라 나타나고 사라지는 동적 엣지(예: HasSession 엣지)를 무시합니다. 이는 실제 상황에서 최적이 아닌 방어 전략을 초래합니다.
2. 제한된 방어 메커니즘 (Limited Defense Mechanisms): 현재의 연구는 거의 전적으로 엣지 제거(권한 박탈)에만 집중되어 있습니다. 이는 운영을 방해하지 않으면서 공격자를 차단할 수 있는 허니팟(honeypot)이나 디코이(decoy)의 전략적 배치와 같은 능동적 방어 모델이 부족합니다.
3. 인간 참여형 확장성의 결여 (Lack of Human-in-the-Loop Scalability): 실질적인 보안 강화를 위해서는 IT 관리자의 승인이 필요합니다. 기존 모델은 모든 엣지의 제거 가능 여부를 사전에 알고 있다고 가정하거나(비현실적), 엣지를 하나씩 개별적으로 질의합니다(확장성 부족). 따라서 공격 경로의 단절을 보장하면서도 관리자의 의사결정 패턴을 학습하여 질의 노력을 최소화할 수 있는 적응형 모델이 필요합니다.

본 논문은 게임 이론 및 최적화 기반 모델을 AD 스타일의 공격 그래프에 특화하여 개발함으로써 이러한 격차를 해결하며, 이 문제들의 계산적 난해함(computational intractability)을 증명하고, 혼합 정수 계획법(MIP)부터 강화 학습(RL)에 이르는 확장 가능한 알고리즘을 제안합니다.

2. 방법론 및 기여

본 논문은 능동적 방어, 시간적 역학, 그리고 적응형 인간 상호작용에 관한 특정 연구 목표를 다루는 네 가지 주요 기여를 중심으로 구성되어 있습니다.

기여 1: 정적 및 동적 그래프에서의 허니팟 배치 (제3장)

문제: 공격자를 차단하기 위해 제한된 예산 내에서 AD 노드에 허니팟을 어떻게 최적으로 배치할 것인가? 이때 공격자는 허니팟을 감지하지 못하는 "단순한(simple)" 공격자와 이를 관찰하고 회피할 수 있는 "유능한(competent)" 공격자를 모두 고려해야 합니다.
방법론:

• 게임 이론적 정식화: 이 문제는 Stackelberg 게임으로 모델링됩니다. 방어자는 단순 공격자와 유능한 공격자가 혼재된 상황에서 공격자의 성공 확률을 최소화합니다.
• 복잡도: 이 문제는 단순 공격자에 대해서는 NP-hard이며, 유능한 공격자에 대해서는 W[1]-hard임이 증명되었습니다.
• 정적 솔루션: MIP 정식화가 개발되었습니다. AD 그래프의 트리 구조를 활용하여, 솔버는 대규모 그래프(최대 약 137k 노드)에서도 높은 효율성을 달성합니다.
• 동적 솔루션: AD 그래프가 HasSession 엣지를 통해 진화한다는 점을 인식하여, 본 논문은 $m$개의 그래프 스냅샷에 대해 최적화하는 **dyMIP(m)**를 제안합니다. 확장성을 처리하기 위해 두 가지 휴리스틱을 도입합니다:
  • 투표 기반 (Voting-based): 스냅샷 배리에 대해 MIP를 실행하고 가장 빈번하게 등장하는 노드를 선택합니다.
  • 클러스터링 기반 (Clustering-based): 그래프 특징(feature)에 대해 k-means 클러스터링을 사용하여 대표 스냅샷을 선택하고, 이 축소된 집합에 대해서만 MIP를 해결합니다.
    결과: 합성 데이터 및 실제 인증 데이터를 대상으로 한 실험에서, 클러스터링 기반 휴리스틱은 동적 엣지의 출현을 고려하지 못하는 정적 전용 방어보다 훨씬 낮은 계산 비용으로 최적에 가까운 차단 계획을 생성함을 보여주었습니다. 이 접근 방식은 수백만 개의 엣지를 가진 그래프로 확장 가능하며, 정적 전용 방어의 한계를 극복합니다.

기여 2: 시간적 그래프에서의 사이버 대응 시간 최적화 (제4장)

문제: 시간적 설정(temporal setting)에서 공격자는 특정 엣지가 사용 가능해질 때까지 노드에 "잠복(lurk)"할 수 있습니다. 목표는 단순히 경로를 차단하는 것이 아니라, 대응 시간(Response Time, RT)—즉, 첫 번째 디코이가 트리거된 시점부터 도메인 관리자(DA)에 도달할 때까지의 시간—을 최대화하는 것입니다.
방법론:

• 지표: RT는 첫 번째 허니팟 트리거와 DA 침해 사이의 시간 차이로 정의됩니다 최악의 경우의 RT를 최대화하는 것이 방어자의 목표입니다.
• 복잡도: 이 최적화 문제는 strict temporal $(s, d)$-separator 문제로부터의 환원을 통해 NP-hard임이 증명되었습니다.
• 알고리즘: 다양하고 고품질인 방어 전략을 찾기 위해 진화적 다양성 최적화(Evolutionary Diversity Optimization, EDO) 알고리즘이 채택되었습니다.
• 최적화 기법:
  • 빠른 적합도 평가 (Faster Fitness Evaluation): 시간적 그래프에서 "최단 도착 경로(earliest-arrival path)"를 계산하기 위한 새로운 Dijkstra 기반 알고리즘이 제안되었습니다. 이는 대부분의 AD 엣지가 정적이라는 점을 활용하여, 최신 기술인 Wu 등의 알고리즘보다 5배 빠른 속도를 달성합니다.
  • 제약 조건 처리 (Constraint Handling): 진화적 탐색 과정에서 유효한 절단(cut)을 찾는 어려움을 해결하기 위해 두 가지 기술이 도입되었습니다:
    1. ILP 복구 (ILP Repair): 정수 선형 계획법을 사용하여 부적합한 자손을 유효한 절단으로 "패치"합니다.
    2. 대리 함수 보조 적합도 (Surrogate-Assisted Fitness): "중요한" 경로들만을 평가하는 가벼운 대리 함수를 사용하며, 공격자에 의해 발견된 새로운 최적 공격 경로에 따라 지속적으로 업데이트됩니다.

결과: EST(Surrogate-Assisted) 방식은 일반적인 EDO보다 약 108배 빠르게 유효한 솔루션에 수렴하며, 대응 시간 지표에서 ILP 기반 복구보다 약 23% 더 우수한 성능을 보이면서도 대규모 그래프에서의 Out-of-Memory 오류를 방지합니다.

기여 3: 크로스 티어 경로 제거를 위한 적응형 위저드 (제5장)

문제: 어떤 엣지가 제거 가능한지 미리 알지 못하는 상태에서, 최소한의 질의로 공격 경로를 끊고 엣지를 제거하기 위해 IT 관리자에게 어떻게 인터랙티브하게 질의할 것인가?
방법론:

• 적응형 경로 제거 (Adaptive Path Removal, APR): "위저드"는 관리자에게 여러 선택지(경로 상의 엣지들)를 포함한 공격 경로를 제시합니다. 관리자는 해당 엣지 중 하나를 제거하도록 선택합니다. 이 과정은 경로가 끊기거나 예산이 소진될 때까지 반복됩니다.
• 복잡도: 최적의 적응형 정책을 찾는 것은 #P-hard임이 증명되었습니다.
• 알고리즘:
  • 정확한 해법 (OPT): 소규모 그래프를 위한 동적 계획법(Dynamic Programming) 방식입니다.
  • 근사 해법 (APP): 적응형 부가적(submodular) 근사 알고리즘입니다.
  • 확장 가능한 휴리스틱 (DPR): 정확한 방법론을 기반으로 하되 대규모 그래프로 확장 가능한 "제한적 동적 계획법(Dynamic Programming with Restrictions)" 휴리스틱입니다.
  • RL 접근법: 낮은 추론 시간을 위해 오프라인에서 훈련된 강화 학습(Reinforcement Learning) 휴리스틱입니다.
    결자: DPR 휴리스틱은 충분한 예산이 있을 때 모든 $s-t$ 경로의 제거를 보장하며 가장 강력한 결과를 제공합니다. 이는 기대 질의 횟수를 줄이는 데 있어 비적응형 베이스라인 전략보다 크게 앞섭니다.

기여 4: 특징 기반 적응형 연결성 테스트 (F-ACT) (제6장)

문제: 적응형 질의 모델을 확장하여, 엣지를 개별적으로 질의하는 대신 엣지의 특징(예: 객체 속성)을 기반으로 관리자의 결정을 일반화하는 방법은 무엇인가?
방법론:

• F-ACT 프레임워크: 위저드는 "엣지 $e$를 제거하시겠습니까?"라고 묻는 대신, 해당 엣지의 특징 벡터를 함께 제시합니다. 관리자의 결정(절단/유지)은 동일한 특징 패턴을 공유하는 모든 엣지에 적용됩니다.
• RL 솔루션 (RL4FT): 적응형 질의 정책을 학습하기 위해 강화 학습 에이전트가 훈련됩니다.
  • 자기 개선 (Self-Improvement): 주어진 참조 정책(reference policy)을 능가할 수 있도록 하는 메커니즘입니다.
  • 보상 형성 (Reward Shaping): 희소한 보상(sparse rewards) 문제를 처리하기 위한 정책 불변(policy-invariant) 체계입니다.
  • 우선순위 경험 재생 (Prioritized Experience Replay): 고가치 전환(transition)에 집중하기 위한 커스텀 리플레이 버퍼입니다.
    결과: RL4FT는 참조 정책보다 개선을 보장하며, 기대 질의 횟수를 최소화하는 데 있어 최신 베이스라인(제5장의 DPR 휴리스틱 포함)을 유의미하게 능가함으로써 특징 기반 일반화의 효용성을 입증했습니다.

3. 주요 결과 및 의의

본 논문은 다음을 입증합니다:

1. 동적 방어의 중요성: 정적 허니팟 배치 전략은 동적 AD 그래프에 적용될 때 성능이 크게 저하됩니다. 제안된 동적 그래프용 클러스터링 및 투표 기반 휴리스틱은 높은 확장성과 함께 최적에 가까운 성능을 달성합니다.
2. 시간적 인식이 대응력을 높임: 그래프를 시간적으로 모델링하고 대응 시간을 최대화함으로써, 방어자는 사고 대응을 위한 결정적인 시간을 확보할 수 있습니다. 제안된 Dijkstra 기반 적합도 평가 및 대리 함수 보조 EDO 알고리즘은 대규모 네트워크에서도 이를 계산적으로 가능하게 만듭니다.
3. 인간 참여형 모델의 확장성: 적응형 질의 모델(APR 및 F-ACT)은 보안 강화에 따른 관리적 부담을 성공적으로 줄여줍니다. 엣지 특징을 통해 결정을 일반화하거나(F-ACT) 적응형 경로 선택을 사용함으로써(APR), 네트워크 보안을 보장하면서도 필요한 질의 횟수를 최소화합니다.
4. 계산적 난해성: 본 논문은 기초가 되는 문제들(허니팟 배치, 시간적 절단 최대화, 적응형 질의)이 계산적으로 매우 어렵다는 것(NP-hard, W[1]-hard, #P-hard)을 엄밀히 규명하여, 제안된 휴리스틱 및 근사 알고리즘의 필요성을 정당화합니다.

의의:
본 연구는 이론적인 그래프 보안 모델과 실질적인 Active Directory 보안 강화 사이의 간극을 메웁니다. 단순히 엣지를 제거하는 휴리스틱을 넘어, 능동적 방어(허니팟), 시간적 인식(대응 시간 최적화), 그리고 인간 중심의 자동화(적응형 위저드)를 포함하는 종합적인 툴킷을 제공합니다. 제안된 알고리즘은 운영의 연속성과 관리자의 업무량이 매우 중요한 실제 엔터프라이즈 규모의 네트워크(수십만 개의 노드)로 확장 가능하도록 설계되었습니다. 본 논문은 문제들이 이론적으로는 매우 어렵지만, 제안된 AI 기반 및 최적화 기반 접근 방식이 현대적인 AD 보안을 위한 실질적이고 효과적인 솔루션을 제공함을 결론짓습니다.