Automated Digital Forensics and Media Exploitation Simson L. Garfinkel Associate Professor, Naval Postgraduate School August 20, 2009 http://simson.net/ 1
Location: Monterey, CA Campus Size:  627 acres
1500
Students:
▪ US Military (All 5 services) ▪ US Civilian (Scholarship for Service & SMART) ▪ Foreign Military (30 countries) ▪ All students are fully funded
Schools:
▪ Business & Public Policy ▪ Engineering & Applied Sciences ▪ Operational & Information Sciences ▪ International Graduate Studies 2
View from front porch... Automated Document and Media Exploitation: The Need
▪ Media collected on the battle field ▪ Media collected over last 7 years — Hundreds of Terabytes — Hundreds of millions of files from thousands of pieces of media collected over 2 years (Source: Defense Cyber Crime Center)
▪ No “contamination” of evidence between cases. ▪ Do not scale to 100s or 1000s of drives. ▪ Designed for visibility & search, not analysis. EnCase by Guidance Software
Different analysts see different hard drives.
A “hash” is a fingerprint for a file. ▪ e.g. 9ed9127ee08da92aa7ff2fd754ddba91
“Hash Set” = A set of hashes
▪ 9ed9127ee08da92aa7ff2fd754ddba91 ▪ 3a3febb29e55ee975098903a31f8022a ▪ 5db454651210bcb920c010f8149d118c cell phone video: 13316868 bytes 9ed9127ee08da92aa7ff2fd754ddba91
Typical hash sets:
▪ National Software Reference Library (NIST): software distributions ▪ National Center for Missing and Exploited Children: Child porn ▪ WetStone’s Gargoyle Investigator: Malware and steganography tools 11
▪ Hashing requires the entire file. ▪ Hashing is brittle: change a single bit and the hash changes. ▪ Hashing is slow, especially SHA256. 13316868 bytes 9ed9127ee08da92aa7ff2fd754ddba91 13316868 bytes b42abbb9bff83ae769bce02e660ccc42
Area #1: End-to-end automation of forensic processing ▪ Digital evidence file formats; chain-of-custody  (AFFLIB) ▪ Tool integration; automated metadata extraction
Area #2: Bringing data mining to forensics
▪ Automated social network analysis (cross-drive analysis) ▪ Automated ascription of carved data
Area #3: Bulk Data Analysis
▪ Stream-processing ▪ Statistical techniques (sub-linear algorithms)
Area #4: Creating Standardized Forensic Corpora
▪ Freely redistributable disk and memory images, packet dumps, file collections.
Multi-User Carved Data Ascription Instant Drive Analysis Standardized Forensic Corpora
15 Automated Ascription of Multi-User Data
Step 1: Physical device is imaged. Step 2: Disk image is stored on a high-capacity storage device. Step 3: Tools process the image and extract files 17
Some hard drives are used by a single person. Some drives are used by multiple people.

File system metadata (“extrinsic”):
▪ Fragmentation patterns (disk usage) ▪ Where the file is on the hard drive (sector numbers) ▪ Timestamps for “orphan” files.
File metadata (“intrinsic”):
▪ Embedded timestamps — Creation Time — Print Time ▪ Make & model of digital cameras ▪ Usage patterns.
Who is responsible for the file? By surveying exemplar files on the disk, an examiner can create ascription rules.
Step 1: Extract all files and file metadata ▪ File Owner (from filename or metadata) ▪ All files: Location on disk ▪ JPEGs: Camera Serial Number ▪ Word Documents: Author, Last Edit Time, Print Time, etc. Step 2: Build a classifier using ascribable files as exemplars Step 3: Use classifier to ascribe carved data.
Per-Image tags <fiwalk> — outer tag <fiwalk_version>0.4</fiwalk_version> <Start_time>Mon Oct 13 19:12:09 2008</Start_time> <Imagefile>dosfs.dmg</Imagefile> <volume startsector="512">
Per <volume> tags:
<Partition_Offset>512</Partition_Offset> <block_size>512</block_size> <ftype>4</ftype> <ftype_str>fat16</ftype_str> <block_count>81982</block_count> Per <fileobject> tags: <filesize>4096</filesize> <partition>1</partition> <filename>linedash.gif</filename> <libmagic>GIF image data, version 89a, 410 x 143</libmagic>
Metadata extractors are specified in the configuration file ../plugins/jpeg_extract dgi *.jpg java -classpath plugins.jar Libextract_plugin *.pdf dgi — Currently the extractor is chosen by the file extension — fiwalk runs the plugins in a different process — We have designed a native Java interface that uses IPC and 1 process, but nobody wants to use it. Metadata extractors produce name:value pairs on STDOUT Manufacturer: SONY Model: CYBERSHOT Orientation: top - left fiwalk incorporates metadata into XML and ARFF: <fileobject> • • • <Manufacturer>SONY</Manufacturer> <Model>CYBERSHOT</Model> <Orientation>top - left</Orientation> </fileobject>

