Phân tích Device Graph: Kết nối các điểm mấu chốt xuyên suốt các phiên
Cách graph database phát lộ những kết nối ẩn giữa các thiết bị, cho phép phát hiện đa tài khoản và nhận diện đường dây gian lận ở quy mô lớn.
Khi một kẻ gian lận đơn lẻ vận hành hàng chục tài khoản, từng tài khoản riêng lẻ trông đều hợp pháp. Mỗi tài khoản có một email riêng, một địa chỉ IP hợp lý, các mẫu duyệt web thực tế. Phát hiện dựa trên luật truyền thống kiểm tra từng tài khoản một cách độc lập và chẳng thấy gì đáng ngờ. Những kết nối giữa các tài khoản — thiết bị dùng chung, các phiên chồng lấn, dấu vân tay mạng chung — là vô hình đối với các hệ thống xử lý từng tài khoản một.
Vì sao dùng Graph
Phân tích device graph thay đổi mô hình. Thay vì đánh giá các tài khoản một cách độc lập, chúng tôi xây một graph trong đó node là thiết bị, tài khoản, địa chỉ IP và phiên, còn cạnh biểu diễn các kết nối được quan sát: "thiết bị này đã được dùng để tạo tài khoản này", "IP này được thấy đi kèm với thiết bị này", "hai tài khoản này dùng chung một session cookie". Graph phát lộ cấu trúc mà các bảng phẳng không thể.
Một đường dây gian lận dùng 50 tài khoản trải trên 5 thiết bị và 3 địa chỉ IP tạo thành một cụm đặc trưng trong graph. Mật độ cụm — nhiều kết nối trong một nhóm nhỏ các node — là một tín hiệu mạnh. Người dùng hợp pháp hiếm khi dùng chung thiết bị với người lạ, và các kết nối tài khoản–thiết bị của họ tạo thành cấu trúc thưa thớt, dạng cây chứ không phải cụm dày đặc.
Kiến trúc Graph Database
Chúng tôi dùng mô hình property graph với bốn loại node: Device (định danh bằng visitor ID), Account (user ID của bạn), Network (địa chỉ IP + ASN) và Session (sự kiện định danh riêng lẻ). Các cạnh mang metadata: dấu thời gian, điểm tin cậy và loại sự kiện.
Graph được lưu trong một adjacency index chuyên dụng, tối ưu cho các phép duyệt 2 bước. Khi một sự kiện định danh mới đến, chúng tôi chèn sự kiện đó dưới dạng node Session, kết nối nó với các node Device và Network, và kiểm tra xem có Account nào được liên kết đang có kết nối tới các thiết bị khác hay không. Thao tác chèn-và-truy-vấn này hoàn tất trong dưới 5ms đối với các graph có tới 10 triệu node.
Thực ra chúng tôi đã thử Neo4j trước tiên. Nó chạy rất tốt khi phát triển với 100K node. Rồi chúng tôi nạp dữ liệu production — 500M node — và những truy vấn Cypher vốn mất 2ms bắt đầu mất tới 800ms. David dành cả một tuần để đo hiệu năng các phương án thay thế trước khi chúng tôi tự xây adjacency index riêng dựa trên RocksDB phân mảnh. Đôi khi giải pháp buồn tẻ, tùy chỉnh lại thắng giải pháp thanh lịch có sẵn.
Các thuật toán phân cụm
Chúng tôi áp dụng hai thuật toán phân cụm lên device graph:
Connected Components
Cách tiếp cận đơn giản nhất: tìm mọi node có thể tới được từ một thiết bị cho trước. Nếu Device A kết nối với Account 1 và Account 2, và Device B cũng kết nối với Account 2, thì Device A và Device B nằm trong cùng một connected component. Điều này nhận diện mọi tài khoản có chung bất kỳ kết nối thiết bị bắc cầu nào.
Connected components tính nhanh nhưng có thể tạo ra những cụm rất lớn khi các thiết bị dùng chung hợp pháp (máy tính gia đình, máy ở thư viện) tạo cầu nối giữa các tài khoản không liên quan. Chúng tôi giải quyết điều này bằng gán trọng số cho cạnh — các kết nối qua những môi trường dùng chung đã biết sẽ nhận trọng số thấp hơn.
Community Detection
Để phân tích tinh tế hơn, chúng tôi chạy Louvain community detection trên graph có trọng số. Thuật toán này phân hoạch graph thành các cộng đồng, trong đó kết nối nội bộ cộng đồng thì dày đặc còn kết nối giữa các cộng đồng thì thưa thớt. Các đường dây gian lận tạo thành những cộng đồng chặt chẽ ngay cả khi được nối vào graph rộng hơn thông qua hạ tầng dùng chung.
Thuật toán Louvain chạy trong thời gian O(n log n), khiến nó khả thi với các graph hàng triệu node. Chúng tôi chạy nó theo kiểu tăng dần — khi có cạnh mới được thêm vào, chúng tôi cập nhật việc gán cộng đồng một cách cục bộ thay vì tính lại toàn bộ phân hoạch.
Mẫu hình thực tế: Phát hiện đường dây gian lận
Một nền tảng game đã tích hợp device graph API của chúng tôi để phát hiện các đường dây gian lận có tổ chức. Ngay trong tuần đầu tiên, graph đã phát lộ một cụm gồm 127 tài khoản nối với nhau qua 8 thiết bị và 4 địa chỉ IP. Các tài khoản được tạo trong khoảng 3 tháng, mỗi tài khoản có email riêng và hồ sơ thực tế. Phát hiện dựa trên luật đã bỏ sót toàn bộ chúng.
Cấu trúc graph chính là điểm lộ tẩy: 127 tài khoản dùng chung 8 thiết bị cho ra trung bình 15,8 tài khoản mỗi thiết bị. Người dùng hợp pháp trung bình chỉ 1,2 tài khoản mỗi thiết bị trên nền tảng này. Mật độ cụm cao gấp 47 lần mốc cơ sở — một tín hiệu gian lận không thể nhầm lẫn.
Hiệu năng ở quy mô lớn
Device graph production của chúng tôi xử lý 2,3 tỷ node và 8,1 tỷ cạnh. Độ trễ chèn là 2,4ms ở p99. Duyệt hai bước (tìm mọi tài khoản nối với một thiết bị qua bất kỳ đường đi độ dài 2 nào) hoàn tất trong 4,1ms ở p99. Các cập nhật community detection xử lý 50.000 cạnh mới mỗi giây.
Graph được phân mảnh theo hash của device ID trên 12 node, mỗi shard giữ khoảng 190 triệu node. Hệ số nhân bản là 3 đảm bảo tính sẵn sàng. Chúng tôi chụp snapshot graph theo giờ để khắc phục thảm họa và chạy tính lại toàn bộ community detection mỗi ngày như một phép kiểm tra nhất quán so với các cập nhật tăng dần.
Tích hợp
Device graph có thể truy cập qua hai giao diện: một query API thời gian thực cho các tra cứu riêng lẻ (thiết bị này có nối với các tài khoản khác không?) và một batch export API cho phân tích (đưa cho tôi mọi cụm có hơn N tài khoản). Real-time API được thiết kế cho các quyết định gian lận nội tuyến — truy vấn trong lúc tạo tài khoản để kiểm tra xem thiết bị đã từng thấy các tài khoản khác chưa. Batch API cung cấp dữ liệu cho các luồng công việc điều tra của nhóm dữ liệu của bạn.