A Novel Vision-based Location Authentication Approach in a Ubiquitous Camera Environment

INTRODUCTION

The evolution of ICT (Information and Communication Technology) and hardware technology brings about the development of ubiquitous computing. Many countries include ubiquitous computing into their industrial policies, such as U-Korea, U-Japan and U-Taiwan (Ubiquitous Taiwan). Among the services related to ubiquitous computing, Location-Based Service (LBS) is one of the fastest growing areas in the mobile world. LBSs include security, information, navigation, tracking and many other services. This was achieved by the removal of the signal-degrading selective availability (SA) from the GPS (global positioning system) signals on the 1st May 2000 (Murakami and Ke, 2006). Many GPS-enabled devices, such as GPS phone, GPS PDA, are currently popular and become important tools with which to access LBSs. For LBSs, the location of a mobile client is very critical information for accessing LBSs. Previous studies have mainly focused on the protection of privacy (Ren et al., 2006; Ren and Wenjing, 2007; Al-Muhtadi et al., 2002). However, if an attacker or a legal user forges the location information, he can access desired information or services illegally via LBSs. Here are some examples:

From the above examples, we conclude that the location authentication should prevent the attacks from malicious attackers. In previous studies, the authentication is mainly based on trusted devices of a third party, such as hardware sensors or tamper proof GPS modules for the location authentication of a cell phone (Durresi et al., 2007). However, the deployment of trusted hardware sensors is not cost-efficient. In addition, a mobile client must be close to a sensor for location authentication. It is also inconvenient for users. The assumption of a tamper proof GPS module is also debatable since a software tool for simulating a GPS receiver is available (GpsGate, 2008).

On the other hand, the camera deployment is towards a ubiquitous camera (UbiCam) environment, especially in an urban area. For example, the area of the Taichung County, Taiwan, is 163.4 km² and the population is about 960 thousands. The number of cameras deployed simply on the streets is more than 3000. On average, at least one camera is deployed at all intersections. If the real-time image of a camera is used for location authentication of a mobile user, it is cost-efficient and convenient for users. Therefore, a novel vision-based location authentication approach, called VLocAuth, is proposed to prevent the location information being forged not only by an attacker but also by a legal user. That is, a user who has authority to access LBSs, but he forges his location for accessing desired information illegally via LBS. Therefore, when a mobile user wants to access LBS, he must pass the location authentication process of VLocAuth.

The location is critical and is easily forged information. However, only a few studies address the solutions to location authentication. The proposed approaches can be classified in ways similar to the classification of Han and Kim (2007):

In addition, the approach proposed by Han and Kim (2007) is using a model similar to the trusted authority of PKI (public key infrastructure). It is based on a specific location service architecture defined by the Geopriv Working Group. The defined location sensing method is that the location information of a mobile client can be generated by both the client and the trusted operator. However, such architecture and the location sensing method are not available currently. They do, however show the practicability of this approach.

There are some drawbacks for the previous approaches. Therefore, the vision-based approach (VLocAuth) proposed in this study is novel to location authentication and meets the UbiCam environmental requirements for the near future.

VISION-BASED LOCATION AUTHENTICATION APPROACH

In the previous methods, the main drawback is that the deployment cost of the trusted devices is too high. It is not cost-efficient and is inconvenient for users since they must find and be close to the trusted device before location authentication. Besides, these methods focus on the protection of location information but do not protect the privacy of mobile clients. The location information of any client should not be able to be obtained by any attackers, authentication or LBS servers. The scenario of VLocAuth is presented in Fig. 1. When a mobile client requests services from LBS server, his location must be authenticated by an Authentication Server (AS). A Camera Server (CS) handles the authentication by matching the coordinates of the mobile client and any moving objects in the camera image.

