Detection and analysis of size controlled heap allocation

XIAO Qixue; CHEN Yu; QI Lanlan; GUO Shize; SHI Yuanchun

PDF(1083 KB)

Journal of Tsinghua University(Science and Technology) ›› 2015, Vol. 55 ›› Issue (5) : 572-578.

COMPUTER SCIENCE AND TECHNOLOGY

Detection and analysis of size controlled heap allocation

{{article.zuoZhe_EN}}

Author information +

History +

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.

Key words

vulnerability analysis / symbolic execution / memory allocation / size controlled heap allocation

Cite this article

EndNote

Ris (Procite)

Bibtex

Download Citations

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

References

[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.
[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/.
[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.
[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.