Stepping Schedules

If you had not noticed before, the subtitle of the Threads window gives the current snapshot number. If you have stepped in the emulator, it will also contain the sequence of steps emulated. Recall the time element of the Debugger’s coordinates. (See the Navigation module if you need a refresher.) The time element, called the schedule, consists of both the current snapshot and the sequence of steps to emulate. The subtitle displays that schedule. If you have done any patching of the emulator’s state, you may notice some more complicated “steps” in the schedule. The syntax is:

• Schedule → Snapshot [ : [ Step ( ; Step ) * ] [ . Step ( ; Step ) * ] ]
• Step → [ t Id - ] ( Tick | Skip | Patch )
• Tick → Count
• Skip → s Count
• Patch → { SleighStmt }

In essence, the schedule is the starting snapshot, followed by zero or more machine-instruction steps followed by zero or more p-code-operation steps. Each step is optionally preceded by a thread id. If omitted, the thread id is the same as the previous step. If the first step has no thread id, it applies to the snapshot’s event thread. A plain number indicates the number of instructions or operations to execute. An s prefix indicates skip instead of execute. Curly braces specify a patch using a single Sleigh statement. Here are some examples:

• 0 — The first snapshot in the trace.
• 3 — Snapshot number 3.
• 3:10 — Emulate 10 machine instructions on the event thread, starting at snapshot 3.
• 3:t1-10 — Same as above, but on the second thread rather than the event thread.
• 3:10;t1-10 — Start at snapshot 3. Step the event thread 10 instructions. Step the second thread 10 instructions.
• 3:10.4 — Start at snapshot 3. Step the event thread 10 instructions then 4 p-code ops.
• 3:{RAX=0x1234};10 — Start at snapshot 3. Override RAX with 0x1234, then step 10 instructions.

The explication of schedules allows Ghidra to cache emulated machine states and manage its emulators internally. You can have Ghidra recall or generate the machine state for any schedule by pressing CTRL-G or using Debugger → Go To Time in the menus.

Assuming you got the program counter onto exit(-1) earlier:

1. Write down the current schedule.
2. Change back to Control Target mode. Ghidra will navigate back to the current snapshot, so PC will match the live target.
3. Change back (again) to Control Emulator mode.
4. Press CTRL-G and type or paste the schedule in, and click OK. The program counter should be restored to exit(-1).

NOTE: The thread IDs used in schedules are internal to the current trace database. Most likely, they do not correspond to the thread IDs assigned by the back-end debugger.

Exercise: Demonstrate the Cell Numbers

The board setup routine in termmines first places mines randomly and then, for each empty cell, counts the number of neighboring cells with mines. In this exercise, you will use extrapolation to experiment and devise a patch to demonstrate all possible counts of neighboring mines:

1. Launch termmines using GDB with Inferior TTY enabled.
2. Use a breakpoint to trap it at the point where it has placed mines, but before it has counted the neighboring cells with mines. (Use SHIFT-R in termmines to reset the game.)
3. Use the emulator to extrapolate forward and begin understanding how the algorithm works.
4. Move the mines by patching the board to demonstrate every number of neighboring mines. That is, when the board is revealed at the end of the game, all the numbers 1 through 8 should appear somewhere.
5. Use extrapolation to debug and test your patch.
6. Once you have devised your patch, apply it to the live target. (Copy-Paste is probably the easiest way to transfer the state from emulator to target.)

Initializing Other State

We had just started executing the target function arbitrarily. Ghidra takes care of a minimal bit of initialization of the trace to start emulation. Namely, it maps the image to its preferred base. It allocates space for the main thread’s stack and initializes the stack pointer. Finally, it initializes the program counter.

It is still up to you to initialize any other state, especially the function’s parameters. Clearly, we will need to initialize param_1. We may need to do a little static analysis around the call to this function to understand what those parameters are, but you could probably make an educated guess: param_1 is argc and param_2 is argv. We might as well initialize both. Luckily, we have plenty of memory, and given the small scope of emulation, we can probably place the strings for argv wherever we would like.

You may prefer to apply patches to the trace database or to the emulator. The advantage to patching in the emulator is that once you have completed your experiments, you can readily see all of the steps that got you to the current machine state, including all patches. The disadvantage is that if you have extensive patches, they will pollute the stepping schedule, and things can get unwieldy.

Alternatively, you can perform the patches in the trace. When you launched the emulated target, all Ghidra really did was initialize a trace database. The advantage to patching the trace is that once you have completed your experiments, you will have your initial state captured in a trace snapshot. The disadvantage is that you will need to remember to invalidate the emulator cache any time you change the initial state. For this tutorial, we will perform the patches in the emulator.

NOTE: If you wish to try patching the trace, then change to Control Trace mode and use the Navigate backward one snapshot control action that appears, so that you are patching the initial state, and not a scratch snapshot. Scratch snapshots are ephemeral snapshots in the trace used to display emulated state. Changes to these snapshots will affect the display, but will not affect subsequent emulation. If your current schedule includes any steps, then Control Trace is patching a scratch snapshot.

Now, we will manually “allocate” memory for argv. Luckily, Ghidra allocated 16K of stack space for us! The target function should not need a full 16K, so we will allocate the lowest addresses of the stack region for our command-line arguments. If you prefer, you may use the Add Region action in the Regions window to manually fabricate a heap region, instead. In the Regions window, filter for “stack” and take note of the start address, e.g., 00001000. We will use the Watches window to perform our patching, though we will also use the Dynamic Listing to double check. Add the following watches:

• RSP — to confirm the stack pointer is far from argv.
• RDI — the location of param_1, i.e., argc.
• RSI — the location of param_2, i.e., argv.

To start, we will just try to return successfully from the parser. From the behavior we have observed, it requires at least argv[0] to be present. Conventionally, this is the name of the binary as it was invoked from the shell, i.e., termmines. There are few reasons a UNIX program might want to examine this “argument.” First, if the binary actually implements many commands, like busybox does, then that binary needs to know the actual command. Second, if the binary needs to print usage information, it may like to echo back the actual invocation. It is possible we may only need to initialize argc, since the parser may not actually use the value of argv[0].

Use the Watches window to set RDI to 1, then click Resume. Like before, the emulator will crash, but this time you should see “pc = 00000000” in red. This probably indicates success. In the Threads window, you should see a schedule similar to 0:t0-{RDI=0x1);t0-16. This tells us we first patched RDI, then emulated 16 machine instructions before crashing. When the parser function returned, it probably read a stale 0 as the return address, so we would expect a decode error at 00000000. Step backward once to confirm this hypothesis.

Stubbing External Calls

For this tutorial, we will set the skill level to Advanced by patching in actual command-line arguments. This continues our lesson in state initialization, but we may also need to stub some external calls, e.g., to strnlen and strcmp. We will need to pass in termmines -s Advanced, which is three arguments. Use CTRL-G to go back to snapshot 0, and add the following watches:

• *:8 (RSI + 0) — the address of the first argument, i.e., argv[0].
• *:30 (*:8 (RSI + 0)) with type TerminatedCString — at most 30 characters of the first argument.
• *:8 (RSI + 8) — argv[1]
• *:30 (*:8 (RSI + 8)) with type TerminatedCString — contents of argv[1]
• *:8 (RSI + 16) — argv[2]
• *:30 (*:8 (RSI + 16)) with type TerminatedCString — contents of argv[2]

This will generate an extensive list of patch steps, so you may prefer to patch the trace in this case. Set RDI to 3. Notice that argv[0] is supposedly allocated at 00000000 according to the Address column for the watch on *:8 (RSI + 0). That was determined by the value of RSI, which is essentially telling us we need to allocate argv, an array of pointers. We can confirm RSP is at the upper end of the stack region, so we allocate argv at 00001000. To do that, set the value of RSI to 0x1000. You should see the Address column update for some other watches. You can double-click any of those addresses to go there in the Dynamic Listing.

NOTE: You do not have to allocate things in a listed region, but if you want to see those things in the Dynamic Listing, it is easiest if you allocate them in a listed region.

Now, we need to allocate space for each argument’s string. To ensure we do not collide with the space we have already allocated for argv, we should place a data unit in the Dynamic listing. Double-click the Address 00001000 in the Watches window to go to that address in the Dynamic Listing. Press P then [ (left square bracket) to place a 3-pointer array at that address. We can now see the next available byte is at 00001018. NOTE: You might set the Dynamic Listing to Do Not Track, otherwise it may seek back to the PC every time you patch.

Now that we know where to put argv[0], we need to patch it to 0x0001018. This should be the watch on *:8 (RSI + 0). When you modify the Value column, you can type either bytes (in little-endian order for x86) or the integer value 0x1018. That should cause the watch on *:30 (*:8 (RSI + 0)) to get the address 00001018. Using the Repr column, set that watch’s value to "termmines". (The quotes are required.) Place a string in the Dynamic Listing using the ' (apostrophe) key. This shows us the next available address is 00001022, so repeat the process to allocate argv[1] and set it to "-s". Then finally, allocate argv[2] and set it to "Advanced". When you have finished, the Watches pane should look something like this:

The Dynamic Listing should look something like this:

NOTE: The placement of data units is not necessary for the emulator to operate; it only cares about the bytes. However, it is a useful aide in devising, understanding, and diagnosing machine state.

Now, click Resume, and see where the emulator crashes next. Depending on your compilation of termmines, it may crash after returning, or it may crash trying to call strnlen or strcmp. If the program counter is 00000000, then it returned successfully. This is unfortunate, because you no longer have motivation to stub external calls.

If the program counter is not 00000000, then step backward until you get to the CALL. There are at least three techniques for overcoming this.

1. You can skip the CALL and patch RAX accordingly.
2. You can override the CALL instruction using a Sleigh breakpoint.
3. You can override the call target using a Sleigh breakpoint.

RAX = 0;
<loop>
if (*:1 (RDI+RAX) == 0 || RAX >= RSI) goto <exit>;
RAX = RAX + 1;
goto <loop>;
<exit>
emu_skip_decoded();

RAX = 0;
<loop>
if (*:1 (RDI+RAX) == 0 || RAX >= RSI) goto <exit>;
RAX = RAX + 1;
goto <loop>;
<exit>
RIP = *:8 RSP;
RSP = RSP + 8;
return [RIP];

Wrapping Up

As you can see, depending on the scope of emulation, and the particulars of the target function, emulating a program image can be quite involved. Whatever technique you choose, once you have successfully returned from the command-line argument parser, you should check for the expected effects.

In the Static Listing, navigate to the variable that stores the board’s dimensions. (Finding that variable is a task in the Beginner portion, but it can be found pretty easily with some manual static analysis.) In the Dynamic Listing, you should notice that the values have changed to reflect the Advanced skill level.

Optional Exercise: Patch the Placement Algorithm

In this exercise, you will use emulation to devise an assembly patch to termmines to change the mine placement algorithm. Instead of random placement, please have them placed left to right, top to bottom. We recommend you devise your patch using the Assembler (Patch Instruction action) in the Static Listing, then test and debug your patch using the Emulator. Perhaps patch the Dynamic Listing to try quick tweaks before committing them to the Static Listing. Once you have it, export the patched binary and run it outside of Ghidra.