Buffer overrun detection using linear programming and static analysis

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Buffer overrun detection using linear programming and static analysis

Full text

Pdf (196 KB)

Source

Conference on Computer and Communications Security archive
Proceedings of the 10th ACM conference on Computer and communications security table of contents

Washington D.C., USA

SESSION: Analysis and verification table of contents

Pages: 345 - 354

Year of Publication: 2003

ISBN:1-58113-738-9

Authors

Vinod Ganapathy	University of Wisconsin-Madison
Somesh Jha	University of Wisconsin-Madison
David Chandler	Grammatech Inc., Ithaca, NY
David Melski	Grammatech Inc., Ithaca, NY
David Vitek	Grammatech Inc., Ithaca, NY

Sponsor

ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 16, Downloads (12 Months): 106, Citation Count: 14

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/948109.948155 What is a DOI?

ABSTRACT

This paper addresses the issue of identifying buffer overrun vulnerabilities by statically analyzing C source code. We demonstrate a light-weight analysis based on modeling C string manipulations as a linear program. We also present fast, scalable solvers based on linear programming, and demonstrate techniques to make the program analysis context sensitive. Based on these techniques, we built a prototype and used it to identify several vulnerabilities in popular security critical applications.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	bugtraq. www.securityfocus.com.
	2	CERT/CC advisories. www.cert.org/advisories.
	3	The twenty most critical internet security vulnerabilities. www.sans.org/top20.
	4	Aleph-one. Smashing the stack for fun and profit. Nov 1996. Phrack Magazine.
	5	Technical analysis of remote sendmail vulnerability. www.securityfocus.com/archive/1/313757.
	6	L. O. Andersen. Program Analysis and Specialization for the C Programming Language. PhD thesis, DIKU, Univ. of Copenhagen, 1994. (DIKU report 94/19).
	7	Erling D. Andersen , Knud D. Andersen, Presolving in linear programming, Mathematical Programming: Series A and B, v.71 n.2, p.221-245, Dec. 20, 1995 [doi>10.1007/BF01586000]
	8	Rastislav Bodík , Rajiv Gupta , Vivek Sarkar, ABCD: eliminating array bounds checks on demand, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.321-333, June 18-21, 2000, Vancouver, British Columbia, Canada
	9	J. W. Chinnek and E. W. Dravinieks. Locating minimal infeasible constraint sets in linear programs. ORSA Journal on Computing, 3(2):157--168, 1991.
	10	RAD: A Compile-Time Solution to Buffer Overflow Attacks, Proceedings of the The 21st International Conference on Distributed Computing Systems, p.409, April 16-19, 2001
	11	Jeremy Condit , Matthew Harren , Scott McPeak , George C. Necula , Westley Weimer, CCured in the real world, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
	12	Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
	13	C. Cowan, S. Beattie, R-F Day., C. Pu, P. Wagle, and E. Walthinsen. Automatic detection and prevention of buffer overflow attacks. In 7th USENIX Sec. Symp., 1998.
	14	C. Cowan, S. Beattie, J. Johansen, and P. Wagle. PointGuard: Protecting pointers from buffer overflow vulnerabilities. In 12th USENIX Sec. Symp., 2003.
	15	Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman , F. Kenneth Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.451-490, Oct. 1991 [doi>10.1145/115372.115320]
	16	G. B. Dantzig and B. Curtis Eaves. Fourier-Motzkin elimination and its dual. Journal of Combinatorial Theory (A), 14:288--297, 1973.
	17	Nurit Dor , Michael Rodeh , Mooly Sagiv, CSSV: towards a realistic tool for statically detecting all buffer overflows in C, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
	18	H. Etoh and K. Yoda. Protecting from stack-smashing attacks. 2000. www.trl.ibm.com/projects/security/ssp/main.html.
	19	V. Ganapathy, S. Jha, D. Chandler, D. Melski, and D. Vitek. Buffer overrun detection using linear programming and static analysis. 2003. UW-Madison Comp. Sci. Tech. Report 1488. ftp://ftp.cs.wisc.edu/pub/tech-reports/reports/2003/tr1488.ps.Z
	20	Susan Horwitz , Thomas Reps , David Binkley, Interprocedural slicing using dependence graphs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.1, p.26-60, Jan. 1990 [doi>10.1145/77606.77608]
	21	Thomas Reps , Susan Horwitz , Mooly Sagiv , Genevieve Rosay, Speeding up slicing, Proceedings of the 2nd ACM SIGSOFT symposium on Foundations of software engineering, p.11-20, December 06-09, 1994, New Orleans, Louisiana, United States
	22	D. Larochelle and D. Evans. Statically detecting likely buffer overflow vulnerabilities. In 10th USENIX Sec. Symp., 2001.
	23	E. Larson and T. Austin. High coverage detection of input related security faults. In 12th USENIX Sec. Symp., 2003.
	24	George C. Necula , Scott McPeak , Westley Weimer, CCured: type-safe retrofitting of legacy code, Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.128-139, January 16-18, 2002, Portland, Oregon
	25	CPLEX Optimizer. www.cplex.com/.
	26	Radu Rugina , Martin Rinard, Symbolic bounds analysis of pointers, array indices, and accessed memory regions, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.182-195, June 18-21, 2000, Vancouver, British Columbia, Canada
	27	Alexandeer Schrijver, Theory of linear and integer programming, John Wiley & Sons, Inc., New York, NY, 1986
	28	M. Sharir and A. Pnueli. Two Approaches to Interprocedural Dataflow Analysis. Prentice Hall Inc., 1981.
	29	David A. Wagner , Eric A. Brewer, Static analysis and computer security: new techniques for software assurance, 2000
	30	D. Wagner, J. S. Foster, E. A. Brewer, and A. Aiken. A first step towards automated detection of buffer overrun vulnerabilities. In Network and Distributed System Security (NDSS), 2000.
	31	Stephen J. Wright, Primal-dual interior-point methods, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1997
	32	R. Wunderling. Paralleler und Objektorientierter Simplex-Algorithmus. PhD thesis, Konrad-Zuse-Zentrum fur Informationstechnik Berlin, TR 1996-09. www.zib.de/PaperWeb/abstracts/TR-96-09/.
	33	Yichen Xie , Andy Chou , Dawson Engler, ARCHER: using symbolic, path-sensitive analysis to detect memory access errors, Proceedings of the 9th European software engineering conference held jointly with 11th ACM SIGSOFT international symposium on Foundations of software engineering, September 01-05, 2003, Helsinki, Finland
	34	Suan Hsi Yong , Susan Horwitz , Thomas Reps, Pointer analysis for programs with structures and casting, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.91-103, May 01-04, 1999, Atlanta, Georgia, United States

CITED BY 14

	Trent Jaeger , Antony Edwards , Xiaolan Zhang, Consistency analysis of authorization hook placement in the Linux security modules framework, ACM Transactions on Information and System Security (TISSEC), v.7 n.2, p.175-205, May 2004
	Wei Xu , Daniel C. DuVarney , R. Sekar, An efficient and backwards-compatible transformation to ensure memory safety of C programs, ACM SIGSOFT Software Engineering Notes, v.29 n.6, November 2004
	G. Edward Suh , Jae W. Lee , David Zhang , Srinivas Devadas, Secure program execution via dynamic information flow tracking, ACM SIGPLAN Notices, v.39 n.11, November 2004
	Prattana Deeprasertkul , Pattarasinee Bhattarakosol , Fergus O'Brien, Automatic detection and correction of programming faults for software applications, Journal of Systems and Software, v.78 n.2, p.101-110, November 2005
	Mihai Christodorescu , Nicholas Kidd , Wen-Han Goh, String analysis for x86 binaries, ACM SIGSOFT Software Engineering Notes, v.31 n.1, January 2006
	Dinakar Dhurjati , Vikram Adve, Backwards-compatible array bounds checking for C with very low overhead, Proceeding of the 28th international conference on Software engineering, May 20-28, 2006, Shanghai, China
	Dinakar Dhurjati , Sumant Kowshik , Vikram Adve, SAFECode: enforcing alias analysis for weakly typed languages, ACM SIGPLAN Notices, v.41 n.6, June 2006
	Xiaolan Zhang , Larry Koved , Marco Pistoia , Sam Weber , Trent Jaeger , Guillaume Marceau , Liangzhao Zeng, The case for analysis preserving language transformation, Proceedings of the 2006 international symposium on Software testing and analysis, July 17-20, 2006, Portland, Maine, USA
	C. M. Linn , M. Rajagopalan , S. Baker , C. Collberg , S. K. Debray , J. H. Hartman, Protecting against unexpected system calls, Proceedings of the 14th conference on USENIX Security Symposium, p.16-16, July 31-August 05, 2005, Baltimore, MD
	Dipanwita Sarkar , Muthu Jagannathan , Jay Thiagarajan , Ramanathan Venkatapathy, Flow-insensitive static analysis for detecting integer anomalies in programs, Proceedings of the 25th conference on IASTED International Multi-Conference: Software Engineering, p.334-340, February 13-15, 2007, Innsbruck, Austria
	Stephan Neuhaus , Thomas Zimmermann , Christian Holler , Andreas Zeller, Predicting vulnerable software components, Proceedings of the 14th ACM conference on Computer and communications security, October 28-31, 2007, Alexandria, Virginia, USA
	Lin Tan , Xiaolan Zhang , Xiao Ma , Weiwei Xiong , Yuanyuan Zhou, AutoISES: automatically inferring security specifications and detecting violations, Proceedings of the 17th conference on Security symposium, p.379-394, July 28-August 01, 2008, San Jose, CA
	Santosh Nagarakatte , Jianzhou Zhao , Milo M.K. Martin , Steve Zdancewic, SoftBound: highly compatible and complete spatial memory safety for c, ACM SIGPLAN Notices, v.44 n.6, June 2009
	Prateek Saxena , Pongsin Poosankam , Stephen McCamant , Dawn Song, Loop-extended symbolic execution on binary programs, Proceedings of the eighteenth international symposium on Software testing and analysis, July 19-23, 2009, Chicago, IL, USA