基于表格的中断数据冲突静态分析方法*

黄 晨，董 燕，王小丽，虞砺琨

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

基于表格的中断数据冲突静态分析方法*

黄 晨，董 燕，王小丽，虞砺琨

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

中断冲突问题是星载嵌入式软件较为典型的缺陷之一，由于中断冲突发生的不确定性和随机性，在动态测试过程中难以复现和定位.介绍一种基于表格的中断冲突静态分析方法，专门针对数据关联性、操作关联性、时序冲突以实例的方式给出分析方法和过程，并总结几种预防中断冲突常见的设计策略和方法.相比较动态测试需要在特定的场景才能发现的数据冲突问题，静态分析方法在设计和测试阶段实施更加容易、高效.

中断冲突;数据关联性;操作关联性;时序冲突

0 引言

星载嵌入式软件多为中断驱动型，即主程序加中断的程序结构，属于非常典型的实时并发软件，要求能够实时处理各种随机任务和完成多种计算活动.但是由于中断触发的随机性和不确定性，在设计和实现过程中很容易引入软件错误，导致一系列不易追踪且难以发现和定位的严重软件故障.针对某些特定的数据或者时序才会出现的访问冲突问题，如果用例设计不当或者测试结果数据分析不当时较难发现，此时采用静态的分析方法反而更容易发现和定位.

目前中断冲突、数据竞争等相关问题在工程和研究领域引起了诸多关注，文献［1］提出了一种基于启发式的静态中断数据竞争检测方法，能够自动推断中断优先级状态、中断使能状态和内存访问状态等信息，提高人工确认结果的效率.文献［2］提出了一种基于变量访问序模式的中断数据竞争检测方法，针对单变量访问序模式，基于抽象解释，提出一种支持过程间分析、中断并发分析的高效检测方法.文献［1-2］的研究重点在于提高计算机自动识别代码通用数据竞争冲突的准确性、高效性.文献［3］专门针对C51语言软件中几种较为典型的中断资源访问冲突问题进行分析研究，其实施与选用的编译器具有较大的关系.

有些数据冲突场景依赖于应用背景仅通过工具是较难或者无法发现的，为避免自动分析工具在分析时出现遗漏情况，且不依赖于选用的编译器，本文详细描述了一种基于表格的中断冲突分析方法，在制定中断属性和资源分析列表的基础上，结合具体实例给出数据相关性、操作相关性和时序冲突分析方法，从冲突问题产生的机理上给出分析和解释，最后给出了几种常见的预防规避措施.

1 中断冲突基本模型

虽然中断能较好地满足实时性的要求，但是如果对中断的实现机理认识不清或者使用不当，也会引入软件错误，比如中断冲突问题.所谓中断冲突即主程序和中断之间，或者可嵌套的两个中断:低优先级和高优先级中断同时对同一个资源(如内存单元)进行访问，且至少有一个访问是写操作［1］.

冲突体现在代码针对某个或某些共享资源发生了竞争访问而造成程序错误［4］.如果某个资源在被读取的过程中“被打断”进行写操作或在被写的过程中“被打断”进行读取或重写操作，则可能存在访问冲突.“被打断”包括主程序中的资源被某个中断服务子程序打断、一个中断服务子程序的资源被某个高级中断服务子程序打断等情况［5-8］，因此，中断冲突需要结合中断及优先级分析.通常，中断程序使用的资源主要包括:单字节变量、多字节变量、缓冲区、数组、I/O端口、寄存器等.

图1 中断冲突基本模型Fig.1 Basic model of interrupt conflict

2 表格分析法

基于静态的分析过程，针对中断中使用的资源进行逐一分析，即针对所有中断服务子程序中访问的资源，逐一分析其在主程序(含其调用的子模块)、各个中断服务子程序的访问情况，以确定资源访问过程中是否存在冲突.实际使用过程中，采用表格分析法:

1)以表格的形式列出所有中断服务子程序使用的资源，中断服务子程序使用资源包括该服务程序调用的所有子模块中使用的资源，一个中断服务子程序的优先级及引用的资源，如表1所示.

表1 中断属性表Tab.1 Summary table of interrupt property

2)以表格的形式说明中断服务子程序中使用的每个资源的引用关系表，如表2所示，并逐一进行分析.

针对主程序和中断子程序访问共享资源时，列举出所有的读写操作方式，如:只读、只写、读写.

采用上述对资源的分析方法，容易发现如下典型的访问冲突:

1)多字节的变量、缓冲区、数组、I/O端口等数据访问冲突.一个多字节变量被主程序读取过程中(如读完第一个字节)，被中断打断并对该变量进行赋值操作，在中断返回后主程序继续读第二字节，导致主程序获取的多字节数据高低字节不同步，发生数据跳变;

表2 中断程序使用资源的引用关系总结表Tab.2 Resources using of interrupt program references

2)寄存器访问冲突:主程序给某个寄存器赋值后，被中断打断并对该寄存器进行其他赋值操作，在中断返回后主程序使用该寄存器数值时，使用的数据是被中断意外改写后的数据，并不是之前赋值的数据.

3 分析改进

采用上述表格检测法能够较好的识别和发现一些中断冲突问题，另外还存在一些更为复杂的情况仅采用上述方法是较难发现的，在此针对数据相关性、操作关联性和时序冲突进行专门的说明.

3.1 数据相关性分析

关联资源可分为两种类型:同一物理对象但标识参数不同的资源;不同物理对象但数值要求同步和统一的资源.

第2章罗列的资源是基于源代码的参数形式存在，如果仅仅采用最基础的表格分析法，针对同一物理对象但标识参数不同的设计代码，会造成资源引用总结的不全面或不正确，最终导致冲突分析的遗漏;针对不同物理对象但数值要求同步和统一的设计代码，会造成资源引用的分离，导致冲突分析的错误.下面通过实例具体说明这两种情况.

实例1.同一物理对象但标识参数不同的资源

如代码中有定义#define AAA_reg((unsigned char xdata*)aaareg)，则在针对AAA_reg、aaareg的访问应该当做同一个资源进行引用总结，多维度考虑是否存在访问冲突，采用表格法列举针对这两个标识参数的引用关系.

基于表格分析法罗列出所有共享资源名称，采用自动分析工具对具有相同物理地址的标识参数进行检测，如果某些标识参数对应的物理地址相同，则认为它们是关联变量.针对这种类型的关联变量，分析过程中调整它们在表格中的位置，放置在相邻行中，并做绑定合并标记(以虚线分割)，以表明这些变量为同一物理对象，作为同一个对象资源，根据冲突原理进行分析.

实例2.不同物理对象但数值要求同步和统一情况1(变量与计算结果相互关联)

3个温度参数T1～T3及它们的温度平均值T0，针对T0～T3应该作为不可分开的资源进行引用总结，建立它们的引用关系表，多维度考虑是否存在访问冲突.

采用表格分析法针对T0～T3的引用关系逐一分析是不会发现访问冲突的，针对这种情况在分析时，需要将T0～T3放置在相邻行中，并做绑定合并标记(以虚线分割)，以表明这些变量为同一物理对象，作为同一个对象资源，根据冲突原理进行分析.

表3 不同标识但映射对象相同的识别Tab.3 The recognition of objects with different identification but same identity mapping

实例3.不同物理对象但数值要求同步和统一情况2 (多个变量的物理意义相互关联)

指令内容DATACMD及其指令编号CMDNO，是固定配对使用的，两者是不可分开的资源，建立它们的引用关系表，如果单独分析参数，没有明显的访问冲突.

表5 变量物理意义相互关联Tab.5 The physical meaning of interrelated variables

数据关联性分析改进:基于表格分析法中罗列的所有资源名称，结合软件背景和代码结构，分析所列资源中的数据关联性，确认哪些资源存在同步关系，即代码针对它们的操作必须同步，不能被打断，将存在数据关联性的资源放到相邻的位置处，绑定合并后进行冲突分析.针对数据关联性问题在动态测试中不易发现，由于中断发生的不确定，只有在被打断函数的特定位置产生中断，且中断中存在写操作时才会发生问题，采取数据关联性分析更容易发现上述问题.

3.2 操作关联性分析

上述方法仅仅是基于资源的分析方法，而没有针对资源引用的一组操作涉及到的多条语句的关联性进行分析，即代码中的某几条语句为相互关联的操作，操作计算过程一旦被打断中间数据被改写，则会造成操作错误.

实例4.计算过程使用的变量相互关联

主程序使用单字节变量time进行计算，time在中断服务子程序中会被赋值改写.如果仅采用基本的表格分析法罗列的资源进行引用，无法发现访问冲突，是正常的代码逻辑设计.

主程序:

在考虑操作关联的情况下，会发现语句(1)和语句(2)中使用的time必须是同一时刻的数值，如果(1)和(2)之间发生中断改写time会导致(1)中计算timer1使用的time值与(2)计算使用的time不一致，timer2计算错误.

操作关联性分析改进:针对一个资源的多个或一组操作涉及到的多条语句，需要分析这些操作中使用的资源是否必须是同一时刻的数据，该点针对复杂运算时尤为重要.为解决该问题，需要增加如下分析工作:

针对每个资源，分析其在每个范围内(如主程序范围内，某个中断服务子程序范围内)的具体操作语句，确认这些操作语句的关联性.对于存在关联操作的语句需要绑定到一起，确保在执行过程中不会出现被打断改写的情况出现.针对操作关联性问题在动态测试中也不易发现，与数据关联性问题类似，需要构造特定的场景才会发生问题.

3.3 时序冲突分析

前面描述的内容归根到底均为数据访问冲突，而时序访问更复杂.如果不同模板(穿插中断)针对同一个资源或某些资源进行写-读，这些读写在正常情况下满足一定的流程(即分析确认不是数据冲突，而是软件的一个正确处理过程，正常情况下该时序不会被打断)，此时需要考虑是否存在破坏正常流程的入口条件，即如果一个正常流程存在被意外打断的外部条件，则当前资源的访问处理流程就存在时序访问冲突.

实例5.通过时序控制端口输出

主程序往IO1写数据，查看反汇编对应的写操作过程分为2步，先写低字节，再写高字节，如果写的过程被T0打断，则导致主程序和中断中的两次写均失效:①主程序中写入的低字节被中断T0中的写覆盖，主程序写入的低字节无效;②中断T0中写入的高字节在从T0中断返回后被主程序写入的高字节覆盖，中断T0中写入的高字节无效.

结合物理需求和代码设计思想，正常情况下，主程序中的写与中断T0中的写间隔是满足一定要求的，主程序不会存在随机被T0打断的可能，主程序和中断T0写IO1的间隔为100 ms(见表6中是否存在数据冲突及相关说明一列).

进一步分析操作过程和时序关系，确认是否存在外界输入，造成上述正常操作流程被打断的可能(见表6中是否存在时序访问冲突一列).

表6 时序访问分析实例表Tab.6 Timing access violation example

时序冲突分析改进:对于具有特定时序要求的资源进行时序访问冲突分析，分析正常流程和外界输入可能打乱正常流程的情况，在表格中增加时序冲突一列进行说明.针对时序冲突问题如果采用特定的输入流程在动态测试中也不易发现问题，需要在动态测试过程中加大、加强各种外界输入的测试，测试用例以不同的发送的时间、最小的时间间隔、覆盖所有的指令输入，以验证程序实现的正确性.

4 预防及规避措施

针对存在访问冲突的资源，为预防冲突发生，软件必须有对应的预防措施和设计策略.针对一些冲突类型，常见的设计策略如下:

(1)关中断

读/写过程关中断是常见的数据访问冲突预防措施，在可能产生中断的位置关闭相应中断，以保证数据访问不被打断，尤其是多字节数据和关联性操作语句，采用该措施是非常有效的.

关中断措施在具体实施时，需要特别注意如下两方面问题:确认当前关中断不能意外被打开，如此时关闭了某一个中断，但在另一个未被关的中断服务子程序中打开了该关闭中断，造成当前关中断操作失效;结合软件需求确认当前关中断时间是否影响软件性能要求，如关中断时间太长影响软件对中断的响应时间，造成其他功能失效.

一般情况下，软件初始化完成之前必须关中断，以保证初始化的完整性.

(2)设置中断发生标记

设置中断发生标记的方式为在读数据之前设置该标记为零，读写完成后判断该标记是否置位(该标记在中断服务子程序中写该数据后置位)，如果置位，则重新读取该数据，以保证当前数据是最新的同步数据，而不会出现跳变.该方法通常用于多字节资源进位的处理，而且仅限于资源读取操作.

(3)互斥量机制

该机制决定了当前共享资源在任何情况下都不会出现访问冲突.当访问资源的模块在任务处理完后将拥有的互斥对象交出，以便其他模块得以访问.

(4)乒乓存储

乒乓存储是一个常常应用于数据流控制的处理技巧，输入数据流通过“输入数据选择单元”将数据流分配到两个数据缓冲区，一个模块对一个数据缓冲区进行都操作过程中，另一个模块对另一个数据缓冲区进行写操作，避免数据冲突，提高处理效率.

(5)现场保护

现场保护是寄存器访问冲突常用的手段，具体实现是在中断服务子程序的入口处将当前寄存器值压到堆栈区，在出口处再从堆栈中弹出保存值到对应的寄存器.具体实施时需要注意堆栈的压入和弹出顺序，以及个数上的一致性.

5 总结

本文描述了一种基于表格的中断冲突静态分析方法，专门针对中断冲突分析中的几个复杂问题:数据相关性、操作相关性和时序冲突问题提出了分析措施和策略，对于数据相关和操作相关的资源合并绑定到一起进行分析;对于具有时序要求的资源增加时序冲突分析，考虑正常流程被外界输入打乱的可能.需要注意的是，在分析过程中需要结合代码具体的应用背景和实际物理意义进行分析.最后总结了几种常见中断冲突的预防设计措施，希望做到从设计层面开始有效避免中断冲突问题.

这种基于表格的中断数据冲突静态分析方法实施容易、高效，已经应用于实际测试过程中，并取得了较好的效果，能够发现诸多动态测试中不易发现的冲突问题.

［1］ 段永颢，陈睿.基于启发式的静态中断数据竞争检测方法［J］.计算机工程与设计，2013，34(1):140-145.DUAN Y H，CHEN R.Heuristic static data race detection for interrupt-driven software［J］.Computer Engineering and Design，2013，34(1):140-145.

［2］ 陈睿，杨孟飞，郭向英.基于变量访问序模式的中断数据竞争检测方法［J］.软件学报，2016，27(3): 547-561.CHEN R，YANG M F，GUO X Y.Interrupt data race detection based on shared variable access order pattern ［J］.Journal of Software，2016，27(3):547-561.

［3］ 侯成杰.航天器C51语言软件中断资源冲突分析方法［J］.空间控制技术与应用，2015，41(4):58-62.HOU C J.Interrupt resource conflict analysis for spacecraft C51 language software［J］.Aerospace Control and Application，2015，41(4):58-62.

［4］ BRYLOW D，PALSBERG J.Deadline analysis of interrupdriven software［J］.IEEE Transactions on Software Engineering，2004，30(10):634-655.

［5］ COOPERIDER N.Data-flow analysis for interrupt-driven microcontroller software［D］//Doctor of Philosophy，the University of Utah，2008.

［6］ Advanced methods in automated software test［C］// IEEE conference on software maintenance.New York: IEEE，1990.

［7］ ENGLER D，ASHERAFL K，RACE X.Effective static detection of aceconditions and deadlocks［C］//Scott M，Petcrson L.Proceedings of the 19thACM Symposium on Operating System Principles.Boiton Landing:ACM press，2003:237-252.

［8］ 吴萍，陈意云，张健.多线程程序中断冲突的静态检测［J］.计算机研究与发展，2006，43(2):329-335.WU P，CHEN Y Y，ZHANG J.Static data-race detection for multithread programs［J］.Journal of Computer Research and Development，2006，43(2):329-335.

Static Analysis Method for Table-Based Interruption Data Conflictions

HUANG Chen，DONG Yan，WANG Xiaoli，YU Likun
(Beijing Institute of Control Engineering，Beijing 100190，China)

Interrupt conflict is one of the typical defects in the board embedded software，due to the interruption of uncertainty and randomness of conflict，which are difficult to reproduce and positioned in the dynamic testing process.A static analysis method of interrupt conflict is described on the form of sheet，specifically for data association，operational relevance，timing violations.Several examples are given to illustrate the method and process.Several interrupt conflict prevention strategies and methods are also summarized.Data conflict problems in specific scenario are hard to be found.Compared to dynamic test，static analysis methods in the design and testing stages are easier and more efficient to implement.

interrupt conflict;data association;operating relevance;timing conflict

TP311.5

A 文章编号:1674-1579(2016)05-0057-06

10.3969/j.issn.1674-1579.2016.05.011

黄 晨(1983—)，女，工程师，研究方向为软件测试;董 燕(1972—)，女，高级工程师，研究方向为软件测试;王小丽(1983—)，女，高级工程师，研究方向为软件测试;虞砺琨(1987—)，女，工程师，研究方向为软件测试.

*国家自然科学基金资助项目(91118007).

2016-05-16