Lab 4: Assembly

Lab sessions Wed Jul 24 to Sat Jul 27

Lab written by Julie Zelenski, with modifications by Nick Troccoli

Learning Goals

This lab is designed to give you a chance to:

  1. study the relationship between C source and its assembly translation
  2. use objdump and gdb to disassemble and trace assembly code

Get Started

Clone the lab starter code by using the command below.

git clone /afs/ir/class/cs107/repos/lab4/shared lab4

Next, pull up the online lab checkoff and have it open in a browser so you can jot things down as you go. Only one checkoff needs to submitted for both you and your partner.

Keep our x86-64 reference sheet handy while you work!

Open x86-64 Reference Sheet

Introduction: New GDB Commands

objdump -d extracts assembly instructions from an executable (called deadlisting - "dead" to distinguish from the study of "live" assembly as it executes). You can also examine a program's assembly representation using GDB, as it runs. First, read about some new GDB commands below. You'll try them out in this lab.

  • disassemble prints the assembly instructions for the currently executing function. Optionally specify the name of a function or an address to disassemble that instead (e.g. disassemble myfn). The leftmost column is the instruction's memory address, and the angle brackets number is the number of bytes that instruction is from the start of the function.
(gdb) disass myfn
Dump of assembler code for function myfn:
   0x000000000040051b <+0>: movl   $0x1,-0x20(%rsp)
   0x0000000000400523 <+8>: movl   $0x2,-0x1c(%rsp)
...
  • b *[ADDRESS] lets you set a breakpoint at a specific assembly instruction (e.g. b *0x400570) or function offset (e.g. b *myfn+8). Offsets are in bytes. Make sure you use the * here - otherwise GDB will misinterpret the address as a function name!
(gdb) b *0x400570      break at specified address
(gdb) b *myfn+8        break at instruction 8 bytes into myfn()
  • stepi and nexti are the assembly versions of step and next. stepi executes the next single assembly instruction, and nexti executes the next single instruction, stepping over function calls like next does.
  • info reg prints out the values in all integer registers.
  • print $[REGISTER] prints a register's contents. Eg. print $rax (note $ instead of %).
  • set $[REGISTER] = VALUE sets a register's contents. E.g. set $rax = 9 (note $ instead of %). Useful for testing hypotheses about program behavior!
  • layout split enters "Text user interface" (TUI) mode with a split code/assembly view for easier viewing. The gdb command layout <argument> starts tui mode. The argument specifies which pane you want (src, asm, regs, split or next). While it can be useful, it can be buggy and sometimes the display gets messed up. Try refresh to fix it. ctrl-x a will exit tui mode and return you to ordinary non-graphical gdb.
  • x ("examine") prints out bytes in memory starting at the specified address. (full documentation here). E.g. to print the 8 hex bytes starting at the address in some pointer ptr, you could do x/8bx ptr. You can specify optional print settings after the slash. 8 is where you specify the number of bytes to print. b is where you specify the unit size (b is bytes, w is words, for instance). x is where you specify the print format (e.g. x for hex, d for decimal).

1) Assembly and GDB

15 minutes + 10min discussion

Learning Goals: Become familiar with new GDB commands to navigate the assembly representation of a program. Stepping through a program in GDB and examining it at the assembly level is key to "reverse engineering" an executable to understand its behavior, which you will be doing on assign5.

Starter code file: code.c

Let's try out all these new gdb commands! Remember that all literal values in assembly on myth are in hexadecimal! This is a common gotcha when reading assembly code. (Compiler Explorer, later in the lab, may convert to decimal, though).

First, read over the program code.c. Then compile the program and load it into gdb. Disassemble myfn. Assume that %rsp is a pointer to the current top of the stack. (we'll learn more about %rsp later).

Q1: What expression (e.g. something in a format like %rdx + 0x5), represents the location of the first element in arr? The last?

Q2: What register stores the value of total, and also squared? (registers can be reused for multiple variables!)

Note that despite us calling strlen and sizeof in the code, these are not present in the assembly. sizeof is evaluated at compile time (the compiler outputs the result), not runtime here. Similarly, the compiler was able to optimize out the call to strlen entirely - it can calculate the length of a literal itself!

2) C to Assembly Translation

(40 minutes + 10min discussion, with 5min check-in discussion in the middle)

Learning Goals: Get more practice connecting assembly back to the C source that it might represent. Understand how different C constructs and operations are represented in assembly. This is critical for "reverse engineering", where you must uncover the behavior of a program without access to its source code, which you will be doing on assign5.

To study C->assembly translation, we recommend you try out Compiler Explorer, a nifty online tool that provides an "interactive compiler". It shows live-updating assembly for code you enter. Each C line is color-coded to match with its corresponding assembly line(s) on the right. We provide Compiler Explorer links in this lab for each exercise; they are pre-configured for myth's version of GCC and compiler flags from the CS107 makefiles. (To manually configure yourself: select language C, compiler version x86-64 gcc 9.3 and enter flags -Og -std=gnu99).

Dereferencing Modes

Open Compiler Explorer

Review the two deref functions below and their generated assembly.

void deref_one(char *ptr, long index) {
    *ptr = '\0';
    ptr[index] = '\0';
}

void deref_two(int *ptr, long index) {
    *ptr = 0;
    ptr[index] = 0;
}

Q3: There are subtle differences between the assembly generated for each function. What are they, and why are they different?

Q4: Edit both functions' second lines to replace ptr[index] with ptr[7]. How does this change the addressing mode using for the destination operand of the mov instruction? Do both deref functions change in the same way?

Signed/Unsigned Arithmetic

Open Compiler Explorer

The add, subl and imul instructions perform addition, subtraction and multiplication, respectively. Here is the format for these instructions:

add src, dst       # dst += src
sub src, dst       # dst -= src
imul src, dst      # dst *= src

The following two functions perform the same arithmetic operation on their arguments, but those arguments differ in type (signedness).

int signed_arithmetic(int a, int b) {
    return (a - b) * a;
}

unsigned int unsigned_arithmetic(unsigned int a, unsigned int b) {
    return (a - b) * a;
}

Notice how both functions generate the same sequence of assembly instructions! The choice of two's complement representation allows the add/sub/imul instruction to work for both unsigned and signed types. Neat!

Edit both functions to add the following line at the start: a >>= b;. This performs a right shift on one of its arguments.

Q5: When doing a right-shift, does gcc emit an arithmetic (sar) or logical (shr) shift? Does it matter whether the argument is signed or unsigned?

For the shift instructions, the shift amount can be either an immediate value, or the byte register %cl (and only that register!). However, the instruction interprets the contents of the %cl register in a slightly interesting way. Check out the lecture slides on the shift instruction for a refresher. Then, take a look back at the assembly code you have been working with so far, particularly the a >>= b lines. Notice how it uses the %cl register for shifting.

Q6: What is the largest shift amount that could be specified using the %cl register for an unsigned int? Why might this limit make sense?

Take a break here and reconvene with the rest of your lab! Your lab leader will pull everyone back together for a short 5 minute discussion about how things are going so far. Then you can get back with your group to review and complete the last questions for an additional 20 minutes.

lea and Multiplication

Multiply is one of the more expensive instructions and the compiler prefers cheaper alternatives where possible. One such alternative is the lea instruction, which is meant to help do calculations with memory addresses, but it also has helpful uses for general arithmetic. It packs a lot of computation in one instruction: two adds and a multiply by constant 1, 2, 4 or 8, and is often used by compiler to do an efficient add/multiply combo. Let's explore multiplication operations, lea, and what the compiler might choose to output.

Open Compiler Explorer

Review the four functions below that do various arithmetic operations, and their generated assembly.

int combine(int x, int y) {
    return x + y;
}

int combine2(int x, int y) {
    return x + 2 * y;
}

int combine3(int x, int y) {
    return x * 17;
}

int combine4(int x, int y) {
    return x * 47;
}

Q7: In combine1 and combine2, the compiler doesn't use add or multiply. How does it use lea instead?

Q8: combine3 no longer fits the limited form of lea, but the compiler still avoids multiply. What does it use instead?

Finally, combine4 uses a multiply instruction, as the compiler is unable to represent it in a form using other instructions such as lea.

Division

This avoidance also applies to division, as it is tedious for modern CPUs. (reminder: the terminology is DIVIDEND / DIVISOR = QUOTIENT). However, there is an additional twist with division; whereas addition, subtraction, and multiplication operate equivalently on signed and unsigned integers, it's not quite so with division, due to integer division rules. In particular, we expect the quotient to be rounded toward zero, which means the behavior changes for signed vs. unsigned. This is something the compiler must consider when it replaces a division instruction with a less-expensive alternative. Here's an example of what we expect when doing integer division:

3 / 2 = 1
-3 / 2 = -1

In the first (unsigned) example, notice how an odd divident divided by 2 is rounded down to 1 (discards remainder). The compiler will usually do this by shifting away the least-significant bit. E.g. 0b11 / 2 = 0b1. However, this rule does not work for signed numbers; in the second (signed) example, notice how the quotient (-1.5) is rounded up to -1! If we try the same shift technique, we have 0b1...1101 / 2 = 0b1....1110 = -2! The right shift (discard lsb) will round a positive value toward zero and rounds a negative value away from zero. This difference in rounding is the crux of why right-shift alone is insufficient if the result is negative.

The compiler therefore compensates for this by "fixing up" the value before dividing. In other words, it changes the dividend (-3 here) such that when it does do the shift, it gets the correct answer. For -3, it would add 1, so that it calculates -2 / 2 = -1. This pushes the dividend to the next larger multiple of the divisor so as to get the proper rounding for a negative quotient.

The necessary fixup amount when dividing by 2 is 1, the fixup for dividing by 4 is 3, for 8 it is 7 and so on. This calculation should be reminiscent of the roundup function we studied way back in lab1!

Open Compiler Explorer

Let's see examples of how the compiler approaches signed and unsigned division. (Note: a shift instruction without a shift amount shifts by 1 place).

unsigned int unsigned_division2(unsigned int x) {
    return x / 2;
}

int signed_division2(int x) {
        return x / 2;
}

unsigned int unsigned_division4(unsigned int x) {
    return x / 4;
}

int signed_division4(int x) {
        return x / 4;
}

In the 2 unsigned division examples, notice how the compiler outputs a right shift.

signed_division2 adds additional instructions. First, trace through the assembly to convince yourself that the behavior is the same if the dividend is positive.

Q9: what does the assembly do to account for a fixup of 1 if the dividend is negative?

signed_division4 does something similar, but uses instructions we haven't seen before called test and cmov ("conditional move"). All you need to know for now is these instructions express the logic "if %edi is non-negative, move %edi into %eax". The assembly calculates the fixup, but then undoes it if the value is nonnegative.

Optional: further explorations: Division by powers of two get special treatment, sure, but what about constants that are not powers of two?

Open Compiler Explorer

unsigned int unsigned_div10(unsigned int x) {
    return x / 10;
}

Look at the C source and generated assembly for this function. The assembly still doesn't use a div instruction, by there is a multiply by a bizarre number: -858993459 (in hex 0xcccccccd). What sorcery is this? This mysterious transformation is effectively multiplying by 1/10 as a substitute for divide by 10. The 1/10 value is being represented as a "fixed point fraction" which is constructed similarly to the way floats are. Enter 0.1 into this float visualizer tool and look to see where that same funny 0xcccccccd number shows up in the significand bits of the float. This technique is known as reciprocal multiplication and gcc will generally convert division by a constant in this way. The math behind this is somewhat complex, but if you'd like to know more, check out Doug Jones' tutorial on reciprocal multiplication.

Recap

Nice work on the lab! It's okay if you don't completely finish all of the exercises during lab; your sincere participation for the full lab period is sufficient for credit. However, we highly encourage you to finish on your own whatever is need to solidify your knowledge. Also take a chance to reflect on what you got what from this lab and whether you feel ready for what comes next! The takeaways from lab5 should be understanding the relationship between C and assembly, along with tools for disassembling object files, and using the debugger at the assembly level. The hands-on practice relating C code to its compiled assembly and reverse-engineering from assembly to C is great preparation for your next assignment. Here are some questions to verify your understanding and get you thinking further about these concepts:

  • Give an example of a C sequence/expression that could be compiled into a variety of different, but equivalent, assembly instruction(s).
  • What is the difference between sar and shr?
  • How is the return value of a function communicated from the callee to the caller?
  • What kind of clues might suggest that an lea instruction is doing an address calculation versus when it is merely arithmetic?