Haritabh Gupta
email: haritabh@sit.iitkgp.ernet.in

Shamik Sural
email: shamik@sit.iitkgp.ernet.in

Vijayalakshmi Atluri
email: atluri@rutgers.edu

Jaideep Vaidya
email: jsvaidya@rutgers.edu

Deciphering Text from Touchscreen Key Taps

Keywords: Acoustic emanation, Touchscreen, Side-channel attack, Time Difference of Arrival (TDoA), NLP

Exploiting acoustic emanations from electronic as well as mechanical devices as a means for side channel attack has recently emerged as a topic of security concern. In this paper, we present an attack methodology that can be used to extract the text typed by a user from the sound recorded by the built-in microphones of a mobile phone. We use signal processing techniques to initially extract a likely set of characters per tap on the touchscreen and then use natural language processing algorithms to find the most probable words and sentences that can be constructed from a given tap sequence. We also discuss the causes that result in this vulnerability and briefly present some countermeasures.

Introduction

In recent times, mobile phones have almost become a necessity rather than a luxury for a large section of people throughout the world. Reports show that mobile phone penetration will reach approximately 70% of the global population by the year 2020. With increased reliance on mobile phones, especially for personal and confidential information exchange like mobile-commerce applications, the level of security ensured by these devices is an important topical issue.

Many users have started using phones for doing almost all of the work that they used to do on computers even a few years back. Although these mobile devices are yet to replace computers in their entirety, still a majority of the work has now shifted to the mobile devices due to various reasons such as mobility, portability, etc. Tasks range from composing e-mails, editing documents and accessing e-banking sites to surfing the net, using various applications (apps) like cab and hotel booking, chatting and participating in online social networking. All these tasks involve text input using a keypad, which is typically touchscreen in nature. In this paper, mobile phones (including smartphones and tablets) are hereinafter referred to simply as phones and they represent mobile devices that have a touchscreen user interface and have features like Internet access, support for recording and storing media files.

Most phones today are equipped with at least two microphones. Since these microphones are attached to the phone body, they pick up even the slightest sound produced on the surface of the phone. As a user taps on the touchscreen while typing, it produces a sound that may not be quite audible to the human ear due to the presence of ambient noise. Such tap sounds can, however, be captured using the microphones of the phone itself. A user hardly ever denies microphone use permission and Internet access to an app while installing the same. Also, an app is not considered to be suspicious unless it asks for some unusual combination of permissions. We show that even the above two seemingly innocuous permissions can be maliciously exploited to extract the text typed on the device and thus cause a security breach.

In the past, there has been some limited work that shows ways to recover text using acoustic emanations from mechanical keyboards [START_REF] Hussain | The rise of keyloggers on smartphones: A survey and insight into motion-based tap inference attacks[END_REF]. They use external microphones to capture the sound and the recorded sound is used to train classifiers that differentiate between the sounds produced by different keys. It has also been shown that the sensors equipped with mobile phones such as accelerometer and gyroscope can be used for text extraction [START_REF] Miluzzo | Tapprints: Your finger taps have fingerprints[END_REF] [8] [START_REF] Ping | Textlogger: inferring longer inputs on touch screen using motion sensors[END_REF]. While such an approach uses the sensors attached to the phone, still it requires supervised learning. The possibility of exploiting the audio signal captured by the built-in microphones of a phone to decipher the typed text has never been studied, to the best of our knowledge.

This paper presents a novel methodology for carrying out a side-channel attack using acoustic emanations from the touchscreen keypad of a phone and that too using readily available tools. The approach is based on phone geometry and keypad layout, while using signal processing and natural language processing (NLP) techniques.

The rest of the paper is organized as follows: Section 2 describes our methodology and the associated algorithms in detail. Section 3 provides the complete workflow of an implemented system. Section 4 presents the results obtained in terms of accuracy of the proposed methodology. Related work is reviewed in Section 5. Some preventive measures are discussed in Section 6. Finally, Section 7 concludes the paper and presents some directions in which this work can be carried forward in future.

Attack Methodology

The complete methodology of the attack can be divided into two phases. The first phase, which is described in Sub-section 2.1, uses signal processing techniques to determine the probability of different characters that might have been entered with each tap using the audio signal received by the two microphones. It exploits the phone geometry and touchscreen keypad layout. In the second phase (Subsection 2.2), NLP techniques are used to extract the probable word sequence that has been typed by processing the output of the first phase.

Character sequence extraction using microphone data

Most of the phones nowadays are equipped with at least two microphones with stereo recording capability. As a user types on the phone touchscreen, it produces a sound for each tap. The microphones, which are quite close to the touch surface, capture this sound. There is hardly any damping as the microphones are solidly attached to the phone body. The two microphones are almost invariably positioned at unequal distances from the point of touch. As a result, from the recorded sound of key taps, the time difference of arrival (TDoA) of peaks in the two microphones can be computed. For each TDoA, the locus of the touch point such that the difference of its distance from the two microphones is constant, forms a hyperbola, with the two microphones at its two foci. Depending on the sign of TDoA, it can be inferred which half of the hyperbola is meaningful for a given key tap. We compute TDoA using cross correlation [START_REF] Benesty | Time-delay estimation via linear interpolation and cross correlation[END_REF] between the two audio signals recorded at the two microphones as explained below.

The co-ordinate system is defined such that the top left corner of the phone, while holding it upright and facing front, coincides with the origin and the left edge is parallel to the x-axis. As a result, one microphone (denoted as m 1 ) lies on the y-axis and the other (denoted as m 2 ) is in the first quadrant. Let the coordinates of the microphones be (0, p) and (l, q), respectively. Then the phone can be represented as shown in Figure 1a. Thus, the vertex of the hyperbola, as mentioned above, also lies in the first quadrant. Hence, we use the general equation of a hyperbola with vertex at (x 0 , y 0 ). The equation to represent this hyperbola from the obtained TDoA is as follows: In Equation 1, (x, y) represents any arbitrary tap point while a and b denote parameters of the desired semi-hyperbola. The following equations are used to compute these parameters in terms of other known and measurable quantities.

