Executando verificação de segurança...
35

Como um jogador diminuiu o tempo de carregamento do GTA Online em 70% usando engenharia reversa (2021)

Nota: este artigo foi longo, mas foi uma ótima leitura. Para quem tem curiosidade em C e/ou engenharia reversa, provavelmente irá gostar. Tem um tópico de resumo perto do fim do artigo, já que contém "spoilers", então você pode pular direto para ele se não quiser ler tudo. Boa leitura!


Para quem já jogou GTA V, provavelmente se deparou com uma grande lentidão ao entrar no modo online. O jogo, lançado em setembro de 2013, continuava lento mesmo em 2021, na época de escrita do artigo.

O autor, que se identificou como "t0st", decidiu investigar esse problema. Ele compartilhou os tempos de carregamento no modo história e no modo online, contando do logo R* até entrar no jogo:

ModoTempo de carregamento
História~1m10s
Online~6m

E as configurações do seu computador eram:

  • Processador: AMD FX-8350
  • SSD: Kingston SA400S37120G
  • RAM: 2x8 GB DDR3-1337Mhz da Kingston
  • Placa de vídeo: NVIDIA GeForce GTX 1070

Apesar de você poder argumentar que o computador já tinha peças antigas na época, o modo online demorava 5x mais para carregar do que o modo história. Inclusive, ele compartilhou uma enquete do Reddit feita em 2020 onde as pessoas votaram no tempo de carregamento médio do modo online na sua máquina (sem distinguir entre PC e console):

51 votos em 1 a 3 minutos; 125 votos em 3~6 minutos; 64 votos em 6 a 10 minutos; 14 votos em 10 a 15 minutos, 17 votos em mais de 15 minutos

Investigando o consumo de recursos

O autor começou a investigar da forma mais simples possível: usando o gerenciador de tarefas do Windows.

Gerenciador de tarefas exibindo os gráficos de CPU, memória RAM, SSD, Internet e GPU

De acordo com o gráfico, ele viu que após aproximadamente 1 minuto de carregamento, que é o período de carregamento de coisas em comum entre o modo online e o modo história, começa o carregamento de coisas exclusivas do modo online, onde o consumo de tudo subiu por um momento, mas o de CPU subiu e manteve-se alto.

A CPU subiu de ~25% para ~60%, o SSD e a GPU subiram um pouco, de quase 0% para algo que imagino ser entre 10% e 20% (não dá para ver pela imagem) por um breve momento e voltou para os ~0%, a memória RAM também subiu um pouco, e a Internet teve picos altos durante 1~2 minutos do carregamento das coisas do modo online e depois voltou a ficar com o uso baixo.

A maior exigência era no processador, em um único núcleo.

Examinando o consumo do processador

Ele decidiu realizar um perfilamento do uso da CPU. Para usar um "profiler", ele teria duas opções:

  1. Ter acesso ao código fonte, para que esse perfilador pudesse instrumenta-lo e obter uma imagem perfeita do que está acontecendo no processo.
  2. Realizar um dump da pilha do processo em execução e da localização do ponteiro de instrução atual para construir uma árvore de chamada em intervalos definidos. Em seguida, ir juntando os resultados para obter estatísticas sobre o que está acontecendo.

Obviamente ele precisaria ir com a segunda opção, visto que o código-fonte do jogo não é aberto. E ele conhecia uma ferramenta capaz de fazer esse trabalho no Windows: Luke Stackwalker.

10 funções diferentes, porém divididas em grupos de dois endereços muito próximos. Um representando 54,8% das amostras e outro 45,2%.

O autor disse que normalmente o Luke agruparia as mesmas funções, mas como não tinha os símbolos de depuração, precisou observar os endereços próximos para adivinhar se eram o mesmo lugar. Com isso, ele encontrou dois gargalos.

Procurando o problema no código

O próximo passo foi usar um disassembler, um programa que traduz linguagem de máquina para Assembly.

