Yuxin Meng
email: yuxin.meng@my.cityu.edu.hk

Wenjuan Li

Lam-For Kwok
email: cslfkwok@cityu.edu.hk

Enhancing Click-Draw based Graphical Passwords Using Multi-Touch on Mobile Phones

Keywords: Graphical Passwords, User Authentication, Multi-Touch, Human Factors, Mobile Phones, Mobile Security

Graphical password based authentication systems are now becoming one of the potential alternatives to alleviate current over-reliance on traditional text-based password authentication. With the rapid development of mobile devices (i.e., the increase of computing power), this kind of authentication systems has been implemented on mobile phones to authenticate legitimate users and detect impostors. But in real deployment, we notice that users can utilize more actions like multi-touch on a mobile phone than on a common computer. The action of multi-touch, which refers to the process of touching a touchscreen with multiple fingers at the same time, is a distinguished feature on a touchscreen mobile phone. In this paper, we therefore attempt to explore the effect of multi-touch on creating graphical passwords in the aspect of security and usability. In particular, we conduct a study of using click-draw based graphical passwords in the evaluation, which combines current input types in the area of graphical passwords, and we further develop a multi-touch enabled scheme on mobile phones. Three experiments were conducted with 60 participants and the experimental results indicate that, by integrating the action of multi-touch, graphical passwords can be generally enhanced in the aspect of both security and usability.

Introduction

User authentication on mobile phones has become more and more important with modern mobile devices being comparable to a PC (i.e., with the continuous increase of computing power). With the popularity of mobile phones, users are likely to store a lot of sensitive information (e.g., credit card numbers) on their mobile phones [START_REF] Karlson | Can I Borrow Your Phone?: Understanding Concerns when Sharing Mobile Phones[END_REF] and to use their phones for security sensitive tasks (e.g., authorizing commercial transactions) due to their fast data connection and wireless connectivity [START_REF] Dunphy | A Closer Look at Recognition-based Graphical Passwords on Mobile Devices[END_REF].

In these cases, it is crucial to develop and implement user authentication mechanisms for a mobile phone to authenticate legitimate users and detect imposters. To mitigate the limitations of traditional text-based password authentication (i.e., users have difficulty in remembering complex and random passwords which is known as long-term memory (LTM) limitations), authenticating users by means of images is one of the possible alternatives in which several studies [START_REF] Nelson | Pictorial Superiority Effect[END_REF][START_REF] Shepard | Recognition Memory for Words, Sentences, and Pictures[END_REF] have shown that human brain was better at remembering and recognizing images than text. Along with this observation, several graphical password applications have been proposed on mobile phones like Android unlock pattern3 , a graphical password based Android application in which users are required to input correct unlock patterns to unlock their Android screen [START_REF] De Luca | Touch Me Once and I Know It's You!: Implicit Authentication based on Touch Screen Patterns[END_REF].

Generally, graphical password based authentication can be categorized into three folders based on their input methods 4 : click-based graphical passwords, choice-based graphical passwords and draw-based graphical passwords. In particular, the clickbased schemes require users to click on the provided image(s) (i.e., choosing an object or element of the image), the choice-based schemes require users to select a series of images (i.e., selecting images in an order), and the draw-based schemes require users to draw some secrets to be authenticated (i.e., drawing a user signature). Several security studies regarding graphical passwords can be referred to [START_REF] Chiasson | A Second Look at the Usability of Click-based Graphical Passwords[END_REF], [START_REF] Dirik | Modeling User Choice in the Passpoints Graphical Password Scheme[END_REF] and [START_REF] Gołofit | Click Passwords under Investigation[END_REF].

Motivation. In real deployment, we find that users can utilize more actions like multi-touch in creating graphical passwords on a mobile phone than on a common computer. The multi-touch refers to the process of touching a touchscreen device with multiple fingers simultaneously, which is a distinguished feature for current touchscreen mobile phones. This observation indicates that the creation of graphical passwords may be different on distinct platforms due to different types of input actions. In addition, touchscreens are becoming the leading input method on the mobile platform where 74% of all phones in the market using a touch screen [START_REF]Mobile mix: The mobile device index[END_REF]. Our motivation is therefore to explore the impact of multi-touch on creating graphical passwords.

Contributions. In this paper, we attempt to investigate the impact of multi-touch on creating graphical passwords in the aspect of security and usability and use it to enhance the creation of graphical passwords. In particular, we employ click-draw graphical password scheme (CD-GPS) in the evaluation which combines current inputs of creating a graphical password. Our contributions can be summarized as below.

-We give a detailed analysis of the possible impact of using multi-touch on the creation of CD-GPS passwords. Based on the original CD-GPS scheme, we develop an example system of multi-touch enabled CD-GPS scheme on a mobile phone that enables users to create the CD-GPS passwords using the action of multi-touch. -To verify our analysis, we conducted three experiments with a total number of 60 participants. By comparing the obtained results, we find that the action of multitouch can positively enhance the construction of graphical passwords in the aspect of both security and usability.

The remaining parts of this paper are organized as follows: in Section 2, we briefly introduce the click-draw based graphical password scheme (CD-GPS); Section 3 analyzes the potential impact of multi-touch on creating CD-GPS passwords; Section 4 presents our developed multi-touch enabled CD-GPS scheme and our experimental methodology; Section 5 describes the experimental results and Section 6 reviews some related work; at last, Section 7 concludes our paper and points out future work.

Click-Draw based Graphical Password Scheme

The click-draw based graphical password scheme (shortly CD-GPS) [START_REF] Meng | Designing Click-Draw based Graphical Password Scheme for Better Authentication[END_REF] was developed with the purpose of enhancing traditional graphical passwords by combining existing input types from click-based, choice-based and draw-based graphical passwords. A general CD-GPS scheme mainly consists of two operational steps: image selection and secret drawing.

The first step is image selection where users are required to select several images from an image pool (i.e., the pool may contain a number of images with different themes) in an ordered sequence, and remember this order of images like a story to assist memorization. Then, users are required to further select one or more images to draw their secrets. In the step of secret drawing, users can freely click-draw their secrets (e.g., a number, a letter) on their selected image(s). The action of click-draw requires users to draw a secret by using a series of clicks. To facilitate the use of click-draw, the CD-GPS scheme partitions the selected image, which is used for click-drawing secrets, into a N × N table.

In [START_REF] Meng | Designing Click-Draw based Graphical Password Scheme for Better Authentication[END_REF], an example system of CD-GPS was also implemented in which the image pool contains 10 different images (i.e., themes like fruits, landscape, people, etc). In the first step, users are required to select 4 images out of the image pool and organize these images in a story order. Then, in the second step of secret drawing, users have to further select 1 image for click-drawing their own secrets. The selected image in the example system will be divided into a 16 × 16 table with 256 clickable squares. The user study with 42 participants showed that the CD-GPS scheme could provide suitable properties in the aspect of both usability and security. Detailed analysis about the CD-GPS can be referred to [START_REF] Meng | Designing Click-Draw based Graphical Password Scheme for Better Authentication[END_REF].

Multi-Touch

In real deployment, we notice that the way of creating graphical passwords may be different on a computer and on a touchscreen mobile phone. For instance, users can use more actions (e.g., multi-touch) on a mobile phone than on a common computer (e.g., PC). Nowadays, multi-touch is becoming a distinguished feature on a touchscreen mobile phone (or other touchscreen based devices) that users can touch the screen with multiple fingers at the same time. Next, we analyze the potential impact of multi-touch on creating the CD-GPS passwords.

