基于状态空间搜索的控制器局域网协议验证方法

摘要

本发明所述的基于状态空间搜索的控制器局域网协议验证方法包含如下过程：系统建模、模型预处理、模型验证。在建模过程中，构建较为抽象的时间状态自动机模型，状态迁移图通过使用动态规划的思想，实现在避免产生冗余状态下的状态空间图的生成，在控制器局域网软件模型检验中，利用基于分解的状态搜索算法，进一步优化模型的状态搜索空间，使整个系统的验证过程在时间和空间复杂度达到进一步的优化，并将经过算法处理的数据输出转换为检验人员易懂的语言形式。本发明能够有效地验证相关网络协议是否满足要求，缓解验证过程中状态空间爆炸问题，实现的系统验证过程时空复杂度低。

说明书

技术领域

本发明涉及一种在控制器局域网协议模型检验中进行状态空间搜索的优化方法，主要利 用基于状态分解的状态空间搜索算法在缓解状态空间爆炸问题的情况下实现对控制器局域网 协议进行验证，属于计算机技术、无线通信、传感器技术和软件验证技术交叉技术应用领域。

背景技术

控制器局域网（CAN，ControllerAreaNetwork）是国际标准化的串行通信协议，属于现 场总线的范畴，是一种有效支持分布式控制系统的串行通信网络。在当前汽车产业中，基于 安全性、方便性、舒适性、成本的要求，研究人员开发出了许多类型的电子控制系统。这些 系统之间的通信对数据类型、可靠性要求各不相同。由于在电子控制系统中多条总线构成情 况增加，通信线束的数量也随着增加。为了解决现代汽车中庞大的电子控制系统中的通信效 率，减少不断增加的信号线，1986年德国电器商博世公司开发出面向汽车的CAN总线协议。 此后，CAN总线协议通过ISO11898及ISO11519进行了标准化，该协议在欧洲已成为汽车网 络的标准协议。由于CAN总线协议高性能、高可靠性以及独特的设计，该协议越来越受到人 们的重视，被广泛应用于诸多领域。CAN总线协议能够检测出所产生的错误，当信号传输距 离达到10km时，该协议仍可提供高达50kbit/s的数据传输速率。由于CAN总线协议具有很 高的实时性能和应用范围，从位速率最高可达1Mbps的高速网络到低成本多线路的50Kbps 网络都可以任意搭配。因此，CAN总线协议己经在汽车业、航空业、工业控制、安全防护等 领域中得到了广泛应用。

随着CAN总线协议在各个行业和领域的广泛应用，对它的通信格式标准化也提出了更严 格的要求。1991年CAN总线技术规范（Version2.0）制定并发布。该技术规范共包括A和B 两个部分，其中2.0A给出了CAN报文标准格式，而2.0B给出了标准的和扩展的两种格式。 美国的汽车工程学会SAE在2000年提出了J1939协议，此后该协议成为了货车和客车中控 制器局域网的通用标准。

模型检验是对有穷状态系统的一种形式化确认方法，主要通过显式状态搜索或隐式不动 点计算来验证有穷状态并发系统的模态/命题性质，该方法实质是利用计算机的快速计算能 力，通过穷举被检验系统的状态空间中的每一个状态来验证该系统满足特定的形式描述。模 型检验的基本思想是用状态迁移系统(S)表示系统的行为，用模态/时序逻辑公式(F)描述系统 的性质，这样“系统是否满足所期望的性质”就转化为数学问题“状态迁移系统S是否公式F的 一个模型”，用公式表示为S|=F？。对有穷状态系统，这个问题是可判定的，即可以用计算机 程序在有限时间内自动确定。模型检验已被应用于计算机硬件、通信协议、控制系统、安全 认证协议等方面的分析与验证中，取得了令人瞩目的成功，并从学术界辐射到了产业界。模 型检验其基本原理实现为系统建立形式化模型，阐述所要验证的性质，然后用算法去检验该 模型是否满足所述性质。模型检验提供一个完整的系统属性验证框架，模型检验的优点是模 型检验能达到完全自动化的程度，只需用有穷状态模型和逻辑公式分别将系统实现和待验证 的系统规范描述出来，之后的判断过程则完全可以由模型检验工具自动完成，不需要人的参 与；模型检验过程总会以“是”或“否”的结果中止，当以“否”的结果中止时，说明设计或系统 不满足某个给定的性质。此时一个违反性质的行为反例将会被给出，此反例将对理解错误的 真正原因和修正错误提供线索。由于模型检验技术有以上优点，利用它对无线传感器网络进 行同步机制的检验，在其设计阶段尽可能的找出错误。

