Codeslack

Running Rules — A Rough Ranking

2023-09-20T12:06:00.003-04:00

A caveat: this post is more brain dump than research. I would not be surprised if multiple academic papers have laid out competing hierarchies and frameworks for classifying rules engines. However, doing research is hard. It takes me days of searching to find good papers, and then it takes me weeks of re-reading to grok them. So what follows is entirely NIH.

Problem definition

Say you have a big pile of data. There's a file, it has some records in it. The records are serialized in some format, like json, protobufs, pcaps, or, more ridiculously, binary xml records inside of a chunked binary file format (how I miss LfLe!). Maybe there's some compression involved. And what your boss/department/company/industry would like to know is whether individual records in that data set match any number of rules in a set and, if so, which ones.

Note how uncomplicated of a task this seems. We don't need to sum any of these fields across records, compute statistics on them, join them with lots of other data sets (well, we do and will; cyber calls this phase "enrichment" but it happens much later), or such. Our problem is, for each of n records, which of our m rules matches on the record?

(Note also how this is actually a join, but since we're so often processing complex records in complicated formats as it lies and using rules with a rich and complicated set of predicates, refining the computation to the point where it can be performed as a join is damn near impossible.)

Rules

Ok, records, sure, records are easy. Tuples of fields, maybe there's some typing, maybe the fields have names, maybe there are complex types, but, still, we all understand these records: they're logs, CSV, JSON, maybe protobufs/Avro/Thrift or pcaps. What are the rules?

A rule could be very simple, e.g., "Value = 5". A simple evaluation rule like this can be called a predicate; it's performing a single evaluation against a single field in the record and the result of the predicate is either true or false. Predicates can be joined together into complex rules with Boolean logic. The operators in the predicates will likely permit equality checks and comparisons. Often there will be functions (which are also just operators without fancy syntax) like "contains", "in", "like", "matches", which help with strings and sets. Perhaps if you're unlucky, you'll be working in an extensible rules language where a predicate can involve parsing kilo/megabytes of raw data to compute some fields on the fly. Then you'll tire of such complexity, and the accompanying slowdown in runtime and development time that comes with it, and you'll adopt the hot new rules language that seems simpler and friendlier, the kind assembled by field practitioners who can't be bothered with knowing that describing computer language syntax was solved 64 years ago.

Rules evaluate different fields in the records, often comparing them against literal values. It may be possible for rules to compare different fields in the same record, e.g., "record.created_timestamp < record.lastmodified_timestamp", though this is rare. What we will not consider is the ability for rules to compare/evaluate multiple/different records with possible aggregations. That's what SQL is for.

Implementation types, ranked

So, how do we write a program to run the rules against our data? What follows is a ranking of implementation approaches I can envision, from least optimized to most. This ranking primarily considers throughput, i.e., how many records can evaluated against a given set of rules in a measure of time.

Ad hoc

Rules seem hard and abstract. Unrestricted Boolean logic? Comparisons? Code Monkey think this is hard! (Code Monkey output not functional or elegant.)

If rules can be restricted to simpler and specialized forms, then an ad hoc rules engine may only need to consider hard-coded logic for looking up hash values in a hash set, parsing PE file headers, or conducting string searches. Perhaps a few different types of rules can express a small number of commonly desired Boolean forms, so a rule could simply OR constituent ad hoc evaluation functions, or maybe AND then, or negate them. I did this with EnCase eDiscovery/EnCase Cybersecurity, where the user could choose from three different Boolean forms for combining logic on filesystem metadata, file content search terms, and file hashes. Those three options handled all the practical use cases.

Parse trees

Ad hoc engines are pretty limited, however, and parsers aren't that hard, once you know how to write one. So, if you can parse formal rules, with Boolean logic, then you can build a parse tree data structure. And if you can build a parse tree, then you can execute it according to the types of nodes in the parse tree. The engine will generally involve a stack data structure and one or more switch statements for executing what to do for each type of node in the parse tree (e.g., an OR operator). Sometimes the parse tree may be turned into an abstract form, with enums and objects; other times it'll just be character literals that are being compared directly.

Performance will vary amongst implementations, and especially depend on the implementation language/platform. An engine written in Python will be a lot slower than one written in Rust or C. Still, throughput may only be 10MB/s or less, and will degrade considerably as the rules add up — each rule will need to be parsed and evaluated, and there's usually not any work done to consolidate logic or even just useful setup work between rules. If parsing is not a separate step from evaluation, then the parsing logic itself will need to be re-evaluated with each record.

A possible way out of writing a proper parser and evaluation engine is to recast the rules into some other language that can be embedded and executed itself; I also did this in EnCase eDiscovery/EnCase Cybersecurity where the EnScript engine itself was exposed as an API to EnScript, and then I could just generate EnScript snippets on the fly as EnCase Filters and execute that code against objects. And when I first started thinking about evaluating rules, in 2005, I realized that if the industry was smart it would simply write its rules in Prolog and life would be easy.

Did the industry adopt Prolog?-

(That was a Prolog joke.)

Instead the industry first adopted OpenIOC (yay xml) and then whatever-the-hell YARA is. And now there's sigma, which is even less well-defined than these two predecessors.

Examples: Hayabusa, chainsaw (a bit more elegant)

Virtual machines

If you can generate a parse tree and you refactor your code enough, you'll often find you have a loop that pops nodes off a stack, evaluates those nodes, and then pushes them back onto the stack until the stack contains only one element and there's nothing left in the rule to parse: that one element then is the result.

If you have that code, then it is not a big leap to represent those nodes as invented byte code, or p-code, and then to execute that byte code. As it happens, this leap can make the evaluation engine astonishingly straightforward — there's a loop around decoding the current instruction where the opcode's evaluated by a switch statement and the cases perform the operation. The complexity of direct parse tree evaluation can be spread out across a separate compilation step, which transforms the parse tree into the byte code.

Generally these virtual machines fall into two classes: stack-based and stackless. Stack-based virtual machines are typically simple and low-level, where the operations are extremely simple and evaluation follows the parse tree representation. Stackless VMs may use a byte code representation that is higher-level and domain specific, with instructions that correspond more directly to complicated functions (e.g., "contains" resulting in a string find). This is not a precise distinction, of course; the precise distinction is that stackless VMs lack a stack... but lacking a stack often results in greater complexity being put into the operations.

Virtual machines have some nice properties that bring performance benefits. Decoding and evaluation results in simple code, and optimizing compilers love simple code, which they can tease out into sequences of instructions that pipelined CPUs can evaluate efficiently. There's often far less branching in the resulting code, so there are fewer stalls. And critically, the byte code tends to be compact and stored altogether in memory, resulting in excellent L1 cache hit characteristics.

With a separate compilation step, the virtual machine approach can also be amenable to optimization passes. For example, across a set of rules there may be duplicate predicates. A rule engine that understands all the rules at once could deduplicate evaluation of these predicates. It could also reorder evaluation of predicates to try to prove rules don't match (the common case) with early exits.

Lightgrep uses the virtual machine, in a stackless complicated way. It's based in no small part on Russ Cox's excellent blog post Regular Expression Matching: the Virtual Machine Approach. Whole programming languages can be implemented with virtual machines, too, like Python. Another notable example that's generated considerable work and blog posts over the years is Lua. One could do a lot worse than embedding Lua and calling it a day.

Other examples: jq, PCRE

JITs

If you're parsing rules and compiling them to byte code, well, why not compile them to machine code instead and make it the CPU's problem? This is called a JIT, for just-in-time.

Do you like speed? JITs can be blazing fast. They lower evaluation to the level of the machine, where there is no engine, i.e., getting your crappy Code Monkey software out of the way of the CPU is probably the best way to go fast.

But JITs also have a cost — welcome to tradeoffs! First, rules tend to be fairly compact, a few dozen characters. Those rules can unroll to hundreds or thousands of machine code instructions. Invented virtual machine byte code can still be compact, but machine code deals with registers, raw arithmetic, and loads/stores. So, typically, JITs will need more memory to represent the rules, and this can turn into a problem when you have a lot of rules.

Additionally, compiling the rules to machine code can take time, so there are larger startup costs. This is especially the case if your JIT has optimization passes. This often leads to faster evaluation, but could wind up being a false economy, where a simpler engine would get through processing all the data before a JIT even starts running.

What's more, an off-the-shelf engine with optimizers can itself be dozens of megabytes in size. You're going to embed LLVM into your tool? Good luck fitting that on a floppy and/or downloading to point-of-sale endpoints running on a cheap Comcast link.

Portability also becomes a concern. If you prudently decide not to embed LLVM, now you need to find a JIT that's portable if you want to support more than x86. Good luck! I'm sure there are solutions, but I don't know of a clear answer off the top of my head.

JITs also have security concerns. A normal executable gets compiled and it runs. Modern operating systems will treat its code and data separately, with the code protected by the virtual memory manager as read-only and the data treated as non-executable. With JITs, data and code are the same thing! The JIT will need to write out machine code to memory and then execute it directly; this requires some low-level operating system trickery.

Examples: PCREjit, luajit, redgrep, Ken Thompson's original regular expression search engine for IBM 7049

SIMDized

Modern CPUs have a lot of capability. Pipelined CPUs became common forty years ago. Thirty years ago CPUs went super-scalar. Twenty years ago CPUs went multi-core.

A rule engine that uses a JIT, especially a simple one without optimization passes, will struggle with pipelining as it's likely to embed many branches that mispredict with some regularity (a 90% branch prediction rate is still pretty bad). It will likely not execute with IPC rates > 1.0 (unless you're running on one of Apples magic M chips, that put jillions of transistors towards a monstrous ROB). And for sure you will not get multiple cores utilized, as multithreading is always an exercise left to the user (and rightfully so).

These three limitations need to be addressed in a rules engine if you want to fly as fast as the hardware can go. Good luck! I don't have good answers for you other than lots and lots of hard work.