Common computer. In a computer (e.g., a PC) with mouse as the input device, users can only create the CD-GPS passwords (i.e., drawing a secret by means of click-draw) with the action of single-click. In this scenario, the potential password space of CD-GPS passwords can be calculated as follows [START_REF] Meng | Designing Click-Draw based Graphical Password Scheme for Better Authentication[END_REF]:

N 1 ! (N 1 -n)! × n! k! × (n -k)! × ∏ k N c ! (N c -K i )! (i = 1, 2, 3, ...)
Where N 1 is the number of images in the image pool, n is the number of selected images in a story-sequence, k is the number of further selected images for click-drawing, N c is the number of clickable squares and K i means there are totally i clicks on a selected image. N 1 ! (N 1 -n)! means that selecting n images out of N 1 images in a story sequence.

n! k!×(n-k)! means that choosing k images out of n images for secret drawing without considering the image sequence. Finally,

∏ k N c ! (N c -K i )
! means the product of password space in selected k images.

Thus for the example system of the CD-GPS (where N 1 =10, n=4, k=1 and N c =256), the potential password space can be specified as below:

(10 -4)! × 4 × 256! (256 -K i )! (i = 1, 2, 3, ...)
Touchscreen mobile phone. On a mobile phone with touchscreen as the main input device, users can perform more actions like multi-touch on the screen than on a common computer. The action of multi-touch greatly distinguishes the creation of graphical passwords on a mobile phone from that on a computer. For example, as shown in Fig. 1, our target is to draw a symbol of arrow '>'. To better illustrate the process of creation, we further assume the ordered sequence of drawing is 1, 2, 3 and 4. On a computer with mouse as the input device, because the CD-GPS scheme does not consider the sequence of clicks, there is only one choice to sequentially click these 4 squares. However, with the action of multi-touch (i.e., only considering two fingers), there exist other 4 choices to complete the creation: {multi-touch{1, 2}, multi-touch{3, 4}}, {1, multi-touch{2, 3}, 4}, {1, 2, multi-touch{3, 4}}, {multi-touch{1, 2}, 3, 4}. In addition, if we do not limit the click sequence to 1, 2, 3 and 4, then the number of click choices can be increased to 4 × 2 = 8. This case indicates that the potential password space of CD-GPS can be further enlarged by integrating the action of multi-touch into the creation of graphical passwords.

If we only consider the multi-touch with 2 fingers (i.e., two squares can be selected at the same time), then the potential password space can be represented as below:

K i ! 2! × N 1 ! (N 1 -n)! × n! k! × (n -k)! × ∏ k N c ! (N c -K i )! (i = 1, 2, 3, ...)
Correspondingly, for the example system of the CD-GPS in [START_REF] Meng | Designing Click-Draw based Graphical Password Scheme for Better Authentication[END_REF], its potential password space can be specified as below:

K i ! 2! × (10 -4)! × 4 × 256! (256 -K i )! (i = 1, 2, 3, ...)
That is, by integrating the multi-touch with only 2 fingers, the password space can be further enlarged by K i ! 2! times in theory. Note that the user study in [START_REF] Meng | Designing Click-Draw based Graphical Password Scheme for Better Authentication[END_REF] has showed that K i is usually bigger than 5. Moreover, with the multi-touch, users may complete their drawings more quickly as two squares can be selected simultaneously.

User Study

With the above analysis of multi-touch, we therefore attempt to verify the impact of multi-touch on creating graphical passwords. In this section, we begin by describing our developed example system of multi-touch enabled CD-GPS on an Android phone and we then present our experimental methodology in the user study.

Multi-Touch Enabled CD-GPS

To enable the creation of CD-GPS passwords with the action of multi-touch, we design and develop an example system of multi-touch enabled CD-GPS that can collect multitouch clicks. This system, as shown in Fig. 2, authenticates whether a user is legitimate by combining the click-coordinate information with multi-touch records.

Fig. 2 (a) illustrates the developed multi-touch enabled CD-GPS scheme. Similarly, the image pool contains 10 images (arranged in 5 × 2 grids) with different themes such as fruits, landscape, cartoon characters, food, sport, buildings, cars, animals, books and people. All used images have the same pixel size of 400 × 400. In the first step, users are required to select 4 images out of the image pool and organize these images in a story order. Then, users are required to select 1 image for drawing their secrets. Different from the CD-GPS scheme on a computer, users can utilize the multi-touch with two fingers to complete their drawings in the developed multi-touch enabled CD-GPS scheme. The multi-touch enabled CD-GPS scheme also divides an image into a 16 × 16 table with 256 clickable squares in which each square has a pixel size of 25 × 25.

