AAAI Publications, The Twenty-Ninth International Flairs Conference

Font Size: 
An Evolutionary Trace Algorithm for Constructing Malware Lineages
Alex Heinricher, Steven Jilcott

Last modified: 2016-03-30


An important problem in malware forensics is generating a partial ordering of a collection of variants of a malware program, reflecting a history of the malware’s evolution as it is adapted by the original or new authors. We present new work extending our results on the malware lineage problem originally presented at FLAIRS 2013. We provide a new algorithm for reconstructing malware lineages with and without branch and merge events. This algorithm incorporates two innovations – the evaluation of candidate evolutionary traces based on candidate sets of feature accretion events and a machine-learning inspired approach to reducing overexplanation in the final lineage. The evolutionary trace algorithm is evaluated on several small families of malware whose ground truth lineage is known.


malware; lineage; machine learning

Full Text: PDF