Person identi cation based on keystroke dynamics is a challenging task with applications in various domains ranging from online education to internet banking. State-of-the-art solutions for this task are based on machine learning. In this paper, we present our solution which is based on dynamic time warping (DTW) and ECkNN, a recent hubness-aware regression technique. We performed initial evaluation on a dataset containing 200 typing sessions and we show that the proposed approach outperforms popular time-series classi ers. Additionally, we point out that we integrated the proposed approach into a Python-based web server which allows to demonstrate real-world applications of the proposed person identi cation technique. Furthermore, in order to motivate research in this domain, we announce an open challenge.
Conventional techniques for person identi cation range from passwords to
biometric identi cation, such as ngerprints, iris-patterns,
electroencephalographbased and electrocardiograph-based person identi cation [
Although the dynamics of typing, e.g. the time series of the duration of keystrokes, is characteristic to users, it is obvious that even the same user can not always type with the exactly same dynamics. This is illustrated in Fig. 1. The gure shows the durations of the rst 25 keystrokes in case of typing the same text by two di erent users. Each of the users typed the same text two times. The time series of user1 are shown in the left of the gure, while the time series of user2 are shown in the right of the gure. As one can see, the time series of the same user are more similar to each other than the time series of di erent users.
In particular, a peak (i.e., an exceptionally long keystroke) close to the fth position is characteristic to user1, whereas exceptionally short keystrokes close to position twenty are characteristic to user2. In case if we consider a large set of users, such as millions of students participating in online education, it may be di cult and time-consuming for human experts to identify patterns that are able to reliably distinguishing users from each other. Therefore, approaches based on machine learning are required for user identi cation based on typing patterns.
In our solution, we consider the task of person identi cation based on the
dynamics of typing as a time-series classi cation problem, for which various
approaches have been introduced ranging from neural networks [
Although the empirical evidence is also justi ed by theoretical results [
As the aforementioned studies show, bad hubs are responsible for surprisingly large fraction of the total classi cation error of nearest neighbour classiers, therefore, reduction of the detrimental e ect of bad hubs can substantially improve the accuracy of time-series classi cation. Consequently, we base our solution on ECkNN, one of the recent hubness-aware machine learning techniques. In Section 4 we present the results of our initial evaluation on a dataset containing 200 typing sessions and we show that the proposed approach outperforms popular time-series classi ers. Furthermore, we point out that we integrated the proposed approach into a Python-based web server which allows to demonstrate real-world applications of the proposed technique. Moreover, in order to motivate research in this domain, we announce an open challenge. 2
Nearest neighbour regression with error correction (ECkNN) is a hubness-aware extension of the kNN regression. By design it is suitable to various types of data, e.g. vector data, time series, etc., given that an appropriate distance measure between the instances of the dataset is available. As we work with time-series data describing the dynamics of typing, the instances are time series in our case. Next, we describe ECkNN in more detail.
In its training phase, ECkNN implements error correction on the training data. In particular, the corrected label yc(x) of an instance x is de ned as 8 1 P y(xi) if jIxj yc(x) = < jIxj xi2Ix 1
;
:y(x);
otherwise
(1)
where Ix denotes the set of those training instances that have x as one of their
k-nearest neighbours, jIxj is the size of the set Ix and y(x) is the original (i.e.,
uncorrected) label of instance x. When ECkNN is applied to predict labels for new
instances, it performs k-nearest neighbour regression using the corrected labels.
That is: for a new instance x*, ECkNN searches for the k-nearest neighbours of
x* among the training instances and outputs the average of the corrected labels
of the neighbours as the estimated label of x*. For more details about ECkNN
we refer to [
As mentioned previously, the dynamics of typing is captured by time series
data. In order to use ECkNN with time series data, it is necessary to determine
the nearest neighbours of time series. For this purpose, we use Dynamic Time
Warping (DTW), an extraordinarily popular time series distance measure that
is robust to elongations and noise [
We base our solution on the wide-spread \classi cation-via-regression" approach. In particular, we use ECkNN regression for the person identi cation task in the following way: for each pair of users (u; v) we train a separate model. While doing that, we associate time series describing the typing dynamics of user u with label 0. Similarly, the time series of user v are associated with label 1. When a new time series is presented to the trained model, the model outputs a continuous value between 0 and 1 (bounds are inclusive). Values close to 0 (or 1, resp.) indicate that, according to the model, the new time series is more likely to represent the typing dynamics of user u (or v, respectively).
Usage of pairwise models, i.e., models that distinguish between two users, is consistent with the circumstances under which the person identi cation problem arise in real-world applications: for example, in case of online exams and online banking, the user claims an identity and the task is to decide if the claimed identity matches the user's true identity. Assume that the claimed identity is u , and other users of the system are denoted by ui; 1 i n. In this case, for each user ui (except u ), we decide if the typing pattern is more consistent with the typing patterns of u than ui. These n decisions can be implemented in parallel if the number of users is high and several computational units are available.1
At each of the above decisions, a simple decision threshold of 0.5 could be applied, i.e., given a model trained to distinguish between the typing patterns of users u and v, if the model outputs less than 0.5 when a new time series is presented to the model, then the decision is u, otherwise the decision is v. However, the simple threshold of 0.5 may be suboptimal, therefore, we learn the threshold in the following way: once the model is trained, we present the time series of the training set to the model and obtain the output of the model for the training time series. Then, we determine the threshold that gives the highest accuracy on the training data. 4
Typing Dynamics Data We collected time series data describing the dynamics of typing, or typing patterns for short. In the initial evaluation, we used the data from four di erent users, each of them donated approximately 50 typing patterns, resulting in a collection of 200 typing patterns in total. In each of the typing sessions, the users were asked to type the same short text of a few sentences. In particular, the users were asked to type the following text based on the English Wikipedia page about Neil Armstrong: 1 As there might be users with similar typing dynamics, depending on the costs of di erent types of errors, in order to successfully authenticate user u we might allow a few of these pairwise decisions to \fail" in the sense that the model outputs that the typing pattern is more likely to belong to user ui instead of u*. Concretely, in case if we allow t of the pairwise decisions to \fail" in the above sense, we say that we set the value of the tolerance parameter to t.
That's one small step for a man, one giant leap for mankind. Armstrong prepared his famous epigram on his own. In a post- ight press conference, he said that he decided on the words just prior to leaving the lunar module.
In each typing session, we measured both (i) the time between consecutive keystrokes and (ii) the duration of each keystroke, i.e., the time between pressing and releasing a key. We used a self-made JavaScript application, a PHP script and a Python script to capture the aforementioned time series, save and preprocess the data. Note that due to typing errors, the length of the typing patterns (and the corresponding time series) varies slightly.
Experimental protocol In order to simulate the scenario in which users provide few typing patterns when they register into a system, we used the rst ve typing patterns per user as training data. The remaining typing patterns were used as test data in order to evaluate the system.
We trained models to distinguish two users: i.e, we trained a separate model
for each pair of users. For each model, we measured the accuracy, i.e., the ratio
of correctly classi ed instances. We report accuracies averaged over all the pairs
of users. We used the binomial test suggested by Salzberg [
We measured the accuracy of our approach, denoted as ECkNN, and the baselines in case of (i) using only the time series of the times between consecutive keystrokes, (ii) using only the time series of the duration of keystrokes, and (iii) using both of the aforementioned two time series. In the latter case, we combined the output of the two models used in the rst two cases by averaging their outputs.
We used the publicly available ECkNN-implementation from the PyHubs
library.2 We set k = 5 for ECkNN which is in accordance with other works on
hubness-aware machine learning [
As described in Section I, 1NN-DTW was reported as an extremely competitive time series classi er, therefore we used it as one of the baselines. Addi2 http://biointelligence.hu/pyhubs tionally, we performed experiments with k-nearest neighbour regression (kNN) with DTW and k=5 and a decision threshold learned on the training data (see Section 3 for the details of the \classi cation-via-regression" approach and how we learned the decision threshold).
Experimental results Fig. 2 and Fig. 3 summarize the results of our experiments. Fig. 2 shows classi cation accuracy of the combined models that use both types of time series. We observed that ECkNN outperforms both baselines statistically signi cantly according to binomial tests at signi cance level of p = 0.001. In Fig. 3, we examine the performance of both types of time series in more detail: keypress duration time-series seems to be more informative than the times between consecutive keystrokes. Most importantly, the combination of both types of information leads to the best performance out of the examined cases. 5
In order to demonstrate applications of the proposed approach in real-world systems, we integrated it into a Python-based web server.
In order to motivate further research in this domain and to allow the evaluation of various models and preprocessing pipelines, we published raw data describing the dynamics of typing and announce an open challenge. The description of the challenge and the dataset is available at: The data used for the challenge contains more than 500 typing sessions. It was collected from 12 users, therefore, the associated identi cation task is inherently more challenging than the task we considered for the initial evaluation. With \open challenge" we mean that the challenge shall run and submissions of new solutions shall be possible as long as there is interest both from the side of the scienti c community and the organizers.
The performance of the proposed approach and the baselines is available on the leaderboard as \ECKNN", \1NN" and \KNN". In the \Person Authentication" task (Task 1), we set the tolerance parameter to t = 2, whereas in the \Person Identi cation" task (Task 2) we used the majority vote of all the pairwise decision models. 6
In this paper, we considered the task of person identi cation based on the dynamics of typing. We presented initial results of our experiments with ECkNN, a hubness-aware regression technique. We compared the results of ECkNN with 1NN-DTW and kNN regression which are highly competitive baselines.
We integrated the proposed approach into a Python-based web server which aims to demonstrate the applicability in real-world systems. In order to encourage large scale evaluation of various machine learning techniques and future research, we announced an open challenge.
In case of person identi cation based on keystroke dynamics, a relatively
small set of reliably labeled data is given, e.g. the typing patterns that were
recorded when the user registered to the system. However, substantially more
unlabeled data (or \weakly labeled" data, under the assumption that the user
claims an identity when she tries to log in) may be collected during the usage
of the system. The presence of unlabeled data was not taken into account in
our work, but it might be exploited using semi-supervised machine learning
techniques, such as the SUCCESS approach [
As hubness-aware approaches performed well for the person identi cation based on the dynamics of typing, we envision that similar techniques may be applied to person identi cation based on electroencephalograph (EEG) and electrocardiograph (ECG) signals as well.
Acknowledgments. We thank Ladislav Peska for implementing the submission system used for the challenge. We thank Dora Neubrandt for her help with the implementation of the server demonstrating person identi cation based on keystroke dynamics. This research was performed within the framework of the grant of the Hungarian Scienti c Research Fund { OTKA PD 111710. This paper was supported by the Janos Bolyai Research Scholarship of the Hungarian Academy of Sciences.