An Information Extraction Framework for Digital Forensic Investigations

The pervasiveness of information technology has led to an explosion of evidence. Attempting to discover valuable information from massive collections of documents is challenging. This chapter proposes a two-phase information extraction framework for digital forensic investigations. In the first phase, a named entity recognition approach is applied to the collected documents to extract names, locations and organizations; the named entities are displayed using a visualization system to assist investigators in finding coherent evidence rapidly and accurately. In the second phase, association rule mining is performed to identify the relations existing between the extracted named entities, which are then displayed. Examples include person-affiliation relations and organization-location relations. The effectiveness of the framework is demonstrated using the well-known Enron email dataset.


Introduction
Investigations involving text documents and data rely on expressionbased or keyword-based searches [6]. Current digital forensics tools implement search methods that rely on accurate keywords. For example, given the name of a suspect, a search tool would return all the exact and similar occurrences in the data [24]. However, in the vast majority of cases, complete keyword information is not available; this makes it necessary to uncover and use additional information to improve searches.
Information summarization and event extraction from data are extremely useful in forensic investigations. In general, the more information that can be extracted, the more accurate the search. However, digital forensic examiners are often unable to comprehensively review all the keyword matches in a corpus [5]. Text summarization can reduce the time spent on reviewing search hits while ensuring that all the instances of interest are located.
Information extraction systems can extract abstract knowledge from a text corpus or extract concrete data from a set of documents [30]. Information extraction has two phases. The first phase, involving the detection and classification of proper names, is called named entity recognition [31]. Since digital forensics focuses on the who, what, where, when and why of a case, it is essential to recognize named entities such as persons, organizations and locations. For instance, in the sentence "Jeff Skilling (born November 25, 1953) is the former CEO of the Enron Corporation headquartered in Houston, Texas," "Jeff Skilling," "Enron Corporation" and "Houston, Texas" correspond to person, organization and location entities, respectively.
The second phase of information extraction is relation extraction. In a forensic investigation, it is useful to discover relations that are hidden in named entities extracted from large data sets. For example, by analyzing newspaper text, it is possible to discern that an organization is located in a particular city or that a person is affiliated with a specific organization [44]. The relations discovered can then be represented in two forms, as association rules or as sets of frequent items.
This chapter describes a novel information extraction framework that helps find valuable evidence in text documents. The framework has two phases. In the first phase, a named entity recognition approach is applied to the raw forensic data to extract the named entities (i.e., persons, organizations and locations). To assist investigators in finding coherent evidence rapidly and accurately, informative named entities are visualized and highlighted using cloud tags and text clouds. The extracted entities provide a useful overview of the data when a forensic investigator does not know what to look for or has a large number of hits to review. The second phase uses a modified version of the Apriori algorithm [34] to identify the relations among the extracted named entities and visually display the extracted relations. Examples of relations are person-affiliation and organization-location. Experiments are conducted on the Enron email corpus to demonstrate that the information extraction framework is very effective at helping find relevant information.

Related Work
The pervasiveness of information technology has led to an explosion of evidence. In order to handle vast amounts of evidence in a limited time, a number of text analysis approaches have been proposed for forensic investigations [12,14,16,21,25,32,35]. Information extraction, which seeks to extract useful information from unstructured text, has become an active research area in digital forensics. The first step in information extraction is the detection and classification of proper names, which is often referred to as named entity recognition [31]. Named entity recognition is a well-studied problem and has many applications, including focused searches over massive collections of textual data [15], social network analysis [19] and information summarization [36].
Named entity recognition has been applied to news articles [28] and scientific articles [7]. These articles are written for fairly broad audiences and the authors generally take great care when preparing them. However, less time and effort are spent on preparing informal documents; as a result, they contain many grammatical and spelling errors. In addition, informal text generally contains many abbreviations. Techniques have been proposed to improve named entity recognition performance for informal text such as email [29] and web postings [19].
Named entity recognition techniques have also been applied in forensic investigations [4,9,21,22,24,33,41]. Louis et al. [24] have used dynamic Bayesian networks to identify named entities. Kuperus et al. [22] have presented a probabilistic named entity recognition model based on multiple candidate labels that exploits user feedback to obtain increased recall with little loss in precision. However, both techniques do not attempt to discover the relations existing between named entities in forensic investigations.
The second step in information extraction is relation extraction. Relation extraction can be characterized as a classification problem: if two entities are potentially related, it is necessary to determine if they are indeed related [3]. Supervised methods [44,45], semi-supervised methods [10,38] and unsupervised methods [43] have been applied to solve this binary classification problem. In the case of structured data, association rules can be used to simplify relation extraction [26,30]. This work uses the Apriori algorithm [34], a classical association rule approach, to discover the relations among named entities. Al-Zaidy et al. [2] have proposed a similar approach. However, they focus on identifying indirect relationships between a person and a prominent community. An indirect relationship starts from a person and forms a chain connecting to a prominent community; each internal node in the chain is a person that links two documents. In contract, the work described in this chapter attempts to discover named entities and their semantic relations.
Colombe and Stephens [11] discuss visualization techniques for assisting forensic investigations. The Tilebars method [17], for instance, is designed to be a navigational aid for analysts. Whittaker et al. [42] visualize term distributions in histograms to support information retrieval from speech archives. Schwartz and Liebrock [37] apply visualization to digital forensic string searches. On the other hand, the information extraction framework presented in this chapter uses tag clouds [18] to visualize named entities and also leverages visualizations of the relations between named entities, providing forensic investigators with an intuitively appealing means to comprehend and analyze large bodies of textual evidence.

