基于BSDiff的改进远程增量更新方案

doi:10.16180/j.cnki.issn1007-7820.2022.07.009

摘要/Abstract

摘要：

传统的增量更新方案跨版本更新性能弱,需要生成并下发多个增量更新包,导致终端设备更新效率低。针对这一问题,文中提出一种基于BSDiff的改进远程增量更新方案。该方案优化了更新服务端的固件管理方式,利用BSDiff差分算法即时生成唯一增量更新包,以减少需要传输的更新数据量,并通过对BSDiff算法进行改进,加快增量更新包的生成。仿真实验结果表明,改进的增量更新方案具有与传统增量更新方案相同的压缩性能,在生成增量更新包时可以减少31.19%的时间,并在跨版本更新时减少了2.07%的数据传输量。

关键词: 服务端, 终端, 固件, 更新, 增量, BSDiff, 后缀数组, 压缩

Abstract:

The traditional incremental update solution has weak cross-version update performance, and multiple incremental update packages need to be generated and issued, resulting in low terminal device update efficiency. In view of this problem, an improved remote incremental update scheme based on BSDiff is proposed in the present study. The scheme optimizes the firmware management method of the update server, and uses the BSDiff algorithm to instantly generate a unique incremental update package to reduce the amount of update data that needs to be transmitted. The BSDiff algorithm is improved to speed up the generation of incremental update packages. The simulation experiments show that the improved incremental update scheme has the same compression performance as the traditional incremental update scheme. It can reduce the time by 31.19% on average when generating incremental update packages and reduce the data transfer amount by 2.07% on average when updating across versions.

Key words: server, terminal, firmware, update, incremental, BSDiff, suffix array, compression

中图分类号:

TP319

陈迪荣,包晓安,杜鹏,胡逸飞,苏鸿斌. 基于BSDiff的改进远程增量更新方案[J]. 电子科技, 2022, 35(7): 52-57.

CHEN Dirong,BAO Xiaoan,DU Peng,HU Yifei,SU Hongbin. Improved Remote Incremental Update Scheme Based on BSDiff[J]. Electronic Science and Technology, 2022, 35(7): 52-57.

图/表 9

图1

表1

表2

图2

表3

表4

表5

表6

图3

参考文献 18

[1]	赵志远, 王建华, 朱智强, 等. 面向物联网数据安全共享的属性基加密方案[J]. 计算机研究与发展, 2019, 56(6):1290-1301.
	Zhao Zhiyuan, Wang Jianhua, Zhu Zhiqiang, et al. Attribute-based encryption for data security sharing of internet of things[J]. Journal of Computer Research and Development, 2019, 56(6):1290-1301.
[2]	沙乐天, 肖甫, 陈伟, 等. 面向工业物联网环境下后门隐私泄露感知方法[J]. 软件学报, 2018, 29(7):1863-1879.
	Sha Letian, Xiao Fu, Chen Wei, et al. Leakage perception method for backdoor privacy in industry internet of things environment[J]. Journal of Software, 2018, 29(7):1863-1879.
[3]	王泽学, 万启东, 秦杨梅, 等. 基于多Agent强化学习的危险车辆预警算法[J]. 电子科技, 2020, 33(9):44-49.
	Wang Zexue, Wan Qidong, Qin Yangmei, et al. Dangerous vehicle early warning algorithms based on multi-agent enhancement learning[J]. Electronic Science and Technology, 2020, 33(9):44-49.
[4]	陈星, 黄志明, 叶心舒, 等. 智能家居情境感知服务的运行时建模与执行方法[J]. 软件学报, 2019, 30(11):3297-3312.
	Chen Xing, Huang Zhiming, Ye Xinshu, et al. Approach to modeling and executing context-aware services of smart home at runtime[J]. Journal of Software, 2019, 30(11):3297-3312.
[5]	胡春生, 王德, 赵汇东. 人体步态特征数据分析和人物身份识别方法研究[J]. 计算机应用研究, 2020, 37(S2):129-132.
	Hu Chunsheng, Wang De, Zhao Huidong. Research on human gait feature data analysis and person identification[J]. Application Research of Computers, 2020, 37(S2):129-132.
[6]	包晓安, 李刚, 文艺霏, 等. 基于压缩和差分算法的嵌入式平台远程更新设计与分析[J]. 浙江理工大学学报(自然科学版), 2020, 43(4):535-541.
	Bao Xiaoan, Li Gang, Wen Yifei, et al. Design and analysis of remote update of embedded platform based on compression and difference algorithm[J]. Journal of Zhejiang Sci-Tech University(Natural Science Edition), 2020, 43(4):535-541.
[7]	Kachman O, Balaz M. Effective over-the-air reprogramming for low-power devices in cyber-physical systems[C]. Caparica: The Seventh Advanced Doctoral Conference on Computing, Electrical and Industrial Systems, 2016.
[8]	魏民, 王艺. 物联网云平台终端远程更新技术研究与应用[J]. 电信科学, 2018, 34(10):137-142.
	Wei Min, Wang Yi. Research and application of remote update technology of IoT terminal[J]. Telecommunications Science, 2018, 34(10):137-142.
[9]	陈云. 嵌入式设备的邮递式升级方案[J]. 计算机科学, 2020, 47(S1):648-652.
	Chen Yun. Embedded device’s IAP solution based on mail-update[J]. Computer Science, 2020, 47(S1):648-652.
[10]	Teraoka H, Nakahara F, Kurosawa K. Incremental update method for resource-constrained in-vehicle ECUs[C]. Kyoto: IEEE the Fifth Global Conference on Consumer Electronics, 2016.
[11]	王豫新, 高美凤. 一种改进的固件增量更新算法[J]. 计算机工程, 2020, 46(10):210-215.
	Wang Yuxin, Gao Meifeng. An improved incremental update algorithm for firmware[J]. Computer Engineering, 2020, 46(10):210-215.
[12]	邓力, 周新志. 一种改良安全机制的嵌入式远程升级系统的研究[J]. 电子测量技术, 2017, 40(8):207-211.
	Deng Li, Zhou Xinzhi.Research of remote update system for embedded devices with improved security mechanism[J]. Electronic Measurement Technology, 2017, 40(8):207-211.
[13]	Ni G, Yan Y, Jiang J, et al. Research on incremental updating[C]. Shanghai: Proceedings of the International Conference on Communications, Information Management and Network Security, 2016.
[14]	马照亭, 刘勇, 沈建明, 等. 智慧城市时空大数据平台建设的问题思考[J]. 测绘科学, 2019, 44(6):279-284.
	Ma Zhaoting, Liu Yong, Shen Jianming, et al. Thinking of construction issue on spatio-temporal big data and platform for smart city[J]. Science of Surveying and Mapping, 2019, 44(6):279-284.
[15]	陈志龙, 倪桂强, 姜劲松, 等. 基于动态字典的增量更新算法[J]. 解放军理工大学学报(自然科学版), 2015, 16(5):426-432.
	Chen 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.
[16]	Bahne J, Bertram N, Böcker M, et al. Sacabench: benchmarking suffix array construction[C]. Segovia: Proceedings of the International Symposium on String Processing and Information Retrieval, 2019.
[17]	Fischer J, Kurpicz F. Dismantling divSufSort[C]. Prague: Proceedings of the Prague Stringology Conference, 2017.
[18]	陈卓民. 网络入侵检测系统中的模式匹配算法设计优化[J]. 电子设计工程, 2018, 26(15):154-157.
	Chen Zhuomin. Design optimization of pattern matching algorithm in network intrusion detection system[J]. Electronic Design Engineering, 2018, 26(15):154-157.

文件名	大小/Byte	DivSufSort	qSufSort	SAIS
101.EXE	438 144	0.050	0.074	0.076
netscape.exe	2 934 336	0.236	0.660	0.460
ping.bin	1 566 200	0.124	0.320	0.206

文件名	大小/Byte	DivSufSort	qSufSort	SAIS
101.EXE	438 144	2.34	3.34	2.09
netscape.exe	2 934 336	14.24	22.39	13.99
ping.bin	1 566 200	7.72	11.95	7.47

文件名	大小/Byte
V1.bin	366 724
V2.bin	380 916
V3.bin	381 124
V4.bin	381 204

版本变更	全量更新		传统增量更新		改进增量更新
	N_date	R_cmp	N_date	R_cmp	N_date	R_cmp
V1→V2	380 916	0	23 892	93.72	23 910	93.72
V2→V3	381 124	0	6 731	98.23	6 743	98.23
V3→V4	381 204	0	6 014	98.46	6 014	98.46

版本变更	全量更新		传统增量更新		改进增量更新
	N_date	R_cmp	N_date	R_cmp	N_date	R_cmp
V1→V3	381 124	0	30 623	91.96	23 989	93.70
V1→V4	381 204	0	36 637	90.43	24 049	93.73
V2→V4	381 204	0	12 745	96.65	8 220	97.84