---
# System prepended metadata

title: 'DRAGON: Detection of Related Account Groups for Online services with uncertain graphs'

---

# DRAGON: Detection of Related Account Groups for Online services with uncertain graphs

### Purpose of this study
Use DRAGON to detect suspicious groups.
### Backgrounds
Existing methods usually focus on the **behavior level** (association bases on their behaviors using services). While this study focuses on **identity level** (relationship between service account and physical world).
### The structure of DRAGON
1. Using **web tracking** to track visitors. Three approaches are introduced:
    * HTTP cookie
        * Store in user's browser.
        * Can be cleared or using incognito mode.
    * IP Address
        * Stateless (not store in user's device).
        * 87% user reusing at least one IP over a month.
    * browser fringerprinting
        * Collect device information.
        * Reveal OS, hardware version, or geolocation.
2. **Modeling a bipartite graph** between physical devices and service accounts.
    * $e(M,N)$ is added in the graph if an identifier $M$ appears when the account $N$ is signed in.
    * Unweighted: the times it signs in are ignored.
3. Project the bipartite graph into an **uncertain graph**.
    * An **unvertain graph** $\mathcal{G}$ is a graph with a probability function $p:e\rightarrow (0,1]$ $\forall e\in \mathcal{E}(\mathcal{G})$. Note that the probability of each edge are independent.
    *  The **Identity Degree** $n$ is the number of common identifiers they share with each other given any two accounts.
    *  The **Coincident identifier probability** $q$ is the probability that one identifier originates from different devices.
    *  We can now construct an uncertain graph $\mathcal{G}=(\mathcal{V},\mathcal{E},p)$ by the Bipartite gragh $\mathcal{B}(M,N,E)$:
        * $\mathcal{V} = N$.
        * $\mathcal{E} = \{(x,y)|x,y\in \mathcal{V}\}$.
        * $\forall e \in \mathcal{E}$, $p(e)=1-q^n$, where $n=|\{m\in M|e=(x,y), (m,x)\in E,(m,y)\in E\}|$.
4. Clipping at low identity degree
    * Set a **clipping threshold $n_{clip}$.**
    * Replace $p$ by $p(e)=(1-q^n)[n>n_{clip}]$.
5. **Cluster** the uncertain graph
    * Uncertain graph clustering algorithm(better).
    * Markov clustering algorithm.
6. Detecting suspicious account groups
    * A tendency: malicious groups usually use more device to manipulate a set of accounts than normal people do.
    * The **Expected Account Relation Ratio (EAR)** is the expected ratio of the number of edge existence to the number of all edges in the community:
    $$\displaystyle EAR = \sum_{G_i\subseteq\mathcal{G_c}}Pr(G_i)\cdot\frac{|E_i|}{|\mathcal{E}|} = \sum_{e\in \mathcal{E}}\frac{p(e)}{|\mathcal{E}|},$$
    where $|\mathcal{E}|$ denotes the edge number in the uncertain graph $\mathcal{G_c}$ and $|E_i|$ stands for the edge number in a possible world $G_i$. The second equation due to the independency of edges.
    * A thershold of EAR can then be used to determine whether an account group is suspicious.
### Real-world evaluation of  DRAGON
1. Real-world Dataset
    * 220 thousand login records collected for six months.
    * Each of the login records contains an anonymized account id and a User-Agent request header.
    * Only $0.2\%$ accounts are marked as malicious ones.
2. Approoaches
    * Set $q = 0.6$ since around 60% identifiers are found not unique in a dataset of a recent study.
    * Set $n_{clip}=1$ 
    * Set the threshold of EAR in DRAGON when it achieves the best F1 score. ($0.9$)
3. Result
    * V.S. binary classifier: DRAGON greatly reduces the false positives.
    * Providing precision-recall curves, we can also see DRAGON is better than binary classifier and $n_{clip} = 1$ brings the best performance.
    * DRAGON can discover not only suspicious accounts but also the relationships among these accounts.
4. Ablation studies
    * The importance of identifier-account relations is shown by replacing all edges with 220 thousand randomly generated ones. 
    * The performance of DRAGON without clipping is shown.
    * Results indicate UGC performs better than MCL in this task.

    







