Detection and analysis of size controlled heap allocation

Abstract
Figures/Tables
References
Related Articles
Metrics

Download: PDF(1083 KB)
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

Abstract Improper memory operations are one of the main causes of software vulnerabilities. This study analyzes controlled memory allocation (CMA) errors which occur when key elements of the memory allocation method are affected by elaborately designed input data. This paper presents a CMA detection approach that uses static analyzes and optimized symbolic execution with a path-guided algorithm. These algorithms are combined with a state-of-the-art symbolic execution engine named KLEE in a CMA detection tool. The tool was tested on commonly used applications like Coreutils, where it found 10 CMA related bugs including 3 previously unknown bugs. Tests show that the tool's path guided searcher reaches an assigned target faster and with more paths than the other path searchers provided by KLEE. The tool executes faster for memory allocation related code with better coverage than conventional symbolic execution engines.

Keywords vulnerability analysis symbolic execution memory allocation size controlled heap allocation

ZTFLH:

TP311.11

Issue Date: 15 May 2015

	Service

	E-mail this article
	E-mail Alert
	RSS
	Articles by authors

	XIAO Qixue
	CHEN Yu
	QI Lanlan
	GUO Shize
	SHI Yuanchun

Cite this article:

XIAO Qixue,CHEN Yu,QI Lanlan, et al. Detection and analysis of size controlled heap allocation[J]. Journal of Tsinghua University(Science and Technology), 2015, 55(5): 572-578.

URL:

http://jst.tsinghuajournals.com/EN/ OR http://jst.tsinghuajournals.com/EN/Y2015/V55/I5/572

[1]	Aleph O. Smashing the stack for fun and profit [J]. Phrack Magazine, 1996, 49:14-16.
[2]	吴世忠, 郭涛, 董国伟, 等. 软件漏洞分析技术进展 [J]. 清华大学学报 (自然科学版). 2012, 52(10): 1309-1319.WU Shizhong, GUO Tao, DONG Guowei, et al. Software vulnerability analyses: A road map [J]. Journal of Tsinghua University (Science and Technology). 2012, 52(10): 1309-1319. (in Chinese)
[3]	National Vulnerability Database. Statistics results [EB/OL]. [2013-12-30]. http://web.nvd.nist.gov/view/vuln/statistics-results. url: http://web.nvd.nist.gov/view/vuln/statistics-results.
[4]	王铁磊.面向二进制程序的漏洞挖掘关键技术研究 [D]. 北京:北京大学, 2011WANG Tielei. Research on Binary-Executable-Oriented Software Vulnerability Detection [D]. Beijing: Peking University, 2011. (in Chinese).
[5]	MITRE. Vulnerability Description in CVE Database [EB/OL]. [2014-12-30]. https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2014-0160.
[6]	Vanegue J. Zero-sized heap allocations vulnerability analysis [C]//WOOT 10 Proceedings of the 4th USENIX conference on Offensive technologies. Washington DC, USA: USENIX Association, 2010:1-8.
[7]	Klocwork. Klocwork Insight [EB/OL]. [2014-12-30]. http://www.klockwork.com/. url: http://www.klockwork.com/.
[8]	Chess B, West J. Secure programming with Static Analysis [M]. Upper Saddle River, NJ, USA: Pearson Education, 2007.
[9]	Rebert A, Cha S K, Avgerinos T, et al. Optimizing seed selection for fuzzing [C]//Proceedings of the USENIX Security Symposium. San Diego, CA, USA: USENIX Association, 2014: 861-875.
[10]	Schwartz E J, Avgerinos T, Brumley D. All you ever wanted to know about dynamic taint analysis and forward symbolic execution (but might have been afraid to ask) [C]//Security and Privacy (SP), 2010 IEEE Symposium on. Oakland,CA,USA: IEEE, 2010: 317-331.
[11]	King J C. Symbolic execution and program testing [J]. Communications of the ACM, 1976, 19(7): 385-394.
[12]	Cadar C, Dunbar D, Engler D R. KLEE: Unassisted and Automatic Generation of High-Coverage Tests for Complex Systems Programs [C]//The 8th USENIX Symposium on Operating Systems Design and Implementation. San Diego, USA: OSDI, 2008: 209-224.
[13]	Haller I, Slowinska A, Neugschwandtner M, et al. Dowsing for overflows: A guided fuzzer to find buffer boundary violations [C]//Proceedings of the USENIX Security Symposium. Washington DC, USA: USENIX Association, 2013: 49-64.
[14]	Avgerinos T, Cha S K, Hao B L T, et al. AEG: Automatic exploit generation [C]//The 18th Annual Network and Distributed System Security Symposium. San Diego, CA, USA: The Internet Society, 2011, 59-66.
[15]	Godefroid P, Levin M Y, Molnar D A. Automated whitebox fuzz testing [C]//The 15th Annual Network and Distributed System Security Symposium. San Diego, CA, USA: The Internet Society, 2008, 151-166.
[16]	Bounimova E, Godefroid P, Molnar D. Billions and billions of constraints: Whitebox fuzz testing in production [C]//Proceedings of the 2013 International Conference on Software Engineering. San Francisco, CA, USA: IEEE Press, 2013: 122-131.
[17]	Ma K K, Phang K Y, Foster J S, et al. Directed symbolic execution [C]//The 18th International Symposium, SAS 2011. Venice, Italy: Springer Science & Business Media, 2011: 95-111.
[18]	Zamfir C, Candea G. Execution synthesis: A technique for automated software debugging [C]//Proceedings of the 5th European conference on Computer systems. Paris, France: ACM, 2010: 321-334.
[19]	Jin W, Orso A. BugRedux: reproducing field failures for in-house debugging [C]//Proceedings of the 34th International Conference on Software Engineering. Zurich, Switzerland: IEEE Press, 2012: 474-484.
[20]	Marinescu P D, Cadar C. KATCH: High-coverage testing of software patches [C]//Proceedings of the 9th Joint Meeting on Foundations of Software Engineering. Saint Petersburg, Russian Federation: ACM, 2013: 235-245.
[21]	Cui H, Hu G, Wu J, et al. Verifying systems rules using rule-directed symbolic execution [C]//International Conference on Architectural Support for Programming Languages and Operating Systems. Houston, TX, USA: ACM, 2013: 329-342.
[22]	LLVM Project. The LLVM compiler infrastructure [EB/OL]. [2013-11-20]. http://llvm.org. url: http://llvm.org.
[23]	Brumley D, Jager I, Avgerinos T, et al. BAP: A binary analysis platform [C]//Computer aided verification. Snowbird, UT, USA: Springer Berlin Heidelberg, 2011: 463-469.
[24]	Chipounov V, Candea G. Enabling sophisticated analyses of x86 binaries with RevGen [C]//Proceedings of the 2011 IEEE/IFIP 41st International Conference on Dependable Systems and Networks Workshops. Hong Kong, China: IEEE Computer Society, 2011: 211-216.
[25]	Chipounov V, Kuznetsov V, Candea G. S2E: A platform for in-vivo multi-path analysis of software systems [C]//Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS). New York, NY, USA: ACM, 2011: 265-278.
[26]	Chipounov V, Kuznetsov V, Candea G. The S2E platform: Design, implementation, and applications [J]. ACM Transactions on Computer Systems (TOCS), 2012: 30(1), 2.
[27]	Valiant Xiao. Bug report[EB/OL]. [2014-12-30].http://debbugs.gnu.org/cgi/bugreport.cgi?bug=16855. url: http://debbugs.gnu.org/cgi/bugreport.cgi?bug=16855.

