基于NMEA 0183的GPS设备轨迹恢复方法

石 凯 徐 明 徐 建 郑 宁

(杭州电子科技大学计算机学院 浙江 杭州 310018)

基于NMEA0183的GPS设备轨迹恢复方法

石 凯 徐 明 徐 建 郑 宁

(杭州电子科技大学计算机学院 浙江 杭州 310018)

针对GPS设备的轨迹恢复问题，由于传统的文件恢复方法依赖于系统元信息，一旦元信息受损、不可读或重新分配等原因就会恢复失败。借助文件雕复的思想提出一种基于NMEA 0183协议的GPS设备轨迹恢复方法，可以在系统元信息不可用的前提下恢复出GPS设备上的轨迹日志数据。首先利用轨迹数据的特征从镜像中定位到所有属于NMEA日志的数据块。再根据日志数据在时间和空间上的局部连续性以及日志的结构特征设计一个判别器，对所有已定位的数据块使用重组算法恢复出日志。最后再根据相应的格式对恢复出的日志进行解析，重构出被删除的行车轨迹。实验结果表明，在数据镜像完整、系统元信息不可用、日志文件高度分片、日志数据部分覆写的情况下恢复率能够保持在99%以上，并且能够兼容不同簇大小的文件系统。

GPS设备 NMEA 0183协议 轨迹恢复 文件雕复

0 引 言

由于GPS导航设备能够提供GPS定位、方位导航和出行路线规划等多种实用功能，它在人们生活中的应用变得越来越广泛。与此同时，由于GPS设备使用量的快速增长，其本身携带的数据(例如：时间、地点、速度等信息)也变得愈发重要。尤其是在数字调查取证领域中，由于行车轨迹可以证明嫌疑人在什么时间、什么地点出现过，因此GPS设备上行车轨迹的恢复是一个十分重要的问题。

值得注意的是，行车轨迹主要由时间信息和地理信息这两个关键因素构成。而这些数据是在GPS接收器和卫星之间按照NMEA 0183协议[1]通信所产生的，部分GPS设备会将该数据以NMEA日志的形式保存下来。因此理论上来说，假如能得到GPS设备上的NMEA日志，就可以按照协议规定的特定格式进行解析并重构出行车轨迹。然而，假如嫌疑人事先删除了GPS设备上的NMEA日志，这无疑将进一步加大取证人员的恢复难度。

为了能够从GPS设备上恢复出被删除的NMEA日志，取证人员可以采用传统的文件恢复方法进行恢复。因为文件删除操作并不会真正擦除文件的数据部分，而仅是将相应的文件系统元信息部分作了标记，表示可用。所以传统恢复方法仍然可以根据元信息定位到被删除文件的数据部分并将其恢复。但是，一旦元信息受损、不可读或被重新分配等多种原因，传统恢复方法就将无法使用。例如，被删除文件的数据发生部分覆写时，其系统元信息已被重新分配给新的文件，根据传统恢复方法的原理，该文件中仍未被覆写的数据部分是无法恢复的。又如一个破损的硬盘，由于其系统元信息受损，传统恢复方法也是无法恢复的。

因此，鉴于NMEA日志对行车轨迹重构的重要性以及传统恢复方法的局限性，本文提出一种不依赖于系统元信息的NMEA日志恢复方法，并根据恢复算法实现了GPSDroid系统，成功重构出GPS设备中的行车轨迹，从实践的角度说明方法的可行性和有效性。

1 相关工作

NMEA 0183协议是一套被广泛用于GPS设备传输数据的通信协议。因为GPS设备都遵守该协议来传输数据，所以可以推测在GPS设备运行时，其内存中应该存在大量的NMEA数据。例如，文献[2]的作者在TomTom品牌的GPS设备内存中发现了大量的NMEA数据。相似地，文献[3]的作者发现配备GPS模块的Android手机设备同样也使用该协议来传输数据，并根据内存中发现的NMEA数据成功重构出行车轨迹。因此，这也充分说明了NMEA 0183协议使用的广泛性和普遍性以及对轨迹重构的重要性。

