Хотя в SQLite и нет возможности прочитать удаленные данные после завершения транзакции, сам формат файла позволяет отчасти сделать это. Подробности — под катом.
Прежде чем перейти непосредственно к теме статьи, необходимо рассмотреть строение файлов SQLite. Файл базы поделен на части, называемыми страницами (page). Чтение и запись в файл ведется целыми страницами. Все страницы пронумерованы, начиная с 1, и имеют одинаковый размер, задаваемый в заголовке файла, который располагается в первых 100-байтах (и соответственно на первой странице). Некоторые значения заголовка приведены ниже, а полный список доступен здесь.
Данные в файле записываются в прямом порядке (big-endian), то есть два последовательных байта
Пример заголовока файла в HEX-редакторе
Данные таблиц хранятся в виде сбалансированных деревьев (B+-tree), где вершины разделены на две группы — внутренние (interior) и листья (leaf/leaves). Строение страниц у групп различно из-за разного назначения: внутренние хранят иерархию, а листья — данные. Индексы и таблицы без rowid хранятся в сбалансированных деревьях (B-tree), у которые для обоих типов вершин используют структуру аналогичную внутренним страницам B+-tree. Если данные, напр. длинный текст или BLOB, не помещаются полностью на страницу, то они переносятся на страницы переполнения (overflow pages), организованные в лист, где первые 4 байта такой страницы указывают номер следующей в листе. Учет неиспользуемого (резервного) места ведется с помощью списка свободных страниц (free list), которые также делятся на корневые (trunk) и листья (leaf). Дополнительные данные для работы операций
После массового удаления строк, размер базы данных остается прежним, поскольку гораздо дешевле с точки зрения ввода-вывода пометить страницы как пустые (иначе говоря поместить в список свободных), чтобы потом, когда потребуется место для сохранения новых данных, использовать их, а сдвигать на освободившееся место данные, чтобы уменьшить размер файла, как это делает команда
Организация списка свободных страниц (freelist) в SQLite
Часть свободных страниц хранится в виде листьев корневых страниц для оптимизации — данные листьев никогда не читаются.
На каждой странице хранятся данные только одного и того же объекта; каждый объект имеет ровно одну стартовую страницу (корень дерева), которая уже содержит ссылки уже на другие.
Первая страница базы данных используется как корневая страница специальной таблицы
Заголовок B/B+-tree страницы имеет следующую структуру
Таким образом, длина заголовка 8 байт для листьев и 12 для внутренних страниц. Сразу после заголовка идет массив по два байта, на каждую хранимую ячейку на странице, где хранится положение этой ячейки на странице. Хотя это и может быть вычислено по заголовку и последовательному перебором ячеек. Обратите внимание, что ячейки записываются с конца, поднимаясь вверх в незанятую область.
Общий вид B/B+-tree страницы
При добавлении новой ячейки на страницу, сначала будет проведена попытка записать данные в один из свободных блоков, и если подходящего по размеру блока не нашлось, то в незанятую область.
Прежде чем продолжить описание B/B+-tree страниц, стоит рассмотреть как SQLite кодирует целочисленные значения, что позволяет, в зависимости от величины значения, хранить его в виде последовательности от 1 до 9 байт, а не обычных фиксированных 4-х байт, и таким образом экономить место.
Как легко видеть числа от 0 до 127 (27 — 1) требуют для хранения 1 байт, от 128 до 16383 (214 — 1) — два байта и так далее. Обратной стороной медали является то, что любое отрицательное число требует 9 байт. Минимальное целое число представляется как
Данные страницы хранят иерархию, где каждая ячейка — это пара, состоящая из номера страницы (4 байта) и ключа (varint, для таблицы ключ — это идентификатор строки
Если определение первичного ключа таблицы отлично от
Каждая ячейка (строка таблицы) состоит из набора: размер всех данных ячейки в байтах, идентификатор строки
Состав ячейки на листе B+-tree
Кодирование типа значения, подбираемого по записываемой величине
Если в таблице есть первичный ключ, то его значение будет использоваться как
Пример ячейки на листе B+-tree
При удалении строки занимаемое место помечается как пустое, путем изменения первых 4 байт ячейки: в первые два записывается расстояние от начала страницы до следующего пустого блока и
Пример трех удаленных строк, две из которых были соседними.
Образовалось два свободных блока. Начало большего, состоящего из оранжевого и маджента?, содержит позицию меньшего, выделенного желтым цветом. По указателю на желтый блок, можно утвержать, что сначала была удалена желтая строка, потом маджента, а после — оранжевая.
Если на странице удаляются все строки, то она переносится в список свободных (корневую или листовую). Перенос страниц происходит также при удалении самой таблицы. При обновлении данных, когда места для новых значений не достаточно, старое место на странице помечается как свободное, и добавляется строка с новыми значениями и старым номером строки (rowid).
Поскольку свободная страница, когда начинает использоваться, напр. для хранения индекса или переполнения, предварительно очищается, то поиск удаленных данных можно ограничить листьями таблиц (незанятое место и свободные блоки) и свободными страницами (корневыми и листовыми). Если прагма
После удаления таблицы командой
Самый наивный и простой способ восстановить данные из блока — это последовательно читать байты, и пытаться декодировать данные, считая, что текущий байт — это начало ячейки. Если это удалось сделать без ошибок (все типы в заголовке строки не равны 10 и 11 и, если есть текстовое поле, то все его данные действительно текст, заданной в заголовке длины), значит скорее всего такая строка была. Строки с поврежденным заголовком (строки) при этом найдены не будут.
Однако зачастую при удалении строки на листе таблицы может быть поврежден не только заголовок ячейки: при типовом использовании SQLite (короткие текстовые данные, хранящиеся в небольших таблицах) для кодирования размера ячейки,
По сути, если отбросить случаи, когда данные строки используют страницу переполнения, задача восстановления строки сводится к определению положения заголовка, записанных в нем типах и их количестве. Для решения этой задачи можно воспользоваться нижеописанным способом.
Сначала надо вывести заголовок строки в «обобщенном» виде, т.е. как строку вида
После того, как «обобщенный» заголовок определен можно попробовать найти его положение в данных, последовательно двигаясь с начала блока до тех пор пока декодирование не даст этот заголовок. Если это не удалось или декодирование строки дает некорректный результат, то отбросить первый тип и попробовать снова. Понятно, что чем меньше «обобщенный» заголовок содержит типов, тем больше вероятность обнаружить не сам заголовок, а случайные данные. Более того, типы такого заголовка могут не полностью совпадать с типами в конкретной строке, т.к. SQLite подбирает тип по значению, и потому для числа
Если заголовок был найден без первого типа, то требуется восстановить этот тип, чтобы понять сколько первых байт он занимает в данных строки. В зависимости от того к какому обобщенному типу принадлежал отсутсвующий
Отмечу, что на свободных страницах, используемых ранее для индекса, содержится информация в виде список проиндексированных значений +
Данная статья возникла как результат прикручивания еще одной фичи для моего проекта sqlite-gui. Поначалу я думал ограничиться встраиванием undark, но он падал с ошибкой на тестовых базах, и потому я решил разобраться в вопросе получше.
Важно понимать, что восстановление возможно только когда значения прагм secure_delete и auto_vacuum равны 0. Обработка BLOB-полей, файлов журналов, индексов и таблиц без rowid осталась за рамками статьи.
Если требуется только восстановить поврежденную базу, то достаточно воспользоваться командами.recoverи.dumpв SQLite CLI. Имейте в виду, что сообщение о поврежденной базе может выводиться, если она зашифрована и указаны неверный метод шифрования, пароль или другие параметры.
Прежде чем перейти непосредственно к теме статьи, необходимо рассмотреть строение файлов SQLite. Файл базы поделен на части, называемыми страницами (page). Чтение и запись в файл ведется целыми страницами. Все страницы пронумерованы, начиная с 1, и имеют одинаковый размер, задаваемый в заголовке файла, который располагается в первых 100-байтах (и соответственно на первой странице). Некоторые значения заголовка приведены ниже, а полный список доступен здесь.
| Сдвиг | Размер | Описание |
|---|---|---|
| 16 | 2 | Размер страницы в байтах. Должно быть степенью 2. Если равно 1, то подразумевается 65536. |
| 20 | 1 | Неиспользуемое число байт с конца, резервируемое для специального применения, напр. хранения контрольной суммы страницы, если база шифруется. Обычно 0. |
| 28 | 4 | Число страниц в базе. Умноженное на размер страницы должно совпадать с размером файла на диске. |
| 32 | 4 | Номер первой свободной корневой страницы (freelist page) |
| 36 | 4 | Число всех свободных страниц в базе |
| 56 | 4 | Кодировка: 1 — UTF-8, 2 — UTF-16LE, 3 — UTF-16BE. |
0B 03 представляют число B0316 = 11 * 162 + 160 * 310 = 281910.Данные таблиц хранятся в виде сбалансированных деревьев (B+-tree), где вершины разделены на две группы — внутренние (interior) и листья (leaf/leaves). Строение страниц у групп различно из-за разного назначения: внутренние хранят иерархию, а листья — данные. Индексы и таблицы без rowid хранятся в сбалансированных деревьях (B-tree), у которые для обоих типов вершин используют структуру аналогичную внутренним страницам B+-tree. Если данные, напр. длинный текст или BLOB, не помещаются полностью на страницу, то они переносятся на страницы переполнения (overflow pages), организованные в лист, где первые 4 байта такой страницы указывают номер следующей в листе. Учет неиспользуемого (резервного) места ведется с помощью списка свободных страниц (free list), которые также делятся на корневые (trunk) и листья (leaf). Дополнительные данные для работы операций
auto_vacuum и incremental_vacuum хранятся на страницах указателей (pointer map или ptrmap pages). Файлы, размер которых превышает 1Гб, имеют одну дополнительную страницу блокировок (lock-byte), располагающуюся всегда на 1073741824 байте и имеющую размер 512 байт. Для восстановления данных достаточно рассмотреть строение страниц у таблиц и списка свободных.Свободные страницы (free list)
После массового удаления строк, размер базы данных остается прежним, поскольку гораздо дешевле с точки зрения ввода-вывода пометить страницы как пустые (иначе говоря поместить в список свободных), чтобы потом, когда потребуется место для сохранения новых данных, использовать их, а сдвигать на освободившееся место данные, чтобы уменьшить размер файла, как это делает команда
VACUUM, удаляющая все свободные страницы из базы, и для больших таблиц занимающая значительное время. Эти страницы хранятся в виде связанного списка корневых (trunk) страниц, где каждая страница в первых 4-х байтах (INTEGER) хранит ссылку (номер) на следующую корневую (или ноль, если больше страниц нет), в следующих 4-х байтах число листьев и далее список номеров этих страниц (по 4 байта на номер).Часть свободных страниц хранится в виде листьев корневых страниц для оптимизации — данные листьев никогда не читаются.
B/B+-tree страницы
На каждой странице хранятся данные только одного и того же объекта; каждый объект имеет ровно одну стартовую страницу (корень дерева), которая уже содержит ссылки уже на другие.
Первая страница базы данных используется как корневая страница специальной таблицы
sqlite_master (она же sqlite_schema), содержащей перечень всех объектов базы данных (их тип, имя, DDL-создания), а для таблиц и индексов еще и номер их корневой страницы. Эта страница по содержимому меньше обычной на 100 байт, поскольку содержит еще и заголовок файла, и ее заголовок располагается на 100 байте, а не нулевом. Для обработки первой страницы стоит иметь в виду, что все сдвиги (offsets) указываются от начала страницы, а не начала заголовка страницы.Заголовок B/B+-tree страницы имеет следующую структуру
| Сдвиг | Размер | Описание |
|---|---|---|
| 0 | 1 | Тип страницы0x02 — внутренняя B-tree индекса0x05 — внутренняя B+-tree таблицы0x0a — лист B-tree индекса0x0d — лист B+-tree таблицы |
| 1 | 2 | Положение первого свободного блока (free block) на странице. Не стоит путать с freelist-страницами. Каждый незанятый блок, представляющий непрерывный участок на странице, в начале хранит позицию следующего пустого блока (2 байта) и свою длину (2 байта), поэтому в заголовке достаточно хранить только позицию первого. |
| 3 | 2 | Число ячеек (cell), хранящих информацию на этой странице. Как и свободный блок, ячейка — это непрерывный участок на странице. Для листьев каждая ячейка хранит всю строку таблицы (за исключением тех случаев, когда не помещается, напр. BLOB с картинкой), а для внутренних — «указатель» на дочернюю ячейку. |
| 5 | 2 | Положение первой ячейки на странице. |
| 7 | 1 | Число свободных блоков длиной меньше 3 байт (видимо потому, что в таких блоках не хватает места для хранения данные о себе). |
| 8 | 4 | Только для внутренних страниц. Номер страницы, где хранится правый/самый большой/следующий узел дерева. |
При добавлении новой ячейки на страницу, сначала будет проведена попытка записать данные в один из свободных блоков, и если подходящего по размеру блока не нашлось, то в незанятую область.
Тип данных varint
Прежде чем продолжить описание B/B+-tree страниц, стоит рассмотреть как SQLite кодирует целочисленные значения, что позволяет, в зависимости от величины значения, хранить его в виде последовательности от 1 до 9 байт, а не обычных фиксированных 4-х байт, и таким образом экономить место.
| Число байт | Диапазон | Шаблон |
|---|---|---|
| 1 | 7 бит | 0XXXXXXX |
| 2 | 14 бит | 1ХХХХХХХ 0ХХХХХХХ |
| 3 | 21 бит | 1ХХХХХХХ 1ХХХХХХХ 0ХХХХХХХ |
| ... | ... | ... |
| 9 | 64 бита | 1XXXXXXX 1XXXXXXX 1XXXXXXX 1XXXXXXX 1XXXXXXX 1XXXXXXX 1XXXXXXX 1XXXXXXX XXXXXXXX |
C0 80 80 80 80 80 80 80 80, а максимальное отрицательное, т.е. -1, как FF FF FF FF FF FF FF FF FF. Алгоритм получения значения по его позиции предполагает побайтное чтение пока не будет обнаружен ведущий ноль (значение байта менее 128) или не прочитано 9 байт.
Перекодирование данных из последовательности байт в int64 (из showdb.c)
/* Возвращает число прочитанных байт */
int decodeVarint (const unsigned char *z, int64_t *pVal) {
int64_t v = 0;
int i;
for (i = 0; i < 8; i++) {
v = (v << 7) + (z[i] & 0x7f);
if ((z[i] & 0x80) == 0) {
*pVal = v;
return i + 1;
}
}
v = (v << 8) + (z[i] & 0xff);
*pVal = v;
return 9;
}
Внутренние (interior) страницы
Данные страницы хранят иерархию, где каждая ячейка — это пара, состоящая из номера страницы (4 байта) и ключа (varint, для таблицы ключ — это идентификатор строки
rowid). При этом ячейки отсортированы по ключу. Принцип поиска по дереву следующий: допустим требуется найти на какой странице хранится строка с rowid равным N. Если первая страница листовая, т.е. таблица помещается на один лист целиком, то поиск выполняется сразу на ней, перебором ячеек и сравнения их rowid с N. Если первая страница внутренняя, то выполняется проход по ячейкам страницы и ищется первая такая, что ее ключ (rowid) больше N. Если такая ячейка найдена, то выполняется переход на страницу, по номеру хранящемуся в первых 4-х байтах ячейки. Если же не найдено, то выполняется поиск на странице, указанной в последних байтах заголовка. И так до тех пор, пока не будет совершен переход на листовую страницу.Если определение первичного ключа таблицы отлично от
INTEGER PRIMARY KEY, когда например ключ составной или тестовый, то таблица использует автосгенерированный rowid, и потому для получения строки по ключу, сначала ищется её rowid в индексном дереве, а потом уже в дереве таблицы.Листовые (leaf) страницы
Каждая ячейка (строка таблицы) состоит из набора: размер всех данных ячейки в байтах, идентификатор строки
rowid, размер блока, где заданы типы хранимых значений по столбцам, включая в размер и это поле, сам блок состоящий из N-значений, задающих типы, а потом все N-значений без каких либо разделителей. Если всё значения не влезли, то в конце добавляется 4-х байтное поле, содержащее номер страницы, где хранится остальное (Overflow page). При этом размеры указываются такими, как если бы размер страницы был неограничен. Размер ячейки и заголовка строки, rowid, а так же типы, отвечающие строкам и BLOB, записываются как varint. Сами данные записываются как есть в big-endian порядке.
Определение наличия страницы переполнения
Зная позиции текущей и следующей ячейки, или если её нет, то конца страницы, можно узнать максимальную длину блока. Если эта длина меньше заданного размера ячейки, то последние 4 байта будут номером страницы переполнения. Поскольку размер ячейки при удалении строк обычно повреждается, то корректное восстановление строк с переполнением представляет проблему. Более того, страница переполнения переносится в список свободных, где отыскать её практически невозможно.
Кодирование типа значения, подбираемого по записываемой величине
| Код типа | Занимаемое место, байт |
Тип |
|---|---|---|
| 0 | 0 | NULL |
| N, от 1 до 4 | N | Целое число |
| 5 | 6 | Большое целое число |
| 6 | 8 | Еще большее целое число |
| 7 | 8 | Число с плавающей запятой (float, double) |
| 8, 9 | 0 | Не занимающие места в данных 0 и 1 |
| 10 и 11 | 0 | Не используется, зарезервировано |
| N, где N четное и больше 12 | (N — 12)/2 | BLOB |
| N, где N нечетное и больше 13 | (N — 13)/2 | Строка |
rowid, а тип этого значения в заголовке строки будет указан как NULL, и, соответственно, в данных это поле будет пропущено. При удалении строки занимаемое место помечается как пустое, путем изменения первых 4 байт ячейки: в первые два записывается расстояние от начала страницы до следующего пустого блока и
00 00, если этот блок последний, а в следующие два — полный размер пустого блока. При этом, если удаляемая строка одним из концов примыкала к свободному блоку, то образуется один блок и- Если свободный блок был слева, то все байты строки остаются неизменными, а изменяются вторые 2 байта блока, увеличивая длину на длину удаленной строки
- Если свободный блок был справа, то в первые два байта строки будут записаны первые два байта из блока (позиция следующего свободного блока), а во вторые два — сумма длин удаленной строки и блока
- Если примыкающий блок имел длину менее трех байт, то первые 2 байта образованного блока будут содержать позицию следующего свободного.
Образовалось два свободных блока. Начало большего, состоящего из оранжевого и маджента?, содержит позицию меньшего, выделенного желтым цветом. По указателю на желтый блок, можно утвержать, что сначала была удалена желтая строка, потом маджента, а после — оранжевая.
Если на странице удаляются все строки, то она переносится в список свободных (корневую или листовую). Перенос страниц происходит также при удалении самой таблицы. При обновлении данных, когда места для новых значений не достаточно, старое место на странице помечается как свободное, и добавляется строка с новыми значениями и старым номером строки (rowid).
Изменение в листовых страницах при добавлении и удалении колонки
Колонка добавляется в конец таблицы, однако на страницах это никак не сказывается, даже если задано значение по умолчанию: SQLite обнаружит, что в ячейке хранится меньшее число значений, чем определяется по DDL таблицы и при выдаче результата дополнит их. При восстановлении данных желательно учитывать это поведение.
При удалении столбца страницы меняются и все значения во всех ячейках переупаковываются. Поэтому процесс удаления столбца из большой таблицы займет много времени.
При удалении столбца страницы меняются и все значения во всех ячейках переупаковываются. Поэтому процесс удаления столбца из большой таблицы займет много времени.
Восстановление удаленных строк
Поскольку свободная страница, когда начинает использоваться, напр. для хранения индекса или переполнения, предварительно очищается, то поиск удаленных данных можно ограничить листьями таблиц (незанятое место и свободные блоки) и свободными страницами (корневыми и листовыми). Если прагма
secure_delete равна fast, то данные в освобождающихся блоках на листьях таблиц затираются нулями, но перенос листа таблицы в список свободных остается неизменным и потому данные на свободных страницах могут быть восстановлены.После удаления таблицы командой
DROP страницы этой таблицы переносятся в список свободных как есть. Аналогично происходит при выполнении DELETE, если в результате удаляются все строки страницы (за исключением первой страницы таблицы, которая даже будучи пустой, не будет добавлена в список свободных). В случае, если страница попадает в листовые списка свободных, то это самый простой случай и она может быть прочитана как обычный лист таблицы. В случае, если она стала корневой, то необходимо оценить объем занятого места. Если он незначителен, то возможно сохранился список позиций ячеек (или его часть) на странице и потому часть данных также можно прочитать.Самый наивный и простой способ восстановить данные из блока — это последовательно читать байты, и пытаться декодировать данные, считая, что текущий байт — это начало ячейки. Если это удалось сделать без ошибок (все типы в заголовке строки не равны 10 и 11 и, если есть текстовое поле, то все его данные действительно текст, заданной в заголовке длины), значит скорее всего такая строка была. Строки с поврежденным заголовком (строки) при этом найдены не будут.
Однако зачастую при удалении строки на листе таблицы может быть поврежден не только заголовок ячейки: при типовом использовании SQLite (короткие текстовые данные, хранящиеся в небольших таблицах) для кодирования размера ячейки,
rowid и размера заголовка строки достаточно трех байт, если каждое из них было менее 128, и потому первые 4 байта свободного блока затрут не только размер заголовка строки, но и первый тип значения.По сути, если отбросить случаи, когда данные строки используют страницу переполнения, задача восстановления строки сводится к определению положения заголовка, записанных в нем типах и их количестве. Для решения этой задачи можно воспользоваться нижеописанным способом.
Сначала надо вывести заголовок строки в «обобщенном» виде, т.е. как строку вида
itt, где i соотвествует любому целочисленному типу, t — текстовому полю, f — значению с плавающей точкой, n для NULL и ? для BLOB. Для блока с листовой страницы таблицы, данная строка может быть восстановлена из DDL таблицы, для блока с свободной страницы или страниц таблицы, у которой в DDL типы не указаны, по неповрежденной строке (или строкам). Поскольку у каждой строки на странице обобщенный заголовок один и тот же, то можно попробовать найти такую обобщенную строку, что для нее на странице найдется максимальное количество блоков, которые при перекодировании дадут эту строку, и предположить её заголовком.После того, как «обобщенный» заголовок определен можно попробовать найти его положение в данных, последовательно двигаясь с начала блока до тех пор пока декодирование не даст этот заголовок. Если это не удалось или декодирование строки дает некорректный результат, то отбросить первый тип и попробовать снова. Понятно, что чем меньше «обобщенный» заголовок содержит типов, тем больше вероятность обнаружить не сам заголовок, а случайные данные. Более того, типы такого заголовка могут не полностью совпадать с типами в конкретной строке, т.к. SQLite подбирает тип по значению, и потому для числа
111.0 тип будет не 0x07 (float), а 0x01 (int8). Аналогичное несовпадение типов будет и для NULL-значений.Если заголовок был найден без первого типа, то требуется восстановить этот тип, чтобы понять сколько первых байт он занимает в данных строки. В зависимости от того к какому обобщенному типу принадлежал отсутсвующий
- (только для листовой страницы таблицы) Если
n, т.к. в DDL таблицы первая колонка имеет в определенииINTEGER PRIMARY KEY, и потому значение хранится вrowid, то и число занимаемых байт 0, т.е. значения в данных строки хранятся начиная со второго. - Если
f, то тип первого значения должен быть0x7, т.е. первые 8 байт — это первое значение. Однако, если хранимое значение целое, то оно использовало целочисленный тип, размер которого от 1 до 8 байт, и потому здесь может возникнуть ошибка восстановления. - Если
t, то длину значения можно вычислить, выделив текстовый блок (см. ниже). Если длина получилась больше 67, то в таком случае она должна была быть записана несколькими байтами, и все эти байты, кроме первого, должны обнаружиться в заголовке. - Если
i, то это самый сложный случай, поскольку значение может занимать 1, 2, 3, 4, 6 или 8 байт. Если в заголовке есть текстовый тип, то можно локализовать его значение и по вычисленной длине найти позицию в заголовке, а потом восстановить значения справа налево (оставшееся число байт — это и будет неопределенное первое значение). Иначе, можно попробовать найти конец текущей удаленной строки, воспользовавшись тем, как изменяются заголовки строк при удалении, и также восстановить значения справа налево.
Обнаружение текста в бинарных данных и определение его длины
Если предположить, что текст может содержать только английские строчные и прописные буквы, некоторые символы пунктуации, дефис и круглые скобки (итого ~60 значений из 256), и потому, если будет найден отличный, то это уже не текст. Дополнительно можно убедиться, что текст начинается с нескольких букв или цифр, не содержит слишком много знаков препинания или слова в перемешанном регистре. Поскольку вероятность правильно найти начало текста больше, то длину можно уменьшать, урезая конец, до тех пор пока она не станет равной значению из заголовка строки. Дополнительно можно вычислить предполагаемую длину всей строки, содержащей текст, и проверить, что получившийся конец скорее всего был концом строки (как и в случае с
Если текст в базе был не на английском языке, то можно проверять характерные для UTF особенности. В частности для UTF-8, где для кодирования одного символа используется от 1 до 4 байт, данные должны удовлетворять шаблонам:
i-значением, по следующим байтам или совпадению с концом блока).Если текст в базе был не на английском языке, то можно проверять характерные для UTF особенности. В частности для UTF-8, где для кодирования одного символа используется от 1 до 4 байт, данные должны удовлетворять шаблонам:
0xxxxxxx (ascii символы), 110xxxxx 10xxxxxx (символы, кодирующиеся двумя байтами, напр. кириллица), 1110xxxx 10xxxxxx 10xxxxxx и 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx. В противном случае, можно считать, что найдена граница текста. Отмечу, что на свободных страницах, используемых ранее для индекса, содержится информация в виде список проиндексированных значений +
rowid. Поскольку rowid при удалении зачастую повреждается, то для восстановления строк индекс не слишком подходит, но вот для получения дополнительных текстовых данных вполне. Описание последовательности действий при восстановлении данных
- Прочитать
sqlite_master, чтобы определить список таблиц и для каждой таблицы корневую страницу и обобщенный тип. - Для каждой таблицы выполнить обход иерархии по внутренним страницам и получить листовые.
- На каждом листе выполнить поиск как в незанятом пространстве, так и в свободных блоках между хранимыми ячейками.
- Построить список свободных страниц.
- Проверить являются свободные листовые страницы бывшими листовыми страницами таблицы. Обработать их, если данные страницы не противоречивы. Дополнительно можно выполнить поиск в свободном месте страниц.
- Выполнить поиск на корневых свободных страницах, если удастся предположить обобщенный заголовок.
Множество нюансов, которые следует учитывать, делают восстановление данных не слишком простой задачей, требующей скрупулезности. Потому в итоге, я решил ограничиться отдельной утилитой проверяющей концепцию, sqlite-unhide с возможной доработкой в дальнейшем, если найдутся желающие проспонсировать разработку. Исходники пока раскрывать не стал. Для отладки использовались набор эталонных баз от Nemetz (папка 0С) и SQLiteExplorer.
Дополнительные материалы
- Официальный сайт SQLite
Database File Format - Sangjun Jeon, Jewan Bang, Keunduck Byun, Sangjin Lee, 2011
A recovery method of deleted record for SQLite database - Christian Meng, Harald Baier, 2019
bring2lite: A Structural Concept and Tool for Forensic Data Analysis and Recovery of Deleted SQLite Records
Утилита bring2lite - Paul Sanderson, 2018 (по отзывам — одна из лучших книг по теме; я её достать не смог)
SQLite Forensics - Dirk Pawlaszczyk, Christian Hummert, 2020
Making the Invisible Visible – Techniques for Recovering Deleted SQLite Data Records
Утилита FQLite - Ramisch Felix, Rieger Martin, 2015
Recovery of SQLite Data using expired Indexes - Paul Daniels, 2016
Утилита Undark
Моя модификация с фиксом - D. Richard Hipp, 2015
SQLite The Databaseology Lectures - Sebastian Nemetz, Sven Schmitt, Felix Freiling, 2018
A standardized corpus for SQLite database forensics
Набор эталонных баз для тестирования - Утилиты для просмотра базы данных постранично в HEX-формате
SQLiteExplorer (сыровата, но HEX-режим хорош)
SysTools SQLite Viewer и клоны (базовый HEX-режим и просмотр удаленных строк).
showdb (консольная, одна из стандартных SQLite утилит)
Комментарии (5)
Akina
17.09.2021 10:27+1Пример заголовока файла в HEX-редакторе
Что-то как-то баланс не сошёлся. Если учитывать, что
Число страниц в базе. Умноженное на размер страницы должно совпадать с размером файла на диске.
то страницы нумеруются с единицы. Если всего в БД 77 страниц, а из них свободных 74, то занятых - вероятно, три, причём одна из них - та, что самая первая. Но если первая свободная страница - номер 6, то занятых получается как минимум первые пять.
Где, в чём ошибка? что приводит к такому несоответствию?
little-brother Автор
17.09.2021 11:22+1Akina, спасибо, что заметили. Надо было уточнить, что это номер первой корневой страницы и разумеется она может быть не первой. Я могу предположить, что это первая свободная страница, которая освободилась при удалении данных. В данном случае: у таблицы одна корневая свободная страница №6, куча листьев, прикрепленных к ней, начиная с №2 (итого 74), sqlite_master на 1-ой странице, одна обычная таблица на №76 (один лист) и для её индекса по первичному ключу на №77. Последние два номера можно получить из sqlite_master.
P.S. Промахнулся и возможности перенести нет.
cliffracer
02.10.2021 15:54+1Так, я правильно понимаю, что если у меня, предположим айфон, в котором сафари хранит всю историю в history.db, и я например ее салучайно потер из гуя приложения, т.е техничкси транкейтнул таблицу, то выгрузив history.db файл наружу (представим, что у меня джейлбрейк) и прогнав по нему вашей утилитой, он теоретически может ресторнуть транкейтнутые филды?
little-brother Автор
02.10.2021 15:57+1Все зависит от того, какие настройки SQLite были использованы. Вроде как для iOS 13+ по умолчанию
secure_deleteвключён (не fast) и потому восстановление данных будет невозможно. Проверить не могу, т.к. нет Apple устройств.
unfilled
Спасибо за статью! Не пользуюсь SQLite, но про внутренности БД всегда интересно читать)