skip to main content
article

Randomized instruction set emulation

Published: 01 February 2005 Publication History

Abstract

Injecting binary code into a running program is a common form of attack. Most defenses employ a “guard the doors” approach, blocking known mechanisms of code injection. Randomized instruction set emulation (RISE) is a complementary method of defense, one that performs a hidden randomization of an application's machine code. If foreign binary code is injected into a program running under RISE, it will not be executable because it will not know the proper randomization. The paper describes and analyzes RISE, describing a proof-of-concept implementation built on the open-source Valgrind IA32-to-IA32 translator. The prototype effectively disrupts binary code injection attacks, without requiring recompilation, linking, or access to application source code. Under RISE, injected code (attacks) essentially executes random code sequences. Empirical studies and a theoretical model are reported which treat the effects of executing random code on two different architectures (IA32 and PowerPC). The paper discusses possible extensions and applications of the RISE technique in other contexts.

References

[1]
Anderson, R. 2003. “Trusted Computing” and competition policy---Issues for computing professionals. Upgrade IV, 3 (June), 35--41.]]
[2]
Arbaugh, W. A. 2002. Improving the TCPA specification. IEEE Comput. 35, 8 (Aug.), 77--79.]]
[3]
Avijit, K., Gupta, P., and Gupta, D. 2004. Tied, libsafeplus: Tools for dynamic buffer overflow protection. In Proceeding of the 13th USENIX Security Symposium. San Diego, CA.]]
[4]
Avizienis, A. 1995. The methodology of N-version programming. In Software Fault Tolerance, M. Lyu, Ed. Wiley, New York, 23--46.]]
[5]
Avizienis, A. and Chen, L. 1977. On the implementation of N-Version programming for software fault tolerance during execution. In Proceedings of IEEE COMPSAC 77. 149--155.]]
[6]
Bala, V., Duesterwald, E., and Banerjia, S. 2000. Dynamo: A transparent dynamic optimization system. In Proceedings of the ACM SIGPLAN '00 Conference on Programming language design and implementation. ACM Press, Vancouver, British Columbia, Canada, 1--12.]]
[7]
Baratloo, A., Singh, N., and Tsai, T. 2000. Transparent run-time defense against stack smashing attacks. In Proceedings of the 2000 USENIX Annual Technical Conference (USENIX-00), Berkeley, CA. 251--262.]]
[8]
Barrantes, E. G., Ackley, D., Forrest, S., Palmer, T., Stefanovic, D., and Zovi, D. D. 2003. Randomized instruction set emulation to disrupt binary code injection attacks. In Proceedings of the 10th ACM Conference on Computer and Communications Security, Washington, DC. 272--280.]]
[9]
Best, R. M. 1979. Microprocessor for executing enciphered programs, U.S. Patent no. 4 168 396.]]
[10]
Best, R. M. 1980. Preventing software piracy with crypto-microprocessors. In Proceedings of the IEEE Spring COMPCON '80, San Francisco, CA. 466--469.]]
[11]
Bhatkar, S., DuVarney, D., and Sekar, R. 2003. Address obfuscation: An approach to combat buffer overflows, format-string attacks and more. In Proceedings of the 12th USENIX Security Symposium, Washington, DC. 105--120.]]
[12]
Boyd, S. W. and Keromytis, A. D. 2004. SQLrand: Preventing SQL injection attacks. In Proceedings of the 2nd Applied Cryptography and Network Security (ACNS) Conference. Yellow Mountain, China. 292--302.]]
[13]
Bruening, D., Amarasinghe, S., and Duesterwald, E. 2001. Design and implementation of a dynamic optimization framework for Windows. In 4th ACM Workshop on Feedback-Directed and Dynamic Optimization (FDDO-4).]]
[14]
Butler, T. R. 2004. Bochs. http://bochs.sourceforge.net/.]]
[15]
Chew, M. and Song, D. 2002. Mitigating Buffer Overflows by Operating System Randomization. Tech. Rep. CMU-CS-02-197, Department of Computer Science, Carnegie Mellon University.]]
[16]
Chiueh, T. and Hsu, F.-H. 2001. Rad: A compile-time solution to buffer overflow attacks. In Proceedings of the 21st International Conference on Distributed Computing Systems (ICDCS), Phoenix, AZ. 409--420.]]
[17]
Cohen, F. 1993. Operating system protection through program evolution. Computers and Security 12, 6 (Oct.), 565--584.]]
[18]
CORE Security. 2004. CORE security technologies. http://www1.corest.com/home/home.php.]]
[19]
Cowan, C., Barringer, M., Beattie, S., and Kroah-Hartman, G. 2001. Format guard: Automatic protection from printf format string vulnerabilities. In Proceedings of the 10th USENIX Security Symposium, Washington, DC. 191--199.]]
[20]
Cowan, C., Beattie, S., Johansen, J., and Wagle, P. 2003. Pointguard: Protecting pointers from buffer overflow vulnerabilities. In Proceedings of the 12th USENIX Security Symposium, Washington, DC. 91--104.]]
[21]
Cowan, C., Hinton, H., Pu, C., and Walpole, J. 2000. A cracker patch choice: An analysis of post hoc security techniques. In National Information Systems Security Conference (NISSC), Baltimore MD.]]
[22]
Cowan, C., Pu, C., Maier, D., Hinton, H., Bakke, P., Beattie, S., Grier, A., Wagle, P., and Zhang, Q. 1998. Automatic detection and prevention of buffer-overflow attacks. In Proceedings of the 7th USENIX Security Symposium, San Antonio, TX.]]
[23]
Cowan, C., Wagle, P., Pu, C., Beattie, S., and Walpole, J. 2000b. Buffer overflows: Attacks and defenses for the vulnerability of the decade. In DARPA Information Survivability Conference and Exposition (DISCEX 2000). 119--129.]]
[24]
Dallas Semiconductor. 1999. DS5002FP secure microprocessor chip. http://pdfserv.maxim-ic.com/en/ds/DS5002FP.pdf.]]
[25]
Dor, N., Rodeh, M., and Sagiv, M. 2003. CSSV: Towards a realistic tool for statically detecting all buffer overflows in c. In Proceedings of the ACM SIGPLAN 2003 Conference on Programming Language Design and Implementation. 155--167.]]
[26]
Etoh, H. and Yoda, K. 2000. Protecting from stack-smashing attacks. Web publishing, IBM Research Division, Tokyo Research Laboratory, http://www.trl.ibm.com/projects/security/ssp/main.html. June 19.]]
[27]
Etoh, H. and Yoda, K. 2001. Propolice: Improved stack smashing attack detection. IPSJ SIGNotes Computer Security (CSEC) 14 (Oct. 26).]]
[28]
Fayolle, P.-A. and Glaume, V. 2002. A buffer overflow study, attacks & defenses. Web publishing, ENSEIRB, http://www.wntrmute.com/docs/bufferoverflow/report.html.]]
[29]
Forrest, S., Somayaji, A., and Ackley, D. 1997. Building diverse computer systems. In Proceedings of the 6th Workshop on Hot Topics in Operating Systems. 67--72.]]
[30]
Frantzen, M. and Shuey, M. 2001. Stackghost: Hardware facilitated stack protection. In Proceedings of the 10th USENIX Security Symposium. Washington, DC.]]
[31]
Gera and Riq. 2002. Smashing the stack for fun and profit. Phrack 59, 11 (July 28).]]
[32]
Harper, M. 2002. SQL injection attacks---Are you safe? In Sitepoint, http://www.sitepoint. com/article/794.]]
[33]
IBM. 2003. PowerPC Microprocessor Family: Programming Environments Manual for 64 and 32-Bit Microprocessors. Version 2.0. Number order nos. 253665, 253666, 253667, 253668.]]
[34]
Intel Corporation. 2004. The IA-32 Intel Architecture Software Developer's Manual. Number order nos. 253665, 253666, 253667, 253668.]]
[35]
Jim, T., Morrisett, G., Grossman, D., Hicks, M., Cheney, J., and Wang, Y. 2002. Cyclone: A safe dialect of c. In Proceedings of the USENIX Annual Technical Conference, Monterey, CA. 275--288.]]
[36]
Jones, R. W. M. and Kelly, P. H. 1997. Backwards-compatible bounds checking for arrays and pointers in C programs. In 3rd International Workshop on Automated Debugging. 13--26.]]
[37]
Kc, G. S., Keromytis, A. D., and Prevelakis, V. 2003. Countering code-injection attacks with instruction-set randomization. In Proceedings of the 10th ACM Conference on Computer and Communications Security. ACM Press, Washington, DC. 272--280.]]
[38]
Kiriansky, V., Bruening, D., and Amarasinghe, S. 2002. Secure execution via program sheperding. In Proceeding of the 11th USENIX Security Symposium, San Francisco, CA.]]
[39]
Klaiber, A. 2000. The technology behind the crusoe processors. White Paper http://www.transmeta.com/pdf/white_papers/paper_aklaiber_19jan00.pdf. January.]]
[40]
Kuhn, M. 1997. The TrustNo 1 Cryptoprocessor Concept. Tech. Rep. CS555 Report, Purdue University. April 04.]]
[41]
Larochelle, D. and Evans, D. 2001. Statically detecting likely buffer overflow vulnerabilities. In Proceedings of the 10th USENIX Security Symposium, Washington, DC. 177--190.]]
[42]
Lhee, K. and Chapin, S. J. 2002. Type-assisted dynamic buffer overflow detection. In Proceeding of the 11th USENIX Security Symposium, San Francisco, CA. 81--88.]]
[43]
Milenković, M., Milencović, A., and Jovanov, E. 2004. A framework for trusted instruction execution via basic block signature verification. In Proceedings of the 42nd Annual Southeast Regional Conference (ACM SE'04). ACM Press, Huntsville, AL. 191--196.]]
[44]
Nahum, E. M. 2002. Deconstructing specweb99. In Proceedings of 7th International Workshop on Web Content Caching and Distribution, Boulder, CO.]]
[45]
Nebenzahl, D. and Wool, A. 2004. Install-time vaccination of Windows executables to defend against stack smashing attacks. In Proceedings of the 19th IFIP International Information Security Conference. Kluwer, Toulouse, France, 225--240.]]
[46]
Necula, G. C., McPeak, S., and Weimer, W. 2002. Ccured: Type-safe retrofitting of legacy code. In Proceedings of the Symposium on Principles of Programming Languages. 128--139.]]
[47]
Nergal. 2001. The advanced return-into-lib(c) exploits. Phrack 58, 4 (Dec.).]]
[48]
Nethercote, N. and Seward, J. 2003. Valgrind: A program supervision framework. In Electronic Notes in Theoretical Computer Science, O. Sokolsky and M. Viswanathan, Eds. Vol. 89. Elsevier, Amsterdam.]]
[49]
Newsham, T. 2000. Format string attacks. http://www.securityfocus.com/archive/1/81565.]]
[50]
PaX Team. 2003. Documentation for the PaX project. See Homepage of The PaX Team. http://pax.grsecurity.net/docs/index.html.]]
[51]
Prasad, M. and Chiueh, T. 2003. A binary rewriting defense against stack based overflow attacks. In Proceedings of the USENIX 2003 Annual Technical Conference, San Antonio, TX.]]
[52]
Pu, C., Black, A., Cowan, C., and Walpole, J. 1996. A specialization toolkit to increase the diversity of operating systems. In Proceedings of the 1996 ICMAS Workshop on Immunity-Based Systems, Nara, Japan.]]
[53]
Randell, B. 1975. System structure for software fault tolerance. IEEE Trans. Software Eng. 1, 2, 220--232.]]
[54]
Ruwase, O. and Lam, M. S. 2004. A practical dynamic buffer overflow detector. In Proceedings of the 11th Annual Network and Distributed System Security Symposium.]]
[55]
Schneier, B. 1996. Applied Cryptography. Wiley, New York.]]
[56]
Security Focus. 2003. CVS directory request double free heap corruption vulnerability. http://www.securityfocus.com/bid/6650.]]
[57]
Seward, J. and Nethercote, N. 2004. Valgrind, an open-source memory debugger for x86-GNU/Linux. http://valgrind.kde.org/.]]
[58]
Simon, I. 2001. A comparative analysis of methods of defense against buffer overflow attacks. Web publishing, California State University, Hayward, http://www.mcs.csuhayward.edu/simon/security/boflo.html. January 31.]]
[59]
SPEC Inc. 1999. Specweb99. Tech. Rep. SPECweb99_Design_062999.html, SPEC Inc. June 29.]]
[60]
TCPA 2004. TCPA trusted computing platform alliance. http://www.trustedcomputing.org/home.]]
[61]
Tool Interface Standards Committee. 1995. Executable and Linking Format (ELF). Tool Interface Standards Committee.]]
[62]
Tsai, T. and Singh, N. 2001. Libsafe 2.0: Detection of format string vulnerability exploits. White Paper Version 3-21-01, Avaya Labs, Avaya Inc. February 6.]]
[63]
Tso, T. 1998. random.C: A strong random number generator. http://www.linuxsecurity.com/feature_stories/random.c.]]
[64]
Vendicator. 2000. StackShield: A stack smashing technique protection tool for Linux. http://angelfire.com/sk/stackshield.]]
[65]
Wagner, D., Foster, J. S., Brewer, E. A., and Aiken, A. 2000. A first step towards automated detection of buffer overrun vulnerabilities. In Network and Distributed System Security Symposium, San Diego, CA. 3--17.]]
[66]
Wilander, J. and Kamkar, M. 2003. A comparison of publicly available tools for dynamic buffer overflow prevention. In Proceedings of the 10th Network and Distributed System Security Symposium, San Diego, CA. 149--162.]]
[67]
Xu, J., Kalbarczyk, Z., and Iyer, R. K. 2003. Transparent runtime randomization for security. In Proceeding of the 22nd International Symposium on Reliable Distributed Systems (SRDS'03), Florence, Italy. 26--272.]]
[68]
Xu, J., Kalbarczyk, Z., Patel, S., and Iyer, R. K. 2002. Architecture support for defending against buffer overflow attacks. In 2nd Workshop on Evaluating and Architecting System dependabilitY (EASY), San Jose, CA. http://www.crhc.uiuc.edu/EASY/.]]

Cited By

View all
  • (2023)A survey: When moving target defense meets game theoryComputer Science Review10.1016/j.cosrev.2023.10054448(100544)Online publication date: May-2023
  • (2021)Performance impact analysis of services under a time-based moving target defense mechanismThe Journal of Defense Modeling and Simulation: Applications, Methodology, Technology10.1177/1548512921103693720:1(41-56)Online publication date: 18-Aug-2021
  • (2020)Layered obfuscation: a taxonomy of software obfuscation techniques for layered securityCybersecurity10.1186/s42400-020-00049-33:1Online publication date: 3-Apr-2020
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Information and System Security
ACM Transactions on Information and System Security  Volume 8, Issue 1
February 2005
152 pages
ISSN:1094-9224
EISSN:1557-7406
DOI:10.1145/1053283
Issue’s Table of Contents
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 February 2005
Published in TISSEC Volume 8, Issue 1

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Automated diversity
  2. randomized instruction sets
  3. software diversity

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)17
  • Downloads (Last 6 weeks)2
