Divide and Conquer: Partitioning OSPF networks with SDN

Software Defined Networking (SDN) is an emerging network control paradigm focused on logical centralization and programmability. At the same time, distributed routing protocols, most notably OSPF and IS-IS, are still prevalent in IP networks, as they provide shortest path routing, fast topological convergence after network failures, and, perhaps most importantly, the confidence based on decades of reliable operation. Therefore, a hybrid SDN/OSPF operation remains a desirable proposition. In this paper, we propose a new method of hybrid SDN/OSPF operation. Our method is different from other hybrid approaches, as it uses SDN nodes to partition an OSPF domain into sub-domains thereby achieving the traffic engineering capabilities comparable to full SDN operation. We place SDN-enabled routers as sub-domain border nodes, while the operation of the OSPF protocol continues unaffected. In this way, the SDN controller can tune routing protocol updates for traffic engineering purposes before they are flooded into sub-domains. While local routing inside sub-domains remains stable at all times, inter-sub-domain routes can be optimized by determining the routes in each traversed sub-domain. As the majority of traffic in non-trivial topologies has to traverse multiple sub-domains, our simulation results confirm that a few SDN nodes allow traffic engineering up to a degree that renders full SDN deployment unnecessary.

I. INTRODUCTION
Distributed IP routing protocols, like OSPF or IS-IS, have worked consistently and predictably in the current Internet and have proven their reliable operation over time. Software Defined Networking (SDN), on the other hand, is a new networking paradigm based on a logically centralized and programmable control plane, that has gained a lot of attention recently. In fact, most network equipment vendors have announced the intention to build devices that support the OpenFlow protocol, the de facto SDN messaging standard, or have already released OpenFlow-capable products [1].
Migrating to a fully SDN-enabled operation is however not without issues and new costly investments. In fact, ISPs are still reluctant regarding the change of the control plane paradigm in their networks from distributed to centralized, as distributed routing protocols operate consistently and predictably over years, efficiently control real life conditions, and reliably re- cover from network failures. A migration to SDN, on the other hand, requires new hardware, new tools, and new expertise for network administrators, while SDN still fights with some hard-to-kill scalability preconceptions [2]. It is therefore no surprise that a lot of work has recognized the importance of the so-called SDN/OSPF hybrid networking paradigm [3]- [6] and many OpenFlow devices support a hybrid mode. In the current approaches, the SDN nodes build their regular forwarding tables from OSPF, while the SDN controller can insert higher priority rules (also with more sophisticated matching parameters).
In this paper, we propose a new method for SDN/OSPF hybrid networking. Our method is fundamentally different from any previous work as we partition the initial OSPF domain with SDN nodes into sub-domains, such that routing protocol updates for inter-sub-domain paths can be overridden at SDN border nodes by the SDN controller, e.g., for traffic engineering purposes. This requires that neighboring sub-domains are connected only via SDN nodes and do not have any direct links otherwise. The advantage of our idea over other hybrid approaches is that our partitioning method can be implemented into an operational OSPF network by operating the SDN nodes initially (i.e., during the migration) in plain OSPF mode. It follows that the SDN nodes in our scheme belong to all sub-domains to which they are connected. Figure 1 illustrates the idea. When all sub-domain border nodes are replaced with SDN-enabled devices and an optimized routing has been determined, the SDN nodes start the update process in the individual sub-domains by flooding routing updates that are individually tuned per sub-domain. Our method capitalizes on the advantages of distributed routing protocols by letting the routing inside each sub-domain be based on OSPF solely so that it remains unchanged and stable at all times. At the same time, inter-sub-domain routes can be optimized by determining the routes in each traversed sub-domain. As the majority of traffic in non-trivial topologies has to traverse multiple subdomains, our simulation results confirm that a few SDN nodes allow traffic engineering up to a degree that renders the full SDN deployment unnecessary.
The rest of the paper is organized as follows: Section II discusses the related work and Section III presents the network architecture. The mathematical model of the traffic engineering logic is presented in Section IV. Section V presents the performance study and Section VI the conclusions.

II. RELATED WORK
Our method appears similar to the partitioning of an OSPF domain into so-called OSPF areas [7], however the use is different, as OSPF areas are used to simplify the administration of large topologies and to reduce the amount of protocol traffic. Our intention is also different, as we partition the OSPF domain to allow SDN-based traffic engineering by controlling the routes of inter-sub-domain traffic.
The SDN/OSPF hybrid networking paradigm has been previously analyzed and explained to a great deal in [3]- [6]. For the capability of the SDN controller to insert higher priority rules into the forwarding tables, this has also been coined as "policy based routing on steroids" [8]. The "topology-based hybrid SDN model" by Vissicchio et al. in [9] differs from the other approaches in this respect, and is interesting to us, as it partitions the network into zones, whereby each node belongs to one zone only. However, the zone approach is different from our concept of sub-domains, as a zone is defined as a set of interconnected nodes controlled by the same paradigm (i.e., SDN or OSPF). In contrary, a sub-domain in our approach is a subgraph of OSPF routers, while the SDN nodes participate in the OSPF.
There are other architectural solutions for traffic engineering (TE), most prominently MPLS. However, we argue that unlike our method, MPLS requires a full deployment in the entire topology and it adds another architectural layer to the network (including its overhead in the data plane). Only a full migration to SDN would actually provide equal performance in terms of TE. Both solutions however, i.e., MPLS and SDN, assume the previously mentioned change to the centralized control plane paradigm. In contrast to these solutions, our method relies mainly on OSPF, while optimized routes are injected into the regular protocol operation by individually tuned routing protocol updates. Our results also show that our method requires relatively few SDN nodes to achieve the same traffic engineering capability to the one with the full MPLS or SDN deployment.
Finally, an intuitively similar approach would be to partition the initial OSPF domain and connect the sub-domains with BGP, while BGP can then be used for load balancing, like shown in [10]. The degree of freedom here regarding routing optimizations are in fact similar to what our method can offer. However, our method does not require the partitioning of the initial routing domain into multiple autonomous systems and provides a clean separation from the BGP setup that operative WANs have already in place.

