/bullet_hell.solve.py Secret
Created
August 21, 2021 01:18
Star
You must be signed in to star a gist
Dynamically solves the bullet hell challenge by relying on the binary to do simulation.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import struct | |
import collections | |
import pwn | |
MAX_X = 30 | |
MAX_Y = 40 | |
WANTED_SCORE = 1337 | |
def qol_patch(): | |
elf = pwn.ELF('bullet_hell') | |
# Don't tick without input | |
elf.asm(elf.symbols['wtimeout'], 'ret') | |
# Become immortal | |
elf.asm(elf.symbols['die'], 'ret') | |
elf.save('./patched') | |
def get_state_addr(proc): | |
# Pretty sure you can get this more intelligently, but cbs | |
GAME_STATE_OFFSET = 0x2e040 | |
maps = open(f'/proc/{proc.pid}/maps') | |
heap_line = next(m for m in maps if m.strip().endswith('[heap]')) | |
return int(heap_line.split('-')[0], 16) + GAME_STATE_OFFSET | |
def read_struct(proc, addr, struct_def, struct_name): | |
rep = collections.namedtuple(struct_name, struct_def.keys()) | |
typ = ''.join(struct_def.values()) | |
raw = proc.readmem(addr, count=struct.calcsize(typ)) | |
return rep(*struct.unpack(typ, raw)) | |
def read_arr(proc, addr, item_type, n_items): | |
return struct.unpack(item_type*n_items, proc.readmem(addr, count=n_items*struct.calcsize(item_type))) | |
def read_gamestate(proc, base_addr): | |
return read_struct(proc, base_addr, { | |
'player_x': 'i', | |
'player_y': 'i', | |
'score': 'i', | |
'bullets': 'P', | |
'bullets_len': 'N' | |
}, 'GameState') | |
def read_bullets(proc, game_state): | |
return [] if game_state.bullets == 0 else [ | |
read_struct(proc, bullet_ptr, { | |
'x': 'i', | |
'y': 'i', | |
'dx': 'i', | |
'dy': 'i' | |
}, 'Bullet') | |
for bullet_ptr in read_arr(proc, game_state.bullets, 'P', game_state.bullets_len) | |
if bullet_ptr != 0 | |
] | |
def provide_game_states(bin_path): | |
# Start the process | |
proc = pwn.process(bin_path, aslr=False) | |
proc.send(b'_') | |
game_state_addr = get_state_addr(proc) | |
game_state = read_gamestate(proc, game_state_addr) | |
pwn.log.info(f'Game State struct @ {game_state_addr:x}') | |
while game_state.score < WANTED_SCORE - 1: | |
if game_state.score % 100 == 0: | |
pwn.log.info(f'Up to frame {game_state.score}') | |
game_state = read_gamestate(proc, game_state_addr) | |
bullets = read_bullets(proc, game_state) | |
yield game_state, bullets | |
proc.send(b'_') | |
proc.clean() | |
def search_for_path(state_provider): | |
""" | |
We technically already have all the bullet positions from the state_provider | |
this automates generating inputs to solve the challenge, but you could just play | |
it by hand | |
""" | |
PADDING = 5 | |
INV_MOVE_OFFSETS = {'_': (0, 0), 'l': (-1, 0), 'k': (0, 1), 'j': (0,-1), 'h': (1, 0)} | |
arr_get = lambda arr, i, j: arr[i][j] if PADDING <= i < len(arr) - PADDING and PADDING <= j < len(arr[0]) - PADDING else False | |
grid = lambda: [[False] * MAX_X for _ in range(MAX_Y)] | |
# Construct reachabilities for each frame going forward | |
init_state, _init_bullets = next(state_provider) | |
t = grid() | |
t[init_state.player_y][init_state.player_x] = True | |
layer_reachable = [t] | |
for _state, bullets in state_provider: | |
layer_bullets = set((b.x, b.y) for b in bullets) | |
last_layer = layer_reachable[-1] | |
cur_reachable = grid() | |
for y, row in enumerate(last_layer): | |
for x, _col in enumerate(row): | |
for dx, dy in INV_MOVE_OFFSETS.values(): | |
if arr_get(last_layer, y+dy, x+dx) and (x, y) not in layer_bullets: | |
cur_reachable[y][x] = True | |
layer_reachable.append(cur_reachable) | |
# Back track over the frames to find a path | |
pos = next( | |
(x, y) | |
for x in range(PADDING, MAX_X - PADDING) | |
for y in range(PADDING, MAX_Y - PADDING) | |
if layer_reachable[-1][y][x] | |
) | |
steps = '' | |
for layer in reversed(layer_reachable): | |
x, y = pos | |
for move_key, (dx, dy) in INV_MOVE_OFFSETS.items(): | |
new_pos = (x+dx, y+dy) | |
if arr_get(layer, new_pos[1], new_pos[0]): | |
steps += move_key | |
pos = new_pos | |
break | |
else: | |
raise "WTF?" | |
assert pos == (init_state.player_x, init_state.player_y) | |
# Algo is off by one, since there are no bullets initially we just ignore it hehe | |
return '_' + ''.join(reversed(list(steps))) | |
if __name__ == '__main__': | |
qol_patch() | |
provider = provide_game_states('./patched') | |
print(search_for_path(provider)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment