基于NMEA 0183的GPS設(shè)備軌跡恢復(fù)方法

石 凱 徐 明 徐 建 鄭 寧

(杭州電子科技大學(xué)計算機學(xué)院 浙江 杭州 310018)

基于NMEA0183的GPS設(shè)備軌跡恢復(fù)方法

石 凱 徐 明 徐 建 鄭 寧

(杭州電子科技大學(xué)計算機學(xué)院 浙江 杭州 310018)

針對GPS設(shè)備的軌跡恢復(fù)問題，由于傳統(tǒng)的文件恢復(fù)方法依賴于系統(tǒng)元信息，一旦元信息受損、不可讀或重新分配等原因就會恢復(fù)失敗。借助文件雕復(fù)的思想提出一種基于NMEA 0183協(xié)議的GPS設(shè)備軌跡恢復(fù)方法，可以在系統(tǒng)元信息不可用的前提下恢復(fù)出GPS設(shè)備上的軌跡日志數(shù)據(jù)。首先利用軌跡數(shù)據(jù)的特征從鏡像中定位到所有屬于NMEA日志的數(shù)據(jù)塊。再根據(jù)日志數(shù)據(jù)在時間和空間上的局部連續(xù)性以及日志的結(jié)構(gòu)特征設(shè)計一個判別器，對所有已定位的數(shù)據(jù)塊使用重組算法恢復(fù)出日志。最后再根據(jù)相應(yīng)的格式對恢復(fù)出的日志進行解析，重構(gòu)出被刪除的行車軌跡。實驗結(jié)果表明，在數(shù)據(jù)鏡像完整、系統(tǒng)元信息不可用、日志文件高度分片、日志數(shù)據(jù)部分覆寫的情況下恢復(fù)率能夠保持在99%以上，并且能夠兼容不同簇大小的文件系統(tǒng)。

GPS設(shè)備 NMEA 0183協(xié)議 軌跡恢復(fù) 文件雕復(fù)

0 引 言

由于GPS導(dǎo)航設(shè)備能夠提供GPS定位、方位導(dǎo)航和出行路線規(guī)劃等多種實用功能，它在人們生活中的應(yīng)用變得越來越廣泛。與此同時，由于GPS設(shè)備使用量的快速增長，其本身攜帶的數(shù)據(jù)(例如：時間、地點、速度等信息)也變得愈發(fā)重要。尤其是在數(shù)字調(diào)查取證領(lǐng)域中，由于行車軌跡可以證明嫌疑人在什么時間、什么地點出現(xiàn)過，因此GPS設(shè)備上行車軌跡的恢復(fù)是一個十分重要的問題。

值得注意的是，行車軌跡主要由時間信息和地理信息這兩個關(guān)鍵因素構(gòu)成。而這些數(shù)據(jù)是在GPS接收器和衛(wèi)星之間按照NMEA 0183協(xié)議[1]通信所產(chǎn)生的，部分GPS設(shè)備會將該數(shù)據(jù)以NMEA日志的形式保存下來。因此理論上來說，假如能得到GPS設(shè)備上的NMEA日志，就可以按照協(xié)議規(guī)定的特定格式進行解析并重構(gòu)出行車軌跡。然而，假如嫌疑人事先刪除了GPS設(shè)備上的NMEA日志，這無疑將進一步加大取證人員的恢復(fù)難度。

為了能夠從GPS設(shè)備上恢復(fù)出被刪除的NMEA日志，取證人員可以采用傳統(tǒng)的文件恢復(fù)方法進行恢復(fù)。因為文件刪除操作并不會真正擦除文件的數(shù)據(jù)部分，而僅是將相應(yīng)的文件系統(tǒng)元信息部分作了標(biāo)記，表示可用。所以傳統(tǒng)恢復(fù)方法仍然可以根據(jù)元信息定位到被刪除文件的數(shù)據(jù)部分并將其恢復(fù)。但是，一旦元信息受損、不可讀或被重新分配等多種原因，傳統(tǒng)恢復(fù)方法就將無法使用。例如，被刪除文件的數(shù)據(jù)發(fā)生部分覆寫時，其系統(tǒng)元信息已被重新分配給新的文件，根據(jù)傳統(tǒng)恢復(fù)方法的原理，該文件中仍未被覆寫的數(shù)據(jù)部分是無法恢復(fù)的。又如一個破損的硬盤，由于其系統(tǒng)元信息受損，傳統(tǒng)恢復(fù)方法也是無法恢復(fù)的。

因此，鑒于NMEA日志對行車軌跡重構(gòu)的重要性以及傳統(tǒng)恢復(fù)方法的局限性，本文提出一種不依賴于系統(tǒng)元信息的NMEA日志恢復(fù)方法，并根據(jù)恢復(fù)算法實現(xiàn)了GPSDroid系統(tǒng)，成功重構(gòu)出GPS設(shè)備中的行車軌跡，從實踐的角度說明方法的可行性和有效性。

1 相關(guān)工作