Information Extraction Framework
This section describes the information extraction framework for finding evidence. As shown in Figure 1, the framework has two main phases. In the first phase, a named entity recognition approach is applied to the raw forensic data to extract the named entities (i.e., persons, organizations and locations). In the second phase, a data mining tool is used to identify the relations existing between the extracted named entities. To assist investigators in finding coherent evidence faster and more intuitively, relevant informative named entities are highlighted with cloud tags and the relations among the named entities are visually displayed.

Named Entity Recognition
Given a sentence, the named entity recognition approach segments words that are parts of named entities and then classifies each entity by its type (person, organization, location, etc.). Existing named entity recognition approaches are divided into two categories: (i) rule-based approaches [31]; and (ii) machine learning approaches [8,39]. A rulebased approach relies on linguistic knowledge, in particular, grammar rules, while a machine learning approach relies on a labeled corpus [1]. A rule-based approach achieves better results in many domains because the rules can be adapted very precisely and are, therefore, able to detect complex entities. However, in the case of an unrestricted domain, it would be expensive in terms of cost and time to derive rules. On the other hand, a machine learning approach is more flexible and is able to identify uncommon patterns of named entities that are not specified in the regular expressions of rule-based systems [1]. The proposed named entity recognition framework exploits the complementary performance associated with the rule-based and machine learning approaches by taking the union of the results provided by the two approaches to improve the recall.
The machine learning approach used in the proposed framework engages the conditional random fields model [23] to identify named entities, primarily because it provides excellent performance for many information extraction tasks [39]. A document is expressed as a vector X = (x 1 , . . . , x i , . . . , x n ) where n is the number of features and x i is the relative frequency of feature i in the document. After all the documents have been represented in this way, the conditional random fields model can be applied to extract the named entities. Lafferty et al. [23] define the probability of a label sequence y given observation sequence x to be the normalized product of potential functions of the form: where t j (y i−1 , y i , x, i) is a transition feature function of the entire observation sequence and the labels at positions i and i − 1 in the label sequence; s k (y i, , x, i) is a state feature function of the label at position i and the observation sequence; and λ j and µ k are parameters that are estimated from training data. When defining feature functions, a set of real-valued features b(x, i) of the observation are constructed to express some characteristic of the empirical distribution of the training data that should also hold in the model distribution. An example of such a feature is: b(x, i) = 1 if the observation at position i is the word "September" 0 otherwise (2) Each feature function takes on a value of one for real-valued observation features b(x, i) if the current state (in the case of a state function) or previous and current states (in the case of a transition function) take on particular values.
In the remainder of this chapter, the notation is simplified by writing: where each f j (y i−1 , y i , x, i) is either a state function s(y i−1 , y i , x, i) or a transition function t(y i−1 , y i , x, i). This allows the probability of a label sequence y given an observation sequence x to be written as: where Z(x) is a normalization factor. In this work, the conditional random fields model was executed using publicly-available Python code [13]. Default settings were used for all the parameters. The rule-based approach largely follows the guidelines listed in [27]. However, several changes have been introduced to make the extracted named entities more practical and to improve the recall of the named entity recognition system. For example, when analyzing email, a check was made to see if a token in the header was equal to some token w.

Relation Extraction
Forensic investigators usually browse forensic data using queries such as "Select all the people who have a relation with the suspect" or "Select all the people who are related to a specific organization." This can be implemented using relation extraction, which identifies the significant relations existing between entities.
This work incorporates a modification of the Apriori algorithm [34] to perform relation extraction. The Apriori algorithm is a classic algorithm that finds relations in data. For example, the rule, Diapers → Beer, suggests that a strong relation exists between the sale of diapers and the sale of beer because many customers who purchase diapers also purchase beer [40].
An indication of how frequently an item or a relation occurs is measured by the support function supp(s). The support of a rule A → B is the percentage of documents in the corpus that contain A ∪ B. The supp measure is important because a rule that has very low support may occur simply by chance.
The confidence measure conf, on the other hand, measures the reliability of the inference made by the rule. For a rule A → B, the higher the confidence, the more likely it is that a document containing A also contains B. Given a set of documents containing extracted named entities, it is necessary to find all the rules with supp ≥ minsupp and conf ≥ minconf where minsupp and minconf are two constant thresholds. Interested readers are referred to [34] for details about the Apriori algorithm.
In the original Apriori algorithm, confidence is the only measure used to verify rules. However, although the confidence of a rule may be high, the rule could still be misleading. For instance, consider the situation shown in Table 1 where there are 100 transactions that contain either tea or coffee. Furthermore, assume that the conf threshold is 70%. From Table 1, for the rule Tea → Coffee, conf = P(Coffee|Tea) = 0.75, indicating that the rule is valid. Nevertheless, a person who does not purchase tea is more likely to purchase coffee since P(Coffee|Tea) = 0.9375. To address this problem, the lift score = P(Y|X)/P(Y) is used to evaluate rules of the form X → Y . Only rules whose lift scores are larger than one are considered.

