Accelerating taint-based concolic testing by pruning pointer overtaint

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.