基于改进Bsdiff算法的车载诊断系统远程升级系统

钱枫 易齐 祝能 王洁

关键词：汽车主动安全；车载诊断（OBD）系统；远程升级；Bsdiff算法；闪存分区；固件更新

随着车载诊断（on-boarddiagnostics，OBD）系统终端在汽车上安装的普及和固件功能的逐渐复杂，车載终端在运行的过程中，一些设计缺陷和软件漏洞逐渐暴露；同时，随着车载OBD终端国家相关法规的完善，旧的固件包已经不能满足相关法规的功能需求，升级现有的固件程序在所难免。当前的固件程序升级流程分为现场升级和全量远程升级。现场升级每次更换新固件程序需要耗费大量的时间和人力，增加了服务成本。全量远程升级需要将新版本固件包完整发送给车载OBD终端设备，这不仅让车载OBD终端设备在使用网络数据的过程中需要支付高昂的流量费用，而且在传输整个新版本固件包的过程中，必然会耗费大量时间和占用大量网络带宽，更容易由于不确定的外界环境因素导致系统崩溃。因此如何提升车载OBD终端设备远程升级固件包安装的稳定可靠性、减小固件包传输体积及提高固件包传输速率成为研究和发展的重点。

空中下载升级（overtheair，OTA）[1]是指利用无线通信技术，通过云升级技术，为联网设备进行远程管理与升级，分为固件远程升级（firmwareovertheair，FOTA）和软件远程升级（softwareovertheair，SOTA）两类。

已有大量针对远程升级的相关研究。D.Makowski等人在xTCA系统上首次尝试采用智能平台管理接口标准完成设备的固件升级[2]。Y.Kwon等提出了一种适用于无线传感器网络的升级模型[3]。高柱荣等对闪存进行了科学的分区、Bootloader程序进行了简化、终端的升级操作引入了时效性和服务器IP地址隐藏化，实现了安全、可靠的远程升级[4]。沈伟等提出了安全稳定、批量化直流充电机远程升级系统，该系统在升级文件传输的过程中不影响充电机的正常业务，同时支持断点续传和批量升级[5]。K.MAYAMA等提出了针对RTCCANopen的固件更新系统，该升级系统可以在线控制自动固件更新的整个过程[6]。

江苏大学施超、鲍可进等提出基于MTK平台和Spreadtrum平台实现Android操作系统远程升级，提出了服务器端自动制作差分升级包的方法，并采用Recovery机制和分区备份的方法来处理软件系统升级中断电的情况[7]。电子科技大学夏棋等对增量数据差分更新算法进行了一系列研究，基于二进制文件差分更新算法，提出了一种减少个人云存储系统中文件更新时传输流量的方法，同时解决了在用户云存储系统中更新策略的冲突化解问题[8]。刘洋和王剑等基于Bsdiff差分算法和FastLz77压缩算法有效地减小了固件包的大小，同时使用跳频和循环异或加密技术，提出了一种适用于LoRa通信设备的固件远程升级方法[9]。高柱荣和蒋昌茂等采用双APP程序分区方案，基于应用程序编程技术设计了燃气表终端远程升级系统，一定程度上解决了物联网燃气表终端远程升级过程中被恶意攻击、固件文件安全传输和可靠更新等问题[10]。沈伟、卫龙龙等设计了远程升级直流充电机系统并提出了升级方法，该系统及方法支持断点续传和批量升级，并稳定有效保证了充电机正常的充电业务和数据通信[11]。殷杰对Bsdiff算法进行了优化并采用混合加密算法来解决FOTA终端的时效性问题与安全性问题[12]。