High dimensionality, heterogeneous data
▪ All files: inode, mode, timestamps, sector #, ▪ JPEG: Serial Number, f-stop, exposure date ▪ Word: Author, Print Time, Create Time, etc.
Sparse data; many missing values
▪ Every data element is missing values in one or more dimensions!
Multiple regions for each class
▪ User files interleave in time, space, etc.
Can’t use “kernel methods”
▪ No linear mapping means no “kernel trick.”

Algorithm: J48
▪ Implementation of Quinlan's C4.5 ▪ Very fast: typically less than 60 seconds. inode > 28455 inode <= 36552 mode <= 365 inode <= 28892: magenta (132.0) inode > 28892 timeline <= 1225239807000: All Users (116.0) timeline > 1225239807000 frag1startsector <= 2585095 libmagic = ASCII text, with CRLF line terminators timeline <= 1225330086000: magenta (8.0) timeline > 1225330086000: yellow (8.0) libmagic = data: magenta (16.0)
Differences from traditional data mining:
▪ Every HD has its own classifier: — Use cross-validation to determine the accuracy of the classifier for this HD. ▪ Every carved file has its own classifier — Only use the dimensions that matter for this piece of carved data.

Special Features:
▪ N=1 works best ▪ We had to create a special distance metric — Nominal Data is distance 0 or 1.0 — Time needs to be specially handled ▪ Hypothesis: — If there is a close exemplar, then that’s the match. sector: 400 time: 543 SN: 5341
sector: 350 time: 400 sector: 32343 time: 23343 File Author: Alice Bob ? sector: 25000 time: 2311 File Author: Alice Bob

Student Theses:
▪ Cpt. Daniel Huynh, “Exploring and Validating Data Mining Algorithms for use in Data Ascription,”  June 2008 ▪ Maj. James Migletz, “Automated Metadata Extraction,” June 2008
Work in progress:
▪ Aleatha Parker-Wood (PhD Candidate, UCSC) ▪ Using “Hamming,” our 1100-core cluster. ▪ J48: —89.5% accuracy on “realistic” data (nps-2009-domexusers) — 93.55% accuracy on real data  (0844) ▪ K-Nearest Neighbor — Less accurate than J48 — Better when N=1 than N=3 or N=10 —Explanation: only works if there is a nearby exemplar. Instant Drive Forensics with Statistical Sampling Research Question: Is it possible to analyze a hard drive in a minute? What if US agents encounter a hard drive at a border crossing? Or a search turns up a room filled with servers?

7.2 GB is a lot of data!
◾ ≈ 0.48% of the disk ▪ But it can be a statistically significant sample. We can predict the statistics of a population by sampling a randomly chosen sample. US elections can be predicted by sampling a few thousand households: Hard drive contents can be predicted by sampling a few thousand sectors: The challenge is identifying likely voters. The challenge is identifying the sectors that are sampled.
Resident Data Deleted Data user files email messages [temporary files] No Data blank sectors
Resident Data
but can only be recovered with forensic tools. Deleted Data
No Data Sampling can distinguish between "zero" and data. It can't distinguish between resident and deleted.
What does it mean if 10,000 randomly chosen sectors are blank? ▪ Well, what does it mean if 1 randomly chosen sector is blank? ▪ A 1TB hard drive has 200,000,000 sectors. — If the drive has 1 blank sector and 199,999,999 data sectors: We are very lucky! — If the drive has 200,000,000 blank sectors and 0 data sectors: The sector is typical. Let’s assume the disk has 10MB of data. ▪ 20,000 non-zero sectors. ▪ Read just 1 sector; the odds of finding a non-blank sector are: 200,000,000 = 0.999. 200,000,000 ▪ Read 2 sectors. The odds are: 200,000–20,000 / / 199,999,999–20,000 / 200,000,000 199,999,999 II 0.99980001 first pick second pick Odds we may have missed something
The more you sample, the better the chance of not missing something:
Table 1:  Odds of not finding 10MB of data for a given number of randomly sampled sectors ▪ So if you sample 50,000 sectors of a 1TB drive and find all blank sectors, there is a 0.67% you missed 10MB of data, or a 99.33% chance the drive has less than 10MB data. 41
A file 30K consists of 60 sectors: newpage.html <html Many file types have characteristics headers and footer:
But what about the file in the middle?
HTML files can be reliably detected with HTML tags <body onload="document.getElementById('quicksearch').terms.focus()"> <div id="topBar"> <div class="widthContainer"> <div id="skiplinks"> <ul> <li>Skip to:</li> MPEG files can be readily identified through framing ▪ Each frame has a header and a length. ▪ Find a header, read the length, look for the next header.
The PDF file format consists of: ▪ PDF header ▪ PDF xref table (a directory of objects in the PDF file)

