基于行为监测的嵌入式操作系统堆栈溢出测试*

杨兴达,陈 灿,方 菱

(1.安徽大学物质科学与信息技术研究院，安徽 合肥 230000；2.中国科学院合肥物质科学研究院，安徽 合肥 230000)

1 引言

嵌入式操作系统是一种面向安全关键的系统，其堆栈安全至关重要。丰田的凯美瑞车型曾发生过严重的意外加速UA(Unintended Acceleration)事故，事故就是由于堆栈溢出造成TASKX死亡所导致的[1]。堆栈溢出通常难以捕捉，因为异常暴露的时间可能滞后于其发生时间。例如，任务P的堆栈溢出，并侵占优先级较低的任务Q的私有堆栈，则至少在任务Q被调度并运行前，系统看起来一切正常。当任务Q显露异常时，开发者难以确定此异常是由任务Q本身造成的还是由其它任务的堆栈溢出引起的，更难以定位造成堆栈溢出的具体代码[2]。另外，为了避免堆栈溢出，开发者经常会无意识地过度分配堆栈，而嵌入式系统是一种资源受限的系统，堆栈资源的浪费将会增加随机存取存储器RAM(Random Access Memory)的成本。在理想的情况下，开发者为各任务堆栈预分配的空间应该略大于该任务实际使用堆栈的极大值。但是，人为地预估堆栈空间十分困难，也无法保证预估结果的准确性。

2 相关研究

关于堆栈溢出测试，相关研究人员进行了一定的研究。

Zhang等人[3]定义了一种用于描述函数间调用行为的树形结构，并通过在树形结构中提取极端树的方式来计算堆栈使用的极大值，从而避免可能的堆栈溢出问题。这种方法虽然可以静态地对系统堆栈进行评估，但是其分析过程比较复杂，需要人为考虑所有的极端情形并绘制函数树模型，且每种函数树的模型都不尽相同，导致此方法在实际工程测试中不够高效。

Xie等人[4]提出了一种算法，可以将堆栈溢出的检测问题转化为整数范围的分析问题。该算法先使用函数定位模块计算代码检测范围，然后将调用函数与风险函数库中的函数进行比对，以扫描检测范围内所有的风险函数，最后通过对风险函数的参数进行分析来准确计算当前函数所需堆栈是否会溢出。该算法仍具有一定的局限性，因为它十分依赖风险函数库。如果被调函数不在风险函数库中，或者造成堆栈溢出的只是一条赋值语句而非函数，那么该算法就会失效。

Choi等人[5]提出了一种基于静态分析配置文件的堆栈最大值动态监测方法。该方法首先通过分析可执行与可链接格式ELF(Executable and Linkable Format)文件提取与函数相关的数据，然后使用深度优先搜索DFS(Depth First Search)确定堆栈最大值，最后通过监测堆栈最大值的地址是否被改写来捕获堆栈溢出。该方法虽然可以动态地发现堆栈溢出，但是不能定位溢出位置。

针对相关研究中存在的不足，本文提出了一种基于实时堆栈分配与回收行为监测的动态堆栈测试方法。首先，静态地确定堆栈行为测试点；接着在测试点上采用一套标准的数据采集与分析流程进行堆栈监测，无需对不同测试点进行特殊改动，在测试效率上有所提高，并在静态分析方法上进行了动态补充；其次，通过插桩来覆盖源代码中所有的堆栈行为测试点，并不依赖于任何第三方库，不会出现失效问题;最后，不仅可以通过堆栈指针SP(Stack Pointer)地址判定堆栈溢出，还能够实时定位发生溢出的源代码，对堆栈溢出测试的功能性进行了拓展。

3 堆栈行为动态监测方法

本节将介绍任务堆栈分配与回收行为实时监测方法的总体设计与具体实现。

3.1 相关技术概述

下面将简单介绍后文所提及的相关技术。

(1)静态测试与动态测试：在嵌入式软件测试中，静态测试是基础，动态测试是必要补充[6]。静态测试往往是通过提取源代码编译生成的汇编代码或二进制代码中的一些特征进行分析，或者构建模型后对模型进行测试验证。比如Fang等人[7]先通过形式化方法建模并验证模型，然后再根据模型开发测试用例生成器，对嵌入式实时操作系统进行了高效的测试验证。动态测试则是通过某种方式获取程序运行时的轨迹信息进行分析[8,9]。动态测试所发现的漏洞是软件中实际存在的，不会误报，并且动态测试不需要像静态测试那样进行复杂的数据流分析[10]。

(2)软件插桩技术：软件插桩是一种在软件运行时进行的状态分析技术，广泛应用于软件质量评价、漏洞挖掘、性能分析与优化等领域中，是解决软件执行路径收集、关键函数调用分析等问题的主要手段[11,12]。

(3)HOOK技术：HOOK是一种操作系统内部的回调函数，会在特定的事件到来之际被回调执行。

