key: cord-027178-tqj8jgem
authors: Tian, Changbo; Zhang, Yongzheng; Yin, Tao
title: Modeling of Anti-tracking Network Based on Convex-Polytope Topology
date: 2020-06-15
journal: Computational Science - ICCS 2020
DOI: 10.1007/978-3-030-50417-5_32
sha: 
doc_id: 27178
cord_uid: tqj8jgem

Anti-tracking network plays an important role in protection of network users’ identities and communication privacy. Confronted with the frequent network attacks or infiltration to anti-tracking network, a robust and destroy-resistant network topology is an important prerequisite to maintain the stability and security of anti-tracking network. From the aspects of network stability, network resilience and destroy-resistance, we propose the convex-polytope topology (CPT) applied in the anti-tracking network. CPT has three main advantages: (1) CPT can easily avoid the threat of key nodes and cut vertices to network structure; (2) Even the nodes could randomly join in or quit the network, CPT can easily keep the network topology in stable structure without the global view of network; (3) CPT can easily achieve the self-optimization of network topology. Anti-tracking network based on CPT can achieve the self-maintenance and self-optimization of its network topology. We compare CPT with other methods of topology optimization. From the experimental results, CPT has better robustness, resilience and destroy-resistance confronted with dynamically changed topology, and performs better in the efficiency of network self-optimization.

The rapid growth of Internet access has made communication privacy an increasingly important security requirement. And the low threshold and convenience of the techniques about network monitoring and tracing also have posed a great threat on the online privacy network users [1] [2] [3] . Anti-tracking network is proposed as the countermeasure to fight against the network monitoring and censorship [4] [5] [6] . So, the attacks on anti-tracking network increase rapidly in recent years, such as network paralysis, network infiltration, communication tracking and so on. Especially, for the P2P-based anti-tracking network which takes the advantage of the wide distribution of nodes for tracking-resistant communication, it is important to keep a stable, secure and destroy-resistant topology structure. Also, considered that the nodes in P2P-based anti-tracking network can join in or quit the network freely and randomly, it increases the uncertainty and insecurity for anti-tracking network to maintain a robust network topology.

Much research has been done regarding the management or optimization of network topology. But as for the aspect of anti-tracking network, current research have some limitations which are concluded as follows:

(1) The cost of network maintenance. Some of current research needs the global view of network to optimize the network topology [7] [8] [9] . Confronted with dynamically changed network topology, the cost of network maintenance would be very high. (2) Weak destroy-resistance. P2P-based anti-tracking network confronts not only the problem of communication tracing, but also the threats of network attacks [10] [11] [12] . Especially, the attack to cut vertices and key nodes will destroy the network structure tremendously. (3) Weak tracking-resistance. Network infiltration is another threat on the security of anti-tracking network [13] [14] [15] . Malicious nodes can be deployed in the network to measure the network topology and traceback the communication.

To address the above problems, we propose the convex-polytope topology (CPT) which can be applied in anti-tracking network. The anti-tracking network based on CPT achieves the self-optimization of its network. The novelty and advantages of our proposal are summarized as follows:

(1) We apply the convex-polytope topology in the anti-tracking network. The anti-tracking network based on CPT has better performance in network stability and resilience. (2) We propose a topology maintenance mechanism based on CPT. Each node in network only needs to maintain its local topology to keep the whole network in stable convex-polytope structure. (3) We propose a network self-optimization mechanism based on CPT. With the self-optimization mechanism, anti-tracking network can optimize its network topology as the network topology changes.

Convex-polytope topology (CPT) is a structured topology in which all nodes are constructed into the shape of convex-polytope, as illustrated in Fig. 1 . CPT has the following advantages to maintain the robust and destroy-resistant topology of anti-tracking network.

-Stability: The structure of CPT has the advantage in avoiding the cut vertices, except the extreme cases in which the connectivity of CPT is too sparse, such as ring structure. So, the maintenance of network topology is just to keep the convex-polytope structure. -Resilience: Confronted with the dynamically changed topology, each node in CPT only needs to maintain its local topology to accord with the properties of convex-polytope, then the whole network will be in the convex-polytope structure. -Self-optimization: The network stability, robustness and destroy-resistance benefit from the balanced distribution of nodes' connectivity. CPT can achieve the self-optimization of the whole network through the optimization of each node's local topology. 

Consider the topology structure of CPT illustrated in Fig. 1 , the whole network is constructed in a convex-polytope structure logically. To maintain this structure, each node has to record both of the neighbouring nodes and the corresponding surfaces in the convex-polytope.

Let v denotes a node, CN denotes its neighbouring node collection, and CS denotes its surface collection. We take the example of node v shown in Fig. 1 , then

So, if one neighbouring node of v disconnects, then node v knows which surfaces are affected by the lost neighbouring node, and adjusts its local topology accordingly.

As we can see from the Fig. 1 , each surface of convex-polytope can be different polygons. For a fixed number of nodes, if each surface has more edges, the connectivity of the whole network becomes more sparse. On the contrary, each surface has less edges, the connectivity of the whole network becomes more dense. If all surfaces have three edges, then the connectivity of the network reaches the maximum. So, in our work, we construct CPT of which each surface is triangle to provide better stability and resilience of anti-tracking network.

Assume there are n nodes to construct CPT with triangle surfaces, then the number of surfaces and edges in this kind of CPT is fixed. Theorem 1 gives the details about the calculation of the number of this CPT's surfaces and edges. Theorem 1. If a convex-polytope has n nodes, and each surface is triangle, then the number of surfaces and edges of this convex-polytope is fixed. The number of edges is: l = 3 × (n − 2), the number of surfaces is: m = 2 × (n − 2).

Proof. Because each surface of convex-polytope with n nodes is triangle, and each edge is shared by two surfaces, assume the number of edges is l, and the number of surfaces is m, then 3 × m = 2 × l. According to Euler Theorem of Polyhedron, we have the equation n + m − l = 2.

Even though CPT has the advantages in the maintenance of network topology, in some extreme cases shown in Fig. 2 , CPT still has the potential threat in topology structure, such as key nodes. Key nodes would have big influence on the stability, robustness and security of network topology. In the construction process of CPT, the balanced distribution of each node's connectivity is the priority to construct a stable and robust anti-tracking network. We propose the construction algorithm to construct a CPT with balanced distribution of nodes' connectivity. The construction algorithm takes two main steps shown as follows:

(1) Constructing a circuit: All nodes construct a circuit.

(2) Adding edges iteratively: Each node takes turns at selecting a node which has the span of 2 and allow new connections along with one direction of the circuit, and adding an edge with it to generate a triangle surface. If all surfaces of one node are triangles, it will refuse new connection with it in order to keep the whole topology in convex-polytope structure. After all nodes have triangle surfaces, the CPT with triangle surfaces has been constructed.

Input: C = [v1, v2, ..., vn]: node collection.

All nodes construct a circuit.

Get a node u which has the span of 2 with v. 6 :

if T he surfaces of v are all triangles then 8:

if N ≤ 0 then 11:

Break. 12: end if 13: end while Algorithm 1 gives the pseudocode for the construction algorithm of CPT. The time complexity of the construction algorithm mainly depends on the executions of the process of building node circuit (line 1) and while loop (line 3∼6). The time complexity of building node circuit is O(n). Because the edges of CPT is fixed which has been proved in Theorem 1, and the node circuit has formed n edges. Then, the while loop in Algorithm 1 only needs to be executed (2 × n − 6) times. So, the time complexity of Algorithm 1 is O(n).

To make straightforward sense of CPT construction algorithm, Fig. 3 illustrates the construction process of CPT with 9 nodes, labeled v 1 , v 2 , ..., v 9 . Firstly, these 9 nodes construct a circuit. We take v 1 as the first node to add an edge with v 3 , then v 1 has a triangle surface (v 1 , v 2 , v 3 ). Iteratively, v 2 adds an edge with v 4 , and v 3 adds an edge with v 5 , untill the surfaces of all nodes are triangles. In Fig. 3(f) , v 2 needs to select a node with the span of 2 to add an edge, there are three nodes, v 5 , v 6 , v 8 . Because all the surfaces of v 5 and v 8 are triangles, the extra edges may break the structure of convex-polytope. So, v 2 can only add an edge with v 6 .

