Fast Botnet Detection From Streaming Logs Using Online Lanczos Method

기술 요약: 온라인 란초스 방법(Lanczos Method)을 이용한 스트리밍 로그 기반의 빠른 봇넷 탐지

문제 정의
본 논문은 대규모 스트리밍 웹 서버 로그(예: Apache access 로그)로부터 봇넷(조직화된 악성 봇 그룹)을 탐지하는 과제를 다룹니다. 기존의 단일 봇 탐지는 주로 높은 요청 속도(이상치 탐지)에 의존하지만, 봇넷은 개별적으로는 인간과 유사한 요청 속도를 모방하도록 설계되어 있어 단순한 속도 기반 방식으로는 탐지하기 어렵습니다. 대신, 봇넷은 행동의 높은 상관관계를 보입니다.

저자들은 실용적인 솔루션을 위한 세 가지 주요 제약 조건을 식별했습니다:

1. 적용 가능성: 기존 방법들은 특수 데이터(예: DNS 트래픽, 프로토콜 지식, 또는 사용자 로그인 그래프)를 필요로 하는 경우가 많아 일반적인 서버 로그에서는 사용하기 어렵습니다. 제안된 방법은 호스트 식별자(IP/호스트명), 요청 식별자(URL), 타임스탬프와 같은 기본적인 로그 필드에만 의존해야 합니다.
2. 시간 복잡도: 스트리밍 로그는 매우 높은 볼륨으로 유입됩니다(예: 30분 동안 100,000개의 엔트리). 전통적인 주성분 분석(PCA)은 상관 행렬의 고유값(eigenvalues)을 통해 데이터 상관관계를 포착하는데, 이는 $O(n^3)$의 세제곱 시간 복잡도를 가집니다. 이는 실시간 모니터링, 특히 민감도를 유지하기 위해 슬라이딩 시간 창(sliding time windows)을 사용하는 상황에서 계산적으로 불가능합니다.
3. 보안 및 개인정보 보호: 이 방법은 네트워크 패킷을 가로채거나 민감한 저수준 하드웨어 데이터에 접근할 필요가 없어야 하며, 사용자가 스트리밍 전에 식별자를 익명화할 수 있어야 합니다.

방법론
제안된 접근 방식은 높은 "주성분 가중치"(상관 행렬의 가장 큰 고유값)를 식별함으로써 협동 행동을 탐지하도록 **주성분 분석(PCA)**을 적응시킨 것입니다. 이 cubic 복잡도를 극복하기 위해, 저자들은 고유값 근사를 위한 수치 선형 대수 방법인 **란초스 반복법(Lanczos iteration)**을 통합했습니다.

이 방법론은 세 가지 핵심 구성 요소로 이루어집니다:

1. 온라인 상관 행렬 업데이트:
   매 시간 창마다 상관 행렬을 처음부터 다시 계산하는 대신, 저자들은 일반화된 업데이트 공식을 도출했습니다. 슬라이딩 윈도우가 이동함에 따라 행(요청)이 추가, 제거 또는 수정됩니다. 본 논문은 윈도우 사이의 변화량($\Delta$)만을 사용하여 평균 벡터, 표준 편차 및 상관 행렬 자체를 업데이트하는 수학적 유도 과정을 제시합니다. 이를 통해 업데이트 복잡도를 cubic에서 약 $O(m^2)$(여기서 $m$은 고유 호스트 수)로 줄였습니다.

2. 조기 종료를 포함한 란초스 반복법:
   알고리즘은 업데이트된 상관 행렬의 최대 고유값과 그에 대응하는 고유벡터를 근사하기 위해 란초스 방법을 사용합니다.

• 이론적 기초: 이 방법은 대칭 행렬의 상위 주성분 부행렬(leading principal submatrices)의 고유값은 비감소한다는 성질(정리 2)에 기반합니다.
• 종료 조건: 오차 범위를 기반으로 한 새로운 종료 조건이 도입되었습니다(정리 1). 알고리즘은 다음의 경우 조기에 반복을 중단합니다:
  • 추정된 고유값에 오차 범위를 더했을 때 임계값 $\omega$를 초과하는 경우(봇넷이 존재할 가능성이 높음을 나타냄).
  • 추정된 고유값에서 오차 범위를 뺐을 때, 일정 횟수의 라운드 동안 하한선 미만으로 유지되는 경우(봇넷이 존재하지 않음을 나타냄).
    이러한 "온라인" 능력 덕분에 시스템은 완전한 수렴을 기다리지 않고 실시간으로 데이터를 처리할 수 있습니다.

