Alex Nelson

XML CONVERSION OF THE WINDOWS REGISTRY FOR FORENSIC PROCESSING AND DISTRIBUTION

Keywords: Windows Registry, Registry analysis, XML syntax, RegXML

The Windows Registry often contains key data that help determine the activities performed on a computer. While some forensic tools format Registry data for common questions that are required to be answered in digital investigations, their output is geared for standalone use, not for indexable content.

This paper describes RegXML, an XML syntax designed to represent Windows Registry hive files. RegXML captures the logical structure of a hive and notes the locations of found data within hive files. The paper also describes a Python library designed to be used with RegXML and the results obtained upon applying the library to analyze two forensic corpora. Experimental results are presented based on hundreds of disk images, thousands of hive files and tens of millions of Registry cells.

Introduction

The Windows Registry is a rich source of information in forensic investigations. Several commercial forensic tools can be used to conduct keyword searches of a Registry, much like they can be used to search through a file system. However, they perform what can be characterized as "first-order analysis" [START_REF] Garcia | Bulk Extractor Windows Prefetch Decoder[END_REF] -data such as files and Registry values are examined for the information they contain and the scope of the search is confined to a single computer or a single case. This style of analysis is commonly employed in forensic practice and betrays an underlying problem: forensic analysis is fundamentally a silo activity.

Silos exist because it is difficult to share information about cases, both for legal and technical reasons. The legal reasons arise from the need to maintain confidentiality. However, the simplest, most-encompassing technical reason is the difficulty of expressing the data in a structured, comparable format. This paper proposes RegXML, a well-structured, interchangeable format for the Windows Registry. RegXML provides a mechanism for scaling forensic analyses to thousands of data sources. The data sources do not need to be complete, and can be excerpts. Examples include a collection of keys known to represent the Registry footprint of steganographic software [START_REF] Zax | Faust: Forensic artifacts of uninstalled steganography tools[END_REF], or malware summaries from antivirus vendors that comprise exchangeable XML annotations of keys, values and relative modification times.

An analysis of many data sources is categorized as bulk [START_REF] Garfinkel | Forensic feature extraction and cross-drive analysis[END_REF] or secondorder analysis [START_REF] Garcia | Bulk Extractor Windows Prefetch Decoder[END_REF] analysis. Such an analysis is easily realized using a scriptable interface to the analyzer program and a well-structured data format that faithfully represents the contents of the original input items. To perform Registry analysis at this scale, it is also necessary to validate the robustness of the tools that are used. The simplest method for validating robustness is to measure how often a tool reports failure. A better approach is to use the common RegXML format to help validate the capabilities and correctness of forensic tools; in particular, RegXML facilitates the comparison of different approaches. This is especially important when data must be inferred from damaged evidence (e.g., evidence extracted from unallocated content). In the Casey Anthony case, the prosecution introduced as evidence the faulty, poorly-corroborated findings of a single tool [START_REF] Alvarez | Software designer reports error in Anthony trial[END_REF]. Well-structured, comparable data can help prevent such discrepancies.

This paper makes three contributions. The first is RegXML, an XML representation of hive files, and its implementation under hivex [START_REF] Jones | hivex -Windows Registry "hive" extraction library (libguestfs[END_REF].

The second is a Python framework for processing RegXML. The third is a time analysis of hives in two research corpora: a real data set collected from several hundred used computers that were purchased on the secondary market [START_REF] Garfinkel | Bringing science to digital forensics with standardized forensic corpora[END_REF], and a longitudinal, realistic data set [START_REF] Woods | Creating realistic corpora for forensic and security education[END_REF].

Related Work

RegXML is a component of the Digital Forensics XML (DFXML) syntax and toolset [START_REF] Garfinkel | Digital forensics XML and the DFXML toolset[END_REF]. As with the parent project, our goal is to facilitate the exchange of structured data and metadata. The principal focus is the design and validation of a Registry data representation.

The National Software Reference Library ran the WiReD Project to index software Registry artifacts as an additional component of the Reference Data Set [START_REF] White | Tracking computer use with the Windows Registry Datasets[END_REF]. However, WiReD does not offer a full-fledged XML schema to describe artifacts. RegXML, with some difference extensions, can serve as a Registry excerpt reporter for this effort.

The CybOX language [START_REF]CybOX -Cyber Observable Expression, Bedford[END_REF] describes observable artifacts that are relevant to digital forensics, logging and malware characterization, among other activities. A portion of the language describes Registry artifacts. However, the focus is on the live Windows Registry instead of hive file artifacts. For example, the enumeration of hives is for high-level Registry keys such as HKEY CURRENT USER, not hive file types.

The MAEC Project [START_REF]Malware Attribute Enumeration and Characterization[END_REF] provides an XML summary of malware behavior, including the file system footprint, Registry footprint and more. The XML Schema Document (Version 1.1) includes descriptors for Registry artifacts in malware under Registry Object Attributes. A string describes the affected hive, albeit without specifications on how to identify the hive; this can be complicated for hives that do not reside in files in the file system, such as the HARDWARE hive, which is only present in memory [START_REF] Russinovich | Inside the Registry[END_REF]. Also, if multiple components of a hive are to be described with MAEC, according to the XML Schema Document there would have to be one Registry Object Attributes element per affected value. The schema also lacks a descriptor for handling encoding types, which may be necessary to handle parser-unfriendly characters (e.g., r ⃝) or steganographic tools that may hide data in the Registry [START_REF] Wong | Forensic analysis of the Windows Registry[END_REF].

Much work has been accomplished in the area of Registry analysis since Russinovich's early description of the Registry structure [START_REF] Russinovich | Inside the Registry[END_REF]. Morgan [START_REF] Morgan | Recovering deleted data from the Windows Registry[END_REF] and Thomassen [START_REF] Thomassen | Forensic Analysis of Unallocated Space in Windows Registry Hive Files[END_REF] discovered the presence of freed-but-noterased content within the slackspace of a hive file. Thomassen [START_REF] Thomassen | Forensic Analysis of Unallocated Space in Windows Registry Hive Files[END_REF] also describes potential parsing errors and provides a useful reference description of the metadata and data structures. As described later in this paper, we were able to verify, by spotting in our real-world usage corpus, a particular structural pointer correction that Thomassen made to the collective knowledge about hive structure. Morgan also provides thorough documentation of data structures and deletion patterns [START_REF] Morgan | The Windows NT Registry File Format (version 0.4)[END_REF], while separately noting data recovery [START_REF] Morgan | Recovering deleted data from the Windows Registry[END_REF].

Carvey and Zhu [START_REF] Carvey | Windows Forensic Analysis[END_REF][START_REF] Zhu | A consistency study of the Windows Registry[END_REF] observed that system restore points contain timestamped copies of the Registry, so systems can provide some history without an investigator needing to take multiple images. Registry Decoder from Digital Forensics Solutions [START_REF]parsers.expat -Fast XML parsing using Expat[END_REF] includes these files, and Volume Shadow Copy files for Windows Vista and Windows 7.

Our work employs a research corpus where multiple computers were consistently imaged nightly for several weeks [START_REF] Woods | Creating realistic corpora for forensic and security education[END_REF]. In our experiments, we did not compare contents within system restore points; instead, we used the differences from the hives on different days.

To permit the verification of the results, our work uses data that is available to other researchers [START_REF] Garfinkel | Bringing science to digital forensics with standardized forensic corpora[END_REF]. Our analysis tool is also made available as a modification to the open source hivex library [START_REF] Jones | hivex -Windows Registry "hive" extraction library (libguestfs[END_REF]. We encourage other Registry-focused projects, such as the Registry Decoder and RegRipper [START_REF] Carvey | RegRipper[END_REF], to also implement RegXML in order to validate the completeness of their results. Currently, the outputs of these tools have to be parsed to permit comparisons. Furthermore, any pairwise comparison of Registry tools would require the validation of the comparator. Implementing a common output format such as RegXML would greatly simplify the task of comparing digital forensic tools.

Hive Structure

The Registry is a composition of hive files. Each hive is like a file system, essentially making the Registry a multi-volume file system namespace. Most of the hives are stored on disk as files with the following paths [START_REF] Carvey | Windows Registry Forensics: Advanced Digital Forensic Analysis of the Windows Registry[END_REF]: Under %WINDOWS%\system32\config:components, sam, security, software and system Under %USER%: localsettings\application data\microsoft\ windows\usrclass.dat and ntuser.dat Other hives are volatile and can only be retrieved through memory carving techniques. We focus on in-file-system hives in this work.

Each hive is logically a collection of keys (also called nodes) and values. Unless otherwise noted, the detailed description provided below comes from Thomassen [START_REF] Thomassen | Forensic Analysis of Unallocated Space in Windows Registry Hive Files[END_REF], which we found to be accurate through our work with the hivex library [START_REF] Jones | hivex -Windows Registry "hive" extraction library (libguestfs[END_REF].

Physically, a hive is divided into 4 KiB blocks. Bins reside in an integral number of contiguous blocks, using the first four bytes of the first block for the signature "hbin" and leaving the rest for any cells that will fit. The first block is called the base block, which has its own structure. The size of a cell is always a multiple of 8 bytes, and the last active cell in a bin owns the remainder of the bin. Table 1 lists all the cell types and their signatures.

Several of the cell types point to one another. Keys point to their parent keys, while values do not. Keys point to value lists (not to individual values) and value lists only point to values. Subkey lists point to other subkey lists or subkeys. Keys point to security descriptor cells (note that we do not investigate security descriptor cells in this work).

Among all the cell types, only two logically contiguous components can be stored in a physically fragmented manner. One is the list of all the Most hive data structures report their own size in embedded headers. The base block and all bins report their size after their first four signature bytes. Cells also report their size and allocation status; all the cell types report their size at the beginning. The size of an allocated cell always appears as the negative of the actual size; this becomes a positive number when the cell is freed. Thomassen [START_REF] Thomassen | Forensic Analysis of Unallocated Space in Windows Registry Hive Files[END_REF] discovered that if the unallocated space within a hive is parsed, then deleted data or moved data can be found by checking for the sign of the size. Thomassen also found that the space in bins is freed by moving all the allocated data towards the beginning of the bin; data at the end is overwritten only if a newly allocated cell needs the space. Therefore, while the space at the end of a bin may belong to the last used cell, it does not mean that the unused space is devoid of content. If this content is to be reported, its location should be included because there is no guarantee that old data has any consistency with the hive at the time of analysis.

Two hive data structures contain mtimes (modification times). The base block contains an mtime for the hive. The mtime of a key is not guaranteed to be the newest mtime for the entire subtree rooted at the key. The Registry shares this parent-child relative time behavior with file systems, where updating a file in a directory does not mean that the directory itself was updated. The only hives that we encountered with parents consistently newer than children were essentially unused (between one and six keys). We also observed that the mtime in the base block is not guaranteed to be the latest mtime related to the hive; this is discussed in Section 7.

<?xml version="1.0" encoding="UTF-8"?> <msregistry hive_version="1.3" name="and Settings\Charlie\ntuser.dat"> <mtime>2009-11-17T00:33:30.9375Z</mtime> <key name="$$$PROTO.HIV" root="1"> <mtime>2009-11-13T04:58:06.15625Z</mtime> <byte_runs> <byte_run file_offset="4128" len="92"/> ... </byte_runs> <key name="AppEvents"> ... <key name="EventLabels"> ... <key name=".Default"> ... <value type="REG_SZ" default="1" value= "Default Beep"> <byte_runs> <byte_run file_offset="5136" len="24"/> <byte_run file_offset="5160" len="30"/> </byte_runs> </value> ...

Representing Hives with RegXML

One of our goals was to represent the tree structure of hives in an XML syntax (i.e., using RegXML). RegXML primarily represents the logical structure of the hive, although there are ample annotations with the byte run elements that point to the physical storage points.

Figure 1 shows a RegXML sample. Most of the logical structure is represented in a straightforward manner -with key elements having key and value children. However, the following hive data were more difficult to represent: Data Location: The location of every element is defined to be the metadata and data cells necessary to reconstruct the logical cell and its child references. For example, a key cell with one cell devoted to listing four subkeys would have two byte runs: one for the key cell and one for the list cell. Each child then gets its own byte runs. This is consistent with file systems, where the listing and order are properties of the directory, not the listed file.

Time: All times are represented as ISO 8601 strings in optional mtime elements, as in DFXML [START_REF] Garfinkel | Digital forensics XML and the DFXML toolset[END_REF]. The only times that are part of the hive structure are mtimes, which are stored as Windows filetimes [START_REF]FILETIME structure[END_REF], where filetime 0 is the first 100-nanosecond interval of the year 1601. Therefore, in the context of hives, a value for the day 1601-01-01 can only represent null (or a system clock that is skewed beyond hopelessness). We use an element to maintain consistency with the time representation of file systems in DFXML.

Encodings: Aside from labeled raw binary data, we encountered some unexpected unprintable characters (including string types that were abused to hold raw binary). Some path names also include unexpected characters, such as the r ⃝ sign included in a product name. Where necessary, the unexpected data are base-64encoded with some type of encoding attribute.

Paths: For encoding reasons shared with value text, we chose to have each cell only note its name (not its full path) when generating the complete RegXML from a hive. This helped us catch a processing error: we had concatenated path names with forwardslash characters without realizing that the forward-slash is a legal name character (e.g., in MIME-type names such as "audio/mpeg") that is used in around 230,000 cells across all of our data. With the general extensibility of XML, a full path attribute could easily be added to any key and value, improving the searchability of excerpted RegXML.

To implement RegXML, we modified the hivexml program from the hivex Project [START_REF] Jones | hivex -Windows Registry "hive" extraction library (libguestfs[END_REF]. hivex is a library that reads and writes hive files, providing a shell (hivexsh), XML converter (hivexml) and bindings for several languages. hivex functions primarily by walking the allocated hive from a starting offset (which does not need to be the root) and invoking callback functions on each visited key and value. Unfortunately, due to some difficulties with the walking architecture design of hivex, hivexml does not currently produce byte runs for key child lists.

RegXML Processing with dfxml.py

The Digital Forensics XML Python processing library is distributed with the Bulk Extractor and Fiwalk Projects [START_REF] Garfinkel | Automating disk forensic processing with SleuthKit, XML and Python[END_REF][START_REF] Garfinkel | Bulk Extractor[END_REF]. We have updated this library to parse RegXML as of Bulk Extractor version 1.0.3 and Fiwalk version 0.6.16.

dfxml.py processes Digital Forensics XML [START_REF] Garfinkel | Digital forensics XML and the DFXML toolset[END_REF], which presents a file system to the user as file objects. We implemented RegXML processing with key and value objects, which we refer to as cell objects. The Python Expat library [19] is the basic processing engine; it is a stream-based parser with events for starting and ending elements, and an event for encountering character data.

#!/usr/bin/env python """Usage: python demo_registry_timeline.py <input.regxml>""" import dfxml, sys timeline = [] def process(co): mtime = co.mtime() if mtime != None: timeline.append([mtime, co.full_path(), "modified"]) dfxml.read_regxml(xmlfile=open(sys.argv [START_REF] Alvarez | Software designer reports error in Anthony trial[END_REF], "r"), callback=process) for record in sorted(timeline):

print("\t".join( map(str, record)) )

Figure 2. Demonstration program that prints a timeline of hive modification times.

Although RegXML and DFXML differ in their structure (where a DFXML file is mostly a stream of fileobject elements), the API for interacting with either is equivalent. The only difference is the logical order in which the namespace is parsed. There is also sufficient information in RegXML to represent a file like DFXML fileobject elements.

dfxml.py invokes a user-supplied callback function when it has completed parsing a key or value, so a user visits the RegXML hierarchy in postorder. Fortunately, if a user's script cannot function in a postorder traversal, then the cell objects and hive namepsace are retained as a property of the object returned by dfxml.read regxml(). Note that metadata elements in Figure 1, including mtime and byte runs, are recorded before child keys and values in RegXML. This allows a parent object to be partially populated before all its children are visited, allowing each child to compare its properties against its parent if desired. This ordering improves performance, but is not necessary because it is possible to iterate over cells after completing the XML input.

To demonstrate the API, we consider a scenario where the times in a Registry need to be investigated for consistency with the rest of the system [START_REF] Zhu | A consistency study of the Windows Registry[END_REF]. One necessary step is extracting the times of the keys. Figure 2 shows a program that prints the timeline of all activity within a hive. The figure is adapted from a similarly succinct timeline program for DFXML [START_REF] Garfinkel | Digital forensics XML and the DFXML toolset[END_REF]. The mtimes are retrieved by a function (co.mtime()) to ease the processing of cell objects that can be keys or values and, thus, may not have a modified time. Byte runs are also retrieved by a function (co.byte runs()). Other desired data, such as the cell name and full path, are also retrieved using functions, with any base-64 decoding handled transparently. The registry object, to which every cell object maintains a handle, stores a dictionary index of all the cell objects by path (object index). To access the registry object, the regxml reader is returned by dfxml.read regxml(), and the reader maintains a handle to the registry object. All these pointers to the registry object ease tasks such as determining hive-scoped extrema (e.g., recording the earliest times in an analysis).

Analysis

We compiled hive data from two corpora:

M57-Patents Scenario (M57): The M57-Patents Scenario [START_REF] Woods | Creating realistic corpora for forensic and security education[END_REF] is a four-week series of desktop computer images produced for forensic education and research. Four personas working in a fictitious company have their computers imaged at the end of every workday for a month. The resulting data set contains the day-today known ground truth of computer activities.

Each computer was imaged by shutting it down using the Windows GUI and rebooting into a Linux LiveCD in order to take a forensic image of the hard drive. Therefore, the computers are expected to be in a consistent state at the time of imaging. Three of the personas used Windows XP computers, up-to-date through November 2009; the remaining persona used a Windows Vista computer. In all, the corpus contains 83 storage device images, 79 of them desktop images.

Real Data Corpus (RDC):

The Real Data Corpus [START_REF] Garfinkel | Bringing science to digital forensics with standardized forensic corpora[END_REF] is drawn from a collection of storage media purchased on the second-hand market from around the world. The media are primarily hard drives and flash drives. Note that the hard drives are not guaranteed to be the drives that house the operating system partition or user profiles. Our analysis was performed on a total of 2,027 storage device images.

Table 2 provides the statistics for the from-image-to-analysis data processing. We modified a Python file extraction script from the Fiwalk utility [START_REF] Garfinkel | Automating disk forensic processing with SleuthKit, XML and Python[END_REF] to extract files that ended with the patterns noted in Section 3. If any extraction failed, we excluded all the hives in the associated image from further analysis. We then ran hivexml on each extracted hive. If hivexml failed, then the XML would be unusable.

To facilitate the analysis, we wrote a script based on the dfxml.py interface to convert from XML to SQLite. This was done for multiple reasons. First, running all the hivexml output through the dfxml.py module serves as a robustness test and an additional data-processing checkpoint. Second, most of the planned queries could have been performed with XML tools like XPath, DOM, in-memory lists, counters and hash tables, but it essentially would have been equivalent to writing a SQL engine. Indeed, we did not go straight to SQL from the raw hive files because the advantage of RegXML as a transport and summary syntax could not be ignored.

The reasons for hivexml failures primarily involved subkey pointer constraints, which we had not yet relaxed (the hivex library does not recognize "li" subkey blocks and assumes "ri" blocks will not point to "ri" blocks). dfxml.py processing failures were entirely based on encountering the same path (byte-for-byte) multiple times, violating our assumption of unique paths. We discarded all the cells from hives containing these path errors from further analysis. While this limited the data that were analyzed, we were still able to find interesting inconsistencies in the hives that were not discarded.

We did not include hives extracted from system restore points in our analysis. We decided to limit the hive extraction to only the hives present and active in the file systems at the time of imaging. This was done because we had no guarantees that the restore points would be logically intact, particularly in the RDC drives.

Still, we believe that the RDC hives serve as a fine robustness testbed. Additionally, in the case of the M57 corpus, we have the opportunity to measure changes from the previous day of computer use. As a demonstration analysis, we use this available sequence to measure cell mtime properties.

Time Inconsistencies

We noted earlier that the mtime consistency for hives was not exactly what one would expect. An update to an internal key should cause an update to the hive that, when recorded to the disk, should update the mtime of the hive in the file system. Table 3 shows how well the assumption plays out. We split the RDC hives into basename types (i.e., usrclass.dat and ntuser.dat not broken out by profile) and observed roughly the same proportions. Hence, to see the last update time of a hive, at least these three times should be checked. Unfortunately, we also discovered that the assumption that mtimes always increase does not always hold. Within the M57 data, we observed that the Windows Vista computer (Terry's computer) had one day when more than a thousand keys had their mtimes revert to 2006 and 2008, seemingly a reset. The reverted tallies are shown in Table 4. Unfortunately, the only scenario note for Terry that day was "Continuing rebuilding Terry's hard drive." Further, there were no common hive path prefixes. We are still unsure about how these changes occurred. Meanwhile, the system clocks that had supported disk images in the RDC were not guaranteed to provide accurate time data. Some clocks were skewed to almost a comical degree: one hive reported an earliest modified key in 1980 and a last shutdown time in 2081. In one case, where a system hive file mtime went back to 1981, its earliest key also went back to 1981. We conjecture -but cannot verify without file carving -that the mtime was allowed to be updated to a smaller value.

Lastly, we observed that the transition from null to non-null mtime does occur -on 418,824 (2.6%) cells in M57. Moreover, no mtime was set to null in the scenario.

Code Availability

We continue to integrate our hivexml modifications into the Red Hat maintained code base. The development revisions that support this work and the RegXML-SQL conversion tool are available at users.soe.ucsc. edu/~ajnelson/research/nelson_ifip12/index.html. The revisions to dfxml.py are readily available in Bulk Extractor [START_REF] Garfinkel | Bulk Extractor[END_REF] and Fiwalk [START_REF] Garfinkel | Automating disk forensic processing with SleuthKit, XML and Python[END_REF].

9.

Future Work

XML differencing, and more generally tree differencing, is a non-trivial problem. RegXML works well to represent a set of keys and values to be searched, but it is geared towards representing Registry data rather than representing search patterns. CybOX [START_REF]CybOX -Cyber Observable Expression, Bedford[END_REF], MAEC [START_REF]Malware Attribute Enumeration and Characterization[END_REF] and WiReD [START_REF] White | Tracking computer use with the Windows Registry Datasets[END_REF] also present a particular key or value to find, or find absent or find persistent after deletion. Unfortunately, none of them formally specify what is interesting about the search data, like a backwards time change or use of low-order bits in the timestamps for steganography. Registry Decoder offers basic functionality in hive differencing, but does not yet provide any reporting on differences [START_REF]Registry Decoder: Instructions for Offline Analysis Component[END_REF]. Further research is needed on representing file system differences and patterns. This could enable, say, an antivirus approach where changes against prior hives (such as in system restore points) are analyzed in an automated manner.

Our analysis assumed that paths are unique. Upon discovering that the assumption is invalid, we instead required the uniqueness of paths in the analyzed data. It may be important to analyze a hive that contains ambiguous paths. However, we have not yet decided how to disambiguate cells. Reporting parent addresses may be sufficient, but this would best be tested on ambiguous-path hives and on bin carving experiments, which we did not perform. Some Registry structures are not presently captured in the hivexml implementation of RegXML. In particular, security descriptor ("sk") cells and big data cells ("db") documented by Morgan [START_REF] Morgan | The Windows NT Registry File Format (version 0.4)[END_REF] are not yet represented. The focus of this work was on representing keys, contiguous values, times and differences. We note that, while documentation is available, security descriptors were not a focus of our work and the majority of the M57 and RDC hives did not support big value data. Morgan notes that only hives of version 1.4 or higher may use fragmented data [START_REF] Morgan | The Windows NT Registry File Format (version 0.4)[END_REF]. For all the hives that hivexml processed at least partially, the hive version was reported as either 1.3 or 1.5. The M57 corpus had 878 hives of version 1.3 and 158 of version 1.5; RDC had 2,901 and 281 hives of versions 1.3 and 1.5, respectively. We suspect that security descriptors will necessitate at least an in-RegXML index. Given that there are still undocumented structures within the Registry, RegXML version 0.1 is the most appropriate version at this time, and it represents the first step to full specification. Future versions of RegXML will incorporate extensions that account for the undocumented structures.

Conclusions

The Windows Registry provides ample evidence of computer activities. RegXML, the XML schema described in this paper, greatly improves the visibility of hive content. XML fits the tree structure of hives well, and RegXML is especially useful for analyzing a hive and indexing activity footprints. The analysis of the timestamps in two research corpora demonstrates the robustness of the implementation in hivexml and the DFXML Python library. We hope that this work will stimulate further research related to Registry exploration and open, searchable reporting.

Note that the views and opinions expressed in this paper are those of the author and do not necessarily reflect the views and opinions of the Department of Defense or the U.S. Government.

Figure 1 .

 1 Figure 1. RegXML excerpt for a user's ntuser.dat hive generated by hivexml.

Table 1 .

 1 Registry cell types and their signatures[START_REF] Thomassen | Forensic Analysis of Unallocated Space in Windows Registry Hive Files[END_REF].

	Cell Type	Signature
	Key cell	nk
	Class name cell
	Security descriptor cell sk
	Subkey list cell	lf, lh, ri, li
	Value list cell
	Value cell	vk
	Value data cell
	Big value data cell	db

subkeys of a key, and the other is value data longer than 16,388 bytes, which are supported in hives version 1.4 or greater

[START_REF] Morgan | The Windows NT Registry File Format (version 0.4)[END_REF]

. Value lists, value data shorter than 16,344 bytes and keys are stored in a contiguous manner.

Table 2 .

 2 Processing statistics for the hive analysis process.

	M57	RDC Description
	83	2,027 Number of media images
	0	145 Images whose hive extraction process
		exited in an error state
	25	231 Hives that hivexml could not process
	1,016	3,053 Hives that hivexml could process
	0	148 Hives that dfxml.py could not process
	0	941,701 Cells processed before dfxml.py failed
	79	198 Total images in SQLite
	1,016	2,986 Total hives in SQLite
	16,238,068 34,127,394 Total cells in SQLite

Table 3 .

 3 Sources of latest mtimes associated with hives.

		File	Hive Latest
		System Root	Key
	M57	620	499	24
	RDC	1,384	1,989	306

Table 4 .

 4 Back-in-time mtime changes in the M57 image terry-2009-11-19.aff.

	Hive	Backwards Non-Backwards % Backwards
		Changes	Changes	Changes
	SOFTWARE	1,069	188,677	0.57
	SYSTEM	316	62,474	0.51
	SECURITY	1	149	0.67
	LocalService/NTUSER.DAT	2	1,351	0.15

Acknowledgements

The author wishes to thank Richard Jones for his advice and review of the hivex revisions, Simson Garfinkel for providing guidance on this research effort, and Kris Kearton and Kam Woods for providing information related to the M57 corpus.


Martin Mulazzani

Markus Huber

Edgar Weippl

Data Visualization for Social Network Forensics

Keywords: Social networks, online forensics, visualization

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

Introduction

The number of users of social networks has been increasing phenomenally -Facebook alone claims to have 800 million users [START_REF]Facebook, Facebook Statistics[END_REF]. Meanwhile, social networks have introduced novel research challenges with regard to digital forensics. While traditional digital forensics relies on the physical acquisition of hardware [START_REF] Brezinski | RFC 3227: Guidelines for Evidence Collection and Archiving[END_REF][START_REF] Carrier | File System Forensic Analysis[END_REF] and the use of hash values to ensure evidence integrity, this approach does not scale to social networking and cloud services and their use of distributed data centers. Due to the lack of standardized APIs for digital forensics and unified processes for service operators, ad hoc isolated solutions are still in widespread use. Another major challenge is the visualization of massive volumes of data [START_REF] Conti | Security Data Visualization: Graphical Techniques for Network Analysis[END_REF][START_REF] Teelink | Improving the computer forensic analysis process through visualization[END_REF].

It is difficult to visualize social networking data in a manner that facilitates the answering of common questions, especially by individuals with limited technical expertise. This occurred recently in the iPhone consolidated.db file controversy. The file in question contained geolocation information that was publicized back in 2010 [START_REF] Morrissey | iOS Forensic Analysis[END_REF]. However, the consolidated.db problem received widespread attention after the April 2011 release of iPhoneTracker software [START_REF] Warden | iPhone Tracker[END_REF], which helped visualize the collected data. The resulting controversy forced Apple to review and change its data collection process [START_REF] Chen | Apple promises fix for location-gathering "bug" on iPhone, Wired[END_REF].

This paper identifies the data sources of interest in forensic investigations of social networks and shows how they can be leveraged in an automated fashion. The paper also describes several visualizations that can be generated from the data sources for use in forensic investigations. Specifically, example graphs and possible visualizations are presented, some of which could be used very effectively in social network analysis. To the best of our knowledge, this work is the first to support the forensic analysis of data from social networks without the collaboration of social network operators.

Background

Social network forensics has to rely on a limited set of data sources in many cases. Acquiring the hard drives of the servers is not feasible, and accessing the data directly requires the cooperation of the social network operator. Moreover, as described in the Facebook Law Enforcement Guidelines published by the Electronic Frontier Foundation [START_REF]Facebook, Facebook Law Enforcement Guidelines[END_REF], an investigator who files a data request with an operator may or may not receive all the relevant data. Network forensic systems such as PyFlag [START_REF] Cohen | PyFlag -An advanced network forensic framework[END_REF] and Xplico [START_REF]Xplico, Network Forensic Analysis Tool[END_REF] also cannot access all the data, because they are passive in nature.

This situation not only hinders evidence collection [START_REF] Brezinski | RFC 3227: Guidelines for Evidence Collection and Archiving[END_REF], but also makes it difficult for an investigator to demonstrate that the evidence that is collected is authentic and reliable. The approach described in this paper stands out because it does not require the cooperation of the social network operator. Additionally, properties such as evidence authenticity and reliability are enhanced due to the open nature of the collection methodology and tools.

Data Acquisition

Before a social network can be analyzed, the relevant data has to be identified and acquired. While traditional digital forensic methods can be used to extract artifacts from the local web browser cache [START_REF]Facebook Artifact Parser version .02[END_REF], many other approaches are possible at the communications layer. These range from passive network sniffing to active methods such as sniffing of unencrypted Wi-Fi traffic [START_REF] Butler | Firesheep[END_REF], possibly in combination with ARP spoofing on a LAN. The recently proposed "friend in the middle attack" [START_REF] Huber | Friend-in-the-middle attacks: Exploiting social networking sites for spam[END_REF], which uses a third party extension for a social network in combination with a traditional crawler component, may also be used.

However, crawling is limited at best, primarily because metadata and accurate timestamps are not shown on web pages; these are only available using social network APIs. Although it is possible to use passive logging at the communications layer, e.g., when a judge has authorized lawful intercepts on the Internet communications of a suspect, this approach is limited because it would take considerable time to collect data, and completeness is hardly possible. Furthermore, many social networks permit data encryption at the communications layer using the HTTPS protocol, which renders passive attacks useless.

Facebook recently announced that its users can download all their profile data. However, the data provided by our method is far superior compared with the Facebook profile download option, which lacks important metadata (among other data) and is, therefore, not useful for social network forensics. In general, it is not possible for a user to download everything that is connected to his or her profile on the social network.

Another interesting feature is Facebook Timeline, which encourages users not to delete anything from Facebook and to use it as a historical archive. This feature will greatly benefit digital forensic investigations of Facebook accounts.

Social Network Data Pool

While social networks vary considerably in their architecture and features, the following generic data sources are particularly useful from the point of view of forensic investigations of social networks:

Social Footprint: What is the social graph of the user? Who are the user's friends?

Communications Pattern: How is the network used for communicating? What methods are used? With whom is the user communicating?

Pictures and Videos: What pictures and videos were uploaded by the user? Who are the other users on whose pictures the user is tagged? Activity Times: When was the user connected to the social network? When did a specific activity take place?

Apps: What apps is the user using? What is their purpose? What information can be inferred in the social context? A plethora of information about prolific users is stored by the operator. Facebook claims that more than 50% of its users use the social network on any given day, which corresponds to around 400 million users [START_REF]Facebook, Facebook Statistics[END_REF]. Sometimes, information is cached locally, but this is not a reliable source because it is neither complete nor stored persistently. Depending on the social network implementation, the availability of the data itself and the possibility of retrieving the data via API calls varies considerably. Nevertheless, most of this data can be extracted directly or inferred with low overhead without the collaboration of the social network operator. Once the data is available to the investigator, the full spectrum of social network analysis can be conducted [START_REF] Wasserman | Social Network Analysis: Methods and Applications[END_REF].

Of course, the easiest way to obtain data pertaining to a social network account is with the consent of the user, who would have to provide the username and password. However, since this data can be quite voluminous, a forensic investigator may require specialized tools to view and analyze the data.

Social Network Visualizations

This section describes certain basic and advanced visualizations that can be constructed from the data sources identified in the previous section. These visualizations can be used very effectively in forensic investigations of social networks.

Basic Visualizations

Four basic visualizations can be constructed from social network data sources: Social Interconnection Graph: It is trivial to retrieve the list of friends of a user. In most social networks, this is public information or information that can be collected quite easily even without entering the social circle of the user of interest [START_REF] Bonneau | Eight friends are enough: Social graph approximation via public listings[END_REF]. However, it is not trivial to cluster the friends themselves. For example, to find out who is connected with whom; or, if a specific contact is in the cluster of workplace friends; or, if there is a direct friend relationship.

Our approach uses a feature of the Facebook API, which allows an application to query if two users are connected. The friends of a user may be clustered into different groups, e.g., people from work, school, family and more, because the members of the groups are more likely to know each other. This yields a undirected graph G =< V, E > where V = {v 1 , v 2 , . . . , v n } is the set of friends of a user and E = {(v x , v y ), . . . } is the set of edges that connects two nodes that are friends in the social network. An example graph is shown in Section 5. Clusters of highly connected nodes represent friends who know many of each other's friends.

Social Interaction Graph: In many investigations, it is important to gather information about users who communicate with each other. The communications include wall posts, direct messages, group communications and reactions to public announcements. User communications can be represented as a directed graph G =< V, E > where the nodes V = {v 1 , v 2 , . . . , v n } correspond to friends and each directed edge (v x , v y ) in E has a weight that is incremented for every message sent from v x to v y . Note that different forms of communication are not distinguished when assigning the weight. Allowing investigators to add custom weights to specific forms of communication is a topic of future work.

An example social interaction graph generated by our software is shown in Section 5. The graph enables an investigator to easily identify the top communication partners at first sight, and correlate them with other information such as phone records.

Complete Timeline: The timeline of activities is of increasing importance as mobile clients on smartphones enable social network users to be online all the time. In many cases, the activities of a user as well as the activities of his/her friends can be extracted. Proper visualization of the activity times of users can be very helpful to an investigator. This includes multiple data layers, such as the activities of the user, activities of friends, group activities and reactions to events by friends, which can simplify analysis. Also, a zoomable timeline for visualizing time ranges of importance can be very useful to an investigator. This is especially effective because a social network user and his/her friends could be involved in more than 500 events on a given day.

Location Visualization: The increasing use of geotagging and location applications needs to be reflected in forensic investigations. Applications such as foursquare [START_REF]Foursquare Labs, foursquare[END_REF] and Facebook Places are employed in social networks to capture and share geolocation information. Digital cameras and smartphones automatically geotag pictures with the exact locations where the pictures were taken.

Most social networks remove metadata from pictures prior to storage [START_REF] Beaver | Finding a needle in Haystack: Facebook's photo storage[END_REF], but this may change in the future.

Advanced Visualizations

This section describes advanced visualizations that can be constructed from social network data sources. The following three advanced visualizations are useful to investigators and should become standard tools in social network forensics:

Event Tracking: Investigations of viruses and other malicious applications that propagate via social networks require the identification of who or what started the series of events. Tracking such events is not straightforward, but having a collection of social network footprints of various users can provide insight into dissemination characteristics, propagation tactics and other analytic information.

Timeline Matching: In a highly centralized system such as a social network, an investigator has the benefit of consistent timestamps provided by the social network implementation. Social network operators often run their own NTP infrastructure and keep their clocks consistent across thousands of servers. The timestamps can be used to match the timelines of different users, and to create an exact timeline for an entire cluster of friends or even a larger group. This feature, which was recently proposed for NTFS [START_REF] Ding | Time based data forensic and cross-reference analysis[END_REF], is of importance to social networks as well as cloud computing systems.

Differential Snapshots: The forensic image of a user profile can vary considerably depending on when it was taken. Therefore, an investigator would welcome the ability to visualize the social network data of a given user as well as the differences between previous images of the same user.

Experimental Results

We implemented the methodology outlined in [START_REF] Huber | Social snapshots: Digital forensics for online social networks[END_REF] to collect data from Facebook, currently the world's largest social network. The data included all the social connections, direct communications, pictures and more. The data acquisition took approximately 20 minutes per account, which, in our opinion, is a reasonable amount of time for data collection. We parsed the output and generated the graphs presented in this section.

Visualization

The creation of the social interconnection graph employed a feature from the Facebook API that allows an application to query if two users are connected. To create the social interconnection graph, we tested if the first friend in a user profile is in a connection with the n -1 friends of the profile, then tested for the second friend with the remaining n -2 friends, and so on. Figure 1 shows an example social interconnection graph, which was constructed using the profile of one of the authors of this paper. The graph was plotted with Gephi [START_REF] Bastian | Gephi: An open source software for exploring and manipulating networks[END_REF], an open source graph visualization tool, using the Fruchterman-Reingold algorithm [START_REF] Blondel | Fast unfolding of communities in large networks[END_REF]. The nodes that appear to be from the same cluster are colored automatically, which simplifies cluster analysis. Note that the connections are hypothetical because the real user names are replaced by random names of computer scientists listed in Wikipedia.

Several different social interaction graphs may be created from Facebook data. Our software makes it possible to create separate graphs for different types of interaction, which could be subsequently integrated to produce a complete social interaction graph. Figure 2 shows an example social interaction graph derived from picture tags in Facebook. The graph is created using the following three steps: (i) for a user account of interest, all the pictures of all the friends are collected and searched for tagged users; (ii) a user who is tagged in a picture but is not in the list of friends is ignored; (iii) if a tagged user is in the list of friends, then an edge is created between the two nodes (users) pointing from the user who uploaded the picture to the tagged user, or the weight of the edge is increased if the edge already exists. Since the edges are directed and weighted, the graph can be used to identify users with "tight" social connections.

Another type of social interaction graph can be created based on direct messages (Figure 3). In this case, an edge is added between two nodes (users) if the user of interest has exchanged messages with another user. The edges are weighted according to the number of messages sent by the users.

Social network data can also be used in the automated creation of timelines. While this feature is currently under development, an example timeline of events in Facebook over a 24-hour period is shown in Figure 4.

Evaluation

The proposed data collection and visualization methods are novel, and are easily integrated with existing social network analysis methods. However, a key drawback is that data collection is hardly reproduciblethe graphs and timelines are expected to change considerably over time because of the highly dynamic aspects of social networks. In a single day, John Doe ID 11111111 UTC-2 a user could change his/her social interconnection graph considerably, and could even attempt to hide communications traffic.

Other data, such as user IP addresses as provided by the Facebook NeoPrint [START_REF]Facebook, Facebook Law Enforcement Guidelines[END_REF], are only available to social network operators, and are not accessible with our methods (using an automated web browser or an API). Furthermore, it is difficult, if not impossible, to guarantee data completeness -once data is deleted by the user, it can only be recovered by the social network operator, so this data is not available for analysis without operator cooperation. Nevertheless, much social network data is static in nature and our methods are applicable and, indeed, very useful in forensic investigations.

Conclusions

Social network forensics is rapidly becoming an important component of digital forensic investigations. This paper has identified several valuable data sources and has shown how they can be leveraged in forensic investigations, even without the cooperation of social network operators. The proposed methods are fully automatable and support cluster analysis as well as timeline visualization. The proof-of-concept software system for creating social interconnection and social interaction graphs from Facebook data demonstrates the feasibility and utility of the methods in social network forensic investigations.

Our future work will implement additional visualizations and an automated report generation feature. Also, it will increase the number of social networks supported by the software system, which will be released as open source in the near future.

Figure 1 .

 1 Figure 1. Anonymized social interconnection graph.

Figure 2 .

 2 Figure 2. Anonymized social interaction graph derived from picture tags.

Figure 3 .

 3 Figure 3. Social interaction graph derived from direct messages.

Figure 4 .

 4 Figure 4. Anonymized timeline for a 24-hour period.


Hayson Tse

Kam-Pui Chow

Michael Kwan

REASONING ABOUT EVIDENCE USING BAYESIAN NETWORKS

Keywords: Digital evidence, Bayesian networks, evidentiary reasoning

This paper presents methods for analyzing the topology of a Bayesian belief network created to qualify and quantify the strengths of investigative hypotheses and their supporting digital evidence. The methods, which enable investigators to systematically establish, demonstrate and challenge a Bayesian belief network, help provide a powerful framework for reasoning about digital evidence. The methods are applied to review a Bayesian belief network constructed for a criminal case involving Bit-Torrent file sharing, and explain the causal effects underlying the legal arguments.

Introduction

The investigation of a crime and the prosecution of the suspect can be an expensive and time-consuming process. The cost of a mistake can be high -a guilty party may be acquitted; even worse, an innocent individual may be convicted. Accordingly, criminal investigators and prosecutors are required to prove the elements of a case beyond a reasonable doubt. This means that the events involving the suspect and constituting the alleged offense must be reconstructed in a faithful manner from the available clues.

Event reconstruction involves the identification of plausible acts based on the evidence observed by an investigator. During reconstruction, it is often necessary to formulate hypotheses based on the evidence and evaluate the likelihood of the hypotheses; eventually, the evidence and the legal reasoning must be presented in court [START_REF] Keppens | Probabilistic abductive computation of evidence collection strategies in crime investigation[END_REF].

In the physical world, the evidence observed by an investigator may be fabricated, removed, forged or altered. The same applies to digital forensic evidence. Cohen [START_REF] Cohen | Two models of digital forensic examination[END_REF] has advocated the development of methods that allow the reliability of evidence to be established, demonstrated and challenged. Such methods should identify the digital processes that created the evidence, assess the weights or degrees of the beliefs of the investigator, and provide reasons in support of the beliefs.

Bayesian belief networks have been applied to digital forensic investigations. de Vel, et al. [START_REF] Vel | An embedded Bayesian network hidden Markov model for digital forensics[END_REF] have proposed a combination Bayesian belief network model and hidden Markov model to encode digital forensic evidence during a given time interval and estimate the degree of criminal activity over time. Lee, et al. [START_REF] Lee | From digital forensic report to Bayesian network representation[END_REF] have developed a methodology for transforming the findings in digital forensic reports to graphical representations using a Bayesian belief network. Kwan, et al. [START_REF] Kwan | Reasoning about evidence using Bayesian networks[END_REF] have used Bayesian belief networks to quantify the strengths of hypotheses formulated during an investigation and their supporting evidence. They demonstrated the utility of a Bayesian belief network model using evidence in a Hong Kong criminal case involving illegal file sharing via BitTorrent.

Any method that is used to support a legal hypothesis would be subject to close scrutiny. In Hong Kong, as in other common law jurisdictions, if a court is to accept the evidence of a specific scientific theory (whether novel or not), then the theory must have a sound scientific basis and must be comprehensible to the court. Also, the methods used to carry out the scientific tests should be safe and reliable, and should follow established protocols (i.e., protocols that have been published, disseminated and acknowledged to be reproducible) [START_REF] Kong | Special Administrative Region High Court, Probation Action Judgment[END_REF].

When constructing a Bayesian belief network, the causal structure and conditional probability values come from domain knowledge or empirical data. Therefore, it is necessary to assess the accuracy of the derived model with regard to the structure and the probability values. This begs the question: what makes a model accurate? Issues related to the interactions between the events corresponding to variables are important. The interactions are reflected by the causal structure or topology of a Bayesian belief network.

This paper describes two methods for analyzing the topology of a Bayesian belief network created to qualify and quantify the strengths of investigative hypotheses and their supporting digital evidence. The methods are applied to review a Bayesian belief network constructed for a criminal case involving BitTorrent file sharing, and to clarify the causal effects underlying the legal arguments.

BitTorrent Overview

Kwan, et al. [START_REF] Kwan | Reasoning about evidence using Bayesian networks[END_REF] created a Bayesian belief network for the evidence in a Hong Kong criminal case involving illegal file sharing via BitTorrent. Kwan and colleagues specified the probability distributions of the hypotheses and evidence in the Bayesian belief network, and used the network to quantify the strengths of the investigative hypotheses. Before we describe the method for analyzing the topology of a Bayesian belief network and its application to the BitTorrent case, we briefly review the operation of BitTorrent.

BitTorrent is a peer-to-peer application that uses metadata files known as "torrents." The metadata is used by a BitTorrent client to connect to remote computers and download files.

In a typical BitTorrent scenario, an "initial seeder" first creates a torrent using a BitTorrent client or a torrent-making application. The torrent is then posted on a website or forum. Next, the initial seeder distributes small chunks of the file that is to be shared to different machines that are connected via a BitTorrent client.

The connected machines are collectively referred to as a "swarm." After the initial seeder has shared all the data chunks with the swarm, the machines in the swarm can proceed to share the chunks with each other and with other newly connected machines.

A torrent primarily contains three pieces of information: (i) name of the file to be shared; (ii) size of each chunk composing the file and the number of chunks; and (iii) uniform resource locator (URL) of a "tracker." A tracker is a dedicated server that links all the peers in relation to a torrent. Remote individuals download the torrent from a website. When the torrent is opened within a BitTorrent client, the client is referred to the initial seeder using the tracker URL.

Locating a torrent alone on a computer is not evidence of file uploading, downloading or sharing by the computer. This is because there are different ways in which a torrent may be stored on a computer. A user may create a torrent and save it anywhere on a network. Alternatively, a user may open a torrent from a website, which causes the torrent file to be saved in the Temporary Internet Files folder (if Internet Explorer is used as the web browser). A user may also copy a torrent from a website, email, Internet Relay Chat or external storage device to any location on the network.

Since the presence of a torrent alone is not evidence of file uploading, downloading or sharing, investigators need to gather additional evidence to show that the torrent was opened within a client. One piece of ev- idence is a backup torrent, which is often created when a BitTorrent client opens a torrent. A BitTorrent client also generates a cache file that contains data about the status of a download. These cache files are used as a recovery system so that a torrent can resume from the same point if the downloading process is interrupted. Therefore, cache files provide evidence of the downloading or seeding of specific files.

BitTorrent Case

In the BitTorrent case study conducted by Kwan, et al. [START_REF] Kwan | Reasoning about evidence using Bayesian networks[END_REF], no torrent file, whether the original or the backup, was ever found on the suspect's computer. Also, a cookie pertaining to the newsgroup forum was not found on the suspect's computer. According to the Bayesian belief network model created in the study and on the basis of other observed evidence, there is still a 92.27% chance that the suspect's computer was used as the initial seeder to distribute an infringing movie on a BitTorrent network.

The Bayesian belief network for the BitTorrent case is shown in Figure 1. Tables 1 and2 list the hypotheses and the evidence involved in the case, respectively.

Bayesian Belief Networks

This section examines the semantics of a Bayesian belief network and reviews the topology of the model constructed for the BitTorrent case.

Table 1. Hypotheses in the BitTorrent case.

Hypothesis Description

H

The seized computer was used by the seeder to share the pirated file on a BitTorrent network H1

The pirated file (destination file) was copied from the seized optical disk (source file) to the seized computer H2

A torrent was created from the pirated file H3

The torrent was sent to a newsgroup for publishing H4

The torrent was activated, which caused the seized computer to connect to the tracker server H5

The connection between the seized computer and the tracker was maintained Table 2. Evidence in the BitTorrent case.

Evidence Description

E1

Modification time of the destination file was identical to that of the source file E2

Creation time of the destination file was after its own modification time E3

Hash value of the destination file matched that of the source file E4

BitTorrent client software was installed on the seized computer E5

File link for the pirated file (shared file) was created E6

Pirated file existed on the hard disk of the seized computer E7

Torrent creation record was found E8

Torrent existed on the hard disk of the seized computer E9

Peer connection information was found on the seized computer E10

Tracker server login record was found E11

Torrent activation time was corroborated by its MAC time and link file E12

Internet history record of the torrent publishing website was found E13

Internet connection was available E14

Cookie of the website of the newsgroup was found E15 URL of the website was stored in the web browser E16

Web browser software was available E17

Internet cache record regarding the publishing of the torrent was found E18

Internet history record regarding the tracker server connection was found

A Bayesian belief network is a graphical structure for representing and reasoning about an uncertain domain. The key feature is that a Bayesian belief network provides a method for decomposing a probability distribution into a set of local distributions. In order to construct a Bayesian belief network, it is necessary to first specify the structure of the domain and then quantify the influences. This is why attention must be paid to the topology of a Bayesian belief network. This section describes two methods for examining the topology of a Bayesian belief network.

The nodes of a Bayesian belief network represent a set of random variables X = {X 1 , . . . , X n } from the domain. A set of directed arcs connect pairs of nodes X i → X j . The structure or topology of the network captures qualitative relationships between variables. Two nodes are connected by a directed arc, which expresses the "direct causal influences" between the two nodes. For example, in Figure 1, H 1 denotes "The pirated file (destination file) was copied from the seized optical disk (source file) to the seized computer" while E 1 denotes "Modification time of the destination file was identical to that of the source file."

Since H 1 is a direct cause of E 1 , there is a directed arc from H 1 to E 1 .
A node is a parent of a child node, if there is an arc from the former to the latter. If there is a directed chain of nodes, one node is an ancestor of another if it appears earlier in the chain. A node is a descendant of another node if it appears later in the chain. For example, in Figure 1, H 2 is the parent of E 5 ; H is an ancestor of E 5 ; and E 18 is a descendant of H.

Since a directed arc connecting two nodes represents a direct causal influence between the two nodes, a parent denotes the direct cause of a child, and the descendants of a node represent the effects of the node.

A Bayesian belief network is a directed acyclic graph (DAG) that expresses conditional independent statements regarding its nodes. Each node is associated with a conditional distribution P (X i | P arents(X i )). Let P arents(V ) be the set of the parents of a variable V in a DAG. Let Descendants(V ) be the set of the descendants of a variable V in a DAG. Then, a DAG G is a representation of the independent statements: for all variables V in a DAG G: I(V, P arents(V ), N onDescendants(V )), which means that every variable is conditionally independent of its nondescendants given its parents. In other words, given the direct causes of a variable, the belief in the variable is not influenced by any other variable, except possibly by its effects.

The resulting method, which we call Method 1, is specified as follows: Method 1: Given a graphical influence model, the above property can be used to examine whether or not a Bayesian belief network is constructed properly. Each node in a model is examined to check whether or not it is conditionally independent of its non-descendants given its parents.

Algorithm 1: Pearl's network construction algorithm [START_REF] Pearl | Probabilistic Reasoning in Intelligent Systems[END_REF].

1: Choose the relevant variables {X 1 , . . . , X n } that describe the domain 2: Choose an ordering on the variables {X 1 , . . . , X n } 3: for all X i , i = 1..n do

4:

Add variable X i to the network 5:

Add arcs to the X i node from some minimal set of nodes already in the network, P arents(X i ), such that the following conditional independence property holds:

P (X i |X ′ 1 , . . . , X ′ m ) = P (X i |P arents(X i ))
where X ′ 1 , . . . , X ′ m are the variables preceding X i 6: end for 7: Define the conditional probabilities for the variables {X 1 , . . . , X n }

The second method, which we call Method 2, examines whether or not the topology is constructed properly. It uses Pearl's network construction algorithm (Algorithm 1) [START_REF] Pearl | Probabilistic Reasoning in Intelligent Systems[END_REF]. Note that Pearl's algorithm requires the user to supply an ordering on the variables. Method 2: Given a graphic influence model, Pearl's algorithm is used to derive a compact network. This network is compared with the given graphic influence model.

To illustrate the methodology, we use the medical diagnosis example from the "Asia Problem," which was specified by Lauritzen and Spiegelhalter [START_REF] Lauritzen | Local computations with probabilities on graphical structures and their applications to expert systems[END_REF] and subsequently modified by Korb and Nicholson [START_REF] Korb | Bayesian Artificial Intelligence, Chapman and Hall/CRC[END_REF]. The problem involves a patient who has been suffering from Dyspnoea (shortness of breath). The patient is concerned that he has lung cancer. It is known that pollution and smoking increase the cancer risk. Lung cancer can affect the patient's breathing (Dyspnoea) and increase the chance of the patient having a positive x-ray. The preceding two sentences are referred to as "story statements."

Let A denote "Pollution," B denote "Smoking," C denote "Cancer," D denote "X-ray," and E denote "Dyspnoea." Thus, the set of relevant variables used to construct the Bayesian belief network is: {A, B, C, D, E}.

First, we choose the ordering {A, B, C, D, E}. We start with variable A as the root node and add B to the network (Figure 2(a)). According to the story statement, there is no causal relationship between A and B, i.e., they are independent of each other. There is no minimal set of nodes in the network, Parents(X i ), such that the conditional independence property is satisfied. Therefore, no arc is added between A and B. The next variable added to the network is C. According to the story statement, pollution (A) and smoking (B) both increase the chance of cancer (C). The minimal set of nodes (parents) such that the conditional independence property is satisfied is {A, B}. Therefore, arcs are added from A to C and from B to C.

The next variable added is D. According to the story statement, cancer (C) can affect the patient's breathing (Dyspnoea) (E) and increase the chance of having a positive X-ray (D). The minimal set of nodes is {C}. Therefore, an arc is added from C to D.

Finally, variable E is added. The minimal set of nodes is {C} and, therefore, an arc is added from C to E.

As a second example, we choose the ordering {D, E, C, A, B}. We start with variable D as the root node and add E to the network (Figure 2(b)).

We now ask if E is independent of D. According to the story statement, cancer (C) affects breathing (E) and increases the chance of having a positive x-ray (D). In other words, D and E have a common cause C. If the presence of either D or E is known, this will affect the probability of the other being present. Therefore, an arc is added from D to E.

Next, variable C is added. Since cancer (C) affects breathing (E) and increases the chance of having a positive x-ray (D), C is directly dependent on both D and E. Therefore, two arcs are added from D to C and from E to C.

Next, variable A is added. According to the story statement, pollution (A) or smoking (B) increase the chance of cancer (C). Therefore, an arc is added from C to A.

Finally, variable B is added to the network. According to the story statement, pollution (A) or smoking (B) increase the chance of cancer (C). Therefore, an arc is added from C to B.

At this point, we observe that C is the common cause of A and B, and that A and B are dependent. However, according to the story statement, A and B are independent. Therefore, an additional arc must be added from A to B, which makes A and B independent.

Let us now consider a third example with the ordering {D, E, B, A, C}. We start with variable D as the root node and add E to the network (Figure 2(c)). Following the same reasoning as in the previous example, an arc is added from D to E.

Next, we add variable B (instead of C in the preceding example). According to the story statement, pollution (A) or smoking (B) increase the chance of cancer (C). Having cancer affects breathing (E) and the chance of having a positive x-ray (D). Therefore, establishing the presence of D or E affects the probability of the presence of B. Thus, we add arcs from D to B and from E to B.

Next, we add variable A. According to the story statements, pollution (A) or smoking (B) increase the chance of cancer (C). Having cancer (C) affects breathing (E) and the chance of having a positive x-ray (D). Therefore, we add two arcs from D to A and from E to A.

At this point, we observe in the resulting network that D is the common cause of A and B, while E is the common cause of A and B; this implies that A and B are dependent. Since A and B are independent according to the story statement, an additional arc is added from B to A to make A and B independent.

Next, we add variable C. Using the same reasoning as above in relation to A, we finally obtain the network in Figure 2(c).

The three examples demonstrate that different node orderings can result in different network structures. Intuitively, it is desirable to build the most compact network possible. Korb and Nicholson [START_REF] Korb | Bayesian Artificial Intelligence, Chapman and Hall/CRC[END_REF] provide three reasons for constructing compact networks. First, the more compact the network, the fewer the probability values that require to be specified (probability updates are more efficient from the computational point of view). Second, an overly dense network may not represent independence in an explicit manner. Third, an overly dense network may fail to represent the causal dependencies in the domain.

According to Pearl [START_REF] Pearl | Probabilistic Reasoning in Intelligent Systems[END_REF], if the ordering of variables reflects causal reasoning, then the algorithm arrives at the most compact network possible, which enables easier assessments of the probability distributions. Of the three examples discussed above, only the first ordering {A, B, C, D, E} is consistent with cause and effect. Since the orderings in the second and third examples are not consistent with cause and effect, the resulting Bayesian belief networks are not compact.

BitTorrent Model Revisited

We apply the two methods discussed in the previous section to the model in Figure 1. Since there are 24 nodes in the model, there are 24 conditional independence statements. The following conditional independence statements correspond to the five nodes, H, H 1 , H 2 , E 1 and E 8 :

I(H, ∅, ∅) I(H 1 , H, {H 2 , . . . , H 5 , E 4 , . . . , E 18 }) I(H 2 , H, {H 1 , H 3 , . . . , H 5 , E 1 , . . . , E 3 , E 9 , . . . , E 18 }) I(E 1 , H 1 , {E 2 , E 3 , H 2 , H 3 , . . . , H 5 , E 4 , . . . , E 18 }) I(E 4 , {H 2 , H 3 }, {H, H 1 , H 3 , . . . , H 5 , E 1 , . . . E 3 , E 5 , . . . , E 18 })
We use the last independence statement regarding E 4 to analyze the topology of the DAG in Figure 1. First, we ask if it is true that given H 2 , H 3 (i.e., parent of E 4 ), our belief in E 4 would be conditionally independent of its non-descendants. In order to answer this, we look for non-descendants that may affect E 4 . If one is found, then the topology regarding E 4 in Figure 1 does not satisfy the requirement of I(V , P arents(V ), N onDescendants(V )).

Next, we create the Bayesian belief network using Pearl's algorithm. To simplify the problem, we discard H and use the set of variables {H i , E 1 , . . . , E 18 }.

Upon applying the algorithm, we discover that H 3 should not be the parent of E 4 . Also, H 4 should be the parent of E 11 .

In other words, "The torrent was sent to a newsgroup for publishing" (H 3 ) does not directly cause "BitTorrent client software was installed on the seized computer" (E 4 ). Therefore, the arc between them in Figure 1 should be removed. Also, "The torrent was activated which caused the seized computer to connect to the tracker server" (H 4 ) directly causes "Torrent activation time was corroborated by its MAC time and link file" (E 11 ). Therefore, an arc is created to connect the cause (H 4 ) to the effect (E 11 ).

We reconstruct the Bayesian belief network using the variables in [START_REF] Kwan | Reasoning about evidence using Bayesian networks[END_REF]. The new Bayesian network is shown in Figure 3.

Figure 4 shows the results obtained when all the evidence in the new model is set to 100% "Yes." In particular, we obtain 97.67% "Yes" for H 1 ; 99.64% "Yes" for H 2 ; 99.86% "Yes" for H 3 ; 98.94% "Yes" for H 4 ; and 98.48% "Yes" for H 5 . On the other hand, if all the evidence is set to 100% "Yes" in the original model, the corresponding results are 99.7% "Yes" for H 1 ; 99.9% "Yes" for H 2 ; 99.9% "Yes" for H 3 ; 99.8% "Yes" for H 4 ; and 94.1% "Yes" for H 5 .

Figure 5 shows the results obtained with the new model when there is no evidence of E 8 and E 10 . In particular, we obtain 97.67% "Yes" for H 1 ; 96.91% "Yes" for H 2 ; 99.85% "Yes" for H 3 ; 83.68% "Yes" for H 4 ; and 98.44% "Yes" for H 5 . On the other hand, if there is no evidence of E 8 and E 10 in the original model, the corresponding results are 92.7% "Yes" for H 1 ; 99.7% "Yes" for H 2 ; 98.3% "Yes" for H 3 ; 99.8% "Yes" for H 4 ; and 94.1% "Yes" for H 5 .

The drop for H 4 from 99.8% "Yes" in the original model to 83.68% "Yes" in the new model is significant. The drop, which is due to the change in the network topology, does not necessarily imply that the new model is more sensitive. Nevertheless, the two methods help create better models that depict direct causation and help visualize the relationships between various hypotheses and pieces of evidence in a complex legal argument. In the case of a large network, the two methods provide systematic approaches by which an investigator may establish, demonstrate and negate challenges to the reliability of findings based on the digital evidence.

Conclusions

The two methods presented for analyzing Bayesian belief network topologies enable investigators to systematically construct, demonstrate and challenge Bayesian belief networks, thereby providing a powerful framework for reasoning about digital evidence. The methods are im- portant because if any reasoning based on a Bayesian belief network is presented in court, it will be required to demonstrate that the method used to create the network is robust, reliable and follows an established protocol. In particular, since subjectivity is involved in constructing a Bayesian belief network, there should be adequate justification for the choices made in network construction.

Method 1 described in this paper ensures that the nodes in a Bayesian belief network satisfy the key requirement that every variable is conditionally independent of its non-descendants given its parents. In other words, given the direct causes of a variable, the belief in a variable is not influenced by any other variable, except possibly by its effects. Method 2 uses Pearl's algorithm to ensure that a Bayesian belief network is constructed properly. Specifically, it guarantees the generation of the most compact network if the ordering on the variables reflects causal reasoning. Moreover, the method can be used to verify and explore the relationships existing between network nodes.

Cohen [START_REF] Cohen | Two models of digital forensic examination[END_REF] has stated that the science of digital forensic examination is in its infancy. For the science to become more mature, important questions such as "What makes a digital evidence reasoning model appropriate?" should be asked and answered. Our work on analyzing Bayesian belief network topologies is a first step in this direction with regard to Bayesian models for legal reasoning. Our future research will explore other issues such as model refinement, probability adjustment, irrelevant factor elimination, latent factor addition and causal relationship adjustment.

  {D, E, B, A, C }.

Figure 2 .

 2 Figure 2. Networks generated by various orderings.

Figure 4 .

 4 Figure 4. All evidence set to 100% "Yes."

Figure 5 .

 5 Figure 5. Evidence E8 and E10 set to 100% "No."

  Revised Bayesian network for the BitTorrent case.

				E 10
		E 15	E 17	E 11
		E 14		H 4
		E 12	H 3		E 18
		E 8		E 16
	E 3	E 7	H 2	E 13	H 5
	E 2	E 5
	E 1	H 1	E 6	E 4	E 9
	Figure 3.

H 1 Yes: 97.67% No: 0.02% Uncertain: 2.31% E 1 Yes: 100% No: 0% Uncertain: 0% E 2 Yes: 100% No: 0% Uncertain: 0% E 3 Yes: 100% No: 0% Uncertain: 0% E 6 Yes: 100% No: 0% Uncertain: 0% H 2 Yes: 99.64% No: 0.00% Uncertain: 0.35% E 5 Yes: 100% No: 0% Uncertain: 0% E 7 Yes: 100% No: 0% Uncertain: 0% E 8 Yes: 100% No: 0% Uncertain: 0% H 3 Yes: 99.86% No: 0.00% Uncertain: 0.14% E 4 Yes: 100% No: 0% Uncertain: 0% E 9 Yes: 100% No: 0% Uncertain: 0% E 12 Yes: 100% No: 0% Uncertain: 0% E 14 Yes: 100% No: 0% Uncertain: 0% E 15 Yes: 100% No: 0% Uncertain: 0% E 17 Yes: 100% No: 0% Uncertain: 0% H 4 Yes: 98.94% No: 0.16% Uncertain: 0.90% E 10 Yes: 100% No: 0% Uncertain: 0% E 11 Yes: 100% No: 0% Uncertain: 0% E 16 Yes: 100% No: 0% Uncertain: 0% E 13 Yes: 100% No: 0% Uncertain: 0% H 5 Yes: 98.48% No: 0.57% Uncertain: 0.96% E 18 Yes: 100% No: 0% Uncertain: 0%