III. NETWORK MANAGEMENT ARCHITECTURE
We propose an SDN/OSPF hybrid network management subsystem, with a TE scheme applicable to a single OSPF routing domain. A routing update is referred to as Link State Advertisement (LSA) and an OSPF router participating in the protocol distributes all its topological information by flooding LSAs throughout the entire network. Figure 2 depicts the assumed Layer 3 network management architecture. As it can be seen, the actual network includes both OSPF and SDN routers. The SDN nodes are connected to the SDN controller and the proposed network management subsystem, referred to as Hybrid Network Manager (HNM), uses the controller's northbound API. As our partitioning-based method requires some sort of all-knowing centralized control intelligence, we consider the implementation as a sort of network application on top of the SDN controller. Because the OSPF protocol advertisements are essential here, the used SDN controller must be configurable to simply forward (without any processing) all LSAs received by the SDN nodes to the HNM, as well as to simply forward the LSAs generated by the HNM to the SDN nodes.
1) Hybrid Network Manager: To gather all the data relevant to Traffic Engineering (i.e., topology, SDN node placement, traffic, and routing), we assume that the HNM implements a Network Information Access Interface that has comprehensive access to various functions and data in the OpenFlow controller, and preprocesses and does the re-formating of this data for the TE Engine, as well as it extracts the routing information from the received LSAs. The Traffic Engineering Engine (depicted as "TE Engine" block in Figure 2) is our main module inside the HNM, which  Fig. 2: The network architecture proposed is used to determine the optimum routing based on the provided data. This module is aware of the OSPF topology partitioning, optimizes the inter-sub-domain routing for load balancing, and computes the according (tuned) OSPF link metrics that will be flooded as LSAs into the individual sub-domains. The TE Engine then passes on the computed routes to the SDN controller's Controller Platform (shown inside the OpenFlow controller) and forwards the LSAs to the corresponding SDN routers.
2) SDN Integration into an OSPF network: Let us assume a single domain and single area OSPF network. Assuming that a few OSPF routers have been replaced by the SDN-enabled devices, the first step for integration into an OSPF networks is to configure the SDN nodes to operate autonomously in the OSPF mode. When the proposed control and management architecture is fully deployed (i.e., the HNM is operating on top of the SDN controller), the sub-domain border nodes can be switched over to SDN mode. From this time on, the SDN nodes send the authentic LSAs (depicted as the black packets marked with an A) received from their OSPF neighbors to the HNM, where they are processed. During the following initialization phase, the HNM is not altering any routing and replies with LSAs according to regular OSPF operation. This phase is used by the HNM to gather all required topology and routing information from the SDN controller and the LSAs received from the OSPF routers. This also involves the logical partitioning of the single OSPF domain into sub-domains depending on the SDN node placement. When the initialization phase is completed (i.e., when the HNM has all data available), the HNM switches over to the load balancing (or, TE) phase, in which it computes the optimum routes that are then translated into link metrics for the tuned LSAs (depicted as the red packets marked with a T). The HNM computes LSAs for load balancing individually depending on the sub-domain and the advertising border node. It then forwards these LSAs via the OpenFlow channel to the corresponding SDN nodes, which distribute them in the corresponding subdomain via flooding.
3) SDN Node Placement: To enable the separation of the OSPF domain into distinct sub-domains, a few SDN-enabled routers must be placed in strategic positions in the network, such that their removal partitions the topology into disconnected components. Obviously, the way the network is clustered into subdomains is determined solely by the operator's choice of nodes that will be exchanged with SDN nodes, i.e., the sub-domains are determined only once in the beginning and can be changed only by adding new or changing the position of existing SDN nodes. In graph theory parlance, this means that the SDNenabled routers must constitute one or multiple vertex separators. An example of how to partition a topology is shown in Figure 1, where it can be seen that the removal of any two SDN nodes separates the topology into two disconnected subgraphs. Evidently, the SDNenabled nodes have to be placed at the weak points of the topology from a network reliability perspective. However, it is one of the strengths of our hybrid scheme that in case of a failing sub-domain border node, OSPF takes care of finding alternative paths via other border nodes. We control the routing of intersub-domain flows only by determining which border node is preferred over the others (by the advertised link metrics), and in case that preferred node fails, the next least cost route via a different border node is automatically used.
It should be noted that the partitioning we use in this paper is rather simplistic: For a given number of SDN-enabled routers, we chose those nodes to be replaced that result in the partitioning with the maximum number of inter-sub-domain flows in the network. Better partitioning strategies are in fact likely to yield better results (outside the scope here).
4) LSA Tuning: The partitioning of the OSPF area allows to advertise routing updates customized per sub-domain, which in turn enables to control the routing of traffic flows between the sub-domains. It should be noted that the OSPF routing of sub-domaininternal traffic is not affected at all.  Table I, grouped in blocks according to the used LSA modification. It can be seen in Table I that by altering the link metrics in the LSAs before being flooded to nodes a and b according to the way depicted in second subfigure of Figure 3, flows a → d and b → c change their routes so that the link between a and b is relieved and the load on the link between c and d increases instead. This poses just a slight modification, which might come in handy when link a − b is overloaded while link c − d provides enough spare capacity. The third sub-figure of Figure 3 shows the possible routing changes, when even topology information is altered in the flooded LSAs: by advertising the non-existing links y − c and x − d, both with low link metrics, all traffic for c exits the upper sub-domain via node y and all traffic for d exits via x (like shown in the third block in Table I), which wouldn't be possible only by altering link metrics of existing links.

IV. LOAD BALANCER MODEL FOR TE
We now present the Integer Linear Programming (ILP) model used for the load balancer in our TE engine. All parameters and variables used are listed in Table II. We assume that all OSPF paths inside subdomains (including their accumulated link metrics) are constant and known. It should be noted that the novelty of the routing scheme in our model requires newly defined constraints on routing which makes the model rather unique and challenging: While OSPF paths must be alternated with SDN links, SDN links