3. 봇 식별:
   높은 주성분 가중치가 탐지되면, 알고리즘은 각 호스트와 주성분 간의 상관관계를 계산합니다. 특정 상관관계 임계값을 초과하는 호스트는 잠재적인 봇넷 구성원으로 플래그가 지정됩니다.

주요 기여
저자들은 다음과 같은 기여를 주장합니다:

• 스트리밍 로그에 대한 첫 적용: PCA 기반 봇넷 탐지를 스트리밍 웹 서버 로그에 구체적으로 적용한 첫 번째 조사입니다.
• 일반화된 업데이트 공식: 가장 일반적인 사례의 슬라이딩 윈도우(추가, 제거 및 수정된 행/열 처리)에 적합한 일반화된 온라인 상관 행렬 업데이트 공식을 제공합니다.
• 란초스 적응: 저자들은 빠른 봇넷 탐지를 위해 란초스 방법을 인식하고 적응시킨 최초의 연구자이며, 조기 종료를 가능하게 하기 위해 오차 범위와 고유값의 비감소 성질을 이용한 종료 조건을 혁신했습니다.
• 복잡도 감소: 이 접근 방식은 고유값 기반 봇넷 탐지의 시간 복잡도를 cubic에서 sub-cubic으로 줄여 슬라이딩 윈도우 사용을 가능하게 했습니다.

실험 결과
실험은 시뮬레이션된 봇 및 봇넷 트래픽이 추가된 약 3억 1,500만 개의 이커머스 웹사이트 Apache access 로그 엔트리 데이터셋을 사용하여 수행되었습니다.

• 성능: 란초스 기반 방법(Lanczos-S)은 전체 PCA 대비 일관되게 20%에서 25% 수준의 시간 비용만을 요구했습니다.
• 정확도:
  • 봇넷의 경우, 슬라이딩 윈도우를 사용하는 란초스(Lanczos-S)는 고정 윈도우 PCA 및 고정 윈도우 란초스보다 높은 정확도(예: 30분 윈도우에서 79.6% 대비 87.9%)를 달しまいました.
  • 단일 봇의 경우, 정확도는 PCA와 유사했으나, 긴 윈도우는 상관관계 신호의 희석으로 인해 일반적으로 성능을 저하시켰습니다.
• 민감도: 슬라이딩 윈도우 접근 방식은 탐지 시간(sensitivity)을 크게 개선했습니다. 40분 윈도우의 경우, Lancзоs-S는 봇을 평균 33.35분 만에 탐지하여 PCA(42.58분)보다 빠른 탐지 속도를 보였습니다.
• 실제 환경 검증: 시뮬레이션 없이 실제 로그에 적용했을 때, 시스템은 232개의 잠재적 봇넷을 식별했습니다. 수동 검증 및 평판 데이터베이스 확인 결과, 확인된 모니터링 서비스 및 비정상적으로 동작하는 검색 엔진 크롤러를 포함하여 상당 부분(88%)이 낮은 평판을 가지고 있는 것으로 확인되었습니다.

의의 및 주장
본 논문은 이 연구를 실시간 보호와 사용 용이성 사이의 균형을 맞춘 "경량" 솔루션으로 포지셔닝합니다. 저자들은 이 방법이 표준 액세스 로그에만 의존하고 복잡한 데이터 전처리나 패킷 검사를 피함으로써, 기존 산업용 봇 탐지 시스템(마르코프 체인 행동 모델과 같은 다른 방법들과 앙상블로 자주 사용됨)에 매우 쉽게 통합될 수 있음을 강조합니다.

주요 의의는 cubic 시간 알고리즘의 지연 시간 없이 실시간 경고를 제공할 수 있도록 슬라이딩 윈도우를 사용하여 스트리밍 로그를 모니터링할 수 있다는 점입니다. 이러한 능력은 시간 복잡도 감소에 직접적으로 기인합니다. 저자들은 이 방법이 협동 봇넷 탐지에는 탁월하지만 모든 유형의 봇을 위한 만병통치약은 아니며, 더 넓은 탐지 앙상블의 일부로서 적합하다고 겸손하게 언급했습니다.