2016/Fundamentals1X

From CS61
Jump to: navigation, search

Treasure hunt

CS61 Exercises Tarball!

In the cs61-exercises/fundamentals1x directory, you’ll find a program called treasure.c.

Type cd fundamentals1x; make to build the ./treasure program.

This program is a treasure hunt! By running the program with different options, you can make it print:

  • Sixty-one
  • An expired cow
  • A precious stone
  • A golden ratio
  • An English word
  • A greeting cat
  • An infinite loop
  • A number that is not a number
  • A zero that is less than zero
  • Some nasal demons
  • A professor
  • A Shakespeare play

In fact, there are two or more substantively different ways to produce most of these results. We know of at least 24 command lines that produce treasure.

How many of them can you find?

Skills

  • Reading and understanding C code
  • Understanding data representation
  • Basic properties of C datatypes
  • Reverse-engineering inputs for C functions
  • Running shell commands
  • Researching C library functions and shell commands
  • Using gdb to explore memory

In-class work

In 45 minutes, try to find the following treasures.

  1. Find “sixty-one” using ./treasure 6. (If you run ./treasure 6 without arguments, it prints “6”. Can you find other arguments so that it prints something like “sixty-one”?)
  2. Find “sixty-one” using ./treasure 5.
  3. Find an expired cow using ./treasure 0.
  4. Find an expired cow using ./treasure 12.
  5. Find a precious stone using ./treasure 21.
  6. Find a precious stone using ./treasure 14.
  7. Find a greeting cat using ./treasure 16.
  8. Find a greeting cat using ./treasure 2.

If you have time, search for other treasures too!

How to hunt

We’ve hidden treasure in the program in many different ways. You’ll make progress by looking at the code, by reasoning through its behavior, and, importantly, by running experiments. You can even change the code to see what happens! (But your answers should work on the handout code.) Also use the Web liberally. Don’t understand a term? Search for it!

Don’t be afraid to treat the code like a scientist: run experiments! We often try to understand code by reading it, but that can be difficult, even for simple loops. If you get stuck, try instead to get a feel for a function by observing its behavior. So try running a treasure function with different arguments. What happens? Use the results to develop a hypothesis about its behavior. Then check your hypothesis against the code, and confirm or refute it by running the code with different arguments.

Having trouble getting started? Try using gdb or lldb. One useful technique: Set a breakpoint at printf and use backtrace (short version: bt) to see how printf got called. gdb treasure, then b printf, r 6 (which runs the program with the argument “6”), bt.

Mac OS X gdb may report Function "printf" not defined. This is because the dynamic library that contains printf is loaded on demand. Try running the program first with r; then you can set the breakpoint. Or use lldb.

After-class work

Try out the self-check comprehension questions and, optionally, hunt for more treasure.

Self-check comprehension questions

You may have found some treasure by guessing. Go back and try to understand why your command lines generate treasure.

You should also be able to answer these questions, or at least to figure out how they could be answered.

  • What is the hexadecimal representation of ints[0]? Of ints[1]?
  • Can you explain why ./treasure 4 6 and ./treasure 4 8 produce different results? You may need to read several manual pages, such as man system.
  • What algorithm does ./treasure 9 run? That is, can you give a concise description of the result of ./treasure 9 A B?
  • What algorithm does ./treasure 10 run? That is, can you give a concise description of the result of ./treasure 10 N?
  • Use gdb or another debugger to explore the contents of memory. Can you predict the result of ./treasure 3 1 0 16 using gdb?
  • Use objdump (on Mac with Homebrew, brew install binutils, and call it gobjdump) to explore the contents of the ./treasure executable. Can you predict the result of ./treasure 3 2 0 16 using objdump? (The -d, -S, or -s options might be useful.)

Post-Class Survey

Please complete this survey before leaving class!

In-class Exercise FAQ

Extension students: after class, we will record any common problems that stumped people during the in-class exercises and put them in a FAQ that accompanies the exercises. We recommend that you first try the exercises, and then, if you get stuck, check the FAQ.

Execise FAQ