Gregory Bosman

Stefan Gruner

Log File Analysis with Context-Free Grammars

Keywords: Intrusion detection, log file analysis, context-free grammars

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

Introduction

Most modern intrusion analysis systems rely on pattern recognition to differentiate malicious network traffic from benign traffic [START_REF] Axelsson | Intrusion Detection Systems: A Survey and Taxonomy[END_REF][START_REF] Lunt | A survey of intrusion detection techniques[END_REF][START_REF] Ning | Intrusion detection techniques[END_REF]. Anomaly-based detection systems are designed to recognize traffic generated during normal network operations. These systems use information such as source and destination addresses and ports, applications that generate traffic, and other header information to determine whether or not a packet should raise an alarm. Sometimes, the analysis proceeds one step further, scrutinizing the packets as a stream instead of just packet by packet. Signature-based analysis systems operate similarly and, in some cases, search for signatures of injected code in network packets. The search typically attempts to identify a series of bits that match certain regular expressions.

State-based analysis is a promising security approach [START_REF] Olivier | Wrappers: A mechanism to support statebased authorization in web applications[END_REF][START_REF] Zhang | A lightweight approach to statebased security testing[END_REF]. Gudes and Olivier [START_REF] Olivier | Wrappers: A mechanism to support statebased authorization in web applications[END_REF] emphasize that the state of an application should also be considered in assessing the security of an application. They reason that certain messages received by an application, while perfectly safe in one state, may compromise the security of the application should the messages be received in some other, more vulnerable state. Therefore, the state of an application should be taken into account when determining whether or not incoming data is harmful. Gudes and Olivier [START_REF] Olivier | Wrappers: A mechanism to support statebased authorization in web applications[END_REF] proposed the use of context-free grammars for state-based analysis. Their approach entails the construction of a grammar to represent the transitions from state to state internally within an application; the grammar also describes the actions that are allowable in any given state. This paper presents an enhancement of the context-free grammar approach for the purpose of intrusion detection.

Related Work

Memon [START_REF] Memon | Log File Categorization and Anomaly Analysis Using Grammar Inference[END_REF] has employed context-free grammars in a log file categorization system. Memon developed a grammar capable of representing a single packet in a data stream, including information such as packet protocol, source and destination. Also, a method of grammar inference was developed, which is capable of expanding an existing grammar modeled to identify benign packets at the discretion of an administrator. However, Memon's approach does not consider the sequencing of packets in a data stream, nor does it take into account the "statefulness" of an interaction between network applications. Also, a grammar that could capture the statefulness of applications communicating over a network would be considerably more complex than the grammars used by Memon.

The possibility of dealing with too many false alerts in automated intrusion detection systems was addressed by Harang and Guarino [START_REF] Harang | Clustering of Snort alerts to identify patterns and reduce analyst workload[END_REF]. They used various heuristics to condense a massive amount of elementary alerts into a manageable number of meta-alerts. However the alert condensation technique has limited theoretical underpinnings. Similar work by Valdez and Skinner [START_REF] Valdez | Probabilistic alert correlation[END_REF] resulted in a fusion system that groups alerts based on their similarity (near-matches) to existing meta alerts.

Method

The context-free grammar described in this paper handles a subset of malicious attack vectors. The grammar, which fits well into the digital forensics context, is related to formal methods in the field of model-based testing [START_REF] Gruner | Model-based passive testing of safetycritical components[END_REF] and may be regarded as a limited form of automated verification on the basis of specific samples. A proof goal is a decision whether or not a network intrusion attempt has occurred in a specific situation. Two types of grammars are used to tackle the problem effectively from both sides:

TRACE -> e | TRANSF | ADRESO | DNSQRY TRACED1 -> TRANSFD1 | ADRESOD1 | DNSQRY1 TRACET1 -> TRANSF1 | ADRESOT1 | DNSQRYT1 TRACET2 -> TRANSF2 | ADRESOT2 | DNSQRYT2 TRACET3 -> PDU | ADRESOT3 | DNSQRYT3 TRACET1D1 -> TRANSF1D1 | ADRESOT1D1 | DNSQRY1T1 TRACET2D1 -> TRANSF2D1 | ADRESOT2D1 | DNSQRY1T2 TRACET3D1 -> PDUD1 | ADRESOT3D1 | DNSQRY1T3 TRACEP1 -> PDU1 | ADRESOP1 | DNSQRYP1 TRACEP2 -> PDU2 | ADRESOP2 | DNSQRYP2 TRACEP3 -> PDU3 | ADRESOP3 | DNSQRYP3 TRACED1P1 -> PDU1D1 | ADRESOD1P1 | DNSQRY1P1 TRACED1P2 -> PDU2D1 | ADRESOD1P2 | DNSQRY1P2 TRACED1P3 -> PDU3D1 | ADRESOD1P3 | DNSQRY1P3 TRANSF -> syn TRACET1 TRANSF1 -> synack acko get TRACET2 TRANSF2 -> acki TRACET3 TRANSFD1 ->
Green Grammar: One green grammar is used to describe log files corresponding to harmless communications. A log file that is successfully parsed with a green grammar is regarded as "hypothetically harmless."

Red Grammars: Several red grammars are used to describe log files that contain traces corresponding to known malicious communications patterns. A log file that is successfully parsed with a red grammar is regarded as "harmful" and raises an alert. A log file that cannot be parsed with a red grammar is regarded as "hypothetically harmless."

Figures 1 and2 present the green grammar that represents acceptable traffic. The grammar was generated from experimental traffic and log files created during the use of a web browser. Each terminal symbol in the grammar represents a single packet that was recorded. The grammar as a whole models a string of packets of a "conversation" that occurs when a web page is transferred. Ideally, the conversation follows the simplified pattern:

TRACE -> syn synack acko get acki PDU PDU -> data data acko PDU | data http acko | http acko

A communication involving a browser begins with a handshake, a sequence of packets with synchronization flags or acknowledgement flags or both flags set. Next, a request is made for data transfer, a GET followed by a packet in which the acknowledgement flag is set (again). Data transfer then begins. This is represented by the protocol data unit (PDU) section. The rest is the data transfer of two packets at a time until the transfer is complete. After every two packets, an acknowledgement is sent to indicate there are no errors and that it is possible to continue with the transfer. When there is no more data, a final HTTP packet is received to indicate the end of the stream, followed by one last outgoing acknowledgement to the web server. The example pattern is an ideal model of a conversation between a client and server. In practice, however, streams tend to be interspersed with additional mini-conversations that carry meta information. For example, an initial Address Resolution Protocol (ARP) message may be sent in order to find the location of a web page. Also, in nearly every trace, there is at least one request for a Domain Name Server (DNS), which tends to jump straight into the middle of the main conversation with the web server. Therefore, an appropriate green grammar must be constructed such that it retains the internal state of a conversation when it is interrupted and returns to the original state after the interrupt.

This implies that an entire conversation must complete in order to be recognized as a benign trace. If the conversation starts, it must terminate successfully. If it does not, then the browser may have been compromised (unless the communication was technically interrupted, for example by a browser crash on the client side). In such a case, the parsing of the corresponding trace leads to a syntax error and the trace is classified as "suspicious."

It is worth noting that the mini-ARP-conversation is always completed without an interruption. However, as in the case of a web page request, a DNS request is susceptible to interruption. Unfortunately, regular expressions (unlike the more expressive context-free grammars) are inadequate to remember the status of a conversation before the occurrence of an interrupt.

Experimental Results

We conducted an experiment that used the green grammar in a controlled laboratory network setting with various permissible and nonpermissible input strings. ANTLR [START_REF] Parr | The Definitive ANTLR Reference: Building Domain-Specific Languages, Pragmatic Bookshelf[END_REF] was used to generate the parser for the green grammar. Table 1 summarizes the experimental results.

Two types of errors are of interest in the analysis:

Alpha Error (False Positive): This error is the incorrect rejection of benign input (6/100 = 6% from Table 1). An alpha error is annoying or inconvenient, but it is not harmful.

Beta Error (False Negative): This error is the incorrect acceptance of malicious input (0/100 = 0% from Table 1). A beta error is interpreted as being harmful.

Despite the zero beta error, a problem with the grammar is that not all parsing failures resulted from syntax errors, which would be the ideal case if the grammar was a priori aware of all possible input tokens. The non-zero lexical errors (errors prior to the parsing phase) show that an input stream can contain unknown symbols that the grammar does not recognize. Thus, the suitability (fit-for-purpose quality) of the intrusion detection grammar can be estimated as follows:

In the ideal alpha case, no parsing errors should occur. Since all the errors occurred during the lexical analysis phase, 100% percent of the alpha errors are from not recognizing all the symbols in the input strings.

In the ideal beta case, only parsing errors should occur. Only 72% percent of the (correct) rejection decisions were based on parsing whereas 28% percent of all rejections were based on "decisionless" lexical errors before the decision-making parsing phase. Therefore, the beta errors are estimated to be as high as 28%.

We conjecture that the errors appear in the context of the occasional mini-communications, which can be corrected for by modifying the manner in which the grammar is processed.

The experiments with malicious input streams were restricted to scenarios in which communications terminate mid-stream, as in the case of buffer overflow attacks. The parser should correctly recognize the absence of stream-closing data packets and label the stream as suspicious. However, in one case, the lexical analyzer could not recognize a termination symbol that was sent properly to terminate a conversation. This problem might be linked to speed discrepancies between data download and analysis. Specifically, the parsing unit may prematurely believe that an input stream has been "hacked" while in fact a harmless communication is in progress.

