Transcript Packet Rule Classification

Rule-based Anomaly Detection
on IP Flows
Nick Duffield, Partick Haffner, Balachander
Krishnamurthy (AT&T),
Haakon Ringberg (Princeton Univ.)
INFOCOM’09
Snort
Snort is a powerful, flexible open source NIDS
 Rule-based Anomaly Detection on Packets


A Snort rule:
Rule actions

Source IP & port direction
Destination IP & port
alert udp $EXTERNAL_NET any -> $HOME_NET 1434
(msg:"MS-SQL version ove…"; dsize:>100; content:"|04|"; …)
Detail of rule
2009/4/9
protocol
Message text
Packet size
Speaker: Li-Ming Chen
Patterns in packet’s payload
2
Challenge for deploying Snort over a
Large Network (e.g., a Tier-1 ISP)

Deploy at the edge:



Deploy at the core:



Network scale is huge
 Deployment issues
Links capacity is high
 Performance issues
Hundreds of rules may need to be operated
concurrently for each packet
2009/4/9
Speaker: Li-Ming Chen
3
Idea: Rules for IP Flows !

Does it possible to construct rules at the flow
level that accurately reproduce the action of
packet-level rules ?


e.g., alerts should be raised for a flow, if some packets
of this flow trigger packet-level rules
Why?

Easy to have IP flows


2009/4/9
ISPs already collect flow statistics ubiquitously (e.g., NetFlow)
More scalable
Speaker: Li-Ming Chen
4
Think about Rules for IP Flows…

If packet-level rule looks like:


alert udp $EXTERNAL_NET any -> $HOME_NET 1434 (msg:"MSSQL version ove…"; dsize:>100; content:"|04|"; …)
In flow-level, maybe we can do:

Alert UDP flows come from $EXTERNAL_NET to $HOME_NET at port
1434 with mean packet size larger than 100

Yes, we ignore the content !!

Although we don’t know the exact packet size, we can measure
mean packet size of each flow !?
 What’s the detection accuracy !?
 Can we LEARN this kind of events (to cover the missed
content signature)?
2009/4/9
Speaker: Li-Ming Chen
5
Motivation & Goal

For NIDS, inspecting every packet would be
ideal, but impractical


Signature-based NIDS has scale and performance
problems
Goal: develop an architecture that can translate
many existing packet signature to instead
operate effectively on IP flows

2009/4/9
Premise: flow statistics are compact and collected
within most ISPs’ network
Speaker: Li-Ming Chen
6
Build Flow Rules via Learning


Authors use machine learning (ML) approaches
to learn the association between flow features
and packet payload
Problem:



2009/4/9
Flows: aggregate packet header information, while
lose payload information
 Flow rules: loss of accuracy !?
 Does ML mitigate the impact of losing payload
information !?
Speaker: Li-Ming Chen
7
Outline

Motivation & Goal

Packet Rule Classification

Packet Rules  Flow Rules

Dataset & Evaluation Methodology

Experimental Results

Real Deployment Issues

Conclusion & My Comments
2009/4/9
Speaker: Li-Ming Chen
8
Why to classify packet rules?
Packet Rule Classification (1/3)

Not all packet rules can be effectively learned…

Using a taxonomy of packet rules to understand their
impacts, and
Evaluate the performance of proposed ML-method

For example, to know which kind of rules:




2009/4/9
ML-method can learn perfectly …
ML-method is likely to learn very well …
The accuracy of ML-method varies based on the nature of the
rule…
Speaker: Li-Ming Chen
9
What kinds of predicates in a packet rule?
Packet Rule Classification (2/3)

3 set of predicates consist a packet rule



FH (flow header): packet fields exactly reported in the flow
record
PP (packet payload): content signature
MI (meta information): other packet header information that
is reported either inexactly or not at all in the flow record
(FH)
(FH)
(FH)
(FH)
(FH)
alert udp $EXTERNAL_NET any -> $HOME_NET 1434
(msg:"MS-SQL version ove…"; dsize:>100; content:"|04|"; …)
(MI)
2009/4/9
Speaker: Li-Ming Chen
(PP)
10
How to classify packet rules?
Packet Rule Classification (3/3)


Partition packet rules into disjoint classes
Classify rules based on types of predicates present
Other rules (no PP,
do have MI,
may include FH)
Rules comprise
only FH predicates
rule
Rules include at least
one PP predicates
2009/4/9
Speaker: Li-Ming Chen
11
Outline

Motivation & Goal

Packet Rule Classification

Packet Rules  Flow Rules

Dataset & Evaluation Methodology

Experimental Results

Real Deployment Issues

Conclusion & My Comments
2009/4/9
Speaker: Li-Ming Chen
12
Rules in Practice
FH, MI & PP

Snort rules:


A Boolean formula composed of predicates that check for
specific values of various fields present in the IP header,
transport header, and payload
Features used to construct flow rules in this paper:

Src. port, Dst. port,

Src. IP address, Dst. IP address,

#packets, #bytes, mean packet size,

duration, mean packet interarrival time,

TCP flags, protocol, ToS.
2009/4/9
Speaker: Li-Ming Chen
13
Packet Rules  Flow Rules
Packets
…
Snort
Snort alerts
e.g., NetFlow
IP flows
Build
training
data
(associate the packet alert
with the corresponding flow)
2009/4/9
Speaker: Li-Ming Chen
ML
-method
Flow
rules
14
Packet Rules  Flow Rules (detailed)

Note that



A single packet may raise multiple Snort alerts
 a flow may associate with many Snort alerts
For each Snort rule,

Training data (xi, yi): flow i has flow features xi, and yi = {–1, 1}.
threshold
Training
error
2009/4/9
Attribute to each Snort rule a score over
flow level predicates pk(x).
Learn these weights to minimize training error.
Speaker: Li-Ming Chen
15
Learning Flow Rules

Machine learning algorithms

2009/4/9
Choose AdaBoost as the candidate algorithm
 Due to, actual number of features is large
 AdaBoost use incremental greedy training
procedure to only adds features needed for finer
discrimination
 Good generalization (than SVM)
 Low level of noise in the training data
Speaker: Li-Ming Chen
16
Outline

Motivation & Goal

Packet Rule Classification

Packet Rules  Flow Rules

Dataset & Evaluation Methodology

Experimental Results

Real Deployment Issues

Conclusion & My Comments
2009/4/9
Speaker: Li-Ming Chen
17
Dataset (during Aug ~ Sep 2005)
OC-3 link
border router

29 days (4 weeks)
Total: >106 flows, >5 TBytes.
Average rate: 2 MBytes/sec.
Average: 14.5 pkt/flow.
55% of flows comprised 1 pkt !

For machine learning:



(all)
Packets
unsampled
NetFlow


IP flows


2009/4/9
Week 1: training
Week 2: training & testing
Week 3 & 4: testing
Speaker: Li-Ming Chen
18
Dataset (learning performance…!?)
Number of flows (106) per week
Normal flows:
Anomalous flows:
(Neg: True Negative, Pos: True Positive)
Amount of unique examples is small
( speed up training)
(further speed up?)
2009/4/9
Speaker: Li-Ming Chen
19
Evaluation Criteria


A detection is a boolean action (T or F ?)
For each rule, we get a confidence score after
testing by a classifier


 require an threshold to determine T or F
Use precision and recall as evaluation criteria

Precision = TPk/(TPk + FPk)

Average Precision =>
 value closer to 1 is better !
2009/4/9
Speaker: Li-Ming Chen
20
Evaluation Methodology

Focus on 21 most triggered rules over wk 1 & 2


Refer to next slide!
Compare the AP (Avg. Precisions) for:

1) Baseline behavior



2) Data drift


Determine how often re-training should be applied (e.g., wk1-3)
3) Sampling of negative example


2009/4/9
Training on one full week and testing on the subsequent week
E.g., wk1-2  training on wk 1 and testing on wk 2.
Normal flows are the majority
Reduce normal flows keep accuracy while reduce training
time !?
Speaker: Li-Ming Chen
21
(Snort alerts)
Show the
complexity
of a unique
flow
1
3
4
ICMP content?
flag
size
flag
9
10
15
20
2009/4/9
Speaker: Li-Ming Chen
22
Header
1
Data Draft:
• 2-week drift is acceptable
3
• 3-week drift  loss of performance
Meta-Info
especially
for Meta-Info & Payload
4
9
Payload
10
 Payload rules show great variability
15
2009/4/9
20
Speaker: Li-Ming Chen
23
Header
1
Sampling of Negative (normal) Example:
• measurable loss in performance
3
• while 6x faster in training
Meta-Info
4
9
Payload
10
15
2009/4/9
20
Speaker: Li-Ming Chen
24
What features are more important than
others?
Feature is removed during detection
Payload rules are hard to reproduced
in a flow setting.
• some rules have several predicates
(that could be learned)
2009/4/9
Speaker: Li-Ming Chen
25
Outline

Motivation & Goal

Packet Rule Classification

Packet Rules  Flow Rules

Dataset & Evaluation Methodology

Experimental Results

Real Deployment Issues

Conclusion & My Comments
2009/4/9
Speaker: Li-Ming Chen
26
Architecture

Other issues:


2009/4/9
Can rules learned from a site be used for other sites?
Some flow features (e.g., duration) are link/network
dependent…
Speaker: Li-Ming Chen
27
Other issues

Computational efficiency



2009/4/9
Initial correlation of Flows and Snort Alarms
AdaBoost parameter setup, and learning time
Run-time classification
Speaker: Li-Ming Chen
28
Conclusion

Propose an ML approach to reproduce packet
level alerts for anomaly detection at the flow
level.



Classification of flow-level rules according to whether
they act on packet header, payload or meta-info is a
good qualitative predictor of average precision.
Learning time will not affect the detection (Data Drift)
Propose an architecture and discuss the
computation complexity
2009/4/9
Speaker: Li-Ming Chen
29
My Comments

Only focus on single packet alarms produced by Snort


Packet classification is not scalable but “just in time”




Other complex rules? (e.g., Bro rules)
Payload signature is usually used to block malicious attack
immediately
Flow rule checking must wait for flow termination
Like packet classification but more simple (only True or
False)
Data reduction & forensics



2009/4/9
Recording flows/packets that trigger alerts is not suitable for
network forensics
Can support attack diagnosis
Successful infections usually not generate alerts
Speaker: Li-Ming Chen
30