# A Road Truncation-Based Location Privacy-Preserving Method against Side-Weight Inference Attack
## 3 Preliminaries and Problem Definition
### Side-Weight Inference Attack  
Before illustrating the scheme in this paper, we first discuss the problem of location privacy disclosure and the corresponding protection schemes. Then, we explain how a side-weight inference attack happens, under the scenario of non-uniform distribution of users.  
In the \(k\)-anonymity scheme, there are at least \(k\) users in each anonymous set. As shown in Figure 2, there are four users in area A. When a user (marked as a triangle) in area A wants to get the service, it sends the query request with region A instead of its precise coordinates. The adversary gets the query message and knows the user belongs to area A. However, there is only an obfuscated area. The adversary cannot distinguish the target user from other users. Without considering the distribution of users, the probability of the adversary targeting the specific user is \(1/k\). As a result, the successful tracking probability of the target user is \(1/4\). Similarly, for anonymous set B, the successful tracking probability is \(1/3\).  
Figure 1: System model.  
Most of the early researches are based on Euclidean geometric space. In fact, many users of LBS are vehicles and restricted in road sections. As shown in Figure 3, there are \(3\times 3\) blocks with 12 streets ignoring the marginal road sections. For both anonymous sets A and B, there are four users. There is one road across the anonymous set A. Meanwhile, there are four roads across the anonymous set B. Obviously, the users in anonymous set B achieves higher privacy. Similar to the definition of \(k\)-anonymity, the anonymous set should contain at least \(l\) different road sections to fulfill the \(l\)-diversity of query requirement. Regardless of the differences of road sections, the probability of the adversary targeting the specific road section is \(1/l\).  
In real-world situations, the users are not uniformly distributed. Hence, the side-weight inference attack happens as the adversary would infer that the target user belongs to a high-density road section with high probability. As shown in Figure 4, the anonymous set is the blue circle which contains four road sections \(\{e_{1},\ldots,e_{4}\}\). There are 13 users in the anonymous set. We can guess the target user is more likely to belong to the edge \(e_{1}\), as there are more users in \(e_{1}\).  
Figure 3: Location privacy protection based on road network.  
Figure 2: Location privacy protection based on \(k\)-anonymity.  
In order to evaluate the performance of the proposed scheme against side-weight inference attack, we introduce two definitions to describe the tracking probability and distribution degree of users. First, we define the tracking probability \(\epsilon\).  
\[\epsilon=\frac{w(e_{i})}{\sum_{i=1}^{n}w(e_{i})}, \tag{1}\]  
where \(w(e_{i})\) stands for the weight of edge \(e_{i}\), namely, the number of users on road \(e_{i}\). Parameter \(\epsilon\) is the ratio between the weight of edge \(e_{i}\) and the whole of the anonymous set, which depicts the tracking probability of the adversary targeting on the specific road section.  
Then, distribution degree \(\lambda\) is defined as follow,  
\[\lambda=\frac{\max w(e)-\min w(e)}{\bar{w}(e)}, \tag{2}\]  
where \(\max w(e)\) and \(\min w(e)\) represent the maximum and minimum values respectively. \(\bar{w}(e)\) stands for the average weight of all road sections. Parameter \(\lambda\) is a normalized factor, which describes the biggest difference of distribution in different sections.