Como parecia haver algum tipo de ofuscação/criptografia que substituiu a maioria das instruções por coisas sem sentido, ele precisaria descarregar a memória do jogo enquanto executava a parte que queria investigar. As instruções, então, seriam desofuscadas. Ele usou o Process Dump para isso.

Código em Assembly

Com a "desofuscação parcial", ele conseguiu encontrar os nomes de duas funções, deduzindo o nome de outra: strlen, vscan_fn e sscanf.

Gráfico de chamada de funções, onde na base duas funções sem nome apontam para a que ele deduziu ser sscanf, que aponta para vscan_fn e que aponta para strlen.

Parecia um parse de algo, mas ainda não era possível saber do quê. Ele decidiu realizar o dump de algumas outras amostras com o x64dbg e descobriu que era o parse de um JSON de 10MB com 63 mil itens no seguinte formato:

{
    "key": "WP_WCT_TINT_21_t2_v9_n2",
    "price": 45000,
    "statName": "CHAR_KIT_FM_PURCHASE20",
    "storageType": "BITFIELD",
    "bitShift": 7,
    "bitSize": 1,
    "category": ["CATEGORY_WEAPON_MOD"]
}

Ele presumiu que era uma lista de todos os itens e atualizações possíveis que você pode comprar no GTA Online.

O processo de parse é o seguinte:

  1. Inicia com uma string em C de 10 MB indo para a memória.
  2. Move o ponteiro para o byte no início do valor a ser lido.
  3. Chama sscanf.
  4. Conta cada caractere da string de 10 MB (lembra do strlen no vscan_fn?).
  5. Retorna o valor lido.
  6. Volta para a etapa 2, até terminar a string de 10MB.

Representação gráfica dos passos acima

O infrator #2

Ok, se o primeiro problema era o uso da função sscanf, que não era nada otimizada para essa situação, faltava descobrir quem era o segundo infrator — lembra que no Luke Stackwalker haviam 2 grupos de funções?

Acontece que o segundo infrator é chamado logo ao lado do primeiro. Ambos são chamados na mesma instrução if, como visto nesta descompilação (os nomes que estão na imagem foram "imaginados" pelo próprio autor):

Código conforme descrito abaixo

É uma condição if que invoca duas funções, que o autor descobriu serem a função de parse e uma função de armazenamento em um array. Esse if está dentro de um loop, ou seja, é executado para cada item do JSON.

Cada entrada parecia algo como:

struct {
    uint64_t *hash;
    item_t   *item;
} entry;

Mas, antes de ser armazenada no array, o código verifica todo o array, um por um, comparando o hash do item para ver se está na lista ou não. Com aproximadamente 63 mil entradas, isso é (n^2+n)/2 = (63000^2+63000)/2 = 1984531500, ou seja, quase 2 bilhões de verificações. A maioria delas, inúteis.

Se você tem hashes exclusivos, por que não usar um hash map?

Código de verificação e armazenamento do "hashmap"

O autor disse que nomeu hashmap ao fazer a engenharia reversa, mas que claramente deveria ser not_a_hashmap. Também disse que esse array estava vazio antes de carregar o JSON, e que todos os itens do JSON são únicos. Eles nem precisam verificar se está na lista ou não, bastaria usar a função de inserir os itens diretamente (que está na imagem acima).

Prova de conceito (PoC)

O próximo passo era tentar resolver o problema. O plano? Escrever uma .dll, injetar no GTA, conectar algumas funções, ???, lucro!

O problema do JSON é complicado, ele não consiguiria substituir o parser de forma realista. Substituir o sscanf por um que não dependa do strlen seria mais realista. Mas havia uma maneira ainda mais fácil:

  • Conectar o strlen.
  • Esperar por uma string longa.
  • "Armazenar em cache" o início e o tamanho dela
  • Se for chamada novamente dentro do intervalo da string, retornar o valor armazenado em cache.

Algo como:

