2020, Vol. 46
b. 江南大学 物联网工程学院, 江苏 无锡 214122
b. School of Internet of Things Engineering, Jiangnan University, Wuxi, Jiangsu 214122, China
随着物联网技术的不断发展, 嵌入式设备的数量大幅增加, 2025年预计将会有1万亿台~3万亿台的嵌入式设备投入使用到物联网场景中[1]。固件是嵌入式设备中基础、底层的工作软件[2], 其安全性与稳定性极其重要, 只有对固件提供持续的更新服务, 才能确保设备的安全性, 满足用户对设备功能的需求。固件更新主要有全量更新和增量更新2种更新方式。全量更新方式是将新版本的固件完整发送给设备, 不仅会造成传输过程中的流量浪费, 还会增加设备的能源消耗[3], 而增量更新方式仅发送新、旧版本之间的差异文件给设备, 因此能够以较小的流量消耗和能源消耗, 实现远程修复固件的安全漏洞和升级固件功能[4]。
增量更新的基本流程是开发端使用输入的新、旧版本固件生成补丁文件, 设备端使用接收到的补丁文件和已有的旧版本固件恢复新版本固件。bsdiff算法[5]是较为成熟的增量更新算法, 由于该算法生成的补丁文件较小, 因此而得到广泛应用。如谷歌使用bsdiff算法的变体算法更新全球Google Chrome浏览器, 文献[6]将bsdiff算法应用于更新移动互联网个人云存储系统, 文献[7]采用bsdiff算法实现手机操作系统的更新。但是bsdiff算法在待更新设备上执行构建新版本固件任务时的内存消耗较大, 且随着新版本固件体积的增大而不断增大, 因此并不适用于内存资源受限的嵌入式设备。bsdiff算法执行构建新版本固件任务需要的辅助空间为u+v+w, 其中, u、v、w分别为旧版本固件大小、新版本固件大小与补丁文件的大小。文献[8]通过重新排序构建新版本固件要执行的编辑操作将其需要的辅助空间减小为max(u, v)+w。文献[9]通过改进bsdiff算法的补丁文件格式, 避免了在应用补丁文件时将整个补丁文件读入内存以及频繁计算偏移量。文献[10]利用哈希算法检测出新、旧版本文件之间的差异部分, 采用bsdiff算法分块执行增量更新, 减小了bsdiff算法需要的新、旧版本固件大小的辅助空间。同时, 由于增量更新算法生成补丁文件的过程发生在运算能力强、内存资源丰富的PC端, 而应用补丁构建新版本固件的过程发生在计算能力弱、内存资源有限的嵌入式设备端, 这2个过程具有典型的非对称特性[11], 因此将具备非对称特性的无损压缩算法引入MS-bsdiff算法的压缩、解压缩过程, 使得MS-bsdiff算法不仅能生成较小的补丁文件, 还能以较小的内存消耗在设备端完成增量更新。
本文基于bsdiff算法, 提出一种节约内存的MS-bsdiff(Memory Saving-bsdiff)增量更新算法。该算法通过改进bsdiff算法的补丁文件格式, 将bsdiff算法中的并行解压过程替换为串行解压, 并减小申请的辅助空间, 以降低设备端构建新版本固件时的内存消耗。
1 bsdiff增量更新算法 1.1 bsdifff算法描述根据bsdiff算法的具体应用, 可将其分为2个子过程:
1) diff过程:在开发端计算新版本固件与旧版本固件之间的差异, 并对该差异进行编码和压缩, 生成补丁文件。
2) patch过程:在设备端解压缩补丁文件中指定的数据, 并按照相应的解码规则应用补丁文件和旧版本固件, 从而构建出新版本固件。
图 1为bsdiff算法的补丁文件的格式, 其中, 阴影部分表示被压缩的数据区域。
|
Download:
|
| 图 1 bsdiff算法的补丁文件格式 Fig. 1 Patch file format of bsdiff algorithm | |
bsdiff算法的diff过程具体步骤为:
步骤1 创建空的补丁文件, 申请2个辅助空间a和b。
步骤2 通过后缀排序以及二分查找算法检索如图 2所示的old、new文件中的相似匹配区域与不匹配区域。
|
Download:
|
| 图 2 bsdiff算法的编码 Fig. 2 Coding of bsdiff algorithm | |
步骤3 对相似匹配区域与不匹配区域的数据进行编码。首先, 计算old、new文件的相似匹配区域的字符差值, 并生成一个di数据块, 将di数据块以追加的方式写入辅助空间a。其次, 不匹配区域代表new文件中独有的数据块, 将该数据块编码为一个ei数据块, 并将ei数据块以追加的方式写入辅助空间b。最后, 将生成的当前di数据块和ei数据块用于执行patch过程的控制信息, 并将这些控制信息存放于一个三元数组ci(xi, yi, zi)中, 其中, xi表示di的字节数, yi表示ei的字节数, zi表示old文件中的偏移量。
步骤4 将ci中的数据压缩后直接写入补丁文件的ctrl区域。
步骤5 重复步骤1~步骤4, 直至new文件的末尾。
步骤6 分别压缩辅助空间a与辅助空间b中的数据, 依次写入补丁文件的diff区域、extra区域, 并补充文件头部信息, 得到完整的补丁文件。
bsdiff算法执行对应的patch过程具体步骤为:
步骤1 创建空的new文件, 申请需要的辅助空间a[newsize]、辅助空间b[oldsize]。
步骤2 打开3个并行的解压进程, 并分别用于解压缩补丁文件的ctrl区域、diff区域和extra区域。
步骤3 解压缩并完成如图 3所示的Add操作。根据解压缩ctrl区域得到ci中的数据(xi, yi, zi), 根据解压缩diff区域得到大小为xi个字节的数据块di, 将di存放于辅助空间a中, 并依据ci中的偏移量zi提取出old文件中与di对应的数据, 将其存放于辅助空间b中。将上述2个数据块相加后得到目标数据, 并以追加的方式暂存在辅助空间a中。
|
Download:
|
| 图 3 bsdiff算法的解码 Fig. 3 Decoding of bsdiff algorithm | |
步骤4 解压缩并完成如图 3所示的Copy操作。解压缩extra区域得到大小为yi个字节的数据块ei, 将ei中的数据以追加的方式复制到辅助空间a中。
步骤5 调整负责管理辅助空间a与辅助空间b的指针, 循环执行步骤3与步骤4, 直至应用完补丁文件中所有的ci数据, 辅助空间a中的数据即为原new文件中的数据。
步骤6 将辅助空间a中的数据全部写入new文件, 释放申请的辅助空间, 并关闭打开的解压缩进程。
1.2 patch过程内存消耗较大的原因分析首先, bsdiff算法在patch过程中, 采用并行解压的方式解压缩补丁文件, 这是造成bsdiff算法内存消耗较大的原因之一, 因为同时解压3个部分需要的解压内存几乎是解压一个部分的三倍[9]。其次, 在patch过程的步骤1中申请的辅助空间过大, 这是由于多数情况下Add操作与Copy操作并不需要与新版本固件、旧版本固件同等大小的辅助空间。最后, bsdiff算法内部使用压缩级别为9的bzip2压缩算法压缩补丁文件, 但是, bzip2压缩算法的解压缩过程需要大量的运行内存, 并不适用于在资源有限的嵌入式设备上使用[12]。
2 MS-bsdiff增量更新算法 2.1 MS-bsdiff算法的补丁文件格式本文采用文献[9]中改进的补丁文件格式, 具体如图 4所示。将每次应用ci构建新版本固件所需的di数据块、ei数据块按序存放在补丁文件中, 执行patch过程只需要依次找到ci所需的di数据块和ei数据块即可逐步构建新版本固件。改进后的文件格式不需要频繁记录并计算每次应用ci所需的di数据块、ei数据块在补丁文件中的偏移量, 因此能够节省计算量和内存消耗。
|
Download:
|
| 图 4 改进的补丁文件格式 Fig. 4 Improved patch file format | |
MS-bsdiff算法的diff过程主要涉及2个过程, 分别为编码生成临时文件与压缩临时文件生成待传输的补丁文件, 其具体步骤为:
步骤1 创建空的临时文件和补丁文件。
步骤2 通过后缀排序以及二分查找算法检索old、new文件中的相似匹配区域和不匹配区域。
步骤3 计算得到当前相似匹配区域和不匹配区域对应的di数据块与ei数据块, 以及生成其对应的控制信息ci, 将ci、di、ei按顺序依次写入临时文件。
步骤4 重复步骤2与步骤3, 直至new文件的末尾。
步骤5 将算法的版本信息和new文件大小写入临时文件的头部区域, 并对临时文件执行一次整体的压缩, 从而得到待传输的补丁文件。
MS-bsdiff算法的patch过程主要涉及解压缩补丁文件得到临时文件, 以及应用临时文件进行解码得到新版本固件2个过程, 其具体步骤为:
步骤1 对补丁文件执行一次串行解压, 得到临时文件。
步骤2 创建空的new文件, 申请大小为m的2个辅助空间a1[m]、a2[m], 申请大小为n的辅助空间b1[n]。
步骤3 取出临时文件中的ci指令, 并存放于辅助空间b1中, 根据ci中的信息执行Add操作。判断ci中代表di数据块大小的xi≤m是否成立, 若成立, 则将di数据块从补丁文件中取出存放于辅助空间a1中, 并依据偏移量zi从旧版本固件中取出与di数据块对应的数据, 存放于辅助空间a2中, 然后将辅助空间a1和辅助空间a2中的数据相加, 将得到的目标数据直接写入new文件; 若xi≤m不成立, 则分批执行本次Add操作, 即每次从补丁文件、旧版本固件中分别取出大小为m的数据块存放在辅助空间a1与辅助空间a2中, 将辅助空间a1和辅助空间a2中的数据相加得到的目标数据写入new文件中, 并记录已经处理的大小为p的数据块, 直至p等于xi时, 完成了对di数据块的处理。
步骤4 根据ci中的信息执行Copy操作。判断ci中代表ei数据块大小的yi≤m是否成立, 若成立, 则将ei数据块从补丁文件中取出并存放于辅助空间a1中, 并将辅助空间a1中的数据写入new文件中; 否则与步骤3类似, 分批处理ei数据块, 直至将ei数据块中的内容全部写入new文件。
步骤5 重复执行步骤3与步骤4, 直至应用完临时文件中所有的ci指令, 从而完成对new文件的写入, 并释放申请的辅助空间, 删除临时文件。
由上述步骤可知, MS-bsdiff算法的解码过程需要的辅助空间大小的固定值为2m+n, 其中, m和n小于新、旧版本固件的大小, m可以根据嵌入式设备的实际内存大小进行调整, n与ci的大小相同。此外, 虽然MS-bsdiff算法在patch过程需要一个临时文件, 占用了设备端的部分存储空间, 但存储空间通常远大于内存空间, 而且存储空间相比于内存空间更易扩展, 因此, 对于内存空间受限的嵌入式设备, 可以消耗部分存储空间以满足程序运行时的内存需求。
2.3 非对称的无损压缩算法在无损压缩算法领域, LZ(Lempel-Ziv)族算法在压缩和解压缩过程中的时间和内存需求方面表现出高度的不对称性[13]。本文将表 1列出的6种无损压缩算法应用于MS-bsdiff算法的压缩与解压缩过程, 且这6种无损压缩算法都实现了对应的处理文件流的函数接口, 除了bzip2算法以外, 其他算法都具备LZ族算法非对称的特点。同时, 为了获得更好的压缩效果, 各种算法都选择当前版本软件所支持的最大压缩级别。
|
下载CSV 表 1 6种无损压缩算法描述 Table 1 Description of six lossless compression algorithms |
实验以机智云物联网科技公司为ESP8266芯片开发的开源固件为样本, 其具体说明如表 2所示, 其中, 固件的名称为版本号加上该固件对应的处理器类型, 以25_16.bin为例说明, 它表示该固件的版本号为25, 对应的处理器类型为16位。
|
下载CSV 表 2 实验样本数据集 Table 2 Experimental sample dataset |
本文以补丁文件大小、patch过程的内存消耗以及时间消耗作为评价增量更新算法的关键指标。补丁文件大小直接影响增量更新算法的可行性, 这是由于即使是很小的新版本固件的变化都可能需要一个很大的补丁文件来记录新、旧版本固件之间的差异信息[14]。此外, 已有研究表明, 在增量更新过程中, 设备通过无线传输接收固件的能量消耗远大于patch过程[15-16], 因此较小的补丁文件能够节省设备的能量。patch过程的内存消耗不宜过大, 因为较大的内存消耗将对设备上执行的其他任务造成影响, 甚至决定能否在设备上运行构建新版本固件的程序[17]。同时, 合理的时间消耗也是需要考虑的性能指标。
本文跟踪算法的补丁文件大小以及在patch过程中的时间和运行内存消耗。补丁文件的大小用压缩率来衡量, 压缩率n的计算方法为:
| $ n=\left(s_{\text {new }}-s_{\text {patch }}\right) / s_{\text {new }} \times 100 \% $ | (1) |
其中, snew为新版本固件的大小, spatch为补丁文件的大小。压缩率n反映了相较于发送整个新版本固件, 发送补丁文件节省的文件大小的程度。压缩率越大, 则表示补丁文件越小, 越节省因传递补丁文件而造成的时间、能量和网络流量开销[18]。
3.1.2 实验环境配置实验环境为Intel® CoreTM i5-3230M处理器, CPU 2.60 GHz, 内存4 GB, 硬盘465 GB。运行环境为Windows 7(32位)系统中的VMware虚拟机, 编程语言为C语言。编译器为gcc-4.8.4.虚拟机的linux操作系统, 版本为ubuntu-14.04.5, 配置参数为单处理器, 内存为1 GB, 硬盘为20 GB。
3.2 实验设计与分析实验选择MS-bsdiff算法的patch过程中的m=32 KB, n=24 Byte。当使用相同的实验样本时, MS-bsdiff算法中patch过程的解码任务处理的数据相同, 需要的辅助空间的固定大小为2m+n, 因此MS-bsdiff算法采用不同的压缩算法时, patch过程的时间和内存消耗主要取决于解压缩任务的时间和内存消耗。实验分别测试了MS-bsdiff算法patch过程的解压缩与解码任务的时间和内存消耗, 由于解压缩与解码任务是先后执行的, 因此patch时间是解压缩时间与解码时间之和, patch内存是解压缩内存与解码内存中的较大值。利用基于bsdiff-4.3版本的开源代码实现MS-bsdiff算法, 并将表 1中列出的6种压缩算法应用于MS-bsdiff算法的压缩、解压缩过程。本文选取了当前普遍使用的xdelta算法[19]、vcdiff算法[20]、zdelta算法[21]3种固件增量更新算法与MS-bsdiff算法进行性能比较, 结果如表 3所示。
|
下载CSV 表 3 各种增量更新算法的性能比较 Table 3 Performance comparison of various incremental update algorithms |
从表 3可以看出, MS-bsdiff算法具有良好的压缩性能。当MS-bsdiff算法内部使用fastLZ算法时, 其压缩率最小为96.84%, 比xdelta-1.1.3算法与vcdiff-3.0.7算法的压缩率大。此外, MS-bsdiff算法的patch过程的时间相比于bsdiff算法有所增长, 但是其patch过程的内存均小于bsdiff算法。当MS-bsdiff算法采用与bsdiff算法相同的压缩算法bzip2时, 其压缩率为98.26%, 相比于bsdiff算法有所下降, 这主要是因为bzip2算法应用于高度结构化的数据时压缩效果更好[5], MS-bsdiff算法使用新的补丁文件格式, 影响了bzip2的压缩性能。bzip2算法的串行解压内存为2 125.0 KB, bsdiff算法的patch内存为8 095.3 KB, 这说明bsdiff算法中负责解压缩补丁文件的3个并行的bzip2解压进程, 是造成bsdiff算法内存消耗较大的主要原因。当MS-bsdiff算法内部使用Lzma算法时, 其压缩率最高为98.43%, 且其patch过程的内存相比于bsdiff算法也有所下降。当MS-bsdiff算法内部使用Lzw算法时, 其压缩率为97.82%, 均大于xdelta-1.1.3算法、vcdiff-3.0.7算法和zdelta-2.1.0算法的压缩率, 同时, 其解压内存仅为1 200.0 KB, 小于使用bzip2算法时的解压内存2 125.0 KB, 在内存资源受限的设备中, MS-bsdiff算法使用Lzw算法进行压缩与解压缩时, 可以进一步降低设备端patch过程的内存消耗。
应用表 2中的6组实验数据, 得到MS-bsdiff算法内部使用Lzw算法时的patch运行内存与bsdiff算法的patch运行内存比较, 如图 5所示。从图 5可以看出, 当MS-bsdiff算法内部使用Lzw算法时, 其patch过程的运行内存远小于bsdiff算法, 且其patch过程的运行内存几乎是恒定的。因此, 当采用内部使用Lzw算法的MS-bsdiff算法执行固件增量更新时, 其patch过程不会由于复杂的系统功能导致的固件体积增大, 而需要更多的内存空间。
|
Download:
|
| 图 5 MS-bsdiff(Lzw)算法与bsdiff算法的patch过程运行内存比较 Fig. 5 Comparison of running memory between MS-bsdiff(Lzw) algorithm and bsdiff algorithm in patch process | |
在bsdiff算法的基础上, 本文提出一种节约内存的增量更新算法MS-bsdiff, 并将非对称的无损压缩算法应用到该算法的压缩与解压缩过程。实验结果表明, 在该算法中使用Lzw算法进行压缩与解压缩时, 其patch过程的内存消耗约为bsdiff算法的1/6, 而且内存消耗不会因固件体积的增大而增大, 同时该算法能够生成较小的补丁文件。下一步将继续探索压缩效率高、解压缩内存消耗小的无损压缩算法在MS-bsdiff算法中的性能, 以提高增量更新算法的效率。
| [1] |
HUYNH-VAN D, TRAN-QUOC K, LE-TRUNG Q.An empirical study on approaches of internet of things reconfiguration[C]//Proceedings of the 7th International Conference on Communications and Electronics.Washington D.C., USA: IEEE Press, 2018: 57-62.
|
| [2] |
DU Zhenlong, SHA Guangxia, LI Xiaoli, et al. Customization and update research on capsule type firmware based on UEFI[J]. Computer Engineering, 2014, 40(10): 292-295, 303. (in Chinese) 杜振龙, 沙光侠, 李晓丽, 等. 基于UEFI的胶囊式固件定制更新研究[J]. 计算机工程, 2014, 40(10): 292-295, 303. |
| [3] |
KACHMAN O, BALAZ M. Effective over-the-air reprogramming for low-power devices in cyber-physical systems[M]. New York, USA: Springer International Publishing, 2016: 284-292.
|
| [4] |
KACHMAN O, BALAZ M, MALIK P. Universal framework for remote firmware updates of low-power devices[J]. Computer Communications, 2019, 139: 91-102. DOI:10.1016/j.comcom.2019.03.014 |
| [5] |
PERCIVAL C.Matching with mismatches and assorted applications[D]. Oxford, UK: University of Oxford, 2006.
|
| [6] |
XIA Qi.Research on difference algorithm in mobile Internet data updating[D]. Chengdu: University of Electronic Science and Technology of China, 2014.(in Chinese) 夏棋.移动互联网增量数据差分更新算法研究[D].成都: 电子科技大学, 2014. |
| [7] |
SHI Chao.The research and design of incremental OTA upgrade system based on Android platform[D]. Zhenjiang: Jiangsu University, 2017.(in Chinese) 施超.基于Android平台OTA增量升级系统研究与设计[D].镇江: 江苏大学, 2017. |
| [8] |
NAKANISHI T, SHIH H H, HISAZUMI K, et al.A software update scheme by airwaves for automotive equipment[C]//Proceedings of 2013 International Conference on Informatics, Electronics and Vision.Washington D.C., USA: IEEE Press, 2013: 1-6.
|
| [9] |
TERAOKA H, NAKAHARA F, KUROSAWA K.Incremental update method for resource-constrained in-vehicle ECUs[C]//Proceedings of the 5th Global Conference on Consumer Electronics.Washington D.C., USA: IEEE Press, 2016: 1-2.
|
| [10] |
LI Jinfeng.Design and implementation of APP hosting platform based on play framework[D]. Beijing: Beijing University of Posts and Telecommunications, 2018.(in Chinese) 李锦峰.基于play framework的APP托管平台的设计与实现[D].北京: 北京邮电大学, 2018. |
| [11] |
MOTTA G, GUSTAFSON J, CHEN S.Differential compression of executable code[C]//Proceedings of 2007 Data Compression Conference.Washington D.C., USA: IEEE Press, 2007: 103-112.
|
| [12] |
KOMANO Y, XIA Z F, KAWABATA T, et al.Efficient and secure firmware update/rollback method for vehicular devices[C]//Proceedings of Information Security Practice and Experience.Berlin, Germany: Springer, 2018: 455-467.
|
| [13] |
FERREIRA A J, OLIVEIRA A L, FIGUEIREDO M A T.On the suitability of suffix arrays for lempel-ziv data compression[C]//Proceedings of International Conference on E-Business and Telecommunications.Berlin, Germany: Springer, 2008: 267-280.
|
| [14] |
WEI Min, WANG Yi. Research and application of remote update technology of IoT terminal[J]. Telecommunications Science, 2018, 34(10): 137-142. (in Chinese) 魏民, 王艺. 物联网云平台终端远程更新技术研究与应用[J]. 电信科学, 2018, 34(10): 137-142. |
| [15] |
MAZUMDER B, HALLSTROM J O.An efficient code update solution for wireless sensor network reprogramming[C]//Proceedings of International Conference on Embedded Software.Washington D.C., USA: IEEE Press, 2013: 1-10.
|
| [16] |
STOJKOSKA B R, NIKOLOVSKI Z.Data compression for energy efficient IoT solutions[C]//Proceedings of the 25th Telecommunication Forum.Washington D.C., USA: IEEE Press, 2017: 1-4.
|
| [17] |
STOLIKJ M, CUIJPERS P J L, LUKKIEN J J.Efficient reprogramming of wireless sensor networks using incremental updates[C]//Proceedings of 2013 IEEE International Conference on Pervasive Computing and Communications Workshops.Washington D.C., USA: IEEE Press, 2013: 584-589.
|
| [18] |
CHENG Zhilong, NI Guiqiang, JIANG Jinsong, et al. Incremental update algorithm based on dynamic dictionary[J]. Journal of PLA University of Science and Technology (Natural Science Edition), 2015, 16(5): 426-432. (in Chinese) 陈志龙, 倪桂强, 姜劲松, 等. 基于动态字典的增量更新算法[J]. 解放军理工大学学报(自然科学版), 2015, 16(5): 426-432. |
| [19] |
MACDONALD J.File system support for delta compression[D]. Berkeley, USA: University of California at Berkeley, 2000.
|
| [20] |
KORN D, MACDONALD J, MOGUL J, et al.The VCDIFF generic differencing and compression data format[EB/OL].[2019-09-20]. https://www.rfc-editor.org/in-notes/pdfrfc/rfc3284.txt.pdf.
|
| [21] |
TRENDAFIL O V D, MEMON N, SUEL T.Zdelta: an efficient delta compression tool[EB/OL].[2019-09-20]. https://www.researchgate.net/profile/Nasir_Memon/publication/2556720_zdelta_An_Efficient_Delta_Compression_Tool/links/0046351f9ae28a19bd000000/zdelta-An-Efficient-Delta-Compression-Tool.pdf.
|