Signature tree generation for polymorphic worms

Yong Tang, Bin Xiao, Xicheng Lu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

41 Citations (Scopus)


Network-based signature generation (NSG) has been proposed as a way to automatically and quickly generate accurate signatures for worms, especially polymorphic worms. In this paper, we propose a new NSG system-PolyTree, to defend against polymorphic worms. We observe that signatures from worms and their variants are relevant and a tree structure can properly reflect their familial resemblance. Hence, in contrast to an isolated view of generated signatures in previous approaches, PolyTree organizes signatures extracted from worm samples into a tree structure, called signature tree, based on the formally defined "more specific relation of simplified regular expression signatures. PolyTree is composed of two components, signature tree generator and signature selector. The signature tree generator implements an incremental signature tree generation algorithm from worm sample clustering, up-to-date signature refinement to efficient tree construction. The incremental signature tree construction gives insight on how the worm variants evolve over time and allows signature refinement upon a new worm sample arrival. The signature selector chooses a set of signatures for worm detection from a benign traffic pool and the current signature tree constructed by the signature tree generator. Experiments show that PolyTree cannot only generate accurate signatures for polymorphic worms with noise, but these signatures are well organized in the signature tree to reflect the inherent relations of worms and their variants.
Original languageEnglish
Article number5487493
Pages (from-to)565-579
Number of pages15
JournalIEEE Transactions on Computers
Issue number4
Publication statusPublished - 7 Mar 2011


  • polymorphic worm
  • sequence alignment
  • signature generation
  • Signature tree

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'Signature tree generation for polymorphic worms'. Together they form a unique fingerprint.

Cite this