research-article

Archipelago: trading address space for reliability and security

Authors:

Vitaliy B. Lvin,

Emery D. Berger,

Benjamin G. ZornAuthors Info & Claims

ACM SIGOPS Operating Systems Review, Volume 42, Issue 2

Pages 115 - 124

https://doi.org/10.1145/1353535.1346296

Published: 01 March 2008 Publication History

Abstract

Memory errors are a notorious source of security vulnerabilities that can lead to service interruptions, information leakage and unauthorized access. Because such errors are also difficult to debug, the absence of timely patches can leave users vulnerable to attack for long periods of time. A variety of approaches have been introduced to combat these errors, but these often incur large runtime overheads and generally abort on errors, threatening availability.

This paper presents Archipelago, a runtime system that takes advantage of available address space to substantially reduce the likelihood that a memory error will affect program execution. Archipelago randomly allocates heap objects far apart in virtual address space, effectively isolating each object from buffer overflows. Archipelago also protects against dangling pointer errors by preserving the contents of freed objects after they are freed. Archipelago thus trades virtual address space---a plentiful resource on 64-bit systems---for significantly improved program reliability and security, while limiting physical memory consumption by tracking the working set of an application and compacting cold objects. We show that Archipelago allows applications to continue to run correctly in the face of thousands of memory errors. Across a suite of server applications, Archipelago's performance overhead is 6% on average (between -7% and 22%), making it especially suitable to protect servers that have known security vulnerabilities due to heap memory errors.

Supplementary Material

JPG File (1346296.jpg)

Download
10.51 KB

index.html (index.html)

Slides from the presentation

Download
.93 KB

ZIP File (p115-novark-slides.zip)

Supplemental material for Archipelago: trading address space for reliability and security

Download
10.75 MB

Audio only (1346296.mp3)

Download
10.97 MB

Video (1346296.mp4)

Download
151.62 MB

References

[1]

A.W. Appel and K. Li. Virtual memory primitives for user programs. In ASPLOS-IV: Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, pages 96--107, New York, NY, USA, 1991. ACM Press.

Digital Library

[2]

T.M. Austin, S.E. Breach, and G.S. Sohi. Efficient detection of all pointer and array access errors. In Proceedings of the ACM SIGPLAN 1994 Conference on Programming Language Design and Implementation, pages 290--301, New York, NY, USA, 1994. ACM Press.

Digital Library

[3]

D. Avots, M. Dalton, V.B. Livshits, and M.S. Lam. Improving software security with a C pointer analysis. In ICSE '05: Proceedings of the 27th international conference on Software engineering, pages 332--341, New York, NY, USA, 2005. ACM Press.

Digital Library

[4]

E.D. Berger and B.G. Zorn. DieHard: Probabilistic memory safety for unsafe languages. In Proceedings of the 2006 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2006), pages 158--168, New York, NY, USA, 2006. ACM Press.

Digital Library

[5]

E.D. Berger and B.G. Zorn. Efficient probabilistic memory safety. Technical Report UMCS TR-2007-17, Department of Computer Science, University of Massachusetts Amherst, Mar. 2007.

[6]

E.D. Berger, B.G. Zorn, and K.S. McKinley. Composing high-performance memory allocators. In Proceedings of the 2001 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2001), Snowbird, Utah, June 2001.

Digital Library

[7]

H.-J. Boehm and M. Weiser. Garbage collection in an uncooperative environment. Software Practice and Experience, 18(9):807--820, 1988.

Digital Library

[8]

R.W. Carr and J.L. Hennessy. Wsclock -- a simple and effective algorithm for virtual memory management. In SOSP, pages 87--95, 1981.

Digital Library

[9]

J.S. Chase, H.M. Levy, M.J. Feeley, and E.D. Lazowska. Sharing and protection in a single-address-space operating system. ACM Transactions on Computer Systems, 12(4):271--307, Nov. 1994.

Digital Library

[10]

P.J. Denning. The working set model for program behaviour. Communications of the ACM, 11:323--333, 1968.

Digital Library

[11]

D. Dhurjati and V. Adve. Backwards-Compatible Array Bounds Checking for C with Very Low Overhead. In Proceedings of the 2006 International Conference on Software Engineering (ICSE'06), Shanghai, China, May 2006.

Digital Library

[12]

D. Dhurjati and V. Adve. Efficiently detecting all dangling pointer uses in production servers. In DSN '06: Proceedings of the International Conference on Dependable Systems and Networks (DSN'06), pages 269--280, Washington, DC, USA, 2006. IEEE Computer Society.

Digital Library

[13]

D. Dhurjati, S. Kowshik, and V. Adve. Safecode: enforcing alias analysis for weakly typed languages. In Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, pages 144--157, New York, NY, USA, 2006. ACM Press.

Digital Library

[14]

D. Dhurjati, S. Kowshik, V. Adve, and C. Lattner. Memory safety without runtime checks or garbage collection. In ACM SIGPLAN 2003 Conference on Languages, Compilers, and Tools for Embedded Systems (LCTES'2003), San Diego, CA, June 2003. ACM Press.

Digital Library

[15]

P. Druschel and L.L. Peterson. High-performance cross-domain data transfer. Technical Report TR 92-11, Dept. Comp. of Sc., U. of Arizona, Tucson, AZ (USA), Mar. 1992.

[16]

R. Hastings and B. Joyce. Purify: Fast detection of memory leaks and access errors. In Proc. of the Winter 1992 USENIX Conference, pages 125--138, San Francisco, California, 1991.

[17]

M. Hertz and E.D. Berger. Quantifying the performance of garbage collection vs. explicit memory management. In Proceedings of the 20th annual ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA), San Diego, CA, Oct. 2005.

Digital Library

[18]

J. Huck and J. Hays. Architectural support for translation table management in large address space machines. In ISCA '93: Proceedings of the 20th annual international symposium on Computer architecture, pages 39--50, New York, NY, USA, 1993. ACM Press.

Digital Library

[19]

T. Jim, J.G. Morrisett, D. Grossman, M.W. Hicks, J. Cheney, and Y. Wang. Cyclone: A safe dialect of C. In Proceedings of the General Track: 2002 USENIX Annual Technical Conference, pages 275--288, Berkeley, CA, USA, 2002. USENIX Association.

Digital Library

[20]

M. Kharbutli, X. Jiang, Y. Solihin, G. Venkataramani, and M. Prvulovic. Comprehensively and efficiently protecting the heap. In ASPLOS-XII: Proceedings of the 12th International Conference on Architectural Support for Programming Languages and Operating Systems, pages 207--218, New York, NY, USA, 2006. ACM Press.

Digital Library

[21]

D. Lea. A memory allocator. http://gee.cs.oswego.edu/dl/html/malloc.html, 1997.

[22]

Microsoft Corporation. Pageheap. http://support.microsoft.com/kb/286470.

[23]

G.C. Necula, S. McPeak, and W. Weimer. CCured: type--safe retrofitting of legacy code. In POPL '02: Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of Programming Languages, pages 128--139, New York, NY, USA, 2002. ACM Press.

Digital Library

[24]

N. Nethercote and J. Fitzhardinge. Bounds-checking entire programs without recompiling. In SPACE 2004, Venice, Italy, Jan. 2004.

[25]

G. Novark, E.D. Berger, and B.G. Zorn. Exterminator: automatically correcting memory errors with high probability. In PLDI '07: Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, pages 1--11, New York, NY, USA, 2007. ACM Press.

Digital Library

[26]

O. Ruwase and Monica S. Lam. A practical dynamic buffer overflow detector. In Proceedings of the 11th Annual Network and Distributed System Security Symposium, pages 159--169, Feb. 2004.

[27]

B. Perens. Electric Fence v2.1. http://perens.com/FreeSoftware/ElectricFence/.

[28]

F. Qin, J. Tucek, J. Sundaresan, and Y. Zhou. Rx: Treating bugs as allergies: A safe method to survive software failures. In Proceedings of the Twentieth Symposium on Operating Systems Principles, volume XX of Operating Systems Review, Brighton, UK, Oct. 2005. ACM.

Digital Library

[29]

M. Rinard, C. Cadar, D. Dumitran, D.M. Roy, and T. Leu. A dynamic technique for eliminating buffer overflow vulnerabilities (and other memory errors). In Proceedings of the 2004 Annual Computer Security Applications Conference, Dec. 2004.

Digital Library

[30]

M. Rinard, C. Cadar, D. Dumitran, D.M. Roy, T. Leu, and J. William S. Beebee. Enhancing server availability and security through failure-oblivious computing. In Sixth Symposium on Operating Systems Design and Implementation, San Francisco, CA, Dec. 2004. USENIX.

Digital Library

[31]

J. Seward and N. Nethercote. Using Valgrind to detect undefined value errors with bit-precision. In Proceedings of the USENIX'05 Annual Technical Conference, Anaheim, California, USA, Apr. 2005.

Digital Library

[32]

N. Swamy, M. Hicks, G. Morrisett, D. Grossman, and T. Jim. Experience with safe manual memory management in cyclone. Science of Computer Programming, 2006. Special issue on memory management. Expands ISMM conference paper of the same name. To appear.

Digital Library

[33]

Symantec. Internet security threat report. http://www.symantec.com/enterprise/threatreport/index.jsp, Sept. 2006.

[34]

P.R. Wilson, S.F. Kaplan, and Y. Smaragdakis. The case for compressed caching in virtual memory systems. In Proceedings of the Annual Technical Conference on 1999 USENIX Annual Technical Conference, pages 101--116, Berkeley, CA, USA, 1999. USENIX Association.

Digital Library

[35]

W. Xu, D.C. DuVarney, and R. Sekar. An efficient and backwards-compatible transformation to ensure memory safety of C programs. In SIGSOFT'04/FSE-12: Proceedings of the 12th ACM SIGSOFT twelfth international symposium on Foundations of software engineering, pages 117--126, New York, NY, USA, 2004. ACM Press.

Digital Library

[36]

C. Yarvin, R. Bukowski, and T. Anderson. Anonymous RPC: Low-latency protection in a 64-bit address space. In Proceedings of the 1993 Summer USENIX Conference, pages 175--186, 1993.

Digital Library

[37]

S.H. Yong and S. Horwitz. Protecting C programs from attacks via invalid pointer dereferences. In ESEC/FSE--11: 11th ACM SIGSOFT International Symposium on Foundations of Software Engineering, pages 307--316, New York, NY, USA, 2003. ACM Press.

Digital Library

Cited By

Stavrakakis DPanfil ANam MBhatotia P(2024)SPP: Safe Persistent Pointers for Memory Safety2024 54th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN)10.1109/DSN58291.2024.00019(37-52)Online publication date: 24-Jun-2024
https://doi.org/10.1109/DSN58291.2024.00019
Li XGulila A(2019)Optimised memory allocation for less false abortion and better performance in hardware transactional memoryInternational Journal of Parallel, Emergent and Distributed Systems10.1080/17445760.2019.1605605(1-9)Online publication date: 6-May-2019
https://doi.org/10.1080/17445760.2019.1605605
Silvestro SLiu HZhang TJung CLee DLiu TOskin MInoue K(2018)SamplerProceedings of the 51st Annual IEEE/ACM International Symposium on Microarchitecture10.1109/MICRO.2018.00027(231-244)Online publication date: 20-Oct-2018
https://dl.acm.org/doi/10.1109/MICRO.2018.00027
Show More Cited By

Index Terms

Recommendations

DieHarder: securing the heap
CCS '10: Proceedings of the 17th ACM conference on Computer and communications security

Heap-based attacks depend on a combination of memory management error and an exploitable memory allocator. Many allocators include ad hoc countermeasures against particular exploits but their effectiveness against future exploits has been uncertain. ...
Archipelago: trading address space for reliability and security
ASPLOS XIII: Proceedings of the 13th international conference on Architectural support for programming languages and operating systems

Memory errors are a notorious source of security vulnerabilities that can lead to service interruptions, information leakage and unauthorized access. Because such errors are also difficult to debug, the absence of timely patches can leave users ...
Archipelago: trading address space for reliability and security
ASPLOS '08

Memory errors are a notorious source of security vulnerabilities that can lead to service interruptions, information leakage and unauthorized access. Because such errors are also difficult to debug, the absence of timely patches can leave users ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGOPS Operating Systems Review

ACM SIGOPS Operating Systems Review Volume 42, Issue 2

ASPLOS '08

March 2008

339 pages

ISSN:0163-5980

DOI:10.1145/1353535

Issue’s Table of Contents

ASPLOS XIII: Proceedings of the 13th international conference on Architectural support for programming languages and operating systems
March 2008
352 pages
ISBN:9781595939586
DOI:10.1145/1346281
General Chair:
Susan Eggers
University of Washington, USA
,
Program Chair:
James Larus
Microsoft Research, USA

Copyright © 2008 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: 01 March 2008

Published in SIGOPS Volume 42, Issue 2

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

69
Total Citations
View Citations
1,074
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Stavrakakis DPanfil ANam MBhatotia P(2024)SPP: Safe Persistent Pointers for Memory Safety2024 54th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN)10.1109/DSN58291.2024.00019(37-52)Online publication date: 24-Jun-2024
https://doi.org/10.1109/DSN58291.2024.00019
Li XGulila A(2019)Optimised memory allocation for less false abortion and better performance in hardware transactional memoryInternational Journal of Parallel, Emergent and Distributed Systems10.1080/17445760.2019.1605605(1-9)Online publication date: 6-May-2019
https://doi.org/10.1080/17445760.2019.1605605
Silvestro SLiu HZhang TJung CLee DLiu TOskin MInoue K(2018)SamplerProceedings of the 51st Annual IEEE/ACM International Symposium on Microarchitecture10.1109/MICRO.2018.00027(231-244)Online publication date: 20-Oct-2018
https://dl.acm.org/doi/10.1109/MICRO.2018.00027
Noorman JNikiforakis NPiessens F(2012)There is safety in numbersProceedings of the 17th Nordic conference on Secure IT Systems10.1007/978-3-642-34210-3_8(105-120)Online publication date: 31-Oct-2012
https://dl.acm.org/doi/10.1007/978-3-642-34210-3_8
Afek YDice DMorrison A(2011)Cache index-aware memory allocationACM SIGPLAN Notices10.1145/2076022.199348646:11(55-64)Online publication date: 4-Jun-2011
https://dl.acm.org/doi/10.1145/2076022.1993486
Afek YDice DMorrison ABoehm HBacon D(2011)Cache index-aware memory allocationProceedings of the international symposium on Memory management10.1145/1993478.1993486(55-64)Online publication date: 4-Jun-2011
https://dl.acm.org/doi/10.1145/1993478.1993486
Chen ZLiu DXiao JWang H(2023)All Use-After-Free Vulnerabilities Are Not Created Equal: An Empirical Study on Their Characteristics and DetectabilityProceedings of the 26th International Symposium on Research in Attacks, Intrusions and Defenses10.1145/3607199.3607229(623-638)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3607199.3607229
Gui BSong WXiong HHuang J(2022)Automated Use-After-Free Detection and Exploit Mitigation: How Far Have We Gone?IEEE Transactions on Software Engineering10.1109/TSE.2021.312199448:11(4569-4589)Online publication date: 1-Nov-2022
https://doi.org/10.1109/TSE.2021.3121994
Milburn AVan Der Kouwe EGiuffrida C(2022)Mitigating Information Leakage Vulnerabilities with Type-based Data Isolation2022 IEEE Symposium on Security and Privacy (SP)10.1109/SP46214.2022.9833675(1049-1065)Online publication date: May-2022
https://doi.org/10.1109/SP46214.2022.9833675
Gui BSong WHuang JCadar CZhang X(2021)UAFSan: an object-identifier-based dynamic approach for detecting use-after-free vulnerabilitiesProceedings of the 30th ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3460319.3464835(309-321)Online publication date: 11-Jul-2021
https://dl.acm.org/doi/10.1145/3460319.3464835
Show More Cited By

View Options

Get Access

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