This page is kept for historical purposes only. Please see the home page for my current situation. —Luca Saiu.

DLL: TP 3 - Reverse-engineering Pong

Today's task is more advanced than the previous exercises, and more realistic; it is still simplified compared to a real situation, but this one doesn't just consist in writing some short functions.

Before doing this you need to be good with Scheme, and with Unix.

If you have not finished the second TP then I suggest to complete it before starting this. I prefer not to speak about advanced Scheme features until I'm sure that most people have understood the content of the second TP.

When you work at the Institut Galilée labs, before starting, you have to execute the following line on every terminal you use:

source ~10706282/add-prefix ~10706282/usr

That is for using the software I have installed in my home directory on the machines at Institut Galilée; I don't have administrator privileges on the lab machines, so I have installed everything in my home directory.

Of course you don't need to do anything similar at home if you have installed everything correctly, because you are the administrator of your own machines.

You can find some practical suggestions at the bottom of the first TP page.

Task -1: Subscribe to the mailing list

I've seen that many people didn't subscribe to the mailing list yet, so chances are that you didn't either; please do it now.
A student noticed that the page may ask you to accept certificates. Don't worry, the server is at LIPN, Université Paris 13; it's perfectly safe.

Task 0: Uncompress, configure and compile guile-game

guile-game is Guile extended with some functionality added by me by calling the SDL and SDL_ttf libraries in order to support graphics, keyboard and mouse events.
You will also use (possibly a newer version of) guile-game for the final project, which is not specified yet.

As usual if you are at the Institut Galilée labs, you have to execute the red line above on each terminal before you start.

Enter the directory within your home where you want to work with guile-game.

Download, uncompress, configure and compile guile-game:

unset http_proxy
wget www-lipn.univ-paris13.fr/~saiu/teaching/DLL-2010/big-project/guile-game/guile-game-0.0.5.tar.gz
tar xfv guile-game-0.0.5.tar.gz
cd guile-game-0.0.5
./configure
make

You shouldn't see any error message; if everything works you will see the executable files guile-game (it's Guile extended with graphic primitives and event support), server, client and monitor.

There are several test programs, including some relatively complex ones such as last year's big project demo:

./guile-game scm/demos/line-demo.scm
./guile-game scm/big-project-demo-2009/big-project-demo-standalone.scm

And of course there is the Pong application, which is most important for you today. You can run it with two players by entering all on the same line:

./server ./client ./client ./monitor

Don't be afraid of reading the source code when it's needed, or when you're simply curious.

Task 1: Understand association lists

Read about association lists in the Guile manual. Learn the predefined functions for working on association lists; you will need them for the next task.

Task 2: Reverse-engineer `client` and implement a similar program

The three files server, client and monitor are proprietary (for didactic reasons only; I'm gonna publish the complete sources at the end of the course); you have already compiled them from C files, but those C files are not the source code as defined, for example, by the GNU GPL; look at the files src/*proprietary.[ch] . Really: open a couple of them with your text editor and have a look.

client (and also monitor, which is another sort of client) communicates via its standard input and standard output: it receives information about the current state in its standard input, decides what move to perform, and emits the move to perform on its standard input. Each message, both input and output, is exactly one (not zero or more than one) Scheme s-expression. Of course pong doesn't require much intelligence to play: the problem is communicating with the right format. Realistic servers and clients would run across the network, on sockets. The clients of this application instead use their standard input and standard output, so that you can reverse-engineer protocols without using network sniffers or more complex software.
The server communicates with clients via pipes, but this isn't interesting for you if you're not developing the server

Read the README file to understand how to run the proprietary Pong application. Your task is implementing a program similar to client, which can interact with the proprietary server, in Scheme. You can observe the behavior of the proprietary version, but you can't directly access the source.
After you have understood the protocol, the implementation will be easy: my solution in Scheme is less than 70 lines.

Call me if you succeed in implementing a program similar to client.

Hints:

Before implementing your program similar to client you must understand the protocol: implement a wrapper that executes the proprietary client, logging its input and output on a file; by reading the log you will easily understand the communication protocol: the only problem is implementing the wrapper. There is an easy solution: my wrapper script is one (short) line long, in Bash. You can do it in other ways, including in Scheme, but it's harder. For example, here is how I use my logger script that I have called solution/with-log (of course you don't have it, you have to implement something similar!):
```
./server ./monitor 'solution/with-log ./client' ./client
```
Notice the quotes around solution/with-log ./client: the server must see it as a single option, even if on its own it's a command line (but this is not the only solution: your script may also call the proprietary client internally, and take no options).
If you want to implement the wrapper as a shell script like I did, you need a standard Unix utility, and pipes. I won't tell you right along the name of the utility, but the GNU implementation is part of the GNU coreutils. Of course it's documented in the GNU coreutils manual. I will tell you more if you get stuck with this too long.
I think that the wrapper script is the best solution, but it's not the only one: for example you can write a program which reads an s-expression from the standard input and saves it on a file. At that point your program will not be able to answer in a correct way as you don't know the correct output protocol yet; so you can kill processes. But you'll have saved one correct input.
After you have discovered the format of the input this way, you can run the client without the server, and manually give it the input you found the first time. Of course the client will answer with output, so you will also see an example of that. Iterate the process.
Reading an s-expression from the standard input (or another port) is easy in Scheme: use the function read
The client output should be flushed after each s-expression: in Scheme you can use the functions write, newline and force-output.
If a monitor process remains hung and it's hard to kill, use xkill.

Optional: understand the C files src/*proprietary.[ch], and tell me. How was the proprietary application implemented? Tell me.

Optional: can you obtain part of the source code of client in some way? Tell me if you succeed. Optional: about trying to recover part of the source code as just requested: is it legal? Why?

Task 3: Make your client play better than the proprietary one

The proprietary client isn't a great player: you can do better and beat it most of the times.

Call me if you succeed in this.

Notes for myself, in case of problems with the SERCAL installation or with student accounts:
~~The emergency machine has IP 194.254.173.145 .~~
My id is 10706282 .

Back to my home page...