安全关键系统的栈空间分析研究

陈高锋，汤小明

(1.杨凌职业技术学院，陕西 杨凌 712100;2.西北工业大学自动化学院，陕西 西安 710072)

0 引言

根据民机适航标准DO-178B的规定，航空电子系统安全等级分为5级［1］。最高级别为安全关键级别，该级别的一个系统故障会引起飞机坠毁和人员伤亡。对于这样的系统，不仅要保证系统开发生命周期的严格可控外，还需要进行非常苛刻的系统分析，如时间分析、系统端到端延迟分析、通信分析以及空间分析等［2，7，12］。

近年来，对于航空电子系统来说，由于硬件的快速发展，特别是处理器速度的快速提升，各大飞机制造商(如波音和空客)从降低系统成本、能耗、重量以及空间等因素出发，纷纷要求或采纳综合模块化的航空电子体系结构(IMA)。

综合模块化航空电子系统要求能够将过去独立的多个具有不同安全关键级别的子系统综合到单一的硬件平台［11］。相对传统计算机，该体系要求几乎全新的系统设计、验证与分析理论和技术。而支撑该体系的核心是具备时间、空间分区的操作系统软件。

(1)时间分析方面。由于航空电子系统属于强实时安全关键系统，其正确性不仅依赖于程序的逻辑，还依赖于程序的时间特性。某一任务必须在指定的时间范围内完成，否则会导致时限缺失(Missed Deadline)。一个时间缺失可能会引起系统的失效，而且对于这种故障类型，一般是由于离线或静态时间分析的不足而引起，因此在产品运行时很难排除或恢复系统。如何对新的分区体系的航空电子系统进行时间分析，目前国内外还处在研究阶段［4］。

(2)空间分析方面。一个由于存储空间异常引起的系统故障，系统开发或维护人员很难从失效特征直接判断到根原因。如图1所示，一般故障的发生会经历故障(Fault)、错误(Error)、失效(Failure)3个阶段。故障是失效的根原因(Root Cause)，错误表示系统出现持续的不期望的行为、条件或状态，失效表示系统或部件不能满足正常的规范或需求。由故障到错误的延迟称为故障延迟(Fault Latency)，由错误到失效的延迟称为错误延迟(Error Latency)。对于存储异常，系统的故障处理机制一般只是触发系统段异常(segmentation fault)，之后提供一个 Coredump功能。Coredump能够将系统出现故障前的状态进行保存。然而，对于存储异常，如栈溢出故障，系统的失效现场一般离真正的故障点差的很远。

图1 故障-错误-失效模型

另外，存储空间异常通常会引起整个系统崩溃，对于安全关键系统，系统的实效往往会引起坠机或人员伤亡。因此，安全关键系统空间分析的重要性是显而易见的。

由于系统栈空间的分析涉及系统动态运行状态，而且目前航空电子系统领域多使用实时操作系统，操作系统的动态调度以及系统中中断触发的不确定性再次增加了对于系统栈空间分析的难度。

1 系统栈空间分析

目前，商用操作一般都要求用户在创建任务时指定任务对栈的需求大小。如图2和图3显示实时操作系统VxWorks和QNX的任务创建函数，它们在任务创建时都要求用户指定栈的大小。一般情况下操作系统或其分析工具并不能提供准确的栈需求量，因此嵌入式软件设计人员仅仅是通过局部变量使用情况进行估算，并没有考虑处理器体系、编译器、中断以及其它任务抢占等因素。由此非常容易造成栈溢出的故障。对于堆栈溢出故障，有可能出现系统崩溃(crash)或挂起(hung)，从而造成灾难性后果。

图2 VxWorks中任务创建对栈空间的需求

图3 QNX中任务创建对栈空间的需求

栈的分析是安全关键系统验证的重要组成部分，安全栈最大使用量的计算是栈分析的重要方式［6］，可以通过静态分析或动态分析的方法得到。

在用户设计中，如果没有进行确定的栈空间分析，一般都会预留足够大的闲余空间，而且既使是留了很大的空间，也并不能证明系统栈空间是可靠了。实际上，中断的触发在程序的任何点都可能发生。本文论述一种方法，该方法能够综合考虑中断的影响。由于该分析方法是基于目标代码，而非高级语言程序，因此同时考虑处理器和编译器对栈的影响。

针对不同的程序设计方法，中断对栈的影响会不同。因此，将现有系统抽象为下面2种假设。

假设1:程序由主程序和中断服务程序组成。中断不允许嵌套，也不允许抢占。栈的安全上限(Stack bound)可以由式(1)计算:

其中，depth(i)表示由中断或函数i使用栈的最大量;inti表示中断i。且有:

假设2:程序由主程序和中断服务程序组成。中断不允许自身嵌套，允许抢占。也即系统中只允许最多一个中断服务程序实例运行。栈的安全上限(Stack bound)可以由式(3)计算:

