石 凱 徐 明 徐 建 鄭 寧

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

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

石 凱 徐 明 徐 建 鄭 寧

(杭州電子科技大學(xué)計(jì)算機(jī)學(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ù)在時(shí)間和空間上的局部連續(xù)性以及日志的結(jié)構(gòu)特征設(shè)計(jì)一個(gè)判別器，對所有已定位的數(shù)據(jù)塊使用重組算法恢復(fù)出日志。最后再根據(jù)相應(yīng)的格式對恢復(fù)出的日志進(jìn)行解析，重構(gòu)出被刪除的行車軌跡。實(shí)驗(yàn)結(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ī)劃等多種實(shí)用功能，它在人們生活中的應(yīng)用變得越來越廣泛。與此同時(shí)，由于GPS設(shè)備使用量的快速增長，其本身攜帶的數(shù)據(jù)(例如：時(shí)間、地點(diǎn)、速度等信息)也變得愈發(fā)重要。尤其是在數(shù)字調(diào)查取證領(lǐng)域中，由于行車軌跡可以證明嫌疑人在什么時(shí)間、什么地點(diǎn)出現(xiàn)過，因此GPS設(shè)備上行車軌跡的恢復(fù)是一個(gè)十分重要的問題。

值得注意的是，行車軌跡主要由時(shí)間信息和地理信息這兩個(gè)關(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ī)定的特定格式進(jìn)行解析并重構(gòu)出行車軌跡。然而，假如嫌疑人事先刪除了GPS設(shè)備上的NMEA日志，這無疑將進(jìn)一步加大取證人員的恢復(fù)難度。

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

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

1 相關(guān)工作

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

除了對GPS設(shè)備的內(nèi)存進(jìn)行研究以外，文獻(xiàn)[4]的作者對Navman品牌系列的GPS設(shè)備中的非易失性閃存也進(jìn)行了探索。該作者利用取證工具EnCase[5]在提取出的閃存鏡像中恢復(fù)出許多NMEA日志，并對其進(jìn)行解析生成相應(yīng)的分析報(bào)告。然而，由于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ù)簇來存儲一個(gè)文件時(shí)，該文件會被分成多段存儲在磁盤上不同的物理位置。這種情況下，早期的頭/尾雕復(fù)方法所恢復(fù)的文件很可能會因?yàn)閵A雜其他的臟數(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è)計(jì)了一個(gè)判別數(shù)據(jù)塊能否合并的判別器和一個(gè)數(shù)據(jù)重組算法，對得到的數(shù)據(jù)塊進(jìn)行合并和重組操作，有效地解決了分片日志的恢復(fù)問題。最后對恢復(fù)出的日志進(jìn)行解析，將重構(gòu)出的行車軌跡通過百度地圖可視化顯示。

2 NMEA 0183協(xié)議

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

2.1 NMEA 0183介紹

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

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

圖1 NMEA日志

圖2 RMC語句格式解析

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

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

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

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

S={r1,r2,…,rn}

(1)

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

(2)

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

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

3 恢復(fù)算法

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

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

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

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

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

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

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

3.1.1 掃描步長

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

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

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

3.1.2 特征選取

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

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

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

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

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

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

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

3.2.1 判別器

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

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

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

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

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

3.2.2 重組算法

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

重組算法

教師可以綜合運(yùn)用多種音樂教學(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)系，我們只能采用暴力的方式對每一種合并的可能都進(jìn)行嘗試。然而，暴力嘗試的復(fù)雜度為O(n2)，所以當(dāng)數(shù)據(jù)塊的數(shù)量大到一定規(guī)模時(shí)，時(shí)間開銷將會非常大。為此，我們對該過程進(jìn)行了優(yōu)化。

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

3.2.3 日志提取

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

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

3.3 日志解析

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

4 實(shí)驗(yàn)與結(jié)果

為了驗(yàn)證本文提出的NMEA日志恢復(fù)算法的有效性，采用C#語言實(shí)現(xiàn)了一個(gè)GPSDroid可視化系統(tǒng)，進(jìn)行相關(guān)的實(shí)驗(yàn)驗(yàn)證。為了保證實(shí)驗(yàn)的公平性，在相同的實(shí)驗(yà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個(gè)NMEA日志，占據(jù)339 MB大小空間。

4.1 實(shí)驗(yàn)一：完整鏡像的恢復(fù)

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

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

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

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

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

(3)

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

(4)

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

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

表1 實(shí)驗(yàn)一恢復(fù)結(jié)果對比

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

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

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

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

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

表2 實(shí)驗(yàn)二恢復(fù)結(jié)果對比

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

4.3 實(shí)驗(yàn)三：日志被部分覆寫的恢復(fù)

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

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

恢復(fù)結(jié)果如圖9所示，恢復(fù)的準(zhǔn)確率一直沒有受到影響，這說明GPSDroid并不會誤讀不屬于日志的數(shù)據(jù)塊。而召回率的降低則是因?yàn)楸桓矊懙臄?shù)據(jù)塊由于被隨機(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 實(shí)驗(yàn)四：不同簇大小鏡像的恢復(fù)

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

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

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

表3 實(shí)驗(yàn)四恢復(fù)結(jié)果對比

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

5 結(jié) 語

針對GPS設(shè)備中被刪除軌跡的恢復(fù)問題，由于傳統(tǒng)恢復(fù)方法受限于系統(tǒng)元信息，本文利用文件雕復(fù)的思想，提出一種基于NMEA 0183的GPS設(shè)備軌跡恢復(fù)方法并據(jù)此實(shí)現(xiàn)了GPSDroid系統(tǒng)。實(shí)驗(yàn)結(jié)果表明，根據(jù)軌跡數(shù)據(jù)在時(shí)間和地理上的局部連續(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ù)性、時(shí)間戳等重要特征開展有關(guān)反取證檢測的研究工作。除此之外，考慮多線程或分布式的方式加快鏡像掃描和解析的過程，進(jì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ì)算機(jī)取證分析[J].吉林師范大學(xué)學(xué)報(bào)(自然科學(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ù)在計(jì)算機(jī)取證中的應(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é)基金項(xiàng)目(61070212，61572165)；浙江省自然科學(xué)基金重點(diǎn)項(xiàng)目(LZ15F020003)。石凱，碩士，主研領(lǐng)域：數(shù)據(jù)恢復(fù)。徐明，教授。徐建，教授。鄭寧，研究員。

TP309.3

A

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