A robust approach ofdetecting anomalous hosts
Network Anomaly Diagnosis Workshop 2006
Tatsuya Mori, Ryoichi Kawahara, Noriaki Kamiyama
NTT Service Integration Laboratories, Tokyo, JapanKeisuke Ishibashi
NTT Information Sharing Platform Laboratories, TokyoJapantatsuya@nttlabs.com
1Motivation
Anomalous hostA host whose behavior is not normalworm-infected hosts, bots







vertical, horizontal scanning

attackers or victims of DDoS
misconfigured servers
etc...

We need to find anomalous hosts
to protect users/customers
 to learn their characteristics


to create a new ACL/signature
to learn the dynamics/mechamisms
to make workload models
2Motivation cont.
 Problems:

anomalous activities could be buried
under the normal activities
Super spreader ≠ worm-infected hosts

public stratum-1 NTP server, TLD DNS server

We need a robust approach of
identifying anomalous hosts.

3

Idea


Characterizing communication pattern ofeach hostno payload information

can be extracted from NetFlow record

anomalous hosts exhibits intrinsic communicationpatternNaïve Bayes Classifier (NBC) for analyzingcommunication patternSimple approachcalculation cost is low while the accuracy is good

Robust identification
E.g., classifying spam messages
4Communication pattern of each hostWe analyze source IPs in this workDefinition of the communication patternFor each source IP:

A1: # of dst IPs / # of flows(0〜1)
A2: # of dst ports / # of flows (0〜1)
A3: # of acked dst IPs / # of dst IPs (0〜1)
A4: # of flows / # of packets (0〜1)

Other metrics were also consideredbogon ratio, src ports statistics etc.
 We chose the best 4 attributes in term of mutualinformation

5Communication pattern of each host

Merit

It can express concentration and dispersion easilymore rich and flexible than entropy-based
statistics


entropy-like statistics

E.g., mean #pkts / flow, bogon ratio etc.

DemeritIt needs to extract “cardinality” from massive flowdata

Some counting techniques such as probabilistic
counting or Bloom filter will be required.
6

Typical examples (mental model)
Worm-infected host

Large-scale web server

A* = {1,0,0,1}

A** = {0,1,1,0}
7

Measured data

1Gbps Internet backbone link

5 minutes of measurement

Number of source host = 116,889 (H) Number of host that generates more than
300 flows = 1,340 (H’)
Mean flow generation rate >= 1 fps

8Communication pattern
W0:
A set of heuristicallyextracted worm-infected
hosts1340 hosts were examined; # of W0 hosts was 269

NBC (1)Machine learning method based on Bayesian inferenceSupervised classification technique

Used in many network applications
 Spam filtering, passive OS fingerprinting, intrusion
detection etc.

Calculation cost is low linear to data sizeRobust classification

10

NBC (2)learning: likelihood probabilitythe probability that the attribute vector of a host is A,
given that the class of the host is Ci,classification : a priori probability
the probability that the class of a host is Ci, given thatthe attribute of the host is A (measured attribute)
 Bayse theorem + assumption of independence
ÆCi is obtained by the maximum a priori probability
(MAP)
11

Identification procedure
D1: training data D2: test data C1: class of worm-infected hosts C2: class of other hosts

Learning: Calculate the likelihood probability
P(A|Ci) for D1
 Classification: calculate the a priori probability
P(Ci|A) for D2
12

How to train the classifier inreality?
Problem : we don’t have complete labeled data ideal labeling : W Æ C1, H’＼W Æ C2
 Solution : heuristic labeling : W0 Æ C1, H’＼W0 Æ C2


H: total hosts
H’: target hosts
W: worm-infected hosts
W0: heuristically extracted worminfected hostsIf the #H’ >> #W0, this assumption holds
13Statistics of measured data

Total # of packets

14Likelihood probability P(A|C)
C1C215

Confusion matrix
estimated classlabeled class

Classified 46(=24+22) hosts as C1

Newly found 22 suspicious hosts (== W*)

Misidentified 1 host as C2 (false negative)
The host seems to communicate with a honeypot
16

Analysis of communication of W*

Extracted hosts that sends the packets withsome of these combinations to more than 300
destination addresses (1 address / sec)
Æ20 of 22 hosts matched the condition
the rest 2 hosts are also likely to be worm-infected17

Results for other data
Training data = D1
 Test data = D3
 measured at different network, 100Mbps
international backbone link, WIDE MAWI dataset

Estimated class

Labeled class

33
15

074
18

Results for other data cont.
Number of newly found suspicious hosts = 15
 Found unknown combination

TCP 445, ICMP, UDP 1028, TCP 80, UDP 137 etc.
 udp.1028 : Kilo, SubSARI or messenger spam (?)

14 of 15 hosts sent the packets with some ofthese combination to more than 900 dst hosts(1 address / seconds)

It is very likely that those newly found hosts
are worm-infected.

19

summary
Method of identifying anomalous hosts
was presented
 idea

communication pattern of each host leveraged the NBC

Validation through the measured data(for worm-infected hosts)
newly found (unknown) worm-infected hosts
 correctly classify the hosts whose attribute
vectors deviated from the typical pattern.
Æ thus, it is robust there exists estimation error Needs for better data set

20Future/ongoing workLabeling

in this work, we trained the classifier with heuristiclabeling
use the labeled + unlabeled data set for NBC

Improvement of the training dataClass of unlabeled item can be estimated with the EM
algorithm + NBC [NIGAM 99]

Coping with the honeypot etc.

Counting distinct elements efficientlydata streaming approach

K. Ishibashi et al., “Finding top N hosts in cardinality”,
IEEE NetDB 2006
T. Mori et al., “NetDelta”, submitted

21

Acknowledgement
This work was supported by Ministry of Internal Affairs
and Communications, Japan.

22