(4)控制器局域网络CAN(Controller Area Network)协议：CAN是一种用于实时应用的串行通信协议总线，可用于汽车中各种不同元件之间的通信。

(5)分布式处理：将位于不同地点或具有不同功能或拥有不同数据的多台计算机通过通信网络连接起来，协调地完成信息处理。

3.2 测试框架概述

本文方法首先静态分析了源代码中所有可能的测试点。对于堆栈溢出测试来说，测试点就是具有堆栈分配或回收行为的代码行。接着，通过软件插桩技术在测试点插入用于采集堆栈数据的桩函数接口。开发者在编写代码时就可以自行插桩，以减轻测试者的负担，桩函数的插入逻辑和编码行为类似于HOOK函数。

插桩后，桩函数应在被测系统实际运行时动态收集测试点的堆栈数据并进行实时分析。为了规避数据分析给操作系统带来的额外工作负荷，本文方法采用了分布式处理的设计思想来进行数据分析，即被测系统仅采集数据，数据分析的工作则交由另一台机器负责。被测系统在完成数据采集后立即将数据传送给上测试器UT(Upper Tester)，再由UT完成实时的数据分析和溢出判定工作。另外，测试数据的统计和堆栈溢出的报警服务也由UT提供。

因为本文方法的被测系统通过CAN进行数据传输，其在传输超过8字节的数据时需要分包，为了进一步降低数据传输对操作系统运行效率的影响，本文方法将采集到的数据压缩成8字节长度的测试码，具体的测试码设计规则将在3.4节中介绍。最后，UT根据测试码的设计规则来反向解析，得到实时的堆栈数据，并进行堆栈溢出判定。当堆栈溢出发生时，测试者可以通过UT实时发现异常，并根据测试点的信息来定位源代码中造成堆栈溢出的确切位置。本文方法的测试流程如图1所示，测试架构如图2所示。

徐进步站在一个塔头上,一点也不知道身后背包里一长截手纸垂下来了。上海女知青谢菲站在另一个塔头上,用上海话朝他喊:“你把你那尾巴卷起来行不行,拖那么长尾巴,演大老鼠啊!”

Figure 1 Workflow diagram of the proposed method图1 本文方法工作流程图

Figure 2 Test frame of the proposed method图2 本文方法测试框架图

3.3 消除数据解析延迟的影响

测试码由被测系统发送至UT显然需要时间，且UT的解析反馈也会造成无法避免的延迟。为了消除延迟对测试的实时性影响，本文方法的测试码包含了详细的堆栈异常信息，其中包括发生异常的任务内部函数编号，使得UT只依靠延迟收到的测试码也能准确定位到发生堆栈溢出的代码位置。

3.4 基于堆栈结构与行为确定测试点

本文方法中被测操作系统进行任务堆栈分配时，会由高地址向低地址递减分配，不同任务的私有堆栈空间被静态确定后，在物理地址上是连续的，如图3所示。

Figure 3 Physical structure diagram of task stack图3 任务堆栈物理结构图

每一块任务私有堆栈都是由3个区域组成的，如图4所示。A区域用于存放静态数据，如普通指针、数组和常量等；B区域是任务的内部函数被调用时所申请的一块空间，可以在被调用函数返回后回收再利用；C区域只有一个魔术数字，被用作堆栈溢出检测。其中，B区域的F1和F2是2个不同的函数，F2在F1的调用返回后重用了F1的堆栈空间。F1.1是F1内部调用的一个函数，其堆栈是紧接着F1的栈顶分配的。图4中的P1、P3、P5是具有堆栈分配行为的测试点，P2、P4则是具有堆栈回收行为的测试点，操作系统各任务中的每个测试点都需要被监测。另外，中断服务程序ISR(Interrupt Service Routines)的堆栈行为与普通函数一致。对于A区域来说，其堆栈的分配行为在编译器编译完成后就已经确定了，故A区域只需要一个测试点就可以监测整个静态数据区的堆栈情况。

Figure 4 Example of task stack allocation and reuse behavior图4 任务堆栈分配与复用行为示例

在测试点插桩后，桩函数会将相应的测试码通过CAN发送出去，每个任务都需要额外承担发送测试码的工作，所以每个任务的执行时间会加长，并且执行用时与测试点数量成正比。因此，本文通过一个全局宏开关来控制测试点桩函数的有效性，只有在测试模式时，宏开关才会被打开，桩函数才会得到执行。

3.5 堆栈数据压缩与测试码设计

测试码需要记录各种不同的测试资源，本文方法将测试码的8字节作为8个数位以最大范围地表示这些资源。