NMEA 0183協(xié)議是一套被廣泛用于GPS設(shè)備傳輸數(shù)據(jù)的通信協(xié)議。因為GPS設(shè)備都遵守該協(xié)議來傳輸數(shù)據(jù)，所以可以推測在GPS設(shè)備運行時，其內(nèi)存中應(yīng)該存在大量的NMEA數(shù)據(jù)。例如，文獻[2]的作者在TomTom品牌的GPS設(shè)備內(nèi)存中發(fā)現(xiàn)了大量的NMEA數(shù)據(jù)。相似地，文獻[3]的作者發(fā)現(xiàn)配備GPS模塊的Android手機設(shè)備同樣也使用該協(xié)議來傳輸數(shù)據(jù)，并根據(jù)內(nèi)存中發(fā)現(xiàn)的NMEA數(shù)據(jù)成功重構(gòu)出行車軌跡。因此，這也充分說明了NMEA 0183協(xié)議使用的廣泛性和普遍性以及對軌跡重構(gòu)的重要性。

除了對GPS設(shè)備的內(nèi)存進行研究以外，文獻[4]的作者對Navman品牌系列的GPS設(shè)備中的非易失性閃存也進行了探索。該作者利用取證工具EnCase[5]在提取出的閃存鏡像中恢復(fù)出許多NMEA日志，并對其進行解析生成相應(yīng)的分析報告。然而，由于EnCase的恢復(fù)原理是基于系統(tǒng)元信息的，當(dāng)元信息受損、不可讀或被重新分配的情況下，這種恢復(fù)方法就會失效。

在這種情況下，文件雕復(fù)技術(shù)[6]得到越來越多研究人員的重視。這是一種不依賴于系統(tǒng)元信息，根據(jù)文件自身結(jié)構(gòu)特征來重新組織磁盤數(shù)據(jù)的恢復(fù)方法。

早期的文件雕復(fù)方法比較簡單，主要是利用文件的頭尾特殊字節(jié)特征來定位鏡像中文件所處的物理位置，然后再提取出頭尾之間的數(shù)據(jù)部分作為恢復(fù)的文件[7-8]。然而，隨著文件在磁盤上的存儲越來越復(fù)雜，很有可能發(fā)生文件分片的現(xiàn)象。文件分片是指由于文件系統(tǒng)無法提供足夠的連續(xù)簇來存儲一個文件時，該文件會被分成多段存儲在磁盤上不同的物理位置。這種情況下，早期的頭/尾雕復(fù)方法所恢復(fù)的文件很可能會因為夾雜其他的臟數(shù)據(jù)而導(dǎo)致恢復(fù)失敗。因此，分片文件的恢復(fù)問題也一直是文件雕復(fù)中的技術(shù)難題。一般而言，要想成功地恢復(fù)分片文件，需要更多地挖掘特定文件類型本身的數(shù)據(jù)特性和其內(nèi)部的結(jié)構(gòu)特征。例如，圖片雕復(fù)[9-11]和視頻雕復(fù)[12-13]等許多研究工作均是利用圖片和視頻自身的內(nèi)容特征和文件結(jié)構(gòu)來重新組織磁盤上的文件分片數(shù)據(jù)的。

為了解決NMEA日志的恢復(fù)問題，本文將采用文件雕復(fù)的思想，在不依賴于系統(tǒng)元信息的前提下恢復(fù)出日志的內(nèi)容。通過觀察和分析NMEA 0183協(xié)議的格式以及日志的內(nèi)部結(jié)構(gòu)，能夠從GPS設(shè)備的存儲鏡像中定位到所有屬于NMEA日志的數(shù)據(jù)塊，并設(shè)計了一個判別數(shù)據(jù)塊能否合并的判別器和一個數(shù)據(jù)重組算法，對得到的數(shù)據(jù)塊進行合并和重組操作，有效地解決了分片日志的恢復(fù)問題。最后對恢復(fù)出的日志進行解析，將重構(gòu)出的行車軌跡通過百度地圖可視化顯示。

2 NMEA 0183協(xié)議

由于本文的恢復(fù)算法是基于NMEA數(shù)據(jù)的特征及其內(nèi)部結(jié)構(gòu)進行恢復(fù)的，因此首先我們將對NMEA 0183協(xié)議進行簡單的介紹。

2.1 NMEA 0183介紹

NMEA 0183協(xié)議是由美國國家海洋電子協(xié)會(National Marine Electronics Association)開發(fā)、維護并發(fā)布的一套通信標(biāo)準(zhǔn)，被用于絕大部分的GPS接收設(shè)備中[1]。它規(guī)定GPS接收器與衛(wèi)星每秒進行一次通信，其數(shù)據(jù)以ASCII文本形式的“語句”表示，并且定義了多種相互獨立的語句。其中，雖然NMEA定義了許多種不同類型的語句，但是兼容性最廣的語句分別是：GGA、GSA、GSV、RMC、VTG和GLL。

如圖1所示，這是一張真實的NMEA日志截圖。圖中表示兩條相鄰的NMEA記錄，每條記錄由若干不同類型的語句組成。從圖中我們可以看到，語句的起始部分是該語句的類型，后面是許多個用逗號隔開的字段內(nèi)容。而不同語句類型的格式和字段各不相同，需要注意的是，作為NMEA推薦的定位信息數(shù)據(jù)格式，RMC類型的語句承載了最重要的日期、時間、地理和速度等信息。圖2是對RMC語句格式的詳細(xì)解釋，其中包含了每個字段的含義。因此，只要按照該格式進行解析，就可以提取出相應(yīng)的時間、地理、速度等信息。除此之外，GGA和GLL語句也是非常重要的語句，根據(jù)它們的格式同樣可以提取出相應(yīng)的地理信息。

圖1 NMEA日志

圖2 RMC語句格式解析

2.2 對軌跡重構(gòu)的重要性

在簡單介紹完NMEA 0183協(xié)議之后，接下來我們將解釋為什么它對GPS設(shè)備的軌跡重構(gòu)有著重要的意義。如圖3所示，每個NMEA日志都可以被看成由多個分片組成，而每個日志分片都會包含若干NMEA記錄。其中，每條NMEA記錄都會包含RMC、GGA和GLL等語句。而RMC語句又包含時間、地理、速度等信息。

圖3 NMEA日志內(nèi)部結(jié)構(gòu)

因此，我們可以得到以下結(jié)論：

S={r1,r2,…,rn}

(1)

ri={datei,timei,lati,lngi}i=1,2,…,n

(2)

式中：S是一個記錄的集合。其中r表示一條NMEA記錄，每條記錄都會包含日期、時間、經(jīng)緯度信息。因此，我們可以把NMEA日志中的每一條記錄看成是一個有時間信息的、根據(jù)地理信息對應(yīng)到地圖上的一個軌跡點。只要對這些軌跡點按照時間順序進行排序，我們就可以重構(gòu)出GPS設(shè)備的行車軌跡。

接下來，我們就將介紹在系統(tǒng)元信息不可用的前提下，我們是如何借助NMEA數(shù)據(jù)的特性和內(nèi)部結(jié)構(gòu)特征來解決NMEA日志的恢復(fù)問題。

3 恢復(fù)算法

在本節(jié)中，我們將介紹恢復(fù)算法的具體細(xì)節(jié)。如圖4所示，恢復(fù)算法框架主要分為三個步驟：

(1) 數(shù)據(jù)預(yù)處理 在進行恢復(fù)之前，需要對GPS設(shè)備的存儲鏡像進行數(shù)據(jù)預(yù)處理。該步驟主要是在掃描存儲鏡像的過程中，根據(jù)NMEA數(shù)據(jù)的特征在鏡像中定位到所有屬于NMEA日志的數(shù)據(jù)塊。

(2) 數(shù)據(jù)重組 這個步驟主要是對獲得的數(shù)據(jù)塊進行合并和重組操作。為此，我們設(shè)計了一個用于判別數(shù)據(jù)塊能否合并的判別器，和一個用于數(shù)據(jù)塊重組的算法，將無序的數(shù)據(jù)塊重新組裝成新的日志文件。

(3) 日志解析 該步驟需要將恢復(fù)得到的NMEA日志按照NMEA 0183的格式進行解析，提取出日志中所有RMC語句的時間地理信息，重構(gòu)出被刪除的行車軌跡，并用百度地圖進行可視化顯示。

圖4 恢復(fù)算法框架

3.1 數(shù)據(jù)預(yù)處理

該步驟需要在掃描鏡像文件的時候找出所有屬于NMEA日志的數(shù)據(jù)塊。然而，由于文件系統(tǒng)分布的復(fù)雜性，NMEA日志的數(shù)據(jù)塊可能分布在鏡像中的任意角落。因此，在數(shù)據(jù)預(yù)處理的過程中我們需要注意以下兩個關(guān)鍵點：掃描步長和特征選取。

3.1.1 掃描步長

由于掃描步長的選擇與磁盤中數(shù)據(jù)的存儲分布息息相關(guān)，所以我們先簡要介紹相關(guān)的背景知識。眾所周知，磁盤的最小存儲單元是扇區(qū)(512字節(jié))，而分配文件的最小邏輯單元是簇(一個或多個扇區(qū)組成)[14]。所以，當(dāng)文件系統(tǒng)為一個文件分配存儲空間而找不到足夠多的連續(xù)文件簇時，文件內(nèi)容不得不先被分割成多段然后存儲在磁盤的不同位置，這就是文件分片[15]。而且，由于NMEA日志的內(nèi)容是隨著時間動態(tài)添加的，所以在存儲時特別容易發(fā)生分片的現(xiàn)象。但是，又因為簇是分配文件的最小邏輯單元，所以即使出現(xiàn)文件分片現(xiàn)象，其分片點也只可能發(fā)生在簇的邊界處。所以，只要選取存儲鏡像的簇大小作為掃描步長，就可以避免分片所造成的數(shù)據(jù)切割錯誤。

然而，不同文件系統(tǒng)的簇大小并不都是一樣的。由于我們的恢復(fù)算法是不基于系統(tǒng)元信息的，也就是說文件系統(tǒng)的簇大小是未知的。而且，選取不當(dāng)?shù)膾呙璨介L將會造成數(shù)據(jù)的誤讀。如圖5(a)所示，當(dāng)鏡像的簇大小是1 KB而掃描步長是4 KB時，除了有效數(shù)據(jù)A被識別外，臟數(shù)據(jù)B也會被誤認(rèn)為是日志的數(shù)據(jù)塊。因此，為了保證算法的兼容性，我們選取最小的簇大小值(512 B)作為掃描步長。因為簇大小都是512 B的整數(shù)倍，即使一個鏡像的簇大于512 B，仍然可以將這個簇看成是由多個512 B的數(shù)據(jù)塊組成的。例如，如圖5(b)所示，當(dāng)鏡像簇大小是1 KB而掃描步長是512 B時，有效數(shù)據(jù)區(qū)域A被看作是兩個512 B的數(shù)據(jù)塊，均可以成功被定位到，而此時的臟數(shù)據(jù)B也不會被誤認(rèn)為是NMEA日志的數(shù)據(jù)塊。