基于状态分解的状态空间搜索算法是一种适用于有穷状态机的，基于深度优先搜索思想 的优化搜索算法，主要运用于形式化验证方法中时序逻辑是否符合状态迁移系统的验证。对 于一个有穷状态机系统，其中的每一个状态可能包含一个或多个信息，基于状态分解的状态 空间搜索算法通过利用h关键函数将每一个状态的信息分解为关键部分s_real和辅助部分s_aux， 并通过利用选择性散列表和选择性栈的性质使得在对状态模型是否满足对应属性的状态搜索 过程中只关注于关键状态部分，实现搜索时间和空间上的优化。相比于传统深度优先搜索算 法生成的系统状态迁移图，基于状态分解的状态空间搜索算法只探索生成“重要状态空间图”。 换句话说，对于一个给定的分布式系统，通过运用形式化方法将其转化为一个有限的状态迁 移系统TS’和对应的属性集F，其中状态迁移系统TS’可以被分解为独立的状态集S.DBSS， 算法通过遍历迁移系统TS’的部分关键状态，模拟出另外一个被TS’包含的状态迁移系统TS。 直观来讲，给出一些状态属性F，通过在现有的模型检验器核心代码中嵌入基于状态分解的 状态空间搜索算法，模型检验器利用DBSS（TS’，F）算法探索行为像TS’的状态迁移系统 TS是否满足属性集F，从而检验系统的完整性，而不是探索TS’。由于TS是被TS’包含的， 相比在TS’上的深度优先搜索，基于状态分解的状态空间搜索实现了时间和内存的效率，也 缓解了状态空间爆炸问题。

发明内容

技术问题：本发明提供一种基于状态空间搜索的控制器局域网协议验证方法，通过使用 基于状态分解的状态空间搜索算法实现对控制器局域网总线协议模型检验的优化，实现在使 用较少时间和空间的条件下验证控制器局域网协议的完整性。

本发明的目的是建立一种基于状态分解的状态空间搜索算法的控制器区域网软件模型检 验方法，解决控制器局域网软件验证问题，克服验证在规模、动态性和资源约束等方面的挑 战，通过利用控制器局域网形式化模型的状态空间结构特点来缓解状态空间爆炸问题。

技术方案：本发明所述的基于状态空间搜索的控制器局域网协议验证方法包含如下过程： 系统建模、模型预处理、模型验证。在建模过程中，构建较为抽象的时间状态自动机模型， 状态迁移图通过使用动态规划的思想，实现在避免产生冗余状态下的状态空间图的生成，在 控制器局域网软件模型检验中，利用基于分解的状态搜索算法，进一步优化模型的状态搜索 空间，使整个系统的验证过程在时间和空间复杂度达到进一步的优化，并将经过算法处理的 数据输出转换为检验人员易懂的语言形式。

本发明所述的基于状态分解的状态空间搜索算法，通过在对生成的用于检验其性质的状 态图的搜索过程中进行的状态的实时分解，搜索状态空间中的关键状态，缓解模型验证过程 中的空间爆炸问题。

基于状态空间搜索的控制器局域网协议验证方法流程如下：

1).系统建模

11)分析控制器局域网协议，列出协议所有常量和变量；

12)列出节点所有可能状态，所述状态是节点能够稳定维持的抽象化表述，包含一个或 多个参数变量；

13)列出每一可能状态的参数变量，所述参数变量是指状态包含的信息大小，信息内容， 状态生成时间，消息历史，状态环境变量；

14)列出节点各个状态之间转移条件，标注转移过程中参量变化；

15)根据转移条件，在各个状态节点之间建立有向边，建立状态自动机模型；

16)用时序逻辑公式语言描述待验证的模型的所有性质；

2).模型预处理

对状态自动机模型中的状态进行遍历，如果一个状态上其前驱迁移或者后继迁移都为空， 则删除此状态，并对与此状态有关的迁移进行合并；

3).模型性质检验

31)建立栈st，初始化为空，该栈用于存储访问状态空间的访问路径；

311)根据控制器局域网协议内容构建功能函数h(s)，该函数用于分解状态s并返回其重 要状态s_rel，其中参数s为一个表示状态的结构体，该结构体用于记录一个状态的各个属性和 迁移条件，h(s)通过分析当前验证的时序逻辑，将与待验证性质相关的状态的属性和迁移条件 取出并生成新的状态，称为重要状态s_rel，并返回；

312)建立栈CE-stack，初始化为空，该栈用于保存已访问状态s的关键部分h(s)的路径；

313)建立栈reached，初始化为空，该栈用于保存已访问过的状态的关键部分，相同的关 键部分不重复存储；

32)根据模型验证性质初始化状态s_I为系统的最初状态；

33)将最初的状态节点放进栈st，并将s_I标记为已访问；

34)利用功能函数h(s)分解并得到当前访问状态的s_rel部分，将s_rel压进栈CE-stack；

35)判断st是否为空，不为空，则取出栈顶元素s，根据状态转移条件，利用局部偏序简 化算法生成s的临时顽固集t，当顽固集t不为空则转向步骤36），当顽固集t为空则转向步 骤37）；所述局部偏序简化算法是指在模型检测并发执行的不同进程动作的不同次序中，将 局部状态的次序固定，减少重复验证本质上相同的路径，所述顽固集是指当前状态必须执行 的转移条件的集合；

36)判断顽固集t是否为空，若为空则转向步骤35），否则，任意取t中的一个转移条件， 并将其从t中删除，根据此转移条件得到状态s’，利用h(s’)得到s’的关键部分s_rel，将s_rel压入栈CE-stack中；

361)判断s_rel是否在reached中，若不在则将其压入reached中；

362)判断在s’上可使用的状态转移个数T是否大于1，如果大于1，则将s’放进栈st 中，否则可知在以后的搜索过程中不会在s’上进行回溯，不需要放进st中；

363)判断当前待验证性质f是否符合当前状态s’；

3631)如果不满足，那么状态空间搜索停止，立即返回当前出错的状态s’和CE-stack， 其中CE-stack存储的是当前从初始状态s_I到不满足条件的状态s’的一条路径，并转步骤37)；

3632)如果满足，那么转步骤36)；

37)根据状态搜索结果进行分析，将根据以上过程进行模型检验的最终结果展示出来，如 果满足验证性质则告知用户满足的性质，反之则返回不满足的性质，并提供不满足性质的反 例，将不满足性质的完整路径显示出来以供用户调试纠错。

有益效果：

1）本发明提供一种基于状态分解的状态空间搜索算法的控制器局域网模型检验方法，其 完整的验证方法过程包括系统建模、生成状态迁移系统、模型性质验证，整个过程思路清晰 完整，可读性强，尽量将晦涩难懂的相关技术概念、相关算法表述清晰，易于理解。

2）本发明中所述建模过程中，提供一个或一套较为抽象的状态自动机模型，能够将实际 网络中的相关协议转化为数学化的模型形式。

3）本发明中所述模型化简与减枝模块减少自动机中的对验证过程不产生影响的状态，从 而能够实现时空复杂度一定程度的优化。

4）本发明中所述基于分解的状态空间搜索算法，利用状态分解的思想在利用状态迁移图 进行性质验证时通过模拟遍历重要状态空间图，使得整个系统的验证过程时空复杂度达到进 一步的优化效果。

附图说明

图1示例是模型检验基本流程。

图2示例验证流程图。

图3是示例由深度优先搜索算法验证时序逻辑时生成的部分状态搜索图和栈操作。

图4是示例由基于状态分解的状态空间搜索优化算法验证时序逻辑时生成的部分状态空 间搜索图和栈操作。

具体实施方式

下面对本发明附图的某些实施例作更详细的描述。

根据附图1，本发明建立在模型检验技术的基础上，具体实施方式为：

1).系统建模

11)分析控制器局域网协议，列出协议所有常量和变量；

12)列出节点所有可能状态，所述状态是节点能够稳定维持的抽象化表述，包含一个或 多个参数变量；

13)列出每一可能状态的参数变量，所述参数变量是指状态包含的信息大小，信息内容， 状态生成时间，消息历史，状态环境变量；

14)列出节点各个状态之间转移条件，标注转移过程中参量变化；

15)根据转移条件，在各个状态节点之间建立有向边，建立状态自动机模型；

16)用时序逻辑公式语言描述待验证的模型的所有性质；

2).模型预处理

对状态自动机模型中的状态进行遍历，如果一个状态上其前驱迁移或者后继迁移都为空， 则删除此状态，并对与此状态有关的迁移进行合并；

3).模型性质检验

31)建立栈st，初始化为空，该栈用于存储访问状态空间的访问路径；

311)根据控制器局域网协议内容构建功能函数h(s)，该函数用于分解状态s并返回其重 要状态s_rel，其中参数s为一个表示状态的结构体，该结构体用于记录一个状态的各个属性和 迁移条件，h(s)通过分析当前验证的时序逻辑，将与待验证性质相关的状态的属性和迁移条件 取出并生成新的状态，称为重要状态s_rel，并返回；

312)建立栈CE-stack，初始化为空，该栈用于保存已访问状态s的关键部分h(s)的路径；

313)建立栈reached，初始化为空，该栈用于保存已访问过的状态的关键部分，相同的关 键部分不重复存储；

32)根据模型验证性质初始化状态s_I为系统的最初状态；

33)将最初的状态节点放进栈st，并将s_I标记为已访问；

34)利用功能函数h(s)分解并得到当前访问状态的s_rel部分，将s_rel压进栈CE-stack；

35)判断st是否为空，不为空，则取出栈顶元素s，根据状态转移条件，利用局部偏序简 化算法生成s的临时顽固集t，当顽固集t不为空则转向步骤36），当顽固集t为空则转向步 骤37）；所述局部偏序简化算法是指在模型检测并发执行的不同进程动作的不同次序中，将 局部状态的次序固定，减少重复验证本质上相同的路径，所述顽固集是指当前状态必须执行 的转移条件的集合；

36)判断顽固集t是否为空，若为空则转向步骤35），否则，任意取t中的一个转移条件， 并将其从t中删除，根据此转移条件得到状态s’，利用h(s’)得到s’的关键部分s_rel，将s_rel压入栈CE-stack中；

361)判断s_rel是否在reached中，若不在则将其压入reached中；

362)判断在s’上可使用的状态转移个数T是否大于1，如果大于1，则将s’放进栈st 中，否则可知在以后的搜索过程中不会在s’上进行回溯，不需要放进st中；

363)判断当前待验证性质f是否符合当前状态s’；

3631)如果不满足，那么状态空间搜索停止，立即返回当前出错的状态s’和CE-stack， 其中CE-stack存储的是当前从初始状态s_I到不满足条件的状态s’的一条路径，并转步骤37)；

3632)如果满足，那么转步骤36)；

37)根据状态搜索结果进行分析，将根据以上过程进行模型检验的最终结果展示出来，如 果满足验证性质则告知用户满足的性质，反之则返回不满足的性质，并提供不满足性质的反 例，将不满足性质的完整路径显示出来以供用户调试纠错。

具体实例：

1.系统建模

现假设控制器局域网采用层次结构，每个网络节点被赋予一个级别，根节点为0级，第 i级的节点至少能够与一个第（i-1）级得节点通信；局域网部署后，由根节点广播级别发现分 组来启动层次发现阶段，级别发现分组包含节点的编号和级别；邻居节点收到分组后，将自 己的级别设置为分组中的级别加1，然后广播新的级别发现分组；节点收到第i级节点的广播 分组后，记录发送这个广播分组的节点编号，设置自己的级别为（i+1），广播级别为（i+1） 的分组，这个过程持续到网络内每个节点都被赋予一个级别；节点一旦建立自己的级别，就 忽略任何其他级别发现分组，防止网络产生洪泛拥塞，这样一个控制器区域网通信模型就被 建立起来。

1）分析控制器局域网协议，列出所有常量和变量。

常量包括节点编号（本例共2个节点，编号为0，1）。

变量包括等待时间、节点所属层次记录数组等。

2)设置节点的所有可能状态

本例中涉及四种可能的状态：发送态，等待态，应答态，接收态

3)列出每个可能状态包含的参数变量如状态性质(应答态，接收态等)，当前帧传输速率， 消息内容，数据量大小，环境上下文，消息历史等，规定本例中每一个状态只包含状态性质， 消息内容，消息历史和环境上下文四个变量

4)列出各个状态之间转移条件，标注转移过程中参量变化。

转移条件为如下四个：其一，节点处于等待态时，若编号不为0，可转移至发送态；其 二，处于等待态，若编号为0，可转移至发送态或接收态；其三，处于接收态则无条件转移 至应答态；其四，处于发送态，则当消息发送完毕可转化为其他任意一个状态

5)根据列出的所有的转移条件，建立有向边，生成用于性质检验的状态自动机模型

2.模型预处理

优化状态自动机模型，减少对验证过程不产生影响的状态，具体过程为：对状态自动机 模型中的状态进行遍历，如果一个状态上没有时钟解释，并且其前驱迁移或者后继迁移都为 空，则删除此状态，并对与此状态有关的迁移进行合并。

3.模型性质验证

根据生成的状态自动机模型，采用基于状态分解的状态空间搜索方法搜索状态空间图， 来确定模型拥有了某种属性或没有某种属性，如果没有这种属性还要提供一个反例以供调试。

具体过程如下：

检验性质：

定义h函数用于分解当前状态s分别为s_real和s_aux(关键部分状态和辅助部分状态)，本例 中规定消息历史为辅助部分状态，其他状态变量未关键部分。

定义栈stack用于存储访问状态空间的访问路径

定义CE-stack栈用于保存已访问状态s的关键部分h(s)的路径

定义reached栈用于保存已访问过的且状态的关键部分，相同的关键部分不重复存储。

在性质验证过程中采用单纯的深度优先搜索算法搜索状态图得到的状态搜索图和相应的 栈操作如图3

其中黑色圆圈表示除了其消息历史不同，其他状态变量都相同的状态

采用本模型性质检验模块提出的基于状态分解的深度优先搜索算法得到的状态搜索图和 相应的栈操作如图4

那么，对应于不同的属性F，通过使用基于分解的状态空间搜索即可验证属性F是否满 足于状态迁移系统，如果不满足则给出反例。