Article

Data Space Randomization

Authors:

Sandeep Bhatkar,

R. SekarAuthors Info & Claims

DIMVA '08: Proceedings of the 5th international conference on Detection of Intrusions and Malware, and Vulnerability Assessment

Pages 1 - 22

https://doi.org/10.1007/978-3-540-70542-0_1

Published: 10 July 2008 Publication History

Abstract

Over the past several years, US-CERT advisories, as well as most critical updates from software vendors, have been due to memory corruption vulnerabilities such as buffer overflows, heap overflows, etc. Several techniques have been developed to defend against the exploitation of these vulnerabilities, with the most promising defenses being based on randomization. Two randomization techniques have been explored so far: address space randomization (ASR) that randomizes the location of objects in virtual memory, and instruction set randomization (ISR) that randomizes the representation of code. We explore a third form of randomization called data space randomization (DSR) that randomizes the representation of data stored in program memory. Unlike ISR, DSR is effective against non-control data attacks as well as code injection attacks. Unlike ASR, it can protect against corruption of non-pointer data as well as pointer-valued data. Moreover, DSR provides a much higher range of randomization (typically 2³²for 32-bit data) as compared to ASR. Other interesting aspects of DSR include (a) it does not share a weakness common to randomization-based defenses, namely, susceptibility to information leakage attacks, and (b) it is capable of detecting some exploits that are missed by full bounds-checking techniques, e.g., some of the overflows from one field of a structure to the next field. Our implementation results show that with appropriate design choices, DSR can achieve a performance overhead in the range of 5% to 30% for a range of programs.

References

[1]

Abadi, M., Budiu, M., Erlingsson, U., Ligatti, J.: Control-flow integrity - principles, implementations, and applications. In: ACM conference on Computer and Communications Security (CCS), Alexandria, VA (November 2005)

[2]

Akritidis, P., Cadar, C., Raiciu, C., Costa, M., Castro, M.: Preventing memory error exploits with wit. In: IEEE Symposium on Security and Privacy (May 2008)

[3]

Andersen, L.O.: Program analysis and specialization for the C programming language. PhD Thesis, DIKU, University of Copenhagen (May 1994), ftp.diku.dk/ pub/diku/semantics/papers/D-203.dvi.Z

[4]

Austin, T.M., Breach, S.E., Sohi, G.S.: Efficient detection of all pointer and array access errors. In: ACM SIGPLAN Conference on Programming Language Design and Implementation, Orlando, Florida, pp. 290-301 (June 1994)

[5]

Baratloo, A., Singh, N., Tsai, T.: Transparent run-time defense against stack smashing attacks. In: USENIX Annual Technical Conference, Berkeley, CA, pp. 251-262 (June 2000)

[6]

Barrantes, E.G., Ackley, D.H., Forrest, S., Palmer, T.S., Stefanović, D., Zovi, D.D.: Randomized instruction set emulation to disrupt binary code injection attacks. In: ACM conference on Computer and Communications Security (CCS), Washington, DC (October 2003)

[7]

Berger, E.D., Zorn, B.G.: DieHard: Probabilistic memory safety for unsafe languages. In: ACM SIGPLAN Conference on Programming Language Design and Implementation, Ottawa, Canada, pp. 158-168 (June 2006)

[8]

Bhatkar, S.: Defeating memory error exploits using automated software diversity. Ph.D. Thesis, Stony Brook University (September 2007), http://seclab. cs.sunysb.edu/seclab/pubs/thesis/sandeep.pdf

[9]

Bhatkar, S., DuVarney, D.C., Sekar, R.: Address obfuscation: An efficient approach to combat a broad range of memory error exploits. In: USENIX Security Symposium (August 2003)

[10]

Bhatkar, S., Sekar, R., DuVarney, D.C.: Efficient techniques for comprehensive protection from memory error exploits. In: USENIX Security Symposium, Baltimore, MD (August 2005)

[11]

Bruschi, D., Cavallaro, L., Lanzi, A.: Diversified process replicae for defeating memory error exploits. In: International Workshop on Information Assurance (WIA) (April 2007)

[12]

Castro, M., Costa, M., Harris, T.: Securing software by enforcing data-flow integrity. In: USENIX Symposium on Operating Systems Design and Implementation (OSDI), Seattle, WA (November 2006)

[13]

Chen, S., Xu, J., Sezer, E.C.: Non-control-hijacking attacks are realistic threats. In: USENIX Security Symposium (2005)

[14]

Chew, M., Song, D.: Mitigating buffer overflows by operating system randomization. Technical Report CMU-CS-02-197, Carnegie Mellon University (December 2002)

[15]

Chiueh, T., Hsu, F.: RAD: A compile-time solution to buffer overflow attacks. In: IEEE International Conference on Distributed Computing Systems, Phoenix, Arizona (April 2001)

[16]

Cowan, C., Barringer, M., Beattie, S., Kroah-Hartman, G.: FormatGuard: Automatic protection from printf format string vulnerabilities. In: USENIX Security Symposium (2001)

[17]

