개요

Detecting Insider Threats Using a Graph-Based Approach를 분석한 내용을 포스팅 한다.

3줄 요약

  • 내부자의 위협을 갈수록 증가하고 이들은 최대한 정상행동 처럼 보이려고 내용을 꾸민다.
  • GBAD 알고리즘을 이용하면 unsupervised 방법으로 최대한 정상에 가까운 비정상 패턴을 잘 찾아 낼 수 있다.
  • 해당 논문은 SUBDUE 시스템과 GBAD 알고리즘 3가지인 GBAD-MDL, GBAD-MPS, GBAD-P를 가지고 e-mail, business process, cybercrime에 탐지를 돌렸을 때 비정상이 잘 찾아진다는 내용이다.

Abstract

이 논문은 그래프 기반의 접근법을 통해 내부직원의 활동으로 부터 이상한 인스턴스(그래프 구조)를 탐지하는 것이다. 이 접근법은 normal transaction으로 취급은 되지만 실제로는 구조적으로 다른 활동을 감지하는 것이다. 논문에서는 e-mail, business process, cybercrime 데이터를 통해 이 접근법이 의심스러운 활동을 얼마나 탐지하는지 다룬다. 그리고 나서 앞으로 할 일인 dynamic 그래프와 frequent subgraph miner에서의 그래프 기반의 비정상 탐지 알고리즘에 대해 언급한다.

Introduction

비도덕적인 행동에 대한 데이터 마이닝은 쉽지가 않은데 이유는 가해자의 모방 때문이다. 만약 사람이나 객체가 불법적인 행동을 하려고 마음을 먹는다면 그들은 최대한 행동이 합법적으로 보일수 있는 방법을 조사해서 이 방법대로 시도하기 때문이다. 사이버 범죄는 앞으로 더더욱 회사 내부의 데이터와 리소스에 있어 위협이 되어가고 있다. (내부자의 위협에 대한 탐지가 점점 중요해진다는 당위성을 말하는 듯 하다.) 최근 몇년동안 기업들은 그들의 IT 활동과 프로세스를 분석하여 내부자의 어뷰징이나 사이버범죄를 찾아내고자 노력하고 있다. 대부분의 접근법은 통계 기반이나 마이닝 또는 그들의 리소스의 시각화를 통해 불법적인 접근이나 시도를 모니터링하려 한다. 하지만, 최근에는 어뷰징의 구조적 패턴을 찾아내기 위해 관계형 데이터를 마이닝 하는게 중요해 지고 있다. 다양한 복잡한 데이터셋의 특성은(network traffic, email, payroll 등) 잠재적으로 데이터 간에 관계를 가지거나 서로 연결되어 있을 가능성이 있다는 것이다. 따라서 이런 복잡한 데이터에 잠재되어 있을수 있는 어뷰징의 가능성은 그래프 기반의 비정상 탐지 기법으로 찾아 질 수 있다.

Related network

내부자의 위협과 관련된 많은 정보는 사고와 관련된 다양한 엔티티들의 관계에 내포되어 있다. NOBEL and COOK은 SUBDUE 시스템을 이용하여 비정상 부분구조와 그래프를 찾아냈다. 비정상 구조 탐지는 전체 그래프에서 발견되는 비정상 부분 구조를 찾아내는 것이다. 비정상 부분그래프를 찾아내는 아이디어는 흔한 부분 그래프를 많이 포함하는 부분 그래프는 흔한 그래프를 거의 포함하지 않는 부분 그래프 대비 일반적으로 더 정상에 가깝다는 것이다. 논문에서는 이후에는 다양한 비정상 탐지 시도법에 대해 다루고 있으니 필요할 때 찾아보자. 그래프 기반 비정상 탐지의 장점은 단지 각 데이터의 비정상 뿐만 아니라 엔티티 간의 관계가 분석될 수 있다는 것이다. 이를 통해 다양하고 복잡한 데이터에서 구조적 특이성을 찾아낼 수 있다는 것을 장점으로 얘기하고 있다.

Graph Based Anomaly Detection(GBAD)

논문에서 다루는 이 GBAD 접근법의 아이디어는 전체 그래프에서 MDL에 해당하는 정상 패턴을 찾고 이를 통해 비정상 부분구조의 그래프를 찾는 것이다.

정의 : 만약 그래프의 정상 부분구조 S에 비해서 그래프의 부분구조 S’가 X% 미만으로 일치하면 비정상이라고 정의한다. X는 S대비 vertex나 edge가 변형이 일어나는 퍼센트를 의미한다.

위의 가설 및 알고리즘이 의미가 있는 것은 미국의 마약과 범죄와 관련된 기관에서 발표하길 더욱 성공적인 돈세탁은 합법적은 돈 거래를 최대한 가깝게 모방하는 것으로 이를 통해 발각될 가능성을 줄이는 것이라고 발표했다. (필자의 의견으로도 실제 어뷰징은 실제의 정상 행동을 최대한 모사하는 것은 맞는 것 같다.) GBAD는 unsupervised 접근법으로써 SUBDUE 시스템을 이용한다. greedy beam search와 MDL을 활용하여 GBAD의 3가지 알고리즘은 SUBDUE를 활용하여 각각의 정상 패턴의 부분 그래프를 찾아낸다. 여기서 계속 언급되는 MDL은 아래와 같이 정의 될 수 있다.

