One of the big problems in detecting malware is that there are so many different forms of the same malicious code. This problem of polymorphism is what led Rick Wesson to develop icewater, a clustering technique that identifies malware.
Presented at Shmoocon 2016, the icewater project is a new way to process and filter the vast number of samples one finds on the Internet. Processing 300,000 new samples a day to determine if they have polymorphic malware in them is a daunting task. The approach used here is to create a fingerprint from each binary sample by using a space-filling curve. Polymorphism will change a lot of the bits in each sample, but as with human fingerprints, patterns are still present in this binary fingerprints that indicate the sample is a variation on a previously known object.
IPv4 addresses shown in a space-filling curve by xkcd CC-BY-NC
The images you’re seeing above are graphic representations of these fingerprints. Images aren’t actually part of the technique, but by converting each byte value to greyscale it is a good way for humans to understand what the computer is using in its analysis.
Once the fingerprint is made, it’s simple to compare and cluster together samples that are likely the same. The expensive part of this method is running the space-filling curve. It take a lot of time to run this using a CPU. FPGAs are idea, but the hardware is comparatively costly. In its current implementation, GPUs are the best balance of time and expense.
This expense measurement gets really interesting when you start talking Internet-scale problems; needing to constantly processing huge amounts of data. The current GPU method can calculate an object in about 33ms, allowing for a couple hundred thousand samples per day. This is about four orders of magnitude better than CPU methods. But the goal is to transition away form GPUs to leverage the parallel processing found in FPGAs.
Rick’s early testing with Xenon Phi/Altera FPGAs can calculate space-filling curves at a rate of one object every 586µs. This represents a gain of nine orders of magnitude over CPUs but he’s still not satisfied. His goal is to get icewater down to 150µs per object which would allow 10 million samples to be processed in four hours with a power cost of 4000 Watts.
How to do you compare computations on hardware the has a different cost to manufacture and different power budgets? Rick plans to reduce the problem with a measurement he calls InfoJoules. This is an expression of computational decisions versus Watt seconds. 1000 new pieces of information calculated in 1 second on a machine consuming 1000 Watts is 1 InfoJoule. This will make the choice of hardware a bit easier as you can weigh both the cost of acquiring the hardware with the operational cost per new piece of information.