CS 270
CS 270 Documentation
CS270 Recitation 14

LC-3 Hacking

Learning Objectives

  • Create assembly language programs, using subroutines, and the stack-based memory model
    • Implement a service routine in assembly.
    • Create a stack-based buffer overflow attack based on your knowledge of the execution stack protocol.

Setup

Make a subdirectory for the recitation, all files should reside in this subdirectory. Copy overflow.tar to the directory. Extract the files from the tar by using the command
 tar -xvf overflow.tar
You should now have the following files:
  • lc3sim-tk (you will need this local version of the simulator to run the updated LC3 OS)
  • lc3sim (local command line simulator)
  • overflow.asm (assembly code you will be running)
  • overflow.obj (assembled overflow.asm for convenience)
  • lc3os.asm (the assembly code for the LC3's OS)
  • geth.asm (code that contains new service routine that will be added to the LC3 OS)
  • Makefile (used to assemble your code and create tar file for submission)
  • privateFun (file that will contain raw hex that when used as input will cause private function to execute)
  • wholeFun (file that will contain raw hex that when used as input will cause a function written in that hex to execute)
  • runScript (basic lc3sim script for using the command line simulator)

Extending the LC3 OS

Once you have untared the files you can open the lc3os.asm file and see the LC3s operating system assembly code. Take some time to look through the code and get a feel for how the TRAP instructions work. You will notice that the addresses near x25 contain the address of the code that executes the corresponding TRAP subroutine. Now it is time to take the code in geth.asm and splice it into the lc3os.asm file (copy and paste with some slight modifications to the existing lc3os.asm code). Make sure you add a link to the newly added GETH code in the TRAP table (addresses x0000- x00FF). The link in the trap table can be put at any address between x00 and xFF but overflow.asm expects it to be at location x28, so I would suggest using location x28. If you are not sure exactly how to do this look at how the existing TRAP x27 is implemented in the OS. The geth.asm code can be located at the end of the existing OS code in lc3os.asm.

Once the GETH TRAP code is added to the lc3os.asm use the assembler to assemble the modified operating system. This can be done with the command

make
If you are curious about how make assembles the code take a look inside the Makefile and compare it to a Makefile for a C project. The purpose of the new GETH TRAP subroutine is to read hexadecimal input from the user and pack the corresponding bits into 16-bit LC3 words. R0 is used to tell the service routine the starting address in memory to store the binary version of the entered Hex characters. The TRAP subroutine will keep processing hex characters in multiples of four characters until the q character is entered and signals the end of input in the buffer by appending a NULL word. Currently only 0-9 and uppercase A-F are accepted. For example, if the following sequence of hex is entered 1234FFFFq; the memory location contained in R0 will contain 0001 0010 0011 0100 and the next memory location will contain 1111 1111 1111 1111

Executing the buffer overflow

Now it’s time to look at overflow.asm. By convention we have been using x3000 for a starting address for our programs and x4000 as the starting address of the stack. For this program I have changes the stack to start at x3040 so it is easy to keep track of it's state.

The basic idea of overflow.asm is the Main function calls ProcessHexData which allocates a buffer on the stack, then calls the GETH TRAP to fill the buffer. If the user enters and amount of data equal to or less than the buffer size everything works normally and the function PrivateFunction will never be called. However, there are no size checks associated with the buffer that GETH receives and so a clever user can exploit this to access PrivateFunction. To successfully call PrivateFunction you will need to keep passing GETH Hex values until GETH overwrites what part of ProcessHexData's stack frame? Keep in mind that some of the passed in Hex will be filler and some will need to be specially crafted to cause the RET at the end of the ProcessHexData function to jump to PrivateFunction instead of back to Main. When running the simulator make sure you use ./lc3sim or ./lc3sim-tk to specify you want the local version of the simulator. This is necessary because the standard lc3sim will use the unmodified version of the lc3os which does not have TRAP GETH. You can enter the Hex in the terminal of the graphical version of the simulator, or you may want to try entering the Hex into the file privateFun then passing privateFun to the command line lc3sim with the following command:

./lc3sim -s runScript < privateFun
this will be especially helpful for the next part which will require more Hex. I would suggest putting a breakpoint after the TRAP x28 (GETH) instruction then stepping though the next instructions and if you have crafted the right Hex input the POP R7 instruction should load the address of PrivateFunction into R7. The Checkin server will use the original overflow.asm so do not modify it.

Try a variation for fun

Once you have figured out how to call PrivateFunction using the buffer overflow technique, you can experiment by calling other OS functions/subroutines, and modifying the code to cause overflows of buffers in other locations besides the stack.21e

Extra Credit / the best part

This one is a bit more work, but results in a lot of (unlimited) flexibility in terms of what you can make the LC3 do. By modifying the current function's return address on the stack, you can get the PC to go anywhere you want it to. If you set the return address to a function that you write using the buffer overflow, then you can execute any code you want. However, first you would need to convert each instruction to its equivalent hex form, and then use this as input to GETH. Use the file wholeFun to hold this hex input. When used as input this hex file should set R4 to x0F0F and then print the SecretMessage string and a newline then halt. Doing this part should really bring everything we have learned about the LC3 together and potentially get you excited about the power of understanding assembly language and the binary representation of instructions. For this part I jumped between the command line and GUI sim as well as modified the runScript to make testing my input easier. Keep in mind that Checkin will use the provided runScript and overflow.asm with no modifications. For fun: What is the minimum number of hex characters that must be used to accomplish this?

What to turn in

For this recitation you will get points for correctly adding GETH to the lc3os.asm and filling the file privateFun with hex that when used as input to the GETH routine will cause the PrivateFunction in overflow.asm to be called. For extra credit the file wholeFun should contain hex that when used as input to GETH will set R4 to x0F0F then print the SecretMessage string, then print a newline and finally HALT. Once you are ready to turn in your code to Checkin type
make package
this will generate a tar file which you will submit to Checkin called of.tar.