論文

査読有り
2019年

A fast algorithm for constructing phylogenetic trees with application to IoT malware clustering

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
  • Tianxiang He
  • ,
  • Chansu Han
  • ,
  • Ryoichi Isawa
  • ,
  • Takeshi Takahashi
  • ,
  • Shuji Kijima
  • ,
  • Jun’ichi Takeuchi
  • ,
  • Koji Nakao

11953 LNCS
開始ページ
766
終了ページ
778
記述言語
掲載種別
研究論文(国際会議プロシーディングス)
DOI
10.1007/978-3-030-36708-4_63

© Springer Nature Switzerland AG 2019. For efficiently handling thousands of malware specimens, we aim to quickly and automatically categorize those into malware families. A solution for this could be the neighbor-joining method using NCD (Normalized Compression Distance) as similarity of malware. It creates a phylogenetic tree of malware based on the NCDs between malware binaries for clustering. However, it is frustratingly slow because it requires (N2+N)/2 compression attempts for the NCDs, where N is the number of given specimens. For fast clustering, this paper presents an algorithm for efficiently constructing a phylogenetic tree by greatly reducing compression attempts. The key idea to do so is not to construct a tree of N specimens all at once. Instead, it divides N specimens into temporal clusters in advance, constructs a small tree for each temporal cluster, and joins the trees as a united tree. Intuitively, separately constructing small trees requires a much smaller number of compression attempts than (N2+N)/2. With experiments using 4,109 in-the-wild malware specimens, we confirm that our algorithm achieved clustering 22 times faster than the neighbor-joining method with a good accuracy of 97%.

リンク情報
DOI
https://doi.org/10.1007/978-3-030-36708-4_63
Scopus
https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85077508217&origin=inward
Scopus Citedby
https://www.scopus.com/inward/citedby.uri?partnerID=HzOxMe3b&scp=85077508217&origin=inward
ID情報
  • DOI : 10.1007/978-3-030-36708-4_63
  • ISSN : 0302-9743
  • eISSN : 1611-3349
  • SCOPUS ID : 85077508217

エクスポート
BibTeX RIS