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:
- Mengajukan sistem klasifikasi malware menggunakan call graph clustering
Method/solution
- Melakukan representasi malware ke dalam call graph untuk mencari kemiripan antara sampel dan melakukan clustering
- Menghitung pairwise graph similarity score
- Menggunakan beberapa algoritma clustering, k-medoids dan Density-based spatial clustering of applications with Noise (DBSCAN)
- Hasil clustering dibandingkan dengan klasifikasi manual oleh analis malware
- Call graph digenerate dari binary melalui analisa statik dari binary dengan tools dissambly IDA Pro
- Layer obfuskasi dibuang dengan unpacking dan decrypting executable
- IDAPro digunakan untuk identifikasi function dan memberikan nama symbollic secara random
- Pada fungsi external yang diimport secara dinamis, namanya diperoleh dari Import Address Table (IAT)
- Bila fungsi library statically linked, fungsi kode library digabungkan dengan compiler dari executable. menggunakan IDA Pro FLIRT
- Setelah semua fungsi (vertice) dari call graph diidentifikasi, edges antara vertice ditambahkan, yang sesuai dengan function call yang diekstrak dari executable yang didisassembled
- Untuk identifikasi, quantisasi dan menunjukan kemiripan antara sampel malware digunakan GED (finding minimum graph edit distances)
- Kemiripan malware dihitung menggunakan rumus similarity σ (G, H) dari call graph dibawahnya
- Untuk cost functionnya dihitung Graph edit distance λφ(G, H)
- Menggunakan Simulated Annealing, sebuah algoritma yang mencari mapping vertex yang memiliki nilai GED minimal
- Untuk inisialisasi cluster medoid digunakan 3 algoritma berbeda, k-means clustering, k-medoids clustering dan inisialisasi cluster cendroid dengan Trained initialization
- Dataset X menggunakan sampel 194 malware call graph yang telah dianalisa manual dan diklasifikasikan oleh analis dari F-Secure menjadi 24 family
- K-optimal atau jumlah cluster diasumsikan 24
- Pada setiap luster k, k-medoid clustering dilakukan 50 kali
- Menggunakan algoritma DBSCAN untuk mencari dense area pada data psace yang terpisah dari area low density.
- 2 parameter yang diukur DBScan adalah MinPts dan Rad
- Pengujian algoritma clustering dilakukan pada 2 batch call graphs yang memiliki sampel 675 dan 1050.
Main result
- Rata-rata call graph sampel memiliki 234 nodes dan 488 edges
- Sampel terbesar memiliki 748 vertices dan 1875 edges
- Ukuran family berbeda-beda dari 2 sampel sampai 17 unique call graph sampel
- Hampir semua anggota setiap family berhasil dikelompokan secara benar
- Hanya beberapa family seperty Baidu dan Boaxxe yang tidak dapat dikelompokan dengan benar dan tersebar ke berbagai cluster
- Hasil DBSCAN lebih baik daripada k-means clustering
Limitation:
- Penentuan parameter Minpts dan Rad agak kompleks
- Masih ada proses clustering sampel yang kurang tepat