More Web Proxy on the site http://driver.im/

article

SAFECode: enforcing alias analysis for weakly typed languages

Authors:

Dinakar Dhurjati,

Sumant Kowshik,

Vikram AdveAuthors Info & Claims

ACM SIGPLAN Notices, Volume 41, Issue 6

Pages 144 - 157

https://doi.org/10.1145/1133255.1133999

Published: 11 June 2006 Publication History

Abstract

Static analysis of programs in weakly typed languages such as C and C++ is generally not sound because of possible memory errors due to dangling pointer references, uninitialized pointers, and array bounds overflow. We describe a compilation strategy for standard C programs that guarantees that aggressive interprocedural pointer analysis (or less precise ones), a call graph, and type information for a subset of memory, are never invalidated by any possible memory errors. We formalize our approach as a new type system with the necessary run-time checks in operational semantics and prove the correctness of our approach for a subset of C. Our semantics provide the foundation for other sophisticated static analyses to be applied to C programs with a guarantee of soundness. Our work builds on a previously published transformation called Automatic Pool Allocation to ensure that hard-to-detect memory errors (dangling pointer references and certain array bounds errors) cannot invalidate the call graph, points-to information or type information. The key insight behind our approach is that pool allocation can be used to create a run-time partitioning of memory that matches the compile-time memory partitioning in a points-to graph, and efficient checks can be used to isolate the run-time partitions. Furthermore, we show that the sound analysis information enables static checking techniques that eliminate many run-time checks. Our approach requires no source code changes, allows memory to be managedexplicitly, and does not use meta-data on pointers or individual tag bits for memory. Using several benchmark s and system codes, we show experimentally that the run-time overheads are low (less than 10% in nearly all cases and 30% in the worst case we have seen).We also show the effectiveness of static analyses in eliminating run-time checks.

References

[1]

A. Aiken, M. Fahndrich, and R. Levien. Better static memory management: Improving region-based analysis of higher-order languages. In ACM SIGPLAN Conf. on Programming Language Design and Implementation (PLDI), June 1995.

Digital Library

[2]

T. M. Austin, S. E. Breach, and G. S. Sohi. Efficient detection of all pointer and array access errors. In ACM SIGPLAN Conf. on Programming Language Design and Implementation (PLDI), June 1994.

Digital Library

[3]

E. Berger and B. Zorn. Diehard: Probabilistic memory safety for unsafe languages. In ACM SIGPLAN Conf. on Programming Language Design and Implementation (PLDI), 2006.

Digital Library

[4]

E. Berger, B. Zorn, and K. McKinley. Reconsidering custom memory allocation. In Proc. Conference on Object-Oriented Programming: Systems, Languages, and Applications, 2002.

Digital Library

[5]

R. Bodik, R. Gupta, and V. Sarkar. ABCD: eliminating array bounds checks on demand. In Proc. ACM SIGPLAN Conf. on Programming Language Design and Implementation (PLDI), 2000.

Digital Library

[6]

G. Bollella and J. Gosling. The real-time specification for Java. IEEE Computer, 33(6):47--54, 2000.

Digital Library

[7]

C. Boyapati, A. Salcianu, W. Beebee, and M. Rinard. Ownership types for safe region-based memory management in real-time java. In Proc. ACM SIGPLAN Conf. on Programming Language Design and Implementation (PLDI), 2003.

Digital Library

[8]

M. C. Carlisle. Olden: parallelizing programs with dynamic data structures on distributed-memory machines. PhD thesis, 1996.

Digital Library

[9]

W.-N. Chin, F. Craciun, S. Qin, and M. Rinard. Region inference for an object-oriented language. In ACM SIGPLAN Conf. on Programming Language Design and Implementation (PLDI), June 2004.

Digital Library

[10]

M. Das, S. Lerner, and M. Siegle. Esp: Path-sensitive program verification in polynomial time. In Proc. ACM SIGPLAN Conf. on Programming Language Design and Implementation (PLDI), Berlin, Germany, Jun 2002.

Digital Library

[11]

