基于增量链接的可回滚星载软件在轨更新方法

汪宏浩，王慧泉，金仲和

（浙江大学 微小卫星研究中心，浙江 杭州310027）

早期星载软件通常是固化的，只有部分长寿命航天器有软件在轨更新功能［1-2］.随着航天技术的发展，星载软件复杂度越来越高，存在缺陷的可能性越来越大［3］，这对于功能密度非常高的皮卫星尤为突出.因此，需要为星载软件提供在轨更新功能，修复在轨故障，延长卫星寿命［4-5］.此外，在卫星寿命末期通过软件在轨更新可以扩展卫星功能，对新任务进行在轨试验［6］.

与地面系统相比，星载软件在轨更新面临诸多挑战：如星地链路通信速率小［7］、通信时间有限，必须减少更新上注数据量；星载计算机的资源有限［8］，且须持续提供服务，因此不能执行复杂的更新算法，要减少停机时间；卫星在轨运行时无法进行人工维护，而软件在轨更新对卫星稳定运行有影响［9］，因此需要保证软件在轨更新过程的可靠性，使之具有回滚到更新前稳定状态的能力；为了修复未知缺陷，按需完成新任务，要扩大软件更新范围，保证在轨更新的灵活性.地面系统软件动态更新技术［10-13］旨在降低停机时间，更新复杂度和上注数据量均较大，需要复杂的操作系统支持，因此不适用于星载软件更新.

目前也有对星载软件在轨更新的相关研究.如将完整星载软件上注至卫星，重启系统以完成更新［14-15］，这类方法对星上软件无特殊要求，可以任意扩充软件功能，但更新数据量大，会长时间占用遥控通道，且重启会造成星上软件中断时间长.李磊霞等［6，16-17］将软件划分成多个模块，利用操作系统加载技术将修改过的模块作为补丁替换原模块，达到更新的目的.这类方法可以显著地减少上注数据量，降低遥控通道占用时间，但需要星载操作系统有模块加载功能，且需预先决定模块可否更新，降低了更新操作的灵活性.

软件更新需要对旧代码进行修改得到新代码，编译生成二进制目标代码并上注至卫星.为了避免上注数据量过大，可将新旧版本目标代码的差异部分作为上注补丁，但源代码的一个小改动会使得目标代码变动较大［18］，导致上注数据量过大.Kiyohara等［19-21］研究对差异部分压缩的算法，但解压缩算法较复杂，不适用于星载计算机.增量链接是编译器为提高链接速度提供的一种优化功能，目前大多数编译器都已实现了该功能［22］.增量链接可以使编译器仅重排修改过的函数地址，而未修改函数的地址保持不变，从而降低软件修改前、后内存空间布局的差异.利用这一特性，提取修改前、后内存空间差异部分制作补丁，星上根据补丁直接对原软件内存空间进行修改，无需重启即可完成软件在轨更新操作.

基于上述特性，结合某型号皮卫星的任务需求，本文提出一种无需重启、上注数据量小、可以任意修改或增减软件功能，并可使软件回滚至更新前状态的星载软件在轨更新方法.

1 硬件平台与软件结构划分

硬件平台采用TI的C6000系列DSP作为中央处理器.该处理器包含定时器和DMA 模块.为DSP配有2MB SDRAM 扩展内存，2 GB NAND Flash扩展外存，使用FPGA 实现看门狗和逻辑资源扩展.软件存储于NAND Flash 中，运行时被加载到SDRAM 中.

为了实现在轨更新，将星载软件分为监测程序和业务逻辑程序两部分.监测程序包含保证系统正常运行的硬件驱动程序（即驱动DSP、SDRAM、NAND Flash和FPGA 的程序）和负责实施更新操作和监控的模块，监测程序不能被更新；业务逻辑程序用于实现卫星的各项功能，如星务管理、电源管理、姿态控制运算等，该部分可以更新.具体结构如图1所示.

系统上电时监测程序首先自举加载，然后初始化DSP、FPGA、SDRAM 和NAND Flash，保证系统正常运行，接下来由更新操作模块加载业务逻辑程序，执行卫星的各项功能.在业务逻辑程序加载后，监测程序仍定时运行，用于负责业务逻辑程序的在轨更新.

为了保证监测程序不被更新，链接阶段将监测程序和业务逻辑程序置于不同的内存空间，实现物理隔离.监测程序仅对业务逻辑程序所在的内存空间实施更新操作.

图1 星载软件结构划分Fig.1 On-board software structure design

2 软件在轨更新方法

2.1 更新方法概述

一次完整更新过程如图2所示.首先在地面完成补丁制作；然后通过地面站将补丁上传至卫星，卫星解析和校验补丁；最后根据补丁信息对星上软件进行动态修改.补丁分为2类，即更新补丁和回滚补丁，分别用于在轨更新软件和使软件回滚至更新前的状态.

2.2 更新补丁制作

首先在地面上对旧版本业务逻辑代码（以下简称旧版本代码）进行修改得到新版本代码；然后通过调试和测试保证新版本代码可靠性，代码编译过程中采用增量链接形式，最后生成新版本代码的目标文件.

图2 软件在轨更新过程Fig.2 Process of on-board software upgrade

修改代码可以归纳为修改函数、修改全局或静态变量和修改复合类型（如结构体、共用体等），这些修改最终影响内存空间.由于静态变量和全局变量位于相同的内存空间，修改静态和全局变量统称为修改变量.修改函数影响内存空间的.text段，修改变量会影响内存空间的.data段和.bss段.由于复合类型信息编译后不保存至目标文件，修改复合类型会影响使用复合类型定义的变量的大小以及函数对这些变量的解析，因此修改复合类型可以归结为修改函数或变量.在更新补丁制作过程中，须考虑代码修改后函数和变量在内存空间的变化，根据变化信息制作更新补丁，用于星上软件的动态修改.

下面举例说明，假设旧版本代码包含一组函数F＝｛f1，f2，f3｝和一组变量V＝｛v1，v2｝.其中f2调用f1、f3，f3调用f1；f1使用v2，f2、f3使用v1.为方便描述，令b（x）表示x 的目标代码，s（x）表示x的大小，a（x）表示x 的地址.函数f 被放置在.text段.若变量v 未初始化，则会放置在.bss段；若v 初始化，则放置在.data段.为了简化监测程序更新操作，强制要求初始化每个变量v.这样旧版本代码编译后，所有的b（f）紧挨着放置在.text段中，所有的b（v）紧挨着放置在.data段中.

首先考虑对修改函数造成的内存空间变化.修改函数可以分为修改现有函数、引入新增函数、删除现有函数3种情况.下面举例说明增量链接情况下修改函数造成的内存空间变化情况.

当修改现有函数时，设修改函数f1得到f′1，s（b（f′1））可能出现如下情况.

当s（b（f′1））≤s（b（f1））时，b（f′1）仍放置于b（f1）空间内，增量链接无需分配新地址，即a（f1′）＝a（f1）.多余的内存空间记为空闲空间.

当s（b（f′1））＞s（b（f1））时，b（f′1）无法放置于b（f1）的空间内，增量链接为f′1分配新的地址，即把b（f′1）置于新空闲空间中.由于a（f′1）≠a（f1），而f2和f3调用f′1，需要对f2和f3中调用f′1的地址作相应修改.原有f1的内存空间记为空闲空间.上述函数内存空间的变化如图3所示.

新增函数时，假设新增了函数f4，且被f2、f3调用f4，由于f4是新引入的，因此f2、f3中须加入对f4的调用语句，从而导致f2、f3的内存空间发生变化.f2、f3的内存空间按照图3中的增量链接情形变化，而f4被分配新的内存地址，b（f4）被放置在空闲空间中.

当删除现有函数时，假设删除了函数f1，由于f1被f2、f3调用，需 要 在f2、f3中 删 除 调 用f1的语句，从而导致f2、f3的内存空间发生变化.f2、f3的内存空间按照图3的情形变化，而b（f1）所在的空间记为空闲空间.

考虑修改变量造成的内存空间变化.修改变量可以分为变量值修改、变量类型修改、引入新变量、删除现有变量4种情况.变量值修改只修改变量内存空间内容，不会影响内存空间的布局，而其他3种情况可能会影响内存空间的布局.

当修改变量值时，设修改v1的值得到v′1，由于v1的类型不变，则其大小不会改变，无需为v′1分配新的地址，即有a（v′1）＝a（v1）和s（v′1）＝s（v1），内存中只有b（a（v1））被修改为b（a（v′1））.

当修改变量类型时，设修改v1的类型得到v′1，不同类型的大小可能不一样，因此会出现如下情况.

当s（b（v′1））≤s（b（v1））时，b（v′1）仍置于b（v1）空间中，增量链接无需为v′1分配新地址，即a（v′1）＝a（v1）.多 余 的 内 存 空 间（大 小 为s（b（v1））-s（b（v′1）））记为空闲空间.

当s（b（v′1））＞s（b（v1））时，b（v′1）无 法 置 于b（v1）的空间内，增量链接为v′1分配新的地址，即把b（v′1）放置于新空闲空间中.由于f2和f3使用v′1，需要将f2和f3中v′1的地址改为a（v′1）.原v1的内存空间（大小为s（b（v1）））记为空闲空间.

上述变量内存空间的变化如图4所示.

当新增变量时，设新增了变量v3，且f2、f3使用了v3；需要在f2、f3中加入使用v3的语句，从而导致f2、f3的内 存 空 间 发 生 变 化.f2、f3的 内 存 空间按照图3 的情形变化.v3被分配新内存地址，b（v3）被放置在空闲空间中.

图3 增量链接下函数内存空间的变化Fig.3 Function memory space change under incremental linking

图4 增量链接下变量内存空间的变化Fig.4 Function memory space change under incremental linking

当删除现有变量时，设删除了现有变量v1，由于v1被f2、f3使用，需要删除f2、f3中使用v1的语句，从而导致f2、f3的内存空间发生变化.f2、f3的内存空间按照图3的情形变化.b（v1）所在的空间记为空闲空间.

最后考虑复合类型定义修改导致内存空间变化的情况.修改复合类型会影响到使用复合类型定义的变量的大小以及函数对这些变量的解析，因此修改复合类型相当于修改函数和修改变量，只需找出受影响的函数和变量，再按照对函数的修改和对变量的修改的处理方式进行即可.

上面分析了增量链接情况下对修改函数和变量造成的内存空间变化，而星上软件动态修改的本质是将星上软件的内存空间更改成地面修改后的软件的内存空间.因此，补丁需要包含代码修改前、后的内存空间的变化信息.上述变化可以用以下2类操作描述.

1）删除操作：Remove（起始地址，大小），删除操作后的空间记为无效.

2）写入操作：Write（起始地址，大小，二进制内容），写入操作后的空间记为占用.

例如图3（a）～（c）的内存空间变化可以描述如下.

1）Remove（0xC1312311，0x73）：删 除 以0xC1312311为首地址的原有函数f1的目标代码b（f1）.

2）Write（0xC13124A9，0x91，b（f′1））：将b（f′1）置于以0xC13124A9为首地址的空闲空间内.

3）Remove（0xC1312390，0x4）：删除f2中调用f1的地址.

4）Write（0xC1312390，0x4，0xC13123A9）：增加f2中调用f′1的地址.

5）Remove（0xC1312424，0x4）：删除f3中调用f1的地址.

6）Write（0xC1312424，0x4，0xC13123A9）：增加f3中调用f′1的地址.

更新补丁中只需包含上述操作信息，星上监测程序收到补丁后按照上述操作修改内存，即可完成更新.一个更新补丁中可以包含多个函数、变量以及复合类型的修改，因此会包含多个Remove和Write操作.为了减小更新补丁的大小，将所有的Remove和Write操作放置在一起，为了方便解析以及保证可靠性，为Remove和Write操作的数据加入标识头和标识尾以及CRC校验.所设计的完整更新补丁的结构如图5所示.

在图5 的更新补丁中，有一组包含m 个Remove操作的数据占用6＋6m 字节，一组包含n 个Write操作的数据占用6＋（6＋）n 字节，为二进制目标码的平均占用字节数.因此，一个更新补丁占用12＋6m＋（6＋k）n字节.

图5 完整更新补丁结构Fig.5 Structure of updating patch

在具体实施过程中，利用编译器前端识别出所有修改过的函数、变量和自定义类型的函数调用图（Call Graph），可以得到受影响的函数和变量的符号；利用这些符号，依照ELF 文件格式［23］，从可执行文件中抽取出每个受影响的函数和变量的二进制目标代码；将这些代码与原目标代码进行对比，可以获取更新补丁中所需要的信息.

2.3 回滚补丁制作

回滚操作所做的是更新操作的逆操作，即修改内存空间至最近一次更新前的状态，因此回滚补丁只需包含一个控制命令，即可以设计成卫星的一个遥控指令.遥控指令占用10个字节，具体的遥控指令设计见文献［7］.

2.4 补丁上注

由于更新补丁包含大量数据块，需要通过地面站以注入数据的方式上注至卫星.为了保证安全性和可靠性，需要约定数据帧格式［24］.

我国主要采用PCM 遥控标准，上行码速率一般为2 000bit／s［7，24］，所以设计的注入数据帧长为2 000／8＝256字节.一个补丁可能需要多个数据帧才能上注完毕，为了保证星上监测程序可以按顺序还原补丁，在数据帧格式中加入分组数和分组编码.设计的注入数据帧格式如表1所示.

表1 注入数据帧格式Tab.1 Format of injected data frame

补丁上注的过程是将制作生成的补丁按照上述帧格式打包成一个或多个注入数据帧，通过地面站将注入数据帧发送至目标卫星.

2.5 星上动态修改

为了避免数据接收引起星上任务长时间中断，星载计算机通过DMA 接收注入数据.在接收到注入数据后，监测程序根据表1的格式对数据帧进行解析和校验，在收取所有数据帧后，拼接补丁数据块形成更新补丁.具体过程如图6所示.

图6 解析和校验注入数据帧的过程Fig.6 Process of parsing and validating injected data frame

监测程序接下来要根据图5的更新补丁结构对补丁进行解析和CRC 校验.若解析失败或CRC 校验不通过，则需地面重传该补丁.解析成功且CRC校验通过后，监测程序可以得到一组Remove操作和一组Write操作.

为了能回滚至更新前的状态，监测程序需要在星上制作逆操作补丁，即为每个Remove操作生成对应的Write操作，为每个Write操作生成对应的Remove操作.把生成的Write和Remove操作按图5的更新补丁格式组织成逆操作补丁，并保存至NAND Flash中.

举例说明，操作Remove（0xC1312311，0x73）的 逆 操 作 是 Write（0xC1312311，0x73，bin（0xC1312311，0x73）），其 中bin（0xC1312311，0x73）是内存空间0xC1312311～0xC1312383 的二进制内容，意思是将删除的内容写回至原内存空间.操作Write（0xC13124A9，0x91，b（f′1））的逆操作是Remove（0xC13124A9，0x91），意思是将内存空间中写入的内容删除.

更新补丁中只包含Remove操作和Write操作，因此对星上软件作动态修改的方式很简单，即直接寻址到对应的内存空间，根据起始地址、大小进行相应的操作.具体的监测程序应用更新补丁和逆操作补丁的算法如下.

在未执行更新操作前，初始化当前程序版本号ver为0.然后监测程序获取程序控制权，根据更新补丁生成逆操作补丁并保存至NAND Flash中，再按顺序执行所有Remove操作和所有Write操作.最后将控制权交换给修改后的业务逻辑程序，并将ver加1.

同样地，需要执行回滚操作时，监测程序从NAND Flash中找到最近一次保存的逆操作补丁，解析并按图7所示的算法执行，并将ver减1.在执行逆操作时不需再生成逆操作的逆操作补丁，因为逆操作的逆操作即为之前的更新操作.

2.6 出错情况应对

为了应对程序跑飞和掉电重启等出错情况，监测程序保留每个更新补丁和逆操作补丁.

若更新过程出现程序跑飞，导致看门狗将整星软件复位或整星掉电重启，则需要重新加载星载软件.监测程序会首先加载最原始版本的业务逻辑程序，并按更新顺序应用ver次更新补丁，将业务逻辑程序恢复到出错前的版本.若恢复过程中依然出现程序跑飞或整星重启等问题，则将ver减1，再执行一次恢复过程，直到ver为0时为止.具体算法如下.

3 试验验证

基于某型号皮卫星星载计算机平台，对所提出的软件在轨更新方法进行试验，主要针对补丁大小、上注时间、更新操作执行情况、回滚操作执行情况和更新出的应对情况进行测试.

虽然试验是在地面进行，但为了模拟星地链路通信速率，补丁通过地面站以2 000bit／s的PCM遥控模式上注.

