Ariel Stolerman

Rebekah Overdorf

Sadia Afroz

Rachel Greenstadt

Breaking the Closed-World Assumption in Stylometric

Keywords: Forensic stylometry, authorship attribution, authorship verification

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The web is full of anonymous communications that are often the focus of digital forensic investigations. Forensic stylometry is used to analyze anonymous communications in order to "de-anonymize" them. Classic stylometric analysis requires an exact set of suspects in order to perform reliable authorship attribution, settings that are often not met in real-world problems. This paper breaks the closed-world assumption and explores a novel method for forensic stylometry that addresses the possibility that the true author is not in the set of suspects.

Stylometry is a form of authorship recognition that relies on the linguistic information found in a document. While stylometry existed before computers and artificial intelligence, the field is currently dominated by artificial intelligence techniques such as neural networks and statistical pattern recognition. State-of-the-art stylometric approaches can identify individuals in sets of 50 authors with better than 90% accuracy [START_REF] Abbasi | Writeprints: A stylometric approach to identity-level identification and similarity detection in cyberspace[END_REF], and even scaled to more than 100,000 authors [START_REF] Narayanan | On the feasibility of Internet-scale author identification[END_REF]. Stylometry is currently used in intelligence analysis and forensics, with increasing applications in digital communications analysis. The increase in rigor, accuracy and scale of stylometric techniques has led legal practitioners to turn to stylometry for forensic evidence [START_REF] Juola | Stylometry and immigration: A case study[END_REF], albeit stylometry is considered to be controversial at times and may not be admitted in court [START_REF] Clark | Forensic Stylometric Authorship Analysis Under the Daubert Standard, University of the District of Comumbia[END_REF].

The effectiveness of stylometry has key implications with regard to anonymous and pseudonymous speech. Recent work has exposed limits on stylometry through active circumvention [START_REF] Brennan | Adversarial stylometry: Circumventing authorship recognition to preserve privacy and anonymity[END_REF][START_REF] Mcdonald | Use fewer instances of the letter "i:" Toward writing style anonymization[END_REF]. Stylometry has thus far focused on limited, closed-world models. In the classic stylometry problem, there are relatively few authors (usually fewer than 20 and nearly always fewer than 100), the set of possible authors is known, every author has a large training set and all the text is from the same genre. However, real-world problems often do not conform to these restrictions.

Controversial pseudonymous documents that are published on the Internet often have an unbounded suspect list. Even if the list is known with certainty, training data may not exist for all suspects. Nonetheless, classical stylometry requires a fixed list and training data for each suspect, and an author is always selected from this list. This is problematic for forensic analysts who have no way of knowing when widening their suspect pool is required, as well as for Internet activists who may appear in the suspect lists and be falsely accused of authorship.

This paper explores a mixed closed-world and open-world authorship attribution problem with a known set of suspect authors, but with some probability (known or unknown) that the author is not in the set.

The primary contribution of this paper is the novel classify-verify (CV) method, which augments authorship classification with a verification step and obtains similar accuracy on open-world problems as traditional classifiers in closed-world problems. Even in the closed-world case, CV can improve results by replacing wrongly identified authors with "unknown." The method can be tuned to different levels of rigidity to achieve the desired false positive and false negative error rates. However, it can also be automatically tuned, whether or not the expected proportion of documents by authors in the suspect list versus those who are absent is known.

CV performs better in adversarial settings than traditional classification. Previous work has shown that traditional classification performs near random chance when faced with writers who change their styles. CV filters most of the attacks in the Extended-Brennan-Greenstadt Adversarial Corpus [START_REF] Brennan | Adversarial stylometry: Circumventing authorship recognition to preserve privacy and anonymity[END_REF], an improvement over previous work that requires training on adversarial data [START_REF] Afroz | Detecting hoaxes, frauds and deception in writing style online[END_REF].

This paper also presents the sigma verification method, which is based on Noecker and Ryan's [START_REF] Noecker | Distractorless authorship verification[END_REF] distractorless verification method that measures the distance between an author and a document. Sigma verification incorporates pairwise distances within an author's documents and the standard deviations of the author's features. Although it is not proven to statistically outperform the distractorless method in all scenarios, it has been shown to be a better alternative for datasets with certain characteristics.

Problem Statement

The closed-world stylometry or authorship attribution problem is: given a document D of unknown authorship and documents by a set of known authors A = {A 1 , ..., A n }, determine the author A i ∈ A of D. This problem assumes that the author of D is in A.

The open-world stylometry problem is: given a document D, identify the author of D.

Authorship verification is a slightly relaxed version: given a document D and an author A, determine whether or not D is written by A.

The problem explored in this paper is a mixture of the two problems above: given a document D of unknown authorship and documents by a set of known authors A, determine the author A i ∈ A of D or that the author of D is not in A. This problem is similar to the attribution problem but with the addition of the class "unknown." An extended definition includes p = P r[A D ∈ A], the probability that the author of D is in the set of candidates.

In the remainder of this paper, test documents are examined in two settings: when the authors of the documents are in the set of suspects, denoted by "in-set," and when the documents are by an author outside the suspect set, denoted by "not-in-set."

Applying closed-world stylometry in open-world settings suffers from a fundamental flaw: a closed-world classifier always outputs some author in the suspect set. If it outputs an author, it merely means that the document in question is written in a style that is more similar to that author's style than the other suspects, and the probability estimates of the classifier reflect only the suspect who is the "least-worst" choice.

Meanwhile, the absence of the document author from the set of suspects remains unknown. This problem is significant in online domains where the number of potential suspects can be virtually unbounded. Failing to address the limitations of closed-world models can result in falsely-attributed authors with consequences for both forensic analysts and innocent Internet users.

Related Work

Open-world classification deals with scenarios in which the set of classes is not known in advance. Approaches include unsupervised, semi-supervised and abstaining classification. Unsupervised stylometry clusters instances based on their feature vector distances [START_REF] Abbasi | Writeprints: A stylometric approach to identity-level identification and similarity detection in cyberspace[END_REF]. Semisupervised methods are used to identify clusters [START_REF] Sorio | Open world classification of printed invoices[END_REF] that are later used in supervised classification. Abstaining classifiers refrain from classification to improve classifier reliability in certain situations, for example, to minimize the misclassification rate by rejecting the results when the confidence of the classifier is low [START_REF] Chow | On optimum recognition error and reject tradeoff[END_REF][START_REF] Herbei | Classification with reject option[END_REF]. The CV method is an abstaining classifier that rejects/accepts an underlying classifier output using a verification step based on the distance between the test author and the predicted author. The novelty of this approach is that, unlike other techniques, CV considers the open-world situation where the author may not be in the suspect set.

Another method is to create a model of the closed-world and reject everything that does not fit the model. In biometric authentication systems, such distance-based anomaly detection methods perform well [START_REF] Araujo | User authentication through typing biometrics features[END_REF].

In authorship classification, one of the authors in a fixed suspect set is attributed to the test document. Current stylometry methods achieve in excess of 80% accuracy with 100 authors [START_REF] Abbasi | Writeprints: A stylometric approach to identity-level identification and similarity detection in cyberspace[END_REF], more than 30% accuracy with 10,000 authors [START_REF] Koppel | Authorship attribution in the wild[END_REF] and greater than 20% precision with 100,000 authors [START_REF] Narayanan | On the feasibility of Internet-scale author identification[END_REF]. None of the methods consider the case where the true author is missing. Although stylometric techniques work well, they are easily circumvented by imitating another person or by deliberate obfuscation [START_REF] Brennan | Practical attacks against authorship recognition techniques[END_REF].

The goal of authorship verification is to determine whether or not a document D is written by an author A. This problem is harder than the closed-world stylometry discussed above. Authorship verification is essentially a one-class classification problem. Research in this area primarily employs support vector machines [START_REF] Manevitz | One-class document classification via neural networks[END_REF][START_REF] Tax | One-Class Classification[END_REF], but little work has focused on stylometry.

Most previous work addresses verification for plagiarism detection [START_REF] Clough | Plagiarism in Natural and Programming Languages: An Overview of Current tools and Technologies[END_REF][START_REF] Van Halteren | Linguistic profiling for authorship recognition and verification[END_REF]. The unmasking algorithm [START_REF] Koppel | Measuring differentiability: Unmasking pseudonymous authors[END_REF] is an example of a general approach to verification, which relies on the "depth-of-difference" between document and author models. The algorithm yields 99% accuracy with similar false positive and false negative rates, but it is limited to problems with large training datasets.

Noecker and Ryan [START_REF] Noecker | Distractorless authorship verification[END_REF] propose the distractorless verification method, which avoids using negative samples to model the "not the author" class. They use simplified feature sets constructed only of character or word n-grams, normalized dot-product (cosine distance) and an acceptance threshold. The approach has been evaluated on two corpora [START_REF] Juola | Ad hoc Authorship Attribution Competition[END_REF][START_REF] Stein | Workshop report: Fourth International Workshop on Uncovering Plagiarism, Authorship and Social Software Misuse[END_REF] with accuracy results up to 88% and 92%, respectively. Noecker and Ryan provide a robust verification framework across different types of writings (language, genre and length independent). However, their results also suffer from low F-scores (up to 47% and 51%), which suggest a skew in the test data (testing more non-matching document-author pairs than matching ones). Section 6.2 takes a closer look at this method along with the error rates.

Corpora

The experiments described in this paper focused on two corpora, the Extended-Brennan-Greenstadt (EBG) Adversarial Corpus [START_REF] Brennan | Adversarial stylometry: Circumventing authorship recognition to preserve privacy and anonymity[END_REF] and the ICWSM 2009 Spinn3r Blog Dataset (Blog Corpus) [START_REF] Burton | Proceedings of the Third Annual Conference on Weblogs and Social Media[END_REF].

The EBG Corpus contains writings of 45 different authors, with at least 6,500 words per author. It also contains adversarial documents, where the authors change their writing styles either by imitating another author (imitation attack) or hiding their styles (obfuscation attack). Most of the evaluations in this paper are performed using the EBG Corpus.

The Spinn3r Blog Corpus from Spinn3r.com is a set of 44 million blog posts made between August 1, 2008 and October 1, 2008. The posts include the text as syndicated, as well as metadata such as the blog homepage, timestamps, etc. This dataset was previously used in Internet-scale authorship attribution [START_REF] Narayanan | On the feasibility of Internet-scale author identification[END_REF]. Our experiments used a subcorpus of 50 blogs with at least 7,500 words as the Blog Corpus. This Blog Corpus was used as control and evaluated under the same settings as the EBG Corpus in order to avoid overfitting configurations on the latter and generalizing the conclusions.

Closed-World Setup

A closed-world classifier was used throughout the research -for the baseline results used to evaluate different methods and as the underlying classifier for the CV method. The linear kernel sequential minimal opti-mization (SMO) support vector machine from Weka [START_REF] Hall | The Weka Data Mining Software: An update[END_REF] was used with complexity parameter C = 1. Support vector machines were selected due to their proven effectiveness for stylometry [START_REF] Juola | Authorship attribution[END_REF].

In addition to classifier selection, another important part of a stylometric algorithm is the feature set used to quantify the documents prior to learning and classification. The EBG Corpus was originally quantified using the Writeprints feature set [START_REF] Brennan | Adversarial stylometry: Circumventing authorship recognition to preserve privacy and anonymity[END_REF] based on the Writeprints algorithm [START_REF] Abbasi | Writeprints: A stylometric approach to identity-level identification and similarity detection in cyberspace[END_REF], which has been shown to be accurate for a large number of authors (more than 90% accuracy for 50 authors). Writeprints uses a complex feature set that quantifies the different linguistic levels of text, including lexical, syntactic and content related features; however, for simplicity, a feature set consisting of one type of feature was chosen. The EBG Corpus was evaluated using ten-fold cross validation with the k most common word n-grams or character n-grams, with k between 50 and 1,000 and n between 1 and 5. The most-common feature selection heuristic is commonly used in stylometry to improve performance and avoid over-fitting [START_REF] Abbasi | Writeprints: A stylometric approach to identity-level identification and similarity detection in cyberspace[END_REF][START_REF] Koppel | Authorship verification as a one-class classification problem[END_REF][START_REF] Noecker | Distractorless authorship verification[END_REF], as are the chosen ranges of k and n.

Character n-grams performed best, yielding the highest F1-score at approximately 0.93 (for k = 400 and higher). The word and character feature sets both outperformed the original EBG evaluation with Writeprints (F1-score of 0.832 [START_REF] Brennan | Adversarial stylometry: Circumventing authorship recognition to preserve privacy and anonymity[END_REF]). We chose the 500 most common character bigrams as the feature set (F1-score of 0.928) for all the experiments; this is denoted by ⟨500, 2⟩-Chars. The choice was made due to its simplicity, performance and effectiveness. Note that ⟨500, 2⟩-Chars also outperformed Writeprints on the control corpus with an F1-score of 0.64 compared with 0.509. All the feature extractions were performed using the JStylo [START_REF] Mcdonald | Use fewer instances of the letter "i:" Toward writing style anonymization[END_REF] and JGAAP authorship attribution framework APIs.

Verification

Authorship verification seeks to determine if a document D is written by an author A. Two naïve approaches suggest themselves. The first and most intuitive is to reduce the problem to closed-world settings by creating a model for not-A (simply from documents not written by A) and to train a binary classifier. This method suffers from a fundamental flaw: if D is attributed to A, it merely means that D's style is less distant from A than it is from not-A. The second approach is to train a binary model of D versus A, and test the model on itself using cross-validation. If D is written by A, the accuracy should be close to random due to the indistinguishability of the models. However, this method does not work well and requires D to contain a substantial amount of text for cross-validation, an uncommon privilege in real-world scenarios.

The following sections discuss and evaluate several verification methods. The first family of methods comprises classifier-induced verifiers, which require an underlying (closed-world) classifier and utilize its class probabilities output for verification. The second family of methods comprises standalone verifiers, which rely on a model built using author training data, independent of other authors and classifiers. Two verification methods are evaluated. The first is the distractorless verification method [START_REF] Noecker | Distractorless authorship verification[END_REF] denoted by V . It is presented as a baseline because it is a straightforward verification method that has been shown to be robust across different domains and does not use a distractor set (model of not-A). The second is the novel sigma verification method, which applies adjustments to V for increased accuracy: adding per-feature standard deviation normalization (denoted by V σ ) and adding per-author threshold normalization (denoted by V a ). Finally, V is evaluated and compared with its new variants.

Classifier-Induced Verification

A promising aspect of the closed-world model that can be used in open-world scenarios is the confidence in solutions provided by distancebased classifiers. A higher confidence in an author may, naturally, indicate that the author is a suspect while a lower confidence may indicate that he is not and this problem is, in fact, an open-world one.

Following classification, verification can be formulated simply by setting an acceptance threshold t, measuring the confidence of the classifier in its result, and accepting the classification if it is above t.

Next, we discuss several verification schemes based on the classification probabilities output by a closed-world classifier. For each test document D with suspect authors A = {A 1 , ..., A n }, a classifier produces a list of probabilities P A i which is, according to the classifier, the probability D is written by A i ( n i=1 P A i = 1). We denote the probabilities P 1 , ..., P n as the reverse order statistic of P A i , i.e., P 1 is the highest probability given to some author (chosen author), P 2 the second highest, and so on.

These methods are obviously limited to classify-verify scenarios because verification is dependent on classification results (thus, they are not evaluated in this section, but in Section 8 as part of the CV evaluation). For this purpose and in order to extract the probability measurements required by the following methods, SMO support vector machine classifiers were used with the ⟨500, 2⟩-Chars feature set for all the experiments described in Section 8. Logistic regression models were fitted to the support vector machine outputs to obtain proper probability estimates.

The following classifier-induced verification methods are evaluated:

P 1 :
This measurement is simply the classifier probability output for the chosen author, namely P 1 . The hypothesis behind this measurement is that as the likelihood that the top author is the true author increases, relative to all others, so does its corresponding probability.

P 1 -P 2 -Diff : This measurement captures the difference between the classifier probability outputs of the chosen and second-choice authors, i.e., P 1 -P 2 ; it is referred to as the P 1 -P 2 -Diff method.

Gap-Conf : In the case of the gap confidence method [START_REF] Paskov | A Regularization Framework for Active Learning from Imbalanced Data[END_REF], one support vector machine classifier is not trained; instead, for all n authors, the corresponding n one-versus-all support vector machines are trained. For a given document D, each classifier i produces two probabilities: the probability that D is written by A i and the probability that it is written by an author other than A i .

For each i, if p i (Yes|D) denotes the probability that D is written by A i , then the gap confidence is the difference between the highest and second-highest p i (Yes|D), which we denote briefly as Gap-Conf. The hypothesis is similar to P 1 -P 2 -Diff : the probability of the true author should be much higher than that of the second-best choice.

Standalone Verification

The following methods are evaluated:

Distractorless Verification (V ): As discussed above, V uses the straightforward distance combined with a threshold: set an acceptance threshold t, model document D and author A as feature vectors, measure their distance and determine that D is written by A if it is below t.

For n denoting the size of the chosen feature set, a model M = ⟨m 1 , m 2 , ..., m n ⟩ is built from the centroid of the character or word n-gram feature vectors of A's documents. For each i, m i is the average relative frequency of feature i across A's documents, where the relative frequency is used to eliminate document length variation effects. In addition, a feature vector F = ⟨f 1 , f 2 , ..., f n ⟩ is extracted from D, where f i corresponds to the relative frequency of feature i in D.

Finally, a distance function δ and a threshold t are set, such that if δ(x, y) < δ(x, z), x is considered to be closer to y than to z. A normalized dot-product (cosine distance) is used:

δ(M, F ) = M • F ∥M ∥∥F ∥ = n i=1 m i f i n i=1 m 2 i n i=1 f 2 i .
This measure has been shown to be effective for stylometry [START_REF] Noecker | Cosine distance nearest-neighbor classification for authorship attribution[END_REF] and efficient for large datasets. Note that "closer to" is defined using > instead of <, which is consistent with the cosine distance (where a value of one is a perfect match). However, we use < as the more intuitive direction (according to which a smaller distance means a better match), and adjust the cosine distance δ in the equation above to 1δ.

The threshold t is set such that D is written by A is determined when δ(M, F ) < t. Ideally, it is empirically determined by analysis of the average δ between the author's training documents; however, the evaluation in [START_REF] Noecker | Distractorless authorship verification[END_REF] uses a hardcoded threshold that does not take the author-wise δ values into account (which V a does, as shown below).

Per-Feature SD Normalization (V σ ): The first suggested improvement to V is based on the variance of the author's writing style. If an author has a style that does not vary much, a tighter bound for verification is required, whereas for a more varied style, the model can be loosened to be more accepting. To do so, the standard deviation (SD) of an author on a per-feature basis is used. For each author, the SD of all of the author's features is determined. When computing the distance between an author and a document, each feature-distance is divided by its SD, so if the SD is smaller, then A and D move closer together, otherwise they move farther apart. This idea is applied in [START_REF] Araujo | User authentication through typing biometrics features[END_REF] for authentication using typing biometrics; however, its application to stylometric verification is novel.

Per-Author Threshold Normalization (V a ): The second proposed improvement is to adjust the verification threshold t on a per-author basis based on the average pairwise distance between all the author's documents; this is denoted by δ A . V does not take this into account and instead uses a hard threshold. Using δ A to determine the threshold is, intuitively, an improvement because it accounts for the spread of the documents written by an author. This allows the model to relax if the author has a more varied style. As in the case of V , this "varying" threshold is still applied by setting a fixed threshold t across all authors, determined empirically over the training set. However, for V a , every authordocument distance measurement δ is adjusted by subtracting δ A before being compared with t, thus allowing per-author thresholds but still requiring the user to set only one fixed threshold value.

The three methods described above were evaluated based on their false positive (F P ) and false negative (F N) rates measured on the EBG Corpus and the Blog Corpus as control. The EBG Corpus was evaluated only on the non-adversarial documents, and the Blog Corpus was evaluated in its entirety. Ten-fold cross-validation with the ⟨500, 2⟩-Chars feature set was used; the author models were built using the training documents. In each fold, every test document was tested against every one of the author models, including its own (trained on other documents by the author).

When applied to the EBG Corpus, V σ significantly outperformed V for F P ≥ 0.05 with a confidence level of p-val < 0.01. Similarly, V a σ outperformed V for F P ≥ 0.114. However, different results were obtained for the Blog Corpus, where V significantly outperformed both V σ and V a σ . The differences could be explained by the corpora characteristics: the EBG Corpus is a cleaner and more stylistically consistent corpus consisting of all English formal writing samples (essays originally written for business or academic purposes), whereas the Blog Corpus contains less structured and formal language, which reduces the distinguishable effects of style variance normalization. This notion is supported by the better performance for the EBG Corpus compared with the Blog Corpus (larger area under the receiver operator curve). Clearly, the results suggest that one method is not preferred over the other, and selecting a verifier for a problem should rely on empirical testing over stylistically similar training data.