Experiments and Analysis
This section describes the experiments performed on a real-world forensic dataset and presents an analysis of the results.

Dataset Description
Because no authoritative real-world forensic datasets are available to evaluate the performance of a named entity recognition system in forensic investigations, a portion of the texts from the Enron corpus was manually labeled. The raw Enron corpus made public by the U.S. Federal Energy Regulatory Commission contains 619,446 messages belonging to 158 users. Klimt and Yang [20] subsequently cleaned up the corpus by removing certain folders associated with each user because they appeared to be computer-generated. The cleaned Enron corpus used in this work has 200,399 messages belonging to 158 users with an average of 757 messages per user.

Data Pre-Processing
The texts were tokenized using the NLTK natural language toolkit. Next, non-alphabet characters, numbers, pronouns, words with two characters or less, punctuation and stop words (common words appearing frequently) were removed from the text. Finally, the WordNet stemmer was applied to reduce the size of the vocabulary and address data sparseness.

Experimental Results
This section discusses the experimental results.
Named Entity Recognition. The experiment to evaluate the effectiveness of the named entity recognition system used 200 randomlychosen messages from the Enron corpus containing more than 100 words as test data. Three natural language processing researchers were then asked to manually label each entity tag (i.e., person, organization, location, etc.). Recall, precision and F 1 measures were used to evaluate the performance of the named entity recognition system: precision = #correct identified entities #total entities found (5) recall = #correct identified entities #total correct entities (6) Table 2 summarizes the results. Since higher values for the three measures indicate more accurate extraction, the results indicate that the named entity recognition system is effective at identifying persons, organizations and locations. In particular, the system has a relatively high recall for persons and organizations. Named Entity Visualization. Forensic investigators are often overwhelmed by the number of keyword matches when dealing with large datasets. To assist investigators in rapidly finding coherent evidence, a text cloud visualization of word importance is used to discriminate the extracted named entities from the original text. Figure 2 shows a text cloud display of a random sample of text from the Enron corpus. The named entities are represented using larger fonts than the other entities.
Suppose that an investigator has no prior knowledge of the data and, thus, does not what to look for. In such a scenario, tag clouds [18] may be used to quickly visualize all the extracted named entities with respect to the name category. Figure 3 shows three tag clouds for persons, organizations and locations, respectively. The importance of each tag is expressed using its font size. For example, "John" and "Jeff" are the top person names in Enron Corp. Note that the tag cloud representation can enable a forensic investigator to quickly draw conclusions from a massive volume of data.  Relation Extraction. In a forensic investigation, it is also important to discover interesting relations that are hidden in named entities. For example, a useful query might be: Select all the persons who have a relation with the suspect. The Apriori algorithm was modified to discover relations existing between name entities (i.e., persons, organizations and locations). The threshold minsupp was set to 150. Table 3 shows some of the relations with relatively high support. Forensic investigators can use this technique to identify a suspect using logically-related queries. Note that traditional exact matching techniques often fail to provide useful results. In addition to discovering direct relations, the information extraction framework can also construct implicit social networks from email activities. For example, although Jeffrey K. Skilling and Matthew Lenhart had no direct email exchanges, a relation between them exists as a result of the rules:"ECT → Jeffrey K. Skilling" and "Matthew Lenhart → ECT." In particular, Jeffrey K. Skilling is the CEO of ECT while Matthew Lenhart is an ECT trader, which manifests the relation that Skilling is the boss of Lenhart.

Conclusions
The information extraction framework presented in this chapter is specifically designed to enhance forensic investigations. It applies a named entity recognition approach on raw forensic data to extract named entities. Following this, association rule mining (i.e., the Apriori algorithm) is applied to identify the relations existing between the extracted named entities. Relevant and informative named entities are visualized using tag clouds, and new relations existing between the named entities can also be discovered. Experiments using the well-known Enron email corpus demonstrate the effectiveness of the framework.
Future research will extend the named entity recognition system to identify addresses, vehicles, narcotics and personal characteristics. It will also attempt to develop social networks of criminals and suspects based on the extracted entities. Additionally, it will apply user interest profiling to reveal indirect relations between individuals and identify individuals who have specific interests over time.