Min Yang
email: myang@cs.hku.hk

Kam-Pei Chow
email: chow@cs.hku.hk

Authorship Attribution for Forensic Investigation with Thousands of Authors

With the popularity of computer and Internet, a growing number of criminals have been using the Internet to distribute a wide range of illegal materials and false information globally in an anonymous manner, making criminal identity tracing difficult in the cybercrime investigation process. Consequently, automatic authorship attribution of online messages becomes increasingly crucial for forensic investigation. Although researchers have got many achievements, the accuracies of authorship attribution with tens or thousands of candidate are still relatively poor which is generally among 20%~40%, and cannot be used as evidence in forensic investigation. Instead of asserting that a given text was written by a given user, this paper proposes a novel authorship attribution model combining both profile-based and instance-based approaches to reduce the size of the candidate authors to a small number and narrow the scope of investigation with a high level of accuracy. To evaluate the effectiveness of our model, we conduct extensive experiments on a blog corpus with thousands of candidate authors. The experimental results show that our algorithm can successfully output a small number of candidate authors with high accuracy.

Introduction

With the development of Internet technologies and online social network, web services (e.g., emails, blogs, forums and micro-blogs) become a means by which new ideas and information spread rapidly. However, since people on the virtual space do not need to provide their real identities, accurate automatic authorship attribution of anonymous documents is increasingly requisite in various cybercriminal scenarios, including online fraud detection, terror message origination, article counterfeit and plagiarism detection. Authorship attribution techniques can assist law enforcement to discover criminals who supply false information in their virtual identities, and collect digital evidence for cybercrime investigation.

Automatic authorship attribution is a problem of computationally inferring the author of an anonymous text or text whose authorship is in doubt [START_REF] Love | Attributing authorship: An introduction[END_REF]. Generally, authorship attribution approaches fall into two major categories: the profilebased approaches and the instance-based approaches [START_REF] Ronald R Coifman | Entropy-based algorithms for best basis selection[END_REF][START_REF] Vel | Mining email content for author identification forensics[END_REF][START_REF] Li | From fingerprint to writeprint[END_REF][START_REF] Zheng | Authorship analysis in cybercrime investigation[END_REF]. For the profilebased approach, a single representation (i.e., profile) is produced for each author using training data. Each text of unknown authorship is then compared with the profile of each author and is assigned to the most likely one. The profilebased approach is able to handle very short texts since they concatenate all the texts by the same author. For the instance-based approach, it produces one representation per training text, and a classification model is built to estimate the most likely author of a anonymous text. Compared with the profile-based approach, the instance-based approach is easier to combine different text representation features, and it is more robust when the size of candidate authors set is large. Further study [START_REF] Kourtis | Author identification using semisupervised learning[END_REF] shows that profile-based and instance-based approaches could be complementary to each other, and combining these two approaches can significantly improve the performance of author attribution.

Most of the previous works on authorship attribution focus on formal texts with only a few possible authors by applying statistics [START_REF] Ronald R Coifman | Entropy-based algorithms for best basis selection[END_REF] and machine learning approaches [START_REF] Vel | Mining email content for author identification forensics[END_REF][START_REF] Li | From fingerprint to writeprint[END_REF][START_REF] Zheng | Authorship analysis in cybercrime investigation[END_REF]. Unfortunately, this version of the authorship attribution problem dose not often arise in the real world. Recently, researchers have turned their attention to informal texts (e.g., emails and social blogs) and tens to thousands of authors [START_REF] Madigan | Author identification on the large scale[END_REF][START_REF] Koppel | Authorship attribution with thousands of candidate authors[END_REF][START_REF] Schler | Effects of age and gender on blogging[END_REF][START_REF] Luyckx | Authorship attribution and verification with many authors and limited data[END_REF][START_REF] Kourtis | Author identification using semisupervised learning[END_REF][START_REF] Koppel | Authorship attribution in the wild[END_REF][START_REF] Seroussi | Authorship attribution with author-aware topic models[END_REF]. For example, Koppel et al. [START_REF] Koppel | Authorship attribution in the wild[END_REF] use similarity-based methods along with multiple randomized feature set to achieve high precision when the set of known candidates is extremely large (many thousands). To conquer the challenge that there are not enough labeled examples to construct an accurate classifier, some semi-supervised learning approaches for authorship attribution have been proposed. These approaches usually use the test data as unlabeled examples to improve the classification model [START_REF] Rafael Guzmán-Cabrera | A web-based self-training approach for authorship attribution[END_REF][START_REF] Kourtis | Author identification using semisupervised learning[END_REF]. Considering the content of documents and the interests of authors, the author-topic model has been used for authorship attribution [START_REF] Seroussi | Authorship attribution with author-aware topic models[END_REF], which yield a state-of-theart performance in terms of classification accuracy when tens or thousands of candidate authors are taken into account.

Although researchers have got many achievements, the accuracies of authorship attribution with tens or thousands of candidate are still relatively poor, which are generally among 20%~40% [START_REF] Luyckx | Authorship attribution and verification with many authors and limited data[END_REF][START_REF] Koppel | Authorship attribution in the wild[END_REF][START_REF] Seroussi | Authorship attribution with author-aware topic models[END_REF]. The traditional authorship attribution approaches cannot be used as evidence in forensic investigation since a quite accurate prediction is required for digital forensics, and it is useless in the sense that we could never confidently assert that a given text was written by a given user. In this paper, we propose a novel hierarchical authorship attribution algorithm combining both profile-based and instance-based approaches to reduce the size of the candidate authors and narrow the scope of investigation with a high level of accuracy. First, we apply profile-based paradigm to build two classifiers with different feature sets for gender and age attribution respectively. And then, a authorship attribution classifier is built using the probabilities distribution of gender and age attribution obtained in the previous step as prior. With this classifier, we can obtain a small number of the most possible authors from thousands of candidate authors with a high level of accuracy that is higher than a threshold (e.g., 95%). At last, we output a set of most possible authors with probabilities. Extensive experiments have been conducted to verify the proposed approach on real-world blog dataset.

The rest of this paper is organized as follows. In Section 2, we review related work in authorship attribution. In Section 3, we introduce our model and algorithm used in this paper. In Section 4, we presents the experiment data and experimental setting. In Section 5, the experiment results are showed and discussed. Finally, Section 6 concludes the paper and indicates some future works.

Related Work

In resent years, plenty of statistical and machine learning techniques have been proposed for authorship attribution using different kinds of features [START_REF] Lee | Efficient l˜1 regularized logistic regression[END_REF][START_REF] Abbasi | Applying authorship analysis to extremistgroup web forum messages[END_REF]. Stamatatos details most of the existing techniques for automatic authorship attribution in [START_REF] Stamatatos | A survey of modern authorship attribution methods[END_REF]. Generally speaking, authorship attribution approaches can be classified into two groups: profile-based approaches and instance-based approaches. Profile-based approaches concatenate training texts per author in one single text file. An unseen text is, then, compared with each author file, and the most likely author is estimated based on a distance measure. For example, Keselj, et al. [START_REF] Kešelj | N-gram-based author profiles for authorship attribution[END_REF] propose a widely used n-grams profile-based method, which is based on building a byte-level n-gram author profile of an authors writing. Frantzeskou et al. [START_REF] Frantzeskou | Effective identification of source code authors using byte-level information[END_REF] proposed a novel and simple distance, called simplified profile intersection (SPI), which simply counts the amount of common n-grams of the two author profiles. This approach to authorship identification of source code provide better results than other distances. In order to utilize the differences between the training texts by the same author, the majority of the modern authorship attribution approaches are instance-based, which consider each training text sample as a unit that contributes separately to the authorship attribution. Such as, Burrows [START_REF] Burrows | An ocean where each kind: Statistical analysis and some major determinants of literary style[END_REF] presents principal components analysis with word frequencies to analyze authorship, and the results show a high level accuracy. Peng et al. [START_REF] Peng | Augmenting naive bayes classifiers with statistical language models[END_REF] extend the naïve Bayes algorithm for authorship attribution with statistical language models. Halteren [START_REF] Van Halteren | Author verification by linguistic profiling: An exploration of the parameter space[END_REF] proposes a method that borrows some elements from both profile-based and instance-based approaches.

To conquer the challenges that there are not enough labeled examples to construct an accurate classifier, some semi-supervised learning approaches have been proposed since it is possible to use the test sets as unlabeled examples and use some information from them to improve the classification model [START_REF] Rafael Guzmán-Cabrera | A web-based self-training approach for authorship attribution[END_REF][START_REF] Kourtis | Author identification using semisupervised learning[END_REF]. Guzman et al. [START_REF] Rafael Guzmán-Cabrera | A web-based self-training approach for authorship attribution[END_REF] propose a self-learning method that is specially suited to work with just a few training examples to tackle the problem that lacks of training data with the same writing style. That method considers the automatic extraction of the unlabeled examples from the web and its iterative integration into the training data set. Kourtis and Stamatatos [START_REF] Kourtis | Author identification using semisupervised learning[END_REF] apply a co-training learning approach for authorship attribution by combining the Common N-Grams (CNG) [START_REF] Kešelj | N-gram-based author profiles for authorship attribution[END_REF] model and a Support Vector Machine classifier based on character n-grams. Its main idea is to combine the outputs of these classifiers in the test set and augment the training set with additional document.

Most of the previous works consider the simple version of the authorship attribution problems, and focus on formal texts with only a small, closed set of candidate authors. In order to apply authorship attribution in real life data, some large candidate sets with informal texts have been considered by researchers recently. Luyckx and Daelemans [START_REF] Luyckx | Authorship attribution and verification with many authors and limited data[END_REF] propose a memory-based learning approach in doing authorship attribution with many authors and limited training data, and the results show the robustness of the memory-based learning approach when compared to eager learning methods such as SVMs and maximum entropy learning. Madigan et al. [START_REF] Madigan | Author identification on the large scale[END_REF] conduct experiments on a collection of data released by Reuters consisting of 114 authors using sparse Bayesian logistic regression. This proposed algorithm shows promising performance as a tool for authorship attribution with high-dimensional document representations. Different from the approaches mentioned above, our algorithm take authors profile information (e.g., age and gender) into consideration, which is motivated by the analysis conducted by Schler et al. in [START_REF] Schler | Effects of age and gender on blogging[END_REF] indicating significant differences in writing style and content between male and female bloggers as well as among authors of different ages. In addition, instead of asserting that a anonymous text was written by a given user, our authorship attribution algorithm proposes to reduce the size of the candidate authors and narrow the scope of investigation with a high level of accuracy.

The Proposed Method

In this section, we describe a novel authorship attribution algorithm combining both profile-based and instance-based approaches to reduce the size of the candidate authors and narrow the scope of investigation with a high level of accuracy. Generally, the proposed algorithm consists of two phase, as shown in Figure 1. In the first phase, we apply profile-based paradigm to build two classifiers with different feature sets for gender and age attribution, respectively. The probability distribution of gender and age can be used as a prior for the next phase. In the second phase, a logistic regression classifier is built using the probability distribution of gender and age as prior based on instance-based paradigms. With this classifier, we can obtain a small number of the most possible authors from thousands of candidate authors with a high level of accuracy that is higher than a threshold.

Features Selection

In this work, we consider differences in male and female authors and differences among authors of different ages. Broadly speaking, two different kinds of potential distinguishing features can be considered: content-based features and style-based features . This is motivated by the observation that different people might tend to write about different topics as well as to express themselves differently about the same topic. For style-based features, we consider individual parts-of-speech and function words, which is described by Eggins in [START_REF] Eggins | Introduction to systemic functional linguistics[END_REF]. Contentbased features are simple content words, and we apply unigrams in this work. For gender, we choose 2000 features with greatest information gain for gender. Similarly, 2000 features with greatest information gain for author are selected to train the classifier for authorship attribution.

Age and Gender Attribution

For each author, we concatenate all his documents and extract both contentbased features and style-based features from them. To present the document with extracted features, we represent a document as a numerical vector X = (x 1 , . . . , x i , . . . , x n ), where n is the number of features and x i is the relative frequency of feature i in the document. Once labeled training documents have been represented in this way, we can apply machine-learning algorithms to learn classifiers that assign new documents to categories. In this paper, we use logistic regression [START_REF] Lee | Efficient l˜1 regularized logistic regression[END_REF] to learn two classifier that classify texts according to author's gender and age, respectively. Logistic regression is widely used for classification problems recently, and the independent variables do not have to be normally distributed, or have equal variance in each group. Whats more, logistic regression is more than just a classifier. Instead, it can make stronger and more detailed predictions such as the predicted probabilities. Consider a binary supervised leaning problem, where were given a set of instance-label pairs {(x i , y i ) | i = 1, . . . , n}. Here, x i ∈ R M is an M -dimensional feature vector, and y i ∈ {0, 1} is the class label. Formally, the logistic regression model which predicts the conditional probability distribution of the class label y given the input feature vector x is that

Pr(Y = 1|X; β 0 , β) = π(x; β 0 , β) = 1 1 + exp(-(β 0 + x • β)) (1)
Where β ∈ R M is the coefficient vector of X, and β 0 is the intercept term. π(x; β 0, β) is the probability of the outcome of interest. For multi-class classification problem, we can still use logistic model. Assume Y can take k values, instead of having one set of parameters β 0 and β , each class c will have its own parameters β (c) 0 and β (c) , then the predicted probability distribution will be

Pr(Y = 1|X; β (c) 0 , β (c) ) = π(x; β (c) 0 , β (c) ) = 1 1 + exp(-(β (c) 0 + x • β (c) )) (2)

Authorship Attribution

After we obtained the estimator for gender and age, we can use the predicted probabilities for gender and sex as a prior for authorship attribution.

Given documents S for an unknown author, given the information of all candidate authors' gender and age information, the probability distribution for authorship attribution is given by

p (author = i|S, gender, age_class) ∝ p (author = i|S)•p (gender(i)|S)•p (age_class(i)|S) (3)
where the first term acts like a likelihood, and the second and third terms served as priors.

p (author = i|S) is estimated with an instance-based approach, i.e. we estimate the likelihood for each instance documents separately, and multiply the probabilities together to get the combined probability

p(author|S) ∝ ∏ i p(author|S i ) (4)
4 Experiments

Dataset description

The Blog Authorship Corpus consists of 678,161 blog posts of 19,320 bloggers gathered by Schler et al. [START_REF] Schler | Effects of age and gender on blogging[END_REF] from blogger.com in August 2004. There are approximately 35 posts and 7250 words per person. The blog posts can be about any topic, but the large number of authors ensures that every topic is likely to interest at least some authors. The (self-reported) age and gender of each author is known and for each age interval the corpus includes an equal number of male and female author based on the authors reported age, we label each blog in our corpus as belonging to one of three age groups: 13-17 (42.7%), 23-27 (41.9%) and 33-47 (15.5%).

Algorithm 1 Hierarchical Author Identification

-Given N documents written by K authors X = {x1, . . . , xN } and their authorship labels y = {y1, . . . , yN }, where yi ∈ {1, . . . , K}. -For each author i ∈ {1, . . . , K}, we have gender(i) ∈ {M, F } and age_class(i) ∈ {teenagers, young adults, middle-aged}. -Gender attribution

• Extract features X (g) for gender classifier using stylistic features and contentbased features selected by information gain for gender • Use X (g) and y (g) = {gender(y1), . . . , gender(yN )} to train a gender classifier with profile-based paradigm • Given documents S from an unknown author, the gender classifier can estimate the probability distribution p(gender|S) for gender ∈ {M, F }. -Age class attribution

• Extract features X (a) for age classifier using stylitic features and content-based features selected by information gain for age class • Use X (a) and y (a) = {age_class(y1), . . . , age_class(yN )} to train an age classifier with profile-based paradigm Since some blogs in this corpus are meaningless for authorship attribution, such as advertisements and lyrics of songs, we first remove the authors who wrote smaller than 20 blogs. And then, we use Akismet1 to remove the potential spams among these authors. Finally, we obtain 2,077 prolific authors with their full posts as our training data. The statistics of the dataset is shown in Table 1.

Experimental Setup

In the experiments, data preprocessing was performed on both data sets. First, the texts are tokenized with a natural language toolkit NLTK2 . Then, we remove non-alphabet characters, numbers, pronoun, punctuation and stop words from For all experiments, we perform ten-fold cross validation, and the results are evaluated using classification accuracy, i.e., the percentage of test documents that were correctly assigned the author. What's more, L1-regularized logistic regression is used to train the classifiers, which is well-suited for large-scale text classification. Here, LIBLINEAR4 is used as the implementation of logistic regression classifier. We experiment with cost parameter valued from the set {0.01, 0.1, 1, 10}, until no accuracy improvement was obtained.

