Reconocer nodos y enlaces, interpretar máscaras y automatizar consultas de análisis.
Trabaja sobre el mismo ejemplo
Selecciona este ejemplo en el companion. El número del comando corresponde al identificador original del laboratorio.
./coursectl chat 11 --example linked-listEstoy siguiendo «Listas enlazadas, enums y operaciones de bits» del curso de Lobera. Reconocer nodos y enlaces, interpretar máscaras y automatizar consultas de análisis. Dame primero una pista. Después contrasta la explicación con las instrucciones y guarda las evidencias que hayamos comprobado.
El agente y la consola comparten el estado de radare2. Preparación y funcionamiento.
Estamos a punto de terminar esta primera parte del curso.
Hoy terminaremos con la memoria dinámica tras estudiar las listas enlazadas; después pasaremos a otro tema y repasaremos las operaciones a nivel de bit, un tema sencillo pero importante, muy presente en muchos programas.
Listas enlazadas
Hasta ahora, cada vez que necesitamos trabajar con múltiples entradas de datos sucesivas tenemos que definir límites o preguntarle al usuario cuántos valores va a introducir, independientemente de si la memoria es dinámica o estática. ¿Qué pasa si queremos que el usuario siga añadiendo valores indefinidamente (hasta agotar la memoria)?
Las listas enlazadas son una forma sencilla de resolver eso. Podemos crear structs de cualquier tipo, así que ¿qué ocurre si creamos un struct que contiene un puntero a otro struct? Cada vez que añadamos un nuevo valor actualizaremos el struct anterior para que apunte al siguiente, formando una cadena. Podemos guardar una referencia al struct «anterior» mientras el usuario introduce valores; cuando termine, solo necesitaremos una referencia al primer elemento para recorrerlos todos.
// Linked list implementation in C
#include <stdio.h>
#include <stdlib.h>
// Creating a node
struct node {
int data;
struct node *next;
};
// print the linked list data
void printLinkedlist(struct node *p) {
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
}
int main() {
// Initialize nodes
struct node *head;
struct node *one = NULL;
struct node *two = NULL;
struct node *three = NULL;
// Allocate memory
one = malloc(sizeof(struct node));
two = malloc(sizeof(struct node));
three = malloc(sizeof(struct node));
// Assign data values
one->data = 1;
two->data = 2;
three->data = 3;
// Connect nodes
one->next = two;
two->next = three;
three->next = NULL;
// printing node-data
head = one;
printLinkedlist(head);
}
Como se puede ver, se crean tres nodos y luego se enlazan al final. El struct del nodo contiene un puntero a un struct del mismo tipo; puede parecer extraño porque el struct no está completamente declarado cuando ya se referencia a sí mismo, pero es perfectamente válido. También hay que tener en cuenta que NULL puede usarse como valor de fin; veremos qué significa NULL internamente.
[0x5558a1d96182]> pdf
; DATA XREF from entry0 @ 0x5558a1d9607d
┌ 167: int main (int argc, char **argv, char **envp);
│ ; var int64_t var_20h @ rbp-0x20
│ ; var int64_t var_18h @ rbp-0x18
│ ; var int64_t var_10h @ rbp-0x10
│ ; var int64_t var_8h @ rbp-0x8
│ 0x5558a1d96182 55 push rbp
│ 0x5558a1d96183 4889e5 mov rbp, rsp
│ 0x5558a1d96186 4883ec20 sub rsp, 0x20
│ 0x5558a1d9618a 48c745e00000. mov qword [var_20h], 0
│ 0x5558a1d96192 48c745e80000. mov qword [var_18h], 0
│ 0x5558a1d9619a 48c745f00000. mov qword [var_10h], 0
│ 0x5558a1d961a2 bf10000000 mov edi, 0x10 ; 16
│ 0x5558a1d961a7 e894feffff call sym.imp.malloc ; void *malloc(size_t size)
│ 0x5558a1d961ac 488945e0 mov qword [var_20h], rax
│ 0x5558a1d961b0 bf10000000 mov edi, 0x10 ; 16
│ 0x5558a1d961b5 e886feffff call sym.imp.malloc ; void *malloc(size_t size)
│ 0x5558a1d961ba 488945e8 mov qword [var_18h], rax
│ 0x5558a1d961be bf10000000 mov edi, 0x10 ; 16
│ 0x5558a1d961c3 e878feffff call sym.imp.malloc ; void *malloc(size_t size)
│ 0x5558a1d961c8 488945f0 mov qword [var_10h], rax
│ 0x5558a1d961cc 488b45e0 mov rax, qword [var_20h]
│ 0x5558a1d961d0 c70001000000 mov dword [rax], 1
│ 0x5558a1d961d6 488b45e8 mov rax, qword [var_18h]
│ 0x5558a1d961da c70002000000 mov dword [rax], 2
│ 0x5558a1d961e0 488b45f0 mov rax, qword [var_10h]
│ 0x5558a1d961e4 c70003000000 mov dword [rax], 3
│ 0x5558a1d961ea 488b45e0 mov rax, qword [var_20h]
│ 0x5558a1d961ee 488b55e8 mov rdx, qword [var_18h]
│ 0x5558a1d961f2 48895008 mov qword [rax + 8], rdx
│ 0x5558a1d961f6 488b45e8 mov rax, qword [var_18h]
│ 0x5558a1d961fa 488b55f0 mov rdx, qword [var_10h]
│ 0x5558a1d961fe 48895008 mov qword [rax + 8], rdx
│ 0x5558a1d96202 488b45f0 mov rax, qword [var_10h]
│ 0x5558a1d96206 48c740080000. mov qword [rax + 8], 0
│ 0x5558a1d9620e 488b45e0 mov rax, qword [var_20h]
│ 0x5558a1d96212 488945f8 mov qword [var_8h], rax
│ 0x5558a1d96216 488b45f8 mov rax, qword [var_8h]
│ 0x5558a1d9621a 4889c7 mov rdi, rax
│ 0x5558a1d9621d e823ffffff call sym.printLinkedlist
│ 0x5558a1d96222 b800000000 mov eax, 0
│ 0x5558a1d96227 c9 leave
└ 0x5558a1d96228 c3 ret
[0x5558a1d96182]>
El programa comienza reservando 32 bytes en la pila para variables, como se puede ver aquí; después se inicializan tres variables a cero. ¿Qué representan? ¿Por qué se inicializan a cero?
│ 0x5558a1d96186 4883ec20 sub rsp, 0x20
│ 0x5558a1d9618a 48c745e00000. mov qword [var_20h], 0
│ 0x5558a1d96192 48c745e80000. mov qword [var_18h], 0
│ 0x5558a1d9619a 48c745f00000. mov qword [var_10h], 0
Sin conocer el código original, en este punto no podríamos saber si esas variables son simplemente ints o cualquier otra cosa, pero como conocemos el código original podemos relacionarlas rápidamente con la inicialización inicial del nodo con NULL, por lo que esas variables referenciarán nuestros nodos (structs).
A continuación se llama a malloc con esas tres variables:
│ 0x5558a1d961a2 bf10000000 mov edi, 0x10 ; 16
│ 0x5558a1d961a7 e894feffff call sym.imp.malloc ; void *malloc(size_t size)
│ 0x5558a1d961ac 488945e0 mov qword [var_20h], rax
│ 0x5558a1d961b0 bf10000000 mov edi, 0x10 ; 16
│ 0x5558a1d961b5 e886feffff call sym.imp.malloc ; void *malloc(size_t size)
│ 0x5558a1d961ba 488945e8 mov qword [var_18h], rax
│ 0x5558a1d961be bf10000000 mov edi, 0x10 ; 16
│ 0x5558a1d961c3 e878feffff call sym.imp.malloc ; void *malloc(size_t size)
Malloc reserva 16 bytes para cada nodo: 4 bytes para el int y al menos 8 bytes más para el puntero al struct, además de algo de espacio adicional. Las direcciones base de esos bloques se guardan en las variables que antes se inicializaron a NULL.
0x5558a1d961cc 488b45e0 mov rax, qword [var_20h]
│ 0x5558a1d961d0 c70001000000 mov dword [rax], 1
│ 0x5558a1d961d6 488b45e8 mov rax, qword [var_18h]
│ 0x5558a1d961da c70002000000 mov dword [rax], 2
│ 0x5558a1d961e0 488b45f0 mov rax, qword [var_10h]
│ 0x5558a1d961e4 c70003000000 mov dword [rax], 3
En este punto se inicializa el campo int de esos structs con los valores 1, 2 y 3. Nótese que aquí se usa [rax], lo que indica que var_20h, var_18h y var_10h almacenan PUNTEROS a STRUCT. En la parte anterior del código, el PUNTERO se estableció a NULL, no el valor; eso es importante. Un puntero nulo, es decir, un puntero que apunta a 0x0, se considera NULL y se identifica fácilmente.
La siguiente parte del código enlaza esos structs mediante punteros:
│ 0x5558a1d961ea 488b45e0 mov rax, qword [var_20h]
│ 0x5558a1d961ee 488b55e8 mov rdx, qword [var_18h]
│ 0x5558a1d961f2 48895008 mov qword [rax + 8], rdx
│ 0x5558a1d961f6 488b45e8 mov rax, qword [var_18h]
│ 0x5558a1d961fa 488b55f0 mov rdx, qword [var_10h]
│ 0x5558a1d961fe 48895008 mov qword [rax + 8], rdx
│ 0x5558a1d96202 488b45f0 mov rax, qword [var_10h]
│ 0x5558a1d96206 48c740080000. mov qword [rax + 8], 0
Cada campo next contiene la dirección del siguiente nodo. En esta compilación empieza en el offset 8: al int de 4 bytes le siguen 4 bytes de padding para alinear el puntero. Esa separación explica los accesos a [nodo + 8].
A continuación se realiza una operación algo peculiar para pasar el primer puntero como argumento a printLinkedList.
│ 0x5558a1d9620e 488b45e0 mov rax, qword [var_20h]
│ 0x5558a1d96212 488945f8 mov qword [var_8h], rax
│ 0x5558a1d96216 488b45f8 mov rax, qword [var_8h]
│ 0x5558a1d9621a 4889c7 mov rdi, rax
│ 0x5558a1d9621d e823ffffff call sym.printLinkedlist
Inspeccionemos esa función.
[0x5558a1d96145]> pdf
; CALL XREF from main @ 0x5558a1d9621d
┌ 61: sym.printLinkedlist (int64_t arg1);
│ ; var int64_t var_8h @ rbp-0x8
│ ; arg int64_t arg1 @ rdi
│ 0x5558a1d96145 55 push rbp
│ 0x5558a1d96146 4889e5 mov rbp, rsp
│ 0x5558a1d96149 4883ec10 sub rsp, 0x10
│ 0x5558a1d9614d 48897df8 mov qword [var_8h], rdi ; arg1
│ ┌─< 0x5558a1d96151 eb25 jmp 0x5558a1d96178
│ ┌──> 0x5558a1d96153 488b45f8 mov rax, qword [var_8h]
│ ╎│ 0x5558a1d96157 8b00 mov eax, dword [rax]
│ ╎│ 0x5558a1d96159 89c6 mov esi, eax
│ ╎│ 0x5558a1d9615b 488d3da20e00. lea rdi, [0x5558a1d97004] ; "%d "
│ ╎│ 0x5558a1d96162 b800000000 mov eax, 0
│ ╎│ 0x5558a1d96167 e8c4feffff call sym.imp.printf ; int printf(const char *format)
│ ╎│ 0x5558a1d9616c 488b45f8 mov rax, qword [var_8h]
│ ╎│ 0x5558a1d96170 488b4008 mov rax, qword [rax + 8]
│ ╎│ 0x5558a1d96174 488945f8 mov qword [var_8h], rax
│ ╎│ ; CODE XREF from sym.printLinkedlist @ 0x5558a1d96151
│ ╎└─> 0x5558a1d96178 48837df800 cmp qword [var_8h], 0
│ └──< 0x5558a1d9617d 75d4 jne 0x5558a1d96153
│ 0x5558a1d9617f 90 nop
│ 0x5558a1d96180 c9 leave
└ 0x5558a1d96181 c3 ret
[0x5558a1d96145]>
Dentro de printLinkedList, el argumento (puntero) pasado a través de rdi se carga en la variable local creada por el compilador: var_8h.
│ 0x5558a1d9614d 48897df8 mov qword [var_8h], rdi ; arg1
│ ┌─< 0x5558a1d96151 eb25 jmp 0x5558a1d96178
│ ┌──> 0x5558a1d96153 488b45f8 mov rax, qword [var_8h]
Después el programa entra en el bucle y hace lo siguiente:
| ┌──> 0x5558a1d96153 488b45f8 mov rax, qword [var_8h]
│ ╎│ 0x5558a1d96157 8b00 mov eax, dword [rax]
│ ╎│ 0x5558a1d96159 89c6 mov esi, eax
│ ╎│ 0x5558a1d9615b 488d3da20e00. lea rdi, [0x5558a1d97004] ; "%d "
│ ╎│ 0x5558a1d96162 b800000000 mov eax, 0
│ ╎│ 0x5558a1d96167 e8c4feffff call sym.imp.printf ; int printf(const char *format)
│ ╎│ 0x5558a1d9616c 488b45f8 mov rax, qword [var_8h]
│ ╎│ 0x5558a1d96170 488b4008 mov rax, qword [rax + 8]
│ ╎│ 0x5558a1d96174 488945f8 mov qword [var_8h], rax
El programa carga el entero del nodo actual para imprimirlo. Después carga el puntero guardado en su campo next, situado en el offset 8, y lo convierte en el nodo de la siguiente iteración. Sumar el offset permite localizar el campo; leer ese campo obtiene la dirección del siguiente nodo.
│ ╎│ ; CODE XREF from sym.printLinkedlist @ 0x5558a1d96151
│ ╎└─> 0x5558a1d96178 48837df800 cmp qword [var_8h], 0
│ └──< 0x5558a1d9617d 75d4 jne 0x5558a1d96153
La condición de salida del bucle se evalúa al final, comparando el PUNTERO con 0; comparar un puntero con 0x0 equivale a compararlo con NULL.
Con esto termina el apartado de memoria dinámica. Como ejercicio, depura el programa por tu cuenta.
Descubriendo r2pipe
Puede haber situaciones en las que el código sea complejo y el programa repita acciones o siga patrones largos antes de generar resultados interesantes. Otras situaciones pueden incluir realizar exactamente el mismo análisis múltiples veces con distintos valores de entrada, o hacer el mismo análisis sobre muchos binarios en lote. También puede interesarnos calcular algo usando la memoria del programa para revelar funcionalidades ocultas, descubrir bugs, fugas interesantes, etc.
En todas esas situaciones, la solución pasa por usar r2pipe.
r2pipe es, en cierto modo, la API de r2. Permite interactuar con r2 mediante scripting en varios lenguajes de programación como Python o JavaScript. En este ejemplo usaremos r2pipe con Python para hacer análisis automático de un binario sencillo. Se puede instalar con pip:
pip3 install r2pipe
Después empezamos a usar r2pipe con:
import r2pipe
r = r2pipe.open('binary')
A partir de ahí, la variable r será un enlace a r2pipe; ejecutar r.cmd('aaa') equivale a estar en una sesión de r2 y ejecutar el comando «aaa». En r2, muchos comandos admiten añadir una «j» al final para que la salida sea un objeto JSON, lo que facilita el trabajo con r2pipe.
Un hello world típico con r2pipe puede ser algo así:
import r2pipe as r2
import json
r = r2.open('superlist')
r.cmd('aaa')
print(r.cmd('iL'))
print(r.cmd('afl'))
Pasemos a la práctica con el siguiente ejemplo:
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
int randy(){
int r = rand();
return r % 20 + 5;
}
struct node {
int i;
struct node *next;
};
int main(){
srand(time(NULL)); // Initialization, should only be called once.
int ran = 0;
struct node *ant;
struct node *first_node = NULL;
first_node = malloc(sizeof(struct node));
first_node->i = 1;
ant = first_node;
for(int i = 0; i < randy(); i++){
struct node *actual;
actual = malloc(sizeof(struct node));
actual->next = NULL;
actual->i = randy();
ant->next = actual;
ant = actual;
}
return 0;
}
Como se puede ver, este programa tiene algo de trampa. Inicializa una lista enlazada dinámica de N elementos aleatorios, cada uno con un int aleatorio y un puntero al siguiente elemento (NULL si es el último). Lo peculiar es que no hay ninguna llamada a printf, por lo que el usuario no tiene forma de saber cuántos valores tiene la lista ni cuál es su contenido.
Podemos desensamblar el programa así:
; DATA XREF from entry0 @ 0x5582293f909d
┌ 171: int main (int argc, char **argv, char **envp);
│ ; var int64_t var_20h @ rbp-0x20
│ ; var int64_t var_1ch @ rbp-0x1c
│ ; var int64_t var_18h @ rbp-0x18
│ ; var int64_t var_10h @ rbp-0x10
│ ; var int64_t var_8h @ rbp-0x8
│ 0x5582293f919e 55 push rbp
│ 0x5582293f919f 4889e5 mov rbp, rsp
│ 0x5582293f91a2 4883ec20 sub rsp, 0x20
│ 0x5582293f91a6 bf00000000 mov edi, 0
│ 0x5582293f91ab e890feffff call sym.imp.time ; time_t time(time_t *timer)
│ 0x5582293f91b0 89c7 mov edi, eax
│ 0x5582293f91b2 e879feffff call sym.imp.srand ; void srand(int seed)
│ 0x5582293f91b7 c745e4000000. mov dword [var_1ch], 0
│ 0x5582293f91be 48c745f00000. mov qword [var_10h], 0
│ 0x5582293f91c6 bf10000000 mov edi, 0x10 ; 16
│ 0x5582293f91cb e880feffff call sym.imp.malloc ; void *malloc(size_t size)
│ 0x5582293f91d0 488945f0 mov qword [var_10h], rax
│ 0x5582293f91d4 488b45f0 mov rax, qword [var_10h]
│ 0x5582293f91d8 c70001000000 mov dword [rax], 1
│ 0x5582293f91de 488b45f0 mov rax, qword [var_10h]
│ 0x5582293f91e2 488945e8 mov qword [var_18h], rax
│ 0x5582293f91e6 c745e0000000. mov dword [var_20h], 0
│ ┌─< 0x5582293f91ed eb44 jmp 0x5582293f9233
│ ┌──> 0x5582293f91ef bf10000000 mov edi, 0x10 ; 16
│ ╎│ 0x5582293f91f4 e857feffff call sym.imp.malloc ; void *malloc(size_t size)
│ ╎│ 0x5582293f91f9 488945f8 mov qword [var_8h], rax
│ ╎│ 0x5582293f91fd 488b45f8 mov rax, qword [var_8h]
│ ╎│ 0x5582293f9201 48c740080000. mov qword [rax + 8], 0
│ ╎│ 0x5582293f9209 b800000000 mov eax, 0
│ ╎│ 0x5582293f920e e852ffffff call sym.randy
│ ╎│ 0x5582293f9213 89c2 mov edx, eax
│ ╎│ 0x5582293f9215 488b45f8 mov rax, qword [var_8h]
│ ╎│ 0x5582293f9219 8910 mov dword [rax], edx
│ ╎│ 0x5582293f921b 488b45e8 mov rax, qword [var_18h]
│ ╎│ 0x5582293f921f 488b55f8 mov rdx, qword [var_8h]
│ ╎│ 0x5582293f9223 48895008 mov qword [rax + 8], rdx
│ ╎│ 0x5582293f9227 488b45f8 mov rax, qword [var_8h]
│ ╎│ 0x5582293f922b 488945e8 mov qword [var_18h], rax
│ ╎│ 0x5582293f922f 8345e001 add dword [var_20h], 1
│ ╎│ ; CODE XREF from main @ 0x5582293f91ed
│ ╎└─> 0x5582293f9233 b800000000 mov eax, 0
│ ╎ 0x5582293f9238 e828ffffff call sym.randy
│ ╎ 0x5582293f923d 3945e0 cmp dword [var_20h], eax
│ └──< 0x5582293f9240 7cad jl 0x5582293f91ef
│ 0x5582293f9242 b800000000 mov eax, 0
│ 0x5582293f9247 c9 leave
└ 0x5582293f9248 c3 ret
[0x5582293f919e]>
Como se puede ver, la lógica principal está dentro de ese bucle: se llama a la función randy() y el programa genera y enlaza los nodos ahí, nada nuevo para nosotros. Extraer todos esos nodos manualmente puede ser tedioso: podríamos poner un breakpoint al final de la función, ejecutar afvd y usar px o pf para inspeccionar la memoria, etc. Como la lista es dinámica y no tiene un tamaño fijo, si lo hacemos manualmente tendríamos que poner un breakpoint en la primera llamada a randy para saber cuántos valores se van a generar; esto puede ser lento y no hay necesidad de hacerlo manualmente, especialmente si necesitamos realizar alguna operación con esos números o volcarlos muchas veces para investigar vulnerabilidades (por ejemplo, un ataque criptográfico).
Podemos automatizar todo con r2pipe. Lo que haría manualmente sería: poner un breakpoint donde se inicializa el primer nodo y otro al final del main, donde todos los nodos deberían estar creados y enlazados. Después inspeccionaría el primer nodo, anotaría el valor, extraería el puntero al siguiente, iría allí y repetiría el proceso hasta que el puntero siguiente fuera 0x0 NULL. Otra opción sería poner un breakpoint tras la llamada inicial a randy, anotar cuántos nodos se van a generar, poner un breakpoint al final del código y desde ahí hacer un pf Ni..p o similar; sin embargo, asumiré que esos nodos pueden no estar contiguos en memoria, así que la primera opción me parece más adecuada.
Basándome en esa lógica, generé el siguiente script en Python usando r2pipe. El código funciona y creo que es suficientemente claro:
Aquí está el código:
import r2pipe as r2
import json
r = r2.open('superlist')
r.cmd('doo; s main')
disasm = json.loads(r.cmd("pdj"))
# mov dword [rax], 1
print("[+] linked list initialization detected at: ")
print(str(hex(disasm[13]["offset"]))+" "+disasm[13]["disasm"])
list_base_addr = hex(disasm[13]["offset"])
print("[+] setting a breakpoint at: "+list_base_addr)
r.cmd('db '+str(list_base_addr))
r.cmd('dc')
initial_regs = json.loads(r.cmd('drj'))
list_first_node = initial_regs["rax"]
print("[+] list initial node base address: "+hex(list_first_node))
# leave
print("[+] end of the main function detected at")
print(str(hex(disasm[39]["offset"]))+" "+disasm[39]["disasm"])
main_end = hex(disasm[39]["offset"])
print("[+] setting a breakpoint at: "+main_end)
r.cmd('db '+str(main_end))
r.cmd('dc')
print("[+] the end of the program has been reached")
print("[+] parsing the list now")
node_int = json.loads(r.cmd('pfj i @ '+str(list_first_node)))
print("[+] int item val = "+str(node_int[0]["value"]))
next_addr = hex(int(list_first_node)+8)
node_pointer = json.loads(r.cmd('pfj p @ '+str(next_addr)))
next_addr = int(node_pointer[0]["value"])
print("[+] next node located @ "+ hex(node_pointer[0]["value"]))
while next_addr != 0:
node_int = json.loads(r.cmd('pfj i @ '+str(hex(next_addr))))
print("[+] int item val = "+str(node_int[0]["value"]))
next_addr = hex(int(next_addr)+8)
node_pointer = json.loads(r.cmd('pfj p @ '+str(next_addr)))
next_addr = int(node_pointer[0]["value"])
print("[+] next node located @ "+ hex(node_pointer[0]["value"]))
print("[*] End Of List")
Como se puede ver, el script ejecuta una serie de comandos de r2, uno tras otro. El concepto clave es que podemos implementar nuestra propia lógica para automatizar tareas.
El script producirá una salida similar a esta:
Process with PID 23857 started...
= attach 23857 23857
File dbg:///home/lab/rev/superlist reopened in read-write mode
[+] linked list initialization detected at:
0x5591047661d8 mov dword [rax], 1
[+] setting a breakpoint at: 0x5591047661d8
hit breakpoint at: 5591047661d8
[+] list initial node base address: 0x559104c23260
[+] end of the main function detected at
0x559104766247 leave
[+] setting a breakpoint at: 0x559104766247
hit breakpoint at: 559104766247
[+] the end of the program has been reached
[+] parsing the list now
[+] int item val = 1
[+] next node located @ 0x559104c23280
[+] int item val = 20
[+] next node located @ 0x559104c232a0
[+] int item val = 21
[+] next node located @ 0x559104c232c0
[+] int item val = 6
[+] next node located @ 0x559104c232e0
[+] int item val = 19
[+] next node located @ 0x559104c23300
[+] int item val = 16
[+] next node located @ 0x559104c23320
[+] int item val = 16
[+] next node located @ 0x559104c23340
[+] int item val = 23
[+] next node located @ 0x559104c23360
[+] int item val = 15
[+] next node located @ 0x559104c23380
[+] int item val = 10
[+] next node located @ 0x0
[*] End Of List
El recorrido sigue los enlaces hasta encontrar un puntero nulo. En este ejemplo los nodos forman una lista válida. Para generalizar el script conviene limitar el número de iteraciones, comprobar que cada dirección es legible y registrar los nodos visitados para detectar ciclos.
Compila el programa y pruébalo tú mismo.
Pasamos ahora a explorar las operaciones a nivel de bit.
Operaciones a nivel de bit
Las operaciones a nivel de bit son muy sencillas; probablemente ya conozcas las operaciones lógicas básicas como AND, OR y XOR. Veamos esto:
#include <stdio.h>
int main() {
int a = 67;
int b = 33;
printf("var a = %d\n", a);
printf("var b = %d\n\n", b);
printf(" Complement of a = %d\n", ~a);
printf(" a AND b = %d\n", a&b);
printf(" a OR b = %d\n", a|b);
printf(" a XOR b = %d\n", a^b);
printf(" A left shifted 1 = %d\n", a << 1);
printf(" A right shifted 1 = %d\n", a >> 1);
getchar();
return 0;
}
El concepto es simple: en C, al igual que en muchos otros lenguajes, estas operaciones a nivel de bit se pueden realizar fácilmente. Están presentes y se usan activamente en algunos programas; presentaremos un ejemplo concreto después de este primero.
Las operaciones a nivel de bit son muy fáciles de entender al desensamblar código porque son literalmente las mismas instrucciones; incluso pueden resultar más claras en el desensamblado. Veamos:
[0x7fa9fae06090]> s main
[0x55d69499a145]> pdf
; DATA XREF from entry0 @ 0x55d69499a07d
┌ 225: int main (int argc, char **argv, char **envp);
│ ; var int64_t var_8h @ rbp-0x8
│ ; var int64_t var_4h @ rbp-0x4
│ 0x55d69499a145 55 push rbp
│ 0x55d69499a146 4889e5 mov rbp, rsp
│ 0x55d69499a149 4883ec10 sub rsp, 0x10
│ 0x55d69499a14d c745f8430000. mov dword [var_8h], 0x43 ; 'C' ; 67
│ 0x55d69499a154 c745fc210000. mov dword [var_4h], 0x21 ; '!' ; 33
│ 0x55d69499a15b 8b45f8 mov eax, dword [var_8h]
│ 0x55d69499a15e 89c6 mov esi, eax
│ 0x55d69499a160 488d3d9d0e00. lea rdi, str.var_a____d ; 0x55d69499b004 ; "var a = %d\n"
│ 0x55d69499a167 b800000000 mov eax, 0
│ 0x55d69499a16c e8bffeffff call sym.imp.printf ; int printf(const char *format)
│ 0x55d69499a171 8b45fc mov eax, dword [var_4h]
│ 0x55d69499a174 89c6 mov esi, eax
│ 0x55d69499a176 488d3d930e00. lea rdi, str.var_b____d ; 0x55d69499b010 ; "var b = %d\n\n"
│ 0x55d69499a17d b800000000 mov eax, 0
│ 0x55d69499a182 e8a9feffff call sym.imp.printf ; int printf(const char *format)
│ 0x55d69499a187 8b45f8 mov eax, dword [var_8h]
│ 0x55d69499a18a f7d0 not eax
│ 0x55d69499a18c 89c6 mov esi, eax
│ 0x55d69499a18e 488d3d880e00. lea rdi, str.Complement_of_a____d ; 0x55d69499b01d ; " Complement of a = %d\n"
│ 0x55d69499a195 b800000000 mov eax, 0
│ 0x55d69499a19a e891feffff call sym.imp.printf ; int printf(const char *format)
│ 0x55d69499a19f 8b45f8 mov eax, dword [var_8h]
│ 0x55d69499a1a2 2345fc and eax, dword [var_4h]
│ 0x55d69499a1a5 89c6 mov esi, eax
│ 0x55d69499a1a7 488d3d870e00. lea rdi, str.a_AND_b____d ; 0x55d69499b035 ; " a AND b = %d\n"
│ 0x55d69499a1ae b800000000 mov eax, 0
│ 0x55d69499a1b3 e878feffff call sym.imp.printf ; int printf(const char *format)
│ 0x55d69499a1b8 8b45f8 mov eax, dword [var_8h]
│ 0x55d69499a1bb 0b45fc or eax, dword [var_4h]
│ 0x55d69499a1be 89c6 mov esi, eax
│ 0x55d69499a1c0 488d3d7e0e00. lea rdi, str.a_OR_b_____d ; 0x55d69499b045 ; " a OR b = %d\n"
│ 0x55d69499a1c7 b800000000 mov eax, 0
│ 0x55d69499a1cc e85ffeffff call sym.imp.printf ; int printf(const char *format)
│ 0x55d69499a1d1 8b45f8 mov eax, dword [var_8h]
│ 0x55d69499a1d4 3345fc xor eax, dword [var_4h]
│ 0x55d69499a1d7 89c6 mov esi, eax
│ 0x55d69499a1d9 488d3d750e00. lea rdi, str.a_XOR_b____d ; 0x55d69499b055 ; " a XOR b = %d\n"
│ 0x55d69499a1e0 b800000000 mov eax, 0
│ 0x55d69499a1e5 e846feffff call sym.imp.printf ; int printf(const char *format)
│ 0x55d69499a1ea 8b45f8 mov eax, dword [var_8h]
│ 0x55d69499a1ed 01c0 add eax, eax
│ 0x55d69499a1ef 89c6 mov esi, eax
│ 0x55d69499a1f1 488d3d6d0e00. lea rdi, str.A_left_shifted_1____d ; 0x55d69499b065 ; " A left shifted 1 = %d\n"
│ 0x55d69499a1f8 b800000000 mov eax, 0
│ 0x55d69499a1fd e82efeffff call sym.imp.printf ; int printf(const char *format)
│ 0x55d69499a202 8b45f8 mov eax, dword [var_8h]
│ 0x55d69499a205 d1f8 sar eax, 1
│ 0x55d69499a207 89c6 mov esi, eax
│ 0x55d69499a209 488d3d6e0e00. lea rdi, str.A_right_shifted_1____d ; 0x55d69499b07e ; " A right shifted 1 = %d\n"
│ 0x55d69499a210 b800000000 mov eax, 0
│ 0x55d69499a215 e816feffff call sym.imp.printf ; int printf(const char *format)
│ 0x55d69499a21a e821feffff call sym.imp.getchar ; int getchar(void)
│ 0x55d69499a21f b800000000 mov eax, 0
│ 0x55d69499a224 c9 leave
└ 0x55d69499a225 c3 ret
[0x55d69499a145]>
La operación complemento equivale a NOT: todos los ceros se convierten en unos y viceversa. La instrucción not en ensamblador funciona así:
│ 0x55d69499a187 8b45f8 mov eax, dword [var_8h]
│ 0x55d69499a18a f7d0 not eax
│ 0x55d69499a18c 89c6 mov esi, eax
│ 0x55d69499a18e 488d3d880e00. lea rdi, str.Complement_of_a____d ; 0x55d69499b01d ; " Complement of a = %d\n"
AND también está presente en el conjunto de instrucciones x86/x64:
│ 0x55d69499a19f 8b45f8 mov eax, dword [var_8h]
│ 0x55d69499a1a2 2345fc and eax, dword [var_4h]
│ 0x55d69499a1a5 89c6 mov esi, eax
│ 0x55d69499a1a7 488d3d870e00. lea rdi, str.a_AND_b____d ; 0x55d69499b035 ; " a AND b = %d\n"
Así como OR:
│ 0x55d69499a1b8 8b45f8 mov eax, dword [var_8h]
│ 0x55d69499a1bb 0b45fc or eax, dword [var_4h]
│ 0x55d69499a1be 89c6 mov esi, eax
│ 0x55d69499a1c0 488d3d7e0e00. lea rdi, str.a_OR_b_____d ; 0x55d69499b045 ; " a OR b = %d\n"
Y XOR; conviene tener muy presente XOR, ya que se usa habitualmente en crypters y packers de baja calidad.
│ 0x55d69499a1d1 8b45f8 mov eax, dword [var_8h]
│ 0x55d69499a1d4 3345fc xor eax, dword [var_4h]
│ 0x55d69499a1d7 89c6 mov esi, eax
│ 0x55d69499a1d9 488d3d750e00. lea rdi, str.a_XOR_b____d ; 0x55d69499b055 ; " a XOR b = %d\n"
Los desplazamientos aparecen en cálculos de índices y en determinadas multiplicaciones o divisiones por potencias de dos. Su interpretación depende del ancho, el signo y las reglas de desbordamiento. sar conserva el signo al desplazar a la derecha; shr introduce ceros y sal/shl desplazan a la izquierda.
│ 0x55d69499a1ea 8b45f8 mov eax, dword [var_8h]
│ 0x55d69499a1ed 01c0 add eax, eax
│ 0x55d69499a1ef 89c6 mov esi, eax
│ 0x55d69499a1f1 488d3d6d0e00. lea rdi, str.A_left_shifted_1____d ; 0x55d69499b065 ; " A left shifted 1 = %d\n"
│ 0x55d69499a202 8b45f8 mov eax, dword [var_8h]
│ 0x55d69499a205 d1f8 sar eax, 1
│ 0x55d69499a207 89c6 mov esi, eax
│ 0x55d69499a209 488d3d6e0e00. lea rdi, str.A_right_shifted_1____d ; 0x55d69499b07e ; " A right shifted 1 = %d\n"
Enums
¿Recuerdas las variables constantes globales?
#include <stdio.h>
enum week {Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, Saturday};
int main()
{
// creating today variable of enum week type
enum week today;
today = Wednesday;
printf("Day %d",today+1);
return 0;
}
Los enums son listas de valores constantes. Descompilemos esto:
[0x55a7617a5135]> pdf
; DATA XREF from entry0 @ 0x55a7617a506d
┌ 47: int main (int argc, char **argv, char **envp);
│ ; var int64_t var_4h @ rbp-0x4
│ 0x55a7617a5135 55 push rbp
│ 0x55a7617a5136 4889e5 mov rbp, rsp
│ 0x55a7617a5139 4883ec10 sub rsp, 0x10
│ 0x55a7617a513d c745fc030000. mov dword [var_4h], 3
│ 0x55a7617a5144 8b45fc mov eax, dword [var_4h]
│ 0x55a7617a5147 83c001 add eax, 1
│ 0x55a7617a514a 89c6 mov esi, eax
│ 0x55a7617a514c 488d3db10e00. lea rdi, str.Day__d ; 0x55a7617a6004 ; "Day %d"
│ 0x55a7617a5153 b800000000 mov eax, 0
│ 0x55a7617a5158 e8d3feffff call sym.imp.printf ; int printf(const char *format)
│ 0x55a7617a515d b800000000 mov eax, 0
│ 0x55a7617a5162 c9 leave
└ 0x55a7617a5163 c3 ret
[0x55a7617a5135]>
Los enums se indexan automáticamente, así que Sunday se representa como 0, Monday como 1, y así sucesivamente; por tanto, Wednesday == 3. Con eso el programa es fácil de entender. Además, como los enums son estructuras estáticas completamente constantes, se pasan directamente al compilador, que construye el programa en consecuencia (cada vez que el compilador encuentra Wednesday simplemente coloca un 3).
Los enums se usan habitualmente junto con operaciones a nivel de bit para pasar flags a funciones.
#include <stdio.h>
enum designFlags {
BOLD = 1,
ITALICS = 2,
UNDERLINE = 4
};
int main() {
int myDesign = BOLD | UNDERLINE;
//
// |
// ___________
//
printf("%d", myDesign);
return 0;
}
Imagina que tienes una función que ya recibe muchos parámetros y necesitas aún más, como permisos, opciones de formato, modos de acceso, etc., y esos parámetros pueden combinarse entre sí. Los parámetros pueden crecer fácilmente y hacer el código muy difícil de leer. Los enums junto con las operaciones a nivel de bit ayudan con eso.
Fíjate en el ejemplo anterior: imagina pasar BOLD como parámetro a una función, sería algo como 00000001; imagina también que quieres el texto en negrita y subrayado a la vez (como se muestra en el código), UNDERLINE sería 00000100. En lugar de pasar ambos valores por separado, podemos combinarlos con un OR lógico y obtenemos 00000101, que es 5. Si la función recibe un 5, sabrá que solo puede ser la combinación de BOLD y UNDERLINE. El mismo principio se aplica a los permisos de chmod.
[0x5560d3fdd135]> pdf
; DATA XREF from entry0 @ 0x5560d3fdd06d
┌ 44: int main (int argc, char **argv, char **envp);
│ ; var int64_t var_4h @ rbp-0x4
│ 0x5560d3fdd135 55 push rbp
│ 0x5560d3fdd136 4889e5 mov rbp, rsp
│ 0x5560d3fdd139 4883ec10 sub rsp, 0x10
│ 0x5560d3fdd13d c745fc050000. mov dword [var_4h], 5
│ 0x5560d3fdd144 8b45fc mov eax, dword [var_4h]
│ 0x5560d3fdd147 89c6 mov esi, eax
│ 0x5560d3fdd149 488d3db40e00. lea rdi, [0x5560d3fde004] ; "%d"
│ 0x5560d3fdd150 b800000000 mov eax, 0
│ 0x5560d3fdd155 e8d6feffff call sym.imp.printf ; int printf(const char *format)
│ 0x5560d3fdd15a b800000000 mov eax, 0
│ 0x5560d3fdd15f c9 leave
└ 0x5560d3fdd160 c3 ret
[0x5560d3fdd135]>
En este caso, el compilador resuelve la operación OR lógica e introduce directamente un 5 en la variable.
Reconstruir el recorrido de una lista.
Hermes examina la función que imprime la lista. El tamaño de los accesos y la actualización del puntero permiten reconocer el campo data, el enlace next y la condición de salida.
Leer la explicación y los comandos
La consulta
Examina printLinkedlist en linked-list. Identifica la lectura de data, el acceso a next y la condición que termina el recorrido. Señala las instrucciones que permiten distinguir el entero del puntero en esta compilación x86-64.
Qué muestra la sesión
La función lee data mediante un acceso de 32 bits al comienzo del nodo. Después prepara ese valor como argumento de printf.
La lectura de next utiliza un acceso de 64 bits en el offset ocho. El valor leído sustituye al puntero de la iteración actual y permite avanzar al siguiente nodo.
El recorrido comprueba el puntero antes de entrar en el cuerpo. La comparación con NULL y el salto condicional determinan la salida. La anchura de un acceso se interpreta junto con el uso del valor para reconstruir su tipo.
Comprobación desde la consola
Desde la consola del companion se revisan estas instrucciones y datos:
pd 14 @ 0x401168
Las direcciones corresponden a la compilación grabada. Localiza las funciones y operaciones de tu propio ejecutable antes de repetir los comandos. Descargar el fuente del vídeo ↙ · Preparar el companion ↗
Vuelve al binario
Reconocer nodos y enlaces, interpretar máscaras y automatizar consultas de análisis. Identifica al menos una instrucción y el dato que utiliza; conserva la compilación con la que lo has observado.
Fuente de esta práctica: linked-list.c ↓.
Descargar los 13 ejemplos de fundamentos ↙
Puedes utilizar la consola del companion sin conversar con el agente, o abrir el ejecutable en tu desensamblador habitual.
./coursectl start 11 --example linked-list
./coursectl consoleCierra la sesión anterior con ./coursectl stop antes de cambiar de laboratorio. Ver preparación.
Antes de continuar
Localiza el campo next y la condición de parada del recorrido. Explica qué instrucciones utilizan el puntero y cuáles leen el dato del nodo.
El progreso se guarda en este navegador. Puedes recorrer las lecciones en cualquier orden.