Michael Spreitzenbarth

Sven Schmitt

Felix Freiling

Comparing Sources of Location Data from Android Smartphones

Keywords: Mobile phone forensics, Android phones, location data

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

This paper focuses on the location data stored by Android smartphones. In particular, it attempts to answer the question: In what sense can the location data extracted from mobile phones replace or complement the location data obtained from network operators? Unlike other research in the area, this work also considers location data maintained by mobile phone applications (apps). The ADEL forensic tool [START_REF] Freiling | Forensic analysis of smartphones: The Android Data Extractor Lite (ADEL)[END_REF] was modified to extract all the different sources of location data and merge them to create a more complete picture of the movements of a phone. The extracted data includes location data from popular social networking apps as well as location data from cache files and GPS coordinates associated with pictures.

Experiments were performed using three brand-new Samsung Galaxy S2 (Android) smartphones. These phones were given to three students who used them with the understanding that the smartphones would be analyzed forensically. The students were encouraged them to take many photographs and make use of social networks and Twitter. After almost four weeks, the data was extracted and analyzed, and the quality of the location data was compared with the data available from Spitz [START_REF] Zeit Online | Tell-all telephone[END_REF]. Overall, the experimental results demonstrate that location data stored on smartphones is often much more precise than the rather coarsegrained data stored by network operators. However, the availability of location data on smartphones varies considerably compared with the data stored by network operators.

Background

Following the 2004 terrorist attacks in Madrid, the European Union issued a 2006 directive [6] to harmonize regulations in EU member states concerning the retention of data generated by publicly-available electronic communications services. The directive seeks to enable law enforcement to access traffic data pertaining to suspects, e.g., to discover who the suspects communicated with and the digital services that had been used. In addition to data about individual communications, the directive also requires certain location data to be retained by network operators. Specifically, the directive requires that the following data be retained for at least six months: Identity and exact GPS coordinates of the radio cell where the user started a phone call.

Identity and coordinates of the radio cell that was active at the beginning of a GPRS data transmission.

Time stamps corresponding to this data. This information can help investigators create movement profiles of suspects. Also, the information may be used to locate and monitor suspects.

Many EU member countries have implemented this directive in national laws. However, in some countries, there has been an intensive public debate about the laws, especially in relation to their threats to privacy. In Germany, discussions were fueled by a data set provided by the German politician Malte Spitz [START_REF] Zeit Online | Tell-all telephone[END_REF]. The data set contained location data over a period of six months that was preserved by his mobile network operator under the data retention law. A German newspaper created a graphical interface that enabled users to visually replay Spitz's detailed movements [START_REF] Zeit Online | Tell-all telephone[END_REF].

Overall, it is argued that retaining large amounts of data creates new risks of abuse. Also, the requirement to store data pertaining to millions of innocent people is out of proportion to the small number of cases in which the data is used by law enforcement. As a result, in 2011, the German Constitutional Court dismissed the original legislation requiring data retention. Meanwhile, the search for less invasive techniques to analyze the movements of criminals continues.

Location Data in Mobile Phones

In recent years, many new types of mobile phones (smartphones) have flooded the market. Since they are essentially small personal computers, they offer much more than the possibility to make phone calls and surf the Internet. Over the last two years, devices based on the Android operating system have become very popular, with a market share of more than 40% and sales of more than 46 million units during the second quarter of 2011 [START_REF] Gartner | Gartner says sales of mobile devices in second quarter of 2011 grew 16[END_REF]. Increasing numbers of subscribers are using apps (mostly third party applications that are directly installed on their phones) and are communicating with friends and family via social networks such as Facebook, Google+ and Twitter. The ubiquity of these services is overwhelming. Facebook had more than 600 million active users in January 2011 [START_REF] Carlson | Goldman to clients: Facebook has more than 600 million users[END_REF]; Google+ attracted 25 million active users in less than one month [START_REF] Gobry | Google+ hits 25 million users, is the fastest growing website ever[END_REF]; Twitter claimed that it topped 100 million monthly users for the first time in August 2011.

For performance and other reasons, mobile devices persistently store location data in local memory. In April 2011, it was reported that Android and iOS store sensitive geographical data [START_REF] Angwin | Apple, Google collect user data[END_REF][START_REF] Raphael | Apple vs. Android location tracking: Time for some truth (blogs[END_REF]. This data, which is maintained in system cache files, is regularly sent to platform developers. But generating geographical data is not restricted to the operating system -many apps that provide location-based services also create and store such data. For example, Benford [START_REF] Benford | Geotags: Friend or foe? Forensic Focus (www.forensic focus[END_REF] has shown that pictures taken by an iPhone contain the GPS coordinates of the locations where the pictures were taken. Such data is sensitive because it can be used to create movement profiles. Unlike the location data retained by network operators, location data stored on smartphones can be accessed by law enforcement via an open seizure.

Forensic Analysis of Mobile Phones

Mobile phones are an increasingly important source of digital evidence. However, until recently, extracting and analyzing data from mobile phones was rather cumbersome because of the diversity of their hardware and software. The situation is gradually changing as the market of mobile platforms consolidates and more tools become available. Hoog [START_REF] Hoog | Android Forensics: Investigation, Analysis and Mobile Security for Google Android[END_REF] discusses the forensic analysis of Android devices, including details about the file system and information stored in apps such as Facebook and Google Maps.

Several commercial forensic tools have been developed for mobile phones, including EnCase and MOBILedit! [START_REF]MOBILedit! Forensic Overview[END_REF]. Additionally, hardware solutions for forensic analysis such as XRY [START_REF]Micro Systemation, XRY Physical[END_REF] are available. The only extraction and analysis tool available as a research prototype is ADEL [START_REF] Freiling | Forensic analysis of smartphones: The Android Data Extractor Lite (ADEL)[END_REF], which incorporates several programming scripts developed for Android 2.x platforms. While some of these tools extract location data stored by the operating system, none of them address location data stored by popular apps.

Up to now, forensic examinations of social networks have primarily focused on computers. A SANS Institute post [START_REF] Bryner | Facebook memory forensics (computer-forensics[END_REF] outlines a method for finding Facebook data in the memory dump of a computer. Wong, al. [START_REF] Wong | Facebook Forensics[END_REF] describe Facebook forensics and the reverse engineering of the Facebook API on virtual environments and mobile devices. However, with regard to the Android operating system, only the design of the database associated with the Facebook app has been studied. Twitter has not been investigated on mobile devices as yet, and only a few publications are available for Google+, among them, a discussion of artifacts related to URL forwarding [START_REF] Whitfield | Flashpost: Google+ artifacts -URL forwarding[END_REF].

ADEL Forensic Tool

ADEL (Android Data Extractor Lite) [START_REF] Freiling | Forensic analysis of smartphones: The Android Data Extractor Lite (ADEL)[END_REF] is a forensic data extraction and analysis tool for versions 2.x of the Android platform. The tool incorporates multiple scripts (modules) written in Python and can be extended rather easily. It can automatically dump predefined SQLite database files from Android devices and extract the contents stored in the dumped database.

Figure 1 shows the ADEL workflow. In the first step, ADEL establishes a connection to an Android device via the Android debugging bridge (adb), dumps the predefined SQLite database files from the phone and stores them on the investigator's machine (dump module). All of the subsequent steps are performed on copies of the database files in the read-only mode to ensure data integrity. In the second step, the contents of the dumped database file copies are analyzed and extracted (analysis module). To accomplish this, we developed a specialized parser module for the SQLite database file format [START_REF] Sqlite | The SQLite Database File Format[END_REF], which extracts content by directly parsing database files. After the contents are extracted, an XML-based report is generated to support the further use and presentation of data (report module). The report can be viewed using an ordinary web browser and can be refurbished with the help of an XSL file. Although it is possible to optionally generate an extensive log file containing entries for all the major steps performed during script execution, the use of ADEL is intended to be as simple as possible for experts as well as non-experts.

In the original development state [START_REF] Freiling | Forensic analysis of smartphones: The Android Data Extractor Lite (ADEL)[END_REF], the following information can be dumped and analyzed:

Telephone and SIM-card information (e.g., IMSI and serial number)

Phone book and call lists

Calendar entries

Browser history and bookmarks SMS messages ADEL is built in a modular manner and, thus, can be augmented quite easily to provide additional functionality. A disadvantage with ADEL is that it can only be used with mobile phones that provide root access to applications ("rooted phones"). The root access is necessary in order to access the adb interface.

Accessing Location Data

This section describes a method for using ADEL with a non-rooted smartphone. Also, it describes the additional modules incorporated to extract location data from specific apps on a smartphone and combine the extracted data in an intuitive visual representation.

Daemon Replacement

Since many manufacturers have publicly released their boot loaders [START_REF]HTC Developer Center[END_REF], it is no longer necessary to exploit the Android system to gain root access to execute ADEL correctly. Indeed, it is sufficient to modify the original kernel so that a root shell is included. As a result, the amount of modified data is significantly less compared with other approaches (e.g., using the "rage against the cage" root exploit).

After a smartphone is updated with the modified kernel, some changes must be made manually to guarantee the trustworthiness and integrity of the extracted data. In particular, the original, untrusted adb-daemon on the smartphone must be replaced by a trusted version. The following commands can be used to copy a trusted adb-daemon to the smartphone and, subsequently, remount the system partition to make it writeable: adb push adbd /sdcard/ adb shell sumount -orw,remount / mv /sbin/adbd /sbin/adbd.old mv /sdcard/adbd /sbin/adbd mount -oro,remount / kill \$(ps $\mid$ grep adbd)

Note that the existing daemon is backed up and the new daemon moved to its place. Following this, the partition is mounted to read-only again to prevent further changes. In the final step, the running (original) adb-daemon is terminated.

New Location Data Sources

We investigated the location data stored by several well-known Android apps. Table 1 lists some of these apps, their databases and their content. The upper half of the table contains data originating from system services, the lower half shows data retrieved from third party apps. The first group includes the cache files and pictures taken by the integrated camera. The camera records GPS coordinates and stores the coordinates in the EXIF data of a JPEG image (if the GPS is switched Google Maps stores all data pertaining to navigations in a separate database. This includes, for example, the current address, destination address and current time. However, since this data is stored when Google Maps computes a navigation, it cannot be assumed that the user actually traveled to the destination.

We also investigated the Facebook app. According to Hoog [START_REF] Hoog | Android Forensics: Investigation, Analysis and Mobile Security for Google Android[END_REF], this app stores location data in a database. However, we could not verify this fact during our investigation. The database and the written status messages were empty although the app had been used extensively. Only the data pertaining to the last location was found in the database.

Experimental Results

This sections describes the experiments that were conducted and their results.

Experimental Set-Up

We purchased three brand new Samsung Galaxy S2 smartphones and gave them to three undergraduate students in computer science who had volunteered to participate in the study. We explicitly selected participants who were active members of multiple social networks. The participants were asked to use the smartphones on a daily basis "according to their normal behavior." The smartphones were provided free-of-charge for a period of approximately four weeks.

After the smartphones were returned, we extracted and analyzed the stored data with the help of ADEL. We modeled each piece of information as a data point, i.e., a tuple (s, g, a, t, d) where s is the specific service or app, g is the GPS measurement (latitude/longitude), a is the measure of accuracy, t is the timestamp, and d is the duration of time for which the measurement holds.

The following assumptions were made regarding the accuracy of location data:

Location data stored in the EXIF header of pictures has an accuracy of 51 to 100 meters.

Location data stored by Twitter during the transmission of a message has an accuracy of 51 to 100 meters.

Google Maps data has an accuracy of less than 50 meters.

The assumptions are made because apps do not always store the exact distance to the broadcasting tower. In the case of GPS sensors, it can be assumed that more precise location data is more accurate. To validate this assumption, we took 100 pictures with a smartphone and compared the stored data with data from a high-precision GPS receiver. We also checked the results inside and outside buildings. Much of the inaccuracy appears to arise in measurements made indoors.

We performed similar experiments with Twitter and Google Maps. In the case of Twitter, it can be expected that a large fraction of messages would be produced and consumed indoors.

Our experiments indicated that Google Maps has by far the best accuracy. Of course, most users would use Google Maps for outdoor navigation as opposed to indoor navigation.

We used a special convention with regard to timestamps when performing the analysis using ADEL. In particular, we assumed that the user remains at a given location for a time period of 15 minutes. This convention was used whenever the interval between several stored location data points was greater than 15 minutes. Otherwise, the interval of time between two timestamps was been chosen as the length of stay.

Data Comparison

We compared the data extracted using ADEL with the Spitz data [START_REF] Zeit Online | Tell-all telephone[END_REF]. The Spitz data was collected by a large German network operator according to regulations enacted as a result of the EU data retention directive [6]. The Spitz data only contains the GPS coordinates of base stations and the rough directions of radio beams. Since cell site locations are smaller in densely populated areas than in the countryside and Spitz had mainly visited larger cities, we assumed that the accuracy was between 501 and 1,000 meters most of the time. The remainder of the time we assumed an accuracy of at least 1,000 meters.

Collected Data

Table 2 provides an overview of the smartphone data extracted using ADEL and network operator (Spitz) data. The number of points in the Spitz data was scaled down to cover approximately the same time frame as the ADEL data. Clearly, the number of data points retained by the network operator is much greater than those found upon forensically analyzing the three smartphones. The reason is that smartphones only save data associated with the last 50 mobile phone cells. Note, however, that the Spitz data is only associated with mobile phone cells, while the smartphone data comes from various sources.

Table 2 also shows that Phone 2 accessed the largest number of WiFi networks. However, according to the extracted data, it did not use the integrated camera, navigation system and social networking apps. Fortunately, the other two phones used the camera, navigation and social networking apps during the test period.

Movement Profiles

Detailed movement profiles can be created using the data extracted with ADEL. Figures 2 and3 show two examples of movement profiles. Each circle in the figures represents the approximate position of a user when a message was published in a social network or when the user made a phone call. The figures also contain marks corresponding to when Google Maps navigations were initiated. However, the navigation destinations were intentionally ignored because it cannot be guaranteed that the routes were ever taken.

Figures 2 and3 also present data from the two cache files, cache.wifi and cache.cell, along with GPS data for pictures taken with the phones. Note that data from the smartphones themselves yields movement profiles that are much more detailed that those generated using network operator data (for which individual cells can have diameters exceeding 1 km). Fusing additional data from the smartphones can yield even more detailed movement profiles.

Figure 2 shows data associated with a trip through the Rhinegau, a region in Germany. All the data points were generated within a time- frame of five hours. According to stored data, the user did not use any other apps during the trip nor did he take any pictures with the smartphone. Based on the overlap of the mobile cells to which the user was connected, it is possible to make assumptions about the streets on which the user traveled.

Figure 3 shows data associated with a trip around Brinzer Lake in Switzerland. No mobile cell data was recorded during this trip. The reason could be that the smartphone was not connected to the network because it had a German SIM card or because the maximum storage capacity of 50 cells was insufficient to store data associated with this portion of the trip. However, the smartphone apparently connected to a large number of WiFi routers. These "cells" are much smaller than mobile cells, which is why the location data has more precision. Also, some locations are recognizable in the pictures taken by the smartphone. Thus, it can be inferred that the user took Federal Road B11 and Highway A8.

The two examples demonstrate that the aggregation of GPS data from different sources can lead to very precise movement profiles.

Tracking Coverage

We attempting to answer this question, we assume that the location data from the mobile phones is extracted by ADEL.

Figures 2 and3 show the movement profiles that were obtained from smartphones using ADEL. Thus, the question arises if data retention by network operators is at all necessary. We investigate this issue.

Figures 4 and5 compare the location data obtained from smartphones with the data retained by network operators. Clearly, the number of data points is much higher in the case of data retention. However, the location data in much more accurate in the case of smartphones (50 to 100 meters) as opposed to data retention (500 meters or more). Clearly, location data extracted from smartphone using ADEL allows for much better positioning of users.

Another question pertains to the effects of the large difference in the number of location data points obtained from smartphones compared with data retention. Note that the smartphone experiment set the number of data points (including stored timestamps) in relation to the maximum possible time period (Figure 6). Since the experiment covered a period of two weeks, the maximum time during which the user is trackable amounts to 20.16 minutes. Taking the steeper line in the figure into consideration, the user is trackable about 83% of the time in the case of data retention -this corresponds to about 16.765 minutes during the two-week period. In contrast, based on data extracted from the smartphones using ADEL, the user is trackable about 17% of the time, which corresponds to only 3.428 minutes.

Upon comparing the two sets of results, it is evident that location data extracted from smartphones is much more precise that the data retained by network operators. However, smartphone-based data exhibits more time-related gaps. In a criminal investigation, tracking a user for 17% of the time using smartphone-based data is quite low compared with 83% of the time with data retention. However, if the time period of interest in the criminal investigation is within the trackability period, then a smartphone would yield much more precise location data for the investigation.

Conclusions

The extension of the ADEL tool described in this paper allows easier access to evidence residing on mobile phones. This includes evidence related to system services as well as popular web services.

With regard to location data, several services and applications running on Android devices store data about the geographical locations of the devices. An additional source of location data available to investigators is the data retained by network operators as a result of prevailing laws and regulations. Our experiments comparing the data sources indicate that location data stored on an Android device is more accurate than the location data retained by network operators. However, network operators often store data for long periods of time whereas the data stored on a device is regularly overwritten with newer data.

One avenue for future research is the implementation of privacy enhancing techniques that reduce the types and amount of data stored on phones. For example, disabling the "Use Wireless Networks" option in the "Location and Security" settings menu of a device could result in the deletion of the cache.wifi and cache.cell files. Other options include turning off "Geotagging" in the camera settings and "Use my location" in the device privacy settings.

Finally, it is important to consider the possibility that the location data retrieved from a mobile device may not be completely reliable. This is true for location data pertaining to WiFi routers because the data is recorded only when a router is encountered for the first time. Since WiFi routers could be moved to new locations, the location data stored in cache.wifi may be outdated. Furthermore, in the case of apps such as Facebook and Google+, it is possible to link a user to a certain location although the user may not actually be at that location.

Figure 1 .

 1 Figure 1. Android Data Extractor Lite (ADEL) workflow.

Figure 2 .

 2 Figure 2. Movement profile generated from Smartphone 1 data.

Figure 3 .

 3 Figure 3. Movement profile generated from Smartphone 3 data.

  now address the research question posed in the introduction: In what sense can location data extracted from mobile phones replace or complement the location data obtained from network operators? In

Figure 4 .Figure 5 .

 45 Figure 4. Location data from smartphones.

Figure 6 .

 6 Figure 6. Percentage of time smartphones were traceable.

Table 1 .

 1 Android applications and stored location information.

	App	Storage Location	Content
	System	cache.cell	Last 50 mobile telecommuni-
			cations cells
	System	cache.wifi	Last 200 WiFi routers
	Camera	Pictures	Latitude and longitude of
			picture location
	Browser	CachedGeopositions.db	Latitude, longitude, accu-
			racy and timestamp
	Twitter	author id.db -status	Latitude and longitude of
			status message
	Twitter	author id.db -search queries Latitude,	longitude and
			radius of location search
			queries
	Facebook	fb.db -user status	Latitude and longitude of
			status message
	Facebook	fb.db -user values	Latitude,	longitude and
			timestamp of last check-in
	Google-Maps da destination history	Source and destination of
			navigation
	on). The integrated browser stores location data that is normally used
	for Google searches.
	The Twitter app adds GPS coordinates to every published message.
	Although this function is deactivated in Android devices by default, it
	is often enabled by users after installation. Twitter also stores location
	data related to local search requests.

Table 2 .

 2 Stored data from smartphones vs. network operators.

	Data Source Phone 1 Phone 2 Phone 3 Operator
	Cell-Cache	50	50	50	3,223
	WiFi-Cache	67	200	175	0
	Twitter	1	0	5	0
	Google Maps	2	0	3	0
	Pictures	20	0	31	0
	Browser	1	1	1	0
	Facebook	1	0	1	0

Acknowledgements

This research was supported by the German Federal Ministry of Education and Research under Grant No. 01BY1021 (MobWorm). A portion of this research was completed at Schloss Dagstuhl, Leibniz Center for Informatics, Wadern, Germany.


Vassil Roussev

MANAGING TERABYTE-SCALE INVESTIGATIONS WITH SIMILARITY DIGESTS

Keywords: Similarity digests, data fingerprinting, hashing

scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The overwhelming majority of the data collected in a digital forensic investigation is often irrelevant to the subject of the inquiry. Thus, the first step in most investigations is to automatically eliminate as much irrelevant data as possible. Conversely, many investigations may have a very specific focus on locating known relevant artifacts such as images or documents. Therefore, the general approach is to construct a reference set of known data and then use a forensic tool to automatically search the target to filter irrelevant or relevant artifacts as the case may be. Since the common unit of interest is a file, this technique is often referred to as "known file filtering."

The standard known file filtering approach is to use cryptographic hashes, such as MD5 and SHA1, and construct tables of known hash val-ues (e.g., of operating system and application installation files). NIST maintains the National Software Reference Library (NSRL) [11], and some vendors provide even more extensive collections of known hash values. However, a methodological problem with known file filtering is that two matching objects must be identical to the last bit, which makes the matching process very fragile. By extension, it is becoming increasingly infeasible to keep the reference sets current as new software updates are produced almost daily. Additionally, user artifacts are often modified, and tracking the various versions of the artifacts across multiple targets and network streams can be an overwhelming task.

The similarity digest approach described in this paper targets three basic scenarios:

Identification of Embedded/Trace Evidence: Given a data object (file, disk block, network packet), identify the traces of its presence inside a larger object of arbitrary size such as a disk image, RAM snapshot or network capture.

Identification of Artifact Versions: Given a large set of artifacts (files), identify the artifacts that are versions of a set of reference artifacts. The target objects could be executable code (e.g., versions of known software) or user-created data objects (e.g., documents).

Cross-Target Correlation: Identify and correlate different representations of the same or similar object on disk, in RAM or in a network flow. This would allow the automated annotation of disk, RAM and network captures without the deep (and costly) parsing and reconstruction required by current approaches.

In addition to supporting the above scenarios, the approach must meet certain accuracy and performance requirements:

High Precision and Recall Rates: Despite the volume of data, the results must be near certain. A false positive rate of 1% is considered to be excellent in many scenarios; however, this rate would result in 100,000 false positives in a forensic image containing ten million files.

Scalable Throughput: The only hope of keeping up with the growth in data volume is to employ ever larger computational resources. Therefore, a forensic tool should scale horizontally and seamlessly leverage the hardware resources that are made available. Indeed, scalability should be measured in terms of server racks and cabinets, not CPU cores. When a digital forensic laboratory receives a large and urgent case, it should be possible to dedicate the entire data center, if necessary, to obtain results on time.

Stream-Oriented Processing: In terms of performance, commodity hard disks are quickly becoming the new magnetic tapes: their capacities are huge and growing, but the only meaningful way to sustain high throughput is by sequential access. In other words, hard drives need to be read end-to-end, or at least in large chunks. The current approach of file-centric data access via a file system API is convenient for developers, but it does not address the performance nightmare of randomized disk access.

Background

The use of similarity digests is motivated by the observation that data fingerprinting methods based on random polynomials, a technique pioneered by Rabin [START_REF] Rabin | Fingerprinting by Random Polynomials[END_REF], do not work all that well on real data. Specifically, it is difficult to guarantee uniform coverage and control false positives. This section briefly outlines the original similarity digest design and the sdhash implementation. Interested readers are referred to [START_REF] Roussev | Data fingerprinting with similarity digests[END_REF] for additional details.

Statistically Improbable Features

The design of sdhash was inspired, in part, by information retrieval concepts such as statistically improbable phrases. The underlying notion is to pick a set of features that are statistically rare in the general population to represent an object, and later compare the features with those of another object. If a number of these features are common, then a degree of correlation is indicated. The more features in common, the higher the correlation; if all the features match, then the two objects are likely identical.

The main challenge is to translate this idea from text to binary data and to implement it efficiently. The starting point is to define a feature as a 64-byte sequence (string) and consider all the features in an object (such as a file) as candidates. It is infeasible to collect, store and query empirical probabilities for all possible 64-byte features. Instead, a normalized Shannon entropy measure H norm is computed for each feature.

First, the Shannon entropy is estimated as:

H = - 255 i=0 P (X i ) log P (X i )
where P (X i ) is the empirical probability of encountering ASCII code i.

Next, the normalized Shannon entropy measure is computed as:

H norm = ⌊1000 × H/ log 2 W ⌋
where all the features are placed in 1,000 equivalence classes. Using an empirical probability distribution from a representative set, a precedence rank R prec is assigned to each feature, such that a feature with a lower probability has a higher rank.

Next, a popularity rank R pop is defined to express how the precedence rank R prec of a feature relates to those of its neighbors. To calculate the popularity rank R pop , for every sliding window of W consecutive features, the leftmost feature with the lowest R prec is identified and its R pop is incremented by one (evidently, R pop ≤ W ). Intuitively, the rarer the feature, the more likely that the feature has a higher score than its neighbors.

Finally, a sweep is made across all the features, and the features satisfying the property R pop ≥ t are selected (0 < t ≤ W is a threshold parameter). During this process, an additional filtering step is performed, which simply ignores all the features for which H norm ≤ 100. This is based on our empirical studies, which indicate that features with low entropy values trigger the vast majority of false positives.

Similarity Digest Bloom Filter

After the features have been selected, each feature is hashed using SHA1. The result is split into five subhashes (which are treated as independent hash functions) and placed in a Bloom filter [START_REF] Bloom | Space/time trade-offs in hash coding with allowable errors[END_REF][START_REF] Mitzenmacher | Compressed Bloom filters[END_REF] of size 256 bytes. Note that a Bloom filter is a probabilistic set data structure, which offers a compressed representation in exchange for a controllable false positive rate.

In the original implementation [START_REF] Roussev | Data fingerprinting with similarity digests[END_REF], a Bloom filter is declared to be full when it reaches 128 elements (features) and a new filter is created to accommodate additional features. This process continues until all the features are accommodated, at which time, the sequence of filters corresponds to the similarity digest of the original object. This digest representation is referred to as sdbf and the tool that generates and compares the digests is called sdhash (or similarity digest hash).

Several parameters can be tuned to provide trade-offs between granularity, compression and accuracy. However, it is also important to have a standard set of parameters so that independently-generated digests are compatible. Based on exhaustive testing, we selected W = 64, t = 16 along with the parameters mentioned above for the reference implementation. In practical terms, the length of each digest is in the order of 3% of the size of the original data. Thus, each filter represents, on the average, a 7-8 KB chunk of the original artifact.

The base operation for comparing digests is the comparison of two constituent filters. Given two arbitrary filters, their dot product (i.e., the number of common bits due to chance) can be predicted analytically. Beyond that, the probability that the two filters have common elements rises linearly and permits the definition of a similarity measure D(•), which yields a number between 0 and 1.

To compare two digests

F = f 1 f 2 . . . f n and G = g 1 g 2 . . . g m (n ≤ m), a similarity distance SD(F, G) is defined as: SD(F, G) = 1 N n i=1 max j=1..m D(f i , g j ).
In other words, for each filter of the shorter digest F , the best match in G is found and the maxima are averaged to produce the final result. In the special case where F has a single filter, the result is the best match, which is the expected behavior. In the case where the two digests have a comparable number of filters, the similarity distance estimates their highest similarity.

Block-Aligned Similarity Digests

The main goal of this work is to make the basic algorithm, which has been shown to be robust [START_REF] Roussev | An evaluation of forensic similarity hashes[END_REF], more scalable by parallelizing it. As a reference point, the optimized serial version of sdhash (version 1.3) is capable of generating digests at the rate of 27 MB/s on a 3 GHz Intel Xeon processor. It takes approximately 3 ms to query the digest of a 100 MB target for the presence of a small file, which has a single filter as a digest. Thus, the small-file query rate is approximately 33 MB/ms.

The original digest generation algorithm is sequential; it was primarily targeted toward file-to-file comparisons. To parallelize the algorithm, it is necessary to move away from the chain dependencies among sdbf component filters; this allows the concurrent generation of digests.

As it turns out, for larger targets such as disk images, it is possible to use a block-aligned version of sdbf, which we call sdbf-dd. The idea is relatively simple -the target is split into blocks of fixed size and signature generation is performed in a block-parallel fashion. To make this efficient, the output to a filter is fixed such that each block in the original data maps to exactly one filter in the digest. This design has the added benefit that query matches can be quickly mapped to disk blocks and follow-up processing can be performed.

Given that a filter typically represents 7-8 KB of data in the original sdhash design, 8 KiB is the de facto minimum block size. There are two additional considerations that factor into the decision process: larger block sizes lead to smaller signatures and faster comparisons, but make it harder to maintain compatibility with the sequential implementation.

To balance these conflicting requirements, the block size was set to 16 KiB and the maximum number of features per filter was increased from 128 to 192. Under average conditions, we would expect that a 16 KiB block would produce upwards of 256 features that clear the standard threshold of t = 16. Therefore, the features are selected starting with the most popular features until the filter is filled or none of the remaining features are above the threshold.

It was also necessary to increase the maximum number of features per filter for the sdbf version from 128 to 160. This introduces two improvements: (i) the average data chunk covered by a single filter is increased from 7-8 KB to 9-10 KB, thereby shortening the digest and reducing comparison times; and (ii) more features can be accumulated, providing for better compatibility with the sdbf-dd version.

Note that the specific values of the parameters -(i) number of features per sdhash filter (128 to 192); (ii) number of features per sdbf-dd filter (128 to 256); and (iii) sdbf-dd block size (8 KB to 16 KB) -were closen using a grid search to strike the right balance between true positive and false positive rates.

With these parameter values, the in-memory sdhash-dd representation requires approximately 1.6% of the size of original data (260 bytes for every 16,384 bytes of data). Thus, 1 TB data can be represented by a 16 GB digest, which easily fits in RAM. The new sdhash representation with variable chunk size and 160 elements per Bloom filter requires, on the average, 2.7% of the size of the original file (258 bytes per 9,560 bytes of data). The on-disk representations of both versions are base64encoded, which incurs a 33% overhead, but this is easily recoverable with standard lossless compression for archival purposes.

Experimental Evaluation

This section assesses the throughput and accuracy of the proposed approach. All the measurements are based on sdhash version 1.7, which is available at roussev.net/sdhash/sdhash.html.

Throughput

All the performance tests were run on a Dell PowerEdge R710 server with two six-core Intel Xeon 2.93 GHz CPUs with hyper-threading, for a This experiment quantified the scalability of the parallelized version as a function of the number of threads employed. The experiment used a 10 GB memoryresident target, which was hashed to eliminate I/O effects.

The results are shown in Table 1. It is evident that excellent scalability is achieved, with the 24-threaded runs achieving 370 MB/s of throughput. For reference, a SHA1 job on the same target produced a throughput of 333 MB/s. It is also clear that, given enough hardware parallelism, the sdhash-dd computation is I/O-bound.

Additionally, sdhash-dd was applied with 24 threads to a 100 GB target. The computation took 475 seconds with a cold cache, yielding an effective throughput of 210 MB/s.

4.1.2

File-Parallel Digest Generation. File-parallel hashing was implemented to scale up the performance of the sdhash version of the code, which is still the preferred digest algorithm for most files. To quantify the performance gain, a 39,700 file sample from the Govdocs1 corpus [START_REF]Digital Corpora, NPS Corpus[END_REF][START_REF] Garfinkel | Bringing science to digital forensics with standardized forensic corpora[END_REF] was employed; the total size of the sample was 26.75 GB.

Table 2 summarizes the results. Note that 300 files were not hashed because their size was under 512 bytes. Also, all the files were cached, so the performance of the I/O system was not a factor in the experiment.

The task distribution in the current implementation is not optimalthe files provided on the command line are deterministically split among the threads with no regard to their size. Thus, an "unlucky" thread could be tasked to digest a well above average amount of data and, therefore, slow down the overall completion time. Another impediment to further speedup is that many of the files in the sample were small, To better understand these effects, a synthetic set of 10,000 files (500 KB per file) was created, and the experiment was performed again. The results are shown in Table 3.

Additionally, sdhash was applied with 24 threads to each of the 147,430 files on the mounted 100 GB target from the previous experiment. With a cold cache, the computation took 1,621 seconds for an effective throughput of 57 MB/s. Figure 1 summarizes the parallelization speedup of digest generation achieved in each of the three cases discussed above: (i) sdhash-dd; (ii) sdhash on real files; and (iii) sdhash on an optimally-balanced workload.

Note that, although the experimental server supported 24 hardware threads, there were only twelve CPU cores. Running two threads on the same core only yields benefits if the threads have complimentary workloads or a thread is stalled. In the experiments, the threads competed for the same CPU units, so the speedup can be expected to increase moderately when going from 12 to 24 threads. The graph in Figure 1 clearly demonstrates this behavior, which results in the sdhash scalability flattening out. Another contributing factor to the difference between the sdhash and sdhash-dd scalabilities is that the former has higher memory management overhead -multiple allocations/deallocations per file versus one large allocation for sdhash-dd. 4 shows the digest comparison rates at various levels of concurrency. The experiment involved 372.9 million Bloom filter (BF) comparisons. The main measure is the number of Bloom filter comparisons per millisecond (BF/ms). Based on this measure, it is possible to calculate the expected execution time for different workloads.

One of the main benchmarks is the comparison rate for small files (≤ 16 KiB) that have digests of one Bloom filter. Based on the 24thread rate, the search of (the digest of) a target for a small file should proceed at the rate of 58, 000× 16, 384 bytes = 950 MB/ms or 950 GB/s.

Relative to the original rate of 33 MB/ms, even the new singlethreaded version offers a speedup of 9.73 times (321 MB/ms) by almost completely eliminating floating point operations and optimizing the dominant case of Bloom filter comparisons. The 24-threaded execution is 28.78 times faster (950 MB/ms). The comparison operation offers an extreme example of how the execution of two threads on a single core offers virtually no advantage because the threads compete for the same functional units.

The above rates are inclusive of the time taken to load the digests. To gain a better estimate of comparison rates, we compared the sdbf-dd digest of a 100 GB target (6.1 million Bloom filters) with a set of 300 small files extracted from the image with a total Bloom filter count of 908. The total execution time using the 24 threads completed in 79 seconds, of which 15 seconds were spent loading and setting up the inmemory representation of the digests. Thus, the "pure" comparison rate is 86,600 BF/ms or 1.4 TB/s for the small file case. This figure is representative of a server-side deployment in which the reference set is loaded once and queried many times.

Accuracy

We recently performed a detailed study [START_REF] Roussev | An evaluation of forensic similarity hashes[END_REF] of the base sdhash algorithm and its performance on controlled and real-world data. Therefore, we limit our discussion here to validating the new parameters chosen for the algorithm by quantifying the accuracy of the sdbf versus sdbf-dd comparisons.

The experiment for measuring accuracy used synthetic targets generated from random data to precisely control the contents of a query and target. For each query size, a 100 MB target and 10,000 control files of the given query size were generated. Then, 10,000 samples of the given size were extracted from the target. The target was hashed using sdhash-dd while the remaining 20,000 files were hashed with sdhash and then compared with the target; a zero result was assumed to be a negative, whereas a non-zero result was counted as a positive. Ideally, all the samples were expected to match, while none of the controls were expected to match.

Table 5 shows the results for query sizes of 1,000 to 3,800 bytes. The experiment investigated query sizes up to 64 KB; however, for reasons of brevity, the results obtained for higher query sizes are omitted. Note, however, that the observed behavior for higher query sizes was essentially identical to that observed for query sizes of 2 KB and higher.

The results demonstrate that the tool produces near-perfect results for queries of 2 KB and up, which are relevant to a block storage device. For low-end queries, which are relevant to network traffic investigations, the false positive (FP) rate starts out high (due to the small number of features selected), but quickly drops below 1% for queries of size 1.4 KB and up. This is not a coincidence, but the result of tuning the performance parameters, which was discussed above. In general, more than 85% of Internet traffic by volume is in the form of packets in the 1.4 KB to 1.5 KB range [START_REF]Cooperative Association for Internet Data Analysis, Packet size distribution comparison between Internet links in 1998 and 2008, San Diego Supercomputer Center[END_REF]; in other words, long data transfers dominate. In a network investigation scenario, the false positive rate for smaller queries can be managed by searching for multiple packets of the same source; e.g., if sdhash flags three independent packets of 1 KB as belonging to a file, the empirical probability that all three are wrong is only 0.19 3 = 0.0069.

Related Work

The idea of generating a flexible data fingerprint dates back to Rabin's seminal work that was published in 1981 [START_REF] Rabin | Fingerprinting by Random Polynomials[END_REF]. Since then, many researchers have developed more complex versions, but Rabin's basic idea has carried over with relatively small variations. In the following, we limit the discussion to the essential ideas. Interested readers are referred to [START_REF] Roussev | Hashing and data fingerprinting in digital forensics[END_REF] for a detailed survey of hashing and fingerprinting techniques.

Rabin Fingerprinting

Rabin's scheme is based on random polynomials; its original purpose was "to produce a very simple real-time string matching algorithm and a procedure for securing files against unauthorized changes" [START_REF] Rabin | Fingerprinting by Random Polynomials[END_REF]. A Rabin fingerprint can be viewed as a checksum with a low, quantifiable collision probability that can be used to efficiently detect identical objects. In the 1990s, there was a renewed interest in Rabin's work in the context of finding similar (text) objects. For example, Manber [START_REF] Manber | Finding similar files in a large file system[END_REF] used the concept in his sif tool to quantify similarities among texts files; Brin [START_REF] Brin | Copy detection mechanisms for digital documents[END_REF], in his pre-Google years, used it in a copy-detection scheme; and Broder [START_REF] Broder | Syntactic clustering of the web[END_REF] applied it to find syntactic similarities among web pages.

The basic idea, alternatively called anchoring, chunking or shingling, is to use a sliding Rabin fingerprint over a fixed-size window to split the data into pieces. For every window of size w, a hash h is computed, divided by a chosen constant c, and the remainder is compared with another constant m. If the two values are equal (i.e., m ≡ h mod c), then the beginning of a chunk (anchor) is declared, the sliding window is moved one position, and the process is repeated until the end of the data is reached. For convenience, the value of c is typically a power of two (c = 2 k ) and m is a fixed number between zero and c -1. After the baseline anchoring is determined, the characteristic features can be selected by: (i) choosing the chunks in between the anchors as features; (ii) starting at the anchor position and picking the next l number of bytes; or (iii) using multiple, nested features.

Note that, while shingling schemes pick a randomized sample of features, they are deterministic and, given the same input, produce the exact same features. Also, they are locally sensitive in that the determination of an anchor point depends only on the previous w bytes of input, where w could be as small as a few bytes. This property can be used to address the fragility problem in traditional file and block-based hashing.

Consider two versions of the same document. One of the documents can be viewed as being derived from the other as a result of inserting and deleting characters. For example, an HTML page could be converted to plain text by removing all the HTML tags. Clearly, this would modify a number of features, but we would expect chunks of unformatted text to remain intact and to produce some of the original features, facilitating an automatic correlation of the versions. For the actual feature comparison, the hashes of the selected features can be stored and used as a spaceefficient representation of the fingerprint of an object.

Similarity Hashing

Kornblum [START_REF] Kornblum | Identifying almost identical files using context triggered piecewise hashing[END_REF] was among the first researchers to propose the use of a generic fuzzy hash scheme for forensic purposes. His ssdeep tool generates string hashes of up to 80 bytes that are the concatenations of 6-bit piecewise hashes. The comparison is then performed using the edit distance. While ssdeep has gained some popularity, the fixed-size hash it produces quickly loses granularity, and can only be expected to work for relatively small files of similar sizes.

Roussev, et al. [START_REF] Roussev | md5bloom: Forensic filesystem hashing revisited[END_REF] have proposed a scheme that uses partial knowledge of the internal object structure and Bloom filters to derive a similarity scheme. This was followed by a Rabin-style multi-resolution scheme [START_REF] Roussev | Multi-resolution similarity hashing[END_REF] that balances performance and accuracy requirements by keeping hashes at several resolutions.

Outside the discipline of digital forensics, Pucha, et al. [START_REF] Pucha | Exploiting similarity for multi-source downloads using file handprints[END_REF] have proposed an interesting scheme for identifying similar files in peer-topeer networks. The approach identifies large-scale similarity (e.g., the same movie in different languages) that can be used to offer alternative download sources in peer-to-peer networks.

Summary

The randomized model of Rabin fingerprinting works well on the average, but when applied to real-world data often suffers from coverage problems and high false positive rates. Both these problems can be traced to the fact that the underlying data can have significant variations in information content. As a result, feature size/distribution can vary widely, making the fingerprint coverage highly skewed. Similarly, low-entropy features produce abnormally high false positive rates, rendering the fingerprint an unreliable basis for comparison.

Active research on payload attribution systems has produced ever more complicated versions of Rabin fingerprints with the goal of ensuring even coverage (see, e.g., [START_REF] Cho | Network forensics on packet fingerprints[END_REF][START_REF] Ponec | Highly efficient techniques for network forensics[END_REF][START_REF] Schleimer | Winnowing: Local algorithms for document fingerprinting[END_REF][START_REF] Shanmugasundaram | Payload attribution via hierarchical Bloom filters[END_REF]. These techniques manage the feature selection process so that big gaps or clusters are avoided. Yet, none of these methods consider false positives due to weak (nonidentifying) features. It is important to recognize that coverage and false positives are inherently connected -selecting weak features to improve coverage directly increases the risk of false positive results.

Conclusions

The similarity-digest-based approach presented in this paper can efficiently correlate large forensic data sets at the byte-stream level. This enables content filtering to be applied on a wide scale and the filtering to be incorporated early in the forensic process. Current best practices dictate that the creation of a cloned copy of the original media, such as a hard drive, is the first step in a formal investigation. However, it is usually the case that no useful processing is done during this lengthy task and, at the end of the task, the investigators know almost nothing more than they did at the beginning of the task. The proposed approach can generate similarity digests at line speed so that content querying can be performed immediately after media cloning. In fact, it is entirely feasible to take this a step further and to start matching hashed data against reference sets even while hashing/cloning is being performed.

Experimental results using an $8,500 commodity rack server demonstrate that a hash generation rate of up to 370 MB/s can be sustained on a 24-threaded system. Content searches of a small (16 KiB) query file in a reference set are executed at the rate of 1.4 TB/s. Moreover, near-perfect true and false positive rates are obtained for query objects of size 2 KB and higher.

The capabilities discussed in this paper can qualitatively change the scope and efficiency of digital forensic investigations. Still, the approach is just the first attempt at massively scaling data correlation. We hope that this work will stimulate efforts to dramatically speed up other automated forensic processing techniques to deal with massive data volumes.

Figure 1 .

 1 Figure 1. sdhash speedup summary.

Table 1 .

 1 sdhash generation performance on a 10 GB target. hardware-supported threads. The host was equipped with a 800 MHz processor, 72 GB RAM and hardware-supported RAID 10 with a benchmarked sequential throughput of 300 MB/s. Unless otherwise noted, the results are presented as stable averages over multiple runs.

		Threads Time Throughput Speedup
			(sec)	(MB/s)
		1	374.0	26.74	1.00
		4	93.0	107.53	4.02
		8	53.0	188.68	7.06
		12	44.5	224.72	8.40
		24	27.0	370.37	13.85
	total of 24 4.1.1	Block-Aligned Digest Generation.

Table 2 .

 2 File-parallel sdhash generation performance on 39,700 files (26.75 GB).

	Threads Time Throughput Speedup
		(sec)	(MB/s)
	1	920	29.08	1.00
	4	277	96.57	3.32
	8	187	143.05	4.92
	12	144	185.76	6.39
	24	129	207.36	7.13
	which increased the overhead and reduced concurrency due to extra I/O
	and memory-management operations.

Table 3 .

 3 File-parallel sdhash generation performance on 10,000 files (5 GB).

	Threads Time Throughput Speedup
		(sec)	(MB/s)
	1	177	28.25	1.00
	4	50	100.00	3.54
	8	30	166.67	5.90
	12	24	208.33	7.38
	24	19	263.16	9.32

Table 4 .

 4 sdhash digest comparison performance with Bloom filters.

		Threads Time Throughput Speedup
			(ms)	(BF/ms)
		1	19,600	19,027	1.00
		4	9,800	38,054	2.00
		8	8,900	41,902	2.20
		12	6,500	57,373	3.02
		24	6,400	58,270	3.06
	4.1.3	Digest Comparison Rates.	Table

Table 5 .

 5 Error rates for sdhash queries versus sdhash-dd target.

	Query	FP	TP	Query	FP	TP
	Size (KB)	Rate	Rate Size (KB)	Rate	Rate
	1.0	0.1906 1.000	2.0	0.0006 0.997
	1.1	0.0964 1.000	2.2	0.0005 1.000
	1.2	0.0465 1.000	2.4	0.0001 1.000
	1.3	0.0190 1.000	2.6	0.0001 0.997
	1.4	0.0098 1.000	2.8	0.0000 1.000
	1.5	0.0058 1.000	3.0	0.0000 0.999
	1.6	0.0029 0.999	3.2	0.0000 0.998
	1.7	0.0023 0.999	3.4	0.0000 0.998
	1.8	0.0013 0.999	3.6	0.0000 1.000
	1.9	0.0010 0.998	3.8	0.0000 0.998


Saif Al-Kuwari

Stephen Wolthusen

FORENSIC TRACKING AND MOBILITY PREDICTION IN VEHICULAR NETWORKS

Keywords: Forensic tracking, mobility models, trace reconstruction

Most contemporary tracking applications consider an online approach where the target is tracked in real time. In criminal investigations, however, it is often the case that only offline tracking is possible, i.e., tracking takes place after the fact. In offline tracking, given an incomplete trace of a target, the task is to reconstruct the missing parts and obtain the full trace. The proliferation of modern transportation systems means that a targeted entity is likely to use multiple modes of transportation. This paper introduces a class of mobility models tailored for forensic analysis. The mobility models are used to construct a multi-modal forensic tracking system that can reconstruct a complete trace of a target. Theoretical analysis of the reconstruction algorithm demonstrates that it is both complete and optimal.

Introduction

Traditional digital forensics is primarily concerned with extracting evidence from electronic devices that may have been associated with or used in criminal activities. In most criminal cases, however, it is also desirable to uncover additional information about suspects, including details about their physical activities. Investigating the locations of a suspect before, during and after a crime, may constitute key evidence, especially if it helps prove that the suspect was in a specific location at a specific time that he previously denied. This type of investigation is called "forensic tracking" [START_REF] Al-Kuwari | Fuzzy trace validation: Toward an offline forensic tracking framework[END_REF], where the tracking is conducted for forensic purposes.

Forensic tracking investigations are usually carried out in an offline manner. A location trace of a suspect is obtained, which undergoes a probabilistic analysis designed to reconstruct the missing parts. A prime example is when a target is randomly captured by CCTV cameras scattered over a particular area. Previous work has focused on conducting offline forensic investigations in a vehicular setting [START_REF] Al-Kuwari | Probabilistic vehicular trace reconstruction based on RF-visual data fusion[END_REF]. This paper extends the approach to deal with scenarios where a suspect uses multiple modes of transportation.

The trace reconstruction algorithm described in this paper involves two main phases: (i) scene representation; and (ii) trace reconstruction. Scene representation uses information about when and where a target was observed to create scattered points over an area, that are subsequently connected to determine the routes that the target could have taken. Trace reconstruction attempts to fill the gaps of missing data between the points where the target was observed. In a multi-modal scenario, a targeted entity is expected to use multiple modes of transportation; thus, all possible routes through the gaps involving pedestrian routes, public routes and a combination of both must be considered to obtain a complete trace of the target. Theoretical analysis of the reconstruction algorithm demonstrates that it is both complete and optimal.

Scene Representation

In order to systematically reconstruct the trace of a target, a graphical representation (map) of the crime scene and the surrounding area must be generated. This is accomplished in five steps as described in this section. To simplify the notation, unnecessary labels and tags are dropped when referring to certain edges and vertices in the map.

Step 1: Map Preparation. In this initial step, a schematic map G M (based on a geographical area M ) of the reconstruction scene is obtained. The reconstruction scene corresponds to the area over which the target trace is to be reconstructed. No restrictions are imposed on the size of G M other than it must cover: (i) all the points at which the target was observed (available traces of the target); and (ii) crime location(s).

Let

G M = (V G M , E G M ) be a scene graph with vertices V G M and edges E G M . We assume that {X G M s ∪ C G M } ∈ V G M such that: X G M s = {x κp 1 , . . . , x
κq n } is the set of locations where the target s was observed; κ p < κ q are the first and last times that s was observed in G M .

C G M = {c κ k 1 , . . . , c κ l m }
is the set of crime locations visited between times k and l. To simplify the discussion, we describe the specifics of the reconstruction algorithm using a single crime. Of course, the algorithm is applicable to multiple crimes.

Step 2: Route Marking. In this step, relevant public transport networks (e.g., buses and trains)

B 1 , B 1 , . . . , B n ∈ B are marked on G M . A transport network B j ∈ B consists of a set of routes B j = {R B j 1 , R B j 2 , . . . , R B j
r } that constitute most of the vertices and edges in G M . Since only public transport routes are marked, vertices in a route R i correspond to a stop (e.g., train station) denoted as an S-vertex, or a road turn denoted as a U -vertex. Similarly, edges can be routed (i.e., part of a route) denoted as a B-edge, or unrouted denoted as a W -edge (mostly added in Step 4 below).

Let e ρ be an edge of type ρ, then:

ρ = B if e ∈ B j ∈B |B j | i=1 R B j i W if e ∈ E G M \ B j ∈B |B j | i=1 R B j i
where |x| is the number of elements in set x assuming that x does not have repeated elements (i.e., corresponding to loop-free routes). Thus, a route R i is defined by the set of vertices V R i = {v 1 , v 2 , . . . , v k } it comprises, and the edges E R i = {e 1 , e 2 , . . . , e k-1 } that link the vertices.

After all the routes are marked, the available traces of the target X M s = {x 1 , x 2 , . . . , x n } are plotted. The traces specify the times and locations where the target has been observed in G M (these form the gaps that must be reconstructed). Each x i is either located on top of a vertex or over an edge (corresponding to a location at an intersection or on a road), i.e., x 1 , x 2 , . . . ,

x n ∈ V G M ∪ E G M .
Elements in X M s should naturally be represented as vertices. Thus, if any x i is located on e i ∈ E G M , then e i is split at the location of x i such that e i = e 1 i + e 2 i . Following this, x i is added to V G M (as a U -vertex) and e i is replaced by e 1 i , e 2 i in E G M , while updating the V R i and E R i of any route R i passing through e i . Next, the locations of the crimes C G M = {c 1 , c 2 , . . . , c m } are marked on G M , but this time a c i may not be on top of a vertex or an edge, in which case, a W -edge is created between c i and the closest v i ∈ V G M . Note that it is acceptable for c i to be on top of an edge e i ∈ E G M because C G M is not involved in the reconstruction process. Finally, the directions of all the edges e i ∈ E G M are specified. The directions of the B-edges e B i can easily be determined by referring to their corresponding routes, while the W -edges e W i are undirected.

Generally, a single edge e i or vertex v i cannot have two different types at the same time. If a particular vertex v i is part of n routes R i , R j , . . . , R n , then it is an S-vertex as long as v i is an S-vertex in at least one of R i , R j , . . . , R n ; otherwise, it is a U -vertex. In contrast, edges are not allowed to be part of more than one route because different routes may assign different weights to their edges. Thus, if more than one route traverses an edge, then as many edges as there are routes are created.

Let e i : v p → v q be an edge between vertices v p and v q , and suppose that n routes pass through e i , then e i is relabeled to e i,1 and n -1 extra edges are created and labeled as e i,2 , . . . , e i,n . Thus, G M is a mixed multi-graph (i.e., it contains directed and undirected edges) and multiple directed edges can have the same head and tail vertices.

Step 3: Vertex/Edge Labeling. All the vertices and edges (except W -edges) are assigned unique labels to specify the routes of which they are a part. A vertex v ℓ i i with label ℓ i = R k j , . . . , R n m indicates that the i th vertex in V G M is simultaneously the k th , . . . , n th vertex of routes R j , . . . , R m , respectively. Since all the vertices are parts of routes, a label ℓ should contain information about at least one route. Edges are characterized by the vertices they link. Thus, e ℓ i i : v ℓp p → v ℓq q means that the i th edge in E G M has its head and tail at v p , v q ∈ V G M where p, q ∈ {1, 2, . . . , |V G M |}. The head v p and tail v q belong to at least one common route, and they are ordered in succession according to the direction of the edge. If more than one route passes by e i , extra parallel edges are created and labeled (Step 2).

Step 4: End Vertices. After all the vertices and edges are labeled, a special set ρ G M is created that contains all the "end" vertices -these are the first and last vertices of every route R i ∈ B j (head and tail of R i ). To simplify the discussion, we consider the routes of a single transportation network B j ; this can easily be extended to multiple networks B m , . . . , B n ∈ B.

Vertices belonging to ρ G M are found by computing the adjacency matrices A R 1 , A R 2 , . . . , A Rn of all the routes R 1 , R 2 , . . . , R n ∈ B j where |B j | = n (B j contains n routes). A particular vertex in R i belongs to ρ G M if its corresponding row in A R i sums to one. Note that A Ry i,j represents the element in the i th row and j th column of A R i . An entire row is denoted as A Rz i, * and an entire column is denoted as A Rz * ,j (i.e.,

A Rz = A Rz * , * ). Thus, formally:

ρ G M = B j ∈B ρ G M B j = B j ∈B R i ∈B j ⎛ ⎝ v k : k∈R i A R i k, * = 1 ⎞ ⎠ Proposition 1. A vertex v j ∈ V i in the adjacency matrix A R i of a finite loop-free route (i.e., simple path) R i = (V i , E i )
, where V i and E i are the sets of vertices and edges forming R i , is an end vertex if its corresponding row A R i j, * in A R i sums to one.

Proof. Let the route R i be represented by the ordered sequence of vertices v 1 , v 2 , . . . , v n where v 1 and v n are the first and last vertices of R i (end vertices). Clearly, v 1 and v n are each adjacent to a single vertex belonging to R i , namely v 2 and v n-1 , respectively. All the other vertices v 2 , . . . , v n-1 are adjacent to two vertices belonging to R i , i.e., v i is adja-

cent to v i-1 and v i+1 for i ∈ {2, . . . , n -1}. Therefore, A R i 1, * = A R i n, * = 1, while A R i i, * = 2 for i ∈ {2, 3, . . . , n -1}. Since the routes in G M are directed, ρ G M B j = - → ρ G M ∪ ← -ρ G M where - → ρ G M
and ←ρ G M are the sets of head and tail (end) vertices of the routes in G M .

Step 5: Additional Edges. This final step creates additional Wedges between several vertices. A new W -edge is created between any two S-vertices if: (i) they belong to different routes; and (ii) the distance between them is no greater than a threshold W max . Formally, the set η of the new W -edges is:

η = e W,ℓ k k = v S,ℓm m ↔ v S,ℓn n : ℓ m ̸ = ℓ n ∧ d(v S,ℓm m , v S,ℓn n ) ≤ W max
where d(x, y) is the distance between x and y. Note that the effect of the infrastructure on the W -edges is disregarded. In other words, we assume that there are no major obstacles between the S-edges that prevent Wedges from being created. However, integrating infrastructure information is easy because most modern maps contain such information. Next, d(x, y) is found by rerouting around the infrastructure and checking that d(x, y) ≤ W max . Finally, the graph

G M = (V G M , E G M )
is defined in terms of its edges and vertices, where

E G M = E G M R ∪E G M W and V G M = X G M s ∪ C G M ∪ V G M S ∪ V G M U .

Mobility Modeling

Mobility models have traditionally been used in computer simulation, where running an experiment (e.g., evaluating a protocol) on real systems is both costly and inconvenient. Mobility models generate artificial mobility traces that resemble mobility patterns of real entities. However, these traces cannot be directly used to reconstruct real traces that have been already made by real-life entities. This is mainly because real mobility patterns are based on human judgment, which is usually stochastic in nature. However, we show that, although mobility traces generated by these models are sufficiently artificial, they can still be used effectively in the reconstruction process.

Mobility models are usually developed at a microscopic level, modeling the mobility of each object in relation to its surrounding environment and neighboring objects, and thus generating realistically-looking traces. Most models, therefore, carefully parameterize the velocity and acceleration of the objects and repeatedly adjust them throughout the simulation. However, in our case, mobility models are used to estimate the time a target entity may have spent while moving from one point to another, completely disregarding the microscopic details. We refer to this class of mobility models as "delay mobility models." In addition, since we are considering a multi-modal scenario where an entity occasionally changes its mode of transportation, it is necessary to model each mobility class as well as the "gluing" of the different models to obtain smooth transitions.

The following sections introduce several mobility delay models, and proceed to model the transition between them.

Pedestrian Mobility Delay Model

Popular pedestrian mobility models, such as the social force model [START_REF] Helbing | Social force model for pedestrian dynamics[END_REF], cannot be directly used in our scenario because they require detailed microscopic information that may not be available. Also, the models focus on inter-pedestrian behavior, which is not important in our scenario. Therefore, we introduce the pedestrian mobility delay model (PMDM) to calculate the time an entity x (pedestrian) takes to move from point a to point b (we are only concerned about the time). The mobility of the entity is mainly influenced by the static and moving obstacle objects that force the entity to perform a suitable "maneuver" in order to avoid them. Each obstacle object to be avoided by the entity is represented as a circle with known centre and radius.

The extra distance that the entity has to travel when maneuvering around an obstacle is approximately the length of the arc formed by the chord cutting through the obstacle's circle based on the entity's direction. The time spent by the entity to traverse from point a to point b is given by:

t s a,b = d a,b + i∈S r i cos -1 2r 2 i -c 2 4r i + ω v s -ϵ + j∈M g((r s + r j ) -d x,j ) (1)
where S and M are the spaces of the static and moving objects, respectively; r i is the radius of the circle surrounding an object (representing its range); c is the length of the chord cutting through the object's circle (obtained via secant line geometry and the direction -→ e s of the target); r s is the radius of the circle surrounding the target s moving with speed up to v s ; d s,j is the distance between the center of s and the center of j; ω is a slight delay due to random factors imposed on the entity (e.g., crossing a road); ϵ is a random negative value (modeling the deceleration of the entity as it avoids obstacles); and g() is a function given by:

g((r s + r j ) -d s,j ) = 1 if r s + r j ≥ d s,j 0 otherwise
which models the time the entity pauses when it comes across a moving object (i.e., waiting for the object to move away). At first glance, Equation (1) may appear to incorporate microscopic details because it models the interactions between objects. However, these details can be modeled without necessarily simulating the scenario at a microscopic level and only by assuming knowledge of the movement directions of the entity. The maneuvering behavior of the entity around static objects (e.g., buildings) is easily modeled by referring to the scene map G M . The number of interactions between an entity and moving objects (e.g., other pedestrians) can be estimated subjectively based on the popularity of the area and the time.

Transport Mobility Delay Models

Another class of common mobility models describes the mobility of vehicular entities, modeling public transport modes such as buses, trains, and underground tubes. Note that we do not consider private vehicles because they are not relevant to our scenario; however, they can be considered to be a special type of the mobility model described in this section (TTMDM). In this model, the mobility of objects is more structured and less stochastic than those in pedestrian models because they are usually constrained by a fixed infrastructure (e.g., roadways and train tracks). However, based on the infrastructure, a distinction can be made between two naturally different types of vehicular mobility patterns. We call the first type "traffic-based transport" and the second "non-traffic-based transport."

The traffic-based transport mobility delay model (TTMDM) is concerned with objects whose mobility is governed by uncertain parameters that, in some cases, could affect the mobility behavior significantly. The model describes the mobility of objects like buses, coaches and similar road-based public transport carriers whose mobility patterns highly depend on road traffic conditions that cannot be modeled precisely in most cases. The non-traffic-based transport mobility delay model (NT-MDM), on the other hand, is easier to develop because random delay factors (such as those in TTMDM) have negligible, if any, effects on mobility behavior. NTMDM is used to model the mobility of infrastructurebased public transportation modes such as trains and underground tubes where, apart from rare occasional signal and other minor failures, have deterministic mobility patterns.

Traffic-Based Transport Mobility Delay Model. Most realistic traffic-based mobility models [START_REF] Harri | Mobility models for vehicular ad hoc networks: A survey and taxonomy[END_REF] adjust the velocity of objects to avoid collisions. However, this level of microscopic modeling is not required in our scenario because we are only concerned about the time taken for objects to move from one point to another, not their actual movements. Thus, we model the factors that affect the time value, which is estimated using the equation: Non-Traffic-Based Transport Mobility Delay Model. Modeling non-traffic-based transport is clearly more straightforward because the uncertainty of the stochastic delays suffered by traffic-based transport is largely eliminated (or mitigated). This class describes the mobility of vehicular entities with fixed infrastructure such as trains and underground tubes. In this case, the time taken by an object to move from point a to point b can be computed using the classical distance equation:

t a,b = d a,b va,b + D traffic a,b + D interest a,b + D abnormal a,b (2)
t a,b = d a,b v a,b + D abnormal a,b
where v a,b is the fixed speed of the object on its journey from a to b spanning a distance d a,b (which can be obtained offline).

Multimodal Mobility Delay Model

Conventionally, when modeling the mobility of a particular object, it is implicitly assumed that the object's behavior is consistent throughout the simulation. However, in our scenario, we cannot rule out the possibility that the target could have used multiple different transportation modes, each with different mobility characteristics. Thus far, we have introduced three mobility delay models (PMDM, TTMDM and NTMDM). We now model the transition between them by constructing a multimodal mobility model (MMM) to assure a continuous flow of the target. Essentially, MMM only models the "transition behavior" between two different models (or two different carriers of the same model) because, once the transition is completed, the relevant mobility model is called to simulate the mobility of the next part of the journey until another transition is required. A "homogenous" transition occurs between two carriers of the same mobility model (e.g., changing a bus). On the other hand, a "heterogeneous" transition occurs between two carriers of different mobility models (e.g., changing from a bus to a train).

In a vehicular setting, we are interested in tracking the target who is transported by a carrier vehicle, not the vehicle itself; thus, the entity who makes the transition must be modeled. Clearly, in PMDM, both the entity and the carrier are a single component. When an entity shifts from any model to PMDM, the transition is smooth and incurs no delay (i.e., an individual does not have to wait before commencing a "walk" behavior). For any other situation, however, transition modeling is required to calculate the time an entity waits before shifting to the next model (or carrier). The main idea is to observe the timetables of the carriers at the transition location and calculate the transient wait time.

In a level-1 transition, the entity shifts from PMDM to TTMDM or NTMDM. In both cases, the entity most likely experiences a slight transient delay due to the time interval between its arrival at location x and when the next carrier belonging to the intended model departs. Therefore, as soon as the entity arrives at x, it checks the intended carrier's timetable for the next departure time at its current location based on the current time and calculates the time difference. We will discuss this process in detail when we describe a level-2 transition, which generalizes a level-1 transition.

Recall that in our scene graph G M roadways are represented by edges E G M and intersections by vertices V G M . A transition can only occur at an intersection, so let v i ∈ V G M be a transition vertex at which n carriers from either TTMDM or NTMDM stop. Let these carriers be denoted by R 1 , R 2 , . . . , R n (this information is included in the label of v i ; see Section 2). The first step is to obtain the timetables of the n carriers T R 1 , T R 2 , . . . , T Rn and convert them into matrices M R 1 , M R 2 , . . . , M Rn , where the rows represent stops and the columns represent journeys.

Note that the dimensions of the matrices depend on the timetables and may be different for different carriers. Next, we extract the rows corresponding to v i from M R 1 , M R 2 , . . . , M Rn and create a 3D matrix M v i by superposing the rows.

The dimensions of this new 3D matrix M v i are 1 × L × n, such that:

L = max{w(M R 1 ), w(M R 2 ), . . . , w(M Rn )}
where w(M ) is the width (number of columns) of matrix M . In other words, L is the number of journeys made by the carrier R i that makes the highest number of journeys where i ∈ {1, 2, . . . , n}. Obviously, if R 1 , R 2 , . . . , R n do not all make the same number of journeys, M v i would contain some undefined values. We assume access to a global clock that returns the current time when the function cT ime() is invoked.

After

M v i is created, c = cT ime() is used to build a 1 × n matrix M v i = [m 1,1 , m 1,2 , . . . , m 1,n ] such that: m 1,j = ⎧ ⎪ ⎨ ⎪ ⎩ |c -m 1,j,z | + ϵ if z ≥ c ≥ z + 1 ϵ if c = z or c = z + 1 ∞ otherwise
where ϵ is a random delay representing the factors that may hold the carriers (e.g., traffic) plus the wait time at each stop. The matrix M v i now indicates how long an entity at the current location x has to wait to pick a carrier R 1 , R 2 , . . . , R n passing by x (regardless of whether R 1 , R 2 , . . . , R n belong to the same or different models). In particular, the matrix lists all the carriers that stop at v i along with their delay times.

Trace Reconstruction

Classical missing data algorithms, such as EM [START_REF] Dempster | Maximum likelihood from incomplete data via the EM algorithm[END_REF] and data augmentation [START_REF] Tanner | The calculation of posterior distributions by data augmentation[END_REF], cannot be directly used in our scenario because the algorithms primarily make statistical inferences based on incomplete data, but do not reconstruct traces. Additionally, it cannot be assumed that a sufficiently large number of available traces are available in order to use these algorithms. Iterative sampling algorithms, such as Markov chain Monte Carlo (MCMC) [START_REF]Markov Chain Monte Carlo in Practice[END_REF], even when adapted for missing data, cannot be used for the same reasons. Instead, we take a different algorithmic approach to fill the "gaps" formed by the missing traces. We develop an efficient reconstruction algorithm that, using mobility delay models, selects the route(s) that the target most likely has taken through a gap given the time it spent traversing the gap. In the worst case scenario, the algorithm eliminates several routes that the target could not possibly have taken, which may still constitute important evidence.

The reconstruction algorithm A R first considers each gap individually and reconstructs the gap. The reconstructed gaps are connected to obtain the full trace of a target s.

Abstractly, A R has two fundamental building blocks: (i) a multigraph traversing algorithm called weight-bound-search (WBS); and (ii) various mobility models. After A R is executed, the reconstruction algorithm proceeds by running WBS over a gap. The WBS algorithm, in turn, repeatedly calls the mobility models (possibly via A R ) and returns a route (or routes) that connect the gap. The A P algorithm then reconstructs the other gaps in a similar fashion.

The WBS algorithm employs a branch-and-bound approach to optimize the reconstruction process, and uses a "crawler" to traverse gaps and find plausible routes. For a gap G p : v m → v n between vertices v m and v n where m, n ∈ {1, 2, . . . , |V G M |}, a crawler C Gp is generated at v m and broadcasted toward v n . The crawler C Gp maintains two data structures: (i) a LIFO list of vertices and edges traversed χ C Gp ; and (ii) a delay variable τ C Gp . The variable χ C Gp is dynamically updated whenever C Gp traverses a vertex or edge to keep track of all the vertices and edges that the crawler C Gp has visited. The delay variable τ C Gp , which is initially set to zero, is also dynamically updated whenever C Gp traverses an edge or an S-vertex (but not a U -vertex as described below).

When C Gp is first initiated at v m , it checks the v m label ℓ m = {R y x , . . . , R l k }, which contains information about the routes of which v m is a part and locates its l m next-hop neighboring vertices using the equation:

l m = |ℓ m | if v m ̸ ∈ ← -ρ G |ℓ m | -k if v m ∈ ← -ρ G
where k is the number of times v m appears in ←ρ G (number of routes in which v m is a tail-end vertex; these routes terminate at v m and thus do not have a next-hop).

Since we are considering a multi-graph, it is possible that some of the routes pass by the same next-hop neighbor (creating parallel edges between two vertices), so the l m list may contain repeated vertices. If this is the case, each outgoing edge (even if all the edges are parallel) must be considered separately because the edge may have a different weight depending on the route to which it belongs. Thus, after all the next-hop neighbors are found, C Gp selects one of them, say v u , finds the edges (routes) between v m and v u , i.e., {e i |e i : v m → v u }, and selects one e i .

After an e i is selected, C Gp tags it as "visited," updates χ C Gp and proceeds to traverse it. It is important that C Gp tags every traversed edge as "visited" so that the edge is not revisited, potentially resulting in an infinite loop. Furthermore, if C Gp arrives at a vertex v k and finds that there is only one unvisited edge e i , it tags e i as "visited," traverses it and then tags v k as "exhausted" so that v k is skipped if it happens to be a neighbor of some vertex that C Gp traverses in the future. Based on the type of the edges connecting v m with its next-hop neighboring vertices, C Gp calls the appropriate mobility model (PMDM, TTMDM or NTMDM) to calculate the delay of the edge. Next, it updates τ C Gp using the equation:

τ C Gp = τ C Gp + t vx,vy
where t vx,vy is the delay returned for the edge e i : v x → v y by the relevant mobility model (this applies to R-and W -edges). Similarly, when C Gp reaches an S-vertex v y , it again updates τ C Gp , but this time by calling MMM such that:

τ C Gp = τ C Gp + t vy
where t vy is the delay assigned to v y by MMM. However, since there is no transition between mobility models in U -vertices, MMM is not called when a U -vertex is reached.

The crawler traverses the various routes by repeatedly backing-up whenever it finds a plausible or implausible route. The back-up procedure proceeds as follows: when the crawler finds an (im)plausible route, it checks χ C Gp and traverses backward through the edge in χ C Gp [START_REF] Al-Kuwari | Probabilistic vehicular trace reconstruction based on RF-visual data fusion[END_REF] toward the vertex χ C Gp [START_REF] Al-Kuwari | Fuzzy trace validation: Toward an offline forensic tracking framework[END_REF] where χ[n] is the n th element of the list χ. Next, it deletes the two elements from χ C Gp and repeats the entire traversal process, but this time it does not traverse the edge it just came from because it is now tagged as "visited" (or generally any edge tagged as "visited").

The crawler C Gp backs-up if: (i) τ C Gp + ϵ > t vn,vm ; or (ii) traverses a vertex/edge that already exists in its χ C Gp ; or (iii) v n (other end of the gap) is reached where ϵ is a random value; or (iv) reaches a vertex v j such that v j is a tail-end vertex in all its routes (i.e., v j is childless).

In (i), the crawler backs-up when τ C Gp reaches a value greater than t vn,vm (time difference between when the target was observed at v m and later at v n -corresponding to the two ends of a gap G p ), and ϵ is a small constant. This means that the target would take much longer than t vm,vn if it had traversed that route. In (ii), only loop-free routes are accepted because these are what a rational target would opt to take (they also prevent infinite loops); so, if C Gp reaches a vertex v i such that v i ∈ χ C Gp , then it backs-up. In (iii), when C Gp reaches v n , it checks τ C Gp . If τ C Gp + ϵ ≤ t vm,vnϵ, it backs-up (in other words, if a crawler returns a time much shorter than t vm,vn , it is probably not the route that the target has taken). Otherwise, if t vm,vnϵ ≤ τ C Gp ≤ t vm,vn + ϵ, it backs-up, returns the route in χ C Gp as a possible route the target may have taken and returns the corresponding τ C Gp . Finally, in (iv) C Gp also backs-up when it reaches a childless vertex v j ; additionally, it tags v j as "exhausted."

The WBS algorithm terminates when its crawler terminates. This occurs when the crawler reaches a vertex in which all neighboring (nexthop) vertices are tagged as "exhausted," meaning that they have already been traversed extensively (i.e., all their outgoing edges are tagged as "visited").

Proposition 2. Given a finite search graph, the WBS algorithm eventually terminates with or without returning valid routes.

Proof. Since the WBS is a weight-based algorithm, it is guaranteed to stop traversing a particular route R i when its weight counter τ C Gp expires (i.e., τ C Gp ≥ t vm,vn + ϵ where t vm,vn is the delay through gap G p : v m → v n and ϵ is a small constant). Thus, the only way for the algorithm to run indefinitely is when it gets into an infinite loop and traverses the same route over and over again. However, a route R i cannot be traversed more than once because the algorithm tags every visited edge and does not traverse any tagged edge. Thus, the algorithm terminates as long as the graph has a finite number of edges.

The WBS algorithm also terminates when processing an infinitely deep graph because it traverses the graph down to the point when its weight counter τ C Gp expires. However, the WBS algorithm may fail to terminate when processing an infinitely wide graph if none of the children of the current level has a weight higher than τ C Gp . This, nevertheless, contributes to the completeness of the WBS algorithm. Proposition 3. Given a finite search graph, the WBS algorithm is complete. If multiple solutions exist, the algorithm returns all the solutions. Proof. For a gap G p : v m → v n , a valid solution means that there is a route R i : v m → v n with a weight τ such that t vm,vnϵ ≤ τ ≤ t vm,vn + ϵ. The crawler C Gp traverses all valid and invalid routes and terminates when there are no more edges to traverse. Therefore, if such a solution route R i exists, the crawler C Gp will find the route.

If multiple routes are returned after the crawler terminates, then the algorithm selects the "best-fit" route such that: The route with less hops is selected because a rational target would probably choose a route that does not have many stops. Additionally, by observing the labels of the edges and vertices of the returned routes, a preferred route can be selected that minimizes the number of transitions between different mobility models and/or carriers with the same model.

|χ C Gp f | = min{|χ C Gp 1 |, |χ

Conclusions

The multi-modal trace reconstruction algorithm described in this paper engages mobility models tailored for forensic analysis to construct a complete trace of a target who may use multiple modes of transportation. Gaps of missing data between the points where the target was observed are filled by considering all possible routes through the gaps involving pedestrian routes, public routes and a combination of both. Theoretical analysis of the reconstruction algorithm demonstrates that it is both complete and optimal. Certain details have been omitted for reasons of space. Interested readers may contact the authors for a complete description of the algorithm and the accompanying theoretical analysis.

  where va,b is the maximum allowable speed of the roadway between points a and b; D traffic a,b is the expected traffic delay of the roadway between points a and b that depends on the geographical and physical characteristics of the area and the time of day; D interest a,b are delays incurred by points of interest located between a and b; and D abnormal a,b represents abnormal events on the road segment between a and b (e.g., accidents and breakdowns), both D interest a,b and D abnormal a,b can be obtained offline from public resources (e.g., maps) or from the police.