D. Dhurjati and V. Adve. Backwards-compatible array bounds checking for C with very low overhead. In Proc. 28th Int'l Conf. on Software Engineering (ICSE), Shanghai, China, May 2006.

Digital Library

[12]

D. Dhurjati and V. Adve. Efficiently detecting all dangling pointer uses in production servers. In Proc. Int'l Conf. on Dependable Systems and Networks (DSN), Philadelphia, USA, June 2006.

Digital Library

[13]

D. Dhurjati, S. Kowshik, and V. Adve. Enforcing alias analysis for weakly typed languages. Tech Report UIUCDCS-R-2005-2657, Computer Science Dept., Univ. of Illinois at Urbana-Champaign, Oct 2005. See http://safecode.cs.uiuc.edu/.

[14]

D. Dhurjati, S. Kowshik, V. Adve, and C. Lattner. Memory safety without runtime checks or garbage collection. In Conf. on Language, Compiler, and Tool Support for Embedded Systems (LCTES), Jun 2003.

Digital Library

[15]

D. Dhurjati, S. Kowshik, V. Adve, and C. Lattner. Memory safety without garbage collection for embedded applications. ACM Transactions on Embedded Computing Systems, Feb. 2005.

Digital Library

[16]

N. Dor, S. Adams, M. Das, and Z. Yang. Software validation via scalable path-sensitive value flow analysis. In Proc. of ACM SIGSOFT international symposium on Software testing and analysis, 2004.

Digital Library

[17]

N. Dor, M. Rodeh, and M. Sagiv. Cssv: Towards a realistic tool for statically detecting all buffer overflows in c. In SIGPLAN Conference on Programming Language Design and Implementation, Sandiego, June 2003.

Digital Library

[18]

V. Ganapathy, S. Jha, D. Chandler, D. Melski, and D. Vitek. Buffer overrun detection using linear programming and static analysis. In Proceedings of the 10th ACM conference on Computer and communications security, New York, NY, USA, 2003.

Digital Library

[19]

D. Gay and A. Aiken. Memory management with explicit regions. In Proc. ACM SIGPLAN Conf. on Programming Language Design and Implementation (PLDI), pages 313--323, Montreal, Canada, 1998.

Digital Library

[20]

D. Grossman, G. Morrisett, T. Jim, M. Hicks, Y. Wang, and J. Cheney. Region-based memory management in cyclone. In Proc. ACM SIGPLAN Conf. on Programming Language Design and Implementation (PLDI), June 2002.

Digital Library

[21]

B. Hackett, M. Das, D. Wang, and Z. Yang. Modular checking forbuffer overflows in the large. In Proc. 28th Int'l Conf. on Software Engineering (ICSE), Shanghai, China, 2006.

Digital Library

[22]

B. Hackett and R. Rugina. Region-based shape analysis with tracked locations. In POPL '05: Proceedings of the 32nd ACM SIGPLANSIGACT symposium on Principles of programming languages, pages 310--323, New York, NY, USA, 2005. ACM Press.

Digital Library

[23]

R. Hastings and B. Joyce. Purify: Fast detection of memory leaks and access errors. In Winter USENIX, 1992.

[24]

T. Henzinger, R. Jhala, R. Majumdar, and G. Sutre. Software verification with Blast. In Tenth International Workshop on Model Checking of Software (SPIN), pages 235--239, 2003.

Digital Library

[25]

M. Hicks, G. Morrisett, D. Grossman, and T. Jim. Experience with safe manual memory-management in Cyclone. In Proc. of the 4th international symposium on Memory management (ISMM), 2004.

Digital Library

[26]

M. Hind. Pointer analysis: Haven't we solved this problem yet? In Proc. ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering (PASTE), pages 54--61, 2001.

Digital Library

[27]

R. W. M. Jones and P. H. J. Kelly. Backwards-compatible bounds checking for arrays and pointers in c programs. In Automated and Algorithmic Debugging, pages 13--26, 1997.

[28]

