Jump to content
unc4nny

Duvida no livro Practical Reverse Engineering (Switch-Case optimization)

 Read less than a minute

Recommended Posts

Posted (edited)
 Read less than a minute

Oi.

Estou lendo o livro practical reverse engineering, e nele, o autor fala sobre otimizacao de switch-case statements usando jump tables. Aqui esta o Assembly e a representacao em Pseudo-C do autor:

image.thumb.png.1254e4a5db05fc3f0e6fbfdff3b235ee.png

image.thumb.png.e06796e41ca8f22d7087a23edda30efe.png

Eu realmente nao to entendendo muito bem o que esta acontecendo:

  1.  O que a linha 03 no codigo ASM quer dizer? No sentido em que, eu acho que entendo mais ou menos o que "ds:offset" significa mas nao entendi o motivo/significado desse [edi*4], principalmente comparando com a linha 01. Se nela o codigo compara edi com 5, como que ele esta usando o operador de acesso a memoria em [edi*4]?
  2. Como que o autor fez essa conversao de asm para pseudo-c? Ele compara edi com 5, e se edi for maior ele pula para a linha 16, que segundo o pseudo-c dele eh o 'default', se for menor ou igual, ele faz uma maracutaia que eu nao entendi muito bem. Tambem nao entendi como que no switch-case dele ele conseguiu achar 6 comparacoes (De 0-5)?

Outra coisa eh esses saltos incondicionais para loc_10001145, mas no pseudo-c dele o endereco nem aparece.

Resumo: O que o asm esta fazendo a partir da linha 03 ate a linha 24? E como que o autor sabe que ele esta comparando com 0, 1 ... 5?

Espero ter explicado minha duvida certinho, hehe.  Obrigado desde ja!

 

Edited by unc4nny
  • Curtir 1
  • l33t 1

Share this post


Link to post
Share on other sites
 Read 3 minutes

Ótima pergunta. Acho realmente incrível estudar os pormenores! Muitos livros passam batido e acho que uma das coisas mais difíceis de se fazer é explicar as bases com qualidade. Vou tentar. 🙂

Você já deve ter ouvido falar que utilizar variáveis numéricas em construções switch/case é "melhor" ou "mais rápido", certo? Fato que a linguagem C nem suporta com outros tipos, mas em PHP por exemplo permite o uso de strings:

switch ($var) {
    case "mente":
        // código
        break;
    case "binária":
        // código
        break;
    default:
        // código
        break;
}

Já no C, tem que ser números mesmo. E aí tem várias maneiras de otimizar isso, em vários níveis. Como a instrução CMP é meio "cara" para o processador, os compiladores tentam evitá-la, assim como os saltos. Num teste rápido aqui compilei o seguinte código no macOS ó:

#include <stdio.h>

int main(int argc, char *argv[]) {

	int var;

	scanf(" %d", &var);

	switch (var) {
		case 0xaa:
			printf("http://menteb.in");
			break;
		case 0xbb:
			printf("mentebinaria.com.br");
			break;
		case 0xcc:
			printf("papobinario.com.br");
			break;
		default:
			printf("menteb.in/conf");
	}
	putchar('\n');

	return 0;
}

O compilador (no meu caso, o clang) evitou instruções CMP usando SUB do valor que pus no case e depois pulando se for zero (JE/JZ):

0000000100000e72        subl    $0xaa, %r8d
0000000100000e79        movl    %eax, -0x18(%rbp)
0000000100000e7c        movl    %edx, -0x1c(%rbp)
0000000100000e7f        movl    %r8d, -0x20(%rbp)
0000000100000e83        je      0x100000eba
0000000100000e89        jmp     0x100000e8e
0000000100000e8e        movl    -0x1c(%rbp), %eax
0000000100000e91        subl    $0xbb, %eax
0000000100000e96        movl    %eax, -0x24(%rbp)
0000000100000e99        je      0x100000ed0
0000000100000e9f        jmp     0x100000ea4
0000000100000ea4        movl    -0x1c(%rbp), %eax
0000000100000ea7        subl    $0xcc, %eax
0000000100000eac        movl    %eax, -0x28(%rbp)
0000000100000eaf        je      0x100000ee6

