Christian Meng, usd HeroLab Consultant, developed an open source tool for forensic data analysis and recovery of deleted SQLite data sets, “bring2lite” as part of his final thesis at the University of Applied Science Darmstadt together with Prof. Dr. Harald Baier. In July, Prof. Dr. Harald Baier presented the tool at DFRWS USA, one of the leading conferences on digital forensics.
“Research in this area is essential for adapting methodological and technical basics for forensic analyses to the ever-growing problems,” explains Christian Meng. “bring2lite is a tool that helps overcoming certain challenges in digital forensics. I was very happy to be able to present our tool to the expert audience at DFRWS USA,” adds Prof. Dr. Harald Baier.
Christian Meng gives an introduction to the topic:
Applications, such as WhatsApp, Skype or Firefox, all use the database SQLite. From an IT forensics point of view, being able to recover deleted data sets is a sensible and useful feature. My thesis had the following objectives:
- Analyze under which circumstances deleted data sets can be restored in the database
- • Develop an open source tool based on this analysis (“bring2lite“)
- Compare “bring2lite” with other, already established, tools
Analysis:
Within the scope of the analysis, 6 scenarios were defined that represent the insert and delete operations of an SQLite database. The scenarios cover various complexity levels. One example is inserting a new record that creates exactly one new page and a new record within the binary tree. Each of the methods used to insert data was then replicated with different database settings. In consequence, 72 new distinct databases were created. Examining these databases, one could note database settings such as secure_delete=0, auto_vacuum=0 or journal_mode=WAL benefited data extraction.
Functional Principle of “bring2lite”:
The developed tool processes data structures as specified on the official website of the SQLite maintainers. The data processing consists of 7 individual steps, which can be seen in Figure 7. The last two steps of the procedure include creating additional SQLite-specific files, which will be ignored in this research. These files could potentially contain deleted data, however, the research focuses on restoring data in the actual database.
In the first step, the SQLite master table is processed. This table contains the scheme of the database and the corresponding root node of the binary tree, in which the actual data resides. By doing this, one can get an understanding of how the formats and data types of the individual tables, and therefore the deleted data, must look like. Steps 3 to 5 represent the actual processing of the deleted data. Free blocks (step 3) are individual, deleted data records within normal SQLite files. These free blocks are structured as linked lists. In consequence, only the first 4 bytes of a record will be overwritten. Due to the missing 4 bytes, SQLite cannot process this data anymore. Additionally, the first 2 bytes of the database represent the address of the next free block, which can be used to find and extract all free blocks in the database.
The unallocated area, which is processed in step 4, is located between the header of a binary tree page (node) and the beginning of the data area, as shown in the figure above. When data at the beginning of the data section is deleted, only a pointer is changed to the new start of active data. Therefore, the data that was supposed to be deleted remains intact. In order to find this data, the unallocated area must simply be extracted and shrinked to the size of the actual data.
All the free lists will be extracted and processed in step 5. A free list is generated by SQLite every time a whole binary tree page is removed. When this occurs, the content of the pages will not be deleted, but the pointer pointing to this page will be removed from the regular binary tree and converted into a free list. This structure can still contain a forensic analyst might find interesting.
Example:
Once installed, the software „bring2lite“ can be executed like this: python3 bring2lite/main.py
Then, the tool will print the following help page:
If a user specifies a path to an SQLite database or a directory, respectively, the processing of the files looks like this:
For each file generated using “bring2lite”, a hash is calculated to prevent unwanted changes to the files. “bring2lite”creates a main directory for each database and also creates a directory for each structure that contains deleted records. For example, the database 0A-01.db looks like this:
As illustrated in the figure, deleted database records could be extracted from the database using free lists. Also the database scheme is extracted into a separate directory. This is helpful if the database contains more than one table, and thus, more schemes are of importance.
The database file which represents an example database is located in the directory /0A-01.db/freelists/freelist_trunk_pages and is named 2-page.log, where the name describes the page in which the records are found. All the extracted data is stored in the CSV file format:
Comparison with different tools:
In order to evaluate the capacity of “bring2lite” properly, 27 standardized databases were processed and the amount of restored data records was reviewed. “bring2lite” achieved a restoration rate of 52.9%. This result shows that “bring2lite” is more effective than all of the 8 tools it was compared to.