VlocAuth consists of two phases: Initialization and location authentication phases. In the initialization phase, a mobile client requests a UserID, hash function h, random seed and MAC (Message Authentication Code) function C from the LBS Server. The above information is transmitted over a secure channel, such as Intranet or VPN (virtual private network), to ensure data security in the location authentication phase. The random seed is the initial value of the one-way hash function, such as MD5 (Message-Digest Algorithm 5). When the mobile client wants to obtain the LBSs in the location authentication phase, the mobile client acquires temporal identification, denoted TID_C, from the LBS server using UserID, hash function h and random seed. Then the mobile client requests location authentication to AS using TID_C. The mobile client submits GPS coordinates to AS. AS forwards coordinates to CS. Then, CS transforms GPS coordinates to image coordinate and tracks the moving objects in a circle candidate area where its center is the image coordinate. The candidate area is changing due to the movement of the mobile client. Therefore, if the GPS coordinates of the mobile client are not forged, the corresponding moving object should appear in the candidate area. Those moving objects are filtered according to the candidate area until only one object is in the candidate area. The location authentication is successful when the successive moving behavior of the object satisfies specific criteria. Two phases are presented in detailed as follows:

Initialization phase: The process of the initialization phase is depicted in Fig. 2. There are two sub-phases: registration and operation sub-phase. In the registration sub-phase, a mobile client requests a UserID, hash function h, random seed and MAC function C from LBS Server.

Fig. 1:	The scenario of the proposed approach

Fig. 2:	The process of the initialization phase

The operation sub-phase consists of four steps described below:

(1)

(2)

(3)

Location authentication phase: The mobile client is proceeding to this phase when the client obtains the TID_C from the LBS server. The process is presented in Fig. 3 and described as follows:

(4)

Fig. 3:	The process of location authentication phase

Table 1:	Notations of the location authentication approach

(5)

During the process illustrated above, the matching of the GPS coordinates and the moving objects in the CS is critical and described in detail below since it determines the authentication result. The notations used throughout the description of the location authentication rules are shown in Table 1.

Firstly, the CS transforms the GPS coordinates to image coordinates C_i. The transformation can be based on Tsai (1987). Since, the GPS coordinates are inaccurate, a tolerate distance, denoted as TD, is thus defined. A circular area, called the candidate area, is formed where its center is located at C_i and the radius is TD. The whole authentication process must be finished within a valid time period, denoted as TE.

Fig. 4:	The process of the key step in the location authentication phase

When the authentication process is started, those mobile objects that are within the candidate area are collected in a candidate set, denoted as CSet. The candidate area changes as the received GPS coordinates change. An object in the candidate set is removed when it does not stay in the candidate area. When there is only one object finally in the candidate set before the time expires by TE, it means identification success. That is, the corresponding moving object of the mobile client is identified in the camera image. The sum of successive vector differences of the object, denoted as SV, is also accumulated. If there is only a few or even one object in the candidate area, the object is easily identified successfully. The SV must be larger than a pre-defined threshold to ensure the identified object has sufficient room to move. For example, if the threshold is 720 degrees, it means that the object must turn around at least twice. On the other hand if all the objects are removed from the candidate set, it means that the identification is a failure, i.e., authentication failure. The above process is depicted in Fig. 4. In advance, several typical scenarios of the key step in the location authentication phase are presented in Fig. 5. They are described as follows:

Fig. 5:	The typical scenarios of the key step in the location authentication phase

Fig. 6:	The location authentication algorithm

According to the above scenarios, objects are excluded based on the candidate area updated periodically until only one object exists in the candidate set. The object is then checked whether its SV is larger than the pre-defined threshold, e.g., 720 degrees. If it is true, the authentication is a success. However, if all the objects are excluded or the elapsed time is longer than the TE, the authentication is a failure. A large SV and a short TE increase the difficulty to authenticate successfully. It also means that an attacker will find it difficult to forge the movement of a mobile client. The design of the SV and the TE parameters enable the flexibility of VLocAuth which will satisfy the desirable security requirements of location authentication. The algorithm for the key step in the location authentication phase is presented in Fig. 6.

SECURITY ANALYSIS