Mas ainda tem os saltos condicionais JE/JZ que fazer o processador ter que checar a Z flag.

Basicamente tô falando tudo isso pra te dizer que o código nem sempre vai ser o que você acha. O compilador pode otimizar de muitas formas. No clang aqui tem várias opções no manual ó:

-O0, -O1, -O2, -O3, -Ofast, -Os, -Oz, -Og, -O, -O4
    Specify which optimization level to use:
        -O0 Means "no optimization": this level compiles the fastest and generates the most debuggable code.
        -O1 Somewhere between -O0 and -O2.
        -O2 Moderate level of optimization which enables most optimizations.
        -O3 Like -O2, except that it enables optimizations that take longer to perform or that may generate larger code (in an attempt to make the program run faster).
        -Ofast Enables all the optimizations from -O3 along with other aggressive optimizations that may violate strict compliance with language standards.
        -Os Like -O2 with extra optimizations to reduce code size.
        -Oz Like -Os (and thus -O2), but reduces code size further.
        -Og Like -O1. In future versions, this option might disable different optimizations in order to improve debuggability.
        -O Equivalent to -O2.
        -O4 and higher
            Currently equivalent to -O3

O gcc tem uma flag específica pra criar ou não as jump tables que você tá com dúvida (a opções são fjump-tables fno-jump-tables) e você pode fazer um teste aí.

Falando especificamente sobre as jump tables agora...

Basicamente, ao invés de fazer várias comparações, o compilador deu um jeito de usar o valor da variável submetida ao switch (no caso, chamada de edi no seu exemplo) para fazer uma conta e pular para o local certo.

Como? Bem, como mostrado na linha 19, no endereço 0x100011a4 o compilador criou a jump table, ou seja, um array (portanto, possui seus elementos armazenados em sequência) com 6 elementos, que contêm o código de cada caso diferente (perceba que existem 6 casos, excluindo o default, mas só 4 são únicos). Este endereços são endereços de 32-bits, logo, 4 bytes cada, então ficaria assim:

0x100011a4 <+0>  == 0x10001125
0x100011a4 <+4>  == 0x10001125
0x100011a4 <+8>  == 0x1000113A
0x100011a4 <+12>  == 0x1000112C
0x100011a4 <+16> == 0x10001133
0x100011a4 <+20> == 0x1000113A

Certo? Tô somando de 4 em 4 bytes. Também poderia escrever os endereços na forma 0x100011a4, 0x100011a8, 0x100011ac, etc, ao invés de usar a notação 0x100011a4 <+offset em decimal>, sacou?

Legal. Cada um desses endereços é um ponteiro e o valor é o endereço do código de um caso único. Por exemplo, o primeiro elemento do array contém o valor 0x10001125, que contém o código dos casos 0 e 1. Por isso o segundo elemento do array tem o mesmo valor do primeiro. 😉

Já o terceiro elemento tem o valor 0x1000113A, que é o endereço do código para os casos 2 e 5. E por aí vai...

Agora como fazer a comparação pra usar a jump table? Analise de novo da linha 1 em diante do teu código...

Tem uma comparação logo de cara, com 5. Se for maior, cai no caso default. O compilador inteligentemente utilizou a instrução JA e não JG. A diferença é que a primeira interpreta os valores como sem sinal, portanto se a variável por igual a -1 por exemplo, ela vai pular pro caso default de qualquer jeito. Foda né? 😎

Na linha 3 vem a mágica: jmp ds:0x100011a4[edi * 4]

O compilador usou a própria variável submetida ao switch (no caso, o valor dela está no registrador EDI) pra direcionar o salto incondicional JMP. Em 0x100011a4 temos a nossa jump table e EDI está sendo usado como índice do elemento do array a ser lido. Então:

  • Se EDI é 0, 0*4==0, então o primeiro elemento do array será lido e o salto vai para 0x10001125.
  • Se EDI é 1, 1*4==4, então o segundo elemento do array será lido e o salto vai para 0x10001125.
  • Se EDI é 2, 2*4==8, então o terceiro elemento do array será lido e o salto vai para 0x1000113A.
  • Se EDI é 3, 3*4==12, então o terceiro elemento do array será lido e o salto vai para 0x1000112C.
  • Se EDI é 4, 4*4==16, então o terceiro elemento do array será lido e o salto vai para 0x10001133.
  • Se EDI é 5, 5*4==20, então o terceiro elemento do array será lido e o salto vai para 0x1000113A.

