Abdelfattah Amamra
email: abdelfattah.amamra.1@ens.etsmtl.cachamseddine.talhi@etsmtl.cajean-marc.robert@etsmtl.ca

Chamseddine Talhi

Jean-Marc Robert

Impact of Dataset Representation on Smartphone Malware Detection Performance

Keywords: Smatphone security, system calls, intrusion detection, machine learning, Anomaly technique

Improving Smartphone anomaly-based malware detection techniques is widely studied in recent years. Previous studies explore three factors: dataset size, dataset type and normal profile model. These factors improve the performance, but increase computation complexity and the required memory space. In this paper we explore a new factor: the dataset representation. Dataset representation is the format adopted to organize and represent data. To investigate the impact of this factor, we examine four machine learning classifiers with three different dataset representations. Those dataset representations are: successive system calls, bag of system calls and patterns frequency system calls. The used dataset is a collection of system call traces of Smartphone executing Android 2.2. We analyse the performance of each classifier and deduce the influence of dataset representation on accuracy and false positive rates. The results show that the dataset representation has a potential impact on the performance of classifiers with low computational and memory cost.

Introduction

Smartphones are very popular and widely used in business and personal life in recent years due to their capabilities and services. Therefore, their market is growing very fast. According to the International Data Corporation (IDC), they expect about 982 million units will be shipped by the end of 2015 [START_REF] Amamra | Performance Evaluation of Multi-pattern Matching Algorithms on Smartphone[END_REF]. This popularity of Smartphones attracts malware developers. Google recently found about 50 applications that were infected with hidden malicious code DroidDream. The applications were loaded in the official applications store (Android Market). They were available for about 4 days and between 50,000 and 200,000 copies were downloaded [START_REF] Amamra | Performance Evaluation of Multi-pattern Matching Algorithms on Smartphone[END_REF]. Thereby, the need of malware detection tool is now more curial. Smartphone malware detection techniques are classified broadly into two main classes: signature-based and anomaly-based [START_REF] Amamra | Smartphone Malware Detection: From a Survey Towards Taxonomy[END_REF]. Signature-based techniques look for patterns that match with malware patterns in their database. Anomaly-based techniques maintain normal behavior profiles and any deviation from these profiles is considered malicious [START_REF] Amamra | Smartphone Malware Detection: From a Survey Towards Taxonomy[END_REF]. The main advantage of anomaly detection techniques is the ability to detect unknown malwares. Therefore, they have been actively investigated. However, anomaly-based malware detection still needs more investigation and improvement to reduce false positive and increase detection accuracy. Prior works explored actively the factors having an impact on the performance of anomaly-based detection techniques. They examined three factors: dataset size, dataset type, and the model of normal profile. From related work, we can learn that increasing the quantity of dataset or varying the data type used to characterize normal behavior profile improves the normal profile accuracy. However, the resulting profile has usually high computational and memory space overhead. Therefore, these factors are not suitable to improve performance of anomaly-based detection technique on limited resources environment, such as Smartphone. Thereby, we should explore other factors that have significant influence on the performance of anomaly-based technique as well as low computation and memory cost. In this work, we highlight the dataset representation factor. We examine the impact of this factor on the performance of anomalybased technique on Smartphone system call traces. Dataset representation is the format of how the data is organized and represented. This format is used during the training phase as well as the detection phase. The process of preparing dataset representation has light computation cost and memory complexity which make it suitable approach for Smartphone malware detection technique.

In this study, we examine three dataset representations on Smartphone system call traces. Those representations are:

 Successive system calls representation, where the ordering information between system calls in sequence is considered. This dataset representation is used in prior work.  Bag of system calls representation, where the successiveness of system calls in sequence is disregarded and only the frequency of each system call is preserved. It is used in prior work.  Patterns frequency system calls representation combines features of the two previous representations. Pattern-frequency representation regards the successive order information of system calls in short pattern, and regards the frequency of each pattern in the sequence. To the best of our knowledge, this representation has not been studied in the past.

We evaluate performance of different machine learning classifiers with the above dataset representations and we deduce the influence of each dataset representation on the performance of each classifier. We select the most known and used classifiers: Support Vector Machine (SVM), Naïve Bayes (NB), Logistic Regression (LR), and the Decision Tree (DT). We experiment our approach on system call traces collected from an HTC Dream Smartphone. These system call traces represent the execution of the 100 most downloaded normal applications and the 90 available real malwares.

The rest of this paper is organized as follows: related work is introduced in section 2. Section 3 presents the dataset presentations. Section 4 presents experiments and results analysis. We end with conclusion in section 5.

Related work

Smartphones malware detection techniques based on system traces such as system calls and system events studied actively in recent years. Several classifiers and datasets types are investigated to produce more accurate model. This comes with more memory and computational cost. Bose et al [START_REF] Bose | Behavioral detection of malware on mobile handsets[END_REF] introduced framework to detect mobile malwares. The framework based on Support Vector Machine (SVM) classifier and temporal logic of causal knowledge (TLCK) to represent the applications behaviors. The application behaviors are constructed from several data: system events, resource accesses and API calls in Symbian OS. The authors studied only 25 distinct malicious behaviors. Shabtai et al [START_REF] Shabtai | Andromaly: a behavioral malware detection framework for android devices[END_REF] proposed a framework using machine learning classifiers to detect new malwares. These classifiers are: k-means, Logistic Regression, Histograms, Decision Tree, Bayesian Networks and Naïve Bayes. The normal behavior is constructed from various system metrics like CPU consumption, number of sent packets through Wi-Fi, number of running processes and battery level. Xie et al [START_REF] Xie | pBMDS: a behavior-based malware detection system for cellphone devices[END_REF] adopted Hidden Markov Model (HMM) to build normal behavior. The training dataset is a combination of user inputs and applications system calls. HMM classifier is powerful, but computationally expensive which make it not suitable to limited resources environment. Zhao et al [START_REF] Zhao | RobotDroid: A Lightweight Malware Detection Framework On Smartphones[END_REF] presented software behavior signature framework called RobotDroid. It runs on Android OS phones. This Framework is based on Support Vector Machine (SVM) active learning algorithm. The classifier is trained on three malwares families: Plankton, DroidDream and Geinimi. The application behaviors are defined as intent issued and system resources accessed by applications. Burguera et al [START_REF] Burguera | Crowdroid: Behavior-Based Malware Detection System for Android[END_REF] proposed a framework named Crowdroid running on Android OS platform. The proposed framework collects system call traces, organizes them in bag of system call representations and applies k-means algorithm to classify them into two categories: normal and malware. The shortcoming of this technique is the fact that the system always divides the system call dataset into two classes even if there is no malware. Amamra et al [START_REF] Amamra | Enhancing Smartphone Malware Detection Performance by Applying Machine Learning Hybrid Classifiers[END_REF] proposed hybrid machine learning classifiers using stacking method to improve the classification process. The classifiers trained and tested with system call traces. These system calls are collected from 100 normal applications and 90 malwares. Hybrid classifiers improve accuracy performance with high computational cost. Pathak et al [START_REF] Pathak | Fine-grained power modeling for smartphones using system call tracing[END_REF] proposed a new system calls based on power modeling framework. This framework consists of two main components: (1) Finite State Machines (FSM) to model the power states and state transitions of each component as well as the whole smartphone, (2) testing application suite which leverages the domain knowledge of system calls to systematically uncover the FSM transition rules. Buennemeyer et al [START_REF] Buennemeyer | Mobile Device Profiling and Intrusion Detection using Smart Batteries[END_REF] proposed B-SIPS (Battery-Sensing Intrusion detection Protection System). B-SIPS monitors the power consumption of Bluetooth and Wi-Fi communication channels to detect intrusion activities. The anomalous activities are de-tected if the power consumption level exceeds the system's dynamic threshold value.

Power based malware detection technique detects only malwares have an impact on device power level, whereas many malwares have normal power level consumption.

System Calls Representations

Roughly speaking, a system call trace is a chunk of information. That information is formatted and organized in a dataset D as shown in Fig 1 . The dataset D has a specific format that expresses how the data is organized. This format is called dataset representation and it is used during training as well as detection phases of machine learning classifiers.

Fig. 1. System call trace transformation to Dataset

Given the dataset D, the purpose of the machine learning algorithms is to find a classifier C: D {normal, malicious} that maximizes accuracy and minimizes false positive rate. Dataset representation has an impact on the accuracy and false positive rate of the machine learning classifier.

For harmony definitions of the three system calls representations, we consider the set of system calls Σ = {s1, s2, s3… sm}, where m is the number of system calls of operating system. Let S i be finite sequence of system calls and |S i | is the length of the sequence. Let Σ * be the set of all possible finite sequences of system calls, Si∈Σ * . N is the number of applications (normal and malware) used in training and test phases.

Successive system calls representation

This representation considers the sequential order information of system calls in sequence. Formally, this representation can be defined as follow: Dataset D is a set of finite sequences of successive system calls generated by different executed applications. The dataset D can be defined formally as: D = {<Si, Ti> | Si∈Σ * , Ti ∈{normal, malicious}} where Si is a finite sequence of system calls generated by an application i and Ti indicates whether this application is normal or malicious. Fig 2 shows an example of successive system calls representation.

System calls trace

Dataset Transformation

Fig. 2. Successive System Calls

The memory complexity of successive system calls representation is depends on the number of sequences S i in the database (N) and the total length of sequences. The memory complexity is

The total length of sequences is big number, therefore this representation is costly.

Bag of system calls representation

This representation disregards the ordering information of sequential system calls.

Only the frequency of system calls in the sequence is maintained. Formally, the representation can be defined as follow: Let dataset D be the set of features X. The feature Xi is defined as a list Xi = <n1, n2, n3, …, nm>, where m =|Σ| and nj is the number of occurrence of a system call sj in the sequence Si.

Fig 3 illustrates bag system call representation of a normal application. Each number in the sequence represents the frequency of a system call in application trace. For example, the numbers 5,0,0,10,75,…. correspond to frequency of the following system calls: fstat64, setgroups32, setgid32, setuid32, getuid32 respectively. The last attribute in figure 3 indicates the sequence for normal application. 5,0,0,10,75,0,0,0,0,0,01,1,3,0,0,4,0,0,0,0,203,25,62,58,0,0,0,0,0,0,0,0,0,0,0,0,35,101,0 ,0,0,0,0,0,0,0,0,0,36,0,0,0,0,0,4,0,10,0,0,0,0,0,0,0,0,0,0,0,0,513,0,0,0,0,0,0,0,0,97,607 2,1617,142,360,0,1,0,0,0,0,0,0,0,0,90,0,0,0,00,0,0,0,0,0,0,0,108,0,0,0,8,0,0,0,0,0,0,0,0 ,0,0,0,0,0,0,0,0,0,0,0,0,0,10,0,0,0,0,85,353,0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,25,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,00,0,0,0,0,2575,40,0,0,normal

Fig. 3. Bag System call Representation

The memory complexity of bag of system calls representation is O(N*|Σ|), where N is the number of sequences and |Σ| is number of system calls. |Σ| is a small number. For example, Linux 2.6 has 326 system calls [START_REF] Organization | Linux 2.6 System calls Table[END_REF], then |Σ| = 326. The cost of this representation is much less than successive system calls representation cost because |Σ| is very small than

l-Patterns frequency of system calls representation

This representation combines features of the two previous representations. Patternfrequency representation regards the successive order information of system calls in a short patterns, and regards the frequency of those patterns in a sequence. Formally, the representation can be defined as follow: Let P be the set of all possible patterns of length l, P = {p 1 , p 2 , p 3 …p r }, where r =|Σ l |. Dataset D is set of features Y. The feature Yi is defined as an ordered list Yi = <n1, n2, n3, …, nr>, where nj is the number of occurrence of a pattern pj in the sequence Si. Fig 4 illustrates 3-pattern frequency representation of a normal application. Each number represents the frequency of pattern of 3 system calls length. For example, the numbers 15,0,30,219,1,…. represents the following: the pattern: (open, fstat64, mprotect) is repeated 15 times, the pattern: (close, close, close) is repeated 0 time, the pattern: (mmap2, mprotect, clone) is repeated 30 times, the pattern: (futex, futex, gettimeofday) is repeated 219 times, and the pattern: (access, access, mkdir) is repeated 1 time. The last attribute in figure 4 indicates the sequence for normal application. 15,0,30,219,1,0,0,0,0,0,0,10,0,113,0,0,4,0,0,0,0,2,125,622,58,0,0,0,0,20,0,0,0,0,0,0,0, 35,101,0,0,0,0,0,0,0,0,0,0,36,0,0,0,0,0,432,0,10,0,0,0,0,0,0,0,0,33,0,0,0,513,0,0,0,0,0, 0,0,0,0,6002,160,1402,360,0,1,0,0,0,0,0,0,0,0,90,0,0,0,00,0,10,0,0,0,0,0,108,0,0,0,8,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,10,0,0,0,0,385,153,0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0 ,25,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,3…,normal

Fig. 4. 3-Patterns Frequency Representation

The memory complexity of l-patterns frequency of system calls representation is O(N*|Σ l |), where N is the number of sequences and |Σ l | number of possible patterns. For short patterns (l = 2 or 3) and |Σ| = 326, |Σ l | is not big number. This representation consumes memory little more than bag of system calls representation and much less than successive system calls representation.

Experiments and Results

In this section we examine and evaluate the influence of dataset representations on the performance of various machine learning classifiers. We measure the performance of the machine learning classifiers using two standard metrics: Accuracy rate and False Positive (FP) rate. Table 1 presents the confusion matrix. Confusion matrix holds information about actual and predicted classes generated by classifier. The performance of classifier is measured using the information in the matrix.  False positive (FP) is the quantity of misclassifying normal behaviours as malicious.

False Positive Rate (FP) =

 Accuracy rate is the rate of correct predictions over the whole dataset.

Accuracy Rate =

We experiment the different dataset representations on the following machine learning algorithms: Support Vector Machine (SVM), Naïve Bayes (NB), Logistic Regression (LR) and Decision Tree (DT). Those classifiers are obtained from the WEKA machine learning visual package [START_REF] Waikato | [END_REF].

The dataset represents a large set of system-call traces of benign and malicious applications. The normal applications are the top 100 popular free applications in the official Android applications store (Android market) [START_REF]Android Market[END_REF]. The 90 available Android real malwares are download from [START_REF] Mobile | [END_REF]. All applications are installed and executed on HTC Dream device running Android OS 2.2. The number of sequences in the dataset N = 190 (100 normal applications + 90 malwares). The length of sequences varies from applications to other. The shortest sequence has 10000 system calls and the longest sequence has 60000 system calls.

Support Vector Machine (SVM) classifier classifies data by determining a set of support vectors, which are members of the set of training inputs that outline a hyper plane in the feature space [START_REF] Mukkamala | Intrusion detection using neural networks and support vector machines[END_REF]. Table 2 represents the support vector machine classifier accuracy and false positive rates using different data representations. Patternfrequency representation of 2 system calls length and 3 system calls length outperforms with 100% accuracy rate and 0% false positive rate, whereas successive system calls representation has better performance than bag of system calls with 95.10% accuracy rate and 6.10% false positive rate. [START_REF] Smola | Introduction to Machine Learning2008[END_REF]. Table 3 shows the performance of naïve Bayes classifier using different system calls representations. The 3-pattern and 2-pattern frequency representation has the best performance (97.10% accuracy rate and 3.10% false positive rate). Bag of system calls representation has the worst performance (91.30% accuracy and 9% false positive rate). [START_REF] Smola | Introduction to Machine Learning2008[END_REF]. Table 4 illustrates the impact of dataset representation on the performance of logistic regression classifier. The 3-pattern frequency representation has the highest performance. It has the higher accuracy rate (100%) and the lower false positive rate (0%). The 2-pattern frequency representation still performs better than the two classical representations with 97.10% accuracy rate and 3.10% false positive rate. Bag of system calls representation has the worst performance (92.30% accuracy and 8% false positive rate). [START_REF] Ben Amor | Naive Bayes vs Decision Trees in Intrusion Detection Systems[END_REF]. Table 5 demonstrates decision tree classifier influenced by dataset representations. The classifier has better performance with pattern frequency system calls representation than other dataset representation. The 3pattern frequency representation has the best performance with accuracy rate 98.20% and false positive rate 2.10%. Successive system calls representation has the worst performance with accuracy rate 92.10% and false positive rate 9.40%. In summarizing of the above the results, the dataset representation has an important impact on the performance of machine learning classifiers. With the same dataset size and type, we have different accuracy rate and false positive rate for the same classifier. The classification process is based on two classification properties: system calls successive property and system calls frequency property. The SVM classifier has low performance with bag of system calls representation with 92.50% accuracy rate and 8.50% false positive rate which means SVM classifier is more sensitive to successive classification property than frequency classification property. Naïve Bayes classifier and Logistic Regression have the same behavior as SVM. Their performance on successive dataset representation is better than the performance on frequency dataset representation. However, Decision Tree classifier is more sensitive to frequency property than successive property; its performance with bag of system calls representation (96% accuracy and 4.10% false positive rate) is better than successive system calls representation (92.10% accuracy and 9.40% false positive rate). The pattern frequency representation has the better performance over all classifiers because this representation holds the both classification properties: frequency property and the successive property of short sequence. SVM classifier reaches its idle performance at two system calls pattern length. Three system calls pattern is the optimal length for Logistic Regression classifier. The LR classifier reaches its best performance with this length. Decision Tree and Naïve Bayes classifier may require longer patterns length to achieve their idle performance. Longer patterns have more successive and frequency information; therefore it is more discriminative in classification process. However, longer patterns require more memory and computation resources. SVM with 2-pattern frequency representation is the best combination of classifier and representation because this combination reaches the idle performance with lowest cost. Table 6 orders the combination (classifier-pattern frequency dataset representation) according to performance per cost. The worst performance of pattern frequency representations is 97.10% accuracy rate and 3.10% false positive rate. However, this performance is better than the best performance of other representations.

