一种用于分析MCS-51目标码堆栈深度的方法

张西超，郭向英

(北京控制工程研究所，北京 100190)

一种用于分析MCS-51目标码堆栈深度的方法

张西超，郭向英

(北京控制工程研究所，北京 100190)

在嵌入式软件中，针对目标码的堆栈分析是堆栈检查的常用手段.提出了一种用于MCS-51系列处理器目标码的堆栈深度分析方法，该方法可分析最坏情况下的堆栈深度，并考虑了不同优先级下中断服务程序对堆栈的影响.利用该方法可开发出分析MCS-51目标码的堆栈分析工具，其分析结果对堆栈安全检查和优化具有参考意义.

MCS-51; 目标码; 堆栈分析; 堆栈深度

在嵌入式系统中，堆栈溢出往往会给系统造成致命的危害[1].检查堆栈深度的方法可分为动态和静态两类.动态方法[2]是运行被测软件，测得的最大堆栈深度通常小于软件的实际最大堆栈深度[3].静态方法是在不运行被测软件情况下，分析堆栈深度，是一种更为可靠的方法.文献[3]所述的堆栈分析方法采用了递归计算方法，根据数据流递归分析每个地址的堆栈深度，从而确定目标码的最大堆栈深度，但由于该方法未提取子程序信息，所以不能获得每个子程序的最大堆栈深度以及最大堆栈深度形成的路径，并且当目标码包含动态跳转、不平衡循环等情况时无法使用该方法.

本文提出的方法不使用递归计算，在分析目标码最大堆栈深度的同时分析出各个子程序最大堆栈深度和最大堆栈深度形成的路径，同时提出了目标码包含动态跳转、不平衡循环等情况时的应对措施.

1 堆栈深度分析方法

该方法的分析思路是根据MCS-51系统处理器的堆栈结构特点，先基于目标码构造出子程序的调用关系图，再逐个分析每个子程序的最大堆栈深度，最后求出整个程序的最大堆栈深度.

1.1MCS-51系列处理器的堆栈特点

MCS-51的堆栈位置是可编程的，栈指针SP是一个8位专用寄存器，指示堆栈顶在内部RAM块中的位置.系统复位后，SP被初始化为07H，使得堆栈事实上默认由08H单元开始.由于MCS-51内部RAM的08H～1FH单元分属于工作寄存器区1～3，最好把SP值该置为1FH或更大的值[4].

但是，SP的初始值越大，可用的堆栈深度就越小；反之，SP的初始值越小，可用的堆栈深度就越深.在MCS-51的指令系统中，除了可以直接改变SP值的指令外，如MOV, SP, #1FH，在执行PUSH、POP、各种子程序调用、中断影响、子程序返回RET和中断返回RETI等指令时，SP值将自动增加或减少.

1.2子程序调用关系图构建方法

子程序调用关系图的构建过程是对目标码进行遍历，找出所有的子程序并构建它们之间的调用关系.在MCS-51目标码中寻找子程序的关键点是寻找子程序调用指令，即ACALL和LCALL指令，指令的目的地址即为子程序入口地址.

这里采用了深度优先的方法遍历目标码，从程序的入口地址开始分析，遍历所有分支，记录每个遇到的ACALL或LCALL指令，取出其目的地址，该地址即为子程序的入口地址.以图1所示为子程序分支结构图为例，按照深度优先方法，先分析分支①②③⑤，其次分析分支①②③⑥，最后分析分支①②④.

图1 子程序分支结构图

分析主程序后，便形成了最上层的调用关系图，然后依次类推，再逐个分析次层子程序，直至不再有新的子程序产生，具体过程可概述如下：

1)采用深度优先的方法从入口地址开始分析主程序，记录其调用的子程序，分析完成后将主程序标记为已分析，子程序均标记为未分析；

2)遍历没有被分析的子程序，记录其调用的子程序，分析完成后将该子程序标记为已分析；

3)重复步骤2直至所有的子程序均被标记为已分析；

4)根据记录的信息，形成调用关系图，最上层是主程序，最下层是扇出为0的子程序.

