Klasifikasi malware call graph clustering-kinable-paper review


Paper Title: Malware Classification based on call graph clustering

Authors: Joris Kinable, Orestis Kostakis

Venue: Journal of Computer Virology 7:233-245

URL: https://link.springer.com/article/10.1007/s11416-011-0151-y

Problem: Setiap harinya perusahaan anti virus menerima ribuan sampel yang harus diklasifikasikan sebagai malware atau benign. Untuk menghadapi jumlah sampel yang besar dibutuhkan teknik deteksi malware automatis

Contribution: 

  1. Mengajukan sistem klasifikasi malware menggunakan call graph clustering

Method/solution

  1. Melakukan representasi malware ke dalam call graph untuk mencari kemiripan antara sampel dan melakukan clustering
  2. Menghitung pairwise graph similarity score
  3. Menggunakan beberapa algoritma clustering, k-medoids dan Density-based spatial clustering of applications with Noise (DBSCAN)
  4. Hasil clustering dibandingkan dengan klasifikasi manual oleh analis malware
  5. Call graph digenerate dari binary melalui analisa statik dari binary dengan tools dissambly IDA Pro
  6. Layer obfuskasi dibuang dengan unpacking dan decrypting executable
  7. IDAPro digunakan untuk identifikasi function dan memberikan nama symbollic secara random
  8. Pada fungsi external yang diimport secara dinamis, namanya diperoleh dari Import Address Table (IAT)
  9. Bila fungsi library statically linked, fungsi kode library digabungkan dengan compiler dari executable. menggunakan IDA Pro FLIRT
  10. Setelah semua fungsi (vertice) dari call graph diidentifikasi, edges antara vertice ditambahkan, yang sesuai dengan function call yang diekstrak dari executable yang didisassembled
  11. Untuk identifikasi, quantisasi dan menunjukan kemiripan antara sampel malware digunakan GED (finding minimum graph edit distances)
  12. Kemiripan malware dihitung menggunakan rumus similarity σ (G, H) dari call graph dibawahnya
  13. Untuk cost functionnya dihitung Graph edit distance λφ(G, H)
  14. Menggunakan Simulated Annealing, sebuah algoritma yang mencari mapping vertex yang memiliki nilai GED minimal
  15. Untuk inisialisasi cluster medoid digunakan 3 algoritma berbeda, k-means clustering, k-medoids clustering dan inisialisasi cluster cendroid dengan Trained initialization
  16.  Dataset X menggunakan sampel 194 malware call graph yang telah dianalisa manual dan diklasifikasikan oleh analis dari F-Secure menjadi 24 family
  17. K-optimal atau jumlah cluster diasumsikan 24
  18. Pada setiap luster k, k-medoid clustering dilakukan 50 kali
  19. Menggunakan algoritma DBSCAN untuk mencari dense area pada data psace yang terpisah dari area low density. 
  20. 2 parameter yang diukur DBScan adalah MinPts dan Rad 
  21. Pengujian algoritma clustering dilakukan pada 2 batch call graphs yang memiliki sampel 675 dan 1050. 

Main result

  1. Rata-rata call graph sampel memiliki 234 nodes dan 488 edges
  2. Sampel terbesar memiliki 748 vertices dan 1875 edges
  3. Ukuran family berbeda-beda dari 2 sampel sampai 17 unique call graph sampel
  4. Hampir semua anggota setiap family berhasil dikelompokan secara benar
  5. Hanya beberapa family seperty Baidu dan Boaxxe yang tidak dapat dikelompokan dengan benar dan tersebar ke berbagai cluster
  6. Hasil DBSCAN lebih baik daripada k-means clustering

Limitation:

  1. Penentuan parameter Minpts dan Rad agak kompleks
  2. Masih ada proses clustering sampel yang kurang tepat
,

Silahkan tuliskan tanggapan, kritik maupun saran