Again and again and again... That's what comes to my mind every time when I see a new variant of the Kavo family and, most recently, also the Hilot family. These malware samples are machine-generated and their authors can develop a "completely new" set of samples based on a simple change made to the generator itself. What's the problem here? These changes are not random as we earlier thought, they're precisely targeted against the most popular AV engines.
Let's describe it with the Hilot case. This malware family is detected algorithmically by our engine and the detection can be called a generic detection (this means not with a fixed signature or checksum). Once the authors notice a higher detection rate of their binaries, they have decided to change the generator. What surprised me was the tight boundary to our detection. We have been checking some characteristics of a significant block inside the binary as a part of our detection process and this block is a part of our cat and mouse game. But, the Hilot authors then shifted this significant block in response. It would be not that surprising generally, but they only moved the block exactly and only as far as our checking routine did not check. Well, the first time I thought it might be a coincidence and I also added a check to the moved block. But a few days afterwards, in new Hilot variants, this significant block shifted again and again only by the necessary amount of bytes to avoid our detection. This scenario has since repeated eight times (and I think it will never stop) and that can't be a coincidence IMO. Sometimes, I even think that Hilot authors are continuously reversing our detection. It's a precise approach, but if someone reads our detections, who's the cat and who's the mouse?
The logical conclusion for you is to always keep your AV and virus database up to date. No matter how efficient the heuristics and generic detections are, malware authors seem to be quite diligent when it comes to inventing new ways of tricking even the most proactive detections.