LSAs Traffic Flow Routing Path
Original  The routing constraints: A valid routing path according to our method is a combination of OSPF paths and SDN links, see the flowchart of Figure 4. Note that our notion of the terms OSPF path and SDN link differs from the intuitive usage. We define an SDN link as a directional link between two nodes, whereas the source of the link has to be an SDN node and the destination of the link can be any (SDN or OSPF) neighboring node. An OSPF path, on the other hand, is defined as the unique least cost path (whereby the mechanisms like Equal Cost Multi Path are not considered) between a (non-SDN) OSPF node and any other (SDN or OSPF) node within the same sub-domain, which also does not traverse any SDN link (like defined previously). To illustrate this definition: the directional link from an SDN node to any of its neighbors can be used as an SDN link, while the same can not be part of any OSPF path. Figure 4 shows an example network with the routing scheme proposed. The source node S has exactly one least cost path to each SDN border node (X and Y ) in Sub-Domain 1. Thus, the route from S to D starts either with OSPF path P 1 or P 2, depending on the cost metric for the routing to D advertised by X and Y . The next element in the route to D is an SDN link. As an SDN node's flow table can be arbitrarily configured, e.g., for packets matching source addresses of traffic from S and destination addresses of traffic to D, we see that P 1 can be continued with SDN links L1, L2 or L3. In fact, P 1 can be continued even with SDN links L1 and L4 successively, whereby we'd like to note the self loop of the SDN link box in the flowchart: Because forwarding in SDN nodes is arbitrarily configurable and not constraint by OSPF, SDN links can be concatenated arbitrarily. Arriving at any of the two first OSPF nodes (node a or node b) in Sub-Domain 2, we have no choice for the next element  To assure in our ILP model that there is a valid routing path for each flow, we first require that exactly one forwarding entity (i.e., an OSPF path or an SDN link), which connects to the source node of the said flow, is used. In other words, routing has to start at the source of the flow: ∀f ∈F, ∀n ∈ N with src(f, n) = 1 : We require the same for the end of the routing path, i.e., routing has to end at the destination of the flow: ∀f ∈F, ∀n ∈ N with dst(f, n) = 1 : Common routing models require only a single routing continuity constraint, but like shown in the flowchart of Figure 4, our model allows two different entities for routing (shown as the intermediate states OSPF path and SDN link). Thus our model requires two different routing continuity constraints for intermediate nodes n. First, we demand that the usage of an OSPF path for the routing of a certain flow always requires the subsequent usage of an SDN link (or the node at the end of that OSPF path is already the destination of the said flow): ∀f ∈F, ∀p ∈ P, ∀n ∈ N with dst(p, n) = 1 : Likewise, we demand that the usage of an SDN link for the routing of a certain flow always requires the subsequent usage of another SDN link or alternatively an OSPF path, unless the node at the end of the initial SDN link is already the destination of the said flow: ∀f ∈F, ∀ ∈ L sdn , ∀n ∈ N with dst( , n) = 1 : The routing continuity constraints so far may appear to provide a valid routing, however, they do not prevent routing loops like shown in Figure 5. (Please note that it is not distinguished between the two entities OSPF path and SDN link in Figure 5, as the described problem is of general nature when routing continuity is modeled in ILPs.) While the only valid path from ∀f ∈F, ∀n ∈ N with src(f, n) = dst(f, n) = 0 : This assures that the intermediate node n, if used for flow f , has not more than two routing entities of f in sum that enter and exit the node. Additionally, we need to demand that the source and destination nodes never appear as intermediate nodes along the routing path to avoid loops containing source or destination: ∀f ∈F, ∀s, d ∈ N with src(f, s) = dst(f, d) = 1 : Finally, we need to constrain that routing through SDN border nodes has to be consistent with the advertised link metrics. This means that for a given sub-domain α and for a given sub-domain-external destination node d, we require the usage of a set of link metrics (to be advertised by the SDN nodes in sub-domain α) which is consistent with all used OSPF paths from any sub-domain-internal source node to that destination d: ∀p ∈ P, ∀f ∈F, ∀d ∈ N with dst(f, d) = 1 : With this constraint we assure that OSPF path p is used to route flow f only if the usage is consistent with the advertised set of LSAs for the destination of f . Finally, as we demand that only a single set of LSAs per sub-domain is advertised per sub-domainexternal destination, we also constrain that ∀d ∈ N, ∀α ∈ SD : The lsa and bel parameters used in the last two constraints are entirely pre-computed, and determining all valid combinations of OSPF paths for which there has to exist a distinct set of link metrics is computationally complex. In our first ILP model, we had the link metrics advertised by SDN nodes for every single destination as variables, which is straightforward. This, however, turned out to be computationally too expensive even for small network sizes. For space reasons, we can not explain the algorithm that generates the used lsa parameter, but assume here that it is computed efficiently and is available in the model.