Discussion

Because context-free languages are a superclass of regular expressions and are, therefore, more complex, they have greater computational re-quirements. A critical question is whether the additional complexity provided by context-free grammars renders the approach impractical. To answer this question, more examples that cannot be treated with regular expressions must be identified. The speed of analysis is the main reason for using regular expressions with Cisco networking devices because the analysis of data streams proceeds in an online and on-the-fly manner. Regular expression analysis can be implemented in a runtimeefficient manner. However, ex post facto log file analysis does not have strict real-time processing requirements.

A practical problem is posed by interrupted communication attempts, for example, due to a crashed or frozen browser on the client side of an Internet connection. On the server side, this results in a broken trace in the log file that cannot be parsed, regardless of whether the interrupted communication is malicious or harmless. Traces of interrupted communication attempts could increase the rate of alpha errors. To tackle this problem, a method is needed to divide a large trace into shorter sub-traces that could be parsed individually. Alternatively, the grammar could be modified so that interrupted communications are explicitly identified as such.

Conclusions

The application of context-free grammars to describe acceptable log files and intrusion patterns can significantly enhance log file analysis. The resulting approach is more powerful and provides better precision than existing techniques based on regular expressions.

Our future research will focus on developing a software framework that enables users to generate case-specific grammars and conduct detailed analyses. We will also attempt to cast a large number of well-known intrusion patterns as case-specific red grammars. A suitable combination of green and red grammars would reduce the alpha and beta error rates; however, this would require an additional meta decision policy for cases where the decisions made by the green and red parsers are inconsistent.

Figure 1 .

 1 Figure 1. Green grammar.

Figure 2 .

 2 Figure 2. Green grammar (continued).

Table 1 .

 1 Green grammar results.

	Input	Total Accepted Rejected Lex Err Syn Err
	Benign	100	94	6	6	0
	Malicious	100	0	100	28	72

Acknowledgement

We thank Bruce Watson for his assistance with the regular expression technique in the context of Cisco networking equipment. We also thank the anonymous reviewers and the conference attendees for their insightful critiques and comments.


Ankit Sarkar

Robin Verma

Gaurav Gupta

Chapter 24 DETECTING COUNTERFEIT CURRENCY AND IDENTIFYING ITS SOURCE

Keywords: Counterfeit currency, detection, Indian rupees

Counterfeit currency varies from low quality color scanner/printer-based notes to high quality counterfeits whose production is sponsored by hostile states. Due to their harmful effect on the economy, detecting counterfeit currency notes is a task of national importance. However, automated approaches for counterfeit currency detection are effective only for low quality counterfeits; manual examination is required to detect high quality counterfeits. Furthermore, no automatic method exists for the more complex -and important -problem of identifying the source of counterfeit notes. This paper describes an efficient automatic framework for detecting counterfeit currency notes. Also, it presents a classification framework for linking genuine notes to their source printing presses. Experimental results demonstrate that the detection and classification frameworks have a high degree of accuracy. Moreover, the approach can be used to link high quality fake Indian currency notes to their unauthorized sources.

Introduction

To counterfeit means to illegally make an imitation of something with the intent to take advantage of the superior value of the imitated product. Counterfeit currency refers to currency that closely resembles the original currency of a country but that is produced without the legal sanction of the government. Counterfeit currency is harmful to a nation. Fake notes increase money circulation, potentially leading to inflation. Also, the overall confidence in the currency decreases. Furthermore, individuals who innocently acquire counterfeit currency are victimized -there are usually no government policies to reimburse them for counterfeit notes that are seized. On the other hand, the individuals who produce counterfeit currency can make significant profits and finance an array of activities, many of which might be against the national interest.

Counterfeits are created in a variety of ways. The easiest and most common way is to use a high resolution scanner to capture both sides of a genuine currency note. The scanned images are then printed using a color inkjet or laser printer. This method works well for small denomination notes that are usually not scrutinized. However, it is easy to identify such counterfeit notes because of the quality of the paper that is used.

A more sophisticated method starts with a low denomination note, bleaches or washes out the ink, and then prints a higher value note. However, the production of a high quality counterfeit requires an entity to use the same raw materials and printing process that are used to produce genuine currency. This is out of the reach of individual counterfeiters due to the high cost and difficulty in procuring the raw materials and equipment. Therefore, the production of high quality counterfeits is generally state sponsored -the goal is usually to undermine the economy of the targeted state. A notable example is the "SuperDollar," a high quality imitation of the U.S. dollar. Another example is the fake Indian rupee notes produced by hostile states that are often indistinguishable from the originals.

Security features are often embedded in currency notes to identify genuine notes. Common security features include watermarks, security threads, latent images, micro-lettering, intaglio (raised print), optically variable ink and fluorescence. In addition to helping verify that a currency note is genuine, the security features deter counterfeiting. Replicating the security features increases the cost of counterfeiting, making it less profitable.

This paper focuses on high quality fake Indian counterfeit notes. While the successful identification of such notes usually requires expert examination, it is a relatively simple problem because only the integrity of the security features has to be investigated. A more difficult task is to identify the source of a counterfeit note. This requires detailed investigation by forensic scientists using expensive instruments. Also, no automatic method exists to link a counterfeit note to its source press. This paper applies digital forensic methods to address the problem, with the ultimate goal of developing an automated and scalable process that can link currency notes to their source presses.

Indian currency notes are printed at dedicated government printing presses. The number of presses is limited and great care is taken to ensure that all the notes produced by the presses are of the same quality. However, it is extremely difficult to produce currency notes that are exactly similar. Differences creep in due to plate defects, plate wear, ink quantity and inaccuracies in the cutting process. Locard's law of exchange states that every contact leaves a trace. According to this law, all currency notes from a particular press should contain some traces of the defects. Since the plates, printing machinery and raw materials are generally not transported from one press to another, it can be assumed that these characteristics are unique to each press. Thus, notes can be grouped into classes depending on their source printing press. Consequently, this paper focuses on identifying features (with intra-class similarity and inter-class differences) that can be used to classify currency notes. The goal is that, given a genuine Indian currency note, it should be possible to classify it as having been printed at one of the government presses. The approach can then be extended to link a fake Indian currency note to its source printing press in a hostile state.

Related Work

This section discusses previous work related to detecting counterfeit documents and linking documents to their source devices.

Detecting Counterfeit Documents

The problem of detecting a forged document has been the subject of much research. However, most approaches involve manual methods. In the case of counterfeit currency, the approach involves visually verifying security features such as security threads, watermarks, optically variable inks and intaglio. Non-visual methods include the use of chemical analysis to verify paper quality. While manual methods are reliable, they are not scalable -most real-world scenarios require the rapid processing of currency notes as soon as they are proffered by their owners.

Few automated methods have been proposed for detecting fraudulent documents. One of the earliest approaches was proposed by Gupta, et al. [START_REF] Gupta | Paradigm shift in document related frauds: Characteristics identification for development of a non-destructive automated system for printed documents[END_REF], who focused on fake documents produced using scanners and printers. In particular, they discovered that a fake document has more unique colors than its genuine counterpart. Gupta, et al. [START_REF] Gupta | Document frauds: Identification and linking fake documents to scanners and printers[END_REF] subsequently introduced two measures for detecting fake documents, variation in intensity and grey level co-occurrence matrix uniformity.

Ryu, et al. [START_REF] Ryu | Document forgery detection with SVM classifier and image quality measures[END_REF] applied machine learning in an automatic framework for detecting fake documents. They modeled detection as a classification problem with two classes, genuine and fake. An SVM classifier was used with seventeen image quality measures as features. The SVM clas-sifier worked relatively well for forgeries using scanners and printers, but there is still scope for improvement, especially with regard to detecting counterfeit currency notes (see, e.g., [START_REF] Chang | Paper currency verification with support vector machines[END_REF][START_REF] Ionescu | Fuzzy Hamming distance based banknote validator[END_REF][START_REF] Liu | Research on identification of counterfeits by recognizing infrared images[END_REF][START_REF] Xie | A new method to identify the authenticity of banknotes based on the texture roughness[END_REF][START_REF] Yeh | Employing multiple-kernel support vector machines for counterfeit banknote recognition[END_REF]).

Another approach is to use intrinsic features to compute a signature for a genuine document [START_REF] Van Beusekom | Document signature using intrinsic features for counterfeit detection[END_REF]. Given a set of pre-processed (properly rotated and pixelwise aligned) genuine documents, an unsupervised learning algorithm is employed to compute the document signature. The major feature used is the difference in alignment between genuine and fake documents. When an unknown document is presented, an attempt is made to match its signature with the genuine signature; the document is deemed to be fake if the signature does not match. The main assumption of this approach is that all genuine documents must be of the same type (e.g., like a particular bill or receipt) and a sufficient number of genuine samples must be available. Also, the approach assumes that a forged document is created using a scanner and printer, which introduce distortions.

Linking Documents to Source Devices

After a document is deemed to have been forged, it is often necessary to conduct a forensic investigation to discover its source. This is a hard problem.

One approach is to use a watermarking scheme in which a predetermined watermark is embedded in the document. The watermark is usually invisible to the naked eye but can be seen under a microscope. Depending on the level of sophistication, the watermark can help identify the make, model and even the specific printing device. However, a major shortcoming of this approach is that it relies on security through obscurity -the watermarking scheme must be kept secret to prevent unauthorized parties from creating the watermarks themselves.

Another approach is to characterize the defects that are unique to a particular scanner or printer. In this case, the amount of quantization done by a scanner, which differs from scanner to scanner, is used to link a fake document to a specific scanner [START_REF] Chang | Paper currency verification with support vector machines[END_REF][START_REF] Gupta | Document frauds: Identification and linking fake documents to scanners and printers[END_REF]. The unique color count is often used to link a forged document to a printer. Morphological features are also used to identify a printer [START_REF] Gupta | A structured approach to detect a scanner-printer used in generating fake documents[END_REF]. The main advantages of this approach are that it does not rely on embedded watermarks and can be applied to any document.

Most approaches focus on detecting forgeries created by scanners and printers. However, high quality counterfeit currency is rarely, if ever, produced by scanners and printers. Indeed, high quality counterfeits are created using the same raw materials and printing processes used to produce the originals. Therefore, it is extremely important to link counterfeit currency notes to their source printing presses. To the best of our knowledge, no research has specifically focused on this problem.

Currency Note Database

This section describes the database used for Indian currency note analysis. First, an overview is provided of Indian currency notes. Next, the genuine and counterfeit currency samples used in this work are described. Finally, the approach used to create digitized samples is detailed.

Indian Currency Notes

Indian currency notes are printed by the Reserve Bank of India (RBI) at four authorized currency presses. The presses are located in four different cities in India; the names of the cities are not publicized for security reasons [START_REF] Gupta | Forensic identification of Rs. 1,000 -Awareness for genuineness[END_REF].

An inset letter -a capital letter found on the number panel on the top right or bottom left of a currency note -is used to identify the printing press. Each of the four presses is allocated a set of inset letters for identification purposes. According to Gupta, et al. [START_REF] Gupta | Forensic identification of Rs. 1,000 -Awareness for genuineness[END_REF], 20 letters are currently used as inset letters. Table 1 presents the mapping of inset letters to printing presses. This information was inferred by Gupta, et al. [START_REF] Gupta | Forensic identification of Rs. 1,000 -Awareness for genuineness[END_REF] based on the name of the printer that appears on reams of printed banknotes.

This information is used as the ground truth in our experiments. Our goal is to attempt to construct a classifier for genuine Indian Rs. 500 notes. The classifier should partition input notes according to their source printing press.

Currency Samples

No publicly available database of genuine and counterfeit Indian currency notes currently exists. Furthermore, according to RBI regulations, no high resolution images of Indian currency notes may be publicly dis- seminated. Therefore, our only option was to create our own database of images. We collected several Rs. 500 currency notes. In the case of genuine notes, we attempted to collect as many samples as possible of each type (i.e., year, inset letter and RBI Governor). The sample size was limited because some older series of notes were not readily available. Another limiting factor was cost. Our genuine currency sample set comprised three notes of each type listed in Table 2.

We were able to collect only ten counterfeit currency notes. Four of these notes were in very bad condition. Thus, the counterfeit currency sample set included just six notes.

Image Creation

High resolution images of the samples were created under different parts of the light spectrum. A visual spectral comparator (VSC 6000) with facilities for examining and photographing documents in varying lighting conditions was used for this purpose.

A total of 23 images were taken for each sample currency note. The images covered various parts of the notes under different lighting conditions and magnifications (Table 3). The imaging decisions were made based on a preliminary examination of the notes using the visual spectral comparator. The 23 images showed the most perceptible differences for the different currency notes examined. As such, they were assumed to be the most promising features for detecting counterfeits and identifying the source presses.

The digitized database thus consisted of 33 currency notes, 27 of them genuine and six counterfeit. Since 23 images were taken for each note, the database contained a total of 759 images.

Preliminary Experiments

A preliminary experiment was conducted to determine which of the 23 features collected for each note would be useful in detecting counterfeit currency notes. Histograms of each feature were generated for all the currency notes and the histogram correlations of the corresponding features of the currency notes were examined. Also, the histograms were manually examined to discern differences that could assist in classifying notes as genuine or counterfeit. Since previous approaches successfully used the unique color count to detect fraudulent documents, the number of unique colors in each image was recorded.

The preliminary analysis also involved observations of the currency notes under a microscope. The Veho VMS-004D 400X USB microscope used for this purpose had fixed optical zooms of 20X and 400X. Various portions of the notes were examined for features that could be used to discriminate between genuine and fake notes.

The preliminary analysis revealed that features related to particular areas of a currency note were more discriminating that those related to the entire note. The most promising features observed were the Rs. 500 denomination lettering in optically variable ink, the area of Gandhi's face and the inset letter. The red, blue and green histograms of these features for genuine and counterfeit notes were compared, but no significant correlations were discerned. However, it appeared that there were clear differences between the unique color counts of features of genuine and fake currency notes, most likely due to differences in the printing process and ink.

Feature Selection

Three features were selected: (i) IMG 10 (Figure 1); (ii) IMG 11 (Figure 2); and (iii) IMG 12 (Figure 3). Based on the results of the preliminary experiments, the unique color count was used as a measure for quantifying the features. For each currency note, the corresponding images were selected and the total number of unique colors in the image was calculated. A C# program was written to perform this task and generate the corresponding CSV file of extracted features. It was not necessary to pre-process the features because they were already focused and adjusted at the time of sampling.

Classifier Design

A C4.5 decision tree was used to classify currency notes as genuine or counterfeit. The implementation of C4.5 in WEKA [START_REF] Hall | The WEKA data mining software: An update[END_REF] was employed for training and testing. A relatively simple classifier was preferred because the feature set comprised only three features. We experimented with other classifiers, including neural networks, radial basis function networks and C4.5 using grafting. However, all four classifiers had comparable accuracy, so the classifier with the least complexity was selected. A simpler classifier requires less time for training and testing compared with a more complex classifier. In a real-world application involving counterfeit currency detection, it is necessary to provide a quick answer because the owner of a currency note would be unwilling to wait for a long period of time.

Results and Evaluation

A C4.5 decision tree was trained and tested using the database of 33 images (27 genuine notes and six counterfeit notes). Ten-fold stratified cross validation was employed; 90% of the set was used for training and the remaining 10% for testing. The number of correctly classified instances was 31 while the number of incorrectly classified instances was two, yielding an average accuracy of 93.94%. Of the two incorrectly classified instances, one was a false positive (genuine detected as fake) and the other was a false negative (fake detected as genuine).

Upon closer examination of the two incorrectly classified instances, we discovered that one was a genuine note that belonged to the old "Blue Series." This older series of Rs. 500 notes does not have as many security features as the newer notes, which may have led to it being erroneously classified as fake. Manual examination of the fake note that was classified as genuine revealed that the note had extensive markings (zigzag lines) in blue ink (possibly made with a ball point pen).

The two currency note samples were then removed and the classifier was tested once again. The results were 100% accurate with all 31 instances classified correctly.

Identifying the Source Printing Press

This section describes the technique used to link a currency note to its source printing press, and the results that were obtained.

Preliminary Experiments

Preliminary experiments were also conducted to identify the features that would help link a currency note to its source printing press. Only genuine notes were used in this experiment because the ground truth was known only for genuine notes. As mentioned earlier, notes with the same inset letter come from the same press. Consequently, the goal was to successfully classify notes with the same inset letter and, thus, the same origin.

As in the previous experiment, histograms of the corresponding features of the notes were constructed. However, since there were more classes, it was difficult to identify one feature that could be used to differentiate between all the classes. Therefore, we attempted to discern some peculiar properties of each class of notes that would support the identification. We observed that, while no single feature was able to discriminate between all the classes, certain features were able to differentiate between one particular class and the others. Hence, we framed the task as a multilevel classification problem and used a cascade of classifiers. The cascade incorporates multiple levels of individual classifiers and passes the output of one classifier to another.

Pre-Processing

Pre-processing was required for some of the images before extracting the features. Two techniques were used for pre-processing:

Percentage Histogram Bins: Histograms (bins 0-255) of the blue, green and red channels were constructed. The values of each bin were divided by the total pixels in the image and multiplied by 100 to expresses it as a percentage of pixels in the image with a particular intensity. This was necessary because the images had different sizes, which precluded the use of regular histograms for comparison (i.e., using only the numbers of pixels).

Threshold UV Images: Threshold images were created from images obtained under ultraviolet (UV) light (Figure 4). Each pixel was given a value of 255 if its intensity in the green channel was greater than 100 and its intensity in the red channel was greater than 100; otherwise, it was given a value of zero. Thus, binary images were obtained with pixels of intensity zero or 255 (Figure 5).

Feature Selection

Based on the experimental results, we selected seven features to be used by the cascade of classifiers. Note that pre-processing was required for feature extraction and quantification. Feat 01 Link: The percentage histogram bins were calculated for IMG 18 (Figure 6). The quantification was performed using the sum of the histogram bins of the blue channel from 0 to 210.

Feat 02 Link: The percentage histogram bins were calculated for IMG 18. The quantification was performed using the sum of the histogram bins of the blue channel from 0 to 100.

Feat 03 Link: The percentage histogram bins were calculated for IMG 18. The quantification was performed using the sum of the histogram bins of the blue channel from 0 to 40. Feat 04 Link: The percentage histogram bins were calculated for IMG 16. The quantification was performed using the sum of the histogram bins of the green channel from 0 to 40.

Feat 05 Link: The number of white pixels in each half of the threshold UV image of IMG 07 was computed. The quantification was performed using the ratio of the white pixels in the right half to those in the left half.

