การวิเคราะห์กราฟอุปกรณ์: เชื่อมโยงจุดต่าง ๆ ข้ามเซสชัน

เมื่อผู้ฉ้อโกงคนเดียวควบคุมบัญชีหลายสิบบัญชี แต่ละบัญชีดูถูกต้องตามกฎหมายเมื่อพิจารณาแยกกัน แต่ละบัญชีมีอีเมลที่ไม่ซ้ำกัน มี IP address ที่ดูสมเหตุสมผล และมีรูปแบบการท่องเว็บที่สมจริง การตรวจจับด้วยกฎเกณฑ์แบบดั้งเดิมจะตรวจสอบแต่ละบัญชีอย่างอิสระและไม่พบสิ่งน่าสงสัย ความเชื่อมโยงระหว่างบัญชี — อุปกรณ์ที่ใช้ร่วมกัน เซสชันที่ทับซ้อนกัน network fingerprint ที่เหมือนกัน — มองไม่เห็นด้วยระบบที่ประมวลผลบัญชีทีละบัญชี

ทำไมต้องใช้กราฟ

การวิเคราะห์กราฟอุปกรณ์เปลี่ยนโมเดล แทนที่จะประเมินบัญชีแยกกัน เราสร้างกราฟที่โหนดคืออุปกรณ์ บัญชี IP address และเซสชัน และเอดจ์แทนความเชื่อมโยงที่สังเกตได้ เช่น "อุปกรณ์นี้ถูกใช้สร้างบัญชีนี้" "IP นี้ถูกพบพร้อมกับอุปกรณ์นี้" "สองบัญชีนี้ใช้ session cookie ร่วมกัน" กราฟเผยโครงสร้างที่ตารางแบบแบนราบไม่สามารถแสดงได้

แก๊งฉ้อโกงที่ใช้ 50 บัญชีบน 5 อุปกรณ์และ 3 IP address จะก่อตัวเป็นคลัสเตอร์ที่โดดเด่นในกราฟ ความหนาแน่นของคลัสเตอร์ — ความเชื่อมโยงจำนวนมากภายในกลุ่มโหนดขนาดเล็ก — เป็นสัญญาณที่ชัดเจน ผู้ใช้ที่ถูกต้องตามกฎหมายแทบไม่เคยใช้อุปกรณ์ร่วมกับคนแปลกหน้า และความเชื่อมโยงระหว่างบัญชีกับอุปกรณ์ของพวกเขาก่อตัวเป็นโครงสร้างที่กระจายบางคล้ายต้นไม้ ไม่ใช่คลัสเตอร์ที่หนาแน่น

สถาปัตยกรรมกราฟดาต้าเบส

เราใช้โมเดล property graph ที่มีโหนดสี่ประเภท ได้แก่ Device (ระบุด้วย visitor ID), Account (user ID ของคุณ), Network (IP address + ASN) และ Session (เหตุการณ์การระบุตัวตนแต่ละครั้ง) เอดจ์บรรจุ metadata ได้แก่ timestamp คะแนนความเชื่อมั่น และประเภทเหตุการณ์

กราฟถูกจัดเก็บใน adjacency index ที่สร้างขึ้นเฉพาะและปรับให้เหมาะกับการ traversal แบบ 2 hop เมื่อมีเหตุการณ์การระบุตัวตนใหม่เข้ามา เราจะแทรกเหตุการณ์นั้นเป็นโหนด Session เชื่อมต่อกับโหนด Device และ Network และตรวจสอบว่ามีโหนด Account ที่เชื่อมโยงใดมีความเชื่อมโยงไปยังอุปกรณ์อื่นหรือไม่ การดำเนินการแทรกและคิวรีนี้เสร็จภายในไม่เกิน 5ms สำหรับกราฟที่มีมากถึง 10 ล้านโหนด

จริง ๆ แล้วเราลอง Neo4j ก่อน มันทำงานได้ยอดเยี่ยมในสภาพแวดล้อมพัฒนาที่ 100K โหนด จากนั้นเราโหลดข้อมูลโปรดักชัน — 500M โหนด — และคิวรี Cypher ที่เคยใช้เวลา 2ms กลับใช้เวลา 800ms David ใช้เวลาหนึ่งสัปดาห์ในการเบนช์มาร์กทางเลือกต่าง ๆ ก่อนที่เราจะสร้าง adjacency index ของเราเองที่รองรับด้วย RocksDB แบบ sharded บางครั้งโซลูชันที่น่าเบื่อและปรับแต่งเองก็เอาชนะโซลูชันสำเร็จรูปที่หรูหราได้

อัลกอริทึมการทำคลัสเตอร์

เราใช้อัลกอริทึมการทำคลัสเตอร์สองแบบกับกราฟอุปกรณ์

Connected Components

วิธีที่ง่ายที่สุด: ค้นหาโหนดทั้งหมดที่เข้าถึงได้จากอุปกรณ์ที่กำหนด หาก Device A เชื่อมโยงกับ Account 1 และ Account 2 และ Device B ก็เชื่อมโยงกับ Account 2 ด้วย แล้ว Device A และ Device B ก็อยู่ใน connected component เดียวกัน วิธีนี้ระบุบัญชีทั้งหมดที่ใช้ความเชื่อมโยงอุปกรณ์แบบ transitive ร่วมกัน

