In a nutshell, we’ve used Apache Hadoop and Apache HBase as the foundation for a new way of processing evidence files, with some key assists from The Sleuthkit, and a deep bench of other open source projects. By using Hadoop, we’re able to stripe evidence data across multiple machines without creating a storage bottleneck, and we’re able to process the evidence in parallel.

The project is still in prototype-phase, and it’s already proven itself to be a viable approach. While ripping apart an evidence file with 20 machines is a lot of fun, we’re even more excited about using intensive processing algorithms (like clustering graphics and documents) with all the CPU cycles we can now harness, and about being able to warehouse evidence files over time for comparative analysis.

You can download our slides (PDF) from the presentation, but feel free to give us a ring or drop us a line if you’d like to know more.

For those who couldn’t make it, the rest of this blogpost is a recreation of my talk, “Factory Forensics.” Geoff and I will be speaking about the technology in a bit more depth at the 2012 DoD Cybercrime Conference in Atlanta, on Wednesday, January 25, at 1100 in the Learning Center room (“Forensic Clusters”). We’re up against Jesse Kornblum in the same time slot, but, hey, he always puts his slides up online, right?

Factory Forensics

Chris Pogue has talked a lot this past year about his approach to casework, which he calls “Sniper Forensics.” I haven’t had the pleasure of meeting Chris in person, but his blogposts about Sniper Forensics are great (Parts One, Two, Three, Four, and Five). The basic idea behind Sniper Forensics is that you keep in mind what question you’re trying to answer in your case, and you work backwards from it [Ed.: admittedly a gross simplification, but, hey, it was a 6 minute talk. Read Chris's posts if you haven't already.]. That way, you stay on target and don’t get overwhelmed by the evidence or fall down a rabbit hole.

But…

The problem with snipers is that they can’t deal with every situation. They need backup. We’re dealing with more raw data as input than ever before, and, as the public has grown aware of computer forensics, we’re now more in demand than ever before. Working smarter (a la Sniper Forensics) and doing less (“triage”) will only take you so far: we have to increase our productivity and get more done. The tool to do that is the assembly line.

According to Henry Ford, there are three main principles of the assembly line. Kind of wordy, but they are:

Ford really wasn’t the inventor of the assembly line, but its refinement at Ford Motor Company early in the twentieth century allowed him to cut the price of the Model T by a third, produce over a thousand of ‘em a day, and put competitors out of business.

So, I went looking around for a way to build an assembly line for forensics, something that would let me process lots of evidence reliably. I looked into how other tech companies were dealing with large data sets, and the most popular solution they use for storing and processing large unstructured data sets is an open source framework, Apache Hadoop.

Hadoop is software that you can run on a cluster of 1 or 2 U servers, your typical entry-level servers with a few disks and a few cores, nothing fancy. It scales up to thousands of machines storing petabytes of data, but clusters can be built incrementally without much hassle.