Feat 06 Link: Image IMG 10 was used. The quantification was performed by counting the total number of unique colors.

Feat 07 Link: Image IMG 19 was used (Figure 7). The quantification was performed by counting the total number of unique colors.

Classifier Design

As described above, a cascade of classifiers uses multiple levels of individual classifiers in which the output of one classifier is input to another. In our design, an individual classifier was used to filter currency notes belonging to one particular class. Thus, each succeeding classifier dealt with one less class than the preceding classifier in the cascade. Each level used a C4.5 decision tree as the classifier. A total of five classifiers were used.

Level 1: This classifier was designed to filter the old Blue Series notes (i.e., Rs. 500 notes printed prior to or during Bimal Jalan's term as RBI Governor). These notes differ significantly from the newer Yellow Series notes. The old Blue Series notes have inset letters A, C or blank, and are from Press 1 in City 1. The features used in Level 1 were Feat 01 Link and Feat 02 Link. All the genuine notes were passed to the classifier, which classified them either as "Old Blue Series with inset letters A, C or nothing" or "New Yellow Series with any inset letter." The currency notes classified as "New Yellow Series" were passed to the Level 2 classifier.

Level 2: This classifier was designed to filter notes with no inset letters. These notes are also from Press 1 in City 1. The feature used was Feat 03 Link. The output of the Level 1 classifier ("New Yellow Series") was passed as input to the Level 2 classifier, which classified the currency notes as "No inset letter" and "Inset letter A, B, E, L or R." The notes with inset letters A, B, E, L or R were passed to the Level 3 classifier.

Level 3: This classifier was designed to filter notes with the inset letter L. These notes are from Press 3 in City 3. The feature used was Feat 04 Link. The output of the Level 2 classifier ("Inset letter "A, B, E, L or R") was passed as input to the Level 3 classifier, which classified the currency notes as "Inset letter L" and "Inset letter A, B, E or R." The notes with inset letters A, B, E or R were passed to the Level 4 classifier.

Level 4: This classifier was designed to filter notes with the inset letter E. These notes are from Press 2 in City 2. The features used were Feat 05 Link and Feat 06 Link. Feat 05 Link was specifically used because our preliminary experiments revealed that the right portion of currency notes with the inset letter E had a larger area that glowed under UV light. The output of the Level 3 classifier ("Inset letter "A, B, E or R") was passed as input to the Level

Experimental Results

This section describes the results obtained for the individual classifiers and the cascade classifier.

Individual Classification: In passing input to a classifier at a given level, we assumed that all the classifiers at the previous levels gave the correct results. Thus, the classifier input only contained instances that would be passed to it from the previous classifier. Ten-fold stratified cross validation was used for each classifier, except for the last (Level 5) classifier, which used eight-fold stratified cross validation.

Table 4 shows the results that were obtained. Note that all five classifiers have high degrees of accuracy.

Cascaded Classification: In this case, we evaluated the system of five cascaded classifiers as a whole. Each classifier was individually trained and then combined to create the cascade. We used the entire set of currency notes to test the cascaded classifier -this was done to use all the available samples for testing and to see if the cascaded classifier failed on any sample. A total of 27 samples were provided as input to the cascade classifier. Of these, 25 were classified correctly based on their inset letter and two were classified incorrectly. This corresponds to an overall accuracy of 92.59%.

Evaluation

While the experimental results indicate that the individual classifiers and the cascaded classifier have high degrees of accuracy, some limitations do in fact exist. First, the classifiers are dependent on the fact that the input images are correct and well focused. For example, the Level 2 classifier is sensitive to changes in focus. To verify this fact, we deliberately blurred a sharp image and provided it to the classifier, which gave an incorrect result.

The second limitation is that the currency notes are assumed to be of good quality. The presence of oil, cellotape, pen marks or dirt on the surface of a note can render it difficult to classify correctly. For example, one of the fake samples had blue pen marks over it, which caused it to be classified as genuine. Also, the presence of cellotape on a currency note produces an abnormal glow when viewed under UV light. The handling of such cases is important because many Indian currency notes are worn or soiled.

A third limitation is that, because the classifiers were trained with Rs. 500 notes, they cannot be applied to other denomination notes. Also, different denomination notes have different security features, and these differences have to be taken into account when training the classifiers.

Integrated Tool

The classifiers were implemented in an integrated tool, which was written in C#. The EmguCV library (a C# wrapper for OpenCV) was used to perform image processing operations. The tool was run on a Compaq Presario laptop with a 2 GHz Intel Core 2 Duo Processor T5800 and 2 GB RAM. The tool took as input the folder containing all 23 image features of the sample currency notes and classified each note as genuine or counterfeit. In the case of a genuine note, the tool also attempted to identify its source printing press. The evaluation of each note was completed within five seconds.

Most individuals do not have the expertise to manually examine a currency note and determine if it is counterfeit. The tool, especially one with an enhanced GUI, would be very useful to individuals who do not have much technical and forensic knowledge. Furthermore, the tool could be integrated with a USB microscope and scanner, which would greatly reduce the possibility of commercial establishments accepting counterfeit currency as payment for goods and services.

Conclusions

The single classifier approach described in this paper is well suited to detecting counterfeit currency notes. The cascaded classifier approach for linking genuine currency notes to their source printing presses is also fast and accurate. The prototype tool, which integrates the two classification approaches, functions as a standalone system for counterfeit currency detection and source press identification.

Our future research will expand the image database and test the classification approaches on samples of different denominations. Additionally, we will extend the identification approach to link counterfeit currency notes to their source printing presses in hostile states. Our ultimate goal is to develop a versatile and inexpensive tool that would enable individuals without much technical and forensic knowledge to quickly detect counterfeit currency notes and identify their source presses.

Figure 1 .

 1 Figure 1. Image IMG 10.

Figure 2 .

 2 Figure 2. Image IMG 11.

Figure 3 .

 3 Figure 3. Image IMG 12.

Figure 4 .

 4 Figure 4. UV image.

Figure 5 .

 5 Figure 5. Threshold UV image.

Figure 6 .

 6 Figure 6. Images IMG 16 (left) and IMG 18 (right).

Figure 7 .

 7 Figure 7. Image IMG 19.

Table 1 .

 1 Mapping of inset letters to printing presses.

	Inset Letter	Printing Press
	Nothing, A, B, C, D Press 1 in City 1
	E, F, G, H, K	Press 2 in City 2
	L, M, N, P, Q	Press 3 in City 3
	R, S, T, U, V	Press 4 in City 4

Table 2 .

 2 Genuine currency samples.

	Year	Inset Letter	RBI Governor Series
	2011	Nothing, E, L, R Subbarao	Yellow
	2010	Nothing, E, L, R Subbarao	Yellow
	2009	Nothing, E, L, R Subbarao	Yellow
	2008	Nothing, E, L, R Reddy	Yellow
	2007	E, L, R	Reddy	Yellow
	2006	Nothing, E, L, R Reddy	Yellow
	2005	R	Reddy	Yellow
	No Year B	Reddy	Yellow
	No Year A	Jalan	Yellow
	No Year A	Jalan	Blue

Table 4 .

 4 Results. This classifier was designed to filter notes with the inset letter R. These notes are from Press 4 in City 4. Any note that was classified at this level was assumed to have inset letter A or B (from Press 1 in City 1). Feature Feat 07 Link was used because none of the other features could discriminate between notes with inset letters A, B and R. The output of the Level 4 classifier ("Inset letter "A, B or R") was passed as input to the Level 5 classifier, which classified the currency notes as "Inset letter R" and "Inset letter A or B."

	Level	Correctly Incorrectly	Correctly	Incorrectly
		Classified	Classified	Classified	Classified
		Instances	Instances	Percentage Percentage
	Level 1	27	0	100%	0%
	Level 2	26	0	100%	0%
	Level 3	20	1	95.24%	4.76%
	Level 4	14	1	93.33%	6.67%
	Level 5	9	0	100%	0%
	4 classifier, which classified the currency notes as "Inset letter E"
	and "Inset letter A, B or R." The notes with inset letters A, B or
	R were passed to the Level 5 classifier.
	Level 5:

The database size was limited by the time constraints imposed by the digitizing process. It took an average of ten minutes to apply the required settings, focus, capture and save each image. Thus, it took about 230 minutes to fully digitize each sample. Due to the time factor, we decided to digitize one sample from each class (combination of year, inset letter and RBI Governor) of genuine notes along with the six counterfeit note samples. Thus, the database contained one representative sample from each series and type.

Detecting Counterfeit Currency Notes

This section describes the technique used to detect counterfeit currency notes, and the results that were obtained.


Wynand Van Staden

PROTECTING THIRD PARTY PRIVACY IN DIGITAL FORENSIC INVESTIGATIONS

Keywords:

The privacy of third parties is an important issue in digital forensic investigations. The typical steps followed during an investigation require that the equipment used during the commission of the crime be seized and analyzed in a manner that complies with accepted investigative policy and practice. The analysis of the data on the seized equipment provides the investigator, who may not necessarily be associated with a law enforcement agency, with the opportunity to access personally identifiable information of persons or entities who may not be linked to the crime; this is especially true in multi-user environments.

This paper considers the key aspects surrounding privacy protection of third parties during the post mortem data analysis phase of digital forensic investigations. It proposes a framework that helps protect privacy without reducing the effectiveness of an investigation. The design includes a profiling component that analyzes a search corpus and a filtering component that calculates the diversity in the search results. Depending on the sensitivity level, the search results are either filtered out or are presented to the investigator.

Introduction

Crimes involving computer equipment are investigated using procedures created specifically to surmount the difficulties associated with the digital nature of the crimes, and also to conform to the requirements for investigative procedures as may be required by law. In the discipline of digital forensics, there are typically two types of procedures, one geared for live investigations (investigations of crimes that are in progress), and the other targeted for post mortem investigations (investigations of crimes after they have been committed).

This paper is concerned with post mortem investigations, with a focus on multi-user environments. The investigative steps include the preservation, collection, examination and analysis of digital evidence [START_REF] Gladyshev | Formalizing Event Reconstruction in Digital Investigations[END_REF][START_REF] Palmer | A Road Map for Digital Forensic Research[END_REF].

The collection phase involves the gathering of all digital data that may be relevant to the case. It includes the seizure of computing devices and the collection of data from storage media. The seized data normally pertains to the suspects and victims as well as third parties whose data and activities may have no bearing to the investigation. When an investigator examines collected data, he may stumble upon sensitive data relating to third parties. Even when filtering techniques are used, intrinsic or extrinsic connections between suspects/victims and third parties may result in third party data being scrutinized. This is an example of a third party privacy breach, where the act of investigating a crime inadvertently results in the loss of privacy for entities that are unrelated to the case.

This paper presents a privacy-enhancing framework that attempts to prevent -or at least minimize the risk of -third party privacy breaches. The approach draws on the basic privacy principle of information selfdetermination. In general, a privacy-enhancing technology (PET) protects access to personally identifiable information pertaining to the users of a computing system. During a digital forensic investigation, the reasonable expectation of privacy by entities that have no bearing to the case should not be discarded without due consideration [START_REF] Van Den Hoven Van Genderen | Cyber Crime Investigation and the Protection of Personal Data and Privacy[END_REF]. Therefore, the framework is designed to protect third party privacy without preventing justifiable access to private information. The framework, which employs a filtering approach for weeding out data that is not relevant to an investigation, provides subjects in a multi-user environment with a reasonable expectation of privacy without reducing the effectiveness and speed of investigations.

Background

This section briefly discusses the main issues related to digital forensics, privacy and privacy-enhancing technologies (PETs).

Digital Forensics

Digital forensics is the branch of forensic science [START_REF] Gladyshev | Formalizing Event Reconstruction in Digital Investigations[END_REF][START_REF] Palmer | A Road Map for Digital Forensic Research[END_REF] that is concerned with the "preservation, collection, validation, identification, analysis, interpretation, documentation and presentation of evidence in a digital context" [START_REF] Palmer | A Road Map for Digital Forensic Research[END_REF]. Scientifically-sound and validated methods are required to be used in every phase of a digital forensic investigation.

During the collection phase, all digital information that may be relevant to the investigation is gathered [START_REF] Gladyshev | Formalizing Event Reconstruction in Digital Investigations[END_REF][START_REF]Technical Working Group for the Examination of Digital Evidence, Forensic Examination of Digital Evidence: A Guide for Law Enforcement[END_REF]. In practice, this often means creating bit-for-bit copies of the seized storage media. This is done to preserve the storage media content without any alteration. Typically, this is accomplished using a write-blocking device when copying the storage media.

Since all the data residing on the seized storage media is potential evidence, the investigator can be expected to access and examine all the data. In some jurisdictions, such as The Netherlands [START_REF] Van Den Hoven Van Genderen | Cyber Crime Investigation and the Protection of Personal Data and Privacy[END_REF] and South Africa [START_REF]Minister of Justice and Constitutional Development, Protection of Personal Information Bill[END_REF], data collected for investigative purposes is referred to as "police data." This data belongs to the police for investigative purposes. In both jurisdictions, the police are allowed to examine all police data without prejudice. Thus, the privacy rights of all the entities about whom there is data on the storage media are suspended during an investigation.

The analysis phase of a digital forensic investigation involves the systematic search of the collected information for data that is relevant to the case. This may involve searching through documents and other related files, searching the slack space and searching for data that may be hidden using anti-forensic techniques such as steganography [START_REF] Gladyshev | Formalizing Event Reconstruction in Digital Investigations[END_REF][START_REF]Technical Working Group for the Examination of Digital Evidence, Forensic Examination of Digital Evidence: A Guide for Law Enforcement[END_REF]. Since a large quantity of data has to be examined, a variety of digital forensic tools have been developed to support the analysis phase. Some of these tools (see, e.g., [START_REF] Fei | Exploring forensic data with self-organizing maps[END_REF]) provide search filters that eliminate data that is considered to be noise (i.e., not relevant to an investigation). The filters typically use text strings (in documents or file metadata), file types and file timestamps [START_REF] Fei | Using selforganizing maps for anomalous behavior detection in a computer forensic investigation[END_REF].

Other techniques for filtering non-relevant data include text mining [START_REF] Beebe | Dealing with terabyte data sets in digital investigations[END_REF] and machine learning approaches such as self-organizing maps [START_REF] Fei | Using selforganizing maps for anomalous behavior detection in a computer forensic investigation[END_REF][START_REF] Fei | Exploring forensic data with self-organizing maps[END_REF]. Text mining [START_REF] Witten | Text mining[END_REF] returns data that is important based on some relevance scale. Self-organizing maps [START_REF] Kohonen | Self-Organizing Maps[END_REF] cluster data using various features to assist the investigator in forming opinions about the relevance of data. Noise may be filtered using the thematic clustering of search results [START_REF] Beebe | Digital forensic text string searching: Improving information retrieval effectiveness by thematically clustering search results[END_REF].

The practice of filtering potential red herrings during the investigative process is well established. Filtering often yields false positives, i.e., data that may not be relevant to an investigation, which requires effort to classify and discard later in the investigation. False negatives are also a problem because they correspond to relevant data that is hidden from the investigator by the filtering tool.

Privacy

Efforts at protecting an individual's right to privacy have been undertaken for more than one hundred years [START_REF] Warren | The right to privacy[END_REF]. Modern interpretations of the right to privacy are enshrined in the European Union Data Protection Directive [START_REF]Protection of Individuals with Regard to the Processing of Personal Data and on the Free Movement of Such Data[END_REF] and the South African Protection of Personal Information Bill [START_REF]Minister of Justice and Constitutional Development, Protection of Personal Information Bill[END_REF], that when enacted, will be on par with the European Union directive. Both these instruments deem privacy important enough to prohibit the cross-border flow of personal information to countries that do not have equivalent privacy laws. To reduce the trade impact of these laws, countries with strict privacy laws generally sign safe harbor treaties with non-compliant countries.

The principles governing the protection of private information were first listed by the Organization for Economic Cooperation and Development (OECD) [START_REF]OECD Guidelines on the Protection of Privacy and Transborder Flows of Personal Data[END_REF]. The OECD principles, which are incorporated in the European Union and South African instruments, include collection limitation, data quality, purpose specification, use limitation, security safeguards, openness, individual participation and accountability. When implemented as technological safeguards for privacy protection, these principles are commonly translated to the right to information self-determination [START_REF] Fischer-Hubner | IT Security and Privacy: Design and Use of Privacy-Enhancing Security Mechanisms[END_REF][START_REF] Van Staden | On compound purposes and compound reasons for enabling privacy[END_REF] -the right of an entity to determine which entities have data about it, what data these other entities have, what these entities may do with the data, and to which entities they may give the data [START_REF] Van Staden | On compound purposes and compound reasons for enabling privacy[END_REF].

Legislation typically provides a reasonable expectation of privacy to individuals who entrust their data to enterprises and service providers who make positive statements about their intent to protect user privacy. The exemption of these laws during an investigation may take individuals by surprise -in particular, the fact that personal information that is not relevant to the case may be perused by an investigator during the course of the investigation.

Privacy-Enhancing Technologies

Privacy protection systems rely on PETs to protect the privacy of individuals. These systems focus on purpose specification and use limitation [START_REF] Fischer-Hubner | IT Security and Privacy: Design and Use of Privacy-Enhancing Security Mechanisms[END_REF][START_REF] Van Staden | On compound purposes and compound reasons for enabling privacy[END_REF]. While the systems address only two of the eight principles of privacy protection, the other six principles are normally taken care of as a matter of operating procedure. Privacy protection systems ensure that personal data is not disseminated to entities who are not supposed to get the data, and certainly not to entities who may desire to use the data for unauthorized purposes [START_REF] Van Staden | On compound purposes and compound reasons for enabling privacy[END_REF].

PETs are effective and, as such, are promising candidates for protecting personal privacy during digital forensic investigations. The challenge is to protect personal privacy without reducing the effectiveness and speed of investigations.

Preventing Third Party Privacy Breaches

As discussed above, filtering techniques can be used to exclude content that is deemed to be not relevant to an investigation. A privacy aware system used during an investigation would incorporate enhancements to basic filtering techniques. The important point is that the system would restrict the results to data that has limited potential to constitute a breach of third party privacy.

Croft and Olivier [START_REF] Croft | Sequenced release of privacy-accurate information in a forensic investigation[END_REF] articulated the notion of privacy aware digital forensics. In particular, they proposed the sequenced release of data to protect the privacy of individuals under investigation. Their proposal pivots on hypothesis testing before any additional data is released. In other words, the system only releases data if it knows that the entity querying the system already has some prior data that is relevant.

The approach presented in this paper allows the privacy of third parties to be taken into account. The system evaluates the results of a query and either releases the results to the investigator or reports that the query may result in a privacy breach. In the latter case, the investigator is requested to provide a more focused query.

Based on the operating principles of a PET listed above, it could be argued that the framework presented here is not a PET because no explicit purpose specification and use limitation are present. However, it is safe to assume that the purpose of the data access is the investigation, and that the data is stored and accessed for the purpose of the investigation.

The PET forces the investigator to present focused questions when searching for evidence. The search results are provided to the investigator only after it is determined that the query is focused. Clearly, this approach should not encourage data sequestration that may hinder an investigator (i.e., the system reports false negatives). In the case of false positives, the guiding principle is accountability. If personal data that is not related to the investigation is accessed, the PET should record the access, enabling the affected entity to know that a privacy breach did in fact occur.

A PET used in an investigative process should have the following characteristics:

The PET should not encumber the investigator. The investigator should not have to perform a significant number of additional tasks during an investigation.

The PET should reasonably sequester data that is determined as being not relevant to the investigation. It should specifically limit data related to parties who are not under investigation.

The PET should provide the investigator with the freedom to access data that is deemed to be false negative.

The PET should support accountability and openness. It should record accidental and intentional accesses of private data that bears no relevance to the investigation.

The PET should not undermine an investigation by adding significant time delays to established investigative techniques such as filtering and text mining.

PET Design

Our PET design for supporting privacy aware digital forensic investigations incorporates four principal components (Figure 1). The first is a profiling component that creates a profile of the data and stores the results in a meta-database; the profile is created just in time, when a new document is queried and the profile is reused after it is created. The second component is a query front-end that enables an investigator to perform searches (e.g., partial string and file type searches). The third component is a response filter that determines if the query results could potentially lead to a privacy breach. The fourth component is an audit log that is used for auditing compliance with the privacy principles.

Note that the meta-database that stores profiling results and caches ad hoc profiles, and the audit log that stores search queries and PET configuration changes must be tamper-proof.

Screening Search Results

As stated above, an investigator may gain access to sensitive data concerning third parties during the course of an investigation. This problem is mitigated by incorporating a filter that forces the investigator to focus search queries on the case at hand. The solution engages the profiling component, a metric that assesses the diversity of search results and a sensitivity measure that determines the leniency to be provided to queries that return diverse search results.

Profiling

The profiling component uses n-grams [START_REF] Cavnar | N-gram-based text categorization[END_REF], an established profiling technique that delivers good results. The n-gram technique relies on Zipf's law, which states that the n th most common word in human text occurs with a frequency that is inversely proportional to n [START_REF] Cavnar | N-gram-based text categorization[END_REF]. The implication is that two texts that are related should have similar frequency distributions. Using this principle, the text is tokenized and each token is deconstructed into n-grams where 2 ≤ n ≤ 5 [START_REF] Cavnar | N-gram-based text categorization[END_REF].

A frequency table is used for each n-gram in a text sample. After a document is scanned, a ranked list is created of the most frequently occurring n-grams. The number of entries in the rank table can vary; however, according to Cavnar and Trenkle [START_REF] Cavnar | N-gram-based text categorization[END_REF], domain-specific terminol-ogy only begins to appear around rank 300. The n-gram technique is fast and provides a usable profile for text.

After a profile is generated, it can be compared with another profile using a distance measure between the two profiles (or texts). Texts that are similar have a smaller distance measure than texts that are dissimilar. The next section describes how the distance is calculated.

Distance Calculation

Cavnar and Trenkle [START_REF] Cavnar | N-gram-based text categorization[END_REF] use the rank-difference of n-grams as a distance measure:

|P k | i |r k(i) -r j(i) | (1)
where P k is the rank profile for text k and r k(i) is the rank of n-gram i for text k. This distance measure takes content into account, but it ignores some important aspects. First, it is reasonable to assume that similar documents that have different owners are the result of two individuals working on the same project. Therefore, a difference in document owners should be considered when evaluating the similarity between documents. However, in an investigation, another user could be an accomplice of the suspect, so the existence of different owners should not skew the results too much.

Another aspect is the logical location of documents in a storage medium. This is important when two or more individuals work on a project, but only one of the individuals has been involved in malicious acts while working on the project. The goal here is to protect innocent individuals by carefully presenting the documents they own as separate and distant from the documents owned by the suspect.

The attributes used to determine the distance measure employ features used in anomaly detection by Fei, et al. [START_REF] Fei | Using selforganizing maps for anomalous behavior detection in a computer forensic investigation[END_REF]. In their approach, the documents that are clustered closely together using the features are worthy of further investigation.

The following features are considered for inclusion when determining the distances between the documents returned during a search for evidence: document text, document creation date and time, document owner and the absolute logical location of the document in the storage medium. Note that we do not propose a fixed set of features because the specific features used in distance calculations would depend on the type of investigation being conducted.

Thus, the distance between two documents in a search result corpus is calculated as:

D(j, k) = R(j, k) + |δ j -δ k | + P (j, k) + O(j, k) (2)
where R(j, k) is the rank-difference distance between j and k, δ i is the creation date and time for i, P (j, k) is the difference in the logical locations of the files, and O(j, k) is the ownership distance. Furthermore, P (j, k) is calculated as the number of directory changes needed to navigate from one location to the other. The ownership difference O(i, j) relies on a maximum value to create additional distance between the suspect and other users:

O(j, k) = 0 if j o = k o τ if j o ̸ = k o ( 3
)
where τ is a maximum value assigned to O(i, j).

After an investigator issues a query, the profiles of the documents are constructed (or retrieved). The distances between all the documents are then calculated. This information is used in the diversity calculation, which is discussed in the next section.

Diversity Classification

After a query is executed, the documents in the search results are clustered to determine the diversity of results using a hierarchical clustering scheme. Single-linkage clustering is used. However, the algorithm is only applied once, yielding an intuitive clustering result that provides a good indication of document similarity. This hierarchical clustering scheme also clusters documents very rapidly [START_REF] Johnson | Hierarchical clustering schemes[END_REF].

For a corpus S consisting of all the documents that are returned in a result: y = argmin z∈S D(x, z) ∀x ∈ S, x / ∈ C i (4) where D(x, y) is a distance measure between x and y. Note that if y ∈ C i for some i, then C i ∪ {x} else C j = {x, y} with j = |C| + 1.

Informally, for each document in the result, the cluster is found that most closely matches it, and the document is added to the cluster. If a document is found that most closely matches the document, but this document is not yet in any cluster, then a new cluster is created with the two documents.

After clustering is complete, the PET computes the diversity of the corpus using Shannon's entropy index [START_REF] Shannon | A mathematical theory of communication[END_REF]:

D S = - C i p i log 2 p i ( 5
)
where C is a cluster, i is a document in cluster C, and p i is the probability of choosing document i from cluster C i . The higher the entropy, the more diverse the corpus. Ideally, the search result would have returned one cluster of documents (i.e., all the documents are closely related). This ideal search result, representing the lower bound on the diversity of the corpus, is called the "uniformity norm." It is calculated as:

N S = - S i p i log 2 p i (6)
Ideally, a search result should be on par with ideal uniformity. In other words, the query is focused enough to return only documents that are closely related to each other. If this is not the case, the query should be rejected.

The proposed PET should support and not interfere with legitimate investigative efforts. To assess this, we introduce a sensitivity level indicator l as a threshold for determining if a search result is too diverse. If the diversity indicator D S > l, then the query is defined as being "too wide" and the results are dropped. Note that l is range limited because N S ≤ l, which requires an ideal query result.

A query that returns results that are too diverse is referred to as a "wide query." On the other hand, a query that is close to the uniformity norm is referred to as a focused query. Note that all wide queries are reported and no results are returned.

A wide ranging implication with regard to threshold adjustment is that the threshold may be used without due regard for privacy and could be disregarded altogether. Specifically, if the threshold is set too low, then the attempt at preventing a third party privacy breach is disabled and all the results are returned. Cross-checks can serve to avoid this situation by requiring authorization from a higher authority before the threshold is adjusted. The audit logging component discussed in the next section is used to record threshold adjustments.

Audit Logging

The audit log records wide queries to ensure that only questions that are related to the investigation are asked and answered. Note that queries are not logged to have a "smoking gun" that the investigator issued unfocused queries, but rather to have documentary proof if the investigative process is questioned in the event of a privacy breach.

The audit log also records changes to the sensitivity level of the results filter, making it possible to trace privacy breaches at a later point in time. Because the queries are recorded and the data and meta-database are kept intact, privacy breaches can be traced by examining the results obtained from queries logged in the system, similar to the auditing compliance work on Hippocratic databases done by Agrawal, et al. [START_REF] Agrawal | Auditing compliance with a Hippocratic database[END_REF]. Additionally, the audit log provides a transparent recording of the investigative process.

Usability

Any digital forensic tool that casts doubt on the integrity of the evidence that it collects or processes is inappropriate for use in an investigation. The framework described in this paper is intended to be an extension of how an investigator searches for relevant data. It merely augments the analysis phase, attempting to prevent sensitive data about uninvolved third parties from being accessed. The framework does not change any data on the media being inspected, nor does it hinder the investigator or investigation. If the investigator uncovers data pertaining to a third party, the sensitivity level can be adjusted to reveal less data. Alternatively, the filter can be switched off completely, enabling the investigator to access all the data.

Conclusions

Preserving the privacy of uninvolved third parties is an important issue during a digital forensic investigation. The possibility of a privacy breach is especially high in multi-user environments where a suspect may have worked on group projects with other innocent users. The privacy protection framework described in this paper is highly effective during the post mortem data analysis phase of an investigation. One of its primary features is that an investigator is required to issue focused queries related to an investigation. If a query is deemed to be too wide, the framework prevents the investigator from accessing the search results. Should the investigator have concerns about missing relevant data, a sensitivity threshold can be adjusted to return results even if the query is considered to be unfocused. An audit log is maintained to ensure that queries and their results are saved for compliance purposes if a privacy breach were to occur. The framework operates on the same principle as tools that filter data that are not relevant to investigations. The important difference, however, is that the framework takes privacy concerns into account when filtering query results.

Our future research will evaluate the usability of the privacy protection framework in actual investigations. Also, it will examine the effectiveness of the framework when querying slack space data and file carving results.

Figure 1 .

 1 Figure 1. PET design for digital forensic investigations.


Martin Olivier

Stefan Gruner

On the Scientific Maturity of Digital Forensics Research

Keywords: Digital forensics, scientific maturity, software engineering

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

Introduction

The digital age has enabled and necessitated digital forensics as a means to maintain law and order in society. Forensic methods have occasionally failed those who were wrongfully convicted on the basis of low-quality evidence [START_REF] Giannelli | Wrongful Convictions and Forensic Science: The Need to Regulate Crime Labs[END_REF][START_REF] Koppl | Digital devices and miscarriages of justice[END_REF]. In the past, the absence of strict scientific standards in some forensic practices has caused confusion about the reliability, validity, repeatability and accuracy of the outcomes, especially when the outcomes were presented in court, where the intended audience did not have the technical knowledge to judge the reliability of the presented evidence. Digital forensic scientists and practitioners have a duty to avoid repeating the mistakes of the past by scrutinizing the scientific maturity of their field, and by approaching and conveying evidence accordingly.

In a mature scientific field, the outcomes of processes can be trusted because they are constantly produced and reproduced in the course of "normal science." This trust is earned through the successful repeatability of processes, which render consistent, accurate, reliable and valid outcomes.

Digital forensics is still a developing field, and the question arises: Is it possible to assess the current level of "scientificness" in the field of digital forensics? We use the informal term "scientificness" to acknowledge the fuzziness of the concept of scientific maturity.

This paper presents a scientific maturity assessment of digital forensics using the Shaw [START_REF] Shaw | The coming-of-age of software architecture research[END_REF] software architecture science maturity scale. The transfer of this maturity scale, from software architecture to digital forensics, is justified by the similarity of the problems, including the shortage of scientificness (which was experienced in the domain of software architecture more than a decade ago) and the impact claims that both fields have in the physical world.

The remainder of this paper presents the software architecture scientificness scale [START_REF] Shaw | The coming-of-age of software architecture research[END_REF]. The scale is used to assess the scientificness of the digital forensics research presented at the first and sixth IFIP WG 11.9 International Conferences on Digital Forensics held in 2005 and 2010, respectively. From the assessment, statements about the progress that has been made in the field of digital forensics in its brief history are discussed.

Scientificness Software Engineering

In 1998, Snelting [START_REF] Snelting | Paul Feyerabend und die Softwaretechnologie[END_REF] published a lament about the shortage of scientificness in the field of software engineering. Snelting reminded the software engineering community about Popper's criterion of falsifiability, with a "slant" against the post-modernist intellectual fashion of socioconstructivism, and demanded more efforts towards the empirical validation of ideas and conjectures. However, Snelting's appeal for more scientificness did not take into account the gradual historic development of emerging academic subjects from the pre-scientific stage through the proto-scientific stage to the fully scientific stage.

In a later paper focusing on the software engineering sub-specialty of software architecture, Shaw [START_REF] Shaw | The coming-of-age of software architecture research[END_REF] included the spectrum of pre-scientific to fully scientific stages. With reference to earlier work by Redwine and Riddle, Shaw [START_REF] Shaw | The coming-of-age of software architecture research[END_REF] identified six typical stages in the historic development of an emerging subject of research, especially in technical science domains. These six stages are characterized by their drive towards practical applications and external usefulness: Early prospecting.

Concept formulation.

Development and extension.

Internal enhancement. External enhancement.

Popularization.

Most relevant to this study is Shaw's three-dimensional maturity classification scheme. The three dimensions are:

Research setting.

Research product (approaches and methods).

Result validation technique.

Tables 1, 2 and 3 show the ascending maturity values in each of these three dimensions of assessments (including some interpretative modification and adaptation).

Table entries where the classification criteria differ from Shaw [START_REF] Shaw | The coming-of-age of software architecture research[END_REF] use Bunge's terminology [START_REF] Bunge | Philosophy of Science (Volume One): From Problem to Theory[END_REF][START_REF] Bunge | Philosophy of Science (Volume Two): From Explanation to Justification[END_REF]. The concept of tabulating levels of quality is also related to maturity assessment schemas in other domains, such as CMMI for general organizational capabilities and TMMI for maturity assessment in the domain of systematic software testing.

Shaw [START_REF] Shaw | The coming-of-age of software architecture research[END_REF] concluded that researchers "must attend to making existing results more robust, more rigorously understood, and more ready to move into application." That is because, to date, "we don't recognize what our research strategies are and how they establish their results. Poor external understanding leads to lack of appreciation and respect. Poor internal understanding leads to poor execution, especially of validation, and poor appreciation of how much to expect from a project or result. There may also be secondary effects on the way we choose what problems to work on at all."

It is outside the scope of this paper to critique the maturity classification scheme. Instead, we transfer Shaw's maturity schema and method

2.e Analytic model or theory

Develop structured quantitative and/or symbolic theories that permit formal analysis and deep explanations.

Table 3. Dimension 3: Validation technique [START_REF] Shaw | The coming-of-age of software architecture research[END_REF].

Dimension Technique Type Style of Argument

3.a Persuasion

We suggest... We believe...

3.b Implementation

Here we made a prototype that can do... Here we see one example that has...

3.c

Informal evaluation Comparison of several objects against each other. Rule-of-thumb comparison against check-lists. Exploratory measuring or counting without theoretical backup.

3.d Formal analysis

Logical and/or mathematical proofs, including mathematical statistics.

3.e Systematic experience

Theoretically motivated experiments. Reliable reproduction of previously hypothesized or predicted phenomena of analysis to the domain of digital forensics, with the goal of revealing how research in the field of digital forensics is suffering from the same issue that software architecture research faced a decade ago. Consequently, we also argue that Shaw's conclusion and request for future work, as quoted above, can be transferred from the domain of software engineering to the domain of digital forensics today.

Scientific Maturity of Digital Forensics

The survey of the state of scientificness in digital forensics research is divided into two parts. First, a large statistical overview of 46 papers is given in terms of Shaw's model of scientific maturity [START_REF] Shaw | The coming-of-age of software architecture research[END_REF]. Second, reviewer feedback for the early papers and some recent calls for developments in digital forensics are discussed in order to qualitatively deepen the findings from the statistical overview.

Classification of Conference Papers

This subsection analyzes the papers presented at two IFIP WG 11.9 International Conferences on Digital Forensics and subsequently published in the Springer book series, Advances in Digital Forensics. Shaw's model of scientific maturity [START_REF] Shaw | The coming-of-age of software architecture research[END_REF] is used in the analysis.

For the purpose of discussion, it is sufficient to look at the first conference volume [START_REF] Pollitt | Advances in Digital Forensics[END_REF] from 2005 with 25 contributions, and one recent (sixth) conference volume, Volume VI [START_REF] Chow | Advances in Digital Forensics VI[END_REF] from 2010 with 21 contributions. The exercise of browsing through all the papers in the seven-volume series (at the time of conducting this research) would merely reinforce the argument because the results are similar for Volumes II-V and VII as well as for related journals and conference proceedings. Table 4 shows the raw data for this survey.

Table 4 and Figure 1 show that in both 2005 and 2010, the majority of papers do not reach Level d in any of the categories. However, a trend exists towards better evaluation efforts -with comparatively more work in Category 3.c -from 2005 to 2010. The large number of papers in Category 2.b in combination with Categories 1.a or 1.c indicates that many authors in the field of digital forensics are working in an engineering mode in which a useful solution is the goal, and not a theoretical explanation. Combinations of Categories 1.b and 2.c are rare in the table; this indicates a scientific research mode with an interest in knowledge for its own sake. Figure 1 shows the shrinking of the lowest value "-a-" in all three quality categories from 2005 to 2010. However, a high value "-d-" rarely appears in 2010.

The raw data in Table 1 is used to create the formal concept lattice visualization in Figure 2, which presents the mutual relationships existing between the papers in an intuitive manner. Figure 2 shows the diversity of attribute combinations (e.g., "1.a-2.b-3.b") extracted from Table 4, from all the papers in 2005 and 2010. The sixteen circles in the lattice in Figure 2 represent sixteen different attribute combinations. Small circles denote rare combinations while large circles denote frequently occurring combinations. The second most frequent combination is "1.c-2.b-3.b" (eight instance papers) represented by one of the two big circles on the right side of the lattice. These are typical engineering papers that focus on a useful skill and prove ability by pointing to a software implementation.

The third most frequent combination is "1.c-2.b-3.c" (seven instance papers) represented by the other large circle on the right side of the lattice. These papers are also engineering-oriented, but they include additional efforts towards evaluating the properties of a software implementation, instead of merely presenting its existence as a proof-of-concept.

All together, these 9 + 8 + 7 = 24 papers correspond to slightly more than 50% percent of the 46 papers analyzed in the two conferences.

Reviewer Perspectives

One of the authors of this paper served as the program co-chair of the second conference (in 2006). The reviews sent to the authors of accepted and rejected papers were still available. The feedback to the authors was concatenated and scanned for comments that would confirm or refute the quantitative classification. Many reviews were positive, but only a few reviews suggested that the corresponding papers met the requirements of a mature discipline. Much of the positive feedback was based on the novelty of the idea in the paper, the way the paper extended the boundaries of digital forensics, or the fact that the paper covered a topic that was important in some way or another. One reviewer, for example, stated that "despite its shortcomings, I believe the work is interesting for two reasons: it provides an opportunity for digital forensics people to take a look beyond the hard drive; and raises the important issue of" considering a specific facet of forensics during the development of new systems. It is a discipline finding its feet that commends worthwhile extensions and critiques those that seem unnecessary. Note that in quoting from a review, verbiage that may identify the paper is redacted.

As can be expected for a new discipline, most of the research feedback focuses on the boundaries of the field as well as initial explorations that show promise.

One positive comment was "This paper looks at a relevant problem and gives a simple solution for it." More critical are the comments that draw the boundaries closer than authors have hoped: "This is not a digital forensics topic. It is a computer security topic" or "The motivation for this work is not obvious." "The connection made to forensics, albeit not deniable, is quite tenuous" and "Despite the title, the paper does not address forensic issues" are two additional comments dealing with the boundaries of the discipline. Referring to Table 1, it is clear that these comments are at the low end of the scale.

It should be noted that a good number of papers explore questions of the form "What is X?" and more often "Is X possible?" (Table 1). Each of these papers typically elicited a statement from a reviewer that the paper shows that X has potential. As such, the papers met reviewer expectations, although the reviewers often wanted tools that could shift the boundaries. In other words, proposing a system to achieve X was acceptable. However, with X as the research product, some additional functionality was expected, which is indicative of an increase in the research setting scale.

Research Product

The research product dimension included the most critical feedback. The community mainly comprises individuals who often have one foot in academia and the other in practice. The practitioners want tools that provide a competitive advantage. However, even from a pure scientific standpoint, research products (new tools, techniques and theories) are likely to push the research setting scale to higher levels.

Examples of comments dealing with the research product dimension are:

"The primary flaw with the paper is that the work is not presented in enough detail for the underlying technology to be used or replicated." "This is not really a research paper. It is more of a hands-on lab manual." "Instead of discussing how this tool could benefit the area of digital forensics, the author focused on how the tool is built and functions." "It would have been nice to see an analysis of an implementation, what were the end requirements of the investigator for initializing and using the system on a compromised network. As well as a study on the amount and type of logging that is necessary." "The paper is definitely one I would like to see developed, but as the document is I found it hard to find significant value." "This paper presents a sketch of an architecture for recording and retrieving TCP/IP network data in a . . . system."

"No new material is contributed and some vital current methods/techniques for establishing location during a network event are missing." "There is no mention of how these things will be done other than stating that they are future work, which really should have been done." "It is more like a position paper." "In terms of pure computer science, this is yet another file format and I find the basic design reasonable."

The (explicit or implied) critique above is of the form that this is "yet another" solution to a known problem. The fact that "yet another" tool or technique has been developed is not necessarily bad. In an emerging field, it may be fatal to prematurely suppress alternative new ideas. Solutions that venture beyond the beaten track may be the ones that eventually have broad impact.

However, a number of solutions were critiqued in that the mere fact that they were novel was no longer sufficient. Many of the comments called for a greater emphasis in the validation technique dimension rather than a deepening of the research product dimension: "Also, the paper should have included experimental results to make it more convincing and solid." "My question is how do you arrive at 30% and 15%?" "At a minimum, the authors should convince the reader that there are many things mentioned in the paper that are technology invariant."

"We should have a good start on [some specific forensic issue] but are not working on it from the scratch."

Validation Technique

The reviewer feedback reflects a number of issues regarding the validation dimension described in Table 3.

One recurring theme was doubt that a solution was correct. One reviewer stated "the analytical results in the paper heavily rely on [some] assumption. Without this assumption, the analytical results would not be valid. But in most real-world scenarios, this assumption is invalid." A related remark about a different paper questions the data used, rather than an assumption: "I would like to be convinced that this is not a toy or contrived problem. The authors could do this by validating their algorithm on actual data, rather than on generated data."

Some other attempts at validation were not met with the same skepticism, but pointed out that the validation was incomplete in some respect. For example: "One of the key aspects of this paper is the new . . . protocol, which even the author says has not been proven to work as advertised." In another instance, a reviewer laments "Currently the paper does not provide any evidence that such a relationship exists." In one case, the absence of validation is noted: "One thing lacking is a validation of the model."

As a final illustration, consider the following remarks about missing details, which primarily affect repeatability: "My main problem with this paper is that some very important details are missing. The authors talk about quantifying the confidence of a forensic examination, but give no information whatsoever how this quantification is done."

"The main problem with the paper is its relative vagueness." "What is the standard deviation of the frequencies and other results?"

Stability and Fluctuation of the Community

The maturation of an emerging field of research is also related to the stability and fluctuation of the community of researchers who are active in a field. The arguments encouraging these aspects are:

Serious researchers, who have confidence in the worthiness of their own work, do not tend to abandon their field of work prematurely.

New researchers tend to flow into an emerging research field as others begin to recognize the relevance of the field. Some fluctuation is to be expected by the natural retirement of the pioneers and "founding fathers." Short-term fluctuation is to be expected due to the co-authorship of student-researchers, who often depart the research scene after having obtained their postgraduate degrees.

The long-term existence of a small set of "gurus" and the high fluctuation rate of student co-authors are likely symptoms of esoteric stagnation and lack of external popularization of the field.

To this end, we have computed a formal concept lattice that represents the "community" during the years 2005 and 2010, based on the authorship of all the papers from the two conferences. Figure 3 shows a lattice graph of the overall author community, with the 2005 community on the left-hand side and the 2010 on the right-hand side. Research clusters are marked using circles, and the middle-ground represents a continuity of researchers who co-authored papers in 2005 and 2010.

The lattice graph shows rapid fluctuation in the community of coauthors during the relatively short period of time between 2005 and 2010, with only a small number of co-authors present in both 2005 and 2010. Some clusters of researchers are recognizable, but on the other hand, there are also a considerable number of contributions from outside the clusters. In other words, the research community depicted in Figure 3 does not suffer from unhealthy inbreeding. On the other hand, the rather small area of personal continuity during a short time span of only five years might be a cause for concern.

Conclusions

This paper has attempted to evaluate the scientific maturity of digital forensics. The statistical review and the qualitative remarks demonstrate that the lack of scientificness that characterized software engineering a decade ago is currently present in digital forensics research. Like Shaw [START_REF] Shaw | The coming-of-age of software architecture research[END_REF] did in the case of software engineering, we emphasize that digital forensics must become more scientific and we urge our colleagues to redouble their efforts to increase the level of scientificness. We also believe that Shaw's model provides a strategy for incrementally improving the scientificness of digital forensics research to the point where the discipline can be considered to be scientifically mature.

Figure 1 .

 1 Figure 1. Shrinking of the lowest value in all three quality categories.

Figure 2 .

 2 Figure 2. Method variety in the papers from 2005 and 2010.

Figure 2

 2 Figure 2 shows a considerably large methodical variety in the rigor of the papers: The most frequent attribute combination is "1.a-2.a-3.a" (nine instance papers) represented by the large circle on the far left of the lattice in Figure 2. Papers with this attribute combination are suggestive, informal and new idea or proposal papers.

Figure 3 .

 3 Figure 3. Lattice showing the early (2005) and recent (2010) author communities.

Table 1 .

 1 Dimension 1: Research setting[START_REF] Shaw | The coming-of-age of software architecture research[END_REF].

	Dimension Setting Type	Typical Questions
	1.a	Feasibility	Is there an X? Is X possible at all?
	1.b	Characterization	What is X like? What do we mean by X? What
			are the important characteristics of X? What
			are the varieties of X, and how are they related?
	1.c	Capability	How can I accomplish X? Is there a smarter
			way of accomplishing X?
	1.d	Generalization	Is X always true of Y? Given X, what is Y?
	1.e	Valuation	Is X more desirable than Y? How do I decide?

Table 2 .

 2 Dimension 2: Research product[START_REF] Shaw | The coming-of-age of software architecture research[END_REF].

	Dimension Product Type	Typical Approach or Method
	2.a	Qualitative or de-	Organize and report interesting observations.
		scriptive model	Suggest and argue for generalizations from ex-
			amples. Structure a problem area and formu-
			late the right questions. Analyze a system or a
			project in an informal manner.
	2.b	Technique	Invent new ways to do some tasks, includ-
			ing procedures and implementation techniques.
			Develop a procedure for choosing among alter-
			natives.
	2.c	System of know-	Embody results in a systematic context. Use
		ledge or engineering	system development as a source of insight and
			carrier of further results.
	2.d	Empirical predic-	Derive predictions from observed data.
		tive model

Table 4 .

 4 Classification of IFIP WG 11.9 Conference papers.

	Year 2005 (Early)	Year 2010 (Recent)
	Paper Classification	Paper Classification

Acknowledgements

The authors thank Candice le Sueur for her assistance with writing the introductory remarks. The authors also thank the anonymous reviewers and workshop participants for their constructive comments.