Phase 13: Tools & Protocols

Levantamento para Pseudocode: IR, SSA e Estruturação a partir do zero

Type: Build

Languages: Python, C

Prerequisites: Phase 13 · 32 (ELF from scratch), Phase 13 · 33 (disassembly and control flow)

Time: ~150 minutes

Objetivos de aprendizagem

• Elevador decodificou instruções x86-64 para uma pequena IR com bandeiras explícitas, cargas, lojas, ramos, chamadas e retornos.
• Transforme os espaços de quadro em variáveis locais e os registros de argumentos do Sistema V em parâmetros.
• Construir SSA mínimo com funções phi nas fronteiras de domínio, em seguida, substituir, simplificar e remover código morto.
• Recuperarif- Não .ifcomelse- Não .while, e do whiledo gráfico de fluxo de controlo com pós-dominatores e bordas traseiras.
• Explica o multiplicar por 0x66666667como uma divisão por 10 e provar a identidade.
• Leia o pseudcódigo Ghidra para as mesmas funções linha por linha e nomeie a instrução, ou a suposição, por trás de cada diferença.

O problema

Perguntaste à Rea o pseudônimo de percent_changeem ledger-x86_64-O1.oGhidra 12.1.4 respondeu em cerca de dez segundos:

cCopyundefined1  [16] percent_change(int param_1,int param_2,ulong param_3)

{
  long lVar1;
  undefined1 auVar2 [16];
  undefined1 auVar3 [16];
  
  if (param_1 != 0) {
    lVar1 = (long)((param_2 - param_1) * 100);
    auVar3._0_8_ = lVar1 / (long)param_1 & 0xffffffff;
    auVar3._8_8_ = lVar1 % (long)param_1 & 0xffffffff;
    return auVar3;
  }
  auVar2._8_8_ = 0;
  auVar2._0_8_ = param_3;
  return auVar2 << 0x40;
}

A fonte tem quatro linhas de comprimento.intvalores e retornos um intGhidra relata um valor de retorno de 16 bytes e um terceiro parâmetro que a fonte não tem. Os dezesseis bytes de código de máquina são corretos, e Ghidra decodificou cada um deles corretamente. A assinatura é uma adivinhação, e nada no texto marca-o como um.

rea retorna este texto como o procedure_pseudo_codeO resultado e liga uma limitação ao registro. A limitação diz: "Pseudocode é Ghidra decompiler saída, não fonte original e não texto equivalente à saída Hopper".compare_functionsO instrumento difere pseudocód como linhas de texto. Seu próprio registro de dimensões diz "Assembly é texto opaco do provedor" e que a normalização de relocação não está disponível. rea não pode olhar para dentro do texto, e nem um agente que apenas lê-lo.

O registro da rea DX-Ball mostra o custo.FUN_00406400(void)- O que é ?__ftol()A visão de instrução mostrava uma entrada de pilha e uma expressão x87.

Esta lição constrói a derivação que o decompiler esconde. Você começa com as 56 instruções que a lição 33 decodificou, levanta-as para um IR, renomeia em SSA, simplifica e estrutura. Então você coloca seu pseudocód next Ghidra's parapercent_change- Não .grade, e totalOs testes compilam a sua saída com clang e executam-na contra a fonte através de uma grade de entrada.

A Fixtura e o Oráculo

code/fixtures/ledger.cé a fixação compartilhada desta parte do curso:

cCopyint percent_change(int before, int after) {
    if (before == 0) return 0;
    return (after - before) * 100 / before;
}

int grade(int score) {
    switch (score / 10) {
    case 10:
    case 9: return 4;
    case 8: return 3;
    case 7: return 2;
    case 6: return 1;
    default: return 0;
    }
}

int total(const int *values, int count) {
    int sum = 0;
    for (int i = 0; i < count; i++) sum += values[i];
    return sum;
}

grade_labelAs três funções acima são as que esta lição testa.

O objeto foi construído com clang -target x86_64-unknown-linux-gnu -O1 -fno-asynchronous-unwind-tables -c ledger.c- O .-O0O objeto fica ao lado dele para a seção de slots de pilha. code/fixtures/README.mdlista ambos os comandos, o SHA-256 de cada objeto, e o comando rea que produziu os fixadores Ghidra.

O oráculo para o decodificador é llvm-objdump -d -rO texto para ambos os objetos é comprometido comoledger-x86_64-O1.objdump.txtE ...ledger-x86_64-O0.objdump.txtUm teste analisa esses ficheiros e compara cada instrução por endereço, por bytes e por texto da AT&T.-O1e todas as instruções em -O0Quando ?llvm-objdumpO teste é feito no caminho fixado, um segundo teste é feito ao vivo e compara novamente.

Aqui está .percent_changeComo o oráculo imprime:

textCopy0000000000000000 <percent_change>:
       0: 85 ff                        	testl	%edi, %edi
       2: 74 09                        	je	0xd <percent_change+0xd>
       4: 29 fe                        	subl	%edi, %esi
       6: 6b c6 64                     	imull	$0x64, %esi, %eax
       9: 99                           	cltd
       a: f7 ff                        	idivl	%edi
       c: c3                           	retq
       d: 31 c0                        	xorl	%eax, %eax
       f: c3                           	retq

Fase 1: Bytes para instruções

A lição 33 construiu o decodificador. Esta lição mantém uma pequena cópia para que o código funcione por conta própria. A cópia cobre exatamente os códigos opcodes que são emitidos paraledger.c- Não .-O0E ...-O1Para qualquer outra coisa que eleve .DecodeErrorcom o endereço e o byte do código op.

O decodificador segue a ordem de bytes do Intel SDM, Volume 2, secção 2.1. Os prefixos vêm primeiro, depois o opcode, depois o ModR/M, depois o SIB, depois o deslocamento, depois o imediato.0x40- Não .0x4FO REX.W seleciona um operando de 64 bits, o REX.R estende o regO campo REX.X estende o índice SIB e o REX.B estende r/mA secção 2.1.3 define os três campos ModR/M mod- Não .reg, e r/m, e os três campos SIB scale- Não .index, e base- Em modo de 64 bits.mod = 00comr/m = 101significa um deslocamento de 32 bits em relação à próxima instrução (seção 2.2.1.6).

O leaq (%rip), %rcx- Não .grade+0x23O objeto carrega uma realocação.R_X86_64_PC32.rodata+0x10em compensação0x36O elevador resolve-o na fase 3.

Fase 2: Blocos e dominadores

Um bloco básico é uma sequência de declarações com uma entrada no topo e uma saída na parte inferior.build_blocks()Reúne líderes: a entrada da função, cada alvo de salto dentro da função e cada endereço após um salto ou retorno. Cada bloco recebe sucessores de sua última instrução.jmp- Não, não.retNão tem nenhum, e um bloco que termina numa instrução ordinária passa para o próximo líder.

total- Não .-O1tem cinco blocos:

immediate_dominators()O algoritmo iterativo de Cooper, Harvey e Kennedy (2001) percorre os blocos em pós-ordem inversa e intersecta os dominadores dos predecessores processados até que nada mude.totalDiz-se que0x44Domina .0x50Também diz que0x50domina-se através da borda traseira, que é como estágio 8 encontra o ciclo.

A mesma função funciona duas vezes mais.dominance_frontiers()utiliza- o para a SSA na fase 5. post_dominators()corre no gráfico invertido com um nó de saída virtual para encontrar conjuntos na etapa 8.

Fase 3: Levantamento para uma pequena IR

