In the latest of his 'Greetz from Academe' series, highlighting some of the work going on in academic circles, John Aycock looks at malware detection using NX responses.
Copyright © 2013 Virus Bulletin
As I write this, we are in the midst of the Calgary Stampede, an annual event where the city is inundated with modern cowboy culture: boots, hats, pick up trucks, and belt buckles that are Entirely Too Large. (Once, as a joke, I covered a dinner-sized paper plate in aluminium foil and wore it as a belt buckle to a Stampede breakfast. No one even noticed.) I am reminded of last September’s VB conference when we descended upon another cowboy-themed city, Dallas.
There, Gunter Ollmann presented a paper  about malware using domain generation algorithms (a.k.a. DGA, AGD or domain flux) and how to detect it by using NX responses. The intuition is that, if malware is spewing out a lot of requests to the domain name system (DNS) for non-existent domain names as it tries to phone home, then looking at the corresponding ‘NX’ error replies from the DNS provides a method for detecting that malware. It seems sensible, and it works. Ollmann’s presentation, if I recall correctly, was a reprise of work published in USENIX Security shortly before VB2012; for anyone wanting more technical detail, it’s all there in , complete with maths and funky Greek symbols for good measure.
I was curious as to how this line of research has progressed since then, and I found my answer in a paper that appeared in June 2013 at the Conference on Dependable Systems and Networks. (I suspect the papers at a conference on undependable systems and networks would be far more entertaining.) Krishnan et al.’s ‘Crossing the Threshold’  carries on with DGA detection, looking at a way to make use of NX replies.
It would be a perfectly justifiable reaction to say ‘um, detection using NX replies has already been done, hasn’t it?’ – and herein lies a basic dichotomy of academic research. On the one hand, academics are great at abstracting away details, sometimes to the point of silliness. For example, I would be perfectly comfortable making a mental category of work called ‘malware detection using DNS anomalies’ into which I would lump the papers I already mentioned , ,  – but I wouldn’t stop there. Invariably, I would also include papers that have nothing to do with DGA or NX replies – such as the detection of scanning worms by watching for network traffic to an IP address that wasn’t looked up by a previous DNS request . In the abstract sense, the papers are all about DNS anomalies, but it’s arguably a pretty broad and meaningless category.
So on the one hand, we have wanton abstraction; on the other hand, academics have a painfully fine eye for detail, when it matters. And it matters when distinguishing what you’ve done from what’s already been done in related work. The NX-based detection in the ‘Crossing the Threshold’ paper is totally different from ,  because it ‘do[es] not rely on domain structure or clustering techniques to identify bots’ .
I’m being facetious, of course. The NX-based detection in  is actually very simple and elegant, and well worth a look for anyone who has a good view of DNS traffic and a hankering to find DGA malware. Krishnan et al. filter out NX replies, and filter again to get rid of NX replies for known-good domains, trying to pare their input down sufficiently for their method to be scalable. The remaining NX replies are mined for the domain name that failed and the IP address of the requesting machine, the idea being to label individual machines as benign or infected. An interesting point is that the way they determine this involves determining whether or not the NX response is for a domain that the machine has seen before. (I’m generalizing a bit here. The researchers use what they call ‘zones’ that correspond to second-level domain names.) There’s enough detail in the paper to both build a system like theirs and set the labelling thresholds, along with copious evaluation. The researchers were able to label machines with only about three to four NX replies – which is pretty impressive, even for failed cowboys like me who don’t know which end of a bull to milk.
 Ollmann, G. The new wave of ‘undetectable’ DGA threats: examining the state of the art in malware evasion techniques. Proceedings of the 22nd Virus Bulletin International Conference, 2012, pp.270–273.
 Antonakakis, M.; Perdisci, R.; Nadji, Y.; Vasiloglou, N.; Abu-Nimeh, S.; Lee, W.; Dagon, D. From throw-away traffic to bots: detecting the rise of DGA-based malware. Proceedings of the 21st USENIX Security Symposium, 2012, pp.491–506.
 Krishnan, S.; Taylor, T.; Monrose, F.; McHugh, J. Crossing the threshold: detecting network malfeasance via sequential hypothesis testing. 43rd IEEE/IFIP International Conference on Dependable Systems and Networks, 2013.