One-Class Classifiers : A Review and Analysis of Suitability in the Context of Mobile-Masquerader Detection

This is a self-archived version of an original article. This version may differ from the original in pagination and typographic details. Author(s): Title: Year: Version: Copyright: Rights: Rights url: Please cite the original version: CC BY 4.0 https://creativecommons.org/licenses/by/4.0/ One-Class Classifiers : A Review and Analysis of Suitability in the Context of MobileMasquerader Detection © Author, 2006 Published version Mazhelis, Oleksiy Mazhelis, O. (2006). One-Class Classifiers : A Review and Analysis of Suitability in the Context of Mobile-Masquerader Detection. South African Computer Journal, 6(36), 29-48. https://doi.org/10.46298/arima.1877 2006 Joint Special Issue — Advances in end-user data-mining techniques 29 One-Class Classifiers: A Review and Analysis of Suitability in the Context of Mobile-Masquerader Detection O Mazhelis Department of Computer Science and Information Systems University of Jyv¨askyl¨a P.O. Box35, FIN-40351, Jyv¨askyl¨a, Finland ABSTRACT One-class classifiers employing for training only the data from one class are justified when the data from other classes is difficult to obtain. In particular, their use is justified in mobile-masquerader detection, where user characteristics are classified as belonging to the legitimate user class or to the impostor class, and where collecting the data originated from impostors is problematic. This paper systematically reviews various one-class classification methods, and analyses their suitability in the context of mobile-masquerader detection. For each classification method, its sensitivity to the errors in the training set, computational requirements, and other characteristics are considered. After that, for each category of features used in masquerader detection, suitable classifiers are identified. KEYWORDS: One-class Classifiers, Mobile Terminal Security, Masquerader Detection 1 INTRODUCTION The problem of classification can be defined as a problem of assigning an object represented by a vector of feature values to a category of objects – class. Using a set of objects from the training set, a classifier learns to assign the category/class labels to previously unseen objects from the test set. One-class classification can be seen as a special type of two-class classification problem, where data only from one class is available for training the classifier (referred to as one-class classifier). One-class classifiers are applied when the data from other classes is extremely hard or impossible to collect. One such application is mobile-masquerader detection, which can be defined as the detection of an attempt to impersonate the legitimate user of a mobile terminal in order to obtain an unauthorized access to sensitive data or services authorized for that user. The risk of such impersonation is high, since the terminals are carried and, due to their small size, they are often lost [1, 2]. Furthermore, since smartphones and PDAs are often used to store personal and business names and addresses, to receive and view emails, to store corporate information, etc. [3], an impersonation of the user of such a terminal may result in an abuse of the critical personal or corporate information. The problem of detecting masqueraders may be approached as the classification problem where the user behavioural or environmental characteristics are classified as belonging to the legitimate user or to an Email: O Mazhelis [email protected] impostor [4]. While the data originated from the legitimate user of the device may be relatively easily collected, the data originated from the behaviour of impostors might be very difficult, if at all possible to achieve, due to privacy and coverage issues [5]. Therefore, the use of one-class classifiers is justified. This paper is aimed at the analysis of various types of one-class classifiers and the examination of their applicability to the problem of mobile-masquerader detection. The classifier’s applicability is analysed according to a simple framework taking into account both the type of the features the classifier deals with, and the characteristics of the classification method, such as robustness, computational and storage requirements, and the number of parameters to be estimated or set. The same analysis framework may, however, be adopted when considering the applicability of one-class classifiers for other application domains, where the use of one-class classifiers is justified: machine fault diagnosis, credit card fraud detection, insurance fraud detection, etc. The paper is organized as follows. In the next Section, the problem of one-class classification is formally stated, a taxonomy of one-class classification methods is presented, and the analysis framework is described. In Section 3, multiple one-class classifiers are considered according to the introduced analysis framework. Section 4 considers the behavioural and environmental features to be used in mobile-masquerader detection, and identifies one-class classifiers potentially suitable for processing these features. Finally, conclusions to the paper are provided in Section 5. 30 Reviewed Article — ARIMA/SACJ, No. 36., 2006 2 ONE-CLASS CLASSIFICATION In this Section, the classification problem is formally stated, and the process of learning classifiers’ models is discussed. The Section also proposes taxonomy of oneclass classifiers, and specifies the criteria, according to which the one-class classifiers are reviewed in this paper. 2.1 Classification problem Let an object Zbe represented by a vector x≡ (x1,...,xnf) of the values of nffeatures from the feature space X, to which we will refer to as to the classifier’s observation vector. The classification problem can be defined as a problem of assigning the object Z by to a class Ci, where Ci, i ={1,...,NC}denotes the label of class i. The training dataset DSTis the set of observation vectors along with the corresponding class labels: DST={((x1,...,xnf)j, yj)|j= 1,...,|DST|}, where yjis the class label. In turn, the test dataset of observations to be classified denoted as DSCconsists of the vectors of feature values without class labels: DSC={((x1,...,xnf)j)|j= 1,...,|DSC|}. Using a training data-set, the classifier learns the set of parameters Θ constituting the model of the classifier. After that, given an unlabeled observation vector x, the classifier produces an output u(x,Θ). Possible values of the output can be u(x,Θ) ∈ {C1,...,CNC}, i.e. the classifier can assign to the object the label of one of NCclasses. Alternatively, for each class Ci, the classifier may implement a real-valued discriminant function uCi(x,Θ) [6], such that the greater values of the function correspond to the higher probability of class membership P(Z∈Ci|x) = P(Ci|x). In this case, the class with the highest value of discriminant function is selected: γ(x,Θ) = agrmax i=1,...,NC uCi(x,Θ),(1) where γis a mapping function. If the classifier outputs approximated probabilities P(Ci|x), this function implements Bayes decision rule, assigning the object to the class with the highest posterior probability. This rule is known to provide the optimal classification accuracy when different classification errors have equal costs [7]. For two-class classification problem, a single discriminant function in a form u(x,Θ) = P(C1|x)−P(C2|x) (2) is sufficient to implement the classification as [6]: γ(x,Θ) = (C1,if u(x,Θ) ≥0, C2,if u(x,Θ) <0.(3) While in the expressions above the discriminant was calculated as a function of posterior probabilities, some classification methods calculate the value of discriminant without explicit estimation of these posterior probabilities. The probability density function (PDF) p(Ci|x) or the parameters Θ of discriminant functions are estimated empirically using training set, e.g. by minimising an error function reflecting the misclassification error over the training set. It is assumed that the values of parameters minimising the error function over the training dataset, will also minimise the misclassification error over the complete set of allowed feature values. This ability of a classifier to generalise beyond the training dataset is referred to as generalisability. In one-class classification, the training dataset contains only the observation vectors belonging to a class C1, while the testing dataset includes the observation vectors from both classes C1and C2. Two types of classification errors can be encountered by one-class classifiers. The type I error EIoccurs if the object of the class C1is recognised as not belonging to this class. The type II error EII is encountered when the object from the class C2is considered as belonging to the class C1. The type I errors are also referred to as false negatives (in security they are also known as false rejection errors), and the type II errors are referred to as false positives (in security they are also known as false acceptance errors). Note, that only type I error can be estimated using training data-set. In the context of one-class classification, the parameters of PDF or the parameters of discriminant function can be evaluated only for the class C1. In order to make the classification possible, an assumption about the distribution of the data in the second class (C2) can be made; e.g., uniform distribution of p(x|C2) may be assumed [8, 9]. After that, the calculation of posterior probabilities p(Ci|x) is possible, and the classification is performed using the discriminant function (2). However, in practise, the value of PDF or discriminant function is often compared against a threshold t: γ(x,Θ) = (C1,if u(x,Θ) ≥t, C2,if u(x,Θ) < t. (4) The value of tis usually selected afterwards, when the parameters of PDF or discriminant function are estimated; it is selected such that the value of the type I error would be limited by a predefined level. Some methods, however, require the value of tto be specified in advance, and the selection of values of other parameters depends on this threshold. An example of such method is support vector data description [10]. 2.2 Learning of classifiers Before a classifier can be used to assign labels to objects, it should be trained, i.e. the parameters of the classifier’s model should be determined. This is done during learning phase (also called as training phase), using training data-set. During this phase, either the probability density functions P(Ci|x) should be estimated, or the parameters Θ of discriminant functions are to be determined. Joint Special Issue — Advances in end-user data-mining techniques 31 2.2.1 Probability density estimation When the probability density function should be estimated, parametric or nonparametric density estimation methods can be employed. Parametric methods assume that the data are generated according to a distribution of a specific form whose parameters are to be estimated using training dataset. The task of estimating the distribution parameters is often approached as the task of maximising a likelihood function. For example, if the assumed distribution is Gaussian, i.e. Θ = {µ,Σ}, the parameters of the distribution can be estimated through maximising the likelihood in the form L(µ,Σ) = Y i∈DST p(xi|µ,Σ).(5) For the above example of Gaussian distribution, the analytical solution maximising the likelihood is known. Often, however, the task of likelihood maximisation is analytically intractable. In such cases, the parameter estimation can sometimes be performed using Expectation-Maximisation (EM) algorithm [11]. This algorithm iteratively applies two procedures referred to as expectation and maximisation steps, respectively. During the expectation step (E-step), the distribution of hidden parameters z(e.g. the variable indicating which component of a mixture of Gaussians generated the observation vector) is approximated, and the expectation Eof the log-likelihood of parameters Θ with respect to these hidden parameters is calculated. During the maximisation step (M-step), the parameters Θ are reassigned the values maximising the expectation of log-likelihood. These Eand M-steps are iteratively repeated until convergence. Non-parametric density estimation methods, contrary to the parametric ones, do not make specific assumptions about the underlying distribution. Rather, the form of the distribution is induced directly from the data (training dataset). Examples of these methods are Parzen density estimator, K-nearest neighbours algorithm, histograms, etc. These methods will be described in Section 3. 2.2.2 Estimation of the parameters of discriminant function Parameters Θ of a discriminant function may be estimated by minimizing an error function of these parameters (such as sum-of-squares error function or crossentropy error function) over the data from the training set. The error function value is evaluated using empirical data, and it reflects the degree of classifier’s misclassification error over the training set. For example, the cross-entropy error function is calculated as [6]: ECE =−X xi∈DST 2 X k=1 yik ln uk(xi,Θ).(6) where yik = 1, if xi∈Ck, and yik = 0, otherwise. However, in order to apply these error functions, the observation vectors for class C2need to be synthesized, e.g. generated according to a specific distribution assumed for class C2[12]. As a result, these functions are rarely used in practice for one-class classification. 2.2.3 Generalisability The generalisability of a classifier is its ability to generalise beyond the training dataset. The problem of generalisability can be better understood by considering the decomposition of the misclassification error into bias and variance terms. Rather than estimating the error for a particular training dataset DST, this decomposition is defined for the expectation of the error over all possible training datasets. For the sum-of-square error function, and for regression rather than classification problem, this expectation can be rewritten as [6]: EDST[(u(xi,Θ) −yi)2] = ={EDST[u(xi,Θ)] −yi}2+ +EDST[{u(xi,Θ)] −EDST[u(xi,Θ)}2] = (bias)2+ variance. (7) where y(x) is the regression function being approximated. The bias component of the above equation reflects the error due to low model flexibility that is insufficient to accurately approximate the function being learnt. For example, a significant bias is expected if a linear model is used to approximate a quadratic function. In turn, the variance component reflects the variability of the learnt model across different training sets. Thus, it reflects how sensitive the classifier’s model is to the choice of training set. A high variance value indicates that the model is too flexible, and that it learns, in addition to the true function y(x), the characteristics of the training set DST. In this case, the model is said to overfit the data, indicating that the model complexity is higher than the complexity of the function being approximated. For example, the approximation of a linear function by a quadratic model is likely to result in overfitting. In order to generalise well beyond the training data-set, the classifier’s model should have a low value of the variance. This can be accomplished e.g. by incorporating an additional regularisation term, punishing the models with high complexity, in the definition of an error function being minimised. Alternatively, several classifiers can be learnt, and by combining their individual classifications the variance component of the error may be reduced. Many one-class classification methods are based on the estimation of a boundary around the training data. In order to avoid overfitting, boundaries with a lesser degree of flexibility are to be applied. For example, as shown in [13], the ellipsoid K-means is preferred to the convex polytope, which, though more flexible and hence able to produce a boundary with a tighter fit to the training data, yet does not provide 32 Reviewed Article — ARIMA/SACJ, No. 36., 2006 a good generality. Conversely, the ellipsoid K-means is able to achieve a tradeoff between the tightness of the fit and the generality, and consequently provides better classification accuracy on a test dataset. It was also found that methods requiring many parameters to be tuned are more susceptible to overfitting; therefore, the methods with a small number of parameters or parameter-free methods should be used in order to alleviate the generalisability problem [14]. 2.3 Taxonomy of one-class classifiers For the purposes of the paper, a taxonomy of one-class classification methods is proposed in this subsection. The methods are divided into categories according to the following criteria: 1. The internal model used by a classifier. Following the work of [9], three types of one-class classifiers can be distinguished, including density methods, boundary methods, and reconstruction methods: •Density methods, as the name implies, are based on the estimation of the probability density function (PDF) of the feature values p(x|C1) in the complete feature space. In the absence of knowledge about the second class, the PDF for that class may be assumed uniform, i.e. p(x|C2) = const. A specific form of the distribution of feature values is often unknown; it is approximated, e.g., by a mixture of Gaussians. The data in training set are assumed to be representative of the true data distribution. In classification, the PDF value corresponding to the current observation vector is compared against a threshold t. •In reconstruction methods, contrary to the density methods, assumptions about underlying data structure are made. Namely, a model of datageneration process is assumed, and the parameters of this model are estimated during the learning phase. For classification, the reconstruction error Ereconstr reflecting the fit of current observation vector to the model is evaluated. The closer is the fit, the more likely the data were generated by this model. The discriminant function can then be implemented as 1/Ereconstr. •Boundary methods do not estimate the density of the data, but rather estimate the boundary thereof. These methods calculate the distance between the observation vector being classified and the boundary built around the observation vectors in the training data-set. The distance calculation takes into account both i) the distance between the observation vectors being analysed and the observation vectors in the training data-set, and ii) the distances between the observation vectors in the training data-set. Neither the density of the data nor the data generation process is specifically modelled. Contrary to density and reconstruction methods traditionally used for multi-class classification, boundary methods are specifically targeted at the one-class classification. 2. The type of data. According to the type of features, the classifiers can be dichotomised into those based on symbolic or numeric features [15]: •The classifiers dealing with symbolic data (also known as qualitative, discrete, or categorical) can be exemplified by the classifier based on Markov models and the classifier based on association rules. These classifiers can be applied to analyse the numeric data after these data have been transformed into a number of categories (e.g. using histograms or clustering). •An example of the classification method dealing with numeric (also called as real-valued, continuous, or quantitative) data is K-nearest neighbour classifier. This classifier employs the measure of distance between observation vectors, and it may be difficult to define the distance measure for symbolic data. Often, however, symbolic features can be transformed into numerical by introducing boolean indicator variables, and consequently can be analysed by the classification method designed for numeric data. 3. The ability of classifiers to take into account temporal relations among features. Based on the importance of the temporal relations between features of the observation vectors, the classifiers can be divided into the ones ignoring temporal regularities and the ones whose internal model takes such regularities into account: •An example of the method ignoring temporal relations is K-nearest neighbour classifier, for which the temporal order of the features is not important. The classifiers dealing with non-temporal data can sometimes be adapted to take into account temporal regularities. For example, a multi-layer perceptron (MLP) neural network can be used to model sequential patters by adding a feedback link between an output(s) and input(s) of the network. •The methods based on temporal relations model how the values of features change along the time axis. An example of the methods capable of modelling temporal relations is the classifier based on Markov models. This classifier estimates the probabilities of the new states of the system on the basis of several previous states; thus, the temporal order of the system states is important for this classifier. The produced taxonomy and selected one-class classifiers located in it are presented in Figure 1. The division of methods according to the internal model of classifiers is aimed at making the analysis process more systematic. The methods based on different models produce classifications using different approaches: the density methods estimate the density of a new observation vector; the boundary methods calculate the distance from the vector to a learnt boundary; in turn, a reconstruction error is calculated in reconstruction methods. That is why it was decided to group the methods being considered in Section 3, according to their internal model. Joint Special Issue — Advances in end-user data-mining techniques 33 Figure 1: Taxonomy of one-class classifiers From a practical perspective, the internal models of classifiers may be not the most important characteristic of a classification method. For example, in deciding upon the classifier to be employed in masquerader detection, the need to address temporal aspects in the data may be more important than the internal classifier’s model. The type of features (numeric vs. symbolic) also may appear more important than the internal structure. Therefore, these characteristics are included into the taxonomy. In the bottom part of the figure, the one-class classification methods are exemplified. These methods will be considered in Section 3 according to the framework of analysis presented in next subsection. The selection of the methods for this review was aimed at covering the well-known one-class classification methods, but the selection also took into account the availability of published examples of their use in the security domain. Meanwhile, in addition to the methods included in the review, a number of other one-class classification methods exist [16, 17]. The proposed taxonomy divides the space of classification methods into 3×2×2 = 12 categories. However, as could be seen from the figure, several brunches in the taxonomy are missing, since no classification methods belonging to these categories are included in the review. Some of the missing branches would be non-empty if the modifications of the classification methods present in other branches would have been considered. For example, a modification of the hidden Markov model is able to analyse the numeric observation vectors [18] and should be located in the “density”–“numeric data”–“based on temporal relations” branch. For several categories, no classification methods that belong to these categories have been identified. For example, no boundary methods dealing with symbolic data or taking into account temporal relations among features have been found in literature. 2.4 Framework for analysis In the following section, several one-class classification methods will be reviewed. For each method, the internal model of the classifier, along with the employed learning and classification processes, will be summarised. After that, the characteristics of these methods will be analysed according to the following criteria (some of them can be found in [9] and [15]): •Robustness. In learning the classifiers, the assumption is usually made that the training dataset is a representative of the data distribution for the class C1. However, it may further be assumed that the data in the training dataset are contaminated by a noise error component (for numeric data) or contain mislabelling errors (for symbolic data). The class labels in the training dataset are symbolic; therefore, the noise corresponds to the feature values only. The mislabelling errors may occur in the values of features as well as in the values of class labels. (The latter case corresponds to the situations when the training dataset is contaminated with the data originated from class C2; we will refer to such observation vectors with invalid class label as to outliers.) The ability of a classifier to learn the true characteristics of the data in the presence of noise/errors, i.e. the method’s robustness, is important for one-class classifiers, especially when the behavioural and environmental characteristics of users are being classified. Due to a great variability exhibited in user behaviour and environment, the values of the corresponding features are not likely to be error-free. •Computational and storage requirements. While both the computational abilities and available storage capacity of computing facilities is increasing constantly, they are still the limiting factors prohibiting the use of some of the methods in certain applications. This is especially relevant for the mobile devices that are usually inferior to the desktop computers in computational power, battery power, and the size of available memory. •Number of parameters to be estimated or set. The number of free parameters that should be either learnt using training set or directly set (e.g. by a user) varies among classification methods. In the context of personal mobile devices, where no security administrator is usually present, the number of parameters set by a human being 34 Reviewed Article — ARIMA/SACJ, No. 36., 2006 should be minimised. •Applications in the domain of security. Reported applications of various one-class classification methods in the domains close to mobilemasquerader detection (intrusion detection [19] or fraud detection [20]) may serve as empirical evidences of applicability of these methods to the masquerader detection problem. Such evidences, however, should be considered with care, since these methods were applied mainly on desktop computers or servers rather than on mobile devices, and because the context, in which the classifiers were applied (e.g. the analysis of network packets or the analysis of system calls) may be different from the context of analysing the behaviour or environment of a mobile-device user. 3 METHODS OF ONE-CLASS CLASSIFICATION In the following subsections, the density, the reconstruction, and the boundary methods of one-class classification will be considered separately. 3.1 Density methods The density methods are based on the estimation of the probability density function. Several representative density methods including histograms, Markov models, Gaussian and mixture of Gaussians models, Parzen density estimation, and K-nearest-neighbours estimation used in various application areas are considered below. 3.1.1 Histograms The histogram analysis is one of the most intuitive and widely used methods of density estimation [17]. It can be employed for the analysis of both symbolic and numeric data. In the latter case, the histogram is produced by dividing the feature space into a number of bins (“buckets”), and calculating the number of observation vectors that fall in each bin. In fact, the data in different groups are treated as having distinct symbolic values. The probability density is then estimated for each bin as the fraction of the observation vectors in this bin [6]. The histograms are relatively robust to the noise in training data as well as to mislabelling errors. However, the accuracy of estimation depends on the way the feature space is divided into bins. Too large bins result in over-smoothed density, while too small bins produce very spiky density estimation [6]. Furthermore, due to the curse of dimensionality [7], a large size of training dataset may be needed in order to estimate the density accurately. Different techniques of partitioning data into buckets have been proposed in order to improve the estimation accuracy. Examples of these techniques are equi-width, equi-depth, and V-optimal partitioning [21]. In V-optimal partitioning, for example, a weighted variance of the values in each bucket is minimised. [22] proposed so-called self-tuning histogram whose bins can be adjusted incrementally as new observations become available. The parameters that need to be provided or learnt depend on the type of the histogram. Usually, at least one parameter (e.g. the number of bins Nbins) needs to be supplied, and the number of parameters to be estimated is usually equal or greater than the number of bins. The learning of histogram is computationally inexpensive. The histograms can be constructed incrementally, discarding the observation vectors that have been considered. In this case, memory space is not needed for storing all the elements of the training set. Similarly, little computational efforts are needed for estimating density using a constructed histogram, and the histogram itself requires little storage space. In anomaly intrusion detection, the histograms were extensively used in the design of the statistical component of IDES and NIDES [23, 24, 25, 26, 27]. Yamanishi et al. [28] also employed histograms to represent probability density for categorical variables. 3.1.2 Markov models A Markov chain is a model of discrete-time stochastic process, i.e. the changes of an observation variable are assumed to occur at discrete points in time. The observation variable can take a finite number of values; these values designate the state of the modelled system at time τ:xτ∈ {s1,...,sNs}.1Thus, this model may be suitable for modelling temporal regularities present in symbolic features. A stationary Markov chain [29] assumes that the probability distribution at time τdepends on the state at time τ−1, and does not depend on the previous states τ−2,...,1. It is further assumed that the probability distribution does not change with time. Assuming a set S={s1,...,sNs}of possible states, the Markov chain model can be represented by a transition probability matrix A={aij}, i, j = 1,...,sNs, where aij =P(sτ+1 j|sτ j), and by a vector of initial probability distributions Π={πi}, i = 1,...,sNs, where πi=P(s1 i) is the probability that initial state of the observation variable is si. The initial and transition probabilities can be estimated empirically as a fraction of corresponding states or transitions between states. Given the model, the probability of a sequence of the observation variable states s1,...,sτat times 1,...,τ is estimated as pMC(s1,...,sτ) = πx1 τ Y k=2 ak−1,k.(8) When the states of the system cannot be observed directly, a hidden Markov model (HMM) [18] is used 1For simplicity, a single observation variable xis used in this subsection instead of observation vector x. The vector x composed of nffeatures, where each feature has Nspossible values, can be transformed to a single variable having nf×Ns possible values. Joint Special Issue — Advances in end-user data-mining techniques 35 instead of the above Markov chain. In HMM, the system being in state sτat time τ, is assumed to emit some observation xτwhose possible values belong to the set of visible symbols v={v1,...,vNv}. These symbols are assumed to be emitted according to probability distribution P(vτ k|sτ j) = bjk ∈B. The transition matrix for HMM is defined as A={aij}, i, j = 1,...,sNs, where aij =P(sτ+1 j|sτ j). The parameters Π,A, and Bcan be found using e.g. the Baum-Welch algorithm, implementing EM procedure [18]. Given the parameters of the model, the probability of a sequence of observations P(v1,...,vτ) is determined using forward algorithm [7, 18]. The Markov models are relatively insensitive to a small number of mislabelling errors in the training dataset, since these errors may have little influence on the estimation of the parameters of the models. Such insensitivity enabled the successful use of the HMM for addressing the problem of speech recognition [18, 30], where a training data may be contaminated with noise. The number of parameters being estimated is determined by the number of states Nsand by the number of visible symbols (for HMM), and is equal to nparamMC =N2 sfor first-order Markov chain, and is equal to nparamHMM =N2 s+Ns(Nv−1) for the HMM. The user should specify the number of hidden states. For the conventional Markov chain model, the imposed computational overhead is negligible for both learning and execution. The needed storage space is determined by the number of states and hence is relatively small. Contrary, the classification with the HMM and especially the estimation of the HMM’s parameters is computationally expensive as indicated e.g. by the results of [31] and [32]. This is due to the fact that one iteration of the training procedure requires O(|DST|N2 s) steps, and a number of iterations are needed before the Baum-Welch algorithm converges. The space requirements during training are also high since the intermediate values need to be stored, and they require |DST|(2Ns+1) floating point values [31]. In the security domain, Ye [33] investigated the application of conventional Markov chain model to the problem of detecting anomalies in the audit logs produced by Basic Security Module (BSM) of Solaris operation system. A number of studies in the intrusion detection employed the HMMs as one-class classifiers, e.g. [34, 31, 35, 32]. 3.1.3 Gaussian and mixture of Gaussians These methods assume that the data is distributed according to the normal (Gaussian) distribution, or according to a mixture of several Gaussian distributions [6]. The Gaussian distribution is defined as: pG(x,µ,Σ) = 1 (2π)d/2|Σ|1/2×(9) ×exp −1 2(x−µ)TΣ−1(x−µ), where µis the mean vector and Σis the covariance matrix. In turn, the mixture of Gaussians model extends the above Gaussian models and represents a linear combination of nMG Gaussian distributions as: pMG(x) = 1 nMG nMG X i=1 pG(x,µi,Σi)P(i),(10) where the mixing parameter P(i) reflects the prior probability that an observation vector is generated from i-th component of the mixture. The number of parameters for Gaussian model is equal nparamG=nf+1 2nf(nf−1) and for mixture of Gaussians is nparamMG =nMG(nparamG+ 1). The parameters of the Gaussian model can be found by maximising the likelihood L(µ,Σ) over the training dataset. This likelihood is maximised when the parameter values are evaluated according to Equations (11) and (12): ˆ µ=1 |DST|X xi∈DST xi(11) ˆ Σ=1 |DST|X xi∈DST (xi−ˆ µ)(xi−ˆ µ)T(12) The learning process in this case is computationally inexpensive. For the mixture of Gaussians, the analytical expression for the parameter values maximising the likelihood is not known. However, these parameters can be found efficiently by employing the EM algorithm. The learning process using EM algorithm is more computationally demanding, as a number of interactions should be done before the algorithm converges. The classification process is relatively simple; the only computationally expensive operation is the inversion of the covariance matrix. The methods based on Gaussian models are sensitive to the noise present in the training data, as this noise may introduce a significant bias to the estimated covariance matrix [9]. The accuracy, with which the density is estimated, and, hence, the accuracy of classification depends on whether the data follows the assumed distribution [17]. Besides, these methods are relatively sensitive to the outliers [17]. Lauer [36] developed a method that tolerates a small number of errors in the training set; however, this method requires the proportion of the outliers in the training set to be known in advance. The storage space required for classification is negligible as only the parameters of the models need to be stored. The storage requirements for learning the models, however, are much higher since all the data from the training dataset are used. In order to minimise the space requirements, the Gaussian model parameters can be evaluated incrementally. In the case of incremental learning, only few observation vectors are needed at each learning step in order to update the parameter values. Modifications of the EM algorithm supporting incremental learning [37] can be used to reduce the storage requirements of the learning of the Gaussian model. 36 Reviewed Article — ARIMA/SACJ, No. 36., 2006 The bias and the variance of the Gaussian and mixture of Gaussians models depend on whether the data follows the assumed distributions. In general, the mixture of Gaussians model is more flexible, and therefore, is expected to have a lower bias error but a higher variance error value. In the security domain, the Gaussian model was used to detect anomalies in Solaris OS audit events [38]. As a distance function (inverse to the discriminant function), the Hotelling T2statistics was employed representing a statistical distance from observation vector xto the mean of the multivariate Gaussian distribution. The use of a mixture of Gaussians model was reported successful in detecting anomalies in the parameters of user requests to a CORBA-server [39]. Mixture of Gaussians was also employed by [28] in order to model the distribution of continuous variables for anomaly detection. 3.1.4 Parzen density estimation Parzen density estimation does not make any specific assumptions about the shape of the data distribution. The density is estimated directly from the training data and is a function of the number of observation vectors situated in a region of a specified volume [7]: p(x) = 1 N N X i=1 1 Vϕ(x−xi h),(13) where N=|DST|is the size of the training data-set, and V=hnfis the volume of the region in a form of the nf-dimensional hypercube with the length of an edge h. The value of hplays the role of a smoothing parameter and it should be provided in advance. The kernel function ϕ(v) is a window function that should satisfy ϕ(v)>0 and Rϕ(v)dv= 1. The Parzen window is defined as: ϕ(v) = (1,if |vj|<1/2, j = 1,...,nf, 0,otherwise.(14) Another commonly used kernel (window) function is a multivariate Gaussian, for which: p(x) = 1 N N X i=1 1 (2πh2)nf/2exp(−||x−xi||2 2h2).(15) Advantage of the method is its ability to approximate arbitrary distribution, whose parametric form is unknown. The learning phase is trivial: since no parameters need to be estimated, the learning phase consists in storing the values of the observation vectors. The method however requires the smoothing hparameter to be specified carefully. Too large values of the parameter result in an over-smoothed estimated density. On the other hand, when too small hvalue is provided, the estimated density contains noise, i.e. it reflects the peculiarities of the training dataset rather than the characteristics of the distribution being estimated [6]. Another drawback of the method is the need to store all the observation vectors. This makes the estimation of probability slower. Besides, if the number of observation vectors to be stored is large, the storage space consumed may become prohibitive. This problem can be partly solved by reducing the number of kernel functions and adapting their widths according to the data [6]. The Parzen density estimation is relatively robust to the outliers in training data since they influence only density estimation in the regions of close proximity [9]. The sensitivity to the noise in data depends on how well the smoothing parameter his selected – as mentioned above, too low values of hmake the estimation noise-sensitive. In the domain of anomaly intrusion detection, this method of density estimation was employed by [40] in order to estimate the PDF of features extracted from TCP/IP packets. As reported by the authors, the detection accuracy obtained in the experiments using KDD Cup 1999 dataset was comparable to the accuracy of best competitors. 3.1.5 K-nearest-neighbours K-nearest-neighbours method is similar to the kernelbased estimation discussed above. The probability density is also calculated based on the number of observation vectors in a region of a certain volume. However, in K-nearest-neighbours, the number of observations Kis fixed in advance, and the volume of the area is allowed to grow so that Knearest observation vectors would be included in it [7]. (Contrary, the kernel-based estimation assumes the constant volume of the regions and lets the number of observation vectors vary.) Taking the number Kas an input smoothing parameter, the method estimates the density as: p(x) = K N VK ,(16) where VKis the volume of the smallest area (hypersphere) with the centre in xsurrounding Kobservation vectors nearest to x. The advantage of K-nearest-neighbours, similarly to the kernel-based estimation, is its ability to estimate arbitrary distributions. Furthermore, by using varying volume size, K-nearest-neighbours overcomes the shortcoming of the kernel-based estimation, which tends to over-smooth the estimate in the areas of high density, and tends to produce too noisy estimate in the areas of low density [6]. The drawback of this method is the need to keep the observation vectors, in the same way as in the kernel-based density estimation. Furthermore, the produced estimate is not true probability density as its integral over the xspace diverges [6]. This limitation is however compensated by the ability to adjust the area volume to the density of the data. No parameters need to be learnt by this method. The number of neighbours K, however, needs to be provided, and too great or too low Kvalues result Joint Special Issue — Advances in end-user data-mining techniques 43 Table 2: Tentative characteristics and features to be employed in mobile-masquerader detection, according to [4] Characteristic Feature Type Temporal order Device’s facilities usage Temporal interval between two consecutive evocations of a program or service of a same type. Real No Device’s facilities usage Type of program or service evoked Symbolic No Sequences of actions followed Sequences of nactions Symbolic Yes Temporal lengths of actions Temporal lengths of actions Real No Temporal intervals between actions in a sequence Temporal intervals between subsequent actions Real No Use of shortcuts vs. use of menu For each menu command with shortcut, the chosen option Symbolic No People contacted with, conditioned on type of communication, time, etc. Phone number, e-mail address, or other address information of the contacted people Symbolic No Routes taken Sequence of cells traversed between two consecutive prolonged stops Symbolic Yes Speed of move conditioned on route and time Speed of move conditioned on route and time Real No Places visited, conditioned on time of day, day of week, etc. Locations where prolonged stops were made Symbolic No Length of work day Time that the terminal is in the place affiliated with the user’s workplace(s) Real No Changes in behaviour and environment Changes in behavioural and environmental characteristics Real Yes Time of reading a unit of textual information Time during which a document is open for reading Real No Time between an incoming event and response Temporal interval between an incoming message (e.g. e-mail) is read and the response is written Real No Words or phrases used more often Frequency of different words used in handwriting (with stylus) or typing Symbolic No Accuracy in typing, in menu item selection, etc. The ratio of errors to the overall number of actions, i.e. the frequency of mistyped keystrokes, errors in menu item selection, etc. Real No Time devoted to communication Time during a day spent for communication (using terminal) including different types of communication (calls, e-mails, etc.) Real No Time, when the user is online Time, during which the communication facilities of the terminal are not deliberately restricted Real No Statistical characteristics of voice Cepstrum coefficients of the signal power Real Yes Temporal characteristics of keystrokes Key duration time, inter-key latency time Real No Pressure, direction, acceleration, and length of strokes when stylus is used Pressure, direction, acceleration, and length of strokes Real Yes Set of installed software, current screen resolution, volume level Changes of device configuration Symbolic No According to Figure 1, these features may be analysed with conventional or hidden Markov models. Since for both features, the states (the user actions and the traversed cells) are directly observable, the use of conventional Markov model is justified. Above, various features to be used in masquerader detection were mapped to the one-class classification methods reviewed in this paper. For the first category of features, several potentially suitable classifiers were identified while for other categories only one classifier was found. Since the review of classifiers provided in this paper, is not exhaustive, there may be also other one-class classifiers suitable for processing these features. In the next subsection, for three of four categories above, the designs of classifiers to process features in these categories are exemplified. 4.2 Building classifiers for mobile-masquerader detection Recently, a dataset describing the behaviour and environment of several mobile users was collected at the University of Helsinki. The dataset was gathered in the course of two field studies aimed at testing social awareness service named ContextContacts [75]. Two groups of respectively four and five users living in the greater Helsinki area participated in the studies for approximately three months, and their behaviour and environment were monitored using the ContextPhone software platform [76] running in the background on Nokia Series 60 smart-phones. The data collected with this software reflects changes of GSM Cell IDs wherein the terminal is registered, the use of applications, active profile, the use of charger, idle and active time, Bluetooth environment, and communication events (SMS and calls). An anonymized version of this dataset can be found at http://www.cs.helsinki.fi/group/context/data/. In the above dataset, some of the features proposed in Table 2 are available; these include: •Type of program or service evoked. Active applications evoked by the user are registered in the dataset. •Sequence of cells traversed. The dataset records the identifiers of the cells (Cell IDs) wherein the mobile terminal is registered. •Speed of move. Though the speed of movements is not available in the dataset, the timestamps of the Cell ID records can be used to estimate the time the terminal spends in a cell, which, in turn, can be used to roughly estimate the terminal’s speed in terms of “cell per second”. 44 Reviewed Article — ARIMA/SACJ, No. 36., 2006 •Locations where prolonged stops were made. The information about the Cell IDs and the time spent in cells can be used to identify those locations (in terms of Cell IDs) where the terminal stays for a relatively long period of time. •Temporal interval between two consecutive evocations of a program or service of a same type. In the dataset, the evocations of two services (calls and SMS) are recorded and time-stamped; using this information, the intervals between evocations of these services can be evaluated. •Temporal lengths of actions. In the dataset, the durations of calls are recorded. •Address information of the contacted people. Phone numbers contacted via calls or SMS are available in the dataset. Besides, the identifiers (MAC-addresses) of neighbouring Bluetoothdevices are logged. These features belong to three categories introduced above: numeric features, temporal relations ignored (temporal lengths of actions, temporal interval between two consecutive evocations of a program or service of a same type, speed of move); symbolic features, temporal relations ignored (type of program or service evoked, locations where prolonged stops were made, address information of the people contacted); and symbolic features, temporal relations are important (sequence of cells traversed). In the remainder of this Section, for each of these three categories, a design of a classifier to process the features belonging to this category is described; further details of these classifier can be found in [77]. For all classifiers, their observation vectors are initialised with feature values by using a sliding window [τ1, τ2] of the length lτ=τ2−τ1(determining the time interval, within which the feature values are collected) and the increment for the window δτ. Numeric features, temporal relations ignored. For the features in the first category, several classifiers were identified in the above analysis as potentially suitable; among them, K-nearest neighbours, Parzen estimator, K-means, and K-centres were preferred for the terminals with restricted computational capabilities. The K-means classifier requires a careful selection of the parameter K, which may be problematic for a mobile-terminal user. The K-centres is sensitive to the noise and outliers in the training dataset. In turn, the Parzen estimator tends to produce oversmoothed or too noisy density estimation. Therefore, the K-nearest neighbours classifier is chosen as the classifier for the features in this category. The design of this classifier is described below for the example of the “temporal lengths of actions” feature. The classifier analyses the mean call duration time τdur within the window [τ1, τ2]. The value of τdur is calculated as τdur =1 ndPi j=i−ndur+1 τdur j, where τdur i is the last call duration registered within the window, and ndur is the average number of calls finished within a window. Using the accumulated empirical distribution function (EDF) of the τdur values, the probability density p(τdur) of the current mean inter-arrival time is evaluated using k-nearest-neighbours method. Given the current inter-arrival time values, the classifier outputs the classification ui=p(τdur). Symbolic features, temporal relations ignored. For the features in the second category, histograms were deemed appropriate. Below, an application of this classifier to one of the features in this category (type of program or service evoked) is described. The classifier assigned to this feature estimates the probability of an application jbeing evoked out of m applications as ˆ P(appj|U) = (aappj+1)/(Pmaappm+ 1), where aappjis the number of times the user evokes the application. Assuming the independence of consequent application evocations, the probability of application evocations within a time window [τ1, τ2] is approximated as ˆ P(appi−napp +1,...,appi|U) = Qi j=i−napp +1 ˆ P(appj|U) , where appiis the last application evoked within the time window, and napp is the average number of applications evoked within the window. Given the current active applications to be classified, the classifier outputs the classification ui=ˆ P(appi−napp+1,...,appi|U). Symbolic features, temporal relations are important. The conventional Markov model was hypothesized to be suitable for the features in this category. Below, the design of the classifier based on this model is specified for the “sequence of cells traversed” feature. The model of the assigned classifier includes a matrix, where each element acellicelljis a counter that stores the number of times the terminal’s Cell ID changed from cell ito cell j. The matrix values are used in approximating the probability ˆ P(cellj|celli, U) of a handover: ˆ P(cellj|celli, U) = acellicellj+ 1 Pmacellicellm+nct i ,(39) where cellmare the cells to which traversals from celliwere registered, and nct iis the number of such cells. Given the parameters lτand δτof sliding window, the average number of handovers nho within a window is estimated. Assuming the independence of consequent handovers, the probability of a sequence of cell changes within a time window [τ1, τ2] is approximated as ˆ P(celli−nho ,...,celli|U) = Qi−1 j=i−nho ˆ P(cellj+1|cellj, U), where celliis the last cell registered within the time window. In the classification phase, given the current route to be classified, the classifier outputs the classification ui= ˆ P(celli−nho ,...,celli|U). Using the dataset described above, initial experiments with these classifiers were conducted. The holdout cross-validation [78] was used in the experiments, in order to evaluate the accuracies of classifiers. The model of each classifier was learnt using the training data-set DST, and was subsequently used to classify the instances of a test data-set DSC. Since the data Joint Special Issue — Advances in end-user data-mining techniques 45 originated from masqueraders were not available in the dataset, the other users’ data were employed as the masquerader’s data. The results of these experiments are reported in [77]; according to these results, a relatively good accuracy can be achieved with some of these classifiers, e.g. with the classifiers processing address information of contacted people. Meanwhile, the accuracy of some of the classifiers (in particular, the classifiers processing temporal intervals between consecutive evocations of a program or service of a same type) was very low, indicating that the corresponding features are poor differentiators between users. According to no-free-lunch theorem [79], no single classification method would provide superior classification accuracy independently of the context, in which the method is applied. Therefore, further empirical studies are needed in order to determine the accuracy, and hence, suitability of different methods in a given context [7]. For example, many of the above methods are sensitive to the noise and mislabelling errors in the training data, and the empirical testing can be employed to evaluate how significant is the influence of such errors for the classification problem in hand. Besides, in the context of mobile-masquerader detection, these empirical studies should determine whether a classification method fits to the constraints of the mobile terminals. For instance, the above Knearest neighbours classifier requires the observation vectors to be kept, thereby consuming the memory of a mobile terminal. However, for the available features analyzed by this classifier, the use of memory is rather conservative. For example, the data required for the classifier analyzing durations of calls consumes in compressed format from 7 to 29 kilobytes; furthermore, a significant proportion of this data is redundant and can be excluded in real-world applications. Thus, the amount of data required for the K-nearest neighbours classifier appears to be tolerable for contemporary smart-phones, making the use of this classifier in the context of mobile-masquerader detection feasible. 5 CONCLUSIONS A noticeable research during last years has been devoted to the problem of one-class classification. The peculiarity of this type of classification is the availability of the observation vectors of only one class during learning. These methods are particularly useful in the application areas, where the observation vectors belonging to other classes are difficult or impossible to obtain. One such application area is mobilemasquerader detection. A number of one-class classification methods have been proposed in literature, varying from modifications of conventional N-class classification methods to the methods designed specially for one-class classification problem. In this paper, some of these methods have been reviewed, and their suitability to the problem of mobile-masquerader detection has been analysed. Both the review of classifiers and the analysis of their suitability to a specific application domain were based on the taxonomy of one-class classification methods that was introduced in the paper. This taxonomy categorises the one-class classification methods according to the internal model, the type of the features, and the ability to take into account the temporal relations between the features. According to the internal model, the classification methods were divided into density, reconstruction, and boundary methods. This division was employed in the review, since the methods within a same category have some similarities in the learning and classification phases. Within each category, the methods were reviewed according to a developed analysis framework. Namely, for each method, the review included the summary of the learning and the classification process implemented by the classifier, its sensitivity to the noise and mislabelling errors in training data, the number of parameters to be set by the user or estimated using training data, and the resources consumed during the learning and classification phases. The categorisation of classification methods according to the type of data and according to the ability to take into account the temporal regularities was employed in order to evaluate the applicability of the methods being reviewed to the problem of mobilemasquerader detection. For this, the features that are hypothesised to be useful in masquerader detection were divided into four categories, according to the type of features (symbolic or numeric) and according to the importance of temporal ordering of measurements. Then, for each category of features, potentially suitable classifiers were identified, and the design of some of the classifiers has been described in detail. Further empirical research is, however, needed in order to compare different methods quantitatively in the context of mobile-masquerader detection. ACKNOWLEDGMENTS This work was partly supported by the COMAS Graduate School of the University of Jyv¨askyl¨a. The author would like to acknowledge the Context project for the implementation of the ContextPhone platform and making available the dataset on mobile context and communication, and would like to thank Seppo Puuronen as well as anonymous reviewers for valuable comments and suggestions. REFERENCES [1] Pointsec Mobile Technologies. “Half of All Corporate PDAs Unprotected Despite Employer Risk”. Pointsec News Letter 2, Available from http://www.pointsec.com/news/mediakit/ (read 09.02.2006), June 2004. [2] Pointsec Mobile Technologies. “Confidential Data Gets Taken for a Ride”. Pointsec News Letter 1, Available from http://www.pointsec.com/news/mediakit/ (read 09.02.2006), March 2005. 46 Reviewed Article — ARIMA/SACJ, No. 36., 2006 [3] Pointsec Mobile Technologies. “IT Professionals Turn Blind Eye to Mobile Security as Survey Reveals Sloppy Handheld Habits”. Pointsec news releases, Available from http://www.pointsec.com/news/ release.cfm?PressId=108 (read 09.02.2006), November 18 2005. [4] O. Mazhelis and S. Puuronen. “Characteristics and measures for mobile-masquerader detection”. In P. Dowland, S. Furnell, B. Thuraisingham and X. S. Wang (editors), Proc. IFIP TC-11 WG 11.1 & WG 11.5 Joint Working Conference on Security Management, Integrity, and Internal Control in Information Systems, pp. 303–318. Springer Science+Business Media, 2005. [5] T. Lane. Machine Learning Techniques for the Computer Security Domain of Anomaly Detection. Ph.D. thesis, Purdue University, W. Lafayette, IN, 2000. [6] C. M. Bishop. Neural Networks for Pattern Recognition. Oxford University Press, Oxford, 1995. [7] R. O. Duda, P. E. Hart and D. G. Stork. Pattern Classification. John Wily & Sons, Inc., New York, second edn., November 2000. ISBN 0-471-05669-3. [8] C. M. Bishop. “Novelty detection and neural network validation”. In IEE Proceedings – Vision, Image and Signal processing, Special Issue on Applications of Neural Networks, vol. 141(4), pp. 217–222. 1994. URL http://citeseer.ist.psu.edu/ bishop94novelty.html. [9] D. Tax. One-class classification. Ph.D. thesis, Delft University of Technology, 2001. [10] D. M. J. Tax and R. P. W. Duin. “Support Vector Data Description”. Machine Learning, vol. 54, pp. 45–66, 2004. [11] A. Dempster, N. Laird and D. Rubin. “Maximum likelihood from incomplete data via the EM algorithm”. Journal of the Royal Statistical Society, vol. 39, no. 1, pp. 1–38, 1977. [12] W. Fan, M. Miller, S. J. Stolfo, W. Lee and P. K. Chan. “Using Artificial Anomalies to Detect Unknown and Known Network Intrusions”. In Proceedings of the First IEEE International Conference on Data Mining. 2001. URL http://www.cc.gatech.edu/ wenke/papers/ artificial anomalies.ps. [13] G. L. Peterson, R. F. Mills, B. T. McBride and W. C. Allred. “A Comparison of Generalizability for Anomaly Detection”. In D. Margineantu, S. Bay, P. Chan and T. Lane (editors), International Workshop on Data Mining Methods for Anomaly Detectio. 2005. [14] E. Keogh, S. Lonardi and C. A. Ratanamahatana. “Towards parameter-free data mining”. In KDD ’04: Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 206–215. ACM Press, New York, NY, USA, 2004. ISBN 1-58113-888-9. doi: http://doi.acm.org/10.1145/1014052.1014077. [15] M. Hilario and A. Kalousis. “Characterizing Learning Models and Algorithms for Classification”. Deliverables 2.1a, 2.2a, CUI - University of Geneva, March 1999. [16] M. Markou and S. Singh. “Novelty detection: a review – part 1: neural network based approaches”. Signal Processing, vol. 83, pp. 2499–2521, 2003. [17] M. Markou and S. Singh. “Novelty detection: a review – part 1: statistical approaches”. Signal Processing, vol. 83, pp. 2481–2497, 2003. [18] L. Rabiner. “A tutorial on hidden Markov models and selected applications in speech recognition”. Proceedings of the IEEE, vol. 77, no. 2, pp. 257–286, Feb 1989. [19] S. Kumar. Classification and Detection of Computer Intrusions. Ph.D. thesis, Purdue University, West Lafayette, USA, 1995. [20] J. Hollmen. User Profiling and Classification for Fraud Detection in Mobile Communications Networks. PhD thesis, Helsinki University of Technology, 2000. [21] V. Poosala, P. J. Haas, Y. E. Ioannidis and E. J. Shekita. “Improved histograms for selectivity estimation of range predicates”. In J. Widom (editor), Proceedings of the 1996 ACM SIGMOD international conference on Management of data, pp. 294–305. ACM Press, New York, NY, USA, 1996. ISBN 0-89791-794-4. doi: http://doi.acm.org/10.1145/233269.233342. [22] A. Aboulnaga and S. Chaudhuri. “Self-tuning histograms: building histograms without looking at data”. In S. B. Davidson and C. Faloutsos (editors), Proceedings of the 1999 ACM SIGMOD international conference on Management of data, pp. 181–192. ACM Press, New York, NY, USA, 1999. ISBN 1-58113-084-8. doi: http://doi.acm.org/10.1145/304182.304198. [23] H. Javits and A. Valdes. “The SRI IDES Statistical Anomaly Detector”. In IEEE Symposium of Research in Computer Security and Privacy. IEEE Computer Society Press, May 1991. ISBN 0-81862-168-0. URL http://www.sdl.sri.com/papers/stats91/. [24] T. F. Lunt, A. Tamaru, F. Gilham, R. Jagannathan, C. Jalali, H. S. Javitz, A. Valdes and P. G. Neumann. “A Real-Time Intrusion Detection Expert System”. Final technical report, Computer Science Laboratory, SRI International, Menlo Park, California, February 1992. URL http://www.sdl.sri.com/projects/ nides/reports/9sri.pdf. [25] T. Lunt. “Detecting Intruders in Computer Systems”. In Conference on Auditing and Computer Technology. 1993. [26] H. S. Javits and A. Valdes. “The NIDES Statistical Component: Description and Justification”. Technical Report A010, Computer Science Laboratory, SRI International, Menlo Park, California, March 1993. URL http://www.sdl.sri.com/papers/statreport/. [27] D. Anderson, T. Frivold and A. Valdes. “Nextgeneration Intrusion Detection Expert System (NIDES): A Summary”. Technical Report SRICSL-95-07, Computer Science Laboratory, SRI International, Menlo Park, California, May 1995. [28] K. Yamanishi, J. ichi Takeuchi, G. Williams and P. Milne. “On-Line Unsupervised Outlier Detection Using Finite Mixtures with Discounting Learning Algorithms”. Data Mining and Knowledge Discovery, vol. 8, no. 3, pp. 275–300, May 2004. [29] D. L. Isaacson and R. W. Madsen. Markov chains: theory and applications. John Wiley & Sons, New York, 1976. ISBN 0-471-42862-0. Joint Special Issue — Advances in end-user data-mining techniques 47 [30] J. Campbell, J.P. “Speaker recognition: a tutorial”. Proceedings of the IEEE, vol. 85, no. 9, pp. 1437–1462, Sep 1997. [31] C. Warrender, S. Forrest and B. Pearlmutter. “Detecting intrusions using system calls: Alternative data models”. In IEEE Symposium on security and Privacy, pp. 133–145. IEEE Computer Society Press, 1999. [32] D.-Y. Yeung and Y. Ding. “Host-based intrusion detection using dynamic and static behavioral models”. Pattern Recognition, vol. 36, no. 1, pp. 229–243, 2003. [33] N. Ye. “A Markov Chain Model of Temporal Behavior for Anomaly Detection”. In Proceedings of the 2000 IEEE Workshop on Information Assurance and Security, pp. 171–174. 2000. [34] S.-B. Cho and H.-J. Park. “Efficient anomaly detection by modeling privilege flows using hidden Markov model”. Computers & Security, vol. 22, no. 1, pp. 45–55, 2003. [35] T. Lane and C. E. Brodley. “An Empirical Study of Two Approaches to Sequence Learning for Anomaly Detection”. Machine Learning, vol. 51, no. 1, pp. 73– 107, April 2003. [36] M. Lauer. “A Mixture Approach to Novelty Detection Using Training Data with Outliers”. In L. D. Raedt and P. Flach (editors), Proceedings of the 12th European Conference on Machine Learning, vol. 2167 of Lecture Notes in Computer Science, pp. 300–311. Springer-Verlag, Berlin Heidelberg, 2001. ISSN 03029743. [37] R. M. Neal and G. E. Hinton. Learning in graphical models, chap. A view of the EM algorithm that justifies incremental, sparse, and other variants, pp. 355–368. MIT Press, 1999. ISBN 0-262-60032-3. [38] N. Ye and Q. Chen. “An anomaly detection technique based on a chi-square statistic for detecting intrusions into information systems”. Quality and Reliability Engineering International, vol. 17, no. 2, pp. 105–112, 2001. [39] R. Puttini, Z. Marrakchi and L. Me. “A Bayesian Classification Model for Real-Time Intrusion Detection”. In Proc. of 22th International Workshop on Bayesian Inference and Maximum Entropy Methods in Science and Engineering (MAXENT’2002), vol. 659(1) of AIP Conference Proceedings, pp. 150–162. IOP Institute of Physics Publishing Ltd, 2003. [40] D. Yeung and C. Chow. “Parzen-window network intrusion detectors”. In Proceedings of the Sixteenth International Conference on Pattern Recognition (ICPR), vol. 4, pp. 385–388. 2002. [41] T. Hastie, R. Tibshirani and J. H. Friedman. The Elements of Statistical Learning. Springer-Verlag, 2001. ISBN 0387952845. [42] T. Kohonen. “The self-organizing map”. Proc. of the IEEE, vol. 78, no. 9, pp. 1464–1480, 1990. [43] D. Marchette. “A statistical method for profiling network traffic”. In Proceedings of the Workshop on Intrusion Detection and Network Monitoring, pp. 119– 128. USENIX Association, 1999. [44] S. Zanero and S. M. Savaresi. “Unsupervised learning techniques for an intrusion detection system”. In G. Bella and P. Ryan (editors), Proceedings of the 2004 ACM symposium on Applied computing, pp. 412–419. ACM Press, New York, NY, USA, 2004. ISBN 1-58113-812-1. doi: http://doi.acm.org/10.1145/967900.967988. [45] J. Hollmen, V. Tresp and O. Simula. “A selforganizing map algorithm for clustering probabilistic models”. In Proceedings of the Ninth International Conference on Artificial Neural Networks (ICANN’99), vol. 2 of IEE Conference Proceedings, pp. 946–951. The IEE, 1999. ISBN 0 85296 721 7. [46] M.-L. Shyu, S.-C. Chen, K. Sarinnapakorn and L. Chang. “A Novel Anomaly Detection Scheme Based on Principal Component Classifier”. In Proceedings of the IEEE Foundations and New Directions of Data Mining Workshop, in conjunction with the Third IEEE International Conference on Data Mining (ICDM’03), pp. 172–179. 2003. Http://www.cs.fiu.edu/ chens/PDF/ICDM03 WS.pdf. [47] D. De Ridder, E. Pekalska and R. Duin. “The economics of classification: error vs. complexity”. In Proceedings of the 16th IAPR International Conference on Pattern Recognition (ICPR 2002), vol. II, pp. 244–247. IAPR, IEEE Computer Society Press, Los Alamitos, CA, 2002. Http://inpc55.et.tudelft.nl/ dick/publications.html. [48] N. Japkowicz. Concept-Learning in the Absence of Counter-Examples: An Autoassociation-Based Approach to Classification. Ph.D. thesis, Technical Report DCS-TR-390, Rutgers University, October 1999. [49] G. E. Hinton. “Connectionist learning procedures”. Artif. Intell., vol. 40, no. 1-3, pp. 185–234, 1989. ISSN 0004-3702. [50] B. ling Zhang. “Internet Intrusion Detection by Autoassociative Neural Network”. In MMU International Symposium on Information and Communications Technologies 2005. 2005. URL http://m2usic.mmu.edu.my/ main/proceeding05bysession.html. [51] R. Agrawal, T. Imielinski and A. N. Swami. “Mining Association Rules between Sets of Items in Large Databases”. In P. Buneman and S. Jajodia (editors), Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, pp. 207–216. ACM Press, New York, NY, USA, May 1993. ISBN 0-89791-592-5. doi: http://doi.acm.org/10.1145/170035.170072. URL http://citeseer.ist.psu.edu/ agrawal93mining.html. [52] R. Agrawal and R. Srikant. “Fast Algorithms for Mining Association Rules”. In J. B. Bocca, M. Jarke and C. Zaniolo (editors), Proc. 20th Int. Conf. Very Large Data Bases, VLDB, pp. 487–499. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, September 1994. ISBN 1-55860-153-8. URL http://citeseer.ist.psu.edu/agrawal94fast.html. [53] M. Klemettinen, H. Mannila, P. Ronkainen, H. Toivonen and A. I. Verkamo. “Finding interesting rules from large sets of discovered association rules”. In N. R. Adam, B. K. Bhargava and Y. Yesha (editors), Third International Conference on Information and Knowledge Management (CIKM’94), pp. 401– 407. ACM Press, New York, NY, USA, 1994. ISBN 089791-674-3. URL http://citeseer.ist.psu.edu/ klemettinen94finding.html. [54] R. Bayardo Jr. and R. Agrawal. “Mining the most interesting rules”. In U. Fayyad, S. Chaudhuri and D. Madigan (editors), Proceedings of 48 Reviewed Article — ARIMA/SACJ, No. 36., 2006 the Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 145–154. ACM Press, New York, NY, USA, September 1999. ISBN 1-58113-143-7. doi: http://doi.acm.org/10.1145/312129.312219. [55] P.-N. Tan, V. Kumar and J. Srivastava. “Selecting the right interestingness measure for association patterns”. In O. R. Za¨ıane, R. Goebel, D. Hand, D. Keim and R. Ng (editors), Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 32–41. ACM Press, New York, NY, USA, 2002. ISBN 1-58113-567-X. doi: http://doi.acm.org/10.1145/775047.775053. [56] F. Angiulli, G. Ianni and L. Palopoli. “On the complexity of mining association rules”. In Ninth National Symposium on Advanced Database Systems (Sistemi Evoluti per Basi di Dati). 2001. [57] D. Barbara, J. Couto, S. Jajodia and N. Wu. “ADAM: a testbed for exploring the use of data mining in intrusion detection”. SIGMOD Rec., vol. 30, no. 4, pp. 15–24, 2001. ISSN 0163-5808. doi: http://doi.acm.org/10.1145/604264.604268. [58] W. Lee and S. Stolfo. “A framework for constructing features and models for intrusion detection systems”. ACM Transactions on Information and System Security (TISSEC), vol. 3, no. 4, pp. 227–261, 2000. ISSN 1094-9224. doi: http://doi.acm.org/10.1145/382912.382914. [59] S. Manganaris, M. Christensen, D. Zerkle and K. Hermiz. “A data mining analysis of RTID alarms”. Computer Networks, vol. 34, no. 4, pp. 571–577, October 2000. [60] X. Qin and W. Lee. “Statistical Causality Analysis of INFOSEC Alert Data”. In G. Vigna, C. Kruegel and E. Jonsson (editors), Proceedings of The 6th International Symposium on Recent Advances in Intrusion Detection (RAID 2003), vol. 2820 of Lecture Notes in Computer Science, pp. 73–93. Springer-Verlag Heidelberg, Heidelberg,Germany, 2003. ISBN 3-540-408789. doi:10.1007/b13476. [61] R. H. Shumway and D. S. Stoffer. Time series analysis and its applications. Springer texts in statistics. New York: Springer, 2000. ISBN 0-387-98950-1. [62] N. Ye, C. Borror and Y. Zhang. “EWMA techniques for computer intrusion detection through anomalous changes in event intensity”. Quality and Reliability Engineering International, vol. 18, no. 6, pp. 443–451, 2002. [63] N. Ye and Q. Chen. “Computer intrusion detection through EWMA for auto-correlated and uncorrelated data”. IEEE Transactions on Reliability, vol. 52, no. 1, pp. 73–82, 2003. [64] A. Ypma and R. Duin. “Support objects for domain approximation”. In Proceedings of Int. Conf. on Artificial Neural Networks ICANN’98. 1998. [65] T. Lane and C. E. Brodley. “Temporal Sequence Learning and Data Reduction for Anomaly Detection”. ACM Transactions on Information and System Security, vol. 2, no. 3, pp. 295–331, 1999. [66] D. Tax and R. Duin. “Data domain description using support vectors”. In M. Verleysen (editor), Proc. of 7th European Symposium on Artificial Neural Networks (ESANN’1999), pp. 251–256. D-Facto, 27 rue du Laekenveld, B-1080 Brussels, Belgium, 1999. ISBN 2-600049-9-X. [67] V. Vapnik. The nature of statistical learning theory. Springer-Verlag New York, Inc., 1995. [68] B. Scholkopf, R. Williamson, A. Smola, J. ShaweTaylor and J. Platt. “Support vector method for novelty detection”. Advances in Neural Information Processing Systems, vol. 12, 2000. [69] B. Scholkopf, J. C. Platt, J. Shawe-Taylor, A. J. Smola and R. C. Williamson. “Estimating the Support of a High-Dimensional Distribution”. Neural Computation, vol. 13, no. 7, pp. 1443–1471, 2001. [70] K. Wang and S. J. Stolfo. “One Class Training for Masquerade Detection”. In ICDM Workshop on Data Mining for Computer Security (DMSEC). Available from http://www.cs.fit.edu/~pkc/ dmsec03/dmsec03notes.pdf (read 20.10.2005), November 2003. [71] K. A. Heller, K. M. Svore, A. D. Keromytis and S. J. Stolfo. “One Class Support Vector Machines for Detecting Anomalous Windows Registry Accesses”. In In Proceedings of the ICDM Workshop on Data Mining for Computer Security (DMSEC 2003). 2003. [72] B. V. Nguyen. “An Application of Support Vector Machines to Anomaly Detection”. Report cs681, Department of Mathematics, Ohio University, Athens, Ohio, USA, Fall 2002. [73] A. Lazarevic, L. Ertoz, A. Ozgur, J. Srivastava and V. Kumar. “A Comparative Study of Anomaly Detection Schemes in Network Intrusion Detection”. In Proceedings of Third SIAM Conference on Data Mining. 2003. [74] N. Tisby. “On the application of mixture AR hidden Markov models to text independent speaker recognition”. IEEE Transactions on Signal Processing, vol. 39, no. 3, pp. 563–570, Mar 1991. [75] A. Oulasvirta, M. Raento and S. Tiitta. “ContextContacts: Re-Designing SmartPhone’s Contact Book to Support Mobile Awareness and Collaboration”. In Proceedings of the 7th International Conference on Human Computer Interaction with Mobile Devices and Services, MOBILEHCI’05, pp. 167–174. ACM, 2005. [76] M. Raento, A. Oulasvirta, R. Petit and H. Toivonen. “ContextPhone, a prototyping platform for contextaware mobile applications”. IEEE Pervasive Computing, vol. 4, no. 2, apr–jun 2005. ISSN 1536-1268. [77] O. Mazhelis, S. Puuronen and M. Raento. “Evaluating classifiers for mobile-masquerader detection”. In Proceedings of Security and Privacy in Dynamic Environments (SEC2006), 21st IFIP TC-11 International Information Security Conference (to appear). Springer Science and Business Media, 2006. [78] I. H. Witten and E. Frank. Data Mining: Practical Machine Learning Tools and Techniques. Morgan Kaufmann Publishers, 2000. [79] D. H. Wolpert. The Mathemtatics of Generalization, chap. The relationship between PAC, the statistical physics framework, the Bayesian framework, and the VC framework. Addison Wesley, 1994.