03 septiembre 2012

Forense de SQLite V - Celdas


Finalizo con esta entrada la serie de artículos teóricos sobre forense en bases de datos SQLite, dejo pendiente para las dos siguientes un ejemplo práctico con todo lo visto y la publicación de la herramienta.

Con lo visto hasta ahora, debemos ser capaces de identificar todo el espacio libre del fichero a excepción del que se incluye en las páginas Overflow, ya que para saber donde terminan las celdas de una página b-tree, es necesario procesar su contenido.

Cada celda contiene un registro de la tabla y las tablas se almacenan en páginas b-tree. Tal y como se veía en la entrada anterior, el número, la posición (relativa) de la primera y el resto de posiciones de las celdas está en la cabecera de la página.

Usando la misma base de datos y página b-tree de ejemplo que en la entrada anterior, se mostrará como se almacena  una celda.

Imagen 1. Cabecera B-tree de hoja de tabla
  • 00 05: Especifica que existen 5 celdas en la página, es decir, que la tabla tiene 5 registros.
  • 01 AE: La primera celda se encuentra en la posición 430 (relativa a la posición de la página).
  • 01 AE - 02 4B - 03 56 - 03 - 72 - 03 E0: cada grupo de 2 bytes, son las posiciones de las celdas en la página: 430, 587, 854, 882 y 992.
  • 03 E0: Esta marcado por que aparentemente es una celda eliminada, ya que se indicó que solo había 5 (coloreadas en azul) y en la sexta posición aún hay datos, aunque su valor se ha sobre escrito con el de la posición de la celda número 5.
Las celdas en hojas de páginas b-tree están compuestas por cuatro campos: tamaño del payload, identificador de la fila (rowid), la cabecera del payload y finalmente el payload (con los datos del registro de la tabla).

Figura 1: estructura de celda

Tanto el tamaño del payload, el identificador de la fila y los tipos de datos se definen utilizando codificación varint.

Un varint (variable-lengt integer) es una forma de codificación estática usando el algoritmo Huffman que permite usar poco espacio para pequeños valores. Los varint tienen un tamaño variable entre 1 y 9 bytes y el propio byte define si el siguiente byte es usado o no basándose en el bit más significativo. El resto de bits son utilizados para calcular su valor.

Como ejemplo práctico analizamos la primera celda para comprender como se estructura. Lo primero es abrir el fichero en la posición donde comienza: 430, es decir, el offset 1454 (1024+430).

Imagen 2: celda (registro de tabla)
En esta imagen se puede observar:
  • El primer byte, 89, equivale al número binario 10001001 . 
    • Como su bit más significante (el primero de la izquierda) es 1, el varint incluye el siguiente.
    • 12 se representa con el binario: 00010010, en este caso el bit más significativo es 0, por lo que termina ahí el varint.
    • Uniendo los 7 bits restantes de ambos bytes:  00010010010010, se obtiene el valor decimal: 1170.
  • Por lo tanto, 89 12 forman el primer varint (tamaño del payload) y equivale a 1170 bytes.
  • 01 (en amarillo) es el varint que representa el ROWID, en este caso su binario es: 00000001, lo que significa que no está compuesto por más bytes y su decimal es: 1.
  • 06: (gris), es el tamaño de la cabecera del payload, incluido este mismo byte. Es decir, 6 bytes.
Los tipos de datos se almacenan de 13 formas distintas especificadas en la siguiente tabla y se definen en más varints dentro de la cabecera del payload (los datos pintados de marrón)

Tabla 1: tipos de formatos de registros
De la imagen 2 de ejemplo, y usando como referencia la tabla, se observan que contienen estos datos, pintados en verde y marcados en recuadros negros:
  • 15: Este varint de un solo byte, ya que su binario es: 00010101. Su decimal 21 es un número mayor de 13 e impar, (corresponde al  último caso de la tabla 1) indica que el primer campo es un string que tiene un tamaño de: (N-13)/2, es decir (21-13/2)=4 bytes
  • 17: varint de un solo byte (decimal 23), por ser un número mayor de 13 e impar, indica que el primer campo de la tabla es un string que tiene un tamaño de: (23-13/2)=5 bytes
  • 17:  El mismo caso que el anterior: (23-13/2)=5 bytes
  • 92 09: Varint de dos bytes (2313), impar y mayor de 13 por lo que su tamaño es de: (2313-13)/2=1150 bytes.
Los campos por lo tanto son: dab1 (4 bytes), alex1 (5 bytes), choco (5 bytes) y 12345...12345 (1150 bytes), todos ellos pintados en verde.

Si has conseguido llegar hasta aquí enhorabuena. Seguramente en una segunda lectura quede todo más claro.

Para finalizar, aún hay un pequeño problema. El último campo de esta celda ocupa 1150 bytes, pero no está completo (de hecho, su tamaño es mayor que la página), por lo que se ha producido un desbordamiento (overflow) a otra página. Para ser más exactos, en la página 3, tal y como se ve pintado de color azul en la imagen 2.

El resto de la celda, se encontrará en esa página 3, siguiendo la cadena de páginas overflows tal y como se comentaba en la entrada anterior.

Esto deja alguna pregunta sin responder, ¿cómo sabemos cuántos bytes de este registro hay en esta página  y cuantos hay en las de overflow? La respuesta está en uno de los requisitos de la documentación (H31190) y para calcularlo se usa la siguiente fórmula:

            min-local := (usable-size - 12) * min-embedded-fraction / 255 - 23
            max-local := usable-size - 35
            local-size := min-local + (record-size - min-local) % (usable-size - 4)
            if( local-size > max-local )
                local-size := min-local

Donde:
  • usable-size: es el tamaño de la página menos los bytes reservados. Los bytes reservados están definidos en la posición 20 de la cabecera y generalmente es 0.
  • min-embedded-faction se define en la posición 22 de la cabecera de la base de datos. La documentación nos dice que ha de ser siempre el valor "32".
Usando la formula y los valores del ejemplo:

          min-local := (1024 - 12 ) * 32 / 255 - 23 = 103
          max-local :=  1024 - 35 = 989
          local-size :=  103 + ( 1150 - 103) % ( 1024 - 4 ) = 130

Por lo tanto en la celda de esa hoja habrá 130 bytes de este dato y los 1020 bytes restantes (1150-130), en la página 3.

Para finalizar, si abriese el sqlite con un gestor gráfico, comprobaría que los datos extraídos son correctos observando el primer registro.:

Imagen 3: sqlite de ejemplo procesado

¿En que afecta todo esto en el análisis forense del fichero? Sencillo, si no somos capaces de recorrer las celdas y encontrar las páginas overflow, es imposible localizar el espacio libre (y por lo tanto susceptible de contener datos eliminados) de las páginas que forman parte de un overflow.

Todos las entradas de la serie:

4 comments :

Angel Alvarez Nuñez dijo...

Esperando impaciente la continuacion XD

fr0g dijo...

Muy bueno, pero podría sugerir que en cada entrada al principio se añadieran los enlaces a cada una de las entradas anteriores¿ es un engorro ir buscando uno a uno..
Bueno, un saludo!

Alejandro Ramos dijo...

Lo haré cuando estén todas, es que ahora mismo no se cual será el link de la siguiente y eso me ha ido pasando en todas.


Aunque de momento, tienes la etiqueta sqlite:
http://www.securitybydefault.com/search/label/sqlite

fr0g dijo...

Graciñas!