(x -x 0 ) 2 a 2 - (y -y 0 ) 2 b 2 = 1 (1)
a = ∆d 2 , where ∆d = |d 1 -d 2 | (2)
Here, d i is the distance of the i th microphone from the tapped point on the touchscreen, i ∈ {1, 2}. From Figure 1a, it is seen that

c = (l -0) 2 + (q -p) 2 2 (3)
Here, l, p, q are phone parameters of which l denotes the length of the phone (dimension of the longer edge). p and q denote the distances of the microphones m 1 and m 2 , respectively from the base of the phone. Hence, we can write:

b = c 2 -a 2 (4)
x 0 = c (5)

y 0 = min(p, q) (6)
Simplifying and solving for x in terms of y from Equation 1, we get:

x = x 0 ± a b b 2 + (y -y 0 ) 2 (7)
We use this equation to obtain the values of x corresponding to the values of y, where y = [0, w], w being the width of the phone. ∆d is computed using the TDoA obtained and the parameters of the recorded sound, namely, the sampling frequency f s and the sample offset ∆s. Sample offset is the value by which one of the audio signals needs to be shifted so that the correlation between the two signals is maximum. The rest of the parameter values are computed using Equations 2 to 7. ∆d is obtained from ∆s and f s using Equations 8 and 9 as follows:

T DoA = ∆s f s (8)

∆d = v sound • T DoA (9)
Thus, by computing the value of TDoA, we can obtain the desired hyperbola. Hence, the problem of determining the hyperbola parameters reduces to estimating the TDoA (or sample offset ∆s) between the signals received by the two microphones. In the rest of the text, the terms T DoA and ∆s are used interchangeably because from Equation 8, it is evident that we can compute one from the other as f s is kept constant.

From the recorded audio signals of the microphones, the first task is to detect the tap instants (peaks in the signal). We present an automated scheme for peak detection, which is shown as the Detect P eak Intervals algorithm (Algorithm 1). It takes the audio signals as input and returns a set of time intervals, each containing only one tap. A detailed description of the algorithm follows.

Algorithm 1 Detect P eak Intervals

Input: Sound signal xi(t) where i ∈ {1, 2}, half window size w h , threshold θ Output: Set of intervals containing taps: intervals 1: for t=1 to n do Calculate Energy 2:

Ai(t) = t+10 n=t x 2 i (n)
, where i ∈ {1, 2} 3: end for 4: for t = 1 to A.length do A ∈ {A1, A2} 5:

s k and e k store beginning and end of a window around the selected time t 6:

[M, I] ← max(Ai(s k : e k )) where i ∈ {1, 2} I : index of the maximum value 7:

if t = I + s k and M > θ • max(A) then 8: tmpIntr ← tmpIntr ∪ (s k : e k ) 9:
end if 10: end for 11: intervals contains time readjusted and center positioned peaks 12: return intervals In Algorithm 1, the for loop of Lines 1 -3 computes the energy levels of the signal by accumulating 10 sample points together. Next, in the for loop of Lines 4 -10, for each sample point, first the beginning and end points of the interval window are set in variables s k and e k for the k th sample point. Lines 6 -9 compute the maxima of the signal in the interval. If this value is greater than the threshold computed according to θ, then the corresponding interval is added to the set tmpIntr. Finally, the computed time intervals are readjusted so that the peaks are positioned at the center of each interval.

Algorithm 1 runs in O(n) time as there are three loops in the algorithm of complexity O(n), O(n) and O(k), respectively. Here, n is the number of sample points of the audio signal, k is the number of taps in the recording and n k. The output of Algorithm 1 is a set of intervals, each of which contains a tap. These intervals are further processed to get the TDoA corresponding to each tap. We next propose an algorithm (Compute T DoA) to find the sample offset ∆s of the two signals in a given interval, which is shown in Algorithm 2. It takes the audio signals (x 1 and x 2 ) from the two microphones (m 1 and m 2 ) and for each of the intervals obtained from Algorithm 1, finds their cross-correlation. Then it takes the median of the top p peaks.

The for loop of Lines 3 -13 in Algorithm 2 selects each interval from the set of intervals one at a time. Next, the for loop of Lines 7 -11 selects the top p peaks (empirically set to a value of 3) from the cross correlation. Line 12 adds the computed median to the set lagM edian. The final lagM edian set is returned by the algorithm.

The set of time lags thus obtained is used to determine the hyperbola corresponding to each tap. The locus of the valid semi-hyperbola obtained using Equation 7, when overlayed on the keyboard layout as shown in Figure 1b, returns the shortest distance of each key from the semi-hyperbola. The probability with which a key is pressed, i.e., the individual character entered by the user, is considered to be inversely proportional to the shortest distance of the key from lagT emp ← φ 7:

for i = 1 to p do 8:

[M, I] ← max(||acorr||) I is the index of the maximum value 9:

acorr[I] ← 0 10:

lagT emp ← lagT emp ∪ M 11:
end for 12:

lagM edian ← lagM edian ∪ median(lagT emp) 13: end for 14: return lagM edian the semi-hyperbola. Thus, we obtain the top k most probable characters for each TDoA and hence, for each key tap.

Word and sentence inferencing from probable character sequence

This sub-section describes the methodology used to construct sentences from the sequence of characters obtained using Algorithm 2 of Sub-section 2.1.

To carry out the attack, uni-gram, bi-gram and tri-gram probabilities are used. The character-level n-grams as well as word-level n-gram counts are learned from the e-mail corpus1 in a pre-processing step.