目前大多数系统都符合假设2程序的假设条件，但是由于嵌入式系统很少遇到像式(3)使用的最坏情况，所以，式(1)的计算过于乐观，而式(3)的计算过于悲观。因此，如何对程序及中断分析，从而得到安全的栈最坏使用深度(Worst Case Stack Depth，WCSD)是本文要论述的重点。

1.1 综合中断影响的栈分析过程

对栈空间的分析需要对汇编代码进行分析，同时与处理器体系相关。为此引入一种对程序的抽象方式，中断抢占图(Interrrupt Preemption Graph，IPG)。

中断抢占图是一种采用对目标码进行数据流分析(结合控制流)的方法，得到程序中可能引发的中断强占关系图。从而可以分析中断对系统栈的影响。结合程序调用可以分析软件全局栈。

中断抢占图是一个带权值的有向图。每一个边代表中断抢占，而权值代表该抢占的中断服务程序对栈的需求。

图4表示在假设1下程序的中断抢占图。其中，中断1对系统栈的单独贡献为12，中断2对系统栈的单独贡献为25，中断3对系统栈的单独贡献为7。图5表示假设2对应的中断抢占图，该图表示打开所有中断的情况。

图4 假设1对应的IPG

图5 假设2对应的IPG

栈的分析主要是对程序数据流的分析，因此需要分析出在一定输入情况下，经过对程序的符号执行(Symbolic Execution)，分析出程序运行后数据的状态。如图6所示，在程序运行后需要知道寄存器R0和R1的状态。

为此需要对程序进行建模。假设安全关键系统中没有递归调用和中断自身嵌套，因此需要跟踪程序中断屏蔽寄存器(Interrupt Mask Register)来分析程序点的栈需求情况，并且为程序PC寄存器、通用寄存器和中断相关的I/O寄存器进行建模。

图6 数据流的变化过程

目标代码或汇编代码分析器设计中，一个重要的问题是针对不同的处理器体系设计每条指令的抽象版本［5］。为此引入位格图(Bitwise Lattices)，图 7显示了1位寄存器的位格图，在该图中，1位可能的值为1、0或不能确定⊥。

图7 1位位格图

基于位格图定义了 4种操作:and、or、xor和merge，如图8所示。

图8 位格图上的操作

其中merge操作用来对控制流路径进行合并操作，例如if-then-else结构的程序，可以看出分析程序采用了保守的操作方式来合并2个分支。

基于以上的位格图及其操作，就可以分析程序的执行过程。例如:如果 A=0b11001100，B=0bXXXX1111，则有:

根据IPG，通过反向(从叶子节点到根节点)遍历IPG图就可以得到系统的WCSD，中断i的WCSD算法如下:

其中，depth(i)表示由中断 i对栈的最大贡献量;depth(i，j)表示在某程序点，中断j使能时，中断i对栈的最大贡献量。

对于如PowerPC体系的处理器，其复位中断为1号中断，因此系统的 WCSD=WCSD(1);对于AVR处理器，其复位中断为0号中断，则系统 WCSD=WCSD(0)。

在操作系统的设计中，除了使用高级语言，如C、C++、Perl等，还使用汇编代码和in-line函数。在操作系统中使用in-line函数，一般具有2个目的:

(1)减少堆栈使用，不需要压栈返回地址，标志寄存器以及函数参数。

(2)提高执行效率，程序不需要弹压栈操作，被调函数与调用函数在同一个执行环境中，以及可以更好地利用处理器寄存器等。

1.2 系统设计对栈的考虑

可以从以上的WCSD计算算法得出，如果IPG图中有循环出现，如图9所示，则使得该算法无法终止和WCSD的求解不确定。循环IPG使得栈安全的证明变得非常困难，因此在程序设计中需要避免出现导致循环IPG。

图9 带循环的IPG

循环IPG是由于中断嵌套引起的，或者说前一个中断还没有结束，后一个中断已经开始运行，因此在安全关键系统设计中，为了保证系统栈深度的确定性，最好不要使用中断嵌套。如果由于特殊需要如时钟中断，则在系统设计中需要非常小心地设计，以保证当中断强占时仍然能保证系统最大栈使用的确定性，如中断函数可重入性、最大嵌套深度确定等。

此外，IPG图中如果中断过度被抢占(IPG图的深度很大)时，需要进行优化设计。因为中断的过度抢占会使系统任务相应变慢，同时由于中断的抢占破坏了程序的局部性，增加Cache实效(Cache missing)的可能性。

图10 带中断的FCOS_domain_get_id调用图

2 系统栈分析实例

目前，业界可以使用的栈分析工具主要有Utah大学的 Stacktool［6］和 Absint公司的 StackAnalyzer［8］。StackAnalyzer是商用软件，支持多种主流处理器类型;Stacktool是一款开源的栈分析工具，目前仅支持Atmel(AVR交叉工具链)处理器。本节论述的系统栈分析是基于开源工具Stacktool进行的。为了分析代码，需要对体系结构相关的代码进行改写，主要是保留压栈和弹栈的代码，以及改变中断相关寄存器的操作和指令，删除其它汇编代码。在对被分析代码的修改过程中，尽量采用保守的方式，即如果对某个中断屏蔽位不是非常确定其为0或为1，都强行将其置为0。

本节主要论述对安全关键操作系统FCOS［2-4］的栈分析过程。FCOS通过APEX接口向上层应用提供服务，APEX接口是由航空电子标准ARINC653规定的分区操作系统为应用提供的一个功能集［9］。APEX接口提供如分区管理函数、进程管理函数、时间管理函数、分区间/分区内通信函数以及健康监控函数等，如表1所示。

表1 APEX接口

为了表述的简便，以GET_PARTITION_STATUS函数的子函数FCOS_domain_get_id()的栈分析为例，论述栈分析过程。图10显示了FCOS_domain_get_id()的调用图(Call graph)，可以看出该调用图与常见的调用图不太一样，多了一些可能会抢占FCOS_domain_get_id()的函数或中断。

图11 函数FCOS_domain_get_id的栈分析报告

采用栈分析工具对函数FCOS_domain_get_id()分析后，得到如图11的分析报告。其中正常使用的栈量表示该函数本身使用的栈大小，而最坏情况使用的栈大小表示综合考虑全系统后的情况。另外，表2还列出了部分APEX接口的栈分析报告。

表2 FCOS函数栈分析

3 结束语

对于安全关键强实时系统，如飞行控制系统、发动机控制系统、医疗设备等，系统的空间分析变得非常重要，其分析结果直接影响到系统设计和系统验证。特别是当系统像综合模块化航空电子系统，需要综合多个传统的子系统与一个单一的硬件平台时，系统的空间分析将直接关系到系统的整体规划和综合。同时由于系统集成商需要同时集成多个提供商的子系统，因此对空间分析的需求变得非常必要。本文论述一种系统栈空间分析方法，并采用该方法对安全关键操作系统FCOS的栈空间进行分析。

［1］Vance Hilderman，Tony Baghai.Avionics Certification:A Complete Guide to DO-178B(Software)，DO-254(Hardware)［Z］.Avionics Communications Inc.，2007.

［2］Tang Xiaoming，Zhu Zhiqiang，Chen Nong.A safety critical operating system towards partitioning arichecture［C］//Proceedings of International Conference on Pacific Asian A-viation and Aerospace.2010.

［3］Tang Xiaoming，Zhao Yuting，Li Yinjuan，et al.A strongly partitioned operating system model for data link networks［C］//Proceedings of the 5th International Conference on Wireless Algorithms，Systems，and Applications.2010:274-281.

［4］Tang Xiaoming，Zhang Xinguo.Timing analysis of safety critiacl operating system FCOS［C］//Proceeding of International Conference on System and Networking on Education.2011.

［5］John Regehr，Alastair Reid.HOIST:A system for automatically deriving static analyzers for embedded systems［C］//Proceedings of Proceedings of the 11th International Conference on Architectural Support for Programming Languages and Operating Systems.2004:133-143.

［6］John Regehr，Alastair Reid，Kirk Webb.Eliminating stack overflow by abstract interpretation［J］.ACM Transactions on Embedded Computing Systems，2005，4(4):751-778.

［7］Legrand J，Singhoff F，Nana L，et al.About bounds of buffers shared by periodic tasks:The IRMA project［C］//Proceedings of the 15th Euromicro International Conference of Real Time Systems.2003.

［8］Absint.StackAnalyzer:Stack Usage Analysis［DB/OL］.http://www.absint.com/stackanalyzer/，2013-08-09.

［9］ARINC 653，Avionics Application Standard Software Interface［S］.

［10］Reinhold Heckmann，Christian Ferdinand.Verifying safety-critical timing and memory-usage properties of embedded software by abstract interpretation［C］//Proceedings of the Conference on Design，Automation and Test in Europe.2005:618-619.

［11］汤小明，李引娟，程农.VxWorks在飞行管理系统中的应用研究［J］.计算机工程与设计，2011，32(3):52-56.

［12］汤小明，苏罗辉，宋科璞.飞行管理系统AADL建模与分析［J］.计算机技术与发展，2010，20(3):91-94.

［13］武华，刘军伟.基于 VxWorks的多任务程序设计［J］.计算机技术与发展，2010，21(9):163-166.

［14］程斐，苗克坚，王瑞敏.QNX与VxWorks的特性分析和实时性能测试［J］.计算机工程与设计，2008，29(18):4734-4735，4739.