research-article

Input generation via decomposition and re-stitching: finding bugs in Malware

Authors:

Juan Caballero,

Pongsin Poosankam,

Stephen McCamant,

Domagoj Babi ć,

Dawn SongAuthors Info & Claims

CCS '10: Proceedings of the 17th ACM conference on Computer and communications security

Pages 413 - 425

https://doi.org/10.1145/1866307.1866354

Published: 04 October 2010 Publication History

Abstract

Attackers often take advantage of vulnerabilities in benign software, and the authors of benign software must search their code for bugs in hopes of finding vulnerabilities before they are exploited. But there has been little research on the converse question of whether defenders can turn the tables by finding vulnerabilities in malware. We provide a first affirmative answer to that question. We introduce a new technique, stitched dynamic symbolic execution, that makes it possible to use exploration techniques based on symbolic execution in the presence of functionalities that are common in malware and otherwise hard to analyze, such as decryption and checksums. The technique is based on decomposing the constraints induced by a program, solving only a subset, and then re-stitching the constraint solution into a complete input. We implement the approach in a system for x86 binaries, and apply it to 4 prevalent families of bots and other malware. We find 6 bugs that could be exploited by a network attacker to terminate or subvert the malware. These bugs have persisted across malware revisions for months, and even years. We discuss the possible applications and ethical considerations of this new capability

References

[1]

}}BitBlaze: Binary analysis for computer security. http://bitblaze.cs.berkeley.edu/.

[2]

}}D. Brumley, J. Caballero, Z. Liang, J. Newsome, and D. Song. Towards automatic discovery of deviations in binary implementations with applications to error detection and fingerprint generation. In Proceedings of the 16th USENIX Security Symposium, pages 213--228, Montreal, Quebec, Canada, Aug. 2007.

Digital Library

[3]

}}D. Brumley, P. Poosankam, D. Song, and J. Zheng. Automatic patch-based exploit generation is possible: Techniques and implications. In IEEE Symposium on Security and Privacy, 2008.

Digital Library

[4]

}}J. Caballero, N. M. Johnson, S. McCamant, and D. Song. Binary code extraction and interface identification for security applications. In NDSS'10: Proceedings of the 17th Annual Network and Distributed System Security Symposium, pages 391--408, San Diego, California, USA, Mar. 2010.

[5]

}}J. Caballero, Z. Liang, P. Poosankam, and D. Song. Towards generating high coverage vulnerability-based signatures with protocol-level constraint-guided exploration. In RAID'09: Proceedings of the 12th International Symposium on Recent Advances in Intrusion Detection, volume 5758 of Lecture Notes in Computer Science, Saint-Malo, France, Sept. 2009.

Digital Library

[6]

}}J. Caballero, P. Poosankam, C. Kreibich, and D. Song. Dispatcher: Enabling active botnet infiltration using automatic protocol reverse-engineering. In CCS'09: Proceedings of the 16th ACM Conference on Computer and Communications Security, pages 621--634, Chicago, Illinois, USA, Nov. 2009.

Digital Library

[7]

}}C. Cadar and D. R. Engler. Execution generated test cases: How to make systems code crash itself. In SPIN'05: Proceedings of the 12th International SPIN Workshop on Model Checking Software, volume 3639 of Lecture Notes in Computer Science, pages 2--23, San Francisco, California, USA, Aug. 2005.

Digital Library

[8]

}}L. Cavallaro, P. Saxena, and R. Sekar. On the limits of information flow techniques for malware analysis and containment. In DIMVA'08: Proceedings of the Fifth Conference on Detection of Intrusions and Malware & Vulnerability Assessment, volume 5137 of Lecture Notes in Computer Science, pages 143--163, Paris, France, July 2008.

Digital Library

[9]

}}CVE: Common vulnerabilities and exposures. http://cve.mitre.org/.

[10]

}}J. Daemen and V. Rijmen. The Design of Rijndael: AES - The Advanced Encryption Standard. Springer, Heidelberg, Germany, Mar. 2002.

Digital Library

[11]

}}D. Danchev. Help! someone hijacked my 100k+ Zeus botnet!, Feb. 2009. http://ddanchev.blogspot.com/2009/02/ help-someone-hijacked-my-100k-zeus.html.

[12]

}}D. De, A. Kumarasubramanian, and R. Venkatesan. Inversion attacks on secure hash functions using SAT solvers. In SAT'07: Proceedings of the Tenth International Conference on Theory and Applications of Satisfiability Testing, volume 4501 of Lecture Notes in Computer Science, pages 377--382, Lisbon, Portugal, 2007.

Digital Library

[13]

}}D. Dittrich, F. Leder, and T. Werner. A case study in ethical decision making regarding remote mitigation of botnets. In WECSR'10: Workshop on Ethics in Computer Security Research, Lecture Notes in Computer Science, Tenerife, Canary Islands, Spain, Jan. 2010.

Digital Library

[14]

}}J. W. Duran and S. C. Ntafos. An evaluation of random testing. IEEE Trans. Software Eng., 10(4):438--444, 1984.

Digital Library

[15]

}}Security guru gives hackers a taste of their own medicine, Apr. 2008. http://www.wired.com/threatlevel/ 2008/04/researcher-demo.

[16]

}}V. Ganesh and D. L. Dill. A decision procedure for bit-vectors and arrays. In CAV'07: Proceedings of the 19th International Conference on Computer Aided Verification, volume 4590 of Lecture Notes in Computer Science, pages 519--531, Berlin, Germany, July 2007.

Digital Library

[17]

}}V. Ganesh, T. Leek, and M. C. Rinard. Taint-based directed whitebox fuzzing. In ICSE'09: Proceedings of the 31st International Conference on Software Engineering, pages 474--484, Vancouver, British Columbia, Canada, May 2009.

Digital Library

[18]

}}P. Godefroid. Compositional dynamic test generation. In POPL'07: Proceedings of the 34th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 47--54, Nice, France, Jan. 2007.

Digital Library

[19]

}}P. Godefroid, A. Kie Ùzun, and M. Y. Levin. Grammar-based whitebox fuzzing. In PLDI'08: Proceedings of the ACM SIGPLAN 2008 Conference on Programming Language Design and Implementation, pages 206--215, Tucson, Arizona, USA, June 2008.

Digital Library

[20]

}}P. Godefroid, N. Klarlund, and K. Sen. DART: directed automated random testing. In PLDI'05: Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 213--223, Chicago, Illinois, USA, June 2005.

Digital Library

[21]

}}P. Godefroid, M. Y. Levin, and D. A. Molnar. Automated whitebox fuzz testing. In NDSS'08: Proceedings of the Network and Distributed System Security Symposium, San Diego, California, USA, Feb. 2008.

[22]

}}M. Kassner. The top 10 spam botnets: New and improved, Feb. 2010. http://blogs.techrepublic.com. com/10things/?p=1373.

[23]

}}A. Kie Ùzun, P. J. Guo, K. Jayaraman, and M. D. Ernst. Automatic creation of SQL injection and cross-site scripting attacks. In ICSE'09: Proceedings of the 31st International Conference on Software Engineering, pages 199--209, Vancouver, British Columbia, Canada, May 2009.

Digital Library

[24]

}}J. C. King. Symbolic execution and program testing. Communications of the ACM, 19(7):385--394, 1976.

Digital Library

[25]

}}C. Kolbitsch, T. Holz, C. Kruegel, and E. Kirda. Inspector Gadget: Automated extraction of proprietary gadgets from malware binaries. In SP'10: Proceedings of the 31st IEEE Symposium on Security and Privacy, Oakland, California, USA, May 2010.

Digital Library

[26]

}}J. Leyden. Monster botnet held 800,000 people's details. The Register, Mar. 2010. http://www.theregister.co.uk/2010/03/04/ mariposa_police_hunt_more_botherders/.

[27]

}}M86 Security Labs. Botnet statistics for week ending April 11, 2010, Apr. 2010. http://www.m86security. com/labs/bot_statistics.asp.

[28]

}}S. McCamant and M. D. Ernst. Quantitative information flow as network flow capacity. In PLDI'08: Proceedings of the ACM SIGPLAN 2008 Conference on Programming Language Design and Implementation, pages 193--205, Tucson, Arizona, USA, June 2008.

Digital Library

[29]

}}Smashing the Mega-d/Ozdok botnet in 24 hours. http://blog.fireeye.com/research/2009/ 11/smashing-the-ozdok.html.

[30]

}}B. P. Miller, L. Fredriksen, and B. So. An empirical study of the reliability of unix utilities. Communications of the ACM, 33(12):32--44, 1990.

Digital Library

[31]

}}D. Molnar, X. C. Li, and D. Wagner. Dynamic test generation to find integer bugs in x86 binary Linux programs. In Proceedings of the 18th USENIX Security Symposium, pages 67--81, Montreal, Quebec, Canada, Aug. 2009.

Digital Library

[32]

}}National Institute of Standards and Technology, Gaithersburg, MD, USA. Federal Information Processing Standard 180--2: Secure Hash Standard, Aug. 2002.

[33]

}}OpenSSL: The open source toolkit for SSL/TLS. http://www.openssl.org/.

[34]

}}OSVDB. Cutwail Bot svchost.exe CC Message Handling Remote Overflow, July 2010. http://osvdb.org/66497.

[35]

}}OSVDB. Gheg Bot RtlAllocateHeap Function Null Dereference Remote DoS, July 2010. http://osvdb.org/66498.

