Abstract

Sequence alignment algorithms have recently found a use in detecting code clones, software plagiarism, code theft, and polymorphic malware. This approach involves extracting birthmarks, in this case sequences, from programs and comparing them using sequence alignment, a procedure which has been intensively studied in the field of bioinformatics. This idea seems promising. However, we show that an attacker can evade detection by considering the positions of inserted dummy code and/or the frequency of function calls. Moreover, we found that randomly inserting and deleting symbols in the sequence was ineffective. By using birthmark sequences extracted from actual malicious and benign programs, we found that the most effective strategy was to use a hybrid approach incorporating “non-consecutive insertion” and “highest frequency deletion”. We also discuss the implementation costs of such attacks and propose using non-determinism through concurrent programming as an alternative evasion strategy. This is joint work with Hyoungshick Kim and Pietro Lio’.

This is a practice talk for SSP ’12.