Skip to content

Instantly share code, notes, and snippets.

Created August 21, 2021 01:18
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save uint0/f357856d4f386dd5233daa7408b0f01a to your computer and use it in GitHub Desktop.
Dynamically solves the bullet hell challenge by relying on the binary to do simulation.
import struct
import collections
import pwn
MAX_X = 30
MAX_Y = 40
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')'./patched')
def get_state_addr(proc):
# Pretty sure you can get this more intelligently, but cbs
maps = open(f'/proc/{}/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)
game_state_addr = get_state_addr(proc)
game_state = read_gamestate(proc, game_state_addr)'Game State struct @ {game_state_addr:x}')
while game_state.score < WANTED_SCORE - 1:
if game_state.score % 100 == 0:'Up to frame {game_state.score}')
game_state = read_gamestate(proc, game_state_addr)
bullets = read_bullets(proc, game_state)
yield game_state, bullets
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
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
# 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
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__':
provider = provide_game_states('./patched')
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment