一种基于冗余编码的变量签名唯一性安全保证方法

曹 杰 汪明新 孙军峰

铁路信号行业直接涉及列车的安全运行和人民群众的生命财产安全，其安全产品必须满足RAMS（可靠性、可用性、可维护性、安全性）的要求。尤其对于车载ATP系统，必须达到SIL4级的系统安全完善度等级。系统要求基于安全冗余编码技术，独立于软件和硬件环境，可以防护硬件或内存错误等引起的操作数、操作符及运算错误，能够保证系统在复杂的软件和硬件环境下达到SIL4级要求的错误不可检出率，有效提升系统的安全度等级。目前，多数ATP系统中都使用冗余代码来保证系统的安全性，虽然形式各异但基本原理相同，并已应用在许多地铁项目中。

要使系统达到SIL4标准要求的错误不可检出率，需要保证冗余代码中所有变量在同一时刻的签名都是唯一的。为此，提出了一种基于冗余编码的变量签名唯一性安全保证方法，可以确保系统中所有的变量签名都是唯一的，这样系统的所有单点故障都可以检测出来。而对于多点故障 （发生多次寻址错误或硬件失效等故障，这类故障发生概率非常小，一般情况下可忽略不计），系统的错误不可检出率也明显降低，该方法大大降低了系统的错误不可检出率。

1 编码理论

微处理器及其电路中所有影响和干扰处理器运算的错误，从处理数据层次上或者从数据的角度，可以归为以下3种类型：①运算错误，即处理器在运算过程中发生了错误；②操作数错误，即处理器在运算时，提取了错误的运算数；③操作符错误，即处理器使用了正确的运算数，却混淆了运算符。

冗余编码算法采用了AN码、分离码相结合的编码方式。对简单变量x，设计其编码后的形式为：

其中，A为编码时选择的大素数；Bx为编码时为变量x分配的数据签名，取值范围为 ［1，A－1］；DT为时间戳，取值范围为 ［1，A－1］。在实际编码中，将2k位的数据分成了高k位和低k位，高k位为数值域，存放数据原始值，XH＝x；低k位为校验域，校验处理器错误

令rkx＝ （2kx）modA，2kx－（2kx）modA ，能够被A整除，符合AN码的格式。按照这种编码方法，通过AN码可以检测算术运算操作是否错误；对每个操作数分配一个固定的签名Bx，可以检测操作数寻址签名错误和操作符错误；时间戳DT可以检测循环中变量的值没有被更新的错误，或者因为失效使用上个周期变量值的错误。

2 设计与实现

在现有的安全冗余编码系统中，对源码中所有的变量都会生成高位和低位，其中高位存储源码的变量值，低位存储变量的校验信息，通过高位和低位信息可以计算出变量的签名。所以，在系统每个周期运行结束后，通过检查变量的签名是否正确，来判断系统在运行过程中是否出现寻址错误、硬件失效等故障 （非系统本身的逻辑错误）。如果变量的签名不唯一，就会导致系统的故障可能检测不出来，也不便于系统安全的定量分析。

2．1 软件功能结构

一种基于冗余编码的变量签名唯一性安全保证方法，包括经签名产生模块后依次进入签名分配模块或签名计算模块、签名检查模块，最后在签名存储模块存储签名，其功能结构如图1所示。

1．签名产生模块：按照签名生成算法产生足够的签名。

2．签名分配与计算模块：对待编码的文件进行冗余编码，判断待编码的语句的类型，为每个变量分配或计算签名。

3．签名检查模块：对签名分配与计算模块得到的签名做签名唯一性检查，如果该签名与已经分配的签名相同，则从签名表中重新取一个签名分配给该变量。

4．签名存储模块：存储经过签名检查模块检查的签名。

图1 软件功能结构示意图

2．2 工作流程

图2为该方法的工作流程图，图3为签名产生模块流程，图4为签名计算模块基本运算签名处理流程。结合图2～图4对各步骤进行详细描述。

步骤1：按照签名生成算法产生签名，图3是签名产生模块的具体步骤，如果产生的签名个数足够，就转向步骤2，否则继续执行步骤1。例如可以设定产生20000个签名。

步骤2：输入待编码的文件，判断待编码的语句的类型，为每个变量分配或计算签名。

1．该语句为变量定义或声明，则从步骤1生成的签名表中分配一个签名给该变量。

2．该语句属于基本运算，则判断该基本运算属于哪种运算，图4描述了该过程的具体步骤。如果是加、减、乘、除运算，或者是逻辑与、或、非运算，或者是左移、右移运算，都按照相应运算的签名计算方式计算签名。

图3 签名产生模块流程图

3．该语句为数组运算。如果是数组赋值、数组取值运算，按照相应运算的签名计算方式计算签名。

4．该语句为分支、循环结构，也按分支、循环结构的签名计算方式计算签名。

5．该语句为函数调用。如果为模块函数调用或计算函数调用，按相应签名计算方式计算签名。

为变量分配或计算好签名后，则转向步骤3。

步骤3：对步骤2（或步骤4）得到的签名做签名唯一性检查，如果该签名与已经分配的签名相同，则转向步骤4，否则转向步骤5。

步骤4：从签名表中重新取一个签名分配给该变量，再转向步骤3。

步骤5：存储经过签名唯一性检查的签名，并判断编码是否结束，如果没有到达待编码文件的结尾，则转向步骤2，否则转向步骤6。

步骤6：结束。

3 分析

按照随机编码思想，在一个消息空间中有N个消息；其中有M个消息是合法消息，那么N个消息中某个消息发生了错误，变成合法消息 （M中的一个）的概率P为：

P＝M／N

前提：编码码字M在消息空间N中分布足够随机。

采用基于冗余编码的变量签名唯一性安全保证方法处理后，系统的有效内存空间中所有变量签名都是唯一的，即对于每个变量该内存空间中只存在一个合法的消息，因此，如果一个合法变量发生错误，该变量只可能变成该内存空间中的一个非法变量，从而利用冗余编码算法签名错误检查机制检测出该错误。

与现有技术相比，该方法保证了所有变量的签名都是唯一的，所有的变量都被唯一标识，系统的所有单点故障都能检测出来；而系统的多点故障，只要基于内存空间中的所有消息 （对应系统中的签名）的分布足够随机 （从某种程度上来说是一种伪随机），就可以通过对系统的安全进行定量分析，也证明该方法明显降低了系统的错误不可检出率。

图4 签名计算模块基本运算签名处理流程图

［1］ 姜坚华．loo2D模型分析及其在地铁列车自动防护系统中的应用［J］．城市轨道交通研究，2011，6：25－28．

［2］ IEC 61508 2010Functional Safety of electrical／electronic／programmable electronic safety－related system［S］．

［3］ Forin P．Vital Coded Microprocessor Principle and Application for Various Transit Systems［C］．1989 IFAC CCCT Symposium：79－84．