Mengkaji dan Memahami Serangan Hash Table Collision Denial of Service (DDOS)

komputerdia.com - Sebelum bicara tentang hash table, alangkah baiknya kalian harus tahu dahulu bahwa associative array (map atau dictionary) yaitu abstract data type (ADT) yang terbagi dalam pasangan kunci serta nilai dan dalam associative array tidak bisa ada kunci yang duplikat atau dobel (nilai bisa dobel, namun kunci tidak bisa). Kunci ini melakukan tindakan seperti nama dari data yang disimpan, hingga dengan mengasosiasikan satu data dengan kunci berbentuk nama atau identifier yang beda, data yang dikehendaki dapat di ambil secara gampang dengan mengatakan kuncinya.

Contoh kecilnya, ketika kalian ingin mengetahui vendor atau pembuat suatu merek hp, maka kalian tinggal mencari kata kunci "make" atau "pembuat" handphone tersebut, maka secara gamblang akan tersedia suatu informasi yang memuat info handphone tersebut.

Baca Juga :



Mengkaji dan Memahami Serangan Hash table Collision Denial of Service (DDOS)

Hubungan Associative Array dengan Hash Table

Associative array yaitu abstract data type, yang berarti strutktur data yang masih berbentuk rencana atau spesifikasi saja. Hash table yaitu satu diantara banyaknya implementasi dari associative array, yang berarti hash table ini yaitu concrete data type atau data yang telah konkrit dan bukan lagi abstract/rencana .

Perumpamaan yang sangat sederhana, ketika kalian akan mencari seseorang yang bernama Agus di satu desa yang terbagi dalam 100 tempat tinggal dan kalian mesti mencarinya satu per satu dari tempat tinggal ke tempat tinggal, hal ini pastinya akan memakai usaha serta waktu yang begitu lama. Dengan adanya Hash table, kalian dapat hindari pencarian linear seperti ini. Dari pada mencari satu per satu di semua tempat tinggal, dengan satu formula matematis tertentu, tentunya kalian dapat mengetahui identitas orang ini hanya dengan mencari nama tersebut pada sebuah data, dan akhirnya kalian akan mengetahui bahwa Agus ada dirumah nomor XXX (natural location), hingga kalian cukup mencari di satu tempat tinggal saja.

Manfaat formula matematis yang dipakai untuk mencari tempat data (natural location) dari satu kunci dalam hash table yaitu peranan hash. Output dari peranan hash ini dimaksud dengan hash code. Hash table pada intinya yaitu satu array (tiap-tiap elemen array ini disebut dengan bucket), jadi peranan hash ini dapat hasilkan index array berbentuk integer, di mana tempat data disimpan.

Baca Juga :

Gambar gerak dibawah ini merupakan contoh dari proses pemasukan data dalam sebuah hash table yang terdiri dari 6 bucket, data yang dimasukkan adalah nama yang berfungsi sebagai key, dan tanggal lahir sebagai datanya.

Mengkaji dan Memahami Serangan Hash Table Collision Denial of Service (DDOS)

Didalam data gambar animasi diatas tidak berlangsung collision, masing-masing data dimasukkan dalam bucket yang berlainan, dengan demikian operasi insert dapat dikerjakan secara cepat. Selanjutnya kaliandapat lihat masalah saat berlangsung hash collision, berarti ada lebih dari satu data yang dimasukkan kedalam bucket yang sama.


Hash collision


Perhatikan bahwa jumlah kemungkinan kunci sangat banyak, bahkan tak terhingga. Bila kunci adalah nama orang, jumlah kemungkinan nama orang sangat banyak, sedangkan jumlah sel dalam hash table terbatas. Hal ini memungkinkan timbulnya collision, artinya ada 2 atau lebih kunci yang menghasilkan hash code yang sama (berebut dalam satu sel yang sama).

Karena collision tidak mungkin terhindarkan, implementasi hash table harus menentukan apa yang harus dilakukan bila terjadi collision. Salah satu cara yang banyak dipakai adalah dengan mengijinkan lebih dari satu nilai dalam satu lokasi. Umumnya hash table menggunakan struktur data linked list untuk menyimpan lebih dari satu nilai dalam satu lokasi  (bucket) yang sama.