Experimental Results

In this section, we present and discuss the experimental results in details.

Gender and age attribution results

For gender attribution, we consider it as a binary classification problem with the class label female and male. Accuracies of gender attribution are shown in the first line of Table 2. From Table 2, we observe that the proposed algorithm can obtain 85.1% accuracy with the combined features, which is 3.2% higher than that using style-based features and 5.9% higher than that using content-based features.

For age attribution, we label each blog in our corpus as belonging to one of three age groups {teenagers, young adults, middle-aged}, based on author's reported age. The age attribution problem in this paper can be treated as a multiclass L1-regularised logistic regression problem. Results for age attribution are shown in the second line of Table 2. Similar to gender attribution, we can gain the best performance with 80.1% accuracy using both style and content features.

•

  Given documents S from an unknown author, the gender classifier can estimate the probability distribution p(age_class|S) for age_class ∈ {teenagers, young adults, middle-aged}. For any author i, calculate thhe posterior probability with author's gender and age class distribution as prior using 3.• Output M authors {a1, . . . , aM } who have highest posterior probability. The number M of authors to output is chosen to ensure

	∑	p(author = ai) >
	threshold.

-Authorship attribution • Use X and y to train an authorship classifier using instance-based pradigm • Given documents S from an unknown author, the authorship classifier can estimate the probability distribution p(author|S) using 4. •

Table 1 .

 1 Dataset statistics the texts. Finally, WordNet stemmer 3 is applied so as to reduce the vocabulary size and settle the issue of data spareness.

	Age	Female	Gender Male	Total
	13~17	335	348	683
	23~27	543	503	1046
	33~47	170	178	348
	Total	1048	1029	2077

http://akismet.com/

http://www.nltk.org

http://wordnet.princeton.edu

http://www.csie.ntu.edu.tw/~cjlin/liblinear/

Based on the results in Table 2, we can summarize that authors' gender and age information might be highly helpful for authorship attribution because of the high accuracies of gender and age attribution on the blog dataset. With the probability distribution gained from gender and age attribution, most of the candidate authors who have different profiles (i.e., gender and age) with the author of anonymous documents, can be filtered in authorship attribution.

Authorship attribution results

To evaluate the effectiveness of our approach, we compared the proposed algorithm with standard logistic regression and Disjoint Author-Document Topic Model (DADT) used in [START_REF] Seroussi | Authorship attribution with author-aware topic models[END_REF], utilizing the same features. We report the classification accuracies in Table 3. As an easy observation, the proposed hierarchical authorship attribution algorithm significantly outperforms the other algorithms that are widely used for authorship attribution. For example, The accuracy of our algorithm is 3.7% higher than DADT model and 7.4% higher than standard logistic regression, validating the effectiveness of the proposed algorithm. Although our algotithm achieves state-of-the-art performance compared to the existing model for authorship attribution, it cannot produce a practicable and authentic result for forensics in real life. Hence, instead of classifying a given text to a specific author with relatively low accuracy, we seek to output a small number of potential candidate authors with a high level of accuracy. The experiment result of our proposed hierarchical authorship attribution is described in Figure 2. With the accuracy of 96.5%, we can narrow down the size of candidates authors from 2,000 to 20. Furthermore, we can get 100% accuracy when choosing 35 candidate authors from the original experimental dataset. These results show that our model can help investigator to narrow the scope of investigation with a high level of accuracy. The advantages of our approach comes from its capability of taking the probability distribution gained from gender and age attribution, as prior knowledge to filter many easily confused candidate authors.

Fig. 2. Accuracy with different number of candidate authors 6 Conclusions and Future Work

In this paper, we introduce a hierarchical classifier which combines profile-based and instance-based paradigms to automatic authorship attribution in cases with a large number of informal texts from thousands of authors. Instead of predicting a author with relatively low accuracy, we seek to reduce the size of the candidate authors and narrow the scope of investigation with a high level of accuracy. The mainly advantage of our approach comes from its capability of taking the probability distribution gained from gender and age attribution, as prior knowledge to filter many easily confused candidate authors. Extensive experimental results indicate that our algorithm can successfully output a small number of candidate authors with high accuracy. For example, we can choose 20 potential candidate authors from 2000 candidates with the accuracy of 96.5%, and the probability of each candidate authors can be output to assist the investigators.

Our approach performed well for closed-set tasks, while it cannot be applied to open-set tasks in which the true author of an anonymous text might not be one of the known candidates. In the future, we will devote our effort to extend the proposed hierarchical classifier to handle the open-set tasks by assessing classification confidence. Another possible research direction is to deal with the imbalance problem where a relatively small number of text at least for some candidate authors compared to other candidates.


Christoph Bier

Jonas Prior

Detection and Labeling of Personal Identiable Information in E-Mails

The protection of personal identiable information (PII) is increasingly demanded by customers and data protection regulation. To safeguard PII a organization has to nd out which incoming communication actually contains it. Only then PII can be labeled, tracked, and protected. E-mails are one of the main means of communication. They consist of unstructured data dicult to classify. We developed an automated detection system for PII in e-mails and connected it to a usage control infrastructure. Our concept is based on previous ndings in the area of spam detection. We tested our approach with a data set in a customer service scenario. The evaluation shows that the utilization of Bayes-classication is very promising to detect PII.

Introduction

The European data protection regulation (95/46/EC) requires enterprises, e.g., telecommunication providers, to comply with the clients' privacy rights, to ensure the protection of personally identiable information (PII) and to fulll the right to information. The right to information entitles the data subject to request from the data controller information on origin, transfer, and purpose of processing of his PII at any time. Thus, the usage and processing of PII needs to be safeguarded and controlled by detection, labeling and tracking. With the tremendous growth of data, it is not feasible to do that ad hoc. As a solution, usage control and provenance tracking methods [START_REF] Bier | How Usage Control and Provenance Tracking Get Together -A Data Protection Perspective[END_REF] are proposed in recent research. But one of the major and yet unsolved problems remains: How does one know which received or created data contains PII? How can privacy policies and PII come together? Up to now, this is mostly done manually. But it is not yet possible to detect unstructured PII and annotate them with policies automatically.

As one of the most frequently used means of communication between clients and companies, especially in customer service, e-mails oer a rich source of PII. Many of them contain highly condential customer data like banking accounts, usage patterns or contractual data, while many others like internal e-mails and newsletters do not. Overall, PII in e-mails is heterogeneous and therefore dicult to identify.

In this paper we present a model that can recognize e-mails containing PII and annotate them with policies (section 2). Our idea is to apply spam lter technologies to the classication of PII in incoming e-mails.

We design an integrated model of PII detection, usage control and provenance tracking, that can attach and enforce policies for sensitive data in order to protect them. A prototype is developed as part of a mail user agent to show the general feasibility of our idea (section 3). An extensive evaluation based on realistic test data shows that our approach is reasonably justied and promising (section 4).

Classication

PII are heterogeneous and dier from scenario to scenario. Therefore, an automatic learning system has to be developed to detect e-mails containing PII. The classication of such e-mails is a binary text classication problem meaning that there is one class with PII and one without PII. The issue is equivalent to the spam lter problem where e-mails need to be classied in good (ham) or bad ones (spam).

A frequently used algorithm for binary text classication is the Naive Bayes classier. Naive refers to the assumption that the occurrence of the features, in this case the words of the e-mail, are distributed independently. But this assumption does not hold for textual data. The Naive Bayes classier estimates a probability for each class based on previously classied data. The best class is the one with the highest probability (maximum a posteriori) [START_REF] Manning | Introduction to information retrieval[END_REF]. Thus, for each class a probability is calculated. The prior knowledge P (c j ) of each class is multiplied by the product of all P (a i |c j ). P (a i |c j ) is the conditional probability that the term a i occurs in class c j based on previously classied data.

c map = arg max cj ∈C P (c j ) n i=1 P (a i |c j ) (1)
Naive Bayes is the basis of most spam lters [START_REF] Zdziarski | Ending Spam: Bayesian Content Filtering and the Art of Statistical Language Classication[END_REF]. The most widely used model of spam lters is based on Graham's and Robinson's ideas [START_REF] Graham | A plan for spam[END_REF][START_REF] Robinson | A statistical approach to the spam problem[END_REF]. Robinson extended Graham's work by customizing the conditional probability P (a i |c j ) in order to deal with rare words that occur only in one class. Furthermore, he used the Fisher method to combine the conditional probabilities into a χ 2distribution with 2n degrees of freedom. In his model, an e-mail can be classied as unsure when the classier is not sure about the correct class. The conditional probabilities for the classes c ham and c spam are combined into a χ 2 -distribution χ 2 2n = -2 ln( We use this approach and substitute the two classes ham and spam with PII and noPII. The classier learns from e-mails marked as PII or noPII and the calculation of the scores I remains the same. The classication of the e-mails then is done by dening two thresholds t noP II and t P II :

