Scalable Graph-based Bug Search for Firmware Images
The DOI matches its Crossref record; 46 of the 46 references it cites were found in a registry or an index.
Abstract
Because of rampant security breaches in IoT devices, searching vulnerabilities in massive IoT ecosystems is more crucial than ever. Recent studies have demonstrated that control-flow graph (CFG) based bug search techniques can be effective and accurate in IoT devices across different architectures. However, these CFG-based bug search approaches are far from being scalable to handle an enormous amount of IoT devices in the wild, due to their expensive graph matching overhead. Inspired by rich experience in image and video search, we propose a new bug search scheme which addresses the scalability challenge in existing cross-platform bug search techniques and further improves search accuracy. Unlike existing techniques that directly conduct searches based upon raw features (CFGs) from the binary code, we convert the CFGs into high-level numeric feature vectors. Compared with the CFG feature, high-level numeric feature vectors are more robust to code variation across different architectures, and can easily achieve realtime search by using state-of-the-art hashing techniques. We have implemented a bug search engine, Genius, and compared it with state-of-art bug search approaches. Experimental results show that Genius outperforms baseline approaches for various query loads in terms of speed and accuracy. We also evaluated Genius on a real-world dataset of 33,045 devices which was collected from public sources and our system. The experiment showed that Genius can finish a search within 1 second on average when performed over 8,126 firmware images of 420,558,702 functions. By only looking at the top 50 candidates in the search result, we found 38 potentially vulnerable firmware images across 5 vendors, and confirmed 23 of them by our manual analysis. We also found that it took only 0.1 seconds on average to finish searching for all 154 vulnerabilities in two latest commercial firmware images from D-LINK. 103 of them are potentially vulnerable in these images, and 16 of them were confirmed.
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
Advances in neural information processing systems 7
Cios, K., & Shields, M. (1997) · Neurocomputing · doi:10.1016/s0925-2312(97)90018-7 · Cited by 22,059
On Spectral Clustering: Analysis and an algorithm
Ng, A. Y., Jordan, M. I., & Weiss, Y. (2001) · Cited by 8,159
Newman, M. (2010) · doi:10.1093/acprof:oso/9780199206650.001.0001 · Cited by 6,595
Video Google: a text retrieval approach to object matching in videos
Sivic, & Zisserman (2003) · Proceedings Ninth IEEE International Conference on Computer Vision · doi:10.1109/iccv.2003.1238663 · Cited by 6,367 · cited 1×
“This invariance property has been verified in a number of image retrieval system [53,59] such as the Google image search.”
MethodA comparison of event models for naive bayes text classification
McCallum, A., & Nigam, K. (1998) · Cited by 3,289
CCFinder: a multilinguistic token-based code clone detection system for large scale source code
Kamiya, T., Kusumoto, S., & Inoue, K. (2002) · IEEE Transactions on Software Engineering · doi:10.1109/tse.2002.1019480 · Cited by 1,711
Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions
Andoni, A., & Indyk, P. (2008) · Communications of the ACM · doi:10.1145/1327452.1327494 · Cited by 1,437 · cited 1×
“Finally, given a function, online search aims at efficiently finding its most similar functions by Locality Sensitive Hashing (LSH) [9].”
BackgroundA Survey of Recent Advances in Hierarchical Clustering Algorithms
Murtagh, F. (1983) · The Computer Journal · doi:10.1093/comjnl/26.4.354 · Cited by 1,058
Driller: Augmenting Fuzzing Through Selective Symbolic Execution
Stephens, N., Grosen, J., Salls, C., Dutcher, A., Wang, R., Corbetta, J., Shoshitaishvili, Y., Kruegel, C., & Vigna, G. (2016) · Proceedings 2016 Network and Distributed System Security Symposium · doi:10.14722/ndss.2016.23368 · Cited by 887
The devil is in the details: an evaluation of recent feature encoding methods
Chatfield, K., Lempitsky, V., Vedaldi, A., & Zisserman, A. (2011) · Procedings of the British Machine Vision Conference 2011 · doi:10.5244/c.25.76 · Cited by 834 · cited 1×
“This step is known as feature encoding [16].”
BackgroundEvaluating bag-of-visual-words representations in scene classification
Yang, J., Jiang, Y.-G., Hauptmann, A. G., & Ngo, C.-W. (2007) · Proceedings of the international workshop on Workshop on multimedia information retrieval · doi:10.1145/1290082.1290111 · Cited by 825
A graph distance metric based on the maximal common subgraph
Bunke, H., & Shearer, K. (1998) · Pattern Recognition Letters · doi:10.1016/s0167-8655(97)00179-7 · Cited by 754
Arandjelovic, R., & Zisserman, A. (2013) · 2013 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2013.207 · Cited by 713
Approximate graph edit distance computation by means of bipartite graph matching
Riesen, K., & Bunke, H. (2009) · Image and Vision Computing · doi:10.1016/j.imavis.2008.04.004 · Cited by 651
A Large-Scale Analysis of the Security of Embedded Firmwares
Costin, A., Zaddach, J., Francillon, A., & Balzarotti, D. (2014) · HAL · Cited by 548
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
Self-citationCP-Miner: a tool for finding copy-paste and related bugs in operating system code
Li, Z., Lu, S., Myagmar, S., & Zhou, Y. (2004) · Operating Systems Design and Implementation · Cited by 410
Cross-Architecture Bug Search in Binary Executables
Pewny, J., Garmany, B., Gawlik, R., Rossow, C., & Holz, T. (2015) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp.2015.49 · Cited by 398
Towards Automated Dynamic Analysis for Linux-based Embedded Firmware
Chen, D. D., Egele, M., Woo, M., & Brumley, D. (2016) · Proceedings 2016 Network and Distributed System Security Symposium · doi:10.14722/ndss.2016.23415 · Cited by 366
Firmalice - Automatic Detection of Authentication Bypass Vulnerabilities in Binary Firmware
Shoshitaishvili, Y., Wang, R., Hauser, C., Kruegel, C., & Vigna, G. (2015) · Proceedings 2015 Network and Distributed System Security Symposium · doi:10.14722/ndss.2015.23294 · Cited by 362
Locality-Sensitive Hashing for Finding Nearest Neighbors [Lecture Notes]
Slaney, M., & Casey, M. (2008) · IEEE Signal Processing Magazine · doi:10.1109/msp.2007.914237 · Cited by 340
Avatar: A Framework to Support Dynamic Security Analysis of Embedded Systems’ Firmwares
Zaddach, J., Bruno, L., Francillon, A., & Balzarotti, D. (2014) · Proceedings 2014 Network and Distributed System Security Symposium · doi:10.14722/ndss.2014.23229 · Cited by 327
Recognizing functions in binaries with neural networks
Shin, E. C. R., Song, D. X., & Moazzezi, R. (2015) · USENIX Security Symposium · 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
Avgerinos, T., Cha, S. K., Rebert, A., Schwartz, E. J., Woo, M., & Brumley, D. (2014) · Communications of the ACM · doi:10.1145/2560217.2560219 · Cited by 263
BinHunt: Automatically Finding Semantic Differences in Binary Programs
Gao, D., Reiter, M. K., & Song, D. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-88625-9_16 · Cited by 255
ReDeBug: Finding Unpatched Code Clones in Entire OS Distributions
Jang, J., Agrawal, A., & Brumley, D. (2012) · 2012 IEEE Symposium on Security and Privacy · doi:10.1109/sp.2012.13 · Cited by 246
Optimizing Seed Selection for Fuzzing
Rebert, A., Cha, S. K., Avgerinos, T., Foote, J. M., Warren, D., Grieco, G., & Brumley, D. (2018) · KiltHub Repository · doi:10.1184/r1/6469118 · Cited by 231
Program-Adaptive Mutational Fuzzing
Cha, S. K., Woo, M., & Brumley, D. (2015) · 2015 IEEE Symposium on Security and Privacy · doi:10.1109/sp.2015.50 · Cited by 231
VCCFinder: Finding Potential Vulnerabilities in Open-Source Projects to Assist Code Audits
Perl, H., Dechand, S., Smith, M., Arp, D., Yamaguchi, F., Rieck, K., Fahl, S., & Acar, Y. (2015) · Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/2810103.2813604 · Cited by 229
Automatic Inference of Search Patterns for Taint-Style Vulnerabilities
Yamaguchi, F., Maier, A., Gascon, H., & Rieck, K. (2015) · 2015 IEEE Symposium on Security and Privacy · doi:10.1109/sp.2015.54 · Cited by 189
K-gram based software birthmarks
Myles, G., & Collberg, C. (2005) · Proceedings of the 2005 ACM symposium on Applied computing · doi:10.1145/1066677.1066753 · Cited by 187
Blanket Execution: Dynamic Similarity Testing for Program Binaries and Components
Egele, M., Woo, M., Chapman, P., & Brumley, D. (2014) · KiltHub Repository · doi:10.1184/r1/6468446 · Cited by 187
Structural Comparison of Executable Objects
Flake, H. (2004) · Technische Universität Dortmund Eldorado (Technische Universität Dortmund) · doi:10.17877/de290r-2007 · Cited by 182
Finding unknown malice in 10 seconds: mass vetting for new threats at the Google-play scale
Chen, K., Wang, P., Lee, Y., Wang, X., Zhang, N., Huang, H., Zou, W., & Liu, P. (2015) · USENIX Security Symposium · Cited by 160
Rendezvous: A search engine for binary code
Khoo, W. M., Mycroft, A., & Anderson, R. (2013) · International Conference on Mining Software Repositories (MSR) · doi:10.1109/msr.2013.6624046 · Cited by 153
Tracelet-based code search in executables
David, Y., & Yahav, E. (2014) · Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation · doi:10.1145/2594291.2594343 · Cited by 134
iBinHunt: Binary Hunting with Inter-procedural Control Flow
Ming, J., Pan, M., & Gao, D. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-37682-5_8 · Cited by 133
Approximate clustering without the approximation
Balcan, M.-F., Blum, A. L., & Gupta, A. (2009) · KiltHub Repository · doi:10.5555/1496770.1496886 · Cited by 121
Effect of separate sampling on classification accuracy
Esfahani, M. S., & Dougherty, E. R. (2013) · Bioinformatics · doi:10.1093/bioinformatics/btt662 · Cited by 115
Zero-Example Event Search using MultiModal Pseudo Relevance Feedback
Jiang, L., Mitamura, T., Yu, S.-I., & Hauptmann, A. G. (2014) · International Conference on Multimedia Retrieval · doi:10.1145/2578726.2578764 · Cited by 64
Bridging the Ultimate Semantic Gap: A Semantic Search Engine for Internet Videos
Jiang, L., Yu, S.-I., Meng, D., Mitamura, T., & Hauptmann, A. G. (2015) · International Conference on Multimedia Retrieval · doi:10.1145/2671188.2749399 · Cited by 61
Towards Automatic Generation of Security-Centric Descriptions for Android Apps
Zhang, M., Duan, Y., Qian, F., & Yin, H. (2015) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/2810103.2813669 · Cited by 61
Self-citationContent-Based Video Search over 1 Million Videos with 1 Core in 1 Second
Yu, S.-I., Jiang, L., Xu, Z., Yang, Y., & Hauptmann, A. G. (2015) · International Conference on Multimedia Retrieval · doi:10.1145/2671188.2749398 · Cited by 31
Cybersecurity and the Internet of Things
Biedermann, C. (2016) · Zagadnienia Informacji Naukowej - Studia Informacyjne · doi:10.36702/zin.301 · Cited by 15
Towards Efficient Learning of Optimal Spatial Bag-of-Words Representations
Jiang, L., Tong, W., Meng, D., et al. (2014) · doi:10.1145/2578726.2578739 · Cited by 14
Cited by
Neshenko, N., Bou-Harb, E., Crichigno, J., Kaddoum, G., & Ghani, N. (2019) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2019.2910750 · Cited by 827
Ding, S. H. H., Fung, B. C. M., & Charland, P. (2019) · 2019 IEEE Symposium on Security and Privacy (SP) · doi:10.1109/sp.2019.00003 · Cited by 438
Detecting Vulnerability on IoT Device Firmware: A Survey
Feng, X., Zhu, X., Han, Q.-L., Zhou, W., Wen, S., & Xiang, Y. (2023) · IEEE/CAA Journal of Automatica Sinica · doi:10.1109/jas.2022.105860 · Cited by 185
The Threat of Offensive AI to Organizations
Mirsky, Y., Demontis, A., Kotak, J., Shankar, R., Gelei, D., Yang, L., Zhang, X., Pintor, M., Lee, W., Elovici, Y., et al. (2023) · Computers & Security · doi:10.1016/j.cose.2022.103006 · Cited by 97
Metadata
- Authors
- Feng, Q., Zhou, R., Xu, C., Cheng, Y., Testa, B., & Yin, H.
- Venue
- Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security
- Publisher
- ACM
- Published
- 2016-10-24
- Pages
- 480-491
- OpenAlex
- W2532962075
- Cited by
- 401
- References
- 46
- FWCI
- 11.80
- 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.