Super Gravitron Leet Edition — Pwn2Win 2018 — Writeup
Super Gravitron Leet Edition (SGLE) was one of the PPC challenges in Pwn2Win 2018. This challenge was only accessible to competitors via VPN.
The description was the following:
Do you know the Super Gravitron by VVVVVV? Yes, Terry Cavanagh is a genius! And the bavs tasked with recruiting new programmers made a version of this game that runs on the console, and use it in their recruitment program! We're trying to infiltrate their IT sector, so we need your programming skills to beat the game, by creating a bot that can last 137 seconds in it!Instructions:
1 - You can only move horizontally, as in the original game, using the directional keys (<- and ->);
2 - The objective is "just" to avoid the obstacles;
3 - When you hit an obstacle, it will be marked with an "X". Press or to exit;
4 - Press or " to close the game at any time;"
5 - The elapsed time and the position of the Jumper(I) are shown in the game screen;
6 - Run it in full screen mode to avoid problems;ssh sgle@10.133.70.3Id: sgle
Total solves: 0
Score: 500
Categories: PPC
The description also had a link the following video:
The challenge was not solved during a competition, but the staff provided the code of the server. Because of that, at the end of the year I decided to finish my solution and write about it.
It is an adaptation of one level of the game VVVVVV, which the player (I) must survive for 137 seconds by diverting from objects that “randomly” appear on the screen.
Server Comunication
In game, player (I) movement was continuous, and it was only possible to invert the horizontal directions that were modular (one side of the screen exits in the other), while the cursor moved uninterruptedly up or down on the screen.
Since the connection uses SSH, the solution should play automatically with the server (I tried the by hand, but I could not get higher than 45s).
The first problem I had (and I lost a lot of time trying to fix) was that I was sending the wrong escape keys to the server. I wrote a snippet to capture keys like that:
import curses
screen = curses.initscr()
tela.addstr("Screen: ")
ans = ''
while True:
key = screen.getkey()
if key == "\n":
break
ans = ans + key
curses.endwin()
print repr(ans)And by pressing left and then right, I would receive the following:
'\x1b[D\x1b[C'Spite of this method, when I sent those keys to the server sometimes I was disconnected. Later (much later) I saw in an article about Screen that there are this other escape keys to the same functions
'\x1b0D\x1b0C'and to ‘right’ direction only this works well.
Because the content received from the server needs to be read continuously, I tried several approaches (sockets, pexpect, pygui) and none could solve instabilities that I had between read and send commands.
After chat with another competitor who was also focused in this challenge, he commented that he had the same problems, and the fix require some trick in the receiving data process.
Knowing that I was not the only suffering with that, I start digging for a solution that continuously receive content and write to a file, which I could read (non-blocking) and sending commands without concern thereafter. So, I found Stack Overflow post with the following snippet:
# make stdin a non-blocking file
fd = sys.stdin.fileno()
fl = fcntl.fcntl(fd, fcntl.F_GETFL)
fcntl.fcntl(fd, fcntl.F_SETFL, fl | os.O_NONBLOCK)where sys is an open process that can receive input from the user while reading content being sent by the server. This way it was possible to solve the challenge, despite some frame being lost during the game.
Solution
One of the first things I noticed in the game is that objects (enemies) on the screen always appeared in the same coordinates (sometimes changing a few fractions of a second, but always repeating), pointing to an evolutionary solution.
In that way, to solve the challenge I ended up implementing a simplified version of a genetic algorithm that was learning as it was playing the game. I do not much into Evolutionary Algorithms or Artificial Intelligence, but sometimes you need to get your hands dirty.
Genetic Algorithm (GA) is a technique for finding approximate solutions for optimization problems imitating biological evolution behaviours. The GA architecture that I used in this solution has the following components: Objective Function, Individual, Population, Generation, Mutation and Selection.
Objective Function is basically the game that we need to play to reach the flag, which is the goal of playing the game.
Individual can be seen as a match where we previously selected all movements to be used during the game. For example, if the game has 137 seconds and we decide to execute one move per second, an individual consists of a set of 137 moves (“left,” “right,” or “nothing”). Example of a set of movements:
+---+---+---+---+---+----
| > | > | < | | > | ...
+---+---+---+---+---+----
0 1 2 3 4 5 ..Thus a set of n individuals is a population, which at the beginning of the algorithm is a set of individuals with “random” movements.
Then the matches are played for each individual and the time of each match is the score that the individual achieves. To collect the times during the match, I used the following regular expression (adapted to be used in python):
currentime = re.findall('\[\d+:\d+\].*\[(\d+.\d+)\]', screen)screen is a string with the content of the screen at the time in the game (non-blocking read). It should be noted in a screen that there are three important things to be tracked (during a game):
- Time: time at moment where the content was read
- “X”: indicates a game over because a collision
- “CTF”: flag (my guess about how the flag should appear)
The round where all games are played (one per individual) is called a generation. At the end of a generation each individual has its own score that indicates how many seconds it survived in the game. The score indicates the moment where the collision occurred. Because of that, to the algorithm improves in each generation using mutation which is responsible for modifying some movements in an individual, trying to correct possible errors during the game, for the next generation.
The following generation consists of the individual with the best score, and a few selected individuals with the following characteristics: 60% are mutations of the best individual (includes the best individual), 30% are mutations of sample of the population and 10% are new individuals.
The mutation from the best individual modifies only a few movements near the position where the individual has lost the game. Here is an example modifying the last two positions from that point of lost:
Best Individual - Score: 5+---+---+---+---+---+-|-+---+---+---+---+---+---+
| > | | < | > | < | > | > | | < | | < | > |
+---+---+---+---+---+-|-+---+---+---+---+---+---+
+
Position where the individual lost the gameMutated Individual (from the best individual)+---+---+---+---+---+---+---+---+---+---+---+---+
| > | | < | > | > | | > | | < | | < | > |
+---+---+---+---+-|-+-|-+---+---+---+---+---+---+
| |
Changed Positions
The mutation of a sampled individual modifies 10% of all the movements. The sample algorithm is biased in a way to choose an individual whose score was good enough (details in the code).
The basic idea of the mutation is that the score of the best individual in a given generation needs to be equal to or better than the best score of the previous generation until the goal is achieved (137 seconds).
Execution of the Solution
Because of the non-blocking reading, sometimes the score worsened. This occurred because there are executions where the movement sent did not match the same frame captured in another execution. And this asynchronous behavior made the time worsen somewhat causing the algorithm to converge sometimes slow or weirdly to the expected result.
At the competition I varied the percentages between the mutations and the sizes of the mutation and sample, but the instability of the communication methods I commented before did not let the algorithm improve in any way and the solution did not exceed 40 seconds. At some moment, the VM were improved by the staff and the algorithm managed to reach 60 seconds, but the competition was already close to the end.
The show in this writeup, I ran the solution with a population of 8 individuals. The new generation had 6 individuals mutated from the best individual (elite squad), one selected from the previous generation and a new individual. In the elite squad, two individual were no mutated. I did this so that I did not lose the best individual in cases where had happen some problem with frame read. Individual 3 get mutated the last six movements, Individual 4 get the last nine movements, Individual 5 get the last twelve movements and Individual 6 the last fifteen movements. The following video show this execution that reach the goal after 47 generations:
Conclusion
Even with some difficulties (from my side), it was a great challenge and a unique opportunity to put in practice some concepts that I didn’t touch for too long.
My first thought to this chall was to code a parallel version of this solution where each individual of a generation will be ran in parallel to speedup the time. As I had problems in the server (which was solved) and in local reading the content from the server (instability of the read frames), I had to abandon the idea.
I learned a lot with this chall and knowledge is never too much. Thanks for all the guys that organized Pwn2Win (one of the few that I played in 2018) for an awesome competition and challenges held in 2018.
Link to the solution code: https://github.com/318BR/CTF-2018/tree/master/Pwn2Win/PPC-SGLE
