Malware lineage studies the evolutionary relationships among malware and has important applications for malware analysis. A persistent limitation of existing approaches is that they only work on synthetic malware, malware that are not packed, or packed malware for which unpackers are available. This is problematic since to evade detection, a majority of malware are packed. In this work, we propose a novel malware lineage approach that works on malware samples collected in the wild.

Given a set of malware executables from the same family, for which no source code is available and which may be packed, our approach produces a lineage graph where nodes are versions of the family and edges describe the relationships between versions. To enable our malware lineage approach, we propose the first technique to identify the versions of a malware family and a scalable code indexing technique for determining shared functions between any pair of input samples. Our approach addresses the challenges introduced by operating on real malware such as unpacking, disassembly, and limitations in the malware collection. We have evaluated the accuracy of our approach on 13 open-source programs and have applied it to produce lineage graphs for 10 malware families. Our malware lineage graphs achieve on average a 26 times reduction from number of input samples to number of versions.