Hadoop has two main components. The first is HDFS, a distributed filesystem. This breaks up files into blocks and it stores the blocks on different machines. The blocks are automatically replicated and checksummed, so it’s fault-tolerant. [These images come from Cloudera's Hadoop Overview, which is a great place to start learning about Hadoop.]

The second component is called MapReduce, which is a batch processing service. You write your program to a specific API, and then MapReduce sends it to all the nodes in the cluster and starts running it. The nodes only process the blocks of data they have locally, so the disk accesses remain local, and then the system collates all the output automatically. Network traffic is thus conserved, and Hadoop generally does large streaming reads and writes to disk instead of seeking all over the place. The important thing to remember is that it’s faster to send the program to the data than it is to send the data to the program.

So, earlier this year we worked on creating a system for doing forensics on top of Hadoop. There are three main steps. First, we have to ingest the data into the system, doing all the filesystem stuff. This is kind of complicated, but using the Sleuthkit was a big help. Second, we have all our processing tasks, like text extracting, keyword searching, and some other cool things. Finally, the output from the system is a set of static HTML reports that contain all the results, the idea being that we could produce useful information automatically for use as a starting point without having to learn another GUI.

Here are some screenshots of the output reports. The first one gives an overview of the evidence and the search results.

The second one shows you some results from our image clustering routine, where we arrange similar images into groups.

The third shows you key frames that we’ve extracted from a video file, so you can just look over the gallery view of key frames without watching the whole video.

How’d it end up? Well, the good news is that it basically works. We ran it with 5 nodes, 10 nodes, and 20 nodes and all the processing tasks worked. Performance was pretty good and it scaled. The bad thing we found is that we had to learn a lot about Hadoop and use some complicated techniques to get good performance—you can write pretty simple code with Hadoop but performance won’t be as good as it should be. The ugly part of it was that Hadoop is all Java and, while Java is very fast, resolving the dependencies between all the different open source libraries, working with their build systems, and configuring it all on a cluster was a big pain. We ended up contributing a patch to Apache to make this easier.

The other big thing we realized after we created the initial prototype was that it’s not really enough to produce static output for you to use. It’s a good start, but if we’re going to incorporate factory processes into forensics, what we need to output are tools for you to use to help you zero in on your cases (like the snipers you are). Initial results always spur further questions, and if you have to go back to the drawing board to answer them, then we haven’t helped you as much as we could. So, we’re working on that.

This is the machine shop at the first assembly line at Ford. It looks pretty primitive to us now. But it changed history. Many people think that the golden age of forensics is behind us, what with full disk encryption, cellphones, the cloud, and a host of other challenges. But we think we’re just getting started in forensics, and that we have a very bright future in front of us.

I ran a session called Statistical Analysis and Data Sampling for eDiscovery; the presentation can be found here. The idea is that you can use statistical sampling to ease the burden in eDiscovery matters, and to validate keywords on smaller sets of data. I also presented an EnScript which helps practitioners by automatically choosing a random sample from EnCase Logical Evidence Files. I think the presentation was generally well-received and there was a lot of good discussion. My only regret was that there was so much good discussion that we didn’t have time to get into keyword testing in EnCase eDiscovery, which is really the final piece to complete the sampling. If anyone has questions for either Jon or I, feel free to drop us a line.

On another exciting note, we gave some limited early beta demos of Lightgrep for EnCase to friends and colleagues while we were in the Sunshine State. Everyone that took part in the interactive demo let us know that Lightgrep would definitely save them a lot of time not only just by searching more quickly, but also by producing more pertinent results. We met a lot of great people and received some very useful feedback and suggestions.

Based on the feedback we received, we’re making some changes before we release the public beta – things that we feel will make Lightgrep even easier to use with better performance than our already game changing capabilities. Stay tuned for more updates!

It was great meeting everyone; there seems to be some exciting work happening in digital forensics these days, from abstract things like frameworks to very concrete things like mobile device forensics. I particularly enjoyed talks by Tyler Moore, detailing his empirical research on phishing and typosquatting, as well as by Heather McCalley on how rootkits surreptitiously call back to their authors.

Special thanks to Mark Pollitt, one of the local organizers, who took us to a wildlife refuge (with alligators!) as an excursion after the conference ended. We saw lots of alligators, no forensic scientists were eaten, and a good time was had by all.

Exposing attendees to his awful handwriting on the chalkboard, Jon introduced the basic theory behind how grep works. Each search term is used to construct a data structure, formally known as a finite state machine (or, collectively, as finite automata). Those are ten dollar words for something every investigator is familiar with: a flowchart.

A simple keyword, like abc, can be represented with a straightforward flowchart, where there’s a box for ‘a’, which leads to a box for ‘b’, and finally to a box for ‘c’. When conducting a search, the computer starts at the beginning of the flowchart and follows it based upon the bytes it reads, trying to move one box for each byte read. If it can’t go forward, then it starts over from the beginning of the flowchart.

What the various grep operators (e.g., *, +, ?, |, {}) do is alter the shape of the flowchart. For example, | lets you move to two different boxes, + lets you loop back to the box you’re already on, ? lets you skip ahead to some other box, and * both allows you to skip the next box and loop back to the current box. So, while regular expressions may look complicated, they aren’t magic; doodling out a flowchart for a regular expression is a great way to understand how it works.

After Jon finished, I showed a demo of Lightgrep for EnCase. We were only at alpha stage at this point, but everything went very smoothly. Not liking to bore people with mindless sales pitch, we got down to the nitty gritty quickly. We’ve been talking it up quite a bit, so it was gratifying for us to finally show the working product to our peers. We’re really looking forward to our beta testers putting it through the ringer under some different stress loads in the near future. If you’re interested, please sign up for our beta mailing list!

Speed is a feature. An Information Week article today talked about the success and growth of the FBI’s RCFL program. In 2009, the RCFLs processed 2.3 petabytes.

If you’re processing petabytes, you need to go big to go fast.

Going 17,000 miles per hour isn’t easy, though. As in rocketry, mistakes in forensics often aren’t survivable. As evidence sets get bigger, and more demands are placed on investigators, it’s conceivable that problems can slip by… until it’s too late.

The issue I’m concerned with right now is not about making lightgrep fast, it’s about ensuring lightgrep’s quality. How do you test grep… for forensics? What if it misses hits and investigators find out? Worse yet: what if it misses hits, in a subtle manner, and no one notices?

User-level acceptance testing is a good start, where you run typical keywords on known evidence files and compare the results to other tools. This gives a basic level of assurance, but it hardly rules out the subtle bugs.

Better yet, develop automated unit tests. Good software has separate parts, and those parts can be tested in isolation. Lightgrep has unit tests covering its parser, analyzer, search engine, and even some serialization routines. Still, there’s a reason why people find regular expressions hard to learn; they express a lot of options in a handful of characters. It’s hard to write unit tests to cover every scenario.

But the nice thing about regular expressions is that they’re regular: they have a structure. This leads us to exhaustive testing: generate all possible inputs and verify they yield the expected output. The problem with exhaustive testing often is that, computationally, we could count all the stars in the sky before the tests completed.

In forensics, we deal with bytes, and bytes have 256 values. If we tried searching all possible regular expressions with all possible byte streams, we could maybe deal with 3-4 bytes of data before our CPUs melted. However, we can take a cue from genetics. DNA has only four types of genes. What if we didn’t test every possible byte and, instead, restricted ourselves to all possible regular expressions, up to a given length, using a very small set of allowed byte values (known as an “alphabet”)? Then the goal becomes much more possible.

Testing all forms of regular expressions on even a small alphabet puts any grep engine through its paces. That’s what happened to lightgrep this week, and the initial results are about what you’d expect. There’s work to do. But with PCRE as a benchmark, lightgrep will get there.

There’ll be a few more posts concerning the specifics of this testing procedure, getting deep into the weeds. In the meantime, it’s worth thinking about how problems in forensics can be reduced to make exhaustive testing feasible. And it’s worth thinking about how forensics tools are tested now, and whether that’s enough to get us where we need to go.

I gave a brief talk on lightgrep, a new digital forensics grep tool I’ve been working on.

It was surprising to find that there wasn’t anything more sophisticated beyond “strings | grep” in the open source forensics world. Regular expression searching is useful not only for finding relevant text, but also for file signature analysis, artifact extraction, and file carving. Having a good grep tool that can search binary data for many keywords at once—like EnCase can—is important.

Regular expression search algorithms are well-known, and I thought it would be fun to see whether I could code up something halfway decent. The initial results were shocking, and reinforced in my mind that this is a problem worth pursuing.

Lightgrep still has some kinks that need to be worked out before release. If you’re willing to push the envelope, drop me a line and I’ll contact you about beta testing.

Lightgrep Slides for NeFX2010 (pdf)