More Web Proxy on the site http://driver.im/

Article

Dowsing for overflows: a guided fuzzer to find buffer boundary violations

Authors:

Asia Slowinska,

Matthias Neugschwandtner,

Herbert BosAuthors Info & Claims

SEC'13: Proceedings of the 22nd USENIX conference on Security

Pages 49 - 64

Published: 14 August 2013 Publication History

Abstract

Dowser is a 'guided' fuzzer that combines taint tracking, program analysis and symbolic execution to find buffer overflow and underflow vulnerabilities buried deep in a program's logic. The key idea is that analysis of a program lets us pinpoint the right areas in the program code to probe and the appropriate inputs to do so.

Intuitively, for typical buffer overflows, we need consider only the code that accesses an array in a loop, rather than all possible instructions in the program. After finding all such candidate sets of instructions, we rank them according to an estimation of how likely they are to contain interesting vulnerabilities. We then subject the most promising sets to further testing. Specifically, we first use taint analysis to determine which input bytes influence the array index and then execute the program symbolically, making only this set of inputs symbolic. By constantly steering the symbolic execution along branch outcomes most likely to lead to overflows, we were able to detect deep bugs in real programs (like the nginx webserver, the inspircd IRC server, and the ffmpeg videoplayer). Two of the bugs we found were previously undocumented buffer overflows in ffmpeg and the poppler PDF rendering library.

References

[1]

CVE-2009-2629: Buffer underflow vulnerability in nginx. http://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2009- 2629, 2009.

[2]

ACZEL, A. D., AND SOUNDERPANDIAN, J. Complete Business Statistics, sixth ed. McGraw-Hill, 2006.

[3]

AKRITIDIS, P., CADAR, C., RAICIU, C., COSTA, M., AND CASTRO, M. Preventing memory error exploits with WIT. In Proceedings of the 2008 IEEE Symposium on Security and Privacy (2008), S&P'08.

[4]

BABIC, D., MARTIGNONI, L., MCCAMANT, S., AND SONG, D. Statically-directed dynamic automated test generation. In Proceedings of the 2011 International Symposium on Software Testing and Analysis (2011), ISSTA'11.

[5]

BANKS, G., COVA, M., FELMETSGER, V., ALMEROTH, K., KEMMERER, R., AND VIGNA, G. SNOOZE: toward a stateful network protocol fuzZEr. In Proceedings of the 9th international conference on Information Security (2006), ISC'06.

[6]

BAO, T., ZHENG, Y., LIN, Z., ZHANG, X., AND XU, D. Strict control dependence and its effect on dynamic information flow analyses. In Proceedings of the 19th International Symposium on Software testing and analysis (2010), ISSTA'10.

[7]

CADAR, C., DUNBAR, D., AND ENGLER, D. KLEE: Unassisted and automatic generation of high-coverage tests for complex systems programs. In Proceedings of the 8th USENIX Symposium on Operating Systems Design and Implementation (2008), OSDI'08.

[8]

CADAR, C., GANESH, V., PAWLOWSKI, P. M., DILL, D. L., AND ENGLER, D. R. EXE: Automatically generating inputs of death. In CCS '06: Proceedings of the 13th ACM conference on Computer and communications security (2006).

[9]

CAVALLARO, L., SAXENA, P., AND SEKAR, R. On the Limits of Information Flow Techniques for Malware Analysis and Containment. In Proceedings of the Fifth Conference on Detection of Intrusions and Malware & Vulnerability Assessment (2008), DIMVA'08.

[10]

CHIPOUNOV, V., KUZNETSOV, V., AND CANDEA, G. S2E: A platform for in vivo multi-path analysis of software systems. In Proceedings of the 16th Intl. Conference on Architectural Support for Programming Languages and Operating Systems (2011), ASPLOS'11.

[11]

COWAN, C., PU, C., MAIER, D., HINTONY, H., WALPOLE, J., BAKKE, P., BEATTIE, S., GRIER, A., WAGLE, P., AND ZHANG, Q. StackGuard: Automatic Adaptive Detection and Prevention of Buffer-Overflow Attacks. In Proceedings of the 7th USENIX Security Symposium (1998), SSYM'98.

[12]

CWE/SANS. CWE/SANS TOP 25 Most Dangerous Software Errors. www.sans.org/top25-software-errors, 2011.

[13]