Conclusion

Dataset representation has a potential impact on the performance of machine learning classifiers. It increases the accuracy rate and decreases the false positive rate. The experiments results affirm the performances of classifiers are improved significantly with same data quantity and type, but with using a new dataset representation. The 3pattern frequency representation has the best performance over all experimented classifiers; it reaches the idle performance of SVM classifier and logistic regression classifier (100% accuracy rate and 0% false positive rate). The cost of improving the performance by using dataset representation factor is very low relative the other factors: normal behavior model, dataset size and dataset type. Because dataset representation keeps the same dataset type and size, the required memory space is few extra kilobytes. The process of preparing dataset representations is not computationally expensive. Bag of system calls representation has the lowest memory cost and the lowest performance. Successive system calls representation has the highest memory cost and not the highest performance. Short pattern system calls representation has a few extra memory cost than bag of system calls representation, but it improves the classifiers performance significantly. The frequency property of system calls in sequence is important in classification process and the successive property of system calls in sequence is also important in the process of classification. However, the pattern frequency property provides advantage by holding the two properties which leads to better classification process. A new factor improves the performance of machine learning classifiers with low computation and memory cost is an important step to implement lightweight machine learning algorithms on Smartphones device. We will study this approach in the future work.

FP

Table 1 .

 1 Confusion Matrix

			Predicted Class
			Normal	Malware
	Actual Class	Normal Malware	True Positive (TP) False Negative (FN)	False Positive (FP) True Negative (TN)
	In order to compare the performance of various machine learning classifiers, we
	employ two standard metrics: false positive rate and accuracy rate.

Table 2 .

 2 Support Vector Machine Classifier Performance Classifier is the simplest form of Bayesian network. It is based on Bayes theorem with heavy independence assumptions

		Accuracy rate	FP rate
	Dataset Representation
	Successive system calls	95.10%	6.10%
	Bag of system calls	92.50%	8.50%
	2-Pattern frequency	100%	0%
	3-Pattern frequency	100%	0%
	Naïve Bayes (NB)

Table 3 .

 3 Naïve Bayes Classifier Performance

		Accuracy rate	FP rate
	Dataset Representation
	Successive system calls	94.10%	6.30%
	Bag of system calls	91.30%	9%
	2-Pattern frequency	97.10%	3.10%
	3-Pattern frequency	97.10%	3.10%
	Logistic Regression (LR) Classifier is a discriminative model. It is based strongly
	on the logistic function

Table 4 .

 4 Logistic Regression Classifier Performance Classifier is built during training phase. The nodes represent attributes, the edges represent the possible attributes values, and leafs represent the classes. The classification start by root node and move down in decision tree relative to attributes values till reach leaf

		Accuracy rate	FP rate
	Dataset Representation
	Successive system calls	96%	4.10%
	Bag of system calls	92.30%	8%
	2-Pattern frequency	97.10%	3.10%
	3-Pattern frequency	100%	0%
	Decision Tree (DT)

Table 5 .

 5 Decision Tree Classifier Performance

		Accuracy rate	FP rate
	Dataset Representation
	Successive system calls	92.10%	9.40%
	Bag of system calls	96%	4.10%
	2-Pattern frequency	97.10%	3.10%
	3-Pattern frequency	98.20%	2.10%

Table 6 .

 6 Classifier-Dataset Representation Order per Performance

		Accuracy rate	FP rate
	Classifier-Dataset Representation
	SVM (2-Pattern frequency)	100%	0%
	SVM (3-Pattern frequency)	100%	0%
	LR (3-Pattern frequency)	100%	0%
	DT (3-Pattern frequency)	98.20%	2.10%
	LR(2-Pattern frequency)	97.10%	3.10%
	DT(2-Pattern frequency)	97.10%	3.10%
	BN (2-Pattern frequency)	97.10%	3.10%
	BN (3-Pattern frequency)	97.10%	3.10%


Christian D Jensen
email: christian.jensen@imm.dtu.dk

Kristine Geneser

Ida C Willemoes-Wissing

Sensor Enhanced Access Control: Extending Traditional Access Control Models with Context-Awareness

Access control models generally distinguish between physical access control that mediates access to physical resources such as buildings, sections of buildings or individual rooms, and logical access control that mediates access to logical objects such as information stored in files or databases. All logical access control models make some, more or less implicit, assumptions about the physical access control model, e.g. that servers are locked in a room with restricted access. However, problems arise when a logical object gets a physical representation, e.g. when a file is displayed on a screen or printed, because the logical access control model has no way to ensure, or even to monitor, that the physical access control policies are being enforced. Traditionally, physical access control policies are enforced by compartmentalization. Users are separated from other users and resources by placing them in different physical locations such as different offices in a building. Access from one to the other is impossible without passing a guard or a door lock, i.e., guards or distribution of keys/access-cards effectively enforce the physical access control policy. However, these mechanisms are generally coarse-grained, inflexible and expensive. In this paper, we propose a Sensor Enhanced Access Control (SEAC) model that extends existing logical access control models with context-awareness. This allows the model to incorporate information about the physical environment and to explicitly define and enforce physical access control policies for logical objects that have physical representations. A prototype implementation of the SEAC model has been developed for the Unix platform. The prototype protects file data when displayed on a computer screen by managing the visibility of windows in the X Window System. Context-awareness is provided by a simple motion detection system build using cheap web-cameras. However, the system is designed so that the sensor component easily can be replaced, making it possible to deploy advanced sensor technologies.

Introduction

Access control is traditionally restricted to logical access control where access only is granted to authorized users in authorized locations. The authorization of a user is usually determined after the user is identified and authenticated by the system, using for Kristine Geneser is the married name of Kristine Frank example a user name and corresponding password. After such a login procedure, a user ID will be associated with every process the user starts. The user ID will be used to determine which resources the process is permitted to access. This form of access control is logical since subjects and objects are logical representations of physical entities, such as processes running on behalf of users and information stored in a file system. After a user has logged in, an unauthorized person may also be able to obtain physical access to the resource. This could, for instance, occur if the user temporarily leaves his computer unattended. Another, more severe, scenario could be that an intruder uses a weapon to coerce the authorized user into providing access to the resource; the access would then be obtained despite the user's physical presence. In any case, a process that is started on the computer cannot determine who are currently present in the environment. It only knows the user ID of the person who currently is logged in. In a military or commercial setting, it can have severe implications if an unauthorized person obtains access to classified information by circumventing the logical access control.

In this paper, we propose a Sensor Enhanced Access Control (SEAC) model that not only takes logical entities into consideration when enforcing access control, but also the persons who are physically present in the environment and the physical representation of logical objects. The model consists of a logical and an environmental access control part. The logical access control part is a traditional access control model where e.g. processes and files are considered to be subjects and objects, respectively. The SEAC model does not impose any restrictions on the choice of the underlying access control model, and it can therefore accommodate any mandatory or discretionary access control model. The novel and important aspects of the SEAC model is not the choice of access control model, but the extension with environmental information. The environmental access control mediates access to the physical objects by persons. The physical objects are physical representations of logical objects, which are exported to an output device such as a display, a printer or loudspeakers. The identity of persons and other security relevant contextual information is captured by sensors and used in the access mediation.

