An Overview of Evading Anomaly Detection using Variance Injection Attacks on PCA
E
v
a
d
i
n
g
A
n
o
m
a
r
l
y
D
e
t
e
c
t
i
o
n
t
h
r
o
u
g
h
V
a
r
i
a
n
c
e
I
n
j
e
c
t
i
o
n
A
t
t
a
c
k
s
o
n
P
C
A
Benjamin I.P. Rubinstein, Blaine Nelson, Anthony
D. Joseph, Shing-hon Lau, NinaTaft, J. D. Tygar
R
A
I
D
2
0
0
8
Presented by: Dong-Jae Shin
•
Background
•
Machine Learning
•
PCA (Principal Component Analysis)
•
Related Work
•
Motivation
•
Main Idea
•
Evaluation
•
Conclusion
•
Future work
2
•
Machine learning (ML)
•
Design and develop algorithms by machine using patterns or
predictions
•
Benefits
•
Adaptability
•
Scalable
•
Statistical decision-making
3
1.
Background
http://1.bp.blogspot.com/-tn9GwuoC45w/TvtQvP6_UFI/AAAAAAAAAHI/ECpLGjyH6AI/s1600/machine_learning_course.png
•
Deriving principal vectors
•
Deriving the principal vector which captures the
maximum variance
•
Find next component
•
PCA (Principal Component Analysis)
•
Orthogonal transformation to
reduce dimension
•
Most
data patterns
are captured by the
several principal vectors
4
1.
Background
PCA
D
a
t
a
p
r
e
s
e
r
v
a
t
i
o
n
(
n
o
t
p
e
r
f
e
c
t
l
y
)
•
PCA Example
5
1.
Background
http://kimhj8574.egloos.com/5632409
Original coordinates
PCA
New coordinates
Projection to 1
st
basis
(maximum variance)
Projection to 2
nd
basis
(next maximum variance)
M
a
x
i
m
u
m
v
a
r
i
a
n
c
e
m
e
a
n
s
g
o
o
d
p
r
e
s
e
r
v
a
t
i
o
n
o
f
i
n
f
o
r
m
a
t
i
o
n
D
i
m
e
n
s
i
o
n
r
e
d
u
c
t
i
o
n
u
s
i
n
g
i
m
p
o
r
t
a
n
t
b
a
s
e
s
>
M
o
r
e
p
r
e
s
e
r
v
e
d
d
a
t
a
•
Goal
•
D
i
a
g
n
o
s
i
n
g
n
e
t
w
o
r
k
-
w
i
d
e
a
n
o
m
a
l
i
e
s
•
Problem
•
Detecting anomalies are difficult because of large amount of
high-
dimensional
and
noisy data
6
2.
Related Work
Attack
Normal Data
A
n
o
m
a
l
y
•
A pattern in the data that does
not
conform to the
expected behavior
•
Example of Link Traffic
7
2.
Related Work
O
D
f
l
o
w
•
Origin-Destination flow
between PoPs
T
o
o
m
u
c
h
c
o
m
p
l
e
x
i
t
y
t
o
m
o
n
i
t
o
r
e
v
e
r
y
l
i
n
k
s
N
e
t
w
o
r
k
a
n
o
m
a
l
y
i
s
t
a
r
t
b
e
n
d
•
Solution
•
Separate normal & anomalous traffic
using Volume Anomaly
with
PCA
•
I
n
f
o
r
m
a
t
i
o
n
:
V
o
l
u
m
e
A
n
o
m
a
l
y
S
i
m
p
l
e
m
e
a
s
u
r
e
•
M
e
t
h
o
d
:
P
C
A
S
i
m
p
l
i
f
y
v
e
c
t
o
r
s
8
•
Measure Volume Anomaly
2.
Related Work
V
o
l
u
m
e
A
n
o
m
a
l
y
•
A sudden positive(+) or negative(-)
change
in an
Origin-Destination flow
P
o
P
•
Node
of backbone network
•
Detecting using PCA
Anomalous
Normal
Measured
Volume
anomaly
9
2.
Related Work
•
Result
•
C
o
m
p
a
r
i
s
o
n
b
e
t
w
e
e
n
t
r
a
f
f
i
c
v
e
c
t
o
r
o
f
a
l
l
l
i
n
k
s
a
n
d
r
e
s
i
d
u
a
l
v
e
c
t
o
r
: Projection vector using PCA
Anomaly Detected
•
PCA-based Detection can be easily poisoned when only
using
single compromised PoP
•
System uses only
Volume Anomaly
•
Machine learning techniques can be deceived in
learning
phase
•
Adversary can
put poisoned data
in learning phase to deceive the
system
10
10
3.
Motivation
Poisoned Data
•
Chaff?
•
Original mean : Disturbing equipment for radar countermeasure
•
This paper : Disturbing data against anomaly detection
11
11
3.
Motivation
http://www.ordtech-industries.com/2products/Chaff/Chaff.html
http://2.bp.blogspot.com/_NyXGIFk_jjk/TFEYxWSNFoI/AAAAAAAAAuo/MFldb0_h7_0/s400/chaff.jpg
•
Chaff
•
Half normal chaff
•
Zero-mean Gaussian distribution
•
Scaled Bernoulli chaff
•
Bernoulli random variables
•
Add-Constant-If-Big
•
Add constant if traffic exceeds a
threshold
•
Add-More-If-Bigger
•
Adds more chaff if traffic exceeds a
threshold
•
Boiling Frog Attacks
•
S
l
o
w
l
y
i
n
c
r
e
a
s
i
n
g
(
θ
)
t
h
e
c
h
a
f
f
s
12
12
4.
Main Idea
V
a
r
i
o
u
s
s
p
o
i
l
e
d
t
r
a
f
f
i
c
t
o
d
e
c
e
i
v
e
m
a
c
h
i
n
e
l
e
a
r
n
i
n
g
b
a
s
e
d
d
e
c
i
s
i
o
n
p
r
o
c
e
s
s
.
F
a
l
s
e
n
e
g
a
t
i
v
e
r
a
t
e
↑
θ
:
A
t
t
a
c
k
p
a
r
a
m
e
t
e
r
c
t
:
C
h
a
f
f
t
r
a
f
f
i
c
•
Detecting is based on
rapid change of residual
•
Chaff and Boiling frog attack makes
•
The
normal traffic
big
•
The
residual traffic
of anomaly
small
13
13
5
.
Evaluation
•
System
•
Abilene’s backbone network with 12 PoPs
•
15 bi-directional inter-PoP links
•
Sampling
•
2016 measurements per week
•
5 minute intervals
14
14
5
.
Evaluation
Abilene’s backbone network
•
Attacks with chaffs and its FNR
15
15
5
.
Evaluation
C
h
a
f
f
s
(
1
8
%
T
o
t
a
l
t
r
a
f
f
i
c
)
u
s
i
n
g
A
d
d
-
M
o
r
e
-
I
f
-
B
i
g
g
e
r
m
e
t
h
o
d
r
e
c
o
r
d
o
v
e
r
5
0
%
o
f
F
N
R
F
N
R
•
False Negative Rate
•
Rate of evading
•
X-axis : How many chaffs to PoP
•
Y-axis : False Negative Rate
•
Attacks with Boiling Frog and Add-More-If-Bigger
16
16
5
.
Evaluation
G
r
o
w
t
h
r
a
t
e
:
M
u
l
t
i
p
l
i
e
d
f
a
c
t
o
r
o
f
θ
B
o
i
l
i
n
g
F
r
o
g
m
e
t
h
o
d
i
s
e
f
f
e
c
t
i
v
e
o
n
e
v
e
n
s
m
a
l
l
g
r
o
w
t
h
r
a
t
e
s
•
X-axis : Attack duration (weeks)
•
Y-axis : False Negative Rate
•
Attack Rejection Rate for Boling Frog Attacks
17
17
5
.
Evaluation
R
a
t
e
:
M
u
l
t
i
p
l
i
e
d
f
a
c
t
o
r
o
f
θ
B
o
i
l
i
n
g
F
r
o
g
m
e
t
h
o
d
e
f
f
e
c
t
i
v
e
l
y
p
o
i
s
o
n
P
C
A
-
b
a
s
e
d
s
y
s
t
e
m
•
X-axis : Attack duration (weeks)
•
Y-axis : Chaff rejection rate
•
Conclusion
•
PCA-based anomaly detectors can be compromised by simple data
poisoning strategies
•
Chaffs
•
Boiling frog attacks
•
Increase the chance of evading DDoS attacks detections by sixfold
•
Future Work
•
Counter-measure based on Robust formulations of PCA
•
Poisoning strategies for increasing PCA’s false positive rate
18
18
6
.
Conclusion & Future Work
5
0
%
o
f
s
u
c
c
e
s
s
w
i
t
h
1
8
%
o
f
a
d
d
i
n
g
t
r
a
f
f
i
c
,
5
%
t
r
a
f
f
i
c
i
n
c
r
e
a
s
e
•
B. I. P. Rubinstein et. al., “Evading anomaly detection
through variance injection attacks on PCA
•
B. I. P. Rubinstein et. al. “Compromising PCA-based
anomaly detectors for network-wide traffic”
•
Lakhina, et. al., “Diagnosing network-wide traffic
anomalies”
19
19
This presentation discusses evading anomaly detection through variance injection attacks on Principal Component Analysis (PCA) in the context of security. It covers the background of machine learning and PCA, related work, motivation, main ideas, evaluation, conclusion, and future work. The content explains the principles behind PCA, such as orthogonal transformation for dimension reduction and data preservation. It also touches on related work in diagnosing network-wide traffic anomalies.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
EE515/IS523: Security 101: Think Like an Adversary Evading Anomarly Detection through Variance Injection Attacks on PCA Benjamin I.P. Rubinstein, Blaine Nelson, Anthony D. Joseph, Shing-hon Lau, NinaTaft, J. D. Tygar RAID 2008 Presented by: Dong-Jae Shin
EE515/IS523: Security 101: Think Like an Adversary Outline Background Machine Learning PCA (Principal Component Analysis) Related Work Motivation Main Idea Evaluation Conclusion Future work 2
EE515/IS523: Security 101: Think Like an Adversary 1. Background Machine Learning Machine learning (ML) Design and develop algorithms by machine using patterns or predictions Benefits Adaptability Scalable Statistical decision-making http://1.bp.blogspot.com/-tn9GwuoC45w/TvtQvP6_UFI/AAAAAAAAAHI/ECpLGjyH6AI/s1600/machine_learning_course.png 3
EE515/IS523: Security 101: Think Like an Adversary 1. Background PCA (Principal Component Analysis) PCA (Principal Component Analysis) Orthogonal transformation to reduce dimension Most data patterns are captured by the several principal vectors ?11 ?21 ?31 ?12 ?22 ?32 ?13 ?23 ?33 ?11 ?21 ?12 ?22 Data preservation (not perfectly) PCA Deriving principal vectors Deriving the principal vector which captures the maximum variance Find next component 4
EE515/IS523: Security 101: Think Like an Adversary 1. Background PCA (Principal Component Analysis) PCA PCA Example Original coordinates New coordinates Projection to 2ndbasis (next maximum variance) Projection to 1stbasis (maximum variance) > More preserved data Maximum variance means good preservation of information Dimension reduction using important bases http://kimhj8574.egloos.com/5632409 5
EE515/IS523: Security 101: Think Like an Adversary 2. Related Work Diagnosing Network-Wide Traffic Anomalies, SIGCOMM 2004 Goal Diagnosing network-wide anomalies Problem Detecting anomalies are difficult because of large amount of high- dimensional and noisy data Anomaly A pattern in the data that does not conform to the expected behavior ? Src. Dest. Data 1.2.3.4 5.6.7.8 DDos Attack Normal Data Src. Dest. Data 4.3.2.1 5.6.7.8 Mail 6
EE515/IS523: Security 101: Think Like an Adversary 2. Related Work Diagnosing Network-Wide Traffic Anomalies, SIGCOMM 2004 OD flow Origin-Destination flow between PoPs Example of Link Traffic b end Network anomaly i start Too much complexity to monitor every links 7
EE515/IS523: Security 101: Think Like an Adversary 2. Related Work Diagnosing Network-Wide Traffic Anomalies, SIGCOMM 2004 Volume Anomaly A sudden positive(+) or negative(-) change in an Origin-Destination flow Solution Separate normal & anomalous traffic using Volume Anomaly with PCA Information : Volume Anomaly Simple measure Method : PCA Simplify vectors Detecting using PCA Measure Volume Anomaly Normal PCA Measured Volume anomaly Anomalous PoP Node of backbone network 8
EE515/IS523: Security 101: Think Like an Adversary 2. Related Work Diagnosing Network-Wide Traffic Anomalies, SIGCOMM 2004 Result Comparison between traffic vector of all links and residual vector : Projection vector using PCA Traffic vector Anomaly Detected Residual Heuristic method can be subverted Easy to detect, identify, quantify traffic anomalies 9
EE515/IS523: Security 101: Think Like an Adversary 3. Motivation Vulnerabilities of PCA PCA-based Detection can be easily poisoned when only using single compromised PoP System uses only Volume Anomaly Machine learning techniques can be deceived in learning phase Adversary can put poisoned data in learning phase to deceive the system Poisoned Data 10
EE515/IS523: Security 101: Think Like an Adversary 3. Motivation Chaff Chaff? Original mean : Disturbing equipment for radar countermeasure This paper : Disturbing data against anomaly detection http://www.ordtech-industries.com/2products/Chaff/Chaff.html http://2.bp.blogspot.com/_NyXGIFk_jjk/TFEYxWSNFoI/AAAAAAAAAuo/MFldb0_h7_0/s400/chaff.jpg 11
EE515/IS523: Security 101: Think Like an Adversary 4. Main Idea Attack Method : Attack parameter ct: Chaff traffic Chaff Half normal chaff Zero-mean Gaussian distribution Scaled Bernoulli chaff Bernoulli random variables Add-Constant-If-Big Add constant if traffic exceeds a threshold Add-More-If-Bigger Adds more chaff if traffic exceeds a threshold Boiling Frog Attacks Slowly increasing ( ) the chaffs Various spoiled traffic to deceive machine learning based decision process. False negative rate 12
EE515/IS523: Security 101: Think Like an Adversary 5. Evaluation What they want Detecting is based on rapid change of residual Chaff and Boiling frog attack makes The normal traffic big The residual traffic of anomaly small 13
EE515/IS523: Security 101: Think Like an Adversary 5. Evaluation Environments System Abilene s backbone network with 12 PoPs 15 bi-directional inter-PoP links Sampling 2016 measurements per week 5 minute intervals Abilene s backbone network 14
EE515/IS523: Security 101: Think Like an Adversary 5. Evaluation Evaluation FNR False Negative Rate Rate of evading Attacks with chaffs and its FNR X-axis : How many chaffs to PoP Y-axis : False Negative Rate Chaffs (18% Total traffic) using Add- More-If-Bigger method record over 50% of FNR 15
EE515/IS523: Security 101: Think Like an Adversary 5. Evaluation Evaluation Attacks with Boiling Frog and Add-More-If-Bigger X-axis : Attack duration (weeks) Y-axis : False Negative Rate Boiling Frog method is effective on even small growth rates Growth rate : Multiplied factor of 16
EE515/IS523: Security 101: Think Like an Adversary 5. Evaluation Evaluation Attack Rejection Rate for Boling Frog Attacks X-axis : Attack duration (weeks) Y-axis : Chaff rejection rate Boiling Frog method effectively poison PCA-based system Rate : Multiplied factor of 17
EE515/IS523: Security 101: Think Like an Adversary 6. Conclusion & Future Work Conclusion & Future Work Conclusion PCA-based anomaly detectors can be compromised by simple data poisoning strategies Chaffs Boiling frog attacks Increase the chance of evading DDoS attacks detections by sixfold 50% of success with 18% of adding traffic, 5% traffic increase Future Work Counter-measure based on Robust formulations of PCA Poisoning strategies for increasing PCA s false positive rate 18
EE515/IS523: Security 101: Think Like an Adversary References B. I. P. Rubinstein et. al., Evading anomaly detection through variance injection attacks on PCA B. I. P. Rubinstein et. al. Compromising PCA-based anomaly detectors for network-wide traffic Lakhina, et. al., Diagnosing network-wide traffic anomalies 19
