Signature Tree Generation for Polymorphic Worms

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.