$$ M(S,G) = DL(G|S) + DL(S) $$

G는 전체 그래프를 의미하고 S는 부분 그래프를 의미한다. $DL(G|S)$는 S로 압축되고 나서의 G의 description length이다. DL(S)는 부분 구조의 description length이다. 어뷰징은 다시 부분 그래프에 추가/수정/삭제가 일어나는 3가지 카테고리의 비정상으로 나눌수 있다. 또한 논문에서는 GBAD-MDL, GBAD-P, GBAD-MPS 3가지 알고리즘을 다루는데 자세한 알고리즘에 대한 정보는 Anomaly detection in data represented as graphs 논문을 참고한다.

Experiments With GBAD

A. E-mail correspondences

우선 데이터셋은 내부자들의 분식회계로 망한 회사인 ENRON의 이메일 데이터셋을 이용하여 GBAD 알고리즘이 비정상을 탐지 할 수 있는지 실험한다.

기본적인 그래프의 구성은 아래와 같이 발신자 직책, 수신자 직책, 원본/답장/포워딩 여부, 수신인/참조자 여부, mid 으로 구성되어 있다.

각 GBAD 알고리즘은 다른 구조적 비정상을 발견하였다. 재미있는 점은 많은 이메일이 팀장 -> 팀원으로의 메일이 발견되었으나 아래와 같이 팀장 -> 팀원 -> 다른 팀원으로 흔치 않은 패턴이 비정상으로 탐지되었다. 추가적으로, trader라는 직책자 -> CEO, trader 직책자 -> President 에게 메일을 보낸 정확이 비정상으로 탐지되었다.

B. Business Process

Business Process에서의 GBAD의 효과를 확인하기 위해 여권 발급 프로세스를 시나리오로 세워 일부의 어뷰징 가능성을 실험하였다. 이를 통해 실제 환경에서의 GBAD의 효용성을 증명하고자 한다.

우선 여권 발급 프로세스는 아래와 같다. 더 자세한 프로세스는 아래에 STEP을 첨부한다.

  1. 신청자는 구청에서 창구 직원에게 여권을 신청한다.
  2. 창구 직원은 정부 db에 신청건을 생성하고 이를 승인을 담당하는 공무원에게 전송한다.
  3. 승인 담당 공무원은 해당건을 db에서 확인하고 이를 심사 담당 공무원 중 한명에게 전달한다. 기본적으로 특정 여권 심사에는 3명의 심사 담당 공무원이 존재한다.
  4. 할당된 심사 담당 공무원이 신청건을 리뷰한다. 심사 담당 공무원이 추가 자료를 요청하면 이게 창구 직원에게 전송되고 창구직원 -> 승인담당 공무원을 거쳐 정보를 다시 받게 된다. 할당된 심사 담당 공무원은 새로운 정보를 db에 업데이트 한다. 할당된 심사 담당 공무원은 해당 신청건을 1명이상의 다른 심사 담당 공무원과 의논 할 수 있다. 끝으로 할당된 심사 담당 공무원은 여권을 승인을 권고하거나 거절을 권고한다. 이 결정이 db에 기록되고나서 승인 담당 공무원에게 전달 된다.
  5. 결과를 수신한 승인 담당 공무원은 최종 승인이나 거절을 결정한다. 이 결정이 db에 기록되고 창구직원과 신청자에게 동시에 전송된다.
  6. 마지막으로 결과를 전달받은 창구 직원이 그 결과를 db에 기록한다.

위의 프로세스를 어뷰징 할 수 있는 몇가지 시나리오를 정하고 이를 GBAD 알고리즘으로 검출 가능한지 알아보려 한다.

  1. 창구 직원이 db의 신청건을 리뷰하려 한다.
  2. 창구 직원이 승인 담당 공무원을 건너뛰고 직접 신청건을 심사 담당 공무원에게 전달한다.
  3. 창구 직원이 신청건의 승인여부를 권고하거나 결정한다.
  4. 승인 담당 공무원이 할당된 심사 담당 공무원의 권고사항을 무시하고 승인/거절을 한다.
  5. 할당되지 않은 심사 담당 공무원이 신청건 내용을 업데이트 하거나 승인권고를 대행해버린다.
  6. 신청자가 창구 직원을 거치지 않고 직접 승인 담당 공무원이나 심사 담당 공무원과 커뮤니케이션 한다.
  7. 할당되지 않은 심사 담당 공무원이 관여한다.
  8. 관련자 밖의 사람이 db에 접근해서 내용을 조회한다.

이에 대한 GBAD 알고리즘을 돌린 결과는 아래와 같다.

  • 시나리오 1,3,6은 GBAD-P로 검출
  • 시나리오 2는 GBAD-MPS로 검출
  • 시나리오 4는 GBAD-P로 검출
  • 시나리오 5는 GBAD-MPS, GBAD-P로 검출
  • 시나리오 7은 아래 그림에서 볼 수 있는 케이스로 GBAD-P로 검출
  • 시나리오 8은 GBAD-P로 검출

결론

GBAD 알고리즘을 e-mail, business process, 사이버범죄에 적용한 결과가 보여주는 것은 이런 그래프 이론에 기반한 접근법이 어떻게 비정상을 탐지하는데 쓰여질 수 있는지이다.