As the nodes can join in or quit the anti-tracking network freely, the frequent change of network topology inevitably has a big influence on the stability and security of network structure. So, an effective maintenance mechanism of network topology guanrantees the robustness and usability of anti-tracking network. In this section, we will discuss the maintenance mechanism in which the relevant nodes only update its local topology to keep the anti-tracking network in convexpolytope structure when confronted with the dynamically changed topology.

In the maintenance mechanism of CPT, two cases are taken into consideration: that of the nodes join in the network and that of the nodes quit the network. 

. So, the node join of CPT only changes the topology of one surface. The whole topology can be easily maintained in the convex-polytope structure.

Nodes Quit CPT. If a node quits CPT, all the surfaces of this node will merge into one surface. If the quitting node has a high degree, CPT will generate a large surface which is detrimental to the stable and robust network topology.

For example, Fig. 5 (a) shows a node with degree of 3 quits CPT. When v 1 quits CPT, its three surfaces (v 2 , v 3 ), (v 2 , v 4 ) and (v 3 , v 4 ) merge into one surface which is still a triangle. In this case, CPT need no additional actions to maintain the topology. Fig. 5(b) , node v 1 with degree of 5 quits CPT, the surface generated by quitting v 1 is pentagon. In this case, the relevant nodes have to update its local topology to keep convex-polytope structure with all triangle surfaces. The maintenance process only exists in the nodes of the generated pentagon surface. Through the connection between these nodes, the pentagon surface can be divided into different triangle surfaces.

The maintenance of the generated pentagon surface is similiar with the construction algorithm of CPT. If all surfaces of a node are triangles, it will refuse any connections. Each node in the pentagon surface connects with a node which has the span of 2 and allow new connection iteratively until all nodes in this surface has triangle surfaces. For example shown in Fig. 5(b) , after v 1 quits CPT, v 2 firstly establishes a connection with v 5 to generate a triangle surface (v 3 , v 5 ).

Then v 3 has all triangle surfaces and refuse any connection with it. Next, v 5 establishes a connection with v 4 to generate a triangle. Then v 6 has all triangle surfaces and refuse any connections. At last, the maintenance of CPT is finished.

As we have discussed above, CPT can keep the network topology in the stable and resilient convex-polytope structure. But the convex-polytope structure still has some extreme cases shown in Fig. 2 which may pose a potential threat on the structure stability and communication efficiency of anti-tracking network because of the key nodes. According to the properties of CPT, we can achieve the self-optimization of anti-tracking network to balance the distribution of nodes' connectivity.

As we have mentioned in Theorem 1 that the number of edges in convexpolytope of which all surfaces are triangles is: l = 3 × (n − 2), and n denotes the number of the nodes. Then, we can calculate the average degree of CPT as shown in Eq. 2. When n is very large, the average degree of CPTd is close to 6. So, we usually set the upper limit of nodes' degree as 10 in CPT. The nodes of which the degree is bigger than 10 should adjust its local topology to reduce its connectivity. Every node in network has the ability to control its connectivity, then CPT has the ability to optimize the network topology. Theorem 1 has proved that the number of edges are fixed for a CPT of which all surfaces are triangles, if the degree of some nodes are reduced, the degree of other nodes should be increased to keep the convex-polytope structure. So, the self-optimization of CPT can be viewed as a transfer process of node degree from the high-degree nodes to the low-degree nodes. Assume that node v 0 has n neighbouring nodes which are labeled in sequence from v 1 to v n . Because all the neighbouring nodes of v 0 form a circuit, we use v i−1 and v i+1 respectively represent the adjacent nodes of v i in the node circuit. If node v 0 needs to reduce its degree, firstly node v 0 has to request for the degree d i of its each neighbouring node v i (1 ≤ i ≤ n). According to the degree of its neighbouring nodes, node v 0 selects a suitable neighbouring node to disconnect. To maintain the convex-polytope structure, the corresponding two neighbouring nodes of node v 0 have to connect with each other. As illustrated in Fig. 6 , node v 0 disconnects with node v 2 , a quadrilateral surface (v 0 , v 1 , v 2 , v 3 ) is formed. After v 1 connects with v 3 , the degree of node v 0 and v 2 is reduced and the degree of v 1 and v 3 is increased.

