Simply put: data carving.
More complex: most modern browsers use SQLite databases for their histories (the old Microsoft Edge being the most common exception). SQLite stores entries in cells grouped into pages. Each page contains cells for only one table (i.e., URLS, Visits, etc.).
Pages have three major components (in this order):
- header
- type signature
- first freeblock address
- number of cells (records)
- first cell address
- number of free bytes (fragmented bytes in the cell storage area)
- cell array (addresses for each cell)
- Unallocated space
- Cells
Each cell contains:
- payload length
- row ID
- the payload, which itself is made of:
- a header
- header length
- column data types/sizes
- a body (table content)
- possibly an overflow page number.
When you delete an individual record, it becomes a freeblock and the first four bytes of the record are overwritten with the page address (offset) of the next freeblock and the length of the current freeblock. If you look at the cell structure I laid out above, the four overwritten bytes usually amount to payload length and rowid, but they can extend into the header portion of the payload (but not more than the header length and/or rowid place holder). Thus, the record data is recoverable until the database overwrites the freeblock.
Pages in which all the records have been deleted are added to a free page list. This is a separate database page that can’t be queried with SQL, but can be read and interpreted. Free pages can contain “intact” cells where the first four bytes have not been overwritten. These database records much easier to recover, as a result. SQLite will reuse or release these pages (shrink the database size) based on different criteria, some of which is defined at the initialization of the database itself.
So, in the end, recovery of deleted history involves knowing: how was the history stored (SQLite, other format), how it was organized (one table, or multiple tables in relation), how was it deleted (one record at a time, wholesale pages), if the records are still in the file structure (SQLite freeblocks and freepages), and can the table data (in the case of SQLite) even be related to other tables again. Remember, the row IDs are overwritten when individual records are dropped from the database, and if the table relations involve row IDs, this might be impossible.
Some commercial tools carve to find deleted Internet histories, but the results can be suspect (they often carve based on regex and confuse data between allocated records and freeblocks.
The best way to do it, at least in the case of SQLite, is to use or create a tool that can read the database header to find the relevant database pages and freepages, then read each page to find records and freeblocks (and possibly carve them from the unallocated portion of the page, which I didn’t discuss but is a further complication). And frankly, finding the structures is the easy part. Reconstructing the freeblock records is where the challenge comes in, especially when the payload header is damaged.
From all this, you can see why you won’t find many SQLite data recovery tools. Each database has different structure, which makes recovery for each database different and more or less profitable.
There’s plenty more to discuss, but I’m going to end here.
