# TOAR: Toward Resisting AS-Level Adversary Correlation Attacks Optimal Anonymous Routing
## 3 System Model
### Basic Definitions  
Using the abstraction that a routing node represents an AS domain, which is widely used in research [19], a routing model is formalized for inter-domain anonymous communication scenarios, as in Figure 2.  
Global Network: Use the graph \(G=(V,E)\) to represent a global network if a vertex, \(v\in V\), denotes that \(AS_{v}\) is in the network, and \(edge(u,v)\in E\) denotes that there is an inter-domain session between \(AS_{v}\) and \(AS_{u}\). Overlay Circuit: This represents an overlay anonymous circuit using a set of relay \((R\,,\ Relay)\) sequences \(AC=[R_{1},R_{2},\ldots,R_{l}]\), with \(l\) denoting the length of the anonymous circuit; for any integer \(i,j\in[1,l]\), if \(i\
eq j\), then \(R_{i}\
eq R_{j}\). \begin{table}
\begin{tabular}{c c} \hline \hline
**Notations** & **Definitions** \\ \hline \(G(V,E)\) & Global network \(G\), a directed graph with \(V\) vertices and \(E\) edges. \\ \(S\), \(D\) & Sender and destination. \\ \(|sym|\) & Route length, \(sym\) can be any symbol representing a route. \\ \(\{R_{i}\}\) & Overlay anonymous circuit \(AC=\{R_{i}|1\leq i\leq l\},l=|AC|\). \\ \(r_{i}^{f}\), \(r_{i}^{b}\) & Forward routing and backward routing \(1\leq i\leq l+1,1\leq j\leq l+1\). \\ \(\left\{v_{i}^{dir}\right\}\) & Simplified inter-routing \(r=\left\{v_{i}^{dir}\middle|1\leq i\leq\eta^{dir}\right\},\ \ \eta=|r|\) ; \(dir\) is direction. \\ \(p\) & The probability that each node in the global network \(G\) is attacked. \\ \(k\) & Number of repetitive nodes in \(r\). \\ \(k_{max}\) & Maximum number of shared nodes selected by the user. \\ \(m\) & Total number of nodes in routing segments \(r_{i}^{f}\) and \(r_{l+1}^{b}\). \\ \(n\) & Total number of nodes in routing segments \(r_{l+1}^{f}\) and \(r_{1}^{b}\). \\ \(d(k)\) & Simplified representation of \(d(p,k,m,n)\); the degree of path safety. \\ \(e(r)\) & Exit policy of \(r\); simplified representation of \(e_{v}(dp,r,u)\). \\ \(c(r)\) & Price policy of \(r\). \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Notations used. Inter-domain Routing: An inter-domain AS route \(r=\left[v_{1},v_{2},\ldots,v_{\eta}\right]\) is represented using a set of AS sequences, with \(\eta\) denoting the length of the underlay routing, and for any integer \(i,j\in[1,\eta],i\
eq j\), then \(v_{i}\
eq v_{j}\). For a given route \(r\), \(v_{1}\) denotes the source AS of the route and \(v_{\eta}\) denotes the destination AS of the route. For a given two-segment route \(r_{1}=\left[v_{1},v_{2},\ldots,v_{m}\right]\), \(r_{2}=\left[u_{1},u_{2},\ldots,u_{n}\right]\), if \(\left(v_{m},u_{1}\right)\in E\), and \(\forall i\in[1,m],\forall j\in[1,n]\), \(v_{i}\
eq u_{j}\), connect the two routes \(r_{1}\oplus r_{2}=\left[v_{1},v_{2},\ldots,v_{m},u_{1},u_{2},\ldots,u_{n}\right]\), which is also an inter-domain route. In conjunction with overlay circuits, and considering the asymmetry of Internet routing, \(r^{f}\) is used to denote the forward route from the sender to the destination, with \(r^{f}_{i}\) denoting the \(i\)th segment of it, and \(r^{b}\) denotes the return route from the destination to the sender, with \(r^{b}_{j}\) denoting the \(j\)th segment of it. Exit policy: The exit policy for inter-domain routing is modeled as a function \(e_{v}(dp,r,u)\) in Equation (1). \[e_{v}(dp,r,u)\triangleq\bigwedge_{i=1}^{\eta}e_{iv}(dp,\left[v_{i},v_{i+1}, \ldots,v_{\eta}\right],v_{i-1}) \tag{1}\]  
where \(e_{v}(dp,r,u)\) denotes the exit policy of each AS node. Assuming that the routing information is propagated from the destination AS towards the source AS, if \(AS_{v}\), according to its own exit policy, will advertise the route \(v\oplus r\) with the destination address prefixed with \(dp\) to its neighbor \(AS_{u}\), the function will return a value of 1. Otherwise, the return value is 0. Price strategy: The price strategy for inter-domain routing is modeled as a function \(c(r)\) in Equation (2). The function returns a real number representing the overhead of an inter-domain route.