基于序列随机性的系统关键因素分析

论文摘要

关键因素分析是系统分析尤其是系统安全分析领域一项重要的基础性工作，是进行系统应用和系统评测的前提条件。本文从设计一种新型的序列随机性分析方法出发，将该思想运用在系统关键因素分析中，对可以抽象出因素键码序的广义系统，形成了相比现有方法更为简单有效的系统关键因素分析方法，同时比传统的概率统计方法具有更广泛的适用性。随后在包括确定性加密方案、广义安全协议和复杂巨系统在内的多种确定性系统和随机系统中验证了这种关键因素查找方案的有效性，主要工作如下：1.提出并实现了一种新型的序列随机性分析方案。该方案通过分析随机序列中序偶出现的方式，可以在仅知随机序列结果和部分确定性因素键码序的情况下，定量分析随机系统中随机因素的影响力大小，从而对随机系统的随机性强弱进行客观有效的评价。对于计算机产生的伪随机序列，该方案可用于评价伪随机序列发生器的性能，相比传统的等价性证明法和结果检验法，该方案在初等数学基础上即可完成，并能在产生机理上保证随机序列发生器的有效性。2.设计实现了一种用于对系统中因素影响力进行排序的高速排序算法——缫丝排序。该算法在经过海量实验数据验证后被证实是一种优于现有经典最优排序算法的普适性排序算法。通过将元素按照主要影响因素的差异进行分离合并，缫丝排序在较小排序规模（待排元素数量N＜500000）下比最快的快速排序快15%，在大型排序规模（待排元素数量N>500000）下比最快的非递归合并排序快10%，该算法的相关研究已被《计算机学报》接受，将于2012年发表。3.提出了一种系统关键因素分析方法。该方法借鉴了前述序列随机性分析方案，可以用于定量地对一个所有因素已知的确定性系统给出因素的影响力比值，或者对一个仅知部分因素的不确定系统给出所有已知因素和随机因素的影响力比值估计，对相关因素进行定性判断，进而找出这些系统中的关键因素或相对关键因素。4.设计实现了上述系统关键因素分析方法并对有效性进行了验证。本文随后设计实现了这种新型的系统关键因素分析方法，并用该方法成功发现了以下系统中的关键因素：DES加密算法中的关键因素S盒和P置换——这是一个纯验证性实验；MD4中的三组均等影响力循环——这是一个半验证半归纳性实验；以及影响人口平均寿命的关键因素查找——这是一个复杂巨系统中的完全归纳性实验。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 课题背景和意义
• 1.1.1 一般述评
• 1.1.2 随机系统中的随机性检验
• 1.1.3 确定性系统中的关键因素查找
• 1.1.4 半确定性系统中的脆弱性分析
• 1.2 关键因素分析研究现状
• 1.3 本文的主要研究工作
• 1.4 本文的内容安排
• 第二章 关键因素分析基础——基于序偶的序列随机性分析
• 2.1 随机数与随机序列
• 2.1.1 随机数
• 2.1.2 随机序列
• 2.2 典型随机序列产生过程
• 2.3 一种基于序偶的序列随机性分析方法
• 2.3.1 算法思想
• 2.3.2 算法设计
• 2.3.3 算法细节
• 2.3.4 算法实现
• 第三章 关键因素分析中的排序算法——缫丝排序
• 3.1 研究意义
• 3.2 算法思想
• 3.3 算法设计
• 3.3.1 算法伪代码
• 3.3.2 滚轴数量的确定
• 3.3.3 滚轴数量结构
• 3.4 算法效率分析
• 3.4.1 时间复杂度
• 3.4.2 空间复杂度
• 3.4.3 效率测试实验
• 3.4.4 结果分析与数值修正
• 3.5 与其他改进方案的比较
• 3.6 与自适应排序库函数的比较
• 3.7 算法小结
• 第四章 基于序列随机性的关键因素分析方案
• 4.1 关键因素分析与序列随机性分析的关系
• 4.2 键值与键码序
• 4.2.1 响应个体
• 4.2.2 键值
• 4.2.3 键码序
• 4.3 方案思想
• 4.4 方案设计
• 4.5 方案细节
• 4.5.1 键值区分度
• 4.5.2 互逆因素处理
• 4.5.3 相同键值的处理
• 4.5.4 因素相关性与同源因素
• 4.5.5 反推因素的线性加和处理
• 第五章 关键因素分析的应用
• 5.1 关键因素分析在 DES 中的验证性应用
• 5.1.1 DES 操作的备选因素
• 5.1.2 对基本操作的单独测试
• 5.1.3 运用线性加和方法的 S 盒单独测试
• 5.1.4 DES 关键步骤综合测试
• 5.1.5 小结
• 5.2 关键因素分析在确定性系统中的应用
• 5.2.1 MD4 的备选因素
• 5.2.2 测试结果
• 5.2.3 小结
• 5.3 关键因素分析在复杂巨系统中的应用
• 5.3.1 人均预期寿命
• 5.3.2 相关数据准备
• 5.3.3 测试结果
• 5.3.4 小结
• 第六章 总结与展望
• 6.1 总结
• 6.2 展望
• 参考文献
• 致谢
• 在学期间的研究成果及发表的学术论文