DEMOTT, J. The evolving art of fuzzng. DEFCON 14, http://www.appliedsec.com/files/The_Evolving_Art_of_Fuzzing.2005.

[14]

FERRANTE, J., OTTENSTEIN, K. J., AND WARREN, J. D. The program dependence graph and its use in optimization. ACM Trans. Program. Lang. Syst. 9 (1997), 319-349.

[15]

GANESH, V., LEEK, T., AND RINARD, M. Taint-based directed whitebox fuzzing. In Proceedings of the 31st International Conference on Software Engineering (2009), ICSE'09.

[16]

GEGICK, M., WILLIAMS, L., OSBORNE, J., AND VOUK, M. Prioritizing software security fortification through code-level metrics. In Proc. of the 4th ACM workshop on Quality of protection (Oct. 2008), QoP'08, ACM Press.

[17]

GODEFROID, P., KLARLUND, N., AND SEN, K. DART: directed automated random testing. In Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation (2005), PLDI'05.

[18]

GODEFROID, P., LEVIN, M. Y., AND MOLNAR, D. A. Automated Whitebox Fuzz Testing. In Proceedings of the 15th Annual Network and Distributed System Security Symposium (2008), NDSS'08.

[19]

GODEFROID, P., AND LUCHAUP, D. Automatic partial loop summarization in dynamic test generation. In Proceedings of the 2011 International Symposium on Software Testing and Analysis (2011), ISSTA'11.

[20]

KAKSONEN, R. A functional method for assessing protocol implementation security. Tech. Rep. 448, VTT, 2001.

[21]

KANG, M. G., MCCAMANT, S., POOSANKAM, P., AND SONG, D. DTA++: Dynamic taint analysis with targeted control-flow propagation. In Proceedings of the 18th Annual Network and Distributed System Security Symposium (2011), NDSS'11.

[22]

KHURSHID, S., PASAREANU, C. S., AND VISSER, W. Generalized symbolic execution for model checking and testing. In Proceedings of the 9th international conference on Tools and algorithms for the construction and analysis of systems (2003), TACAS'03.

[23]

LATTNER, C., AND ADVE, V. LLVM: A compilation framework for lifelong program analysis & transformation. In Proceedings of the international symposium on Code generation and optimization (2004), CGO'04.

[24]

MARINESCU, P. D., AND CADAR, C. make test-zesti: a symbolic execution solution for improving regression testing. In Proc. of the 2012 International Conference on Software Engineering (June 2012), ICSE'12, pp. 716-726.

[25]

MILLER, B. P., FREDRIKSEN, L., AND SO, B. An empirical study of the reliability of UNIX utilities. Commun. ACM 33 (Dec 1990), 32-44.

[26]

MITRE. Common Vulnerabilities and Exposures (CVE). http://cve.mitre.org/, 2011.

[27]

MOLNAR, D., LI, X. C., AND WAGNER, D. A. Dynamic test generation to find integer bugs in ×86 binary linux programs. In Proceedings of the 18th conference on USENIX security symposium (2009), SSYM'09.

[28]

MOSER, A., KRUEGEL, C., AND KIRDA, E. Exploring multiple execution paths for malware analysis. In Proceedings of the 2007 IEEE Symposium on Security and Privacy (2007), SP'07, IEEE Computer Society.

[29]

NAGAPPAN, N., BALL, T., AND ZELLER, A. Mining metrics to predict component failures. In Proceedings of the 28th international conference on Software engineering (2006), ICSE'06.

[30]

NETHERCOTE, N., AND SEWARD, J. Valgrind: A Framework for Heavyweight Dynamic Binary Instrumentation. In Proceedings of the Third International ACM SIGPLAN/SIGOPS Conference on Virtual Execution Environments (2007), VEE'07.

[31]

NEWSOME, J., AND SONG, D. Dynamic taint analysis: Automatic detection, analysis, and signature generation of exploit attacks on commodity software. In Proceedings of the Network and Distributed Systems Security Symposium (2005), NDSS'05.

[32]

NGUYEN, V. H., AND TRAN, L. M. S. Predicting vulnerable software components with dependency graphs. In Proc. of the 6th International Workshop on Security Measurements and Metrics (Sept. 2010), MetriSec'10, ACM Press.

[33]

SEN, K., MARINOV, D., AND AGHA, G. CUTE: a concolic unit testing engine for C. In Proceedings of the 10th European software engineering conference held jointly with 13th ACM SIGSOFT international symposium on Foundations of software engineering (2005), ESEC/FSE-13.

[34]

SEREBRYANY, K., BRUENING, D., POTAPENKO, A., AND VYUKOV, D. AddressSanitizer: A fast address sanity checker. In Proceedings of USENIX Annual Technical Conference (2012).

[35]

SHIN, Y., AND WILLIAMS, L. An initial study on the use of execution complexity metrics as indicators of software vulnerabilities. In Proceedings of the 7th International Workshop on Software Engineering for Secure Systems (2011), SESS'11.

[36]

SLOWINSKA, A., AND BOS, H. Pointless tainting?: evaluating the practicality of pointer tainting. In EuroSys '09: Proceedings of the 4th ACM European conference on Computer systems (2009).

[37]

SLOWINSKA, A., STANCESCU, T., AND BOS, H. Body Armor for Binaries: preventing buffer overflows without recompilation. In Proceedings of USENIX Annual Technical Conference (2012).

[38]

SOTIROV, A. Modern exploitation and memory protection bypasses. USENIX Security invited talk, http://www.usenix.org/events/sec09/tech/slides/sotirov.pdf, 2009.

[39]

SPIKE. http://www.immunitysec.com/resources-freesoftware.shtml.

[40]

SUTTON, M., GREENE, A., AND AMINI, P. Fuzzing: Brute Force Vulnerability Discovery. Addison-Wesley Professional, 2007.

[41]

VAN DER VEEN, V., DUTT-SHARMA, N., CAVALLARO, L., AND BOS, H. Memory Errors: The Past, the Present, and the Future. In Proceedings of The 15th International Symposium on Research in Attacks, Intrusions and Defenses (2012), RAID'12.

[42]

WANG, T., WEI, T., GU, G., AND ZOU, W. TaintScope: A Checksum-Aware Directed Fuzzing Tool for Automatic Software Vulnerability Detection. In Proceedings of the 31st IEEE Symposium on Security and Privacy (2010), SP'10.

[43]

WILLIAMS, N., MARRE, B., AND MOUY, P. On-the-Fly Generation of K-Path Tests for C Functions. In Proceedings of the 19th IEEE international conference on Automated software engineering (2004), ASE'04.

[44]

ZIMMERMANN, T., NAGAPPAN, N., AND WILLIAMS, L. Searching for a Needle in a Haystack: Predicting Security Vulnerabilities for Windows Vista. In Proc. of the 3rd International Conference on Software Testing, Verification and Validation (Apr. 2010), ICST'10.

[45]

ZITSER, M., LIPPMANN, R., AND LEEK, T. Testing static analysis tools using exploitable buffer overflows from open source code. In Proc. of the 12th ACM SIGSOFT twelfth international symposium on Foundations of software engineering (Nov. 2004), SIGSOFT '04/FSE-12.

Cited By

Kuliamin V(2024)A Survey of Software Dynamic Analysis MethodsProgramming and Computing Software10.1134/S036176882401007950:1(90-114)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1134/S0361768824010079
Choi KSon DKim YSeo JWilliams BChen YNeville J(2023)Testing the channels of convolutional neural networksProceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v37i12.26726(14774-14782)Online publication date: 7-Feb-2023
https://dl.acm.org/doi/10.1609/aaai.v37i12.26726
Lee MCha SOh HGrundy JPollock LPenta M(2023)Learning Seed-Adaptive Mutation Strategies for Greybox FuzzingProceedings of the 45th International Conference on Software Engineering10.1109/ICSE48619.2023.00043(384-396)Online publication date: 14-May-2023
https://dl.acm.org/doi/10.1109/ICSE48619.2023.00043
Show More Cited By

Dowsing for overflows: a guided fuzzer to find buffer boundary violations
1. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Software defect analysis

Recommendations

Automatically assessing crashes from heap overflows
ASE '17: Proceedings of the 32nd IEEE/ACM International Conference on Automated Software Engineering

Heap overflow is one of the most widely exploited vulnerabilities, with a large number of heap overflow instances reported every year. It is important to decide whether a crash caused by heap overflow can be turned into an exploit. Efficient and ...
Automatically Fixing C Buffer Overflows Using Program Transformations
DSN '14: Proceedings of the 2014 44th Annual IEEE/IFIP International Conference on Dependable Systems and Networks

