An Automated Signature-Based Approach against Polymorphic Internet Worms

Capable of infecting hundreds of thousands of hosts, worms represent a major threat to the Internet. However, the defense against them is still an open problem. This paper attempts to answer an important question: How can we distinguish polymorphic worms from normal background traffic? We propose a new worm signature, called the position-aware distribution signature (PADS), which fills the gap between traditional signatures and anomaly-based intrusion detection systems. The new signature is a collection of position-aware byte frequency distributions. It is more flexible than the traditional signatures of fixed strings while it is more precise than the position-unaware statistical signatures. We propose two algorithms based on expectation-maximization (EM) and Gibbs sampling to efficiently compute PADS from a set of polymorphic worm samples. We also discuss how to separate a mixture of different polymorphic worms such that their respective PADS signatures can be calculated. We perform extensive experiments to demonstrate the effectiveness of PADS in separating new worm variants from normal background traffic.