The probability of occurrence of an n-gram is the count of that n-gram divided by the total number of n-grams. However, since the number of n-grams is very large, the probability value comes out to be too small. To compute the probability of a string, we need to multiply these n-gram probabilities. If we use the actual probability values, the product might cause an underflow. On the other hand, taking the product of the count of n-grams results in an overflow. Hence, to avoid both underflow and overflow, instead of using the probabilities directly, we introduce the notion of pseudo -probability, which is the log of the count of n-grams. The steps for computing pseudo-probability are shown in Algorithm 3 (Compute pseudo-probability of a string). In this algorithm, the outer f or loop of Lines 2 -12 runs the inner loop considering i-grams in its i th iteration. The inner f or loop of Lines 7 -10 picks up an i-gram from the string, computes its pseudo-probability, and adds it to the temporary variable prob t . Finally, Line 11 adds the temporary probability (prob t ) to the total probability variable prob of the string after multiplying it with the appropriate weight factor.

There are two loops in Algorithm 3. The outer loop runs n times if n-grams are used for the computation, while the inner loop runs in the order of the length of the string, denoted here as l. Hence, the overall time complexity is O(n • l)

From the computed score of strings, we build an inference tree to determine the most probable text that was typed. The language model is based on ngram and inference based tree [START_REF] Zhu | A monolingual tree-based translation model for sentence simplification[END_REF] [START_REF] Brown | Class-based ngram models of natural language[END_REF]. The character-level n-grams are used to construct a word-level inference tree. At each level, we include the next set of probable characters and recompute the probabilities of the strings thus obtained. At every level, only the top k nodes are retained and the rest are pruned. This prevents the tree from expanding exponentially. In the last level of the tree, we are left with k most probable words that can be constructed using the character sequences obtained from the algorithms presented in Sub-section 2.1.

The node used to create the tree in Algorithm 4 is a three-tuple represented as node = string, prob, children , where string is the partial word that is stored in the node. prob stores the pseudo-probability of this partial word computed using Algorithm 3. The children for this node is stored in the list children. In this tree, for any child node c, if p is its parent node, then p.string is a prefix of c.string (Property 1 ). Also, the tree is constructed in such a way that at any level l of the inference tree, the maximum number of nodes does not exceed n, where n is a user-defined input parameter (Property 2 ).

We propose an algorithm (Generate W ord-level inf erence tree) that builds the word-level inference tree whose properties and node structure are defined in the previous prargraph. This algorithm builds the inference tree one level at a time. Each level of the tree adds to the tree, the set of probable characters corresponding to the next tap. The outermost f or loop of Lines 2 -13 selects the set of characters corresponding to the i th tap in the i th iteration. Next, the leaf nodes in the tree are pruned so that the tree retains Property 2. The f or loop of Lines 5 -12 selects each of the remaining leaves one at a time. Pruning of leaves is done using the T runcate leaves procedure as shown in Algorithm 5. The f or loop of Lines 6 -11 adds new child nodes to the current node and sets the string so that they satisfy Property 1. The prob value in new nodes (denoted as t) is computed using Algorithm 3. Algorithm 4 terminates when all the probable characters corresponding to all the key taps have been added to the tree.

There are three nested f or loops in Algorithm 4, with time complexity of O(n), O(c) and O(k), respectively. Here, n is the total number of taps, k is the number of probable characters returned per tap and c is the number of allowed child nodes per level. Invocation of T runcate leaves() contributes to O(l) time, where l is the number of nodes at a level prior to pruning. So, the time complexity of Algorithm 4 is O(n • (O(l) + (c • k))). c and k being fixed parameters and independent of the input size n, the time complexity becomes O(n • l).

A similar approach is used to build a sentence-level inference tree based on the most probable word sequence. As in the word-level inference tree, at each level, we prune all the nodes except the top k (based on the pseudo-probability value). In the last level, we are then left with the top k most probable sentences that can be constructed from the set of probable words and hence from the set of probable characters.

Both the word-level as well as sentence-level inference trees use leaf pruning to prevent exponential expansion of the tree. The pruning algorithm (T runcate leaves) first takes the list of all children at the current level as shown in Algorithm 5. It then deletes all nodes except the top c nodes and returns the modified list. The time complexity of this algorithm is O(n • c), where n is the number of leaves prior to pruning and c is the desired number of leaves after pruning. Since c is a constant, the overall time complexity is O(n). In this section, we have described the two phases of the proposed attack methodology and the algorithms used to carry out the attack. The next section presents the details of implementation of a complete system for carrying out such an attack.

Algorithm 5 T runcate leaves

Implementation Details

This section presents an implementation flow of the attack starting from the recording of sound to the extraction of estimated typed text. A trojan app is installed on the victim's phone that creates audio files from the recorded tap sounds. It needs only microphone permission during installation and Internet access permission so that the audio files can be sent to the attacker's server for further processing. The processing of audio files needs information extracted from preprocessed text corpus which is quite large to store in the phone and the word extraction will be quite computation expensive for the phone processor. Hence, we propose to perform all computations on the server rather than on the phone.

The first module at the server end processing in the overall block diagram of Figure 2 takes the raw audio file as input and generates the list of time intervals that contain peaks (taps on the touchscreen). Our recording environment emulated any quiet room like library, office, conference room, etc., typical places The list of peaks is given as input to the next module along with the audio file. This module, as described in Algorithm 2, computes the cross correlation between the sound waves from the two microphones. Figure 3a shows the energy spectrum of the audio signals as captured by the two microphones corresponding to a tap. It is seen in the figure that there are sharp peaks during the tap, preceded and followed by periods of silence. This property of the microphone captured signal is used to extract peaks from the audio files.

The time domain representation of the two audio signal amplitudes in Figure 3b shows that there is a noticeable shift between them. Figure 4a presents a detailed view of the two audio signals corresponding to a tap. Cross correlation is computed between these two signals. The cross correlation peak is the actual TDoA between the signals. The computed TDoA is used as a parameter for the hyperbola that corresponds to the probable region of tap. It is also observed from Figures 3a-3b that out of the two signals, one has higher amplitude than the other. This difference in amplitude is used to select the valid semi-hyperbola. As an example, if signal from microphone m 1 has higher amplitude, then the tap sound must be emanating from the left half of the keyboard (the half that is closer to microphone m 1 ).