Load balancing as objective function:
The purpose of the used Traffic Engineering scheme is to load balance the network, that is to increase the headroom of the links so that a sudden surge in traffic and large flows are unlikely to congest the network. Therefore, we first define the utilization of a link by which adds the utilization of each flow (i.e., f 's demand divided by 's capacity) that is routed by our load balancer via to the utilization caused by all intersub-domain (i.e., plain OSPF) flows. We now need to define a load balancing objective and there exist various approaches in the literature: The minimization of the maximum link utilization is one of the common models. However, it was discussed in [11] that this approach has issues with unavoidable bottlenecks: In case of a heavy loaded link that can not be relieved during the optimization, the objective to minimize the maximum link utilization doesn't load balance less loaded links at all. This can be avoided with a cost (i.e., penalty) function that increases exponentially with the link utilization. Every link can then be associated with a cost according to its utilization and the objective of the optimization would be to minimize the total cost in the entire network. As ILP models require linear constraints, an exponentially increasing cost function must be emulated with a piecewise linear function (i.e., with a concatenation of straight lines), like proposed in [11]. The set Y of functions {y 0 , y 1 , ...} that we used in this paper is shown in Figure 6, and the intention behind it is as follows. Our ISP prefers to route flows over links with utilization below 60%, and therefore, links with utilization ≤60% generate zero cost. The closer the link utilization gets to 100%, the more sensitive the link gets to traffic   bursts that could cause congestion. The straight lines of Y are fixed such that each of them constitutes the lower bound of the valid cost region for a 5% section on the x-axis, and the gradient doubles stepwise. The link utilization is evidently bounded by 0% and 100% and we constrain the utilization cost for each link to be greater equal than all cost functions. The resulting valid solution space is depicted in Figure 6. The set Y of linear cost functions was therefore defined as with values a and b given in Table III. We accordingly constrain the link utilization cost with: Finally, the objective function is simply: For our performance analysis, we used the Atlanta and Polska topologies from the SNDlib library [12]. Figure 7 shows our resulting graphs, which are the histograms of link utilization, defined as the frequency of the occurrence of a particular link utilization value. Three SDN nodes have been placed according to the heuristic that was explained in Section III, i.e., we chose the nodes providing the maximum number of inter-sub-domain flows. This resulted in a partitioning (also depicted in Figure 7) of the Atlanta network into four sub-domains, whereas three SDN nodes in the Polska network partition the topology into two subdomains.
The experiments in both topologies were conducted as follows: For each individual experiment (the results shown are averaged over hundred trials) we initially used the unpartitioned network and assigned uniform link metrics and determined the OSPF least cost paths, which resulted in minimum hop count routing. We then assigned uniformly distributed demands in the range of 1 Gbit/s to 7 Gbit/s to the traffic flows and determined the link loads resulting from the traffic demand and the routing. After that we assigned link capacities greater equal the link loads and assumed that links are available in the following granularity: 10 Gbit/s, 40 Gbit/s, 100 Gbit/s, and 400 Gbit/s. The resulting utilization of links clearly covers a wide range and was used for the OSPF plot in both histograms in Figure 7, which serves as a kind of "worst case" distribution, as no load balancing is performed.
To generate the results for our hybrid SDN/OSPF load balancing scheme, we partitioned the network into sub-domains and deleted all OSPF paths from the parameter set P that are not consistent with our definition in Section IV, i.e., the paths across sub-domain borders. That scenario was used in each experiment run as input parameters along with the mathematical model explained in Section IV, which then was optimzed on an Intel Core i7-3930K CPU (6 x 3.2 GHz) using the GUROBI solver. A single experiment run took on average less than three minutes. The results of the load balancing scheme is shown as the Hybrid plot in both histograms of Figure 7. The utilization cost function is superimposed in both histograms (the Cost plot) to highlight how smoothly the load distribution of our scheme mirrors the cost function in the range above 80% link utilization.
The improvement through load balancing (i.e., the re-routing of flows from highly utilized links) is marked as shaded area and demonstrates the performance of the proposed TE mechanism. As we can see, the link utilizations of 85% and above occur rarely, while a couple of such heavily loaded links are common in the plain (non-load-balanced) OSPF case. We can also see the occurrence of links utilized above 95% in the OSPF scheme, whereas our proposed load balancing scheme can prevent congestion in the majority of cases. To show the upper bound on traffic engineering (i.e., the "best case" link utilization distribution), we also computed the optimal routing without any OSPF constraints in each experiment run and added this as the Full TE plot in both histograms. This graph shows the distribution when full TE capabilities are deployed in the network, as if MPLS or OpenFlow was available at every node. It can be seen that the advantage is marginal, which indicates that even a small number of    Table IV. Here we can observe some topological differences. The results of our scheme are much closer to the optimum in the Atlanta network than in the Polska network. This reflects the fact that Atlanta network was partitioned into four (instead of only two) sub-domains, which results in a lot more traffic flows that have to cross sub-domain borders, and accordingly more options to traffic engineer the highly utilized links.  In this paper, we proposed a new architecture for a hybrid SDN/OSPF operation, in which a few SDN nodes are used to partition the OSPF domain into multiple sub-domains. We have explained the requirements and assumptions regarding the corresponding network architecture, which suggested that our proposed method can be implemented with ease into common OSPF networks. We showed how OSPF Link State Advertisements can be tuned to optimize the routing. Finally, we illustrated the idea with analysis and numerical results and showed that very few SDN routers are required to achieve results close to the optimum. The low number of required SDN routers also allows that a relatively high number of nodes can remain in the configure-once-never-touch-again operation, which is a known and desired feature from OSPF. The results also suggest that the performance depends on the number of sub-domains in which the original topology can be partitioned into. The proposed hybrid management framework can be easily integrated into the ongoing architectural frameworks, such as IETF ABNO and OpenDaylight. The idea is promising and future work will extend the analysis to a wider range of topologies. We are also interested in more suitable and effective partitioning algorithms, especially in larger topologies.


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.