操作系统中每个任务的堆栈空间都是静态分配的，从任务堆栈的起始地址(栈底，高地址，变量名为BOS)计算出其结束地址(栈顶，低地址，变量名为TOS)。因此，测试码需要记录BOS，而任务堆栈的静态分配大小是已知的，无需记录。另外，测试码还需记录当前任务SP的实时地址，用于判定堆栈是否溢出，正常堆栈的SP应该在[BOS,TOS]。最后，测试码还应记录任务中实时调用的函数信息，以在堆栈溢出时确定源代码中发生异常的具体位置。鉴于某些函数签名十分冗长,本文方法为各任务中的函数建立了映射，以数字而非字符串来标识不同的函数，使得测试码能够以较大的进制在有限的数位上表示更大的数据范围。测试码中各数位的职能信息如表1所示。另外，被测系统中的堆栈地址都具有0x40000000大小的固定偏移，为了压缩数位空间，本文方法在采集堆栈地址信息后会移除偏移，以缩小数据范围。例如，UT接收到的16进制测试码“10 5C 10 04 30 30 30 34”表示当前任务已经回收了编号为4的函数所申请的堆栈空间，并且当前SP的地址为0x40001004，当前任务的堆栈上界为0x4000105C。

Table 1 Bit mapping table of test code

3.6 UT设计

UT接收到测试码后，会解析测试码并得到各个数位的信息。被测系统中测试所需的有效信息都应在UT中备份，这样UT在进行数据分析时无需被测系统介入。另外，UT除了监测堆栈溢出，还需要比对任务在调用函数前后的SP记录，以保证堆栈回收的正确性。如果某测试点的SP在堆栈分配前后不一致，则说明堆栈回收过程出现了异常，此时UT不能直接定位异常代码，测试者需要排查其余任务的堆栈溢出异常来确定此回收异常的原因。

4 实验与分析

本文通过对基于MPC5748G芯片的车载远程信息处理器T-BOX(Telematics BOX)系统进行堆栈溢出测试，发现了如下问题:在1 ms周期性任务中，虽然没有发生堆栈溢出，但是其堆栈被静态分配得过大，造成了系统资源的浪费;在500 ms周期性任务和全球定位系统GPS(Global Positioning System)任务中，利用本文方法定位到了3处堆栈溢出。

具体地，在500 ms任务的数据打包函数中，开发者申请了一块数组空间用于业务数据采集，当数组容量达到阈值时会打包上传当前数据并清空数组以复用。但是，程序在擦除旧数组时发生了问题，导致数组前10个索引上的数据没有被清除。随着系统的持续运行，未被清除的垃圾数据越积越多，最终造成了任务堆栈溢出，系统被强制复位，RAM数据全部丢失。本文方法准确地定位到了这个异常，并且发现此异常溢出的数据覆盖了与500 ms任务堆栈相邻的任务中的部分数据。GPS任务中的1处堆栈溢出则是由于函数递归调用嵌套太深导致的，因为开发者在静态分配任务堆栈时忽略了递归与ISR所需的堆栈空间，溢出直接造成了系统崩溃。另外，开发者违反了MISRA-C标准，该标准明令禁止任何直接的和间接的递归函数调用。

在修正了堆栈异常的代码后，500 ms任务和GPS任务实际使用的堆栈极值分别为228和164。这2个任务中共有10个由极端环境触发的硬件保护函数未被执行，导致测试点未触发完全。通过估计并补偿这部分函数所需的堆栈空间，本文方法最终将500 ms任务和GPS任务静态分配的堆栈大小优化至242和190。

测试发现的全部堆栈异常信息如表2所示；操作系统中部分任务堆栈空间的静态分配值和实际使用极大值对照如图5所示；测试统计数据和相关优化如表3所示。

Figure 5 Comparison diagram of actual space used by task stack图5 任务堆栈实际使用空间对照图

Table 2 Exception information table of task stack表2 任务堆栈异常信息表

Table 3 Statistics table of test data

5 结束语

本文针对嵌入式操作系统的堆栈安全问题，提出了一种基于实时堆栈分配与回收行为监测的动态堆栈溢出测试方法。该方法不依赖于任何第三方库，且不会产生误报，解决了嵌入式操作系统堆栈溢出测试的实际工程问题，在实验中精确定位到了3处堆栈异常，并检测到1处受其它任务堆栈溢出影响而导致的数据覆写异常。实验结果表明，使用该方法动态监测嵌入式操作系统中的实时堆栈溢出问题是可行且有效的。另外，本文的测试结果可以指导操作系统任务堆栈的静态分配。通过对全部6个操作系统任务插入232个测试点，本文方法共监测了232个函数，并在测试后对异常代码进行了修正，对静态分配过大的堆栈空间进行了优化。最后，将1 700个双字的任务RAM优化到了1 071，即压缩至原RAM空间的63%，开发者可以利用空余出的堆栈为操作系统增添一些新任务，或者更换RAM更小的设备以降低硬件成本。在未来，重点研究一种自动化的插桩工具，用于改善开发者或测试者需要主动执行代码插桩的情形，以提高测试效率。