远程升级技术已在各传统领域得到了广泛的应用。针对车载OBD终端设备现场升级方法服务成本高及维护难度大和全量远程升级占用较大网络带宽和性能不稳定等问题，本文设计了一种基于改进Bsdiff算法的OBD远程升级系统，首先阐述了差分算法的基本原理，并对Bsdiff算法进行了优化，然后介绍系统的基本组成，并对闪存（flashmemory，Flash）分区进行了优化设计，阐述了差分包的上传、下发步骤，最后对SpringBoot和STM32F103搭建的测试环境进行全量升级和差分升级对比试验，验证该系统相较于全量远程升级系统各方面性能指标有大幅度提升。

1算法分析

1.1Bsdiff差分算法

差分升级是指进行固件升级的时候，只对固件变更的地方进行升级，未做变更的地方保持不变。实际流程是：在开发端，以旧版本固件作为基础，对新版本固件和旧版本固件进行差分对比，生成一个补丁文件；在客户端，以旧版本固件作为基础，合并补丁文件还原新版本固件进行安装，如图1所示。

生成补丁文件的核心是使用差分算法对新旧版本固件进行差分计算。目前应用广泛的二进制文件差分算法有：Xdelta、RTPatch、Exediff、Bsdiff等算法。为了评估这些差分算法在计算补丁文件时的压缩率和性能，本文使用了参考文献[13]中的结论，该文献对比、分析了补丁文件的压缩率。本文主要列举了3种二进制文件：Agrep、gcc、Alimpse，对比分析结论见表1所示。

从表1中可以看出：对于二进制文件来说，Xdelta算法的压缩率最低，Exediff算法压缩率最高，其次Bsdiff算法压缩率最高。但是Exediff算法对运行的平台有严格要求，所以本文采用能独立于平台的Bsdiff算法实现补丁文件的制作。

Bsdiff算法[14]是较为高效的差量更新算法，由于该算法生成的patch补丁文件体积小，因此在各领域得到了广泛应用[15]。Bsdiff算法分为diff过程和patch过程，diff过程是在开发端对新版本固件与旧版本固件进行差分计算、编码和压缩，从而产生补丁文件。patch过程是在客户端以旧版本固件为基础，按照规定的解码规则还原出补丁文件并和旧版本固件进行合并，从而构建出新版本固件进行安装[16]。

Bsdiff算法首先申请两个辅助空间并创建一个空的补丁文件，然后采用快速后缀排列算法对旧版本固件的所有后缀按字典顺序进行排列得到后缀数组SA[·]，经过逆运算后得到名次数组RANK[·]，如表2所示为以AABAB为例的SA[·]和RANK[·]生成过程中下标位置变化的次数[17]。

利用旧版本固件的后缀数组和二分查找算法检索新版本固件和旧版本固件中的相似匹配区域与不匹配区域。接下来，对所有近似匹配执行相减操作并记录下近似匹配区域数据的差值和不匹配区域的内容，最后，快速打包出补丁文件。由于这些相似区域数据的差值包含大量的零值，所以可以使用bzip等压缩算法压缩该部分差值，以减少补丁文件的大小[18]。整个补丁文件包括头部区域、控制区域、差分区域和扩展区域4个部分。

Bsdiff算法在客户端对新版本固件进行恢复的过程中，首先会申请开辟2个辅助空间并创建3个并行的解压进程，并分别用于对补丁文件中的控制区域、差分区域和扩展区域进行解压。然后执行2类操作：复制操作，依据控制区域解压缩提取的控制信息，对差分区域解压缩获得的数据与旧版本固件中对应数据执行相加操作并将生成的数据块复制到指定区域；插入操作，将扩展区域解压缩获得的数据插入到指定区域。图2所示为新版本固件的恢复流程。

1.2Bsdiff算法优化

通过对Bsdiff算法流程的分析可知，Bsdiff算法生成的补丁文件差分区域数据存在大量冗余零值是目前差分算法的不足。针对该问题，本文以减小补丁文件体积及多线程分包下发为核心思想，对差分区域数据进行了去冗优化，并将补丁文件进行分包处理，采用多线程机制对车载OBD终端进行补丁下发。该方法不仅减少云平台与车载OBD终端的通信开销和数据传输时间，使数据传输更稳定；而且，在车载OBD终端节约内存开销，让其他应用程序运行更加稳定，整个系统运行速度更加流畅。

如图3所示为Bsdiff算法去零流程图。步骤如下：

步骤1：使用Bsdiff算法处理新旧版本固件，以获取补丁文件；

步骤2：移动标志指针p的位置，让其指向差分区域首地址；

步骤3：扫描差分区域，若标志指针p扫描到的是零值，则不做统计与序列编码，标志指针p直接向后移动一位；若标志指针p扫描到的是非零值，则对该段字节序列进行差值统计，并插入特征字节；

步骤4：重复步骤3直到差分区域字节数据全部编码完成，最终得到sim-diffblock；

步骤5：扫描差分文件，读取头部区域、控制区域、差分区域和扩展区域字节数据临界位置信息，并对该信息进行序列编码与存储。

对差分文件的非零值進行统计和序列编码消除了大量冗余零值，减小了差分文件的体积，有利于提高云平台与车载终端之间的数据传输速度，节省车载终端内存消耗。

云平台一般同时备案与管理数千台车载OBD终端，车载OBD终端之间宽带共享。如果每台车载OBD终端的优先级相同，多台终端设备一起连接到该云平台并请求升级差分文件，那么每个车载终端所使用的实际带宽就是云平台带宽的均分。所以，如果接入的车载终端数量较多，则每个车载终端所占用的带宽十分有限，差分文件的下载将十分的耗时，导致远程升级的效率十分低下。

为充分利用服务器网络带宽资源，提高车载OBD终端CPU的利用率和差分文件传输效率，本文采用了多线程分包传输方案，如图4所示为多线程差分文件下载流程图。步骤如下：

步骤1：车载OBD终端请求升级，并下载记录了差分包属性值的配置文件；

步骤2：车载OBD终端根据步骤1获取的差分包属性信息确定分包参数，包括各片文件大小pieceSize、总片数pieceCount及每片的pieceNumber；

步骤3：车载OBD终端创建差分文件下载任务，并携带着分包参数向云平台发送请求，以获取文件分片记录信息；

步骤4：根据步骤3读取的文件分片记录信息，车载OBD终端创建pieceCount个线程并分别与云平台连接，然后发送指定分片文件下载指令；

步骤5：车载OBD终端对pieceCount个线程进行统一管理，并记录各自片文件下载信息；

步骤6：主线程监听各子线程数据下载完成进度，如果未下载完毕继续等待步骤4，直到各线程片文件下载完成后，进行新版本固件的恢复操作。

2系统设计

本文设计的车载OBD远程升级系统由车载OBD终端、本地开发环境和FOTA云平台组成，见图5。车载OBD终端搭载ThreadX操作系统，外接安全芯片、4G联网、应用调试等模块，见图6。

本地开发环境主要负责通过DS-5开发工具进行固件代码的编写、通过msys64开发工具对固件进行编译和通过Bsdiff算法脚本制作差分包；FOTA云平台主要负责车载OBD终端设备管理、远程升级任务的管理、升级包的管理、远程升级任务的下发和升级状态与数据的监测。

2.1改进闪存分区设计

传统闪存分区方式将片内闪存划分为Bootloader引导区和用户主程序区，如图7a所示。这种划分方式需要借助片外闪存来完成远程更新操作，具体整包升级流程如下。

步骤1：下载更新包数据并保存至片外闪存；

步骤2：重启设备，进入引导程序；

步骤3：将更新包数据从片外闪存拷贝到片内主程序区；

步骤4：执行新版本程序。

通过分析可知，传统闪存分区方式不仅浪费闪存空间，而且在片内闪存和片外闪存数据交换上耗费大量时间。对此本文提出了一种动态调整分区空间的闪存分区方式，将闪存划分为6个区域，如图7b所示，分别为Bootloader引导区、fota_param区、fota_pkg区、主分区、空闲区和备份区，其中空闲区属于主分区，主要用于处理程序中的坏块问题，以提高系统运行的稳定性。fota_param分区用来存放升级时的一些重要参数信息，fota_pkg分区用来存储升级包。主分区和备份区通过一个字节的标志位来区分，本系统中0代表主分区，1代表备份区。主分区用于存放需要运行的程序。

优化后的更新操作如图8所示。具体差分升级流程如下。

步骤1：下载参数文件和差分包数据，并将其分别保存至fota_param分区和fota_pkg分区；

步骤2：合并、释放备份区和空闲区，并将其划分为一个新的备份区；

步骤3：由步骤1中的fota_param参数信息对备份区进行重新划分，并将新版本固件包数据写入刚划分好的主分区中；

步骤4：固件升级完成，重新设置主分区和备份区的标志位，加载指针跳转至主分区程序入口，执行新版本程序。

本文采用动态调整分区空间的方式来操作闪存内存空间，与传统操作闪存内存方式相比，具备以下优势：无需申请片外闪存空间，有效的节约了嵌入式设备中紧张的存储资源；主分区与备份区的交替使用，提高了闪存存储空间的利用率；避免执行传统整包升级过程中耗时的数据拷贝与数据擦除操作，提高了固件更新的效率。

2.2远程升级网络结构

在车载OBD远程升级系统中，车载终端升级程序主要任务是通过TCP协议请求连接到服务器并维持心跳，在此期间，向服务器发送固件版本对比请求、处理服务器反馈结果和其他信息数据流等。服务器应用程序的主要任务是可以同时接受多台终端设备的接入和有序地处理多台客户端的请求并及时做出有效响应。考虑到移动终端设备的唯一性和合法性，每台车载OBD终端上都会绑定唯一的IMEI编号，当车载OBD终端请求远程升级之前，首先会携带着终端设备上的IMEI编号进行备案，备案请求通过之后才允许进行远程固件升级[19，20]。这种网络拓扑结构如图9所示。

2.3远程升级流程

远程升级分为4个部分：补丁包制作、补丁包上传、补丁包下载和旧版本固件升级。远程升级流程如图10所示。

根据优化后的差分算法制作可执行文件Bsdiff.exe，使用该Bsdiff.exe差分工具对旧版本system文件和新版本system文件进行字节对比，生成最小系统差分包和非最小系统差分包2个差分文件。然后，将这两个差分文件上传到远程升级云平台中，创建设备分组并下发升级任务。升级时首先下载最小系统差分文件，下载完成后重启进入updater升级。完成最小系统的升级后重启运行的就是最新的可联网的最小系统，然后再下载非最小系统升级文件，下载完成后校验，校验通过后整个升级完成。

3实验对比分析

本文OBD车载终端设备使用ARMCortex-R5应用处理器，搭载FreeRTOS操作系统实现远程升级。使用IBMX350M4作为服务器（Intel（R）Xeon（R）CPUE5～2680v3@2.50GHz），操作系统为CentOS7.364位，采用Java开发语言配合SpringBoot后端框架编写服务接口，数据库采用MongoDB，前端页面使用Vue框架开发OTAWeb管理系统。

基于以上硬件和服务器环境分别进行优化前的差分升级、优化后的差分升级和传统的全量远程升级试验。使用本地开发環境生成从Test_V1.bin到Test_V5.bin一组测试固件包作为本次实验样本。本次实验所用的样本数据如表3所示，其中从Test_V1.bin到Test_V5.bin文件大小逐步变大，其代码差异也逐步变大。为消除网络、本地环境等随机误差，每个样本均测试30次。本文以全量远程升级和差分升级过程中压缩率和编译运行时间作为主要评价指标。

对比中压缩率定义为相较于全量远程升级，通过差分升级减少的数据编译、传输大小的程度。压缩率越大，表征差分算法性能越好，数据编译时间、传输时间、设备功耗、内存占用及网络流量占用较少。对比结果如表3所示。

从表3中Ⅰ、Ⅱ、Ⅲ组试验可以看出：当试验样本文件较小时，优化前的差分升级算法压缩率较大，最高可达68.72%。

从Ⅳ、Ⅴ组试验可以看出：当试验样本文件较大时，优化后的差分升级算法具有明显优势，压缩率可以达到82.30%，相较于优化前的差分升级算法，压缩性能提高了23.55%。本文优化后的差分算法具有良好的压缩性能。且压缩率与试验样本的文件大小呈现非线性的正相关。

由表4可知，对比全量远程升级，差分升级在编译运行时所耗时间显著减少；在试验样本文件较小时，优化前的差分升级和优化后的差分升级编译运行时间相差不大；在试验样本文件较大时，相较于优化前的差分升级，优化后的差分升级编译运行时间更短，在第Ⅴ组试验中，优化前的差分升级编译耗时42.7s，优化后的差分升级编译耗时31.6s，节省约26%的编译运行时间，提升效果明显，优化后的差分升级算法优越性显著。

差分升级、全量远程升级传输时间对比和占用内存对比实验测试数据同样使用Test_V1.bin到Test_V5.bin该组测试固件包，最终测试结果如图11、图12所示。

对图11分析可得，使用本文优化后的差分升级算法，平均可以减少约73.78%的数据传输时间。在试验样本文件较小时，优化前差分升级和优化后差分升级传输耗时接近，提升比率相差不大。在试验样本文件较大时，如第Ⅴ组试验，优化后差分升级传输时间更短，耗时5.9s，提升比率为79.15%，相较于优化前差分升级算法，高出17.31%。

图12表明在内存开销方面，当测试包文件较小时，优化后差分升级算法优势不太明显，当文件较大时，优化后差分升级算法对比全量远程升级和优化前差分升级算法，提升明显，最高可达到约80%。

在测试环境下上述对比试验表明：相较于优化前差分升级算法，优化后的差分升级算法在压缩率、编译运行时间等指标上均有显著提升。为进一步验证优化后差分升级实际性能表现及以上试验结论，进行如下升级试验，该试验在实际环境下进行，基于以上硬件和服务器环境分别进行优化后差分升级和全量远程升级。使用本地开发环境对新版本固件源码进行编译得到250MB的新版本固件包，编译期间耗时8min，并使用新版本固件进行了30次全量远程升级测试，平均下载时间4min，平均安装时间为15min。根据2.3所述的远程升级流程制作了大小为47MB的补丁包文件，补丁包制作期间耗时3min，并使用补丁文件进行了30次差分升级，平均下载时间2min，平均安装时间2min。测试结果如表5所示。

表5表明：相比于全量远程升级，优化后差分升级补丁文件要小，编译耗时要少，下载时间要短以及安装速度要快，极大地提高了车载OBD的远程升级效率和减少了远程升级文件传输的流量消耗。

4结论

本文设计的一种基于改进Bsdiff算法的车载诊断系统远程升级系统。主要在以下方面做了优化：

1）针对原Bsdiff算法生成的补丁文件差分区域数据存在大量冗余零值的问题，本文以减小补丁文件体积及多线程分包下发为核心思想，对差分区域数据进行了去冗优化，并将补丁文件进行分包处理，采用多线程机制对车载OBD终端进行补丁下发；

2）对单片机闪存分区做了优化设计，采用动态调整分区空间的方式提高了闪存空间的利用率，避免了传统闪存分区执行更新操作时拷贝数据、擦除数据等耗时操作，提高了固件更新效率。

实验数据证明了在车载OBD终端设备上采用差分远程升级的可行性和可靠性。同时，与全量升级方法相比，采用优化后差分升级的方法在文件大小方面减小了203MB，性能提升81.2%；在文件编译、固件包下载及安装的时间方面性能分别提高了62.5%、50.0%和86.7%。从而，本文的升级系统提高了车载终端远程升级的效率。