Enhanced Asymmetric Bilinear Model for Face Recognition

Bilinear models have been successfully applied to separate two factors, for example, pose variances and different identities in face recognition problems. Asymmetric model is a type of bilinear model which models a system in the most concise way. But seldom there are works exploring the applications of asymmetric bilinear model on face recognition problem with illumination changes. In this work, we propose enhanced asymmetric model for illumination-robust face recognition. Instead of initializing the factor probabilities randomly, we initialize them with nearest neighbor method and optimize them for the test data. Above that, we update the factor model to be identified. We validate the proposed method on a designed data sample and extended Yale B dataset. The experiment results show that the enhanced asymmetric models give promising results and good recognition accuracies.

Introduction
Face recognition has been an active research area due to its applications in security entry systems and automatic law enforcement system. Pose variances, illumination changes, and noise from observations make it hard to define a model with promising recognition accuracies. Previous work [1][2][3][4][5] has proven that image variations of faces under varying illuminations could be modeled by linear spaces while view spaces which resulted from varying head poses are considered nonlinear [6]. Manifold learning [6,7], bilinear models [8][9][10], linear dimensionality reduction [11,12], and tensor analysis [13][14][15] have all been applied to solve face recognition problems. Recently deep learning techniques are also employed to solve face recognition problems and have achieved good performances [16][17][18].
Usually, faces need to be aligned before recognition. There has been lots of works which have been done on face alignment [19][20][21][22][23][24][25][26][27][28][29][30]. And it is well known that misalignment will result in recognition accuracy drop [20]. In our work, we explore the possibility of face recognition without alignment. In the proposed algorithm, we concentrate on separating factors that might affect recognition accuracy. To be specific, we use bilinear model to separate a varying factor from recognition target. And we prove in experiments that this separation is effective and required.
Bilinear models [8] are usually used to model systems with two factors and each factor itself is linear given the other factor fixed. Bilinear models for 2D image data have been widely used to solve face recognition problems due to their simplicity in formulation. In this category of solutions, factors introduced in a system are modeled as a symmetric bilinear model or asymmetric bilinear model. In this work, we also introduce asymmetric bilinear model due to its simplicity in representation.
Among all variance factors in face recognition problems, illumination change is one influential and intensively studied factor. Example works on illumination variations in face recognition problem include [9,10], of which work in [10] is closely related to our work. Authors in [10] combine ridge regression into symmetric bilinear model to separate illumination and identity factor. Symmetric bilinear model decomposes input data into two factor matrices representing two factors and an interaction matrix denoting interactions between two factors. Instead of symmetric models, we utilize asymmetric models which decompose input data into a factor matrix and a matrix containing the other factor and interaction matrix. With fewer parameters to optimize, 2 International Journal of Distributed Sensor Networks the asymmetric model does not suffer from convergence problem as in symmetric model. But, due to noise captured in image features, the original asymmetric model is not able to cope with illumination changes in real world face recognition problems.
In this work, we propose a modified asymmetric model for accurate face recognition. As in the original asymmetric bilinear model, we calculate probability predictions with Bayesian rules and expectation maximization method (EM). But instead of initializing the factor probabilities randomly, we initialize them with nearest neighbor method and optimize them for the test data. And we update the factor model to be identified. The enhanced asymmetric model is composed of three modules: calculating factor matrices from training data, initialization step for test data, and optimization and classification step for test data. In the first step, we use singular value decomposition to separate the factor to be identified from other factors based on training data. In the initialization step, a nearest neighbor method is introduced to initialize the joint probabilities of all factors which is further updated in optimization step. In the third step, we update the factor model to be identified. We validate the proposed method on a manually created data and cropped images from extended Yale B dataset. The experiment results show that the enhanced asymmetric models give promising results and good recognition accuracies.
The rest of this paper is organized as follows: in Section 2 we explain the proposed method in detail, including how to use Bayesian rules and EM method to optimize test factors and how to achieve illumination-robust face recognition and identity-robust illumination recognition goal with the proposed method; in Section 3, we validate the proposed method on two types of data: designed data and public available extended Yale B dataset; in Section 4, we will conclude our work and discuss possible future works.

