星载软件的语句级高效更新方法

靳 鑫，徐清华，王慧泉，金仲和

(1.浙江大学 微小卫星研究中心，杭州 310000； 2.上海宇航系统工程研究所，上海 201109)

随着微小卫星功能的软件化快速发展[1-2]及任务难度的升级，星载软件功能出现异常的风险越来越高，软件在轨更新已发展成为星载软件的基础功能之一[3]。此外，对在轨卫星进行软件更新，还可实现硬件故障隔离和应用功能扩展，是提高卫星运行安全与经济价值的重要手段[4]。

由于微小卫星星地测控链路(特别是S频段测控)通信速率小、通信时间有限，因此大型星载软件更新通常采用低数据量的差异更新[5]，常用的星载软件差异更新方法主要可分为两种[6]：1)模块级更新。模块级更新通过将更新模块的目标文件上注，利用星上操作系统动态加载技术进行目标文件替换，达到星载软件更新的目的[7-8]；2)语句级更新。其基本原理是对比更新版与参考版的加载文件，将不同之处生成补丁上注，星上将上注的差异内容覆盖参考版对应位置内容，完成更新[9]。相较模块级更新，语句级更新无需操作系统环境，因此在微小卫星中广泛应用。 然而，由于代码修改通常会影响程序空间布局，使得加载文件内容发生大幅变动，进而出现更新数据量激增的现象[5]。为降低更新数据量，朱虹等[10]提出了将可更新子程序独立存储，通过地址表进行子程序调用的方法，使得子程序内部修改不影响外部内容。李雁斌等[11]提出可以将可更新函数进行独立存储，利用钩子函数进行可更新函数寻址调用。这两种预设可更新对象的方法虽易实施，但限制了软件更新范围。李振松等[12]提出将每个函数看成可更新对象，并逐个分配固定存储区。该方法的优点在于最大程度地限制了代码修改对程序空间的影响，然而该方法不仅难以应对函数新增情况，而且采用的函数级修改方法极易导致存储空间需求激增，需为每个函数预留充足的存储空间，增加内存容量负担，并使得内存空间严重碎片化。

上述语句级更新方法只强调如何通过约束程序空间的方式来降低代码修改对加载文件的影响，却忽略了加载文件的差异生成过程对最终更新数据量的影响。传统的差异提取方式可称为同地址比较法，即比较参考版与更新版加载文件在相同程序空间地址上的内容，二者不同则认为是差异内容。这种差异提取方式放大了处于低地址空间的更新对整个更新数据量的影响。只约束程序空间而不改进差异提取方式的语句级更新方法，在追求更低更新数据量同时，会极大地限制更新范围或带来严重的内存负担，难以实现星载大规模软件的灵活更新。

为了克服传统语句级更新方法存在的问题，本文在约束程序空间布局的基础上，进一步考虑差异生成过程对更新数据量的影响，提出了一种利用序列间匹配路径进行差异补丁制作的方法。同时本文为了保证星载软件状态可回滚，设计了版本引导程序。实验结果表明，利用本文提出的方法进行软件在轨更新时，更新上注数据量少、过程可靠，且软件状态可回滚。

1 星载软件在轨更新方法

1.1 更新方法概述

一次完整的星载软件语句级更新通常包含地面过程和星上过程两部分，如图1所示。

图1 语句级星载软件在轨更新过程

地面过程包含4个步骤，分别为：1)开发新版本软件。利用开发工具对软件源码进行修改、编译和链接，生成新版目标可执行文件，并从中提取加载依赖项形成加载文件；2)制作差异补丁。将新版与参考版加载文件按照一定规则进行比对，提取差异内容并制作成补丁文件；3)制作注数块。对补丁文件进行分割与封装，将其转换为满足星地遥控数据格式约束的注入数据块序列；4)遥控上注。通过星地遥控链路，将更新数据块逐块上注至卫星。星上过程包含3个步骤，分别为：1)解析注数块。解析并拼接更新数据块，恢复出补丁文件；2)在轨合成。根据补丁文件内容对参考版加载文件进行修改，形成新版加载文件；3)重加载。对采用非在线更新的星载计算机，还需通过重加载操作实现软件版本切换。

1.2 加载文件设计

加载文件服务于卫星程序装载过程，由可执行文件裁剪而来。在DSP软件开发环境CCS(code composer studio)中，可执行文件又称.out文件，该文件中除包含软件独立运行的所有信息外，还包含用于保持通用性的内容。对采用静态加载的星载计算机，程序装载只关心入口地址和各初始化段内容，因此可将.out文件裁剪成图2所示文件格式。