size_t strlen_cacher(char* str)
{
  static char* start;
  static char* end;
  size_t len;
  const size_t cap = 20000;

  // if we have a "cached" string and current pointer is within it
  if (start && str >= start && str <= end) {
    // calculate the new strlen
    len = end - str;

    // if we're near the end, unload self
    // we don't want to mess something else up
    if (len < cap / 2)
      MH_DisableHook((LPVOID)strlen_addr);

    // super-fast return!
    return len;
  }

  // count the actual length
  // we need at least one measurement of the large JSON
  // or normal strlen for other strings
  len = builtin_strlen(str);

  // if it was the really long string
  // save it's start and end addresses
  if (len > cap) {
    start = str;
    end = str + len;
  }

  // slow, boring return
  return len;
}

E quanto ao problema do array-hash, é mais simples - basta ignorar completamente as verificações de duplicatas e inserir os itens diretamente, já que os valores são únicos.

char __fastcall netcat_insert_dedupe_hooked(uint64_t catalog, uint64_t* key, uint64_t* item)
{
  // didn't bother reversing the structure
  uint64_t not_a_hashmap = catalog + 88;

  // no idea what this does, but repeat what the original did
  if (!(*(uint8_t(__fastcall**)(uint64_t*))(*item + 48))(item))
    return 0;

  // insert directly
  netcat_insert_direct(not_a_hashmap, key, &item);

  // remove hooks when the last item's hash is hit
  // and unload the .dll, we are done here :)
  if (*key == 0x7FFFD6BE) {
    MH_DisableHook((LPVOID)netcat_insert_dedupe_addr);
    unload();
  }

  return 1;
}

O código completo da PoC está no GitHub: tostercx/GTAO_Booster_PoC.

E os resultados foram:

ModificaçãoTempo
Modo online original6m
Com apenas a correção da verificação de duplicações4m30s
Com apenas a correção do parser JSON2m50s
Com ambas correções1m50s

É uma melhora de 69,4% no tempo de carregamento!

Resumo

  • Há um gargalo de CPU em um único thread ao iniciar o GTA Online;
  • Acontece que GTA se esforça para analisar um arquivo JSON de 10 MB;
  • O parser do JSON em si é mal construído/ingênuo; e
  • Após a análise, há uma rotina lenta de deduplicação de itens

Atualização da Rockstar!

Em aproximadamente 15 dias após a publicação do artigo:

  • O autor recebeu uma confirmação da Rockstar de que isso seria corrigido em breve;
  • Recebeu US$ 10.000 por meio do programa de recompensas no HackerOne da Rockstar como uma exceção (geralmente é apenas para questões de segurança).
  • Ele tentou pedir mais detalhes técnicos, mas as pessoas da Rockstar não puderam dizer nada.

E, no dia seguinte, a Rockstar publicou a atualização:

[March 16, 2021] – General / Miscellaneous (PS4 / Xbox / PC)

  • General network connectivity improvements

General / Miscellaneous (PC)

  • Improvements to PC loading times *Thanks to t0st for his contributions around this part of today's title update

E o resultado do tempo de carregamento após a atualização foi 1m54s:

Cronômetro com 1m54s

🎉

Carregando publicação patrocinada...
9

Além da história ser interessante, dá pra tirar algumas lições dela.

  • Acontece que GTA se esforça para analisar um arquivo JSON de 10 MB;
  • O parser do JSON em si é mal construído/ingênuo;

Na verdade eu voltaria alguns passos e questionaria se precisa mesmo de um arquivo JSON deste tamanho.

Fica aí um questionamento que todos nós deveríamos fazer. Hoje em dia todo mundo usa JSON pra tudo sem pensar, mas será que ele é o formato mais adequado para este caso? Se é algo que contém tantas informações e só vai ser lido pelo programa (ou seja, entendo que não precisa ser human readable), poderia muito bem estar em um formato binário, como por exemplo o Protobuf (que além de gerar arquivos bem menores que JSON, ainda tem - na média - o parsing mais rápido — para mais detalhes veja aqui e aqui, e também postei um teste que fiz comparando os dois formatos).

