Penerapan Teknik Support Vector Machine untuk Pendeteksian Intrusi pada Jaringan Sidang IF40Z2-Tugas Akhir II Krisantus Sembiring 13503121 Selasa, 11 September 2007
2/1/2008
1
Latar Belakang y y y
Pentingnya pendeteksian intrusi pada jaringan Teknik signature g based memerlukan signature g yang y g dibuat secara manual Pendeteksian intrusi dengan data mining: ◦ Kelebihan: K l bih x Mengatasi kelemahan teknik signature based x Misuse detection & anomaly detection
◦ Kekurangan: x Biaya komputasi tinggi (butuh pelatihan dan pengujian) x Butuh data pelatihan dalam jumlah besar x Anomaly detection Æfalse positive yang tinggi y
SVM: teknik data mining untuk mendeteksi intrusi dengan akurasi tinggi gg 2/1/2008
2
y
Rumusan Masalah: ◦ B Bagaimana i model d l terbaik t b ik d dalam l mengimplementasikan i l t ik SVM untuk t k pendeteksian intrusi pada jaringan. ◦ Bagaimana pengaruh variasi dataset terhadap performansi SVM pada di ib i d distribusi data yang natural.l
y
Tujuan: ◦ Melakukan studi dan implementasi p pendeteksian p intrusi ppada jjaringan g baik dengan metode misuse maupun anomaly detection dengan menggunakan SVM.
y
Batasan masalah: ◦ Mining dilakukan terhadap data yang diaudit ◦ Evaluasi hasil penerapan SVM yang dilakukan, digunakan data KDDCUP 99 hhttp://kdd.ics.uci.edu/databases/kddcup99. //kdd i i d /d b /kdd 99 ◦ Prototipe perangkat lunak yang dibuat lebih ditujukan untuk eksperimen
2/1/2008
3
Deskripsi Sistem
2/1/2008
4
Metode pendeteksian intrusi dengan data mining Anomaly Detection
Misuse Detection
Proses: Membangun model dari data normal Intrusi adalah deviasi dari data normal
Membangun model data intrusi dari dataset yang memiliki label
Kelebihan K l bih : Dapat mendeteksi intrusi jenis baru
Mendeteksi M d k i intrusi i i yang sudah d h diketahui secara akurat false positive rendah
Kekurangan: Cenderung menghasilkan false positive yang tinggi. Jenis intrusi tidak diketahui
Umumnya tidak mampu mendeteksi jenis intrusi baru
2/1/2008
5
Penelitian Pendeteksian Intrusi dengan SVM Srivinas Mukkamala, 2002 ◦ SVM biner, kernel RBF ◦ 14292 dataset : 7312 ppelatihan,, 6980 ppengujian g j ◦ Akurasi 99.5% y Srivinas Mukkamala, 2002 ◦ Multi Class SVM One-against all ,kernel RBF ◦ 5 kelas (normal, dos, probe, r2l,u2r) ◦ 12072 dataset : 5092 pelatihan, 6980 pengujian y Pavel Laskov et. al, 2004 ◦ One Class SVM, SVM kernel RBF y Pavel Laskov et. al, 2005 ◦ SVM, biner, kernel RBF ◦ 2000 data (5% intrusi), 41 atribut, distribusi intrusi seimbang ◦ Hasilnya : x (with known attack) : terbaik C4.5 akurasi 95% pada false positive 1%, diikuti SVM dan MLP dengan perbedaan kecil x With unknown attack : SVM terbaik dengan perbedaan significant dibandingkan algoritma lain y
2/1/2008
6
Dataset Eksperimen Data
KDDCUP 99 Hasil preprocessing data mentah (tcpdump ) DARPA 98 Data simulasi jaringan yang mirip dengan jaringan angkatan udara AS Data 9 minggu , 4.9 juta record 22 jenis intrusi dalam 4 kategori utama yaitu DOS (Denial of Service), Remote to User, User to Root, dan Probes. Pavel Laskov (2005): Data KCCUP 99 paling baik diproses dengan algoritma non-linier ÆSVM nonliniear dengan fungsi kernel RBF
2/1/2008
7
Dasar Teori SVM D t t Dataset
M d l SVM Model
{x ,..., x } 1
n
y ∈ {+ 1,−1} i
Cari bidang pemisah dengan margin (m= 2 ) terbesar
Support Vector
m
Kelas 2
w
−b w
Bidang pembatas kelas 2: xi . w+b = 1
Kelas 1 Bidang pembatas kelas 1: xi . w+b = -1
Pembelajaran:
1 2 ⎛ n ⎞ min w + C ⎜ ∑ ξ i ⎟ 2 ⎝ i =1 ⎠
1 n max LD ≡ ∑ α i − ∑ α iα j yi y j xi .x j 2 i =1, j =1 i =1
s.t xi .w + b ≤ −1 + ξ i , ξ i > 0
s.t.
ns
Klasifikasi:
Bidang pemisah: xi . w+b = 0
f ( x ) = ∑ α i y i x i .x + b i =1
n
n
∑α y i =1
i
i
= 0, α i ≥ 0
if f ( x) ≥ +1 then yi = +1 if f ( x) ≤ −1 then th yi = −1
2/1/2008
8
Dasar Teori SVM Transformasikan data sehingga linearly separable di feature space dengan fungsi kernel
φ( ) φ(.)
Klasifikasi:
φ( ) φ( ) φ( ) φ( ) φ( ) φ( ) φ( ) φ( ) φ( ) φ( ) φ( ) φ( ) φ( ) φ( ) φ( ) φ( ) φ( ) φ( )
Input space
Feature space
f ( x) = ∑ α i y i K (xi , x ) + b ns
ns
f (x ) = ∑ α i yiφ (xi )φ ( x ) + b
i =1
i =1
RBF kernel
Æ
(
)
K (xi , x j ) = exp − γ xi − x j , γ > 0
2/1/2008
2
9
Dasar Teori One Class SVM Dengan bidang pemisah:
φ(.)
origin i i
+1
-1
Pembelajaran:
1 2 1 n min w + ∑ ξ i − r 2 vn i =1 s.t. (w.φ ( xi )) ≥ r − ξ i ,
Klasifikasi:
f ( x) = ∑i α i K (xi , x ) − r
ξi ≥ 0 2/1/2008
10
Metode Pendeteksian Intrusi dengan SVM y
Anomaly detection dengan One Class SVM ◦ Supervised : data pelatihan = data normal ◦ Unsupervised: data pelatihan mungkin mengandung data intrusi
y
Misuse Detection ◦ SVM Biner : 2 Kelas , intrusi dan normal ◦ Multi M l i Class Cl SVM One O Against A i One O
2/1/2008
11
◦ Multi Class SVM One Against All
◦ SVM Biner Æ Multi Class SVM One Against All
2/1/2008
12
y
SVM Biner Æ Multi Class SVM One Against One
Pembelajaran:
Klasifikasi:
2/1/2008
13
Analisis Pembelajaran dengan SVM
Preprocessing: Input SVM : vektor bilangan real Representasi data diskrit yang tidak terurut dengan memakai 1-of-c encoding. g Contoh pprotocol_type: _ yp tcp p udp p icmp p [100]
[010]
[001]
Normalisasi/ scaling ke dalam rentang [0,1] Æ x = x − min max − min Estimasi parameter dengan k-folds cross-validation dan grid search Algoritma pelatihan decomposition dengan shrinking dan caching '
2/1/2008
14
SVM Pada Imbalanced Dataset
Teknik klasifikasi umumnya akurasinya menurun pada imbalanced dataset y Solusi : memberikan bias sehingga SVM lebih memperhatikan instance dari kelas minoritas y
min w,b ,ξ
1 2 w + C+ ∑ ξi + C− ∑ ξi 2 yi =1 yi = −1
s.t. y i (wxi + b ) ≥ 1 − ξ i ,
ξ i ≥ 0, i = 1,..., n
Incremental Training untuk SVM Fungsi keputusan hanya dipengaruhi oleh support vector y Pilih kandidat k did t support pp t vector t sebelum b l pelatihanÆjumlah l tih Æj l h data d t pelatihan l tih berkurang y
y ( x ) f ( x ) <= β + 1
Feature Selection y
F-Score
2/1/2008
15
Tujuan Eksperimen y y y y
Mereplikasi hasil paper acuan dan membandingkan setting parameter dan metode preprocessing data Memilih model terbaik dari alternatif implementasi pendeteksian intrusi dengan SVM. Menguji g j skalabilitas model terbaik. Mengetahui hasil upaya peningkatan performansi ◦ Penggunaan gg nilai C berbeda ◦ feature selection g ◦ incremental training. 2/1/2008
16
Parameter Evaluasi
True Positive Rate/ Detection Rate (DR)
DR =
False Positive Rate
FPrate
TP P
ROC C Curve
t-Test pada nilai F-measure
Waktu pelatihan dan pengujian
FP = N
F-Measure
2 * recall * p precision F − measure = recall + precision 2/1/2008
17
Skenario y
Replikasi Hasil Paper Acuan ◦ [MUK02A] x SVM Biner, kernel RBF, data pelatihan : 7312 , data pengujian : 6980 x Parameter C = 1000, 1000 g=1.0 g=1 0 x Asumsi : distribusi data intrusi tidak diubah, tidak ada normalisasi
◦ [MUK02B] x One Against All, All kernel RBF, RBF data pelatihan : 7312 , data pengujian : 6980 x Asumsi : parameter sama dengan [MUK02A], tidak ada normalisasi
◦ [LAS04] x Kernel e e RBF,, uunsupervised supe v sed anomaly a o a y detect detection, o , pa parameter a ete nuu dan a rasio as o intrusi t us bervariasi x Preprocessing data numerik: data diskrit: 1/c-of-c encoding x Asumsi : data pelatihan dan data pengujian @2000
◦ [LAS05] : x SVM Biner, kernel RBF, data intrusi seimbang, 2 skenario pengujian x Preprocessing x data d t kategori: k t i 1-of-c 1 f encoding. di x Selanjutnya normalisasi data numerik dan diskrit dengan 2/1/2008
18
Skenario [2] y
Perbandingan Performansi Alternatif Implementasi SVM ◦ Pelatihan : x Komposisi data intrusi diusahakan seimbang : data pelatihan 100000 x Komposisi data intrusi tidak seimbang : data pelatihan 49420
◦ Pengujian 9 X 100.000 data pada data yang mengandung intrusi jenis baru dan sebaliknya y
2/1/2008
19
Skenario [3] y
Pengujian Skalabilitas model terbaik
◦ P Pelatihan l tih dengan d 250.000 250 000 data, d t penambahan b h 250 250.000 000 data d t pada d pelatihan berikutnya ◦ Pengujian pada 1.000.000 ◦ Untuk One Class SVM data pelatihan awal dan penambahannya = 50000 y
Upaya Peningkatan Kinerja Model Terbaik ◦ Nilai C berbeda pada rasio data intrusi bervariasi ◦ Feature Selection, eksperimen dengan variasi jumlah atribut paling penting ◦ Incremental training
2/1/2008
20
Hasil Eksperimen Eksperimen:: Replikasi hasil [MUK02]
Multi Class SVM One- Against-All
y
Berdasarkan t-Test metode dengan normalisasi + parameter hasil grid search adalah yang terbaik
y
T Tanpa normalisasi li i : ◦ Nilai parameter C besar ◦ waktu pelatihan dan pengujian jauh lebih besar
2/1/2008
21
Hasil Eksperimen Eksperimen:: Replikasi hasil [LAS04] nu = rasio data intrusi ◦ Berdasarkan t-Test metode normalisasi data hasil analisis TA adalah yang terbaik ◦ Metode normalisasi data [LAS04] dan [LAS05] membutuhkan nilai parameter g lebih kecil
◦ Metode normalisasi [LAS05] lebih baik dari [LAS04] karena memproses atribut g atribut numerik diskrit sama dengan ◦ Pada [LAS04] nilai atribut diskrit = 1/ jumlah kategori Æ rentang nilainya umumnya menjadi lebih kecil 2/1/2008
22
Hasil Eksperimen Eksperimen:: Replikasi hasil [LAS05] Data pengujian mengandung intrusi jenis baru:
◦ Berdasarkan t-Test metode normalisasi data [LAS05] > analisis TA > [LAS04] ◦ Metode M d normalisasi li i [LAS05] dan d analisis li i TA lebih l bih baik b ik pada d kategori k i data d tertentu ◦ Metode normalisasi [LAS05] lebih baik pada data DOS (80% dari dataset) ◦ Metode normalisasi [LAS05] dipilih untuk eksperimen selanjutnya
2/1/2008
23
Hasil Eksperimen Eksperimen:: Perbandingan Model Anomaly Detection y
Data intrusi seimbang y
Data pelatihan tidak mengandung intrusi jenis baru Berdasarkan t-Test MD2 > MD1
y
Data pelatihan mengandung intrusi jenis baru Berdasarkan tt-Test Test MD1 > MD2
y
MD2 menganggap sebagian data intrusi sebagai data normal sehingga: y
Detection rate turun
y
Akurasi u as pa padaa data ata normal o a dan a fa false se pos positive t ve lebih eb ba baik
2/1/2008
24
Hasil Eksperimen Eksperimen:: Perbandingan Model Anomaly Detection [2] y
y
Pada data intrusi tidak seimbang y
Data pelatihan tidak mengandung intrusi jenis baru Æ MD1 > MD2
y
Data pelatihan mengandung intrusi jenis baru Æ MD1 > MD2
Berdasarkan t-Test pada gabungan hasil seluruh skenario MD1 dipilih sebagai model anomaly detection terbaik
2/1/2008
25
Hasil Eksperimen Eksperimen:: Perbandingan Model Misuse Detection y
Data intrusi seimbang y
Data pengujian tidak mengandung intrusi jenis baru
Berdasarkan t-Test MD6 = MD7 > MD5 >MD4
y
Data ppengujian g j mengandung g g intrusi jjenis baru
Berdasarkan t-Test MD6 > MD7 > MD5 >MD4
2/1/2008
26
Hasil Eksperimen Eksperimen:: Perbandingan Model Misuse Detection [2] y
Data intrusi tidak seimbang y
Data pengujian tidak mengandung intrusi jenis baru
Berdasarkan t-Test MD5> MD4 >MD7>MD6
y
Data ppengujian g j mengandung g g intrusi jjenis baru
Berdasarkan t-Test MD6 > MD7 > MD5 >MD4
2/1/2008
27
Hasil Eksperimen Eksperimen:: Perbandingan Model Misuse Detection [3] y
y
MD6 dipilih sebagai model misuse detection terbaik karena: y Total waktu pelatihan dari seluruh skenario paling kecil y Paling g baik berdasarkan t-Test ppada ggabungan g hasil seluruh skenario Mengapa MD6 dan MD7 umumnya lebih baik? y Semua model menggunakan lebih dari 1 SVM Biner y Pada MD6 dan MD7 data normal digunakan hanya pada satu SVM Biner Æ waktu pelatihan lebih kecil y Penentuan jenis intrusi lebih akurat karena fungsi keputusannya tidak dipengaruhi data normal
2/1/2008
28
Hasil Eksperimen Eksperimen:: Pengujian Skalabilitas Model Terbaik y y
y
Pengujian pada 1 juta data = data 12.85 hari Model Anomalyy detection terbaik
y
Parameter nu = 0.05 Æ jumlah minimum support vector
y
Waktu pelatihan sebanding dengan jumlah support vector
y
MD1 scalable untuk data pelatihan dalam jumlah ribuan
Model Misuse Detection terbaik
y
MD6 scalabe untuk data pelatihan dalam jumlah besar
y
750000 data = data dari 9.5 hari 2/1/2008
29
Upaya Peningkatan performansi dengan nilai C berbeda y y
y
Performansi tidak berubah bahkan dengan perbandingan nilai C yang sangat besar Hal ini menunjukkan: y Bidang pemisah terbaik tidak berubah y Selama pelatihan tidak terjadi banyak error dalam klasifikasi Akurasi pada data R2L dan U2R lebih kecil y Sedikitnya jumlah data bukan masalah utama y Menurut [KAY05] berdasarkan analisis atribut dengan information gain Æ hampir tidak ada atribut relevan untuk jjenis intrusi ini
2/1/2008
30
Upaya Peningkatan performansi dengan menghilangkan atribut tidak penting y
FFeature selection l i dengan d f f-score sangat efisien fi i pada d 500000 data d hanya h membutuhkan waktu 19.8 detik
y
Jika ada atribut penting yang hilang maka performansi menurun
y
Dengan feature D f t selection l ti ini i i efisiensi fi i i umumnya meningkat i k t sedangkan d k efektifitas f ktifit tidak berubah MD1
MD6
2/1/2008
31
Hasil Eksperimen Eksperimen:: Upaya Peningkatan performansi dengan Incremental Training y
Training dengan n partisi data masing-masing distribusinya sama
y
Parameter Beta y y y
y
y y
y
Multi Class SVM One-Against-One: 0.001 One Class SVM : -0.99
Jumlah partisi y
y
SVM Biner : 0.6 06
SVM Biner : 10 Multi Class SVM One-Against-One: 5 One Class SVM : 20
MD6 : y
efektifitas cenderung tetap
y
Efi i i meningkat Efisiensi i k t
MD1 y
Efisiensi jauh meningkat
y
Efektifitas jauh meningkat pada parameter Beta B b il i sangat kecil bernilai k il
2/1/2008
32
Hasil Eksperimen Eksperimen:: Upaya Peningkatan p performansi y
MD6
y
MD1
2/1/2008
33
Kesimpulan y
Model terbaik SVM Biner Æ Multi Class SVM One Against One dan One Class SVM dengan mengunakan data data normal.
y
Pada P d data d KDDCUP 99, 99 data d untukk One O Class Cl SVM llebih bih bbaik ik dinormalisasi ke nilai maksimum dan minimumnya sedangkan data untuk SVM Biner Æ Multi Class SVM One Against One lebih baik dinormalisasi dengan data dependent normalization (data hasil one-of-c one of c encoding juga ikut dinormalisasi).
y
Performansi SVM dengan misuse detection tidak jauh berubah pada berbagai variasi dataset, dataset akan tetapi pada anomaly detection terjadi perubahan yang signifikan
y
Penghilangan atribut kurang penting dan incremental training dapat meningkatkan i k tk efisiensi fi i i SVM secara signifikan i ifik sehingga hi mampu menangani pelatihan dalam jumlah yang lebih besar.
y
Penggunaan nilai C berbeda tidak mampu menangani masalah i b l imbalance ddataset t t pada d d data t KDDCUP 99 99. 2/1/2008
34
Saran y
Penelitian mengenai mengenai incremental training terutama pada kriteria pembuangan data pelatihan dan parameter pelatihannya. pelatihannya
y
Penelitian mengenai metode pencarian parameter selain dengan grid search sehingga membutuhkan waktu yang lebih singkat terutama pada dataset berukuran besar. besar
y
Penelitian mengenai metode lain untuk mengatasi masalah imbalanced dataset pada data KDDCUP 99.
y
Penelitian mengenai kombinasi teknik lain dengan One Class SVM. Hasil prediksi One Class SVM dapat di-filter dengan teknik tersebut, sehingga jumlah false positive yang dihasilkan semakin b k berkurang.
2/1/2008
35