图2 加载文件格式

图2中“入口地址”(4 Byte)表示程序运行时的起始地址；“段总数”(4 Byte)表示程序加载时所需的代码段及初始化数据段总数，该值记为K；“段地址”(4 Byte)、“段大小”(4 Byte)及“段内容”分别为该数据段/代码段在程序空间中的起始地址、占用量及具体内容。默认设置下，CCS开发平台生成的初始化段有5个：text、switch、vectors、cinit及const段。开发者可以根据实际应用需求，利用MEMORY和SECTIONS伪指令对链接命令文件(.cmd文件)重新编辑来自定义程序空间分配情况，然后利用预编译指令pragma在源文件和头文件中用设置函数和全局/静态变量的归属段。

在本文提出的更新方法中，要求软件更新时不改变程序空间划分情况，因此参考版加载文件和更新版加载文件中“段总数”和各对应“段地址”相同。

1.3 补丁文件设计

语句级更新方法的核心在于获取参考版加载文件和更新版加载文件之间的差异内容。从图2所示的加载文件格式可知，两版加载文件之间的差异主要来自各“段内容”字段，因此高效提取该字段的差异是降低更新数据量的关键。

参考段序列与更新段序列分别设为T=t1,t2,…,tn、S=s1,s2,…,sm，其中n、m分别为参考段和更新段的大小。利用同地址比较法进行差异内容提取时，差异内容规模表示为

F(T,S)=F({ti1≤i≤n},{si1≤i≤m})=

(1)

式中f(x,y)为差异函数，定义为

对星载软件在轨更新而言，差异内容的规模直接决定了更新上注的数据量。若进一步将T表示为T=t1,…,tk,tk+1,…,tk+w,tk+w+1,…,tn，那么利用同地址比较方法得到的差异内容规模与更新方式之间存在如下关系：

1)替换内容。当更新时将T的第k+1～k+w字节内容替换成x1,…,xw，(tk+i≠xi，1≤i≤w)，形成的更新段S=t1,…,tk,x1,…,xw,tk+w+1,…,tn。此时T和S之间的差异内容规模F(T,S)为

F(T,S)=F({ti1≤i≤k},{ti1≤i≤k})+

F({tik+1≤i≤k+w},{xi1≤i≤w})+

F({tik+w+1≤i≤n},{tik+w+

(2)

可知以内容替换的方式进行更新时，差异内容规模即为替换内容规模。

2)新增内容。当更新时在T的第k字节内容后插入w个字节x1,…,xw，形成的更新段S=t1,…,tk,x1,…,xw,tk+1,…,tk+w,tk+w+1,…,tn。此时T和S之间的差异内容规模F(T,S)为

F(T,S)=F({ti1≤i≤k},{ti1≤i≤k})+

F({tik+1≤i≤k+w},{xi1≤i≤w})+

F({tik+w+1≤i≤n},{tik+1≤i≤n})=

F({tik+1≤i≤k+w},{xi1≤i≤w})+

F({tik+w+1≤i≤n},{tik+1≤i≤n-w})+

F(∅,{tin-w+1≤i≤n})=

(3)

由于

故有w≤F(T,S)≤n-k+w。当以内容新增的方式更新时，差异内容规模不小于新增内容规模，规模最大值与参考段内容的长度n及新增内容规模w成正线性关系，与新增位置偏移k成负线性关系。

3)删除内容。当更新时将T的第k字节内容后删除w个字节，形成更新段S，表示为S=t1,…,tk,tk+w+1,…,tn。此时T和S之间的差异内容规模F(T,S)为

F(T,S)=F({ti1≤i≤k},{ti1≤i≤k})+

F({tik+1≤i≤n-w},{tik+w+1≤i≤n})=

(4)

可得0≤F(T,S)≤n-k-w，即当以内容删除的方式更新时，差异内容规模最小值为0，最大值与参考段内容的长度n成正线性关系，与删除位置偏移k和删除内容规模w成负线性关系。

根据上述分析可知，利用同地址比较方法进行差异内容提取时，若更新出现内容新增或删除，提取出的差异内容规模受到参考段大小、新增/删除位置偏移及规模相关，易发生数据量激增的现象，不利于星载软件的在轨更新应用。为了克服该缺点，本文引入能够表示序列间相互转换所需的最少编辑操作次数的编辑距离理论[13]，通过计算参考段与序列段间的匹配路径，进行差异内容提取。具体过程如下所述。

