This article originates from a grep on the wrong directory. Casually, I remembered having deleted that particular record in an SQLite DB and finding it in the grep results, even if surrounded by strange characters, left me surprised for a moment. We often don’t think deeply about how systems manage our data and assume that everything is much more complex and precise than it is (in this case: Delete is not delete).

SQLite was developed in early 2000 to eliminate the dependency of a simple but key application on an Informix DB server. Since then, having an SQL server on a personal computer or even on a PDA has become a fundamental part of the development of applications: Motorola, AOL, Symbian, up to Android and iOS, all store data in local SQLite databases.

And the information stored becomes more and more sensitive.

Why SQLite is important

SQLite is everywhere. It is in web browser, it is in phone, it is in car, and it is definitely in commercial planes. It is where iMessages and WhatsApp messages are stored, and if you do a find on your computer for *.db, you will be amazed at how many SQLite databases you find.

SQLite is the de facto standard technology to store structured information in a file on a local system. Any application that needs to maintain normalized data without resorting to heavy applications such as SQL servers, uses this file-based or in-memory, lightweight, compact and efficient structure. This has made the software a fundamental piece of many applications, manager and custodian of our most sensitive data.

SQLite Database Format

I don’t want to explain the inner workings of SQLite. The important things to remember:

• Like a filesystem, the structure of each database is organized in pages.
• The data of each table or index are saved in a B-Tree structure that occupies one or more pages. Each page contains only the data coming from a specific table or a specific index. As a result, there are no pages containing records belonging to different tables.
• Each page can contain pointers to other pages (internal pages) or data (leaf pages). Larger tables/indexes contain a root page that points to internal pages which in turn point to multiple internal pages or leaf pages (chained).
• When tables are added, records are changed, or records are deleted, the number of pages used by a table can increase or decrease, and records can be moved between pages.
• The freelist contains a list of pages that are not currently in use. Each freeblock is linked to a page freelist.
• The freeblock may contain data that should no longer be accessible.

Where is the Data

Being a local file-based database, the data can be retrieved using the standard interface provided by the SQLite daemon, without further authorization steps. But what happens with the deleted data? It depends. As we will see below, some parameters affect how data is removed from the database file. In general, and by default, however, the data remains in the file and the space is just marked free. It is therefore possible to go through the list of freeblocks and retrieve the deleted content, in some way.

The algorithms used to manage the information in the database are well known, therefore it is possible with minimal effort to program tools that retrieve the information. The problem lies, absurdly, in the simplicity of the structure itself. As mentioned, the data are easily traceable, and on each page, there are only records belonging to a specific table, but which one? If we have a database with several tables, and we delete some records, if there are any left on that page, we can be sure that the deleted data belongs to the table to which the remaining records belong, but otherwise, it is not possible to know which table they are to. In this case, it is customary to bet on membership based on the content and form of the record. This process, however, becomes more and more inaccurate as the size of the deleted blocks increases or the content is binary; for this reason, the data cannot always be reconstructed perfectly.

Accessing information is very simple. With few lines of code, is possible to dump the key parameters necessary to reconstruct deleted records:

rcc@vic:~/scip_Labs/labs.20210819_sqlite3_forensic/databases$ python3 info.py --database contacts-v1.db
Passed databasename is contacts-v1.db
Database contacts-v1.db exists and is a regular file.
Open database contacts-v1.db
Database version:         SQLite format 3
Page size (bytes):        4096
Database size (pages):    1929
Freelist first page nr:   25
------------
Address of the first freelist page:  b'\x00\x00\x00\x19'  ->  25
Number of freelist pages:            b'\x00\x00\x01\xe7'  ->  487
*** Read page nr:  25
   - Page header:   b'\x00\x00\x00\x00\x00\x00\x01\xe6'
    Address of the next freelist trunk page :  b'\x00\x00\x00\x00'  ->  0
    Address of the next freelist leaf page  :  b'\x00\x00\x01\xe6'  ->  486
*** Read page nr:  486
   - Page header:   b'\r\x00\x00\x00Z\x00\xe2\x00'
    Address of the next freelist trunk page :  b'\r\x00\x00\x00'  ->  218103808
    Address of the next freelist leaf page  :  b'Z\x00\xe2\x00'  ->  1510007296
    Address of the next freelist page :  b'\r\x00\x00\x00'  ->  218103808
*** Read page nr:  218103808
   - Page header:   b''
    Address of the next freelist trunk page :  b''  ->  0
    Address of the next freelist leaf page  :  b''  ->  0
    This is the last freelist page.

Tools and Recovery Rates

There are standard tests to check the quality of a tool in restoring deleted records. Note, in any case, that even the best tools in the best conditions do not go beyond the recovery of 50% of deleted records, depending on the type of data stored (text or binary).

SQLite Pragmas

As mentioned, the data recovery success rate depends on the options that are in use. SQLite has some mechanisms to shrink or overwrites space that is no longer in use. If they are in use, the recovery of the deleted data is practically impossible.

The following options affect the behavior of the deleted records.

Vacuum

When auto-vacuum is disabled and data is deleted from a database, the database file remains the same size. Unused database file pages are added to a freelist and reused for subsequent inserts. When the auto-vacuum mode is 1 or full, the freelist pages are moved to the end of the database file and the database file is truncated to remove the freelist pages at every transaction commit. Note that auto-vacuuming must be turned on before any table is created.

Secure Delete On

When secure_delete is on, SQLite overwrites deleted content with zeros. This is the most secure option to make sure deleted records are not recoverable. We suggest to use this pragma whenever possible, even if it slightly impacts on performance.

Journal Mode

The journal mode, rollback or write-ahead, is used for atomic transactions. Both kinds of logs keep a history of the last actions performed in the database, therefore are a valuable source of data, in the case of forensic analysis. Many parameters can influence the logs (length, persistence, etc.), but in general, if they are present, the few tools based on log recovery perform much better than tools that analyze only the database; in some particular cases, the recovery of the deleted information was 100%.

Summary

SQLite allows us to store structured information without the need for a heavy system like a database. In any case, it is advisable, even if it is not possible to compare the security options between a database server and SQLite, to use some precautions to make the use of the application safer, for example by making sure that the deleted records are irrecoverable.

About the Author

Rocco Gagliardi has been working in IT since the 1980s and specialized in IT security in the 1990s. His main focus lies in security frameworks, network routing, firewalling and log management.

Links

• https://sqlite.org/fileformat.html
• https://www.sciencedirect.com/science/article/pii/S1742287618300471
• https://www.sciencedirect.com/science/article/pii/S1742287619301677