安全关键系统中的安全编码生成方法与装置

摘要

本发明涉及一种安全关键系统中的安全编码生成方法，包括：通过对预生成信息码进行二进制取反操作，生成原始码字；对原始码字通过二进制数学计算进行编码。本发明提出的一种安全关键系统中的安全编码生成方法具有安全性，便捷性，高效性，且具有算法封装性，即将编码函数和解码函数进行了对象封装，客户端只需使用一个全局只读的算法对象，即可访问所有算法，减轻了程序员的记忆负担。本发明还公开了一种安全关键系统中的安全编码生成装置。

说明书

技术领域

本发明涉及城市轨道交通技术领域，尤其涉及一种安全关键系统 中的安全编码生成方法与装置。

背景技术

目前，在铁路、民航、航天等安全关键领域中，其控制中枢属 于安全关键系统，必须具有极高的安全性、可靠性和健壮性。这类 系统的质量不仅取决于在所有可能输入下都是正确的，更取决于当 有外界电磁干扰、机械振荡、热噪声存在时，软件或者可以正常运 行或者导向安全侧。在特定行业的技术规范中，一般都会对安全关 键软件的程序代码提出苛刻的要求。例如，在铁路行业中，《计算机 联锁技术条件(送审稿)(V1.31)》8.4.3条和8.4.4条就有明确规定， 与铁路行车安全相关的变量的不同取值之间的汉明距离不小于4，非 法码字与合法码字的比例不小于255:1。这两条规定不仅适用于铁路 行业，也适用于民航、航天、汽车等对可靠性要求苛刻的行业。

综观各行业安全关键软件，它们对这两条规定的应对方案可以 分为三种：一是顺序编码，即某个变量的取值完全按照1、2、3、4 等顺序来自然编码，这种编码方式具有直观、高效、易于理解的优 点，但是它完全忽略了上述两条规定，在复杂电磁环境下易受到内 存跳变的影响，存在极大的安全隐患；二是随机编码，即某个变量 的取值通过随机数发生器来确定，这种方式具有方便、快捷的优点， 但是它不能保证同一变量的任意两个取值之间的汉明距离不小于4， 因此无法避免因电磁干扰等导致的内存跳变问题；三是手工指定具 有特定汉明距离的码字，这种编码方式可以保证遵守上述两条安全 编码规定，但是容易出错，效率很低，上下文交互极不方便，经常 因为程序员的遗忘等因素导致人为串码，具有很大的安全隐患。

发明内容

本发明所要解决上述提到的技术问题，本发明提供了一种安全关 键系统中的安全编码生成方法与装置。

为此目的，本发明提出了一种安全关键系统中的安全编码生成方 法，包括：

S1：对预生成信息码进行二进制取反操作，生成原始码字；

S2：对所述原始码字通过二进制数学计算进行编码。

具体地，所述步骤S2进一步包括：通过C语言预编译宏方式进行 提供；预编译宏在编译之前进行解析，在编译期间进行宏展开和常量 合并。

具体地，所述步骤S2进一步包括：通过C语言函数方式进行提供； 通过静态数组映射的方式返回编码结果。

进一步地，还包括：对编码后的码字进行解码。

具体地，所述对编码后的码字进行解码，具体包括：通过C语言 函数的方式进行提供；使用二分法进行搜索和解码。

为此目的，本发明提出了一种安全关键系统中的安全编码生成装 置，包括：

原始码字生成模块，用于对预生成信息码进行二进制取反操作， 生成原始码字；

编码模块，用于对所述原始码字通过二进制数学计算进行编码。

具体地，所述编码模块，还包括：

第一方式提供单元，用于通过C语言预编译宏方式进行提供；

解析单元，用于预编译宏在编译之前进行解析；

宏操作单元，用于在编译期间进行宏展开和常量合并。

具体地，所述编码模块，还包括：

第二方式提供单元，用于通过C语言函数方式进行提供；

编码结果返回单元，用于通过静态数组映射的方式返回编码结 果。

进一步地，还包括：解码模块，用于对编码后的码字进行解码。

具体地，所述解码模块，还包括：

第三方式提供单元，用于通过C语言函数的方式进行提供；

搜索与解码单元，用于使用二分法进行搜索和解码。

本发明公开了一种安全关键系统中的安全编码生成方法，通过对 预生成信息码进行二进制取反操作，生成原始码字；对原始码字通过 二进制数学计算进行编码。本发明提出的一种安全关键系统中的安全 编码生成方法具有安全性，即任意码字之间的距离都不小于4，非法 码字与合法码字的比例远远大于255:1；便捷性，即针对不同的变量， 可以方便地进行编码和解码；高效性，即提供了两种编码手段，第一 种手段仅消耗编译时间，几乎不耗费任何运行时间，第二种手段具有 极低的常量运行时间。提供了一种解码手段，其运行耗时大约为第二 种编码手段的两倍，效率非常高。编码和解码的运行时空间复杂度都 是O(1)；提供编码常量：第一种编码手段提供的码字可以当作常量来 使用，以规避C语言编译器对数组大小的常量限制；适用范围广，即 提供了169个基本码字和足够多的扩展码字，适合绝大多数工业软件 中的变量取值范围；不易出错，即自动化的编码和解码手段，消除了 手工编码的费时易错特点；算法封装性，即将编码函数和解码函数进 行了对象封装，客户端只需使用一个全局只读的算法对象，即可访问 所有算法，减轻了程序员的记忆负担。本发明还公开了一种安全关键 系统中的安全编码生成装置。

附图说明

通过参考附图会更加清楚的理解本发明的特征和优点，附图是示 意性的而不应理解为对本发明进行任何限制，在附图中：

图1示出了本发明实施例中的一种安全关键系统中的安全编码生 成方法的步骤流程图；

图2示出了本发明实施例中的一种安全关键系统中的安全编码生 成装置的结构框图；

图3示出了本发明实施例中的一种安全关键系统中的安全编码生 成方法中编码宏的定义过程的步骤流程图；

图4示出了本发明实施例中的一种安全关键系统中的安全编码生 成方法中编码宏使用过程的步骤流程图；

图5示出了本发明实施例中的一种安全关键系统中的安全编码生 成方法中编码函数的定义过程的步骤流程图；

图6示出了本发明实施例中的一种安全关键系统中的安全编码生 成方法中编码函数的使用过程的步骤流程图；

图7示出了本发明实施例中的一种安全关键系统中的安全编码生 成方法中解码函数的定义过程的步骤流程图；

图8示出了本发明实施例中的一种安全关键系统中的安全编码生 成方法中解码函数的使用过程的步骤流程图。

具体实施方式

为了保证安全关键软件中的程序代码遵循安全编码规定，同时避 免现有技术方案的缺点，本发明提出了一种改进型编码方式，安全编 码快速生成器，即本发明提出了一种安全关键系统中的安全编码生成 器及生成方法。

下面将结合附图对本发明的实施例进行详细描述。

为了更好的理解与应用本发明提出的一种安全关键系统中的安 全编码生成方法与装置，以如下附图示例进行详细说明。

如图1所示，本发明提出了一种安全关键系统中的安全编码生成 方法，包括：

步骤S1：对预生成信息码进行二进制取反操作，生成原始码字。

步骤S2：对原始码字通过二进制数学计算进行编码。

具体地，步骤S2进一步包括：通过C语言预编译宏方式进行提供； 预编译宏在编译之前进行解析，在编译期间进行宏展开和常量合并。 因此，这种手段生成的编码结果将是运行时常量，不用在运行时为编 码过程申请新的内存，因此运行时的时间复杂度和空间复杂度都是 O(1)。这种编码手段适合于C语言对数组大小和switch-case语句有常 量要求的场合，也适用于对运行效率有苛刻要求的场合。

进一步地，步骤S2进一步包括：通过C语言函数方式进行提供； 通过静态数组映射的方式返回编码结果。运行效率极高，时间复杂度 是O(1)，只需一次数组地址偏移即可得到结果。静态数组属于模块内 的堆内存，是编译期间分配的，无需申请新内存，运行时的空间复杂 度是O(1)。这种编码手段提供了极大的运行时灵活性，方便对动态输 入进行安全编码。通过C语言预编译宏方式进行提供。

更进一步地，本发明提出的一种安全关键系统中的安全编码生成 方法还包括：对编码后的码字进行解码。具体地，通过C语言函数的 方式进行提供；使用二分法进行搜索和解码。

本发明提出了一种安全关键系统中的安全编码生成方法，通过对 预生成信息码进行二进制取反操作，生成原始码字；对原始码字通过 二进制数学计算进行编码。本发明提出的一种安全关键系统中的安全 编码生成方法具有安全性，即任意码字之间的距离都不小于4，非法 码字与合法码字的比例远远大于255:1；便捷性，即针对不同的变量， 可以方便地进行编码和解码；高效性，即提供了两种编码手段，第一 种手段仅消耗编译时间，几乎不耗费任何运行时间，第二种手段具有 极低的常量运行时间。提供了一种解码手段，其运行耗时大约为第二 种编码手段的两倍，效率非常高。编码和解码的运行时空间复杂度都 是O(1)；提供编码常量：第一种编码手段提供的码字可以当作常量来 使用，以规避C语言编译器对数组大小的常量限制；适用范围广，即 提供了169个基本码字和足够多的扩展码字，适合绝大多数工业软件 中的变量取值范围；不易出错，即自动化的编码和解码手段，消除了 手工编码的费时易错特点；算法封装性，即将编码函数和解码函数进 行了对象封装，客户端只需使用一个全局只读的算法对象，即可访问 所有算法，减轻了程序员的记忆负担。

如图2所示，本发明还提出了一种安全关键系统中的安全编码生 成装置10，包括：原始码字生成模块101与编码模块102。

具体地，原始码字生成模块101用于对预生成信息码进行二进制 取反操作，生成原始码字；编码模块102用于对原始码字通过二进制 数学计算进行编码。

进一步地，编码模块102还包括：第一方式提供单元(图中未示 出)用于通过C语言预编译宏方式进行提供；解析单元(图中未示出) 用于预编译宏在编译之前进行解析；宏操作单元(图中未示出)用于 在编译期间进行宏展开和常量合并。

更进一步地，编码模块102还包括：第二方式提供单元(图中未 示出)用于通过C语言函数方式进行提供；编码结果返回单元(图中 未示出)用于通过静态数组映射的方式返回编码结果。

更进一步地，本发明提出的一种安全关键系统中的安全编码生成 装置还包括：解码模块103用于对编码后的码字进行解码。具体地， 解码模块103还包括：第三方式提供单元(图中未示出)用于通过C 语言函数的方式进行提供；搜索与解码单元(图中未示出)用于使用 二分法进行搜索和解码。

本发明提出了一种安全关键系统中的安全编码生成装置，通过原 始码字生成模块对预生成信息码进行二进制取反操作，生成原始码 字；最终通过编码模块对原始码字通过二进制数学计算进行编码。本 发明提出的一种安全关键系统中的安全编码生成装置具有安全性，即 任意码字之间的距离都不小于4，非法码字与合法码字的比例远远大 于255:1；便捷性，即针对不同的变量，可以方便地进行编码和解码； 高效性，即提供了两种编码手段，第一种手段仅消耗编译时间，几乎 不耗费任何运行时间，第二种手段具有极低的常量运行时间。提供了 一种解码手段，其运行耗时大约为第二种编码手段的两倍，效率非常 高。编码和解码的运行时空间复杂度都是O(1)；提供编码常量：第一 种编码手段提供的码字可以当作常量来使用，以规避C语言编译器对 数组大小的常量限制；适用范围广，即提供了169个基本码字和足够 多的扩展码字，适合绝大多数工业软件中的变量取值范围；不易出错， 即自动化的编码和解码手段，消除了手工编码的费时易错特点；算法 封装性，即将编码函数和解码函数进行了对象封装，客户端只需使用 一个全局只读的算法对象，即可访问所有算法，减轻了程序员的记忆 负担。

为了更好地理解与应用本发明提出的一种安全关键系统中的安 全编码生成与装置，进行以下示例，且本发明不局限以下示例。

具体地，在本发明中，使用信息论的手段，利用生成多项式预生 成信息码1、2、3、4、5、6、7对应的七个码字，对这七个码字施加 二进制取反，得到另外七个码字。这十四个码字称为原始码字。在原 始码字的基础上，通过二进制数学运算，可得169个码字，称为基本 码字，容易验证，任意两个基本码字之间的汉明距离都不小于4，因 此符合上述第一条安全编码规定。

进一步地，使用4字节无符号整数来表示基本码字，则169个码字 所在的码集是[0,2³²-1]。在这个码集中合法码字有169个，非法码字有 (2³²-1-169)个，非法码字与合法码字的比例为(2³²-1-169)/169≈ 25414006:1，远远大于255:1。因此，这种编码方案完全符合上述第 二条安全编码规定。

更进一步地，为了扩大安全编码的表示范围，必要时可以对169 个码字进行组合扩展。例如，一次组合将得到扩展码字(基本码字A, 基本码字B)，将得到169×169＝28561个扩展码字，进一步的组合将 得到更多扩展码字。任意两个扩展码字的汉明距离仍然不小于4。扩 展之后，非法码字与合法码字的比例进一步增大，提高了安全性。例 如，一次组合后的比例为((2³²-1)²-28561)/28561≈645871785480886: 1，显然远远大于255:1。

