Large-scale malware indexing using function-call graphs
The DOI matches its Crossref record; 23 of the 23 references it cites were found in a registry or an index.
Abstract
A major challenge of the anti-virus (AV) industry is how to effectively process the huge influx of malware samples they receive every day. One possible solution to this problem is to quickly determine if a new malware sample is similar to any previously-seen malware program. In this paper, we design, implement and evaluate a malware database management system called SMIT (Symantec Malware Indexing Tree) that can efficiently make such determination based on malware's function-call graphs, which is a structural representation known to be less susceptible to instruction-level obfuscations commonly employed by malware writers to evade detection of AV software. Because each malware program is represented as a graph, the problem of searching for the most similar malware program in a database to a given malware sample is cast into a nearest-neighbor search problem in a graph database. To speed up this search, we have developed an efficient method to compute graph similarity that exploits structural and instruction-level information in the underlying malware programs, and a multi-resolution indexing scheme that uses a computationally economical feature vector for early pruning and resorts to a more accurate but computationally more expensive graph similarity function only when it needs to pinpoint the most similar neighbors. Results of a comprehensive performance study of the SMIT prototype using a database of more than 100,000 malware demonstrate the effective pruning power and scalability of its nearest neighbor search mechanisms.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
(1979) · Cited by 43,841
The Hungarian method for the assignment problem
Kuhn, H. W. (1955) · Naval Research Logistics Quarterly · doi:10.1002/nav.3800020109 · Cited by 13,120
An Algorithm for Subgraph Isomorphism
Ullmann, J. R. (1976) · Journal of the ACM · doi:10.1145/321921.321925 · Cited by 2,277
Simple Fast Algorithms for the Editing Distance between Trees and Related Problems
Zhang, K., & Shasha, D. (1989) · SIAM Journal on Computing · doi:10.1137/0218082 · Cited by 1,310
(1993) · doi:10.5555/313559.313789 · Cited by 998
Similarity Search The Metric Space Approach
Zezula, P., Amato, G. M., Dohnal, V., & Batko, M. (2006) · The Kluwer international series on advances in database systems · doi:10.1007/0-387-29151-2 · Cited by 962
Graph indexing: a frequent structure-based approach
Yan, X., Yu, P. S., & Han, J. (2004) · Proceedings of the 2004 ACM SIGMOD international conference on Management of data · doi:10.1145/1007568.1007607 · Cited by 637
Scalable, behavior-based malware clustering
Bayer, U. (2009) · Cited by 603
Learning and Classification of Malware Behavior
Rieck, K., Holz, T., Willems, C., Düssel, P., & Laskov, P. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-70542-0_6 · Cited by 589
Learning to Detect and Classify Malicious Executables in the Wild
Kolter, J. Z., & Maloof, M. A. (2006) · doi:10.5555/1248547.1248646 · Cited by 562
Automated Classification and Analysis of Internet Malware
Bailey, M., Oberheide, J., Andersen, J. H., Mao, Z. M., Jahanian, F., & Nazario, J. (2007) · Lecture notes in computer science · doi:10.1007/978-3-540-74320-0_10 · Cited by 531
Algorithmics and applications of tree and graph searching
Shasha, D., Wang, J. T. L., & Giugno, R. (2002) · Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems · doi:10.1145/543613.543620 · Cited by 387
Polymorphic Worm Detection Using Structural Information of Executables
Kruegel, C., Kirda, E., Mutz, D., Robertson, W., & Vigna, G. (2006) · Lecture notes in computer science · doi:10.1007/11663812_11 · Cited by 337
Distance-based indexing for high-dimensional metric spaces
Bozkaya, T., & Ozsoyoglu, M. (1997) · Proceedings of the 1997 ACM SIGMOD international conference on Management of data - SIGMOD '97 · doi:10.1145/253260.253345 · Cited by 332
Substructure similarity search in graph databases
Yan, X., Yu, P. S., & Han, J. (2005) · Proceedings of the 2005 ACM SIGMOD international conference on Management of data · doi:10.1145/1066157.1066244 · Cited by 314
Closure-Tree: An Index Structure for Graph Queries
He, H., & Singh, A. K. (2006) · 22nd International Conference on Data Engineering (ICDE'06) · doi:10.1109/icde.2006.37 · Cited by 293
Graph indexing: tree + delta <= graph
Zhao, P., Yu, J. X., & Yu, P. S. (2007) · Very Large Data Bases · Cited by 260
Efficient matching and indexing of graph models in content-based retrieval
Berretti, S., Del Bimbo, A., & Vicario, E. (2001) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.954600 · Cited by 225
OmniUnpack: Fast, Generic, and Safe Unpacking of Malware
Martignoni, L., Christodorescu, M., & Jha, S. (2007) · Twenty-Third Annual Computer Security Applications Conference (ACSAC 2007) · doi:10.1109/acsac.2007.15 · Cited by 208
A binary linear programming formulation of the graph edit distance
Justice, D., & Hero, A. (2006) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2006.152 · Cited by 184
A Study of the Packer Problem and Its Solutions
Guo, F., Ferrie, P., & Chiueh, T.-C. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-87403-4_6 · Cited by 180
Self-citationMyers, R., Wison, R. C., & Hancock, E. R. (2000) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.862201 · Cited by 171
Bipartite Graph Matching for Computing the Edit Distance of Graphs
Riesen, K., Neuhaus, M., & Horst Bunke, A. (2007) · Lecture notes in computer science · doi:10.1007/978-3-540-72903-7_1 · Cited by 137
Cited by
Semantics-Aware Android Malware Classification Using Weighted Contextual API Dependency Graphs
Zhang, M., Duan, Y., Yin, H., & Zhao, Z. (2014) · Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/2660267.2660359 · Cited by 453
Novel Feature Extraction, Selection and Fusion for Effective Malware Family Classification
Ahmadi, M., Ulyanov, D., Semenov, S., Trofimov, M., & Giacinto, G. (2016) · Proceedings of the Sixth ACM Conference on Data and Application Security and Privacy · doi:10.1145/2857705.2857713 · Cited by 359
Structural detection of android malware using embedded call graphs
Gascon, H., Yamaguchi, F., Arp, D., & Rieck, K. (2013) · Proceedings of the 2013 ACM workshop on Artificial intelligence and security · doi:10.1145/2517312.2517315 · Cited by 329
Smashing the Gadgets: Hindering Return-Oriented Programming Using In-place Code Randomization
Pappas, V., Polychronakis, M., & Keromytis, A. D. (2012) · 2012 IEEE Symposium on Security and Privacy · doi:10.1109/sp.2012.41 · Cited by 322
discovRE: Efficient Cross-Architecture Identification of Bugs in Binary Code
Eschweiler, S., Yakdan, K., & Gerhards-Padilla, E. (2016) · Proceedings 2016 Network and Distributed System Security Symposium · doi:10.14722/ndss.2016.23185 · Cited by 302
Metadata
- Authors
- Hu, X., Chiueh, T.-C., & Shin, K. G.
- Venue
- Proceedings of the 16th ACM conference on Computer and communications security
- Publisher
- ACM
- Published
- 2009-11-09
- Pages
- 611-620
- ISSN
- 1543-7221 (ISSN-L)
- OpenAlex
- W2068211976
- Cited by
- 312
- References
- 23
- FWCI
- 17.69
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.