0x00 Предыстория
Ради уменьшения размера бинарника на что только не пойдешь. Имеет ли это смысл на текущий момент можно спорить много, но сейчас не об этом.
Бывает так что программе нужно прочитать записи из базы данных sqlite3, казалось бы, что сложного, используем официальный код от разработчиков на С, либо байдинги и адаптации под другие языки, но отпугивает одно - плюс 500кб к бинарю или около того. И если адепта байтодрочерства это не устраивает, то приходится идти на некоторые ухищерения. Пример такого мы можем найти в сорцах старой доброй Pony. Автор реализовал свой движок читалки sqlite3 баз. Линк - https://github.com/nyx0/Pony/blob/master/source/PonySrc/PasswordModules.asm#L6976 . Ассемблер это конечно хорошо, но с переносимостью проблемы, к тому же судя по коду читалка реализована не полностью.
Есть более интересный пример, это старый код на VisualBasic. Линк - https://github.com/mwsrc/PlasmaRAT/blob/master/Stub/Misc/SQLite.vb. В те далёкие времена VB был в моде, например 9 из 10 крипторов были на VB. Пока мода не перешла на C#. И тогда этот код был толи переконвертирован, толи переписан на любимый язык начинающего мыловара. Линк - https://github.com/swagkarna/Echelon-Stealer/blob/master/Stealer/Browsers/Chromium/SqlHandler.cs. Наверно шутки ради в конце-концов сорец был переписан и на C - https://github.com/H4xl0r/Necro-Stealer/blob/master/NecroStealer/NecroSteal/SqlHandler.cpp.
Проблемы этих читалок в том, что они не полностью умеют читать базы, в реализациях много допущений. По этому я захотел подробнее изучить внутреннее устройсто sqlite3 и описать пошагово и на пальцах, из чего состоит база, как ее парсить и в какой последовательности. Свою реализацию прототипа парсера-читалки я набросаю на python3.
0x01 Начинаем разбираться
Откуда брать информацию, кроме как не с офф-сайта sqlite3. Разработчиками был описан формат файла по моему мнению очень сухо и сложно, но других вариантов нет: отправная точка - https://www.sqlite.org/fileformat2.html, плюс к этому сами сорцы https://github.com/sqlite/sqlite.
И так, из чего состоит файл БД? Как и многие другие форматы файлов, первым в структуре идет заголовок. Заголовок в sqlite3 занимает 100 байтов в начале файла
Заголовок sqlite3 в hex-редакторе
Для чтения нам нужны не все, опишем нужные:
- По смещению 16 в заголовке расположено двухбайтовое число - это размер страницы
- Смещение 56 - кодировка текста в базе данных, 4 байта
- Смещение 20 - число, которое означает сколько зарезервированных байтов содержится на каждой странице - 1 байт
Все числа записаны в формате big-endian - то есть прямой порядок байтов.
По немногу начнем писать парсилку, оформим как класс:
Python:
class TinySQlite:
def __init__(self):
self.buffer = None
self.Encoding = None
self.PageSize = None
Файл базы будем читать сразу весь в буфер, также прочитаем нужные нам значения из заголовка:
Python:
def loadDB(self, path):
f = open(path, 'rb')
self.buffer = f.read()
f.close()
self.Encoding = self.unp('>I', 56)
self.PageSize = self.unp('>H', 16)
self.PageReservedSpace = self.unp('>B', 20)
if self.PageSize == 1:
self.PageSize = 65536
def unp(self, fmt, offset):
return struct.unpack_from(fmt, self.buffer, offset)[0]
unp(self, fmt, offset) - извлекает значение из буфера в нужном нам представлении.Подробнее про размер страницы: размер страницы должен быть степенью двойки между 512 и 65536. Это число записано в заголовке, но число 65536 не поместится в два байта, по этому если там единица, то воспринимаем её как 65536.
0x02 Страницы и ячейки
Теперь про страницы. Файл условно поделен на равные блоки - страницы. По сути они являются элементами бинарного дерева (BTree), формат sqlite3 построен на этой концепции.
У страницы тоже есть заголовок, он занимает либо 8 либо 12 байт в начале, размер зависит от типа страницы. Тип страницы - первый байт заголовка.
0x02 - interior index b-tree page.
0x05 - interior table b-tree page.
0x0a - leaf index b-tree page.
0x0d - leaf table b-tree page.
По мимо вышеперечисленных есть еще так называемые страницы переполнения, они не имеют заголовка, но о них чуть позже.
Забегая на перед - данные хранятся в ячейках. Ячейки содержаться на страницах BTree.
Далее по иерархии идут ячейки, которые хранятся на страницах бинарного дерева. И формат записи ячеек зависит от того, на какой странице они находятся.
Прежде чем описать формат ячеек нужно объяснить пару моментов.
В sqlite3 используются числа с переменной длинной, называются varint. Они нужны чтоб экономить место на страницах, принцип кодировки похож на то как кодируются символы в UTF-8. Varint занимает от 1 до 9 байт и может кодировать числа до 64 бит. Функция которая читает varint и возвращает закодированное число и занимаемое им место:
Python:
def readVarInt(self, stream, offset=0):
ret = 0
chr = struct.unpack(">B", stream[offset:offset+1] )[0]
of = 1
while(chr & 0x80 and of < 9):
ret = ret << 7
ret += chr & 0x7F
chr = struct.unpack(">B", stream[offset+of:offset+of+1] )[0]
of += 1
ret = ret << 7
ret += chr
return ret, of
Вернемся к ячейкам. В зависимости от типа страницы ячейка состоит из:
0x02 - interior index b-tree page
- 4 байтовое число - номер страницы на которой хранится предыдущие ячейки
- varint - количество байт, занимаемое полезной нагрукой (payload)
- непосредственно сам payload
- 4 байтовое число - номер страницы на котором хранится часть payload, если она не поместилась в ячейке. Если поместилась, то это число игнорируется
0x05 - interior table b-tree page
- 4 байтовое число - номер страницы на которой хранится предыдущие ячейки
- varint, который нам не интресен
0x0a - leaf index b-tree page
- varint - количество байт, занимаемое payload
- payload
- 4 байтовое число - номер страницы переполнения
0x0d - leaf table b-tree page
- varint - количество байт, занимаемое payload
- varint - rowid, это уникальный номер строки
- payload
- 4 байтовое число - номер страницы переполнения
Теперь вернемся к страницам, формат заголовка такой:
- смещение 0, размер 1 байт - тип страницы (0x02, 0x05, 0x0a, 0x0d)
- смещение 3, размер 2 байта - количество ячеек на странице
- смещение 8, размер 4 байта - номер последней страницы с дочерними элементами. Только для interior страниц, на leaf страницах нет этого в заголовке
Сразу после заголовка идут N двухбайтовых чисел, которые являются смещениями к ячейкам, где N - количество ячеек на странице
Алгоритм чтения ячеек со страницы следующий:
1 - получаем количество ячеек на странице
2 - крутим цикл от 0 до N-1 в котором читаем смещения к ячейкам
2.1 - читаем ячейку по смещению
2.2 - если interior страница, то достаем из ячейки номер дочерней страницы и парсим ее
3 - в случае interior страниц читаем номер последней страницы с дочерними элементами, и парсим эту страницу
Про переполнения и страницы переполнения.
Если payload не помещается полностью в ячейку, то та часть которая не помещается записывается на одну или несколько страниц переполнений. Страницы переполнения образуют связный список. Формат страницы переполнения простой - первые 4 байта это номер следующей страницы в списке, остальное payload. Объясню алгоритм на примере:payload не поместился в ячейке полностью, поместилась только начальная часть, из ячейки считываем эту часть, далее перемещаемся на страницу переполнений, номер которой указан в ячейке, считываем оттуда остальное, если номер следующей страницы не равен 0, то переходим на следующую страницу и так далее по списку, пока номер не будет 0.
Заголовок страницы leaf table b-tree page
Пора разбавить текст кодом, реализация прохода страницы:
Python:
def readTable(self, pagenum):
rows = []
offset = self.pageNumToOffset(pagenum)
hdr = 0
if pagenum == 1:
hdr = 100
nCell = self.unp('>H', offset+hdr+3)
pageTypeFlag = self.buffer[offset+hdr]
if pageTypeFlag in [2, 5]:
cellstart = offset+hdr+12
for i in range(0, nCell):
ofst = self.unp('>H', cellstart+(i*2))
child = self.unp('>I',offset + ofst)
rows = rows + self.readTable(child)
if pageTypeFlag == 2:
rows.append(self.dumpCell(self.readCell(offset + ofst, pageTypeFlag)))
child = self.unp('>I', cellstart-4)
rows = rows + self.readTable(child)
if pageTypeFlag in [10, 13]:
cellstart = offset+hdr+8
for i in range(0, nCell):
ofst = self.unp('>H', cellstart+(i*2))
cellbuffer = self.readCell(offset + ofst, pageTypeFlag)
rows.append(self.dumpCell(cellbuffer))
return rows
Python:
def pageNumToOffset(self, pagenum):
return (pagenum - 1) * self.PageSize
Python:
def readCell(self, offset, pageTypeFlag):
if pageTypeFlag == 2:
offset = offset + 4
recordsize, vi = self.readVarInt(self.buffer, offset)
rowid, vi2 = 0, 0
if pageTypeFlag == 13:
rowid, vi2 = self.readVarInt(self.buffer, offset+vi)
onOverflow = self.getOnOverflow(recordsize, pageTypeFlag)
onTree = recordsize - onOverflow
buffer = self.buffer[offset+vi+vi2:offset+onTree+vi+vi2]
if onOverflow == 0:
return buffer
if onOverflow > 0:
overflowpagenum = self.unp('>I', offset+onTree+vi+vi2)
buffer = buffer + self.readOverflow(overflowpagenum, onOverflow)
return buffer
Python:
def readOverflow(self, pagenum, bytestoread):
buffer = b""
readflag = True
while readflag == True:
offset = self.pageNumToOffset(pagenum)
nextpage = self.unp('>I', offset)
sizeofpayloadonpage = self.PageSize-self.PageReservedSpace-4
if sizeofpayloadonpage >= bytestoread:
buffer = buffer + self.buffer[offset+4: offset+4+bytestoread]
if nextpage == 0:
readflag = False
else:
pagenum = nextpage
buffer = buffer + self.buffer[offset+4: offset+4+sizeofpayloadonpage]
bytestoread = bytestoread - sizeofpayloadonpage
return buffer
Еще немного про переполнения, какая часть полезной нагрузки запишется в ячейку, а какая часть уйдет на страницы переполнения зависит от типа страницы и расчитывается по определенной формуле. Функция, реализующая этот расчет:
Python:
def getOnOverflow(self, recordsize, pageTypeFlag):
U = self.PageSize - self.PageReservedSpace
X = U - 35
if pageTypeFlag == 10 or pageTypeFlag == 2:
X = ((U-12)*64//255)-23
P = recordsize
M = ((U-12) * 32//255) - 23
K = M + ((P-M) % (U-4))
onOverflow = 0
if P>X and K<=X:
onOverflow = P-K
if P>X and K>X:
onOverflow = P-M
return onOverflow
Последнее про страницы, первая страница имеет одну особенность. В нее включен 100 байтовый заголовок самой базы данных, по этому заголовок самой страницы будет смещен на 100 байт - это необходимо учитывать.
0x03 Полезная нагрузка
В предыдущей главе описаны проход страницы и чтение из ее ячеек полезной нагрузки. Теперь подробнее про payload.
В payload закодированы данные, которые являются ячейками нужных нам таблиц. Разберемся из чего он состоит.
Как обычно в начале заголовок, после заголовка тело. Заголовок состоит из varint`ов, первый varint это размер заголовка, остальные - так называемые serial types. Тело же состоит из записанных друг за другом значений.
По серийному типу можно узнать тип и размер ячейки в теле.
Серийные типы:
| Серийный тип | Размер в байтах | Значение в ячейке |
|---|---|---|
0 | 0 | Null |
1 | 1 | Integer, 1 байт |
2 | 2 | Integer, 2 байта |
3 | 3 | Integer, 3 байта |
4 | 4 | Integer, 4 байта |
5 | 6 | Integer, 6 байтов |
6 | 8 | Integer, 8 байтов |
7 | 8 | Double, число с плавующей запятой, 8 байтов |
8 | 0 | Число 0 |
9 | 0 | Число 1 |
N≥12 и при этом четное | (N-12)/2 | Произвольные бинарные данные, BLOB |
N≥13 и при этом нечетное | (N-13)/2 | Текстовая строка |
Реализация чтения данных из полезной нагрузки:
Python:
def dumpCell(self, cellbuffer):
RecordHeaderSize, vi3 = self.readVarInt(cellbuffer, 0)
x = RecordHeaderSize - vi3
ofc = vi3
offsettodata = RecordHeaderSize
items = []
while x > 0:
serialtype, vi4 = self.readVarInt(cellbuffer, ofc)
item = self.readValueFromCellbuffer(cellbuffer, serialtype, offsettodata)
items.append(item)
ofc = ofc + vi4
x = x - vi4
offsettodata = offsettodata + self.contentSizeBySerialType(serialtype)
return items
Преобразование данных в нужный формат:
Python:
def readValueFromCellbuffer(self, cellbuffer, stype, offset):
if stype == 0:
return None
if stype == 8:
return 0
if stype == 9:
return 1
if stype in [1,2,3,4,5,6]:
return int.from_bytes(cellbuffer[offset: offset+self.contentSizeBySerialType(stype)], "big")
if stype == 7:
return struct.unpack('>d', cellbuffer[offset: offset+self.contentSizeBySerialType(stype)] )[0]
if stype >= 12 and IsEven(stype):
return cellbuffer[offset: offset+self.contentSizeBySerialType(stype)]
if stype >= 13 and IsOdd(stype):
if self.Encoding == 1:
return cellbuffer[offset: offset+self.contentSizeBySerialType(stype)].decode("utf-8")
if self.Encoding == 2:
return cellbuffer[offset: offset+self.contentSizeBySerialType(stype)].decode("utf-16le")
if self.Encoding == 3:
return cellbuffer[offset: offset+self.contentSizeBySerialType(stype)].decode("utf-16be")
0x04 Master table
Информация о том, сколько таблиц в базе, где они расположены, какие имеют поля и т.д. находится в главной таблице, она же master table и sqlite_master. Эта таблица размещается всегда на первой странице базы данных. Таблица имеет следующие поля:
- type - тип 'table', 'index', 'view' или 'trigger' - нам интересны только table
- name - имя элемета
- tbl_name - имя таблицы, к которой относится элемент
- rootpage - номер страницы на которой находится элемент - то что нам нужно
- sql - SQL запрос которым был создан этот элемент. Если нужно получать названия колонок таблиц, то придется доставать их из запроса
Итого алгоритм для чтения нужной нам таблицы следующий:
- Парсим master_table, ищем запись с именем нашей таблицы в tbl_name
- Получаем смещение до страницы с таблицой по rootpage
- Парсим таблицу
0x05 Важные моменты
Допустим, таблица создана следующим sql-запросом:
CREATE TABLE mytable (id INTEGER PRIMARY KEY, data TEXT)
Когда мы распарсим страницы, то в поле id у нас будет NULL. Все потому что первичный ключ в payload будет опущен, его роль примет на себя rowid из ячейки. Такая таблица будет размещаться на страницах interior table b-tree page и leaf table b-tree page.
Если же данная таблица будет создана таким запросом
CREATE TABLE mytable (id INTEGER PRIMARY KEY, data TEXT) WITHOUT ROWID
, то с полями будет все нормально, но таблица будет размещаться уже на interior index b-tree page и leaf index b-tree page.
0x06 Заключение
По итогу формат формат sqlite3 оказался не слишком сложным. В отличие от существующих решений были реализованы чтение индексных страниц и чтение страниц переполнений. Возможно после прочтения статьи у читателя остануться пробелы, по этому ниже будет опубликован полный код класса, это примерно 200 строк кода, благодаря тому что питоновский код очень понятный и простой - можно изучить формат базы прям по коду. Скрипт читает базу и выводит значения из всех таблиц, иными словами дампит базу, значения пишутся в кортеж, таблица представляется как кортеж кортежей.
Полный исходный код:
Python:
# -*- coding: utf-8 -*-
# !/bin/python
import os
import struct
def IsEven(a):
return a % 2 == 0
def IsOdd(a):
return not IsEven(a)
class TinySQlite:
def __init__(self):
self.buffer = None
self.Encoding = None
self.PageSize = None
def loadDB(self, path):
f = open(path, 'rb')
self.buffer = f.read()
f.close()
self.Encoding = self.unp('>I', 56)
self.PageSize = self.unp('>H', 16)
self.PageReservedSpace = self.unp('>B', 20)
if self.PageSize == 1:
self.PageSize = 65536
def unp(self, fmt, offset):
return struct.unpack_from(fmt, self.buffer, offset)[0]
def readVarInt(self, stream, offset=0):
ret = 0
chr = struct.unpack(">B", stream[offset:offset+1] )[0]
of = 1
while(chr & 0x80 and of < 9):
ret = ret << 7
ret += chr & 0x7F
chr = struct.unpack(">B", stream[offset+of:offset+of+1] )[0]
of += 1
ret = ret << 7
ret += chr
return ret, of
def pageNumToOffset(self, pagenum):
return (pagenum - 1) * self.PageSize
def contentSizeBySerialType(self, stype):
if stype <= 4:
return stype
if stype == 5:
return 6
if stype == 6 or stype == 7:
return 8
if stype == 8 or stype == 9:
return 0
if stype >= 12 and IsEven(stype):
return (stype-12)//2
if stype >= 13 and IsOdd(stype):
return (stype-13)//2
def readValueFromCellbuffer(self, cellbuffer, stype, offset):
if stype == 0:
return None
if stype == 8:
return 0
if stype == 9:
return 1
if stype in [1,2,3,4,5,6]:
return int.from_bytes(cellbuffer[offset: offset+self.contentSizeBySerialType(stype)], "big")
if stype == 7:
return struct.unpack('>d', cellbuffer[offset: offset+self.contentSizeBySerialType(stype)] )[0]
if stype >= 12 and IsEven(stype):
return cellbuffer[offset: offset+self.contentSizeBySerialType(stype)]
if stype >= 13 and IsOdd(stype):
if self.Encoding == 1:
return cellbuffer[offset: offset+self.contentSizeBySerialType(stype)].decode("utf-8")
if self.Encoding == 2:
return cellbuffer[offset: offset+self.contentSizeBySerialType(stype)].decode("utf-16le")
if self.Encoding == 3:
return cellbuffer[offset: offset+self.contentSizeBySerialType(stype)].decode("utf-16be")
def readOverflow(self, pagenum, bytestoread):
buffer = b""
readflag = True
while readflag == True:
offset = self.pageNumToOffset(pagenum)
nextpage = self.unp('>I', offset)
sizeofpayloadonpage = self.PageSize-self.PageReservedSpace-4
if sizeofpayloadonpage >= bytestoread:
buffer = buffer + self.buffer[offset+4: offset+4+bytestoread]
if nextpage == 0:
readflag = False
else:
pagenum = nextpage
buffer = buffer + self.buffer[offset+4: offset+4+sizeofpayloadonpage]
bytestoread = bytestoread - sizeofpayloadonpage
return buffer
def getOnOverflow(self, recordsize, pageTypeFlag):
U = self.PageSize - self.PageReservedSpace
X = U - 35
if pageTypeFlag == 10 or pageTypeFlag == 2:
X = ((U-12)*64//255)-23
P = recordsize
M = ((U-12) * 32//255) - 23
K = M + ((P-M) % (U-4))
onOverflow = 0
if P>X and K<=X:
onOverflow = P-K
if P>X and K>X:
onOverflow = P-M
return onOverflow
def dumpCell(self, cellbuffer):
RecordHeaderSize, vi3 = self.readVarInt(cellbuffer, 0)
x = RecordHeaderSize - vi3
ofc = vi3
offsettodata = RecordHeaderSize
items = []
while x > 0:
serialtype, vi4 = self.readVarInt(cellbuffer, ofc)
item = self.readValueFromCellbuffer(cellbuffer, serialtype, offsettodata)
items.append(item)
ofc = ofc + vi4
x = x - vi4
offsettodata = offsettodata + self.contentSizeBySerialType(serialtype)
return items
def readCell(self, offset, pageTypeFlag):
if pageTypeFlag == 2:
offset = offset + 4
recordsize, vi = self.readVarInt(self.buffer, offset)
rowid, vi2 = 0, 0
if pageTypeFlag == 13:
rowid, vi2 = self.readVarInt(self.buffer, offset+vi)
onOverflow = self.getOnOverflow(recordsize, pageTypeFlag)
onTree = recordsize - onOverflow
buffer = self.buffer[offset+vi+vi2:offset+onTree+vi+vi2]
if onOverflow == 0:
return buffer
if onOverflow > 0:
overflowpagenum = self.unp('>I', offset+onTree+vi+vi2)
buffer = buffer + self.readOverflow(overflowpagenum, onOverflow)
return buffer
def readTable(self, pagenum):
rows = []
offset = self.pageNumToOffset(pagenum)
hdr = 0
if pagenum == 1:
hdr = 100
nCell = self.unp('>H', offset+hdr+3)
pageTypeFlag = self.buffer[offset+hdr]
if pageTypeFlag in [2, 5]:
cellstart = offset+hdr+12
for i in range(0, nCell):
ofst = self.unp('>H', cellstart+(i*2))
child = self.unp('>I',offset + ofst)
rows = rows + self.readTable(child)
if pageTypeFlag == 2:
rows.append(self.dumpCell(self.readCell(offset + ofst, pageTypeFlag)))
child = self.unp('>I', cellstart-4)
rows = rows + self.readTable(child)
if pageTypeFlag in [10, 13]:
cellstart = offset+hdr+8
for i in range(0, nCell):
ofst = self.unp('>H', cellstart+(i*2))
cellbuffer = self.readCell(offset + ofst, pageTypeFlag)
rows.append(self.dumpCell(cellbuffer))
return rows
def dumpDB(self):
master_table = self.readTable(1)
for row in master_table:
print("=====================================")
print(row)
print("=====================================")
rootpage = row[3]
if rootpage > 0:
for trow in self.readTable(rootpage):
print(trow)
if __name__ == "__main__":
db = TinySQlite()
db.loadDB(os.path.dirname(os.path.realpath(__file__)) + '/database.db')
db.dumpDB()