根据上述方法可快速构建出子程序调用关系图，为计算堆栈深度提供了基础.需要注意的是，分析某些目标码时上述方法会遇到障碍，下面介绍这些特殊情况及处理方法.

1.3子程序堆栈深度分析

在介绍子程序堆栈分析方法之前，先定义几个表述子程序堆栈深度的名词：路径、路径平衡度、路径堆栈深度、子程序平衡度和子程序堆栈深度，含义分别如下：

1)路径：从子程序入口开始，沿子程序内的某一控制流执行，直到出现RET(或RETI)指令，此时所经历的所有语句便组成了一条路径.

2)路径平衡度：相对于进入路径第一条语句时的堆栈深度，沿路径执行到最后一条指令时产生的堆栈偏移量便是该路径的平衡度.如果路径中含有子程序调用指令，被调子程序的平衡度计入本条路径，如果路径产生的偏移量为-2(RET和RETI指令对堆栈的影响均为-2)，则认为这是一条平衡路径.以表1中的路径为例，其路径平衡度计算方法是：-2=1+2+(-2)+(-1)+(-2)，等号右边的数字分别是PUSH、ACALL、子程序SUBP平衡度、POP和RET对堆栈的影响.

3)路径堆栈深度：从路径的起点开始，执行至终点过程中达到的最大堆栈深度，即为路径堆栈深度.如果路径中包括了函数调用指令，函数的堆栈深度也计入该路径堆栈深度.以表1中的路径为例，路径堆栈深度计算方法是：8=1+2+5，等号右边的数字分别是PUSH、ACALL指令对堆栈的影响及子程序SUBP的最大堆栈深度.

子程序平衡度：这里将子程序的平衡度定义为其所有路径中路径平衡度的最大值，如果该值为-2，那么这是一个平衡子程序.

子程序堆栈深度：即子程序所有路径中路径堆栈深度的最大值.

表1 子程序路径

分析程序堆栈时，首先根据子程序调用关系图确定子程序调用层次，当一个子程序出现在不同的层次时，将其归类在较低的层次，同时将其调用的子程序放在更低的层次.如子程序A调用了子程序B和C，子程序B调用了C，那么C应该处于B的下层.

在子程序层次确定后，先分析深层次子程序的堆栈，然后依次类推，直至主程序(主程序也可视为特殊的子程序，扇入为0).采用这种自下而上过程的优点是分析一个子程序时，其所调用的子程序(如果扇出不为0)的平衡度和堆栈深度均已知，其对堆栈的影响可直接计入当前所分析路径，当一个子程序被多次调用时，可避免重复分析.

与构造调用关系图的过程类似，分析堆栈深度仍采用深度优先的方法.不同的是前者仅关注子程序调用指令，这里需要计算路径中所有影响堆栈的指令，具体步骤如下：

1)根据深度优先的原则，分析第一条路径的堆栈深度，并记录路径上各条指令所在地址的堆栈深度值.该路径分析结束后，设置子程序平衡度为第一条路径的平衡度，子程序堆栈深度为第一条路径的堆栈深度.

2)分析后继路径，如果该路径上指令已经被分析过，且在当前路径上该指令所在地址的堆栈值小于记录的堆栈值，停止分析该路径；否则更新该条指令所在地址的堆栈深度值，继续分析该路径上后继指令.

3)根据步骤2)中分析出的路径平衡度与堆栈深度更新函数的平衡度和堆栈深度.

4)重复步骤2)、3)直至分析完所有路径.

这个过程的优点是能够尽早排除那些不可能产生最大堆栈深度的路径，避免做无用分析，同时，由于按照调用层次自下而上分析子程序，每个子程序只须分析一次.但与构建程序的调用关系图一样，在分析某些包含特殊情况的路径时会遇到障碍.

2 不确定因素分析及应对措施

前文已经提到，有些特殊情况无法使用上面提到的方法进行分析，下面介绍这几种情况及解决方案.

2.1不确定因素分析

