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

[unc4nny]

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:

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!

 

[Fernando Mercês]

Ó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 e 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!

[unc4nny]

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

[Fernando Mercês]

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!