Enhanced Asymmetric Bilinear Model
Bilinear models [8] separate the input data into two factors, described as style and content. Content is the factor to be identified; for example, identity and style are the factors that vary and need to be separated. Bilinear models reduce to the linear model when one factor is fixed. It contains symmetric and asymmetric models. Authors in [10] use symmetric model and take the identity as content and the illumination as style. In a symmetric bilinear model, style and content interact using an interaction matrix. But actually we are not interested in both style and content matrices in a single task classification problem. For simplicity, we choose an asymmetric model and modify it to accurately recognize factors.
Suppose we represent content with a vector of parameters b of dimension and use y to denote dimensional input feature vector of style and content ; an asymmetric bilinear model represents the observation vector y as This formulation can also be written as where A denotes × matrix with entries { } and In a symmetric model, and in (3) are represented separately thus resulting in one more variable.
As in [8], we use singular value decomposition to fit asymmetric model to training data. First we stack ×dimensional input features as follows: .
then we apply singular value decomposition to the observation: The style matrix A is initialized as the first columns of US and the content matrix is initialized as the first rows of V .

Optimizing Factor Matrix for Test Data.
Given test dataỸ of an unseen stylẽ, the goal is to find the matrix containing style factor Ãand content factor b̃approximating test data as precious as possible, that is, to minimize the approximation error , In original bilinear model, optimization is under several assumptions: style matrix of the test data b̃equals style matrix of the training data b̃; the probability of test observation of a specific style and a specific content does not need special way of initialization. Due to captured noise in input feature, the problem in reality is not preciously a linear model. So we add initialization step and update content matrix in optimization. According to experimental results, updating the content matrix b̃instead of keeping it unchanged gives more accurate recognition results.
This variable is introduced as a weight in optimization step. Instead of the random initialization, we set the initial (ỹ | ,̃) as 1 ifỹ has a nearest neighbor y with a stylẽand a content̃and 0 otherwise.

Illumination
Training data Test data Figure 1: In the illumination-robust identity recognition application, we show the split between the training and test data.

The Algorithm.
To minimize the error between the test features and its approximation Ãb̃, we use an EM and add an extra update of the matrix containing content b̃which proves to give more accurate recognition results.
(1) Initialize the matrix containing style factors̃as being equal to that computed from training data , and initialize (ỹ |̃,c) as 1 ifỹ has a nearest neighbor y with a stylẽand a content̃, and otherwise 0.

