March 15, 2010, 9:33 AM — Anti-virus products scan for malware in two ways. They look for sequences of bits that are found in programs that are known to be bad (but which are not commonly found in good programs). And they run programs in sandboxes and look for known malicious actions. The first approach only catches known malware instances, while the second can also catch variants of these. Still, many malware agents slip through the cracks undetected... until the rules of the anti-virus programs are updated, that is. It is a constant battle between the attackers and the defenders.
Instead of looking for known patterns -- whether of instructions and data, or of actions -- wouldn't it be great if we could look for anything that is malicious? That may sound like a pipe dream.
Not to me.
Let me tell you why. But first, let's agree about some things.
1) There are absolutely only three things malware can do when you scan for it. One: be active in RAM, maybe trying to interfere with the detection algorithm. Two: not be active in RAM, but store itself in secondary storage. It cannot interfere with the detection algorithm then, quite obviously. And option number three: erase itself.
2) Any program -- good or bad -- that wants to be active in RAM has no choice but to take up some space in RAM. At least one byte, right?
Assume now that we have a detection algorithm that runs in kernel mode, and that swaps out everything in RAM. Everything except itself. Well, malware may interfere, of course, as it often does, and remain in RAM. But if we know how big RAM is, we know how much space should be free. Assume we write pseudo-random bits over all this supposedly free space. Again, a malware agent could refuse to be overwritten. It could store those random bits somewhere else instead... like in secondary storage.
Then, let us compute a keyed hash of the entire memory contents -- both our detection program and all the random bits. Here is what could happen: If there is no malware in RAM, the results will be the expected result. An external verifier checks this, and tells us that the scanned device is clean. Or there could be malware in RAM, and the checksum will be wrong. The external verifier would notice and conclude that the device must be infected. Or malware could divert the read requests directed at the place it is stored to the place in secondary storage where it stored the random bits meant for the space it occupies. That would result in the right checksum... but a delay. This delay would be detected by the external verifier, which would conclude that the device is infected.
Why a delay, you ask? Because secondary storage is slower than RAM. Especially if the order of the reads and writes are done in a manner that intentionally causes huge delays if diverted to flash, hard drives, etc.
All we need is the help of an external verifier that knows how much RAM a device we want to protect has, and how fast its processor is. And ways to avoid latency variance when we measure the time to compute the checksum.
This tells us a few interesting things. We can guarantee detection of malware. And that includes zero-day attacks and rootkits. We can even guarantee that we will detect malware that infected a device before we installed our detection program. Think about it. Or read more here and here.
