Phase 13: Tools & Protocols

Differencia binaria y ejecución simbólica: función de coincidencia y solución de entradas

Type: Build

Languages: Python, C, x86-64 assembly, Java (one Ghidra script)

Prerequisites: Phase 13 · 33 (disassembly and control flow), 34 (lifting to pseudocode), 36 (rebuild and prove equal)

Time: ~150 minutes

Objetivos de aprendizaje

• Construye cinco firmas de funciones de un objeto y su listaje: bytes exactos, bytes con campos de reubicación enmascarados, secuencia mnemónica, forma de flujo y nombre del símbolo.
• Ejecutar un juego codicioso en escena en el estilo BinDiff, donde una firma coincide solo cuando es única en ambos lados, y grabar el escenario y la calidad detrás de cada partido.
• Reproduce el caso en el que dos funciones idénticas de byte falten un correlador de byte en imágenes cargadas y lo pase después de la mascarada, con la aritmética de reubicación que explica los cuatro bytes cambiados.
• Reproduce las relaciones de similitud de radiff2 desde la distancia de Levenshtein y explique por qué una relación sólo aparece cuando la comparación utiliza los 82 bytes de radar2 alcanzados.
• Enumera las rutas de una función en un pequeño IR, lleva una condición por ruta y resuelve cada hoja para entradas con una búsqueda limitada.
• Medir la explosión de la trayectoria en un bucle con un límite simbólico y comparar los recuentos, clases y modelos con angr 10.0.3 y z3 5.1.0.

El problema

Usted reconstruyó .ledger.cEn el-O2y preguntó a un agente si algo cambió desde el-O1El agente hizo un difer y informó quegradeEl programa de programación de la red de datos de la red de datos de la red de datos de la red de red de datos de la red de red de datos de la red de red de red de datos de la red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de red de redgradeLas imágenes comparadas después de la reubicación son idénticas en los dos archivos objetos..rodatase encuentra 0x70 bytes más adelante en el -O2programa, por lo que un desplazamiento en gradecreció en 0x70.

La misma tarde que preguntaste qué puntaje ganagradeLa función devuelve 4 para cada puntaje de 90 a 109, y la pregunta no tenía límite, por lo que la respuesta del agente era una muestra donde necesitabas un conjunto.

Las dos fallas provienen de la misma brecha. Una coincidencia y una entrada resuelta son cada una una reclamación con un método detrás de ella. Esta lección construye los dos métodos en Python y ejecuta las herramientas de producción al lado de ellos. Cuando las herramientas y el código coinciden, tienes dos derivadas. Cuando no coinciden, tienes una dirección, un byte o un vínculo para mirar.

Una firma de función es una reivindicación de calidad

Flake enmarcó la diferencia binaria en 2004 como la construcción de un isomorfismo entre los conjuntos de funciones de dos ejecutables similares. Dullien y Rolles lo extendieron en 2005 a bloques y instrucciones básicas. La página de conceptos de BinDiff describe la estrategia que salió de ese trabajo. Computa un atributo para cada función en ambos lados. Un valor que aparece exactamente una vez en cada lado es una coincidencia. Un valor que aparece más de una vez es ambigüo y se abre el siguiente atributo dentro de esa clase de equivalencia. Un valor sin contraparte se mantiene sin igual. Después de cada paso, los llamadores y llamados de nuevos partidos forman pequeños conjuntos donde es probable que el siguiente atributo sea único, y el proceso se repite con el siguiente atributo.

Cada algoritmo de coincidencia tiene una cualidad. La página clasifica la coincidencia hash de bytes de función bruta y la coincidencia hash de nombre como muy buena, el índice MD del gráfico de flujo y la coincidencia de firmas primas (cada mnemónica un pequeño primer, producto sobre la función) como buena, las referencias de cadena como medio y el recuento de bucles o secuencia de direcciones como pobre. La confianza de una coincidencia es la calidad promedio de los algoritmos que la producen, ponderada por un sigmoide. La similitud de la función es de aproximadamente 25% de los bordes de flujo-grafo coincidentes, 15% de los bloques básicos coincidentes, 10% de las instrucciones coincidentes y 50% de la diferencia en el índice MD del flujo-grafo, multiplicado por la confianza.

Esta lección mantiene cinco de esos atributos y la única regla que importa: único en ambos lados o no coincide. Se deja de lado el índice MD, porque las páginas de conceptos lo nombran sin una fórmula, y utiliza una secuencia de grados simples en su lugar. Las etiquetas de calidad permanecen, porque un coincidencia es tan buena como el hecho más débil que la produjo.

Cinco firmas de un registro de funciones

El diferencial lee dos cosas por objeto. El ELF da bytes, tamaños de símbolos y .rela.*Los registros.llvm-objdump -dLa lista da límites de instrucción y mnemónica, y la lección 33 demostró un decodificador igual a la lista en cada instrucción de estos objetos. function_record()verifica que los bytes de cada instrucción en la lista son iguales a los bytes del objeto en esa dirección y aumenta de otra manera.

¿ Qué ?gradeEn elledger-x86_64-O1.oEl símbolo dice que se compensa 0x10 y tamaño 46, por lo que el registro cubre 0x10 a 0x3e y excluye el de dos bytes nopque alinea la siguiente función.

La firma de bytes exactos es la SHA-256 de los 46 bytes. La firma de bytes enmascarados cero primero cada campo de reubicación. Hay un campo: el registroR_X86_64_PC32 .rodata+0x10en el desplazamiento 0x36, cuatro bytes de ancho, el desplazamiento de la leaq (%rip), %rcxEn un objeto RELA esos cuatro bytes ya tienen cero, por lo que las dos firmas coinciden en cada función de cada objeto aquí.

La firma mnemónica hashes la secuencia de 14 mnemónicos:

movslq imulq movq sarq shrq addl addl xorl cmpl ja movl leaq movl retq

La firma de forma del gráfico de flujo proviene de los bloques básicos y los bordes tipografados de la lección 33, restringidos a los bloques que la entrada puede alcanzar. gradeEn el-O1Tiene tres bloques y tres bordes.ja 0x3dCon un borde tomado y un borde de caída, el bloque 0x31 cae a través de 0x3d, y 0x3d devuelve. La secuencia de grados enumera (en, fuera) por bloque en orden orden ordenado, por lo que la firma se lee 3b 3e [0/2,1/1,2/0]- Para .gradeEn el-O0El registro resuelve el salto indirecto a través de los cinco .rela.rodataLas entradas son exactamente como lo hizo la lección 33, que da ocho bloques y once bordes con cuatro tablelos bordes.

La firma del nombre es el nombre del símbolo, es el hecho más fuerte cuando existe y nada cuando se despoja la construcción.

Un campo más se corre para el caso de parche más tarde.leatraslado a la.rodata, un control de límites, y una carga indexada,referenced_table()lee la tabla de la manera que la lección 36 hizo: el cmpl $0x4antes dejada cinco entradas y la carga movl (%rcx,%rax,4), %eaxDa cuatro bytes cada uno.gradeEn el-O1la mesa en .rodata+0x14Leía1, 2, 3, 4, 4¿ Qué ?

El codicioso empate

match_functions()El juego registra la etapa, la calidad de la etapa, cada otra firma que también coincide y una relación de similitud.

for stage in order:
    for signature, candidates in left_groups.items():
        partners = right_groups.get(signature, [])
        if len(candidates) != 1 or len(partners) != 1:
            continue
        a, b = candidates[0], partners[0]
        agreeing = [s.id for s in STAGES if a.signatures()[s.id] == b.signatures()[s.id]]
        matches.append(Match(a, b, stage, agreeing, radare2_ratio(a.raw, b.raw), data_equal))

El orden de las lecciones es el primero de las cuatro etapas estructurales y los nombres son los últimos, por lo que las etapas estructurales se prueban y los nombres los clasifican después.-O1contra-O2¿Qué es esto ?

totalEl clang vectorizó el bucle con SSE2 y mantuvo un bucle escálar restante. Su forma pasó de cinco bloques y cinco bordes a diez bloques y trece bordes. Nada estructural sobrevive, y sólo el símbolo une los dos.

Para-O0contra-O1el mismo orden produce una coincidencia incorrecta:

percent_changeEn el-O0es un diamante de cuatro bloques: una entrada que se ramifica en before == 0, dos brazos, y una unión que regresa.0/2, 1/1, 1/1, 2/0- ¿ Qué ?grade_labelEn el-O1¿ Qué ?gradeLa forma es única en ambos lados y la regla lo acepta. La etiqueta de calidad media es la advertencia, y el nombre de etapa, ejecutado después, contradice.grade_labela la derecha, así que la verdadera percent_changey grade_labelLos pares permanecen sin igual.

El orden BinDiff ejecuta la coincidencia de nombres como la segunda etapa en la que existen nombres reales, y BINDIFF_ORDEREn el código hace lo mismo.-O0las funciones coinciden con sus -O1Las versiones por nombre, que es el resultado Ghidra informa a continuación. La lección mantiene ambos órdenes en la demostración para que el fracaso sea visible.ify elseque se une antes del regreso.

Bytes idénticos, operandos reubicados

Ghidra aplica relocaciones cuando importa un objeto. su correlador de byte compara imágenes cargadas y lección 36 campos de relocalización enmascarados por esta razón. load_image()Reproduce la importación.sh_addralign, y los establece desde 0x100000. Luego aplica cada registro:S + A - Pescrito como un valor de 32 bits firmado para R_X86_64_PC32y R_X86_64_PLT32¿ Qué ?S + Acomo 64 bits para R_X86_64_64¿ Qué ?

El diseño está de acuerdo con Ghidra 12.1.4 en cada sección de inicio en ambos programas, que la suite de pruebas verifica con la salida de seguimiento de versión capturada:

.textes 112 bytes más largo en -O2, el crecimiento de total, así que.rodatacomienza 0x70 bytes más adelante. gradeSe encuentra en 0x100010 en ambos programas.leaqEn el desplazamiento 0x33 tiene su campo de desplazamiento en 0x36 y termina en 0x3a..rodata+0x14¿ Qué ?

En el-O1imagen: 0x1000a0 + 0x14 - 0x10003a = 0x7a = 122En el-O2imagen: 0x100110 + 0x14 - 0x10003a = 0xea = 234Los bytes de campo son7a 00 00 00en una imagen y ea 00 00 00En el otro, un byte de 46 difiere, la relación de Levenshtein es de 0,978, y la etapa de bytes exactos falla.grade_labelse desplaza por el mismo 0x70 que su tabla, por lo que sus desplazamientos se mantuvieron iguales y pasa bytes exactos en ambas vistas.

