Exact and approximation algorithms for sensor placement against DDoS attacks Konstanty Junosza-SzaniawskiDariusz Nogalski

2025-04-24 0 0 2.35MB 30 页 10玖币

侵权投诉

Exact and approximation algorithms for sensor

placement against DDoS attacks

Konstanty Junosza-Szaniawski∗Dariusz Nogalski†

Paweł Rzążewski‡

Abstract

In a DDoS attack (Distributed Denial of Service), an attacker gains

control of many network users through a virus. Then the controlled

users send many requests to a victim, leading to its resources being

depleted. DDoS attacks are hard to defend because of their distributed

nature, large scale and various attack techniques. One possible mode

of defense is to place sensors in a network that can detect and stop an

unwanted request. However, such sensors are expensive so there is a

natural question as to the minimum number of sensors and the optimal

placement required to get the necessary level of safety. Presented below

are two mixed integer models for optimal sensor placement against

DDoS attacks. Both models lead to a trade-oﬀ between the number of

deployed sensors and the volume of uncontrolled ﬂow. Since the above

placement problems are NP-hard, two eﬃcient heuristics are designed,

implemented and compared experimentally with exact mixed integer

linear programming solvers.

1 Introduction

1.1 Distributed Denial of Service

Denial of Service (DoS) attacks are intended to stop legitimate users from

accessing a speciﬁc network resource (Zargar et al.; 2013). A DoS attack is

an attack on availability, which is one of the three dimensions from the well

known CIA security triad - Conﬁdentiality, Integrity and Availability. Avail-

ability is a guarantee of reliable access to information by authorized people.

In 1999 the Computer Incident Advisory Capability (CIAC) reported the

ﬁrst Distributed DoS (DDoS) attack incident (Criscuolo; 2000). In a DDoS

attack, the attacker gains the control of a large number of users through a

∗Warsaw University of Technology, e-mail: k.szaniawski@pw.edu.pl

†Military Communication Institute, e-mail: d.nogalski@wil.waw.pl

‡Warsaw University of Technology and University of Warsaw, e-mail:

p.rzazewski@pw.edu.pl

arXiv:2210.06559v1 [cs.DS] 12 Oct 2022

virus and then simultaneously performs a large number of requests to a vic-

tim server via infected machines. As a result of this large number of tasks,

the victim server is overwhelmed and out of resources, unable to provide

services to legitimate users.

DDoS attacks are a problem not only on the Internet (Ramanathan et al.;

2018), but also in the context of a Smart Grid (Wang et al. (2017), Cameron

et al. (2019) and Huseinović et al. (2020)), Cloud (Bonguet and Bellaïche;

2017) and Control Systems (Cetinkaya et al.; 2019). According to Cameron

et al. (2019) availability is more critical than integrity and conﬁdentiality for

Smart Grid environments.

DDoS attacks are diﬃcult to defend against because of the large number

of machines that can be controlled by botnets and participate in an attack.

In consequence, an attack may be launched from many directions. A single

bot (compromised machine) sends a small amount of traﬃc which looks

legitimate, but the total traﬃc at the target from the whole botnet is very

high. This leads to an exhaustion of resources and disruption to legitimate

users (Mirkovic and Reiher (2004), Ranjan et al. (2009)). Another diﬃculty

is that the attack pattern may be changed frequently. Typically, only a

subset of botnet nodes conduct an attack at the same time (Belabed et al.;

2018). After a certain time, the botnet commander switches to another

subset of nodes that conduct the attack.

As pointed out by Zargar et al. (2013), there are basically two types of

DDoS ﬂooding attacks:

i) Disruption of a legitimate user’s connectivity by exhausting bandwidth,

router processing capacity or network resources. These are essentially link-

ﬂooding attacks. Within this group we have Coremelt attacks (Studer and

Perrig; 2009), and Crossﬁre attacks (Kang et al.; 2013). Both of these at-

tacks aim at intermediate network links located between attack sources and

targets. Traditional target-based defenses do not work with these types of

attacks (Liaskos and Ioannidis (2018), and Gkounis et al. (2016)).

ii) Disruption of a legitimate user’s service by exhausting server resources

(e.g., CPU, memory, bandwidth). These are essentially target-ﬂooding at-

tacks conducted at application layer.

This work addresses target-ﬂooding attacks with the assumption that

there are multiple targets.

Some other well-known attacks are: Reﬂector attacks (Ramanathan et al.;

2018) - an attacker sends a request with a fake address (of a victim) to DNS

server, and the server responds to the victim; Spoofed attacks (Armbruster

et al.; 2007) - an attacker forges the true origin of packets. Detailed classi-

ﬁcations of DDoS attacks are discussed in e.g., Mirkovic and Reiher (2004),