And even if you are able to write a fantastic rules engine that JITs out code with high branch prediction and IPC rates, and uses threads smartly to process [batches of, you'll need to amortize your locking to avoid stalling] records in parallel, you still won't be using your CPU to its fullest potential.

18 years ago Intel released SSE3, and SSE3 quietly revolutionized SIMD optimization. It took awhile for folks to figure out the magic new pshufb instruction, but each new SIMD ISA since has added lots of capability (though ARM's NEON ISA is more comparable to SSE 4.2 or AVX, with 128 bit registers while just about everyone with an Intel CPU has at least 256 bit registers and many have 512 bit registers). Contemporary CPUs can now often retire multiple SIMD instructions per cycle, if they're scheduled correctly.

Predicates in rules evaluate to true and false. Rules combine predicates with Boolean logic. If you're thinking what I'm thinking, then finding ways to represent predicates and rules in SIMD bit vectors is likely to provide a lot of benefit.

However, it's easy to forget the MD in SIMD. A good SIMD engine will likely only gain high throughput by biting off a chunk of records, decomposing them into their fields, and evaluating those fields with SIMD operations in parallel, then, many instructions later, taking a look at the result and separating matching records.

One major trouble with adopting SIMD is portability. Even amongst x86 CPUs, there are multiple targets ISAs (AVX-512 is a family [and a Tolstoy-esque unhappy one at that] of differing ISAs, then there's AVX-2, AVX, SSE 4.2 for the Sandy Bridge diehards like me...), and different CPU microarchitectures may have very different performance characteristics for the instructions in those ISAs. And then there's ARM NEON. Oy.

Another major trouble with using SIMD operations in a rules engine is that the predicates in a modern cybersecurity ruleset are many, but most evaluate to false a great deal of the time. So a bit vector representation of all the predicates across all the rules will still be large (thousands of bits), much too large for a single register, and most of the bits will be unset. So, there's natural sparsity to cope with — maybe a bit vector representation isn't worth it? Another major trouble will be the dependencies between predicates in the rules; how do you benefit from early exit with a SIMD approach?

The only answer when it comes to SIMD optimization is empirical bloodymindedness.

Examples: none that I know of, naïve SIMDization is an uncanny valley of death

Multi-algorithm SIMD with ad hoc components

Bloodymindedness it is then. Relying on simple SIMD operations to evaluate sparse bit vectors with thousands of bits could lose out to a normal JIT engine, maybe even a VM. The way to apply SIMD is to look for amenable types of predicates and rules and target those with specialized SIMD algorithms.

Here Hyperscan reigns supreme and alone, and with its integration into Suricata pcap scanning has benefited from it for a number of years. Noseyparker also integrates Hyperscan for secrets scanning. But Hyperscan, as an Intel project, is unsurprisingly Intel-only. There's been an attempt or two to port Hyperscan to ARM, but Hyperscan's development itself seems tenuous and the porting attempts can be characterized as "academic" in comparison.

DuckDB is also worthy of mention here. As a columnar database, it is a good fit for SIMD operations, and it benefits greatly from them. Any Python programmer considering writing a rules engine should do everyone a favor and instead focus on ingesting their data into DuckDB. (I would also extend this recommendation to many C programmers who've written popular engines, as well as to those that naïvely bundle such engines into larger scanners.)

Further Considerations

Record parsing

Rules don't exist in a vacuum. After all, what we care about are the records. And records are inevitably represented in their own form (CSV, json, in-memory data structures, etc.). Dealing with those records and getting their necessary fields out to where they can be evaluated by predicates in our ruleset is not free. In fact, it may dominate the runtime, perhaps by orders of magnitude, especially if we're not careful with how the data's encoded (ugh cybox) and which libraries are used (🤡).

An interesting approach is simdjson. Simdjson uses SIMD operations in parsing json records in parallel, but it also embeds some [very] rudimentary rules capability with JSON Pointer support. That allows it to evaluate json records without first doing a full parse.

Avoiding full parsing has of course been a key aspect in regular expression searching. Fast regular expressions don't parse text into lines, parse lines into Unicode codepoints, and run codepoints through their Unicode-aware regexp engines; no, fast regular expression engines look for byte literals in megabyte-sized blocks of bytes and only when there are hits—and some refuse to believe there are hits without repeated evidence—do they bother to look for line breaks and consider the full regular expression(s).

Heavyweight processing components

Additionally, some predicates may be call-outs to entire subcomponents doing complicated things (looking at you, YARA). Searching strings or files, hashing, parsing parts of file formats, these are operations that go well beyond evaluating records of tuples/dicts in csv or json. The rules engine must call out to these subcomponents, and a considerable portion of runtime will be spent in those components and not in the evaluation of rules.

Predicate cost weighting

To repeat, runtime may be dominated in components evaluating complicated predicates completely outside the normal ken of a rules engine. Therefore, the ideal rules engine will have some notion of which types of predicates are costlier than others, and the engine will then analyze the rules and the predicate costs to evaluate the cheapest predicates first that permits early-exit.

For an example of a trick I've used for decades, though not in a general purpose rules engine, consider cryptographic hashing for file matching; if I know the file sizes of the set of [contraband/IP/malware] files I'm trying to match against then I can first check to see whether the input file has a matching file size; only if it does will the input file need to be read and hashed. This will get you several orders of magnitude of speedup when scanning disk images or live endpoints, so long as you have all the original file sizes and their cardinality is not too great.

A Dismal Conclusion

Do I have a conclusion? No, not really. Rule engines exist, but few are separate from their rule language, with tight coupling that consigns them to the same fate as that of the rule language and the commercial entities that sponsor them. Most of the best engines tap out with a virtual machine approach, avoiding the hard engineering involved in JITs and SIMD, but also missing out on the 10+ GB/s of throughput that's possible with contemporary CPUs and DRAM. A few crazy people have made it to that promised land but for specialized domains. And going crazy is meaningless if you don't consider the input format of the records you want to process.

Developing and maintaining an ideal rules engine is a hard problem, requiring genius, expertise, bloodymindedness, and the long-term focus/dedication (with concomitant financing) to scrap existing code and build new implementations from scratch in response to new hardware capabilities. Am I working on one? No. Would I like to? Sort of. Will I? Maybe, but likely without success, because genius, expertise, bloodymindedness, and long-term focus are a lot to ask, and I am lazy, tired, and distracted.

So, continue along with your YARA and SIGMA rules, and their 386-era throughput.

Learning Timely & Differential Dataflow, Part I of K

2022-10-30T23:33:00.003-04:00

Differential Dataflow is both a Rust library and a dataflow computation paradigm. This blogpost is about the former.

Except... it's not?

Differential Dataflow seems to be an advanced construct built on top of Timely Dataflow, which is also both a Rust library and a dataflow computation paradigm. The rough idea is that Differential Dataflow can accept new input items after having processed a bunch of data and update derived result sets/output with a minimum of computation; it does this by paying attention to changes/deltas/differentials between nodes in a dataflow graph. (NB: I do not understand it beyond this rough idea; some day I'll get around to reading the paper, but there are programs to write.)

In order to compute differences in a dataflow graph, though, one first needs a dataflow graph system, and that's what Timely Dataflow provides.

So, here's how to learn Timely.

Step 1: Do not read the Differential Dataflow docs.

(This may seem alternately obvious and counterintuitive.) They're less than fantastic at distinguishing what Differential Dataflow provides above and beyond Timely, yet any use of the differential dataflow crate will have one quickly using the timely dataflow API, and likely more heavily than the former.

Step 2: Read the Timely Dataflow docs.

Timely Dataflow online book (pamphlet)
Blog posts — An Introduction to Timely Dataflow

https://docs.rs/timely/latest/timely/

Step 3: Investigate magic in examples

wtf does timely::execute_from_args do?
inspect — this seems more as a debugging aid? or does it force computation?
is aggregate just reduce by a different name? is it more? is it less?

Hash is presumably used for grouping values from the different keys together, but read the source to confirm this is correct, kind of akin to Hadoop's RawComparator.
But is Hash collision resistant? Does it just use for rough partitioning and distinguish between different keys? Or do collisions (on a 64 bit int) signify equality and good luck working with strings and such?

Step 4: Write some toy programs.

Many (most?) of the example programs in the docs have to do with iterative graph computations. I can see how they're the motivating class of problems for Timely, as older systems fall down here (ahhhh, remember the days of cascading MapReduce jobs?), but it would be nice to have simpler examples with clearer analogues to other systems (by which I mean, WordCount).

In particular, Timely and Differential Dataflow are Rust libraries, so they are a readymade data processing engine that play nicely in the Rust ecosystem. The downsides of Hadoop/Spark/Flink/et al have always been their cost of scaling down and being so firmly mired in the muck of Java, requiring enormous shell scripts to manage classpaths and the like.

Rust scales down to a single machine quite nicely, and Timely purports to do so as well. Therefore, it's nice to use for data processing even if all the advanced time/windowing features are used.

Programs to write:

WordCount
WordCount w/ Combiner (or does Rust just do this?)
Map-side join
Reduce-side join
Composite aggregation, of count and sum (how many files do we have, and what are their total size?)

Step 5: Questions

Does Timely actually support distributed processing, with multiple nodes???
How hard is it to submit patches to the docs?
How much attention is it getting now that Materialize exists and is focused on a higher-level database product?

Evaluating SANS Courses

2020-01-07T10:14:00.000-05:00

I've only taken one DFIR training course, the EnCase Advanced class back in 2003, the third week into my new job at Guidance Software at their old Green Street location. It was taught by Jessica Bair and Ric Stonesifer, and, knowing nothing about forensics or EnCase, it was a good fast-paced introduction to the field. From there, I learned by doing, maintaining Guidance's core set of artifact EnScripts and then supporting the company's professional services examiners in their casework.

I've forgotten a great deal about old artifacts since then, and have not kept up on new artifacts as much lately. And, of course, there are far more systems and approaches to forensics than existed 15 years ago—macOS, iOS, Android, memory forensics, malware analysis, etc. My dimly-recalled Windows 98 artifact knowledge no longer applies.

Live training is a good option for me because I can turn my phone and email off and simply focus for a week. So, I'm thinking about taking a SANS course this year. Which one should I take? These are the possibilities:

FOR500, Windows Forensics. I do know a lot about Windows forensics, so I'm worried I might get a little bored, but this would also be a good tune-up.
FOR 508, Advanced IR & Threat Hunting. I've assisted on a number of large-scale IR scenarios, but always in a focused, limited capacity where I've been asked to write code to do a specific thing (usually at scale). Working through the complete chain of an investigation could give me new insight into current problem areas to focus on as a developer, and especially provide me with greater intuition into the needs of IR examiners.
FOR 572, Network Forensics. I've focused almost exclusively on host-based forensics, and have always thought that network forensics is not well integrated into traditional forensics investigations (especially IR and IP theft scenarios). I did a bit of libpcap network programming in 2002, but there'd be much here that'd be new to me.
FOR 578, Cyber Threat Intelligence. I'm trying to learn much more about threat intelligence and see it as directly applicable to my job. OTOH, the course seems a bit thin; working more hands-on with threat intel data sets would be good practice, but I worry about there being too much focus on jargon (I still am skeptical that "kill chain" means anything that isn't obvious) and on high-level intelligence analysis and techniques (e.g., ACH) and less on tech. It's fine for training classes to address non-technical aspects of a subject, but I personally would get bored and then not get much out of the class.
FOR 610, Malware Analysis. Here's something I don't know much about. But would I be better off taking a more in-depth reverse-engineering course from a different organization? Spending time on little utilities like pescan and pdfid would not be useful to me; fundamental deep dives into PE and ELF, unpacking, reverse engineering, call graph analysis, and so on, definitely would be great.
FOR 498, Battlefield Forensics. I worked on bulk_extractor and a few other MEDEX projects, and a lot of this seems specific to acquiring different devices and whatnot. Probably not for me.
FOR 518, Mac and iOS Forensics. I know a few macOS artifacts and use a Mac as my daily computer, but there'd be a lot here for me to learn.
FOR 585, Smartphone Forensics. I know next to nothing about smartphone forensics. This might be inspiring, as my impression of existing mobile forensics tools has not been favorable.
FOR 526, Memory Forensics. I also know very little about memory forensics. I do have a pretty good sense of how operating systems and the memory hierarchy work. The fact that this covers multiple operating systems and associated techniques is promising, though.

Are there other courses I should look at, including outside of the SANS curricula? Training works best for me when it's very fast-paced and requires hands-on work. Otherwise, my ADD-addled brain will stop paying attention and I'll just daydream.

2020 Goals

2019-12-31T11:13:00.006-05:00

My tech skill development goals for 2020:

Build something useful in Rust, with Rust proficiency as a side-effect
Develop competence with low-level optimization

tooling: nonius, perf, flame graphs, some dtrace/strace
assembly: casual familiarity reading x86, comfort with SSE/AVX and associated libraries
hardware: learn recent microarchitectures (Haswell–) for Intel and AMD, gain empirical expertise with contemporary memory hierarchies including NVMe
libraries: add a few C++ libraries to my trusted working set beyond Boost, focused on addressing particular performance issues (e.g., replacements for std::unordered_map, B-trees, a trie, a Bloom filter lib, etc.)

Do everything with some set of Docker, CloudFormation, Vagrant, and Terraform
Apply some data science/machine learning techniques to real problems
Become dangerously inept with ReactJS and Django as a frontend/backend webapp platform

With the exception of learning how to use ReactJS with Django in order to build a simple webapp, these goals are focused on developing working expertise, building off my strengths in batch processing/backend/systems development. None of these goals involve surface-level reading about new technologies in order to gain conceptual familiarity. I've read about a lot of these technologies for years. It's high time to incorporate them into my daily development activities.

GNU Autotools Grievances

2014-05-30T22:45:00.002-04:00

Part 1, of Infinity

Adding or renaming a source file requires changing Makefile.am, which means you have to run autoreconf again, which generates a new configure script, which you then must re-run, even though nothing about your configuration has changed.
Pulled some changes, now out of date, and you want to run make clean? Have to run ./configure again.
Why, yes, my system has strlen. Thank you for checking. Again. And again. And again.

Is there a sane response to C development on a system without strlen?

NB: Folks running UNICOS don't get to vote.

Every function, header, and library you check for in autoconf results in generating a C/C++ program and compiling, all done through shell script, natch.
The GNU documentation advises against globbing all source files in a given directory for your Makefile and recommends, instead, listing them all individually. Who does this?
Autoconf is really just a bunch of shell macros, which means they introduce new shell variables. So when you see a variable referenced somewhere and you search for it to find where it's set, good luck to you.
libtool! Huh! Good God, y'all... What is it good for? Absolutely nothing!

Seriously, this is a gigantor shell script whose purpose in life, to the best of my understanding, is to supply the right GCC options for building object code for shared libraries, and then linking them together.

That is, it's an enormous shell script middleman to save you the hassle of knowing "-fPIC", "-shared", and ".so". No, really.

20 years ago (maybe even 10; maybe), the platform portability problems libtool was “designed” (a strong word for anything written in shell) to fix might have been an issue. EVERYONE USES LINUX NOW. And those who use FreeBSD still use the same tools.
IT HIDES YOUR EXECUTABLES in .folders and generates shell scripts which you think would be your executables, but aren't, and their sole job in life is to fuxor the PATH and then invoke the hidden executables. Good luck using some debugger other than gcc.

The configure script is not in any way parallelizable. Running it on a wide enough machine can actually make it the slowest part of building.
Want to make a debug build? Rerun configure.
Want to use an alternate compiler on your system? Make sure you pass CC and CXX as variables on the command-line every single time you run configure. (Props to SCons for remembering default choices in its build_variables.py file.)
Have you ever tried reading through the phantasmagoria that is the shell scripts generated by autoconf? It's seriously the inspiration behind Plato's Allegory of the Cave.

System Reconfig

2012-12-02T12:17:00.001-05:00

A year and a half ago, I bought a new system. Meet Virgil:

Virgil's main specs:

2x Xeon E5645 (2.4GHz, 6 cores, 12MB L3, hyperthreading—apiece)
the legendary EVGA SR-2 motherboard
24GB RAM
a pair of WD RE4 2TB hard drives
in a Lian Li PC-V2120 case
all kinds of I/O ports and a ho-hum-but-CUDA-capable GPU

The SR-2 motherboard is a non-standard size and will not fit in a normal ATX case. It necessitated the mondo case. At the time, the SR-2 was about the only desktop board that allowed for dual Xeons (otherwise you needed to buy a true server; blech). A year and a half after purchase, it is still far more computer than I need and I sometimes feel bad considering how much it idles. With its cores at only 2.4GHz, some laptops can beat Virgil at single-threaded tasks, but Virgil excels at parallel compiles, data processing, and the like. With Xeon fans, Virgil sounds like a red-lined Ferrari when its under load.

Operating Systems

I first started off running Ubuntu, which I mostly liked. However, the upgrade to 12.04 failed completely—Virgil could not boot, and I had no interest in trouble-shooting the failure. Additionally, I found Ubuntu's Unity interface a little tiresome. I probably appreciated it more than most Linux users, but it involved a bit more mousing around than I wanted.

A colleague is an expert Fedora user, so I installed Fedora. I figure it'd be worthwhile to learn an alternate approach and I could always piggyback off his knowledge. However, I hated Fedora. Gnome 3 is a disaster, Xfce felt like 1998 all over again, and Fedora demanded far too much sysadmin time from me. I didn't want to re-learn how to setup Samba configuration files again, as if it was still 2002; I wanted to click a checkbox and have my home folder shared so I could access it from VMs without any fuss. This was possible on Ubuntu... not so much on Fedora.

Additionally, I gradually realized that the Fedora installer had messed up my RAID. Under Ubuntu, I'd configured the two drives to act as an LVM RAID-1. When I installed Fedora, it could not recognize the partition, which was hugely annoying, but it did seem to recognize the underlying LVM RAID. I was wrong, though: it turned the RAID-1 into a spanned volume. I no longer had a redundant 2TB drive; I had a 4TB drive with twice the probability of failure as a single drive and no redeeming performance qualities.

Of course, by the time I realized this (disclosure: I am really bad at IT/sysadmin), I'd already accumulated a little over 2TB of data, thanks in large part of VirusShare. It would not be so simple to go back to the RAID-1.

Reconfig

So I bought another 2TB WD RE4 hard drive and a 256GB OCZ Vertex 4 SSD. I had two main goals: first, I wanted to install Mint as the main Linux system and I wanted to do it in such a way that I could trash it, install some other system, and be up and running again in a day or less, without too much time spent sysadmin'ing; second, I wanted a RAID for my main data, and I wanted the volume somewhat separate from /home so I could simply remount it as a subdirectory in my home directory under a new system, perhaps issue a recursive chown & chgrp, and be good to go. (Fedora and Ubuntu use different numbering schemes for UIDs, of course; it should be possible to preserve one's UID from system to system with a little bit of work, but the underlying theme of this blog post is how I am too lazy to do such things).

I first installed the SSD in the system and installed the newly released Mint 14 (with the Cinnamon UI) on a single / partition. I then backed up all of my data to an external 3TB drive, installed the 3rd WD drive, and blew my old data away.

Although the SR-2 board supports various RAID options in hardware, I decided I wanted a software RAID so I could survive a motherboard failure. Virgil has compute power to spare, and these are only 7200 RPM drives so I shouldn't suffer significant performance loss by going the software RAID route. I first constructed an unformatted partition on each of the drives, leaving a small buffer before and after in case I someday need to add another drive that differs slightly in its sector count. I followed the instructions to construct a RAID5 array from the three partitions, according the Linux RAID wiki:

mdadm --create --verbose /dev/md0 --level=5 --devices=3 /dev/sda1 /dev/sdc1 /dev/sdd1

mdadm --detail --scan >> /etc/mdadm/mdadm.conf

This created a 4TB RAID5 across the disks, with a default-selected chunk size of 512KB.

XFS

I narrowed my choices for the filesystem to EXT4 or XFS. Since I have a mix of very large files (evidence and other archives) and very small files (source code), I wanted an extent-based filesystem. Despite its advanced feature-set, reading up on BtrFS does not fill one with confidence about its reliability. Of course, one can find data loss stories about EXT4 and XFS as well. In the end I decided to go with XFS as it is an older design that's been strenuously tested on far more advanced RAID hardware, but it's still under active development and maintenance. This is an intuitive choice more than anything.

So I issued the command:

mkfs -t xfs /dev/md0

and immediately was presented with an error that the 512KB chunk size was too large for XFS. It seems that the default chunk size of 512KB is a recent change in the mdadm tools, likely geared towards EXT4. However, the maximum chunk size that XFS can handle is 256KB and XFS developers still recommend a 32KB chunk size in the general case. So, I deleted the RAID and recreated it:

mdadm --create --verbose /dev/md0 --level=5 --devices=3 /dev/sda1 /dev/sdc1 /dev/sdd1

mdadm --detail --scan >> /etc/mdadm/mdadm.conf

mkfs -t xfs /dev/md0

mount /dev/md0 /mnt/raid

mkdir /mnt/raid/jon/data

ln -s /mnt/raid/jon/data /home/jon/data

I now had my XFS RAID5 and had it easily accessible inside my home directory, while still having the overall volume available for other uses.

One thing I noticed in reading about Linux RAIDs is that many people use LVM on top of the raw RAID device and then create different filesystems on top of LVM. If one were managing a system with a few large RAIDs for a large number of users, I could see how LVM would be useful. However, I cannot see any utility for it when you just want a single RAID volume. There's likely no performance loss to using LVM, but it adds another layer of complexity... and I am too lazy for unnecessary complexity.

The Disposable System

The RAID solves my data problem, but what about being able to get up and running with another system in the future? This enters into the realm of configuration management. There are two new configuration management systems that are taking the open source world by storm, Puppet and Chef. Both are implemented in Ruby and both seem like good pieces of software. They're both geared towards sysadmins who need to manage many systems. Essentially what both do is take configuration files specifying what packages, files, user accounts, and other configuration details should apply to a given system, and then they make the system conform to that description.

The main differentiator between Puppet and Chef is that Puppet has its own syntax for its config files whereas Chef's config files are valid Ruby source code. What I want to do is simply track the packages I install over time, so that I can get them reinstalled quickly if I need to. After looking at the syntax for each of Puppet and Chef, I decided that Puppet would be slightly more simple.

So, what I have been doing is building a directory of Puppet config files, each containing a list of software packages. The config files are roughly categorized, so I have one for basic C/C++ development, another for Python, one for system tools, one for GUI applications, etc. When I find myself in need of a package, I add it to the appropriate config file, and I can then bring my system into compliance with:

sudo puppet apply config-file.pp

Puppet figures out which, if any, packages are missing and then invokes apt-get to download and install them. If I switched back to Fedora, or to FreeBSD or some other crazy system, I would likely need to remap some of these package names slightly, but at least I'm tracking them. Additionally, I will sometimes create an EC2 instance to accomplish a specific task, and having categorized Puppet config files should help me bootstrap barebones instances in short order. I track my config files with git, natch, and mirror them on Github as I do with all my other source code.

Data has mass; I now have a RAID that should be able to survive a move to a different environment without having to make copies. And by using Puppet to reduce system management into, essentially, software development, I have reduced the mass of my operating system to almost nothing. All I need to do on a new system is get it to mount my RAID, drop my ssh keys, install Puppet, and then wait while all the rest of the software I depend on is downloaded and installed automatically.

etckeeper

Speaking of Git, another useful software package for anyone running Linux is etckeeper. etckeeper is a software package that interacts with your package management system and tracks changes to /etc. If you inadvertently screw up some aspect of your system via editing of various /etc config files, you can always go back in time to restore things. In this respect, it's sort of like System Restore, except that it works.
`

Representing Encoding Chains

2012-11-14T09:40:00.001-05:00

Here's a problem I've been mulling over the last couple days: what is a good way to represent encoding chains?

What's an encoding chain?

When we search for text, it's always in some kind of encoding, something that specifies how logical characters are represented as "physical" bytes (a discussion of the physicality of bytes is best left for happy hour). For example, "A" is represented as byte 0x41 in the ANSI or UTF-8 encodings but as the two-byte sequence 0x41 0x00 in UTF-16LE (aka "two-byte Unicode") and UCS-2 (aka "fake two-byte Unicode"; never use UCS-2).

To search for a keyword in a file, we either need to know the encoding used for the file and convert the bytes in the file to logical characters to perform the comparison to the keyword or we need to convert the characters in the keywords into their binary form using the file's encoding and then search for those bytes in the file. Most text editors do the former; Lightgrep does the latter, as we don't usually know the encodings used for files, especially when searching fragments in unallocated space and whatnot.

An encoding chain goes beyond a single encoding: it's what happens when we want to deal with data that's been subject to a series of transformations, including a normal characters-to-bytes encoding.

Examples

A useful artifact in forensics is the UserAssist registry key. These keys store recently run programs, recording the name of the program, when it was last run, and the number of times it was run. A bewildering aspect of values under the UserAssist key is that the names of the programs are ROT13 "encrypted". This means that "A" becomes "N", "B" becomes "O", and so on.

ROT13 seems like a silly form of obfuscation... until you need to search for UserAssist registry keys pertaining to a particular program. Many forensic tools will parse registry hives and some will even decrypt the UserAssist keys for you, but if you'd like to look for traces of keys in the pagefile or in unallocated, you are out of luck when it comes to tool support. You must manually apply ROT13 to the name of the program ("notepad" becomes "abgrcnq") and then apply the UTF-16LE encoding to it ("abgrcnq" becomes "a\x00b\x00g\x00r\x00c\x00n\x00q\x00"). Tedious, no?

Another example (featuring more love for Didier Stevens) is when looking for obfuscated strings in malware. XORSearch is a program Messrs. Stevens recently released which lets you search for strings that have been obfuscated with XOR, ROR (rotate-right), or ROL (rotate-left) transformations. These types of transforms are often used by malware authors to obfuscate strings like URLs.

When searching, it would be very nice to say "look for 'notepad' but in ROT13'd UTF-16LE" or "look for 'http://sirhaxal0t.ru/' in UTF-8 that's been XOR'ed". The permutation of "ROT13, then UTF-16LE" or "UTF-8, then XOR" is what I mean when I say "encoding chain." We want to apply a chain of encodings to our search terms.

Characters v. Bytes

ROT13 is a transformation that applies to characters, with "A" becoming "N" and so on. In contrast, XOR is a transformation that applies to bytes. Character transforms apply to the string first before it's encoded into bytes, whereas byte transforms apply to the bytes after the encoding has happened. Here's a table that clearly delineates transformations and encodings:

Character Transforms	Encodings	Byte Transforms
ROT13, URL encoding, HTML entities	ASCII, UTF-8, UTF-16LE, EBCDIC, Shift-JIS, ISO-8859-5, etc.	XOR, ROR, ROL, Outlook Compressible Encryption, Base64

You may have noticed that there are a few constraints to the encoding chains we'd like to apply. First, there's an ordering constraint in that character transforms must come first, followed by the encoding, and finally by byte transforms. An encoding chain like "XOR -> ROT13 -> UTF-8" is invalid and nonsensical. Second, while it's possible to have multiple character transforms or byte transforms in a chain, there can be only one encoding. An encoding changes the type of thing we're working with from characters (ideally Unicode codepoints) to bytes, and that type change can only occur once.

The Ultimate Problem

We've been working on adding support for Outlook Compressible Encryption to Lightgrep, and that's necessitated thinking about encoding chains and how to expose the abstraction. At this point the main technical work is done and we are arguing about how to represent the encoding chains.

Whither:

"outlook(base64(utf8(rot13())))"

or

"ROT13 | UTF-8 | Base64 | Outlook"

or

"ROT13 > UTF-8 > Base64 > Outlook"

?

We'd like to have a good notation for specifying these chains. One interesting thing to note is that some transformations may want parameters. For example, ROR and ROL need to know how many bits of shift to apply. It would be silly to have ROR1, ROR2, ROR3, ROR4, ROR5, ROR6, and ROR7, when we could just have "ROR(2)", for example. With parameters, we could come up with a generic rotate character transformation, and then ROT13 would be "ROT(13)". (If you were investigating a classically trained hacker, you may want to look for text obfuscated by the Caesar cipher, i.e., ROT(3).)

So...

...which representation above do you prefer? Or can you come up with something better?

* Addendum *

You can expect Outlook Compressible Encryption support in Lightgrep fairly soon, but it will be some time before you see base64. Base64 is not so much a byte transformation as it is a bit transformation, taking 6 bits of data and turning them into 8. Lightgrep needs some work in order to work well with bits.

Forensic Programming Rules of Thumb

2012-09-17T10:46:00.003-04:00

I have a set of mental guidelines I use when writing digital forensics programs, and it's high time I write them down. These are by no means a complete list of useful programming techniques, but I think they're all worth keeping in mind.

Algorithms

1. Don't be afraid to use RAM. Most investigators' machines have several gigabytes of RAM installed, so you might as well use it.

2. Remember, though, that RAM is fixed while disk space is nearly infinite. If you can't set an upper limit on the amount of RAM used by your program, create a cache data structure, size it appropriately, then spill to disk if you exceed it.

3. Prefer streaming models to building up complex data structures in RAM. Streaming models will generally use a fixed amount of memory and scale to large evidence sets.

4. Choose algorithms based on the best worst-case behavior, rather than the best average-case. Investigators don't need the best possible performance from their software as much as they need predictable performance, and the ability for the software to cope when faced with The Big One. An algorithm that has bad worst-case performance is not mission capable.

Timestamps

1. Convert local time to UTC as soon as possible.

2. Always report timestamps in UTC. I'm generally not a fan of programmers telling users what to do, but I'll make an exception in this case; when users ask for local time output, firmly reply "no" and tell them to get comfortable working in UTC.

3. Do not separate times from dates in output. Timestamps are points in time; separating times from dates imposes the periodicity of the earth's revolution onto your investigation, and that's often not germane. Even if it is germane, having dates and times separated makes it a huge PITA to calculate timestamp differences in, e.g., Excel.

4. Timestamps generally exist within a "context," for lack of a better word. Contexts are often cascading/recursive. For example, the context for an OLE timestamp with a Word 2003 document is "Word 2003 OLE", followed by the filesystem (e.g. UTC for NTFS, local time adjustment for FAT32), followed by the system time settings, followed by, say, the timezone of where the evidence was seized. It's important to remember these contexts when handling local time. Even if you convert local time to UTC, one of these contexts could later be found to be incorrect. Consider the timestamps as existing in a database; it would be better to query for the appropriate rows to adjust by this context then through some ad hoc mechanism.

Artifacts

1. Never assume anything about your input. Ooh, you found a magic header for your artifact? So what!? The data could have been generated by a cuckoo clock. Sanity check everything, especially when reading in variable length buffers/strings with sizes denoted in other fields. Return true or false depending on whether the artifact parsed successfully. If it mostly parsed but failed some kind of test, return the partial results along with false.

2. Keep your artifact parsing code separate from your I/O code (if possible; better to operate on provided memory buffers and let other code feed it data) and separate from your reporting code. This way you can foster code reuse when someone else needs to parse the same artifact but in a different context.

3. Put the immediate results from parsing into a struct or, perhaps better, a name-value data structure, such as a Python dict. Don't serialize into a string or otherwise obliterate the type information you have at that moment; that's for your output code to handle. Again, this fosters code reuse.

4. Always refer to bytes on disk. When you output parsed artifacts, always give the user reference to where that artifact existed on disk. This way the user has a chance in hell of finding it for themselves and validating that your software parsed it correctly.

5. Remember that parsing is not the same thing as analysis. The output from parsing an artifact should be in a form that makes it convenient for the examiner to analyze. This could mean, for example, that it's easy to get the output into Excel or Access or pipe it into different command-line utilities. It's way better to produce output that is well-structured than pretty—well-structured data can always be prettied up, while it's often hard to recreate structure from pretty data.

6. It's better to identify an artifact by searching for it than by assuming it exists within a well-structured file. If you can identify artifacts by searching, then you can parse them out of RAM dumps, virtual memory swapfiles, and unallocated space.

Happy Birthday, Mr. Pigeon

2012-08-24T17:18:00.001-04:00

Yesterday, I asked a question on Twitter:

Alright lazy web, yes or no: can I use md5() for lazy man's equality testing of strings ranging from 3 bytes to 3GB?
— Jon Stewart (@codeslack) August 23, 2012

I will admit, at the time I was hoping that one of the respondents would be Jesse Kornblum. I was not disappointed. There was a little back on forth on twitter, and then Jesse decided to write a blog post, "Being Unreasonable About MD5." In it, he advised me to use a SHA-2-based hash, or wait until SHA-3 is determined.

DFIR Slugfest!

It being 2012, we should all know that MD5 is "broken." The first MD5 collision was announced in 2004 (some analysis [PDF]). The ability to generate collisions since then has only gotten better. Earlier this summer we were treated to the sheer awesomeness of Flame exploiting an MD5 collision which could not have been generated based on publicly known techniques (*cough* USA!, USA! *cough*).

Here's the problem, though: I'm looking for a hash function that I can use for lazy equality comparisons, not for use in digital signatures. That is, I want to see whether a new string of input I've read in from a program is the same as a previous string of input I've read in.

Why do I want to do this? Well, I want to grep hard drives for email addresses and spit out a list of all the unique ones I've seen. I also want to do this with web addresses/URLs, credit card numbers, Social Security Numbers, and so on. One possible way of doing this (a really lazy way, and it might not even be the best way; that's a separate story altogether) is to hash all the email addresses with MD5 and call it a day. MD5 will surely work for this, won't it?

...

In 1834, Johann Dirichlet postulated what has come to be known as the Pigeonhole Principle. It is one of those theorems in mathematics where the proof of it is simply common sense: if you have n pigeonholes, and n+1 pigeons, you're guaranteed to have 2 pigeons shacking up.

MD5 is a 128 bit hash algorithm. Thus, it has 2^128 different pigeonholes. According to the pigeonhole principle, we need to have (2^128) + 1 items before we're guaranteed to have a collision.

In case you're wondering, 2^128 = 340,282,366,920,938,463,463,374,607,431,768,211,456. There certainly aren't that many unique email addresses we're ever going to encounter, so we should be good right?

Well, actually, let's take a moment to guess how many unique email addresses there are. I don't have a central repository of all the email addresses ever used, but I can use myself as an example and estimate out from there. Here are all the email addresses I can remember having:

(I don't remember the first one, but it was @nebbs.nersc.gov on a Cray X-MP, which was rad.)
beefstew@aol.com (yes, really)
stew1@iastate.edu
stew1@avalon.net
jonathan.l.stewart@uiowa.edu
jstewart@cs.uiowa.edu
stew1@ellipsis.cx
jonathan_l_stewart@hotmail.com
jonathan_l_stewart@yahoo.com
jonathan.l.stewart@gmail.com
jonathan.l.stewart@acm.org
jonstewart17@comcast.net (DIAF, Comcast)
jon@lightboxtechnologies.com

Lucky number 13. Of course, I may have used a few burner email addresses over the years and there could be a couple of legitimate ones I've forgotten, too. So, let's round that up to 50, just for sake of argument.

Also, let's assume that I'm the most average person on Earth. How many people are there? Supposedly 7.035 billion, as of today, August 24, 2012. Extrapolating out, we could be dealing with 351 billion email addresses, if every single person on the planet has had 50 email addresses. However, there are almost certainly email addresses that are associated with computers and departments and mailing lists and such, not just people. So, well, let's double that: 702 billion email addresses. That's our estimated population.

Right off the bat, we can see that those clinging to 32-bit integers are going to need a bigger boat. If I happened to have a hard drive with all the email addresses on it and I was using a 32-bit hash, the pigeonhole principle tells me I'd have a lot of collisions.

Still, though, MD5 only has to deal with 702,000,000,000 email addresses and fit the hashes from our email addresses into 340,282,366,920,938,463,463,374,607,431,768,211,456 possible values. Continuing along the primrose path of overly simplistic math, this means we should have a probability of 702 billion/2^128, which is 2.062992585693e-27, or 1 chance in 2.06 octillion. That's a lot of room for MD5 to play in.

Nyet so fast, Komrade!

However, thus far I've failed to take into account the Birthday Paradox. Have you ever been in a group of people and been surprised to find that two of them have the same birthday? As it turns out, odds are even that two guests at a 23-person dinner party will have the same birthday and 99% that two people in a group of just 57 will have the same birthday. This is because we are comparing pairs of birthdays to each other, each person trying to pair themselves to all the rest. The number of pairs of n things is (n*(n-1))/2. As people start piling up, so do the combinations and the number of days in a year are quickly overwhelmed.

The Birthday Paradox leads to the Birthday Attack: start testing for collisions by brute force and, over time, you will get lucky and have a pair collide. The number of items we have to test, Q, before finding the first collision in a fair hash function is roughly equal to the square root of (pi * H)/2, where H is the total number of available pigeonholes. For MD5, H=2^128 and thus Q = sqrt((3.1415926 * 2^128)/2). What is that number?

It's ~23,119,565,135,021,060,000. That is, 23 quintillion. That number, while large, is a lot smaller than 340,282,366,920,938,463,463,374,607,431,768,211,456. That's the number of strings we have to hash before we have close to a 100% chance of having a hash collision on MD5. What about a 1% chance? Well, fortunately, Wikipedia calculated that number in the table that you see under the Birthday Attack article. For a fair hash with 128 bits, if we try hashing a tenth of that many items, the probability we'll have a collision is 1 in 100. If we generate ~820,000,000,000,000 strings (820 trillion), the chance we'll have a collision is 1 in a billion. If we generate 1000 times fewer strings, ~820,000,000,000 (820 billion), the chance we'll have a collision is 1 in a quadrillion.

820 billion is pretty close to the 702 billion distinct email addresses we estimated above. So, if MD5 is fair, we can expect we have about a 1 in quadrillion chance that we'll have a collision.

Have you noticed how fast and loose I've played with the math here? And how much I've relied on Wikipedia? Disclaimer: I am really bad at math. When trying to figure out math like this, I generally reserve the right to be off by a factor of 1000. Therefore, you only get to correct me if you can show that I'm off by more than a factor of 1000.

Additionally, all these numbers above assume that MD5 is perfectly fair. In fact, we know that it isn't, because of the collision attacks. If I reserve the right to be off by a factor of 1000 and we know that MD5 is also kind of caput, that means we need to estimate our probability to be somewhat higher. So, one in a trillion? One in 100 billion? Maybe a little less?

Now we're in judgment call territory. For my application of deduping email addresses, well, meh. I'll certainly take the odds of a collision when hashing all of the email addresses ever at one in quadrillion, and even at one in a trillion. The nice thing about using MD5 for this is that it's reasonably fast (Xeons even have a special instruction for calculating MD5 on the chip) and the keys will fit in 16 bytes, the size of an SSE2 register.

However, what about all possible files? Are there more possible files than email addresses? Probably. What about all distinct 512-byte sectors, for those who like sector block hashing? Almost certainly. Are we starting to bump up into limits where we have to think about whether it's safe or not? Yes. Is that a bad thing? Yes. Like Rocky, we do not want to think, we do not want the judge to think, we do not want the jury to think; we want to win.

So, unless you want to think about all these things above, including whether you want to explain one in a trillion, then you should stop using MD5.

Although, to keep things in perspective, the risk of everyone dying next year due to a comet or asteroid strike is only 1 in 20,000.

...

Ok. Now you may correct my shoddy math in the comments.

Random Sampling in Forensics

2012-08-11T21:19:00.000-04:00

(NB: Some links are to PDFs.)

I had the pleasure of attending the Digital Forensics Research Workshop this past week. DFRWS is different than the other forensics conferences I've attended, in that speakers must submit formal academic papers for review by a committee. Less than one-third of submitted papers make the cut.

This is how most academic conferences work, and there are a few consequences stemming from the emphasis on peer-reviewed papers. One is that the quality of the material is generally high. This is good. Another is that many leading practitioners—who, as forensics generally demands, also double as researchers—don't present, since writing a formal academic paper is an enormous PITA. This is less good.

I enjoyed a number of presentations at DFRWS this year (chief among them was Ralf Brown's about language identification). The one that stood out for me, though, was a blend of theory and practice. This was The Use of Random Sampling in Investigations Involving Child Abuse Material, presented by Mike Wilkinson and co-authored by Brian Jones and Syd Pleno.

What Mike, Brian, and Syd did is, frankly, revolutionary. They established procedures at the New South Wales police force's State Electronic Evidence Branch so that child pornography possession cases make use of statistical sampling early in the analysis of the case. By using sampling, they have cut their case backlog from 3+ months to zero.

By using an EnScript that selects a random sample of images from suspects' hard drives, investigators can estimate the total amount of child pornography on the system with a high degree of confidence. A report based on the sampling review is created and, while situations no doubt vary, the report is typically presented to the suspect along with a plea bargain... and most take the plea. Such cases take only a few hours of processing.

Of course, such a methodology is only appropriate for possession cases, not distribution or where active child abuse is suspected. Digital investigators benefit because they don't have to sit for hours reviewing thousands (or millions) of corrosive images, and they have more time for other cases. Other investigators benefit because their computer evidence gets turned around faster. Even the falsely accused benefit, because they are quickly exonerated.

Part of why the procedure works is because it's well-adapted to the law in New South Wales, Australia. However, with care and consideration, it is hard to believe that the basic idea could not be applied in the United States.

I encourage you to read their paper and review their presentation. Kudos to Brian, Syd, and Mike, and to the New South Wales police for adapting to the increasing strain on digital investigators with an elegant and effective solution.

Lightgrep 1.0

2012-06-14T11:37:00.000-04:00

I've just released Lightgrep for EnCase 1.0. Lightgrep is a new multipattern regular expression search engine that I've been developing with my colleagues over the last two years, and our EnCase integration makes it the fastest way to conduct searches over digital evidence.

I'm hoping I'll be writing more blogposts now, as I allow my mind to wander a bit more.

Lightgrep for EnCase at CEIC 2012

2012-05-19T09:53:00.000-04:00

I'll be at CEIC 2012 next week, arriving Monday and leaving mid-morning on Thursday. Geoff Black and I will be talking again about the use of statistical sampling in eDiscovery matters, based on a matter we worked on in which the Hon. Andrew J. Peck was the presiding judge. Our talk is at 4:30pm on Monday.

We are also putting the finishing touches on Lightgrep for EnCase and we'd love to show it to folks attending CEIC. Lightgrep is a new regular expression search engine we wrote, that searches evidence for many keywords very quickly. We've created an EnScript wrapper around the low-level search engine that allows you to use it instead of EnCase's own keyword search facility. It will bookmark search hits and create an Excel report with details about the search, in addition to several other features.

Lightgrep shines when you have many keywords or need more advanced grep functionality than EnCase provides. Last year we had some investigators use an early version on a case with over a million keywords, so we think it sets a new standard for scalability. Lightgrep also supports more grep features, and we try to make them work as close to Perl as possible. We don't have all of Perl's functionality just yet, but we'll keep adding more grep operators over time (and we do a lot of testing to make sure we get the same hits Perl does).

Unicode support is what we've been working on most recently, and I'm pretty excited about it. Out of the gate, we'll have support for ASCII (really, Windows code page 1252), UTF-8, UTF-16LE (two-byte Unicode on Windows), UTF-16BE, and UTF-32LE and BE. We are able to look for every character in the Unicode standard, including brand new ones in Unicode version 6.1.0, like the infamous U+1F4A9. We won't support other code pages just yet, but the code is mostly developed and we simply need our test suites to catch up.

The cool thing about Lightgrep's Unicode support is that you can use Unicode properties in patterns. You can specify \p{Digit} or \p{Letter} and look for only valid digits or letters, but in any language. You can also specify different scripts, which is amazingly useful when looking for text that's not in the Latin alphabet. For example, \p{Cyrillic}+ and \p{Arabic}+ will find all words in Cyrillic (i.e., Russian) and Arabic, respectively.

If you'd like to see Lightgrep in action at CEIC, just email me, at jon@lightboxtechnologies.com, and we'll find a good time to chat. I'll have a few dozen thumb drives with a Lightgrep trial version installer, so don't be shy.

Differential EnScript

2012-03-22T17:38:00.000-04:00

My former colleague Jamie Levy released a new EnScript today, for doing differential analysis of hard drives. You should check it out.

Don't call virtual functions in a destructor

2012-03-21T09:39:00.000-04:00

Sometimes I like to define the outline of an operation in a base class and then have it delegate to virtual functions in derived classes. This is the Template Method design pattern.

class Base {
uint Counter;

void foo() {
++Counter;
_foo();
}

pure void _foo();
}

class Derived {
virtual void _foo() {
Console.WriteLine("In Derived::_foo");
}
}

Last night I tried to gin up a sort of "stack guard," something that would let me perform an operation once I got to a certain point in a function, but which also would be executed if the function returned early. When something needs to be done at the end of a block of code, I usually define a new class that has code in its destructor. For example, a lock class could take a critical section and acquire it in its constructor and release it in its destructor, and you just need to create the object in the appropriate place to perform your thread-safe operation. I wanted the same thing, but just a bit more complex, where I could call the release function manually once I'd reached a certain point and then be assured it would not be called in the destructor.

class Committer {
bool Committed;

~Committer() {
if (!Committed) {
commit();
}
}

void commit() {
_commit();
}

pure void _commit();
}

class SafeDB: Committer {
SafeDB(Database db): Committer() {
// open a database connection
}

virtual void _commit() {
// commit any pending transactions
}
}

Simple enough. You can quibble about whether it's really worth it to define a class hierarchy for such simple functionality, but I've been trying hard to increase the amount of abstraction I use in EnScript to reduce code bloat and time wasted debugging.

The problem is that this doesn't work and generates run-time errors about null references. Why?

Answer: SafeDB's destructor is called first, and then Committer's destructor is called. As part of executing SafeDB's destructor, it nulls out whatever class members are a part of SafeDB before calling Committer's destructor. Hence, by the time you get to Committer's destructor, you really only have a Committer object, not a SafeDB object. The virtual table is still active, however, so the call to SafeDB::_commit() happens successfully, but it finds itself confronted with no class variables. Boom!

So, this is now another little corner of the EnScript world that's been explored. Time to light out for the territory...

ThreadClass::WAITSAFE

2012-01-31T14:40:00.001-05:00

A New Year's Resolution, if you can call it that, is to blog more in the moment, as I'm figuring stuff out. I think I just figured out how the ThreadClass::WAITSAFE option works, so here goes...

ThreadClass::WAITSAFE is an enum value under ThreadClass::WaitOptions. It can be passed to several of the different Wait() methods related to the threading classes. The gloss on it says "Exits early if thread stops running," but there aren't any examples that show it in action and it seems to be the default parameter for some of the Wait() methods, but not for all of them. Specifically, it's not the default parameter for either of the ThreadClass::WaitClass methods.

To test it, we're going to have three threads. One is just going to spin its wheels—it's the thread we'd have doing real work, so we'll call it the "doer." Another thread will launch the doer and wait for it to finish, which we'll call the "waiter." This seems kind of silly, except that in a real application, the waiter could have a pool of doer threads, and could be coordinating their work and that may justify a separate thread of its own (especially if it's happening while you have a dialog up). Finally, we'll have our main thread that creates and launches the waiter, sleeps for a bit, then tells it to cancel. The waiter in turn will cancel the doer thread, and exit once the doer has exited. Here's the code:

class Doer: ThreadClass {

  Doer(): ThreadClass() {}

  virtual void Run() {

    while (IsRunning()) {

      Console.WriteLine("Doer sleeping...");

      SystemClass::Sleep(1000);

    }

    Console.WriteLine("Doer exiting.");

  }

}

class Waiter: ThreadClass {

  Waiter(): ThreadClass() {}

  virtual void Run() {

    Doer d();

    ThreadClass::WaitClass w();

    Console.WriteLine("Starting doer...");

    d.Start();

    w.AddObject(d);

    Console.WriteLine("Waiting on doer...");

    bool waitRet = w.WaitAll();

    Console.WriteLine("Woke up waiter");

    if (!IsRunning()) {

      Console.WriteLine("Waiter was cancelled. Stopping doer...");

      d.StopRunning();

      d.Wait();

    }

    Console.WriteLine("Waiter exiting, waitRet = " + waitRet);

  }

}

class MainClass {

  void Main() {

    SystemClass::ClearConsole();

    Waiter t();

    Console.WriteLine("Starting waiter...");

    t.Start();

    Console.WriteLine("Sleeping for 10 seconds");

    SystemClass::Sleep(10000);

    Console.WriteLine("Cancelling waiter...");

    t.StopRunning();

    Console.WriteLine("Waiting for waiter to quit...");

    t.Wait();

    Console.WriteLine("Waiter returned successfully. Done.");

  }

}

This code produces the following output:

Starting waiter...

Sleeping for 10 seconds

Starting doer...

Waiting on doer...

Doer sleeping...

Doer sleeping...

Doer sleeping...

Doer sleeping...

Doer sleeping...

Doer sleeping...

Doer sleeping...

Doer sleeping...

Doer sleeping...

Doer sleeping...

Doer sleeping...

Cancelling waiter...

Waiting for waiter to quit...

Doer sleeping...

Doer sleeping...

Doer sleeping...

Doer sleeping...

Doer sleeping...

Doer sleeping...

Doer sleeping...

Doer sleeping...

Doer sleeping...

Doer sleeping...

Doer sleeping...

...

The problem is that this script never terminates successfully. The Waiter class uses WaitAll() to wait for the Doer thread to finish, but the Doer thread is just hanging out, enjoying its infinite loop until someone calls StopRunning() on it... which never happens. This is where ThreadClass::WAITSAFE comes in. Here's some modified code:

class Doer: ThreadClass {

  Doer(): ThreadClass() {}

  virtual void Run() {

    while (IsRunning()) {

      Console.WriteLine("Doer sleeping...");

      SystemClass::Sleep(1000);

    }

    Console.WriteLine("Doer exiting.");

  }

}

class Waiter: ThreadClass {

  Waiter(): ThreadClass() {}

  virtual void Run() {

    Doer d();

    ThreadClass::WaitClass w();

    Console.WriteLine("Starting doer...");

    d.Start();

    w.AddObject(d);

    Console.WriteLine("Waiting on doer...");

    bool waitRet = w.WaitAll(ThreadClass::INFINITE, ThreadClass::WAITSAFE);

    Console.WriteLine("Woke up waiter");

    if (!IsRunning()) {

      Console.WriteLine("Waiter was cancelled. Stopping doer...");

      d.StopRunning();

      d.Wait();

    }

    Console.WriteLine("Waiter exiting, waitRet = " + waitRet);

  }

}

class MainClass {

  void Main() {

    SystemClass::ClearConsole();

    Waiter t();

    Console.WriteLine("Starting waiter...");

    t.Start();

    Console.WriteLine("Sleeping for 10 seconds");

    SystemClass::Sleep(10000);

    Console.WriteLine("Cancelling waiter...");

    t.StopRunning();

    Console.WriteLine("Waiting for waiter to quit...");

    t.Wait();

    Console.WriteLine("Waiter returned successfully. Done.");

  }

}

This time, we pass ThreadClass::INFINITE (the default) and ThreadClass::WAITSAFE (not the default) as parameters to the WaitAll() method in the Waiter. This is what we get for output:

Starting waiter...

Sleeping for 10 seconds

Starting doer...

Waiting on doer...

Doer sleeping...

Doer sleeping...

Doer sleeping...

Doer sleeping...

Doer sleeping...

Doer sleeping...

Doer sleeping...

Doer sleeping...

Doer sleeping...

Doer sleeping...

Doer sleeping...

Cancelling waiter...

Waiting for waiter to quit...

Doer sleeping...

Woke up waiter

Waiter was cancelled. Stopping doer...

Doer exiting.

Waiter exiting, waitRet = 0

Waiter returned successfully. Done.

Huzzah! Calling StopRunning() in the main thread on the waiter causes the waiter to wake up from WakeAll(), now that we're using ThreadClass::WAITSAFE. Once the Waiter wakes up, it checks IsRunning() to check whether it's been given the signal to quit, via StopRunning(), and then does likewise with the Doer thread. The Doer exits gracefully, then the Waiter exits gracefully, and then the whole script exists. Quite nice.

Notice that we've output the return value from WaitAll(), and it seems to have been false in this case. The question this raises is, would it return true if Doer exited before Waiter was cancelled with StopRunning()? Here's some modified code where the Doer exits after about 5 seconds, while the main thread still waits about 10 seconds to tell the Waiter to stop.

class Doer: ThreadClass {

  Doer(): ThreadClass() {}

  virtual void Run() {

    uint i;

    while (IsRunning() && i++ < 5) {

      Console.WriteLine("Doer sleeping...");

      SystemClass::Sleep(1000);

    }

    Console.WriteLine("Doer exiting.");

  }

}

class Waiter: ThreadClass {

  Waiter(): ThreadClass() {}

  virtual void Run() {

    Doer d();

    ThreadClass::WaitClass w();

    Console.WriteLine("Starting doer...");

    d.Start();

    w.AddObject(d);

    Console.WriteLine("Waiting on doer...");

    bool waitRet = w.WaitAll(ThreadClass::INFINITE, ThreadClass::WAITSAFE);

    Console.WriteLine("Woke up waiter");

    if (!IsRunning()) {

      Console.WriteLine("Waiter was cancelled. Stopping doer...");

      d.StopRunning();

      d.Wait();

    }

    Console.WriteLine("Waiter exiting, waitRet = " + waitRet);

  }

}

class MainClass {

  void Main() {

    SystemClass::ClearConsole();

    Waiter t();

    Console.WriteLine("Starting waiter...");

    t.Start();

    Console.WriteLine("Sleeping for 10 seconds");

    SystemClass::Sleep(10000);

    Console.WriteLine("Cancelling waiter...");

    t.StopRunning();

    Console.WriteLine("Waiting for waiter to quit...");

    t.Wait();

    Console.WriteLine("Waiter returned successfully. Done.");

  }

}

And here's the output:

Starting waiter...

Sleeping for 10 seconds

Starting doer...

Waiting on doer...

Doer sleeping...

Doer sleeping...

Doer sleeping...

Doer sleeping...

Doer sleeping...

Doer exiting.

Woke up waiter

Waiter exiting, waitRet = 1

Cancelling waiter...

Waiting for waiter to quit...

Waiter returned successfully. Done.

So, as you can see, WaitAll() still returns when the Doer thread exits, and this time it returns true. Waiter then exits from its Run() function before the main thread has the chance to cancel it. The upshot is that we can use the return value from WaitAll() to tell whether the thread waiting has had StopRunning() called on it (return value is false) or whether simply the operations it's waiting on have completed (return value is true).

Oh frabjous day, everything works!

SANS 360 Lightning Talk

2011-12-14T17:07:00.003-05:00

I've published a write-up on the Lightbox blog of my SANS 360 talk, "Factory Forensics." You could watch the video, of course, but then you'd have to suffer through my stumbling and general awkwardness. The turnout was great, and I was humbled by the quality of the speakers.

ExecuteClass pitfall

2011-08-09T23:34:00.000-04:00

Of the ways that EnScript can interact with other programs, using ExecuteClass to launch programs from the command-line is probably my favorite. It's simple to use, simple to debug, and doesn't leave you with an unholy mess of code, like COM. However, I recently ran into a pitfall with ExecuteClass and hopefully sharing it here will keep others from running into it or, at least, recognizing it when they're at their wits' end.

The problem? ExecuteClass becomes angry when the target program writes a lot of data to stdout or stderr, and you wouldn't like ExecuteClass when it's angry.

ExecuteClass currently has the Output property, a String, for giving you back stdout output from the application. My somewhat shaky belief is that this is updated once the application has ended—I haven't tested this in a while, though. Additionally, notice that there's no property representing stderr.

If the target application you are running generates lots of output to stdout or to stderr, you will find that the application will hang after a while. Why? Well, in the words of the illustrious Beej, "On many systems, pipes will fill up after you write about 10K to them without reading anything out." Once the target application fills up whatever pipe EnCase has connected to stdout or stderr, it will block on the next write to the stream... and EnCase will never consume from the pipe, causing the target application to hang indefinitely.

One possible workaround to this is not to call your target application, but to call cmd.exe instead, with the argument being the command you want to run, redirecting output to a file. I haven't yet tested this, but it should work. The other, of course, is to change the target application to write output to a file itself. As for the underlying win32 calls involved, I found an MSDN article with a sample program demonstrating how child processes are created and how to read data from stdout and stderr.

DFRWS 2011

2011-08-05T11:37:00.002-04:00

I spent this last week in New Orleans at the Digital Forensic Research Workshop. DFRWS is primarily a research workshop for academics, to which they can submit formal papers for acceptance by peer review and then eventual publication. Folks whose papers are accepted then give presentations about their work.

Highlights

Vassil Roussev presented on the work he's done on fuzzy hashing, comparing his sdhash tool to Jesse Kornblum's venerable ssdeep in an information retrieval-type experiment. In general, sdhash does a significantly better job of identifying similar files, with the main trade-off being that hash values are not fixed-length (I haven't played with sdhash enough to know whether performance is a significant factor, either). Fuzzy hashing is a great example of applying computer science theory to forensics. More of this, please. (pdf)
Robert Beverly presented on work at the Naval Postgraduate School in finding artifacts of common structures used by programmers in networking code. It turns out that these ephemeral structures in RAM can often be found on disk (pagefile/hiberfil/unallocated), allowing the astute investigator to construct a partial remembrance of networks past. (pdf)
Michael Cohen of PyFlag fame presented on GRR. GRR stands for "GRR Rapid Response", but you can probably substitute "Google" for the G if you'd like to avoid the left-recursion. GRR is an open source tool for collecting and analyzing data from remote machines on an enterprise network, created for internal investigations at Google. It is the closest thing I've seen to my old friend ESAC, and built on a far-richer software stack. It's early days, but I'll be following development of GRR very closely and I recommend that you do as well (it's much cheaper to buy Cory a beer than to buy your overly-friendly enterprise software salesperson a new Ferrari). The one aspect of GRR I'm leery of is the use of AFF's RDF-based data model, because I think RDF is a bit abstruse for most problems in forensics (or, at least, doesn't have the pay-off you'd like in return for learning RDF, a technology only semioticians could love). (pdf)
Clay Shields presented on some work he's done using, essentially, document indexing for supporting enterprise investigations. By creating bag-of-word style feature vectors for documents on hosts, he can perform offline queries to help discover machines involved in an investigation. Indexing and the bag-of-words do have a host of problems that require careful consideration, but this would no doubt be a useful technique for many investigations. I'd love to see such functionality put into GRR. (pdf)
Christopher King and Tim Vidas from Carnegie Mellon presented on some aspects of Solid State Disks. This is a paper everyone should read carefully once it's been posted. (pdf)
James Okolica and Gilbert Peterson figured out how to find and extract data from the Windows clipboard in RAM images. (pdf)
Judson Powers from ATC-NY gave lightning talks both on MacOS X Lion's new full disk "encryption" (the quotes are needed, my fellow Mac weenie brethren) and Dropbox artifacts.
Last but certainly not least, Ralf Brown talked about his ZipRec tool, which is able to find and recover data from corrupt DEFLATE streams (i.e., from zip files and many other compressed formats). It'll be very interesting to see how this tool develops and what other topics in forensics Ralf turns to. (pdf)

Format

Not being an academic, I find these sorts of conferences kinda' weird. Their primary purpose is to provide a forum for academic researchers to present their work. I don't have skin in that game, and there were, frankly, some pretty boring moments for me... and, in the case of the legal panel, some pretty boring moments for everyone (a panel of class action plaintiffs attorneys, replete with hair product and suits, for an audience of bits-and-bytes forensics researchers is an odd pairing; the caliber of the audience demands the likes of Craig Ball, Ralph Losey, Jason Baron, or other folks capable of engaging with the best forensics researchers; throwing a prosecutor into the mix would be good, too).

While my ADD-addled brain would like a more-compressed, faster-paced format (can someone organize a conference consisting of forensics lightning talks? that'd be great), DFRWS is the place to be to learn about the future of forensics. Most folks there are working on substantive problems and I had some great conversations with various researchers throughout the conference. I definitely need to start planning now so I can submit a paper or two for next year and participate a bit more actively. DEFCON and Black Hat may get the press, and DFRWS probably missed out on a few practitioners in attendance because of the scheduling conflict, but I think DFRWS is the best mash up of computer science and digital forensics I've yet seen.

The Fail Whale

Finally, an expedition was organized to The Beach, a bar on Bourbon Street that has a mechanical killer whale (instead of a mechanical bull). Life's not all about hex, code, and catching bad guys; it's also about taming wild beasts.

EnCase 7: First Impressions

2011-05-22T23:04:00.000-04:00

I was able to play with EnCase Version 7 for the first time this past week at CEIC (which was a great conference, btw). It will take me some time to explore v7 fully and make definite conclusions about much of its functionality. Additionally, just as restaurant reviewers don't visit a new restaurant until its had some time to find its rhythm, formally reviewing v7 seems pointless until 7.02 or 7.03. Still, I do have some immediate impressions.

What I Love

Tabs. EnCase now just has a single row of tabbed windows along the top. Bookmarks? That's a tab. Search results? That's a tab. The familiar tree-table view is then contained within the tab. I've heard some griping that the user interface has changed too much, but the tabs are a break-through and I'll tell you why: your windows stay as you left them.

In previous versions of EnCase, which type of data you were looking at (entries, records, etc.) and the way you looked at data (table, report, gallery, timeline) were global settings. So if you wanted to go from the table view in Entries to the report view in Bookmarks, you had to switch views as well as the tab. Not only is it now far easier to navigate between different windows, but also the individual display settings and contexts for those windows are maintained. I took to this change like a fish to water, and I believe daily users will find it far more effective. Kudos to GSI for rethinking one of the fundamental aspects of the EnCase look-and-feel and pulling it off splendidly.

The EnScript Class Browser. If you write EnScripts, the upgrade is clear. If you depend on EnScripts in v6, you'll need to upgrade, too, because developers are not going to want to support v6 after upgrading. V7 includes a detachable version of the EnScript Types view, so you can edit your code and have the documentation in front of you at the same time. This really should have been possible long, long ago, but I'm glad it's here now. The fact that it generates a separate class browser for your own code is a nice touch.

Search Results. I haven't played around with the search results view enough to know whether it's fully baked, but it seemed darned close. The results of conditions/filters/searches/scripts now live in a separate tab, where they persist. This is similar to bookmarks, but Search Results can contain different types of data, and I believe retain a notion of what generated them (at least if generated through a search). Additionally, like everything else in v7, Search Results are persisted to disk, supposedly allowing for smoother operation with large numbers of items (as opposed to filling up RAM and dealing with the data greedily). The distinction between Bookmarks and Search Results then becomes that Bookmarks are for items you've selected for your report.

What I don't think I'll love

Reports. The new reporting functionality is certainly better than nothing, but I was disappointed nonetheless. First, looking it over, it's clear that the reporting is built similarly to ExportClass in EnScript, which offers very limited display functionality in exchange for portability between HTML and RTF. Second, as with everything else in EnCase, the metaphor is the tree. You must organize your report into chapters, sections, subsections, and so on. Third, there is actually a new report description language built into this, for you to use for customization. There are dozens of html templating languages and technologies... so why not another one?!?!

Here's my view: this should have had hooks into ASP.Net, and RTF should have been sacrificed on the altar of ancient technologies. I don't really like ASP.Net (or any other Microsoft web technology; give me Python and Django), but it's readily available on Windows and millions of people know it. EnCase would have been open to far more tinkering in one fell swoop. As for RTF, its primary purpose in EnCase is to let you write reports in Microsoft Word. That's useful, I know, really useful even, but not nearly as useful as having first-class HTML reporting support with the ability to save out as PDF. Plus, Microsoft Word supports copying-and-pasting from a browser into Word, so that's still available. Full-fledged HTML5 support would more than make up for the loss of RTF, an unloved also-ran in the document format wars.

What's more, reporting could have been rethought from the ground up. What about something like Evernote or Onenote or TiddlyWiki? The new reporting functionality will be useful to those who want better reporting in EnCase; the Love just isn't there, though. If I need to create great reports, I'll still export the data and use some other tool/technology.

Tags. Maybe I won't love tags. I thought it was really cool you could tag a file just by clicking in the right place in the Tags column. I need to see whether this works in Records and the other views, and what the EnScript support is like. Tags are clearly a head-nod in the direction of review platform capabilities, but review needs specialized—and simplified—controls and functionality. Additionally, it's not clear to me how tags interact with Bookmarks and whether the two should be separate. Is a tag a type of bookmark? Can bookmarks be organized by tag? Is it easy to see overviews of tags? What about multi-case tag review? Will there be any kind of automatic classification done by tag? Tags beg a lot of questions.

The Death of forall(). In EnScript in v7, iterators are the new hotness and forall() is the old and busted. Or so we are told. The problem? forall() is the lone great innovation of EnScript. Recursive descent in every other programming language is a PITA; forall() makes it a joy. What's more, the iterator design in V7, while technically solid on its own, dovetails so nicely into forall() it's a shame the two aren't integrated. There's no reason that iterators could not be used with forall(), regardless of whether the data's in memory or on disk. forall() means "for all" and the extra bit of syntactic sugar guarantees that the iteration will occur successfully without worrying about termination.

In fact, more often than not, forall() maps onto Map. The body of forall() loops are often data-parallel, and with a little bit of work in the EnScript language, forall() could have become a concurrent map(). Trivial parallel processing.

That said, if ItemIteratorClass supports virtual functions, such that we can write our own iterators, then this will be a worthy trade. With our own iterators, EnScripters can do lots of things, like define reverse iterators and create generic interfaces to common routines that use different data structures.

Wait and See

EnCase V7 is hands-down the most significant upgrade to EnCase I've witnessed. It's astonishing the amount of work that's gone into it, and I'm greatly looking forward to using it. The amount of work that went into addressing the everything-in-RAM design of prior versions of EnCase can only be described as Herculean; that GSI's developers went so far beyond such back-end changes and put large amounts of time into rethinking EnCase for the new decade is heartening.

There's a lot to learn, and it will take me some time to puzzle it all out. Conclusions are for another time. I will say that, for the first time in a long time, I'm looking forward to upgrading EnCase and exploring it. I think it will be fun.

Next Generation of Hadoop

2011-02-23T20:00:00.000-05:00

The last couple of weeks has seen some new information trickle out from Yahoo! about their efforts to improve scalability on Hadoop. (For a sense of a scale to the uninitiated, by "improve scalability" I mean, "scale beyond clusters of 4,000 servers.") Yahoo! is calling this effort Next Generation Hadoop, or, Hadoop .Next.

To paraphrase V.S. Naipaul on the New Yorker and fiction, Yahoo! knows nothing about enterprise software marketing, nothing.

To those paying attention, it's clear there's been tension between Yahoo!, Hadoop's first and most important patron, and Cloudera, the usurper. It's not hard to play armchair psychologist and speculate about the forces behind the tension, but I certainly don't know enough to comment on it intelligently. What is undeniable, though, is that release momentum hiccuped at a critical period in Hadoop's adoption by the industry at large, and that momentum has only recently been restored. Yahoo!'s recent statement about abandoning their own Hadoop distro and working to improve Apache trunk was very good news.

Still, remember that Hadoop is not yet that magical 1.0. It's changed enormously over the past year or two, and for the better. It's silly it's not considered 1.0 already, and it's clear that a 1.0 designation is coming down the pike.

THEREFORE: It makes no sense whatsoever to talk about "Next Generation Hadoop." All the technical reasons are sound, but here's what this sounds like to me: "We haven't hit 1.0 yet, but we've already come down with a terminal case of Second System Effect." Moreover, this sense of foreboding is not at all helped by the fact that the presentations and documents about Hadoop .Next have not included any information about the most important facet of a Hadoop refactoring: the API. So, not only do I have to worry about deciding between implementing Mapper or inheriting from Mapper, I'm now worried that I'll have to abandon Mapper for ConfigurableGenericJobTask and ConfigurableGenericJobTaskFactoryInterface and rewrite all my code to suit. Viva la Revolution.

I'm not really that worried. Mostly, Hadoop has been evolving according to a Teilhardian roadmap. However, it'd be fantastic if the community released 1.0 in 2011 and phased in Hadoop .Next incrementally, without making it seem so disruptive.

Fast Unique Files filter for EnCase

2011-02-15T18:43:00.001-05:00

Related to my post Fast Hash Matching post from November and Lance's original post, here's the code to an EnCase filter for the Entries view that will show you only the first occurrence of each file by hash value:

include "GSI_Basic"

class MainClass {

  NameListClass  HashList;

  BinaryTreeClass Tree;

  MainClass() :

    HashList(),

    Tree(HashList, new NodeStringCompareClass())

  {

    if (SystemClass::CANCEL == SystemClass::Message(

     SystemClass::ICONINFORMATION |

     SystemClass::MBOKCANCEL, "Unique Files By Hash",

     "Note:\nFiles must be hashed prior to running this filter."))

    {

      SystemClass::Exit();

    }

  }

  bool Main(EntryClass entry) {

    HashClass hash = entry.HashValue();

    if (Tree.FastFind(hash)) {

      return false;

    }

    else {

      Tree.FastInsert(new NameListClass(null, hash), hash);

      return true;

    }

  }

}

The code in the comments on Lance's blog is close, but not quite correct, maybe due to the comment form or some such. You need to hash all files before you run this. As discussed in my earlier post, this is by no means the fastest possible way to do this, but I recently had someone ping me about needing exactly this, and it makes sense to put it up for everyone.

This filter is utterly dependent on BinaryTreeClass in GSI_Basic.EnScript, a support file that comes with EnCase and can be found at Program Files\EnCase 6\EnScript\Include\GSI_Basic.EnScript.

I also have put an ini file of the filter that you can import directly into EnCase (right-click in the filter tree, choose Import...), available here on Google Docs.

Dynamic Features in EnScript

2011-02-15T17:00:00.000-05:00

EnScript is first and foremost a static language. It's statically typed and statically compiled, which means that EnScript figures out everything in your script before it starts to execute it, and if it cannot figure out which code should be called or finds any other syntactic problems, it generates a compilation error. It also means that EnScript executes reasonably efficiently, since the compiler has figured out which functions to call in advance, and this is done in a relatively lightweight manner.

(It should be noted that EnScript does not do much in the way of code-optimization, however, so dynamic languages that make use of just-in-time compilation and other aggressive techniques may yet execute faster than EnScript.)

Despite being squarely in the static camp of languages, EnScript does have some features which can be considered "dynamic." By dynamic, I mean that you can write an EnScript that is able to interact with the EnScript engine and script code, at least in some ways.

The dynamic features in EnScript are:

Typecasting
Class reflection
Property accessors
Subordinate execution through ProgramClass

These dynamic features make EnScript far more powerful than it initially seems. I'll be writing about these features over the next few weeks. Since typecasting is short and sweet, I'll cover that now.

Upcasting

Let's say you're working with a NameListClass object. Since NameListClass inherits from NodeClass, you can always treat a NameListClass object as a NodeClass object without doing anything special:

NameListClass list();

list.Parse("one two three", " ");

NodeClass nodeRef = list; // up-cast

Console.WriteLine(nodeRef.Count());

This is an example of upcasting, where we treat a derived object as its parent type by manipulating it through a parent-type reference. EnScript knows that NameListClass inherits from NodeClass, so there's no need for you to do anything special, and this cannot possibly fail. There is no ambiguity.

Downcasting

What if we want to do the reverse? Say we have a function that takes a NodeClass object as a parameter, and we'd like to treat it specially if it's a NameListClass object? Here's the answer:

void foo(NodeClass node) {

  NameListClass listRef = NameListClass::TypeCast(node);

  if (listRef) {

    // ...

}

}

As it turns out, every class in EnScript has a static function named TypeCast(). TypeCast() takes an ObjectClass reference and returns a reference to an object for its particular type, e.g., NameListClass::TypeCast() returns a NameListClass object reference. Because every object inherits from ObjectClass implicitly (even NodeClass), you can pass just about anything into TypeCast(), and because NameListClass::TypeCast() returns a reference to a NameListClass object, EnScript's compiler doesn't complain about assigning the result to the listRef reference here. TypeCast() lets us bridge the gap, allowing us to treat our NodeClass as a NameListClass.

Note here that we then check listRef to see whether its null. Why? Well, what if someone called foo() and passed in an EntryClass object? An EntryClass object is not a NameListClass object, so NameListClass::TypeCast() will return null. By doing so, you can safely test your downcast. Of course, if you didn't do the check, the code would compile but you'd end up with a null reference error when someone called foo() with anything other than a NameListClass object.

One more thing about TypeCast(): Don't pass it a null reference. TypeCast() itself will generate a null reference error if you pass it null. Therefore, to be truly safe, foo() should look like this:

void foo(NodeClass node) {

  if (node) {

    NameListClass listRef = NameListClass::TypeCast(node);

    if (listRef) {

      // ...

}

}

}

Single Object Inheritance is the Root of All Evil

If you make your own class hierarchies, you will find yourself having to make use of TypeCast() quite a bit. Let's say you have an AnimalClass as a base class and two derived classes, DogClass and CatClass. Further, we want to have a method to check whether two AnimalClass objects are equal (...uh, whatever that means...). So, we would have to create a virtual function in AnimalClass, isEqual(), that looks like this:

class AnimalClass {

  pure bool isEqual(AnimalClass other);

}

and then override the function in DogClass and CatClass. Clearly, a dog is not ever going to be equal to a cat. But not all cats are equal to each other, either. We will need to check their favorite brand of kitty food, kitty litter, markings, meowing habits, and whatnot to decide two cats are equal. So, even though isEqual() receives an AnimalClass object, we'll need to treat it as a CatClass to inspect all the member variables that are specific to cats and make this determination.

class CatClass {

  String FaveWetFood, FaveDryFood, FaveLitter;

  virtual bool isEqual(AnimalClass other) {

    CatClass cat = CatClass::TypeCast(other);

    if (cat) {

      return FaveWetFood == cat.FaveWetFood

        && FaveDryFood == cat.FaveDryFood

        && FaveLitter == cat.FaveLitter;

}

    return false; // must be a dog or a ferret

}

}

The TypeCast() ends up being necessary because there's something common we want to do for all animals (e.g., make equality comparisons), so the functionality must go in the base class and the function signature must involve an AnimalClass object. In languages like Java, SmallTalk, and EnScript, programmers end up having to do this a lot.

In C++, which has templates, you can often make use of the Curiously Recurring Template Pattern.

sed quis custodiet ipsos custodes?

2011-02-11T02:44:00.004-05:00

Fifty years on, Eisenhower's farewell address seems quite relevant to the times, and the readers of this blog.

A quibble:

Yet, in holding scientific research and discovery in respect, as we should, we must also be alert to the equal and opposite danger that public policy could itself become the captive of a scientific-technological elite.

In 2011, when any village idiot/realtor can comment on which NSF grants do not have merit, it is safe to say that public policy is in no danger of becoming captive to the scientific-technological elite. (By the way, Jacques Barzun's The House of Intellect is a great exploration of anti-intellectualism in the U.S. [I hope I look that good when I'm 102, and I'm unsurprised the Presbyterians played host.])

However, a core tenet of the contemporary homeland defender's creed is "we don't set policy." The scientific-technological elite, to which you, dear reader, no doubt belong, strives to uphold the Unix ideal, providing mechanism, not policy... capability, not culpability. This is a cop-out. You can't sit Grandma down in front of a bash prompt and tell her she'll be just fine with man man.

Our clients, those whom we serve, likely do not understand what it is we do, what we know, what we can do, and, most importantly, what should be done. If we in the Cyber Industrial Complex* do not act with restraint, if we do not "conduct our struggle on the high plane of dignity and discipline," then we risk legitimizing the paranoid delusionals, and the lawless actions of their defenders. "Thy will be done" may be the easy interpretation our masters desire, but when our masters are not omniscient, or lack sufficient wisdom, then, ever mindful of our own weaknesses and ever penitent, we should strive to be of good counsel. Machine learning, SNA, disinformation, and old school psyops are good tools, but only if we have good targets.

* Military Cyber Complex is maybe more apt, but less poetic.

Update: Penitence requires more than an apology, but it's a good start.

Update 2: The paper of record

Comment: What about severing ties to Hunton & Williams? Severing ties to a tiny firm like HB Gary Federal seems like kicking a dead dog.

Empty hash values don't get sorted?

2011-01-22T14:23:00.000-05:00

Weird thing in EnCase 6.18 I came across today: when sorting by the Hash Value field, entries without hash values (0-byte contents) seem immune to sorting, and seem to remain in a stable ordering, relative to each other. You can see this in this screenshot, where the evidence is in a logical evidence file with folders that don't have content. I don't know whether this is specific to logical evidence files, but it's somewhat annoying.

Wanted: strpbrk()

2010-12-04T22:49:00.000-05:00

I'm looking for a good EnScript API method for testing whether a string contains any characters in a second string.

That is, I want the standard C function strpbrk().

For some reason, I feel like earlier versions of EnCase had a function that did this. (By earliere versions, I mean v5 or v4.)

String::Trim() would almost do the job, except that it replaces the occurrences, which isn't what I want. The second parameter of Trim() is an int for passing in a combination of the String::TRIMOPTIONS enums. So, I tried passing in 0 instead of one of the enums, hoping this would find all occurrences but not replace them. Sadly, passing in 0 finds no occurrences.

You can use SearchClass with a character class regexp (e.g., [abc]) or NameListClass::Parse(), but both of them are pretty heavyweight.

In happier news, though, you can use EnScript to convert doubles to strings in scientific notation.