圖5 掃描步長對數(shù)據(jù)塊定位的影響

3.1.2 特征選取

在確定掃描步長之后，我們還需要選取出特征，能夠在掃描鏡像的過程中判斷某個數(shù)據(jù)塊是否屬于NMEA日志。根據(jù)NMEA 0183協(xié)議規(guī)范的定義，每類語句的起始部分都是特定的字節(jié)序列(例如＄GPGGA,＄GPGSA,＄GPGSV,＄GPRMC,＄GPVTG,＄GPGLL)。因此，我們可以確定每個屬于NMEA日志的數(shù)據(jù)塊都應(yīng)該至少包含這些特殊字節(jié)序列中的一個。而且，相比較于其他的統(tǒng)計特征分類方法[16-17]，這種特定字節(jié)序列的搜索方法顯得更加簡單高效。

根據(jù)我們的實驗統(tǒng)計觀察，NMEA日志中的單條記錄不會超過512 B。因此，一條NMEA記錄在一個512 B的數(shù)據(jù)塊中有3種分布情況。如圖6所示，(a)表示一個數(shù)據(jù)塊恰好包含一條完整記錄；(b)表示一條記錄橫跨在兩個相鄰數(shù)據(jù)塊中；(c)表示一條記錄被分割成了兩段，并且日志發(fā)生了分片。

圖6 NMEA記錄在數(shù)據(jù)塊中的分布情況

這三種情況都可以根據(jù)特殊字節(jié)序列在鏡像中被定位到，但是由于圖6(a)中的數(shù)據(jù)塊包含完整的一條記錄，所以可以根據(jù)其中的RMC語句提取出相應(yīng)的時間、地理信息。而對于(b)和(c)，兩者都需要與相應(yīng)的另一半合并才能提取出完整的記錄和相應(yīng)的信息。值得注意的是，根據(jù)文件存儲的局部性原理，雖然可能存在文件分片現(xiàn)象，但是一個文件中邏輯相鄰的數(shù)據(jù)塊很大可能在物理存儲時也是相鄰的。因此理論上來說，(b)出現(xiàn)的概率要大于(c)。

為了能夠辨別出是(b)還是(c)，我們可以根據(jù)NMEA 0183協(xié)議的另一個特征“校驗和”(一條語句中＄和*之間所有ASCII字符的異或值，詳見圖2)來判斷物理相鄰的兩個數(shù)據(jù)塊是否在邏輯上也是相鄰的。具體地，假如一個數(shù)據(jù)塊無法提取時間信息，則可以先嘗試將該數(shù)據(jù)塊與下一個數(shù)據(jù)塊進行合并操作。然后再提取出兩個數(shù)據(jù)塊分界處拼湊成的語句，并利用協(xié)議所定義的校驗和計算方式算出該拼湊語句的校驗和，與該拼湊語句末尾的校驗和字段進行比較。如果兩者的值是吻合的，那么說明這兩個物理上相鄰的數(shù)據(jù)塊在邏輯上也是連續(xù)的(即情況(b))，可以按照RMC語句的格式從合并后的記錄中提取出相應(yīng)的時間、地理信息；如果兩者的值不同，說明此處的日志在存儲時確實發(fā)生了分片現(xiàn)象(即情況(c))，只能根據(jù)GGA或者GLL語句的格式提取地理信息。

3.2 數(shù)據(jù)重組

在經(jīng)過數(shù)據(jù)預(yù)處理之后，存儲鏡像中的數(shù)據(jù)塊的分類結(jié)果可以用圖7表示。首先可以根據(jù)數(shù)據(jù)塊是否包含特殊字節(jié)序列特征分成兩類：有效數(shù)據(jù)塊和無效數(shù)據(jù)塊。接著，再根據(jù)數(shù)據(jù)塊能否提取時間信息分為兩類：帶時間信息(圖6中的(a)和(b))和不帶時間信息(圖6中的(c))。為了方便表述，我們用List1表示存儲所有帶時間信息的數(shù)據(jù)塊，List2表示存儲不帶時間信息的數(shù)據(jù)塊。

因為NMEA日志的內(nèi)容是隨時間動態(tài)添加的，每次都會在文件的末尾追加新的NMEA記錄。所以，同屬于一個日志的數(shù)據(jù)塊的前后順序應(yīng)該就是記錄的時間先后順序。因此簡單來看，鏡像中失序的數(shù)據(jù)塊可以根據(jù)時間作為線索進行重新排序。但是根據(jù)數(shù)據(jù)預(yù)處理的結(jié)果可知，還有相當(dāng)一部分存儲在List2中的數(shù)據(jù)塊是沒有時間信息的。因此，僅對帶時間信息數(shù)據(jù)塊進行時間排序所得到的恢復(fù)結(jié)果是不完整的，還需要一個合并算法將List2中的數(shù)據(jù)塊合并到List1中。

圖7 鏡像數(shù)據(jù)塊分類結(jié)果

3.2.1 判別器

為了能夠判別兩個數(shù)據(jù)塊能否進行合并，我們根據(jù)軌跡數(shù)據(jù)在時間和地理上的局部連續(xù)性以及NMEA數(shù)據(jù)的結(jié)構(gòu)特征設(shè)計了一個判別器，主要由四個約束條件構(gòu)成。首先嘗試合并兩個數(shù)據(jù)塊，并提取出分界處拼湊的語句。假如該拼湊得到的語句同時滿足這四個約束條件，說明這兩個數(shù)據(jù)塊很可能是邏輯相鄰的，因此可以合并。其中四個約束條件分別為：

(1) 正則表達式 NMEA 0183協(xié)議規(guī)定了每一類語句的特定格式，所以可以據(jù)此設(shè)計相應(yīng)的正則表達式來過濾無法匹配的拼湊語句。

(2) 校驗和 每一類語句的最后一個字段都是校驗和，所以可以根據(jù)相應(yīng)的計算公式算出校驗和并與語句末尾的校驗和字段進行比較，相同則可以通過。

(3) 地理信息 由于在短時間內(nèi)車輛的移動距離是有限的，所以相鄰數(shù)據(jù)塊的地理位置坐標(biāo)應(yīng)該是連續(xù)而非跨越性的。

(4) 時間信息 由于GPS設(shè)備每秒鐘會在日志最后寫入新的數(shù)據(jù)，所以相鄰數(shù)據(jù)塊的時間信息應(yīng)該是連續(xù)的。

3.2.2 重組算法

根據(jù)判別器，我們可以判斷List2中不帶時間信息的數(shù)據(jù)塊是否可以與List1中的帶時間信息的數(shù)據(jù)塊進行合并。重組算法就是根據(jù)判別器，對所有的數(shù)據(jù)塊不斷進行合并最終重新組裝成新的日志。

重組算法

教師可以綜合運用多種音樂教學(xué)方法，將“感受美”貫穿于教學(xué)中，通過旋律唱游引導(dǎo)兒童感知音樂的旋律之美；通過肢體律動引導(dǎo)兒童感知音樂節(jié)奏之美；通過音樂游戲、音樂故事引導(dǎo)兒童感知鋼琴音色之美；通過音樂聯(lián)想引導(dǎo)兒童感知樂曲意境之美。

Input: List1, List2

Output: List1

1 sort List1chronologically;

2 count = List1.count + List2.count + 1;

3 while(count > List1.count + List2.count) {

4 merge clusters from List1based on discriminator;

5 insert cluster from List2into List1based on discriminator;

6 count = List1.count + List2.count;

7 }

8 drop clusters from List2;

9 return List1;

根據(jù)重組算法可知，由于List1和List2中的數(shù)據(jù)塊沒有對應(yīng)關(guān)系，我們只能采用暴力的方式對每一種合并的可能都進行嘗試。然而，暴力嘗試的復(fù)雜度為O(n2)，所以當(dāng)數(shù)據(jù)塊的數(shù)量大到一定規(guī)模時，時間開銷將會非常大。為此，我們對該過程進行了優(yōu)化。

首先，List1中的數(shù)據(jù)塊可以先按時間進行排序。然后，在每一輪的暴力合并迭代之前，可以先將List1中的數(shù)據(jù)塊進行合并。因為List1中的數(shù)據(jù)塊是有序的，所以合并只在前后相鄰的數(shù)據(jù)塊之間進行嘗試，時間復(fù)雜度也因此變成了O(n)。而List1在經(jīng)過一輪的合并操作之后，其中帶時間信息的數(shù)據(jù)塊數(shù)量將會大大減少，但是單個數(shù)據(jù)塊的大小卻因合并而逐漸變大。所以，這一步操作將會大大減少List1和List2暴力嘗試合并的機會，所花的時間開銷也將因此減少。最后，直到某一輪迭代結(jié)束時，數(shù)據(jù)塊數(shù)量之和沒有再減少說明所有的數(shù)據(jù)塊已經(jīng)無法再進一步合并，此時List2中剩余的數(shù)據(jù)塊也應(yīng)該被舍棄。

3.2.3 日志提取

經(jīng)過上一步的重組算法，所有的數(shù)據(jù)塊已經(jīng)被合并成一段段的軌跡數(shù)據(jù)存儲在List1中?？紤]到GPS設(shè)備是按軌跡的日期來命名日志文件的，也就是說同一天的軌跡數(shù)據(jù)保存在同一個日志文件中。所以，最后我們將List1中的數(shù)據(jù)塊按照日期進行分類，將同一天的數(shù)據(jù)塊保存到同一個新文件中，并以當(dāng)天的日期作為新文件的文件名。

至此，NMEA日志的恢復(fù)算法已經(jīng)完成，鏡像中所有屬于NMEA日志的數(shù)據(jù)都將會被提取并保存成新的日志文件。

3.3 日志解析

在2.2節(jié)中，我們詳細(xì)地解釋了一個NMEA日志可以看成是一些帶時間信息的軌跡點的集合。因此，只要根據(jù)NMEA 0183協(xié)議的相應(yīng)格式，將NMEA日志中所有的RMC語句進行解析，就可以得到相應(yīng)的時間、地理信息。最后再按照時間順序?qū)⑦@些軌跡點排序就能重構(gòu)出相應(yīng)的行車軌跡。除此之外，我們還調(diào)用了百度地圖API，將這些行車軌跡進行可視化顯示。

4 實驗與結(jié)果

為了驗證本文提出的NMEA日志恢復(fù)算法的有效性，采用C#語言實現(xiàn)了一個GPSDroid可視化系統(tǒng)，進行相關(guān)的實驗驗證。為了保證實驗的公平性，在相同的實驗條件下，我們將選取EnCase作為傳統(tǒng)恢復(fù)方法的代表，對比兩種恢復(fù)方法的恢復(fù)效果。

由于沒有公開的GPS設(shè)備數(shù)據(jù)鏡像集，我們最終選擇一款Eroda HD-X10品牌的便攜式導(dǎo)航設(shè)備作為數(shù)據(jù)來源。由于該設(shè)備設(shè)有SD卡槽，我們在其SD卡(存儲容量約為14.8 GB)中一共發(fā)現(xiàn)359個NMEA日志，占據(jù)339 MB大小空間。

4.1 實驗一：完整鏡像的恢復(fù)

在該實驗中，我們將模擬典型的取證場景，即獲得的GPS存儲鏡像是完整的，其系統(tǒng)元信息仍然存在并且可以使用。

首先，我們使用文件刪除的方法刪除SD卡中所有的NMEA日志文件。然后再使用WinHex工具[18]制作一份此時的SD卡鏡像文件。最后再分別使用EnCase和GPSDroid對該鏡像進行恢復(fù)。圖8為GPSDroid從鏡像中恢復(fù)出的一條軌跡。

圖8 GPSDroid恢復(fù)出行車軌跡

為了量化恢復(fù)的效果，我們使用以下等式來計算恢復(fù)結(jié)果的準(zhǔn)確率和召回率：

P(Precision)=A/(A+B)×100%

(3)

R(Recall)=A/(A+C)×100%

(4)

其中，A代表恢復(fù)的日志中確實屬于原日志的數(shù)據(jù)塊(512 B為單位)數(shù)量；B代表恢復(fù)的日志中不屬于原日志的數(shù)據(jù)塊數(shù)量；C代表恢復(fù)的日志中沒有恢復(fù)出屬于原日志的數(shù)據(jù)塊數(shù)量。

實驗一的恢復(fù)對比結(jié)果如表1所示，結(jié)果表明在系統(tǒng)元信息存在并且可用的前提下，EnCase和GPSDroid均能成功恢復(fù)出日志。相比之下，GPSDroid恢復(fù)的準(zhǔn)確率和召回率仍存在一點瑕疵，而且比EnCase還多恢復(fù)兩個日志。為此，我們仔細(xì)地觀察了多出的兩個日志，發(fā)現(xiàn)這兩個文件都是一個512 B的數(shù)據(jù)塊。出錯的原因在于這些數(shù)據(jù)塊中RMC語句的時間字段值發(fā)生異常，其時間信息并不在這359個日志所在的時間范圍內(nèi)。我們猜測這可能是數(shù)據(jù)在衛(wèi)星和GPS通信的過程中發(fā)生了錯誤。不過，這類噪點數(shù)據(jù)在最后解析日志數(shù)據(jù)的時候應(yīng)該被舍棄，所以并不會影響最終的軌跡呈現(xiàn)效果。

表1 實驗一恢復(fù)結(jié)果對比

除此之外，我們還發(fā)現(xiàn)GPSDroid恢復(fù)所消耗的時間要大于EnCase。這是因為EnCase是基于元信息恢復(fù)的，所以只需解析鏡像中的系統(tǒng)元信息數(shù)據(jù)部分即可。而GPSDroid需要掃描完整個存儲鏡像才能確保不會遺漏屬于NMEA日志的數(shù)據(jù)塊。在取證調(diào)查當(dāng)中，考慮到鏡像大小為14.8 GB，我們的恢復(fù)算法所消耗的時間仍然是可以接受的。

4.2 實驗二：元信息不可用鏡像的恢復(fù)

在這個實驗中，我們將設(shè)計對比實驗來證明在系統(tǒng)元信息不可用的情況下，GPSDroid仍然能夠成功恢復(fù)出GPS設(shè)備上的行車軌跡，而EnCase則不能。

首先，我們拷貝一份實驗一中的完整鏡像，然后通過編寫python腳本以512 B大小為單位，將拷貝得到的鏡像分割成多份，并將其整個打亂。經(jīng)過處理后，由于鏡像中所有的數(shù)據(jù)塊都被打亂了，所以其系統(tǒng)元信息已經(jīng)不可使用。與此同時，考慮到分片文件是文件雕復(fù)的一個技術(shù)難題，此時的鏡像文件也是分片最嚴(yán)重的情形。雖然現(xiàn)實生活場景中不可能發(fā)生這類情況，但是如果GPSDroid能在系統(tǒng)元信息不可用，且文件分片最嚴(yán)重的情況下重構(gòu)出NMEA日志，那么說明其他的情況下GPSDroid同樣也能處理。

恢復(fù)的對比結(jié)果如表2所示。很顯然，EnCase在系統(tǒng)元信息不可用的情況下恢復(fù)失敗，而GPSDroid恢復(fù)的準(zhǔn)確率和召回率仍能保持在99%以上。

表2 實驗二恢復(fù)結(jié)果對比

這說明本文提出的恢復(fù)算法不依賴于系統(tǒng)元信息，而且能夠有效地解決分片文件的恢復(fù)問題。需要注意的是，相比較于實驗一中GPSDroid恢復(fù)所消耗的時間，實驗二多了將近5分鐘。這是因為對鏡像的分片亂序操作破壞了日志文件原有的組織結(jié)構(gòu)，許多本來帶時間信息的數(shù)據(jù)塊都由于分片原因而丟失了時間信息，使得List2中不帶時間信息的數(shù)據(jù)塊數(shù)量大大增加。而在數(shù)據(jù)重組的過程中，由于List1和List2中的數(shù)據(jù)塊所需要暴力嘗試的合并次數(shù)增加，最終所需的恢復(fù)時間因此也變大了。