class =      PII if t P II > I > 0 unsure if t noP II ≥ I ≥ t P II noPII if 1 > I > t noP II (2)
If the classication returns the class unsure. then the user has to do the classication manually. If t noP II + t P II = 1, then there is no third class unsure.

Architecture

The scenario of privacy policies requires to combine the classication of textual information proposed in the foregoing section with usage control and provenance tracking technologies. Hence, we have developed an overall architecture described in the rst part of this section forming the framework for these components. Following, the structure of the PII-detector is claried. An instantiation shows the practical applicability of our approach.

The Usage Control and Provenance Architecture. Our PII-detector is embedded in an architecture to enable usage control and provenance tracking of the sensitive data contained in detected e-mails. A basic usage control architecture consists of a policy enforcement point (PEP), a policy decision point (PDP) and a policy information point (PIP). The PEP is integrated in each application or system where policies have to be enforced in. Every time an event (like "copy" or "delete") is detected, the PEP informs the PDP and asks if the event is allowed or not. The PDP decides this request based on the deployed policies. In the case of data-centered policies [START_REF] Pretschner | Representation-Independent Data Usage Control[END_REF], the PDP asks the PIP if the container (e.g., les, e-mails) mentioned in the event contains data referred to in one of the deployed policies. If the PDP allows the event to happen, the information ow model of the PIP is updated. Provenance tracking takes advantage of the information ow state represented by the PIP and provides comprehensive information to the person concerned (data subject) [START_REF] Bier | How Usage Control and Provenance Tracking Get Together -A Data Protection Perspective[END_REF].

The process of introducing a PII-containing e-mail to the infrastructure is as follows: First, the policy of the container is deployed at the PDP. Second, representations of the containers holding the newly detected PII are created at the Provenance Storage Point (ProSP). Additional meta information (e.g., sender e-mail address) is provided. Third, the PIP is informed about a new representation, connecting the container and the data ID.

The PII-Detector as Part of a Mail User Agent. The processing of incoming e-mails is handled by the mail user agent (e.g., Mozilla Thunderbird) in which the PII-detector is integrated by taking advantage of the agent's plugin framework. The PII-detector is responsible for three tasks: Detect e-mails containing PII based on the previous described classication model, label the e-mails classied as sensitive, and inform the usage control infrastructure. For detection, the message body of a new incoming e-mail is tokenized in its single words. The header of the e-mail is omitted, because the potentially sensitive sender and receiver addresses do not provide any information about the sensitivity of the content itself. Furthermore a rule-based classication on header elds (e.g. messages from sender A contains always PII) could lead to a high percentage of false classied e-mails. Next, an analyzer calculates probabilities for each word and combines them with the Fisher method (see section 2). Based on the calculated scores, the e-mail is marked as an e-mail containing PII or not. Finally, the tokens of the new incoming e-mail are added to the existing training data. E-mails clasied as containing PII are labeled by adding a special tag to the header of the e-mail. This labeling is shown to the user via the graphical interface of the mail user agent. By one click, the user can correct the decision made by the classier.

To show the benet of our approach, we instantiated the PII-detector as the Thunderbird (TB) extension Thunderbayes4PII. A PEP for TB has already been developed [START_REF] Loerscher | Usage Control for a Mail Client[END_REF]. Furthermore, spam lter implementations are available. Our implementation is built on Thunderbayes++. 1 We selected it because it integrates SpamBayes, 2 an one-to-one implementation of the methodology of Robinson and Graham. We adapted SpamBayes such as only the body and the subject of a message are analyzed for classication. In addition, we replaced the classes ham and spam by PII and noPII. Moreover, spam-specic components were deactivated and the GUI was adapted to the PII-detection task.

Evaluation

We evaluate the performance of the previously described PII-detector to detect e-mails with PII with a test data set consisting of e-mails with (class PII ) and without PII (class noPII ). Our use case is the e-mail communication between customers and the customer support of a telecommunication company. Unfortunately, there are no publicly available e-mails with PII. Hence, we used public data sets which we transformed to an appropriate test set by adding PII.

We crawled the messages of customers from the Service Forum of Deutsche Telekom AG, 3 where customers ask questions concerning telecommunication services, bills or orders. Although these messages are public, they represent communication between a customer and customer service. Furthermore, the style of writing in these messages is similar to e-mail communication. However, these messages do not contain any PII to identify the customer. Therefore we added articially generated PII to create a realistic data set for the class PII. Depend- 1 ThunderBayes++ Google Code Project https://code.google.com/p/thunderbayes/. 2 SpamBayes Project Website http://spambayes.sourceforge.net/. 3 Deutsche Telekom AG Service Forum http://forum.telekom.de. ing on the content of the messages, we added PII such as the full address, a customer/access/invoice/order/phone number or banking account data.

For class noPII we selected e-mails from the authors' mailbox, e-mails about telecommunication, internet advertisements and marketing. Moreover, e-mails from the Service Forum of the Deutsche Telekom not containing PII were chosen. Likewise, we added e-mails from the ENRON data set, which represents internal communication of a company. Table 1 provides an overview of the selected sources. The messages from the Service Forum were converted into an e-mail format. The e-mails are written in German language, except the e-mails from the ENRON data set, which were translated from English to German. For the evaluation, we used 500 e-mails belonging to class PII and 500 e-mails belonging to class noPII whereby the data set consists of 1000 e-mails in total. We used a confusion matrix to create measures to evaluate the performance of the classier [START_REF] Han | Data mining: concepts and techniques[END_REF]. True Positives (TP) and True Negatives (TN) refer to the number of elements, which are classied correctly while False Positives (FP) are predicted as positives, but are actually negatives. False Negatives (FN) are predicted as negative elements which are actually positives. Unsure Negative (UN) and Unsure Positive (UP) are the e-mails, which are classied as unsure. The confusion matrix in table 2 summarizes TP, FP, FN, TN, UN and UP.

Accuracy describes the fraction of the correctly classied e-mails in total.

Accuracy = T P + T N T P + F P + T N + T P + U N + U P (4)
We performed a n-fold cross-validation to evaluate the performance of our detection system. This means that the data set was split into n subsets. n-1 of them are used for training the PII-detector, the remaining subset was the test data to evaluate it. This was repeated n times, each time with a dierent training and test set. The average of the results of all evaluations is the performance of the model. We performed an evaluation for n=5 and n=10. This means, the training data in the 10-fold cross-validation consisted of 900 e-mails and the test data of 100 e-mails. In the 5-fold cross-validation the ratio was 800 e-mails for training and 200 e-mails for testing.

Furthermore, the thresholds t P II and t noP II were varied. We started with t P II = 0.1 and t noP II = 0.9 and increased t P II in each iteration by 0.1 and at the same time decreased t noP II by 0.1 (see gure 1). The results of the evaluation show that our proposed system can detect emails with PII very well and has an accuracy of more than 95%. The articial inclusion of PII in the Telekom data set has not inuenced the quality of the evaluation. The classication of the Bayes lter was in all e-mails based on key words in proximity to the PII, but not on the PII itself. Nevertheless, it should be considered that the quality of the PII-detector depends on the quality of the training data. Furthermore, the training and test data consists of e-mails in German language. The results could dier in other languages.

Related Work

Text classication is mostly done by learning algorithms. According to the literature, the results of evaluation and comparison of dierent classication models (Support Vector Machines, k-Nearest-Neighbours, Decision Trees, Naive Bayes, ... ) on textual data has shown that Support Vector Machines performed best in the evaluations [911]. Still, Naive Bayes classiers have the advantage to learn new data incrementally.

