You are here

UCF Digital Collections ยป ETD Collection

GRAPH-THEORETIC APPROACH TO MODELING PROPAGATION AND CONTROL OF NETWORK WORMS

Download pdf | Full Screen View

Date Issued:
2005
Abstract/Description:
In today's network-dependent society, cyber attacks with network worms have become the predominant threat to confidentiality, integrity, and availability of network computing resources. Despite ongoing research efforts, there is still no comprehensive network-security solution aimed at controling large-scale worm propagation. The aim of this work is fivefold: (1) Developing an accurate combinatorial model of worm propagation that can facilitate the analysis of worm control strategies, (2) Building an accurate epidemiological model for the propagation of a worm employing local strategies, (3) Devising distributed architecture and algorithms for detection of worm scanning activities, (4) Designing effective control strategies against the worm, and (5) Simulation of the developed models and strategies on large, scale-free graphs representing real-world communication networks. The proposed pair-approximation model uses the information about the network structure--order, size, degree distribution, and transitivity. The empirical study of propagation on large scale-free graphs is in agreement with the theoretical analysis of the proposed pair-approximation model. We, then, describe a natural generalization of the classical cops-and-robbers game--a combinatorial model of worm propagation and control. With the help of this game on graphs, we show that the problem of containing the worm is NP-hard. Six novel near-optimal control strategies are devised: combination of static and dynamic immunization, reactive dynamic and invariant dynamic immunization, soft quarantining, predictive traffic-blocking, and contact-tracing. The analysis of the predictive dynamic traffic-blocking, employing only local information, shows that the worm can be contained so that 40\% of the network nodes are not affected. Finally, we develop the Detection via Distributed Blackholes architecture and algorithm which reflect the propagation strategy used by the worm and the salient properties of the network. Our distributed detection algorithm can detect the worm scanning activity when only 1.5% of the network has been affected by the propagation. The proposed models and algorithms are analyzed with an individual-based simulation of worm propagation on realistic scale-free topologies.
Title: GRAPH-THEORETIC APPROACH TO MODELING PROPAGATION AND CONTROL OF NETWORK WORMS.
40 views
16 downloads
Name(s): Nikoloski, Zoran, Author
Deo, Narsingh, Committee Chair
University of Central Florida, Degree Grantor
Type of Resource: text
Date Issued: 2005
Publisher: University of Central Florida
Language(s): English
Abstract/Description: In today's network-dependent society, cyber attacks with network worms have become the predominant threat to confidentiality, integrity, and availability of network computing resources. Despite ongoing research efforts, there is still no comprehensive network-security solution aimed at controling large-scale worm propagation. The aim of this work is fivefold: (1) Developing an accurate combinatorial model of worm propagation that can facilitate the analysis of worm control strategies, (2) Building an accurate epidemiological model for the propagation of a worm employing local strategies, (3) Devising distributed architecture and algorithms for detection of worm scanning activities, (4) Designing effective control strategies against the worm, and (5) Simulation of the developed models and strategies on large, scale-free graphs representing real-world communication networks. The proposed pair-approximation model uses the information about the network structure--order, size, degree distribution, and transitivity. The empirical study of propagation on large scale-free graphs is in agreement with the theoretical analysis of the proposed pair-approximation model. We, then, describe a natural generalization of the classical cops-and-robbers game--a combinatorial model of worm propagation and control. With the help of this game on graphs, we show that the problem of containing the worm is NP-hard. Six novel near-optimal control strategies are devised: combination of static and dynamic immunization, reactive dynamic and invariant dynamic immunization, soft quarantining, predictive traffic-blocking, and contact-tracing. The analysis of the predictive dynamic traffic-blocking, employing only local information, shows that the worm can be contained so that 40\% of the network nodes are not affected. Finally, we develop the Detection via Distributed Blackholes architecture and algorithm which reflect the propagation strategy used by the worm and the salient properties of the network. Our distributed detection algorithm can detect the worm scanning activity when only 1.5% of the network has been affected by the propagation. The proposed models and algorithms are analyzed with an individual-based simulation of worm propagation on realistic scale-free topologies.
Identifier: CFE0000640 (IID), ucf:46521 (fedora)
Note(s): 2005-08-01
Ph.D.
Engineering and Computer Science, School of Computer Science
Doctorate
This record was generated from author submitted information.
Subject(s): network worms
cops-and-robbers games
reactive control
pair-approximation
individual-based simulation
Persistent Link to This Record: http://purl.flvc.org/ucf/fd/CFE0000640
Restrictions on Access: campus 2006-01-31
Host Institution: UCF

In Collections