For both corpora, V a σ outperformed V σ starting at F P = 0.27 and F P = 0.22 for the EBG and Blog Corpora, respectively. These properties allow verification approaches to be used according to need, dependent on the F P and F N error rate constraints that a specific problem may impose.

Classify-Verify

The CV method employs an abstaining classifier [START_REF] Chow | On optimum recognition error and reject tradeoff[END_REF], i.e., a classifier that refrains from classification in certain cases to reduce misclassifications. CV combines classification with verification to expand closedworld authorship problems to the open-world essentially by adding the "unknown" class. Another aspect of the novelty of the CV method is the utilization of abstaining classification methods to upgrade from closedworld to open-world, where the methods for thwarting misclassifications are evaluated based on how they apply to those that originate outside the assumed suspect set, instead of simply missing the true suspect.

First, closed-world classification is applied to the document D in question and the author suspect set A = {A 1 , ..., A n } (i.e., sample documents). Then, the output of the classifier A i ∈ A is given to the verifier to determine the final output. Feeding only the classifier result to the verifier leverages the high accuracy of classifiers, which outperform verifiers in closed-world settings, thus focusing the verifier only on the top choice author in A. The verifier determines whether to accept A i or reject by returning ⊥ based on a verification threshold t. CV is essentially a classifier over the suspect set A ∪ {⊥}.

The threshold t selection process can be automated with respect to varying expected portions of in-set and not-in-set documents. The likelihood of D's author being in A, the expected in-set documents fraction, is denoted by p = P r[A D ∈ A] (making the likelihood of the expected notin-set documents 1p). In addition, p⟨measure⟩ refers to the weighted average of the measure with respect to p. For instance, p-F 1 is the weighted F1-score, weighted over F1-scores of p expected in-set documents and 1p expected not-in-set documents. Thus, the threshold t can be determined in several ways: Manual: The threshold t can be manually set by the user. The threshold determines the sensitivity of the verifier, so setting t manually adjusts it from strict to relaxed, where the stricter it is, the less likely it is to accept the classifier output. This enables the algorithm to be tuned to different settings, imposing the desired rigidity.

p-Induced Threshold: The threshold can be set empirically over the training set to maximize the target measurement, e.g., F1score, in an automated process. If p is given, then the algorithm applies cross-validation on the training data alone using the range of all relevant manually-set thresholds and chooses the threshold that yields the best target measurement. This essentially applies CV recursively on the training data one level deeper with a range of manual thresholds. The relevant threshold search range is determined automatically by the minimum and maximum distances observed in the verify phase of CV.

In-Set/Not-In-Set-Robust: If the expected in-set and not-inset documents proportion is unknown, the same idea as in the previously described threshold can be applied. Upon examining the CV F1-score curve for some p along a range of thresholds, if p increases, then it favors smaller (more accepting) thresholds, therefore the curve behaves differently for different values of p. However, all the curves intersect at one t -at which the in-set and not-in-set curves intersect. This can be utilized to automatically obtain a robust threshold for any value of p by taking the thresholds that minimize the difference between the p-F 1 and q-F 1 curves for arbitrary p, q ∈ [0, 1] (for simplicity, values of 0.3 and 0.7 are used). The robust threshold does not guarantee the highest measurement; it does, however, guarantee a relatively high expected value of the measure independent of p, and is, thus, robust for any open-world settings. This measurement is denoted by p-⟨measure⟩ R (for robust), e.g., p-F 1 R .

Figure 1 shows the flow of the CV algorithm on a test document D and a suspect set A with optional threshold t and in-set portion p.

Evaluation and Results

This section describes the evaluation methodology and the experimental results.

Evaluation Methodology

Main Experiment. The main experiment evaluated the CV method on the EBG Corpus (excluding the adversarial documents) and the Blog Corpus as control. The corpora were evaluated in two settings: when the authors of the documents under test were in the set of suspects (in-set) and when they were not (not-in-set). Each classification over n authors A = {A 1 , ..., A n } produces one of n+1 outputs: an author A i ∈ A or ⊥ ("unknown"). Therefore, when the verifier accepts, the final result is the author A i chosen by the classifier, and when it rejects, the final result is ⊥.

In the evaluation process, the CV algorithm was credited when the verification step thwarted misclassifications in in-set settings. For instance, if D was written by A, classified as B, but the verifier replaced B with ⊥, the result was considered to be true. This approach for abstaining classifiers [START_REF] Herbei | Classification with reject option[END_REF] relies on the fact that a result of "unknown" is better than an incorrect author.

The overall performance was evaluated using ten-fold cross-validation. For each fold experiment, with nine of the folds as the training set and one fold as the test set, every test document was evaluated twice: once as in-set and once as not-in-set.

For the classification phase of CV over n authors, n (n -1)-class classifiers were trained, where each classifier C i was trained on all the authors except for A i . A test document by some author A i was then classified as in-set using one of the n -1 classifiers that were trained on A i training data; for simplicity, we chose C i+1 (and C 1 for A n ). For the not-in-set classification, the classifier that was not trained on A i , i.e., C i , was employed.

For the verification phase of CV, several methods were evaluated: one standalone method (V σ for the EBG Corpus and V for the Blog Corpus), Gap-Conf, P 1 and P 1 -P 2 -Diff. V σ was used for the EBG Corpus and V for the Blog Corpus because these methods outperformed the other standalone methods evaluated per corpus as discussed in Section 6.

The more the verifiers reject, the higher the precision (because bad classifications are thrown away), but the recall decreases (as good classifications are thrown away as well), and vice-versa -higher acceptance increases recall but decreases precision. Therefore, the overall performance is measured using the F1-score, since it provides a balanced measurement of precision and recall:

F 1-score = 2 × precision × recall precision + recall where precision = tp tp + f p ; recall = tp tp + f n .
The two automatic verification threshold selection methods discussed in Section 7 were used. For the scenario in which the proportion of in-set and not-in-set is known with the in-set proportion p = 0.5 (the not-in-set proportion is 1p), we used the p-induced threshold that maximizes the F1-score on the training set. For the scenario in which p is unknown, we used the robust threshold configured as described in Section 7. In order to calculate the F1-score of evaluating the test set, the confusion matrices produced by the in-set and not-in-set evaluations were combined to form a p-weighted average matrix, from which the weighted F1-score was calculated. The p-induced F1-scores is denoted by p-F 1 and robust threshold induced F1-scores evaluated at some p is denoted by p-F 1 R .

The threshold optimization phase of the CV method discussed in Section 7 was performed using nine-fold cross-validation with the same experimental settings as in the main experiment. Since the F1-score was used to evaluate the overall performance, it was also used as the target measurement to maximize in the automatic threshold optimization phase. When p was known, the threshold that maximizes p-F 1 was selected, and when it was unknown, the robust threshold was selected as the one for which the F1-scores of different p values intersect (arbitrarily set to 0.3-F 1 and 0.7-F 1).

As a baseline, the F1-scores were compared with ten-fold cross-validation results of closed-world classification using the underlying classifier, SMO support vector machine with the ⟨500, 2⟩-Chars feature set. Let p-Base be the baseline F1-score of the closed-world classifier where the in-set proportion is p. It follows that 1-Base is the performance in pure closed-world settings (i.e., only in-set documents) and for any p ∈ [0, 1], p-Base = p • 1-Base (since the classifier is always wrong for not-in-set documents).

Adversarial Settings. To evaluate the CV method in adversarial settings, the models were trained on the non-adversarial documents in the EBG Corpus, and tested on the imitation and obfuscation attack documents to measure how well CV thwarted attacks (by returning ⊥ instead of a wrong author). In this context, ⊥ can be considered as either "unknown" or "possible-attack." The term 0.5-F 1 was measured, i.e., how well CV performed on attack documents in an open-world scenario where the verification threshold was set independent of a possible attack, tuned only to maximize performance on expected in-set and not-in-set document portions of 50% each. As a baseline, the results with standard classification using SMO support vector machine were compared with the ⟨500, 2⟩-Chars feature set.

Results

Main Experiment. For the EBG Corpus, the baseline closed-world classifier attained 1-Base = 0.928 in perfect in-set settings, which implies that 0.5-Base = 0.464. For the Blog Corpus, 1-Base = 0.64, which implies that 0.5-Base = 0.32. Figure 2 shows the 0.5-F 1 results for the CV method on the EBG and Blog Corpora, where the authors are equally likely to be in-set or not-in-set (p = 0.5) and the verification thresholds were automatically selected to maximize 0.5-F 1. For the EBG and Blog Corpora, the CV 0.5-F 1 results significantly outperform 0.5-Base (dashed lines) for all the underlying verification methods at a confidence level of p-val < 0.01. Furthermore, the results are not only better than the obviously bad 0.5-Base, but produce similar results to 1-Base, giving an overall 0.5-F 1 for open-world settings up to approximately 0.87. For the EBG Corpus, moving to open-world settings only slightly decreases the F1-score compared with the closed-world classifier performance in closed-world settings (dotted line in Figure 2), which is a reasonable penalty for upgrading to open-world settings. However, for the Blog Corpus, where the initial 1-Base is low (0.64), CV manages to upgrade to open-world settings and outperform 1-Base. These results suggest that out of the in-set documents, many misclassifications were thwarted by the underlying verifiers, leading to an overall increase in the F1-score.

Next, the robust threshold selection scheme was evaluated. In this scenario, the portion of in-set documents p was not known in advance. Figure 3 shows the p-F 1 R results for the EBG and Blog Corpora, where different p scenarios were "thrown" at the CV classifier with robust verification thresholds. The expected portion of in-set documents p var- deception detection results reported in [START_REF] Afroz | Detecting hoaxes, frauds and deception in writing style online[END_REF] with F1-scores of 0.895 for imitation and 0.85 for obfuscation attacks. A major difference is that the results in this paper were obtained in open-world settings with a threshold configuration that does not consider inside-attacks. Moreover, unlike the methods applied in [START_REF] Afroz | Detecting hoaxes, frauds and deception in writing style online[END_REF], no attack documents were used as training data. Interestingly, the results presented above were obtained for a standard p = 0.5 open-world scenario, without possible attacks in mind. Still, the overall results were affected very little, if at all, depending on the underlying verifier. For example, when using Gap-Conf, 0.5-F 1 is at 0.799 in non-attack scenarios and the F1-scores range from 0.784 to 0.826 under attack.

Discussion

The evaluation results suggest that classifier-induced verifiers consistently outperform standalone verifiers. However, this trend may be limited to large datasets with many suspect authors in the underlying classifier, like those evaluated in this paper, on which classifier-induced verifications rely. It may be the case that standalone verifiers perform better for small author sets; this direction should be explored in future research. Moreover, standalone verifiers provide reasonable accuracy that enables them to be used in pure one-class settings, where only true author data exists (a scenario in which classifier-induced methods are useless).

The CV 0.5-F 1 results for the EBG and Blog Corpora (Figure 2) suggest that using P 1 or P 1 -P 2 -Diff as the underlying verification method yield domain-independent results for which 0.5-F 1 is approximately 0.87.

The superiority of P 1 -P 2 -Diff is emphasized by the p-F 1 R results in Figure 3, where p-F 1 R over 0.7 is obtained for both corpora independent of p. Therefore, P 1 -P 2 -Diff is a robust, domain and in-set/not-in-set proportion independent verification method to be used with CV.

CV is effective in adversarial settings, where it outperforms the traditional closed-world classifier without any training on adversarial data (which is required in [START_REF] Afroz | Detecting hoaxes, frauds and deception in writing style online[END_REF]). Furthermore, no special threshold tuning is needed to achieve this protection, i.e., standard threshold selection schemes can be used for non-adversarial settings while still thwarting most attacks. Finally, it appears that the results in adversarial settings can potentially be improved if p is tuned not to the likelihood of in-set documents, but to the likelihood of an attack.

Conclusions

From a forensic perspective, the possibility of authors outside the suspect set renders closed-world classifiers unreliable. In addition, whether linguistic authorship attribution can handle open-world scenarios has important privacy ramifications for authors of anonymous texts and individuals who are falsely implicated by erroneous results. Indeed, when the closed-world assumption is violated, traditional stylometric approaches do not fail in a graceful manner.

The CV method proposed in this paper can handle open-world settings where the author of a document may not be in the training set, and can also improve the results in closed-world settings by abstaining from low-confidence classification decisions. Furthermore, the method can filter attacks as demonstrated on the adversarial samples in the EBG Corpus. In all these settings, the CV method replaces wrong assertions with the more honest and useful result of "unknown."

The CV method is clearly preferable to the standard closed-world classifier. This is true regardless of the expected in-set/not-in-set ratio, and in adversarial settings as well. Moreover, the general nature of the CV algorithm enables it to be applied with any stylometric classifiers and verifiers.

Our future research will pursue three avenues. The first is to apply the CV method to other problems such as behavioral biometrics using, for example, the Active Linguistic Authentication dataset [START_REF] Juola | A dataset for active linguistic authentication[END_REF]. The second is to attempt to fuse verification methods using the Chair-Varshney optimal fusion rule [START_REF] Chair | Optimal data fusion in multiple sensor detection systems[END_REF] to reduce error rates. The third avenue is to investigate the scalability of the CV method to large problems while maintaining its accuracy.

Figure 1 .

 1 Figure 1. CV method flow.

Figure 2 .

 2 Figure 2. 0.5-F 1 results for the EBG Corpus (left) and Blog Corpus (right).

Figure 4 .

 4 Figure 4. F1-scores for the EBG Corpus under imitation and obfuscation attacks.

ied from 10% to 90% and was assumed to be unknown, and robust p-independent thresholds were used for the underlying verifiers.

In the robust thresholds scenario with the EBG Corpus, CV still significantly outperforms the respective closed-world classifier (p-Base results) for p < 0.7 with any of the underlying verifiers at a confidence level of p-val < 0.01. For the Blog Corpus, CV significantly outperforms p-Base using any of the classifier-induced verifiers for all p at a confidence level of p-val < 0.01.

Moreover, the robust threshold selection hypothesis holds true, and for both corpora all the methods (with the exception of V on the Blog Corpus) manage to guarantee a high F1-score at approximately 0.7 and above for almost all values of p. For the EBG Corpus, at p ≥ 0.7 the in-set portion is large enough that the overall p-Base becomes similar to p-F 1 R . For the Blog Corpus, using V fails and has a similar performance as 0.5-Base.

P 1 -P 2 -Diff is the preferred verification method. It consistently outperforms the other methods across almost all values of p for both corpora, which implies that it is robust to domain variation.

Adversarial Settings. Evaluated on the EBG Corpus under imitation and obfuscation attacks, the baseline closed-world classifier yields F1-scores of 0 and 0.044 for the imitation and obfuscation attack documents, respectively. The results imply that the closed-world classifier is highly vulnerable to these types of attacks. Figure 4 shows the F1-scores for CV on the attack documents. Note that all attack documents were written by in-set authors and were, thus, handled as in-set documents.

The results suggest that CV successfully manages to thwart the majority of the attacks, with F1-scores up to 0.826 and 0.874 for the imitation and obfuscation attacks, respectively. These results are very close to the


Mian Ahmad Raza Cheema

Waseem Iqbal

Waqas Ali

Mian Muhammad

An Open Source Toolkit for iOS Filesystem Forensics

Keywords: Mobile phone forensics, iOS, iPhone

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The Apple iOS operating system is a Unix-like operating system based on FreeBSD. Despite the open source roots of iOS, the operating system is locked down and accessing the core Unix functions requires an iOS device such as an iPhone to be jailbroken. An iPhone has two filesystem partitions: one partition stores iOS-specific files such as kernel images and configuration files, and the other stores user-specific settings and applications [START_REF] Kubasiak | Mac OS X, iPod and iPhone Forensic Analysis[END_REF]. From a forensic perspective, the second partition is more important because it contains user applications and data. The call history, short messaging service (SMS) messages, contact list, emails, audio and video, and pictures taken with the built-in camera are all located in the second partition.

Since iOS is closed source and proprietary, general purpose forensic techniques and tools do not work on iOS devices. This paper analyzes the iOS filesystem and identifies files and directories that contain data that can aid investigations of hacking and cracking attacks launched from iPhones. The paper also describes an open source forensic toolkit and forensic procedures that can extract and analyze data stored on iPhones running iOS versions 3.1.3 through 4.3. The toolkit has been tested on an iPhone 3G running iOS version 3.1.3.

Related Work

The iOS filesystem stores a large number of relevant files in multiple locations. The files are stored in a variety of formats (both open and proprietary); therefore, without knowledge of the location and purpose of each file, a forensic investigation is bound to fail.

Companies that market forensic software for iPhones and Android devices claim that the software can securely recover data from these devices [START_REF]ElcomSoft, ElcomSoft Phone Password Breaker[END_REF]. However, because of the lack of independent verification and the closed source nature of the forensic investigation tools, the procedures used by the tools are questionable.

Schmidt [START_REF] Schmidt | iOpener: How safe is your iPhone data? The H Security[END_REF] discusses the bruteforcing of iPhone passcodes in a safe manner without any loss of data; it is not possible to guess the passcode through the graphical interface because the data is automatically erased after ten unsuccessful attempts. Zdziarski [START_REF] Zdziarski | iPhone Forensics[END_REF] has developed a custom firmware loading and acquisition method that is forensically secure. However, the tools and techniques developed by Zdziarski are only available to the law enforcement community and are applicable to the older iOS 2.x firmware versions. Hay, et al. [START_REF] Hay | Evaluating digital forensic options for the Apple iPad[END_REF] have updated Zdziarski's process to work on firmware versions through 4.x; they also provide details about the locations where valuable data resides. Mallepally [START_REF] Mallepally | Implementation of Applications to Improve iPhone Forensic Analysis and Integrity of Evidence[END_REF] discusses a number of challenges involved in extracting evidence from iOS devices, including novel anti-forensic techniques.

Implementation

Designing a forensic investigation toolkit requires care in order to ensure data integrity and that evidence is not lost. The NIST Computer Forensics Tool Testing Program for Mobile Devices [8] requires that a forensic toolkit must perform a complete data extraction and must maintain the forensic integrity of the data. The open source toolkit [START_REF] Shenoi | Open source toolkit for iPhone filesystems file analysis[END_REF] described in this paper meets both requirements. The data integrity requirement is achieved by unmounting the iOS filesystem and then copying the two partitions using the dd utility via a secure shell (SSH) connection between the phone and investigator machine over Wi-Fi. Unmounting the filesystem prevents the accidental writing of data to the filesystem and, thus, maintains forensic integrity during data extraction. The forensic toolkit is written in C#. Because iOS requires executables to be digitally signed, an iPhone must be jailbroken to circumvent this restriction and obtain root privileges. Root privileges can be gained using manual or automated jailbreaking methods. A manual method provides more control over the jailbreaking process. However, an automated method [1,[START_REF] Sigwald | Analysis of the jailbreakme v3 font exploit[END_REF] can be used because jailbreaking only changes files in the first partition. User data and other information in the second partition remain intact no matter which method is used.

After obtaining root access to the iPhone, an OpenSSH server is installed on the device. A secure shell client implemented in the forensic investigation toolkit is then used to connect to the OpenSSH server and extract data from the device to the forensic investigation machine. This process is secure because all the data is transferred through an encrypted SSH tunnel, which ensures data confidentiality and integrity Figure 1 shows a screenshot of the forensic investigation toolkit. The toolkit menu is organized as follows:

Logical Acquisition: Important files stored in the iOS filesystem are transferred from the iPhone to the forensic investigation machine. No deleted data is recovered and only the files stored in the filesystem are recovered. This type of acquisition is useful for quickly searching and retrieving evidence.

Physical Acquisition: A bit-for-bit copy of the data is obtained. This type of acquisition provides the forensic investigator with a complete copy of all the data stored on the device.

Analysis

After manually analyzing the iOS file contents, the files listed in Table 1 were identified as being relevant to iPhone investigations. The file content of interest includes address book data, SMS messages, email, images and audio/video. iPhones have been used to attack networks and the digital infrastructure [START_REF] Compton | Own with an iPhone (www.youtube[END_REF]; the installed application files listed in Table 1 are also useful for investigating these crimes.

Most of the files are in the open source SQLite database format. SQLite is an efficient and lightweight database engine. However, SQLite database files lack a trailing signature and can only be identified by their file header (53 51 4C 69 74 65 20 66 6F 72 6D 61 74 20 33 00). This makes it difficult to recover deleted files; searching for files using only the header signature yields a large number of false positives. However, our research indicates that the false positive rate is greatly reduced if the maximum file sizes listed in Table 2 are chosen.

System Information

The General.log file is the first file that should be analyzed. It contains information about the iOS version installed on the device, which is important because it provides insights into the protection measures that are in place and the vulnerabilities that can be exploited in a forensic investigation. The iOS version information can also help the forensic practitioner select the appropriate tools for data recovery and analysis. The General.log file also stores the date when the firmware was installed; this gives an estimate of how long the device has been in use.

Another important file is localtime, which contains local time settings data that is useful for developing an accurate timeline of user activity involving an iPhone.

Installed Applications

The /private/var/mobile/Library/Backup directory contains multiple .deb files. These files correspond to Debian package management system install packages; their presence indicates that they were downloaded by the user in preparation for installation on the iPhone. Even if an application is subsequently removed from the device, its down-loaded package persists until the maximum archive size specified in the apt.conf file is reached. Of particular interest in investigations are .deb files corresponding to hacking and cracking applications.

Together with the .deb archive files, the status file can be used to establish that a user not only downloaded applications but also installed them. The status file contains the status of every package ever installed on the iPhone, including applications downloaded and installed from Cydia repositories

Each installed application has a sub-directory in the /private/var /stash/Applications directory. This is useful when a user has deliberately hidden applications from the normal display. For example, applications are available for hiding applications from the SpringBoard GUI until a particular key combination or password is entered. This protection can be circumvented by examining the contents of the /private/ var/stash/Applications directory.

User Data

The most important files for investigating traditional crimes are located in the /private/var/mobile/Library/ directory. This directory and its sub-directories contain the address book, calendar, call history, SMS messages, email and web browser history.

The AddressBook.sqlitedb file contains contact information and numbers stored in the iPhone. Two tables, ABPerson and ABMulti-Value, are especially important. ABPerson contains contact names while the ABMultiValue table has the corresponding contact numbers.

The Calendar.sqlitedb file stores user calendar entries. Another important file is Call history.db, which contains the last 100 calls dialed, received and missed. The Voicemail.db file stores the sent and received voicemail messages.

The message table in the sms.db file contains the sent and received SMS messages. Data extracted from this table must be correlated with the data stored in the ABPerson and ABMultiValue tables to determine the contact information of the person who sent an SMS message. Relating the data with AddressBook.sqlitedb requires the execution of the following command line query: ATTACH DATABASE "AddressBook.sqlitedb" AS AB; ATTACH DATABASE "sms.db" AS sms; SELECT First,Last FROM AB.ABPerson WHERE rowid=(SELECT record_id FROM AB.ABMultiValue WHERE value=(SELECT address FROM sms.message WHERE text LIKE \%\%));

The DraftMessage.draft file contains SMS messages that have not yet been sent. By default, iOS does not have a draft saving feature. However, messages written using the Messages application, but that have not yet been sent are saved in this file.

Email messages are stored in the "Protected Index" file. This file has no file extension, but opening it in a hex editor and examining the header reveals that it is a SQLite database file. Two tables, messages and messages data, contain important forensic artifacts. User browsing history artifacts are found in the History.plist, SafeBrowsing.db and Cookies.plist files.

Evaluation

This section presents two use cases: one involving an iPhone seized in a traditional criminal investigation and the other involving an iPhone used in a hacking incident. The two cases highlight how the results of this research can support digital forensic investigations.

Traditional Crime Use Case: A phone is often one of the most important evidence containers in traditional crimes such as theft and murder. Traditional criminal cases typically focus on the contact list, SMS messages, email, images, audio/video and call history. Recovering data from an iPhone can be difficult if proper tools and techniques are not employed. The open source tool described in this paper was tested on an iPhone 3G with 8 GB internal storage running firmware version 3.1.3.

The first task in a forensic investigation is to jailbreak the iPhone to obtain root access and bypass the security restrictions. This should be done using offline jailbreak tools such as JailbreakMe [1], which can jailbreak iPhones up to firmware version 4.3. Jailbreaking only alters the data in the first partition; no data (including user data) residing in the second partition is modified or lost.

After the phone is jailbroken, the next step is to use the Cydia repository to install OpenSSH on the device. Then, the open source toolkit [START_REF] Shenoi | Open source toolkit for iPhone filesystems file analysis[END_REF] described in this paper is used to download the files in the /private/var/mobile/Library directory in order to perform offline analysis. The most important data is the call history, contact list, SMS messages and email, all of which are stored in SQLite files that can be analyzed with a SQLite browser (e.g., the open source SQLite Browser) or hex dump software. Audio and video files are also recovered from their sub-directories and analyzed. Hacking Incident Use Case: In the case of an iPhone involved in a hacking or cracking case, it is necessary to the analyze specific application files used in the illegal activities as well as the configuration and log parameters. Commonly-used hacking tools such as Nmap, Metasploit and Aircrack-ng can only be installed if the device has already been jailbroken. The problem is that when an iPhone is jailbroken to conduct an investigation, important log files and application files related to the incident are modified because they are also stored in the first logical partition that is affected by a jailbreaking process. Since an iPhone involved in a hacking or cracking case has already been broken to load the attack tools, there is no need to jailbreak the device and the forensic integrity of the device is not impacted.

The most important files in hacking and cracking investigations are files located in the installed application directory /private/var/ stash/Applications and the .bash history file located in the root directory. The installed application directory lists the applications installed on an iPhone (Figure 2) while the .bash history file lists all the commands executed via the terminal.

Conclusions

The Apple iPhone is a modern smartphone that provides sophisticated computing, communications and user functionality. The proprietary and closed nature of the iPhone hardware and software greatly complicates forensic recovery and analysis. The analysis of the iOS filesystem has identified files and directories that contain evidentiary data of interest to traditional criminal investigations as well as investigations of hacking and cracking attacks launched from an iPhone. The open source forensic toolkit described in this paper is specifically designed to extract and analyze evidentiary data stored on iPhones running iOS versions 3.1.3 through 4.3.

Figure 1 .

 1 Figure 1. Screenshot of the forensic investigation toolkit.

Figure 2 .

 2 Figure 2. Applications installed on an iPhone.

Table 1 .

 1 iOS filesystem evidence files. After the bit-for-bit copy is obtained, the Scalpel open source forensic data carving tool is used to recover deleted data.

	File Name	File Location	Description
	General.log	/Library/logs/	iPhone firmware information
		AppleSupport/
	localtime@	/private/var/db/timezone/ Local time zone configura-
			tion details
	*.deb	/private/var/mobile/	Downloaded application in-
		Library/Backup	stall packages
	Status	/private/var/lib/dpkg/	Application installation sta-
			tus
	Each directory	/private/var/stash/	Install location of each appli-
		Applications/	cation
	AddressBook	/private/var/mobile/	User contact list
	.sqlitedb	Library/AddressBook/
	Calendar.sqlite	/private/var/mobile	User calendar data
		/Library/Calendar/
	Call history.db	/private/var/mobile	Details of the last 100 calls
		/Library/CallHistory/	placed, received and missed
	Voicemail.db	/private/var/mobile	Information about voicemail
		/Library/voicemail/	senders
	sms.db	/private/var/mobile	Default SMS database file
		/Library/SMS/	containing SMS messages
			sent and received
	DraftMessage.	/private/var/mobile	SMS messages written in the
	plist	/Library/Draft/PENDING	Messages application but not
		/.draft/	yet sent
	Email	/private/var/mobile	"Protected Index" file with
		/Library/Mail/	email information
	SafariHistory	/private/var/mobile	Safari browser website his-
	.plist	/Library/Safari/	tory information
	SafeBrowsing.db	/private/var/mobile	Websites visited using the
		/Library/SafeBrowsing/	Safari Safe Browsing feature
	Cookies.plist	/private/var/mobile	Website cookies saved for the
		/Library/Cookies	Safari browser
	Data Carving:

Table 2 .

 2 Recommended file sizes for data recovery.

	File Name	Type	Size
	sms.db	Default SMS file	1.2 MB to 2 MB
	AddressBook.sqlitedb Default address book	220 KB
	Notes.db	Notes file	50 KB
	Calendar.sqlitedb	Calendar entries	204 KB
	Call history.db	User call history	28 KB
	History.plist	Safari browser history	1 MB
	Voicemail.db	Voice mail information 100 KB


Nhien-An Le-Khac

Mark Roeloffs

Tahar Kechadi

FORENSIC ANALYSIS OF THE TOMTOM NAVIGATION APPLICATION

Keywords: Forensic acquisition, TomTom, GPS devices, smartphones

Exactly where an individual has been is important when attempting to forensically reconstruct an incident. With the advent of portable navigation systems and mobile phones, information about where a person has been is recorded more comprehensively than ever before. This paper focuses on the data recorded by the Android TomTom Navigation Application. It also describes how mobile device usage data can assist a digital forensic practitioner in determining where the device has been.

Introduction

Devices equipped with Global Positioning System (GPS) navigation capabilities assist motorists, pilots and sailors in determining their geographical locations and provide information such as maps, directions, alternative routes and their status, and the locations of amenities (e.g., food and fuel). Because these devices store historic navigation data, the acquisition and analysis of forensic evidence from the devices is of great interest. One of the market leaders in the domain of personal GPS navigation systems is the TomTom Portable Navigation Device (TomTom PND).

Smartphones are used for all kinds of activities, from placing calls to browsing on the Internet and playing games. But more important is the fact that users carry their smartphones wherever they go [START_REF] Barkhuus | Empowerment through seamfulness: Smartphones in everyday life[END_REF]. Smartphones often incorporate an embedded GPS chip. From a forensic perspective, this feature is very important because it is possible to know the geographical location of the device at any given time. However, a large number of diverse mobile device applications are available, each of which stores relevant data in proprietary formats. The primary chal-lenge in mobile device forensics is to extract and analyze data from these applications.

Android is currently the most widely used smartphone platform in the United States [START_REF]U.S. smartphone subscriber market share[END_REF]. One of the most popular navigation applications on Android devices is the TomTom Navigation Application (TomTom NA). It was launched in October 2012 and has been downloaded thousands of times. The application stores multiple geographical points and timestamps during navigation, making any device that uses the application very valuable in an investigation.

This paper focuses on the forensic acquisition and analysis of navigation data from the TomTom NA. A step-by-step procedure for retrieving forensic data from TomTom NA is described. Multiple driving tests with a Samsung Galaxy S3 (GT-i9300) mobile phone were conducted to locate and decode the significant files. These files contain information about favorite locations, addresses and routes. The paper also compares the data that is available in a TomTom PND and a TomTom NA.

Related Work

The vast majority of TomTom device research has focused on the TomTom PND. Analysis of a TomTom PND requires the device to be rooted in order to copy the data [START_REF] Hannay | A methodology for the forensic acquisition of the Tom-Tom One Satellite Navigation System -A research in progress[END_REF]. The process described by Nutter [START_REF] Nutter | Pinpointing TomTom location records: A forensic analysis[END_REF] extracts a physical image to retrieve the most important files, which are subsequently decoded. The retrieved files include a settings file and data residing in unallocated clusters [START_REF] Nutter | Pinpointing TomTom location records: A forensic analysis[END_REF]. The commercial tool TomTology [START_REF][END_REF] can decode images extracted from the first generation of TomTom PNDs, but not later generations of the device.

Research related to Android mobile phone forensics (see, e.g., [START_REF] Aouad | An open framework for smartphone evidence acquisition[END_REF][START_REF] Harkness | An Investigation of Mobile Phone Forensics[END_REF]) has not considered the TomTom NA. To our knowledge, this is the first effort to focus on the TomTom NA used in Android smartphones.

Methodology

Documenting the navigation data available from the TomTom NA involves three steps: (i) physical image extraction; (ii) file identification; and (iii) file decoding and analysis.

Most of the data collection was performed by planning routes, entering favorites, changing the home location, etc. in the town of Gouda, The Netherlands. Two routes in the vicinity of Gouda, approximately 3 km each, were driven while using the TomTom NA.

Physical image extraction used the UFED Physical Analyzer [START_REF]Cellebrite, UFED Touch Ultimate[END_REF]. This tool was chosen over manual bootloader methods because of their complexity and the fact that different devices require different methods.

Identifying Important Files

The files found in a mobile device are not all forensically useful, so the crucial task is to identify the files of interest. The favorite location data, address and location files were identified by comparing the images before and after entering the test data for altered files; the important files identified by the comparison procedure were designated for extraction using a forensic tool. Because many changes occur throughout the system, it was easiest to perform the comparison of mobile phone filesystems. The process of searching for important files involved three steps: (i) loading the physical image into software (e.g., UFED Physical Analyzer) that decodes the filesystem; (ii) searching for the TomTom folder using the string "tomtom;" and (iii) examining the files in the TomTom folder to identify the altered files.

File Decoding

The identified files were decoded and analyzed to determine how the data is stored within the files. Because the information is stored in the XML format, useful metadata is also present [START_REF]World Wide Web Consortium, Extensible Markup Language (XML)[END_REF]. Scripts were written to decode the files and extract the relevant information. The outputs of the scripts were presented in the form of tables to help interpret the recovered data.

Results

The TomTom NA stores most of the relevant data in base64 strings in XML files. Because of the base64 encoding, each of the strings must be decoded to become readable.

The TomTom NA also uses a consistent location data structure to identify the places of interest to a user. The location data structure includes the following components:

Location UserName: The name given (by a user) to a location (not applicable if it is an address).

Location UserPos: The position of the location in a specified coordinate system (usually decimal degrees). This is the point that the user enters into the device.

Location LocName: In the case of a street address, the street name is saved in this field. If the location is a city, the city name is stored in this field.

Location LocType: The type of the location. The following types have been identified:

-LOCTYP MAPTICK: Navigated to a "Point on Map" or to a "Latitude-Longitude."

-LOCTYP ADDRESS: Navigated to an "Address" or "Contact."

-LOCTYP HOME: Navigated to "Home."

-LOCTYP POI: Navigated to a "Point of Interest."

-LOCTYP undefined: No defined location.

-LOCTYP FAVOURITE: Navigated to a "Favorite."

-LOCTYP GPS: The current GPS location. If this is in a route stream, it is also the last known position. The current GPS position may be incorrect if there was no GPS coverage (in which case, the last known GPS location is stored).

Location CityName: The city associated with the location.

HouseNumber Number: The house number associated with the address.

There is no option to see if a location was visited, unless the Location LocType is LOCTYP GPS, in which case, the location was visited at some point in time. The relevant files and data identified include settings, favorite locations and searches, and recent destinations.

4.1

NavkitSettings.xml

The NavkitSettings.xml file contains the home locations and a range of settings.

UP HomeLocations: This item stores the home locations. The TomTom application can store multiple numbered home locations. The location with the highest number is the current home location.

TTPlusManager: This item contains all the paid subscriptions activated in the TomTom application. Some of these subscriptions are for Mobile HD traffic, TomTom Places, Free POIs, Free Maps and Free Voices. The start and end times are stored with each subscription. The TTPlusManager data type has entries for the username, password, ConnectionData LastValidTime, Connec-tionData LastConnectionTime and AccountInfo DatelastUpdate. date on the TomTom servers is off by one month. The time is correct and is in Greenwich Mean Time (GMT).

LastDockedPositionX, LastDockedPositionY, LastDocked Time: These three items reference the last docked location. Last-DockedPositionX and LastDockedPositionY contain the longitude and latitude of the last docked position in the location format. The time is stored differently from the other time records (i.e., minutes instead of seconds). Therefore, decoding requires the time to be multiplied by 60 to convert it to the time format used elsewhere in the application.

MapUpdateLastReminderDate,LastMapShareConnection

Reminder, LMGDisplayDate, LastMapShareSubscription Reminder, LastTimeTempBTEnabled: These items correspond to static dates and times. We were unable to alter the values.

UserTimeOffset: This item stores the offset (in seconds) of the clock in the mobile device. For example, when the time offset is GMT +2 (summer time in The Netherlands), the value of the variable is 7,259. Dividing the value by 3,600 results in a value of approximately 2, which corresponds to the GMT offset.

ArrivalTime: During testing, it was not possible to change the value of this item, which remained fixed at 86,401. We concluded that the value is not changed by the application.

LocalSearchService: This item contains the local search history.

A search term that is used multiple times is stored only once.

Favorites

The favorites are stored in the Favorites.ov2 file. The OV2 file also appears in TomTom PNDs and the format is documented in the TomTom API [START_REF] Tomtom | TomTom Navigator SDK (version 3.0, build 193[END_REF]. Figure 1 shows the header of an OV2 file. The first five bytes are the OV2 file header. The next four bytes at offset 0x10 are magic numbers specific to OV2 files, which are different for different Android devices. The bytes located between 0x09 and 0x0F are the same for all OV2 files.

`

Status

Entry Length Latitude Longitude Figure 2 shows an example Favorite entry. The first byte is a status byte, which indicates that the entry is a current favorite. The next four bytes denote the length of the entry (in this case, 0x35). The next eight bytes hold the longitude and latitude of the location. The user string is the last part on the entry, which is a null-terminated ASCII string. Note that the home location is not stored as a favorite.

4.3

Benelux XXXXXXXX.xml

The Benelux XXXXXXXX.xml file contains a large number of relevant fields. The XXXXXXXX in the Benelux filename is a number that is specific to a particular mobile device model. Each mobile device model is assigned a number (not necessarily unique). For example, a Samsung Galaxy S3 smartphone has the file Benelux AF7DE92B.xml.

The The most relevant items from the forensic point of view are:

EngineRecents: This item stores the recently visited locations in the location format. The locations include addresses, points of interest (POIs) and particular points on a map.

AddressRecents: While EngineRecents stores all the locations, AddressRecents only stores the locations that are addresses.

RouteStream: This item stores the departure location data, the destination location data and the departure time. If the device has a GPS lock, the departure location is the current GPS location.

If not, the last known location is stored. The departure time is dependent on the clock of the device, not the GPS time. Therefore, if the time on the device is set incorrectly, the departure time is also incorrect.

LastSelectedPoi: This item stores the last selected location (or POI) in the location format.

LastSelectedSearchItem:

The TomTom application has an option to perform a local search. The TomTom local search looks for the closest location of interest near the current location. For example, a user who wishes to find a retail store would enter the name of the store and TomTom would attempt to locate the closest stores using an Internet connection. In the local search screen, the last selected search item can be seen; this item is stored in LastSelectedSearchItem. The sub-data types are the same as for the EngineRecents data type.

RegularRouteLocHome/Work: During the research, this item was observed not to store any data. However, the name suggests that it stores a regular route to help the user plan a trip. The item could, perhaps, be used by the user to see the amount of traffic on a home/work route.

LastKnownTrueGpsPosX/PosY: These items store the last known GPS position. The GPS time is not stored.

LastSelectedPoiData: This item stores the location of the last selected POI. An inconsistency regarding the stored data is that the GPS location must be halved in order to match the GPS location format used elsewhere in the application.

Voices

The TomTom Android program includes a VoiceProvidersDatabase that contains the locations of the available audio voice files. The audio voice files, which give directions to the user, are stored in an external micro SD card when available or in the internal storage of the device. If the user storage area is not large enough, the application will not work. The voice files and map chart material are downloaded and stored the first time that the program starts. The voices feature was not investigated further because no changes were observed between routes.

Times and Dates

The TomTom PND stores little time/date information with GPS coordinates. The most interesting temporal information in a TomTom PND is the triplog data, which contains the routes that were driven, along with their dates and times. It is essentially a breadcrumb trail along which the TomTom PND was driven. The TomTom NA does not contain a triplog; thus, this highly relevant information is not available.

The only TomTom NA location-specific temporal information that is available is found in the last docked locations time and the departure time. Unfortunately, these time/date items are set by the mobile device and could be incorrect. Also in the case of the departure time, if the data type is LOCTYP GPS, it could be wrong if there was no GPS lock at that location. In short, limited time/date data is available, making it difficult to identify where a mobile device was at a certain point in time.

5.

TomTom PND versus TomTom NA

The TomTom Go 720 and TomTom Via 825 Live devices were chosen for comparison. The Go 720 is a first generation TomTom PND system. The relevant data is stored in the mapsettings.cfg file, which can be decoded by the TomTology program.

The Via 825 Live is a second generation TomTom PND. It is no longer possible to get a physical image of this device using a USB connection. Data extraction requires the chip to be removed or a proprietary non-destructive method to be used. The relevant data is stored in the mapsettings.tlv file, but other files also store data related to the data found in the first series of TomTom PNDs.

Table 1 shows the corresponding locations in TomTom PND and Tom-Tom NA where user data of interest in forensic investigations is stored.

Conclusions

The analysis of the Android TomTom NA on a Samsung Galaxy S3 smartphone provides important details about potential digital evidence. Files that contain location information for the device were identified by comparing filesystem changes between multiple physical captures. Another important contribution is the comparison of the contents of files residing in a TomTom PND and a TomTom NA. A TomTom PND stores data in a binary format while the TomTom NA uses the XML format and the base64 encoding. The TomTom PND and TomTom NA record similar user favorites and search data, which enable digital forensic practitioners to determine where the devices have been.

Future research on the TomTom NA will focus on subscription services. Some of these services, including TomTom HD traffic and the services that provide information about speed cameras and danger zones, can provide detailed information about the geographical locations visited and routes taken, and may also reveal information about user actions (e.g., speeding). Future research will also focus on TomTom NA running on other smartphones models and on recovering deleted data.

  The times for ConnectionData LastValidTime, ConnectionData LastConnectionTime and AccountInfo DatelastUpdate are off by one month and one day. Repeated observations indicated that the OV2 File Header Magic Number Same for all OV2 Files Magic Number Same for all OV2 Files

Figure 1 .

 1 Figure 1. OV2 file header.

Figure 2 .

 2 Figure 2. OV2 Favorite entry.

  most relevant portion of the Benelux XXXXXXXX.xml file is the data immediately preceding the final </string> tag.

	The XML items
	in this file include: EngineRecents; AddressRecents; NeverAskedDe-
	faultCountry; SafetyCameraWarnings; LastSelectedPoi; PoiSet; Route
	Stream; LastSelectedSearchItem; LastKnownTrueGpsPosX; LastKnown
	TrueGpsPosY; PDKAutoShutdown; PDKDisableiPodMenuIcon; Regu-
	larRouteLocHome; RegularRouteLocWork; LastSelectedPoiData; PD-
	KUseDefaultSettingsFromUserFile; TrafficOnMap; SoundVolumeHands-
	Free; TrafficAutoUpdate; TrafficAutoReplan; TaiwanCenterAvailable;
	CurrentTrafficRouteType; PoiWarnings; GeoFormat; CurrentSelected-
	CountryIndex; TrafficUpdateFrequency; UserEnabledTraffic; PoicatHot
	listCat; SupportASN; ValidPassword; PoicatHotListValidatedOnce; Poi
	catHotlistHit; UserMarkerAvailable; TrafficWarnings; EnableBT.

Table 1 .

 1 Corresponding TomTom PND and TomTom NA data locations.

	Items	First	Second	Android
		Generation	Generation	Application
	Triplogs	Statdata folder	Statdata folder	N/A
	Home Location	mapsettings.cfg userpatch.dat	NavkitSettings.xml
	Favorites	mapsettings.cfg Favorites.ov2	Favorites.ov2
	Recent	mapsettings.cfg mapsettings.tlv Benelux file
	Destinations
	Entered locations mapsettings.cfg mapsettings.tlv Benelux file
	Journeys	mapsettings.cfg mapsettings.tlv Benelux file
				with departure time
	Last Docked	mapsettings.cfg Userpatch.dat	NavkitSettings.xml
				with a timestamp
	Bluetooth	mapsettings.cfg Settings.tlv	Handled by the
	Coupled Devices			Android OS
	SIM Card Data	N/A	mobility.sim	Handled by the
				Android OS


Kristian Bredies

David Vicente

A note about the jump set of a solution of a second order PDE in BV

This paper deals with the localization of the jump set of a function with bounded variation which is also in the kernel of a second order partial differential operator. For the case where the operator is hyperbolic, this result may be interpreted as a generalization of the notion of wavefront to the space of functions with bounded variation where the classical notion of wavefront is replaced in the spatial domain by the jump set of the function and in the frequency domain by the direction of its measure theoretic normal vector.

Introduction

In this paper, we are interested in the localization of the jump set for solutions of a second order PDE which also belongs to the space of functions with bounded variation (BV). More precisely, if Ω ⊂ R d is open, A = (a i,j ) i,j is a d × d symmetric matrix and u ∈ BV(Ω) is a weak solution of the following equation where H d-1 is the d -1 dimensional Hausdorff measure, J u is the jump set of u and ν(x) is an orthonormal vector to J u at x. For the case where the matrix A is with signature (1, d -1), or equivalently if the equation (0.1) is hyperbolic, this result can be interpreted as a generalization of the notion of wavefront to the space BV. Indeed, for any x ∈ J u , it forces the surface J u to be tangent to the singular cone {x

+ v : v ∈ R d , (Av) • v = 0}.
The authors do not know if such a result is original (probably it is not). However, in the context of Inverse Problem and Image Processing such a result is needed and its proof is not so long.

Section 1 is devoted to introduce the BV framework and some useful properties of geometric measure theory. Section 2 is devoted to the statement and the proof of our result.

Notations

In all this paper, we assume that Ω ⊂ R d is an open, connected and bounded domain with Lipschitz boundaries. Moreover, we denote • the ball with center x and radius ρ by B ρ (x),

• the Lebesgue measure with dimension k by L k ,

• the Hausdorff measure with dimension k by H k ,

• the trace of a measure µ onto a set A by µ A.

Measure theory framework and fine properties on space BV

We need the following consequence of Besicovitch Covering Theorem (Theorem 2.22 in [START_REF] Fusco | Functions of Bounded Variation and Free Discontinuity Problems[END_REF]). Then, for µ-a.e. x in the support of µ the limit

f (x) = lim ρ→0 + ν(B ρ (x)) µ(B ρ (x))
exists in R d and moreover, the Radon-Nikodym decomposition of ν is given by ν = f µ + ν s , where ν s ⊥ µ.

A set E ⊂ R d is countably H d-1 rectifiable if there exists a countable family of Lipschitzian functions Ψ i : A i → R d such that, for any i, A i ⊂ R d-1 is bounded and

H d-1 E \ i Ψ i (A i ) = 0.
We need a locally univalent description of rectifiable sets. For that, we introduce the following result which may be found in [START_REF] Federer | Geometric Measure Theory[END_REF] (Lemma 3.2.18).

Lemma 1.1. If W is a countably H d-1 rectifiable and H d-1 measurable subset of R d , and if 1 < λ < ∞, then there exists compact subsets (K i ) i ⊂ R d-1 and Lipschitzian maps (Ψ i ) i of R d-1 onto R d such that (Ψ i (K i )) i are disjoints subsets of W with H d-1 W \ i Ψ i (K i ) = 0
and, for each positive integer i,

Lip(Ψ i ) ≤ λ, Ψ i |K i is univalent , Lip[(Ψ i |K i ) -1 ] ≤ λ.
Let Ψ : R d-1 → R d a Lipschtzian function. According to Rademacher Theorem, Ψ is almost everywhere differentiable. Thus, for almost every x ∈ R d-1 , one may define

J d-1 Ψ(x) = det(DΨ(x) * • DΨ(x)),
where DΨ(x) * : R d → R d-1 is the transpose of DΨ(x). So, we may introduce the Area Formula for Lipschitz functions (Theorem 3.2.3 in [START_REF] Federer | Geometric Measure Theory[END_REF]). Theorem 1.2. Let Ψ : R d-1 → R d be a Lipschtzian function. Then, if u is an integrable function with respect to the Lebesgue measure, then

R d-1 u(x)J d-1 Ψ(x)dx = R d x∈Ψ -1 {y} u(x)dH d-1 (y). A function u ∈ L 1 (Ω) is with bounded variation, u ∈ BV(Ω), if its derivative Du is a vectorial Radon measure, Du ∈ M(Ω; R d ).
The total variation of u is defined by the total mass of Du and is denoted by TV(u) = Du M . Definition 1.1. For u ∈ BV (Ω) and x ∈ Ω, we set i)

u + (x) = inf t : lim ε→0 + L d (B ε (x) ∩ {u > t}) ε d = 0 , ii) u -(x) = sup t : lim ε→0 + L d (B ε (x) ∩ {u < t}) ε d = 0 , iii) J u = {x ∈ Ω : u -(x) < u + (x)}.
For H d-1 almost every x ∈ J u , u has a measure theoretic jump across a hyperplane whose normal direction is yield by an unit normal vector ν u (x). Thus, the structure of the trace of the gradient of u in J u is the following (3.78 in [START_REF] Fusco | Functions of Bounded Variation and Free Discontinuity Problems[END_REF]) Theorem 1.3. For any u ∈ BV(Ω), we have

Du J u = (u + -u -)ν u H d-1 J u .
The jump set J u is rectifiable. More precisely, we have the following Theorem 1.4. There exists countably many compacts

(K k ) k , such that K k is included in a C 1 - hypersurface S k for any k and such that H d-1 J u \ k K k = 0. In particular, the set J u is countably H d-1 -rectifiable.
The previous result is a consequence of "Structure Theorem for sets with finite perimeter" and "Pointwise properties of BV functions" that may be found in [START_REF] Evans | Measure Theory and Fine Properties of Functions[END_REF], Sections 5.7 and 5.9. Moreover, the proof of this result, which uses "Whitney extension Theorem" gives us in addition that

ν u (x) = ν k (x), for H d-1 -a.e. x ∈ K k , (1.1)
where ν k is an unit normal vector to S k and ν u is the measure theoretic outer normal of J u .

Theorem 1.5. For H d-1 almost every x ∈ Ω, we have

-∞ < u -(x) ≤ u + (x) < +∞.
Definition 1.2. For ν ∈ S d-1 and x ∈ Ω, we define the hyperplane

H x,ν = {y ∈ Ω : ν • (y -x) = 0}
and the half-spaces

H + x,ν = {y ∈ Ω : ν • (y -x) ≥ 0}, H - x,ν = {y ∈ Ω : ν • (y -x) ≤ 0}.
Theorem 1.6. For H d-1 almost every x ∈ J u , there exists ν = ν u (x) such that

lim ε→0 + 1 L d (B ε (x) ∩ H + x,ν ) Bε(x)∩H + x,ν |u -u + (x)| d/(d-1) dy = 0 and lim ε→0 + 1 L d (B ε (x) ∩ H - x,ν ) Bε(x)∩H - x,ν |u -u -(x)| d/(d-1) dy = 0.

Jump set of a weak solution of second order PDE in BV

We introduce a weak definition of solution for a linear second order PDE which is adapted to functions with bounded variation and we establish our main result.

Definition 2.1. Let A = (a i,j ) i,j be a d × d symmetric matrix. We say that u ∈ BV(Ω) is a weak solution of i,j a i,j

∂ 2 u ∂x i ∂x j = 0 in Ω, if Ω (A∇ϕ) • dDu = 0, for any ϕ ∈ C ∞ c (Ω). (2.1)
As u ∈ BV(Ω), the derivative of u is a Radon measure and the integration in (2.1) is well defined.

Theorem 2.1. Let A = (a i,j ) i,j be a d × d symmetric matrix and u ∈ BV(Ω) be a weak solution of i,j a i,j ∂ 2 u ∂x i ∂x j = 0. Then, we have

(Aν u (x)) • ν u (x) = 0, for H d-1 -a.e. x ∈ J u .
Proof. We divide the proof in three steps. First, we compare the speed of decrease of |Du|(B ε (x)) with ε d-1 . Then, we introduce a blow-up process and compute its limit. Finally, we use the definition of weak solution in BV with an adapted choice of test functions.

Step 1: For H d-1 -almost every x ∈ J u , we have

0 < lim inf ε→0 + |Du|(B ε (x)) ε d-1 ≤ lim sup ε→0 + |Du|(B ε (x)) ε d-1 < +∞.
According to Theorem 1.4 and Lemma 1.1, for any u ∈ BV(Ω) we get

H d-1 J u \ i Ψ i (K i ) = 0,
where (Ψ i ) i , (K i ) i satisfy the conditions of Lemma 1.1. Let i be fixed and x ∈ Ψ i (K i ). As Ψ i is Lipschitzian, we may apply to the Area Formula, it gives

H d-1 (Ψ i (K i ) ∩ B ε (x)) = R d-1 1 K i ∩Ψ -1 i (Bε(x)) J d-1 Ψ i dx. Since Ψ i |K i and (Ψ i |K i ) -1 are Lipschitz with coefficient λ we get B λ -1 ε (Ψ -1 i (x)) ⊂ Ψ -1 i (B ε (x)) ⊂ B λε (Ψ -1 i (x)).
Since J d-1 Ψ i corresponds to the area element of the surface parametrized by Ψ i :

K i → R d , we have λ -(d-1) ≤ J d-1 Ψ i (x) ≤ λ d-1 , for L d-1 almost every x ∈ K i .
Thus, it yields

λ -(d-1) B λ -1 ε (Ψ -1 i (x)) 1 K i dx ≤ R d-1 1 K i ∩Ψ -1 i (Bε(x)) J d-1 Ψ i dx ≤ λ d-1 B λε (Ψ -1 i (x)) 1 K i dx.
According to Area Formula (Theorem 1.2), we get

λ -(d-1) B λ -1 ε (Ψ -1 i (x)) 1 K i dx ≤ H d-1 (Ψ i (K i ) ∩ B ε (x)) ≤ λ d-1 B λε (Ψ -1 i (x)) 1 K i dx. F = y ∈ K i : lim ε→0 + 1 πε d-1 Bε(y) 1 K i dx = 1 .
According to Theorem 1.1, K i \ F is negligible. Then, Area Formula yields 0 = R d-1

1 K i \F dx, = R d-1 1 K i \F J d-1 Ψ i dx, = H d-1 (Ψ i (K i ) \ Ψ i (F)).
So, we deduce that, for

H d-1 almost every x ∈ Ψ i (K i ), we have 0 < lim inf ε→0 + H d-1 (Ψ i (K i ) ∩ B ε (x)) ε d-1 ≤ lim sup ε→0 + H d-1 (Ψ i (K i ) ∩ B ε (x)) ε d-1 < +∞. (2.2)
In order to conclude the proof of Step 1, we split the following ratio

|Du|(B ε (x)) ε d-1 = |Du|(B ε (x)) H d-1 (Ψ i (K i ) ∩ B ε (x)) H d-1 (Ψ i (K i ) ∩ B ε (x)) ε d-1 .
For the first factor, we recognize the density ratio of the measure |Du| with respect to the measure

H d-1 Ψ i (K i ) at x. The left-hand side of Inequalities (2.2) implies that x is a density point for H d-1 Ψ i (K i )
and then, according to Theorem 1.1 and Theorem 1.3, this ratio admits as limit

u + (x)- u -(x) > 0 for H d-1 almost every x ∈ Ψ i (K i ).
According to the right-hand side of inequalities (2.2), we deduce the result of Step 1.

Step 2: We set u ε (y) = u(x + εy). For H d-1 almost every x ∈ J u , there exists

(ε k ) k converging to 0 + such that (u ε k ) k is weak-convergent to v in BV loc (R d ). Moreover, with ν = ν u (x), we have v = u -(x)1 H - 0,ν + u + (x)1 H + 0,ν .
We fix R > 0 and x ∈ J u . For ε > 0 sufficiently small, the function

u ε is defined in B R (0 R d ). First, we verify that (u ε ) ε is bounded in BV(B R (0 R d )). For ν = ν u (x), we have B R (0 R d ) |u ε |dy ≤ B R (0 R d ) |u ε | d/(d-1) dy (d-1)/d (L d (B R (0 R d )) 1/d , ≤ 1 ε d B Rε (x) |u| d/(d-1) dx (d-1)/d (L d (B R (0 R d )) 1/d . As (a + b) d/(d-1) ≤ 2 1/(d-1) (a d/(d-1) + b d/(d-1
) ), we get

B Rε (x) |u| d/(d-1) dx ≤ 2 1/(d-1) B Rε (x)∩H + x,ν |u -u + (x)| d/(d-1) dx +2 1/(d-1) B Rε (x)∩H - x,ν |u -u -(x)| d/(d-1) dx +2 1/(d-1)-1 (u + (x)) d/(d-1) + (u -(x)) d/(d-1) L d (B Rε (x)).
According to Theorem 1.6, we deduce that (u

ε ) ε is bounded in L 1 (B R (0 R d ))
. Moreover, we have

|Du ε |(B R (0 R d )) = sup B R (0 R d ) u ε (y)div(ϕ)(y)dy : ϕ L ∞ ≤ 1, supp(ϕ) ⊂ B R (0 R d ) , = sup 1 ε d B Rε (x) u(x)div(ϕ) x - x ε dx : ϕ L ∞ ≤ 1, supp(ϕ) ⊂ B R (0 R d ) , = sup 1 ε d-1 B Rε (x) u(x)div(ϕ) (x) dx : ϕ L ∞ ≤ 1, supp(ϕ) ⊂ B Rε (x) , = |Du|(B Rε (x)) ε d-1 .

According to

Step 1, we deduce that, for

H d-1 almost every x ∈ J u , (Du ε ) ε is bounded in M(B R (0 R d ); R d ). So, for any R > 0, (u ε ) ε is bounded in BV(B R (0 R d )) and then (u ε ) ε is bounded in BV loc (R d ). Ac- cording to compactness property in BV loc (R d ), there exists (ε k ) k converging to 0 + such that (u ε k ) k is weak-convergent in BV loc (R d ). With ν = ν u (x), set v = u -(x)1 H - 0,ν + u + (x)1 H + 0,ν .
Then, with R > 0 and ν = ν u (x) we have 1) dx.

B R (0 R d ) |u ε -v| d/(d-1) dy = 1 ε d B Rε (x) u(x) -v x - x ε d/(d-1) dx, ≤ 1 ε d B Rε (x)∩H + x,ν |u -u + (x)| d/(d-1) dx + 1 ε d B Rε (x)∩H - x,ν |u -u -(x)| d/(d-
According to Theorem 1.6, we deduce that, for

H d-1 almost every x ∈ J u , (u ε k ) k converges to v in L d/(d-1) loc (R d
) and then, necessary, v is the weak-limit of (u ε k ) k .

Step 3: We choose an adapted test function ϕ and we plug it in (2.1).

Let θ be a given function in

C ∞ 0 (R d ) such that θ(0 R d ) = 1, θ ≥ 0 and supp(θ) ⊂ B 1 (0 R d ). For x ∈ J u and ν = ν u (x), we set ϕ ε (x) = ν • (x -x) ε d-1 θ x - x ε .
For ε > 0 sufficiently small, we have ϕ ε ∈ C ∞ 0 (Ω) and then

Ω (A∇ϕ ε ) • dDu = 0. (2.3)
We compute

Ω (A∇ϕ ε ) • dDu = R d 1 ε d-1 θ x - x ε (Aν) • dDu + R d ν • (x -x) ε d A∇θ x - x ε • dDu
Moreover, for any Φ ∈ C ∞ 0 (B ε (x); R d ), we have As ν • y = 0 for any y ∈ H 0,ν , H 0,ν θdH d-1 > 0 and (u + -u -)(x) > 0, we may conclude that (Aν) • ν = 0, and this is true for almost every x ∈ J u .

R d Φ(y) • dDu ε (y) = - R d u ε (y)div(Φ)(y)dy, = - 1 ε d R d u(x)div(Φ) x - x ε dx, = - 1 ε d-1 R d u(x)div x → Φ x - x ε dx, = 1 ε d-1 R d Φ x - x ε • dDu.

  x)) • ν(x) = 0, for H d-1 -a.e. x ∈ J u , (0.2)

Theorem 1 . 1 .

 11 Let µ be a positive Radon measure in an open set Ω ⊂ R d and ν an R d -valued measure.

(

  A∇ϕ ε ) • dDu = R d θ(y)(Aν) • dDu ε (y) + R d ν • y(A∇θ(y)) • dDu ε (y).(2.4)According to Step 2, (Du ε k ) k is weak-convergent in M(R d ) to Dv = (u + (x) -u -(x))νH d-1 H 0,ν .According to (2.3) and passing through the limit in (2.4), we get0 = (u + -u -)(x)(Aν) • ν H 0,ν θ(y)dH d-1 (y) + (u + (x) -u -(x))H 0,ν ν • y(A∇θ(y) • ν)dH d-1 (y).

Acknowledgements

The authors are with the Institute of Mathematics and Scientific Computing, University of Graz, Austria. The Institute of Mathematics and Scientific Computing is a member of NAWI Graz (www.nawigraz.at) and BioTechMed Graz (www.biotechmed.at). This work was supported in part by the Austrian Science Fund (FWF) under grant SFB F32 (SFB "Mathematical Optimization and Applications in Biomedical Sciences").