Cowan, C., Beattie, S., Johansen, J., Wagle, P.: PointGuard: Protecting pointers from buffer overflow vulnerabilities. In: USENIX Security Symposium, Washington, DC (August 2003)

[18]

Cowan, C., Pu, C., Maier, D., Walpole, J., Bakke, P., Beattie, S., Grier, A., Wagle, P., Zhang, Q., Hinton, H.: StackGuard: Automatic adaptive detection and prevention of buffer-overflow attacks. In: USENIX Security Symposium, San Antonio, Texas, pp. 63-78 (January 1998)

[19]

Cox, B., Evans, D., Filipi, A., Rowanhill, J., Hu, W., Davidson, J., Knight, J., Nguyen-Tuong, A., Hiser, J.: N-variant systems: A secretless framework for security through diversity. In: USENIX Security Symposium (August 2006)

[20]

Dhurjati, D., Adve, V.: Backwards-compatible array bounds checking for c with very low overhead. In: International Conference on Software Engineering (2006)

[21]

Emami, M., Ghiya, R., Hendren, L.J.: Context-sensitive interprocedural points-to analysis in the presence of function pointers. In: ACM SIGPLAN Conference on Programming Language Design and Implementation, pp. 242-256 (June 1994)

[22]

Etoh, H., Yoda, K.: Protecting from stack-smashing attacks (June 2000), http: //www.trl.ibm.com/projects/security/ssp/main.html

[23]

Forrest, S., Somayaji, A., Ackley, D.H.: Building diverse computer systems. In: Workshop on Hot Topics in Operating Systems, pp. 67-72. IEEE Computer Society Press, Los Alamitos (1997)

[24]

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

[25]

Hind, M., Burke, M., Carini, P., Choi, J.-D.: Interprocedural pointer alias analysis. In: ACM Transactions on Programming Languages and Systems (TOPLAS) (July 1999)

[26]

Jones, R.W.M., Kelly, P.H.J.: Backwards-compatible bounds checking for arrays and pointers in C programs. In: International Workshop on Automated and Algorithmic Debugging, pp. 13-26 (1997)

[27]

Kc, G.S., Keromytis, A.D., Prevelakis, V.: Countering code-injection attacks with instruction-set randomization. In: ACM conference on Computer and Communications Security (CCS), Washington, DC, pp. 272-280 (October 2003)

[28]

Li, L., Just, J., Sekar, R.: Address-space randomization for windows systems. In: Annual Computer Security Applications Conference (ACSAC) (December 2006)

[29]

McPeak, S., Necula, G.C., Rahul, S.P., Weimer, W.: CIL: Intermediate language and tools for C program analysis and transformation. In: Conference on Compiler Construction (2002)

[30]

Necula, G.C., McPeak, S., Weimer, W.: CCured: type-safe retrofitting of legacy code. In: ACMSymposium on Principles of Programming Languages (POPL) (January 2002)

[31]

Novark, G., Berger, E.D., Zorn, B.G.: Exterminator: Automatically correcting memory errors with high probability. In: ACM SIGPLAN Conference on Programming Language Design and Implementation, San Diego, CA, pp. 1-11 (June 2007)

[32]

PaX (2001), http://pax.grsecurity.net

[33]

Ramalingam, G.: The undecidability of aliasing. ACM Transactions on Programming Languages and Systems (TOPLAS) 16(5), 1467-1471 (1994)

[34]

Ruwase, O., Lam, M.S.: A practical dynamic buffer overflow detector. In: Network and Distributed System Security Symposium, San Diego, CA, pp. 159-169 (February 2004)

[35]

Shacham, H., Page, M., Pfaff, B., Goh, E., Modadugu, N., Boneh, D.: On the effectiveness of address-space randomization. In: ACMconference on Computer and Communications Security (CCS), Washington, DC, pp. 298-307 (October 2004)

[36]

Steensgaard, B.: Points-to analysis by type inference of programs with structures and unions. In: Gyimóthy, T. (ed.) CC 1996. LNCS, vol. 1060, pp. 136-150. Springer, Heidelberg (1996)

[37]

Steensgaard, B.: Points-to analysis in almost linear time. In: ACM Symposium on Principles of Programming Languages (POPL), pp. 32-41 (January 1996)

[38]

Wagner, D., Dean, D.: Intrusion detection via static analysis. In: IEEE Symposium on Security and Privacy (May 2001)

[39]

Wilson, R.P., Lam, M.S.: Efficient context-sensitive pointer analysis for C programs. In: ACM SIGPLAN Conference on Programming Language Design and Implementation (1995)

[40]

Xu, J., Kalbarczyk, Z., Iyer, R.K.: Transparent runtime randomization for security. In: Symposium on Reliable and Distributed Systems (SRDS), Florence, Italy (October 2003)

[41]

Xu, W., DuVarney, D.C., Sekar, R.: An efficient and backwards-compatible transformation to ensure memory safety of C programs. In: ACM SIGSOFT International Symposium on the Foundations of Software Engineering, Newport Beach, CA (November 2004)

