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:

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):

Investigando o consumo de recursos

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

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.

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.

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

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.

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):

É 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?

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:

É 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:

🎉