The DOI matches its Crossref record; 23 of the 23 references it cites were found in a registry or an index.
Large-scale malware indexing using function-call graphs
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.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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
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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Large-scale malware indexing using function-call graphs. https://app.cochat.ai/papers/10.1145/1653662.1653736
- The paper
- Hu, X., Chiueh, T.-C., & Shin, K. G. (2009). Large-scale malware indexing using function-call graphs. Proceedings of the 16th ACM conference on Computer and communications security. https://doi.org/10.1145/1653662.1653736
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.