除了对GPS设备的内存进行研究以外，文献[4]的作者对Navman品牌系列的GPS设备中的非易失性闪存也进行了探索。该作者利用取证工具EnCase[5]在提取出的闪存镜像中恢复出许多NMEA日志，并对其进行解析生成相应的分析报告。然而，由于EnCase的恢复原理是基于系统元信息的，当元信息受损、不可读或被重新分配的情况下，这种恢复方法就会失效。

在这种情况下，文件雕复技术[6]得到越来越多研究人员的重视。这是一种不依赖于系统元信息，根据文件自身结构特征来重新组织磁盘数据的恢复方法。

早期的文件雕复方法比较简单，主要是利用文件的头尾特殊字节特征来定位镜像中文件所处的物理位置，然后再提取出头尾之间的数据部分作为恢复的文件[7-8]。然而，随着文件在磁盘上的存储越来越复杂，很有可能发生文件分片的现象。文件分片是指由于文件系统无法提供足够的连续簇来存储一个文件时，该文件会被分成多段存储在磁盘上不同的物理位置。这种情况下，早期的头/尾雕复方法所恢复的文件很可能会因为夹杂其他的脏数据而导致恢复失败。因此，分片文件的恢复问题也一直是文件雕复中的技术难题。一般而言，要想成功地恢复分片文件，需要更多地挖掘特定文件类型本身的数据特性和其内部的结构特征。例如，图片雕复[9-11]和视频雕复[12-13]等许多研究工作均是利用图片和视频自身的内容特征和文件结构来重新组织磁盘上的文件分片数据的。

为了解决NMEA日志的恢复问题，本文将采用文件雕复的思想，在不依赖于系统元信息的前提下恢复出日志的内容。通过观察和分析NMEA 0183协议的格式以及日志的内部结构，能够从GPS设备的存储镜像中定位到所有属于NMEA日志的数据块，并设计了一个判别数据块能否合并的判别器和一个数据重组算法，对得到的数据块进行合并和重组操作，有效地解决了分片日志的恢复问题。最后对恢复出的日志进行解析，将重构出的行车轨迹通过百度地图可视化显示。

2 NMEA 0183协议

由于本文的恢复算法是基于NMEA数据的特征及其内部结构进行恢复的，因此首先我们将对NMEA 0183协议进行简单的介绍。

2.1 NMEA 0183介绍

NMEA 0183协议是由美国国家海洋电子协会(National Marine Electronics Association)开发、维护并发布的一套通信标准，被用于绝大部分的GPS接收设备中[1]。它规定GPS接收器与卫星每秒进行一次通信，其数据以ASCII文本形式的“语句”表示，并且定义了多种相互独立的语句。其中，虽然NMEA定义了许多种不同类型的语句，但是兼容性最广的语句分别是：GGA、GSA、GSV、RMC、VTG和GLL。

如图1所示，这是一张真实的NMEA日志截图。图中表示两条相邻的NMEA记录，每条记录由若干不同类型的语句组成。从图中我们可以看到，语句的起始部分是该语句的类型，后面是许多个用逗号隔开的字段内容。而不同语句类型的格式和字段各不相同，需要注意的是，作为NMEA推荐的定位信息数据格式，RMC类型的语句承载了最重要的日期、时间、地理和速度等信息。图2是对RMC语句格式的详细解释，其中包含了每个字段的含义。因此，只要按照该格式进行解析，就可以提取出相应的时间、地理、速度等信息。除此之外，GGA和GLL语句也是非常重要的语句，根据它们的格式同样可以提取出相应的地理信息。

图1 NMEA日志

图2 RMC语句格式解析

2.2 对轨迹重构的重要性

在简单介绍完NMEA 0183协议之后，接下来我们将解释为什么它对GPS设备的轨迹重构有着重要的意义。如图3所示，每个NMEA日志都可以被看成由多个分片组成，而每个日志分片都会包含若干NMEA记录。其中，每条NMEA记录都会包含RMC、GGA和GLL等语句。而RMC语句又包含时间、地理、速度等信息。

图3 NMEA日志内部结构

因此，我们可以得到以下结论：

S={r1,r2,…,rn}

(1)

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

(2)

式中：S是一个记录的集合。其中r表示一条NMEA记录，每条记录都会包含日期、时间、经纬度信息。因此，我们可以把NMEA日志中的每一条记录看成是一个有时间信息的、根据地理信息对应到地图上的一个轨迹点。只要对这些轨迹点按照时间顺序进行排序，我们就可以重构出GPS设备的行车轨迹。

接下来，我们就将介绍在系统元信息不可用的前提下，我们是如何借助NMEA数据的特性和内部结构特征来解决NMEA日志的恢复问题。

3 恢复算法

在本节中，我们将介绍恢复算法的具体细节。如图4所示，恢复算法框架主要分为三个步骤：

(1) 数据预处理 在进行恢复之前，需要对GPS设备的存储镜像进行数据预处理。该步骤主要是在扫描存储镜像的过程中，根据NMEA数据的特征在镜像中定位到所有属于NMEA日志的数据块。

(2) 数据重组 这个步骤主要是对获得的数据块进行合并和重组操作。为此，我们设计了一个用于判别数据块能否合并的判别器，和一个用于数据块重组的算法，将无序的数据块重新组装成新的日志文件。

(3) 日志解析 该步骤需要将恢复得到的NMEA日志按照NMEA 0183的格式进行解析，提取出日志中所有RMC语句的时间地理信息，重构出被删除的行车轨迹，并用百度地图进行可视化显示。

图4 恢复算法框架

3.1 数据预处理

该步骤需要在扫描镜像文件的时候找出所有属于NMEA日志的数据块。然而，由于文件系统分布的复杂性，NMEA日志的数据块可能分布在镜像中的任意角落。因此，在数据预处理的过程中我们需要注意以下两个关键点：扫描步长和特征选取。

3.1.1 扫描步长

由于扫描步长的选择与磁盘中数据的存储分布息息相关，所以我们先简要介绍相关的背景知识。众所周知，磁盘的最小存储单元是扇区(512字节)，而分配文件的最小逻辑单元是簇(一个或多个扇区组成)[14]。所以，当文件系统为一个文件分配存储空间而找不到足够多的连续文件簇时，文件内容不得不先被分割成多段然后存储在磁盘的不同位置，这就是文件分片[15]。而且，由于NMEA日志的内容是随着时间动态添加的，所以在存储时特别容易发生分片的现象。但是，又因为簇是分配文件的最小逻辑单元，所以即使出现文件分片现象，其分片点也只可能发生在簇的边界处。所以，只要选取存储镜像的簇大小作为扫描步长，就可以避免分片所造成的数据切割错误。

然而，不同文件系统的簇大小并不都是一样的。由于我们的恢复算法是不基于系统元信息的，也就是说文件系统的簇大小是未知的。而且，选取不当的扫描步长将会造成数据的误读。如图5(a)所示，当镜像的簇大小是1 KB而扫描步长是4 KB时，除了有效数据A被识别外，脏数据B也会被误认为是日志的数据块。因此，为了保证算法的兼容性，我们选取最小的簇大小值(512 B)作为扫描步长。因为簇大小都是512 B的整数倍，即使一个镜像的簇大于512 B，仍然可以将这个簇看成是由多个512 B的数据块组成的。例如，如图5(b)所示，当镜像簇大小是1 KB而扫描步长是512 B时，有效数据区域A被看作是两个512 B的数据块，均可以成功被定位到，而此时的脏数据B也不会被误认为是NMEA日志的数据块。

图5 扫描步长对数据块定位的影响

3.1.2 特征选取

