The main purpose of designing Vehicular Ad-hoc Networks (VANETs) is to achieve safety by periodically broadcasting the vehicle s coordinates with a high precision. This advantage brings a threat represented in the possible tracking and identi cation of the vehicles. A possible solution is to use pseudonyms instead of real identities. However, even by changing pseudonyms, the vehicle can still be tracked if the adversary has knowledge about the potential start and end points of a particular driver who has social interactions (e.g., with neighbors) which introduces the concept of Vehicular Social Networks (VSNs). In this work we propose a location privacy scheme, namely: Extreme Points Privacy (EPP) for trips and home identi cation in VSNs by exploiting the nature of the end points that are common between many VSN users bringing the option to create shared zones to anonymize these users. An analytical study accompanied by a simulation using the realistic vehicular tra c mobility generator SUMO are presented to show the e ectiveness of the proposed scheme.
The humain behaviour and social interactions were almost apparent in drivers moving patterns which lead to the emergence of VSNs. The evolution and enhancement of VANET capabilities have signi cant in uence on the successfulness of the Intelligent Transportation Systems (ITSs) [1, 2]. In VANETs, there exist two kinds of communications: Vehicle to Vehicle (V2V) and Vehicle to Infrastructure (V2I). In order to be able to communicate, vehicles are equipped with On Board Units (OBUs); speci c devices that allow vehicles to: communicate, process date, receive GPS signal and use variant sensors. Vehicles may often communicate with central infrastructures. Such infrastructures may be Road Side Units (RSUs) [4]. VANET applications may be diverse; however, the number one reason for what it was proposed is to reduce the number of crashes and fatalities [4] by enabling periodic broadcasts (also called beacons or heartbeat messages). This requires the vehicle to include its status in kind of location, speed, velocity and other information that allow a better environment knowledge like Basic Safety Messages (BSMs). The standard SAE J2735 sets the frequency of BSMs to be each 100ms with a 300 meter transmission range radius [5]. The frequent and precise location provided by BSMs helps enormously the safetyrelated applications but, at the same time, reduces dramatically the privacy of VSN users since the BSMs location is not encrypted for fast reaction and less delay. Thus, any adversary willing to monitor the VSN users can do that in real time with just some eavesdropping station(s). Among the possible solution there exist: the use and the change of pseudonyms instead of one real identity, the cooperation of vehicles during the pseudonym change, the use of silent periods [6] and other techniques that will be seen in the next section.
In this paper, we demonstrate the model of EPP by giving an analytical study for the privacy level achieved by the VSN users of a particular district taking into account the number of gates and the possible headings from each gate; the de nition of the above concepts will be further explained. This analytical study is accompanied by simulations in order to evaluate the e ectiveness of EPP scheme. The rest of this paper is organized as follows. Sect. 2 presents some related works. In Sect. 3, we describe the proposed EPP strategy. The experimental results are presented in Sect. 4 and we conclude the paper in Sect. 5. 2
In what follows we brie y describe some of the potential solutions to defend
against location privacy and identi cation: (
The problem of location tracking and re-identi cation of VANET users was studied delicately in a lot of works. In [4], the CARAVAN scheme was proposed which consists of changing pseudonyms over time by combining the silent period and the group concepts. The authors in [8] namely swing & swap used the pseudonym change after ensuring the increase of the neighbors(swing), swap aims at letting vehicles exchange their pseudonyms instead of a normal change. The exchange of pseudonyms enhances privacy but it highly relies on the infrastructures for the accountability requirement. In CMIX [9] the vehicles are supposed to change their pseudonyms at mix-zones [10] (e.g. the intersections, at tra c lights, etc.) in addition of the encryption of safety messages once the vehicle enters the mix-zone. Density-based location privacy (DLP) [11] scheme uses the neighborhood number as a parameter to decide whether to change the pseudonym or not. Pseudonym change at social spot (PCS) [1] was proposed to let vehicles change their pseudonyms at dense places such as intersections or parking lots. However, the map does not always have such places. To betterchoose the moment of the pseudonym change, cooperative pseudonym change (CPN) [12] was proposed. CPN uses di erent triggers in order to achieve a high level of privacy. The neighbors number is one of these triggers. In [5], Endpoit Protec-tion Zone (EPZ) deals e ectively with the location privacy in the domain of LBSs where users query the appropriate LBS. Authors suggested that the users have to be grouped spatially and have to use the same login credentials in addition to keep silent until leaving the EPZ. The scenario of the colluding between an LBS and an RSU dishonest owners is also investigated. EPZ deals mainly with the problem of dishonest LBS owners. In our work we give more attention to the scenario of a dishonest RSU owner or a potential external eavesdropper who may attempt to monitor a region of interest while using backward knowledge represented in: the starting point, exiting point (called gateway here) and potential direction (called heading)at a given time. We also study the different possible scenarios (described in more details in the coming section) in order to investigate the successfulness of the adversary to determine whether his target(s) had quited or not. 3
In this section we outline the principals of the proposed scheme EPP which is a zone division-based that exploits the nature of the VSNs and we give the possible behavior of any VSN user and its implications on the privacy of these users.
Since the pseudonym change strategy is not working in all scenarios, new
techniques must be deployed to ll this gap. An example is when vehicles start
from a prede ned spot. Here, if the adversary has some knowledge (represented
by social engineering), he can match the used pseudonym with the real identity
of its driver whatever the strength of the deployed pseudonym change strategy is
(it goes in vain). We suggest the use of the EPP scheme which is built basing on
the characteristics of the end points that, in general, do belong to speci c zones
that have speci c nature as: (
As shown in Figure 1.a, the map, according to EPP, is divided into: District zones, Gateway zones and the Outside Environment and are explained in details in what follows: A. District Zones: They contain the start and end points of speci c VSN users who use these points (spots) more frequently (the home for example). The nature of such zones, allows dispensing with BSMs because of the vehicle s e ciency in dealing with the environment and neighborhood vehicles. The vehicles then will be authorized to stay silent while they are inside the district zone(s) without safety dangers and threats.
B. Gateway Zones: Each district is attached with the outside environment.
The role of gateways (GWs) is to let the outside environment vehicles know about the newly coming vehicles from the district. Now, BSMs become a must (instead of being an option in district zones). In addition, a district may have many gateways and headings (HDs). A heading is a direction that a vehicle would take once it leaves the gateway, it then determines the trip of the driver.
C. The outside Environment: it is the remaining part of the network in
where a privacy mechanism like pseudonym change at mix-zones is used.
The vehicle changes its pseudonym and may: (
As explained in the previous subsection, a VSN user starts from the district, more
precisely from his appropriate spot inside that district. We assume that the
adversary is advanced, e.g., is considered as Global Passive Adversary (GPA) [3]
with a backward knowledge about all VSN users inside that district. The
adversary then knows about each vehicle s potential spots, exiting/entering gateway
and its heading. With ordinary strategies, the adversary will know for sure about
the events of: (
(b) Network and threat models in EPP
In this part we explain the entities of the network with their de nitions for better comprehension: We rst de ne the three possible scenarios (or vehicle classes) that may occur: - A set of VSN users who are aware of the privacy concept. Thus, they enable the radio-silence feature to protect their privacy. The set is de ned as "X". - A set of VSN users who are not aware of their privacy. Thus, they disable the radio-silence feature. The reason may also be that they need to use some services which require a continuous connected. The set is de ned as "Y ". - A set of VSN users who may not be able or cancel their appointments, works or visits for whatever reason. This kind of vehicles surprises the adversary since they act unexpectedly to his thoughts. This set is de ned as "Z". - The adversary is supposed to be aware of the approximate movement time of his target(s) due to the social engineering techniques (Figure 1.b). shows both of the network model and the threat model in EPP scheme. Let the set of VSN users who belong to the district be:
S = fv1; v2; :::vng = X + Y + Z The set of VSN users who are similar in term of gateway and heading:
Ssim(i) = fvj 2 S : Similarity(vi; vj ) = 1g The set of VSN users who are still inside the district: The set of VSN users who quitted the district:
Sin(i) = fvj 2 Ssim(i) : State[vj ] = "Inside"g
Sout(i) = Ssim(i)
Sin(i) The set of VSN users who quitted the district for sure in the thoughts of the adversary with a 100% of certainty:
SClearly out(i) = fvj 2 Sout(i) : Class[vj ] = "Y "g
(
0
jSsim(i)j jSout(i)j
jSsim(i)j jSClearly out(i)j
(
Else Poutside(vi) = 1
Pinside(vi)
(
In this section, we evaluate the e ectiveness of the proposed EPP scheme. For this aim, we consider a set of 10 VSN users of a speci c district (taken from Tlemcen town, Algeria) that contains two gateways and two headings per each gateway. Our main task is to evaluate the adversary s certainty about the exiting/quitting of a target(s) (Vi). Each VSN user may belong to either classes (X, Y or Z). The number of gateways and headings is manipulated in order to see its e ect on the achieved privacy. The simulations were done by taking three scenarios (namely: I, II and III). In I, a real district that contains two gateways and two heading per each gateway was taken. We modify this real map fragment and transform it into II then III (one gateway, two headings and one gateway, one heading respectively).
We use SUMO to make realistic VSN user traces. For this purpose, we generate a vehicular road tra c starting from 7 : 40 until 8 : 15. The reason we took this interval of time is because users often leave their homes in such a period (rush time) to either: work, study, etc. we then (via a c++ program) randomly generate our ten district vehicles departure times, the exiting gateways and the headings. We also make four parameters per each scenario by varying the number of vehicles in each class (see Figure 3).
As explained before, we choose three scenarios and per each one we make four runs, we then evaluate the probability of quitting. The monitored targets are taken randomly from each class (i.e. from X, Y and Z which is only one since it is 10% from 10).
Scenario I: We start by the scenario of two gateways with two hidings per each. The taken Vahicles from each class are mentioned in the graphs. The obtained results are as follows:
The results in Figure 4 shows that the VSN user who does not activate/enable the privacy mechanism (class "Y ") fails both: (a) easily and (b) faster than other classes. The next one is the class "X" user, because he does not expose himself by staying silent until he quits the district. However, class "Y " VSN users a ect him by letting the adversary know about their quitting events. The last category ("Z") comes with the best privacy level since it does not quit the district which enhances its and others privacy (users who share the same similarity as it). A similarity in our scheme re ect the same gateway and heading.
(a) II:1 (c) II:3 (b) II:2 (d) II:4
Another two observations from the four results in gure 4 indicate that (
Scenario II: This scenario is formed by only one gateway and two hidings. The taken Vahicle from each class is mentioned in the graphs (as in scenario I). The obtained results are the followings:
The results interpretation is almost the same as in scenario I where "Y "
users are the rst to be exposed followed by the class "X" then lastly class
"Z" maintains its privacy perfectly as in Figure 5. The additional observations
are: (
Scenario III: This last scenario is formed by only one gateway and one hiding. The taken Vahicle from each class is mentioned in the graphs. The obtained results are represented as follows: (a) III:1 (b) III:2 (c) III:3 (d) III:4
The VSN user in this scenario share the same characteristics as the previous
two scenarios and class "Z" is the best in privacy preserving followed by class
"X" then class "Y " comes in the last place (see Figure 6). The special
characteristic in such a scenario is that all VSN users are similar because of the unique
gateway and heading. Our observations are: (
In this work we investigated the end points location privacy and the re-identi cation problem. We rst introduced the problem and our EPP scheme. We accompanied this with di erent simulations where we varied the number of gateways, headings and the number of VSN users who enable, disable and not leave the district. The obtained results showed that the more the users have the same similarity, the more they are protected from quitting-event exposition. The results also showed that the class "Y " VSN users a ect negatively the privacy of other users. Thus, from all of these we conclude that, in order to ensure a high level of privacy, VSN users have not to be sel sh and be aware of the privacy term. With this, not only they protect their own privacy, but, the others as well. The nature of the district and the number of gateways and headings have also an impact on the achieved privacy. Finally, EPP has to be accompanied by a pseudonym change strategy such as mix-zones in order to maintain the privacy of VSN users even after leaving the district (e.i. in the outside environment).