Using a bioinformatics approach to generate accurate exploit-based signatures for polymorphic worms

Yong Tang, Bin Xiao, Xicheng Lu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

32 Citations (Scopus)


In this paper, we propose Simplified Regular Expression (SRE) signature, which uses multiple sequence alignment techniques, drawn from bioinformatics, in a novel approach to generating more accurate exploit-based signatures. We also provide formal definitions of what is "a more specific" and what is "the most specific" signature for a polymorphic worm and show that the most specific exploit-based signature generation is NP-hard. The approach involves three steps: multiple sequence alignment to reward consecutive substring extractions, noise elimination to remove noise effects, and signature transformation to make the SRE signature compatible with current IDSs. Experiments on a range of polymorphic worms and real-world polymorphic shellcodes show that our bioinformatics approach is noise-tolerant and as that because it extracts more polymorphic worm characters, like one-byte invariants and distance restrictions between invariant bytes, the signatures it generates are more accurate and precise than those generated by some other exploit-based signature generation schemes.
Original languageEnglish
Pages (from-to)827-842
Number of pages16
JournalComputers and Security
Issue number8
Publication statusPublished - 1 Nov 2009


  • Distance restriction
  • Exploit-based signature generation
  • One-byte invariant
  • Polymorphic worms
  • Sequence alignment
  • Simplified regular expression

ASJC Scopus subject areas

  • Computer Science(all)
  • Law


Dive into the research topics of 'Using a bioinformatics approach to generate accurate exploit-based signatures for polymorphic worms'. Together they form a unique fingerprint.

Cite this