Bila data akan dimasukkan ke dalam bucket yang sudah ada isinya (collision terjadi), maka operasinya tidak sesederhana pada kasus bucket kosong. Mari kita perhatikan animasi yang saya buat di bawah ini.

Mengkaji dan Memahami Serangan Hash Table Collision Denial of Service (DDOS)

Ketika memasukkan data (insert), pada bucket yang tidak kosong maka perlu dilakukan operasi komparasi kunci untuk melihat apakah kunci yang sama sudah ada di bucket itu atau belum. Bila kunci yang sama ternyata ada di situ, artinya operasi insert berubah menjadi operasi update, yaitu mengubah data yang lama dengan yang baru. Bila kunci yang dimasukkan tidak ada di situ, maka kunci dan data yang dimasukkan akan disimpan di node paling akhir dari bucket tersebut.

Perhatikan sekali lagi animasi di atas.

  • Pada saat memasukkan data agus, kondisi bucket no.4 sudah berisi 1 node yaitu john. Sebelum bisa memasukkan data, harus dilakukan komparasi dulu 1x, apakah john==agus yaitu apakah kunci di node pertama dalam bucket tersebut adalah agus? Bila ternyata sama tidak perlu membuat node baru, hanya melakukan update node tersebut dengan data baru.
  • Pada saat memasukkan data adi, kondisi bucket no. 4 sudah berisi 2 node yaitu john dan agus. Sebelum bisa memasukkan data, harus dilakukan komparasi dulu 2x, apakah john==adi ? dan apakah agus==adi?
  • Pada saat memasukkan data budi, kondisi bucket no. 4 sudah berisi 3 node: john, agus, adi. Sebelum bisa memasukkan data, harus dilakukan komparasi sebanyak 3x, apakah john=budi? , apakah agus=budi? dan apakah adi=budi?
Bisa disimpulkan bahwa bila terjadi collision dan di dalam bucket tersebut sudah berisi n data, untuk melakukan operasi insert sebuah data, diperlukan operasi komparasi maximal "n" kali. Komparasi maximal "n" kali terjadi bila data yang akan dimasukkan tidak ada dalam bucket (harus membuat node baru).


Kompleksitas Algoritma


Ketika tidak terjadi collision, usaha yang harus dilakukan prosesor untuk memasukkan 1 data adalah konstan, anggap lah satu, jadi kalau ada n data maka usaha yang harus dilakukan prosesor adalah 1*n, jadi bisa dikatakan kompleksitasnya O(n) atau linear complexity.

Ketika terjadi collision, usaha yang harus dilakukan prosesor untuk memasukkan 1 data ke dalam hash table tergantung dari data yang sudah ada dalam bucket yang sama. Mari kita analisa kasus terburuk dimana n data dengan kunci yang unik (tidak ada yang duplikat) dimasukkan ke dalam hash table dan semuanya berkumpul dalam bucket yang sama.
  • Ketika memasukkan data yang pertama, bucket masih kosong, usaha yang harus dilakukan prosesor adalah 1.
  • Ketika memasukkan data yang ke-2, bucket berisi 1 node, akibatnya prosesor harus melaukan komparasi 1 kali dan 1 usaha lagi untuk memasukkan data di akhir node, jadi total 2 usaha.
  • Ketika memasukkan data yang ke-3, bucket berisi 2 node, akibatnya prosesor harus melakukan komparasi 2 kali dan 1 usaha lagi untuk memasukkan data di akhir node, jadi total 3 usaha.
  • Dan seterusnya, data yang ke-n, total usaha adalah "n".
Jadi total usaha yang harus dilakukan untuk memasukkan n data adalah 1+2+3+….+n = n * (n+1) / 2. Dalam menilai kompleksitas algoritma, n+1 bisa dianggap n dan 1/2 bisa diabaikan karena kita tidak sedang mengukur secara eksak, kita hanya melihat kompleksitasnya relatif terhadap jumlah input. Jadi bisa dikatakan kompleksitas ketika terjadi worst case adalah n*n atau O(n²) (quadratic complexity), artinya bila jumlah input dinaikkan menjadi 2x lipat, maka usaha atau waktu yang dibutuhkan prosesor naik menjadi 4x lipat.




.
.

Berlangganan Artikel terbaru (free):

Post a Comment