4.3 實驗三：日志被部分覆寫的恢復(fù)

考慮到數(shù)據(jù)覆寫也是磁盤上經(jīng)常發(fā)生的現(xiàn)象之一，在這個實驗中，我們將測試NMEA日志在被刪除后，其中部分?jǐn)?shù)據(jù)被覆寫的情況下GPSDroid的恢復(fù)效果。需要注意的是，被刪除文件在發(fā)生部分覆寫時，說明其相應(yīng)的系統(tǒng)元信息資源已經(jīng)被重新分配給其他新的文件。所以在這種情況下，EnCase這種傳統(tǒng)恢復(fù)方法是肯定失敗的。

具體地，我們先拷貝5份實驗一中的完整鏡像。接著，我們編寫python腳本，每次讀入512字節(jié)的數(shù)據(jù)塊，如果這個數(shù)據(jù)塊是屬于NMEA日志的，則每次生成一個0到1的隨機數(shù)。如果該隨機數(shù)小于一個rate值，則用512個隨機字節(jié)覆蓋掉原數(shù)據(jù)塊。其中，rate值分別取值為0.05、0.1、0.15、0.2、0.25。這樣一來，我們就得到了5個不同覆寫率的鏡像集，其中rate就是該鏡像的覆寫率。為了進一步加大恢復(fù)的難度，我們也對這5個鏡像分別進行512 B的分片打亂處理，最后再用GPSDroid對這5個鏡像分別進行恢復(fù)操作。

恢復(fù)結(jié)果如圖9所示，恢復(fù)的準(zhǔn)確率一直沒有受到影響，這說明GPSDroid并不會誤讀不屬于日志的數(shù)據(jù)塊。而召回率的降低則是因為被覆寫的數(shù)據(jù)塊由于被隨機數(shù)據(jù)填充而導(dǎo)致無法再被GPSDroid識別。

圖9 不同覆寫率下的GPSDroid恢復(fù)效果

不過，從圖中可以發(fā)現(xiàn)召回率的值加上其對應(yīng)的覆寫率的值始終約等于100%，這說明GPSDroid已經(jīng)將日志中仍未被覆寫的數(shù)據(jù)塊都恢復(fù)出來，相比較于傳統(tǒng)的恢復(fù)方法，已經(jīng)將數(shù)據(jù)覆寫所造成的損失降到了最低。

4.4 實驗四：不同簇大小鏡像的恢復(fù)

在該實驗中，我們將測試本文提出的算法對簇大小的兼容性。由于不同文件系統(tǒng)的簇大小有所不同，所以在系統(tǒng)元信息不可用的情況下，恢復(fù)算法對簇大小的兼容性顯得非常重要。

具體地，我們先拷貝4份實驗一中的完整鏡像(該SD卡的簇大小是默認(rèn)值4 KB)，然后再用python腳本，對四個鏡像分別按512 B、1 KB、2 KB、4 KB大小進行分片打亂處理。這樣我們就模擬出了四個簇大小分別為512 B、1 KB、2 KB和4 KB的鏡像，而且鏡像中的數(shù)據(jù)內(nèi)容是按簇完全打亂的。最后，我們再用GPSDroid分別進行恢復(fù)。

恢復(fù)結(jié)果如表3所示，除了恢復(fù)時間不同之外，恢復(fù)結(jié)果的準(zhǔn)確率和召回率完全一致，這說明本文提出的恢復(fù)算法具有較好的兼容性，可以適用于各種簇大小的文件系統(tǒng)。

表3 實驗四恢復(fù)結(jié)果對比

值得注意的是，當(dāng)簇大小是512 B時，所消耗的時間是最多的。因為當(dāng)簇大于512 B時，每個簇都將至少包含兩條記錄。所以在數(shù)據(jù)預(yù)處理的時候，可以保證每個數(shù)據(jù)塊都是有時間信息的。因此在重組算法過程中，暴力合并嘗試的機會幾乎沒有，恢復(fù)所消耗的時間自然也就少了。

5 結(jié) 語

針對GPS設(shè)備中被刪除軌跡的恢復(fù)問題，由于傳統(tǒng)恢復(fù)方法受限于系統(tǒng)元信息，本文利用文件雕復(fù)的思想，提出一種基于NMEA 0183的GPS設(shè)備軌跡恢復(fù)方法并據(jù)此實現(xiàn)了GPSDroid系統(tǒng)。實驗結(jié)果表明，根據(jù)軌跡數(shù)據(jù)在時間和地理上的局部連續(xù)性以及NMEA數(shù)據(jù)的其他一些結(jié)構(gòu)特征，GPSDroid可以在數(shù)據(jù)鏡像完整、系統(tǒng)元信息不可用、日志文件高度分片、日志數(shù)據(jù)部分覆寫和不同簇大小的鏡像等多種應(yīng)用場景下成功恢復(fù)出行車軌跡，且準(zhǔn)確率和召回率均能保持在99%以上。然而，雖然GPSDroid能幫助取證人員從導(dǎo)航中恢復(fù)出行車軌跡，但是仍然無法保證日志數(shù)據(jù)是否有被不法分子所篡改過。因此，接下來主要是根據(jù)歷史軌跡的連續(xù)性、時間戳等重要特征開展有關(guān)反取證檢測的研究工作。除此之外，考慮多線程或分布式的方式加快鏡像掃描和解析的過程，進一步提升GPSDroid的工作效率。