在确定扫描步长之后，我们还需要选取出特征，能够在扫描镜像的过程中判断某个数据块是否属于NMEA日志。根据NMEA 0183协议规范的定义，每类语句的起始部分都是特定的字节序列(例如＄GPGGA,＄GPGSA,＄GPGSV,＄GPRMC,＄GPVTG,＄GPGLL)。因此，我们可以确定每个属于NMEA日志的数据块都应该至少包含这些特殊字节序列中的一个。而且，相比较于其他的统计特征分类方法[16-17]，这种特定字节序列的搜索方法显得更加简单高效。

根据我们的实验统计观察，NMEA日志中的单条记录不会超过512 B。因此，一条NMEA记录在一个512 B的数据块中有3种分布情况。如图6所示，(a)表示一个数据块恰好包含一条完整记录；(b)表示一条记录横跨在两个相邻数据块中；(c)表示一条记录被分割成了两段，并且日志发生了分片。

图6 NMEA记录在数据块中的分布情况

这三种情况都可以根据特殊字节序列在镜像中被定位到，但是由于图6(a)中的数据块包含完整的一条记录，所以可以根据其中的RMC语句提取出相应的时间、地理信息。而对于(b)和(c)，两者都需要与相应的另一半合并才能提取出完整的记录和相应的信息。值得注意的是，根据文件存储的局部性原理，虽然可能存在文件分片现象，但是一个文件中逻辑相邻的数据块很大可能在物理存储时也是相邻的。因此理论上来说，(b)出现的概率要大于(c)。

为了能够辨别出是(b)还是(c)，我们可以根据NMEA 0183协议的另一个特征“校验和”(一条语句中＄和*之间所有ASCII字符的异或值，详见图2)来判断物理相邻的两个数据块是否在逻辑上也是相邻的。具体地，假如一个数据块无法提取时间信息，则可以先尝试将该数据块与下一个数据块进行合并操作。然后再提取出两个数据块分界处拼凑成的语句，并利用协议所定义的校验和计算方式算出该拼凑语句的校验和，与该拼凑语句末尾的校验和字段进行比较。如果两者的值是吻合的，那么说明这两个物理上相邻的数据块在逻辑上也是连续的(即情况(b))，可以按照RMC语句的格式从合并后的记录中提取出相应的时间、地理信息；如果两者的值不同，说明此处的日志在存储时确实发生了分片现象(即情况(c))，只能根据GGA或者GLL语句的格式提取地理信息。

3.2 数据重组

在经过数据预处理之后，存储镜像中的数据块的分类结果可以用图7表示。首先可以根据数据块是否包含特殊字节序列特征分成两类：有效数据块和无效数据块。接着，再根据数据块能否提取时间信息分为两类：带时间信息(图6中的(a)和(b))和不带时间信息(图6中的(c))。为了方便表述，我们用List1表示存储所有带时间信息的数据块，List2表示存储不带时间信息的数据块。

因为NMEA日志的内容是随时间动态添加的，每次都会在文件的末尾追加新的NMEA记录。所以，同属于一个日志的数据块的前后顺序应该就是记录的时间先后顺序。因此简单来看，镜像中失序的数据块可以根据时间作为线索进行重新排序。但是根据数据预处理的结果可知，还有相当一部分存储在List2中的数据块是没有时间信息的。因此，仅对带时间信息数据块进行时间排序所得到的恢复结果是不完整的，还需要一个合并算法将List2中的数据块合并到List1中。

图7 镜像数据块分类结果

3.2.1 判别器

为了能够判别两个数据块能否进行合并，我们根据轨迹数据在时间和地理上的局部连续性以及NMEA数据的结构特征设计了一个判别器，主要由四个约束条件构成。首先尝试合并两个数据块，并提取出分界处拼凑的语句。假如该拼凑得到的语句同时满足这四个约束条件，说明这两个数据块很可能是逻辑相邻的，因此可以合并。其中四个约束条件分别为：

(1) 正则表达式 NMEA 0183协议规定了每一类语句的特定格式，所以可以据此设计相应的正则表达式来过滤无法匹配的拼凑语句。

(2) 校验和 每一类语句的最后一个字段都是校验和，所以可以根据相应的计算公式算出校验和并与语句末尾的校验和字段进行比较，相同则可以通过。

(3) 地理信息 由于在短时间内车辆的移动距离是有限的，所以相邻数据块的地理位置坐标应该是连续而非跨越性的。

(4) 时间信息 由于GPS设备每秒钟会在日志最后写入新的数据，所以相邻数据块的时间信息应该是连续的。

3.2.2 重组算法

根据判别器，我们可以判断List2中不带时间信息的数据块是否可以与List1中的带时间信息的数据块进行合并。重组算法就是根据判别器，对所有的数据块不断进行合并最终重新组装成新的日志。

重组算法

教师可以综合运用多种音乐教学方法，将“感受美”贯穿于教学中，通过旋律唱游引导儿童感知音乐的旋律之美；通过肢体律动引导儿童感知音乐节奏之美；通过音乐游戏、音乐故事引导儿童感知钢琴音色之美；通过音乐联想引导儿童感知乐曲意境之美。

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;

根据重组算法可知，由于List1和List2中的数据块没有对应关系，我们只能采用暴力的方式对每一种合并的可能都进行尝试。然而，暴力尝试的复杂度为O(n2)，所以当数据块的数量大到一定规模时，时间开销将会非常大。为此，我们对该过程进行了优化。

首先，List1中的数据块可以先按时间进行排序。然后，在每一轮的暴力合并迭代之前，可以先将List1中的数据块进行合并。因为List1中的数据块是有序的，所以合并只在前后相邻的数据块之间进行尝试，时间复杂度也因此变成了O(n)。而List1在经过一轮的合并操作之后，其中带时间信息的数据块数量将会大大减少，但是单个数据块的大小却因合并而逐渐变大。所以，这一步操作将会大大减少List1和List2暴力尝试合并的机会，所花的时间开销也将因此减少。最后，直到某一轮迭代结束时，数据块数量之和没有再减少说明所有的数据块已经无法再进一步合并，此时List2中剩余的数据块也应该被舍弃。

3.2.3 日志提取

经过上一步的重组算法，所有的数据块已经被合并成一段段的轨迹数据存储在List1中。考虑到GPS设备是按轨迹的日期来命名日志文件的，也就是说同一天的轨迹数据保存在同一个日志文件中。所以，最后我们将List1中的数据块按照日期进行分类，将同一天的数据块保存到同一个新文件中，并以当天的日期作为新文件的文件名。

至此，NMEA日志的恢复算法已经完成，镜像中所有属于NMEA日志的数据都将会被提取并保存成新的日志文件。

3.3 日志解析

在2.2节中，我们详细地解释了一个NMEA日志可以看成是一些带时间信息的轨迹点的集合。因此，只要根据NMEA 0183协议的相应格式，将NMEA日志中所有的RMC语句进行解析，就可以得到相应的时间、地理信息。最后再按照时间顺序将这些轨迹点排序就能重构出相应的行车轨迹。除此之外，我们还调用了百度地图API，将这些行车轨迹进行可视化显示。

4 实验与结果

为了验证本文提出的NMEA日志恢复算法的有效性，采用C#语言实现了一个GPSDroid可视化系统，进行相关的实验验证。为了保证实验的公平性，在相同的实验条件下，我们将选取EnCase作为传统恢复方法的代表，对比两种恢复方法的恢复效果。

由于没有公开的GPS设备数据镜像集，我们最终选择一款Eroda HD-X10品牌的便携式导航设备作为数据来源。由于该设备设有SD卡槽，我们在其SD卡(存储容量约为14.8 GB)中一共发现359个NMEA日志，占据339 MB大小空间。

4.1 实验一：完整镜像的恢复

在该实验中，我们将模拟典型的取证场景，即获得的GPS存储镜像是完整的，其系统元信息仍然存在并且可以使用。

首先，我们使用文件删除的方法删除SD卡中所有的NMEA日志文件。然后再使用WinHex工具[18]制作一份此时的SD卡镜像文件。最后再分别使用EnCase和GPSDroid对该镜像进行恢复。图8为GPSDroid从镜像中恢复出的一条轨迹。

图8 GPSDroid恢复出行车轨迹

为了量化恢复的效果，我们使用以下等式来计算恢复结果的准确率和召回率：

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

(3)

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

(4)

其中，A代表恢复的日志中确实属于原日志的数据块(512 B为单位)数量；B代表恢复的日志中不属于原日志的数据块数量；C代表恢复的日志中没有恢复出属于原日志的数据块数量。

实验一的恢复对比结果如表1所示，结果表明在系统元信息存在并且可用的前提下，EnCase和GPSDroid均能成功恢复出日志。相比之下，GPSDroid恢复的准确率和召回率仍存在一点瑕疵，而且比EnCase还多恢复两个日志。为此，我们仔细地观察了多出的两个日志，发现这两个文件都是一个512 B的数据块。出错的原因在于这些数据块中RMC语句的时间字段值发生异常，其时间信息并不在这359个日志所在的时间范围内。我们猜测这可能是数据在卫星和GPS通信的过程中发生了错误。不过，这类噪点数据在最后解析日志数据的时候应该被舍弃，所以并不会影响最终的轨迹呈现效果。

表1 实验一恢复结果对比

除此之外，我们还发现GPSDroid恢复所消耗的时间要大于EnCase。这是因为EnCase是基于元信息恢复的，所以只需解析镜像中的系统元信息数据部分即可。而GPSDroid需要扫描完整个存储镜像才能确保不会遗漏属于NMEA日志的数据块。在取证调查当中，考虑到镜像大小为14.8 GB，我们的恢复算法所消耗的时间仍然是可以接受的。

4.2 实验二：元信息不可用镜像的恢复

在这个实验中，我们将设计对比实验来证明在系统元信息不可用的情况下，GPSDroid仍然能够成功恢复出GPS设备上的行车轨迹，而EnCase则不能。

首先，我们拷贝一份实验一中的完整镜像，然后通过编写python脚本以512 B大小为单位，将拷贝得到的镜像分割成多份，并将其整个打乱。经过处理后，由于镜像中所有的数据块都被打乱了，所以其系统元信息已经不可使用。与此同时，考虑到分片文件是文件雕复的一个技术难题，此时的镜像文件也是分片最严重的情形。虽然现实生活场景中不可能发生这类情况，但是如果GPSDroid能在系统元信息不可用，且文件分片最严重的情况下重构出NMEA日志，那么说明其他的情况下GPSDroid同样也能处理。

恢复的对比结果如表2所示。很显然，EnCase在系统元信息不可用的情况下恢复失败，而GPSDroid恢复的准确率和召回率仍能保持在99%以上。

表2 实验二恢复结果对比

这说明本文提出的恢复算法不依赖于系统元信息，而且能够有效地解决分片文件的恢复问题。需要注意的是，相比较于实验一中GPSDroid恢复所消耗的时间，实验二多了将近5分钟。这是因为对镜像的分片乱序操作破坏了日志文件原有的组织结构，许多本来带时间信息的数据块都由于分片原因而丢失了时间信息，使得List2中不带时间信息的数据块数量大大增加。而在数据重组的过程中，由于List1和List2中的数据块所需要暴力尝试的合并次数增加，最终所需的恢复时间因此也变大了。

4.3 实验三：日志被部分覆写的恢复

考虑到数据覆写也是磁盘上经常发生的现象之一，在这个实验中，我们将测试NMEA日志在被删除后，其中部分数据被覆写的情况下GPSDroid的恢复效果。需要注意的是，被删除文件在发生部分覆写时，说明其相应的系统元信息资源已经被重新分配给其他新的文件。所以在这种情况下，EnCase这种传统恢复方法是肯定失败的。