In order to evaluate the security of VLocAuth, we analyzed for the following attacks, issues and compared with some previous approaches:

Attack 1: Suppose the attacker can intercept the request message (UserID, r_U, T, MACK_CL (UserID, r_U, T)), the attacker cannot pass the authentication of LBS server through replay attack since the message includes a time stamp T. In advance, a challenge is answered after the MAC code is verified by the server to ensure the message is not altered during transmission. Only the registered mobile client owns the hash function h and random seed to generate the response correctly.

Attack 2: Only the registered mobile client owns the hash function h and random seed. Therefore, only the registered mobile client can generate the keys, K_CL, K_CA and K_CS. The attacker is unable to guess or estimate the correct key values. VLocAuth can resist the man-in-the-middle attack.

Unforgeability issue: In VLocAuth, the ubiquitous camera is responsible for the authentication by matching the GPS coordinates and moving objects in the real-time camera image. Either a legal user or an attacker is unable to forge the GPS coordinates and the movement of the moving object simultaneously to authenticate location successfully. Therefore, VLocAuth meets the requirements of location unforgeability.

Privacy issue: Before the location information is transmitted to the AS, it is symmetrically encrypted by using r_C given by the LBS server and a shared secure code obtained in the registration phase. An attacker is unable to obtain the location information. Besides, the GPS coordinates are associated with a temporal identifier TID_C given by the LBS server. The AS does not know the real identifier requested for location authentication. In addition, the location authentication is handled by AS and CS. The LBS server does not know the location of the mobile client. Accordingly, VLocAuth protects the privacy of mobile clients.

Confidentially issue: Only the LBS server and registered mobile clients obtain the shared hash function h, MAC function C and random seed. Therefore, only K_CL, K_CA and K_CS can be generated by them. The same session key is used for decrypting ciphertext. Therefore, VLocAuth can resist the ciphertext-only attack.

Integrity issue: The transmission message is associated with the MAC code in VLocAuth. The LBS server and the registered mobile client only share the function C, of the MAC code. An attacker is unable to intercept and tamper with the message. Therefore, VLocAuth protects the message integrity.

Simplicity issue: Only symmetric encryption algorithm and exclusive-OR operation is used in VLocAuth. Therefore, VLocAuth is simple and suitable for mobile devices with limited computing resources.

Practicability issue: VLocAuth is mainly based on the coming of a UbiCam environment. It is practical and cost-effective. It can also promote the applicability of UbiCam environment.

VlocAuth is compared to the previous approaches, including time-bound based (Sastry et al., 2003), constrained channel (Kindberg et al., 2002) and GPS-based approaches (Denning and Macdoran, 1996). The comparison results shown in Table 2 are extended from that presented in the trusted authority (Han and Kim, 2007). The original privacy requirement in Han and Kim (2007) is divided into two ones, privacy against attacker and privacy against service provider. They are used to check the privacy requirement more clearly. The deployment cost is also compared in the Table 2.

For the time-bound based authentication approach proposed by Sastry et al. (2003), there is no deployment cost since there is no additional hardware or device needed. However, the location and personal information is not encrypted during transmission. That is, the approach cannot protect the privacy against attackers and service provider. In addition, its covered range is limited since the transmission time is easily influenced by the network traffic.

For the GPS-based authentication method proposed by Denning and Macdoran (1996), it mainly based on the Location Signature Sensor (LSS) to authenticate the location information acquired by the GPS receiver. However, it is vulnerable to replay attack since, an attacker can collect transmission data between a receiver and satellites. The deployment cost is high since the devices of users must be equipped LSS and many fixed hosts equipped LSS must be also installed for location authentication.

For the authentication approach based on constrained channel proposed by Kindberg et al. (2002), the deployment cost is high since many third-party devices are needed. It is also inconvenient for users since the access range of the third-party devices is limited. Although, this approach can protect the privacy against attackers during transmission, it does not protect the privacy against the service provider. That is, the service provider can know the real-time locations of users.