Douligeris and Mitrokotsa (2004), Peng et al. (2007), Zargar et al. (2013),

Bonguet and Bellaïche (2017), and Huseinović et al. (2020).

A detection algorithm of DDoS attacks and the identiﬁcation of an attack

signature is out of the scope of this research. In the literature one can ﬁnd

various works in this ﬁeld. Many works use machine learning or other artiﬁ-

cial intelligence techniques e.g., de Miranda Rios et al. (2021) use Multi-layer

Perceptron (MLP) neural network with backpropagation, K-Nearest Neigh-

bors (K-NN), Support Vector Machine (SVM) and Multinomial Naive Bayes

(MNB); Daya et al. (2020) incorporate graph-based features into machine

learning. Other works focus on general methods of anomaly detection, in-

cluding signature-based and proﬁle-based methods e.g., Huang et al. (2021)

propose a multi-channel network traﬃc anomaly detection method combined

with multi-scale decomposition; Hwang et al. (2020) present an anomaly traf-

ﬁc detection mechanism, which consists of a Convolutional Neural Network

(CNN) and an unsupervised deep learning model; Zang et al. (2019) use the

ant colony optimization (ACO) to construct the baseline proﬁle of the nor-

mal traﬃc behavior. Other related works are present e.g., Liu et al. (2021),

Gera and Battula (2018), Jiao et al. (2017), Zekri et al. (2017), de Assis

et al. (2017), Kallitsis et al. (2016), and Afek et al. (2013). Comprehensive

surveys of DDoS detection are also available: Jafarian et al. (2021) overview

anomaly detection mechanisms in software deﬁned networks; Khalaf et al.

(2019) focus on the defense methods that adopt artiﬁcial intelligence and

statistical approaches.

1.2 Sensor placement

One of the ways to defend against a DDoS attack is to place sensors in the

network which recognize and stop unauthorized demands. However, placing

such sensors in every node of the network would be very expensive and inef-

ﬁcient. Commercial IPS (Intrusion Prevention Systems)/Firewalls solutions

that detect and eliminate DDoS attacks have a high acquisition price (Fayaz

et al.; 2015)(Blazek et al.; 2019). Hence, a natural question arises concern-

ing what the number of sensors should be, and where they should be placed.

The detection precision may be higher closer to attack sources since it is

easier to detect spoofed addresses and other anomalies. On the other hand,

the traﬃc closer to targets is large enough to accurately recognize an actual

ﬂooding attack. In order to eﬃciently control the ﬂooding, sensors should

be placed in the core of the network, where most of the traﬃc can be ob-

served. A taxonomy of defense mechanisms against DDoS ﬂooding attacks -

including source-based, destination-based, network-based, and hybrid (a.k.a.

distributed) defense mechanisms is discussed in (Zargar et al.; 2013).

El Defrawy et al. (2007) formulate the problem of the optimal allocation

of DDoS ﬁlters. They model single-tier ﬁlter allocation as a 0-1 knapsack

problem and two-tier ﬁlter allocation as a cardinality-constrained knapsack.

However, both models assume a single victim, while the models in this study

allow for multiple victims.

Armbruster et al. (2007) analyze the problem of packet ﬁlter placement

to defend a network against spoofed denial of service attacks. They examine

the optimization problem (NP-hard) of ﬁnding a minimum cardinality set of

nodes (ﬁlter placements) that ﬁlter packets so that no spoofed packet (with

forged origin) can reach its destination. They relate the problem to the

vertex cover problem and identify topologies and routing policies for which

a polynomial-time solution to the minimum ﬁlter placement problem exists.

They prove that under certain routing conditions a greedy heuristic for the

ﬁlter placement problem yields an optimal solution. The paper addresses

speciﬁc version of DDoS - a Spoofed attack.

Jeong et al. (2004) and Islam et al. (2008) minimize the number of sensors

such that every path of a given length (r) contains a sensor. Any node less

than rhops away is permitted to attack another node, since the impact of

the attack is regarded as low, especially for a low r. This paper considers

the problem of sensor placement under a diﬀerent assumption.

Fayaz et al. (2015) propose a Bohatei system for DDoS defense within a

single ISP (Internet Service Provider). They use modern network architec-

tures - software-deﬁned networking (SDN) and network function virtualiza-

tion (NFV) and develop the system orchestration capability to defend against

a DDoS. The system addresses a resource management problem (NP-hard)

to determine the number and location of defense VMs (Virtual Machines).

These VMs detect and block attack traﬃc. After VMs are ﬁxed, the system

routes the traﬃc through these VMs. The goal of the resource manager is

to eﬃciently assign available network resources to the defense, (1) minimiz-

ing the latency experienced by legitimate traﬃc, and (2) minimizing network