Note that, the sign of TDoA can also be used to select the correct half of the hyperbola. For example, if the peak in the signal from microphone m 1 occurs before the peak in the signal from microphone m 2 , it can be concluded that the click originated from that half of the keypad which is closer to microphone m 1 .

The magnitude of the TDoA is used next to obtain the probable region on the keyboard layout where the tap occurred. This is shown in Figure 4b. In this example, the key a was tapped. The computed TDoA was used to plot the hyperbola and depending upon the sign of the TDoA, the other half of the hyperbola was discarded. We see that the maximum probability region passes over a. Thus, for every tap, we determine the most probable region of the tap. To get the k most probable characters, we set the width of the band in such a way that k number of keys fit into the band of the hyperbola. The P robable Character Extraction module of Figure 2 then returns the k characters that have the highest intersection area with the plotted region.

Sample number

Text inferencing from the probable sequence of letters is done by building the inference tree and pruning leaves at each level as explained in Algorithms 4 and 5. This approach is used for both word level as well as sentence level inferencing of Figure 2.

Experimental results

We carried out detailed experiments with our system implementation described in Section 3. In this section, we present several important observations that were made during the experiments as well as quantitative result on accuracy. The results consist of two parts. Sub-section 4.1 presents the results obtained till the extraction of the probable characters from the audio signal captured by the microphones. Sub-section 4.2 then presents the results of the stages related to inferencing of words from probable characters and that of sentences from the probable set of words.

The dataset that we used to test the hypothesis and proposed methodology has following statistics. On average, the audio encoding of each character takes ≈82 kB per character, while the average typing speed was ≈ 2 characters per second. Moreover, the complete methodology presented in Section 2, takes about 70 seconds to decipher text from a recording containing ≈ 100 taps.

Audio processing results

Figure 5 shows the plot of various TDoAs measured in number of sample points and the character set that are returned corresponding to each TDoA. In one of the phones used for experimentation (layout shown in Figure 1b), T DoA ∈ [-8, 10]. We plot each TDoA over the keyboard layout keeping k = 3 as described in Section 3 and return the character set corresponding to that TDoA. A linear trend is seen in the values of TDoA and the characters returned also shift from the left end of the keypad to the right end. For example, for T DoA = 10, the returned character set is {q, w, a} and for the minimum value of T DoA = -8, the returned character set is {p, l, o}. In Figure 6a, we plot the distribution of the computed value of TDoA for one particular letter (clicked letter is a). The set of top k most probable characters containing the typed character can be extracted with quite good accuracy. From Figure 6b it is seen that, using k = 3, the character that was actually typed is present in the set of probable characters 90% of the time. For the rest 10%, the computed TDoA deviates only by 1. Hence, it can be concluded that TDoA is a robust feature to be used for the proposed attack methodology. This set of probable characters is used as input for the NLP module, the results of which are presented in the next sub-section.

Text extraction results

Figure 7a shows the variation in word occurrence frequency and word level accuracy with change in word length. We took a test set of 30 messages of varying sizes. The text was deciphered using the proposed attack methodology from the tapping sounds picked up by the two microphones and compared with the actual typed text. The bars in the graph show the fraction of the count of occurrences and the fraction of the number of times they were recovered correctly. The piecewise continuous line represents the accuracy and a linear trend line is also plotted in the graph for reference. From the figure, it is observed that accuracy approaches 1.0 when the word length is 1 or 2. This is because these are usually stop words like a, an, be, at, etc. Such words are quite common and thus can be inferred accurately. The next peaks occur at word lengths 3, 4 and 5. This is due to the fact that, in the English language, the average word length is 5.1 letters [START_REF] Bochkarev | Average word length dynamics as indicator of cultural changes in society[END_REF]. Words with greater length occur rarely, as a result of which, there are less number of samples with longer length to train the language model. Therefore, while inferring, the accuracy decreases with increasing word length beyond 5. The average word level accuracy is 0.81. Figure 7b shows the variation in accuracy of complete text with message size. For this study, we use the same data set as in Figure 7a. It is seen from the figure that the accuracy lies in the range of 0.57 -0.95, with an average of 0.88. It is also observed that accuracy tends to increase with increasing length of the text. The NLP algorithm assumes that the text is composed of English words only. Hence, such a trend is observed, because with increase in message size, the ratio of valid English words to the total number of words increases.

A few local variations are also seen in the figure. This point was further investigated. It was found that our assumption that the user would be typing in English, i.e., using words from the valid English vocabulary did not always hold. Often the message contained certain words like URLs, dates, proper nouns, etc., that are not there in the English dictionary, which caused some degradation in performance.

Related work

It has been shown in the literature that emanations from devices can be exploited in ways to reveal information associated with the source, thereby breaching security. There are several variations of this type of attack based on the type of emanation [6] [9]. Particularly, acoustic emanations from various devices is an important field of research. Asonov et al. [START_REF] Asonov | Keyboard acoustic emanations[END_REF] show that the keyboard strokes can be recovered using the acoustic emanations from mechanical keyboards. They argue that although the emanations from different keys sound similar to human ear, they are actually different and a classifier can be trained to distinguish between the keys. Fast Fourier Transform is used as the feature set of the sound and backpropagation neural network is used for classification.

The above issue was readdressed by Zhuang et al. [START_REF] Zhuang | Keyboard acoustic emanations revisited[END_REF], who presented a novel technique using which even random keystrokes can be recovered. Unlike the attack methodology of [START_REF] Asonov | Keyboard acoustic emanations[END_REF], which requires labeled data to train the neural network before it can be used as a classifier, this attack uses the statistical constraints of the English language to train a model by unsupervised learning. They use cepstrum features, which were shown to be superior to FFT. Another related work [START_REF] Dagon | Mobile phones as computing devices: the viruses are coming![END_REF] provides a brief explanation and analysis of the possible attacks that can be carried out using mobile phones. It presents a nomenclature for various attacks. Some preventive measures are suggested that can be implemented to minimize the risk from the identified possibilities of attack.

Since our work is aimed at deciphering text from touchscreen mobile phones, we next present some work in this field. Miluzzo et al. [START_REF] Miluzzo | Tapprints: Your finger taps have fingerprints[END_REF] discuss the possibility of use of the accelerometer and gyroscope sensors of phones and present a method to recover the tap position as well as the typed text. They propose that each point on the screen, when tapped, produces different values of linear and angular acceleration, which can be captured using the phone sensors.

Zhu et al. [START_REF] Zhu | Context-free attacks using keyboard acoustic emanations[END_REF] present a context-free attack technique to recover keystrokes using phones as recording devices placed in the vicinity of the keyboard being typed on. With enough number of such external microphones, the keystroke region can be pinpointed with good accuracy. To make the attack even more general, the keyboard orientation is also assumed to be unknown beforehand. Keyboard reconstruction is formulated as an optimization problem and the most likely keyboard layout is taken as the orientation of the keyboard. Finally, the keystrokes are recovered.

There is, however, no work that recovers key taps from touchscreen keypads using built-in microphones of a mobile phone as reported in this paper. Such an attack is more realistic than the ones mentioned above since the previous attacks require external hardware to record the sound of key presses. Setting up of extra hardware in the vicinity of the victim while he is typing is susceptible to detection. Since the proposed methodology uses the microphone already attached to the device, it can silently record and transmit the audio signals to the attacker's server.

Preventive measures

There are a few basic preventive measures, which however, might reduce the impact of such an attack, even though it cannot be eliminated fully. For instance, if the user keeps the key-press tone ON, then with each tap, an additional sound will be generated masking the actual sound created by the tap to a certain extent. A similar effect may be achieved if the vibration on each key-press is kept ON. However, both of these counter-measures are inconvenient for the user and they drain the battery as well.

Another approach that may be adopted by the operating system developers is that the OS can display notifications (using icons) to depict which devices are currently being used in the background. Thus, the user will be notified if the microphone or any other sensor is running in the background. The OS may also display the apps which are currently using that sensor data. In this way, the user can become aware of any background app trying to eavesdrop and possibly terminate it to prevent the attack. However, such measures demand a certain level of maturity and knowledge on the part of the user.

Conclusion

The primary goal of this paper was to bring to light the vulnerabilities of touchscreen phones, which we have exploited and devised an attack methodology that is reasonably accurate. It may be noted that, any form of encryption will not help to prevent this attack as the proposed methodology records the tap sounds generated at the time of typing itself.

The direction for future work on improving the attack methodology is threefold: (i) improving accuracy of the signal processing unit (ii) use of other NLP techniques to enhance the performance of the text inferencing phase and also to detect special characters and numerals. This would allow the attack to detect passwords as well. (iii) Fusion of data from more number of sensors. Sensors such as gyroscope and accelerometer are also present in almost all smartphones. For each key tap, the accelerometer and gyroscope values would vary. Although this data is a bit more difficult to make use of as compared to the microphone data, still it is a possibility that is worth exploring to see how the attack performs.

Fig. 1 :

 1 Fig. 1: (a) Hyperbola coverage on keyboard with k = 3. (b) Hyperbola coverage on keyboard with k = 6.

Algorithm 2

 2 Compute T DoA Input: Set of intervals intervals each containing one peak, audio signal xi(t) where i ∈ {1, 2} Output: Set of TDoA corresponding to each peak: lagM edian 1: lagM edian ← φ 2: p ← 3 Median of p peaks is computed 3: for n = 1 to intervals.length do 4: si = xi(sn : en), where (sn, en) = interval[n] and i ∈ {1, 2} 5: [acorr, lag] ← xcorr(s1, s2) Compute cross-correlation 6:

Fig. 2 :

 2 Fig. 2: Block diagram of attack flow implementation

Fig. 3 :Fig. 4 :

 34 Fig. 3: (a) Energy spectrum of the input signsl corresponding to a single tap. (b) Input signals in time domain corresponding to a tap.

Fig. 5 :

 5 Fig. 5: Character sets for different values of TDoA

Fig. 6 :

 6 Fig. 6: (a) Computed values of TDoA obtained from cross-correlation for 100 taps of a. (b) Distribution of the computed TDoA.

Fig. 7 :

 7 Fig. 7: (a) Accuracy for different word lengths (b) Variation in accuracy with message size

  Algorithm 3 Compute pseudo-probability of a stringInput: Candidate string str, weight factor ω, maximum n-gram length nGrams

	Output: Pseudo-probability of string: prob
	1: prob ← 0
	2: for l = 1 to nGrams do
	3:	if l > str.length then
	4:	break
	5:	end if
	6:	probt ← 0
	7:	for i = 1 to str.length do
	8:	subStr ← str[i : i + l]
	9:	probt ← probt + log(gramCount(subStr)) + 1
	10:	end for
	11:	prob ← prob + (probt) • ω l	weighted sum of n-gram pseudo-probabilities
	12: end for
	13: return prob

  It is shown in Algorithm 4.Algorithm 4 Generate W ord -level inf erence treeInput: Probable characters of a word in 2-d array aplha, child count c Output: set of c most probable words: words 1: initialize root node and set all parameters to φ 2: for i = 1 to alpha.length do

	3:	allLeaves ← getLeaves(root)
	4:	trLeaves ← truncateLeaves(allLeaves, c)
	5:	for all curr ∈ trLeaves do
	6:	for all ch ∈ alpha[i] do
	7:	t ← φ
	8:	t.string ← curr.string • ch	append ch to the string of parent node
	9:	t.prob ← stringP rob(t.string)/t.string.length	Compute
		pseudo-probability of string t.string and normalize by string length
	10:	curr.children ← curr.children ∪ t
	11:	end for
	12:	end for
	13: end for
	14: return getLeaves(root)

