Survey of methods for automated code-reuse exploit generation

This paper provides a survey of methods and tools for automated code-reuse exploit generation. Such exploits use code that already contains in a vulnerable program. The code-reuse approach, e.g., return-oriented programming, allows one to exploit vulnerabilities in the presence of operating system protection that prohibits execution of code in memory pages marked as data. We define fundamental terms such as gadget, gadget frame, gadget catalog. Moreover, we show that a gadget is, in fact, an instruction, and a set of gadgets defines a virtual machine. We can reduce an exploit creation problem to code generation for this virtual machine. Each particular executable file defines a virtual machine instruction set. We provide a survey of methods for gadgets searching and determining their semantics (creating a gadget catalog). These methods allow one to get the virtual machine instruction set. If a set of gadgets is Turing-complete, then a compiler can use a gadget catalog as a target architecture. However, some instructions can be absent. Hence we discuss several approaches to replace missing instructions with multiple gadgets. An exploit generation tool can chain gadgets by pattern searching (regular expressions) or taking gadgets semantics into consideration. Furthermore, some chaining methods use genetic algorithms, while others use SMTsolvers. We compare existing open source tools and propose a testing system rop-benchmark that can be used to verify whether a generated chain successfully opens a shell.

1. The Heartbleed bug. URL: http://heartbleed.com.

2. D. Halperin, T. S. Heydt-Benjamin, B. Ransford, S. S. Clark, B. Defend, W. Morgan, K. Fu, T. Kohno, and W. H. Maisel. Pacemakers and implantable cardiac defibrillators: software radio attacks and zero-power defenses. In Proc. of the IEEE Symposium on Security and Privacy, 2008, pp. 129–142.

3. CWE top 25 most dangerous software errors. URL: https:// cwe.mitre.org/top25/archive/2019/2019_cwe_top25.html.

4. A. Peslyak. Getting around non-executable stack (and fix). Bugtraq mailing list archives, Aug. 1997. URL: https://seclists.org/bugtraq/1997/Aug/63.

5. H. Shacham. The geometry of innocent flesh on the bone: return-into-libc without function calls (on the x86). In Proc. of the 14th ACM Conference on Computer and Communications Security, 2007, pp. 552–561.

6. E.J. Schwartz, T. Avgerinos, and D. Brumley. Q: exploit hardening made easy. In Proc, of the 20th USENIX Conference on Security, 2011, 16 p.

7. R. Roemer, E. Buchanan, H. Shacham, and S. Savage. Return-oriented programming: systems, languages, and applications. ACM Transactions on Information and System Security, vol. 15, no. 1, 2012, pp. 2:1–2:34.

8. T. Kornau. Return oriented programming for the ARM Architecture. Master’s thesis, Ruhr-University, Bochum, Germany, 2009.

9. S. Checkoway, L. Davi, A. Dmitrienko, A.-R. Sadeghi, H. Shacham, and M. Winandy. Return-oriented programming without returns. In Proc. of the 17th ACM Conference on Computer and Communications Security, 2010, pp. 559–572.

10. L. Davi, A. Dmitrienko, A.-R. Sadeghi, and M. Winandy. Return-oriented programming without returns on ARM. Technical Report HGI-TR2010-002, Ruhr-University, Bochum, Germany, 2010.

11. Z.-S. Huang and I. G. Harris. Return-oriented vulnerabilities in ARM executables. In Proc. of the IEEE Conference on Technologies for Homeland Security, 2012, pp. 1–6.

12. O.L. Fraser, N. Zincir-Heywood, M. Heywood, and J.T. Jacobs. Return-oriented programme evolution with ROPER: a proof of concept. In Proc. of the Genetic and Evolutionary Computation Conference Companion, 2017, pp. 1447–1454.

13. E. Buchanan, R. Roemer, H. Shacham, and S. Savage. When good instructions go bad: generalizing return-oriented programming to RISC. In Proc. of the 15th ACM Conference on Computer and Communications Security, 2008, pp. 27–38.

14. A. Francillon and C. Castelluccia. Code injection attacks on harvard-architecture devices. In Proc. of the 15th ACM Conference on Computer and Communications Security, 2008, pp. 15–26.