Ghidra informa de la misma división.-O1contra-O2, Función exacta Bytes Match encontrado percent_changey grade_label, Exact Function Instructions Match encontró esos dos másgradeLa correlación de instrucciones enmascara las operandas, que cubre el desplazamiento. La vista de imagen de la lección da coincidencias de bytes exactos para exactamente las dos funciones que el correlador de bytes de Ghidra encontró y el acuerdo de bytes enmascarados para exactamente las tres que su correlador de instrucciones encontró.

Las rea 6.5.0 compare_functionsEl texto del proveedor de line-diffs. En la dimensión de montaje se adjunta la limitación "normalización de reubicación no está disponible".

¿Qué medidas radiff2

Radar2 6.2.4 barcos radiff2- Con-ACAnaliza los archivos y imprime una fila por función: el tamaño izquierdo y la dirección, MATCH o UNMATCH, una relación, y el tamaño correcto y la dirección.

La proporción en la fuente de radar2 es 1 - distance / max(len_a, len_b), donde la distancia es la distancia de Levenshtein entre las dos huellas dactilares de la función y una huella dactilar es la concatenation de los bloques básicos de la función en orden de direcciones.radare2_ratio()En elcode/main.pyImplementa la misma fórmula sobre los bytes de la función en bruto y reproduce 0.130435, 0.106061, 0.269841, y 0.171429 a seis decimales.

No se reproduce en 0.426829 para gradeEn el-O0. Sobre los 118 bytes de la función la relación es de 0,296610.118Sin reubicaciones aplicadas no puede resolver la tabla de salto, por lo que su análisis llega al bloque de entrada, el bloque que termina en jmpq *%rax, el caso predeterminado, y la devolución: 82 bytes, el mismo 82 que el descenso recurrente de la lección 33 reclamó.-O1es 47, y 1 - 47/82 = 0.426829- Con-e bin.relocs.apply=trueradar2 encuentra todos los 118 bytes y impresa 0,288136, lo que equivale a la relación de la lección sobre las imágenes relocadas, donde los cuatro bytes de desplazamiento difieren de los campos cero del objeto.

-OLa información de la información de la base de datos de la base de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de datos de cuyo-O0En comparación-O1Las relaciones aumentan a 0,239130, 0,512195, 0,303030 y 0,523810, y totalEn el-O1En comparación-O2Las distancias de archivo entero también existen: -s(Myers) informa de similitud 0.956 y distancia 162 entre los dos objetos,-ss(Levenshtein) 0,927 y 137. Estos números incluyen encabezados, tablas de símbolos y secciones de reubicación y no dicen nada sobre funciones.

Correlatores de seguimiento de la versión de Ghidra

La herramienta de seguimiento de versiones de Ghidra combina un programa fuente con un programa de destino con correlatores. Los correladores de función son el Match de Bytes de Función Exactas, el Match de Instrucciones de Función Exactas (operandos enmascarados), el Match de Mnemónicas de Función Exactas y el Match de Instrucciones de Función Duplicadas (1:N y N:M). Los correladores de datos son Exact, Duplicado y Similar Data Match. Los correlatores de símbolos coinciden exactamente con los nombres, como duplicados o por similitud. Los correladores de referencia utilizan coincidencias aceptadas para encontrar más. Las funciones deben definirse en el programa de destino, y la longitud mínima de la función se establece por defecto en 10 bytes. Auto Version Tracking ejecuta el nombre exacto del símbolo, datos exactos, bytes de función exacta, instrucciones de función exacta, mnemónicas de función exacta, instrucciones de función duplicadas, luego un correlador de referencia, y crea coincidencias implícitas para las aceptadas. Se añadió un correlador BSim en el punto 11.2.

La lección capturó a los correladores sin cabeza.capture_ghidra_vt.shimportar los tres objetos en un proyecto y ejecutar ListVersionTrackingMatches.java, un guión corto que se extiendeAbstractGhidraVersionTrackingScript, abre los programas de origen y destino por camino, ejecuta los seis correladores no referentes en el orden de seguimiento de la versión automática, e imprime una línea por bloque, función, correlador y coincidencia.

Cada función cambió entre -O0y -O1En la página de ayuda se describen los correlatores exactos como similitud 1.0 y confianza 1.0, por lo que la escala de la confianza impresa es una pregunta abierta que esta lección registra y no resuelve.

Los programas de diferencias, en las herramientas, es algo diferente. Compara dos programas con el mismo espacio de direcciones en bytes, etiquetas, unidades de código, referencias, comentarios y funciones en direcciones iguales. Es un diferente alineado con direcciones y no coincide con nada que se movió.

Diafora y Ninja binario, de sus documentaciones

Diaphora es un plugin IDA Pro, lanzado por primera vez en 2015 y en la versión 3.4.2 a partir de 2026-08-18. Es AGPL-3.0 desde 2.0 y necesita IDAPython, por lo que se ejecuta en IDA Home o IDA Pro y no en IDA Free. Exporta cada base de datos a SQLite y ejecuta sus heurísticas como consultas SQL. Cada heurística tiene un nombre, una categoría de Mejor, Partial o No confiable, un tipo de relación y banderas opcionales como SAME_CPU o SLOW. Los nombres en la fuente actual se leen como las etapas de esta lección con más de ellos: hash de bytes, la misma dirección y mnemónica, la misma ensamblaje limpio, Mnemonics pequeño-primes-producto, los mismos nodos, bordes, bucles y componentes fuertemente conectados, topológico ordenar hash, y pseudo-código fuzzy hashes que necesitan el Hex-Rays descompilador. Sus notas de lanzamiento muestran el historial de sintonización: las heurísticas lentas solo funcionan por debajo de unas 2.000 funciones, y "El mismo gráfico" se trasladó a la categoría poco confiable. Ese movimiento es el diamante de cuatro bloques de esta lección, visto en escala.

Binary Ninja 6.0, lanzado 2026-09-03, añadió Binary Similarity como un marco con proveedores y resolvadores. Envía a BinDiff como proveedor estructural y WARP para coincidencias exactas de funciones que toleran operands relocables, y su guía dice que se utilice WARP cuando las funciones coinciden aparte de las instrucciones relocables y BinDiff cuando permanecen estructuralmente relacionadas después de la recompilación. La función está en la edición final sólo. Binary Ninja no tiene un gestor de paquetes instalado aquí y no se ejecutó, así que este párrafo proviene de su documentación y nada más.

BinDiff en sí mismo ha sido de código abierto desde 2023-09-25 bajo Apache-2.0, con la última versión v8. Necesita un desmonteador y el plugin BinExport, que admite IDA Pro 9.4 o posterior, Binary Ninja y Ghidra. El camino libre para un aprendiz es Ghidra más BinExport más la línea de comandos BinDiff. La lección no lo ejecutó, y su Practice Lab le pide que lo haga.

El mismo código, diferente constante

La lección 36 mantuvo un candidato a reconstruir elgradecuya tabla tiene 3 como última entrada, donde el original tiene 4. grade_case10_wrong.otiene los mismos 46 bytes de código que gradeEn el-O1El parador los empareja en bytes exactos con cada firma de acuerdo.1, 2, 3, 4, 4a través de una reubicación y 1, 2, 3, 4, 3a través de los demás y los informes dataEqual: falseLos otros tres .-O1las funciones son incomparables a la izquierda, porque el objeto candidato tiene una función.

Esta es la forma de parche-análisis. Una función diferente que se detiene en bytes dice que nada cambió. Ghidra's Exact Data Match y BinDiff's correlación de referencia de cadena existen por la misma razón. La versión de la lección es pequeña: para cada par coincidente, comparar los bytes de cada función relocaciones punto en, con el recuento de los límites de control y el ancho de la carga.

Ejecución simbólica: caminos, condiciones, soluciones

King describió la ejecución simbólica en 1976. Las entradas se convierten en símbolos. Cada declaración actualiza una tienda simbólica. Cada rama agrega una condición al camino, y un solvente decide si el camino es factible y produce una entrada concreta que lo sigue. Una función con ramas se convierte en un árbol de caminos, y una hoja es un retorno con una condición unida.

Baldoni, Coppa, D'Elia, Demetrescu y Finocchi estudiaron el campo en 2018. Su sección 5 llama la explosión de ruta como el costo central: un ejecutor puede forjarse en cada rama, por lo que el conteo de estado puede crecer exponencialmente en el número de ramas, y un bucle cuyo límite depende de una entrada simbólica da un conjunto ilimitado de caminos. Las mitigations que enumeran son poda de caminos irrealizables resolviendo en cada rama, resúmenes de funciones y bucles, estado de fusión, y sub-aproximación. La ejecución concólica ejecuta el programa de forma concreta y simbólica a la vez, registra las condiciones a lo largo de la ejecución concreta, niega una y pide al solvente la próxima entrada. DART (2005), CUTE (2005), y SAGE (2008) son los sistemas nombrados.

KLEE (Cadar, Dunbar, Engler, OSDI 2008) es una máquina virtual simbólica sobre el bitcode LLVM, por lo que su entrada es clang -emit-llvmEn los 89 programas de GNU coreutils alcanzó una cobertura de línea del 84.5% frente al 67.7% para las pruebas de los desarrolladores y encontró 56 errores graves. KLEE 3.2 fue lanzado 2025-12-23 bajo la licencia NCSA, con LLVM 16 recomendado.

Angr trabaja en binarios. angr.Projecttiene un cargador CLE que mapea el objeto y aplica reubicaciones, un elevador que convierte un bloque en VEX IR (block.vex) con código de tubería como alternativa, y una fábrica para los estados.SimStatecontiene registros, memoria y un solvente.SimulationManagerescalones de estados nombrados active¿ Qué ?deadended¿ Qué ?found¿ Qué ?avoided, y errored, y explore(find=..., avoid=...)En cada paso los motores se ejecutan en orden: fallo, syscall, gancho, unicornio para datos concretos, y VEX como la caída. claripy es el solver frente sobre Z3, y en angr 10.0 es una implementación vendida de Rust importada como from angr import claripy. angr 10.0.3 fue subido el 2026-10-10, es BSD-2-Clause, y necesita Python 3.12 o posterior. Z3 5.1.0, lanzado 2026-08-16 bajo MIT, es el solver detrás de angr, Triton y backend opcional de KLEE.

Un pequeño ejecutor sobre la lección 34 IR

El ejecutor en code/main.pyutiliza una pequeña IR con las formas de la declaración de la lección 34: Assign¿ Qué ?Branch¿ Qué ?Jump¿ Qué ?Return, más el SwitchEl terminador que el laboratorio de práctica de la lección 34 pidió.Const¿ Qué ?Var¿ Qué ?Bincon un ancho, Cast¿ Qué ?Loadde una mesa de hormigón con nombre, y Not. Las cuatro funciones de fijación se levantan a mano en el nivel que la lección 34 alcanza después de la simplificación, donde la 0x66666667multiplicarse se ha convertido en score / 10, y cada bloque IR enumera las direcciones de instrucciones de donde proviene. check_ir_against_listing()afirma que las direcciones cubren la lista de la función exactamente una vez.

gradeEn el-O0en ese IR:

0x30: local_8 = score; local_10 = score / 10 - 6; if (local_10 >u 4) goto 0x9a else 0x62
0x62: switch local_10 -> 0x91, 0x88, 0x7f, 0x76, 0x76
0x76: local_4 = 4; goto 0xa1        0x7f: local_4 = 3; goto 0xa1
0x88: local_4 = 2; goto 0xa1        0x91: local_4 = 1; goto 0xa1
0x9a: local_4 = 0                    0xa1: return local_4

Los objetivos del cambio provienen de jump_table_targets(), la misma aritmética de reubicación que la lección 33, así que el IR lee la fijación.

execute()Un estado tiene el bloque actual, el rastro de bloques, la lista de condiciones y un entorno que mapea cada variable a una expresión sobre las entradas. AssignEl medio ambiente se sustituye por la fuente y almacena el resultado. BranchSe puede encontrar una parte que el solvente no puede satisfacer, que es la poda ansiosa que describe la encuesta. SwitchLos grupos de entradas de la tabla por objetivo y bifurcaciones una vez por objetivo distinto con la disyunción de las igualdades de entrada, que es la forma en que Angr trata un objetivo de salto simbólico también. ReturnUna pista más larga que el límite de paso marca el camino truncado y lo detiene.

Sigue el camino hacia return 4La entrada asigna local_10 = score / 10 - 6- El estado de la ramalocal_10 >u 4es falso en este camino, por lo que la lista de condiciones se mantiene !(score / 10 - 6 >u 4). El interruptor entradas 3 y 4 ambos puntos en 0x76, por lo que el tenedor a 0x76 se agrega score / 10 - 6 == 3 || score / 10 - 6 == 4. Bloqueo 0x76 asigna local_4 = 4, salta a 0xa1, y el reemplazo de retorno a 4La hoja es el par de esa condición y ese valor.

El solucionador esBoundedSearch. Tiene un dominio finito por entrada, enumera el producto de los dominios y evalúa cada restricción con semántica C: 32 bits de envoltura, división truncada, comparaciones firmadas y sin firmas, y cambios aritméticos o lógicos. Una división por cero o un índice de tabla fuera de la tabla hace que esa asignación no sea la restricción.scoreen -200 a 1200 los cinco caminos de gradeEl resultado de la evaluación de cada hoja para el conjunto de entradas es:

qsignificascore / 10 - 6Las mismas clases salen degradeEn el-O1, donde el IR tiene dos caminos, el camino de la tabla regresando lookup_14[q]y el camino predeterminado devuelve 0, y la pregunta se convierte en una restricción en el valor devuelto, porque no hay un bloque de caso para alcanzar.lookup_14se lee desde el objeto .rodataen 0x14.

El límite es el límite del método. Una búsqueda limitada se completa dentro de su dominio y silenciosa fuera de él. Dentro de -200 a 1200 ningún puntaje en 60 a 109 devuelve 0 y ningún puntaje de 110 o más devuelve un valor no cero. z3 prueba ambos para todos los 2 ^ 32 puntajes, y la siguiente sección muestra donde los dos métodos devuelven diferentes testigos.

Se midió la explosión del camino

totalEn el-O1es el ciclo de la lección 33: una prueba en count, un cuerpo de bucle que agrega values[rdx]y incrementos rdx, y un jneDe vuelta al cuerpo mientrasrdx != rcxEn el IRrcx¿ Es verdad ?zext64(count)y rdxcomienza en 0. Cada paso a través de la parte posterior de la bifurcación en rdx != countconrdxuna constante, así que el camino para count = cdirige el cuerpo cTiempo y salida.countlimitado a 0 a 2, el ejecutor encuentra 3 caminos. Con 0 a 4 encuentra 5, y con 0 a 8 encuentra 9. Cada camino devuelve la suma triangular de su conteo: (0, 0), (1, 1), (2, 3), hasta (8, 36). angr informa estados 3, 5 y 9 muertos y los mismos nueve pares de conteo y suma en los tres niveles de optimización, incluyendo -O2, cuyo bucle vectorial necesita un recuento de al menos 8 y por lo tanto nunca cambia el recuento de trayectoria en este rango.

Sin ningún límite el ejecutor nunca termina, porque cada cuenta de iteraciones es un camino más factible.countEl informe da esos tres números. El costo de solución también crece: 33 evaluaciones en la línea 2, 115 en 4, 531 en 8, y 6.900 para la carrera limitada.

Angr y z3 en las mismas preguntas

capture_angr.pyCLE cargó cada objeto relocable con el backend ELF a 0x400000, aplicó 13 relocalizaciones para-O0y 8 para los demás, y resuelto los cuatro símbolos.gradecon un argumento simbólico de 64 bits, run()terminó con 5 estados en desfallecimiento en-O0y 2 en -O1y -O2, en 0,475, 0,408, y 0,318 segundos.eax == vEn el caso de los Estados miembros, el valor de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los valores de los cuyo de los cuyo de los valores de los cuyo de los valores de los cuyo de la cuenta de los valores de los valores de los cuyo de los cuyo de la cuenta de los cuyo de la cuenta de la cuenta de la cuenta de la cuenta de la cuenta de la cuenta de la cuenta de la cuenta de la cuenta de la cuenta de la cuenta de la cuenta de la cuenta de la cuenta de la cuenta de la cuenta de la cuenta de la cuenta de la cuenta de la cuenta de la cuenta de la cuenta de la cuenta de la cuenta de la cuenta de la cuenta de la cuenta de la cuenta de la cuenta de la cuenta de la cuenta de la cuenta de la cuenta de la cuenta de la cuenta devEn todos los niveles, los controles cruzados fueron completados sin ningún resultado.

El formulario de alcance de un bloque utilizó CFGFast en gradeEn el-O0, que enumera las ocho bloques de la lección 33 encontrada, entonces explore(find=0x400076)En el bloque que almacena 4. Encontró un estado con tres todavía activos en 0,47 segundos, con un mínimo de 90 y un máximo de 109 en el argumento y muestras 91, 93, 94, 97 y 101.

Parapercent_change, dos estados sin salida con las restricciones before[31:0] != 0y before[31:0] == 0. Pidiendo el estado no cero paraeax == 50¿ Qué ?before = 21055744, after = 332315210En el-O0¿ Qué ?40566804, 834296877En el-O1, y -24484867, 993934694En el-O2La búsqueda limitada en -16 a 16 respuestas .before = -10, after = -15. z3, hizo la misma pregunta sobre la lista de la lección 34, respuestas before = -25092599, after = 305712160. La suite de pruebas evalúa los cinco pares con el evaluador IR y cada uno da 50. Un modelo prueba que existe una entrada.

capture_z3.pyModelo de la-O1lista de gradeen 32 bits bit vectores con el multiplicador, los dos turnos, y la tabla, y hace cuatro preguntas más.switchPara algunas puntuaciones de 32 bits: no se ha establecido en 0,068 segundos, por lo que la función compilada es igual a la fuente en todas las entradas de 2^32. La lista difiere de la lección 36 de la puesta a punto de la lección 36: se ha establecido en la puntuación 706346536, donde score / 10Es 70634653 y el interruptor cae al estado predeterminado mientras los umbrales regresan 4. La misma diferencia restringida a 0 a 109: no satisfecha, por lo que la cuadrícula de la lección 36 no pudo verlo.percent_change¿ Qué ?before == 3con el resultado -133 se sitúa con after = 1073741823, la célula de desbordamiento de la lección 36, y la búsqueda limitada encuentra un segundo testigo dentro de su dominio,after = -1, donde (-1 - 3) * 100 / 3Truncates a -133 sin sobrecarga en absoluto.

Construye el mismo

Ejecutar la demostración:

cd phases/13-tools-and-protocols/44-binary-diffing-and-symbolic-execution
python3 code/main.py

La salida es un informe JSON. diffscontiene los archivos de objetos y las imágenes cargadas para -O0contra-O1y -O1contra-O2, más el -O0pareja en el orden BinDiff. toolComparisonpone la etapa de la lección junto al veredicto y la relación radiff2 y los correlatores de Ghidra para cada función. patch¿ Es el grade_case10_wrong.o¿Qué es esto?radare2Ratiosreproducir los números radiff2, gradeRelocationCasemuestra el diseño y los dos desplazamientos, y symbolictiene los caminos, clases y recuentos de explosiones.

Leer .code/main.pyen este orden:

1. ElfObjectLeer secciones, símbolos y .rela.*Registros.parse_listing()Leemos el llvm-objdump¿Qué es eso?
2. jump_table_targets()y build_cfg()dar bloques accesibles y bordes tipografados. FunctionRecord.signatures()construye las cinco firmas.
3. load_image()establece las secciones asignadas y se aplica S + A - Py S + A¿ Qué ?
4. match_functions()es el juego en escena. levenshtein()y radare2_ratio()dar la similitud.
5. parse_radiff2()y parse_ghidra_vt()leer las salidas de la herramienta capturadas para la comparación.
6. evaluate()¿ Qué ?substitute(), y BoundedSearchson la semántica de las expresiones y el solvente.
7. execute()Enumera los caminos. solve_returns()solicita a cada hoja un conjunto de entradas.
8. grade_ir_o0()¿ Qué ?grade_ir_o1()¿ Qué ?percent_change_ir_o1(), y total_ir_o1()son los levantadores de manos con sus direcciones de instrucción.

Hay tres órdenes más.python3 code/main.py diff A.o B.oDiferencia dos objetos cuyas listas se encuentran junto a ellos, y --imageDifere sus imágenes cargadas. python3 code/main.py paths grade O0Imprime las rutas y clases de una función, paths total 8el bucle con un límite. python3 code/main.py figure-dataImprime los datos que la figura interactiva incorpora.

Usalo

Utilice el difer y el ejecutor en este orden en dos construcciones de su propio programa.

1. Captura una lista para cada objeto y deja function_record()Verifique con los bytes, arregle la lista antes de cualquier otra cosa.
2. Difórmese primero los archivos objetos. Lea la etapa de cada coincidencia y trate las coincidencias de forma del gráfico de flujo como sugerencias hasta que una segunda firma esté de acuerdo.
3. Diferencia las imágenes cargadas. Una función que baja de bytes exactos a bytes enmascarados se mueve en relación con sus datos, y la aritmética de desplazamiento nombra la sección que se movió.
4. Para cada coincidencia, compara las tablas referenciadas. El mismo código con constantes diferentes es una función modificada.
5. Cuando la construcción tiene símbolos, ejecuta el orden BinDiff y usa el resultado estructural sólo para clasificar las etapas.
6. Cuando una herramienta informa una relación, averiguar qué bytes se metieron en ella antes de compararla con la suya.
7. Para la función cuyas entradas desea, escriba la IR con una dirección por instrucción, ejecuta execute()con un límite en cada contador de bucle simbólico, y resolver cada hoja.
8. ejecuta la misma consulta a través de angr o z3 cuando estén disponibles y compara los límites de la clase.

Laboratorio interactivo

Laboratorio A: cinco firmas a mano

Desde elcodedirectorio, Python abierto:

cd phases/13-tools-and-protocols/44-binary-diffing-and-symbolic-execution/code
python3 -q

• ¿Qué quieres decir ?

from main import *
grade = {r.name: r for r in fixture_records("ledger-x86_64-O1.o")}["grade"]
grade.raw.hex(" ")
grade.masked_bytes() == grade.raw
grade.mnemonics
grade.cfg_shape()
grade.signatures()

Escriba los cuatro bytes en el desplazamiento 0x26 de la función antes de imprimir grade.rawEntonces sigue las mismas líneas .gradede laledger-x86_64-O0.oy contar los tablelos bordes en grade.edges¿ Qué ?

Laboratorio B: ver la reubicación rompe el hash de byte

case = grade_relocation_case()
case["layout"]
case["displacements"], case["rodataShift"]
case["objectBytesEqual"], case["imageBytesEqual"], case["maskedImageBytesEqual"]

Computación0x100110 + 0x14 - 0x10003aen papel antes de leer.displacementsEntonces cambia la base enload_image()a 0x400000 y confirmar que los desplazamientos no cambian, porque ambos operandos se mueven juntos.

Laboratorio C: la coincidencia falsa y el orden que la evita

report = diff_fixtures("ledger-x86_64-O1.o", "ledger-x86_64-O2.o")
[(m.left.name, m.right.name, m.stage) for m in report.matches]
report = diff_fixtures("ledger-x86_64-O0.o", "ledger-x86_64-O1.o")
[(m.left.name, m.right.name, m.stage, m.names_agree) for m in report.matches]
report = diff_fixtures("ledger-x86_64-O0.o", "ledger-x86_64-O1.o", stages=BINDIFF_ORDER)
[(m.left.name, m.right.name, m.stage) for m in report.matches]

Impresiónrecords(...)["percent_change"].cfg_shape()por-O0y grade_labelpor-O1y leer las dos secuencias de grados. Luego escriba una sexta etapa que hashes la mnemónica ordenada, así que el orden ya no importa, y ver si se separa.

Laboratorio D: caminos y límites

report = grade_paths("O0")
[(p["trace"], p["condition"], p["returns"]) for p in report["paths"]]
report["returns"]["4"]
total_paths(2), total_paths(4), total_paths(8)
total_paths(64, step_limit=24)["truncated"]

CambiarSCORE_DOMAIN¿ Qué ?range(0, 110)y volver a correr.grade_paths("O0"). La clase para 0 se reduce a 60 entradas y los dos controles cruzados todavía se mantienen.range(90, 100)Y leer qué hojas no tienen modelo en absoluto.

Laboratorio de práctica

Ejecutar BinDiff en los fijos y compararlo con los tres resultados que ya tienes.

Requisitos:

• Instale la extensión BinExport en Ghidra 12.1.4 y exporta los tres programas de libro mayor. Graba la etiqueta de lanzamiento de BinExport y la versión de Ghidra.
• Instale la línea de comando BinDiff 8 y produzca la-O0En comparación-O1y -O1En comparación-O2resultados con la opción de similitud única.
• Captura la similitud y la confianza por función en code/fixtures/con los comandos exactos en build_fixtures.sh¿ Qué ?
• Extendersetool_comparison()con un bindiffcolumna y añadir una prueba que compara el conjunto de BinDiff coincidiendo en -O1En comparación-O2con el conjunto de bytes enmascarados de la lección.
• Escriba un párrafo que nombre el algoritmo BinDiff utilizado para gradey si comparó imágenes cargadas.

El éxito significa que la demostración imprime cuatro columnas de herramientas por función y la nueva prueba establece una igualdad o una diferencia explicada.

Lección Artefacto

Esta lección incluye outputs/skill-binary-diffing-and-symbolic-execution.md. Utilice para convertir dos builds y una función en una diferencia en etapas con una calidad declarada por partido, una explicación de cada función sin igual o cambiada, y un informe de camino con un conjunto de entradas resueltas por hoja y el límite que la produjo.

Verifique el hecho

Ejecutar la demostración y la suite:

cd phases/13-tools-and-protocols/44-binary-diffing-and-symbolic-execution
python3 code/main.py
python3 -m unittest discover -s code/tests -v

La verificación deberá demostrar:

• Las tablas de símbolos dan las cuatro funciones con tamaños 46, 118, 66, 39 en -O0, 16, 46, 31, 63 en -O1, y 16, 46, 140, 63 en -O2
• el .rela.textregistros de los -O1objeto se describe como llvm-objdump -rlas imprime
• cada instrucción en la lista está en su extensión de símbolo y sus bytes igual al objeto, y un byte cambiado aumenta
• totalEn el-O1tiene cinco bloques, cinco bordes y un bucle propio, y su cadena de forma es determinista
• gradeEn el-O0Recupera cinco objetivos de la mesa de salto de .rela.rodatay tiene ocho bloques y once bordes
• sin la mesa,gradeEn el-O0alcanza 82 bytes en cuatro bloques
• percent_changeEn el-O0y grade_labelEn el-O1tienen la misma forma de cuatro bloques
• hashes exactos y enmascarados coinciden en cada función de un objeto relocable
• -O1y -O2compartir bytes para tres funciones, -O0y -O1no comparten
• el cuadro de referencia de gradeLeía1, 2, 3, 4, 4y las lecturas del candidato.1, 2, 3, 4, 3
• los lugares del cargador .text¿ Qué ?.rodata, y .rodata.str1.1donde Ghidra los colocó en ambos programas
• R_X86_64_PC32se escribe como S + A - Py da desplazamiento 122, y R_X86_64_64las entradas en .datarecibir direcciones de cadena
• gradelos bytes coinciden en los objetos y difieren en las imágenes por un cambio de 0x70, y el enmascaramiento restaura la coincidencia
• -O1En comparación-O2coincide con tres funciones en bytes exactos y totalpor nombre; la vista de imagen coincide gradepor bytes enmascarados con similitud 1 - 1/46
• el orden de las lecciones produce una coincidencia falsa de forma del gráfico de flujo en -O0En comparación-O1, y el orden BinDiff coincide con los cuatro por nombre
• el candidato de parche coincide en bytes y no en los datos referenciados
• La relación Levenshtein reproduce 0.130435, 0.106061, 0.269841, 0.171429, 0.426829 sobre 82 bytes, y las relaciones de bytes reubicados imprimen radiff2 con reubicaciones aplicadas
• el conjunto MATCH de radiff2 es igual al paso de bytes exactos, y los correladores de byte e instrucción de Ghidra son iguales a los conjuntos exactos y enmascarados de la vista de imagen
• Ghidra sólo encontró nombres en -O0En comparación-O1, con similitud 1.0 y confianza 10.0 en cada partido
• El IR levantado a mano cubre cada instrucción enumerada una vez, y el evaluador sigue la semántica C
• gradeTiene cinco caminos en -O0con las condiciones de cambio y dos en -O1con las mismas clases
• las clases de límites 60 a 69, 70 a 79, 80 a 89, 90 a 109 de angr igual en los tres niveles y z3, con 5 y 2 estados de límite y el rango de alcance de un bloque de 90 a 109
• los dos controles cruzados no tienen modelo en el límite, en angr, o en z3, y z3 demuestra que la lista es igual al interruptor de origen
• cada unopercent_changemodelo de la búsqueda limitada, angr, y z3 evalúa al valor solicitado
• totalda 3, 5, 9 caminos con las sumas triangulares, igual a angr, y el paso de la tapa devuelve 22 y truncadas 2
• Los datos de la figura contienen las dos vistas, los números de reubicación y cinco hojas con sus conjuntos de entradas, y el módulo de sitio incorpora los mismos datos

Modos de falla de producción

Regla de funcionamiento

Compare en una firma a la vez, acepta sólo valores únicos en ambos lados, y mantenga el escenario y su calidad con el juego. Diferencia los objetos y las imágenes cargadas y explica cada función que cambia de escenario entre los dos. Enumera los caminos con un solvente en cada rama, enlace cada bucle simbólico, y informe un conjunto de entrada con su límite. Un modelo único sin límite es una muestra.

Leer más

• BinDiff concepts: matching strategy, algorithms, and quality ratings
• BinDiff repository and the v8 open-source release
• BinExport README: IDA Pro, Binary Ninja, and Ghidra exporters
• Flake, "Structural Comparison of Executable Objects" (DIMVA 2004) and Dullien, Rolles, "Graph-based comparison of Executable Objects" (SSTIC 2005), shipped in the BinDiff repository
• Diaphora README and heuristics source
• Ghidra Version Tracking correlators help page
• Ghidra Auto Version Tracking help page
• Ghidra 12.1.4 release
• Binary Ninja 6.0 "Krypton" release notesy Binary Similarity user guide
• radare2 book: radiff2y radare2 6.2.4 source
• King, "Symbolic execution and program testing" (CACM 1976)
• Baldoni et al., "A Survey of Symbolic Execution Techniques" (ACM Computing Surveys 2018)
• Cadar, Sen, "Symbolic execution for software testing: three decades later" (CACM 2013)
• Cadar, Dunbar, Engler, "KLEE: Unassisted and Automatic Generation of High-Coverage Tests for Complex Systems Programs" (OSDI 2008)y KLEE 3.2 release
• Shoshitaishvili et al., "SoK: (State of) The Art of War: Offensive Techniques in Binary Analysis" (IEEE S&P 2016)
• angr documentation: loading, simulation managers, and the simulation pipeliney angr 10.0.3 on PyPI
• Z3 5.1.0 release
• Triton dynamic binary analysis library
• System V Application Binary Interface, AMD64 Architecture Processor Supplement, Table 4.9: Relocation Types

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.