Enron Mail corpus: https://www.cs.cmu.edu/ ~./enron/


Stefan Thaler
email: s.m.thaler@tue.nl

Jerry Den Hartog
email: j.d.hartog@tue.nl

Milan Petkovic

Towards Creating Believable Decoy Project Folders for Detecting Data Theft

Keywords: Data Theft Detection, Data Theft, Intrusion Detection, Decoy, Honey Pot, Trap-based Defense, Deception

Digital data theft is difficult to detect and typically it also takes a long time to discover that data has been stolen. This paper introduces a data-driven approach based on Markov chains to create believable decoy project folders which can assist in detecting potentially ongoing attacks. This can be done by deploying these intrinsically valueless folders between real project folders and by monitoring interactions with them. We present our approach and results from a user study demonstrating the believability of the generated decoy folders.

Introduction

Digital data theft is becoming a huge problem in our ever more digitalized society. The total number of data breach incidents as well as the damage caused are rising an alarming rate. One strategy to detect ongoing digital attacks is baiting data thieves with digital decoys. These decoys are valueless, therefore any interaction with them is suspicious and will alert the responsible security offer.

One type of decoys is decoy documents. A decoy document is a file which contains seemingly sensitive information. These documents are usually stored with other sensitive documents and closely monitored. Interactions with them are reported and stored. However, while decoy documents are useful tools to obtain intelligence about an ongoing attack, most of a company's intellectual property comprises multiple files and folders, grouped together in a project folder. Yet, deceptive approaches as detection strategy are hardly used in this setting, since manually creating believable project decoys is a cumbersome, labor intensive task.

In this work we present a data-driven approach for dynamically creating new project folders from a set of existing folders based on multiple Markov models using maximumlikelihood parameter estimation. After the decoy model is learned, it can be used to sample believable project folders which resemble the original folders and can be used as deceptive bait. This deceptive bait can be placed between "real" projects. Assuming the decoys are properly monitored, they can aid in the detection of malicious activity around these real project files, since any interaction with a decoy is per definition suspicious.

We have implemented a prototype and conducted a user study to evaluate whether the generated project decoys are perceived as being realistic.

We begin this paper with a brief review on related approaches in Section 2 to highlight gaps and motivate our approach. In Section 3 we describe our approach. We start by giving a high level intuition of our approach which is followed by a formal definition of our decoy model. In Section 4, we provide empirical evidence for the believability of the generated decoys. In Section 5 we discuss the results and limitations of our work. We conclude this paper by highlighting possible future improvements.

Related work

Deception has been an element of warfare since a long time. In the context of IT security, Clifford Stoll reported one of the first uses of deception [START_REF] Stoll | The cuckoos egg: Tracing a spy through the maze of computer espionage[END_REF] to catch a hacker. Lance Spitzner coined the term honeypot and honeytoken [START_REF] Spitzner | Honeypots: Catching the insider threat[END_REF], which are descriptive synonyms for computing resources that are created to deceive an attacker. Bringer et al.'s survey provides an overview over recent advances in the field [START_REF] Bringer | A survey: Recent advances and future trends in honeypot research[END_REF].

In this paper we introduce a data-driven approach to create believable project folders that can be deployed to detect data theft attempts. Previous approaches focused on creating and placing single decoy documents( [START_REF] Yuill | Honeyfiles: deceptive files for intrusion detection[END_REF], [START_REF] Bowen | Baiting inside attackers using decoy documents[END_REF], [START_REF] Voris | Lost in translation: Improving decoy documents via automated translation[END_REF], [START_REF] Whitham | Canary Files: Generating Fake Files to Detect Critical Data Loss from Complex Computer Networks[END_REF]) or file systems [START_REF] Rowe | Automatic detection of fake file systems[END_REF]. Conceptually we also create decoys to detect data theft. However, instead of creating single documents we focus on creating project folders with a believable structure, file names and properties.

Decoy Project Folder Generation

On a high level our approach can be divided into two phases, a learning phase and a sampling phase. Both phases are subdivided into two steps each.

The first step of the learning phase is to normalize the training data. In this step we replace properties of the source files and folders with placeholders. Examples of such properties are occurrences of the project name or access rights. We use this normalized training data to learn Markov chains representing the folders and property distributions, which is the second step of the learning phase. The decoy model is defined in Section 3.2.

In the sampling phase we use the previously learned model to generate decoy project folders. The first step of this phase is to generate the decoy directory structure. The second step is to instantiate the decoy project folder by assigning attributes to the nodes of the directory structure and replacing property placeholders with instantiation values.

Preliminaries and Assumptions

We assume the following concepts used in the paper are known: we will use first-order, finite-state, discrete-time, Markov chains (simply called Markov chains below) to model the co-occurrence of files and folders within one directory. We use the maximizing likelihood estimator [START_REF] Kemeny | Finite markov chains[END_REF] to learn the Markov chain parameters from observed sequences of files and folders.

In order to maximize the information of our learned decoy model, we will use a heuristic based on the mutual information [START_REF] Shannon | The mathematical theory of communication[END_REF] of files occurring together.

We will use a (finite) forest [START_REF] Diestel | Graph theory[END_REF], i.e. a set of trees, to model our training file systems.

Learning requires multiple samples. To be able to effectively learn the content of folders we assume that two folders with the same name have similar contents.

Assumption 1 If two folders within a context have the same name, they have similar contents.

Definition of the Decoy Model

In this section we formally define our decoy model in a bottom-up manner.