15. F. Lindner. Cisco IOS router exploitation. In Black Hat USA, 2009. URL: https://www.blackhat.com/presentations/bh-usa-09/LINDNER/BHUSA09-Lindner-RouterExploit-PAPER.pdf.

16. S. Checkoway, A. J. Feldman, B. Kantor, J. A. Halderman, E. W. Felten, and H. Shacham. Can DREs provide long-lasting security? The case of return-oriented programming and the AVC advantage. In Proc. of the 2009 Conference on Electronic Voting Technology/Workshop on Trustworthy Elections, 2009, 16 p.

17. T. Bletsch, X. Jiang, V. W. Freeh, and Z. Liang. Jump-oriented programming: a new class of code-reuse attack. In Proc. of the 6th ACM Symposium on Information, Computer and Communications Security, 2011, pp. 30–40.

18. P. Chen, X. Xing, B. Mao, L. Xie, X. Shen, and X. Yin. Automatic construction of jump-oriented programming shellcode (on the x86). In Proc. of the 6th ACM Symposium on Information, Computer and Communications Security, 2011, pp. 20–29.

19. A. Sadeghi, S. Niksefat, and M. Rostamipour. Pure-call oriented programming (PCOP): chaining the gadgets using call instructions. Journal of Computer Virology and Hacking Techniques, vol. 14, no. 2, pp. 139–156.

20. R. Hund, T. Holz, and F. C. Freiling. Return-oriented rootkits: bypassing kernel code integrity protection mechanisms. In Proc. of the 18th Conference on USENIX Security Symposium, 2009, pp. 383–398.

21. N.A. Quynh. OptiROP: hunting for ROP gadgets in style. URL: https://media.blackhat.com/us-13/US-13-Quynh-OptiROP-Huntingfor-ROP-Gadgets-in-Style-Slides.pdf.

22. W. Ding, X. Xing, P. Chen, Z. Xin, and B. Mao. Automatic construction of printable return-oriented programming payload. In Proc. of the 9th International Conference on Malicious and Unwanted Software: The Americas, 2014, pp. 18–25.

23. Y. Ouyang, Q. Wang, J. Peng, and J. Zeng. An advanced automatic construction method of ROP. Wuhan University Journal of Natural Sciences, vol. 20, no. 2, 2015, pp. 119–128.

24. A. Follner, A. Bartel, H. Peng, Y.-C. Chang, K. Ispoglou, M. Payer, and E. Bodden. PSHAPE: automatically combining gadgets for arbitrary method execution. Lecture Notes in Computer Science, vol. 9871, 2016, pp. 212–228.

25. B. Milanov. ROPGenerator: practical automated ROP-chain generation, 2018. URL: https://youtu.be/rz7Z9fBLVs0.

26. N. Mosier and P. Johnson. ROP with a 2nd stack, 2019. URL: http://www.cs.middlebury.edu/~nmosier/portfolio/rsrc/ropcslides.pdf.

27. A. Follner, A. Bartel, H. Peng, Y.-C. Chang, K. Ispoglou, M. Payer, and E. Bodden. PSHAPE - practical support for half-automated program exploitation. URL: https://github.com/Alexandre-Bartel/inspector-gadget.

28. O.L. Fraser. ROPER: a genetic ROP-chain development tool. URL: https: //github.com/oblivia-simplex/roper.

29. mona.py, Corelan Consulting BVBA. URL: https://github.com/ corelan/mona.

30. J.Salwan. ROPgadgettool. URL: https://github.com/JonathanSalwan/ ROPgadget.

31. B. Milanov. ROPGenerator. URL: https://github.com/BoyanMILANOV/ropgenerator.

32. C. Salls. angrop. URL: https://github.com/salls/angrop.

33. S. Schirra. Ropper. URL: https://github.com/sashs/ropper.

34. Paul. ROPC. URL: https://github.com/pakt/ropc.

35. ropc-llvm, Programa STIC. URL: https://github.com/programastic/ropc-llvm.

36. J. Stewart. An open source, multi-architecture ROP compiler. URL: https:// github.com/jeffball55/rop_compiler.

37. A. Nurmukhametov. ROP Benchmark. URL: https://github.com/ ispras/rop-benchmark.