Table 2:	The comparison of various location authentication approaches
The extended part is marked in bold letters .The mark T denotes that the approach satisfies the requirement in the row and V denotes that it does not satisfy. 1Sastry et al. (2003), 2Denning and Macdoran (1996), 3Kindberg et al. (2002) and 4Han and Kim (2007)

The provider can even analyze users’ preferences from the logged location information.

For the approach using trusted authority and proposed by Han and Kim (2007), the identifier of a user is transmitted with its location information while requesting LBS. That is, it cannot protect the privacy against the service provider. Besides, the approach is based on a specific location service architecture defined by the Geopriv Working Group. The defined location sensing method is that the location information of a mobile client can be generated by both the client and the trusted operator. However, such location service architecture and the location sensing method are not available currently. The deployment cost for practicing the proposed approach is high.

With our approach, VLocAuth, the deployment cost is middle since the method utilizes the UbiCam environment currently available and even more getting popular. The authentication is based on the match between the GPS coordinates and moving objects in the real-time camera image. It is impossible to forge GPS coordinates and movement in the camera image. That is, VLocAuth meets the unforgeability requirement. The transmission of location information is encrypted in advance by r_C given by the LBS server and a shared secure code obtained in the registration phase. This method can protect the user privacy against attackers. A temporal identification, TID_C, is also given to the mobile client by the LBS server for location authentication with AS. AS does not know the real identification of the mobile client and the LBS server does not know the location information of the client. Therefore, the method can also protect user privacy against the service provider. The method can also prevent replay attack because of the design of the challenge/response mechanism in the initialization phase.

PERFORMANCE EVALUATION

In VLocAuth, the matching between GPS coordinates and moving objects in the real-time camera image is the key step in determining the success or failure of location authentication. The matching process is mainly influenced by the following factors:

The above factors are difficult to verify by mathematical proof. Therefore, a simulation tool and a matching tool were implemented separately to evaluate the performance of the key matching step from different ways. They are presented in the following subsections.

The simulation study: The simulation tool is designed to imitate a system developed previously, called GODTA (GPS-based Object Detection and Tracking Approach) (Hsien-Chou and Pao-Tang, 2009). Its screen shot is shown in Fig. 7. The left-upper part is the FOV of a camera. The parameter setting is listed on the right-hand side. The people walking in a square are assumed to be the typical environment for location authentication. It is simulated by using a random waypoint mobility model. The parameters of the model are listed on the upper-right part. They include speed of movement, maximum pause time and maximum time span. A person, i.e., a node, moves in the range of the speed of movement for a period of time that is less than the maximum time span. Then, it pauses for another period of time that is less than the maximum pause time. A new direction is chosen randomly and repeats the above steps again. The lower-right part of the screen shot shows the simulation parameters. They include the selection of GPS types, the FOV size and the number of mobile nodes, TD, network delays and identification times (the simulation times). The execution interval is used to control the execution speed of the simulations. The identification of the mobile client is the primary process of location authentication. When the mobile client is identified, its location is authenticated after its SV satisfies the threshold within the period limited by TE. The checking of SV and TE is trivial. Therefore, only the identification of the mobile client is considered in the simulation study.

When the start button is pressed, mobile nodes are moving according to a random waypoint mobility model. For every location authentication, a node is chosen randomly as the mobile client. It is marked by the color red as shown in Fig. 7. The candidate area based on the received GPS coordinates and the TD is marked by a blue circle. Initially, all the nodes in the candidate area are added into the candidate set, CSet. However, when a node moves out of the candidate area, it is removed from the CSet and marked by the color blue. Those nodes marked by the color purple are still included in the CSet.

Fig. 7:	The screen shot of the location authentication simulation tool

Table 3:	The parameter settings of the simulations
PP: Pass percentage

The pass or failure of the identification process is determined according to the rules described in the previous section. When all the identification is finished, the result is listed on the lower-left part. The results consist of three items: average nodes, average time and pass percentage. The average node is the average number of nodes in the initial CSet. The average time is the average time to finish the identification process. The passed percentage is the percentage of the mobile clients identified correctly.

Three simulations are designed here. One shows the pass percentage versus various node densities by using a general GPS receiver. Another shows the influence of network delay on the pass percentage. The other shows the pass percentage and average time of identification by using a popular D-GPS receiver.

The parameter settings of three simulations are listed in Table 3. The basic setting is common to the three simulations. The total number of simulations is five hundred. The FOV size is 320x240 m². The number of mobile nodes varies from 20 to 800 simulating sparse to dense conditions. The setting of the speed of movement is close to the normal walking speed. Those custom settings are presented below:

Fig. 8:	Pass percentage vs. mobile nodes for G-GPS receiver

Pass percentage vs. node density by using G-GPS receiver: For a G-GPS receiver, this simulation shows the influence of node density and TD to the pass percentage. For the custom setting of parameters in this simulation, the network delay is 0 sec for executing the simulation under an ideal situation. The setting of TD is from 15 to 27 m since, the positioning error of a G-GPS is about 5 to 30 m. The simulation results of pass percentage using various TDs are depicted in Fig. 8. When TD is only 15, the corresponding pass percentage is decreased quickly to less than 30% by increasing the node density. However, when TD is 24 or 27 m, the pass percentage is larger than 80% no matter what the node density is. For a normal situation with 100 mobile nodes and the TD set to 24 m, shown by the blue-dashed circle in Fig. 8, the pass percentage is 83.4% and the average identification time is 14.26 sec. The result of such setting is good for practical usage by using G-GPS.

Pass percentage vs. network delay by using G-GPS receiver: There exists the delay while transmitting the GPS coordinates from a mobile device to the CS in the practical environment. Therefore, the custom setting of network delay and TD is from 0 to 3 sec and 24 or 27 m, respectively, as listed in Table 3. The simulation results are depicted in Fig. 9. According to the results, the delay causes a small decrease in the pass percentage compared with that of zero delay. The decrease is less than 5%. Therefore, a larger TD can keep the pass percentage high and reduce the influence of network delay.

Pass percentage and identification time by using D-GPS receiver: In the previous simulations, a G-GPS receiver is used show the pass percentage under various node densities and TDs, The pass percentage and identification time of a D-GPS receiver are measured in advance in this simulation.

Fig. 9:	Pass percentage vs. network delay for mobile nodes with G-GPS receiver

Fig. 10:	Pass percentage vs. mobile nodes with G-GPS and D-GPS receivers

The parameter settings are shown in Table 3. The parameter, TD (D-GPS), is set to two, three, or 4 m since the positioning error of a D-GPS receiver is zero to 5 m. The simulation results are depicted in Fig. 10. When TD equals 3 m, the pass percentage is about 68%. When TD equals 4 m, the pass percentage is increased quickly to 90%. It is similar to that of a G-GPS receiver with 27 m TD.

The time needed to identify the target mobile node for two types of GPS receivers is quite different. The results of the average identification times are listed in Table 4. According to the results, the identification time of a G-GPS receiver is increased by the increase of mobile nodes and TD.

Table 4:	Identification time vs. mobile nodes with G-GPS and D-GPS receivers

Fig. 11:	The screen shot of the matching tool

Conversely, for D-GPS receiver, the identification time is shortened to less than 1 sec by a small TD. To sum up, when the number of nodes are less than 100, the time taken by a G-GPS receiver is less than 21.6 sec. It is acceptable for the location authentication. However, when the number of nodes is high, a D-GPS receiver is suitable for fulfilling the need to shorten the authentication time.