Fig. 2 (b) shows the authentication process in our developed example system. When users finish their drawings, the authentication system collects all the inputs (e.g., clicked squares' coordinates) and multi-touch information (i.e., coordinates with multi-touch), and then constructs a signature in the phase of signature construction. Take the clicks in Fig. 1 as an example, if the squares with 2 and 3 are clicked with multi-touch, the relevant plaintext signature is recorded as: {(3, 1), multi-touch{(4, 2), (5, 2)}, (3, 3)}. In the phase of signature comparison, the authentication system can detect an imposter by comparing current collected signature with the pre-defined normal signature. The comparison process is described as follows: -If signature matching is successful, then the user is regarded as a legitimate user.

-If signature matching is failed, then the user is regarded as an imposter.

Finally, the authentication system outputs the decision and can require users to perform extra validation (i.e., inputting a correct PIN) if they are identified as imposters. In addition, Fig. 2 (c) illustrates an example of single touch and multi-touch on a selected image (fruit theme) in the example system. Users can use either single touch or multi-touch to draw their own secrets.

In the evaluation, the above example system of multi-touch enabled CD-GPS was implemented on an Google/HTC Nexus One Android phone (with resolution 480 × 800 px and CPU 1GHz). In the current smartphone market, Android OS and iOS make up the largest share with a combined 80% of smartphones [START_REF]Mobile mix: The mobile device index[END_REF]. In addition, the merits of using this particular phone is that its stock Android system can be replaced by a modified customized OS version. Specifically, we updated the phone with a modified Android OS version 2.2 based on CyanogenMod 5 . The modification mainly consists of changes to the application framework layer to record the multi-touch input and relevant coordinate information from the touchscreen. The implementation details are similar to our previous work [START_REF] Meng | Touch Gestures Based Biometric Authentication Scheme for Touchscreen Mobile Phones[END_REF].

Experimental Methodology

To evaluate the performance of the multi-touch enabled CD-GPS scheme, we conducted an in-lab user study that consisted of three major experiments with totally 60 participants those who were interested in our work. All participants are volunteer with diverse backgrounds including both students and senior people. Particularly, 30 participants (13 females and 17 males) are from the computer science department (but not security related major). All participants are regular web, mobile phone users and ranged in age from 18 to 55 years. The detailed information of participants is shown in Table 1. In the user study, we mainly attempt to identify the effect of multi-touch by collecting user's feedback. To avoid any bias, we employed a double-blind manner in the user study that we did not uncover the name of these two schemes but we introduced our objectives in the user study and gave a detailed description of using these two example systems. Specifically, the original CD-GPS scheme was implemented on a computer with mouse as the input device [START_REF] Meng | Designing Click-Draw based Graphical Password Scheme for Better Authentication[END_REF] while the multi-touch enabled CD-GPS scheme was deployed on an Android phone with a touchscreen as the input device. To further avoid the bias of platforms, we evaluate the multi-touch enabled CD-GPS scheme by enabling and disabling multi-touch on the Android phone respectively.

Every participants can complete 3 practice trials for each scheme to get familiar with the platforms before they start to complete real trails. Therefore, a total of three experiments were conducted with the same 60 participants and the detailed steps in each experiment are described as below:

-Experiment1. This experiment was conducted on a desktop computer and each participant had to create 5 CD-GPS passwords.

• In the second day, all participants were required to complete a login session and gave their feedback.

• Step 4. CD-GPS Login: Logging in the example system with all created CD-GPS passwords. Users can cancel an attempted login if they noticed an error and try again. • Step 5. Feedback: All participants should complete a feedback form about the password login. -Experiment2. This experiment was conducted on an Android phone by enabling the action of multi-touch, and the steps are similar to Experiement1.

• Step 1. Multi-touch enabled CD-GPS scheme Creation: Creating 5 CD-GPS passwords based on the two steps in the scheme. Multi-touch is available during the creation.

• Step 2. Multi-touch enabled CD-GPS scheme Confirmation: This step is similar to Experiment1, but multi-touch is enabled.

• Step 3. Feedback collection.
In the second day, all participants were required to complete a login session and gave their feedback.

• Step 4. Multi-touch enabled CD-GPS scheme Login: Logging in the example system with all created passwords. The action of multi-touch is enabled.

• Step 5. Feedback collection.
-Experiment3. This experiment was conducted on an Android phone by disabling the action of multi-touch with the purpose of avoiding the bias regarding the platforms. The steps are similar to Experiment2.

• Step 1. Multi-touch disabled CD-GPS scheme Creation: Creating 5 CD-GPS passwords based on the steps in the scheme. Multi-touch is disabled during the creation. • Step 2. Multi-touch disabled CD-GPS scheme Confirmation: Confirming the password with multi-touch disabled. • Step 3. Feedback collection.

In the second day, all participants were required to complete a login session and gave their feedback.

• Step 4. Multi-touch disabled CD-GPS scheme Login: Logging in the example system with all created passwords. Different from Experiment2, the action of multi-touch is disabled.

• Step 5. Feedback collection.
Ten-point Likert scales were used in each feedback question where 1-score indicates strong disagreement and 10-score indicates strong agreement. We denoted 5-score as the meaning of "It is hard to say" for a question. In the analysis, these collected questions and scores for each experiment can be used to investigate the impact of multi-touch on creating graphical passwords. During the evaluation, 300 real trails were recorded for Experiment1, Experiment2 and Experiment3 respectively.

Results and Analysis

In this section, we present the results obtained in the experiments and analyze the results by means of the collected users' feedback. The success rate and average completion time regarding the step of creation, confirmation and login in Experiment1, Experiment2 and Experiment3 are shown in Table 2.

Particularly, the success rate in the step of Creation means that participants created their passwords without restarting, the success rate in the step of Confirmation means that participants confirmed their passwords without restarting and failed attempts for the first time, while the success rate in the step of Login means that participants, for the first time, pressed the login button and entered into the example system successfully. The average completion time is an average value computed by all participants. Success Rate. In Experiment1, as shown in Table 2, the success rate is 74.3% in the Creation step, several participants restarted the password creation (i.e., click-drawing another secret) because they changed their minds in drawing the secrets. The success rate is 90.3% in the Confirmation step, some restarting and failed attempts were detected since these participants clicked a wrong square. In the Login step, most participants could enter their passwords successfully with a success rate of 84.7%, some failed attempts were identified since these participants forgot their selected images or clicked on a wrong square for the first time.

In Experiment2, the success rate is 90% in the Creation step which is higher than the corresponding results in both Experiment1 and Experiment3. The success rate achieves 96% in the Confirmation step which is also higher than both Experiment1 and Experi-ment3. Most participants indicated that they could create and confirm their passwords more easily by using the action of multi-touch. That is, it is easier for them to remember their passwords by reducing the number of touch gestures. In the Login step, the success rate again achieves a higher value of 92% compared to both Experiment1 and Experiment3. Participants indicated that the action of multi-touch could facilitate their construction and memorization.

In Experiment3, by disabling the multi-touch, the success rate is decreased to 86%, 92% and 88.3% with regard to the Creation step, Confirmation step and Login step respectively. Participants indicated that they should use more touch gestures to construct a secret without multi-touch. But the results obtained in this experiment are still better than those obtained in Experiment1. Participants reflected that they could use a touch gesture more conveniently and accurately than a mouse-click.

Completion Time. In Experiment1, the average completion time is around 20 seconds in the Creation step since participants should spend more time in deciding the imageorder and selecting the images. The average consuming time is gradually decreased to 15.7 seconds and 14.3 seconds in the Confirmation step and Login step respectively. The main reason is that participants only need to re-create their passwords without spending additional time in constructing a new one.

In Experiment2, the average completion time is 12.1 seconds regarding the Creation step, which reduces about 40.1% of the time consumption in creating the passwords compared to Experiment1. The same as Experiment1, the average time consumption in Experiment2 continuously decreases to 7.1 seconds and 7.6 seconds for the Confirmation step and Login step respectively. Most participants indicated that they could create and confirm the passwords more quickly by utilizing the action of multi-touch. Moreover, it is visible that the standard deviation (SD) is further reduced in Experiment2 than that in Experiment1 (i.e., for the Creation step, SD 7.6 for Experiment1 while SD 5.3 for Experiment2), which shows that participants can generally create their passwords more quickly in Experiment2.

In Experiment3, compared with the result in Experiment2, the average completion time is increased to 16.8 seconds, 11.2 seconds and 9.6 seconds for the Creation step, Confirmation step and Login step respectively. The reason is that participants should spend more time in single touching without the action of multi-touch. For example, selecting two clickable squares, we should use two single touches instead of a multitouch. But similar to the situation regarding the successes rate, the results are still better than those in Experiment1, the main reason is that it is more convenient to use a touch gesture than a mouse-click for a participant.

The Number of Clicks. To further analyze the experimental results, we present the click information in Table 3. This table shows that in Experiment1, most participants prefer the number of 5 and 6 clicks with the percent of 32.6% and 30.7% respectively. For the number of 7 and 8 clicks, the percent of trails is 18.7% and 7.3%, and there is no participant click above 9 squares. The results in Experiment3 is similar to the Experiment1, but there are 3.3% trails selecting 9 squares. The reason is that participants feel more convenient to use a touch gesture than a mouse-click.

In Experiment2, it is visible that most participants prefer to click 6 and 8 squares to construct their secrets with the percent of 36% and 24%. For the number of 7 clicks, the percent is 18.3%. Compared to Experiment1, there are about 6.7% and 3.3% of total trails in Experiment2 clicking 9 and 10 squares whereas no participants choose to draw secrets with 4 clicks. The situation is similar when compared to Experiment3 (i.e., there are 7% trails constructing passwords using only 4 squares and no trail selecting 10 squares in Experiment3). The major reason is that most participants prefer to create passwords using multi-touch on the Android phone in which a single click of multitouch can select two squares. By means of only 4 multi-touch clicks, a participant can easily draw a secret with 8 squares.

Feedback Result. We present several questions used in the feedback step and corresponding scores in Table 4. The scores in the table are simply average values calculated by the recorded scores of all participants.

The scores in the No.2 and No.3 questions indicate that, on the same platform of mobile phones, two schemes are accepted by most participants while most participants feel more comfortable to create passwords using the multi-touch enabled CD-GPS scheme. In comparison, the No.1 question receives a lower score of 7.5 with regard to the platform of a PC. Similarly, for the No.4, No.5 and No.6 questions, the multi-touch enabled CD-GPS scheme obtains the highest score of 9.2. This means that most participants These results of the feedback show that utilizing the action of multi-touch can further enhance the graphical password in the aspect of usability. In addition, users can increase the password entropy by using several multi-touch clicks.

Usability and Security Discussion. For the usability, the scores regarding Experi-ment2 and Experiment3 (these two experiments were conducted on the same platform) indicate that most participants prefer the multi-touch enabled CD-GPS scheme in which they can use multi-touch to create passwords more quickly and comfortably. Back to Table 2, it is visible that participants indeed perform better in Experiment2 by utilizing the multi-touch with regard to each step of creation, confirmation and login. Overall, these results show that the action of multi-touch can enhance the usability of the CD-GPS scheme by speeding up the password input.

For the security, as we analyzed in Section 3, by integrating the multi-touch with only 2 fingers, the password space can be enlarged by K i ! 2! times (K i means the number of clicked squares). As shown in Table 3, participants are likely to click more squares in Experiment2 than Experiment3. For example, there are about 3.3% trails clicking 10 squares to construct passwords in Experiment2 whereas no participant clicks 10 squares in Experiment3. Also, there are 24% trails clicking 8 squares in Experiment2 but only 8.3% trails in Experiment3. In addition, no participant chooses 4 squares to create their passwords in Experiment2 while up to 7% trails clicking 4 squares in Experiment3. In this case, if a participant select 8 squares by means of multi-touch, the password space can be enlarged by 8! 2! = 20160 times compared to the original CD-GPS scheme. On the whole, these results indicate that the action of multi-touch can generally enhance the security of the CD-GPS scheme because users are more likely to select larger number of squares to construct their passwords through remembering less number of touches on touchscreen devices such as mobile phones.

Related Work

In recent years, a number of graphical password schemes have been proposed aiming to enhance the user authentication [START_REF] Suo | Graphical Passwords: A Survey[END_REF]. Blonder [START_REF] Blonder | Graphical Passwords[END_REF] first designed a click-based graphical password scheme that users could generate their passwords by clicking on several predefined locations on an image. For authentication, users are demanded to re-click same locations. Then, graphical password based authentication systems like PassPoints system [START_REF] Wiedenbeck | Passpoints: Design and Longitudinal Evaluation of A Graphical Password System[END_REF], Story scheme [START_REF] Davis | On User Choice in Graphical Password Schemes[END_REF], DAS (Draw-a-secret) scheme [START_REF] Jermyn | The Design and Analysis of Graphical Passwords[END_REF], Cued Click Points (CCP) [START_REF] Chiasson | Graphical Password Authentication Using Cued Click-Points[END_REF] and Qualitative DAS scheme [START_REF] Lin | Graphical Passwords & Qualitative Spatial Relations[END_REF] are developed on a common computer.

With the rapid development of mobile computing, more work of designing graphical passwords has been studied on a mobile device. Dunphy et al. [START_REF] Dunphy | A Closer Look at Recognition-based Graphical Passwords on Mobile Devices[END_REF] presented different challenges such as shoulder surfing and intersection attack in the field of graphical passwords, and investigated the deployment of recognition-based graphical password mechanisms on a mobile device. Their experiments showed that user acceptance was often driven by convenience and login durations of approximately 20 seconds were unattractive to many users. Kim et al. [START_REF] Kim | Multi-Touch Authentication on Tabletops[END_REF] evaluated a number of novel tabletop authentication schemes that exploit the features of multi-touch interaction in order to inhibit shoulder surfing. Later, Oakley and Bianchi [START_REF] Oakley | Multi-Touch Passwords for Mobile Device Access[END_REF] presented the feasibility of constructing a graphical password with multi-touch, but their work did not give a detailed analysis. De Luca et al. [START_REF] De Luca | Touch Me Once and I Know It's You!: Implicit Authentication based on Touch Screen Patterns[END_REF] recently presented an implicit approach to improve user authentication based on the way they perform an action on current mobile devices by means of unlock patterns. However, they have not studied the impact of multi-touch on creating passwords. Several recent work about biometrics based authentication and potential attacks on touch-enabled mobile phones can be referred to [START_REF] Angulo | Exploring Touch-Screen Biometrics for User Identification on Smart Phones[END_REF][START_REF] Meng | Touch Gestures Based Biometric Authentication Scheme for Touchscreen Mobile Phones[END_REF][START_REF] Trewin | Biometric Authentication on A Mobile Device: A Study of User Effort, Error and Task Disruption[END_REF][START_REF] Zhang | Fingerprint Attack against Touch-enabled Devices[END_REF].

Different from the above work, in this paper, we mainly focus on the platform of a touchscreen mobile phone and attempt to explore the impact of multi-touch on the click-draw based graphical passwords in the aspect of usability and security. In the user study with 60 participants, we find that the action of multi-touch can generally enhance the construction of graphical passwords.

Conclusion and Future Work

Graphical passwords have been developed as a promising alternative to traditional textbased passwords. In real-world applications, we find that the creation of graphical passwords may be different on a computer and on a touchscreen mobile phone. That is, users can use more actions like multi-touch on a mobile phone than on a common computer (e.g., desktop computer).

In this work, we therefore attempt to enhance the creation of graphical passwords by using the action of multi-touch. In particular, we conducted a study of using the click-draw based graphical passwords (CD-GPS) in the evaluation, which combines the current input types in the area of graphical passwords and we further developed an example system of multi-touch enabled CD-GPS scheme on a mobile phone. We begin by analyzing the potential impact of multi-touch on computing the password space of CD-GPS and we then conducted a user study that was composed of three major experiments (named Experiment1, Experiment2 and Experiment3) with totally 60 participants. Ex-periment1 was performed on a desktop computer, while Experiment2 and Experiment3 were conducted on an Android phone. We later give a detailed analysis of success rate, completion time, the number of clicks and users' feedback in these experiments. The experimental results show that by integrating the action of multi-touch, the construction of graphical passwords can be further improved in the aspect of both security and usability, and that users are more likely to generate more secure passwords by remembering less number of touches on a mobile phone.

Our work is an early work in discussing the impact of multi-touch on creating the CD-GPS graphical passwords. The future work could include performing a even larger user study with much more participants to validate the results obtained in this work (e.g., a more systematic experiment) and discussing the implications of multi-touch on shoulder-surfing and smudge attacks. In addition, future work could also include conducting a further analysis of password patterns generated by participants with different ages to explore the effect of multi-touch, and integrating and evaluating more actions (e.g., rotate, scrolling) in creating graphical passwords on a mobile device.

Fig. 1 .

 1 Fig. 1. An example of creating CD-GPS: drawing a symbol of arrow '>'.

Fig. 2 .

 2 Fig. 2. An example system of multi-touch enabled CD-GPS scheme: (a) Multi-touch Enabled CD-GPS Scheme; (b) Authentication Process in the Example System; (c) An example of single touch and multi-touch on a selected image.

Step 1 .

 1 CD-GPS Creation: Creating a CD-GPS password by following the two steps in the scheme: image selection and secret drawing. • Step 2. CD-GPS Confirmation: Confirming the password by re-selecting images in the correct order and re-drawing secrets in the correct place. If users incorrectly confirm their password, they can retry the confirmation or return to Step 1. • Step 3. Feedback: All participants are required to complete a feedback form about the password creation and confirmation.

Table 1 .

 1 Participants information in the user study.

	Age Range Male Female
	15-25	10	10
	25-35	10	8
	35-45	6	6
	45-55	6	4

Table 2 .

 2 Success rate and average completion time for the step of creation, confirmation and login in Experiment1, Experiment2 and Experiment3.

	Experiment1	Creation	Confirmation	Login
	Success Rate (the first time)	223/300 (74.3%) 271/300 (90.3%) 254/300 (84.7%)
	Completion Time (Average in seconds)	20.2	15.7	14.3
	Standard Deviation (SD in seconds)	7.6	7.5	5.3
	Experiment2	Creation	Confirmation	Login
	Success Rate (the first time)	270/300 (90.0%) 288/300 (96.0%) 276/300 (92.0%)
	Completion Time (Average in seconds)	12.1	7.1	7.6
	Standard Deviation (SD in seconds)	5.3	3.5	3.2
	Experiment2	Creation	Confirmation	Login
	Success Rate (the first time)	258/300 (86.0%) 276/300 (92.0%) 265/300 (88.3%)
	Completion Time (Average in seconds)	16.8	11.2	9.6
	Standard Deviation (SD in seconds)	5.9	6.5	4.2

Table 3 .

 3 The number of selected squares in Experiment1, Experiment2 and Experiment3.

	# of selected squares Experiment1	Experiment2	Experiment3
	4 squares	32/300 (10.7%)	0	21/300 (7.0%)
	5 squares	98/300 (32.6%) 35/300 (11.7%) 101/300 (33.7%)
	6 squares	92/300 (30.7%) 108/300 (36.0%) 98/300 (32.7%)
	7 squares	56/300 (18.7%) 55/300 (18.3%) 45/300 (15.0%)
	8 squares	22/300 (7.3%) 72/300 (24.0%) 25/300 (8.3%)
	9 squares	0	20/300 (6.7%) 10/300 (3.3%)
	10 squares	0	10/300 (3.3% )	0

Table 4 .

 4 Several questions and relevant scores in the user study. touch can reduce the time consumption since they can increase the speed of selecting squares by using several multi-touch clicks. Regarding the No.7 and No.8 questions, participants advocate to create a password by means of multi-touch with a higher score of 9.5 while the score of the opposition is only 2.1.

	Questions	Score (average)
	1. I could easily create a password in the Experiment1	7.5
	2. I could easily create a password in the Experiment2	8.9
	3. I could easily create a password in the Experiment3	8.0
	4. The time consumption in the Experiment1 is acceptable	6.7
	5. The time consumption in the Experiment2 is acceptable	9.2
	6. The time consumption in the Experiment3 is acceptable	7.9
	7. I prefer to use multi-touch	9.5
	8. I do not prefer to use multi-touch	2.1
	feel multi-

http://code.google.com/p/androidunlockpatternswitch/.

Another graphical password classification (e.g.,[START_REF] Chiasson | A Second Look at the Usability of Click-based Graphical Passwords[END_REF][START_REF] Suo | Graphical Passwords: A Survey[END_REF]): recognition based scheme (i.e., recognizing images), pure recall based scheme (i.e., reproducing a drawing without a hint) and cued recall based scheme (i.e., reproducing a drawing with hints).

http://www.cyanogenmod.com/

Acknowledgments. We would like to thank all participants for their hard work in the experiments and thank all anonymous reviewers for their helpful comments.


Sabrina Kirrane

Alessandra Mileo

Stefan Decker

Applying DAC principles to the RDF graph data model

In this paper we examine how Discretionary Access Control principles, that have been successfully applied to relational and XML data, can be applied to the Resource Description Framework (RDF) graph data model. The objective being to provide a baseline for the specification of a general authorisation framework for the RDF data model. Towards this end we provide a summary of access control requirements for graph data structures, based on the different characteristics of graph models compared to relational and tree data models. We subsequently focus on the RDF data model and identify a list of access rights based on SPARQL query operations; propose a layered approach to authorisation derivation based on the graph structure and RDFSchema; and demonstrate how SQL GRANT and REVOKE commands can be adapted to cater for delegation of privileges in SPARQL.

A1

...

Introduction

A Data Model is an abstraction used to represent real world entities, the relationship between these entities and the operations that can be performed on the data. Database models can be broadly categorised as relational, tree and graph based. An important requirement for any of Database Management Systems (DBMSs) is the ability to protect data from unauthorised access. An Access Control Model is a blueprint for defining authorisations which restrict access to data. Discretionary Access Control (DAC), Mandatory Access Control (MAC) and Role Based Access Control (RBAC) are the predominant access control models both found in the literature and used in practice. In this paper we focus specifically on DAC and examine how it can be used to restrict access to RDF data. We base our work on the DAC model as: it has been successfully adopted by several relational DBMS vendors; because of its inherent flexibility; and its potential for handling context based authorisations in the future.

Several researchers have investigated how to add access control to RDF data. Existing approaches can be categorised as ontology based [START_REF] Costabello | Linked data access goes mobile: Context-aware authorization for graph stores[END_REF][START_REF] Sacco | An Access Control Framework for the Web of Data[END_REF], rules based and [START_REF] Jain | Secure resource description framework: an access control model[END_REF][START_REF] Dietzold | Access control on RDF triple stores from a semantic wiki perspective[END_REF][START_REF] Li | Design and application of rule based access control policies[END_REF] and inference based [START_REF] Jain | Secure resource description framework: an access control model[END_REF][START_REF] Qin | Concept-level access control for the Semantic Web[END_REF][START_REF] Javanmardi | SBAC:A SemanticBased Access Control Model[END_REF][START_REF] Ryutov | Access Control Policies for Semantic Networks[END_REF][START_REF] Amini | Multi-level authorisation model and framework for distributed semantic-aware environments[END_REF]. In previous work, which would also be categorised as inference based, we demonstrated how Annotated RDF can be used to propagate permissions assigned to triples based on RDFSchema [START_REF] Lopes | A Logic Programming approach for Access Control over RDF[END_REF]. We proposed a number of rules that can be used for the derivation of access rights based on subject, access rights and resource hierarchies [START_REF] Mileo | Protect Your RDF Data![END_REF]. In this paper, we examine the specification, derivation and delegation of access control over RDF graph data guided by DAC principles and experiences applying these principles to the relational and tree based data models. Based on our analysis, we make the following contributions:(i) discuss how DAC principles can be used to restrict access to RDF data; (ii) describe how the graph structure can be used to derive implicit access rights; (iii) propose a set of rules that are necessary for derivation of authorisations based on RDFSchema; and (iv) demonstrate how SQL grant and revoke commands can be adapted to manage RDF authorisations. Together these contributions provide a solid building block for DAC policy enforcement for the RDF data model.

The remainder of the paper is structured as follows: In Section 4 we discuss related work. Section 2 describes how DAC is used to restrict access to relational and tree based data models. Issues applying DAC to graph data are discussed and possible handling mechanisms are proposed in Section 3. Finally, we conclude and outline directions for future work in Section 5.

Preliminaries

DAC policies limit access to data resources based on access rules stating the actions that can be performed by a subject. The term subject is an umbrella term used to collectively refer to users, roles, groups and attribute-value pairs. In DAC access to resources are constrained by a central access control policy, however users are allowed to override the central policy and can pass their access rights on to other users [START_REF] Sandhu | Access control: principle and practice[END_REF], known formally as delegation. Over the years the DAC model has been extended to consider: constraint based authorisations (e.g. time, location); access to groups of users, resources and permissions; support for both positive and negative authorisations; and conflict resolution mechanisms [START_REF] Samarati | Access control: Policies, models, and mechanisms[END_REF]. In this section we describe how DAC is used to protect relational and tree based data models.

Applying DAC to the Relational Model

In the relational model (Fig. 1), data items are grouped into n-ary relations. A relation header is composed of a set of named data types known as attributes. The relation body is in turn made up of zero of more tuples i.e. sets of attribute values. A primary key, composed of one or more attributes which uniquely identifies each tuple, is defined for each relation. Relations are connected when one or more attributes (i.e. a foreign key) in a relation are linked to a primary key in another relation. Relations can be categorised as base relations or views. Base relations are actually stored in the database whereas views are virtual relations derived from other relations. Views are commonly used to: (i) provide access to In relational databases access is restricted both at a schema level (database, relations and attributes) and a data level (tuples and values). The access rights themselves are tightly coupled with database operations such as SELECT, INSERT, UPDATE, DELETE and DROP. In addition the GRANT privilege allows users to grant access to others based on their own privileges. Griffiths and Wade [START_REF] Griffiths | An authorization mechanism for a relational database system[END_REF] describe how DAC is implemented in System R [START_REF] M M Astrahan | System R : Relational Management Approach to Database[END_REF] an experimental DBMS developed to carry out research on the relational data model. Two of the underpinning principles of DAC are derivation of implicit authorisations from explicit authorisations and the delegation of access rights.

Authorisations explicitly defined at schema level are implicitly inherited by other database entities, for example (i) database authorisations are inherited by all database resources; (ii) relation authorisations are inherited by all tuples; and (iii) attribute authorisations are inherited by all attribute values. Aside from Schema level derivations Griffiths and Wade [START_REF] Griffiths | An authorization mechanism for a relational database system[END_REF] describe how views can be used to implicitly grant access to one or more tables, attributes or tuples spanning multiple relations. Under DAC database users are granted sole ownership of the tables and views that they create. They can subsequently grant access rights to other database users. Griffiths and Wade [START_REF] Griffiths | An authorization mechanism for a relational database system[END_REF] and Bertino et al. [START_REF] Bertino | An Extended Authorization Model for Relational Databases[END_REF] discuss how the revocations process is complicated due to recursive delegation of permissions and propose algorithms which are used to revoke access rights.

Applying DAC to the Tree Model

In the tree model data is organised into a hierarchical structure with a single root node. Each data item, represented as a node, is composed of one or more attributes. Relations are connected via parent-child links: whereby each parent can have many children, however each child can have only one parent. Both object-oriented databases and the Extensible Markup Language (XML) are examples of the tree model. In the remainder of this section, we focus on XML however it is worth noting that the core derivation and delegation principles can also be applied to other instances of the tree data model. In an XML data model (Fig. 2) relations are represented as elements that can contain textual information and zero or more attribute-value pairs. Simple elements contain data values whereas complex data types are constructed from other elements and/or attributes giving XML it's hierarchical structure. A Document Type Definition (DTD) or an XMLSchema describe the structure of an XML document. In contrast to the relational model, XML data is not necessarily an instance of some schema.

Bertino et al. [START_REF] Bertino | Securing XML documents with Author-X[END_REF] describe how DAC is implemented in Author-X a prototype developed to demonstrate how access control policies can be applied to XML documents, that may or may not conform to a DTD/XMLSchema, exposed on the web. Similar to the relational model, tree based access control can also be specified at both schema and data levels. From a schema perspective access can be restricted based on the structure of the document/data item, a DTD or an XMLSchema. Whereas data level restrictions can be applied to specific elements and attributes. Similar to the relational model the access rights reflect the operations commonly performed on an XML document for example READ, APPEND, WRITE, DELETE and INSERT.

Propagation of authorisations based on the is-part-of relationship between documents, elements, sub-elements and attributes is one of the key features of DAC for XML [START_REF] Bertino | Database security -concepts, approaches, and challenges[END_REF]. Although implicit authorisations simplify access control administration, a knock on effect is that exceptions need to be catered for. In XML inheritance chains can be broken by explicitly specifying authorisations for leaf nodes. In addition, a combination of positive and negative authorisation can be used to grant access in the general case and deny access for specific instances. The introduction of negative authorisation brings with it the need for conflict resolution mechanisms (e.g. denial takes precedence). Gabillon [START_REF] Gabillon | An authorization model for XML databases[END_REF] describes how delegation of privileges can be adapted to work for XML databases. The author defines a security policy language for XML which incorporates SQL GRANT and REVOKE commands.

Applying DAC to RDF

In this section we describe how the graph data model differs from the tree data model. We discuss how DAC can be applied to graph-based data and detail Although in this paper we focus on RDF specifically a number of observations can be applied to other graph data models.

Graph

The RDF Data Model

The graph data model extends the tree model by allowing each node to have multiple parent relations, resulting in a generalized graph structure. Undirected and directed binary relationships between nodes are represented as edges and arcs respectively. In a directed graph the node from which an arc originates is called the head and the destination the tail. Graphs differ from trees in several aspects, for example: a graph doesn't have a top or bottom; a node can have more than one parent; a node can be its own ancestor; and multiple paths between nodes are permissible. The graph data model is often used where information about the graph topology is just as important as the data itself. An overview of several graph based models is provided by Angles and Gutierrez [START_REF] Angles | Survey of graph database models[END_REF].

The RDF graph model is designed to represent knowledge in a distributed manner. RDF captures the semantics of data and presents it in a machine readable format. Uniform Resource Identifiers (URIs) in turn are used to uniquely identify data items. The fundamental building block of the RDF data model (Fig. 3) is an RDF triple which constitutes a statement about the relationship between two nodes. An RDF triple is represented as a tuple S, P, O ∈ UB × U × UBL3 , where S is called the subject, P the predicate, and O the object and U, B and L, are used to represent URIs, blank nodes and literals respectively. The following triples represented using N34 use the FOAF5 vocabulary, a subset of which is presented in Fig. 4, to state that the JoeBloggs is a person who's first name is Joe and lastname is Bloggs: entx : JoeBloggs rdf : type foaf : Person . entx : JoeBloggs foaf : givenName " Joe ". entx : JoeBloggs foaf : lastName " Bloggs ". RDFSchema is a set of classes and properties used to describe RDF data. Unlike XMLSchema, RDFSchema does not describe the structure of an RDF graph. Instead RDFSchema provides a framework used by vocabularies (known formally as ontologies) to describe classes, properties and relations.

In RDF there is a tight coupling between the schema and instance data. Unlike the relational and XML data models classes, properties and instances cannot be identified based on the structure alone. Like XML, Namespaces are used to uniquely identify a collection of RDF resources. Prefixes are used as a shorthand notation for ontology Namespaces. In this paper, we use the following ontologies RDF, RDFSchema(RDFS), FOAF and a sample enterprise ontology: @prefix rdf : < http :// www . w3 . org /1999/02/22 -rdf -syntax -ns # > . @prefix rdfs : < http :// www . w3 . org /2000/01/ rdf -schema # > . @prefix foaf : < http :// xmlns . com / foaf /0.1/ > . @prefix entx : < http :// urq . deri . org / enterprisex # > .

An RDF graph is a finite set of RDF triples. Named graphs are used to collectively refer to a number of RDF statements. In this paper we use TriG6 , an extension of N3, which uses curly brackets to group triples into multiple graphs identifiable by a URI (Fig. 5). In practice the triple and the named graph are stored as quads.

Graph based and Schema based Authorisations

The first step in the identification of access control requirements for RDF data is to identify the resources that need to be protected and the access rights required. The graph data model alone is quite limiting when it comes to the management of access rights. Therefore in Section 3.3, we examine how RDFSchema can be used to define more expressive authorisations.

RDF Resources. From a data perspective access can be restricted to a node (subject or object), an arc (property), two connected nodes (triple), a collection of nodes and edges (multiple triples that share a common subject) or arbitrary views of the data (named graphs). Whereas from a schema perspective authorisations can be applied to classes and properties. Given the tight coupling between schema and data items, authorisations based on classes (e.g. foaf:person) and properties (e.g. foaf:givenName) would need to be derived using schematic vocabulary such as RDFSchema or Web Ontology Language (OWL) 7 . In Section 3.3, we examine how permissions can be derived based on both the graph structure and RDFSchema.

Access Rights. The access rights of both the relational and XML data models are very similar and differ primarily by vocabulary. SPARQL proposes several operations similar to ones that exist for relational and XML data (SELECT, INSERT, DELETE/INSERT, DELETE and DROP). However SPARQL also defines a number of additional query operations (CONSTRUCT, ASK and DESCRIBE) and a number of operations specifically for graph management (CREATE, COPY, MOVE and ADD). Notable omissions from the list of SPARQL operations are the GRANT and REVOKE commands which allows users to grant access to or revoke access from others access based on their own privileges. In Section 3.4 we discuss how the grant and revoke operations could be accommodated in SPARQL.

Access Control

Policy. An Access Control Policy details the actual authorisations and access restrictions to be enforced. Each authorisation is represented as a quad Sub, Acc, Sign, Res where Sub denotes the subject (not to be confused with an RDF triple subject), Acc the access rights, Sign indicates if the user is granted or denied access and Res represents the resource to be protected (i.e. rdf quad with optional variables, represented using a ? prefix, in any position). A matrix outlining the access rights that are appropriate for each operation (represented by an X) is provided in Table 1. For conciseness two connected nodes is abbreviated to Con, a collection of nodes and edges to Col and RDF properties to Prop. A sample access control policy is in turn presented in Table 2. Each authorisation is labelled (A n ) to ease referenceability. (A 1 ), (A 2 ) and (A 3 ) grant access rights SELECT, INSERT and DELETE to the graph entx:G1, (A 4 ) grants access to a particular class and (A 5 ) denies access to the salary property.

If no explicit or implicit policy exists it is possible to adopt either a closed policy (deny access by default) or an open policy (grant access by default).

Derivation of Authorisations

In both the relational model and the tree model authorisations can be derived based on the data schema. When it comes to the RDF data model similar derivations are highly desirable as they simplify authorisation administration. Existing RDF database vendors adopt a view based approach to derivation, organising triples into named graphs based on the access control requirements and granting access to the entire graph. Although similar to views in relational databases in this instance the graph is materialised. An alternative approach would be to derive permissions based on the graph structure. However as it isn't possible to distinguish between schema and instance data such an approach alone is quiet limited. Therefore we propose an additional layer of derivations based on a vocabulary such as RDFSchema to define rules that leverage the semantic relations between nodes and edges. In the following rules both the premises (above the line) and the conclusion (below the line) are represented as a 5 tuple S, P, O, γ, λ . Where: (i) S represents a subject, P a predicate and O an object (together they represent a triple); (ii) γ is used to denote a named graph (which may or may not be the same for each triple); and (iii) λ is used to represent permissions i.e. authorisation subject, access rights and sign attributes Sub, Acc, Sign . By including the named graph in the derivation rules it is possible to constrain the derivation to a particular graph or alternatively to span multiple graphs. Such graphs in turn can be distributed across multiple data sources.

Derivation based on the graph structure. Similar to the tree model we could assign permissions to a node and recursively derive authorisations for all nodes connected to it by arcs. Another approach would be to derive authorisations for all nodes along a particular path. Existing graph search algorithms, such as those proposed by Tarjan [START_REF] Tarjan | Depth-First Search and Linear Graph Algorithms[END_REF], could be used to recursively traverse the graph and assign permissions to the nodes. A thorough investigation into the application of graph traversal and access control is proposed in future work.

Derivation based on RDFSchema. One limitation of the RDF data model is that it isn't possible to distinguish between schema and instances from the graph structure alone. For example to restrict access to attributes we would need a means to derive permissions for all instances of a particular property type. Likewise to restrict access to a relation we would need to derive permissions for all properties that are instances of a particular class. To accommodate schema based derivation a combined data approach to derivation is warranted. The following rules can be used to derive access rights based on the RDFSchema vocabulary.

Rule 1. Using this rule we can derive λ, which has been assigned to a class, for all instances of that class. ?X rdf:type rdf:Class γ λ, ?Z rdf:type ?X γ, ?Z ?Y ?A γ ?Z ?Y ?A γ λ (R1)

Rule 2. In this rule, λ which has been assigned to a property of a class, is derived for all instances of that property.

?X rdf:type rdf:Class γ, ?Y rdf:type rdf:Property γ λ, ?Y rdfs:domain ?X γ, ?Z ?Y ?A γ ?Z ?Y ?A γ λ (R2) Rule 3. The following rule propagates λ, assigned to an instance of a class, to property values associated with that instance.

?X rdf:type rdf:Class γ, ?Z rdf:type ?X γ λ, ?Y rdfs:domain ?X γ, ?Z ?Y ?A γ ?Z ?Y ?A γ λ (R3) Given a snapshot of the FOAF ontology (Fig. 4), a subset of an enterprise RDF dataset (Fig. 5) and a sample access control policy (Table . 2), we can derive additional authorisations such as those summarised in Table 3. (DA 1 ) to (DA 8 ) were derived by applying R1 to (A 4 ). Whereas (DA 9 ) and (DA 10 ) were inferred from R3 and (A 5 ). Two additional rules which use the rdfs:subclass (R4) and rdfs:subproperty (R5) properties are proposed to demonstrate flexibility that can be gained from RDFSchema. More expressive rules based on richer vocabularies such as OWL could also be used. The database should be flexible enough to allow derivations to be turned on and off on a case by case basis. Rule 4. In this rule we use the RSFSchema subclass inheritance mechanism to derive the permissions λ assigned to a class for all subclasses. ?X rdf:type rdf:Class γ λ, ?Y rdf:type rdf:Class γ, ?Y rdfs:subClassOf ?X γ ?Y rdf:type rdf:Class γ λ (R4)

Rule 5. Similar to the above rule however in this instance we use the subproperty inheritance to derive the permissions λ assigned to a property for all subproperties.

?X rdf:type rdf:Property γ λ, ?Y rdf:type rdf:Property γ, ?Y rdfs:subPropertyOf ?X γ ?Y rdf:type rdf:Property γ λ (R5)

Delegation of Access Rights

In both relational and XML databases GRANT and REVOKE commands are used to manage delegation of access rights. The SPARQL 1.1 update language does not currently support the GRANT and REVOKE commands. It thus needs to be extended to cater for authorisation administration and delegation of access rights. We propose an adapted version of the SQL GRANT (Def.1) and REVOKE (Def.2) commands that caters for named graphs. We adopt the US-ING NAMED clause from other SPARQL 1.1 operations.

( USING ( NAMED )? IRIref )*

In addition in keeping with standard SPARQL we adapt the syntax of the GRANT OPTION replacing surrounding [] with () and a ? which indicates cardinality.

( WITH GRANT OPTION )?

Privilege name denotes the privileges identified in Section 3. As revocation is not dependent on the data model existing approaches, such as cascading [START_REF] Fagin | On an authorization mechanism[END_REF][START_REF] Griffiths | An authorization mechanism for a relational database system[END_REF] and non-cascading [START_REF] Bertino | Authorizations in relational database management systems[END_REF], devised for relational databases would also work for rdf databases (datastores).

Conflict Resolution

Conflicts can occur as a result of inconsistent: explicit; derived; and delegated policies. Samarati [START_REF] Samarati | Access control: Policies, models, and mechanisms[END_REF] discusses the need for different conflict resolution depending on the situation. Earlier in this section, we proposed a number of derivation rules to ease RDF access control administration and stated that implicit authorisations should be overridden by explicit authorisations. It is important that the conflict resolution strategy proposed is in keeping with both the derivation rules and overriding mandate. In this paper, we propose three complementary approaches to conflict resolution that fit well with DAC: (i) explicit policies override implicit policies (ensures that positive explicit authorisations will always prevail over negative implicit authorisations); (ii) most specific along a path takes precedence (allows users to grant access in the general case and deny access for specific instances); and (iii) denial takes precedence (caters for scenarios where we have a conflict between two explicit or two implicit authorisations). In Section 3.3, we seen how derivation rules can result in conflicting authorisations, for example Table 3 (DA 4 ) and (DA 9 ) or (DA 8 ) and (DA 10 ). As both policies are implicit the explicit policies override implicit policies strategy is not applicable. In this instance the negative authorisation would prevail based on the most specific along a path takes precedence, as a policy assigned to a property is more specific than one applied to a class.

Related Work

Both Costabello et al. [START_REF] Costabello | Linked data access goes mobile: Context-aware authorization for graph stores[END_REF] and Sacco et al. [START_REF] Sacco | An Access Control Framework for the Web of Data[END_REF] propose access control vocabularies and frameworks that can be used to enforce access control policies over RDF Data. In both instances the authors provide a filtered view of data using SPARQL ask queries. However the authors do not perform any reasoning over the access control policies they propose.

Other researchers adopt a rule based approach to access control. Dietzold and Auer [START_REF] Dietzold | Access control on RDF triple stores from a semantic wiki perspective[END_REF] define access control requirements from a Semantic Wiki perspective. The authors propose a filtered data model using a combination of SPARQL queries and SWRL rules. Li et al. [START_REF] Li | Design and application of rule based access control policies[END_REF] also adopt a rule based approach providing users with a more intuitive way to specify access control policies. Both Dietzold and Auer [START_REF] Dietzold | Access control on RDF triple stores from a semantic wiki perspective[END_REF] and Li et al. [START_REF] Li | Design and application of rule based access control policies[END_REF] use rules to give a more explicit meaning to the access control policies as opposed to authorisation derivation in our case.

Several reseachers Qin and Atluri [START_REF] Qin | Concept-level access control for the Semantic Web[END_REF], Javanmardi et al. [START_REF] Javanmardi | SBAC:A SemanticBased Access Control Model[END_REF], Ryutov et al. [START_REF] Ryutov | Access Control Policies for Semantic Networks[END_REF], Amini and Jalili [START_REF] Amini | Multi-level authorisation model and framework for distributed semantic-aware environments[END_REF] propose access control models for RDF graphs and focus on policy propagation and enforcement based on semantic relations. None of the authors examine access control from either a data model or a database perspective. Similar to us, Jain and Farkas [START_REF] Jain | Secure resource description framework: an access control model[END_REF] derive authorisations and propose conflict resolution mechanisms. They adopt a multilevel label-based approach to access control where policies are specified in terms of RDF patterns associated with an instance, a schema and a security classification. The derivations they propose are however limited to RDFSchema entailment rules.

Only Jain and Farkas [START_REF] Jain | Secure resource description framework: an access control model[END_REF] and Javanmardi et al. [START_REF] Javanmardi | SBAC:A SemanticBased Access Control Model[END_REF] actually mention DAC and even then they just describe DAC and do not examine how their approach compares or contrasts. A number of authors who use Semantic Technology for access control however do not apply their approach to the RDF data model, detail their support for DAC Kodali et al. [START_REF] Kodali | Multimedia access control using rdf metadata[END_REF], Damianou et al. [START_REF] Damianou | The ponder policy specification language[END_REF], Berners-Lee et al. [START_REF] Berners-Lee | Creating a Policy-Aware Web: Discretionary, Rule-based Access for the World Wide Web[END_REF]. However to the best of our knowledge to date no one has investigated the application of DAC to the RDF data model. We fill this gap by examining how DAC has been used to protect the relational and tree data models and by proposing strategies that allow us to apply DAC to the RDF graph model. We identify the resources to be protected and the access rights required, based on the RDF data model and SPARQL 8 the predominant RDF query language respectively. In addition we propose mechanisms to assist with access control administration through derivation of authorisation, delegation of permissions and conflict resolution

Conclusions and Future Work

Although the RDF data model has been around for over a decade, little research has been conducted into the application of existing access control administration to RDF data. In this paper we discussed how the DAC model could be applied to RDF, a distributed graph based data model. We identified the resources to be protected and the access rights required based on the graph data model and SPARQL query operations respectively. We proposed a layered approach to authorisation derivation based on the graph structure and RDFSchema. We subsequently identified a number of rules that can be used to manage authorisations in an intuitive manner. Furthermore we demonstrated how SQL GRANT and REVOKE commands could be adapted to cater for authorisation administration over RDF data. As for future work, we propose to further investigate how enforcement of access control policies can be improved by exploiting the graph data structure and to examine complexity issues related to management of authorization over graph data.

Fig. 1 .

 1 Fig. 1. Relational Data Model

Fig. 2 .

 2 Fig. 2. XML Tree Model

Fig. 3 .

 3 Fig. 3. RDF Graph Model

Table 3 .

 3 Snapshot of Derived Authorisations

	Sub	Rights	Sign Obj
	(DA1) Emp SELECT + entx:JoeBloggs rdf:type foaf:Person entx:G1
	(DA2) Emp SELECT + entx:JoeBloggs foaf:givenName "Joe" entx:G1
	(DA3) Emp SELECT + entx:JoeBloggs foaf:lastName "Bloggs" entx:G1
	(DA4) Emp SELECT + entx:JoeBloggs entx:salary "40000" entx:G1
	(DA5) Emp SELECT + entx:MayRyan rdf:type foaf:Person entx:G1
	(DA6) Emp SELECT + entx:MayRyan foaf:givenName "May" entx:G1
	(DA7) Emp SELECT + entx:MayRyan foaf:lastName "Ryan" entx:G1
	(DA8) Emp SELECT + entx:MayRyan entx:salary "80000" entx:G1
	(DA9) Emp SELECT -	entx:JoeBloggs entx:salary "40000" entx:G1
	(DA10) Emp SELECT -	entx:MayRyan entx:salary "80000" entx:G1

  1 (SELECT, CON-STRUCT, ASK, DESCRIBE, INSERT, DELETE/INSERT, DELETE, DROP, COPY, MOVE, ADD). Resource name represents one or more instances of the following RDF resources (NAMED GRAPH, CLASS, PROPERTY, TRIPLE).User name, role name, attribute value are used to identify users, roles and attributes respectively and a reserved word PUBLIC is used to assign access to all users. Finally the WITH GRANT OPTION is used to provide users with the ability to delegate the access right(s) to others.

	Definition 1 (GRANT command).
	GRANT privilege_name
	( USING ( NAMED )? IRIref )*
	ON resource_name
	TO { user_name | PUBLIC | role_name | attribute_name }
	( WITH GRANT OPTION )?;
	Definition 2 (REVOKE command).
	REVOKE privilege_name
	( USING ( NAMED )? IRIref )*
	ON resource_name
	FROM { user_name | PUBLIC | role_name | attribute_value_pair }

For conciseness, we represent the union of sets simply by concatenating their names.

http://www.w3.org/TeamSubmission/n3/

FOAF Vocabulary Specification, http://xmlns.com/foaf/spec/.

http://www.w3.org/2010/01/Turtle/Trig/

Acknowledgements. This work is supported in part by the Science Foundation Ireland under Grant No. SFI/08/CE/I1380 (Lion-2), the Irish Research Council for Science, Engineering and Technology Enterprise Partnership Scheme and Storm Technology Ltd. We would like to thank Nuno Lopes and Aidan Hogan for their valuable comments on the paper.