Cited By

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
Ahmed SLiljestrand HJamjoom HHicks MAsokan NYao DCalandrino JTroncoso C(2023)Not all data are created equalProceedings of the 32nd USENIX Conference on Security Symposium10.5555/3620237.3620318(1433-1450)Online publication date: 9-Aug-2023
https://dl.acm.org/doi/10.5555/3620237.3620318
Franzen FWilhelmer AGrossklags J(2023)RandCompile: Removing Forensic Gadgets from the Linux Kernel to Combat its AnalysisProceedings of the 39th Annual Computer Security Applications Conference10.1145/3627106.3627197(677-690)Online publication date: 4-Dec-2023
https://dl.acm.org/doi/10.1145/3627106.3627197
Show More Cited By

Recommendations

Return address randomization scheme for annuling data-injection buffer overflow attacks
Inscrypt'06: Proceedings of the Second SKLOIS conference on Information Security and Cryptology

Buffer overflow(BOF) has been the most common form of vulnerability in software systems today, and many methods exist to defend software systems against BOF attacks. Among them, the instruction set randomization scheme, which makes attacker not to know ...
An Enhanced Dynamic Information Flow Tracking Method with Reverse Stack Execution

Memory errors have long been a critical security issue primarily for C/C++ programming languages and are still considered one of the top three most dangerous software errors according to the MITRE ranking. In this paper the authors focus on their ...
Fast and automated generation of attack signatures: a basis for building self-protecting servers
CCS '05: Proceedings of the 12th ACM conference on Computer and communications security

Large-scale attacks, such as those launched by worms and zombie farms, pose a serious threat to our network-centric society. Existing approaches such as software patches are simply unable to cope with the volume and speed with which new vulnerabilities ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

DIMVA '08: Proceedings of the 5th international conference on Detection of Intrusions and Malware, and Vulnerability Assessment

July 2008

278 pages

ISBN:9783540705413

Editor:
Diego Zamboni

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 10 July 2008

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

60
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

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
Ahmed SLiljestrand HJamjoom HHicks MAsokan NYao DCalandrino JTroncoso C(2023)Not all data are created equalProceedings of the 32nd USENIX Conference on Security Symposium10.5555/3620237.3620318(1433-1450)Online publication date: 9-Aug-2023
https://dl.acm.org/doi/10.5555/3620237.3620318
Franzen FWilhelmer AGrossklags J(2023)RandCompile: Removing Forensic Gadgets from the Linux Kernel to Combat its AnalysisProceedings of the 39th Annual Computer Security Applications Conference10.1145/3627106.3627197(677-690)Online publication date: 4-Dec-2023
https://dl.acm.org/doi/10.1145/3627106.3627197
Berlakovich FBrunthaler SFedorova ANarayanan DDi Luna GQuerzoni L(2023)R2C: AOCR-Resilient Diversity with Reactive and Reflective CamouflageProceedings of the Eighteenth European Conference on Computer Systems10.1145/3552326.3587439(488-504)Online publication date: 8-May-2023
https://dl.acm.org/doi/10.1145/3552326.3587439
Nie XChen LWei HZhang YCui NShi G(2023)KPDFIComputers and Security10.1016/j.cose.2023.103183128:COnline publication date: 1-May-2023
https://dl.acm.org/doi/10.1016/j.cose.2023.103183
Shen ZDharsee KCriswell J(2022)Randezvous: Making Randomization Effective on MCUsProceedings of the 38th Annual Computer Security Applications Conference10.1145/3564625.3567970(28-41)Online publication date: 5-Dec-2022
https://dl.acm.org/doi/10.1145/3564625.3567970
Vinck JAbrath BCoppens BVoulimeneas ADe Sutter BVolckaert SBromberg YKermarrec AKozyrakis C(2022)Sharing is caringProceedings of the Seventeenth European Conference on Computer Systems10.1145/3492321.3519558(99-116)Online publication date: 28-Mar-2022
https://dl.acm.org/doi/10.1145/3492321.3519558
Xu JLin HYuan ZShen WZhou YChang RWu LRen KOshana R(2022)RegVaultProceedings of the 59th ACM/IEEE Design Automation Conference10.1145/3489517.3530549(715-720)Online publication date: 10-Jul-2022
https://dl.acm.org/doi/10.1145/3489517.3530549
Wang LZhang MJajodia SSinghal AAlbanese M(2022)Modeling Network Diversity for Evaluating the Robustness of Networks against Zero-Day AttacksComputer Security - ESORICS 201410.1007/978-3-319-11212-1_28(494-511)Online publication date: 10-Mar-2022
https://dl.acm.org/doi/10.1007/978-3-319-11212-1_28
Huang JXue SWang C(2022)Fast Out-of-Band Data Integrity Monitor to Mitigate Memory Corruption AttacksProvable and Practical Security10.1007/978-3-031-20917-8_10(139-155)Online publication date: 11-Nov-2022
https://dl.acm.org/doi/10.1007/978-3-031-20917-8_10
Show More Cited By

View Options

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

Media

Figures

Other

Tables

View Table of Contents