Show HN: hackeie seu oponente com um jogo de tabuleiro de mesa em assembly RISC-V

 (punkx.org)
3 pontos por GN⁺ 2023-10-01 | 1 comentários | Compartilhar no WhatsApp
  • PROJEKT: OVERFLOW é um jogo educativo que transforma assembly RISC-V e buffer overflow em regras de jogo de tabuleiro, fazendo você acompanhar diretamente memória, stack e manipulação de endereços de retorno
  • Os jogadores competem compartilhando a mesma memória e o mesmo programa, sem memória virtual, em um esquema de escalonamento preemptivo que executa apenas 10 instruções por turno
  • A partida é decidida pela criação de shellcode ao copiar instruções existentes e sobrescrever o return address do oponente para enviá-lo a game_over()
  • Acessos incorretos à memória, leituras e escritas desalinhadas e instruções ilegais levam a travamentos e à execução do tratador de exceção, e mudar o endereço de trap e fazer monkeypatch com nop são variáveis estratégicas centrais
  • Há jogo via web, tabuleiro para impressão e helper do jogo para ESP32 e celular, mas algumas regras ainda estão sendo ajustadas, então ele se parece mais com um quebra-cabeça experimental de hacking

Objetivo do jogo e modelo de execução

  • PROJEKT: OVERFLOW é um projeto que trata assembly RISC-V e buffer overflow como um jogo de tabuleiro de mesa
  • O objetivo central é copiar instruções existentes para criar um pequeno shellcode na memória, pular para esse código com um buffer overflow e então sobrescrever o return address do oponente para fazê-lo chamar a função game_over()
  • A estratégia vai além da simples execução de código e inclui configuração de tratadores de exceção e até monkeypatch
  • Todos os jogadores compartilham a mesma memória e o mesmo programa, e usam o mesmo processador em fatias de tempo
    • Em cada turno, executam 10 instruções
    • O stack pointer de cada jogador começa em uma posição diferente
    • Não há memória virtual

Fluxo de build e geração do tabuleiro

  • O código é compilado com riscv64-unknown-elf-gcc para um alvo RV32
    • As principais opções incluem -march=rv32g, -mabi=ilp32, -ffreestanding, -nostdlib, -nostartfiles, -O0 e outras
    • Graças a -O0, o código de máquina fica verboso, mas fácil de acompanhar
  • O material do tabuleiro é criado analisando a saída de riscv64-unknown-elf-objdump -S -l -fd game
    • As instruções ▲ e ✎ são modificadas
    • Os offsets de salto são convertidos de hexadecimal para decimal
    • O assembly é reorganizado e associado ao código-fonte
    • Um SVG é gerado e depois convertido em PDF com o Inkscape

Impressão e materiais

  • O tabuleiro é usado imprimindo PDFs separados em lado esquerdo e direito
  • A impressão em A3 é preferida; A4 também funciona, mas fica pequeno
  • Os materiais necessários são 1 peça para a instrução nop, 1 peça para o endereço de trap, 2 peças por jogador para program counter e stack pointer, além de lápis e borracha
  • A versão web oferece suporte a jogo solo e com amigos, e também há um helper do jogo para ESP32 e celular

Regras básicas e andamento do turno

  • O estado inicial é o seguinte
    • Todos os registradores começam em 0, mas o registrador de return address ra começa em 1000
    • O sp do Player 1 é inicializado em 2244, e o do Player 2 em 3844
    • O pc dos dois jogadores começa em 1000, o endereço inicial da função main
    • A peça de trap é colocada no endereço 1000
    • Todos os endereços de memória, exceto o programa pré-carregado, começam com valor 0
    • A peça da instrução nop não é colocada no tabuleiro no início
  • Em um turno, é preciso executar 10 instruções, e saltos como jal e beq também devem ser seguidos normalmente
  • O jogador pode encerrar o turno após executar pelo menos 1 instrução e carregar o restante para o próximo turno
    • O máximo acumulável é de 20 instruções