To balance the distribution of nodes' connectivity, it is better to guarantee that two disconnected nodes are with high-degree and the two connected nodes are with low-degree. So, before node v 0 decides the disconnected node, it needs to calculate which node is more suitable to disconnect according to the degree of each neighbouring node.

For each neighbouring node v i of node v 0 , we calculate the fitness value c i of node v i as shown in Eq. 3. If the degree of node v i is smaller than one of its two adjacent nodes, the fitness value of node v i is 0. Because after node v 0 disconnects with this candidate node, the degree of its adjacent nodes will become bigger. If the degree of node v i is bigger than both of its adjacent nodes, node v 0 calculate the fitness value by the multiplication of (d i − d i−1 ) and (d i − d i+1 ). At last, node v 0 selects the candidate node with the biggest fitness value to disconnect. Then, node v 0 instructs the two adjacent nodes of candidate node to connect with each other to maintain the topology stable. 

Algorithm 2 gives the pseudocode for the self-optimization algorithm of each node. Once the degree of each node is bigger than the upper limit of degree (We usually set the upper limit of degree is 10), the current node begins the self-optimization process to adjust its local topology. And the basic idea of selfoptimization is to transfer the degree from the high-degree node to low-degree node. With the collaboration of all nodes in anti-tracking network, CPT can achieve the self-optimization of network topology.

In this section, we compare CPT with two self-organizing methods of network topology, one is a based on the neural network (NN) [16] and the other is based on distributed hash tables (DHT) [17] . NN achieves the self-optimization of topology by the neural network algorithm deployed in each node. DHT achieves the self-organizing network based on the hierarchical aggregation structure. We evaluate the three methods from the following aspects: (1)network robustness, (2)maintenance efficiency, and (3)communication efficiency.

Firstly, we seperately simulate three networks with 5000 nodes by CPT, NN and DHT, calculate the distribution of nodes' degree D d and the distribution of nodes' density D s to compare the difference of the three network topologies. We use the number of nodes which have the span not more than 2 with v i to represent the density of v i . As illustrated in Fig. 7(a) , D d of CPT is mainly distributed in the interval [3, 10] , because of the convex-polytope structure limitation. D d of NN is mainly distributed in the interval [3, 15] . D d of DHT is distributed widely. The distribution of nodes' density has the similar tendency with the distribution of nodes' degree. In general, the local density of nodes is in direct proportion to their degree, and the nodes with high density becomes the key nodes easily. In Fig. 7(b) , D s of CPT is mainly distributed in the low density area which means the topology structure of CPT is more stable than NN and DHT.

To evaluate the network resilience, we firstly give a metric to quantify the performance of network resilience. As shown in Eq. 4, we use a graph G to represent the original network, G(p) denotes the subgraph after p percent of nodes is removed from G, MCS(G(p)) denotes the maximum connected subgraph of G(p), Num(g) denotes the node number of a graph g, N denotes the node number of G. The metric β measures the maximum connectivity of the network after some nodes are removed from the network. The β is higher, the network resilience is better.

Based on the above simulated networks constructed by CPT, NN and DHT, we remove p percent nodes from the three networks each time until all nodes are removed. In each round, we calculate the β to evaluate network resilience. In the experiments, we use two different ways to remove nodes shown as follows.

-Random-p Removal. In each round of nodes removal, we remove p percent of nodes from the network randomly. -Top-p Removal. In each round of nodes removal, we remove p percent of nodes with the highest degree.

From the experimental results shown in Fig. 8 , CPT has a better performance in network resilience and β keeps higher than NN and DHT in both randomp removal and top-p removal. In random-p removal, even β of CPT is always higher than NN and DHT, the difference of the three methods is not very high. The performance of the three methods in network resilience begins to decrease when β is less than 40%.

But in top-p removal, the performance of DHT degrades sharply. The performance of NN in network resilience begins decrease when β is less than 20%. But CPT still maintains good performance in network resilience under top-p removal. The experiments show that top-p removal causes bigger damage to the 

The real network environment is complex and changeable, the maintenance efficiency has a direct influence on the performance of network self-optimization. If the network maintenance process costs too much time or computing power, it is ineffective in the practical application. In this section, we evaluate the maintenance efficiency of CPT, NN and DHT from two aspects.