[36]

}}OSVDB. Zbot Trojan svchost.exe Compressed Input Handling Remote Overflow, July 2010. http://osvdb.org/66501.

[37]

}}OSVDB. Zbot Trojan svchost.exe Network Message Crafted Payload Size Handling Infinite Loop Remote DoS, July 2010. http://osvdb.org/66500.

[38]

}}OSVDB. Zbot Trojan svchost.exe RtlAllocateHeap Function Null Dereference Remote DoS, July 2010. http://osvdb.org/66499.

[39]

}}W. A. Owens, K. W. Dam, and H. S. Lin, editors. Technology, Policy, Law, and Ethics Regarding U.S. Acquisition and Use of Cyberattack Capabilities. The National Academies Press, Washington, DC, USA, 2009.

Digital Library

[40]

}}B. Potter, Beetle, CowboyM, D. Moniz, R. Thayer, 3ricj, and Pablos. Shmoo-fu: Hacker goo, goofs, and gear with the shmoo. In DEFCON, Las Vegas, Nevada, USA, July 2005. http://www.defcon.org/images/defcon-13/dc13- presentations/dc-13-beetle-shmoo-fu.pdf.

[41]

}}Shadowserver foundation. http://www.shadowserver.org/.

[42]

}}D. Song, D. Brumley, H. Yin, J. Caballero, I. Jager, M. G. Kang, Z. Liang, J. Newsome, P. Poosankam, and P. Saxena. BitBlaze: A new approach to computer security via binary analysis (keynote invited paper). In ICISS'08: Proceedings of the 4th International Conference on Information Systems Security, volume 5352 of Lecture Notes in Computer Science, pages 1--25, Hyderabad, India, Dec. 2008.

Digital Library

[43]

}}T. Wang, T. Wei, G. Gu, and W. Zou. TaintScope: A checksum-aware directed fuzzing tool for automatic software vulnerability detection. In SP'10: Proceedings of the 31st IEEE Symposium on Security and Privacy, Oakland, California, USA, May 2010.

Digital Library

[44]

}}Z. Wang, X. Jiang, W. Cui, X. Wang, and M. Grace. ReFormat: Automatic reverse engineering of encrypted messages. In ESORICS'09: 14th European Symposium on Research in Computer Security, volume 5789 of Lecture Notes in Computer Science, pages 200--215, Saint-Malo, France, Sept. 2009.

Digital Library

[45]

}}Y. Xie and A. Aiken. Scalable error detection using boolean satisfiability. In POPL'05: Proceedings of the 32nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 351--363, Long Beach, California, USA, Jan. 2005.

Digital Library

[46]

}}The zlib library. http://www.zlib.net/.

Cited By

Botacin M(2024)Fuzzing and Symbolic Execution for Multipath Malware Tracing: Bridging Theory and Practice via Survey and ExperimentsDigital Threats: Research and Practice10.1145/37001475:4(1-33)Online publication date: 11-Oct-2024
https://dl.acm.org/doi/10.1145/3700147
Wang LYang YAlavalapati G(2024)Analyzing Implementation-Based SSL/TLS Vulnerabilities with Binary Semantics AnalysisSecurity and Privacy in Communication Networks10.1007/978-3-031-64954-7_19(371-394)Online publication date: 15-Oct-2024
https://doi.org/10.1007/978-3-031-64954-7_19
Luo CMing JFu JPeng GLi Z(2023)Reverse Engineering of Obfuscated Lua Bytecode via Interpreter Semantics TestingIEEE Transactions on Information Forensics and Security10.1109/TIFS.2023.328925418(3891-3905)Online publication date: 2023
https://doi.org/10.1109/TIFS.2023.3289254
Show More Cited By

Index Terms

Input generation via decomposition and re-stitching: finding bugs in Malware
1. Security and privacy
  1. Systems security
    1. Operating systems security

Recommendations

Malware classification method via binary content comparison
RACS '12: Proceedings of the 2012 ACM Research in Applied Computation Symposium

With the wide spread uses of the Internet, the number of Internet attacks keeps increasing, and malware is the main cause of most Internet attacks. Malware is used by attackers to infect normal users' computers and to acquire private information as well ...
Detecting, validating and characterizing computer infections in the wild
IMC '11: Proceedings of the 2011 ACM SIGCOMM conference on Internet measurement conference

Although network intrusion detection systems (IDSs) have been studied for several years, their operators are still overwhelmed by a large number of false-positive alerts. In this work we study the following problem: from a large archive of intrusion ...
Correlation Analysis between Spamming Botnets and Malware Infected Hosts
SAINT '11: Proceedings of the 2011 IEEE/IPSJ International Symposium on Applications and the Internet

Many of recent cyber attacks are being launched by botnets for the purpose of carrying out large-scale cyber attacks such as spam emails, Distributed Denial of Service (DDoS), network scanning and so on. In many cases, these botnets consist of a lot of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CCS '10: Proceedings of the 17th ACM conference on Computer and communications security

