Если можно сделать следующие предположения, возможно ли восстановить головной узел связанного списка.
- Связанный список создается с помощью malloc, и к нему можно получить доступ из области кучи.
- Начальный и конечный адрес кучи можно найти в / proc / self / maps (по крайней мере, в Linux).
- По крайней мере один узел в исходном связанном списке доступен.
- Указатель на предыдущий узел будет где-то найден в куче.
- И его можно рекурсивно искать, пока не будет найден фактический заголовок.
Чтобы проиллюстрировать это лучше, пожалуйста,используйте следующую программу, которая может быть успешно скомпилирована с gcc по крайней мере в Ubuntu / WSL при настройках по умолчанию.
Программа
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
typedef struct node
{
int val;
struct node *next;
} node_t;
node_t *head = NULL;
unsigned long start_address = 0;
unsigned long end_address = 0;
node_t *getLastNode()
{
node_t *iter = head;
for (; iter->next != NULL; iter = iter->next)
;
return iter;
}
void addToLinkedList(int value)
{
node_t *data = malloc(sizeof(node_t));
data->val = value;
data->next = NULL;
if (head == NULL)
head = data;
else
getLastNode()->next = data;
}
void createLinkedList()
{
// Add 10 nodes to the linked list
int start_val = 0x10101010;
for (int i = 1; i <= 10; i++)
addToLinkedList(start_val * i);
}
void printLinkedList()
{
printf("Head pointer of Linked List : %p\n", head);
for (node_t *iter = head; iter != NULL; iter = iter->next)
printf("%p -> value = %X, next = %p \n", iter, iter->val, iter->next);
printf("\n");
}
void resetHeadPtr()
{
// Lets make head point to the last node
head = getLastNode();
}
void findHeapBoundary()
{
// Code inspired from https://unix.stackexchange.com/a/251769/152334
char mapsFilename[1024];
char line[256];
char area[1024];
sprintf(mapsFilename, "/proc/%d/maps", getpid());
FILE *pMapsFile = fopen(mapsFilename, "r");
while (fgets(line, 256, pMapsFile) != NULL)
{
// Dirty hack to get the heap start and end address
sscanf(line, "%08lx-%08lx%*[^[]%s\n", &start_address, &end_address, area);
if (strcmp(area, "[heap]") == 0)
break;
}
fclose(pMapsFile);
printf("Heap memory start address : %p\n", (int *)start_address);
printf("Heap memory end address : %p\n", (int *)end_address);
}
node_t *findPointerInMemory()
{
for (int *ptr = (int *)start_address; ptr < (int *)(end_address - sizeof(node_t)); ptr++)
{
if (((node_t *)ptr)->next == head)
return (node_t *)ptr;
}
return NULL;
}
void recoverHeadPtr()
{
node_t *ptr = findPointerInMemory();
if (ptr == NULL)
{
printf("Cannot find %p in heap memory\nStopping Search\n\n", head);
return;
}
printf("Found %p at %p\n", head, ptr);
head = ptr;
recoverHeadPtr();
}
int main(int argc, char const *argv[])
{
createLinkedList();
printf("Original Linked List Contents\n*****************************\n");
printLinkedList();
resetHeadPtr();
printf("Linked List Contents after reset\n********************************\n");
printLinkedList();
findHeapBoundary();
recoverHeadPtr();
printf("Recovered Linked List Contents\n******************************\n");
printLinkedList();
return 0;
}
Вывод
Original Linked List Contents
*****************************
Head pointer of Linked List : 0x1db6010
0x1db6010 -> value = 10101010, next = 0x1db6030
0x1db6030 -> value = 20202020, next = 0x1db6050
0x1db6050 -> value = 30303030, next = 0x1db6070
0x1db6070 -> value = 40404040, next = 0x1db6090
0x1db6090 -> value = 50505050, next = 0x1db60b0
0x1db60b0 -> value = 60606060, next = 0x1db60d0
0x1db60d0 -> value = 70707070, next = 0x1db60f0
0x1db60f0 -> value = 80808080, next = 0x1db6110
0x1db6110 -> value = 90909090, next = 0x1db6130
0x1db6130 -> value = A0A0A0A0, next = (nil)
Linked List Contents after reset
********************************
Head pointer of Linked List : 0x1db6130
0x1db6130 -> value = A0A0A0A0, next = (nil)
Heap memory start address : 0x1db6000
Heap memory end address : 0x1dd7000
Found 0x1db6130 at 0x1db6110
Found 0x1db6110 at 0x1db60f0
Found 0x1db60f0 at 0x1db60d0
Found 0x1db60d0 at 0x1db60b0
Found 0x1db60b0 at 0x1db6090
Found 0x1db6090 at 0x1db6070
Found 0x1db6070 at 0x1db6050
Found 0x1db6050 at 0x1db6030
Found 0x1db6030 at 0x1db6010
Cannot find 0x1db6010 in heap memory
Stopping Search
Recovered Linked List Contents
******************************
Head pointer of Linked List : 0x1db6010
0x1db6010 -> value = 10101010, next = 0x1db6030
0x1db6030 -> value = 20202020, next = 0x1db6050
0x1db6050 -> value = 30303030, next = 0x1db6070
0x1db6070 -> value = 40404040, next = 0x1db6090
0x1db6090 -> value = 50505050, next = 0x1db60b0
0x1db60b0 -> value = 60606060, next = 0x1db60d0
0x1db60d0 -> value = 70707070, next = 0x1db60f0
0x1db60f0 -> value = 80808080, next = 0x1db6110
0x1db6110 -> value = 90909090, next = 0x1db6130
0x1db6130 -> value = A0A0A0A0, next = (nil)
Фон
Моему другу в интервью был задан следующий вопрос.«Можете ли вы найти указатель заголовка одного связанного списка, если указан последний узел?».Он ответил «нет», и хотя интервьюер не был полностью удовлетворен ответом, ему предложили работу.Это заставило меня задуматься, возможно ли это сделать.
Итак, реальные вопросы таковы.
- Правильно ли этот подход?
- Нужно ли искать в других сегментах памяти?
- Можно ли обобщить этот подход для работы и в Windows?
- Будет ли ASLR иметь какое-либо влияние на этот подход?