具体地，我们先拷贝5份实验一中的完整镜像。接着，我们编写python脚本，每次读入512字节的数据块，如果这个数据块是属于NMEA日志的，则每次生成一个0到1的随机数。如果该随机数小于一个rate值，则用512个随机字节覆盖掉原数据块。其中，rate值分别取值为0.05、0.1、0.15、0.2、0.25。这样一来，我们就得到了5个不同覆写率的镜像集，其中rate就是该镜像的覆写率。为了进一步加大恢复的难度，我们也对这5个镜像分别进行512 B的分片打乱处理，最后再用GPSDroid对这5个镜像分别进行恢复操作。

恢复结果如图9所示，恢复的准确率一直没有受到影响，这说明GPSDroid并不会误读不属于日志的数据块。而召回率的降低则是因为被覆写的数据块由于被随机数据填充而导致无法再被GPSDroid识别。

图9 不同覆写率下的GPSDroid恢复效果

不过，从图中可以发现召回率的值加上其对应的覆写率的值始终约等于100%，这说明GPSDroid已经将日志中仍未被覆写的数据块都恢复出来，相比较于传统的恢复方法，已经将数据覆写所造成的损失降到了最低。

4.4 实验四：不同簇大小镜像的恢复

在该实验中，我们将测试本文提出的算法对簇大小的兼容性。由于不同文件系统的簇大小有所不同，所以在系统元信息不可用的情况下，恢复算法对簇大小的兼容性显得非常重要。

具体地，我们先拷贝4份实验一中的完整镜像(该SD卡的簇大小是默认值4 KB)，然后再用python脚本，对四个镜像分别按512 B、1 KB、2 KB、4 KB大小进行分片打乱处理。这样我们就模拟出了四个簇大小分别为512 B、1 KB、2 KB和4 KB的镜像，而且镜像中的数据内容是按簇完全打乱的。最后，我们再用GPSDroid分别进行恢复。

恢复结果如表3所示，除了恢复时间不同之外，恢复结果的准确率和召回率完全一致，这说明本文提出的恢复算法具有较好的兼容性，可以适用于各种簇大小的文件系统。

表3 实验四恢复结果对比

值得注意的是，当簇大小是512 B时，所消耗的时间是最多的。因为当簇大于512 B时，每个簇都将至少包含两条记录。所以在数据预处理的时候，可以保证每个数据块都是有时间信息的。因此在重组算法过程中，暴力合并尝试的机会几乎没有，恢复所消耗的时间自然也就少了。

5 结 语

针对GPS设备中被删除轨迹的恢复问题，由于传统恢复方法受限于系统元信息，本文利用文件雕复的思想，提出一种基于NMEA 0183的GPS设备轨迹恢复方法并据此实现了GPSDroid系统。实验结果表明，根据轨迹数据在时间和地理上的局部连续性以及NMEA数据的其他一些结构特征，GPSDroid可以在数据镜像完整、系统元信息不可用、日志文件高度分片、日志数据部分覆写和不同簇大小的镜像等多种应用场景下成功恢复出行车轨迹，且准确率和召回率均能保持在99%以上。然而，虽然GPSDroid能帮助取证人员从导航中恢复出行车轨迹，但是仍然无法保证日志数据是否有被不法分子所篡改过。因此，接下来主要是根据历史轨迹的连续性、时间戳等重要特征开展有关反取证检测的研究工作。除此之外，考虑多线程或分布式的方式加快镜像扫描和解析的过程，进一步提升GPSDroid的工作效率。

[1] 钱德俊,张哲,胡晨.NMEA0183协议解析[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] 李卫卫. 基于EnCase系统的计算机取证分析[J].吉林师范大学学报(自然科学版),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的数据恢复技术在计算机取证中的应用[J].净月学刊,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。国家自然科学基金项目(61070212，61572165)；浙江省自然科学基金重点项目(LZ15F020003)。石凯，硕士，主研领域：数据恢复。徐明，教授。徐建，教授。郑宁，研究员。

TP309.3

A

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