Connected components คำนวณได้รวดเร็วแต่อาจสร้างคลัสเตอร์ขนาดใหญ่มากเมื่ออุปกรณ์ที่ใช้ร่วมกันโดยชอบธรรม (คอมพิวเตอร์ในครอบครัว เครื่องในห้องสมุด) สร้างสะพานเชื่อมระหว่างบัญชีที่ไม่เกี่ยวข้องกัน เราแก้ปัญหานี้ด้วยการถ่วงน้ำหนักเอดจ์ — ความเชื่อมโยงผ่านสภาพแวดล้อมที่ทราบว่าใช้ร่วมกันจะได้น้ำหนักที่ต่ำกว่า

Community Detection

สำหรับการวิเคราะห์ที่ละเอียดขึ้น เรารัน Louvain community detection บนกราฟที่ถ่วงน้ำหนักแล้ว อัลกอริทึมนี้แบ่งกราฟออกเป็นคอมมิวนิตี้ที่ความเชื่อมโยงภายในคอมมิวนิตี้หนาแน่นและความเชื่อมโยงระหว่างคอมมิวนิตี้กระจายบาง แก๊งฉ้อโกงก่อตัวเป็นคอมมิวนิตี้ที่แน่นหนาแม้จะเชื่อมโยงกับกราฟที่กว้างขึ้นผ่านโครงสร้างพื้นฐานที่ใช้ร่วมกัน

อัลกอริทึม Louvain ทำงานในเวลา O(n log n) ทำให้ใช้งานได้จริงกับกราฟที่มีโหนดหลายล้านโหนด เรารันแบบ incremental — เมื่อมีการเพิ่มเอดจ์ใหม่ เราจะอัปเดตการกำหนดคอมมิวนิตี้เฉพาะจุดแทนที่จะคำนวณการแบ่งพาร์ทิชันทั้งหมดใหม่

รูปแบบในโลกจริง: การตรวจจับแก๊งฉ้อโกง

แพลตฟอร์มเกมหนึ่งได้ผสานรวม API กราฟอุปกรณ์ของเราเพื่อตรวจจับแก๊งฉ้อโกงที่จัดตั้งขึ้น ภายในสัปดาห์แรก กราฟเผยคลัสเตอร์ของ 127 บัญชีที่เชื่อมโยงกันผ่าน 8 อุปกรณ์และ 4 IP address บัญชีเหล่านี้ถูกสร้างขึ้นในช่วงเวลา 3 เดือน แต่ละบัญชีมีอีเมลที่ไม่ซ้ำกันและโปรไฟล์ที่สมจริง การตรวจจับด้วยกฎเกณฑ์ไม่ได้แจ้งเตือนแม้แต่บัญชีเดียว

โครงสร้างกราฟคือสิ่งที่เผยความจริง: 127 บัญชีที่ใช้ 8 อุปกรณ์ร่วมกันให้ค่าเฉลี่ย 15.8 บัญชีต่ออุปกรณ์ ผู้ใช้ที่ถูกต้องตามกฎหมายมีค่าเฉลี่ย 1.2 บัญชีต่ออุปกรณ์บนแพลตฟอร์มนี้ ความหนาแน่นของคลัสเตอร์สูงกว่าค่าฐาน 47 เท่า — เป็นสัญญาณฉ้อโกงที่ชัดเจนไม่มีข้อกังขา

ประสิทธิภาพในระดับสเกลใหญ่

กราฟอุปกรณ์โปรดักชันของเรารองรับ 2.3 พันล้านโหนดและ 8.1 พันล้านเอดจ์ Insert latency อยู่ที่ 2.4ms ที่ p99 Two-hop traversal (ค้นหาบัญชีทั้งหมดที่เชื่อมโยงกับอุปกรณ์ผ่านเส้นทางความยาว 2 ใด ๆ) เสร็จใน 4.1ms ที่ p99 การอัปเดต community detection ประมวลผลเอดจ์ใหม่ 50,000 เอดจ์ต่อวินาที

กราฟถูก shard ตาม hash ของ device ID กระจายไปยัง 12 โหนด โดยแต่ละ shard เก็บประมาณ 190 ล้านโหนด replication factor เท่ากับ 3 รับประกันความพร้อมใช้งาน เราทำ snapshot กราฟทุกชั่วโมงเพื่อการกู้คืนจากภัยพิบัติ และรันการคำนวณ community detection ใหม่ทั้งหมดทุกวันเป็นการตรวจสอบความสอดคล้องเทียบกับการอัปเดตแบบ incremental

การผสานรวม

กราฟอุปกรณ์เข้าถึงได้ผ่านสองอินเทอร์เฟซ ได้แก่ real-time query API สำหรับการค้นหาแต่ละรายการ (อุปกรณ์นี้เชื่อมโยงกับบัญชีอื่นหรือไม่?) และ batch export API สำหรับการวิเคราะห์ (ขอคลัสเตอร์ทั้งหมดที่มีมากกว่า N บัญชี) real-time API ถูกออกแบบมาสำหรับการตัดสินใจเรื่องฉ้อโกงแบบ inline — คิวรีระหว่างการสร้างบัญชีเพื่อตรวจสอบว่าอุปกรณ์นั้นเคยพบบัญชีอื่นหรือไม่ ส่วน batch API ป้อนข้อมูลให้กับกระบวนการสืบสวนของทีมข้อมูลของคุณ