An improved ant colony system algorithm for solving the IP traceback problem

Ping Wang, Hui-Tang Lin, Tzy Shiah Wang

Research output: Contribution to journalArticle

22 Citations (Scopus)

Abstract

The difficulty in identifying the origin of an attack over the Internet is termed the IP traceback (IPTBK) problem. The probable origin of an attack is commonly investigated using some form of ant colony system (ACS) algorithms. However, such algorithms tend to converge to a local suboptimal solution, meaning that the perpetrator of the attack cannot be found. Therefore, the present study proposes a modified ACS scheme (denoted as ACS-IPTBK) that can identify the true attack path even without the entire network routing information. The ability of the ants to search all feasible attack paths was enhanced using a global heuristic mechanism in which the ant colony was partitioned into multiple subgroups, with each subgroup having its own pheromone updating rule. The performance of the ACS-IPTBK algorithm in reconstructing the attack path was investigated through a series of ns2 simulations by using network topologies generated by the Waxman model. The simulations focused specifically on the effects of the ACS model parameters and network characteristics on the performance of the ACS-IPTBK scheme in converging towards the true attack path. Finally, the robustness of the proposed scheme against spoofed IP attacks was investigated. The results showed that the proposed scheme has a slightly slower convergence speed than does the conventional ACS algorithm, but yields a more globally optimal solution for the attack path, particularly in large-scale network topologies.

Original languageEnglish
Pages (from-to)172-187
Number of pages16
JournalInformation sciences
Volume326
DOIs
Publication statusPublished - 2016 Jan 1

Fingerprint

Ant Colony System
Attack
Topology
Path
Network routing
Network Topology
Internet
Subgroup
Ants
Pheromone
Convergence Speed
Ant Colony
Probable
Updating
Simulation
Routing
Optimal Solution
Entire
Heuristics
Tend

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Theoretical Computer Science
  • Computer Science Applications
  • Information Systems and Management
  • Artificial Intelligence

Cite this

@article{83211c23d86f427ba4a9f72996cc18ff,
title = "An improved ant colony system algorithm for solving the IP traceback problem",
abstract = "The difficulty in identifying the origin of an attack over the Internet is termed the IP traceback (IPTBK) problem. The probable origin of an attack is commonly investigated using some form of ant colony system (ACS) algorithms. However, such algorithms tend to converge to a local suboptimal solution, meaning that the perpetrator of the attack cannot be found. Therefore, the present study proposes a modified ACS scheme (denoted as ACS-IPTBK) that can identify the true attack path even without the entire network routing information. The ability of the ants to search all feasible attack paths was enhanced using a global heuristic mechanism in which the ant colony was partitioned into multiple subgroups, with each subgroup having its own pheromone updating rule. The performance of the ACS-IPTBK algorithm in reconstructing the attack path was investigated through a series of ns2 simulations by using network topologies generated by the Waxman model. The simulations focused specifically on the effects of the ACS model parameters and network characteristics on the performance of the ACS-IPTBK scheme in converging towards the true attack path. Finally, the robustness of the proposed scheme against spoofed IP attacks was investigated. The results showed that the proposed scheme has a slightly slower convergence speed than does the conventional ACS algorithm, but yields a more globally optimal solution for the attack path, particularly in large-scale network topologies.",
author = "Ping Wang and Hui-Tang Lin and Wang, {Tzy Shiah}",
year = "2016",
month = "1",
day = "1",
doi = "10.1016/j.ins.2015.07.006",
language = "English",
volume = "326",
pages = "172--187",
journal = "Information Sciences",
issn = "0020-0255",
publisher = "Elsevier Inc.",

}

An improved ant colony system algorithm for solving the IP traceback problem. / Wang, Ping; Lin, Hui-Tang; Wang, Tzy Shiah.

In: Information sciences, Vol. 326, 01.01.2016, p. 172-187.

Research output: Contribution to journalArticle

TY - JOUR

T1 - An improved ant colony system algorithm for solving the IP traceback problem

AU - Wang, Ping

AU - Lin, Hui-Tang

AU - Wang, Tzy Shiah

PY - 2016/1/1

Y1 - 2016/1/1

N2 - The difficulty in identifying the origin of an attack over the Internet is termed the IP traceback (IPTBK) problem. The probable origin of an attack is commonly investigated using some form of ant colony system (ACS) algorithms. However, such algorithms tend to converge to a local suboptimal solution, meaning that the perpetrator of the attack cannot be found. Therefore, the present study proposes a modified ACS scheme (denoted as ACS-IPTBK) that can identify the true attack path even without the entire network routing information. The ability of the ants to search all feasible attack paths was enhanced using a global heuristic mechanism in which the ant colony was partitioned into multiple subgroups, with each subgroup having its own pheromone updating rule. The performance of the ACS-IPTBK algorithm in reconstructing the attack path was investigated through a series of ns2 simulations by using network topologies generated by the Waxman model. The simulations focused specifically on the effects of the ACS model parameters and network characteristics on the performance of the ACS-IPTBK scheme in converging towards the true attack path. Finally, the robustness of the proposed scheme against spoofed IP attacks was investigated. The results showed that the proposed scheme has a slightly slower convergence speed than does the conventional ACS algorithm, but yields a more globally optimal solution for the attack path, particularly in large-scale network topologies.

AB - The difficulty in identifying the origin of an attack over the Internet is termed the IP traceback (IPTBK) problem. The probable origin of an attack is commonly investigated using some form of ant colony system (ACS) algorithms. However, such algorithms tend to converge to a local suboptimal solution, meaning that the perpetrator of the attack cannot be found. Therefore, the present study proposes a modified ACS scheme (denoted as ACS-IPTBK) that can identify the true attack path even without the entire network routing information. The ability of the ants to search all feasible attack paths was enhanced using a global heuristic mechanism in which the ant colony was partitioned into multiple subgroups, with each subgroup having its own pheromone updating rule. The performance of the ACS-IPTBK algorithm in reconstructing the attack path was investigated through a series of ns2 simulations by using network topologies generated by the Waxman model. The simulations focused specifically on the effects of the ACS model parameters and network characteristics on the performance of the ACS-IPTBK scheme in converging towards the true attack path. Finally, the robustness of the proposed scheme against spoofed IP attacks was investigated. The results showed that the proposed scheme has a slightly slower convergence speed than does the conventional ACS algorithm, but yields a more globally optimal solution for the attack path, particularly in large-scale network topologies.

UR - http://www.scopus.com/inward/record.url?scp=84943800149&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84943800149&partnerID=8YFLogxK

U2 - 10.1016/j.ins.2015.07.006

DO - 10.1016/j.ins.2015.07.006

M3 - Article

AN - SCOPUS:84943800149

VL - 326

SP - 172

EP - 187

JO - Information Sciences

JF - Information Sciences

SN - 0020-0255

ER -