一种基于系统操作指南的隐通道搜索方法

摘要

本发明公开了一种基于系统操作指南的隐通道搜索方法，首先标识出系统中所有被多个用户共享的对象；对每个对象标识出该对象拥有的所有属性；将属性分成布尔型、数值型、字符型三种类型；对每种类型，依据系统操作指南将引起属性相同变化的高安全级用户的操作序列归结为一类，将引起属性相同变化的低安全级用户的操作序列归结为一类；在高低安全级用户的每一类操作序列中分别随机选取一个操作序列，将两个操作序列按照组合规则组成一个新操作序列集；运行所有新操作序列并记录结果；如果某个新操作序列的执行结果与运行低安全级用户选取的操作序列得到的结果不一致，则新操作序列可用来产生隐通道。适用于面向用户的多级安全系统中的隐通道搜索。

说明书

技术领域

本发明属于信息安全技术领域，涉及一种基于系统操作指南的对多级安全系统进行隐通 道搜索的方案。

背景技术

多级安全系统因为不存在密钥管理、以及对用户透明等优点，所以在军方、企业的内部网络中得到了 广泛应用。但多级安全系统中存在着一个重要的安全隐患，即隐通道问题。

由于隐通道在导致机密性信息泄漏方面所起的作用，美国国防部率先在其发布的可信计算机系统评估 准则（TCSEC）中，将隐通道明确列入评估的指标，规定在B2级及以上高安全等级系统设计和开发中，必 须进行隐通道分析。其后，多个国家都在相应的标准中对隐通道分析作了硬性规定。我国《计算机信息系 统安全保护等级划分准则》（GB 17859-1999）中也规定：对于第四级（结构化保护级）和第五级（访问验 证保护级）的安全系统，系统开发者应彻底搜索隐通道，并根据实际测量或工程估算确定每一个被标识信 道的最大带宽。

彻底搜索隐通道，即标识隐通道的工作是隐通道分析中最为困难的一环。其困难性体现在理论和工程 实践两个方面：第一理论上仍然不够成熟，没有严谨且行之有效的方法；第二实际工作量庞大，手工分析 容易出错，缺乏行之有效的自动工具。目前存在的隐通道搜索方法主要有下面四种。

共享资源矩阵法

共享资源矩阵法由Kemmerer于1983年提出，是迄今为止最为成功的一种隐蔽通道标识方法。该方法的 分析步骤是:

1、分析所有的可信计算基TCB原语操作，确定通过TCB接口用户可见/可修改的共享资 源属性；

2、构造共享资源矩阵，该矩阵的各行对应于用户可见的TCB原语，各列对应于用户可 见/可修改的共享资源属性。如果一个原语可以读一个变量，则将该矩阵项（TCB原语，变量）标记为R。 类似地，如果一个原语可以修改一个变量，则将该矩阵项（TCB原语，变量）标记为M。最后，将既不能 读又不能写的变量合并，分析时将它们视为一个变量。

3、对共享资源矩阵完成传递闭包操作，具体步骤如下:在矩阵中搜索包含标记R的每一项，如果该 项所在的行中出现M标记，则检查包含该M项的所在列。如果在该列的任意一个行中出现R标记，且该 行与原始R项所在列的对应行中没有R标记，则在该矩阵项中增加间接读标记r。重复以上操作，直到矩 阵中无法再增加r项时为止。注意，这里区分r与R仅表明，r为间接读，R为直接读。在今后的分析中， 将r等同地视为R。

4、分析每个矩阵行，找出同时包含R和M的行，并删去其他矩阵行。当一个进程可以读一个变量且 另一个进程可以写该变量时，如果写进程的安全级支配读进程的安全级，就可能产生潜在的隐蔽通道。通 过对矩阵项的分析，可以得到以下4种不同类型的通道:

(1)该通道为合法通道，将它标记为“L”；

(2)从该通道无法获得有用的信息，将它标记为“N”；

(3)发送进程与接收进程是同一个进程，将它标记为“S”；

(4)该通道为潜在的隐蔽通道，将它标记为“P”。

5、分析矩阵所有的项，构造潜在隐蔽通道的实际应用场景。可以构造出实际应用场景的潜在隐蔽通 道，即为真实隐蔽通道。

语法信息流方法

语法信息流方法的分析步骤是，(1)将信息流语义附加在每个语句之后。例如，当b不为常数时，赋 值语句a:＝b产生由b到a的信息流，用a←b表示，并称之为“明流”。类似地，条件语句产生暗流。例如， if x＝a then y:＝b else z:＝c产生的暗流是y←x和z←x。这时，同时存在明流y←b和z←c。(2)定 义安全信息流策略，例如“如果信息从变量b流向变量a，则a的安全级必须支配变量b的安全级”。(3)将 流策略应用于形式化顶层规范或源代码，生成信息流公式。例如，a:＝b的流公式为SL(a)≥SL(b)，其中SL(x) 表示变量x的安全级。(4)证明流公式的正确性。如果无法证明某个流公式的正确性，则需要进一步对语 句进行语义分析，并判断该信息流：(a)是非法流还是伪非法流；(b)是否能够产生真实隐蔽通道，而不 只是潜在隐蔽通道。

语义信息流方法

语义信息流方法的分析步骤是，(1)选择用于隐蔽通道分析的内核原语；(2)确定内核变量的可见性 /可修改性：(i)通过语义分析，确定内核变量的直接可见性/可修改性；(ii)对每个原语生成一个“函 数调用依赖关系”集合FCD；(iii)通过信息流分析，确定内核变量的间接可见性；(iv)在每个原语中解 决变量别名问题；(v)标识在原语间共享的用户进程可见/可修改的变量，消除局部变量；(3)分析共享 变量，并标识隐蔽存储通道。

无干扰方法

无干扰方法的本质是一个用户不应当知道他不支配的其他任何用户的任何动作。他们将可信计算基 TCB视为一个状态机，并定义了两个用户进程之间的无干扰概念。假设状态机有一个初始状态，称一个用 户进程与另一个用户进程是无干扰的，如果从初始状态开始，删除第1个进程所有的输入(等价于从来没有 这些输入)，第2个进程的输出没有任何变化。可以证明，进程之间无干扰具有以下性质:如果一个进程的 输入不能影响另一个进程的输出，则不可能从第1个进程向第2个进程传输信息。

依据上述搜索方法所分析的对象不同可将它们分成基于系统顶级描述和基于系统源代码的搜索方法。 这意味着上述两类方法需要系统的开发者提供详尽的系统顶级描述和源代码，然而在实际的软件开发过程 中开发者为了保护自己的利益不愿意把顶级描述和源代码提供给用户，从而导致用户无法使用目前存在的 方法对系统进行隐通道搜索，进而无法发现系统中存在的机密信息泄露途径。但是用户为了保证机密信息 不被泄露，必须对系统进行隐通道搜索，从而堵住信息泄露的途径。因此现有技术缺少面向用户具有普遍 适用性的隐通道搜索方法。

发明内容

为了解决以上技术问题，本发明提出一种面向用户的基于系统操作指南的隐通道搜索方法。系统操作 指南是开发者必须提供给用户的文档，该方法基于系统操作指南进行搜索，使得分析者在无法获得系统顶 级描述和源代码的情况下也可以搜索隐通道，发现系统中存在的信息泄露途径。具体技术方案如下。

一种基于系统操作指南的隐通道搜索方法，其特征在于包括以下步骤：

步骤一，依据系统操作指南标识出系统中所有被多个用户共享的对象，记为Object₁,Object₂,…, Object_n；

步骤二，依据系统操作指南对每个对象Object_i（1≤i≤n）标识出该对象的属性Property_i,1,…, Property_i,m；

步骤三，对每个属性Property_i,j（1≤i≤n，1≤j≤m），依据属性的类型是布尔类型，数值类型，还是 字符类型，计算相应的操作序列集seq(Property_i,j)；

步骤四，将所有属性Property_i,j（1≤i≤n，1≤j≤m）对应的序列集seq(Property_i,j)合并为集合Com, 对Com中的每一个元素a，运行操作序列a并记录得到的结果，运行由a中低级用户的操作组成的序列并 记录得到的结果，如果两个结果不一致，则断言操作序列a会导致隐通道。

对于布尔类型的属性，所述操作序列集的计算方法包括以下步骤：

步骤A，对于低级用户L，在系统操作指南中随机选择一个使得Property_i,j的值从0变为1的操作序列， 记为oper₁＝o₁₁,...,o_1e；随机选择一个使得Property_i,j的值从1变为0的操作序列，记为oper₂＝o₂₁,...,o_2r；随 机选择一个使得Property_i,j的值保持为0的操作序列，记为oper₃＝o₃₁,...,o_3t；随机选择一个使得Property_i,j的 值保持为1的操作序列，记为oper₄＝o₄₁,...,o_4y；

步骤B，对于高级用户H，在系统操作指南中随机选择一个使得Property_i,j的值从0变为1的操作序 列，记为seq₁=s₁₁,s₁₂,...,s_1q；随机选择一个使得Property_i,j的值从1变为0的操作序列，记为seq₂=s₂₁,..,s_2w；

步骤C，将oper₁与seq₂组合成集合seqoper_1,2，具体组合过程为：序列sequence∈seqoper_1,2当且仅当 sequence的长度为e+w,sequence中的最后一个元素为oper₁中的最后一个元素o_1e，sequence在集合 Set(oper₁)（Set(oper₁)表示由oper₁中的操作构成的集合）上的投影等于oper₁，sequence在集合Set(seq₂) （Set(seq₂)表示由seq₂中的操作构成的集合）上的投影等于seq₂；

步骤D，将oper₂与seq₁组合成集合seqoper_2,1，具体组合过程为：序列sequence∈seqoper_2,1当且仅当 sequence的长度为r+q,sequence中的最后一个元素为oper₂中的最后一个元素o_2r，sequence在集合 Set(oper₂)上的投影等于oper₂，sequence在集合Set(seq₁)上的投影等于seq₁；

步骤E，将oper₃与seq₁组合成集合seqoper_3,1，具体组合过程为：序列sequence∈seqoper_3,1当且仅当 sequence的长度为t+q,sequence中的最后一个元素为oper₃中的最后一个元素o_3t，sequence在集合 Set(oper₃)上的投影等于oper₃，sequence在集合Set(seq₁)上的投影等于seq₁；

步骤F，将oper₄与seq₂组合成集合seqoper_4,2，具体组合过程为：序列sequence∈seqoper_4,2当且仅当 sequence的长度为y+w,sequence中的最后一个元素为oper₄中的最后一个元素o_4y，sequence在集合 Set(oper₄)上的投影等于oper₄，sequence在集合Set(seq₂)上的投影等于seq₂；

步骤G，合并所有的序列集：seq(Property_i,j)＝seqoper_1,2∪seqoper_2,1∪seqoper_3,1∪seqoper_4,2。

对于数值类型的属性，所述操作序列集的计算方法包括以下步骤：

步骤A，对于低级用户L，在系统操作指南中随机选择一个使得Property_i,j的值变大的操作序列，记为 oper₁＝o₁₁,...,o_1e；随机选择一个使得Property_i,j的值变小的操作序列，记为oper₂＝o₂₁,...,o_2r；随机选择一个 使得Property_i,j的值保持不变的操作序列，记为oper₃＝o₃₁,...,o_3t；

步骤B，对于高级用户H，在系统操作指南中随机选择一个使得Property_i,j的值变大的操作序列，记 为seq₁=s₁₁,s₁₂,...,s_1q；随机选择一个使得Property_i,j的值变小的操作序列，记为seq₂=s₂₁,..,s_2w；

步骤C，将oper₁与seq₁组合成集合seqoper_1,1，具体组合过程为：序列sequence∈seqoper_1,1当且仅当 sequence的长度为e+q，sequence中的最后一个元素为oper₁中的最后一个元素o_1e，sequence在集合 Set(oper₁)上的投影等于oper₁，sequence在集合Set(seq₁)上的投影等于seq₁；

步骤D，将oper₂与seq₂组合成集合seqoper_2,2，具体组合过程为：序列sequence∈seqoper_2,2当且仅当 sequence的长度为r+w，sequence中的最后一个元素为oper₂中的最后一个元素o_2r，sequence在集合 Set(oper₂)上的投影等于oper₂，sequence在集合Set(seq₂)上的投影等于seq₂；

步骤E，将oper₃与seq₁组合成集合seqoper_3,1，具体组合过程为：序列sequence∈seqoper_3,1当且仅当 sequence的长度为t+q，sequence中的最后一个元素为oper₃中的最后一个元素o_3t，sequence在集合 Set(oper₃)上的投影等于oper₃，sequence在集合Set(seq₁)上的投影等于seq₁；

步骤（F）将oper₃与seq₂组合成集合seqoper_3,2，具体组合过程为：序列sequence∈seqoper_3,2当且仅当 sequence的长度为t+w，sequence中的最后一个元素为oper₃中的最后一个元素o_3t，sequence在集合 Set(oper₃)上的投影等于oper₃，sequence在集合Set(seq₂)上的投影等于seq₂；

步骤（G）合并所有的序列集：seq(Property_i,j)＝seqoper_1,1∪seqoper_2,2∪seqoper_3,1∪seqoper_3,2。

对于字符类型的属性，所述操作序列集的计算方法包括以下步骤：

步骤A，对于低级用户L，在系统操作指南中随机选择一个使得Property_i,j的长度变大的操作序列，记 为oper₁＝o₁₁,...,o_1e；随机选择一个使得Property_i,j的长度变小的操作序列，记为oper₂＝o₂₁,...,o_2r；随机选择 一个使得Property_i,j的长度保持不变的操作序列，记为oper₃＝o₃₁,...,o_3t；

步骤B，对于高级用户H，在系统操作指南中随机选择一个使得Property_i,j的长度变大的操作序列， 记为seq₁=s₁₁,s₁₂,...,s_1q；随机选择一个使得Property_i,j的长度变小的操作序列，记为seq₂=s₂₁,..,s_2w；随机选择 一个使得Property_i,j的长度保持不变的操作序列，记为seq₃＝s₃₁,...,s_3u；

步骤C，将oper₁与seq₁组合成集合seqoper_1,1，具体组合过程为：序列sequence∈seqoper_1,1当且仅当 sequence的长度为e+q，sequence中的最后一个元素为oper₁中的最后一个元素o_1e，sequence在集合 Set(oper₁)上的投影等于oper₁，sequence在集合Set(seq₁)上的投影等于seq₁；

步骤D，将oper₂与seq₂组合成集合seqoper_2,2，具体组合过程为：序列sequence∈seqoper_2,2当且仅当 sequence的长度为r+w，sequence中的最后一个元素为oper₂中的最后一个元素o_2r，sequence在集合 Set(oper₂)上的投影等于oper₂，sequence在集合Set(seq₂)上的投影等于seq₂；

步骤E，将oper₃与seq₁组合成集合seqoper_3,1，具体组合过程为：序列sequence∈seqoper_3,1当且仅当 sequence的长度为t+q，sequence中的最后一个元素为oper₃中的最后一个元素o_3t，sequence在集合 Set(oper₃)上的投影等于oper₃，sequence在集合Set(seq₁)上的投影等于seq₁；

步骤F，将oper₃与seq₂组合成集合seqoper_3,2，具体组合过程为：序列sequence∈seqoper_3,2当且仅当 sequence的长度为t+w，sequence中的最后一个元素为oper₃中的最后一个元素o_3t，sequence在集合 Set(oper₃)上的投影等于oper₃，sequence在集合Set(seq₂)上的投影等于seq₂；

步骤G，合并所有的序列集：seq(Property_i,j)＝seqoper_1,1∪seqoper_2,2∪seqoper_3,1∪seqoper_3,2。

本发明具有有益效果。本发明提出的一种基于系统操作指南的隐通道搜索方法，可以使用户在无法获 取顶级形式化描述或者源代码的情况下亦能搜索隐通道。系统操作指南是所有开发者必须提供给用户的说 明文档，本发明基于系统操作指南的隐通道搜索方法对用户来说具有普遍适用性的，使得用户对隐通道的 搜索不再于依赖于系统的开发者。

附图说明

图1是基于系统操作指南中的隐通道搜索流程。

图2是布尔类型下操作序列集的选取流程。

图3是数值类型下操作序列集的选取流程。

图4是字符类型下操作序列集的选取流程。

具体实施方式

下面根据附图对本发明的技术方案做进一步详细说明。

在多级安全系统中文件夹是一个非常普通的对象，当文件夹被多个用户共享时，为了保证信息的机密 性，安全机制要求低安全级用户只能往文件夹中写数据，但是不能读数据，高安全级用户可以读文件夹中 的数据，也可以往文件夹中写数据。由于安全机制的监控，高安全级用户不能直接通过文件夹给低安全级 用户传递信息。

文件夹至少具有两个属性：maxsize和currentsize，其中maxsize规定了文件夹空间的最大值，currentsize 指定了文件夹当前的空间大小。高安全级用户可以执行命令mf_H(size_H)来在文件夹中创建一个大小为size_H且不超过maxsize的文件，低安全级用户可以执行命令mf_L(size_L)来在文件夹中创建一个大小为size_L且不超 过maxsize的文件。currentsize是数值型，操作oper₁＝mf_L(size_L)和seq₁＝mf_H(size_H)都是使得currentsize变大 的操作序列，按照3.2）中的Step3，组合成的集合seqoper_1,1＝{a＝(mf_H(size_H),mf_L(size_L))}。假设当前文件 夹的大小为0，即currentsize＝0，执行序列a↓_L后得到的输出f(a↓_L)为“创建成 功”，执行a后得到的输出f(a)是“创建失败”，因此f(a)≠f(a↓_L)。高级用户可以通过不执行命令 mf_H(size_H)来向低级用户传递信息“0”，通过执行命令mf_H(size_H)来向低级用户传递信息“1”。

基于系统操作指南的隐通道搜索的基本流程如下。

如图1所示，搜索隐通道的基本步骤如下：

步骤（1）依据系统操作指南标识出系统中所有被多个用户共享的对象，记为Object₁,Object₂,…, Object_n；

步骤（2）依据系统操作指南中对每个对象Object_i（１≤i≤n）标识出该对象的属性Property_i,1,…, Property_i,m；

步骤（3）对每个属性Property_i,j（1≤i≤n，1≤j≤m），依据属性的类型是布尔类型，数值类型，还 是字符类型，计算相应的操作序列集seq(Property_i,j)；

步骤（4）将所有属性Property_i,j（1≤i≤n，1≤j≤m）对应的序列集seq(Property_i,j)合并得到集合Com, 对Com中的每一个元素a，运行操作序列a并记录得到的结果，运行a中低级用户的操作组成的序列并记 录得到的结果，如果两个结果不一致，则断言操作序列a会导致隐通道。

布尔类型下操作序列集的选取流程如下。

如图2所示，布尔类型下操作序列集的选取步骤如下：

步骤（1）对于低级用户L，在系统操作指南中随机选择一个使得Property_i,j的值从0变为1的操作序 列，记为oper₁＝o₁₁,...,o_1e；随机选择一个使得Property_i,j的值从1变为0的操作序列，记为oper₂＝o₂₁,...,o_2r； 随机选择一个使得Property_i,j的值保持为0的操作序列，记为oper₃＝o₃₁,...,o_3t；随机选择一个使得Property_i,j的值保持为1的操作序列，记为oper₄＝o₄₁,...,o_4y；。

步骤（2）对于高级用户H，在系统操作指南中随机选择一个使得Property_i,j的值从0变为1的操作 序列，记为seq₁=s₁₁,s₁₂,...,s_1q；随机选择一个使得Property_i,j的值从1变为0的操作序列，记为seq₂=s₂₁,..,s_2w。

步骤（3）对oper₁与seq₂进行合并，合并后的序列组成的集合记为seqoper_1,2。seqoper_1,2的生成过程如 下：序列sequence∈seqoper_1,2当且仅当sequence的长度为e+w，sequence中的最后一个元素为oper₁中的最 后一个元素o_1e，sequence在集合Set(oper₁)（Set(oper₁)表示由oper₁中的操作构成的集合）上的投影等于 oper₁，sequence在集合Set(seq₂)（Set(seq₂)表示由seq₂中的操作构成的集合）上的投影等于seq₂。

步骤（4）对oper₂与seq₁进行合并，合并后的序列组成的集合记为seqoper_2,1。seqoper_2,1的生成过程如 下：序列sequence∈seqoper_2,1当且仅当sequence的长度为r+q，sequence中的最后一个元素为oper₂中的最 后一个元素o_2r，sequence在集合Set(oper₂)上的投影等于oper₂，sequence在集合Set(seq₁)上的投影等于 seq₁。

步骤（5）对oper₃与seq₁进行合并，合并后的序列组成的集合记为seqoper_3,1。seqoper_3,1的生成过程如 下：序列sequence∈seqoper_3,1当且仅当sequence的长度为t+q，sequence中的最后一个元素为oper₃中的最 后一个元素o_3t，sequence在集合Set(oper₃)上的投影等于oper₃，sequence在集合Set(seq₁)上的投影等于seq₁。

步骤（6）对oper₄与seq₂进行合并，合并后的序列组成的集合记为seqoper_4,2。seqoper_4,2的生成过程如 下：序列sequence∈seqoper_4,2当且仅当sequence的长度为y+w，sequence中的最后一个元素为oper₄中的最 后一个元素o_4y，sequence在集合Set(oper₄)上的投影等于oper₄，sequence在集合Set(seq₂)上的投影等于 seq₂。

步骤（7）合并所有的序列集，即令seq(Property_i,j)＝seqoper_1,2∪seqoper_2,1∪seqoper_3,1∪seqoper_4,2。

数值类型下操作序列集的选取流程如下

如图3所示，数值类型下操作序列集的选取步骤如下：

步骤（1）对于低级用户L，在系统操作指南中随机选择一个使得Property_i,j的值变大的操作序列，记 为oper₁＝o₁₁,...,o_1e；随机选择一个使得Property_i,j的值变小的操作序列，记为oper₂＝o₂₁,...,o_2r；随机选择一 个使得Property_i,j的值保持不变的操作序列，记为oper₃＝o₃₁,...,o_3t。

步骤（2）对于高级用户H，在系统操作指南中随机选择一个使得Property_i,j的值变大的操作序列， 记为seq₁=s₁₁,s₁₂,...,s_1q；随机选择一个使得Property_i,j的值变小的操作序列，记为seq₂=s₂₁,..,s_2w。

步骤（3）对oper₁与seq₁进行合并，合并后的序列组成的集合记为seqoper_1,1。seqoper_1,1的生成过程如下： 序列sequence∈seqoper_1,1当且仅当sequence的长度为e+q，sequence中的最后一个元素为oper₁中的最后一 个元素o_1e，sequence在集合Set(oper₁)上的投影等于oper₁，sequence在集合Set(seq₁)上的投影等于seq₁。

步骤（4）对oper₂与seq₂进行合并，合并后的序列组成的集合记为seqoper_2,2。seqoper_2,2的生成过程如 下：序列sequence∈seqoper_2,2当且仅当sequence的长度为r+w，sequence中的最后一个元素为oper₂中的最 后一个元素o_2r，sequence在集合Set(oper₂)上的投影等于oper₂，sequence在集合Set(seq₂)上的投影等于 seq₂。

步骤（5）对oper₃与seq₁进行合并，合并后的序列组成的集合记为seqoper_3,1。seqoper_3,1的生成过程如 下：序列sequence∈seqoper_3,1当且仅当sequence的长度为t+q，sequence中的最后一个元素为oper₃中的最 后一个元素o_3t，sequence在集合Set(oper₃)上的投影等于oper₃，sequence在集合Set(seq₁)上的投影等于seq₁。

步骤（6）对oper₃与seq₂进行合并，合并后的序列组成的集合记为seqoper_3,2。seqoper_3,2的生成过程如 下：序列sequence∈seqoper_3,2当且仅当sequence的长度为t+w，sequence中的最后一个元素为oper₃中的最 后一个元素o_3t，sequence在集合Set(oper₃)上的投影等于oper₃，sequence在集合Set(seq₂)上的投影等于 seq₂。

步骤（7）合并所有的序列集，即令seq(Property_i,j)＝seqoper_1,1∪seqoper_2,2∪seqoper_3,1∪seqoper_3,2。

字符类型下操作序列集的选取流程如下

如图4所示，字符类型下操作序列集的选取步骤如下：

步骤（1）对于低级用户L，在系统操作指南中随机选择一个使得Property_i,j的长度变大的操作序列， 记为oper₁＝o₁₁,...,o_1e；随机选择一个使得Property_i,j的长度变小的操作序列，记为oper₂＝o₂₁,...,o_2r；随机选 择一个使得Property_i,j的长度保持不变的操作序列，记为oper₃＝o₃₁,...,o_3t。

步骤（2）对于高级用户H，在系统操作指南中随机选择一个使得Property_i,j的长度变大的操作序列， 记为seq₁=s₁₁,s₁₂,...,s_1q；随机选择一个使得Property_i,j的长度变小的操作序列，记为seq₂=s₂₁,..,s_2w。

步骤（3）对oper₁与seq₁进行合并，合并后的序列组成的集合记为seqoper_1,1。seqoper_1,1的生成过程如下： 序列sequence∈seqoper_1,1当且仅当sequence的长度为e+q，sequence中的最后一个元素为oper₁中的最后一 个元素o_1e，sequence在集合Set(oper₁)上的投影等于oper₁，sequence在集合Set(seq₁)上的投影等于seq₁。

步骤（4）对oper₂与seq₂进行合并，合并后的序列组成的集合记为seqoper_2,2。seqoper_2,2的生成过程如 下：序列sequence∈seqoper_2,2当且仅当sequence的长度为r+w，sequence中的最后一个元素为oper₂中的最 后一个元素o_2r，sequence在集合Set(oper₂)上的投影等于oper₂，sequence在集合Set(seq₂)上的投影等于 seq₂。

步骤（5）对oper₃与seq₁进行合并，合并后的序列组成的集合记为seqoper_3,1。seqoper_3,1的生成过程如 下：序列sequence∈seqoper_3,1当且仅当sequence的长度为t+q，sequence中的最后一个元素为oper₃中的最 后一个元素o_3t，sequence在集合Set(oper₃)上的投影等于oper₃，sequence在集合Set(seq₁)上的投影等于seq₁。

步骤（6）对oper₃与seq₂进行合并，合并后的序列组成的集合记为seqoper_3,2。seqoper_3,2的生成过程如 下：序列sequence∈seqoper_3,2当且仅当sequence的长度为t+w，sequence中的最后一个元素为oper₃中的最 后一个元素o_3t，sequence在集合Set(oper₃)上的投影等于oper₃，sequence在集合Set(seq₂)上的投影等于 seq₂。

步骤（7）合并所有的序列集，即令seq(Property_i,j)＝seqoper_1,1∪seqoper_2,2∪seqoper_3,1∪seqoper_3,2。