Skip to content

Instantly share code, notes, and snippets.

@uint0
Created Aug 21, 2021
Embed
What would you like to do?
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
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