PDF header:
PDF xref:

PDF JPEG: PDF Text:
のの
6 0 obj << /ProcSet [ /PDF /Text /ImageB /ImageC /ImageI ] /ColorSpace << /Cs1 7 0 R /Cs2 10 0 R >> /Font << /F1.0 11 0 R >> /XObject << /Im1 8 0 R >> >> endobj 8 0 obj << /Length 9 0 R /Type /XObject /Subtype /Image /Width 800 /Height 533 /ColorSpac\ ↑ 0 R /Interpolate true /BitsPerComponent 8 /Filter /DCTDecode >> stream \377\330\377\340^@^PJFIF^@^^^^^^^^^^^^@^@\377\33^@C^@^F^D^E^F^E^D^F^F^E^F^G^G^FV YH AP T^X^X^W^T^Y^Y^Z^]%^_^Z^[#^\^Y^Y , #%')*)^Y^_-0-(0%()(\377\333^@C^A^GY AGAG YH AS 12 0 obj << /Length 13 0 R /N 3 /Alternate /DeviceRGB /Filter /FlateDecode >> stream x^A\205\224MH^Tα^X\307\377\263\215^D\261^F\321\227^H\305\320\301$T&^KR^B\323\365 b\2353w\235^\q\247\231\335-E"\204\350\230u\214.VD\207\210N\345 C\247:D^D\231u\211\240\243E^P^E^"\266\377;\223\273cT\27603\277y\236\377\373|\275\ 303^@U\217R\216cE4 ^\312\316\273\311\336\230vztL\333\374^ZU\250F^T\)\303s:^R\211^AV 25\317\365k\365-^TiYj\224\261\326\3736|\253v\231^PP4*wd^C> y<\340\343\2\ 5α$^[^S\2514\331!7\270C\311N\362-\362\3261\210\307C\234^V\236^AT\265S\ \310-E#+c> \353v\332\264\311\357\245=\355^YS\324\260\337\31079^K\33\ ?50\333^^ \323\213\212m\314^C^^\334^C^\327UI\3655\300\316^O`\361P\305\\ 366=\351\3176\331\365\312\313^\j\366\303}\321^Xk\372P*}\257^C6\337^@~^/\225~\334.V \225~\336q^N\326\361\3242 n\321\327\2620\345%^P\324^Γ\354f \374\344^Z\375\213\203\236|U^K\260\3009\2161^A\ \373^_^B\333^_^C\2111 \\250^U\221\31317\270\362\342"\347^Bt 814N\344\265f ]?\242u\360h\205\326g^ [M^MZ\312\2624\337\345i \256\360\204 [^T\351&L\ {x\2280\366^W\271$\274\356\337\254\314\245$1\234%\232\330\326\247\264\350\
▪ Compressed Text ▪ Numbers (4)
▪ ColorSpace ▪ ColorSpace ▪ JPEG ▪ Compressed Text ▪ Array [ /ICCBased 12 0 R] • Text ▪ Array [ /ICCBased 14 0 R] ▪ Media Box ▪ Page Count ▪ Compressed Text ▪ Font Table ▪ Font Descriptor ▪ Metadata xt I his is some i
Terminal — emacs-i386 — 96×20 :UxEn\337~\312\3121\328R\325\202^FNQ^Z^P\311^\\204^G^Q\361ThCK^K\206F\387\329\251\2456=$M9\311\\ ^D\302^FJ3^[\275\310<\252\357S\364~"^Q\274\341\257\313P\236\332t$js^0 *~\252+^M\324\306\212\366\\ ^F^Z\343\225Q\334R\221$-*V\242\304n\301\301QS^C\224Ds\263PK^\U6^S^[\360\260\322\301\334d*\2851\\ 331YQ \301^X*\212uP\226\273SVI\371YI^S\303\206\374\324S\267f\310\344\265*ia\217^N^\\367U^R^B\20\ 2\255\306\212:\310K^^\329Q^\^U\326\305QC+\237L^N\234\362QQP\334]^S\303j^ZA^]U\356[\213\250\267\\ 324\3230\267\212\302{ ;ew\264\355h\266^L\274h#^_\273"\246\284\364\316kr]/\305\350\232bW\324\266^\ \2278^0{\220\323\232\271q^Kc^D0\227^^\301EeS\266\341z\250^M^A\314\284\235\373\224M\2753\287mM\ 68 L?? -:---F1 file1.pdf (Text)----11:51AM 1.13 Nail------------ Terminal — emacs-i386 — 96×20 888867114 18999 n eeeeaaa34  eeaaa  r #200066178 enang n PROFESSION (PROFESSION) 000072689 80000 n 6999972925  89999  n trailer << /Size 21 /Root 16 B R /Info 1 B R /ID [ <5daBb90054e3d59eede498c9741112cb> <Sdg8b98854e3d59eede198c9741112cb> 1 >> (Text)——11:55M 0.83 Mail-------- -:---F1 file1.pdf 47 Most files on the hard drive are not fragmented. JPEGs in PDFs can be identified by scanning forward. In previous research, we found that only 15% of forensically interesting files are fragmented [Garfinkel 2007]. Therefore, we can use a sector's context to assist in identification:
In previous research, we found that only 15% of forensically interesting files are fragmented [Garfinkel 2007]. Therefore, we can use a sector's context to assist in identification:
In previous research, we found that only 15% of forensically interesting files are fragmented [Garfinkel 2007]. Therefore, we can use a sector's context to assist in identification:
In previous research, we found that only 15% of forensically interesting files are fragmented [Garfinkel 2007]. Therefore, we can use a sector's context to assist in identification:
In previous research, we found that only 15% of forensically interesting files are fragmented [Garfinkel 2007]. Therefore, we can use a sector's context to assist in identification:
In previous research, we found that only 15% of forensically interesting files are fragmented [Garfinkel 2007]. Therefore, we can use a sector's context to assist in identification:
In previous research, we found that only 15% of forensically interesting files are fragmented [Garfinkel 2007]. Therefore, we can use a sector's context to assist in identification:
In previous research, we found that only 15% of forensically interesting files are fragmented [Garfinkel 2007]. Therefore, we can use a sector's context to assist in identification:
Time to read 10,000 randomly chosen 64K runs: 45 seconds
Identifiable:
▪ Blank sectors • JPEGs ▪ Encrypted data • HTML
Sample report:
▪ Encrypted: 10% (100GB) ▪ JPEGs: 5% (50GB) ▪ MP3s: 50% (500GB) — Kind of interesting if you are looking at an iPod

Publications:
▪ Roussev, Vassil, and Garfinkel, Simson, File Classification Fragment---The Case for Specialized Approaches, Systematic Approaches to Digital Forensics Engineering (IEEE/ SADFE 2009), Oakland, California. ▪ Farrell, P., Garfinkel, S., White, D. Practical Applications of Bloom filters to the NIST RDS and hard drive triage, Annual Computer Security Applications Conference 2008, Anaheim, California, December 2008.
Work in progress:
▪ Alex Nelson (PhD Candidate, UCSC) summer project ▪ Using “Hamming,” our 1100-core cluster for novel SD algorithms. ▪ Roussev’s Similarity Metric Standardized Forensic Corpora

Key technical challenges:
▪ Evidence preservation. ▪ File recovery (file system support);  Undeleting files ▪ Encryption cracking. ▪ Keyword search.
Evidence Reconstruction ▪ Files (fragment recovery carving) ▪ Timelines (visualization) Clustering and data mining Social network analysis Sense-making

Hallmarks of Science:
▪ Controlled and repeatable experiments. ▪ No privileged observers.
Why repeat some other scientist’s experiment?
▪ Validate that an algorithm is properly implemented. ▪ Determine if your new algorithm is better than someone else's old one. ▪ (Scientific confirmation? — perhaps for venture capital firms.)
We can’t do this today.
▪ Bob's tool can identify 70% of the data in the windows registry. — He publishes a paper. ◾ Alice writes her own tool and can only identify 60%. — She writes Bob and asks for his data. — Bob can’t share the data because of copyright & privacy issues.
Since 2001 more than a dozen papers have been published. ▪ McDaniel et. al reported 43.83% accuracy on JPEGs ▪ Moody & Erbacher report 72% accuracy. ▪ Karresand and Shahmehri: 97.90% true positive rate and 99.99% true negative rate. ▪ Calhoun and Coles: 83% to 99% accuracy
But everybody used a different data set!
▪ Most did not release their code, either. ▪ If you try to re-implement the algorithm, how do you know you got it right? Problems in working with “wild data:” ▪ You don’t know ground truth ▪ Time spent collecting & preparing is time lost to research
Some teachers get used hard drives from eBay. ▪ Problem: you don’t know what’s on the disk. — Ground Truth. — Potential for illegal Material. ▪ Distributing pornography to children is illegal. ▪ Possibility for child pornography. Some teachers have students examine other student machines: ▪ Self-examination: students know what they will find ▪ Examining each other’s machines: potential for inappropriate disclosure Also: IRB issues

Forensic Challenges
• DFRWS 2005 — 2009 — Windows memory analysis — Linux memory analysis — File Carving ▪ DoD Cyber Crime Center (DC3) Challenges ▪ Honeynet “Scan of the Day” — Widely used, but questionable realism
NIST Computer Forensic Reference Data Sets (CFReDS)
▪ Small number of test images. ▪ Good for tool testing, but not necessarily for research or training.

Test Data
◾ Constructed for the purpose of testing a specific feature. ▪ CFReDS “Russian Tea Room floppy disk image” to validate Unicode search & display.
Sampled Data
▪ A subset of a large data source — e.g., sampled web pages or packets. ▪ Hard to randomly sample.
Realistic Data
▪ Not “real” — made in a lab, not in the field.
Real and Restricted Data
▪ Created by actual human beings during activities that were not performed for the purpose of creating forensic data. ▪ Controlled for privacy reasons.
Real but Unrestricted
▪ Released for some reason. e.g. the Enron Email Dataset ▪ Photos on Flickr; User profiles on Facebook.
This is primarily an issue with federally funded research.
Experiments are exempt under 45 CFR 46:
▪ “if these sources are publicly available” ▪ “or if the information is recorded by the investigator in such a manner that subjects cannot be identified, directly or through identifiers linked to the subjects." What about re-identification research? ▪ Probably needs IRB approval in advance.
A real but unrestricted file corpus ▪ 1 million files Test and Realistic Disk Images ▪ 6 disk images
The Real Data Corpus
▪ More data than you can shake a stick at. Really! — Half is in Cambridge MA — Half is in Monterey, CA
1 million documents downloaded from US Government web servers ▪ Specifically for file identification, data & metadata extraction. ▪ Found by random word searches on Google & Yahoo ▪ DOC, DOCX, HTML, ASCII, SWF, etc.
Free to use; Free to redistribute
▪ No copyright issues — US Government work is not copyrightable. ▪ Other files have simply been moved from one USG webserver to another. ▪ No PII issues — These files were already released.
Distribution format: ZIP files
▪ 1000 ZIP files with 1000 files each. ▪ 10 “threads” of 1000 randomly chosen files for student projects. ▪ Full provenance for every file (how found; when downloaded; SHA1; etc.)
tp://domex.nps.edu/corp/files/

Test Images:
▪ nps-2009-hfstest1 ▪ nps-2009-ntfs1
Realistic Images:
▪ nps-2009-canon2 ▪ nps-2009-UBNIST1 ▪ nps-2009-casper-rw ▪ nps-2009-domexusers (NTFS)
Each image has:
▪ Narrative of how the image was created and expected uses. ▪ Image file in RAW/SPLITRAW, AFF and E01 formats ▪ SHA1 of raw image ▪ “Ground truth” report (HFS+) (NTFS) (FAT32) (FAT32) (embedded EXT3)
Most forensic work is based on “realistic” data created in a lab. We get real data from CN, IN, IL, MX, and other countries.
Real data provides:
▪ Real-world experience with data management problems. ▪ Unpredictable OS, software, & content ▪ Unanticipated faults
We have multiple corpora:
▪ Non-US Persons Corpus ▪ US Persons Corpus (@Harvard) ▪ Releasable Real Corpus ▪ Realistic Corpus
Note: IRB Approval is Mandatory!

Publications:
▪ Garfinkel, Farrell, Roussev and Dinolt, Bringing Science to Digital Forensics with Standardized Forensic Corpora, Best Paper, DFRWS 2009
Websites:
▪ http://digitalcorpora.org/ ▪ http://domex.nps.edu/corp/files/
Work in progress:
▪ Joshua Gross, NPS postdoc, 2009-2010