The empirical study: The key matching step of VLocAuth is mainly based on the image understanding technique which may be time-consuming. Therefore, a matching tool was implemented to match the GPS coordinates and moving objects on the real-time camera image. It is used to evaluate the performance of the key matching step in the practical environment. The screen shot of the tool is shown in Fig. 11. The real-time camera image is captured continuously and displayed on the left-hand side. The subtraction of two consecutive images is used to detect the foreground moving objects. Initially, those objects are collected in a candidate set (CSet) when its size is within a predefined range and marked by a blue rectangle as shown in the Fig. 11. A client tool was also implemented to transmit the GPS coordinates of the target object every second to the matching tool. When the target object is moving and turning around, it causes a larger angle of two successive moving vectors computed from the GPS coordinates. The angle change of the corresponding image coordinates should be similar, too. When the vector angle of GPS coordinates is larger than a threshold set on the upper-right corner of the Fig. 11, the matching tool removes all the objects without such angle change from CSet. The above process is repeated until only one object is left in the CSet. The image of the last object is displayed on the upper-right corner. If the object is the designated target, it means the target object is identified successfully. Then, the target object is re-identified again and the time is listed in the event list on the lower-right corner of the Fig. 11.

Table 5:	The identification time of the matching tool in practical environment

For the example shown in the figure, the re-identification is started on 5:19:06. The target object is identified after two turning around events on 5:19:11 and 5:19:18. The corresponding vector angles are 137 and 167 degrees that are larger than the threshold, 115 degrees. The matching tool spent 12 sec (5:19:06-5:19:18) to identify the target object.

Two performance values are measured using the matching tool. One is the computing time of image understanding technique. The other is the identification time. The main image understanding technique used in the key matching step is moving object detection. For the measurement of the computing time, two consecutive images are processed by a series of steps for detecting moving objects, including convert to gray scale, subtraction, binarization, dilatation, extraction the BLOB (binary large object) data, i.e., the moving objects. The above steps are repeated 100 times on an AMD Athlon 64x2 dual core 5600+ processor 2.9 GHz desktop computer. The average computing time is 138 and 37 msec for one 640x480 and 320x240 image, respectively. It shows that the image understanding is quite efficient. Especially, when many clients request for authenticating their locations and they are within the FOV of the same camera, the moving objects are only needed to be detected once for every image. Then, the information of the moving objects can be used to match with the GPS coordinates of individual clients. Such matching time is not included in the computing time since, it is very fast with respect to the moving object detection.

For the measurement of the identification time, a target object is re-identified for 86 times by using the matching tool. The results of the identification time are listed in Table 5. They are classified based on the number of moving objects. Most of identifications are performed on one to 10 objects. The time is not changed obviously when the number of moving objects is increased to 50. The identification time is ranging from five to 17 sec and the average time is 11.37 sec. The results are similar to the simulation results of the G-GPS listed in Table 4, i.e., 12.3 sec for 40 nodes.

CONCLUSIONS AND FUTURE WORK

The previous approaches, including time-bound based, constrained channel and GPS-based, have some drawbacks, such as deployment cost is high, cannot protect privacy against attacker or service provider, or cannot prevent replay attack. Therefore, a vision-based location authentication approach, called VLocAuth, is proposed in this study. The real-time camera image is incorporated into the location authentication mechanism for improving the drawbacks of previous approaches. The coming of the UbiCam environment is helpful in increasing the feasibility of VlocAuth. VLocAuth not only achieves location authentication but also protects the privacy of users against attacker and service provider. For the simulation study of the key step in location authentication phase, the simulation results show that the pass percentage of a general GPS (G-GPS) receiver can be up to 90% and the identification time is less than 1 sec for a differential GPS (D-GPS) receiver. The results of the matching tool also show that VLocAuth is able to handle many requests simultaneously without influenced seriously by the image understanding technique. And the average identification time, 11.37 sec, is acceptable in the practical environment. Therefore, VLocAuth is a novel ideal by utilizing the UbiCam environment on location authentication. It also raises some issues to be addressed for further development of location authentication. For example, the location exposure is usually determined by services, temporal, or spatial information. VLocAuth can be refined to control of location exposure. In addition, it will be extended to indoor environments so as to become a total solution for location authentication in the future.