Monkeypatch e condição de vitória

  • No início de cada turno, após executar exatamente 1 instrução, é possível mover a peça da instrução nop para qualquer endereço de uma função que os jogadores não estejam executando no momento
  • Quando o pc chega a esse endereço, a instrução se comporta como no-operation
  • Ao mover a peça nop, você perde o turno atual e o próximo, e o oponente pode executar até 20 instruções no turno seguinte
  • A regra de monkeypatch ainda não está bem balanceada e vem mudando um pouco a cada poucos dias
  • No modo difícil, o jogo termina quando você hackeia o oponente e o faz chamar a função game_over()
  • Se nenhum dos lados puder mais mandar o outro para game_over(), o resultado é empate
  • No modo fácil, vence o primeiro jogador a executar ret em main e sair do loop principal

Símbolos especiais e tratamento de exceções

  • ✎ permite escolher qualquer número arbitrário de 12 bits, de 0 a 4095, como valor immediate de uma instrução li
  • ▲ permite escolher, em uma instrução de load, um valor dentro da faixa de ±128 bytes com base no próprio stack pointer
    • Por exemplo, se sp for 2180, é possível escolher de 2052 a 2308
  • Ações proibidas fazem o programa travar
    • sobrescrever endereços de memória abaixo de 1192
    • fazer leitura ou escrita desalinhada em endereços que não sejam múltiplos de 4
    • executar instruções ilegais
  • Quando ocorre um travamento, o tratador de exceção é executado e há um salto para o endereço de trap
    • O endereço de trap começa em 1000, mas pode ser sobrescrito pela função set_trap()
    • Quando uma exceção acontece, o program counter recebe um valor específico e a execução continua
  • Se fraude ou erro forem detectados, o estado do programa, a memória e os registradores daquele jogador são reinicializados

Regras de expansão para 3 a 4 jogadores

  • O sp do Player 3 é definido como 2116
  • O sp do Player 4 é definido como 3716
  • Com 3 ou mais jogadores, o símbolo ▲ só pode ser usado no intervalo de -128 bytes a partir do stack pointer
  • Com mais de 2 jogadores, o jogo fica bastante instável e se corrompe rapidamente
  • Chegar à condição de vitória fica mais difícil, mas a partida se torna mais divertida e caótica

Exemplos de estratégia de hacking

  • Travamentos podem ser usados como estratégia ofensiva para bloquear o progresso do oponente
  • Se o trap handler for trocado para a função game_over, o primeiro jogador a travar perde
    • Nesse estado, a peça nop fica extremamente forte
    • Se o oponente colocar nop sobre o ret da função que você está executando, você pode perder
  • Na função bug(), se o índice sofrer overflow para 400 ou -400, é possível acessar a stack do oponente e sobrescrever o return address
    • Por exemplo, para ir do endereço 3784 para 2184, como (3784 - 2184) / 4 = 400, é necessário o índice -400
  • Com a função copy(), é possível copiar instruções específicas para a memória e montar um shellcode curto
    • Um shellcode de exemplo executa escrita arbitrária com a combinação li a4, ✎, li a5, ✎, sw a4, 0(a5), ret
    • Se a instrução ret for copiada, o return address passa a ser definido como o ponto inicial do shellcode, criando um loop infinito
  • Na função bug(), se o índice for definido como 6, a variável value pode ser escrita sobre o return address salvo na stack em 28(sp)
    • Ao retornar de bug(), o valor de 28(sp) é copiado para o registrador de return address
    • Se você colocar ali o endereço do shellcode criado, pode saltar para a memória

Interpretação das instruções e mudanças

  • Todos os saltos são relativos ao program counter atual, mesmo que no disassembler pareçam endereços absolutos
    • Por exemplo, o código de máquina 1903 para jal a4, 0 vira um loop infinito quando executado
  • A lista de instruções válidas do jogo foi organizada a partir das instruções RV32 JRI entre os códigos de máquina 0 e 4095, usando formas com a0, a4, a5, sp, ra e afins
  • O changelog 0.0.6 inclui a troca de while(run) por while(*prun)
    • Isso permite que o oponente induza um desreferenciamento desalinhado e provoque um travamento forçado
    • A regra de NOP foi alterada para permitir colocação apenas em funções que não estejam sendo executadas no momento

Design e materiais de estudo

  • Os retângulos dos lados esquerdo e direito do tabuleiro são uma mensagem binária codificada em ASCII
    • Retângulos brancos valem 1, e retângulos pretos valem 0
  • As cores usadas são apenas vermelho, azul, preto e branco, para manter a impressão barata e a legibilidade em impressoras monocromáticas
  • Não há syntax highlighting
    • A escolha evita o efeito de algumas partes do código parecerem mais importantes dependendo do tema e favorece julgamento próprio e concentração
  • Materiais para estudar assembly RISC-V incluem riscv-programming.org, cs3410 risc-v interpreter e rvcodecjs do luplab
  • Como material para estudar C, usa-se a parte inicial de Beej's Guide to C Programming
  • Também são oferecidos PDFs imprimíveis de exercícios de assembly cobrindo variáveis, chamadas de função, ponteiros, strings, structs, arrays e recursão, além de uma versão estilo preenchimento de lacunas chamada “assembly hangman”

Leituras relacionadas

1 comentários

 
GN⁺ 2023-10-01
Opiniões do Hacker News

  • Realmente impressionante. O mais incrível, em especial, parece ser ter conseguido fazer a filha de 12 anos jogar isso junto
    Quando podemos esperar uma versão CHERI? :-D

    • Como “CHERI tem três objetivos centrais de projeto para melhorar bastante a segurança da TCB da linguagem C moderna por meio de suporte no processador para proteção de memória granular e isolamento de software escalável, e requisitos que às vezes entram em conflito exigiram ajustes cuidadosos no design”, acho que uma versão CHERI seria difícil :)
    • Aos 12 anos eu programava em assembly 6502. No ambiente de computação de hoje, não é fácil para uma criança de 12 anos fazer isso
    • Na era dos 8 bits, essa era uma idade comum para começar com computadores

  • Core War é um jogo em uma arena de memória de uma máquina virtual que dá suporte a uma linguagem assembly simulada simples. Vi pela primeira vez na Scientific American em 1984 e, como eu já programava havia uns 15 anos, reconheci que ele era inspirado no jogo mais antigo do Bell Labs, Darwin
    Darwin foi criado em 1961 e rodava no IBM 7090. Os programas competiam por recursos, e vencia o programa que se replicasse por todo o espaço alocado e o dominasse. Não durou muito depois que Robert Morris Sr. criou um programa invencível. Veja [2]
    Em meados dos anos 1970, Software Practice and Experience era um dos meus periódicos favoritos de ciência da computação, e publicava com frequência a coluna Computer Recreations, escrita sob o pseudônimo Aleph-Null. Na pós-graduação, me diverti implementando vários dos jogos que apareciam naquela coluna. A revista é cara, mas, se você é universitário, é bem possível que consiga encontrá-la na biblioteca da universidade, como eu fazia antigamente. As edições dos anos 1970 traziam temas como compiladores Pascal, Algol 68 e programação concorrente, eram fáceis e divertidas de ler, e foi por textos de N. Wirth que conheci Module[3,4] e, mais tarde, Oberon[5]
    [1] https://en.wikipedia.org/wiki/Core_War
    [2] https://en.wikipedia.org/wiki/Darwin_(programming_game)
    [3] https://onlinelibrary.wiley.com/doi/abs/10.1002/spe.43800701...
    [4] https://onlinelibrary.wiley.com/doi/abs/10.1002/spe.43800701...
    [5] https://onlinelibrary.wiley.com/doi/abs/10.1002/spe.43801909...

  • Eu tinha um amigo que dizia gostar de jogos, mas não ter cabeça para programação; com Human Resource Machine, ele acabou programando na prática, e algumas das soluções dele eram melhores que as minhas, mesmo eu tendo anos de experiência

    • Às vezes, uma nova perspectiva ajuda muito mais do que se imagina
      Meu filho de 12 anos odeia matemática, mas é surpreendentemente bom em Human Resource Machine e SpaceChem. Fico me perguntando se a matemática do ensino médio e a matemática da programação são fundamentalmente diferentes

  • Muito interessante. Considerando o tamanho da memória dos computadores hoje, sempre achei que mnemônicos curtos são uma escolha ruim de engenharia
    Aqui também, a primeira coisa a fazer é aprender e memorizar o que cada instrução faz. Se os nomes fossem trocados por formas mais descritivas, seria muito mais fácil aprender, lembrar e ler o código. Acho suspeito que as pessoas não façam isso com frequência
    Também acho que o fato de esse tipo de vulnerabilidade ser possível aponta para uma falha de projeto do sistema como um todo. Isso não quer dizer que não seja um jogo divertido ou uma boa forma de aprender, mas, na engenharia, problemas estruturais são aceitos com facilidade demais. A maioria nem consegue enxergar essa falha estrutural

    • Na primeira versão havia um pseudo-assembly muito mais legível, e pensei em seguir nessa direção. Mas, no fim, eu queria que minha filha se sentisse confortável lendo a saída do objdump, e não vejo aprender alguns mnemônicos como um grande problema
      Acho que crianças respondem muito bem quando não são subestimadas. Pelo menos foi assim com a minha
      Você acha que existe alguém que não veja leitura e escrita arbitrárias como falhas estruturais? Milhares de pessoas estão trabalhando nesse problema e fizeram bastante progresso. Ao mesmo tempo, ainda acho peek e poke divertidos

  • Isso é muito legal. Quero testar na empresa

  • Parece bem divertido. Para qual faixa etária você acha adequado?

    • Acho que a condição de vitória fácil, ou seja, sair do loop principal com um buffer overflow rápido em bug(), dá para crianças de 10 a 15 anos fazerem
      Minha filha tem 12 anos e estamos nos divertindo juntos. A condição de vitória difícil, ou seja, fazer o adversário saltar para a função game_over(), é mais complicada, mas acho que dá para chegar lá em 5 ou 6 meses
      Quanto a adultos, não sei. Algumas pessoas têm tanto medo de assembly, como se fosse coisa do diabo, que talvez seja mais difícil fazê-las jogar do que crianças

  • O interessante é que tendemos a ver o mundo como um espelho de nós mesmos
    Se eu me interesso por buffer overflow e programação, qual é a chance de minha filha naturalmente ter muito interesse nisso também? Sendo a primeira criança e, além disso, a segunda uma menina, a probabilidade parece ainda menor, mas mesmo assim vejo muitos pais insistindo
    Ao fazer um projeto desses, fico curioso se houve pelo menos alguma consciência de que ele é, em certa medida, um projeto de vaidade. De todo modo, eu me interesso por esse tipo de coisa, então fico feliz que tenha sido publicado

    • Mais interessante ainda é ver como as pessoas fazem suposições enormes sem se incomodar, só para tornar o próprio argumento plausível
      Você está insinuando que o criador do projeto força isso sobre a filha por vaidade própria, mas qual é a base para isso? Dei uma olhada em algumas páginas do site e não vi absolutamente nada que sugerisse isso; pelo contrário, há várias formulações suaves dizendo que a filha se diverte e tem bastante interesse
      Por que descartar a possibilidade de que a filha tenha começado por ficar sempre curiosa sobre o que o pai fazia no computador? Pode ter começado pequeno e crescido como um processo de mão dupla entre uma pessoa que compartilha seu interesse e uma jovem coexploradora
      Eu também não sei como foi de fato, mas você também não sabe. Como alguém que participou da educação por alguns anos, digo que crianças são aprendizes muito melhores do que normalmente se acredita. A estrutura da escola é uma razão, mas talvez, no fundo, também existam crenças limitantes como essa. Quero aplaudir esse pai por tentar compartilhar seus interesses e paixões com a filha e com o mundo
    • Como pai, estou apenas tentando ensinar tudo o que posso. Às vezes é programação, às vezes é luta, às vezes é meditação
      Algumas dessas coisas terão valor, outras não. As probabilidades estão sempre contra. A vida é assim mesmo

  • Quando o caminho de código RISC-V de 64 bits se estabilizar, funcionar bem o suficiente e até o “buffer overflow” desaparecer, como eles vão lidar com a obsolescência planejada se C/C++ nem sempre muda a sintaxe para ajudar? Pobres almas...

  • Espera aí.
    Um jogo de tabuleiro de mesa que envolve programação em assembly? Por que eu não pensei nisso antes? :D

  • PL/I acertou em coisas como verificação de limites de strings/arrays e uma pilha que cresce para cima, não para baixo
    https://www.acsac.org/2002/papers/classic-multics.pdf