CS 485-006, Spring 2016
Midterm Exam Review

The midterm exam for CS 485G will be held in class on Friday, 4 March, 2016. The exam will be closed-note, closed-book.

There will be a mix of multiple-choice, fill-in-the-blank, short-answer (one or two sentences), long-answer (a paragraph or two), and code-writing questions (C or C++ and assembly).

Topics

Study questions

The following questions and problems are representative of those that might appear on the exam. The actual exam will be nowhere near this long, of course.

We will not be posting solutions to these problems. If you would like to verify your answers, send them to Dr. Moore by email.

All questions assume we are talking Linux running on the x86-64 architecture.

    1. Convert hexadecimal 0x2b to decimal.
    2. Convert decimal 485 to binary.
    3. Convert binary 0b1001011010110011 to hexadecimal.
  1. Is x86-64 big-endian or little-endian? Show how the 32-bit number 0x40046f is represented as a sequence of bytes (you can leave the bytes in hexadecimal).
  2. What is the value of the largest unsigned integer, if interpreted instead as a signed integer?
  3. Represent the number -12 as an 8-bit two's-complement number.
  4. What is the signed decimal value of the 8-bit two's-complement number 0b10011100?
  5. Find the value of:
    1. 0x42 | 0x2a
    2. 0x42 & 0x2a
    3. 0x42 ^ 0x2a
    4. 7 << 3
    5. -5 >> 1
  6. Name a C integer type that has the same size as a pointer.
  7. What C integer type is guaranteed to be able to hold any valid array index (on every architecture, not just x86-64)?
  8. How many bytes are required to hold an array of five ints?
  9. What is the meaning of the value stored in the %rip register?
  10. Which of the following are illegal instructions? Select all the correct answers.
    1. movq (%rsp), %rdi
    2. movq %rbx, %rbp
    3. movq (%rdi), (%rsi,%rdx,4)
    4. movl $1, %edx
    5. movq %r10, 44(,%r10,2)
    6. movq %r16, %rax
    7. movq %rbp, (%rdx,%rcx,6)
  11. If %rdi = 5000 and %rsi = 100, what is the (decimal) address computed by each of the following operands?
    1. (%rdi)
    2. (%rdi,%rsi,4)
    3. (%rsi,%rdi,4)
    4. (%rdi,%rsi)
    5. 12(%rdi)
    6. 12(,%rsi,2)
    7. 12(%rdi,%rsi,8)
  12. What is the difference between the sar and shr instructions? Give an example where they compute different answers, and show the result of each (decimal, binary, or hexadecimal is fine).
  13. Write a single instruction to compute the value of %rdi - %rax. Where does the instruction store its result?
  14. Write a single assembly instruction that computes a*2 + b, if a is in register %rax and b in %rbx.
  15. Write a single leaq instruction that computes a*5, if a is in register %rax.
  16. What is the value of %rax after the following code executes?
          movl $1, %eax
          movl $3, %ebx
          leaq (%rax, %rbx, 2), %rcx
          shl  %rax, 4
          subq %rcx, %rax
  17. What are the values of the flags CF, ZF, SF, and OF after executing each of the following instructions? Assume that, before executing each instruction, %rax contains the value 10 and %rbx contains the value -10.
    1. add %rax, %rax
    2. add %rbx, %rbx
    3. add %rax, %rbx
    4. sub %rax, %rax
  18. What is the difference between the instructions subq and cmpq?
  19. What is the difference between the instructions testq and cmpq?
  20. Suppose %rax contains the value 10 and %rdx contains the value -2. After executing the instruction cmp %rax, %rdx, which of the following instructions will jump?
  21. Translate the following C code into assembly. Assume that a and b are of type long and are stored in %rax and %rbx, respectively.
          if (a > b)
              a = b;
  22. Translate the following C code into assembly. Assume that a and b are of type size_t and are stored in %rax and %rbx, respectively.
          if (a < b)
              b -= a;
          else
              a -= b;
  23. What are the values of %rax and %rbx after the following code executes?
          movl $10, %eax
          movl $5,  %ebx
          cmpq %rax, %rbx
          jge L2
          subq $1, %rax
      L2:
          subq $1, %rbx
  24. Rewrite the following fragments of C code to use goto rather than the high-level loop constructs. Write your answers in C, not assembly.
    1.         do {
                  sum += x;
                  x *= 2;
              } while (x < 64);
    2.         while (x) {
                  sum += x->data;
                  x = x->next;
              }
    3.         for (i = 0; i < size; i++) {
                  a[i] = 0;
              }
  25. Translate the following fragments of C code into assembly. Assume that a and b are of type long and are stored in %rax and %rbx, respectively.
    1.         do {
                  a += b;
                  b += 4;
              } while (b < 10);
    2.         while (a) {
                  b++;
                  a /= 2;
              }
  26. Translate the following fragments assembly code into C. Use the variable names rax, rbx, etc. in your code to represent the registers.
    1.   L1: addq %rbx, %rcx
            addq $1, %rbx
            cmp %rax, %rbx
            jl L1
    2.       jmp L2
        L1: addq %rbx, %rcx
            addq $1, %rbx
        L2: cmp %rax, %rbx
            jl L1
    3.       cmp %rax, %rbx
            jg L2
        L1: addq %rbx, %rcx
            addq $1, %rbx
            cmp %rax, %rbx
            jl L1
        L2:
  27. The callq instruction does two separate things. What are they?
  28. When a function is called, what is stored at the address pointed to by %rsp?
  29. Suppose we have the function: long myfunc(long x, long y, long z), and that we have three long variables a, b, and c, stored in %rax, %rbx, and %rcx, respectively. Write assembly code to call myfunc(a, b, c)
  30. If a function modifies the contents of %rbp, what should be the first instruction executed by that function? What should be the last instruction before ret?
  31. Suppose you are writing an assembly function with no parameters that does not call any other functions. You need to use a register to store a local variable. All else being equal, should you prefer to use %rax or %rbx? Why?
  32. List all the callee-saved registers. In what situations is it preferable to use a callee-saved register rather than a caller-saved register?
  33. Why is %rax caller-saved rather than callee-saved?
  34. Suppose %rsp has the value 5000 and %rbp has the value 100. When the instruction pushq %rbp is executed:
    1. What is the new value of %rsp?
    2. At what memory address is the value 100 stored?
  35. Suppose we have the variable d in register %rdx. We want to call func1(d) then func2(d). Why does the following code not work?
          movq %rdx, %rdi
          callq func1
          movq %rdx, %rdi
          callq func2
    Write a corrected version of the code.
  36. Which registers are used for passing arguments to a function? If a function call has more arguments than the number of argument registers, where are the other arguments stored?
  37. Write a complete implementation in assembly of the following C function:
          long calc(long x, long y)
          {
              long result = (x + y) / 2;
              return result;
          }
  38. Suppose the array variable int a[6] = { 0, 10, 20, 30, 40, 50 } is stored at address 4000. What is the type and value of each of the following C expressions?
    1. a[1]
    2. &a[1]
    3. a + 3
    4. a[0] + 3
    5. a[6]
    6. &a[6]
  39. Suppose the array variable long a[10]; is stored at address 4000, and that the variable i is stored in register %rsi. Write an assembler instruction to load the value of a[i] into the register %rdx.
  40. Suppose that %rdi holds a pointer p to an array of longs, and that %rsi stores the variable i. Write an assembler instruction to load the value of p[i] into the register %rdx.
  41. Suppose we have a nested array int a[3][5] stored at address 1000. What is the address of:
    1. a[0]
    2. a[0][0]
    3. a[1]
    4. a[1][0]
    5. a[1][1]
    6. a[2][4]
  42. Suppose we have a nested array int a[10][8] stored at address 1000, and two variables i and j stored in %rax and %rdx, respectively. Write an assembly instruction to add 1 to the value of a[i][j].
  43. List at least one advantage and one disadvantage of multi-level arrays (arrays of pointers to arrays) compared to nested (multidimensional) arrays.
  44. Suppose we have a nested array int *a[3] stored at address 1000, and two variables i and j stored in %rax and %rdx, respectively. Write a sequence of assembly instructions to add 1 to the value of a[i][j].
  45. Consider the data structure:
          struct data {
              char array[5];
              int number;
              size_t size;
          };
    1. What are the alignment requirements for each of the three members?
    2. What is the alignment requirement for the struct as a whole?
    3. What is sizeof(struct data)?
    4. If struct data d is stored at address 4000, what is the address of d.number? Of d.size?
    5. If %rbx stores a pointer struct data *p, write an assembly instruction to load p->size into register %rdx.
  46. Consider the data structure:
          struct too_big {
              char x;
              long y;
              char z;
          };
    1. What is the value of sizeof(struct too_big)?
    2. Write C code to define a structure just_right that contains the same data members as too_big, but that requires less space. What is sizeof(struct just_right)?
  47. In what region of memory (text, data, heap, stack) is each of the following stored?
    1. A global variable.
    2. A local variable.
    3. The machine code for main.
    4. An array allocated with malloc.
    5. An array defined as int a[4]; inside a function.
  48. Which region of memory is located at the very top of the program's address space?
  49. How can the gets() function be used safely with no risk of buffer overflows?
  50. Consider the following assembly code:
    badfunc:
          subq $8, %rsp
          movq %rsp, %rdi
          callq gets
          addq $8, %rsp
          ret
    1. What is the maximum amount of user input that will allow this function to execute without problems?
    2. If the user provides a few more bytes of input than that, which instruction is likely to crash?
    3. If another function evil is at address 0x00414243, what input could the user provide to this gets call to cause evil to be executed?
      Hint: 0x41 is the ASCII code for "A".
  51. What two techniques does the x86-64 architecture use by default to mitigate against buffer overflow attacks? How can an attack still be carried out despite these techniques?
  52. What technique does gcc -fstack-protector use to mitigate against buffer overflow attacks?
  53. Describe how stack canaries work.
  54. List at least two significant current or historical buffer overflow attacks.
  55. What have buffer overflow attacks been used for, other than gaining unauthorized access to other peoples' computers? List at least one real-world example.
  56. List the gcc command-line options for each of the following:
    1. Generate a .o file rather than an executable.
    2. Generate a .s (assembly code) file rather than an executable.
    3. Enable the highest level of optimization.
    4. Enable optimizations that do not make debugging more difficult.
    5. Include debugging information in the executable file.
  57. Give the gdb command to do each of the following:
    1. Set a breakpoint at the beginning of main.
    2. Set a breakpoint at line 150 of prog.c.
    3. Set a breakpoint at address 0x4005fc.
    4. Print the value of %rax.
    5. Print the value of %rax in hexadecimal.
    6. Print the 64-bit value stored at the top of the stack.
    7. Print the C string pointed to by %rdi.
    8. Print the address of the next instruction to be executed.
    9. Print the next instruction to be executed.
    10. List the assembly code for the entire current function.
    11. See the list of stack frames, including the current function, its caller, its caller's caller, etc.
  58. What is the difference between the print and display commands in gdb?
  59. What is the difference between the nexti and stepi commands in gdb?
  60. What is gprof used for? How does one compile a program so that it can be used with gprof?
  61. List at least two different kinds of problems that valgrind can help detect.
  62. Without running gdb, how can you list the assembly code for an executable program?