38. J. Salwan. An introduction to the return oriented programming and ROP-chain generation, 2014. URL: http://shell-storm.org/talks/ROP_ course_lecture_jonathan_salwan_2014.pdf.

39. T. F. Dullien. Weird machines, exploitability, and provable unexploitability. IEEE Transactions on Emerging Topics in Computing (Early Access), 2017, 15 p.

40. M. Graziano, D. Balzarotti, and A. Zidouemba. ROPMEMU: a framework for the analysis of complex code-reuse attacks. In Proc. of the 11th ACM on Asia Conference on Computer and Communications Security, 2016, pp. 47–58.

41. E.J. Schwartz, T. Avgerinos, and D. Brumley. Update on Q: exploit hardening made easy, 2012. URL: https://edmcman.github.io/papers/ usenix11-update.pdf.

42. G. F. Roglia, L. Martignoni, R. Paleari, and D. Bruschi. Surgically returning to randomized lib(c). In Proc. of the Annual Computer Security Applications Conference, 2009, pp. 60–69.

43. N.R. Weidler, D. Brown, S.A. Mitchell, J. Anderson, J.R. Williams, A. Costley, C. Kunz, C. Wilkinson, R. Wehbe, and R. Gerdes. Return-oriented programming on a resource constrained device. Sustainable Computing: Informatics and Systems, vol. 22, 2019, pp. 244-256.

44. Вишняков А.В. Классификация ROP гаджетов. Труды ИСП РАН, том 28, вып. 6, 2016, стр. 27-36 / Vishnyakov A.V. Classification of ROP gadgets. Trudy ISP RAN/Proc. ISP RAS, vol. 28, issue 6, 2016, pp. 27-36 (in Russian). DOI: 10.15514/ISPRAS-2016-28(6)-2.

45. Вишняков А.В, Нурмухаметов А.Р., Курмангалеев Ш.Ф., Гайсарян С.С. Метод анализа атак повторного использования кода. Труды ИСП РАН, том 30, вып. 5, 2018 г., стр. 31-54 / Vishnyakov A.V., Nurmukhametov A.R., Kurmangaleev Sh.F., Gaisaryan S.S. Method for analysis of code-reuse attacks. Trudy ISP RAN/Proc. ISP RAS, vol. 30, issue 5, 2018, pp. 31-54 (in Russian). DOI: 10.15514/ISPRAS-2018-30(5)-2.

46. T. Avgerinos, S.K. Cha, B.L.T. Hao, and D. Brumley. AEG: automatic exploit generation. In Proc. of the Network and Distributed System Security Symposium, 2011, pp. 283– 300.

47. S. K. Cha, T. Avgerinos, A. Rebert, and D. Brumley. Unleashing Mayhem on binary code. In Proc. of the IEEE Symposium on Security and Privacy, 2012, pp. 380–394.

48. V.A. Padaryan, V.V. Kaushan, and A.N. Fedotov. Automated exploit generation for stack buffer overflow vulnerabilities. Programming and Computer Software, vol. 41, no. 6, 2015, pp. 373–380.

49. Федотов А.Н., Падарян В.А., Каушан В.В., Курмангалеев Ш.Ф., Вишняков А.В., Нурмухаметов А.Р. Оценка критичности программных дефектов в рамках работы современных защитных механизмов. Труды ИСП РАН, том 28, вып. 5, 2016 г., стр. 73-92 / Fedotov A.N., Padaryan V.A., Kaushan V.V., Kurmangaleev Sh.F., Vishnyakov A.V., Nurmukhametov A.R. Software defect severity estimation in presence of modern defense mechanisms. Trudy ISP RAN/Proc. ISP RAS, vol. 28, issue 5, 2016. pp. 73-92 (in Russian). DOI: 10.15514/ISPRAS-2016-28(5)-4.

50. Y. Shoshitaishvili, R. Wang, C. Salls, N. Stephens, M. Polino, A. Dutcher, J. Grosen, S. Feng, C. Hauser, C. Kruegel, and G. Vigna. SOK: (state of) the art of war: offensive techniques in binary analysis. In Proc. of the IEEE Symposium on Security and Privacy, 2016, pp. 138–157.