Fixing C buffer overflows at source code level remains a manual activity, at best semi-automated. We present an automated approach to fix buffer overflows by describing two program transformations that automatically introduce two well-known security ...
Testing for buffer overflows with length abstraction
ISSTA '08: Proceedings of the 2008 international symposium on Software testing and analysis

We present Splat, a tool for automatically generating inputs that lead to memory safety violations in C programs. Splat performs directed random testing of the code, guided by symbolic execution. However, instead of representing the entire contents of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

SEC'13: Proceedings of the 22nd USENIX conference on Security

August 2013

702 pages

ISBN:9781931971034

Program Chair:
Sam King
University of Illinois and Adrenaline Mobility

Sponsors

Akamai: Akamai
Google Inc.
IBMR: IBM Research
NSF
Microsoft Reasearch: Microsoft Reasearch

Publisher

USENIX Association

United States

Publication History

Published: 14 August 2013

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

41
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kuliamin V(2024)A Survey of Software Dynamic Analysis MethodsProgramming and Computing Software10.1134/S036176882401007950:1(90-114)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1134/S0361768824010079
Choi KSon DKim YSeo JWilliams BChen YNeville J(2023)Testing the channels of convolutional neural networksProceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v37i12.26726(14774-14782)Online publication date: 7-Feb-2023
https://dl.acm.org/doi/10.1609/aaai.v37i12.26726
Lee MCha SOh HGrundy JPollock LPenta M(2023)Learning Seed-Adaptive Mutation Strategies for Greybox FuzzingProceedings of the 45th International Conference on Software Engineering10.1109/ICSE48619.2023.00043(384-396)Online publication date: 14-May-2023
https://dl.acm.org/doi/10.1109/ICSE48619.2023.00043
Lahiri SRoy SRyu SSmaragdakis Y(2022)Almost correct invariants: synthesizing inductive invariants by fuzzing proofsProceedings of the 31st ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3533767.3534381(352-364)Online publication date: 18-Jul-2022
https://dl.acm.org/doi/10.1145/3533767.3534381
Schumilo SAschermann CJemmett AAbbasi AHolz TBromberg YKermarrec AKozyrakis C(2022)Nyx-netProceedings of the Seventeenth European Conference on Computer Systems10.1145/3492321.3519591(166-180)Online publication date: 28-Mar-2022
https://dl.acm.org/doi/10.1145/3492321.3519591
Blazytko TAschermann CSchlögel MAbbasi ASchumilo SWörner SHolz THeninger NTraynor P(2019)GRIMOIREProceedings of the 28th USENIX Conference on Security Symposium10.5555/3361338.3361475(1985-2002)Online publication date: 14-Aug-2019
https://dl.acm.org/doi/10.5555/3361338.3361475
Lyu CJi SZhang CLi YLee WSong YBeyah RHeninger NTraynor P(2019)MOPTProceedings of the 28th USENIX Conference on Security Symposium10.5555/3361338.3361473(1949-1966)Online publication date: 14-Aug-2019
https://dl.acm.org/doi/10.5555/3361338.3361473
Güler EAschermann CAbbasi AHolz THeninger NTraynor P(2019)ANTIFUZZProceedings of the 28th USENIX Conference on Security Symposium10.5555/3361338.3361472(1931-1947)Online publication date: 14-Aug-2019
https://dl.acm.org/doi/10.5555/3361338.3361472
Kim TKim CRhee JFei FTu ZWalkup GZhang XDeng XXu DHeninger NTraynor P(2019)RVFUZZERProceedings of the 28th USENIX Conference on Security Symposium10.5555/3361338.3361368(425-442)Online publication date: 14-Aug-2019
https://dl.acm.org/doi/10.5555/3361338.3361368
Zhu XFeng XJiao TWen SXiang YCamtepe SXue JGalbraith SRussello GSusilo WGollmann DKirda ELiang Z(2019)A Feature-Oriented Corpus for Understanding, Evaluating and Improving Fuzz TestingProceedings of the 2019 ACM Asia Conference on Computer and Communications Security10.1145/3321705.3329845(658-663)Online publication date: 2-Jul-2019
https://dl.acm.org/doi/10.1145/3321705.3329845
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Table of Contents