(1)动态跳转：MCS-51有一条间接长转移指令，格式为：JMP @A+DPTR.该指令的转移地址由数据指针DPTR和累加器A的内容相加形成，从目标码难以确定转移地址，影响子程序调用关系图的构建，因此无法按照上面的步骤完成分析.

(2)递归：在构建子程序调用关系图时可以检测出递归程序，但无法确定递归次数，因此无法计算其堆栈深度.如果一个子程序调用了一个递归子程序，调用递归程序的路径无法确定堆栈深度，因此子程序的堆栈深度也无法确定，依次类推，主程序的堆栈深度也不能确定.

(3)不平衡循环：这里的不平衡循环指循环体不是堆栈平衡的，循环对堆栈的影响会随着循环次数的变化而变化，如下面的循环，每循环一次堆栈就会加1，仅仅基于目标码做静态分析难以确定其对堆栈的最终影响.如果函数包含了不平衡循环，那么将无法直接利用1.2节所介绍的方法对其进行分析.

REL: PUSH A

DJNZ R0, REL

(4)直接改变SP指令：在MCS-51系统中，有一些可以改变SP值的指令，如MOV、INC、ANL等指令，均可以修改SP的值.由于本文介绍的方法为子程序计算出的堆栈深度是相对值，即相对子程序入口点的堆栈深度.当子程序中包含直接改变SP的指令时，无法确定与入口间的相对值，因此不能用该方法.但MOV SP,#data指令仅在主程序中时，该方法依然适用.因为主程序入口堆栈始终为0，相对堆栈深度即实际的堆栈深度，因此依然可以使用该方法进行分析.

2.2应对措施

针对上节提出的几种不确定因素，可使用下面两种方法解决：

(1)人工辅助：尽管上几种不确定因素会影响分析，但都可以被检测出来，因此可以使用人工辅助的方法.检测到异常情况时，可由测试人员分析上下文，辅助堆栈分析程序完成后继工作.为减少人工干预的工作量，可使用抽象解释[5]方法强化该方法，增强易用性.

(2)编程规范约束：由于MCS-51堆栈资源非常有限，最大堆栈深度为128字节，再除去为数据区保留的空间，实际可用堆栈尚不足128字节.因此，定义编程规范来约束开发人员，尽量避免使用可能造成堆栈溢出指令，是具有实际意义的.

动态跳转指令使程序的控制流变得不确定，因此应该尽量少用；递归函数的每次递归调用都会使用子程序调用指令，即使堆栈深度增2，堆栈开销很大；不平衡循环由于对堆栈的影响都循环次数的影响，很容易造成堆栈溢出；在子程序中直接修改SP时，在不同的地方调用该子程序会对堆栈产生不同的影响，也需要慎用.

鉴于上述几种不确定因素对堆栈安全的危害性比较大，因此，可考虑制定编程规范对这几种情况进行约束，如一旦检测到目标码中存在不平衡循环，可直接认定软件出现了问题[6].

3 中断对堆栈的影响

中断程序有其独立的入口地址，在从主程序开始构建调用关系图时无法将中断程序纳入其中.但可以将其视为一个特殊的独立程序，采用与主程序相同的分析过程单独分析其最大堆栈深度.

MCS-51共有6个中断，分别是外部中断0、定时器0、外部中断1、定时器1、串行口、定时器2，共2个优先级，可通过软件配置每个中断的优先级高低，低级中断允许被高级中断打断.由于MCS-51的中断服务程序没有使用独立堆栈空间，因此可以分为下面两种情况计算软件的最大堆栈深度：

(1)软件使用了一个级别的中断

最大堆栈深度=主程序最大堆栈深度+中断服务程序堆栈深度的最大值；

(2)软件使用了两个级别的中断

最大堆栈深度=主程序最大堆栈深度+高级中断服务程序堆栈深度的最大值+低级中断服务程序堆栈深度的最大值；

采用这种方法计算的缺点是没有考虑中断的开关情况，由于软件中经常会有关中断事件，所以主程序和中断服务程序堆栈深度同时达到峰值的情况可能并不会出现.如果考虑开关中断情况，平均来说，分析出的堆栈值比直接进行堆栈叠加小35%[7].

4 实验验证

基于上面的论述，可知即使出现动态跳转等不确定因素，也可以人工辅助完成分析.作者正是基于该方法开发了堆栈分析工具，其分析流程大致如下：

1)选择被分析软件使用的中断及优先级；

2)构建主程序的调用关系图，如果构建过程中出现了动态跳转，工具提示动态跳转的位置信息，等待人工确定跳转地址；

3)如果人工确定了跳转地址，那么继续分析，直至构建出完整的调用关系图；否则分析失败，退出；

4)计算主程序和各个子程序的堆栈深度，同时检测是否有递归子程序，以及子程序中是否包含不平衡循环和直接修改SP的指令；

5)如果子程序中包含递归、不平衡循环或直接修改SP的指令，分析失败，退出；

6)按照上面的步骤分析各中断服务程序对堆栈的影响；

7)根据中断优先级，将中断服务程序对堆栈的影响与主程序的堆栈深度进行累加，求出软件最大堆栈深度.

表2是使用该工具分析4个MCS-51软件所得出的统计数据，其中子程序总数包括了中断服务程序，其中所示的例子中递归和不平衡循环没有出现，动态跳转指令出现的次数也较低.尽管本文提出的方法无法自动解决目标码中可能存在的不确定因素，但这些因素出现的次数较低时，仍可以使用人工辅助的方法弥补其不足.

表2 不确定因素指令统计

5 结 论

本文所提出的基于目标码的堆栈分析方法过程简单、易于实现，可从MCS-51程序的目标码中直接分析出最坏情况下软件使用的堆栈深度，对堆栈安全性检查和优化具有参考意义.但值得注意的是，静态方法分析堆栈的问题在于分析出的堆栈深度往往大于实际的堆栈深度，因为分析出的路径可能实际上并不会被执行.因此，如果采用静态方法分析出的堆栈值超过了允许范围，不可盲目认定是软件堆栈溢出，需要根据产生最大堆栈深度的路径信息确认该路径是否有效.

[1] Kleidermacher D N.Practical application of static analysis for embedded systems[J].Ada User Journal，2008, 29(1): 38-42

[2] 刘通平.栈溢出的动态检测技术[J].计算机科学,2007,34(9):282-286

[3] Regehr J.Say not to stack overflow embedded systems design[Z].http:// www.embedded.com/columns/technicalinsights/47101892?_requestid=440562#

[4] 孙涵芳, 徐爱卿.MCS-51/96系列单片机原理及应用[M].北京：北京航空航天大学出版社，1989，21-22

[5] 常硕, 赵彬, 辛文逵.抽象解释技术在嵌入式软件测试中的应用[J].中国测试技术,2007,33(6):93-95

[6] Dennis B, Niels D, Jens P.Static checking of interrupt-driven software[C].The 23rdInternational Conference on Software Engineering (ICSE) , Toronto, Canada ,May 2001

[7] Regehr J, Alastair R, Kirk W.Eliminating stack overflow by abstract interpretation[C].The 3rdInternational Conference on Embedded Software (EMSOFT), Philadelphia, PA，October 2003

AnApproachtoMCS-51ObjectStackDepthAnalysis

ZHANG Xichao, GUO Xiangying

(BeijingInstituteofControlEngineering,Beijing100190,China)

In an embeded software, an object code-based stack analysis is a common means of stack inspection.An analysis-based approach is proposed to analyse MCS-51 series processor’s object code.This approach can obtain the worst case stack depth and also takes into account effects of interrupt service routines on the stack under different priorities.Using this method, a stack analysis tool for MCS-51 object can be quickly developed and its analyzed results give a reference to stack safety inspection and optimisation.

MCS-51; object code; stack analysis; stack depth

2009-11-06

张西超(1983—)，男，河南人，工程师，研究方向为嵌入式软件虚拟测试平台技术(e-mail：xichaozhang@163.com).

TP31

A

1674-1579(2010)02-0047-04