[1]	WANG Hongping, HU Yanzhu, ZHANG Yufeng, WANG Song. Analyzing the vulnerability of electrified transportation road networks[J]. Journal of Tsinghua University(Science and Technology), 2023, 63(10): 1584-1597.
[2]	WANG Haojie, MA Zixuan, ZHENG Liyan, WANG Yuanwei, WANG Fei, ZHAI Jidong. Efficient memory allocator for the New Generation Sunway supercomputer[J]. Journal of Tsinghua University(Science and Technology), 2022, 62(5): 943-951.
[3]	ZOU Quanchen, ZHANG Tao, WU Runpu, MA Jinxin, LI Meicong, CHEN Chen, HOU Changyu. From automation to intelligence: Survey of research on vulnerability discovery techniques[J]. Journal of Tsinghua University(Science and Technology), 2018, 58(12): 1079-1094.
[4]	HAN Xinhui, WEI Shuang, YE Jiayi, ZHANG Chao, YE Zhiyuan. Detect use-after-free vulnerabilities in binaries[J]. Journal of Tsinghua University(Science and Technology), 2017, 57(10): 1022-1029.
[5]	MA Jinxin, ZHANG Tao, LI Zhoujun, ZHANG Jiangxiao. Improved fuzzy analysis methods[J]. Journal of Tsinghua University(Science and Technology), 2016, 56(5): 478-483.
[6]	XIN Wei, SHI Zhiwei, HAO Yongle, DONG Guowei. Approach ofgenerating vulnerability signature based on taint analysis and symbolic execution[J]. Journal of Tsinghua University(Science and Technology), 2016, 56(1): 28-34.

Viewed

Full text

Abstract

Cited

Shared

Discussed