根据物联网操作系统安全性设计的需求，同时结合在经典线性时态逻辑、逻辑程序设计、形式化模型检测理论方面的研究与工程实践探索，提出了一种应用于物联网操作系统安全性设计的方法论，并进行了工程原型验证。实践证明该方法的效果符合预期，不仅适合物联网操作系统的安全性设计，也可以进一步推广到其他安全性要求较高的软件产品设计领域。
中文引用格式： 张华强，李凯航，王继刚. 基于线性时态逻辑的物联网操作系统安全性设计[J].电子技术应用，2020，46(2)：92-97，102.
英文引用格式： Zhang Huaqiang，Li Kaihang，Wang Jigang. Safety design of IoT operating system based on linear temporal logic[J]. Application of Electronic Technique，2020，46(2)：92-97，102.
随着物联网技术的发展，物联网设备安全性问题将是急需解决的核心问题之一。同时，在保障物联网设备安全的所有措施中操作系统层面的安全是重中之重，从本质上讲，可以说物联网操作系统的安全性直接决定了整个物联网设备系统的可靠性。本文在上述背景下提出了一套行之有效的针对物联网操作系统的安全性设计理论，目的是解决上述核心问题。传统的操作系统设计方法主要依赖于人的以往经验和简单的逻辑分析，因此无法从根本上保证操作系统设计的安全性和正确性。形式化方法的核心就是形式化语言，以及基于形式化语言构建出来的形式化模型。其基础思路是将高可靠性系统用语义明确的形式化语言进行建模，采用模型检测、定理证明的方法对系统目标属性进行正确性推演和验证。因此，采用该方法进行操作系统的设计和验证能够保证操作系统的安全性和确定性[1-2]。经过大量的工程实践比较与研究，本文提出了基于线性时态逻辑的操作系统形式化设计理论模型[2]，如图1所示。
(1)一阶数理逻辑+集合论建立顶层数理逻辑模型，该模型是原始需求的数学规格化描述，是进一步设计求精和验证的依据；(2)线性时态逻辑表达式,是时态逻辑的规格化描述；(3)针对并发体描述抽象的第二步线性时态逻辑规格化描述[3]；(4)针对线性时态逻辑规格化描述的模型验证[3-5]。下面结合图1的模型以开源物联网操作系统Zephyr的一个核心内存管理功能为例，说明线性时态逻辑在操作系统内核安全性、正确性设计中的具体应用。本案例基于Zephyr内存分配器功能进行需求建模、设计求精和验证。
3.1 顶层逻辑模型设计
按照在图1中描述的形式化方法，首先要对内存分配需求进行顶层逻辑建模。为了更好地兼容后面线性时态逻辑的求精和验证，本文选用目前在业界成熟应用的TLA+作为建模工具。顶层的逻辑模型首先考虑构造一个四叉树模型来表示内存池，树中的每一个节点代表一个内存块，每一层的大小一致，从根到叶子降序排列，允许多线程访问。选用TLA+的Record+Function模型来表达这一概念，如图2所示。
图2中k_mem_pool为一个record模型，max_sz是这颗四叉树顶层最大内存块尺寸，levels是一个function用来表示树的每一层拥有的空闲内存块，每一层空闲块用集合来表达。下面考虑两个基本概念：合适尺寸的内存块和裂解概念。合适尺寸内存块可以用数学概念表达，如图3所示。
对于内存块裂解概念，需要先考虑一个基本引理，即裂解过程需要一个基于树的层次区间进行，本文根据裂解层次的开始、结束和释分配层级设计一套数学公式来表达这个裂解过程[4]，如图4所示。
最后综合上述分析过程，内存分配的模型描述如图5所示。
3.2 线性时态逻辑模型求精
根据顶层逻辑模型的规格化描述，将公式里的OPERATOR进一步展开成状态流用时态逻辑进行表达。这里提出一个技巧性原则：如需求描述涉及并发体访问，则可以先考虑非并发模型的求精过程，之后再逐步加入针对并发体访问逻辑的时序状态描述。实践证明这样求精的效率非常高。非并发的时态逻辑求精如图6所示。
这样可以基于上述非并发时态逻辑简单增加一个如图7所示的终止条件。
对非并发体时态逻辑状态机能正常终止验证通过后，再增加图8所示的并发体的时态逻辑。
3.3 时态属性安全性验证
通过对顶层逻辑模型求精成线性时态逻辑公式，在时态逻辑层面就可以借助于TLA+的模型检查器TLC进行时态属性验证。求精到时态逻辑公式实际上有两个目的：(1)求精之后的模型与底层的目标代码逻辑已经非常接近，便于将验证过的模型直接转换成目标代码实现；(2)对时态逻辑模型，可以直接构造时态属性进行模型检查[6-7]。下面来看上述时态逻辑模型的验证思路，首先满足非并发条件下单线程访问程序最终能够结束，即图7所示的终结条件。属性需要得到满足，使用TLC模型检查的配置及结果如图9、图10所示。
在保证非并发单线程执行模型正确后，开始在此基础上增加对并发模型的属性检查，即所有并发体访问都要保证能够正常结束，不会发生死锁、忙等、空等等非法状态，需要满足如图11所示的终止条件。
使用TLC模型检查器的参数配置及检查结果如图12、图13所示。
由于时态模型在并发访问层面上是具有归纳性质的，因此这里选取10个线程集合进行验证即可。可以看到，上述模型检查的结果验证了时态逻辑模型对于多线程并发访问是安全的（可以正常终止），此外从图7公式分析单线程模型只有L4状态，如图14所示。
由于该状态涉及对全局变量k_mem_pool的修改，从代码执行性能角度可以考虑将L4状态转换成目标代码时加锁，其他状态模型转换时不必加锁，如果使用关开中断来实现锁可以保证并发性能最优化[2]。
3.4 时态属性正确性验证
上面使用时态属性进行了软件模型安全性验证，最终的目标是在安全性的基础上让设计模型满足预期(即正确性)[8]。对于四叉树结构，假设同时有N个线程在访问这个分配器接口，由于分配器的模型本身具有归纳性质，可以简化正确性的验证模型为N个线程同时从初始化四叉树模型中申请大小相同的内存块所要满足的预期属性。该属性的规格化描述如下：
根据模型的归纳性质将N设置为3，预期属性如图17所示。
为了计算申请内存块在四叉树上面裂解的层数和最终四叉树裂解层所包含的空闲内存块数，引入两个辅助操作函数进行计算，如图18所示。
这样就可以在TLC模型检查器中增加正确性属性进行检查，如图19所示。
遗憾的是如图20所示的模型检查没有通过，证明模型设计存在问题，需要根据TLC反馈的错误进行进一步分析问题产生的原因。
经过对TLC Error的分析，这里面包括两个关键错误原因：(1)四叉树裂解过程中存在可以被其他线程所抢占的时间空隙，会导致内存分配错误，从而产生时序状态违例；(2)L3状态的内存分配可以被其他线程所抢占造成当前线程内存分配计算的free_l、alloc_l游标与被抢占后的四叉树模型不一致，从而导致内存分配失败产生时序违例。针对这两种情况，考虑将L3、L4状态进一步优化，如图21和图22所示。
优化后考虑将裂解过程中层间内存块提取的裂解操作合并成一个状态成为一个原子操作，然后增加L4状态下的判断：如果裂解到当前层为空而又不是alloc_l标识的最后一层，则证明裂解过程中存在其他线程抢占情况，重新回到L1状态重新计算内存分配的格局游标free_l和alloc_l，这样就可以保证多线程抢占条件下内存分配的正确性。为了防止TLC检查发生stutterring，将时态修改为如图23所示。
图24所示表示修正后的时态逻辑已经通过正确性检查。可以直接使用验证过的数学模型进行目标代码编写和测试。上述案例说明形式化方法可以从系统设计层面就能保证需求实现的完整性和设计模型的安全性、正确性。对于物联网操作系统的需求概念模型设计与验证使用线性时态逻辑来做是比较高效的选择。使用本文提出的设计方法可以在顶层逻辑程序设计阶段就将需求概念模型进行精确描述，即使是错误的模型或在求精设计阶段存在BUG，也可以通过时态逻辑的属性验证发现并进行修改优化。使用线性时态逻辑作为顶层逻辑模型的求精既保证了与顶层需求模型的一致性，又保证了求精模型可以在实现层面很容易向目标代码转换。这部分虽然只能做到部分形式化，但是只需经过简单的目标测试就可以完成产品目标代码最终的验证工作。本文提出的理论方法对于其他对安全性和可靠性要求较高的软件设计领域也具有极高的参考价值。
参考文献
[1] LAMPORT L.Specifying systems[M].Boston：Pearson Education，Inc.，2002.
[2] ABELSON H，SUSSMAN G J，SUSSMAN J.Structure and interpretation of computer programs[M].Cambridge，Massachusetts London，England：The MIT Press，1996.
[3] 朱峰，鲁征浩，朱青.形式化验证在处理器浮点运算单元中的应用[J].电子技术应用，2017，43(2)：29-32.
[4] ROSEN K H.离散数学及其应用(原书第七版)[M].徐六通，杨娟，吴斌，译.北京：机械工业出版社，2017.
[5] 张杰，王少超，关永.基于形式化方法的有限域乘法器的建模与验证[J].电子技术应用，2018，44(1)：109-113.
[6] Yu Yuan，MANOLIOS P，LAMPORT L.Model checking TLA+ specifications[C].Lecture Notes in Computer Science，Number 1703，Springer-Verlag，1999：54-66.
[7] 贺江，蒲宇亮，李海波，等.一种基于OpenCL的高能效并行KNN算法及其GPU验证[J].电子技术应用，2016，42(2)：14-16.
[8] NIPKOW T，PAULSON L C，WENZEL M.高阶逻辑辅助证明系统[M].陈光喜，刘卓军，译.北京：北京理工大学出版社，2013.
作者信息：
张华强，李凯航，王继刚
(中兴通讯成都研发中心，四川 成都610041)
原创声明：此内容为AET网站原创，未经授权禁止转载。
