Inside the Permutation-Scanning Worms: Propagation Modeling and Analysis

In recent years, both sophistication and damage potential of Internet worms have increased tremendously. To understand their threat, we need to look into their payload for signatures as well as propagation pattern for Internet-scale behavior. An accurate analytical propagation model allows us to comprehensively study how a worm propagates under various conditions, which is often computationally too intensive for simulations. More importantly, it gives us an insight into the impact of each worm/network parameter on the propagation of the worm. Traditionally, most modeling work in this area concentrates on the relatively simple random-scanning worms. However, modeling the permutation-scanning worms, a class of worms that are fast yet stealthy, has been a challenge to date. This paper proposes a mathematical model that precisely characterizes the propagation patterns of the general permutation-scanning worms. The analytical framework captures the interactions among all infected hosts by a series of interdependent differential equations, which are then integrated into closed-form solutions that together present the overall worm behavior. We use the model to study how each worm/network parameter affects the worm propagation. We also investigate the impact of dynamic network conditions on the correctness of the model.