W. Kelly, V. Maslov, W. Pugh, E. Rosser, T. Shpeisman, and D. Wonnacott. The Omega Library Interface Guide. Technical report, Computer Science Dept., U. Maryland, College Park, Apr. 1996.

Digital Library

[29]

C. Lattner. Macroscopic Data Structure Analysis and Optimization. PhD thesis, Comp. Sci. Dept., Univ. of Illinois, Urbana, IL, May 2005.

Digital Library

[30]

C. Lattner and V. Adve. LLVM: A Compilation Framework for Lifelong Program Analysis and Transformation. In Proc. Int'l Symp. on Code Generation and Optimization (CGO), San Jose, Mar 2004.

Digital Library

[31]

C. Lattner and V. Adve. Automatic pool allocation: Improving performance by controlling data structure layout in the heap. In Proc. ACM SIGPLAN Conf. on Programming Language Design and Implementation (PLDI), Chicago, IL, Jun 2005.

Digital Library

[32]

A. Loginov, S. H. Yong, S. Horwitz, and T. Reps. Debugging via run-time type checking. Lecture Notes in Computer Science, 2001.

Digital Library

[33]

G. C. Necula, J. Condit, M. Harren, S. McPeak, and W. Weimer. Ccured: type-safe retrofitting of legacy software. ACM Transactions on Programming Language and Systems, 27(3):477--526, 2005.

Digital Library

[34]

H. Patil and C. N. Fischer. Efficient run-time monitoring using shadow processing. In Automated and Algorithmic Debugging, pages 119--132, 1995.

[35]

J. Seward. Valgrind, an open-source memory debugger for x86-gnu/linux.

[36]

B. Steensgaard. Points-to analysis in almost linear time. In ACM symposium on Principles of programming languages (POPL), 1996.

Digital Library

[37]

M. Tofte, L. Birkedal, M. Elsman, N. Hallenberg, T. H. Olesen, P. Sestoft, and P. Bertelsen. Programming with Regions in the ML Kit. Technical Report DIKU-TR-97/12, 1997.

[38]

M. Tofte and J.-P. Talpin. Region-based memory management. Information and Computation, pages 132(2):109--176, Feb. 1997.

Digital Library

[39]

R. Wahbe, S. Lucco, T. E. Anderson, and S. L. Graham. Efficient software-based fault isolation. ACM SIGOPS Operating Systems Review, 27(5):203--216, December 1993.

Digital Library

[40]

Y. Xie, A. Chou, and D. Engler. Archer: using symbolic, path-sensitive analysis to detect memory access errors. SIGSOFT Softw. Eng. Notes, 28(5):327--336, 2003.

Digital Library

[41]

S. H. Yong and S. Horwitz. Protecting C programs from attacks via invalid pointer dereferences. In Foundations of Software Engineering, 2003.

Digital Library

Cited By

Huang KPayer MQian ZSampson JTan GJaeger TLuo BLiao XXu JKirda ELie D(2024)Top of the Heap: Efficient Memory Error Protection of Safe Heap ObjectsProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3690310(1330-1344)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3690310
Khan SChatterjee BPande STsafrir DMusuvathi MGupta RAbu-Ghazaleh N(2024)Pythia: Compiler-Guided Defense Against Non-Control Data AttacksProceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 310.1145/3620666.3651343(850-866)Online publication date: 27-Apr-2024
https://dl.acm.org/doi/10.1145/3620666.3651343
Li WXu DWu WGong XXiang XWang Ygu FZeng Q(2019)Memory access integrity: detecting fine-grained memory access errors in binary codeCybersecurity10.1186/s42400-019-0035-x2:1Online publication date: 7-Jun-2019
https://doi.org/10.1186/s42400-019-0035-x
Show More Cited By

Index Terms

SAFECode: enforcing alias analysis for weakly typed languages
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages

Recommendations

SAFECode: enforcing alias analysis for weakly typed languages
PLDI '06: Proceedings of the 27th ACM SIGPLAN Conference on Programming Language Design and Implementation

