# TOAR: Toward Resisting AS-Level Adversary Correlation Attacks Optimal Anonymous Routing
## 3 System Model
### Optimal Anonymous Routing Problem  
The inter-domain optimal routing problem is defined based on the modeling of inter-domain routing in the previous section. Problem of inter-domain optimal routing: For an inter-domain network \(G=(V,E)\), where \(e(r)\), \(c(r)\), and \(d(r)\) denote the exit policy, price policy, and security policy, respectively; \(f(r)\) is the global objective function \(B_{max}\) is the threshold to satisfy the price policy; and \(D_{max}\) is the threshold to satisfy the security of the path strategy, the optimal route \(r^{*}\) from the source AS \(S\) to the destination AS \(D\), as defined in Equations (8) and (9), is the solution of the following optimization problem. \[maxmize\ f(r)Subject\ to \tag{7}\]  
\[v_{1}^{S\to R_{1}}=v_{|r_{l+1}^{R_{1}\to S}}^{R_{1}\to S}=S \tag{8}\]  
\[v_{|r_{l+1}^{f}|}^{R_{l}\to D}=v_{1}^{D\to R_{l}}=D \tag{9}\]  
\[e(r)=1 \tag{10}\]  
\[d(r)\leq D_{max} \tag{11}\]  
\[c(r)\leq B_{max} \tag{12}\]  
The objective function \(f(r)\) returns a real number that represents the objective of the inter-domain route \(r\). Specifically, \(f(r)\) is the inverse of the AS routing length, including the weighted exit policy, price strategy, and security policy. This is expressed by the Equation (13) as follows. \[f(r)=\frac{e(r)}{|r|\cdot d(r)\cdot c(r)} \tag{13}\]Finding the shortest path that satisfies the constraints over a number of segments--in this case, four segments, where none of the paths are deterministic--may result in each individual path not being the optimal path. However, the combination of these paths can result in an optimal path that satisfies the constraints. Determining the number k, which specifies how many duplicate vertices should be removed and in which segment of the path they should be removed, is a problem of combining segments to produce optimal routes when the pricing strategy is also considered. The naive algorithm involves listing a subset of all path segments of \(\{V-k\}\) and examining each one, and the algorithm runs in super-polynomial time when \(k\) is close to \(V/2\) in general time, so for this problem, it is difficult to find a polynomial time optimal solution. The 3-CNF-SAT problem (3-Conjunctive Normal Form Satisfiability Problem) is known to be an NPC (Nondeterministic Polynomial Complete) problem, and if the optimal routing problem is reformulated as a determination problem, which is a simplification of the optimal solution problem, then by reducing the 3-CNF-SAT problem to the optimal routing decision problem and proving that the problem is NP-hard, we can prove that our optimal routing problem is NP-hard. The optimal AS routing problem that satisfies the policy constraints is reformulated. Given an inter-domain network \(G=(V,E)\), is it possible to find a route \(r\) from the source \(AS_{S}\) to the destination \(AS_{D}\), such that the following conditions are met:  
* The AS path length of route \(r\) does not exceed \(\eta\). * Each AS traversed by route \(r\) complies with the export policy. * Route \(r\) adheres to the pricing policy, with a total cost less than \(B_{max}\). * Route \(r\) follows the security policy and does not traverse the same AS more than once. To prove that it is NP-hard, first consider an instance of the 3-CNF SAT problem with \(n\) clauses, such as \(\{C_{1},C_{2},\ldots,C_{n}\}\). Let \(x_{ij}\) represent the \(j\)-th variable in the \(i\)-th clause, where \(j=1,2,3\). This is denoted as Equation (14). \[\varphi=(x_{11}\cup x_{12}\cup x_{13})\cap(x_{21}\cup x_{22}\cup x_{23})\cap \ldots\cap(x_{n1}\cup x_{n2}\cup x_{n3}) \tag{14}\]  
For each clause, construct a graph \(G_{i}=(V_{i},E_{i})\), where \(V_{i}=\{s_{i},v_{i1},v_{i2},v_{i3},t_{i}\}\), \(E_{i}=\left\{\left(s_{i},v_{ij}\right),\left(v_{ij},t_{i}\right)\middle|j=1,2, 3\right\}\).