To build the model we will use a training file system that contains a number of projects which structure objects such as files and directories in the form of a tree and assigns properties to these objects. Definition 1. We assume a fixed set of objects O, a set of attributes A and a (training) file system T T over these objects is given. Here an attribute a ∈ A is a function from objects to a domain Dom a and file system T T is a forest over objects.

Intuitively, Definition 1 states that we use a set of project folders as input for our decoy model. These project folders are organized within a directory tree, which is common in Windows-and Unix-based operating systems. An object represents a file or a folder within a project directory, and each file or folder has certain attributes such as a name, permissions or creation-and modification dates.

Some attributes are dependent on the project, for example filenames containing the project title or creation time of files that will be within the running time of the project. Therefore, to learn a common structure from different projects we 'normalize' the project to make them consistent. For example, we replace all occurrences of the project name by a 'placeholder'. We then refer to the normalized objects as nodes, and the normalized T T as NodeTree. For simplicity a file is represented as a node without children.

Definition 2. We assume a fixed set N , called Nodes, a node tree N T over nodes and normalization function µ : O → N , mapping objects to nodes, are given.

The only attribute that we assume is always there is 'name'. The other attributes may depend on the operating system, therefore we do not further specify them here. Instead, we simply assume they are available.

We aim to learn the content of folders. Assumption 1 states that similar names convey similar contents. Therefore, we group nodes (i.e. normalized files and folders) by their name. Next, we look at the content i.e. the children of these nodes.

N G(d) = {n ∈ N | name(n) = d} N GC(d) = {ch(d ) ∪ {s s , s e } | d ∈ N G(name(d))}
Here, s s represents an artificial node 'start state', i.e. the start of a directory and s e represents the end of a directory.

From a NameGroupChildren we can find the frequencies of occurrence of nodes. However, simply taking their frequency may not be sufficient; some nodes will naturally occur together or will exclude each other. As such combination might allow an attacker to easily spot a fake project folders we need to take such dependencies into account. Thus we need to estimate the probability of certain nodes co-occurring in a folder. Yet, learning the complete joint probability of all nodes with any accuracy is not very realistic because the number of samples needed grows exponential with the number of (possible) children nodes of a node.

As a compromise we use Markov chains to model the probabilities. This allows taking into account pairwise dependencies between some nodes. In order to train our Markov chains we will treat the children of the nodes of a NameGroup as encountered observations. In this construction the order of the nodes matters; dependencies are only taking into account between the current and next node. After visiting an intermediate node this information is lost. As such nodes with a relevant dependency on each other should occur next to each other to ensure the dependency is expressed in the model. Definition 4. To help optimize the amount of information about dependencies that we can capture in our model we use a simple, greedy heuristic 'sorted' which starts with the start state s s and then continuously selects follow-up nodes with maximum mutual information max(I(n i , n i+1 )), where n i+1 has not been selected before. In case of a tie we prefer nodes that occur together often, i.e. P(n i+1 |n i ) is higher. 'sorted' always ends with the end state s e .

Next, we want to learn a Markov chain with states S and a transition matrix P for a name group N G. That is, we want to learn a Markov chain that represents the distribution of files and folders of all directories with the same name (see Assumption 1). To do so, we treat the sets of nodes c ∈ N GC(d) as sequence of 'observed events'. In order to capture the probabilities of the node attributes, we learn the probability that certain nodes have. Here Assumption 1 is used to cluster the group of properties.

Definition 8. The attribute model captures the frequency of occurrence of an attribute value within a name group. It is a function from N to probability measures P over the domain of a. P is defined as:

P a,N G(n) (x) = #{n ∈ N G(n) | a(n ) = x} #N G(n)
and the attribute model AM as:

AM (n, a) = P a,N G(n)
Finally, using the previous definitions we define our decoy model as follows:

Definition 9. The decoy model DM comprises the tree model T M and attribute model AM . Intuitively, the tree model captures the learned, normalized directory structure, whereas the attribute model contains the learned, normalized file-and folder attributes.

Sampling decoys

A learned decoy model can be used to sample decoy project folders. First, the user chooses instantiation values for the placeholders, e.g. a project name for the decoy project. Then, the directory structure is created by a recursive random walk over the tree model. This recursive random walk starts with the Markov chain M C p , where p is the placeholder for the project name. This random walk generates a set of nodes, which represents the content of this folder. The recursion step performs random walks over the Markov chains for each of these nodes. Thereafter, we instantiate the generated directory structure, which outputs the decoy project folder. We randomly pick the attributes from the attribute model AM for each node of the directory structure. Finally, we replace all attribute placeholders with the chosen instantiation values and write the instantiated nodes as files or folders to the disk.

Validation

Decoys have several desirable properties ( [START_REF] Bowen | Baiting inside attackers using decoy documents[END_REF], [START_REF] Whitham | Design requirements for generating deceptive content to protect document repositories[END_REF]), but the most important one is believability, i.e. capable of eliciting belief or trust [START_REF] Bowen | Baiting inside attackers using decoy documents[END_REF]. Therefore, we have conducted a user study to validate whether human judges are able to distinguish between real projects and decoys. To conduct the experiments, we have implemented a prototype of our approach in Python 2.7.

Survey setup. In this study, we presented 30 software project folders to 27 human judges. Half of the presented software project folders were generated using our prototype, the other half were real project directories. The study participants were asked to decided which ones were real and which ones were decoys. The software project folders were shared on-line and the participants could click around freely within the projects.

We learned three different decoy models, one for Java projects, one for Python projects and one for Ruby on Rails projects. We chose three different project types to identify differences in the trained model and the effect of the believability of the decoy. In total we used 25 open source projects for each project type to learn the decoy models. The number 25 was determined using trial and error and based on believability and variability of the generated decoy projects. The "real" projects that we use for training were different from the "real" ones that we presented to the survey participants. We obtained the projects by searching GitHub for certain terms, e.g. "Java and Security" and chose popular projects to related topics. Since evaluating 30 projects would take a long time, the study was split into three parts, one for each project type. Each participant was free to chose which of the parts and the number of parts they wanted to complete. Each partial surveys contained a section with demographic questions.