序列T和S之间的编辑距离值Lev(T,S)表示为

(5)

式中tail(T)、tail(S)分别为序列T和S除首元素外的尾序列。本文基于动态规划方法计算Lev(T,S)[14]，按如下3个步骤进行：

步骤1建立(n+1)×(m+1)大小的编辑距离矩阵D(m+1)×(n+1)={di,j}(0≤i≤m，0≤j≤n)。

步骤2设置初项d0,j=j(0≤j≤n)和di,0=i(0≤i≤m)。

步骤3根据式(6)所示的状态转移公式，迭代出矩阵D中余下元素di,j(0

(6)

式中dm,n的值即表示从序列T到S所需的编辑次数Lev(T,S)，算法时间复杂为O(mn)，空间复杂度可优化至O(min(m,n))[14]。相比同地址比较法，基于匹配路径的方法虽然时间复杂度较高，但该过程只在地面进行，实际并不影响星载软件的在轨更新应用。此外根据编辑距离的定义可知，无论更新时发生内容替换、新增还是删除，所需执行的编辑操作次数均等于更新的字节数，而编辑操作次数即为差异内容规模，故本文提出的差异提取方法不会出现更新数据量激增的现象。

为了确定具体编辑位置和编辑方式，需从矩阵D的dm,n元素向d0,0元素出发，回溯出序列T和S的匹配路径[14]，然后根据匹配路径d0,0->dm,n上各元素的坐标和取值变化特点生成编辑过程：1)当匹配路径呈水平状(行坐标不变)时，删除序列T的当前字节；2)当匹配路径呈竖直状(列坐标不变)时，在序列T的当前字节之后插入序列S的当前字节；3)当匹配路径呈对角状(行、列坐标均变)时，如果编辑距离值不变，则无需进行编辑操作，否则将序列T的当前字节改写成序列S的当前字节。如图3所示展示了序列T={0x01,0x02,0x03,0x04,0x05,0x06,0x07,0x08,0x09,0x10}，S={0x03,0x04,0x06,0x36,0x07,0x09,0x10,0x11,0x12,0x13}时的编辑距离矩阵D、匹配路径以及T到S的编辑过程。

由图3可知将序列T转换为序列S需要进行8个字节的编辑，具体编辑过程为：将序列T的第1、2、5字节删除，将第7、8字节分别改写成序列S的第4、5字节，在第10字节之后依次插入序列S的第8、9和10字节。为了保证该编辑过程能够被准确解析，需在差异补丁中体现对参考内容的编辑位置、编辑方式及编辑后内容；同时为了减小差异补丁大小，可将对连续字节进行同类型编辑操作的编辑过程进行合并。因此本文提出的差异补丁的具体格式如图4所示。

图3 序列T和S的编辑矩阵与编辑过程

图4 差异补丁格式

“地址偏移”和“编辑长度”分别表示本次编辑的起始地址偏移及编辑字节数，考虑到编辑距离矩阵求解过程的时间和空间复杂度分别为O(nm)和O(m)，段内容过长时易出现运行时间过长和程序内存不足的问题，故本文推荐这两个字段均采用2字节表示，对应要求加载文件中各段内容的长度不超过64 KByte；“编辑类型”(1 Byte)可取值为0x11、0x22或0x33，分别对应“删除”、“插入”和“改写”操作；“更新后内容”表示插入和改写后的内容。根据该差异补丁格式，图3所示的编辑过程对应的十六进制码流为：{0x0000,0x11,0x0002;0x0004,0x11;0x0001;0x0006,0x33;0x0002,0x36,0x07;0x000A,0x22,0x0003,0x11,0x12,0x13}。

上述内容描述了参考版与更新版加载文件中，段内差异补丁制作方法与过程，而加载文件间可能的差异字段还包括“入口地址”和各“段大小”；此外为了兼容回滚操作，补丁文件中需指明补丁类型，回滚补丁中需给出回滚版本号，更新补丁中需给出参考版本号和更新版本号。综合上述字段需求，本文提出的完整补丁文件格式如图5所示。

图5中“补丁类型”(1 Byte)指明是回滚补丁或更新补丁：如果是回滚补丁，则“版本号1”(1 Byte)表示回滚操作的目标版本号，补丁文件中无可选字段；如果是更新补丁，则“版本号1”表示参考版本号，且补丁文件中包含可选字段。可选字段中：“版本号2”(1 Byte)表示更新版本号；“入口地址”(4 Byte)表示新版程序运行时的起始地址；“段k地址”(4 Byte)表示存在内容差异的段地址，k(1≤k≤K)为段序号；“段k长度”(4 Byte)表示新版加载文件中第k段的长度；“段k差异补丁集合”表示第k段的差异补丁集合，该集合由若干个按图4格式生成的差异补丁组成。

图5 补丁文件格式

1.4 上注数据块设计

补丁文件字节数较多，需地面以注入数据形式上注至卫星。以ZDPS-3A卫星为例，该卫星是针对中国卫星测控网测控设备和远程雷达精度标校需求而设计的纳卫星，已于2020年6月17发射入轨。该卫星上行数据采用PCM遥控体制，除去帧控制域、帧校验域等标准字段外，实际用于放置应用数据的字段长度为249 Byte，因此一个更新补丁文件通常需要多个注数帧才能上注完毕。为了保证星上能够按序还原更新补丁文件，需要在更新数据块中增加块总数和块序号信息。如图6所示给出了本文设计的在轨更新注入数据帧格式，I、i分别为数据块总数和当前数据块编号，均占2字节。

图6 在轨更新注入数据帧格式

从图6中可以看出，各数据块帧数据域中前2字节均为“数据块编号”，表示数据块在补丁文件中的顺序，用于保证星上能够对收到的补丁文件进行有序重组。对首条数据块，帧数据域第3～4字节为“数据块总数”，表示本次更新所需上注数据块总数，星上用该值进行数据块检验，并据此提示地面所缺数据块编号；数据块帧数据域余下空间均填充补丁文件内容，当补丁文件内容无法填满数据域时，不足空间填充0xAA。

1.5 在轨更新监视程序设计

为了实现图1所示的在轨更新星上过程步骤1)、2)，即数据块解析和新版加载文件在轨合成，本文设计了如图7所示的在轨更新监视程序。

图7 在轨更新监视程序执行流程

根据图7所示，在轨更新监视程序会对通过合法性判断的数据块进行“补丁类型”判断，如果是回滚操作，则根据补丁中的“版本号1”字段设置下次软件加载版本号；如果是更新操作，则进行更新补丁拼接直至获取完整补丁文件，并据此对补丁中“版本号1”字段指明的参考版加载文件进行修改，生成新版加载文件写入存储器，最后根据补丁中“版本号2”字段设置下次软件加载版本号。

在轨更新监视程序的可靠性设计主要包括数据块合法性检查、数据存储和过程状态监视等3方面内容。

1)合法性检查方面。设计检查对象除CRC(cyclic redundancy check)校验码外，还包括补丁中的特殊字段。首先要求星上收到的第1条数据块必须为编号0的数据块，原因在于只有编号0的数据块中包含补丁类型、版本号和数据块总数等信息；其次要求当前数据块序号i应小于总数据块个数I；最后还要求补丁文件中“版本号1”字段(即回滚版本号或参考版本号)在星上已存版本号范围之内，“版本号2”字段(即更新版本号)等于星上已存最新版本号加1。

2)数据存储方面。设计使用NAND Flash循环存储各版本加载文件，并使用ReRAM存储版本管理信息，包括NAND Flash中已存各版本加载文件的地址和对应的版本号，以及下次软件加载的版本号。由于差异更新需要基准版本，因此将NAND Flash的代码存储区分为不可擦除区和可擦除区，不可擦除区在地面阶段烧入第0版本加载文件作为差异更新的可用基准，可擦除区采用循环模式存储在轨生成的各版加载文件。NAND Flash和ReRAM中数据均采用三模冗余存储方式。

3)过程状态监视方面。设计了8个遥测量共18字节，用于保证地面能够实时掌握在轨更新进度和程序执行状态，进而配合星上过程顺利完成软件更新或回滚。这8个遥测量依次为：

a)合法性检查结果(1 Byte)：0x00合法；0x11校验码异常；0x22关键字段提取异常；0x33版本号1异常；0x44版本号2异常；0x55序号字段异常。

b)在轨更新运行状态(1 Byte)：0x00，完成；0x11，未完成；0x22，数据块非法；0x33，参考版加载文件读取失败；0x44，新版加载文件写入失败。

c)已存最旧版本号(1 Byte)。

d)已存最新版本号(1 Byte)。

e)下次加载版本号(1 Byte)。

f)所缺数据块条数(2 Byte)。

g)所缺前5个数据块ID(10 Byte)。

1.6 版本引导程序设计

为了实现图1所示的在轨更新星上过程步骤3)，即软件版本切换，本文中设计了版本引导程序，整体流程如图8所示。

根据图8所示，执行版本引导程序时，首先进行DSP和存储器(NAND Flash和FeRAM)的初始化；接着从FeRAM中读取软件版本管理信息和目标版本号信息，如果这两种信息任一获取失败，则从NAND Flash中读取版本0的加载文件，否则读取目标版本的加载文件；最后将加载文件内容分段装载至程序空间，并将程序入口地址装载至程序计数器，开始运行卫星程序。

版本引导程序的可靠性设计主要体现为读取NAND Flash和FeRAM中数据时采用三模冗余操作，且任意数据获取异常时，星上能够加载版本0代码回到默认稳定状态。

图8 版本引导程序执行流程

2 实验结果

本文实验基于ZDPS-3A卫星星载计算机平台，对所提出的软件在轨更新方法进行试验，主要针对更新/回滚操作执行情况，以及更新数据量等项目进行测试。虽然实验在地面进行，但过程模拟实际在轨状态，数据块均通过地面站以2 000 bps的PCM遥控模式上注，并在实验开始前将版本0的加载文件烧入NAND Flash不可擦除区。

2.1 更新与回滚操作实验

实验在版本0的基础上进行15次修改，形成编号为1～15的更新版本。表1显示了24次更新与回滚操作的实验结果，其中列“Id”为滚回版本号或更新版本号，列“Idr”为参考版本号，列“Idc”、“Idc’”分别为操作前和操作后星上运行的版本号，列“Ido”、“Idn”分别为操作之前NAND Flash中可擦除区保存的最旧和最新加载文件版本号。

表1数据显示经过24次更新/回滚操作实验，更新成功与失败次数分别为15次和2次，回滚成功与失败次数分别为5次和2次。进一步分析各次操作结果可知：

1)当更新/回滚操作满足在轨更新监视程序的合法性设计时，操作能正常执行；

2)执行更新操作时，如果新版加载文件版本号不连续，或参考版本号不在星上存储范围时，星上不执行更新操作，而保持当前版本运行，该现象符合在轨监视程序的可靠性设计；

3)执行回滚操作时，如果回滚版本号不在星上存储范围时，星上会自动加载版本0程序以保证软件安全，该现象符合版本引导程序的可靠性设计。

表1 软件更新操作执行结果

上述实验结果表明本文提出的软件更新方法能够可靠地实现软件更新和回滚。

2.2 差异更新效果实验

由于回滚操作仅需要1条注数块，因此本实验仅针对更新操作。实验以传统的同地址比较法为比较对象，分析了本文提出的利用匹配路径进行差异提取的方法在更新数据量方面的优势。

实验时首先在版本0的基础上进行修改，逐步生成5个新版本加载文件；然后以版本0为参考对象，进行版本1～5的更新。如图9所示显示了传统差异提取方法和本文差异提取方法在不同版本更新过程中所生成的补丁文件规模。

图9表明利用版本0进行版本1～5的更新时，相比传统差异提取方法，本文方法能够显著减少补丁文件规模。表2列出了以不同版本为参考进行版本1～5更新时，传统方法与本文方法在更新数据量、注入数据块数量及测控资源需求等3个项目上的实验结果。表2在计算测控资源需求量时，参考ZDPS-3A卫星平均每个测控圈的实际发令情况，设置每个测控圈中可用于上注在轨更新数据块的时长和发令间隔分别为6 min和8 s，因此每圈可上注约45条在轨更数据块，当需求量不足整圈时，按整圈向上取整。

图9 更新补丁规模

表2 不同更新方法实验结果

表2实验数据表明，两种差异更新方法得到的补丁文件规模都远小于加载文件规模，因此上注差异补丁比上注完整的加载文件更适合用于星载软件在轨更新。两种差异更新方法比对来看，相比使用传统的同地址比较法进行差异内容提取的方式，使用本文提出的基于匹配路径的差异内容提取方式，平均可降低53.00%的补丁规模、52.95%的数据块上注量和50.74%的测控圈需求量，因此本文提出的差异内容提取方法更适合应用于语句级差异更新。

3 结 论

1)本文提出的星载软件更新方法在程序空间优化的基础上，利用匹配路径进行差异内容提取，达到了降低更新数据量的目的。实验结果表明与传统语句级更新方法相比，本文方法可降低超过50.00%更新上注数据量，进而降低超过50.00%的测控资源需求量，大大缩短了更新上注时间。

2)通过版本引导程序设计，可实现星载软件版本灵活控制。

3)文件及程序的可靠性设计，使得更新过程能够屏蔽非法操作，保证了更新过程的安全性。