디바이스 그래프 분석: 세션 간 점들을 연결하기
그래프 데이터베이스가 디바이스 간 숨겨진 연결을 드러내어, 대규모 환경에서 다중 계정 탐지와 사기 조직 식별을 가능하게 하는 방법.
한 명의 사기꾼이 수십 개의 계정을 운영할 때, 개별 계정들은 따로 놓고 보면 정상적으로 보인다. 각각 고유한 이메일, 그럴듯한 IP 주소, 현실적인 브라우징 패턴을 가지고 있다. 전통적인 규칙 기반 탐지는 각 계정을 독립적으로 검사하며 아무런 의심 징후도 발견하지 못한다. 계정들 사이의 연결 — 공유된 디바이스, 겹치는 세션, 공통 네트워크 핑거프린트 — 은 계정을 하나씩 처리하는 시스템에는 보이지 않는다.
왜 그래프인가
디바이스 그래프 분석은 이 모델을 바꾼다. 계정을 독립적으로 평가하는 대신, 노드가 디바이스, 계정, IP 주소, 세션이고 엣지가 관찰된 연결을 나타내는 그래프를 구축한다. 예를 들어 "이 디바이스로 이 계정이 생성되었다", "이 IP가 이 디바이스와 함께 관찰되었다", "이 두 계정이 세션 쿠키를 공유했다" 같은 것이다. 그래프는 평평한 테이블로는 드러낼 수 없는 구조를 보여준다.
5개 디바이스와 3개 IP 주소에 걸쳐 50개 계정을 사용하는 사기 조직은 그래프에서 독특한 클러스터를 형성한다. 클러스터 밀도 — 소수의 노드 집단 내에 많은 연결이 존재하는 것 — 는 강력한 신호다. 정상 사용자는 낯선 사람과 디바이스를 공유하는 경우가 거의 없으며, 그들의 계정-디바이스 연결은 밀집한 클러스터가 아니라 희소한 트리 형태의 구조를 이룬다.
그래프 데이터베이스 아키텍처
우리는 네 가지 노드 유형을 가진 프로퍼티 그래프 모델을 사용한다. Device(방문자 ID로 식별), Account(귀사의 사용자 ID), Network(IP 주소 + ASN), Session(개별 식별 이벤트)이다. 엣지는 메타데이터를 담는다. 타임스탬프, 신뢰도 점수, 이벤트 유형이다.
그래프는 2홉 순회에 최적화된 전용 인접 인덱스에 저장된다. 새로운 식별 이벤트가 도착하면, 이벤트를 Session 노드로 삽입하고, 이를 Device 및 Network 노드에 연결하며, 연결된 Account가 다른 디바이스와 연결이 있는지 확인한다. 이 삽입-및-쿼리 작업은 최대 1천만 노드 규모의 그래프에서 5ms 미만으로 완료된다.
사실 우리는 처음에 Neo4j를 시도했다. 개발 환경에서 10만 노드로는 훌륭하게 작동했다. 그런 다음 프로덕션 데이터 — 5억 노드 — 를 로드했더니, 2ms가 걸리던 Cypher 쿼리가 800ms를 잡아먹기 시작했다. David는 자체 인접 인덱스를 샤딩된 RocksDB 기반으로 구축하기 전에 일주일 동안 대안들을 벤치마킹했다. 때로는 투박하고 직접 만든 해법이 우아한 기성품 해법을 이긴다.
클러스터링 알고리즘
우리는 디바이스 그래프에 두 가지 클러스터링 알고리즘을 적용한다.
연결 요소 (Connected Components)
가장 단순한 접근법이다. 주어진 디바이스에서 도달 가능한 모든 노드를 찾는다. Device A가 Account 1과 Account 2에 연결되어 있고 Device B도 Account 2에 연결되어 있다면, Device A와 B는 같은 연결 요소에 속한다. 이는 어떤 전이적 디바이스 연결이라도 공유하는 모든 계정을 식별한다.
연결 요소는 계산이 빠르지만, 정상적으로 공유되는 디바이스(가족 공용 컴퓨터, 도서관 단말기)가 서로 무관한 계정들 사이에 다리를 놓으면 매우 큰 클러스터를 만들어낼 수 있다. 우리는 이를 엣지 가중치로 해결한다 — 알려진 공유 환경을 통한 연결에는 더 낮은 가중치를 부여한다.
커뮤니티 탐지 (Community Detection)
보다 정교한 분석을 위해, 우리는 가중 그래프에 Louvain 커뮤니티 탐지를 실행한다. 이 알고리즘은 그래프를 커뮤니티들로 분할하는데, 커뮤니티 내부의 연결은 밀집하고 커뮤니티 간 연결은 희소하다. 사기 조직은 공유 인프라를 통해 더 넓은 그래프에 연결되어 있더라도 밀집한 커뮤니티를 형성한다.
Louvain 알고리즘은 O(n log n) 시간에 실행되어, 수백만 노드 규모의 그래프에도 실용적이다. 우리는 이를 증분 방식으로 실행한다 — 새로운 엣지가 추가되면, 전체 분할을 다시 계산하는 대신 커뮤니티 할당을 국소적으로 갱신한다.
실제 패턴: 사기 조직 탐지
한 게임 플랫폼이 조직적인 사기 조직을 탐지하기 위해 우리 디바이스 그래프 API를 통합했다. 첫 주 만에 그래프는 8개 디바이스와 4개 IP 주소를 통해 연결된 127개 계정의 클러스터를 드러냈다. 이 계정들은 3개월에 걸쳐 생성되었으며, 각각 고유한 이메일과 현실적인 프로필을 가지고 있었다. 규칙 기반 탐지는 이 중 하나도 잡아내지 못했다.
정체를 드러낸 것은 그래프 구조였다. 8개 디바이스를 공유하는 127개 계정은 디바이스당 평균 15.8개 계정을 만들어낸다. 이 플랫폼에서 정상 사용자는 디바이스당 평균 1.2개 계정이다. 클러스터 밀도는 기준선의 47배였다 — 명백한 사기 신호다.
대규모 환경에서의 성능
우리 프로덕션 디바이스 그래프는 23억 노드와 81억 엣지를 처리한다. 삽입 지연은 p99에서 2.4ms다. 2홉 순회(길이 2의 어떤 경로로든 디바이스에 연결된 모든 계정 찾기)는 p99에서 4.1ms에 완료된다. 커뮤니티 탐지 갱신은 초당 5만 개의 새로운 엣지를 처리한다.
그래프는 디바이스 ID 해시로 12개 노드에 걸쳐 샤딩되며, 각 샤드는 약 1억 9천만 노드를 보유한다. 복제 계수 3으로 가용성을 보장한다. 우리는 재해 복구를 위해 그래프를 매시간 스냅샷하고, 증분 갱신에 대한 일관성 검사로 전체 커뮤니티 탐지 재계산을 매일 실행한다.
통합
디바이스 그래프는 두 가지 인터페이스를 통해 접근할 수 있다. 개별 조회를 위한 실시간 쿼리 API(이 디바이스가 다른 계정들과 연결되어 있는가?)와 분석을 위한 배치 내보내기 API(N개 이상의 계정을 가진 모든 클러스터를 달라)다. 실시간 API는 인라인 사기 판정을 위해 설계되었다 — 계정 생성 중에 쿼리하여 해당 디바이스가 다른 계정들을 본 적이 있는지 확인한다. 배치 API는 귀사 데이터 팀의 조사 워크플로에 데이터를 공급한다.