-Efficiency of network construction. According to the netword construction methods of CPT, NN and DHT, we construct a network in simulation environment and count the time requirement for comparison. -Efficiency of network self-optimization. For each network constructed by CPT, NN and DHT, we randomly remove p percent of nodes and count the time requirement of network self-optimization as the metric. By increasing the percentage of removed nodes, we compare the change of time requirement to evaluate the efficiency of network self-optimization. Figure 9 (a) illustrates the time requirement of network construction with CPT, NN and DHT. The value of X-axis denotes the node number of the constructing network. With the increase of the network node number, the time requirement of CPT increases slower than NN and DHT. Limited by the computation of neural network, the time requirement of NN increases sharply. DHT relays too much on the agent nodes to construct and manage the network topology. Benefited from the convex-polytope structure, the whole network of CPT keeps the balanced distribution of nodes' connectivity. Without the too much computation like NN and too many connections like DHT, CPT can achieve better efficiency of network construction. Figure 9 (b) illustrates the time requirement of network self-optimization after p percent of nodes are removed from the network randomly. When more than 50% nodes are removed randomly, the network will be split into different subgraphs. In this case, we need to connect the different subgraphs into one whole network, then continue the network self-optimization process and count the time requirement. As we can see in Fig. 9(b) , the curves of three methods increase at the beginning, and then decrease when p is more than 50%. Because along with the increase of the percentage of removed nodes, the network size becomes smaller. So, when the network size reduces to a certain degree, the time requirement of network self-optimization will decrease.

In this experiment, CPT performs better in both network construction and network self-optimization. The simple structured topology of CPT improves the efficiency of network construction, maintenance and self-optimization.

To evaluate the communication efficiency, we randomly select two nodes to communicate in each test and count the average time requirement after 100 round tests. With the increase of network size, we compare the communication efficiency of CPT, NN and DHT through the average time requirement.

The network diameter and average path length increase with the increase of network size. The randomly selected two nodes would spend more time to communicate in each network. As illustrated in Fig. 10 , the average time requirement of CPT is always higher than NN and DHT. But, the difference of communication efficiency between CPT, NN and DHT is not very big and it is also acceptable for anti-tracking network.

The reason of CPT's low communication efficiency blames for the convexpolytope structure. To keep the convex-polytope structure, CPT improves the network robustness and destroy-resistance at the cost of communication efficiency. And the research has proved that anti-tracking network can not achieve all the three properties: strong tracking-resistance, low bandwidth overhead, and low latency overhead [18] . But from the tracking-resistant standpoint, the 

In this paper, we propose convex-polytope topology (CPT) which can be applied in anti-tracking network. We construct the anti-tracking network according to the properties of convex-polytope, and maintain the network topology in the convex-polytope structure. When the node join in or quit the network, CPT can still maintain the convex-polytope topology to keep a stable and resilient network. Based on the convex-polytope topology, we design a self-optimization mechanism for anti-tracking network. The experimental results show that CPT has better performance in network robustness, maintenance efficiency than current works.

A survey on routing in anonymous communication protocols

RAPTOR: routing attacks on privacy in tor

Development of measures of online privacy concern and protection for use on the Internet

Achieving dynamic communication path for anti-tracking network

A Sybil attack detection scheme for a forest wildfire monitoring application

A review on Sybil and Sinkhole of service attack in VANET. Recent Trends Electron

A fuzzy particle swarm optimization algorithm for computer communication network topology design

Topology management in unstructured P2P networks using neural networks

Self-organizing network services with evolutionary adaptation

A loss-tolerant mechanism of message segmentation and reconstruction in multi-path communication of antitracking network

De-anonymizing and countermeasures in anonymous communication networks

How to block Tor's hidden bridges: detecting methods and countermeasures

Information leaks in structured peer-to-peer anonymous communication systems

Detecting Sybil nodes in anonymous communication systems

SEINA: a stealthy and effective internal attack in Hadoop systems

A smart topology construction method for anti-tracking network based on the neural network

A P2P computing based self-organizing network routing model

Anonymity trilemma: strong anonymity, low bandwidth overhead, low latency-choose two

Acknowledgments. We thank the anonymous reviewers for their insightful comments. This research was supported in part by the national natural science foundation of China under grant No. U1736218 and No.61572496. Yongzheng Zhang is the corresponding author.