The SEAC model is designed to counter the granularity gap between traditional logical and physical access control models: By extending logical access control models so that they also encompass objects when they are represented physically, a comparable level of granularity can be obtained. A system based on the SEAC model can be used to evade the paradox situation where fine-grained logical access control protects objects, but the physical representation of objects is only protected by coarse-grained access control such as a guard at the main entrance of a building.

The extension of a traditional access control models with context-aware computing [START_REF] Schilit | Context-aware computing applications[END_REF] has (to our knowledge) not been explored in the past. The current access control models for context-aware computing are mainly concerned with securing applications in a pervasive computing environment [START_REF] Michael | A Flexible Security Architecture for Pervasive Computing[END_REF][START_REF] Michael | Generalized role-based access control for securing future applications[END_REF][START_REF] Michael | Securing context-aware applications using environment roles[END_REF][START_REF] Al-Muhtadi | Cerberus: A context-aware security scheme for smart spaces[END_REF][START_REF] Hengartner | Access control to information in pervasive computing environments[END_REF][START_REF] Zhang | Context-aware dynamic access control for pervasive applications[END_REF]. None of these models address how access mediation in a traditional computer system can benefit from contextual information. On the other hand, models have been developed that protect information when it obtains physical form on an output device [1,[START_REF] Berger | Compartmented mode workstation: Prototype highlights[END_REF]. These models are, however, not context-aware and are merely concerned with labelling the output on peripheral devices, e.g. a display or paper, with its security classification. Furthermore, these models are mainly used by the military, and strong physical access control to the premise of the computers is therefore also deployed. In organizations with lower security requirements (and budgets), it may not be feasible to deploy fine-grained physical access control to the premise of the computers. These organizations may find an access control solution based on context-awareness useful. For example, an open-plan office in a company with many employees and visitors can use it to enforce that windows become invisible when unauthorized persons are present in front of the display.

To demonstrate the validity of the SEAC model, a prototype system based on the model has been developed. The system is designed so that it can be integrated with an existing Unix system. The logical access control is enforced by a file system that, in addition to storing files, acts as a reference monitor when it mediates access to files by processes. The environmental access control is implemented using services provided by the X Window System and two web-cameras that are used as simplified sensors. The rules that are used when mediating access to objects by subjects are based on the Bell-LaPadula confidentiality model. The environmental access control will enforce a no-view up rule, that is, persons can only read data in windows at their own level or a lower level. If a person who is not authorized to see the information displayed in a window, this window will disappear from the display so that the content is no longer is human-readable.

The reminder of this paper is organized as follows: The granularity gap between traditional logical and physical access control models are discussed in Section 2. The SEAC model is presented in Section 3. The design and implementation of our prototype is presented in Section 4. The evaluation of the prototype is discussed in Section 5, and related work is reviewed in Section 6. Finally, our conclusions and guidelines for future work are presented in Section 7.

The Granularity Gap

The protection of logical objects within computers has been widely explored during the past decades, resulting in a wide range of access control models that meet different security requirements. In contrast to the availability of logical access control models, relatively few access control mechanisms are available to regulate access to the premise of the computers. The oldest physical access control mechanism is to post guards who control access to a room or equipment. The disadvantages with guards are that they must be on duty continuously, are expensive, and must personally recognize the authorized persons or an access token such as a badge. The second oldest physical access control mechanism is to use a lock. This mechanism is cheaper and simpler than using a guard. The main issues with the use of keys and other access tokens are that they can be lost or forged. Furthermore, the revocation or modification of access rights can be troublesome with access tokens.

When considering the granularity aspects of physical access control mechanisms, the use of locks is relatively coarse-grained. Guards enforce more fine-grained policies, but they have to be paid, so this mechanism can be quite expensive. Furthermore, if a fine-grained solution is required, it will typically cause more inconvenience for the authorized users who frequently have to present their credentials.

A coarse-grained mechanism may be sufficient if the physical access control is only required to prohibit unauthorized outsiders from obtaining access to the premise of the computers. Many companies do, however, require that the access of insiders also is controlled. For instance, it may be a requirement that only top-executives have permission to the computer room where confidential corporate information is processed. A finegrained access control solution can be obtained by using devices that interface with a computer. Such devices can be smart cards, biometric mechanisms, RFID tags, etc.

The granularity gap between the protection provided by traditional physical and logical access control models can result in some paradox security situations. For example, in a corporate setting where strict logical access control is enforced, the physical representation of objects may be accessible to all within the building. The only physical access control may be a guard at the main entrance, and everyone inside the building will consequently have access to all physical objects, e.g. an object rendered on a computer display will typically be unprotected while the owner is out for a cup of coffee. It is a paradoxical situation that much effort is put into the protection of logical objects, whereas physical objects only are protected by old-fashioned means such as guards and locks.

Sensor Enhanced Access Control

The limitations of traditional physical access control mechanisms can be addressed by using advancements in context-aware computing. In particular, the use of sensors to detect persons in an environment can make other physical access control mechanisms superfluous. Furthermore, the use of sensors can provide a very fine-grained and flexible solution. The Sensor Enhanced Access Control (SEAC) model is an extended access control model which in addition to logical entities also encompasses physical entities. The SEAC model consists of a logical access control part that is extended with an environmental access control part. Figure 1 illustrates the logical and physical entities in the SEAC model and their relationships. The logical access control part is a traditional access control model such as the Bell-LaPadula [START_REF] Lapadula | Secure computer systems: A mathematical model[END_REF], RBAC [START_REF] Ferraiolo | Role-based access controls[END_REF][START_REF] Sandhu | Role-based access control models[END_REF], or Chinese Wall [START_REF] Brewer | The chinese wall security policy[END_REF] model. The important part in the SEAC model is not the choice of logical access control model, but the extension with context-awareness via the environmental access control part.

The environmental access control is concerned with mediating access to physical objects by persons. A physical object is a physical representation of a logical object. More precisely, a physical object is presented to persons using an output device that makes it perceivable to one of the human senses. Most computers present output in a viewable format where the output device is a computer display or a printer and the corresponding physical objects are a window on the display or a printed paper, respectively. Loudspeakers is an example of an output device that generates a physical object which is perceived by the hearing sense and in this case the physical object is the pressure waves that constitutes sound. An example where it is useful to control access to sound is if the loudspeakers play a recording of a confidential meeting or medical information recorded by a doctor. A person is defined as any human principal, and the access operation is the human sense used to perceive the physical object. The environment is defined as the physical location from where a person can perceive the physical object. If the output device is a display or a printer, the environment is the area in front of the display or the printer room, respectively. The environment where sound can be perceived is relatively large, but headphones or loudspeakers that produce directional sound can be used to limit the size of the environment.

The representation manager enforces the environmental access control: The persons in the environment are only granted access to a physical object if this is permitted by the representation manager. For example, if the information in a window or on a piece of paper must not be seen by the persons, the representation manager can deny access by removing the window or cancelling the printing job. Since the representation manager mediates access to physical objects by physical subjects (that is, persons), it acts as a reference monitor for the environmental access control. When a person requests access to an object, a user-initiated subject must therefore first request the reference monitor for access to the object and, secondly, it must request the representation manager for access to represent the object as a physical object.

The security policy enforced by the representation manager will (usually) resemble that of the logical access control model, ensuring that the same level of granularity is enforced both logically and physically. This policy is defined in terms of properties related to physical objects and contextual information such as time and identities of persons in the environment. For example, a policy can state that certain persons can only access a physical object during working hours.

All contextual information is captured by sensors. In general, sensors can capture a variety of information such as noise, temperature, or motion. When mediating access to physical objects, the most relevant information is the identity and location of persons. Depending on the capabilities of the sensors, they may capture fine-grained biometric information such as facial features, or they may be very basic and only detect whether someone is present or not. Another possibility is to let the sensors read an identity from a badge; however, this solution is not secure because a person can gain another persons identity by simply wearing his badge.

The context manager aggregates information from all the deployed sensors. Whenever the context manager has detected a security relevant event, the representation manager is notified about this event, ensuring that the environmental access control is mediated dynamically. A person who is detected by sensors, but cannot be identified, must be associated with a default clearance, which reflects the underlying physical access control mode. For example, if only persons cleared to "secret" can enter a particular part of a building, it is safe to assume that the clearance of the unidentified person is at least "secret". For persons who can be identified, the captured identity must be verified using an authentication service.

The SEAC model is mainly concerned with providing confidentiality as it enforces access control to output devices and prevents that unauthorized persons can perceive classified information. The model does not encompass other security requirements such as integrity and availability. It is, however, not difficult to develop a dual SEAC model which provides integrity: Whenever a physical object is presented on an input device, the dual SEAC model must prevent that unwanted physical objects are represented internally as a logical object. This duality is reminiscent of the duality between the Bell LaPadula confidentially model and Biba integrity model.

The SEAC Prototype

To demonstrate the feasibility of the SEAC model, we have developed a simple prototype system [START_REF] Frank | Combining logical and physical access control for smart environments[END_REF], which is integrated with an existing Unix system.

Adapting the SEAC Model to Unix

An overview of our adaption of the SEAC model can be seen in Figure 2. The separation of user and kernel space found in a Unix system has been included in the figure since it is important from a security perspective.

Logical Access Control

The logical access control model that we have chosen to use in our system is a simplified version of the Bell-LaPadula model [START_REF] Lapadula | Secure computer systems: A mathematical model[END_REF]. The reference monitor enforces the no read up and no write down rules a.k.a. the simple-security property and *-property in the Bell-LaPadula model. In a Unix system where information flow must be prevented, the only system calls that are subject to access control restrictions are read and write.

In our adaption of the Bell-LaPadula model, only process and files are considered to be subjects and objects, respectively. A file is a passive entity that stores information on a computer and is uniquely identified by an inode number. There exists many types of files, such as regular files, directories, or symbolic links. A file level is associated with each inode number, and it is used by the reference monitor when access to a file with a given inode number is mediated. File levels correspond to classification labels in the the Bell LaPadula model.

A user is an active entity that can access files. Each user has an account, and a user must identify herself and be authenticated as part of a login procedure before she can access the system. When a file is accessed by a user, it is actually not the user who directly accesses the file, but a process that runs on behalf of the user. The logical subject is therefore a user-started process. A user is uniquely identified by a user ID, and this user ID is associated with all processes that are started by the user. A user level will be associated with each user ID, and it constitutes the basis for deciding what files a given user has access to. User levels correspond to clearance labels in the the Bell LaPadula model.

Environmental Access Control Without loss of generality, we only consider windows on displays as the physical objects in the environmental access control. In a Unix system, windows are typically managed by the X Window System, which we rely on in our prototype. The X Window System is based on a client-server architecture where the X server offers graphics display services to the X clients. An X client is an application, such as a text editor or an Internet browser, that sends drawing requests to the X server. It is the responsibility of the X server to render the appropriate bits on the user's display.

A window is as an area of the display that is used to represent a computation graphically. In Figure 2, a window has been drawn in user space since it is represented internally by a data structure which is manipulated by the X server. A window will, however, be visible in the environment when the X server sends drawing requests to the computer's graphics card. Each window on a display must be uniquely identified by a window ID. Most GUI applications will create one top-level window and possibly some sub-windows inside this special window. A sub-window can, for instance, be a button, a menu, or a scrollbar. The SEAC system only uses the first top-level window created by an application and ignores any further created top-level windows as well as all the sub-windows of top-level windows. This ensures that an application can be uniquely identified by a window ID.

The access operation for a window is viewing. If access to viewing a window is denied, the window will be unmapped so that it no longer is visible on a computer display. Otherwise, if access to a window is granted and it currently is unmapped, the window will be mapped.

Like the logical access control, the environmental access control is based on a multilevel security model. A window level is associated with each top-level window, and its value is determined using a rule based on the high-water mark principle [START_REF] Landwehr | Formal models for computer security[END_REF]: If two files are opened by a GUI application, the window level of the application becomes the higher of the two file levels. Consequently, the level of a window can only increase.

The term environment level will denote the level of a person as it is detected by a sensor. If a person cannot be identified, i.e., no environment level can be associated with a human principal known to be present, a default level is associated with that person. The clearance level models a combined level for all the persons in a given environment and the user. It is equal to the minimum of all the detected environment levels and the user level.

The representation manager is denoted the visibility manager and it uses the clearance level and the window levels to enforces a no view up rule: if a window level is greater than the clearance level, the window is unmapped. The clearance level is also used by the reference monitor as our adaption of the Bell LaPadula model compares the clearance level, and not the user level, with a file level when access to a file is mediated.

Design and Implementation

The system we have developed encompasses many different types of functionality, ranging from storing file and user levels to detecting when persons enter or leave a given environment. The system implements a layered architecture, where the lowest layer is a file system which, in addition to storing files, enforces logical access control. The middle layer enforces the environmental access control, i.e., it is responsible for changing the visibility of windows on a display. The services provided by this Visibility Management layer are used by sensors in the Sensors layer whenever persons are detected in the environment. The layered architecture is closed in the sense that each layer only uses the services provided by the layer immediately below it. If only logical access control is required, the MAC file system can be used independently of the higher layers. In the remainder of this section, the implementation of these three layers will be described.

To support information classification of stored data in the Unix system, we had to implement a special file system that associates a file level with every file stored in the file system. The development of a new file system is, however, a difficult and tedious process. In order to focus on the access control aspects of the file system, we decided to use a stackable file system. A stackable file system [START_REF] David | Evolving the vnode interface[END_REF] is a layer that resides above a native file system and below the Virtual File System (VFS). This is illustrated in Figure 3. Because existing file systems and interfaces are used, it is much easier to develop a stackable file system than a traditional file system.

File system data and error codes

File system data and error codes

Stackable file system

Virtual File System

Native file system

Process

Error codes System calls

User space

Kernel space

Fig. 3. A stackable file system can be used as a reference monitor if it mediates access to files in a native file system by processes.

The stackable file system used in our system is denoted macfs (mandatory access control file system), and it is developed using the FiST (File System Translator) system [START_REF] Zadok | FiST: A System for Stackable File System Code Generation[END_REF][START_REF] Zadok | Fist: A language for stackable file systems[END_REF]. FiST enables programmers to write stackable file systems for several versions of Linux, Solaris, and FreeBSD. The performance overhead when using FiST generated stackable file system is only 1-2% [START_REF] Zadok | Fist: A language for stackable file systems[END_REF].

The main objective of the macfs is to enforce the logical access control part of the SEAC model. For this purpose, macfs stores a file level associated with each file in the underlying native file system and a user level corresponding to each user who has access to the system. Using these file and user levels, macfs implements a reference monitor that mediates access to files by user processes.

A FiST generated stackable file system is a kernel module. When compared to static kernel code, a kernel module has the advantage that it can be loaded and unloaded from memory separately from the main body of the kernel. It is therefore not necessary to rebuild and reboot the kernel every time a new module is to be added.

It is very important from a security perspective that the stackable file system is part of the kernel as it then is protected from non-privileged users via the operating system user/kernel modes. Furthermore, including access control mechanism in the kernel gives better performance because fewer context switches have to be made.

Visibility Management

The X server and X clients run in the user space part of a Unix system. Consequently, the part of our system that manages the visibility of windows must also reside in user space so that services provided by the X server can be used. We have developed an X client, denoted visibility manager, that sends requests to the X server whenever a window must be mapped or unmapped.

Our prototype works with both text editors and pure file readers such as Internet browsers. These GUI applications use library functions provided by the X Window System when making drawing requests. We have developed a preloaded shared library which overloads the function that creates a new window. Whenever an application requests the creation of a top-level window, our library will ensure that a message is sent to the visibility manager process before the real function is invoked. The message contains the process ID of the application and the window ID of the top-level window. Message 1 in Figure 4 illustrates this message exchange. The visibility manager process maintains a table with information about all created top-level windows and the corresponding applications that have created them.

The level of a window is equal to the maximum file level which is associated with a file opened by the application. Because the visibility manager mediates access to windows, it must be informed about all the files that an application opens. This part is implemented using an auxiliary process, file open monitor, which blocks on a semaphore in macfs. Whenever a file is opened in macfs, the semaphore is signalled and the file open monitor process unblocks and sends a message to the visibility manager. This message contains the process ID of the application, the inode number and the file level associated with the newly opened file (see Message 2 in Figure 4).

Besides information about the window levels, the visibility manager must also know the levels of all the persons who are present in the environment so that the clearance level can be updated accordingly. Therefore, a second auxiliary process, sensor server, is included in the system. This process aggregates data from all the deployed sensors and it will thus function as a simple context manager. The aggregated data includes the environment level of a detected person and the movement direction of the person. The term direction denotes the movement direction of the person. It is a binary value which models that the person either enters or leaves the environment. Fig. 4. The visibility manager process is a representation manager. It receives information about created windows, opened files, and detected persons and uses these data when it requests the X server to map or unmap windows.

The three processes visibility manager, file open monitor, and sensor server must be started by the super user and subsequently run as demon processes. It is very important from a security perspective that they are started by the super user since they then will be protected by the Unix security mechanisms. In particular, a nonprivileged user must not be allowed to kill them by sending them a signal, regardless of whether this is done deliberately or not.

Sensors As several sensors may be used simultaneously, we have chosen to implement the sensor part of the system using the client/server paradigm. The sensor server receives data from all the deployed sensors, which are denoted sensor client, and relays the data to the visibility manager (see Message 3 and 4 in Figure 4). The window levels and the clearance level are used when the visibility manager sends requests to the X server about which windows should be mapped or unmapped (see Message 5).

The sensor client used in our prototype system is based on two web-cameras and a motion detection program. The web-cameras are only used to determine whether someone enters or leaves the environment and a common level is therefore assigned to all the detected persons. This common level depends on the physical access control that is enforced in the monitored location. A more fine grained physical access control policy can be enforced if it is possible to associate a specific user ID to the person entering the area, e.g. through the use of persistent authentication [START_REF] Christian | Persistent authentication in smart environments[END_REF][START_REF] Kirschmeyer | Persistent authentication in smart environments[END_REF], but this is not implemented in the current prototype.

Evaluation

The main security requirement that the SEAC system has been designed to meet is access control. In this section, we will describe how well the prototype meets this requirement by evaluating the mediation of access to windows by persons. Since a system only is as strong as its weakest link, we will also evaluate other security properties of the SEAC system.

Access Mediation to Windows by Persons

The environmental access control in the SEAC system must enforce that GUI applications are mapped and unmapped in accordance with the authorizations of the persons who enter or leave the environment. The system has been designed to work with GUI applications that only create one top-level window since this avoids ambiguity about which windows should be mapped or unmapped. However, not all applications work this way, and the Inter-Client Communication Conventions Manual [START_REF] Rosenthal | Inter-Client Communication Conventions Manual[END_REF] used in the X Window System does not specify that all applications should use the same window hierarchy. The prototype can therefore not be guaranteed to work with all applications, and users should be restricted to using applications that successfully can be unmapped.

The Unix version used the GNOME desktop environment with the metacity window manger. The test showed that typical applications, such as the emacs, nedit, and mozilla, fully integrate with our system, i.e. windows were mapped or unmapped according to the no-view up rule. The system could, however, not unmap the gedit editor because the communication between gedit and the window manager metacity was very unpredictable. We think that the main reason for this unpredictable behaviour is that gedit is tightly integrated with GNOME and therefore may use a custom protocol when it communicates with metacity. After all, this unspecified behaviour is permitted since the X Window System provides mechanism, not policy.

Security Analysis

The security provided by the logical access control part of the prototype depends on the used Unix system and the security it provides. In particular, the macfs file system is only a kernel module that interacts with other parts of the Unix system. Security procedures such as user identification and authentication are therefore beyond the boundaries of our system, and we must just assume that they are secure.

The environmental access control in the SEAC model is mainly concerned with access control to output devices such as displays and printers, but when constructing a secure system one should also remember to secure input devices and all communication channels. In particular, the communication between the sensors and the visibility manager must be secured so that traditional security requirements such as confidentiality, integrity, and availability are met.

In general, when deploying a security mechanism in an environment with high security requirements, one should notice that these requirements cannot be met with a mainstream operating system [START_REF] Loscocco | The inevitability of failure: The flawed assumption of security in modern computing environments[END_REF]. Our system is no exception since it is based on a regular Unix version. For example, the X Window System is not designed with security in mind and it does not meet any of the basic security goals confidentiality, integrity and availability [START_REF] Vance | Securing the x window system with selinux[END_REF]. The visibility management part of our system is actually exploiting the lack of availability: the X client visibility manager unmaps the windows of other X clients, and no permission checks are made before this occurs.

Even if all software and hardware parts of the system are assumed to be secure, the security provided by the system can be breached if the super user (a.k.a. root in Unix) cannot be trusted. The actions of the super user are not restricted by any access control, and he can therefore easily circumvent all access control mechanisms that protect logical objects. The environmental access control can also be evaded by the super user, for instance by killing the visibility manager process. This vulnerability implies that the person who is able to log in as the super user should use some form of physical access control, such as locking the door, before using the system. Otherwise, an unauthorized person might enter the environment and coerce the person into misusing the super user privileges, bypassing all logical access control mechanisms provided by the system.

Related Work

The use of environment information in access control mediation has previously been explored by Covington et al. [START_REF] Michael | Generalized role-based access control for securing future applications[END_REF][START_REF] Michael | A Flexible Security Architecture for Pervasive Computing[END_REF] and Bertino et al. [START_REF] Bertino | Geo-rbac: a spatially aware rbac[END_REF]. Covington et al. propose GRBAC, which is an extended RBAC model that, in addition to the traditional subject roles, includes object roles and environment roles. Object roles capture properties of resources in the system, and environment roles capture context information. All types of roles can be used to define fine-grained and flexible security policies. Bertino et al. propose GEO-RBAC, where spatial entities are used to model objects, user positions, and geographically bounded roles. Roles are activated based on the physical or virtual position of the user. An important difference between SEAC and both GRBAC and GEO-RBAC is that SEAC also includes persons who cannot be identified. If a person is detected, but cannot be identified in the SEAC model, the default clearance is associated with the person. This will prevent that unidentified persons obtain access to a physical object, for which they are not authorized.

Context-aware security mechanisms have been explored by Aziz and Jensen [START_REF] Aziz | Adaptability in corba: The mobile proxy approach[END_REF], who describe a mechanism that adapts the security properties of client-server communication in CORBA based on context information at runtime. The mechanism uses a context server to enforce multiple security policies defined for the current context, e.g., to encrypt all communications when a mobile client is away from the home network. While this work explores ideas that are similar to the ideas presented in this paper, their work focuses on communications security, but access control is not addressed. Moreover, their system is based on simple software based sensors, e.g., to determine whether the client is at home by comparing the current IP address identical to the home IP address and it does not explicitly address the use of external sensors.

Conclusion

Traditional access control models protect logical objects within a computer; however, these models are inadequate when the objects are represented as physical objects to persons, e.g. in the form of windows on a computer screen or printed papers. To protect physical objects, physical access control is therefore typically deployed in the form of guards or locks. This access control mechanism is typically coarse-grained, expensive, and inflexible.

To counter the limitations of traditional access control models, we present a novel access control mechanism: any traditional logical access control model can be extended to encompass physical representations of logical objects. Corresponding to the reference monitor used in logical access control models, we propose a representation manager that mediates access to physical objects by persons. The representation manager is context-aware and uses information about the authorizations of the persons in the environment when it mediates access. The presented model is denoted the Sensor Enhanced Access Control (SEAC) model because it relies on sensors to capture environmental information. A system based on the SEAC model can be used as a replacement or enforcement of traditional physical access control mechanisms. In a context-aware environment where sensors are deployed, such a system can provide a fine-grained and flexible access control mechanism.

A prototype system based on the SEAC model has been developed for the Unix platform. It consists of three main parts: Firstly, a stackable file system acts as a reference monitor when it mediates access by processes to files. Secondly, services provided by the X Window System are used to ensure that the visibility of windows change according to the common authorization of the persons in the environment. Finally, a simple movement sensor based on two web-cameras are used to detect persons in the environment.

Future Work

The development of the prototype demonstrates the applicability of the SEAC model. In particular, it demonstrates that access control to physical objects in the form of windows can be enforced successfully. Future work on our prototype can include enforcement of access control to printers and other output devices. This can, for instance, be implemented by utilizing that many types of resources are accessed via special files in a Unix system. In particular, the /dev directory will (usually) contain files for accessing printers, hard disks, modems, terminals on remote computers, etc. Access control to a printer can be enforced by restricting write access to the printer special file, which typically is the file /dev/lp0. FiST-generated stackable file systems can (at the time of writing) not be stacked on top of directories containing special files, so this type of access control is not supported by our prototype.

The sensor client implemented in the current prototype does not associate a unique user ID with the different people moving around in the area. We plan to address this limitation by integrating the SEAC prototype with a fine grained remote authentication mechanism, such as persistent authentication [START_REF] Christian | Persistent authentication in smart environments[END_REF], possibly enhanced with remote biometrics [START_REF]Handbook of Remote Biometrics[END_REF] to improve robustness.

As with most other security mechanisms, the SEAC model can also result in some inconvenience for the users: if a user e.g. sits in an open-plan office where unauthorized persons frequently pass the computer, the user will (eventually) be very annoyed because the windows disappear all the time. The windows will, of course, reappear on the screen again once the persons are gone, but it will nevertheless be irritating. An area of future work within usability and HCI is the provision of availability of physical objects for authorized persons.

Developments in sensor technologies for pervasive computing environments will provide a basis for interesting work in the near future. These sensors will be able to capture detailed contextual information, which can be used in a fine-grained and flexible access control model where all physical representations of logical objects are protected. We therefore plan to explore the integration of our work on persistent authentication with the SEAC model presented in this paper.

Fig. 1 .

 1 Fig. 1. The Sensor Enhanced Access Control model.

Fig. 2 .

 2 Fig. 2. Our adaption of the SEAC model to the Unix platform.


Jiwan Seo
email: 1jwseo@ec.cse.cau.ac.kr

Seungjin Choi

Sangyong Han

The method of Trust and Reputation systems based on Link prediction and Clustering

Keywords: Trust and Reputation Systems, Link Prediction, Clustering

Online environments offer a major advantage that data can be accessed freely. At the same time however, they present us with an issue of trust: how much any data from online sites can be trusted. Trust and Reputation Systems (TRS), developed to address this issue of trust on network, quantify reliability in terms of semantics and derive a trustnetwork from a targeted online data. The performance of TRS is often hindered despite the promises because the number of links formed in the ideal scenario frequently is not reached, suffering from the problems of cold-start and sparsity. In this paper, we propose a method in which Link Prediction(LP) and Clustering are applied to TRS so that these two problems are adequately addressed. We evaluate our proposed method with a recommendation system we constructed. Our experiment results show that our method positively contributes to the performance of a recommendation system and help control the problems of cold-start and sparsity in TRS.

Introduction

Spread of the Internet in recent years has made it possible for the general public to search and access data easily. At the same time, a problem has risen whether users could trust such data unlike as in off-line situations [START_REF] Seo | The method based on professionalism of evaluator for reliability reputation model[END_REF]. Therefore in most cases, users end up relying on the information provided either by commercial sources with vested interest or any arbitrary third parties. Such inputs can be biased or inaccurate, causing users to make unintelligent decisions [START_REF] Josang | A survey of trust and reputation systems for online service provision[END_REF][START_REF] Yang | Defending Online Reputation Systems against Collaborative Unfair Raters through Signal Modeling and Trust[END_REF]. Trust and Reputation Systems (TRS) effectively address these two problems. Being based on the Word-of-Mouth (WoM) algorithm, TRS form a virtual network using links people with direct experiences on a given topic. From this virtual network, TRS can extract useful data for various application programs. However, two major problems hinder the performance of TRS when a real-world data set is applied [START_REF] Kim | Identity management-based social trust model for mediating information sharing and privacy enhancement[END_REF]. One is, constructing functioning trust-networks for new users is hard because there is insufficient amount of data related to them.The term the cold-start problem refers to this. The other problem refers to a case when links between nodes are not formed even though they are expected to in theory. This is called the sparsity problem. Both of these problems deteriorate the performance of a system based on a trust-network.

There are two algorithms that can address these two problems: the Link Prediction and Clustering algorithms. The LP algorithm analyzes the structural characteristics such as betweenness, degree, and density of the nodes in a network and determines the strength of the feasibility between any two unconnected nodes [START_REF] Getoor | Link mining: a Survey[END_REF][START_REF] Butts | Network inference, error, and information (in)accuracy: a Bayesian approach[END_REF]. Then links with good chances of forming in the future are identified. As the number of feasible links increases through the LP algorithm, sparsity problem is directly controlled. The Clustering algorithm, on the other hand, addresses the sparsity and cold-start problems differently by utilizing the concept of group of nodes. The Clustering algorithm identifies clusters in a network, assigning each node a membership to a cluster or clusters. It is assumed that a node can trust the other nodes within its cluster with more confidence even without direct links established between them, and this distinction helps control the sparsity and cold-start problems. In this paper, we suggest an improved trust-network to which the LP and Clustering algorithms are applied and use this in an application program to evaluate our method. For experiment, we derived a trust-network from a real-world data set of a film-rating website. This data was quantified from various semantic points and the LP algorithm was applied with the structural perspective to improve the trust-network. Then the Clustering algorithm was applied as well, resulting in significant clusters. With the resultant trust-network, we constructed a movie recommendation system, with which we evaluated our method.

The remaining parts of this paper are organized as follows: In Section 2, we discuss works related to TRS, the LP algorithm, the Clustering algorithm. Section 3 details our proposed method. Section 4 shows a comparison of performances between the conventional method and ours. Further explorations are suggested in Section 5.

Related work

Trust and Reputation Systems

In an online environment, user access data from other users. In this case, it is hard to tell whether the sources of the data have any vested interest in the topic in which users are interested. In the end, they have to resort to relying on the data from dubious sources. Users might end up making purchases online without knowing about the goods and services directly. Taking actions without prior direct experience on a given topic is referred to as the risk of performance [START_REF] Josang | A survey of trust and reputation systems for online service provision[END_REF]. This risk can be addressed with TRS, which are based on the WoM algorithm. The WoM algorithm extracts opinions and data from a virtual network of people with direct experiences on a given topic so as to suggest valuable information for decision making processes. Based on direct experiences of other users, both trust and reputation systems in common estimate credibility. But, the trust system utilizes trust value, which is derived from each user, and the reputation system uses reputation value, a reliability factor to can derive from groups. On the other hand, the performance of programs based on TRS was decreased by some problems, which were called the cold-start and sparsity problems. So, recently many researches proposed the method based on extending the trust and reputation network for controlling these problems [START_REF] Chen | An effective recommendation method for cold start new users using trust and distrust networks[END_REF][START_REF] Pitsilis | Social Trust as a solution to address sparsity-inherent problems of Recommender systems[END_REF].

The Link Prediction and Clustering Algorithm

The LP algorithm [START_REF] Getoor | Link mining: a Survey[END_REF] evaluates the relation between any of the two unconnected nodes within a network based on the structural characteristics of the pair in relation to the network. With this evaluation, this algorithm then produces a set of links that are likely to form in due course. Many variants of the LP algorithm have been developed in recent years. One of them, the Common Neighbor algorithm, computes the possibility of a link formation between any two unconnected nodes by assigning scores. This is done by comparing the neighbor group of an arbitrary node x and the neighbor group of another arbitrary node y. Another variant, the Adamic-Adar Index algorithm, extends the Common Neighbor algorithm with the additional step of discounting the scores of higher-degree nodes found among the common neighbor nodes.

The Clustering algorithm [START_REF] Xu | Survey of clustering algorithms[END_REF] exploits the characteristics of the definition of a community within a network. A community, which is a group of nodes by definition, has higher density of links inside itself. By identifying a community that a user belongs to, application programs may consider only a restricted range of nodes rather than all of the nodes within the network because noisy links can be ignored, hence more useful results can be obtained. There are a handful variants of Clustering algorithms with different methods of constructing a cluster. A cluster consists of a head node and member nodes which surround the head. The various kinds of Clustering algorithm essentially differ in selection of head nodes and their surrounding member nodes.

3 Proposed method

Establishing the Trust-network

A trust-network can be constructed by quantifying trust, the numbers of which are calculated with statistical and probabilistic analyses. A link might be suggested between users A and B after these analyses. Higher frequency of interactions between two nodes signifies a stronger feasibility of a link between them. We built a trust-network for a recommendation system in our experiment using data obtained from a movie ratings site. For this, we chose the users' profiles and movie ratings that ranged between 1 and 5.

We assumed that the tastes of two users were similar when both of them gave the same ratings to a movie. The number of matches in their ratings were normalized to yield a matrix that contained a value within the range of 0 and 1. When this was rounded with a threshold that we manipulated, a weighted undirected sparse trust-network was obtained. User profile was one major component for building our trust-network. Our user-profile-based trust-network took the gender, age, profession and area of residence of each user as input. Our assumption was that each of these properties had an influence on users movie preferences. We defined and assigned weight to each property based on the following equation. Affinity is an attempt to gauge how much each of the properties influences a users taste for movies. The following equation was used to calculate affinity:

Af f inity = N umberof Link occurrence N umberof Link possible (1)
Numeric values of profile-based user affinity were normalized by dividing each affinity value with the total sum of the profile affinity values. Common attributes of profiles from a pair of users were translated to numeric affinity values between the pair, and the values were added up to be assigned as the strength of links. Going through this step for every pair of users yielded a user-profile-based trustnetwork.

Link Prediction for Enhancing Trust-network

We chose the Common Neighbor algorithm among the many LP algorithms available because of its simplicity in implementation and effectiveness in finding significant results. The Common Neighbor algorithm takes the number of common neighbor nodes that a given nodes of x and y have in order to calculate the score of each edge. A higher score between two nodes signifies that both of the nodes are likely to form a new link judged from the weights of their neighboring links. Whereas it is an unweighted undirected network that the Common Neighbor algorithm takes when considering the number of common neighbors, our method used a weighted undirected trust-network. This makes it necessary for our method to use the following equation to calculate the score of each predicted links in order to reflect the weight of each neighbor node [START_REF] Murata | Link Prediction of Social Network based on weighted proximity measures[END_REF]:

score(x, y) = a∈Γ (x)∩Γ (y) w(x, a) + w(y, a) 2 (2)

Grouping with the Clustering Algorithm

Using the Clustering algorithm allowed us to identify a cluster or clusters that an arbitrarily chosen user belongs to. clusters were identified from either the structural or the semantic viewpoint of the network. This guaranteed improved services for users as well as program scalability. We used the K-means Clustering algorithm because of its ease of implementation [START_REF] Ja Hartigan | Algorithm AS 136: A k-means clustering algorithm[END_REF]. In this algorithm, K seeds are selected, each of which is the header for each cluster; then members are added to clusters based on their relation with the seeds. Once all of the nodes in the network have obtained membership to any one of the clusters, the first step was finished and evaluation on this clustering began. If the evaluation result turns out to be unsatisfactory, another new set of headers are selected and clustering is repeated. In constructing our movie recommendation system, we decided that K users with higher degrees were the influential users in the trust-network, and chose them as seeds for the Clustering algorithm.

Collaborative Filtering for Recommendation System

We enhanced the trust-network and selected significant groups following the aforementioned steps. After enhancement, we constructed a recommendation system based on this trust-network and the widely used Collabrative Filtering(CF) algorithm was used for this. This algorithm, based on the K-nn algorithm, estimates weights by considering similarities between users, from which recommendations are made. How distance is defined and calculated yields different results, but the trust-network itself can provide the distance data for the purpose of our experiment. Therefore, the CF algorithm can be implemented using our trust-network and Euclidean Distance. In addition, the group selected via the Clustering algorithm becomes the target to apply the CF algorithm.

Experiment

Experiment Method

To test our proposed method, we used the actual data set from the website MovieLens, a movie ratings site. We considered movie ratings data made by 1,000 arbitrarily chosen users, and picked a timestamp that divided the ratings data chronologically: this timestamp was set to a point when 80% of the ratings were done. The data before this time dividing timestamp were used as training data and the rest for evaluation. To evaluate our method, we built three different trust-networks -the first one was based on user tastes, the second on user profiles, and the third integrated the first and the second. The additional test cases were where only the LP algorithm was applied and where the Clustering algorithm was applied. We used Mean Absolute Error (MAE) and Root Mean Square Error (RMSE) indices, which are widely used for the purpose of evaluating the performance of recommendation systems. MAE index signifies average of differences between actual values and estimated values. RMSE is the standard deviation of the differences between actual values and estimated values. While both of them evaluates the recommendation performance of a recommendation system, RMSE especially, can measure the stability of performance of a recommendation system. By using these two indices as measuring tools, we demonstrate that the problems of cold start and sparsity can be controlled by comparing the number of links before and after our method was applied. The Table 1 shows the result of our experiment.

Tn

LP-Tn LPCl-Tn taste profile hybrid taste profile hybrid taste profile hybrid MAE 0.765 0.739 0.765 0.701 0.797 0.701 0.641 0.775 0.641 RMSE 1.013 0.927 1.012 0.897 1.004 0.897 0.822 0.972 0.823

Experiment Analysis

There are nine columns for data in the table as three different trust-networks were implemented, each of which was tested with or without the LP and the Clustering algorithms applied. As the rating scores range between 1 and 5, the values of RMSE and MAE are less than 4; the closer the value approaches 0, the more similar the predicted value is to the actual values. Tn(taste), which was the trust-network of taste, performed worse than the profile-only trust-network. Because you can see in the table 2, the taste-based trust network consists of a sparse matrix than the profile-based. It is hard to derive the rating for recommendation. The LP and Cl algorithms improved the result to a great degree over when Tn(taste) was used. We observed that the number of links in the network increased with the application of the LP algorithm. This implies that users can take advantage of trust of more users. Such increase of feasible links contributes to controlling of the cold-start and sparsity problems. Also, the Clustering algorithm identifying significant clusters to which weights were assigned enhanced performance. Use of the Clustering algorithm made the recommendation system more receptive to the opinions from more significant users than opinions from less significant users. This reduced the influence of noisy data, resulting in enhanced performance. However, if trustnetwork isn't sparse, as like a Tn(profile), LP and Cl make the noisy data and cloud systems judgment. Two trust-networks merged together can complement each other. One of our trust-networks, Tn(hybrid), was constructed this way. In short, the LP algorithm enlarged the scope of significant links so that there were more opinions to be considered. The Clustering algorithm increased receptivity towards opinions of significant users. Both, when combined together, improved the recommendation performance of the trust-network-based recommendation system. The cold start and sparsity problems are caused because the number of links in a trust-network is small, both of which deteriorate the performance of application programs based on a trust-network. Using the proposed method in our paper contributes to controlling of the two problems because the LP algorithm increases the number of links as shown in the table. The Clustering algorithm contributes to controlling of the two problems as it uses the data from members of focused clusters.

In the processes of constructing a trust-network and going through the LP algorithm, promising links are rounded; the threshold for rounding fundamentally affects the link density of the trust-network. In our experiment, the performance of our application program was negatively influenced when the number of links was either too small or too large.

Conclusion and Suggestion for Further Explorations

In this paper, we proposed the method based on LP and Clustering algorithms for solving problems which were named cold-start and sparsity problems. We constructed a trust-network from a semantics viewpoint to improve reliability. The LP algorithm and the Clustering algorithm were applied for improving the reliability from the structural viewpoint. Based on our proposed trust-network, we implemented a recommendation system operating on a real-world data set to test whether an improvement in performance can be achieved with our proposed method. We could observe that when the LP algorithm is applied to a trust-network, the density of the network changes depending on how rounding is performed in forming links, which affects the performance of the recommendation system. We also observed that applying the Clustering algorithm to a trust-network improves the trust-network by finding significant links. Our proposed method, by expanding links and finding significant links, could successfully control the problems of cold-start and sparsity that frequently take place in a trust-network and improve the application program. It should be noted, however, that the algorithms used in this paper are comparatively easy to implement, a reason for variable results depending on how the algorithms were set and combined. Securing improved performance thus requires flexible and intelligent combining of algorithms depending on the characteristics of the system being developed. Further explorations may investigate how trust-networks are constructed from various viewpoints as well as how different algorithms are combined intelligently to provide improved services to users.

Fig. 1 .

 1 Fig. 1. Graph of results.

Table 1 .

 1 Results of experiments.

Table 2 .

 2 Comparing original network and prediction network.

		Number of links The percentage of links
	Tn(taste)	5,742	1.149%
	Tn(profile)	350,541	70.18%
	LP-Tn(taste)	37,566	7.520%
	LPCL-Tn(taste)	47,586	9.527%

Table 3 .

 3 The MAE in accordance with change of round

	No round Average round Round(0.2)
	MAE 0.767	0.751	0.765

Acknowledgments. This research was supported by the MKE(The Ministry of Knowledge Economy), Korea and "LG Electronics". under IT/SW Creative research program supervised by the NIPA(National IT Industry Promotion Agency) (H0504-23-1022) and Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education, Science and Technology (2012009387)