Detection and analysis of size controlled heap allocation
XIAO Qixue1,3, CHEN Yu1, QI Lanlan2, GUO Shize3, SHI Yuanchun1
1. Department of Computer Science and Technology, Tsinghua University, Beijing 10084, China;
2. Department of Networks, Electronic Engineering Institute of PLA, Hefei 230037, China;
3. North Electronic Equipment Research Institute, Beijing 100191, China
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.
Chess B, West J. Secure programming with Static Analysis [M]. Upper Saddle River, NJ, USA: Pearson Education, 2007.
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.
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.
King J C. Symbolic execution and program testing [J]. Communications of the ACM, 1976, 19(7): 385-394.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
LLVM Project. The LLVM compiler infrastructure [EB/OL]. [2013-11-20]. http://llvm.org.
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.
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.
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.
Chipounov V, Kuznetsov V, Candea G. The S2E platform: Design, implementation, and applications [J]. ACM Transactions on Computer Systems (TOCS), 2012: 30(1), 2.