O IR tem seis tipos de declarações: Assign- Não .Store- Não .Branch- Não .Jump- Não .IndirectJump, e Return. Expresões constantes, variáveis, operações binárias com largura, castes (sext- Não .zext- Não .truncOs cinco outros tipos existem, mas serão simplificados mais tarde:Flags- Não .Cond- Não .Concat- Não .SignFill, e Symbolic- Não .

Registros são variáveis nomeadas pela sua família de 64 bits.%eaxé um Assign- Não .raxcom largura 32, e uma leitura de %eaxé uma leitura de raxEm modo de 64 bits, uma escrita de 32 bits se estende a zero no registro completo, de modo que uma leitura posterior de 64 bits do mesmo valor é um zextO elevador não conhece a definição de alcance, por isso registra a largura de leitura e permite à SSA inserir o molde na fase 5.

As bandeiras são uma variável

Cada instrução que define os códigos de condição escreve uma variável chamada flags, e cada salto condicional lê-lo.cmp a, bescrevecmp(a, b), a test a, bescrevetest(a, b), e sub- É o mesmo .cmpA forma como efeito colateral.jcctorna-seBranch(Cond(cc, flags), target, fallthrough)O código de condição determina o operador de comparação quando os dois se encontram na fase 6:

xorl %eax, %eaxé levantado diretamente para eax = 0As bandeiras que ele coloca são escritas como:addAs bandeiras de estilo que não saltam na fixação.xorIdioma é importante em grade, onde Ghidra perdeu a cabeça.

CGT e IDEV

cltd- Não .%edxcom o sinal de %eax- Não .idivl %ediDivide o par de 64 bits %edx:%eaxPor%edi, coloca o coeficiente em %eax, e o resto em %edxO levantador escreve o par num nome temporário .dividendO restante da declaração, então, lê o antigo%eaxNo SSA, a metade superior aparece comosignfillO simplificador reduz o par para a metade baixa, e a divisão se torna um 32-bit /- Não .

Figura 1 - 0

• Não .-O0O Clang mantém todos os locais no quadro.percent_changeLojas%edi- Não .-0x8(%rbp)E ...%esi- Não .-0xc(%rbp)O levantador observa para que não haja uma armação.pushq %rbpseguida por movq %rsp, %rbpDepois do prólogo, uma ópera de memória com base.%rbp, sem índice, e um deslocamento se torna uma variável chamada local_<hex>- Não .-0x8(%rbp)É o que élocal_8- Não .-0xc(%rbp)É o que élocal_c- Não .

As próprias instruções de quadro não produzem IR, e nem o fazem.subqE ...addq- Não .%rspQualquer outro operando de memória permanece umLoadou Store- Não .

Relocalizações

O leaq (%rip), %rcxem gradeO deslocamento em compensação0x36Diz:R_X86_64_PC32.rodata+0x10O linker escreverá .S + A - P- Para o campo.Sé o endereço de .rodata- Não .Aé o adicionado0x10, e PO comando calcula o número de pontos de referência.next_ip + disp = (P + 4) + S + A - P = S + A + 4- Não .

O levantador aplica a mesma aritmética sem um linker. O objetivo de compensação é o adendo mais a distância do campo até o final da instrução, 0x10 + 4 = 0x14A IR diz:rcx = &.rodata+0x14E a mesa ali tem os cinco .intValores1, 2, 3, 4, 4- Não .

Fase 4: Parâmetros da Convenção de Convocatória

O sistema V AMD64 psABI, secção 3.2.3, aprova os argumentos da classe INTEGER em %rdi- Não .%rsi- Não .%rdx- Não .%rcx- Não .%r8- Não .%r9O resultado retorna em%raxE depois ...%rdxO ponto 3.2.1 diz que %rbp- Não .%rbx, e %r12através de%r15pertencem ao chamador e devem ser preservados.

collect_params()aplica uma regra: um registro de argumentos que é lido antes de qualquer escrita na função é um parâmetro. O maior registro desse tipo fixa a contagem, então uma função que lê %rsiE nunca .%rdiAinda tem dois parâmetros.percent_changelê %ediE ...%esi, então tem .param_1E ...param_2- Não .gradeSó lê .%edi- Não .totallê %rdicomo uma base de 64 bits e %esicomo uma contagem de 32 bits.

Agora é a Ghidra.param_3Tem uma explicação.idivlescreve%rdx, e o psABI permite um retorno de 128 bits INTEGER em %rax:%rdxEm um arquivo objeto não há um chamador para dizer o tamanho do valor de devolução.

No caminho zero,xorl %eax, %eaxSó escreve .%eaxGhidra leu .%rdxA entrada da função foi feita por umparam_3A assinatura é uma suposição sobre as partes que as instruções deixam abertas.

Fase 5: SSA, Um nome por definição

Depois de levantar,gradeescreveraxQuatro vezes e rcx- Três vezes. Cytron, Ferrante, Rosen, Wegman e Zadeck (1991) definem a forma de atribuição estática única. Cada variável é atribuída exatamente uma vez, e as funções phi em pontos de junção selecionam entre as definições que as atingem. A construção deles tem duas etapas. A secção 5.1 coloca as funções phi usando fronteiras de domínio, e a secção 5.2 renomeia cada definição e uso com um passeio sobre a árvore dominadora.insert_phis()E ...rename()Segue as duas secções.

A lista da SSA de totalMostra o que a construção produz:

textCopyblock 0x44 -> 0x50
  ecx_1 = esi_0
  edx_1 = 0
  eax_1 = 0
block 0x50 -> 0x50, 0x5b
  eax_2 = phi(0x44: eax_1, 0x50: eax_3)
  rdx_2 = phi(0x44: edx_1, 0x50: rdx_3)
  flags_2 = phi(0x44: flags_1, 0x50: flags_5)
  flags_3 = add(eax_2, load32(rdi_0 + rdx_2 * 4))
  eax_3 = eax_2 + load32(rdi_0 + rdx_2 * 4)
  flags_4 = inc(rdx_2, 1)
  rdx_3 = rdx_2 + 1
  flags_5 = cmp(zext64(ecx_1), rdx_3)
  if jne(flags_5) goto 0x50 else goto 0x5b

A versão 0 de um registo é o seu valor na entrada. esi_0E ...rdi_0O cabeçalho do loop.0x50tem dois predecessores, o bloco de configuração e ele mesmo, então cada variável com uma definição no loop obtém um phi lá.flags_2A SSA mínima coloca-o porque...flagsO estágio 6 remove-o porque nada o lê.

O passo de renome também fixa as larguras. edx_1 = 0é uma definição de 32 bits e rdx_3 = rdx_2 + 1é de 64 bits, então o phi rdx_2O que é que é o que é o que é o que é o que é o que é o que é o que é o que é o que é o que é o que é o que é o que é o que é o que é o que é o que é o que é o que é o que é o que é o que é o que é o que é o que é o que é o que é o que é o que é o que é o que é o que é o que é.%rcxem cmpq %rdx, %rcxé de 64 bits enquanto a sua definição ecx_1 = esi_0é de 32 bits, então o uso se torna zext64(ecx_1)Cada elenco no pseudocódio final vem desta única regra.

A parte "lite" é a saída da SSA.coalesce_webs()O sistema de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de computador de

Etapa 6: Simplificar, Substituir, Remover Código Morto

optimize()O simplificador reescreve expressões de baixo para cima com estas regras:

A substituição avançada muda uma definição para seu único uso. A regra tem três condições. O uso está no mesmo bloco. O uso é uma declaração e não uma phi. Quando a definição contém uma carga, nenhuma armazenagem ou chamada fica entre a definição e o uso. Um endereço constante ou uma seção é substituído em qualquer lugar, exceto em uma phi, porque um argumento phi tem que permanecer uma variável para a web.

A eliminação de código morto elimina uma atribuição ou uma phi cujo destino não tem utilidade e cuja expressão não tem chamada.percent_changeO restanteedx_2 = dividend_1 % edi_0Está morto, então vai primeiro.edx_1 = signfill(eax_1)com uma única utilização, por isso é substituído por dividend_1 = edx_1:eax_1- Não .

A regra do par reduz entãosignfill(eax_1):eax_1- Não .eax_1, e a divisão se torna eax_1 / edi_0Agora .eax_1 = esi_1 * 100tem uma única utilização e esi_1 = esi_0 - edi_0O processo de reestruturação é um processo de reestruturação.flagsAs definições foram substituídas pelas condições de ramo e desaparecem.

cCopyreturn (param_2 - param_1) * 100 / param_1;

O multiplicador 0x66666667

gradeDivide a pontuação por 10, e o clang emite não.idiv- Ele emite .imulq $0x66666667, %rax, %rax, entãosarq $0x22, %rcx- Então, em uma cópia.shrq $0x3f, %raxO compilador escolhe um multiplicador.mE um turno .s- Para cada um .xna faixa, (x * m) >> sdeve ser igual x / d- Não .

Aqui .m = 0x66666667 = 1717986919E ...s = 34A matemática confirma:2^34 / 10 = 1717986918.4, e o teto é1717986919O erro é:m * 10 - 2^34 = 6Para que a identidade seja mantida em cada 32 bits .x, os tempos de erro 2^31Deve ficar abaixo.2^34, então o erro deve ser no máximo 8.(x * m) >> 34- É igual .floor(x / 10)para cada não negativo int- Não .

Para negativo xO piso gira para longe do zero enquanto o C gira para o zero. shrq $0x3fExtrae o bit de sinal do produto, que é 1 exatamente quando xAdicioná-lo corrige o arredondamento.

magic_divisor(m, s)Teste um par candidato.dcomo o coeficiente inteiro de 2^sPormE tenta .dE ...d + 1Aceita um .dSó quandomé igual ao limite máximo de 2^s / de o erro ligado mantém. O mesmo multiplicador com s = 33dád = 5, o que é correto, porque 0x66666667é também o teto de 2^33 / 5Um teste verifica a identidade contrac_div(x, 10)Em 2.406 valores incluindo os dois extremos daint- O alcance.

Com reconhecimento,gradelê ecx_1 = param_1 / 10 - 6;Com o reconhecimento desligado, a demonstração imprime o formulário bruto:

cCopyrax_1 = (long)param_1 * 0x66666667;
ecx_1 = (int)(rax_1 >> 34) + (int)((unsigned long)rax_1 >> 63) - 6;

Quando você lê código de um compilador que não estudou, a forma crua é a honesta.

Fase 7: Tipos de uso

O código da máquina tem largura e não há tipos. infer_types()Uma rede cujas definições são de 32 bits de largura éint, e uma web de 64 bits é longUma web que é a base de um acesso a elementosbase[idx]com elementos de 4 bytes é int *O tipo de ponteiro se espalha ao longo de cópias e phis, então local_8 = param_1- Não .-O0Faz os dois .int *. O tipo de devolução é a largura do valor no return- Declarações.

O resultado para totalÉ o que éint total(int *param_1, int param_2)Ghidra escreveu:int total(long param_1,uint param_2)O levantador usou a carga em escala como prova de ponteiro.*(int *)(param_1 + uVar2 * 4)Nem sequer conseguem ver .constE nem um nem outro sabe .int *deunsigned *- Não .

Lee, Avgerinos e Brumley (TIE, NDSS 2011) frame type recovery como solução de restrição sobre uma rede. O resultado é um limite superior e inferior em vez de uma conjectura. Noonan, Loginov e Cok (Retypd, PLDI 2016) adicionam polimorfismo e recorrência.constA lição de "Paperback" é uma lição que usa as duas regras mais baratas da linha de trabalho e chama o que não pode ver.

A aritmética não assinada é mantida nas expressões e não nos tipos de variáveis. jaDepoiscmpl $0x4, %ecximpressões como (unsigned int)ecx_1 > 4, e shrqimpressões como (unsigned long)rax_1 >> 63As variáveis permanecem assinadas para que o leitor veja o valor do registo e o único lugar onde a instrução o trata como não assinado.

Fase 8: Estruturação a partir do gráfico

Cifuentes (1994), capítulo 6, corresponde regiões do gráfico às formas de uma linguagem de alto nível. Os loops vêm primeiro (6.6.1), depois os condicionalismos bidirecionais (6.6.2), depois os condicionalismos n-direita (6.6.3). Yakdan, Eschweiler, Gerhards-Padilla e Smith (NDSS 2015) tomam a outra estrada. Eles derivam a condição sob a qual cada nó executa e construem a estrutura a partir dessas condições, sem formas fixas. A motivação deles é uma medida. Hex-Rays em uma amostra produzida 1.571 gotoAs declarações em 49.514 linhas, uma por 32 linhas, e a sua estruturação não produziram nenhuma das 1.530 funções de núcleo.

structure()É um pequeno membro da primeira família. Precisa de dois fatos a partir da fase 2.BranchO limite de fundo é uma borda de um bloco que domina sua fonte. O ciclo natural é o conjunto de blocos que chegam à fonte de fundo sem passar o cabeçalho.

Para um Branchcom joão j- Não .

• Sejé o alvo de salto, emitirif (!cond) { fallthrough region }e continuar emj- Não .
• SejÉ a queda, emitirif (cond) { target region }e continuar emj- Não .
• SejÉ a saída da função, ambos os braços retornam.if (cond) {... }E o outro braço depois dele, sem um elseEste é o regresso precoce depercent_changeE ...total- Não .
• Caso contrário , emitir .if (cond) { target } else { fallthrough }e continuar emj- Isto é ...percent_change- Não .-O0, onde ambas as armas armazenamlocal_4E encontramo-nos no epílogo.

Para um cabeçalho de loop:

• Se o cabeçalho termina em um Branchcom um sucessor fora do circuito, emitir while (cond) { body }- Não .total- Não .-O0tem esta forma: o cabeçalho compara local_14comlocal_ce folhas emjge- Não .
• Se o cabeçalho é também o bloco com a borda traseira, ou o fechamento sai em vez disso, emitir do { body } while (cond);- Não .total- Não .-O1tem esta forma: bloco 0x50Adiciona, aumenta, compara e salta para si mesmo.

Um IndirectJumpAcaba um bloco sem sucessores.grade- Não .-O0É uma mesa de saltos.jmpq *%raxatravés de cinco compensações relativas em .rodata+0x0Aqui o elevador imprime uma nota em vez disso.0x76- Não .0x7f- Não .0x88, e 0x91O laboratório de prática acrescenta que os dados de um grupo de dados de um grupo de dados são obtidos apenas através do salto indireto e não foram levantados.switch- Não .

O que o -O1 fez ao interruptor

• Não .-O1O Clang não guardou uma mesa de salto para ograde- Ele calculou .score / 10 - 6E comparou o resultado com 4 como um número não assinado.int- Não ..rodata+0x14A comparação sem assinatura é uma instrução que abrange ambas as partes .score / 10 < 6E ...score / 10 > 10Uma diferença negativa é um grande valor não assinado, por isso falha no mesmo cheque.

A mesa aguenta .1, 2, 3, 4, 4para os coeficientes 6 a 10.switchcom cinco returnAs declarações tornaram-se umaifO elevador emite exatamente isso e chama a mesa.lookup_14após a sua secção de compensação.

O comprimento da mesa é heurístico.table_values()Leia da tabela de início para a próxima .rodataO que é que é?.textReferências de realocação, ou ao final da seção. Neste objeto, o próximo offset referido é 0x28, a tabela de grade_label- Então ...lookup_14- Não .(0x28 - 0x14) / 4 = 5A comparação sem assinatura com 4 concorda. Ghidra também não sabe o comprimento.*(uint *)(&DAT_001000b4 + (ulong)uVar2 * 4), um endereço de byte mais um offset, e deixou os cinco valores para o leitor olhar para cima.

Junto com Ghidra

A demonstração imprime cada par.code/fixtures/ghidra/*.jsonOs registos da prova mostram que a rea voltou em 2026-10-14.npx -y rea-agents@6.5.0 decompile ledger-x86_64-O1.o <function> --provider ghidra --format jsonCada disco tem umconfidence: observedE ...authority: shipped-artifactO texto é observado. As alegações dentro do texto são derivadas, e os registos não dizem quais.

%_change

textCopylifter                                         | ghidra
-----------------------------------------------+-----------------------------------------------
int percent_change(int param_1, int param_2)   | undefined1  [16] percent_change(int param_1,int param_2,ulong param_3)
{                                              | {
  if (param_1 == 0) {                          |   long lVar1;
    return 0;                                  |   undefined1 auVar2 [16];
  }                                            |   undefined1 auVar3 [16];
  return (param_2 - param_1) * 100 / param_1;  |   if (param_1 != 0) {
}                                              |     lVar1 = (long)((param_2 - param_1) * 100);
                                               |     auVar3._0_8_ = lVar1 / (long)param_1 & 0xffffffff;
                                               |     auVar3._8_8_ = lVar1 % (long)param_1 & 0xffffffff;
                                               |     return auVar3;
                                               |   }
                                               |   auVar2._8_8_ = 0;
                                               |   auVar2._0_8_ = param_3;
                                               |   return auVar2 << 0x40;
                                               | }

A versão reparada em code/fixtures/ghidra/ledger-x86_64-O1.ghidra-repaired.cO teste é feito com a fonte de 81 pares de entradas.

grau

textCopylifter                                         | ghidra
-----------------------------------------------+-----------------------------------------------
static const int lookup_14[5] = {1, 2, 3, 4, 4}; | uint grade(int param_1)
int grade(int param_1)                         | {
{                                              |   uint uVar1;
  int eax_1;                                   |   uint uVar2;
  int ecx_1;                                   |   
                                               |   uVar2 = param_1 / 10 - 6;
  ecx_1 = param_1 / 10 - 6;                    |   uVar1 = -(param_1 >> 0x1f) ^ (uint)((ulong)((long)param_1 * 0x66666667) >> 0x3f);
  eax_1 = 0;                                   |   if (uVar2 < 5) {
  if ((unsigned int)ecx_1 <= 4) {              |     uVar1 = *(uint *)(&DAT_001000b4 + (ulong)uVar2 * 4);
    eax_1 = lookup_14[(unsigned long)(unsigned int)ecx_1]; |   }
  }                                            |   return uVar1;
  return eax_1;                                | }
}                                              |

Total

textCopylifter                                         | ghidra
-----------------------------------------------+-----------------------------------------------
int total(int *param_1, int param_2)           | int total(long param_1,uint param_2)
{                                              | {
  int eax_1;                                   |   int iVar1;
  int ecx_1;                                   |   ulong uVar2;
  long rdx_1;                                  |   
                                               |   if (0 < (int)param_2) {
  if (param_2 <= 0) {                          |     uVar2 = 0;
    return 0;                                  |     iVar1 = 0;
  }                                            |     do {
  ecx_1 = param_2;                             |       iVar1 = iVar1 + *(int *)(param_1 + uVar2 * 4);
  rdx_1 = 0;                                   |       uVar2 = uVar2 + 1;
  eax_1 = 0;                                   |     } while (param_2 != uVar2);
  do {                                         |     return iVar1;
    eax_1 = eax_1 + param_1[rdx_1];            |   }
    rdx_1 = rdx_1 + 1;                         |   return 0;
  } while ((unsigned long)(unsigned int)ecx_1 != rdx_1); | }
  return eax_1;                                |
}                                              |

O teste de comportamento compilou o texto Ghidra para gradeE ...totalNão mudou, adiciona dois.typedefLinhas e definição de DAT_001000b4dos vinte bytes em .rodata+0x14Ambas as funções correspondem à fonte na grade.

O que a pesquisa diz sobre a leitura de pseudocódios

LLM4Decompile (EMNLP 2024) avaliou Ghidra sozinho em 20,12% de re-executabilidade em HumanEval-Decompile. Cerca de uma em cada cinco funções recompilou e passou as afirmações que vêm com o índice de referência. Refinando a produção da Ghidra com o modelo 6.7B, elevou isso para 52,74%. DecompileBench (Findings of ACL 2025) executou seis decompiladores industriais e seis abordagens de LLM em 23.400 funções de 130 programas. Os resultados do LLM foram melhores e tiveram uma correcção de funcionalidade 52,2% menor.

Liu, Raff e Micinski (arXiv 2609.05370, setembro 2026) explicam a lacuna. Usaram 300 funções de biblioteca do GitHub e 287 funções baseadas em CVE. O modelo de refinamento mais forte aumentou a taxa de construção de Ghidra de 75 para 90 por cento, enquanto a taxa de correspondência comportamental caiu de 74 para 62 por cento. Os candidatos que passaram em todos os testes no índice de referência ainda divergiram em entradas confusas. Isso aconteceu em 4,9% dos casos em oito sistemas, e até em 13% para um sistema. Até um décimo das vulnerabilidades reveladas desapareceram do código refinado.

As causas que eles rastream são simples: campos, tipos, calles e guardas inventados substituíram os desconhecidos visíveis que o decompiler havia deixado no texto.

É por isso que o elevador imprime .(unsigned long)(unsigned int)ecx_1Imprime uma nota em vez de um "switchpara o salto não resolvido, e lookup_14Em vez de uma etiqueta um modelo inventaria.code/main.py- Ghidra's.undefined1 [16]É feio e honesto.int percent_change(int, int)O mesmo modelo produzirá uma assinatura errada na próxima função.

Construí-lo

Executa a demonstração:

bashCopycd phases/13-tools-and-protocols/34-lifting-to-pseudocode
python3 code/main.py

A demonstração decodifica as quatro funções do -O1Objeto e compara cada instrução com o cometido llvm-objdump- Não, não.percent_change- Não .grade, e totalImprime o IR antes do SSA, a listagem do SSA com funções phi e o pseudocódio ao lado do texto Ghidra.gradecom o reconhecimento de divisão desligado, o -O0versões de percent_change- Não .total, e grade_label, e um resumo:

jsonCopy{
  "functions": ["grade", "grade_label", "percent_change", "total"],
  "instructions": 56,
  "blocks": {"percent_change": 3, "grade": 3, "total": 5, "grade_label": 4},
  "phis": {"percent_change": 0, "grade": 1, "total": 2, "grade_label": 1},
  "objdumpDifferences": 0
}

Leia code/main.pyna ordem seguinte:

1. read_object()Leia os cabeçalhos da secção, a tabela de símbolos e o .relaSeções de um objeto ELF64 realojável.
2. decode_one()E ...render_att()Descifrar uma instrução e imprimir-a no caminho llvm-objdump- Não, não.
3. build_blocks()- Não .immediate_dominators(), e dominance_frontiers()Construir os fatos gráficos.
4. lift_insn()transforma uma instrução em declarações de IR e resolve as realocações.
5. insert_phis()E ...rename()Construir SSA e inserir lançamentos de largura.
6. make_simplifier()- Não .substitute_once(), e remove_dead_code()Correr para dentro .optimize()- Não .
7. collect_params()- Não .coalesce_webs(), e infer_types()nome e digitar as telas.
8. structure()compost_dominators()E ...natural_loops()emite o corpo C.
9. lift_function()liga os estágios e lift_all()Levanta um objeto inteiro com assinaturas de callee.

Usá-lo

Para levantar uma função de seu próprio objeto, construí-la com clang -target x86_64-unknown-linux-gnu -ce ligar .lift_all(read_object(path))Quando o decodificador levantarDecodeError, leia o byte de código optico da mensagem e encontre-o no mapa de código optico SDM. Adicione uma entrada às tabelas no topo do arquivo. Quando o elevador eleva em um mnemônico, adicione uma regra para lift_insn()Quando o estruturador emite umgoto, imprimir o gráfico com IrPrinterCada adição é pequena e cada uma é controlada contrallvm-objdumpOu clang pelos testes existentes.

Quando o Ghidra estiver instalado, execute rea na mesma função e coloque os dois textos lado a lado. Preencha a tabela de diferença antes de acreditar em qualquer texto. Uma diferença com uma instrução por trás dela é uma escolha de apresentação. Uma diferença sem instrução por trás dela é uma adivinhação, e a adivinhação pode ser de ambos os lados.

Laboratório Interativo

Laboratório A: uma função através de cinco etapas

• Docodediretório, Python aberto:

bashCopycd phases/13-tools-and-protocols/34-lifting-to-pseudocode/code
python3 -q

• Correr .

pythonCopyfrom main import *
obj = read_object(FIXTURES / "ledger-x86_64-O1.o")
lifted = lift_function(obj, "percent_change")
for insn in lifted.decoded: print(f"0x{insn.address:x}: {insn.raw.hex(' ')}  {insn.att()}")
print(lifted.ir_text)
print(lifted.ssa_text)
print(lifted.pseudocode)

Segue-me .%esidesubl %edi, %esi- Não .esi_1 = esi_0 - edi_0- Não .(param_2 - param_1)O byte .feé o ModR/M do subl, com mod = 11- Não .reg = edi, e r/m = esi- Não .

Laboratório B: o idioma da divisão

pythonCopyprint(lift_function(obj, "grade", recognize_division=False).pseudocode)
print(magic_divisor(0x66666667, 34), magic_divisor(0x66666667, 33), magic_divisor(0x66666667, 31))

A primeira linha imprime o multiplicar bruto e as mudanças.10 5 NoneDescubra por que o mesmo multiplicador divide por 5 com um turno a menos e por que o turno 31 não consegue a linha de erro.

Laboratório C: um novo objeto para o decodificador

Construir o dispositivo em -O2E levantá-lo:

bashCopyclang -target x86_64-unknown-linux-gnu -O2 -fno-asynchronous-unwind-tables -c fixtures/ledger.c -o "$TMPDIR/ledger-O2.o"
python3 -c 'from main import *; from pathlib import Path; import os; lift_all(read_object(Path(os.environ["TMPDIR"]) / "ledger-O2.o"))'

O decodificador termina em 0x56comopcode 81 is outside the fixture subset- Código de opção .81é o formulário do grupo 1 com um instantâneo de 32 bits.andl $0x7ffffff8, %edx, e Clang usou-o no ciclo vectorizado de total- Adicione-o ao lado .0x83em decode_one()O subconjunto aumenta uma entrada por vez e cada entrada é verificada contra llvm-objdump- Não .

Laboratório D: Valor padrão de Ghidra em grau

pythonCopyprint(ghidra_pseudocode("grade"))
for score in (-25, 0, 59, 60, 100, 115):
    sign = -(score >> 31)
    product_sign = ((score * 0x66666667) & ((1 << 64) - 1)) >> 63
    print(score, sign ^ product_sign)

Cada linha imprime 0, Ghidra uVar1A expressão é correta e ilegível, e a instrução xorl %eax, %eaxDiz-o em dois bytes.

Laboratório de Prática

Adicionarswitchrecuperação para grade- Não .-O0- Não .

Requisitos:

• Leia as cinco mudanças em .rela.rodatadeledger-x86_64-O0.o, cada um R_X86_64_PC32.text+offset, e calcular os cinco objetivos do caso a partir da tabela em .rodata+0x0- Não .
• Adicionar umSwitchO terminal para o IR com a expressão do índice, a lista de alvos e o padrão do jaantes da carga da mesa.
• Dê ao bloqueador um sucessor por alvo para que os dominadores, os pos-dominadores e o SSA continuem a trabalhar.
• Emiteswitch (local_10) { case 0:... }com um .casepor alvo e o epílogo compartilhado após a união.
• Mantenha a nota para qualquer salto indireto cuja mesa não possa ser amarrada.
• Compile o resultado com clang e compare-o com a fonte sobre a grade de pontuação nos testes.

O sucesso significagrade- Não .-O0E ...grade- Não .-O1produzir a mesma saída sobre a rede, com um switchE não .goto- Não .

Artifacto

Esta lição produzoutputs/skill-lifting-to-pseudocode.md. Utilize-o para levantar uma função com uma derivação para cada linha e para preencher a tabela de diferença contra o texto de um decompilador.

Verifique

Execute a demonstração e a suíte determinista:

bashCopycd phases/13-tools-and-protocols/34-lifting-to-pseudocode
python3 code/main.py
python3 -m unittest discover -s code/tests -v

A suite tem 25 testes.

• O decodificador concorda com o comprometido llvm-objdumptexto em cada instrução de ambos os objetos, e com um vivo llvm-objdumpquando está instalado
• REX, ModR/M, SIB e o offset de campo de deslocamento de leaq (%rip), %rcxsão decodificados como descrito no MDS
• um código op fora do subconjunto aumenta DecodeErrorEm vez de adivinhar
• O leitor do ELF lista as quatro funções e as três .textRealocações
• totalTem cinco quarteirões.0x44Domina .0x50, e 0x50é um cabeçalho de loop com a si mesmo como o corpo
• %rdiE ...%rsiTornar-separam_1E ...param_2, e param_1em totalÉ o que éint *
• testE ...cmpcomje- Não .jle- Não .ja, e jgeTornar-se==- Não .<=Não assinado .>, e <
• SSA coloca duas funções Phi ao vivo no cabeçalho do loop de totalE nenhum em .percent_change
• O pseudcódigo de percent_change- Não .grade, e totalé igual ao texto esperado
• gradelê param_1 / 10 - 6com reconhecimento e multiplicação bruta com reconhecimento
• 0x66666667com o turno 34 dividido por 10, com o turno 33 dividido por 5, e a identidade mantém-se na grade
• - Esposas em pilha-O0Tornar-selocal_4- Não .local_8- Não .local_c, e o marcador de quadro nunca aparece
• A mesa em .rodata+0x14lê 1, 2, 3, 4, 4através da realocação
• O salto indireto emgrade- Não .-O0é relatado com os seus quatro blocos não levantados
• Os aparelhos Ghidra contêm o retorno de 16 bytes, o param_3, o não simplificado .xor, e o long param_1
• As seis unidades emitidas compilam com clang -std=c11 -Wall -WerrorParax86_64-unknown-linux-gnu
• As funções levantadas, o texto Ghidra reparado e a fonte imprimem as mesmas 232 linhas sobre a grade de entrada

Modos de falha de produção

Regra de funcionamento

Trate o pseudocód como uma derivação que você não viu. Reproduzir a partir das instruções com um elevador que você pode ler. Coloque os dois textos lado a lado, e escreva a instrução ou a adivinha atrás de cada linha que difere. Compile ambos e corre ambos contra a fonte quando você tem. Uma linha sem instrução atrás dela permanece uma adivinha, não importa o quão limpo ele lê.

Mais leitura

• Intel SDM Volume 2, chapter 2, Instruction Format
• System V AMD64 psABI, section 3.2, Function Calling Sequence
• Cytron et al., Efficiently Computing Static Single Assignment Form and the Control Dependence Graph, TOPLAS 1991
• Cooper, Harvey, Kennedy, A Simple, Fast Dominance Algorithm, 2001
• Cifuentes, Reverse Compilation Techniques, PhD thesis, QUT 1994
• Yakdan et al., No More Gotos, NDSS 2015
• Granlund, Montgomery, Division by Invariant Integers using Multiplication, PLDI 1994
• Lee, Avgerinos, Brumley, TIE, NDSS 2011
• Noonan, Loginov, Cok, Polymorphic Type Inference for Machine Code, PLDI 2016
• LLM4Decompile, EMNLP 2024
• DecompileBench, Findings of ACL 2025
• Liu, Raff, Micinski, When LLM Decompilers Recompile More and Preserve Less, 2026
• rea 6.5.0 Ghidra provider notes
• rea 6.5.0 fonte em tag 3b79af2que esta lição descreve: src/domain/functionComparisonDimensions.ts- Não .website/evidence/dx-ball-sound-pan.md- Não .

This free lesson is part of the AI Engineering from Scratch curriculum. Read the full explanation, run the lesson code, and verify the result in the interactive reader or from the repository source.

Browse the complete course catalog or open this lesson on GitHub.