We recorded the answers to the surveys as well as the clicks of the participants within the folders. We neither counted survey answers where we did not have any corresponding clicks nor clicks on folders that could not be correlated to participants of the study. The data was collected within the period from February 1st to February 8th in 2016.

In total, we had 27 unique participants and we have collected 23 complete surveys for Java, 19 for Python and 15 for Rails projects resulting in 570 answers. We rejected 27 answers where the monitoring showed that the corresponding project was not looked at by this user. Thus in total we collected 543 valid judgments.

The majority of our study participants (81.5%) was highly educated, i.e. had a college or post graduate degree and also most of them (70.37%) rated their own software development skills as average or better. Most of the participants (78.3% / 68.3%) who responded to the Java and Python part of survey stated that they have at least some knowledge of the Java programming language / Python programming language respectively, whereas only 20 percent of the participants had some knowledge of the Rails framework. On average participants rated their Java, Python and rails framework knowledge respectively as 2.87, 2.43 and 1.40 on a scale from 1 to 5 with 5 being the highest.

To avoid participants' bias towards project names, we replaced the project names that occurred in all files and folders of a project with a randomly numbered placeholder of the form Pxx, where xx was a randomly chosen number between 01 and 20. The study participants were informed about this measure. Apart from that, the participants knew that they were presented partially generated and partially real folder listings. To counter any bias originating from this knowledge, we phrased the evaluation question in a non-suggestive way, i.e.: "The number of real/decoy projects does not necessarily have to be balanced. There may be 0 real projects, there may also be up to 10 real projects.". Survey results. In total, of the 543 valid answers 271 were on real projects and 272 were on decoy projects. 143 of the answers on real projects labeled them correctly as real and 128 declared them as decoys (52.7%). 135 of the answers on decoys labeled them incorrectly as real and 137 were correctly identified as decoys (50.37%). The average accuracy per project type was 52.19% correct answers for Java projects, 53.63% for Python projects and 46.32% for Rails projects. In total 51.20% of the 543 answers were correct.

The minimum recorded accuracy of the individual judges was 30%, and about a quarter of the participant's accuracies were below 50% total accuracy while the highest accuracy was 90%. The total average individual performance was 53.3%, which is slightly better than random guessing.

Discussion and Limitations

We have presented a data driven approach to create decoy project folder. These decoys may aid detecting potential data theft attacks by placing them closely monitored between real projects. A perfect decoy would be indistinguishable from the object it tries to mimic, therefore ideally the performance of the judges should be close to random guesses. In our believability study, the participants were able to identify real projects and decoys in 51.57% of the answers, which suggests that they had difficulty distinguishing generated projects from real ones.

We have empirically shown that the generated decoys are perceived as believable, however, we did so in a limited way. We did not take into account some of the external factors that can influence the believability of the decoy, for example the context where a decoy is deployed, the choice of source projects that are used to train the decoy model as well as the choice of projects that decoys will be compared to during the study. In order to more properly interpret the results of our study, further investigations on a wellfounded baseline are required. Finally, we have to validate whether the decoys can be effectively used to detect data-thefts.

Our proposed approach has some limitations. First of all, currently we need to specify instantiation parameters such as the name of the project decoy manually. We assume that these parameters contribute to the effectiveness of our approach, thus ideally they are also learned from the source projects as well as the target context. Next, our approach will not work if an attacker already knows which project they want to steal, because then they do not need to browse other projects to determine their value. Also, in other contexts simply refusing access to the data works better than deceiving an attacker [START_REF] Biskup | For Unknown Secrecies Refusal is Better than Lying[END_REF]. Finally, potentially sensitive data could be leaked using our approach.

Conclusion and Future work

In this paper we presented a data driven approach based on first-order Markov chains that can be used to automate the generation of decoy project folders within a specific, topical context. We have implemented a prototype of this approach, generated decoy project folders and validated their perceived believability via a user study with 27 participants and 543 evaluated projects. The user study showed that the participants could only correctly identify 51.2 percent of the projects, which is only slightly better than random guessing.

To address the previously mentioned limitations and thereby improve our approach, we plan to include methods for learning and generating the patterns of existing file names so that we can create new ones. Furthermore, we believe that hybrid methods which are based on templates as well as on data could further improve the believability of the generated project folder structure. Additionally, we are investigating on methods to learn instantiation parameters such as the project name from existing sources.

While our approach has certain limitations, we envision decoy project folders being deployed as cheap, supportive measure to detect ongoing data thefts.

Definition 3 .

 3 A NameGroup N G(d) for a name d ∈ Dom name is the set nodes that have name d. A NameGroupChildren N GC(d) for a name d ∈ Dom name is a set of sets, capturing the content of these folders.

Definition 5 .Definition 6 .Definition 7 .

 567 Let d be a name d ∈ Dom name and N GC(d) the name group children of d. Then, we define the states S of the Markov Chain M C for a N GC with: S = ( c∈N GC(d) c) Furthermore, we will refer to a Markov chain M C that for the NameGroupChildren of a node N GC(d) as M C d . Next, we estimate transition probabilities of M C d . Let us assume that each c ∈ N GC(d) has been sorted by the heuristic which was introduced in Definition 4. Then the transition probabilities P for two successive nodes n i ,n i+1 of a Markov chain M C d are estimated using a Maximum Likelihood Estimators, using each c ∈ N GC(d) as an observed sequence of events. So far we have modeled single directories. A tree model captures a whole directory tree. The tree model TM is a function that maps a name d ∈ Dom name to a corresponding Markov chain M C d . T M : d → M C d

Acknowledgements

This work has been partially funded by the Dutch national program COMMIT under the THeCS project.