3.1 更新和回滚操作试验

原始版本业务逻辑程序的目标代码大小为275 kB，进行了4 次版本修改，共得到4 个更新补丁.表2显示了更新补丁应用的试验结果，包含每个版本目标代码大小、更新补丁大小、补丁上注时间、代码修改信息和补丁包含的Remove操作数m、Write操作数n和二进制目标码的平均字节数.

在星上运行版本4程序时，上注回滚补丁（即发送用于回滚的遥控指令），星上业务逻辑程序成功回滚至版本3.

表2的结果表明，该方法的更新和回滚操作功能正确，更新补丁大小远小于目标代码大小，补丁上注时间仅为秒级.其中，即使版本4相对于版本3进行了大量修改，补丁上注时间也仅为46s.与上注完整软件的软件在轨更新方法相比，采用该方法显著减小了上注数据量，降低了上注时间.

3.2 更新出错试验

试验时星上运行版本3程序.为了模拟各类出错情况，对上注数据出现误码、更新的软件存在缺陷使得程序跑飞、更新过程中整星断电这3种出错情况进行模拟.

出错情况1：上注数据误码.在注入数据帧中随机注入多比特错误，再将注入错误后的数据上注至卫星，观察其更新状态.

出错情况2：更新软件存在缺陷使程序跑飞.故意修改版本4代码使之随意修改.text段而使程序跑飞，再将该版本的代码制作成更新补丁上注至卫星，观察其更新状态.

出错情况3：在更新过程中整星断电.在星上执行更新操作的时候人为重启整星.一般情况下为单次重启.在实际中可能会出现更新至上一个版本时仍发生整星断电的情况，为了更好地模拟实际情况，引入多次重启操作，即在重启后的系统恢复过程中，再次实施重启操作，该重启操作不断实施20次，并观察其更新状态.

上述出错试验的结果如表3所示.结果表明，该方法能够成功应对各种更新出错情况，满足任务需求.

表2 更新补丁应用试验结果Tab.2 Experiment result of performing updating patch

表3 更新出错试验结果Tab.3 Experiment result of exception simulations

4 结 语

本文基于编译器的增量链接特性，提出一种无需重启、上注数据量小、并且可回滚至更新前状态的星载软件在轨更新方法.该方法将更新操作归结为内存空间的写入操作和删除操作，能够随意修改或增减星载软件功能，简化了补丁的结构和星上监测程序的更新操作过程，并能够回滚至更新之前的状态.试验结果表明，利用本文方法进行更新，补丁上注时间短，更新操作正确，回滚操作有效，并成功应对各种更新出错情况.本文方法高效可行，具有较好的安全性，可以应用在包括皮卫星在内的各种航天器中.

（

）：

［1］包海超，杨根庆，李华旺.小卫星星载软件微内核的设计［J］.计算机工程，2008，34（9）：81-82.BAO Hai-chao，YANG Gen-qing，LI Hua-wang.Micro kernel design of small satellite software［J］.Computer Engineering，2008，34（9）：81-82.

［2］ZHANG Y，JIANG J.Bibliographical review on reconfigurable fault-tolerant control systems［J］.Annual Reviews in Control，2008，32（2）：229-252.

［3］LEVESON N G.Role of software in spacecraft accidents［J］.Journal of spacecraft and Rockets，2004，41（4）：564-575.

［4］张然峰，郝贤鹏，金龙旭，等.空间相机软件在轨重注方法研究与实现［J］.光机电信息，2011，28（6）：30-34.ZHANG Ran-feng，HAO Xian-peng，JIN Long-xu，et al.Study and realization on method of software in space camera on-board reprogramming ［J］.OME Information，2011，28（6）：30-34.

［5］ROSA J，CRAVEIRO J，RUFINO J.Exploiting AIR composability towards spacecraft onboard software update［C］∥Actas do INForum-Simposio de Informatica.Braga：［s.n.］，2010：675-686.

［6］李磊霞，王宇，林宝军，等.基于宏定义动态链接的模块化星载软件升级方法研究［J］.空间科学学报，2010，30（2）：180-184.LI Lei-xia，WANG Yu，LIN Bao-jun，et al.Research of software updating for micro-satellite in the orbit based on dynamic link with macros［J］.Chinese Journal of Space Science，2010，30（2）：180-184.

［7］GJB 1198.1A-2004，航天器测控和数据管理第l部分：PCM 遥控［S］.北京：国防科学技术工业委员会，2004.

［8］杨牧，王昊，张钰，等.抗辐射加固的皮卫星用实时操作系统设计［J］.浙江大学学报：工学版，2011，45（6）：1021-1026.YANG Mu，WANG Hao，ZHANG Yu，et al.Design of radiation-hardened real-time operating system for pico-satellite［J］.Journal of Zhejiang University：Engineering Science，2011，45（6）：1021-1026.

［9］BUTLER R，PENNOTTI M.The evolution of software and its impact on complex system design in robotic spacecraft embedded systems ［J］.Procedia Computer Science，2013，16：747-756.

［10］KIM D K，TILEVICH E，RIBBENS C J.Dynamic software updates for parallel high-performance applications［J］.Concurrency and Computation：Practice and Experience，2011，23（4）：415-434.

［11］NEAMTIU I，HICKS M，STOYLE G，et al.Practical dynamic software updating for C［C］∥Proceedings of the 2006 ACM SIGPLAN Conference on Programming Language Design and Implementation. New York：ACM，2006：72-83.

［12］HICKS M，NETTLES S.Dynamic software updating［J］.ACM Transactions on Programming Languages and Systems，2005，27（6）：1049-1096.

［13］KIM D K，TILEVICH E，RIBBENS C J.Shortening time-to-discovery with dynamic software updates for parallel high performance applications［R］.Virginia Tech：Department Of Computer Science，2009.

［14］STEIGER C，FURNELL R，MORALES J.OBSM operations automation through the use of on-board control procedures［C］∥Space OPS 2004Conference.Montreal：AIAA，2004：1-15.

［15］徐伟，朴永杰.航天相机控制器在轨软件重注［J］.光电工程，2013，40（4）：65-71.XU Wei，PIAO Yong-jie.Re-injection technology for software in aerospace camera controller on orbit［J］.Opto-Electronic Engineering，2013，40（4）：65-71.

［16］安军社，刘艳秋，孙辉先.软件的动态维护与实现［J］.计算机工程，2003，29（2）：238-239.AN Jun-she，LIU Yan-qiu，SUN Hui-xian.Implementation of on-board software maintenance［J］.Computer Engineering.2003，29（2）：238-239.

［17］THI A T，TSO K S，ALKALAI L，et al.On-board guarded software upgrading for space missions［C］∥Proceedings of the 18th Digital Avionics Systems Conference.St Louis：IEEE，1999：7.B.4-1-7.B.4-8.

［18］LI W，ZHANG Y，YANG J，et al.UCC：update-conscious compilation for energy efficiency in wireless sensor networks［C］∥Proceedings of the 2007ACM SIGPLAN Conference on Programming Language Design and Implementation.New York：ACM，2007：383-393.

［19］KIYOHARA R，MII S，MATSUMOTO M，et al.A new method of fast compression of program code for OTA updates in consumer devices［J］.IEEE Transactions on Consumer Electronics，2009，55（2）：812-817.

［20］BELLAACHIA A，RASSAN I A.Efficiency of prefix and non-prefix codes in string matching over compressed databases on handheld devices［C］∥Proceedings of the 2005 ACM Symposium on Applied Computing.New York：ACM，2005：993-997.

［21］BESZÉDES Á，FERENC R，GYIMÓTHY T，et al.Survey of code-size reduction methods［J］.ACM Computing Surveys（CSUR），2003，35（3）：223-267.

［22］田祖伟，杨恒伏，罗阳旭.基于增量链接的PE文件信息隐藏技术研究［J］.计算机科学，2012，39（12）：91-93.TIAN Zu-wei， YANG Heng-fu， LUO Yang-xu.Research of PE file information hiding based on incremental link［J］.Computer Science，2012，39（12）：91-93.

［23］TIS C.Executable and linking format（ELF）specification［S］.［S.l.］：Tool Interface Standard Committee，1995.

［24］何熊文.一种通用遥控注入数据格式的设计与应用［J］.航天器工程，2008，17（1）：94-99.HE Xiong-wen.Design and application of a common spacecraft telecommand data format ［J］.Spacecraft Engineering，2008，17（1）：94-99.