Illumination-Robust Face Recognition and Identity-Robust Illumination Recognition.
In this section, we explain the possible applications of the proposed method in face recognition problems. First, we define identity as content and illumination as style to show the application of linear models to illumination-robust face recognition problem; see Figure 1. Then we switch content and style and set the illumination as content and identity as style. It is widely acknowledged that the illumination changes could be modeled with linear space but it is not clear if the identity space is also the same case. We design the second experiment to show the application of the proposed method in identity-robust illumination recognition and to test the expansibility of the system. In the following section, we show experimental results of these two experiment settings.

Experimental Results
We validate the proposed method with two categories of data: one is a manually defined sample data and another is a publicly available face recognition dataset. The aim of the designed sample data is to verify the soundness of the proposed method and the second category of experiments is to provide standard results.

Experiment on Designed Data. Suppose we have a tensor
here content denotes the total number of ones in a feature vector and style denotes which positions are set as ones. For example, in the first style, ones occur in the first, third, fifth, and seventh columns. If we use all contents and styles for training and select one content to test the method, the recognition accuracies should reach 100 percent. So we choose the whole tensor as training data and pickỸ as Y(2, : , :).
With the proposed method, we get the experimental results in Table 1. The tables show recognition accuracies and approximation errors in each iteration. From the table, we can see that the proposed method can reach 100 percent recognition accuracy on the designed dataset.

Experiment on Extended Yale B Dataset. The extended
Yale Face Database B contains 16128 images of 28 human subjects under 9 poses and 64 illumination conditions and they provide a subset of cropped images. In our experiment we use the cropped images. With this dataset, we design two sets of experiments: illumination-robust face recognition and identity-robust illumination recognition.
In illumination-robust face recognition, we pick those illuminations with id ranging from 1 to 39 as training and illuminations with id 50 for test. The experimental results for this experiment setting are shown in Table 2. From the table, we can see that after 3 iterations the recognition accuracy reaches the maximum 0.92 and then starts decreasing dramatically.
In identity-robust illumination recognition, we pick those persons with id ranging from 1 to 38 as training and person with id 39 as test. The experimental results for this experiment setting are shown in Table 3  although with similar amount of training data, illumination recognition gives better results than identity recognition. This might be due to sufficient training data (38) for the identity space or illumination to be an easier target. From Tables 2 and  3, we can say that the enhanced asymmetric model gives high recognition accuracies. Recognition accuracies increase quite fast with approximation error decreasing and with several steps, we can achieve the optimum recognition accuracies for our method. We further show a set of experiments exploring the effect of training sample numbers. In illumination-robust identity recognition application, we pick the same test data as the previous experiment but we pick the illumination with identity ranging from 1 to 5 as training in experiment 1 (Exp1), illuminations with identity ranging from 1 to 9 as training in experiment 2 (Exp2), and illuminations with identity ranging from 1 to 13 as training in experiment 3 (Exp3). Experimental results are shown in Figure 2.
From the figure, we can see that, in the term of errors, the training sample numbers differences have an obvious effect in the first and the second iterations but tend to be subtle in the following iterations. In fact, with more training  sample numbers, the optimization tends to be unstable. The best accuracy 92.31% occurs in all experiment settings. In the third iteration, experiment 1 and experiment 2 reach the maximum while experiment 3 reaches the maximum in iteration 6.
The proposed algorithm is further compared with a nearest neighbor method to show the importance of separating style and content. We design the nearest neighbor method applied in identity recognition problem: first, varying numbers of training data are selected (i.e., 5, 9, and 13); then, for each test data, it is compared with all styles (illumination variations in this case) from all contents (face identity in this case); finally, the label of the test data is set as the label of the training data with the minimum distance. The recognition accuracy of the nearest neighbor method is shown in Table 4. From the table, we can see that the raw nearest neighbor method performs very badly on the identity recognition problem here. What is more, when the number of training data increases, the recognition accuracy drops. Note that each training data case has a different style compared to other training data in the dataset. We can see from the recognition accuracies that more training data from variant styles confuses the method. Adding different styles of training data without separating them makes the recognition accuracies worse.

Conclusions and Future Works
In this paper, we present an enhanced asymmetric bilinear model and apply it to illumination-robust face recognition problem and identity-robust illumination recognition problems. By initializing the content and style probability with nearest neighbor method and adding update for content matrix, we achieve quite good recognition accuracies. In the future, it would be interesting to explore the application of the proposed method on models containing more than two factors. Also, we would like to explore applications of asymmetric models on applications other than face recognition.