É como na aritmética de ponteiros em C - uma soma por exemplo considerará o tamanho do tipo. Então, no código abaixo, o primeiro elemento vai estar num endereço X e o segundo em X+4, o terceiro em X+8 etc. Testa aí só:

#include <stdio.h>

int main(int argc, char *argv[]) {

	int array[] = { 0x10001125, 0x10001125, 0x1000113a, 0x1000112c, 0x10001133, 0x1000113a };

    for (int i=0; i<6; i++)
        printf("%p: %#.2x\n", array+i, *(array+i));

    return 0;
}

No meu caso aqui deu isso:

$ gcc -o jmp jmp.c && ./jmp
0x7ffee12a48c0: 0x10001125
0x7ffee12a48c4: 0x10001125
0x7ffee12a48c8: 0x1000113a
0x7ffee12a48cc: 0x1000112c
0x7ffee12a48d0: 0x10001133
0x7ffee12a48d4: 0x1000113a

Perceba que na primeira iteração, o printf imprime o endereço do array, que no meu caso é 0x7ffee12a48c0. Na segunda iteração, o printf já imprime o endereço do segundo elemento, que é 0x7ffee12a48c4 e não 0x7ffee12a48c1, pois cada elemento possui 4 bytes. Por isso o [edi * 4] no teu código. 😉

Acho que entendendo isso você mesmo consegue responder as perguntas que fez, mas avisa aí se faltar algo.

Abraço!

Share this post


Link to post
Share on other sites
Posted (edited)
 Read less than a minute

Cara, acho que entendi tudo o que voce disse (eu espero haha), explicou muito bem. O que realmente me bugou foi o uso do edi como acesso ao indice do vetor, eh isso mesmo que ta acontecendo? Pq eu achava que o acesso nesses segmentos era feito por SEGMENTO:OFFSET, ai esse [ edi * 4 ] me bugou muito, pq que o asm esta usando essa sintaxe? Na minha cabeca seria assim: ds:[0x100011a + edi * 4] <- isso faz sentido? Eh a primeira vez que eu vejo essa sintaxe.

Mto obrigado mano vc eh brabissimo

Edited by unc4nny

Share this post


Link to post
Share on other sites
 Read less than a minute

Ah, isso é a sintaxe do IDA. É exatamente a mesma coisa:

jmp dword ptr ds:[edi*4+100011] // OllyDbg, x64dbg, etc
jmp dword_100011a[edi * 4] // IDA

Ambas são interpretações de um salto indireto FF 24. Pode checar com o radare2 ó:

$ rasm2 -ax86 -d ff24bd11001000
jmp dword [edi*4 + 0x100011]

FF 24 é o jump indireto. BD é o EDI*4 e o resto é o endereço do array. Percebe que o radare já não usa o "ptr" que o Olly e o x64dbg usam. Pode ser confuso mesmo, mas é tudo a mesma coisa.

É que assim, no geral as pessoas simplificam em sintaxes Intel e AT&T, mas na prática os disassemblers fazem "pequenos patches" nelas. Só pra você ver o quanto varia:

IDEAL (Borland):

JMP [DWORD DS:EDI*4+0x100011]

HLA (High Level Assembly):

JMP ([TYPE DWORD DS:EDI*4+0x100011])

AT&T:

jmp *%ds: 100011(,%edi,4)

Sem contar as opções que os disassemblers possuem como omitir o segmento (aí não vai ter mais o ds:), disassemblar em maiúsculo ou minúsculo, com ou sem o "0x", etc.

E tem mais: quando estamos escrevendo código-fonte em Assembly, mudam detalhes também. No MASM por exemplo se o seu array se chama "arr", vai ser arr[edi * 4] (como o IDA mostra). Mas aí tem que ver como é no TASM, YASM, NASM, BASM... Enfim, no final, sabendo que as diferenças de sintaxe existem, compare sempre os opcodes, assim você vai ter certeza do que tá rolando. 😉

Abraço!

 

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.


  • Recently Browsing   0 members

    No registered users viewing this page.

×
×
  • Create New...