[1] 錢德俊,張哲,胡晨.NMEA0183協(xié)議解析[J].電子器件,2007,30(2):356-359.

[2] Eijk O V,Roeloffs M.Forensic acquisition and analysis of the Random Access Memory of TomTom GPS navigation systems[J].Digital Investigation,2010,6(3-4):179-188.

[3] Sousa J P C D,Gondim J J C.Extraction and Analysis of Volatile Memory in Android Systems:An Approach Focused on Trajectory Reconstruction Based on NMEA 0183 Standard[C]//International Conference on Availability,Reliability and Security.IEEE Computer Society,2016:328-337.

[4] Cusack B,Simms M.Evidential recovery from GPS devices[J].Journal of Applied Computing & Information Technology,2011.

[5] 李衛(wèi)衛(wèi). 基于EnCase系統(tǒng)的計算機取證分析[J].吉林師范大學(xué)學(xué)報(自然科學(xué)版),2011,32(2):110-113.

[6] Pal A,Memon N.The evolution of file carving[J].IEEE Signal Processing Magazine,2009,26(2):59-71.

[7] Iii G G R,Roussev V.Scalpel:A Frugal,High Performance File Carver[C]//Refereed Proceedings of the Digital Forensic Research Workshop,DFRWS 2005,Astor Crowne Plaza,New Orleans,Louisiana,Usa,August.DBLP,2005.

[8] Cohen M I.Advanced carving techniques[J].Digital Investigation,2007,4(3-4):119-128.

[9] Xu M,Huang L,Zhang H,et al.Recovery method for JPEG file fragments with missing headers[J].Journal of Image & Graphics,2013,18(1):24-35.

[10] Uzun E,Sencar H T.Carving Orphaned JPEG File Fragments[J].IEEE Transactions on Information Forensics & Security,2015,10(8):1549-1563.

[11] Memon N,Pal A.Automated reassembly of file fragmented images using greedy algorithms[J].IEEE Transactions on Image Processing A Publication of the IEEE Signal Processing Society,2006,15(2):385-93.

[12] Na G H,Shim K S,Moon K W,et al.Frame-Based Recovery of Corrupted Video Files Using Video Codec Specifications[J].IEEE Transactions on Image Processing A Publication of the IEEE Signal Processing Society,2013,23(2):517-26.

[13] Yannikos Y,Ashraf N,Steinebach M,et al.Automating Video File Carving and Content Identification[J].Ifip Advances in Information & Communication Technology,2013,410:195-212.

[14] Poisel R,Tjoa S,Tavolato P.Advanced File Carving Approaches for Multimedia Files[C]//IEEE,International Conference on Computational Science and Engineering.IEEE,2011:1558-1565.

[15] Garfinkel S L.Carving contiguous and fragmented files with fast object validation[J].Digital Investigation the International Journal of Digital Forensics & Incident Response,2007,4:2-12.

[16] Karresand M,Shahmehri N.Oscar—File Type Identification of Binary Data in Disk Clusters and RAM Pages[M]//Security and Privacy in Dynamic Environments.Springer US,2006:413-424.

[17] Veenman C J.Statistical Disk Cluster Classification for File Carving[C]//International Symposium on Information Assurance and Security.DBLP,2007:393-398.

[18] 吳琪.基于Winhex的數(shù)據(jù)恢復(fù)技術(shù)在計算機取證中的應(yīng)用[J].凈月學(xué)刊,2014(4):78-81.

APPROACHOFTRAJECTORYRECOVERYFROMGPSDEVICESBASEDONNMEA0183

Shi Kai Xu Ming Xu Jian Zheng Ning

(SchoolofComputerScienceandTechnology,HangzhouDianziUniversity,Hangzhou310018,Zhejiang,China)

For the problem of trajectory recovery from GPS devices, since traditional recovery method relies on system metadata, it will be failed if the metadata is damaged, unreadable or reallocated. An approach of trajectory recovery from GPS devices based on NMEA 0183 protocol is proposed according to the idea of file carving, which can successfully recover the track log data under the condition that metadata is unavailable. At first, all the data blocks belonging to the NMEA log were pinpointed by using the characteristics of track data. Then, a discriminator was designed according to the time and space continuity of log data and some structural characteristics. The obtained data blocks were reconstructed into new logs by leveraging a reassembly algorithm. Finally, the deleted trajectories were reconstructed by analyzing the recovered logs according to the NMEA formats. The experimental results show that the recovery rate can be maintained above 99% in the cases of complete forensic image, unavailable metadata image, extremely fragmented image and data overwriting. In addition, it is also compatible with various file systems of different cluster sizes.

GPS devices NMEA 0183 protocol Trajectory reconstruction File carving

2017-01-24。國家自然科學(xué)基金項目(61070212，61572165)；浙江省自然科學(xué)基金重點項目(LZ15F020003)。石凱，碩士，主研領(lǐng)域：數(shù)據(jù)恢復(fù)。徐明，教授。徐建，教授。鄭寧，研究員。

TP309.3

A

10.3969/j.issn.1000-386x.2017.12.003