Accelerating taint-based concolic testing by pruning pointer overtaint

Yun Min Cheng*, Bing Han Li, Shiuhpyng Shieh

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Taint-based Concolic testing is a software testing technique, which combines dynamic taint analysis, symbolic testing and concrete execution. Concolic testing is faster than symbolic testing while maintaining the same precision. Taint-based concolic testing uses dynamic taint analysis to help identify instructions related to inputs, and at the same time reduce the total number of constraints. Although taint-based concolic testing can be faster than concolic testing, issues regarding the taint propagation of pointers must be addressed. Decision on whether to taint the read-from-memory data referenced by a tainted address may cause either pointer undertaint or overtaint. The inappropriate taint will cause the result of insufficient or redundant constraints. Consequently, the insufficient constraint will lead to inaccurate test results and make the test target exploitable. On the other hand, the redundant constraint significantly slows down the test due to the fact that the constraint solving time depends on the constraint size. In this paper, we propose a new tainting approach which can prune pointer overtaint without causing pointer undertaint to depress the size of the path constraints. While exploring the target program exhaustively and detecting potential vulnerabilities, the proposed tainting approach can substantially accelerate taint-based concolic testing.

Original languageEnglish
Title of host publicationProceedings of the 2012 IEEE 6th International Conference on Software Security and Reliability, SERE 2012
Pages187-196
Number of pages10
DOIs
StatePublished - 1 Oct 2012
Event2012 IEEE 6th International Conference on Software Security and Reliability, SERE 2012 - Gaithersburg, MD, United States
Duration: 20 Jun 201222 Jun 2012

Publication series

NameProceedings of the 2012 IEEE 6th International Conference on Software Security and Reliability, SERE 2012

Conference

Conference2012 IEEE 6th International Conference on Software Security and Reliability, SERE 2012
CountryUnited States
CityGaithersburg, MD
Period20/06/1222/06/12

Keywords

  • Software testing
  • Symbolic execution
  • Taint-based concolic testing

Fingerprint Dive into the research topics of 'Accelerating taint-based concolic testing by pruning pointer overtaint'. Together they form a unique fingerprint.

  • Cite this

    Cheng, Y. M., Li, B. H., & Shieh, S. (2012). Accelerating taint-based concolic testing by pruning pointer overtaint. In Proceedings of the 2012 IEEE 6th International Conference on Software Security and Reliability, SERE 2012 (pp. 187-196). [6258308] (Proceedings of the 2012 IEEE 6th International Conference on Software Security and Reliability, SERE 2012). https://doi.org/10.1109/SERE.2012.31