Linking records across files

Summary

• A phone seldom says anything once. The same event can leave a row in a database, an entry in an XML file and a line in a log, each written by a different component for a different purpose.
• Three tests make a link: a shared key such as a package name, a clock relationship that fits what each store records, and an explanation for any store that should hold a record and does not.
• One store is often the only witness. In the Lab's research collection the median share of events with a single witness ranged from 30 to 98 percent, depending on the event type.
• Adding a store can only add support to a finding that something happened. Losing one can turn that finding into a finding that nothing happened.
• A report should name each finding's witnesses and writers, and write "not observable", not "absent", for times that no store you hold covers.

One event, many records

A finding about a phone is usually written as if the phone said it once: the app was installed at this time, the camera was used in this minute, the phone restarted on this day. In practice a phone says most things in as many places as keep a record of them. We call each place a store. A store can be a database, an XML file, a log, or a snapshot printed into a bug report. Each has its own writer (the component that creates its records), its own purpose and its own retention [1].

An examiner rarely holds every store. An acquisition class may leave one out, a tool may not read it, or a retention limit may have erased it. Two readers of the same phone can then reach different verdicts without either making a mistake. This article is about the step in between: deciding that records in different stores describe one event, and what the finding is worth once that is decided.

Figure 1 shows the idea with a synthetic example. One use of the camera by an app leaves a record in three stores of Android's App Ops service [2].

No record repeats another. The database row keeps the first event of a one-minute window and a count of accesses. The XML file keeps the last access and nothing earlier. The dump in a bug report is a snapshot, printed with a time and an offset from the moment it was taken [2]. A reader who expects three copies of one value will think the stores disagree. A reader who knows what each store keeps will see that they fit together.

What makes a link

Before two records are called one event, we ask for three things. A link that lacks one of them is a guess.

A shared key

The key is whatever both stores use to name the subject: a package name, a package name with an operation, a run code. LAB-0001 shows a two-letter run code that links two Samsung recovery files. Time alone makes a weak link. In Figure 3, a record for a different package lies two seconds from an install time and still does not link. Some events have no key at all. A restart has no subject, so restart records can only be linked by time, with a tolerance of 300 seconds in the Lab's measurement [1].

A clock relationship

Records of one event rarely carry the same time, and a link should not require it. The App Ops history row holds the time of the first access in its window, while the XML file holds the last access. On five Android 16 images, 54.0 percent of 3,180 XML times equaled a database time to the millisecond. Of the unequal times that fell inside a window, 99.8 percent (1,182 of 1,184) belonged to a row that counted more than one access, which is what the platform source predicts [2]. The right test is that the time falls inside the window, not that it is equal.

For other pairs of stores the Lab measured how far apart linked records lie (Figure 2). In the median the difference was under 7 seconds for every event type except restarts, where a dropbox entry and a usage event differed by 18 seconds and other pairs by 180 and 364 seconds. The platform sources give a reason: the dropbox entry is written when the boot-completed broadcast is received, and the usage event records the start of the runtime [1].

Two more limits apply to time. Readings of different clocks can be compared only with a stated bound on how far the clocks may disagree. Readings of one clock share an offset, and can be ordered once they differ by more than the sum of their resolutions [3]. On 300 synthetic phones, comparing point timestamps put 3.1 percent of near-simultaneous pairs from different stores in the wrong order [3]. And a time on a record is not always a time the event happened on this phone: of 13 Android phones with messages, 7 held some dated before the phone's first boot, which is consistent with records carried over from an earlier handset [4].

An explanation for what is missing

A link also needs a story for a store that should hold a record and does not. Some reasons are not errors: the store never records this kind of event, its retention has passed, a newer value replaced the old one, or the acquisition did not include it. A package's file time dates its first install only while the package has never been updated; after an update it dates the update. In the Lab's research collection that store held 28 percent of the first installs that another store also held, against 98 percent for package restrictions [1]. A store can also explain its own gaps: in Android media stores, the tombstone table covered a median 39 percent of the issued identifiers that had no live row [7].

A missing record with an explanation is neutral. A missing record without one is a question.

Link the records yourself

Figure 3 is a record linker with invented values. Pick a scenario, then select a record to link it to the event. The figure tests the link for a shared key, a clock relationship and an explanation, and says whether it counts as a witness. Untick "In my acquisition" on a store to see what the finding becomes when that store is lost. The table under the figure holds the same content.

What to look for. In the install scenario the package list and the package restrictions agree to within two seconds, but both are written by the package manager, so they count as one writer. The APK file time looks related, yet it follows the last update, so it is not a witness of the install. Take out the two package-manager stores and the APK store is left. It covers the time and holds no linked record, so the finding would read as absent, and that absence rests on a store with a 28 percent detection rate.

In the camera scenario the XML time does not equal the database time, yet the link is supported, because the time falls inside the window of a row that counted four accesses. The dump line shares the key and the time, but the Lab did not show that dump times match other forms, so it stays an indicator. Take out the database and the file, and nothing you hold covers the minute: the finding is unobservable, which is different from absent.

How many stores stand behind a finding

In the Lab's research collection we linked records with the rules above and counted the stores behind each event. Figure 4 gives, for each event type, the share of events with a single witness in the median phone that had at least five events of the type. For app first installs it was 89 percent, for screen-on events in Android extractions 92 percent and for connected calls 94 percent. App last updates are the exception at 30 percent, because two stores record them [1].

Counting stores can also overstate protection. In bug reports the event log and the system log both record screen wake-ups from the same power service. Of the 39 screen-on events with two or more stores, 26 were held by three stores but only two writers [1]. A second store written by the same component adds no protection against a fault in that component.

A report is a chain of such findings, and a chain is as strong as its weakest link. If findings are independent and 52.5 percent of calls have a single witness, as in the iOS call data, the chance that all five calls of a five-call timeline have a second witness is 2.4 percent [1].

When a store is missing

Existence and absence behave differently. Adding a store can only add support to a finding that something happened. Removing a store can turn it into a finding that nothing happened: if the lost store was the only witness and another store covers the time, the remaining store is silent, and a careless reader writes "no record" for an event that occurred [1].

How often is that exposure real? In the research collection, after the only witness was lost, another store still covered the time for 36 percent of single-witness iOS calls and 29 percent of single-witness Android screen-on events. For 96 percent of single-witness iOS messages nothing else covered the time, so the finding became unobservable, not absent. Whether a covering store supports absence depends on how well it records such events: for iOS calls, the interaction store held 75 percent of the calls that the call-history database also held [1]. The same asymmetry applies to a day with no records. Of the days with no record, 79 percent (iOS calls), 91 percent (iOS messages) and 97 percent (Android screen-on) were observed by one store only [1].

Removed apps show the effect at a larger scale. We counted package names that a store held for an app the phone no longer lists as installed. Of 770 such names on Android, 98 percent were held by exactly one store, and reading the app store's local state alone found 91 percent of them; any other single store found at most 5.5 percent. On iOS, 11 of 118 logged uninstalls (9 percent) left a name in any store we read [5]. A missing trace in one store is weak evidence that an app was never installed.

Writing the finding

A finding that states a time should state its witnesses, whether they share a writer, and, for any absence, which stores observed the time and how often they hold events of that kind [1]. "No restart was recorded in the usage store, which covers the day and held 73 percent of the restarts that another store also held" is a different claim from "the phone did not restart". Without the usage store, the first claim becomes "not observable".

A finding should also be traceable. In a replay of a reference reconstruction on 53 phones, 70 percent of findings had a complete chain from the finding to a file, a digest and a value. None of the findings of absence, which were 22 percent of all findings, recorded what had been searched [6].

Before you write "the phone did X at time T":

1. Name the key that the stores share.
2. State the clock relationship you used (equality, a tolerance or a window) and its size.
3. List the witnesses and their writers.
4. For every store without a record, say why it can be empty, or say that it is unexplained.
5. For a store that is not in your acquisition, write "not observable" for the times only that store covers.

Try it on a test phone

1. On a phone you control, install an app and open its camera feature once. Write down the minute.
2. Take a full file system extraction and a bug report from the same phone.
3. For each store in Figure 3, find the record and note its key, its time and what the store keeps.
4. Apply the three tests. Write down the tolerance or window you used, and why any store has no record.
5. Take one store away and write the finding again.

Publish counts and store names, never values from a phone that holds personal data.

What this does not prove

Sources

Every number and claim above comes from a Lab Technical Report. No public documentation was used for a stated fact.

Papers cited

Related

Version history and corrections

Corrections log

No corrections have been published for this article. Corrections to any article are listed on Corrections.