51. J.C. King. Symbolic execution and program testing. Communications of the ACM, vol. 19, no. 7, 1976, pp. 385– 394.

52. E. J. Schwartz, T. Avgerinos, and D. Brumley. All you ever wanted to know about dynamic taint analysis and forward symbolic execution (but might have been afraid to ask). In Proc. of the IEEE Symposium on Security and Privacy, 2019, pp. 317– 331.

53. P. Godefroid, M. Y. Levin, and D. A. Molnar. Automated whitebox fuzz testing. In Proc. of the 16th Annual Network & Distributed System Security Symposium, 2008, pp. 151–166.

54. A. Homescu, M. Stewart, P. Larsen, S. Brunthaler, and M. Franz. Microgadgets: size does matter in turing-complete return-oriented programming. In Proc. of the 6th USENIX Workshop on Offensive Technologies, 2012, 13 p.

55. M. Tran, M. Etheridge, T. Bletsch, X. Jiang, V. Freeh, and P. Ning. On the expressiveness of return-into-libc attacks. Lecture Notes in Computer Science, vol. 6961, 2011, pp. 121–141.

56. BARF: binary analysis and reverse engineering framework. URL: https://github.com/programa-stic/barf-project.

57. N. Mosier. A pair of return-oriented programming utilities: a gadget finder and ROP compiler. URL: https://github.com/nmosier/rop-tools.

58. SQLab ROP payload generation. URL: https://github.com/ SQLab/ropchain.

59. E. Göktas, B. Kollenda, P. Koppe, E. Bosman, G. Portokalidis, T. Holz, H. Bos, and C. Giuffrida. Position-independent code reuse: on the effectiveness of ASLR in the absence of information disclosure. In Proc. of the IEEE European Symposium on Security and Privacy, 2018, pp. 227–242.

60. I. Jager and D. Brumley. Efficient Directionless Weakest Preconditions. Technical Report CMU-CyLab-10-002, Carnegie Mellon University, CyLab, 2010.

61. N. Nethercote and J. Seward. Valgrind: a framework for heavyweight dynamic binary instrumentation. SIGPLAN Notice, vol. 42, no. 6, 2007, pp. 89–100.

62. T. Dullien and S. Porst. REIL: a platform-independent intermediate representation of disassembled code for static code analysis, 2009.

63. В.А. Падарян, М.А. Соловьев, А.И. Кононов. Моделирование операционной семантики машинных инструкций. Труды ИСП РАН, том 19, 2010 г., стр. 165–186 / V.A. Padaryan, M.A. Soloviev, and A.I. Kononov. Modeling operational semantics of machine instructions. Trudy ISP RAN/Proc. ISP RAS, vol. 19, 2010, pp. 165–186 (in Russian).

64. C. Heitman and I. Arce. BARF: a multiplatform open source binary analysis and reverse engineering framework. En los Materiales del XX Congreso Argentino de Ciencias de la Computación, 2014, 10 p.

65. А.В. Вишняков. Верификация семантики линейной последовательности машинных инструкций. Курсовая работа, МГУ им. М.В. Ломоносова, ф-т ВМК, 2019 г. / A. V. Vishnyakov. Semantic verification of linear machine instruction sequence. Course Paper, M.V. Lomonosov Moscow State University, faculty of CMC, 2019 (in Russian).

66. A. Follner, A. Bartel, and E. Bodden. Analyzing the gadgets: towards a metric to measure gadget quality. Lecture Notes in Computer Science, vol. 9639, 2016, pp. 155– 172.

67. E.W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, vol. 1, no. 1, 1959, pp. 269–271.

68. A.V. Aho, M.S. Lam, R. Sethi, and J.D. Ullman. Code Generation by Tiling an Input Tree. In Compilers: principles, technologies, and tools. Addison Wesley, 2th edition, 2006, pp. 560–563.

69. J. Stewart and V. Dedhia. ROP compiler. URL: https://css.csail.mit.edu/6.858/2015/projects/je25365-ve25411.pdf.

70. T. Mortimer. Removing ROP gadgets from OpenBSD. In Proc. of the AsiaBSDCon, 2019, pp.13–21.