Escolher algo só porque todo mundo usa nem sempre é a melhor opção. Claro que muitas vezes não faz diferença, mas acho que faria muita no caso citado. O importante, como sempre, é avaliar caso a caso, e não ter medo de mudar conforme a necessidade. JSON tem suas vantagens, mas não serve - e nem deveria ser usado - pra tudo (e isso vale pra qualquer tecnologia que usamos).


Outro detalhe interessante é a escolha da estrutura de dados e a forma como era usada: um array para guardar os itens e a verificação de elementos repetidos. Como já dito, se podem ter itens repetidos, uma tabela de hash seria o mais adequado. E se os itens não se repetem, não precisaria verificar nada. Daí a importância de conhecer estruturas de dados, esta disciplina básica que faz parte dos fundamentos da computação, mas que ao mesmo tempo é tão negligenciada (até mesmo por "cursos" famosinhos, e por isso muita gente acha que é "teoria chata e inútil" — Não é!).

O que acontece é que muitas vezes lidamos com poucos dados, e aí tanto faz a estrutura escolhida porque a diferença é irrisória e até mesmo imperceptível. O problema só aparece em grandes volumes, como foi o caso do GTA, e aí conhecer bem as estruturas (pra que serve cada uma, em quais casos uma é melhor que outra, etc) faz toda a diferença.


Enfim, fica a lição. Nem mesmo um jogo AAA com orçamento de milhões de dólares está livre de cometer erros básicos. O que é meio triste, se parar pra pensar...

2

muito interessante sua colocação sobre o Protobuff, não conhecia e além disso são formas interessantes de resolver os problemas que se iniciaram errado e alguém provavelmente pode ter tido a mesma idéia mas preferiram deixar o jogo que já estava funcionando a 10 anos

EDIT: vale um post explicando o protobuff?
Eu meio que entendi a teoria rs.
e no caso existe um framework? escrevo human-readable e converte para protobuff?

2

Bom, eu usei pouco o Protobuf, então não sei se entendo tanto a ponto de escrever um post (talvez um introdutório, veremos).

A ideia básica é que vc cria um arquivo contendo o formato da mensagem (por exemplo, "Usuario" com os campos "id" e "nome", etc), e o compilador do Protobuf gera o código correspondente na linguagem desejada. Na documentação tem a lista de linguagens.

Basicamente, ele cria as classes que correspondem à mensagem que vc definiu. Aí vc usa essas classes para preencher com os dados e depois escreve tudo no arquivo binário. Este arquivo, por sua vez, pode ser lido por código em qualquer outra linguagem (desde que tenha sido gerado pelo mesmo arquivo com o formato).

Quanto a questão do human readable, já tem funções prontas para converter de/para texto (tanto para JSON quanto para um formato de texto próprio), bem útil para debugar. Não sei se tem framework pronto, mas meu chute é que alguém já deve ter feito :-)

1
1

Muito obrigado por disponibilizar!
Ficou muito bem organizado e entendível, melhor resposta que do ChatGPT kkkkk
Espero um dia precisar usar isso, na teoria eu entendi tudo :)

2

Isso foi um feito realmente incrível. Algo que impactaria praticamente toda a comunidade gamer, sendo que só foi resolvido mais de 10 anos depois do lançamento do jogo. Obrigado por compartilhar esse conhecimento aqui, expondo alguns conceitos de base que não são comuns hoje em meio a tanta discussão de frameworks e libs novas que surgem todos os dias.

1

Né rsrs pessoal inventa uma monte de coisa genérica de libs e frames, muitas vezes inutéis ou com pouca distinção entre elas, sendo que poderiam estar fazendo esses tipo de otimização em jogos da massa rs mto bom! E eu ainda nem cheguei nos Gurus dos Saas da vida kkkkkkkkk

1

Post bacana! Me ganhou no nome "Luke Stackwalker" rsrs, gostaria de ver mais sobre esses assuntos no TabNews, essa temático de jogos e como aplicar "programação" de maneira uma útil no dia a dia é muito bacana rs! 👍