Desarrollando un recuperador de archivos borrados
Cuando borras un archivo de tu disco duro o pendrive, realmente no se borra del todo, puede que recién te enteres de esto o ya lo sabias desde antes, de todas maneras es interesante profundizar en el trasfondo de esta afirmación y aún más interesante sería preguntarse: ¿Si no se borran del todo, se pueden recuperar?
Sistemas de archivos
En terminos muy simples, tu unidad de almacenamiento, ya sea un disco duro o pendrive, almacena bytes de forma secuencial, cada posición se puede acceder mediante una dirección única. Para que el sistema operativo pueda econtrar rápidamente los archivos que deseas acceder lo hace utilizando un “Sistema de archivos”, el cual, es una estructura que organiza la ubicación de cada fichero en el disco duro, identificando, entre otras cosas, el nombre del archivo y la ubicación dentro de la unidad de almacenamiento.
Dependiendo del sistema de archivo que se utilice el mecanismo puede variar y puede ser más o menos eficiente, para efectos de nuestro propósito solo es necesario saber que el sistema de archivos guarda una referencia a la ubicación en el disco que contiene la información. Cuando eliminamos un archivo solamente eliminamos esta referencia, de esta forma es mucho mas rápido que recorrer todos los bytes de la información y modificarlos para dejarlos en 0.
Como se muestra representado en los diagramas anteriores, al eliminar el archivo “imagen2.png” solamente borramos la referencia, pero el contenido de la imagen sigue estando en algún lugar de la unidad de almacenamiento, el problema es que ahora para encontrarlo, debemos recorrer todo el disco hasta lograr identificar que en ese lugar existe un archivo.
Para finalizar con esta explicación hace falta aclarar que una vez que se borra la referencia del archivo, el espacio en el disco queda disponible para guardar más información, por lo tanto, no es de extrañar que recuperemos archivos corruptos o archivos donde solo se muestre información parcial.
Formato PNG
En este caso para mantener la explicación sencilla, solo vamos a buscar archivos PNG. Explicaremos en términos muy simples como se estructura un archivo en este formato y nos centraremos en lo esencial para poder encontrarlos dentro la unidad de disco.
Muchos formatos de archivo comienzan con una secuencia de bytes que identifican el inicio de estos, a esta secuencia se le conoce como “bytes mágicos” o “File signature”, puedes ver una lista completa en este link de Wikipedia. En el caso de las imágenes PNG podemos ver que sus primeros 8 bytes corresponden a la secuencia: “89 50 4E 47 0D 0A 1A 0A”, al verlo en formato ASCII podemos identificar fácilmente la sigla PNG: “‰PNG␍␊␚␊”.
Una vez identificado el inicio del archivo queda identificar todos los bytes que corresponden a la imagen hasta su final. Para eso primero veamos de forma muy resumida como se estructura un archivo PNG.
Luego de los 8 bytes que identifican el inicio del archivo, el formato PNG contiene distintos trozos o “Chunks” que aportan información útil para interpretar las imagenes. En primer lugar tenemos el chunk de cabecera IHDR que contiene información propia de la imagen como sus medidas, luego viene una serie de distintos tipos de chunks que para nuestros propósitos no nos interesa conocer en detalle como están definidos y por último y más importante viene el chunk de final IEND, que simplemente identifica que es el último chunk de la imágen y no contiene mayor información.
Si quieres obtener todo el detalle de como se estructura un archivo PNG puedes ver su especificación en este link a su RFC.
En este caso solo nos interesa identificar el final del archivo que para nuestra facilidad lo podemos encontrar exactamente por la palabra IEND o representada por la secuencia de bytes en hexadecimal “49 45 4E 44”.
Todo lo que se encuentre entre el inicio y el final lo interpretaremos como una imágen de formato PNG.
Programando el recuperador de archivos
Ya tenemos toda la información necesaria para poder desarrollar el programa que nos permitirá recuperar los archivos PNG borrados que se encuentren en el disco. Daré una explicación a alto nivel sobre la lógica del programa y mostraré como estan implementadas ciertas funciones, de todas maneras el código completo se puede encontrar en este repositorio.
La lógica más importante de nuestro programa es poder identificar una secuencia de bytes, de hecho, debemos identificar dos secuencias, la de inicio y la de final. Para esto leeremos byte a byte toda la unidad de disco y compararemos cada byte con el inicio de la secuencia que estamos buscando, una vez encontremos la coincidencia con el primer byte aumentaremos un contador, así sucesivamente hasta que tengamos la misma cantidad de coincidencias que el largo de la secuencia. Si encontramos un byte que no coincide volvemos el contador a cero y seguimos buscando.
fn check_init(&mut self, byte: u8) -> bool {
if self.match_index > PNG::MAGIC_INIT.len() - 1 {
self.match_index = 0;
}
if Self::MAGIC_INIT[self.match_index] == byte {
self.match_index += 1;
} else {
self.match_index = 0;
}
return self.match_index == PNG::MAGIC_INIT.len();
}En el código anterior podemos ver la implemetación en rust de esta lógica. La constante MAGIC_INIT contiene la secuencia de inicio que estamos buscando, la variable match_index es el contador que indica hasta que posición hemos encontrado una coincidencia, en caso de que la coincidencia se cumpla se va aumentando el valor de la variable match_index, en caso de que no coincida se vuelve a 0, y para finalizar una vez que el valor de match_index es igual al largo de la cadena que estamos buscando retornamos un valor verdadero para indicar que encontramos la secuencia.
Para encontrar la cadena del final el código es similar, es más, se puede refactorizar el código y generalizar la lógica para encontrar cualquier secuencia, pero por ahora lo mantendremos simple.
Luego nuestro buscador debe tener la lógica para saber en que momento está buscando la cadena de inicio y cuando tiene que buscar la cadena de final, además en el momento que encontremos la secuencia de inicio debemos almacenar cada byte que nos encontremos. Para resolver esto usaremos una sencilla máquina de estado, tendrá dos estados: “buscando inicio” y “buscando final”.
pub fn step(&mut self, byte: u8) -> Option<Vec<u8>> {
match self.state {
State::SearchingInit => {
let found = self.check_init(byte);
if found {
self.state = State::SearchingEnd;
}
}
State::SearchingEnd => {
self.png_bytes.push(byte);
let found = self.check_end(byte);
if found {
self.state = State::SearchingInit;
let mut complete_png_bytes: Vec<u8> = Vec::new();
complete_png_bytes.extend_from_slice(&Self::MAGIC_INIT);
complete_png_bytes.extend_from_slice(&self.png_bytes);
self.png_bytes = Vec::new();
return Some(complete_png_bytes);
}
}
}
self.position += 1;
None
}Aquí podemos ver la implementación en rust. Comparamos y hacemos una acción distinta según el estado en el que nos encontramos. El estado “buscando inicio” es sencillo ya que solo ejecutaremos nuestra función para encontrar el inicio que vimos anteriormente y una vez que lo encontremos cambiamos al estado “buscando final”. Cuando nos encontremos en el estado buscando final haremos tres cosas, guardamos los bytes que nos encontramos ya que sabemos que pertenece a la imágen, chequeamos si encontramos el final utilizando la función para encontrar la secuencia y en caso de encontrarla retornamos todos los bytes encontrados. Adicionalmente reiniciamos el estado de la máquina a “buscando inicio”, limpiamos el arreglo de los bytes que almacenamos y concatemanos los bytes encontrados con los 8 bytes del inicio.
Teniendo esta lógica construida ya abordamos los más importante, ahora solo nos queda poder entregarle a nuestra función los bytes en los que debe buscar.
En los sistemas Unix (MacOs o distribuciones de linux) la tarea se hace muy sencilla, en estos sistemas operativos todo es un archivo, incluidas las unidades de almacenamiento que se encuentran conectadas a la computadora, por lo tanto, solo debemos saber que archivo debemos leer. En general estos archivos se encuentran en la carpeta /dev, puedes ejecutar el comando “ls /dev” y se listarán todos los dispositivos conectados y otros archivos interesantes. En Mac puedes identificar el dispositivo que deseas analizar utilizando la utilidad de discos o con alguna herramienta similar en sistemas linux.
pub fn recover_png(filepath: &str, output: &str) -> io::Result<i32> {
let mut file = File::open(filepath)?;
let mut buffer = [0; 32];
let mut png = PNG::new();
let mut founds = 0;
let mut byte: usize = 0;
loop {
let n: usize = file.read(&mut buffer)?;
if n == 0 {
break;
}
for buffer_byte in buffer.iter_mut() {
match png.step(*buffer_byte) {
Some(image) => {
founds += 1;
let file_name = format!("image{}.png", founds);
println!("📁 PNG: {} {:?} bytes", file_name, image.len());
save_file(image, output, &file_name);
}
None => {
}
}
}
byte += n;
print_progress(byte);
}
Ok(founds)
}En el código anterior podemos ver la implemetación en Rust. Como vemos la función recibe por parámetro la ruta del archivo que debe leer (puede ser el archivo de la carpeta /dev que mencionamos anteriormente) y un segundo parámetro donde se guardarán las imagenes encontradas.
En primer lugar se abre el archivo, en este caso sería nuestra unidad de almacenamiento. En la variable png se crea una instancia de la clase que buscará las imagenes png. Luego debemos leer el archivo hasta el final, para ello utilizamos un ciclo infinito y vamos leyendo el archivo, en este caso se lee almacenando la información en un buffer de 32 bytes, esto se hace ya que la lectura hacia discos externos es muy lenta, por lo tanto si leemos de a 1 byte cada vez el proceso se demorará mucho, por otra parte si el buffer es muy grande utilizaremos mucha más memoria. Cuando no haya nada mas por leer se finalizará el ciclo. Iteramos sobre los bytes obtenidos en el buffer y se lo pasamos de a uno en uno a nuestra clase buscadora de pngs, cada vez que encuentre una imagen se retornará el arreglo de bytes que identificó como una imágen, ahora simplemente imprimimos unos logs para mostrar el avance y guardamos el archivo.
fn save_file(file_bytes: Vec<u8>, folder: &str, filename: &str) {
let file_name = format!("{}/{}", folder, filename);
let mut file = File::create(file_name).unwrap();
let _ = file.write_all(&file_bytes);
}La función para guardar el archivo es trivial, solo debemos entender que ya obtuvimos los bytes que representan esa imagen y si los guardamos con la extensión correcta podremos recuperar las imagenes que estabamos buscando.
Ejemplo de uso
Para probar la herramienta simplemente agregué archivos PNG a un antiguo pendrive que tenía guardado, luego evidentemente borré estas imágenes y ejecuté la herramienta.
Como podemos ver en la imágen antes de los primeros 400 bytes de búsqueda ya encontró los archivos de prueba que había guardado y borrado.
Para mi sorpresa al dejar funcionar la herramienta terminó encontrando un total de 407 imágenes. La mayoría de sistemas operativos que habré instalado en el pendrive hace bastantes años. Muchas imágenes encontradas estaban completamente inutilizables, a otras evidentemente los faltaba información y algunas
Consideraciones
Esta explicación y el desarrollo de la herramienta se hizo solo con fines demostrativos y de aprendizaje, por lo tanto me salté muchas consideraciones importantes al hacer una herramienta de este estilo, por ejemplo, si encontramos el inicio de un imagen PNG no podemos asegurar que encontraremos su final, recuerda que estamos buscando en espacios del disco que pueden ser sobreescritas por otros archivos, por lo tanto para hacer mucho mas robusta la herramienta deberiamos leer con mayor exactitud el formato PNG y determinar en caso que exista un error en la imagen.
El formato aquí visto es un formato fácil de identificar y también es sencillo encontrar su final, de todas maneras puede que en otros formato la única forma de encontrar su final sea interpretando cada bytes para saber con exactitud donde terminará.
Estás totalmente invitado a hacer pull request para mejorar la herramienta, tambien espero agregarle más caracteristicas y hacerla más robustas, pero si deseas tener el código en el que se basa este artículo te dejo el commit específico en este link.
Conclusión
A pesar que el funcionamiento de este programa es bastante sencillo pudimos aprender muchas cosas distintas para lograr nuestro cometido. Vimos como funciona a muy grandes rasgos un sistema de archivos y por qué cuando eliminamos un archivo no se borra completamente; aprendimos a identificar en este caso un archivo con formato PNG y por último usamos ese conocimiento para desarrollar una herramienta que nos permita encontrar estos archivos dentro de un dispositivo de almacenamiento. Por último vimos un ejemplo de la herramienta siendo utilizada y consideraciones para hacerla mucho mas robusta y completa.
Muchas gracias por llegar hasta aquí, espero que hayas aprendido tanto como yo lo hice.