# TOAR: Toward Resisting AS-Level Adversary Correlation Attacks Optimal Anonymous Routing
## 4 Design of TOAR
### First Stage Algorithm for Simplified Security Policy Function  
The first stage searches for the shortest paths that satisfy the constraint that shared vertices are fewer than \(k_{max}\) by simplifying the security policy function in the algorithm. This is accomplished by ignoring the path lengths \(m\) and \(n\) and only considering the number of repetitive ASes \(k\) as in Equation (15). \[d\approx 1-(1-p)^{k},0\leq k\leq max[m,n] \tag{15}\]  
After simplification, \(d\) is bounded only by \(k\), and the value of \(d\) grows as \(k\) grows. Specifically, a larger \(k\) means that the route segment has more shared nodes, and thus, the whole circuit is more likely to be compromised. The algorithm determines the threshold \(k_{max}\) to be used by the user and filters the routes that satisfy the security policy. A smaller \(k_{max}\) threshold means that the user chooses a stronger security policy and vice versa, and a larger \(k_{max}\) means a weaker security policy. Specifically, define the set \(R_{F}\) satisfying the \(k_{max}\) constraints, which is initially empty, and use the Policy-Compliance Shortest Routing Algorithm [19] to obtain the four shortest paths that satisfy the policy: \(r_{1}^{f},r_{l+1}^{f},r_{1}^{b},r_{l+1}^{b}\). Take the computed \(r=r_{1}^{f}\oplus r_{l+1}^{f}\oplus r_{1}^{b}\oplus r_{l+1}^{b}\) as the a priori of the whole black-box optimization problem, and then use it as the basis to carry out path sampling in the approximate global search space. First, the two shortest paths, \(r_{1}^{f}\) and \(r_{l+1}^{b}\), are taken as two segments in the final path. Then, we search for new paths of \(r_{1}^{f}\) and \(r_{l+1}^{b}\) segments that satisfy the requirement that the shared nodes with the paths of \(r_{l+1}^{f}\) and \(r_{1}^{b}\) segments are fewer than \(k_{max}\). Specifically, take \(m-k_{max}\) vertices from the \(m\) vertices of the set \(V_{r_{1}^{f}}\cup V_{r_{l+1}^{b}}\) each time and label the order of the set consisting of these points as \(V_{i}^{M}\). Find the shortest path that matches the strategy, add it to the set \(R_{F}\), and update \(R_{F}\). Then, use the shortest paths, \(V_{r_{l+1}^{f}}\) and \(V_{r_{1}^{b}}\), as two segments in the determined final path, and search for new \(r_{l+1}^{f}\) and \(r_{1}^{b}\) segment paths that satisfy the requirement that the vertices shared with the \(r_{1}^{f}\) and \(r_{l+1}^{b}\) segments paths are fewer than \(k_{max}\). One at a time, from the \(V_{r_{l+1}^{f}}\cup V_{r_{1}^{b}}\) set of \(n\) nodes set to take \(n-k_{max}\) vertices, label the order of the set composed of these points as \(V_{i}^{N}\), find the shortest path that meets the policy, add it to the \(R_{F}\) set, and update \(R_{F}\). Finally, return the shortest path in \(R_{F}\), as in the search algorithm in Algorithm 1. If providing anonymity services is considered to require path diversity properties for routes, \(R_{F}\) may provide pools of alternative paths. This is because information about route lengths may degrade anonymity if routing protocols always choose the shortest route. If the autonomous domain policy is not considered, i.e., the symmetric routing scenario, [PERSON]'s algorithm or [PERSON]'s algorithm can be indirectly used instead of the policy-compliance shortest routing algorithm. The symmetric routing scenario can be used as a special case of Algorithm 1. For example, in the case of LAP [20], symmetric routing is used, where each AS along the route adds the encrypted path to the packet. During the path establishment phase, as the packet is forwarded, the complete encrypted path is generated. The receiver host then uses the complete encrypted path carried by the arriving packet to return an answer. When the number of shared vertices \(k\leq k_{max}\), the algorithm can return early; otherwise, the complexity is based on the complexity of the PCSR algorithm referenced in Algorithm 1. Specifically, in the worst case, it needs to enumerate all the possible routes, and the complexity is \(O(V!