October 2010

782 pages

ISBN:9781450302456

DOI:10.1145/1866307

General Chair:
Ehab Al-Shaer
University of North Carolina, Charlotte, USA
,
Program Chairs:
Angelos D. Keromytis
Columbia University, USA
,
Vitaly Shmatikov
University of Texas at Austin, USA

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGSAC: ACM Special Interest Group on Security, Audit, and Control

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 October 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

CCS '10

Sponsor:

SIGSAC

CCS '10: 17th ACM Conference on Computer and Communications Security 2010

October 4 - 8, 2010

Illinois, Chicago, USA

Acceptance Rates

CCS '10 Paper Acceptance Rate 55 of 325 submissions, 17%;

Overall Acceptance Rate 1,261 of 6,999 submissions, 18%

Upcoming Conference

CCS '25

Sponsor:
sigsac

ACM SIGSAC Conference on Computer and Communications Security

October 13 - 17, 2025

Taipei , Taiwan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

41
Total Citations
View Citations
790
Total Downloads

Downloads (Last 12 months)27
Downloads (Last 6 weeks)7

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Botacin M(2024)Fuzzing and Symbolic Execution for Multipath Malware Tracing: Bridging Theory and Practice via Survey and ExperimentsDigital Threats: Research and Practice10.1145/37001475:4(1-33)Online publication date: 11-Oct-2024
https://dl.acm.org/doi/10.1145/3700147
Wang LYang YAlavalapati G(2024)Analyzing Implementation-Based SSL/TLS Vulnerabilities with Binary Semantics AnalysisSecurity and Privacy in Communication Networks10.1007/978-3-031-64954-7_19(371-394)Online publication date: 15-Oct-2024
https://doi.org/10.1007/978-3-031-64954-7_19
Luo CMing JFu JPeng GLi Z(2023)Reverse Engineering of Obfuscated Lua Bytecode via Interpreter Semantics TestingIEEE Transactions on Information Forensics and Security10.1109/TIFS.2023.328925418(3891-3905)Online publication date: 2023
https://doi.org/10.1109/TIFS.2023.3289254
Yang ZYuan ZJin SChen XSun LDu XLi WZhang H(2022)FSAFlow: Lightweight and Fast Dynamic Path Tracking and Control for Privacy Protection on Android Using Hybrid Analysis with State-Reduction Strategy2022 IEEE Symposium on Security and Privacy (SP)10.1109/SP46214.2022.9833764(2114-2129)Online publication date: May-2022
https://doi.org/10.1109/SP46214.2022.9833764
Aman MBasheer MDash SSancheti AWong JXu JLim HSikdar B(2022)PRoM: Passive Remote Attestation Against Roving Malware in Multicore IoT DevicesIEEE Systems Journal10.1109/JSYST.2021.306643716:1(789-800)Online publication date: Mar-2022
https://doi.org/10.1109/JSYST.2021.3066437
Yong Wong MLanden MAntonakakis MBlough DRedmiles EAhamad MKim YKim JVigna GShi E(2021)An Inside Look into the Practice of Malware AnalysisProceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security10.1145/3460120.3484759(3053-3069)Online publication date: 12-Nov-2021
https://dl.acm.org/doi/10.1145/3460120.3484759
Park KSahin BChen YZhao JDowning EHu HLee WCao JHo Au MLin ZYung M(2021)Identifying Behavior Dispatchers for Malware AnalysisProceedings of the 2021 ACM Asia Conference on Computer and Communications Security10.1145/3433210.3457894(759-773)Online publication date: 24-May-2021
https://dl.acm.org/doi/10.1145/3433210.3457894
Manes VHan HHan CCha SEgele MSchwartz EWoo M(2021)The Art, Science, and Engineering of Fuzzing: A SurveyIEEE Transactions on Software Engineering10.1109/TSE.2019.294656347:11(2312-2331)Online publication date: 1-Nov-2021
https://doi.org/10.1109/TSE.2019.2946563
Li TLi JHe X(2021)An Improvement of AFL Based On The Function Call Depth2021 18th International Computer Conference on Wavelet Active Media Technology and Information Processing (ICCWAMTIP)10.1109/ICCWAMTIP53232.2021.9674138(440-445)Online publication date: 17-Dec-2021
https://doi.org/10.1109/ICCWAMTIP53232.2021.9674138
Yilmaz FSridhar MChoi W(2020)Guide Me to Exploit: Assisted ROP Exploit Generation for ActionScript Virtual MachineProceedings of the 36th Annual Computer Security Applications Conference10.1145/3427228.3427568(386-400)Online publication date: 7-Dec-2020
https://dl.acm.org/doi/10.1145/3427228.3427568
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten