기술 요약: 바늘은 실이다: 노이즈가 있는 프로세스 트리에서 심어진 경로 찾기

1. 문제 정의

본 논문은 대규모의 노이즈가 섞인 라벨링된 유향 비순환 그래프(DAG) 내에 심어진 작고 의미 있는 시퀀스(경로)를 복구하는 수학적 과제인 "심어진 경로(planted path)" 문제를 다룹니다. 이 문제는 "심어진 클리크(planted clique)" 및 "심어진 구조(planted structure)" 문헌의 이론적 유사성을 가지고 있으나, 본 연구는 사이버 보안, 특히 프로세스 트리에서의 실질적인 응용에 초점을 맞춥니다.

이 문맥에서 목표는 공격자가 실행한 프로세스의 시퀀스(심어진 경로)를 찾아내는 것이며, 이는 탈취된 컴퓨터의 방대한 노이즈 섞인 로그 속에 파묻혀 있습니다. 도전 과제는 다음과 같습니다:

• 전체 로그 데이터의 양이 매우 방대함.
• 단순한 휴리스틱을 사용하면 인간이 검사하기에 너무 많은 "의심스러운" 라인을 생성함.
• 실제 악성 시퀀스는 전체 트리에서 아주 작은 부분만을 차지하며, 노이즈(누락된 이벤트, 거짓 양성, 무관한 백그라운드 프로세스)에 의해 가려져 있음.
• 전체 이벤트가 관찰된 데이터 내에 반드시 하나의 연속된 경로로 엄격하게 존재하지 않을 수 있음.

저자들은 "심어진 경로" 추상화가 실제 데이터에는 불완전할 수 있지만, 부분적인 경로를 추출하는 것이 악성 시퀀스의 신호를 결집하고 노이즈를 필터링하여 신호를 증폭시키는 중요한 "신호 집계(signal-aggregation)" 단계 역할을 한다고 주장합니다.

2. 방법론

2.1 퍼지 매칭 알고리즘 (Algorithm 1)

핵심 기여는 두 트리 $G$와 $H$ 사이의 **특징 기반 유사도 점수(feature-based similarity score)**를 계산하도록 설계된 동적 계획법 알고리즘입니다.

• 입력: 노드가 집합 $S$의 특징들로 라벨링된 두 개의 유향 트리와, 두 특징 사이의 유사도를 정량화하는 가중치 함수 $w$.
• 메커니즘: 알고리즘은 두 트리 모두에서 부모-자식 순서($u_i <_G u_{i+1}$ 및 $v_i <_H v_{i+1}$)를 준수하는 노드 매칭 $(u_1, v_1), \dots, (u_k, v_k)$를 찾기 위해 하향식 탭레이션(tabulation) 방식(재귀 방지)을 사용합니다.
• 점수 산정: 매칭의 점수는 가중치 $w(\phi_G(u_i), \phi_H(v_i))$의 합입니다. 알고리즘은 최적의 "퍼지" 정렬을 찾기 위해 이 점수를 최대화합니다.
• 복잡도: 시간 복잡도는 각 트리의 노드 수를 $n$과 $m$이라 할 때 다항 시간인 $O(nm)$입니다.
• 출력: 알고리즘은 매칭된 노드 시퀀스와 최대 점수를 반환합니다. 이는 단일 최적 경로를 반환하거나 "Top-K" 경로를 추출하도록 구성될 수 있습니다.

2.2 워크플로우

저자들은 알고-리즘 1을 더 큰 머신러닝 워크플로우의 빌딩 블록으로 사용하는 방법을 제안합니다.

• 비지도 클러스터링 (Algorithm 2):

  • 목표: 대규모 그래프 집합 내에서 알려지지 않은 템플릿을 식별함.
  • 과정:
    1. 알고리즘 1을 사용하여 데이터셋 내의 모든 트리 간 쌍별 유사도 점수를 계산함.
    2. 특정 정규화(Eq. 5)를 사용하여 유사도 행렬을 거리 행렬로 변환함.
    3. UMAP을 사용하여 트리를 저차원 공간으로 임베딩함.
    4. HDBSCAN을 사용하여 임베딩을 클러스터링함.
    5. 클러스터 내에서 가장 잘 매칭되는 시퀀스들에 대해 다중 서열 정렬(MSA) 접근법을 적용하여 대표적인 "엑셈플러(exemplar)"를 추출함.

• 분류기를 위한 특징 증강 (Section 3.2):

  • 목표: 트리(예: 정상 vs 악성)의 분류 성능을 개선함.
  • 과정: 알려진 템플릿(예: 알려진 공격 시퀀스) 세트를 사용하여 관찰된 각 트리에 대한 보조 특징을 생성함. 특징 $X_{i,j}$는 트리 $G_i$와 템플릿 $T_j$ 사이의 최장 공통 경로 길이(또는 점수)를 나타냄. 이 특징들은 이후 표준 분류기(예: Random Forest)에 입력됨.

2.3 합성 데이터 생성

접근 방식을 검증하기 위해, 저자들은 트리(tree)에 특화된 확률적 블록 모델(SBM)과 유사한 데이터 생성 프로세스(Algorithms 3 및 4)를 도입합니다.

• 트리 생성: "무성한(bushy)" 트리를 생성하기 위해 갈톤-왓슨슨(Galton-Watson) 프로세스를 사용함.
• 심어진 경로: 특정 라벨 시퀀스가 트리의 무작위 경로 내에 심어짐.
• 노이즈 모델: 심어진 경로의 라벨은 관측 확률 $p$(서브샘플링)와 오류 확률(재샘플링)의 영향을 받음. 다른 노드들은 알파벳으로부터 균등하게 라벨링됨.
• 설계 목표: 이 모델은 라벨의 분포가 심어진 경로의 클래스와 독립적이도록 하여, 단순한 라벨 빈도 계산과 같은 사소한 알고리즘들이 실패하게 만들며, 알고리즘이 구조적 경로 정보에 의존하도록 강제함.

3. 주요 결과

3.1 합성 실험

• 구별 가능성: 알고리즘 1에서 도출된 유사도 점수는 경로가 큰 트리 내에서 아주 작은 비율을 차지하고 낮은 관측률($p=0.75$)로 관찰될 때도, 심어진 경로가 있는 트리와 없는 트리를 성공적으로 구별해 냄.
• 클러스터링: 4개의 클래스가 있는 비지도 학습 환경에서 임베딩 워크플로우(Algorithm 2)는 실제 정답 클러스터를 성공적으로 분리함.
• 가중치의 영향: 확률 가중치 점수 함수를 사용하여 희귀한 심볼의 가중치를 낮추는 것이, 알파벳에 희귀 심볼이 포함되어 있을 때 단순 이진 점수보다 클러스터 분리 성능을 유의미하게 향ol상시킨다는 것을 실험을 통해 보여줌.

3.2 실제 적용 (ACME4 데이터셋)

저자들은 제안된 방법을 다양한 공격이 포함된 Windows 비즈니스 네트워크를 시뮬레이션한 사이버 보안 데이터셋인 ACME4 데이터셋에 적용함.

• 데이터 규모: 데이터셋은 110만 개 이상의 프로세스 트리(대부분 크기 2)와 약 300만 개의 노드를 포함함. 오직 8개의 트리만이 "악성(bad)" 사용자를 포함하고 있었음.
• 서브 트리 구축: 작은 트리들의 비중이 높은 문제를 해결하기 위해, 저자들은 더 큰 프로세스 트리로부터 2,693개의 서브 트리(크기 3~9,558)를 구축함.
• 매칭 결과:
  • "악성" 사용자를 포함하는 참조 트리를 사용하여, 다른 트리들에서 일치하는 경로를 성공적으로 식별함.
  • 점수 산정의 유연성: 프로세스 이름에 대한 정확한 매칭(exact match)과 프로세스 이름 및 사용자 이름에 대한 소프트 매칭(soft matching)을 사용하는 서로 다른 점수 함수가 각각 다르지만 의미 있는 결과를 낸다는 것을 입증함. 예를 들어, "소프트" 매칭은 프로세스 시퀀스는 동일하지만 사용자 이름이 약간 다른 경우(예: "user88" vs "bad3")에도 경로를 식별할 수 있었음.
• 워크플로우 성능:
  • 필터링: 알려진 템플릿과 경로를 공유하는 트리를 선택하는 필터로 사용했을 때, 이 방법은 높은 점수를 가진 트리의 하위 집합을 성공적으로 격리했으며, 이는 트리 크기 및 특정 프로세스 시퀀스(예: winlogon.exe $\to$ cmd.exe)와 상관관계를 보임.
  • 분류: 경로 매칭(38개 템플릿에 대한 공통 경로 길이)으로부터 파생된 특징으로 훈련된 Random Forest 분류기는 루트 프로세스 이름을 기준으로 트리를 분류하는 데 높은 정확도를 달erm았으며, bash.exe와 cmd.exe 사이에서만 미미한 혼동을 보임.

4. 의의 및 주장

본 논문은 제안된 방법이 실질적인 사이버 보안 데이터에서 경로 추출이 실행 가능하며 유용함을 보여주는 탐색적 연구임을 표방합니다.

• 실용적 유용성: 저자들은 "심어진 경로" 문제가 하나의 추상화일지라도, 제안된 알고리즘이 관련 이벤트들로부터 신호를 효과적으로 결집하여 인간 전문가를 압도할 수 있는 방대한 양의 노이즈를 필터링한다고 주장합니다.
• 제한된 범위: 저자들은 본 연구가 예비 연구임을 명시합니다. 현재의 작업이 특정 깨끗한 버전의 문제에 대해 통계적으로 최적인 솔루션을 제공하는 것이 아니라, "지저분한" 데이터를 위한 현실적인 모델을 개발하는 데 중점을 두고 있음을 인정합니다.
• 향-후 과제: 논문은 향-후 버전에서 더 현실적인 머신러닝 워크플로우, 실제 데이터셋에 대한 다른 알고리즘과의 비교, 그리고 기본적인 이론적 분석을 제공할 것임을 언급합니다.
• 한계점: 저자들은 실제 데이터에서는 전체 이벤트가 단일 경로 내에 엄격하게 포함되지 않을 수 있으며, 관찰의 노이즈가 전체 심어진 경로의 관찰을 방해할 수 있음을 인정합니다. 그러나 이들은 불완전한 필터링이라 할지라도 악성 시퀀스의 신호를 증폭시킨다고 주장합니다.

요약하자면, 본 논문은 노이즈가 섞인 프로세스 트리에서 의미 있는 시퀀스를 복구하기 위한 기초 도구로서 퍼지 매칭 알고리즘을 소개하며, 합성 모델을 통해 그 효용성을 검증하고, 특징 생성기 및 필터로서의 잠재력을 실제 환경에서 입증하였습니다.