Static analysis of programs in weakly typed languages such as C and C++ is generally not sound because of possible memory errors due to dangling pointer references, uninitialized pointers, and array bounds overflow. We describe a compilation strategy ...
Memory safety without garbage collection for embedded applications

Traditional approaches to enforcing memory safety of programs rely heavily on run-time checks of memory accesses and on garbage collection, both of which are unattractive for embedded applications. The goal of our work is to develop advanced compiler ...
Precise flow-insensitive may-alias analysis is NP-hard

Determining aliases is one of the foundamental static analysis problems, in part because the precision with which this problem is solved can affect the precision of other analyses such as live variables, available expressions, and constant propagation. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 41, Issue 6

Proceedings of the 2006 PLDI Conference

June 2006

426 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/1133255

Issue’s Table of Contents

PLDI '06: Proceedings of the 27th ACM SIGPLAN Conference on Programming Language Design and Implementation
June 2006
438 pages
ISBN:1595933204
DOI:10.1145/1133981
General Chair:
Michael Schwartzbach
University of Aarhus, Denmark
,
Program Chair:
Thomas Ball
Microsoft Research

Copyright © 2006 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 June 2006

Published in SIGPLAN Volume 41, Issue 6

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

138
Total Citations
View Citations
878
Total Downloads

Downloads (Last 12 months)35
Downloads (Last 6 weeks)3

Reflects downloads up to 11 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Huang KPayer MQian ZSampson JTan GJaeger TLuo BLiao XXu JKirda ELie D(2024)Top of the Heap: Efficient Memory Error Protection of Safe Heap ObjectsProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3690310(1330-1344)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3690310
Khan SChatterjee BPande STsafrir DMusuvathi MGupta RAbu-Ghazaleh N(2024)Pythia: Compiler-Guided Defense Against Non-Control Data AttacksProceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 310.1145/3620666.3651343(850-866)Online publication date: 27-Apr-2024
https://dl.acm.org/doi/10.1145/3620666.3651343
Li WXu DWu WGong XXiang XWang Ygu FZeng Q(2019)Memory access integrity: detecting fine-grained memory access errors in binary codeCybersecurity10.1186/s42400-019-0035-x2:1Online publication date: 7-Jun-2019
https://doi.org/10.1186/s42400-019-0035-x
(2018)ReferencesThe Continuing Arms Race10.1145/3129743.3129753(261-281)Online publication date: 1-Mar-2018
https://dl.acm.org/doi/10.1145/3129743.3129753
Coppens BDe Sutter BVolckaert S(2018)Multi-variant execution environmentsThe Continuing Arms Race10.1145/3129743.3129752(211-258)Online publication date: 1-Mar-2018
https://dl.acm.org/doi/10.1145/3129743.3129752
Jin YSullivan DArias OSadeghi ADavi L(2018)Hardware control flow integrityThe Continuing Arms Race10.1145/3129743.3129751(181-210)Online publication date: 1-Mar-2018
https://dl.acm.org/doi/10.1145/3129743.3129751
Schuster FHolz T(2018)Attacking dynamic codeThe Continuing Arms Race10.1145/3129743.3129750(139-180)Online publication date: 1-Mar-2018
https://dl.acm.org/doi/10.1145/3129743.3129750
Göktas EAthanasopoulos EBos HPortokalidis G(2018)Evaluating control-flow restricting defensesThe Continuing Arms Race10.1145/3129743.3129749(117-137)Online publication date: 1-Mar-2018
https://dl.acm.org/doi/10.1145/3129743.3129749
Kuznetzov VSzekeres LPayer MCandea GSekar RSong D(2018)Code-pointer integrityThe Continuing Arms Race10.1145/3129743.3129748(81-116)Online publication date: 1-Mar-2018
https://dl.acm.org/doi/10.1145/3129743.3129748
Crane SHomescu ALarsen POkhravi HFranz M(2018)Diversity and information leaksThe Continuing Arms Race10.1145/3129743.3129747(61-79)Online publication date: 1-Mar-2018
https://dl.acm.org/doi/10.1145/3129743.3129747
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents