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

摘要

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

目录

封面

声明

中文摘要

英文摘要

目录

图表清单

注释表

缩略词

第一章 绪论

1.1 课题背景和意义

1.2 关键因素分析研究现状

1.3 本文的主要研究工作

1.4 本文的内容安排

第二章 关键因素分析基础——基于序偶的序列随机性分析

2.1 随机数与随机序列

2.2 典型随机序列产生过程

2.3 一种基于序偶的序列随机性分析方法

第三章 关键因素分析中的排序算法——缫丝排序

3.1 研究意义

3.2 算法思想

3.3 算法设计

3.4 算法效率分析

3.5 与其他改进方案的比较

3.6 与自适应排序库函数的比较

3.7 算法小结

第四章 基于序列随机性的关键因素分析方案

4.1 关键因素分析与序列随机性分析的关系

4.2 键值与键码序

4.3 方案思想

4.4 方案设计

4.5 方案细节

第五章 关键因素分析的应用

5.1 关键因素分析在DES中的验证性应用

5.2 关键因素分析在确定性系统中的应用

5.3 关键因素分析在复杂巨系统中的应用

第六章 总结与展望

6.1 总结

6.2 展望

参考文献

致谢

在学期间的研究成果及发表的学术论文