congestion. The authors formulate an Integer Linear Program (ILP) to solve

the resource management problem. However, due to the long computation

time they apply hierarchical decomposition as well. For that purpose, they

designed two heuristics, the ﬁrst for data-center selection, and the second

for server selection at the data-center. When it comes to routing, this pa-

per doesn’t assume any speciﬁc routing protocol, it simply assumes that it

is multi-path. Additionally, traﬃc is not steered through a network; it is

assumed that routing is an independent problem.

Mowla et al. (2018) assume SDN architecture for their proposal. They

propose a cognitive detection and defense mechanism to distinguish DDoS

attacks and Flash Crowd traﬃc. The detection sensors are placed in the

OpenFlow Switches, where approaching traﬃc is identiﬁed and speciﬁc fea-

tures are extracted. The extracted data is handed over to the SDN controller

for analysis and production of security rules to defend against the attack.

They use two classiﬁcation techniques, namely SVM and Logistic Regres-

sion. It must be noted that such an approach has its drawbacks speciﬁcally,

a centralized SDN controller is a potential single-point-of-failure (security

risk).

Ramanathan et al. (2018) propose a collaboration system (SENSS) to

protect against DDoS. SENSS enables the victim of an attack to request an

attack monitoring and ﬁltering on demand from an ISP. Requests can be sent

both to the immediate and to remote ISPs, where SENSS servers are located.

The victim drives all the decisions, such as what to monitor and which actions

to take to mitigate attacks (e.g., monitor, allow, ﬁlter). The number and

location of monitoring sensors is not thoroughly analyzed in the research. For

certain types of attack (direct ﬂoods without transport/network signature),

the article suggests a location-based ﬁltering approach that compares traﬃc

volumes for ISP-ISP links during normal operation and during an attack.

Monnet et al. (2017) place control nodes (CN) in a clustered WSN (Wire-

less Sensor Network). CN detects abnormal behavior (DoS) and reports it

to a cluster leader up in the WSN hierarchy. The authors propose three

methods of CN placement. The ﬁrst uses a distributed self-election process.

A node chooses a pseudo-random number, checks the number against the

threshold and potentially self-elects itself as a CN. The second method is

based on the residual energy of nodes. Cluster heads select nodes with the

highest residual energy. The third method is based on democratic election.

Nodes vote for the nodes that will be selected as a CN.

A related problem, the design of sensor networks for measuring the sur-

rounding environment (natural ﬂoods, pollution etc.), is addressed in many

works. Khapalov (2010) addresses source location and sensor placement in

environmental monitoring. The ﬁrst problem here is linked to ﬁnding an un-

kown contamination source. The second concerns the placement of sensors

to obtain adequate data. Ucinski (2012) focuses on the design of a mon-

itoring sensor network to provide proper diagnostic information about the

functioning of a distributed parameter system. Patan (2012) determines a

scheduling policy for a sensor network monitoring a spatial domain in order

to identify unknown parameters of a distributed system. Suchanski et al.

(2020) study the dependency between density of a sensor network and map

quality in the radio environment map (REM) concept. There have been a

large number of works on developing methods and technology of person’s

activity recognition and monitoring. Some use wearable devices to collect

vital sign signals, some use video analysis and an accelerometer to recog-

nize the activity pattern, other use thermal sensors. The work Chou et al.

(2019) develops a framework to measure gait velocity (walking speed) us-

ing distributed tracking services deployed indoors (home, nursing institute).

The work aims to minimize the sensing errors caused by thermal noise and

overlapping sensing regions. The other goal is to minimize the data volume

to be stored or transmitted. One fundamental question is how many sen-

sors should be deployed and how these sensors work together seamlessly to

provide accurate gait velocity measurements.

In the literature there is well-known class of interdiction problems, which

can be related to our DDoS problem. Altner et al. (2010) study the Maximum

Flow Network Interdiction Problem (MFNIP). In the MFNIP a capacitated

s−t(directed) network is given, where each arc has a cost of deletion, and a

budget for deleting arcs. The objective is to choose a subset of arcs to delete,

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

ExactandapproximationalgorithmsforsensorplacementagainstDDoSattacksKonstantyJunosza-Szaniawski*DariuszNogalskiPaweªRz¡»ewskiAbstractInaDDoSattack(DistributedDenialofService),anattackergainscontrolofmanynetworkusersthroughavirus.Thenthecontrolleduserssendmanyrequeststoavictim,leadingtoitsresourcesb...

展开>> 收起<<

Exact and approximation algorithms for sensor placement against DDoS attacks Konstanty Junosza-SzaniawskiDariusz Nogalski.pdf

共30页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Exact and approximation algorithms for sensor placement against DDoS attacks Konstanty Junosza-SzaniawskiDariusz Nogalski

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: