Collaborative Detection of Coordinated Port Scans

Sapienza Universit` a di Roma

Via Ariosto 25, I-00185 Roma, Italy

Collaborative Detection of Coordinated

Port Scans

Roberto Baldoni, Giuseppe Antonio Di Luna and Leonardo Querzoni [baldoni, diluna, querzoni]@dis.uniroma1.it

Midlab Technical Report 1/12 2012

Abstract

In this paper we analyze the coordinated port scan attack where a single adversary coordinates a Group of Attackers (GoA) in order to obtain information on a set of target networks. Such orchestration aims at avoiding Local Intrusion Detection Systems checks allowing each host of the GoA to send a very few number of probes to hosts of the target network. In order to detect this complex attack we pro- pose a collaborative architecture where each target network deploys local sensors that send alarms to a collaborative layer. This, in turn, correlates this data with the aim of (i) identifying coordinated attacks while (ii) reducing false positive alarms and (iii) correctly separating GoAs that act concurrently on overlapping targets. Locally deployed sensors adopt graph-based clustering techniques over non-established TCP connections to generate alarms. The collaborative layer employs a similarity approach to aggregate alarms and approximated optimiza- tion algorithms to separate distinct GoAs. The soundness of our ap- proach is tested on real network traces. Tests show that collaboration among networks domains is mandatory to achieve accurate detection of coordinated attacks and sharp separation between GoAs that execute concurrent attacks on the same targets.

1 Introduction

A port scan is a specific kind of malicious activity carried out by an adver- sary aimed at inspecting a target network for open hosts/ports. The final adversary goal is usually to identify possible vulnerabilities in the system that can be later exploited for realizing an intrusion. Detecting this kind of activity is thus fundamental for proper network protection. In order to avoid detection the adversary employs several decoying techniques aimed at obfuscating the presence of network packets generated by the port scan ac- tivity within the regular network traffic. One of such techniques consists in coordinating a group of geographically dispersed computers (i.e., the attack- ers) to split the scan activities. From a defender point of view this attack appears as a set of uncorrelated connections coming from independent ma- chines. Common network intrusion detection systems (IDSs) often fail in detecting such coordinated attacks and, in the best case, report it simply as separate scans produced by independent attackers. These coordinated attacks require high technical skill, thus, from the defender viewpoint, as- sessing the dimension of the attack can help in understanding the motivation and skill of the adversary.

Recently, Gates [8] proposed an offline solution for solving the problem of accurately identifying coordinated port scans executed against a single network domain and based on adversary modeling of the desired information gain. This solution clusters several different sources identified as scanners in order to provide a coherent view of the coordinated scan. Even though

results are quite encouraging, Gates’s solution could fail in identifying scans executed by groups of attackers (GoAs) targeting machines/ports located in different networks domains or, in the best case it could detect part of the attackers if the scan activity done in the single network domain is above some thresholds. Thus, as a matter of fact, the problem of providing an integrated solution to correctly identifying coordinated port scans that carry out their activities over multiple network domains is still an open problem.

This paper focuses on such type of coordinated port scans and provides a novel approach based on the collaboration among independent network domains. Our solution deploys a local system at each network domain that monitors and stores data on failed connections and, if the number of connec- tion errors within the network domain goes above a given threshold, triggers the construction of a local attack graph retrieving historical information on failed connections. Interestingly, the amount of information retrieved de- pends on the speed of the scan activity (e.g., if the threshold has been quickly reached, the scan activity is suspected to be fast, then failed con- nections within a small time window will be retrieved from storage). The local attack graph provides potential group of attackers at the collaborative layer. The latter collects all this information and builds a collaborative graph that identifies GoAs even if they are executing concurrent and (partially) overlapping scan activities. Contrarily to [8], this approach is on-line in the sense that it continuously monitors failed connections and, if there is a cer- tain amount of suspect scan activities on the network domain, it launches the next steps towards the detection of GoAs. The contributions presented in this paper are:

- a formal model of the local network domain that is able both to express an estimated failure threshold for coordinated port scans and to define a local graph that isolates potential attackers into connected components;

- concurrent use of graph clustering and separation techniques, similarity- based clustering [17] and Parallel Reactive GRASP [12] respectively, at the collaborative layer to identify and separate GoAs.

- the realization of a java-based prototype of the collaborative port scan de- tection system and its evaluation based on real runs and GoAs of 800 hosts.

An interesting outcome of the performance evaluation is a tradeoff between GoA detection accuracy and the number of network domains participating to the collaboration. In most of the cases (around 70%) the collaborative system is also able to separate concurrent GoAs of 200 hosts each. The rest of the paper is structured as follows: Section II presents the related work.

Section III provides an overview of the problem and Section IV introduces the network domain model. Section V presents the collaborative layer and Section VI the System Architecture. Section VII reports on the results of the evaluation and Section VIII points out limitations and future perspectives.

Finally, Section IX draws the conclusion of this work.

A

z1 z2 z3 z4 z5 z6 z7 z8

Adversary

Group of Attackers

Network Domain 1 Network Domain 2 Network Domain 3 Network Domain 1 Network Domain 2 User A

Attacker Adresses Adversary

Figure 1: (a) pattern of probes of an adversary that coordinates a set of attackers/zombies scanning addresses on multiple network domain; (b) pat- tern of probes of users contacting addresses of services on multiple network domain

2 Related Work

The idea of a coordinated port scan traces back to 1999 [9] even if it was not considered by literature on security till three years later. Apart from [8]

the other works that address it are:

Staniford et al. [14] in 2002 introduced the concept of distributed scan- ning and provided a solution constituted by two subsystems: a network anomaly detector (Spade) and a correlation engine (Spice). The paper does not propose any experimental results for the detection of coordinated port scan, so it is not clear how well this approach could be effective in our case study.

The solution proposed by Conti and Abdullah in [5] heavily relies on human-analysis to find suspicious patterns in the normal traffic, and it is not clear how those patterns will be modified by the normal network activity.

Robertson et al. [13] proposed a method for detecting coordinated port scans under the assumption that the attack sources are on the same subnet.

Even if this assumption sounds reasonable it somewhat limits the applica- bility of this solution.

A real collaborative project is Dshield [1]. DShield could be seen as a world-wide sensor network, that collects data coming from firewalls and IDSs of volunteers spread all over the world. Data collected by the DShield system is sent to the Internet Storm Center, inserted in the central database and analyzed by the staff.

Using data from DShield, Yegneswaran et al. [16] have done a

3 Problem Overview

The scenario we consider is constituted by several network domains, pos- sibly managed by independent administrators. An adversary is willing to obtain information on some addresses (ports) of the hosts (also called target addresses) within these networks using port scanning. Thus the adversary

coordinates a set of attackers by splitting the set of addresses in order each attacker has different targets to scan. This set is also called Group of At- tacker (GoA).

The adversary wants to obtain this information within a predefined time- frame, i.e. it is not willing to wait an unreasonable amount of time for a port scan to end; at the same time it wants to remain undetected, i.e. it doesn’t want network administrators to be able to correctly identify that separate scan activities are originated by a single adversary. Figure 1.a shows a pat- tern of such coordinated port scanning while Figure 1.b shows a normal use of network addresses by non-malicious activities. This figure could represent a pattern of requests sent to two web servers.On the administrator side, the goal is to collect and correlate enough information such that scan activities originating from different sources can be correctly clustered. Ideally, each cluster should contains scan sources pertaining only to a single GoA: the result should be both complete, all machines in the GoA are included in the cluster, and accurate, no machine external to the GoA is included in the cluster. IDSs deployed within networks can identify attacker only on the basis of local information and raise alarms. Sometimes this informa- tion is not enough to correctly separate distinct attacker or merge group of source addresses belonging to a single attack. To this aim, we advocate a cooperative approach: local network domains send their alarms toward a centralized coordination node, where this data is aggregate in order to have a more complete view on the composition of GoA and thus on the number of attackers.

4 Network Domain Model

A Network N can bee seen as a set of addresses N = {S

∀j∀cx^c_j} where c is the portnumber and and j is the hostname. The state of each address at a given time t can be closed, open or undefined (i.e. {c, o, u}). An address x^c_j is in the o state if at time t if it replies with a SYN-ACK to any SYN packet sent to it. If the state is c it means that the address replies with RST-ACK to any SYN packet. Finally, the address is in the u state if there is no active service on it or because there is a firewall blocking its connections. The function st : N → {c, o, u} maps each address of N to the corresponding state. Two addresses x^k_i, x^t_j belong to the same host if and only if i = j.

In the the following we consider an address x^c_j as k-active at time t if

∃t⁰ ∈ [t − k, t]|s_t⁰(x^c_j) = o. Otherwise x^c_j is k-closed. Therefore, we can define the two set of k − active K_t^a and k − closed K_t^caddresses.

4.1 Observer

The observer is an entity able to see and inspect any packet transmitted on the monitored network N and unable to monitor the attacker source network

N_A. The observer has limited computational power and can observe the network for a limited time window ∆o. As an example the observer can compute on-the-fly which ports are k − active and k − closed if k < ∆o. 4.2 Adversary

An adversary A is an entity that wants to know the state of a set of targets S in N . The set S can be build using a sampling function ψt: N → P(N ).

Commonly adopted ψ functions are [14]:

• ψ_v vertical scan: S = {x^c_j | j = h c ∈ P }. All the addresses belong to the same host.

• ψ_h horizontal scan: S = {x^c_j | c = h j ∈ H}. All the addresses share the same port but are distributed among different hosts.

• ψ_s strobe scan: S = {x^c_j | j ∈ H c ∈ P }. The same set of ports P is tested over a set of hosts H.

Let us remark that it is always possible for an adversary to use a sam- pling function ψk that is totally random. In the following, as in [8], we consider only adversaries that are carrying out scan activities using con- tiguous addresses as a target. In order to identify these specific sampling functions, we introduce the symbol ψ; two addresses x^k_j, x^t_i are contiguous if k − t = 1 ∧ i = j or k = t ∧ i − j = 1.

Each adversary A has a limited amount of time useful to accomplish the scanning. This assumption is reasonable because, as an example, the results of a scan can easily become useless if the scan lasts for a too long period. We call ∆_A the maximum time window in which the adversary is supposed to accomplish the scan. If c = |S| is the size of the target set we can define the minimum request rate that the adversary has to sustain during the scanning as:

ρ^c_A= c

∆A

4.3 Coordinated Port Scanning

A coordinated port scan is a port scan activity in which the target set S is probed by a set of attackers Z = {z₁, ..., z_n} orchestrated by the adversary A. The problem of the adversary is to carry out the coordinated port scan without being noticed by the observer which means that the number of probes sent by each attacker should be below a certain threshold.

We define the assignment function:

φ : Z → P(S)

This function assigns to each attacker z_j the set φ(z_j) containing the subset of addresses in S that zj will probe during the attack and such that S = Sn

j=1φ(zj).

We can now define the average number of probes for an attacker as:

cz =

n

X

j=1

|φ(z_j)|

|Z|

Here we assume that 0 < cz < ts where ts is the minimum number of requests that results in a scan detection by the observer.

4.4 Failures and Failure Network Threshold Let r^t_xc

j be the request done by an attacker at the address x^c_j at time t. We denote the outcome function o_t: R → O with O : {0, 1} as

o(r^t_x^c

j) =

(1, if s_t(x^c_j) ∈ {o}, 0, if st(x^c_j) ∈ {c, u}.

We will call failure a request r such that o(r) = 0. So we can divide the target set S in two subsets

St,f = {x^c_j ∈ S|o(r_x^tc j) = 0}

and S_t,s such that S = S_t,f ∪ S_t,s and S_t,s∩ S_t,f = ∅. According to [10], a majority of the connections executed during a scan activity results in failed connection attempts. This characteristics translates within our model in the following assumption:

|S_t,f| > |S_t,s|

We define expected failure density at time t of a port scan activity over S as:

ρ^S_t^f = |S_t,f|

|S| > 1

2 (1)

We define the k-closed density as:

ρ^H_t = |K_t^c∩ S_t,f|

|S_t,f|

In the following we consider as anomalous, a failure affecting a k-closed address. We are now in the position to compute the average rate of anomalous failures that the adversary will generate during its scanning activity

ρ^A_f^s =

Rt0+∆a

t0 ρ^H_t ρ^S_t^fdt

∆_a ρ^c_A

where t₀ is the starting time of the port scan t₀+ ∆_a is the ending time.

If ∆a is reasonably small (e.g. in the order of one day) and the target network behaves normally, we can assume that the parameters ρ^H_t and ρ^S_t^f will be constant. This is due to the fact that the majority of services behind the ports have lifetime much larger than ∆_a. Under this assumption we can simplify the previous formula as follows

ρ^A_f^s = ρ^H_t ρ^S_t^fρ^c_A

Let now consider an observer o using a time window size ∆_o and an adversary A carrying out a port scan activity over S. During this period the number of anomalous failures occurred within the network N and observed by o are:

P = ρ^A_f^s∆o

Since an observer can count the k − active addresses in a time window, it is possible to compute the density ρactive of k − active addresses over N . So the observer can estimate the density of k−closed addresses as 1−ρ_active, this implies for an adversary with a fixed request rate ρ^0c_A scanning the network N , that the observer should see during ∆oa number of failures that is (using (1))

P = ρ^0c_A(1 − ρ_active)∆_oρ^S_t^f ≥ t(ρ^0c_A, ∆_o) = ρ^0c_A(1 − ρ_active)∆_o 2

t(ρ^0c_A, ∆_o) represents the estimated failure threshold for the network and it is a function of both the observation window and the adversary rate.

In other words, this threshold is not considered for failures caused by single source attacks like in [8], but rather it is considered for all the failures happening in the observed network N .

4.5 Local Attack Graph

An attack executed against a network can be represented through a Source- Errors graph, namely Local Attack Graph LAG, that has some important properties. Assume A starts a coordinated port scan towards S ⊆ N at time t₀ and that this attack will end at time t₀+ ∆_A. Without loss of generality, let us assume that this attack is an horizontal port scan. Consider F^c, that is the set of connection failures directed towards a k-closed port c at time t₀+ ∆_a, and F^c(x), the subset of these failures generated by source x.

We define the Local Attack Graph LAG(V, E_ψ^p

h) where V = {z_j|∃r^t_xc

j ∈

F^c(zj)} and E_ψ^p

h = {(vj, vi) ∈ E_ψ^p

h|∃r^t_xc

k ∈ F^c(vj) ∧ ∃r_x^tc

t ∈ F^c(vi) ∧

near(x^c_k, x^c_t)}.

ip4 ip1

ip2 ip3 ip5

ipA

ipB ipB

ip2 ip1 ip4 ip3

(a) (b)

<ipC,h0> accept

<ip2,h1> drop

<ip3,h1> drop

<ip4,h1> drop

<ip1,h1> drop

<ipD,h0> accept

<ipE,h0> accept

<ipB,hx> drop

Failure History B

<ipE,h0> accept

<ipE,h0> accept

<ipC,h0> accept

<ip2,h1> drop

<ip3,h2> drop

<ip4,h3> drop

<ip1,h4> drop

<ipD,h0> accept

<ipE,h0> accept

<ip5,h5> drop<ipB,hx> drop

<ipA,hy> drop

Failure History A

<Src,Dst> outcame <Src,Dst> outcame

Figure 2: (a) Local Attack Graph obtained by the Failure history A (b) Local Attack Graph obtained by the Failure history A. In both graphs dmax

is equal to 2.

The near function is defined as:

near(x^c_k, x^c_t) =

(true if 0 < |{x^c_k, x^c_k+1, · · · , x^c_t}\K_t^o

0+∆_a| ≤ dmax

f alse otherwise

In other words, if we consider the list of failures there is an edge be- tween two nodes that failed a connection to a host in N if their addresses are contiguous according to the near function. As an example, Figure 2.a and Figure 2.b show two LAGs obtained from the failure histories a and b respectively. Note that if one host fails a connection to an address that is not contiguous to other failures then these hosts appear as isolated nodes in LAG (e.g., ipB and ipA in Figure 2.a). In the case there is no contiguity at all between any pair of failures we get the graph shown in Figure 2.b where all hosts are isolated. Let us now introduce the following lemma:

Lemma 1. Let G be the Local Attack Graph in case of coordinated port scan with sampling function ψ_h^p the following two properties hold:

(1) all the attackers that generated at least one anomalous failure are in G.

(2) all the attackers controlled by a same adversary are in the same connected component.

Proof. Property (1) follows by construction of V . Property (2) is proved by contradiction. Let us suppose that at least two partition V1 and V2 of V exist (i.e. V1, V2 ⊆ Z, and ∀i, j : z_i ∈ V₁, zj ∈ V₂, @ei,j ∈ E). Given the construction rules for E, this implies that @ r_x^tc

k ∈ F^c(V₁) ∧ r^t_x⁰c

t ∈ F^c(V₂) ∧

near(x^c_t, x^c_k). Since the scanned address space is contiguous and the attacker scans all the addresses in S, this is not possible (as the attacker needs to scan a semi-continuos set of k − closed addresses), thus the contradiction.

As a consequence, a contiguous coordinated port scan will create con- nected components inside the LAG. This brings to the following observa- tion: if a LAG shows connected components with high intra-edge density there is a suspect that a coordinated port scan is running. If we consider

Figure 2.a there is a connected component of hosts that can be suspected to be a (or a part of ) group of attackers. This is just a suspect because the connected component could be a false positive. Each suspect is reported as a potential group attack (PGA) alert constituted by a set of possible at- tackers at = {at1, at2, ..., atz} and for each attackers at_j the set of targets Tatj. As an example considering Figure 2.a, at = {ip1, ip2, ip3, ip4, ip5} and T_ip1 = {h4}, T_ip2 = {h1}, T_ip3 = {h2}. These potential alerts are sent to the collaborative layer described below.

5 Collaborative Layer Model

The LAG can be used to detect an attack carried out by an adversary that just probes addresses in that single network. However, if we consider an adversary A carrying out an attack through GoA Z against multiple networks domains, each single local attack graph contains only a partial view of the attack. By analyzing separately the LAGs information about the port scan could go undetected. More specifically the following issues arise at the single network domain level:

• (1) Detection of big attack communities: it is possible that the set of attackers available for the adversary is bigger than |N | (i.e. c_z < 1);

in this case the information collected within each single network is not sufficient to detect the entire GoA.

• (2) Separation of adversaries: assume that two adversaries owning two independent GoA Z1, Z2 decide to attack the same set of addresses at the same time; if c_z = 1 there is no way to distinguish attackers belonging to the two GoA using only information of a single network domain, since each possible partition of the attackers set would be arbitrary.

Collaborative Graph. We can mitigate these issues by introducing a collaborative layer where a set of network domains share information about PGA. This layer collects PGA alerts from local network domains and creates a Collaborative Graph CGc(V, E) that should be able to cluster and separate GoAs. In a collaborative graph V is the set of PGA alerts and two PGAs are connected by an edge if a measure of similarity between them is above a certain threshold δs. The edge is labeled with the list of the intersections of attackers. To express this notion of similarity, let us introduce the inter- alert similarity (IAS) between two alerts a₁, a₂. IAS is defined as the ratio between the union of targets of the intersection of attackers over the union of targets. i.e.,

IAS(a1, a2)=| ∪_{∀atj∈a1∩a2} T_atj|

| ∪_{∀ati∈a1∪a2} Tati|

Potential Group Attack Attackers Intersection

PGA1

PGA2 PGA3

PGA6 PGA7 PGA5

PGA4

PGAA PGA9

PGA8 PGAC

PGAB

Potential Group Attack

AlertID Attackers Targets

<PGA1, {a,b,c,1,...}, T_a={n1h1},T_b={n1h2},..>

<PGA2, {3,c,4,b,...}, T_3={n2h1},T_c={n2h2},..>

<PGA3, {4,3,c,1,...},T_4={n2h1},T_3={n2h2},..>

<PGA4, {3,4,c,x,...}, T_3={n2h1},T_4={n2h2},..>

<PGA5, {3,4,x,0,...}, T_3={n2h1},T_4={n2h2},..>

...

Figure 3: Cooperative Graph obtained by a list of potential group attack alerts got by the Network Domains. The list highlights potential group attack alerts PGA1,.., PGA5.

As an example let consider Figure 3, an edge is established between potential group attack alerts P GA1 and P GA2 that share the attackers {b, c}, each attacker has one target so in this case the cardinality of the union of targets it is equals to the cardinality of the union of attackers. This value is divided for the cardinality of the union of all targets in P GA1 and P GA2, the result is above the threshold and leads to the creation of the edge between P GA1 and P GA2 whose label is {b, c}.

Each time a new PGA alert gets to the collaborative layer, a node is added to the collaborative graph and its corresponding edges are created.

Periodically, a procedure is executed transforming the graph in order first to aggregate and then to separate group of attackers. The final aim of this procedure is to detect entire group of attackers and to separate two groups in case of concurrent attack. Below we describe the two main step of this procedure.

5.1 Group attack Aggregation

Once we have a Collaborative Graph, we need a mechanism that is capable to aggregate PGA alerts coming from Local Attack Graphs.

We employ a clustering algorithm on CG(V, E) that try to maximize the modularity [11], since the group of PGA alerts generated by the same attackers are likely to have an higher density of intra-cluster links. The clusters obtained in this way are then analyzed: if the set C obtained by the union of all the edge-sets covers a sufficient number of targets, then the cluster is collapsed; all the nodes are deleted and substituted with a supernode that contains the attackers in C and the relative targets. When this happens the set C is signaled as a group of attackers.

In order to trigger the collapsing behavior we need to introduce the intra-alert coverage (IAC) of a set of attackers C = {at₁, at₂, ..., at_z} over the PGA a as:

IAC(C,a)=| ∪_{∀atj∈C∩a}T_atj|

| ∪_∀ati∈aTati|

we allow the collapse only when the set of attackers in C covers at least a certain threshold ρiac of targets over at least a threshold ρalert of PGA alerts.

5.2 Separation of adversaries

The Group Attack aggregation step could merge two different GoAs, then we need a step that tries to check if this has been done and, in the affirmative, separate the two groups. We assume, as in [8], that the adversary will orchestrate the GoA attackers to maximize the scan coverage minimizing the intra scan overlap. So we define the Maximum Union Minimum Intersection problem as follows:

Definition 1 (definition MUMI). (Maximum Union Minimum Intersection) Consider a set of attackers A = {at₁, ..., at_z} each one associated with a set of targets T_atj = {t₁, ..., t_katj}. We want to find out the subset A^∗of attackers that maximize g(X) = | ∪∀atj∈X Tatj| − kP

∀at_j,ati∈X|T_atj ∩ T_ati| without violating the coverage constraint | ∪∀at_j∈A^∗T_atj| ≥ C with C ≤ | ∪_∀atj∈AT_atj| and with k > 0

Theorem 1. MUMI is not solvable in polynomial time.

Proof. Let us suppose to have an algorithm A that solves the MUMI prob- lem. Given an Instance I :< U, C > of Maximum Set Packing (MSP) [6] we can use A to solve MSP on I. From I we can build an instance I⁰ of MUMI in this way: we build a set W : {ek∈ W | ∃ C_i, Cj ∈ C ∧e_k∈ C_i∩C_j} . This can be done in at most O(|U ||C|) operations, for each element in U we check using a counter if it is present in more than two set, since a set have at most

|U | elements, we need to cycle at most |U | for each set. Now we need to cre- ate the attackers, we create an attacker atj for each set Cj in C. We create a target set T_atj for each attacker at_j, T_atj : ∪2|U |−|W ∩Cj|

i=1 e^at_i ^j ∪ {C_j ∩ W }.

Now we put the constant c = 0 and k ≥ 1 + 2|C||U | in this way k will be greater than the union of all Tatj since each of them contains 2|U | elements.

Now we can apply A to I⁰ obtaining the subset A^∗ from this set we can map-back to a subset C^∗ ⊆ C. Let us suppose by contradiction that the set C^∗ is not a correct solution for MSP, first of all this could happen if in C^∗ there are two set with non empty intersection Cj, Ci but that means that the two sets Tatj, Tati have at least one overlapping target x ∈ W . But at the same time A^∗ is a solution for MUMI so maximize g(X), but g(A^∗) − g(A^∗\ T_ati) < g(A^∗) − (g(A^∗) − (2|U | − 2|U ||C| − 1)) since Tati can contribute to the union with at most 2|U | elements and a malus of at least k. Now g(A^∗) − (g(A^∗) − (2|U | − 2|U ||C| − 1)) = 2|U |(1 − |C|) − 1 ≤ −1. So g(A^∗) − g(A^∗\ T_ati) < −1 < 0, contradiction! So we have that in C^∗ there are not intersections. Now let us suppose that C^∗ is not maximal for MSP on I this means that there one C⁰ with |C⁰| > |C^∗|, we can map this set to

A⁰ ⊆ A now g(A^∗) − g(A⁰) ≤ 2|U ||A^∗| − 2|U ||A⁰| < 0 contradiction. So C^∗ is a Maximum Set Packing on I. This instance transformation can be done in polynomial time so it is not possible to have a polynomial algorithm A that solves MUMI. Solving MUMI is at least as difficult as solving Maximum Set Packing. So MUMI is at least NP-Hard.

It is possible then to formulate MUMI using Integer Linear Programming [15] when all variables are in {0, 1}. Having the formulation of the MUMI problem in PLI, we can employ a greedy algorithm or meta heuristics to solve the problem such as the Parallel Reactive GRASP [7]. This will get to an approximated solution to MUMI that can be compared to the optimum thanks to the additional information on the upper bound obtained solving the relaxed formulation of the PLI problem [15].

Network Domain N Network Domain 2

Collaborative Analysis

-Similarity Based Clustering -Separation Algorithm

Graph status updates

Potential Group Attack (PGAs)

DB

Trigger (slow/normal/fast + port)

Network

Connection Sniffing Network Domain 1

Local Attack Graph

Slow Nor Fast

Failures History

Collaborative Graph

Failures Filtering

Failure Network Alert Generator

Failures

Console

Event Correlation

Figure 4: The overall architecture of the collaborative port scan detection system.

6 System Architecture

The architecture of our collaborative ports scan detection system, depicted in Figure 4, is constituted by a set of subsystems deployed within each con- trolled network domain and a collaborative layer.

Network domain level

The system is constituted at this level by three independent modules. In- formation sniffed on the local network infrastructure flows through these modules where it is analyzed and transformed in order to produce Potential Group Attacks (PGAs) for the collaborative layer.

Event correlation: this module is in charge of collecting data sniffed at the network level, filter and analyze it to detect possible anomalous activities.

More in detail, connection events sniffed at the network level are sent to- ward a Failures Filtering block. This block discards all regular connections and let only anomalous connections (failures) pass through it. Note that connection filtering is executed within this block by taking into account possible accidents that could easily raise the number of false positives. For example, the block discards failures happening on k-active addresses that recently become inactive as this is probably a sign of a failed local service still targeted by non-malicious connection attempts. The block also discards massive amounts of failures incoming from independent sources and directed to specific addresses as they are usually a consequence of transient miscon- figurations (e.g. some changes in a DSN directory). Failures that pass the filtering stage are directed towards the DB module and the Failure Network Alert Generator block.

The Failure Network Alert Generator block receives failures and keeps track of the number of connection attempts made toward k-closed addresses in multiple concurrent time-windows. These statistics are separately traced per port. Each counter is compared with thresholds calculated using the function t. Here we consider three kind of scan activities that we are inter- ested in tracing (that correspond to three different time windows):

Fast : a fast attacker wants to scan S, with ∆A limited to few minutes.

This kind of attack uses a scan rate ρ^c_A≥ 1^req_s , issuing a large number of errors in a small time window. To trace this kind of activity we can use a small sliding time window δf triggered when the errors are more than t(1^req_s , δ_f).

Normal : a normal attacker uses 1_min^req ≤ ρ^c_A < 1^req_s , with ∆A covering a time span of few hours. To detect these attacks a time window δn> δ_f is used. The value t(1_min^req, δ_f) is the threshold of this window.

Slow : a slow attacker uses a rate ρ^c_A<1_min^req, with ∆Alarger than ten hours.

In this case the threshold is computed using ^{(1−ρactive}₂ ^{)|N |}. At least half of all the k-closed addresses must be covered.

Every time a defined threshold is surpassed within a time window, this block triggers the Local Attack Graph module to create a new graph. DB: this module simply stores failures received from the Event correlation module;

in this way the system keeps track of local failure histories that will be used to build LAGs.

Local Attack Graph: this module is in charge of building the LAG. It is triggered by the Event correlation module every time some suspicious activ- ity (slow, normal or fast) is detected on a specific port. The LAG is built extracting historical information on past failures for that specific port from the DB and using on it the construction method detailed in Section 4.5. The module locally maintains data to compute the near function using a modi- fied version of the interval-tree; this allows efficient maintenance under the addition and removal of active ports using logarithmic operations for update and querying. The LAG is then examined to find suspicious agglomerates created using the Louvain¹ clustering algorithm [4]. Each cluster whose size is larger than a configurable threshold represents a PGA that is sent to the collaborative layer.

Collaborative layer

The collaborative layer is constituted by two modules: the Collaborative Analysis module and a Console. The former correlates and analyze PGAs in- coming from the various network domains producing a Collaborative Graph that contains information on running attacks; the latter is used to visualize the CG.

Collaborative Analysis: this module continuously maintains the CG using the pseudocode reported in Figure 5. Every time a new PGAs is received from a network domain it is added to the CG (line 01) and the edges are updated accordingly (lines 02-04). Periodically, the module checks if alerts contained in the CG can be grouped as single GoAs. This is done by ap- plying again the Louvain [4] clustering algorithm on the CG (line 06) that returns a set of clusters. If a cluster can be collapsed (following the poli- cies specified in Section 5) the module solves the MUMI problem using it as input in order to extract from it the attackers actually pertaining to the GoA. The approximate solution to MUMI is obtained using a reactive greedy randomized adaptive search procedure (*RGRASP) [12] where the stopping condition is true when the ratio of new covered elements over the overlap- ping elements is less or equal to a threshold k, while the probability for the parameter αj is defined as P (αj) = solαj/P

∀isolαi where solαj is the av- erage of all the solutions found using αj. We slightly modified the original RGRASP adding one step after the local search procedure: the idea is to run the randomized greedy until the stopping condition is satisfied; then, as in the original GRASP we run the local search to improve the solution found so far. The result of the search procedure is improved using one more step of randomized greedy, then this solution is used to feed a local search and so on till we reach a local maximum. The rationale in this procedure

1The Louvain algorithm has been selected since it is considered one of the fastest available method for community detection and, according to the authors, it scales well on graphs of large size.

Global Variables:

A: set of PGA alerts

CG(V,E): collaborative graph

When a new PGA a is received:

(01) V ← V ∪ a

(02) for each alert e ∈ A do (03) if (IAS(e,a)> δs) (04) E ← E ∪ {e,a⁰} (05) A ← A ∪ a

Periodically executed:

(06) Clusters ← cluster(CG)

(07) for each cluster c ∈ Clusters do (08) if c can be collapsed

(09) g ← solve MUMI on c (10) for each alert a ∈ c do

(11) remove from a every attacker at ∈ g (12) V ← C ∪ a new alert a⁰ containing g (13) for each alert e ∈ A do

(14) if (IAS(e,a⁰)> δs) (15) E ← E ∪ {e,a⁰} (16) A ← A ∪ a⁰

Figure 5: Collaborative analysis algorithm

is that the local search procedure could improve the solution selected by the randomized greedy removing a conflicting attacker; this could lead to the addition of a new attacker that now does not conflict with the solution obtained after the local search. After a solution to MUMI has been found, we create from this set of attackers a new node in the CG (this is like a new alert) that correspond to a GoA (lines 12-16). The attackers included in this GoA are removed from other alerts that remain the in the CG (lines 10-11).

The choice of *RGRASP has been done after an evaluation of this meta- heuristic against a greedy algorithm and the original RGRASP. Results of this comparison can be found in Section 7.

System prototype: We realized a prototype of the system in java using Jung libraries [3] for the visualization and graph manipulation. The event corre- lation module has been developed using Esper Complex Event Processing system [2]. The output of the system is a human-readable form of the CG that is generated by a Console module. The console could easily be substi- tuted by more complex reactive systems that, by inspecting changes in the CG would trigger adequate automatic responses (e.g. the addition of rules to a firewall).

7 Evaluation

This section provides an evaluation of a prototype implementation of the proposed system with respect to its ability to correctly identify coordinated port scan activities.

7.1 Input data

In order to feed the system with realistic data we collected several traces from the firewall deployed at the edge of the DMZ network of a large academic institution². The traces globally contain data collected during three days of activity, from november 4^th to november 7^th, 2011. The network where activity was traced includes web-servers of the institution and many other public services available from outside, (email server, ftp, etc.). Each TCP connection in a trace is represented as a tuple <source,destination> with an associated timestamp with granularity up to seconds, and state information (Dropped or Accepted). With respect to our model a dropped connection is considered as a connection to a closed port, while an accepted connection is a connection towards an open service.

Note that we had no way to clearly detect the presence of coordinated port scan activities in the traces but to run our solution on it. We decided to purposely inject such activities within the traces to simulate the presence of (multiple) adversaries. Gates [8] quotes two softwares for distributed port scan that are DSCAN and NSAT. To the best of our knowledge, these software are currently not publicly available. For this reason we wrote a coordinated port scan simulator tool that, taking a trace as input, inserts coordinated port scan activities in it. It is possible to tune the simulator specifying parameters like the number of adversaries, the scan rate, the size of the GoAs, and the targets. The tool uses an random assignment of targets that tries to balance the number of requests for each attackers minimizing c_z. In order to mimic a collaborative scenario we used the available traces as if they were extracted from different network domains.

7.2 Measures of interest

The two main characteristics of the proposed solution we want to evaluate are its capability in isolating GoAs that are larger than the target network and its effectiveness in correctly identifying multiple adversaries whose tar- gets overlap. Before performing these test, we evaluate different solvers us- able to implement step 09 of the collaborative layer algorithm (cfr. Figure 5).

2A precise reference to the institution has been removed for double blind review pur- poses

We define the Intra Cluster Detection (ICD) of GoA Z for a CG node V as the ratio ^{|Z∩V |}_|A| . The ICD will be 1 if all the attackers in Z have been detected and inserted in the right node.

In order to measure the system ability to correctly separate concur- rent attacks we can start computing the ICD for all the GoAs Zj present in a same CG node V , i.e. ICD(Z_j, V ). Intuitively a bad separation of distinct GoAs within V will lead to similar values for their ICDs, while with a good separation only one GoA will sport an ICD value close to one, while all the other ICDs will be close to zero. Therefore, the sum H(V ) =P

∀Zj∈V −ICD(Z_j, V )Log(ICD(Z_j, V )) is larger with a bad sepa- ration and zero if the node is homogeneous, i.e. it includes attackers from a single GoA. We normalize that value obtaining H(V ) and compute the converse D(V ) = 1 − H(V ). The value for D(V ) will be close to one when GoAs are well separated and close to zero when the attackers present in the CG node are equally distributed between various GoAs (bad separation).

7.3 Experimental results

0,6 0,65 0,7 0,75 0,8 0,85 0,9 0,95 1

0 5 10 15 20 25

Approximation of the optimum

Time (runs)

*RGRASP RGRASP Greedy

Figure 6: Comparison among three different approaches used to solve MUMI: Modified RGRASP, RGRASP and Greedy.

Solvers comparison

The solver used within the collaborative layer to find an approximate solu- tion to MUMI has an impact on the global performance of the system as it separates GoAs collapsed in a singe CG node. In Section 6 we defined

*RGRASP, a variation of the standard RGRASP solver that was designed ad-hoc for the peculiarities of the MUMI problem. During our evaluation we compared *RGRASP with both a standard RGRASP implementation and a simple Greedy approach. The results are reported in Figure 6. The graph shows how much the solutions provided by each solver were distant from the optimum during the execution of a test that involved multiple sub- sequent runs of the algorithm. Clearly the Greedy approach is the worst performer as the quality of its solutions varies a lot among the various runs.

The standard RGRASP approach provides much better solutions that are usually close to the optimum. *RGRASP positively adapts RGRASP to the MUMI problem providing solutions that are always close to the optimum and often coincide with it.

0,0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1,0

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

ICD

Number of network domains

Cz=2 Cz=1 Cz=0.6 Cz=0.5

Figure 7: Intra-Cluster Detection with ρ_iac= 0.85, ρ_alert = 0.9

0,0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1,0

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

ICD

Number of network domains

Cz=2 Cz=1 Cz=0.6 Cz=0.5

Figure 8: Intra-Cluster Detection with ρ_iac= 0.7, ρ_alert= 0.7

Detection of GoAs

In this experiment we test the behaviour of the system considering a GoA Z that scans twenty network domains. The target dimension |S| is limited to 200 addresses. We varied both the size of the GoA by tuning c_z and the parameters ρ_iac and ρ_alert used to configure the CG clustering. The three Figures 7, and 8 report results obtained setting ρiac = 0.85, 0.7 and ρ_alert = 0.9, 0.7 respectively. Each graph plots the values for c_z = 2, 1, 0.6 and 0.5.

The results show that, for a given configuration (e.g. ρiac = 0.7 and ρ_alert = 0.7) the system requires information incoming from a larger number of network domains to identify GoAs (c_z = 0.5, 0.6), while smaller GoAs (cz = 2) can be easily identified using data incoming from few domains.

The impact ρ_iac and ρ_alert have on the results is less intuitive. By in- creasing their values toward one, we are tuning the collaborative layer to be more “picky” in the selection of attackers that form an identified GoA; as a consequence, if the GoA is large (e.g. cz = 0.5) it takes a larger amount of information for the system to isolate it, but, once the GoA is identified, in- formation about almost all its attackers is already available in the CG. This accounts for the results that show how the ICD value increase for larger number of domains but at a very steep rate, quickly reaching values close to one (cfr. Figure 7). Conversely, by decreasing the values of the two ρ param- eters, we choose to have a system that reacts quicker to potential attacks starting to isolate GoAs as soon as information from few network domains is available; on the other side, “early” isolation of GoAs comes at a price:

most detections happens with incomplete information about the GoAs as it is shown by the slower growth rate of the curves reported in Figure 8.

Overlap size CG nodes D(V ) 20 V1 = (|Z1| = 198, |Z₂| = 0) D(V1) = 1

V2 = (|Z1| = 1, |Z₂| = 200) D(V2) = 0.95 17 V1 = (|Z1| = 200, |Z₂| = 2) D(V1) = 0.91

V₂ = (|Z₁| = 0, |Z₂| = 198) D(V₂) = 1 15 V₁ = (|Z₁| = 199, |Z₂| = 15) D(V₁) = 0.62

V₂ = (|Z₁| = 16, |Z₂| = 199) D(V₂) = 0.62 13 V₁ = (|Z₁| = 200, |Z₂| = 16) D(V₁) = 0.62

V2 = (|Z1| = 0, |Z₂| = 80) D(V2) = 1 11 V1 = (|Z1| = 177, |Z₂| = 6) D(V1) = 0.79

V2 = (|Z1| = 0, |Z₂| = 200) D(V2) = 1 9 V1 = (|Z1| = 98, |Z₂| = 158) D(V1) = 0.03 7 V1 = (|Z1| = 91, |Z₂| = 151) D(V1) = 0.04 5 V1 = (|Z1| = 186, |Z₂| = 129) D(V1) = 0.02 1 V1 = (|Z1| = 192, |Z₂| = 0) D(V1) = 1

V2 = (|Z1| = 0, |Z₂| = 193) D(V2) = 1 0 V1 = (|Z1| = 199, |Z₂| = 0) D(V1) = 1 V₂ = (|Z₁| = 0, |Z₂| = 198) D(V₂) = 1

Table 1: Results of experiments on GoA separation. The overlap size in- dicates the number of shared target network domains in the adversaries’

targets. The total number of domains is 20. Each CG node is summarized as a list of cardinality for the detected GoAs.

Separation of GoAs

The other aspect of our system is the possibility to correctly identify two adversaries attacking concurrently the same targets. We tested this feature using 20 network domains and running different tests where we vary the amount of network domains where the targets of the two adversaries over- lap. As Table 1 shows the separation is sharp in the most cases proving the effectiveness of our approach in identifying concurrent coordinated port scans. Some difficulties arise when the target overlap happens on few do- mains. In these cases the system is not able to clearly separate the GoAs and create in the CG a single node containing a mix of attackers from both GoAs. Let us recall that within the MUMI problem formulation a param- eter k is present that assigns a malus for the presence in a same CG node of two different attackers that share some targets. Tests reported in Table 1 has been performed setting k = 2.0. This lead to the bad behaviour re- ported above when the cardinality of the overlap is above half of the union of the targets. By tweaking the value of k it would be possible to take into account these specific scenarios and still obtain an effective GoA separation.

However, larger k values could bring into play undesired side effects like the partitioning of a single GoA in two CG nodes.

8 Limitation, Conclusion and Future work

In this paper we presented a new approach for collaborative detection of coordinated port scans over multiple network domains. Despite the encour- aging results reported in Section VII, the proposed solution still shows some limitations that could be exploited by skilled adversaries to avoid the detec- tion.

Target Contiguity: the system assumes that the target set of an attack contains contiguous addresses. The presence of dmax mitigates this problem as attackers that have probed addresses that are not strictly contiguous will be still considered as neighbors in the local graph.

Collaboration among network domains: the system is designed to leverage information coming from different network domains to detect co- ordinated port scans.The collaborative layer, in fact, is totally useless when the adversary is acting only against one network domain.

Botnet-based GoAs: if the adversary controls a huge GoA, for example one based on a large-scale botnet, it could be capable of generating a single probe per attacker. In this way all the PGAs generated by network domains will be fully uncorrelated, hampering the possibility to identify the GoA at the collaborative layer.

Very slow attackers: an adversary willing to use a time-window larger than the observer maximum window will avoid detection in the network domain.

As a future direction for the evolution of this work, we are interested in devising new correlation methods, possibly based on characteristics of the scan activities that have not been considered in this work, that would make the system capable of solving some of the previous limitations.

References

[1] DShield: Cooperative Network Security Community - Internet Security.

http://www.dshield.org/indexd.html/, 2009.

[2] Esper. http://esper.codehaus.org/, 2011.

[3] Jung. http://jung.sourceforge.net/, 2011.

[4] V.D. Blondel, J.L. Guillaume, R. Lambiotte, and E.L.J.S. Mech. Fast unfolding of communities in large networks. J. Stat. Mech, page P10008, 2008.

[5] G. Conti and K. Abdullah. Passive visual fingerprinting of network attack tools. In Proceedings of the 2004 ACM workshop on Visualization and data mining for computer security, VizSEC/DMSEC ’04, pages 45–

54, New York, NY, USA, 2004. ACM.

[6] P. Crescenzi and V. Kann. A compendium of NP optimization prob- lems. 1998.

[7] T.A. Feo and M.G.C. Resende. A probabilistic heuristic for compu- tationally difficult set covering problems. Operation Research Letters, pages 67–71, 1989.

[8] C. Gates. Coordinated scan detection. In Proceedings of the 16th An- nual Network and Distributed System Security Symposium (NDSS 09), 2009.

[9] hybrid. Distributed Information Gathering. http://www.phrack.org/

issues.html?issue=55&id=9, 2011.

[10] W. John, S. Tafvelin, and T. Olovsson. Trends and differences in connection-behavior within classes of internet backbone traffic. In Pro- ceedings of the 9th international conference on Passive and active net- work measurement, PAM’08, pages 192–201, Berlin, Heidelberg, 2008.

Springer-Verlag.

[11] M. E. J. Newman. Modularity and community structure in networks.

Proceedings of the National Academy of Sciences, 103(23):8577–8582, June 2006.

[12] M. Prais and C. C. Ribeiro. Reactive grasp: An application to a matrix decomposition problem in tdma traffic assignment. INFORMS Journal on Computing, 12:164–176, 1998.

[13] S. Robertson, E. V. Siegel, M. Miller, and S. J. Stolfo. Surveillance detection in high bandwidth environments. In In Proceedings of the 2003 DARPA DISCEX III Conference, pages 229–238. IEEE Press, 2003.

[14] S. Staniford, J. A. Hoagland, and J. M. Mcalerney. Practical automated detection of stealthy portscans. Journal of Computer Security, 10:105–

136, 2002.

[15] V. V.Vazirani. Approximation Algorithms. Springer, 2001.

[16] V. Yegneswaran, P. Barford, and J. Ullrich. Internet intrusions: global characteristics and prevalence. SIGMETRICS Perform. Eval. Rev., 31:138–147, June 2003.

[17] C. V. Zhou, C. Leckie, and S. Karunasekera. A survey of coordinated attacks and collaborative intrusion detection. Computer and Security 29 (2010), pages 124–140, 2009.