更进一步地，本发明提供两种编码手段。第一种手段是以C语言 预编译宏的方式提供的，预编译宏在编译之前进行解析，在编译期间 进行宏展开和常量合并。因此，这种手段生成的编码结果将是运行时 常量，不用在运行时为编码过程申请新的内存，因此运行时的时间复 杂度和空间复杂度都是O(1)，这种编码手段适合于C语言对数组大小 和switch-case语句有常量要求的场合，也适用于对运行效率有苛刻要 求的场合；第二种手段以C语言函数的方式提供，它通过静态数组映 射的方式返回编码结果，运行效率极高，时间复杂度是O(1)，只需一 次数组地址偏移即可得到结果，静态数组属于模块内的堆内存，是编 译期间分配的，无需申请新内存，运行时的空间复杂度是O(1)。因此， 这种编码手段提供了极大的运行时灵活性，方便对动态输入进行安全 编码。

更进一步地，本发明提供了一种运行时解码手段，以C语言函数 的方式提供。具体地，它使用二分法进行快速搜索和解码，169个码 字的解码的时间复杂度7.4O(1)(7.4≈log₂169)，为常量时间复杂度， 效率极高。解码时所用的内存空间是编译期间分配的堆内存，无需申 请新内存，运行时的空间复杂度是O(1)。一次扩展码字解码的时间复 杂度为O(i)＝log₂28561≈14.8，依然为常量时间复杂度，且运行时的空 间复杂度是O(1)。

综上所述，其中，编码宏、编码函数和解码函数完全隐藏了繁琐 的编码过程，客户端只需使用类似Func(input)的方式进行访问，因此 使用极为便捷，极不容易出错。

具体地，如图3所示，为编码宏的定义过程，在步骤S1中，定义 了169个基本码字常量_Haming_0到_Haming_168，分别对应0x00、 0x17、0x2E、……、0xFFFFD1、0xFFFFE8。应说明的是，这些标志 符的前导下划线，其意在提醒客户端的程序员，这些标识符是私有标 识符，外部模块不应对其进行访问；在步骤S2中，定义了一个拼贴宏 _HamingPaste(n)，其定义内容为：

#define_HamingPaste(n)(_Haming_##n)

例如，_HamingPaste(168)将得到_Haming_168，也即得到常数 0xFFFFE8。

在步骤S3中，定义了编码宏Haming(n)，该标识符前面没有下划 线，表明它是一个公开的宏，可以被外部模块调用。编码宏Haming(n) 的定义如下：

#define((n)<0？0:((n)>168？168:_HamingPaste(n)))

其中，Haming(n)主要是用于处理范围[0,168]之外的输入，以提 高编码的健壮性。

更进一步地，编码宏使用过程如图4所示，具体地，客户端仅需 使用Haming(n)即可获得参数n对应的安全编码结果，而无需知道其他 宏的内部实现方式，因此使用起来极为方便、不易出错，且在C语言 中，Haming(n)返回的是一个编译器常量和运行时常量，运行时效率 非常高，时间复杂度和空间复杂度都是O(1)。特别地，Haming(n)可 以用作C语言的数组大小和switch-case语句中的分支标志，因此 Haming(n)可以给程序员带来很好的附加功能。

如图5所示，为编码函数的定义过程，具体地，在步骤S4中，定 义了静态数组D1和一种结构体类型A1。其中，数组D1由169个码字 按照由小到大的顺序构成，以方便快速访问和。结构体类型A1含有 两个函数指针，分别用于指向编码函数和解码函数,有需要时可以方 便地添加新的函数指针；在步骤S5中，定义了编码函数F1(n)，用于 返回唯一参数n的编码结果，同时防护了非法的参数值。函数F1(n)的 内部实现极为简单，就是进行简单的地址偏移操作，即进行数组取值 运算D1[n]。由于数组取值运算仅耗费一个单位的内存访问时间，且 不用申请新的内存，因此函数F1(n)在运行时的时间复杂度和空间复 杂度都是O(1)；在步骤S6中，定义唯一的全局只读算法对象A2，其 类型为A1，同时在初始化的时候将真实函数F1绑定至A2的编码函数 指针。

将编码函数封装成结构体类型A1，有两个好处：一是便于以后 添加新的算法，而无需修改现有代码。例如，如果以后要为A1添加 解码函数F2(n)、汉明距离计算函数F3(n1,n2)、汉明重量计算函数 F4(n)，那么只需在A1中增加三个函数指针，然后定义三个真实的函 数，最后进行初始化绑定即可，而无需修改编码函数F1的定义过程和 绑定过程。二是减少客户端程序员的记忆压力，以便快速访问算法对 象提供的服务，也即程序员只需记住唯一全局只读对象A2的名字即 可，而无需记住各个具体函数的名字。应该说明的是，结构化编程要 求尽量减少全局变量的使用，但是这里的全局变量A2是只读的，因 此在带来便利性的同时，并未带来负面作用。

进一步地，如图6所示，为编码函数的使用过程，具体为F1(n)的 内部处理流程使用了D1的内容，因此能保证F1(n1)和F1(n2)(n1不等 于n2)的汉明距离不小于4。编码函数F1(n)的使用方式非常简单，程 序员只需记住A2的名字，使用点号运算符“.”即可获知具体的函数 名字F1。

如图7所示，为解码函数的定义过程，具体地，在步骤S7中，定 义了解码函数F2(n)，用于返回唯一参数n的解码结果。如果参数n是 非法码字，那么将返回一个不合理的解码值(例如-1)，以便客户端 进行判断和处理。

进一步地，如图8所示，为解码函数的使用过程，具体地，对于 两个不同的n1和n2，仅当它俩的汉明距离不小于4且它俩都是合法码 字的时候，F2才返回两个不同的有效解码值，这样能够大幅度减少n1 和n2之间的串码可能性，提高通信数据的检错率，从而提高抗干扰能 力、提高安全性。

更进一步地，解码时利用了静态数组D1，无需申请新内存，因 此运行时的空间复杂度是O(1)。由于静态数组D1里面的元素是有序排 列的，因此解码时可以进行二分法搜索，时间复杂度为7.4O(1)(7.4 ≈log₂169)。二分法搜索过程是，任意给定码字x(x可能是非法码字)， 先判断x与D1的中间元素a的大小关系，如果相等，则x是合法码字， 同时返回a的下标作为解码结果；如果x大于(或小于)中间元素，则 将x与D1的右半部(或左半部)元素的中间元素比较，这样只需x与a 的一次比较，就将搜索范围缩小了一半。如此下去，直到找到x或找 不到x为止。显然，这种折半搜索的方式，最多只需log₂169≈7.4次折 半操作，就能得出结果，因此速度很快。对于28561个一次扩展码字， 仅需log₂28561≈14.8次折半操作，速度仍然很快。

本发明的各个部件实施例可以以硬件实现，或者以在一个或者多 个处理器上运行的软件模块实现，或者以它们的组合实现。本领域的 技术人员应当理解，可以在实践中使用微处理器或者数字信号处理器 (DSP)来实现根据本发明实施例设备中的一些或者全部部件的一些 或者全部功能。本发明还可以实现为用于执行这里所描述的方法的一 部分或者全部的设备或者装置程序(例如，计算机程序和计算机程序 产品)。这样的实现本发明的程序可以存储在计算机可读介质上，或 者可以具有一个或者多个信号的形式。这样的信号可以从因特网网站 上下载得到，或者在载体信号上提供，或者以任何其他形式提供。

本文中所称的“一个实施例”、“实施例”或者“一个或者多个实 施例”意味着，结合实施例描述的特定特征、结构或者特性包括在本 发明的至少一个实施例中。此外，请注意，这里“在一个实施例中” 的词语例子不一定全指同一个实施例。

在此处所提供的说明书中，说明了大量具体细节。然而，能够理 解，本发明的实施例可以在没有这些具体细节的情况下被实践。在一 些实例中，并未详细示出公知的方法、结构和技术，以便不模糊对本 说明书的理解。

应该注意的是上述实施例对本发明进行说明而不是对本发明进 行限制，并且本领域技术人员在不脱离所附权利要求的范围的情况下 可设计出替换实施例。在权利要求中，不应将位于括号之间的任何参 考符号构造成对权利要求的限制。单词“包含”不排除存在未列在权 利要求中的元件或步骤。位于元件之前的单词“一”或“一个”不排 除存在多个这样的元件。本发明可以借助于包括有若干不同元件的硬 件以及借助于适当编程的计算机来实现。在列举了若干装置的单元权 利要求中，这些装置中的若干个可以是通过同一个硬件项来具体体 现。单词第一、第二、以及第三等的使用不表示任何顺序。可将这些 单词解释为名称。

此外，还应当注意，本说明书中使用的语言主要是为了可读性和 教导的目的而选择的，而不是为了解释或者限定本发明的主题而选择 的。因此，在不偏离所附权利要求书的范围和精神的情况下，对于本 技术领域的普通技术人员来说许多修改和变更都是显而易见的。对于 本发明的范围，对本发明所做的公开是说明性的，而非限制性的，本 发明的范围由所附权利要求书限定。

虽然结合附图描述了本发明的实施方式，但是本领域技术人员可 以在不脱离本发明的精神和范围的情况下做出各种修改和变型，这样 的修改和变型均落入由所附权利要求所限定的范围之内。