Access & Usage Control systems need policy specication languages [START_REF] Pretschner | Policy Evolution in Distributed Usage Control[END_REF]. Usage control can be understood as an extension of access control to the future [START_REF] Park | The UCON ABC usage control model[END_REF]. Usage control is concerned with how data can be used when it has been accessed to. Usage control systems have been instantiated for several kinds of layers such as Thunderbird [START_REF] Loerscher | Usage Control for a Mail Client[END_REF], Firefox [START_REF] Kumari | Distributed Data Usage Control for Web Applications: A Social Network Implementation[END_REF], and Windows [START_REF] Wüchner | Data Loss Prevention based on data-driven Usage Control[END_REF].

Provenance tracking originates in scientic computing community [START_REF] Simmhan | A survey of data provenance in e-science[END_REF]. But in recent work it is also discussed how provenance can improve transparency in the context of privacy [START_REF] Bier | How Usage Control and Provenance Tracking Get Together -A Data Protection Perspective[END_REF]. PII is especially relevant in large, unstructured data sets. Hence, a system like the one proposed in this work is a prerequisite to utilize usage control and provenance tracking for the purpose of privacy improvements.

Conclusion

We developed a system that is able to detect e-mails with PII. It is embedded into a usage control and provenance architecture. To our knowledge, it is the rst approach to detect PII automatically and annotate them with policies. We performed a soundly evaluation for a realistic data set and the results have shown that our PII-detector has an accuracy of over 95%, indicating that the approach is promising. Up to now, our evaluation is limited to the German language. Further evaluations with data sets in other languages are suggested.

Future work could encompass extending our PII-detector to other data sources like Word documents. In some cases it could be also interesting to have more than two classes, like PII of dierent degrees of sensitivity.

  a i |c spam )))).Finally the two scores are combined into a single score I = 1+H-S 2 with values between 0 and 1.

  N +U P ) species the fraction of emails containing PII, which are classied correctly. True Negative Rate (T N R = T N T N +F P +U N ) species the fraction of e-mails containing no PII, which are classied correctly. The False Positive Rate (F P R = F P +U N T N +F P +U N ) species the fraction of e-mails containing no PII, which are classied incorrectly. The False Negative Rate (F N R = F N +U P T P +F N +U P ) species the fraction of e-mails containing PII, which are classied incorrectly. The Error rate measures the fraction of incorrectly classied e-mails in total. Error = F P + F N + U N + U P T P + F P + T N + T P + U N + U P

  For the second class a χ 2 -distribution can be dened by replacing P (a i |c ham ) with 1 -P (a i |c spam ) because it is P (a i |c ham ) = 1 -P (a i |c spam )

	n i=1 (P (a i |c spam ))).
	due to the
	binary classication task. The inverse χ 2 2n -function χ -2 2n is applied to both χ 2 -distributions to calculate a score for each class (H and S). The Equation for score H is H = χ -2 2n (-2 ln(

Table 1 .

 1 Data Sources

	Class PII	Class noPII
	Messages from Deutsche Telekom Forum	E-mails from the authors' mailbox E-mails from ENRON data set 4 E-mails about internet marketing 5
		E-mails from internet advertisement platform (Zanox 6 and Alinet 7 )

Table 2 .

 2 Confusion Matrix

				Predicted class
			PII	noPII	unsure
	Actual	PII	TP	FN	UP
	class	noPII

  Fig. 1. Variation of tP II and tnoP II

		Class unsure
	0	t pii	t nopii	1
	Class PII	Class noPII

Table 3

 3 shows the average results of each iteration. The results of the crossvalidation show, that the PII-detector classied e-mails from class PII correctly and did not misclassify any e-mails with PII for t P II ≥ 0.4. The PII-detector misclassied e-mails from the class noPII for some values of t noP II . The e-mails from the class PII seem to be a homogeneous class and dier strongly from most e-mails of the class noPII.

Table 3 .

 3 Cross-Validation n=10 and n=5

	Parameter	Results n=10	Results n=5
	tP II tnoP II Err. Acc. TNR FNR TPR FPR Err. Acc. TNR FNR TPR FPR
	0.1 0.9	0.062 0.938 0.882 0.006 0.994 0.118 0.061 0.939 0.882 0.004 0.996 0.118
	0.2 0.8	0.050 0.950 0.902 0.002 0.998 0.098 0.051 0.949 0.898 0.000 1.000 0.102
	0.3 0.7	0.048 0.952 0.906 0.002 0.998 0.094 0.048 0.952 0.904 0.000 1.000 0.096
	0.4 0.6	0.046 0.954 0.908 0.000 1.000 0.092 0.047 0.953 0.906 0.000 1.000 0.094
	0.5 0.5	0.045 0.955 0.910 0.000 1.000 0.090 0.047 0.953 0.906 0.000 1.000 0.094

Enron Data http://enrondata.org/.

ServiceReport http://servicereport.eu.

Zanox AG, http://www.zanox.com.

alinet GmbH, http://www.affili.net.

Acknowledgment: This work was partially funded by Fraunhofer Gesellschaft Internal Programs, Attract 692166.


Abdallah Ghourabi
email: abdallah.ghourabi@supcom.rnu.tn

Tarek Abbes
email: tarek.abbes@isecs.rnu.tn

Adel Bouhoula
email: adel.bouhoula@supcom.rnu.tn

Behavior Analysis of Web Service Attacks

Keywords: Honeypot, Web Service, Attacker's Behavior, Clustering, Data Analysis

With the rapid development of Internet and its services, cyber attacks are increasingly emerging and evolving nowadays. To be aware of new attacks and elaborate the appropriate protection mechanisms, an interesting idea is to attract attackers, then to automatically monitor their activities and analyze their behaviors. In this paper, we are particularly interested in detecting and learning attacks against web services. We propose an approach that describes the attacker's behavior based on data collected from the deployment of a web service honeypot. The strengths of our approach are that (1) it offers a high interaction environment, able to collect valuable information about malicious activities; (2) our solution preprocesses the set of data attributes in order to keep only significant ones (3) it ensures two levels of clustering in order to produce more concise attack scenarios. In order to achieve these contributions, we employ three analysis techniques: Principal Component Analysis, Spectral Clustering and Sequence Clustering. Our experimental tests allow us discovering some attacks scenarios, such as SQL Injection and Denial of Services (DoS), that are modeled in Markov chains.

Introduction

The Web Service technology is increasingly used in companies due to its simplicity and interoperability. It is based on several standards such as SOAP and XML for exchanging information between applications in heterogeneous environments through the Internet. Among the security problems of Web Services are the exchanged data that can convey many threats to the target system. To address these security issues, administrators have to carefully supervise the execution and utilization of web services. The Honeypot technology constitutes an ideal solution to ensure this kind of monitoring. It allows discovering new attacks methods, intrusion scenarios and attackers' objectives and strategies. In this context, we have proposed in an earlier work [START_REF] Ghourabi | Design and implementation of web service honeypot[END_REF] a honeypot solution, called WS Honeypot, designated to attract and monitor web service attacks.

Honeypots are very useful for collecting valuable information about the attackers and their techniques. However, the volume of collected data increases rapidly due to frequent and repetitive data. The large amount of data complicates the analysis task and overwhelms rapidly the human analyst. Thus, a manual tracking of attackers' activities on the honeypot seems to be very difficult and tedious work. To improve the performance of the data analysis in our WS Honeypot, we propose in this paper an automatic approach to analyze the collected data and describe attackers' behaviors on the honeypot. Our approach combines 3 analysis techniques: Principal Component Analysis to select the features to be extracted from the captured data; Spectral Clustering to cluster the collected requests and Sequence Clustering to regroup the similar activities performed by the attackers and describe their behavior.

The remaining parts of the paper are organized as follows: Section 2 reviews the related works. Section 3 defines the analysis techniques used in our approach. Section 4 presents the architecture of our analysis approach and describes the working principle of the implemented algorithms. Section 5 reports our experimental results. Finally, we conclude the paper in Section 6.

Related Work

The approach proposed in this paper is positioned among other related works that aim to characterize attacks in the honeypots. Despite the common purpose, these works have used various analytical techniques. For instance, Pouget and Dacier [START_REF] Pouget | Honeypot-based Forensics[END_REF] proposed a simple clustering approach to analyze the data collected from the honeypot project Leurre.com. Their objective is to characterize the root causes of attacks targeting their Honeypots. The aim of this algorithm is to gather all attacks presenting some common characteristics (duration of attack, targeted ports, number of sent packets, etc.) based on generalization techniques and association-rule mining. Resulting clusters are further refined using Levenshtein distance. The final goal of their approach is to group into clusters, all attacking sources sharing similar activity fingerprints, or attack tools. Alata et al. [START_REF] Alata | Collection and analysis of attack data based on honeypots deployed on the Internet[END_REF] presented some results obtained from their project CADHo (Collection and Analysis of Data from Honeypots). The purpose of this project is to analyze the data collected from the environment Leurre.com and to provide models for the observed attacks. They proposed simple models describing the time-evolution of the number of attacks observed on different honeypot platforms. Besides, they studied the potential correlations of attack processes observed on the different platforms taking into account the geographic location of the attacking machines and the relative contribution of each platform in the global attack scenario. The correlation analysis is based on a linear regression models. Thonnard and Dacier proposed a framework for attack patterns' discovery from the honeynet collected data [START_REF] Thonnard | A framework for attack patterns' discovery in honeynet data[END_REF]. The aim of this approach is to find, within an attack dataset, groups of network traces sharing various kinds of similar patterns. In this work, the authors applied a graph-based clustering method to analyze one specific aspect of the honeynet data (the time series of the attacks). The results of the clustering applied to time-series analysis enable to identify the activities of several worms and botnets in the traffic collected by the honeypots.

Compared to above works, our approach offers two main advantages. Firstly, we use the Principal Component Analysis to select the pertinent features unlike other works where this selection is done manually. Secondly, to cluster observed attacks, we employ a sequence clustering method which allows tracking the transition between the attacker's activities taking into account the order of realization.

Data analysis techniques

To analyze the large amount of data collected from the honeypot, several techniques of data analysis can be applied, such as statistics, data mining and machines learning. Generally, researchers apply such methods to data for two main reasons: to better understand the existing data and to predict something about new data [START_REF] Maloof | Machine Learning and Data Mining for Computer Security: Methods and Applications[END_REF]. In this paper, we propose a hybrid approach composed of three analysis techniques (Principal Component Analysis, Spectral Clustering and Sequence Clustering) to analyze the data collected from our WS Honeypot and describe the behavior of the captured attacks. Before presenting our approach, we devote this section to introduce these three techniques.

Principal Component Analysis

The Principal Component Analysis (PCA) is a data analysis method used for dimensionality reduction and multivariate analysis. The central idea of principal component analysis is to reduce the dimensionality of a data set consisting of a large number of possibly correlated variables, while retaining as much as possible of the variation present in the data set [START_REF] Jolliffe | Principal Component Analysis[END_REF]. This is achieved by transforming these variables into a smaller number of uncorrelated variables called principal components. This transformation is defined in such a way that the first principal component is a linear combination of the original variables with the largest possible variance. The second principal component is the linear combination of the original variables with the second largest variance and orthogonal to the first principal component, and so on [START_REF] Wang | Identifying Intrusions in Computer Networks with Principal Component Analysis[END_REF].

To describe the principle of PCA, let us consider a set of observations (x 1 , x 2 , ..., x n ) where each observation is represented by a vector of length m. The dataset is represented by a matrix X of dimensions n × m. The transformation into principal components is mainly based on the eigenvalues and the eigenvectors of the covariance matrix C (formed from X). We suppose that (λ 1 , u 1 ), (λ 2 , u 2 ), ..., (λ m , u m ) are the pairs (eigenvalue, eigenvector) of the covariance matrix C. We choose the k eigenvectors having the largest eigenvalues. Afterwards, we form a m × k matrix U whose columns consist of the k eigenvectors. The representation of the data by principal components is made by projecting the original data onto the k-dimensional subspace according to the following rule [START_REF] Wang | Identifying Intrusions in Computer Networks with Principal Component Analysis[END_REF]:

y i = U T (x i -µ)
Where µ = 1 n n (i=1) x i and y i is a k-dimensional vector that represents the projection of the original m-dimensional data vector x i .

Spectral Clustering

Clustering is an unsupervised learning method that seeks to assign a set of objects into homogeneous groups (called clusters). Several algorithms can be used to cluster data such as k-means, hierarchical clustering, spectral clustering, etc. In recent years, spectral clustering has become one of the most popular modern clustering algorithms. It is simple to implement and very often outperforms traditional clustering algorithms such as the k-means algorithm [START_REF] Luxburg | A Tutorial on Spectral Clustering[END_REF]. Unlike other clustering algorithms, the spectral clustering algorithm is based on the concept of similarity between each pair of points instead of distance.

Given a set of data points x 1 , ..., x n , the similarity matrix may be defined as a matrix S, where S ij represents a measure of the similarity between all pairs of data points x i and x j . The main goal of clustering is to divide the data points into several groups in a way that the data points of the same group exhibit similar properties. To do that, the Spectral clustering represents the data in the form of the similarity graph G = (V, E). Each vertex V i in this graph represents a data point x i . Two vertices are connected if the similarity S ij between the corresponding data points x i and x j is positive or larger than a certain threshold, and the edge is weighted by S ij [START_REF] Luxburg | A Tutorial on Spectral Clustering[END_REF].

After constructing the similarity graph, the next step is to find a partition of the graph in a way that the edges between different groups have very low weights and the edges within a group have high weights. The basic idea is to calculate the graph Laplacian matrix L, and to extract the k (number of clusters to construct) first eigenvectors of L. These eigenvectors allow obtaining a projection space with a smaller dimension (k dimensions). Afterwards, a clustering algorithm (e.g. kmeans) can be applied to assign each data point into a cluster among the k ones.

Sequence clustering

The role of sequence clustering is to group a set of sequences in such a way that sequences in the same group (cluster) are more similar to each other than to those in other clusters. The working principle of a sequence-clustering algorithm differs depending on the used implementation. In our work, we are particularly interested in Microsoft Sequence Clustering algorithm [START_REF] Tang | Data Mining with SQL Server[END_REF] which is included in the data mining tools of Microsoft SQL Server.

Microsoft Sequence Clustering

The Microsoft Sequence Clustering algorithm is a hybrid algorithm that uses Markov chain to analyze the sequences and partitions them using the Expectation Maximization (EM) method of clustering. The Markov chain can be defined as a mathematical system that describes the transition probabilities between a set of states. In Microsoft Sequence Clustering algorithm, each generated cluster is associated to an n-order Markov chain.

To describe the basic principles of this algorithm, consider the case of a firstorder Markov chain. For an observed sequence, the probability of belonging to a given cluster is in effect the probability that the observed sequence was produced by the Markov chain associated with that cluster [START_REF] Ferreira | Approaching Process Mining with Sequence Clustering: Experiments and Findings[END_REF]. Consider a sequence x = x 1 , x 2 , ..., x l of length l, the probability of belonging to a given cluster C k is calculated using the following formula:

p(x|C k ) = p(x 1 , C k ). l (i=2) p(x i |x (i-1) , C k ) (1)
where p(x 1 , C k ) is the probability that x 1 is the first state in the Markov chain associated with the cluster C k and p(x i |x (i-1) , C k ) is the transition probability of state x (i-1) to x i in the same Markov chain. To calculate the parameters of this model, the Microsoft Sequence Clustering implements the iterative algorithm Expectation and Maximization (EM).

Automatic analysis of Web service Honeypot data

The data collected from a honeypot contains interesting information about the attacker and his activities. This information is useful to understand the hackers' strategies and to learn the modus operandi of their attacks. To obtain a better knowledge, an exhaustive analysis of collected data is very important. In this paper, we propose an automatic approach to analyze attacks traces collected from the deployment of a Web service Honeypot called WS Honeypot, previously presented in [START_REF] Ghourabi | Design and implementation of web service honeypot[END_REF].

WS Honeypot is a high interaction honeypot that simulates the behavior of a Web service. The role of this honeypot is to attract and monitor attackers targeting web service applications. WS Honeypot provides real web services to ensure a real interaction with attackers. The services offered by the honeypot can be deployed by using two technologies, Axis and .Net. The approach proposed in this paper aims at describing the behavior of attacks captured by WS Honeypot, using several analysis techniques.

WS Honeypot data Analysis workflow

The overall architecture of our approach is shown in Figure 1. The WS Honeypot captures the SOAP messages sent by the attackers. Afterwards, we extract from each SOAP message its characteristic parameters (Feature extraction). Then, we apply a statistical method called "Principal Component Analysis" to select the most relevant features that ensure reliable identification of attacks. Thus, we obtain a dataset of observations (DS1) incorporating significant parameters extracted from captured SOAP messages. The next step consists in applying a spectral clustering on dataset DS1 in order to cluster the captured SOAP messages into homogeneous groups; each group is supposed to represent a message type. As each SOAP message sent by the user is designated to perform an activity in the web service, we consider in the following that each resulting cluster represents an activity type that an attacker can accomplish with different manners at the WS Honeypot. Hence, the spectral clustering analysis allows us to characterize the session of an attacker by determining his activity types in the honeypot in a period of 24 hours. These data are stored on a second dataset DS2 called "session characteristics". The final step of our analysis process consists in applying a sequence clustering on the second dataset DS2 in order to form homogeneous clusters. Each cluster is designed to describe the attacker's behavior for each attack type. The cluster, containing related activity types, can be modeled by a Markov chain to outline the attack scenario.

Features selection and extraction

Features selection and extraction is a preprocessing step, which is very important in our approach. It allows the selection of relevant features to be extracted from the SOAP messages in order to improve the performance of the clustering process. Although the choice of these features can be made manually based on expert knowledge, the use of automated algorithms for feature selection is very interesting to obtain better results. In the case of our approach, we employ a statistical method called "Principal Component Analysis" to select the most pertinent features.

The selection process is as follows: Firstly, we prepare a preliminary list of all possible features that we can extract from a SOAP message. Then, we apply the PCA algorithm on a set of instances representing some SOAP messages according to the chosen features. Finally, we exploit the results of PCA to reduce the preliminary list of features and keep only those which are relevant.

Preliminary list of features

First of all, we describe all features that we are able to extract from a SOAP message. The Web service requests are formatted in XML language and encapsulated in SOAP messages with the use of HTTP as a transport protocol. A malicious user, trying to attack the Web service, can inject a malicious content in the SOAP message in order to exploit the target. Therefore, the inspection of the SOAP messages contents is essential to identify attacks. Moreover, we extract extra parameters characterizing the SOAP exchange and the amount of consumed resources for processing. This list includes the source IP address of the sender machine, the destination IP address, the encoding type, the header size, the overall size of the request, the protocol type, the port number, the input parameters of the web service operations and some information related to the request processing (execution time, memory and CPU usage). We present in Table 1 the preliminary list of the selected features during this step.

Selection of pertinent features

The objective of this step is to apply the Principal Component Analysis (PCA) method in order to reduce the list of preliminary features described in Table 1 by eliminating useless features. For this purpose, we collect several types of SOAP requests. In addition to normal requests, we gather others messages with malicious code causing several attacks such as SQL/XML injection, denial of service, parameter tampering, etc. From each SOAP message, we extracted the features described in Table 1 and we stored them in a dataset. Each instance (observation) of the dataset is designed to characterize a SOAP request. On this dataset, we applied a PCA algorithm implemented in Tanagra software [START_REF] Rakotomalala | TANAGRA: a free software for research and academic purposes[END_REF].

The PCA replaces the old axes with new axes (called factorial axes). The latter are associated with new variables (called principal components) obtained by linear combinations of old variables. To interpret the results, we report in Table 2 the obtained factorial axes, the associated eigenvalues, the proportion of inertia (data dispersion) explained by each factorial axis and the cumulative inertia. For the choice of factorial axes (or principal components) to be retained, we are based on the Kaiser criterion [START_REF] Kaiser | The application of electronic computers to factor analysis[END_REF] which consists in only retaining the axes that have an eigenvalue greater or equal to 1 (i.e. the first 6 axes). Nevertheless, as the axes 7 and 8 have an eigenvalue very close to 1, we also retained them. From Table 2 we can see that the first 8 factorial axes dispose 77.84% of the available information.

The last step in this process consists in projecting the original data on the 8 first factorial axes and determining the variables that correlate better with these axes. Based on this projection, we selected 12 variables that have a high correlation with the factorial axes: Operation, Soap msg Size, Mem, CPU, Time, in1, in2, in3, in4, in5, in6, and in7. This analysis show that these 12 variables are the most important (and hence the most relevant) compared to the rest of variables.

The selected variables (features) are used to construct the first dataset "SOAP message content" noted DS1. From each SOAP request captured by the WS Honeypot, we extract the 12 features to characterize the request and we store them in the dataset DS1.

SOAP messages clustering

Intruders employ different methods to penetrate the target system. When exploiting web services, they have several ways to succeed an attack (SQL injection, Path traversal, XML Injection, DoS, etc.). Thus, clustering similar attacks is useful to characterize the different categories of intrusion. For this process, we used the spectral clustering algorithm. To cluster the collected SOAP messages (requests), we apply the clustering algorithm on the first dataset DS1 of "SOAP messages content". The execution of spectral clustering algorithm includes essentially three steps: construction of the similarity matrix S, extracting the k first eigenvectors from the Laplacian matrix L, and partitioning the data.

Construction of similarity matrix

The first step in spectral clustering is to construct a similarity matrix that measures the similarity between the data points of our dataset DS1. We construct a graph where pairs of objects are connected by links weighted by similarity values. The final objective is to find a partition of the graph such that edges between different groups have a very low weight (similarity) and the edges within a group have a high weight. Since SOAP messages are viewed as a set of string, we choose the Levenshtein distance instead of the Euclidean distance to compute the similarity. Having two strings, the chosen distance is equal to the minimum number of edits needed to transform one string into the other, with the allowable edit operations being insertion, deletion, or substitution of a single character. Once we calculate this value, the resulting similarity function is a Gaussian measure S ij = exp(

-d 2 (xi,xj ) 2σ 2
), where d is a distance function (Levenshtein distance) and σ is a user specified scaling factor. At the end of this step, we obtain a similarity matrix S ∈ R n×n , where n is the size of the objects set.

Extracting the k first eigenvectors

The next step of spectral clustering is to construct the similarity graph G = (V, E) based on the similarity matrix S. V denotes the set of vertices V i representing the data point x i ; E is the set of edges connecting the pairs of vertices. In the case of our implementation, each data point x i contains the characteristic parameters of each SOAP message captured by the WS Honeypot.

Afterwards, we need to calculate the graph Laplacian matrix L and extract the k (number of clusters to construct) first eigenvectors (u 1 , ..., u k ) of L as described in Subsection 3.2. These eigenvectors allow obtaining a projection space with smaller dimensions (equal to k). We use these vectors (u 1 , ..., u k ) as a set of columns to obtain a matrix U whose rows will be classified in the next and final step.

For the choice of the number of clusters k, we refer to the idea presented by U. Luxburg [START_REF] Luxburg | A Tutorial on Spectral Clustering[END_REF], which is based on the eigengap heuristic. Here, the goal is to choose the number k in such a way that all the λ 1 , ..., λ k eigenvalues are very small, but λ k+1 is relatively large.

Data partitioning

At the final step of spectral clustering, we consider each row of the matrix U as a point in R k and we cluster it via K-means (in our case) or other algorithm. Finally, we assign the original object x i (SOAP message i) to cluster j if and only if row i of the matrix U is assigned to cluster j.

Sequence clustering

Web service attacks are not always too simple as sending a single request containing malicious parameters. Attackers are now looking for solutions to generate more complicated attacks that are performed on several steps, hence involving multiple Web service requests. For example, the denial of service attack is performed by submitting multiple requests from one or several sources in the same time. In other cases, an attacker must initiate other attacks in order to succeed his final attack. To follow and characterize the entire attack scenario, the security expert needs to monitor the interaction between the attacker and the system. For this reason, we choose in our approach to monitor the entire sessions captured by the WS Honeypot. The proposed idea consists in collecting the sequence of activities occurred during a user session and applying a clustering algorithm to form homogenous clusters. We define a session as the set of SOAP requests submitted to the WS Honeypot from one source during a period not exceeding 24 hours. Each formed cluster is designed to describe the behavior of attackers that have performed similar activities in the honeypot.

The sequence clustering algorithm is applied on the second dataset "session characteristics", noted DS2. Each instance of the dataset contains: the source IP address of the session, the sequence of activities performed during the session and the average inter-arrival time. The sequence of activities is created based on the results of spectral clustering. Knowing that each cluster formed by the spectral clustering represents an activity type, we can determine the sequence of activities in each session by checking each received request to which activity cluster is belonging. For example, suppose that during a given session we captured 5 SOAP requests (req1, req2, req3, req4 and req5). After the spectral clustering, we concluded that req1, req2 and req3 are belonging to Cluster 1 because they are very similar. On the other hand, req4 and req5 belong respectively to Cluster 2 and Cluster 3. The sequence of activities related to this session is then equal to {A1, A1, A1, A2, A3}.

The sequence clustering method used in this approach is based on Microsoft Sequence Clustering algorithm described in Subsection 3.3. In this clustering process, we collect all the sequences of activities captured from the WS Honeypot and we form homogenous clusters. Each cluster is supposed to describe the attacker's behavior for an attack type. In some clusters we can find several attacker sequences. This means that these attackers have performed similar activities in the honeypot. Each resulting cluster is represented by a Markov chain. The chain is used to describe the attacker's behavior and the transitions between the activities that s/he has carried out.

Experimental results

Experimental data

The experimental tests described in this section are performed on the data collected from the deployment of our WS Honeypot on Internet. The period of deployment has lasted five months starting from February 2012 until June 2012. The honeypot was configured to simulate a Web service for online shopping. This type of service attracts many attackers especially those seeking for confidential information like credit card numbers and user passwords.

To enrich the data upon which WS Honeypot can work and give it the opportunity to receive other types of attack, we have chosen to simulate multiple attacks and to use some tools of penetration test and vulnerabilities discovery in order to attack the WS Honeypot. In this way, the overall data collected from the honeypot were coming from different sources:

-Real traffic from the Internet -Fuzzing penetration testing tool (WSFuzzer) -Web vulnerability scanner (Acunetix) -Simulated attacks from different sources In total, we have collected an amount of data equal to 38.7 MB, which are generated by 2317 requests coming from 113 different IP sources. In Table 3, we give a brief summary of the collected dataset.

SOAP messages clustering

Most often, attackers send SOAP requests with malicious contents in order to attack a web service. The purpose of these requests is to generate harmful activities on the target service. The content and the nature of a malicious request depend on the attack type and goal. For example, the added code within a SOAP request to launch an SQL injection attack differs from that used in an XSS (Cross-site scripting) attack. To assign each SOAP request to an attack class, we employed the spectral clustering. The goal of this clustering is to categorize the activities performed by the attacker during its interaction with the WS Honeypot.

To test this technique we applied the spectral clustering over our collected dataset. In Table 4, we describe the result of this task by presenting some formed groups (clusters) and the malicious content found in these groups.

Description of the attacker's behavior

All activities performed by the users in the WS Honeypot, whatever malicious or not, are stored in our datasets. To characterize these activities, we firstly apply a spectral clustering. For example, if an attacker sent a SOAP request to the honeypot and the clustering process reveals that the request belongs to group 1 (in Table 4), we can conclude that the attacker performed the activity type 'A1', i.e. it is most likely to be an SQL injection. Afterward, we determine the list of activities for each user within the same session, and we apply a sequence clustering on the constructed dataset.

In Table 5, we present some examples from the obtained results. Among the clusters formed by the sequence clustering, we describe Cluster 5 and Cluster 12. In cluster 5, we find 6 similar sequences of 6 different attackers. There are 3 types of activity: A1, A8 and A10. The attacker number 1 has performed during the same session the following activities: A1, A1, A8, A8 and finally A10. A1 means an SQL injection; A8 and A10 refer to 2 variants of parameters tampering attack. To describe the behavior of the intruder in this cluster, we employ the Markov chain. In this chain, the states represent the activities types and the links describe the transition probabilities between these states. By analyzing the Markov Chain derived from Cluster 5, we can conclude that the attack begins with the activity A1 (which may be repeated several times) and then passes to A8 and A10 with a given transition probability. In Cluster 12, there are 2 sequences formed by the activity A4. Here, A4 designates the submission of a large SOAP request with a repetitive content. An attacker, who generates at several times this type of activity, essentially aims to conduct a denial of service attack. Each cluster can be summarized by a signature describing the attack process. For example, we present in Figure 2 the attack signature of Cluster 5.

Conclusion

In this paper, we proposed an analysis method to explore data collected from a web service honeypot. The analysis process is based on the use of a statistical technique "Principal Component Analysis" and two clustering methods: Spectral Clustering and Sequence Clustering. The described approach is divided into three main steps. Firstly, we selected the pertinent features from collected data by the use of Principal Component Analysis. Afterwards, we applied a spectral clustering to extract groups of activities sharing common characteristics. Finally, we gathered the sequence of activities for each attack session and we used the sequence clustering to form homogeneous groups describing the behavior of attackers having similar attitudes. We evaluated our approach by experimental tests applied on data collected from our Web Service Honeypot. The obtained results describe the attacker's behavior in the form of a Markov Chain representing the transition between its activities.

As a future work, we plan adding another functionality to automatically construct enriched attacks signatures to be used by Intrusion Detection and Prevention Systems (IDPS). We envisage also expanding the detection features of our Honeypot so that it can support attacks targeting web applications in general.

Fig. 1 .

 1 Fig. 1. Data analysis workflow in WS Honeypot

Table 1 .

 1 List of initial features

	No	Feature	Description
	1	Src IP	source IP address
	2	Dest IP	destination IP address
	3	Protocol	type of used protocol
	4	Port	destination port number
	5	Soap msg size	size of the SOAP message
	6	Soap header size	size of the header
	7	Soap request type	request type
	8	Soap response type	response type
	9	Encoding	used encoding type
	10	Operation	called operation name
	11	in1	input for parameter number 1
	12	in2	input for parameter number 2
	13	in3	input for parameter number 3
	14	in4	input for parameter number 4
	15	in5	input for parameter number 5
	16	in6	input for parameter number 6
	17	in7	input for parameter number 7
	18	in8	input for parameter number 8
	19	in9	input for parameter number 9
	20	in10	input for parameter number 10
	21	Time	request processing time
	22	Mem	memory occupation
	23	CPU	request CPU usage

Table 2 .

 2 Factorial axes issued from PCA

	Axis	Eigen value	Proportion (%)	Cumulative (%)
	1	2,770407	17,32 %	17,32 %
	2	2,182733	13,64 %	30,96 %
	3	1,689447	10,56 %	41,52 %
	4	1,524927	9,53 %	51,05 %
	5	1,230749	7,69 %	58,74 %
	6	1,105892	6,91 %	65,65 %
	7	0,989987	6,19 %	71,84 %
	8	0,960595	6,00 %	77,84 %
	9	0,844701	5,28 %	83,12 %
	10	0,802064	5,01 %	88,13 %
	11	0,419877	2,62 %	90,76 %
	12	0,350289	2,19 %	92,95 %
	13	0,332850	2,08 %	95,03 %
	14	0,301130	1,88 %	96,91 %
	15	0,267431	1,67 %	98,58 %
	16	0,226920	1,42 %	100,00 %
	17	0,000000	0,00 %	100,00 %
	...

Table 3 .

 3 Dataset Characteristics

	Dataset size	Number of	Number of sources Number of sessions	Protocol
		captured requests			distribution
	38.7 MB	2317	113	451	SOAP (96%)
					Other (4%)

Table 4 .

 4 Example of groups formed by the Sectral Clustering ../../../../../../../../../../../etc/passwd%00 Path Traversal ../../../../../../../../../../../../etc/passwd ../../../../../../../../../../../../etc/shadow%00 ../../../../../../../../../../../../etc/shadow \..\..\..\..\..\..\..\..\..\..\passwd ../../../../../../../../conf/server.xml

	Group number Malicious sequence	Probable attack type
		0 or 1=1
		' or 0=0 -
		" or 0=0 -
		or 0=0 -
	Group 1	' or 0=0	SQL injection
		' or 1=1-
		" or 1=1-
		' or 'x'='x
		0 or 1=1

	Group 2

	Meta-Character Injection
		'
		/'
	Group 3 ../Group 4 AAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAA......AA AAAAAAAAAAAAAAAAAAAAA	Unknown
		BBBBBBBBBBBAAAAAAAA.....AAA
		BBBBBBBBBBBBBBBBBBBBBBBBBB
		BBBBBBBBBBBBBB
	...

Table 5 .

 5 Example of clusters obtained from sequence clustering

	Cluster description	Associated Markov Chain
	1. A1,A1,A8,A8,A10
	2. A1,A1,A8,A8,A10
	3. A1,A1,A8,A10
	4. A1,A1,A8,A8,A10
	5. A1,A1,A1,A8,A10
	6. A1,A1,A8,A10
	1. A4, A4, A4, A4, A4, A4, A4,
	A4, A4, A4, A4
	2. A4, A4, A4, A4, A4, A4, A4,
	A4, A4, A4, A4, A4, A4, A4, A4,
	A4, A4