06 May 2015

I’m currently taking a class in C with the excellent Prof. Joel Castellanos for my CS degree, and the final project was to write an AI for a game, described in the assignment slides. The short version of the game is that 1-6 players are placed in a 500x300 square grid with a small amount of randomly generated obstacles placed inside. Each turn, every player may expand to one grid square connected to any of their existing grid squares; the player with the most grid squares claimed at the end of the game is the winner. Rather than a traditional approach, I decided to see if I could creatively break the game instead of coming up with a winning strategy.

Technical Aspects of the Game

Each player in the game is run in a separate thread, and are given 5ms per round to compute their move. If they go over time, they are skipped that turn, and are given another chance to finish in the next 5ms, and so on until they return a move or the game ends. Because of the multithreading approach, I thought to try and ‘cheat’ the game by attempting to freeze or crash my opponents’ threads.

First Foray: Let’s See How Robust the Main Program Is

The rules of the game state that any player whose AI causes the main program to crash or exit unexpectedly is disqualified. I therefore expected some kind of enforcement, perhaps by creating a signal handler for SIGSEGV in each thread to notify the main program and exit if the AI crashes. To test this, I compiled a simple AI into the main program, and used gdb to pause it when my AI is first called. I then grabbed its PID from ps -a, cd‘d into the corresponding part of the /proc/ filesystem, and found the thread ID in /proc/[PID]/task/; it only had two entries - the main thread, whose TID is the same as the program’s PID, and my threads ID. A simple kill -SIGSEGV [TID] tested the response to the ‘crash’, and lo and behold, the whole program crashed. No signal handler. Darn.

A Side Note on Linux Thread ID’s

Before moving on to other methods of breaking threads, I decided to try and figure out how to determine my AI’s thread ID at runtime. A little Googling revealed that there is in fact a Linux syscall for this, gettid(), which for some reason lacks a glibc wrapper. Unfortunately, the opaque thread pointers returned by pthread_self and friends cannot be converted to or from Linux TID’s, which will be important later.

Second Try: SIGSTOP and SIGKILL

Looking through the process signal list (kill -l) revealed the existence of SIGSTOP and SIGKILL. SIGKILL just kills the whole program, even when sent to a specific thread. No dice. SIGSTOP on the other hand, does work on specific threads… if you’re running Linux < 2.26 or so; this behavior is apparently a bug, as POSIX dictates that SIGSTOP applies only to whole processes. This was fixed, so no easy freezing for me.

Third Time’s The Charm: pthread Methods

Well the main program uses pthreads, so let’s see what’s available in that library. I see three possibilities:

  • pthread_cancel: This is actually a voluntary thing - it just sends a signal and the thread being cancelled has to manually check for and respond to it.
  • pthread_destroy: This would actually work, except that it may cause weird behavior when the program tries to do anything else with the thread I’ve just killed.
  • pthread_suspend: This would work perfectly, except that Linux doesn’t implement it. Grr.

Also, there’s no way to get a handle to a pthread, you have to get it direct from the return value of pthread_create. You also can’t convert Linux TID’s to pthread handles. Once again, not useful.

Last, and certainly not least: ptrace!

The last thing I tried was ptrace, the Linux debugger interface. It includes PTRACE_SUSPEND, which is exactly what I want! It even works on [P|T]ID’s rather than thread handles, which is perfect for me. I tried a simple example, running PTRACE_ATTACH and then PTRACE_SUSPEND after manually determining which TID belonged to my opponent. Unfortunately, ptrace only works on threads that have already called PTRACE_TRACEME (or if you’re root), which means that I have to fork() the whole main program and trace it that way. It doesn’t work due to complications involving multithreading and graphics.

Conclusion

Well, I learned a lot about Linux internals, and how security is handled. Unfortunately, I won’t be winning any competitions with my non-working cheaty code. Oh well.


Categories

Tags