Reflects downloads up to 18 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2023)A survey: When moving target defense meets game theoryComputer Science Review10.1016/j.cosrev.2023.10054448(100544)Online publication date: May-2023
  • (2021)Performance impact analysis of services under a time-based moving target defense mechanismThe Journal of Defense Modeling and Simulation: Applications, Methodology, Technology10.1177/1548512921103693720:1(41-56)Online publication date: 18-Aug-2021
  • (2020)Layered obfuscation: a taxonomy of software obfuscation techniques for layered securityCybersecurity10.1186/s42400-020-00049-33:1Online publication date: 3-Apr-2020
  • (2020)On Architectural Support for Instruction Set RandomizationACM Transactions on Architecture and Code Optimization10.1145/341984117:4(1-26)Online publication date: 10-Nov-2020
  • (2020)Internal interface diversification as a method against malwareJournal of Cyber Security Technology10.1080/23742917.2020.1813397(1-26)Online publication date: 31-Aug-2020
  • (2019)Hiding a fault enabled virus through code constructionJournal of Computer Virology and Hacking Techniques10.1007/s11416-019-00340-z16:2(103-124)Online publication date: 24-Oct-2019
  • (2019)Overview of Control and Game Theory in Adaptive Cyber DefensesAdversarial and Uncertain Reasoning for Adaptive Cyber Defense10.1007/978-3-030-30719-6_1(1-11)Online publication date: 31-Aug-2019
  • (2018)Evaluation of Register Number Abstraction for Enhanced Instruction Register FilesIEICE Transactions on Information and Systems10.1587/transinf.2017EDP7221E101.D:6(1521-1531)Online publication date: 1-Jun-2018
  • (2018)Integrated instruction set randomization and control reconfiguration for securing cyber-physical systemsProceedings of the 5th Annual Symposium and Bootcamp on Hot Topics in the Science of Security10.1145/3190619.3190636(1-10)Online publication date: 10-Apr-2018
  • (2018)Hybrid Obfuscation to Protect Against Disclosure Attacks on Embedded MicroprocessorsIEEE Transactions on Computers10.1109/TC.2017.264952067:3(307-321)Online publication date: 1-Mar-2018
  • Show More Cited By

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media