下载文档原格式
©2004 Journal of Software 软件学报题目*作者名1+, 作者2, 作者名31(单位全名部门(系)全名,省市(或直辖市) 邮政编码2(单位全名部门(系)全名,省市(或直辖市) 邮政编码)3(单位全名部门(系)全名,省市(或直辖市) 邮政编码)NAME Name-Name1+, NAME Name2, NAME Name-Name312(Department of ****, University, City ZipCode, China)3(Department of ****, University, City ZipCode, China)+ Corresponding author: Phn +86-**-****-****, Fax +86-**-****-****, E-mail: ****, http://****Name NN, Name N, Name NN. Title. Journal of Software/1000-9825/15/0000.htmAbstract:Key words:摘要: *摘要内容.*关键词: *关键词;关键词*中图法分类号: ****文献标识码: A*正文部分1 一级标题1.1 二级标题1.1.1三级标题定理1(******). *定理内容.* [“定义”、“算法”等的排版格式与此相同]证明:*证明过程.* [“例”等的排版格式相同]*正文部分致谢*致谢内容*Supported by the **** Foundation of China under Grant No.****, **** (基金中文完整名称); the **** Foundation of China under Grant No.****, ****(基金中文完整名称作者简介: 作者名(出生年－),性别,****(籍贯,具体到市、县或地区)人,学位(或目前学历),职称,主要研究领域为*****,****;作者(出生年－),性别,学位(或目前学历),职称,主要研究领域为****,****;作者名(出生年－),性别,学位(或目前学历),职称,主要研究领域为2Journal of Software 软件学报 2004,15(1)References[1] 作者. 出版年,卷号(期号):起始页码. [期刊][2] 作者. 书名. 版次(初版不写), 出版地(城市名): 出版者, 出版年. 起始页码(非必要项). [书籍][3] 作者. 题目. In (中文用“见”): 整本文献的编者姓名ed (多编者用eds). 文集实际完整名称. 出版地(城市名): 出版者, 出版年. 起止页码. [会议录(论文集、论文汇编等)][4]著者. 题名. 学位, 学位授予单位, 出版年. [学位论文][5] Author. Title. Technical Report, Report No., Publishing place (city name): Publisher, Year (in Chinese with English abstract). [科技报告]附中文参考文献: [5] 著者.题名.科技报告,报告号,出版地(或单位所在地):出版者(或单位),出版年.。
2022年南京理工大学数据科学与大数据技术专业《操作系统》科目期末试卷B（有答案）一、选择题1、假设5个进程P0、P1、P2、P3、P4共享3类资源R1、R2、R3.这些资源总数分别为18、6、22。
T0时刻的资源分配情况（见表），此时存在的一个安全序列是（）。
A. P0, P2, P4, P1, P3B. P1, P0, P3, P4, P2C. P2, P1, P0, P3, P4D. P3, P4, P2, P1, P02、下列关于批处理系统的叙述中，正确的是（）I.批处理系统允许多个用户与计算机直接交互II.批处理系统分为单道批处理系统和多道批处理系统III.中断技术使得多道批处理系统的1/O设备可与CPU并行工作A.仅II、IIIB.仅IIC.仅I、IID. 仅I、III3、若系统中有5台绘图仪，有多个进程需要使用两台，规定每个进程一次仪允许申请一台，则最多允许（）个进程参与竞争，而不会发生死锁。
A.5B.2C.3D.44、若某单处理器多进程系统中有多个就绪进程，则下列关于处理器调度的叙述中，错误的是（）。
A.在进程结束时能进行处理器调度B.创建新进程后能进行处理器调度C.在进程处于临界区时不能进行处理器调度D.在系统调用完成并返回用户态时能进行处理器调度5、下列进程调度算法中，综合考虑进程等待时间和执行时间的是（）A.时间片轮转调度算法B.短进程优先调度算法C.先来先服务调度算法D.高响应比优先调度算法6、虚拟设备是通过（）技术实现的。
A.并行B.通道C.SPOOLingD.虚拟存储7、CPU输出数据的速度远远高于打印机的打印速度，为解决这矛盾可采用（）。
A.并行技术B.通道技术C.缓冲技术D.虚拟技术8、在一个文件被用户进程首次打开的过程中，操作系统需做的是（）A.将文件内容读到内存中B.将文件控制块读到内存中C.修改文件控制块中的读写权限D.将文件的数据缓冲区首指针返回给用户进程9、位示图可用于（）A.实现文件的保护和保密B.文件目录的查找C.磁盘空间的管理D.主存空间的共享10、操作系统采用分页存储管理方式，要求（）。
2002年系统分析师考试真题及答案-上午卷●适用于TCP/IP网络管理的根本协议是__(1)__，其对应的管理信息库为__(2)__。
(1)： A．CMIS B．CMIP C．SNMP D．SMTP(2)： A．MIB-1 B．MIB-2 C．MIB-4 D．RMON●采用美国数据加密标准DES进展数据加密时，加密算法中的根本运算不包括__(3)__。
(3)：A．置换运算B．模加运算C．模乘运算D．移位运算●关于 RSA 算法以下说法不正确的选项是__(4)__。
(4)：A．RSA 算法是一种对称加密算法B．RSA 算法的运算速度比DES慢C．RSA 算法可用于某种数字签名方案D．RSA 的平安性主要基于素因子分解的难度●以下图为一个确定的有限自动机 DFA 的状态转换图，有向弧<i，j>上可以标记以下符号之一：小数点‘．’、十进制数字‘d’、正负号‘+／-’及科学记数标志‘e’。
请补充图中弧上的标记，使该 DFA 可以识别十进制形式和科学记数表示形式的实数。
有向弧<0，3>和<1，3>的标记为__(5)__；有向弧<1，2>和<2，4>的标记为__(6)__；有向弧<2，6>和<4，6>的标记为__(7)__；有向弧<4，5>和<5，6>的标记为__(8)__；有向弧<5，5>、<6，8>和<6，7>的标记为__(9)__。
(5)： A．‘d’和‘d’B．‘．’和‘d’C．‘．’和‘．’D．‘d’和‘．’(6)： A．‘d’和‘e’B．‘d’和‘．’C．‘e’和‘．’D．‘e’和‘d’(7)： A．‘+/-’和‘e’B．‘e’和‘d’C．‘e’和‘+/-’D．‘e’和‘e’(8)： A．‘e’和‘d’B．‘．’和‘d’C．‘d’和‘e’ D．‘e’和‘+/-’(9)： A．‘d’、‘d’和‘+／-’B．‘d’、‘．’和‘d’C．‘d’、‘+／-’和‘d’D．‘d’、‘．’和‘e’●在下面所列举的逻辑测试覆盖中，测试覆盖最强的是__(10)__，最弱的是__(11)__。
2022年天津工业大学计算机科学与技术专业《操作系统》科目期末试卷B（有答案）一、选择题1、在文件的索引节点中存放直接索引指针10个，一级和：级索引指针各1个。
磁盘块大小为IKB，每个索引指针占4B。
若某文件的索引节点已在内存中，则把该文件偏移量（按字节编址）为1234 和307400处所在的磁盘块读入内存，需访问的磁盘块个数分别是（）。
A.1.2B.1.3C.2.3D.2.42、下列算法中，用于磁盘调度的是（），A.时间片轮转法B.LRU算法C.最短寻道时间优先算法D.高优先级算法3、在单处理器的多进程系统中，进程切换时，何时占用处理器和占用多长时间取决于（）A.进程响应程序段的长度B.进程总共需要运行时间的长短C.进程自身和进程调度策略D.进程完成什么功能4、若一个用户进程通过read系统调用读取一个磁盘文件中的数据，则下列关于此过程的叙述中，正确的是（）。
I.若该文件的数据不在内存中，则该进程进入睡眠等待状态II.请求rcad系统调用会导致CPU从用户态切换到核心态III.read系统调用的参数应包含文件的名称A.仅I、IIB. 仅I、IIIC.仅II、IIID. I、II和III5、若系统中有n个进程，则在阻塞队列中进程的个数最多为（）？Α. n B.n-1 C.n-2 D.16、下列关于页式存储说法中，正确的是（）。
I.在页式存储管理中，若关闭TLB，则每当访问一条指令或存取一个操作数时都要访问两次内存II.页式存储管理不会产生内部碎片III.页式存储管理当中的页面是为用户所感知的IV.页式存储方式可以采用静态重定位A.仅I、II，IVB. 仅I、IVC. 仅ID.I、II、III、IV7、假设页的大小为4KB，页表的每个表项占用4B。
对于一个64位地址空间系统，采用多级页表机制，至少需要（）级页表（本题默认字长为1B）。
A.3B.4C.5D.68、所谓（），是指将一个以上的作业放入内存，并且同时处于运行状态。
2022年南京信息工程大学计算机科学与技术专业《计算机系统结构》科目期末试卷A（有答案）一、选择题1、（）属于MIMD系统结构。
A.各处理单元同时受同一个控制单元的管理B.各处理单元同时接受同一个控制单元送来的指令C.松耦合多处理机和多计算机D.阵列处理机2、费林按指令流和数据流的多倍性把计算机系统分类，这里的多倍性指（）。
A.系统瓶颈部件上处于同一执行阶段的指令流是数据流的多少倍。
B.系统瓶颈部件上处于同一执行阶段的数据流是指令流的多少倍。
C.系统瓶颈部件上处于同一执行阶段的指令或数据的最大可能个数。
D.A和B3、下列说法中不正确的是（）A.软件设计费用比软件重复生产费用高B.硬件功能只需实现一次，而软件功能可能要多次重复实现C.硬件的生产费用比软件的生产费用高D.硬件的设计费用比软件的设计费用低4、全相联地址映象是指（）。
A.任何虚页都可装入主存中任何实页的位置B.一个虚页只装进固定的主存实页位置C.组之间是固定的，而组内任何虚页可以装入任何实页位置D.组间可任意装入，组内是固定装入5、块冲突概率最高的Cache地址映象方式是( )A.段相联B.组相联C.直接D.全相联6、外部设备打印机适合于连接到( )。
A.数组多路通道B.字节多路通道C.选择通道D.任意一种通道7、IBM360/91属于（）A.向量流水机B.标量流水机C.阵列流水机D.并行流水机8、浮点数尾数下溢处理时，最大误差最大，但下溢处理不需要时间，平均误差又趋于0的方法是( )。
A.截断法B.舍入法C.ROM查表法D.恒置"1"法9、多处理机的各自独立型操作系统（）。
A.要求管理程序不必是可再入的B.适合于紧耦合多处理机C.工作负荷较平衡D.有较高的可靠性10、静态流水线是指( )A.只有一种功能的流水线B.功能不能改变的流水线C.同时只能完成一种功能的多功能流水线D.可同时执行多种功能的流水线11、计算机系统多级层次中，从下层到上层，各级相对顺序正确的应当是（）。
2022年南京大学软件工程专业《操作系统》科目期末试卷B（有答案）一、选择题1、某进程访问页面的序列如下所示。
若工作集的窗口大小为6，则在t时刻的工作集为（）。
A.（6，0，3，2）B. （2，3，0，4）C.（0，4，3，2，9）D.（4，5，6，0，3，2）2、CPU输出数据的速度远远高于打印机的速度，为解决这一矛盾，可采用（）。
A.并行技术B.通道技术C.缓冲技术D.虚存技术3、设有一页式存储管理系统，向用户提供的逻辑地址空间最大为16页，每页2048B，内存总共有8个存储块，试问逻辑地址至少为多少位？内存空间有多大（）？A.逻辑地址至少为12位，内存空间有32KBB.逻辑地址至少为12位，内存空间有16KBC.逻辑地址至少为15位，内存空间有32KBD.逻辑地址至少为15位，内存空间有16KB4、操作系统采用分页存储管理方式，要求（）。
A.每个进程拥有一张页表，且进程的页表驻留在内存中，B.每个进程拥有一张页表，但只要执行进程的页表驻留在内存中C.所有进程共享一张页表，以节约有限的内存空间，但页表必须驻留在内存中D.所有进程共享一张页表，只有页表中当前使用的页面必须驻留在内存中5、当系统发生抖动（Trashing）时，可以采取的有效措施是（）。
I.撤销部分进程 II.增大磁做交换区的容量 III.提高用户进程的优先级A. 仅IB.仅IIC.仅IIID.仅I,II6、用户程序在口态下使用特权指令引起的中断属于（）。
A.硬件故障中断B.程序中断C.外部中断D.访管中断7、实时操作系统必须在（）内处理完来白外部的事件。
A.一个机器周期B.被控对象规定时间C.周转时间D.时间片8、（）结构的文件最适合于随机存取的应用场合。
A.流式B.索引C.链接D.顺序9、下面关于文件的叙述中，错误的是（）。
I.打开文件的主要操作是把指定文件复制到内存指定的区域II.对一个文件的访问，常由用户访问权限和用户优先级共同限制III.文件系统采用树形片录结构后，对于不同用户的文件，其文件名应该不同IV.为防止系统故障造成系统内文件受损，常采用存取控制矩阵方法保护文件A.仅IB. 仅I、IIIC.仅I、III、IVD.I、II、III，IV10、下列选项中，降低进程优先权级的合理时机是（）。
2022年南京农业大学计算机科学与技术专业《操作系统》科目期末试卷A（有答案）一、选择题1、现有一个容量为10GB的磁盘分区，磁盘空间以簇（Cluster）为单，位进行分配，簇的大小为4KB，若采用位图法管理该分区的空闲空问，即用.位（bit）标识一个簇是否被分配，则存放该位图所需簇的个数为（）A.80B.320C.80KD.320K2、为支持CD-ROM小视频文件的快速随机播放，播放性能最好的文件数据块组织方式是（）。
A.连续结构B.链式结构C.直接索引结构D.多级索引结钩3、银行家算法在解决死锁问题中用于（）。
A.预防死锁B.死锁避免C.检测死锁D.解除死锁4、在操作系统中，一方面每个进程具有独立性，另一方面进程之间具有相互制约性。
对于任何两个并发进程，它们（）。
A.必定无关B.必定相关C.可能相关D.可能相同5、有5个批处理任务A、B、C、D、E几乎同时到达一计算中心。
它们预计运行的时间分别是10min，6min，2min、4min和8min。
其优先级（由外部设定）分别为3，5，2，1和4，这里5为最高优先级。
下列各种调度算法中，其平均进程周转时间为14min 的是（）。
A.时间片轮转调度算法B.优先级调度算法C.先来先服务调度算法D.最短作业优先调度算法6、作业在执行中发生缺页中断，经操作系统处理后应让其执行（）指令。
A.被中断的前一条B.被中断的那一条C.被中断的后·条D.启动时的第一条7、下面有关外层页表的叙述中错误的是（）。
A.反映在磁盘上页面存放的物理位置B.外层页表是指页表的页表C.为不连续（离散）分配的页表再建立一个页表D.若有了外层页表，则需要一个外层页表寄存器就能实现地址变换8、下面说法错误的有（）。
I分时系统中，时间片越短越好。
II.银行家算法是防止死锁发生的方法之。
III若无进程处于运行状态，则就绪和等待队列均为空。
A. I和IIB. II和IIIC. I和IIID. I、II和II9、一个多道批处理系统中仅有P1，和P2两个作业，P2比P1晚5ms到达。
V ol.15, No.2©2004 Journal of Software 软 件 学 报 1000-9825/2004/15(02)0179 两种对URL 的散列效果很好的函数∗李晓明+, 凤旺森(北京大学 计算机科学技术系,北京 100871)Two Effective Functions on Hashing URLLI Xiao-Ming +, FENG Wang-Sen(Department of Computer Science and Technology, Peking University, Beijing 100871, China)+ Corresponding author: Phn: +86-10-62756589, Fax: +86-10-62765813, E-mail: lxm@, Received 2003-03-05; Accepted 2003-06-18Li XM , Feng WS . Two effective functions on hashing URL . Journal of Software , 2004,15(2):179~184. /1000-9825/15/179.htmAbstract : Hashing large collection of URLs is an inevitable problem in many Web research activities. Through a large scale experiment, three hash functions are compared in this paper. Two metrics were developed for the comparison, which are related to web structure analysis and Web crawling, respectively. The finding is that the well-known function for hashing sequence of symbols, ELFhash, is not very good in this regard, and the other two functions are better and thus recommended. Key words :hashing; ELFhash; URL; even distribution; Web mining; load balance摘 要: 在Web 信息处理的研究中,不少情况下需要对很大的URL 序列进行散列操作.针对两种典型的应用场合,即Web 结构分析中的信息查询和并行搜索引擎中的负载平衡,基于一个含有2 000多万个URL 的序列,进行了大规模的实验评测.说明在许多文献中推荐的对字符串散列效果很好的ELFhash 函数对URL 的散列效果并不好,同时推荐了两种对URL 散列效果很好的函数.关键词: 散列;ELFhash;URL;均匀分布;Web 挖掘;负载平衡 中图法分类号: TP314 文献标识码: A散列(hashing)是信息存储和查询所用的一项基本技术,许多教科书中都有介绍[1].这项技术虽然发明于50年前,其间也有过不少非常系统、完整的研究工作[2],但直到近几年仍然有新的工作进展[3~5].散列技术的基础性及其在许多领域的可应用性是其不断被人们研究的源泉,而对它进行的研究能不断有新意的基本原因在于,其优化性能在很大程度上取决于输入键的结构.本文研究散列的键是用于访问网页的url,即形如“/…”之类的字符串[6].考虑如下两种应用情形:∗ Supported by the National Grand Fundamental Research 973 Program of China under Grant No.G1999032706 (国家重点基础研究发展规划(973))作者简介: 李晓明(1957－),男,湖北荆州人,教授,博士生导师,主要研究领域为计算机系统,网络计算;凤旺森(1980－),男,硕士生,主要研究领域为算法设计,复杂性理论.180Journal of Software 软件学报 2004,15(2)(1) 假设我们已经有了全国网页的集合,记作P ={p 1,p 2,p 3,…}.对应地,所有URL 的集合,记作URL ={url 1,url 2,url 3,…}.作为研究Web 结构的一个方面,我们关心的是,给定两个网页p i 和p j ,从p i 到p j 的最少链接数是多少.为此,我们可以首先从网页中抽取出基本结构信息,将每一个网页表达为,...},...,,:{,2,1,j i i i i i url url url url p =,即我们将每篇网页看成是一个有向图的节点,这样表达的p i 就给出了节点的标识和它的“外向”相邻关系.注意,并不是所有的url i ,j 都属于上述URL 集合(可能有死链,还可能有我们在此不关心的链,例如指向国外的).此时,得到从p i 到p j 的最少链接数的方法之一就是从p i 开始做先宽搜索.在搜索过程中,为了不重复劳动,要记住已经查过的节点(记作集合visited-nodes);凡是遇到一个节点,就要用它和visited-nodes 中的元素对比,若在其中,则放弃,否则,将它放入visited-nodes,继续沿其含有的url 向下搜索.显然,将visited-nodes 组织成一个散列表是最自然的.散列的对象(键)是url.(2) 在并行搜索引擎的工作过程中,若干台计算机并行地从Web 上抓取网页[7].并行系统维护一个全局的visited-pages,每台计算机维护一个局部的unvisited-pages.每当从一个刚抓来的网页中提取出一个url 时,首先和visited-pages 的元素对比(这里可能也用散列,与前述情况类似,在此不赘述),看是否存在;如果不存在,则将它散列到某台计算机上,让它来负责该url 对应网页的抓取.我们注意到,这两种应用的要求是有区别的.前者追求的是查询效率,后者追求的是负载平衡;前者的散列槽数可能很大(对于千万量级的节点数,槽数可以大到百万量级),后者的散列槽数相比要小得多(并行系统中计算机台数).同时,前者追求的是某种“平均”效果,后者要考虑“最大值”的情况.这样的认识是后面进行实验设计和分析的基础.首先,我们针对上述两种应用需求给出相应的散列函数质量的评估测度.随后,描述参与实验的数据源和几个散列函数;特别地,其中包括在许多文献中推荐的对字符串散列效果很好的ELFhash 函数(一种散列URL 的自然选择)和阎宏飞、谢正茂设计的用于我们的天网搜索引擎的散列函数,以及我们在“Web 信息博物馆”中使用的另一种函数.在介绍了实验设计的细节之后,我们给出执行的结果.最后是对结果的几点分析和讨论.1 实验的设计和执行1.1 评估测度为了比较不同的散列函数,需要有与应用背景相关的评估测度.对于上述第1种应用,我们关心的是对散列后url 的平均查询时间.对于第2种应用,我们关心最大的槽中元素的个数.为此,有下面两种对应的测度定义.信息查询性能测度.设有N 个url 字符串待处理,将这些字符串用散列函数F 散列到M 个槽中,对i (1≤i ≤M )号槽,散列到其中的url 个数为N i .我们假设查询每个url 的概率是相等的,则对N 个url 各作一次查询的时间算术平均值,便可当作F 的查询性能测度.按照通常散列表项的链表结构,对i 号槽中第k 个元素作查询,需要访问存储k 次,所以,对散列在i 号槽中的所有字符串都作一次查询,则需要访问存储2)1(+i i N N 次.考虑所有的槽,我们可以用下面的平均存储访问次数来表示散列函数F 的查询性能测度,越小越好.∑∑==+=+=M i i Mi i i N N N N NA 12121212)1(1, 其中. ∑==Mi i N N 1根据上述条件和凹函数(x 2)的基本性质易知,当所有MNN i =时A 取最小值,当只有1个,其他都为0时取最大值.两个极值分别为N N i =i N 21/+M N 和21+N . 负载平衡性能测度.设有N 个url 所指网页待抓取,将这些url 字符串用散列函数F 散列到M 台机器中,对i (1≤i ≤M )号机器,散列到其中的url 字符串个数为N i ,则M 台机器并行完成N 个网页抓取的时间取决于任务最多李晓明 等:两种对URL 的散列效果很好的函数181的机器的完成时间,即与max(N i )成比例.做一定的规格化,我们用)max(i N NMB =来作为F 的负载平衡性能测度,这个量也可以解释成抓取一个网页所要消耗的平均机器时间,越小越好.同样,我们不难看出它的极值分别为1和M ,发生在MNN i =)max(和N N i =)max(.我们注意到,B 值的物理意义是散列结果和最佳期望值的倍数差距,即MN B ⋅N i =)max(. 1.2 待评估的散列函数我们考虑3个函数,第1个取自文献[8],源于UNIX System V,号称“实际生活散列函数中的典型魔术”,也是我们在信息查询研究工作中的首选,但发现不理想,从而导致了本文的研究工作.int ELFhash(char* url, int size) {unsigned int h =0; while (*url) {h =(h<<4) + *url++; unsigned int g= h & 0xF0000000; if (g) h^=g>>24; h&=~g; }return h%size;}第2个是由阎宏飞和谢正茂采用折叠方法设计的,一直用在天网搜索引擎中,感觉负载平衡效果比较好,但没有系统评估过.unsigned int HfIp(char* url, int size) {unsigned int n =0; char* b =(char*)&n;for (int i=0; i<strlen(url); i++) b[i%4]^=url[i]; return n%size;}第3个是谢正茂为了在多个数据库中分布网页设计的,也是出于负载平衡的目的,主要的一个考虑因素是实现简单.int _hf(char* url, int size) {int result =0; char* ptr =url; int c; for (int i=1; c=*ptr++; i++) result += c*3*i; if (result<0) result = −result;182Journal of Software 软件学报 2004,15(2)return result%size;} 1.3 实验方案和数据结果我们以天网搜索引擎搜集的2 000万个url 序列为源数据∗,用上述3种散列函数分别针对两种应用的需求实验,考察在不同的N 和M 情况下测度A 和B 的情况.对信息查询应用,我们分别取槽数M =20,80,100,200(单位:万),以50万为间隔,以N =50万,100万,…,2000万个url 为输入执行散列函数,得到测度A.共执行4次,每次执行得到3×40个数据.对负载平衡应用,我们分别取槽数M =8,10,12,40,同样也是以50万为间隔,以N =50万,100万,…,2000万个url 为输入执行散列函数,得到测度B.也是共执行4次,每次执行得到3×40个数据.图1和图2是这些数据的图示.如图1所示为信息查询的性能,如图2所示为负载平衡的性能,其中标有A 的图与测度A 相关,标有B 的图与测度B 相关.A(1): M =200000A(2): M =800000Record number (unit: 10 000)I n f o r m a t i o n r e t r i e v a l p e r f o r m a n c e n u m b e r* ELFhash • Hflp + hf* ELFhash • Hflp + hfRecord number (unit: 10 000)I n f o r m a t i o n r e t r i e v a l p e r f o r m a n c e n u m b e r* ELFhash • Hflp + hfA(4): M =2000000Record number (unit: 10 000) * ELFhash • Hflp + hfI n f o r m a t i o n r e t r i e v a l p e r f o r m a n c e n u m b e rI n f o r m a t i o n r e t r i e v a l p e r f o r m a n c e n u m b e rRecord number (unit: 10 000)A(3): M =1000000Fig.1 Performance comparison for information retrieval图1 检索性能比较∗可以免费提供给有兴趣做类似研究工作的同行,燕穹产品号:YQ-URLLIST-2002-03.李晓明 等:两种对URL 的散列效果很好的函数183L o a d b a l a n c e p e r f o r m a n c e n u m b e r* ELFhash • Hflp + hf * ELFhash • Hflp + hfB(2): M =100000Record number (unit: 10 000) B(1): M =80000L o a d b a l a n c e p e r f o r m a n c e n u m b e rRecord number (unit: 10 000)* ELFhash • Hflp + hf* ELFhash • Hflp + hfL o a d b a l a n c e p e r f o r m a n c e n u m b e rB(4): M =400000Record number (unit: 10 000)B(3): M =120000L o a d b a l a n c e p e r f o r m a n c e n u m b e rRecord number (unit: 10 000)Fig.2 Performance comparison for load balance图2 负载平衡性能比较2 实验的结论与分析我们分信息查询(对应于A)和负载平衡(对应于B)两种情况加以讨论. 观察图1中A(1),A(2),…,A(4)的形态,我们有:• HfIp 散列函数具有绝对的优势,在所有情况下都是最好的.• hf 的性能在M 较小的情况下与HfIp 相当,比ELFhash 要好;但随着M 的增大,hf 的相对性能逐步下降,最后比ELFhash 要差.• 特别地,我们注意到HfIp 和最优值相当接近.例如,在M =20万的情形下,我们有下面的对比(其中最优A 值可由前面的测度表达式定义计算出):N 500 000 1 000 000 1 500 000 2 000 000 2 500 000 3 000 000 … 20 000 000 A (opt) 1.75 2.75 4.25 5.5 6.75 8.00 … 50.50 HfIp1.89 3.23 4.54 5.85 7.01 8.31 … 51.75这些数据显示HfIp 不仅很接近最优,而且相当稳定.184Journal of Software 软件学报 2004,15(2)观察图2中B(1),B(2),…,B(4)的形态,我们有:• HfIp 散列函数在负载平衡方面表现也不错.它的B 测度基本上都在1.1以下,接近B 的最优值(即1.0,与图的横轴重合).它最大的优点是稳定,对不同的M 表现很一致.• hf 在M =8,10,40时表现最好(比HfIp 要好),但在M =12时最差(比ELFhash 要差).这种不稳定性的原因不清楚.• ELFhash 的表现较差,B 值在1~5之间大范围波动.由于hf 在负载平衡实验中的异常表现,我们在2 000万个url 序列中随机选取40万个url 作为样本,单独作一个比较实验,证明hf 的不稳定性.对负载平衡应用,我们分别取槽数M =11,12,14,16,18,以1万为间隔,以N =1万,2万,…,40万个url 为输入执行散列函数hf,得到测度B.共执行5次,每次执行得到40个数据.图3是这些数据的图示,可以很清楚地看到hf 性能的波动.• M =11* M =12+ M =14□ M =16M =18L o a d b a l a n c e p e r f o r m a n c e n u m b e rRecord number (unit: 10 000)Fig.3 Instability of algorithm hf in load balance application图3 hf 算法在负载平衡应用中的不稳定性作为本项研究的结论,我们有:对于URL 的散列,(1) 无论出于信息查询还是负载平衡的需求,HfIp 都是很可靠的,可以首选使用;(2) Hf 在有些情况下对负载平衡很好,但它对槽数的敏感性是一个值得注意的缺陷,有时可能效果很不好,需要小心;(3) 不推荐使用ELFhash.致谢 许多人在这项工作中给予了帮助:阎宏飞和谢正茂提供了他们的散列函数,孙磊收集并整理了用于实验的数据,肖明忠对论文的初稿提出了一些有益的建议,张立昂老师一直关心这项工作的进行.在此,我们对他们表示衷心的感谢. References :[1] Cormen TH, Leiserson CE. Introduction to Algorithms. 2nd ed., Cambridge: MIT Press, 2001. 221~252.[2] Knuth DE. Sorting and Searching, Volume 3 of the Art of Computer Programming. New York: Addison-Wesley, 1973. 506~549. [3] McKenzie BJ, Harries R, Bell T. Selecting a hashing algorithm. Software Practice and Experience, 1990,20(2):208~210. [4] Tong MCF. General hashing [Ph.D. Thesis]. Computer Science Department, University of Auckland, 1996. [5] Peter K. Pearson, fast hashing of variable length text strings. Communications of the ACM, 1990,33(6):676~678. [6] Berners-Lee T. Universal resource locator. 2003. /Addressing/URL/Overview.html[7] Yan HF, Wang JY, Li XM, Guo L. Architectural design and evaluation of an efficient Web-crawling system. Journal of System andSoftware, 2002,60(3):185~193.[8] Shaffer CA. Zhang M, Liu XD, Trans. Data Structure and Algorithm Analysis. Beijing: Publishing House of Electronics Industry,1998. 211~213 (in Chinese).附中文参考文献:[8] Shaffer CA,著.张铭,刘晓丹,译.数据结构与算法分析.北京:电子工业出版社,1998.211~213.。
V ol.13, No 1000-9825/2002/13(S)0000-00©2002 Journal of Software 软件学报Needham-Schroeder协议的形式化分析Ã王贵林1,2, 卿斯汉1,2, 周展飞31(中国科学院软件研究所信息安全国家重点实验, 北京 100080);2(中国科学院信息安全技术工程研究中心, 北京 100080)3(Mathematics Department, Nihon University, Tokyo 101-8308, Japan.)E-mail: glwang@; qsihan@; zhanfei_zhou@http:// 摘要: 认证协议是网络环境中一类重要的安全协议, 而对协议进行形式化分析是保障其安全性的主要手段. 本文以BAN逻辑为工具, 分析了著名的Needham-Schroeder私钥认证协议(简称为NS协议)及其改进形式. 结果表明, 原NS协议的安全性能是有限的, 而改进后的NS协议则可以达到预期的认证目标.关键词: 认证协议; Needham-Schroeder协议; 形式化分析; BAN逻辑; 信息安全密码协议是用来提供安全服务的. 因此, 如果协议设计不正确, 就不能或不能很好地提供安全服务. 这方面的例子是很多的[1]. 使用形式化方法来分析密码协议的安全性是合适的. 一方面, 这些问题具有良好的自包含性, 所以可对其进行建模和分析. 另一方面, 这些问题又比较复杂, 且协议中的漏洞常与直觉相反, 所以用非形式化的方法进行分析时容易导致错误, 故而不可靠. 自七、八十年代开始以来, 密码协议的形式化分析已逐渐成为信息安全研究领域中的一个热点, 涌现出了众多的研究方法. 从目前来看, 研究比较广泛且受到重视的方法主要有以下四种: 基于知识与信念推理的模态逻辑方法, 基于通信状态机模型的研究方法, 基于知识推理的代数方法以及基于顺序通信进程的方法[1,2].基于知识和信念推理的模态逻辑系统, 类似于在分布式系统中分析知识、信念演化的现有逻辑. 这些逻辑系统通常由一些命题和推理规则组成. 命题表示主体对消息的知识或信念, 而运用推理规则可以从已知的知识、信念推导出新的知识、信念. 在这类方法中, 最著名的就是BAN类逻辑[3,4,5,6]. 目前, 这方面的最新研究是Kindred所提出的密码协议生成理论---RV逻辑[7].Needham-Schroeder协议(简称为NS协议)是出现较早的一类认证协议[8,3,9], 也是一个重要的认证协议, 因为许多广泛使用的认证协议都是以NS协议为蓝本而设计的. NS协议可分为私钥体制和公钥体制下的两种版本, 但本文只讨论私钥NS协议. 文献[10]指出了对NS私钥协议的一个攻击并给出了改进版本. 本文使用BAN逻辑对NS私钥协议及其改进版本[10]作了形式化分析, 结果表明：文献[3]对该协议的分析是有问题的, 而我们的改进版本则可以达到理想的认证目标. 另外, 本文的研究也表明: 使用BAN逻辑时, 确定初始化假设集是很重要的, 因为只有在合理的假设集下得出的分析结果才是可靠的.1 BAN逻辑简介BAN逻辑[3]的提出, 为认证协议的形式化分析提供了一种有效的工具. BAN逻辑只在抽象的层次上讨论认证协议的安全性, 因此它并不考虑由协议的具体实现所带来的安全缺陷和由于加密体制的缺点所引发的Ã收稿日期:2001-03-15; 修改日期: 2001-06-16基金项目: 国家重点基础研究发展规划973资助项目(G.1999035800)作者简介: 王贵林(1968－), 男, 云南大理人, 博士, 主要研究领域为安全协议和信息安全基础; 卿斯汉(1939－), 男, 湖南邵阳人, 研究员, 博士生导师, 主要研究领域为信息安全理论和技术; 周展飞(1969－), 男, 江苏苏州人, 博士, 主要研究领域为密码理论和应用数学.2Journal of Software 软件学报 2002,13协议缺陷. 总的来说, BAN 逻辑系统所作的假设如下： (1) 密文块不能被篡改, 也不能用几个小的密文块组成一个新的大密文块.(2) 一个报文中的两个密文块被看作是分两次分别到达的.(3) 总假设加密系统是完善的(perfect), 即只有掌握密钥的主体才能理解密文消息, 因为不知道密钥的主体不能解密密文而得到明文；而攻击者无法从密文推断出密钥.(4) 密文含有足够的冗余信息使得解密者可以判断他是否用对了密钥.(5) 报文中含有足够的冗余信息使得主体可以判断该报文是否来源于自身.(6) BAN 逻辑还假设参与协议的主体是诚实的.作为一种多类型模态逻辑(many-sorted modal logic), BAN 逻辑主要包含下面三种处理对象：主体(principals)、密钥(keys)和公式(formulas). 其中的公式, 也称为语句或命题(statements). BAN 逻辑仅包含合取这一命题联接词, 用逗号表示；合取连接词满足交换律和结合律. 此外, P , Q 和R 表示主体变量, 而K 表示密钥变量, X 和Y 表示公式变量；而A , B 表示两个普通主体, S 是认证服务器；as K 是A 和S 间的共享密钥. 下面, 我们逐一介绍BAN 逻辑构件(construct)的语法和语义、逻辑推理规则和形式化分析步骤.1.1 BAN 逻辑构件的语法和语义BAN 逻辑共有10个构件, 其语法和语义如下所述:1. X P ≡|: 主体P 相信(believes)公式X 是真的.2. X P <: 主体P 接收到了(received or sees)包含X 的报文, 也即存在某主体给P 发送了包含X 的报文.3. X P |~: 主体P 曾经发送了(sent or said)包含X 的报文.4. X P ⇒|: 主体P 对X 有管辖权(control).5. )(#X : X 是新鲜的(fresh), 即X 没有在此执行回合前作为某报文的一部分而被发送过. 这里的X 一般为临时值(nonce) .6. Q P K →←: K 为P 和Q 的共享密钥(shared key)；且除P , Q 和他们信任的主体外, 其他主体都不知道K . 7. P K →: K 为P 的公开密钥(public key)；且除P 和他信任的主体外, 其他主体都不知道相应的秘密密钥1−K . 8. P Q : X 为P 和Q 的共享秘密(shared secret)；且除P , Q 和他们信任的主体外, 其他主体都不知道X . 9. K X }{: 用密钥K 加密(encrypted) X 后得到的密文. 这是P X K from }{的简写.10.Y X ><: 表示由X 和秘密Y 合成的(combined)报文.1.2 BAN 逻辑的推理规则BAN 逻辑共有推理规则19条, 下面将第n 条推理规则简记为Rn(n=1,2,…,19). 在以下的推理规则中, ┣是元语言符号. Γ┣ C 表示可以由前提集Γ推导出结论C . 以推理规则R1为例, 如果P 相信K 为P 和Q 的共享密钥且P 接收到报文K X }{, 则P 相信Q 发送了报文X . 其他规则的语义解释可参考文献[3, 5].消息含义规则(Message-meaning rules)三条:R1. K K X P P Q P }{,|< →←≡┣;|~|X Q P ≡ R2. 1}{,|− → ≡K K X P Q P <┣;|~|X Q P ≡ R3. P P ≡| Y X P Q }{,<┣.|~|X Q P ≡临时值验证规则(Nonce-verification rule)一条：R4. X Q P X P |~| ),(# |≡≡┣.||X Q P ≡≡管辖规则(Jurisdiction rule)一条：R5. X Q P X Q P ≡≡⇒≡|| ,||┣.|X P ≡接受消息规则(Seeing rules)五条：R6. ),(Y X P <┣;X P < R7. Y X P >< <┣;X P <R8. K K X P Q P P }{,|< →←≡┣;X P < R9. K K X P P P }{,|< → ≡┣;X P < X Y3R10. 1}{,|− → ≡K K X P Q P <┣.X P < 消息新鲜性规则(Freshness rule)一条：R11. )(# |X P ≡┣). ,(# |Y X P ≡信念规则(Belief rules)四条：R12. Y P X P ≡≡| ,|┣); ,( |Y X P ≡ R13. ) ,( |Y X P ≡┣;|X P ≡R14. ) ,(| |Y X Q P ≡≡┣;||X Q P ≡≡ R15. ) ,(~| |Y X Q P ≡┣.|~|X Q P ≡密钥、秘密规则(Key and secret rules)四条：R16. R R P K ′ →←≡|┣;|R R P K →←′≡ R17. R R Q P K ′ →←≡≡||┣;||R R Q P K →←′≡≡ R18. R P ≡| R ′┣R P ′≡| ;R R19. R Q P ≡≡|| R ′┣R Q P ′≡≡|| .R1.3 用BAN 逻辑分析认证协议的步骤运用以上推理规则, 即可使用BAN 逻辑形式化地分析认证协议, 具体步骤如下：1. 对认证协议进行理想化, 将协议的实际报文转换成BAN 逻辑所能识别的公式.2. 对协议进行解释, 即将形如X Q P :→的报文转换成形如X Q <的逻辑语言. 解释过程中应遵循以下规则：(1) 若命题X 在报文Y Q P :→前成立, 则在其后X 和Y Q <都成立.(2) 若根据推理规则可以由命题X 推导出命题Y , 则命题X 成立时, 命题Y 亦成立.3. 用逻辑语言对系统的初始状态进行描述, 给出初始化假设集.4. 运用推理规则对协议进行形式化分析, 推导出结果.2 NS 私钥认证协议的形式化分析本节在简要回顾了文献[3]对NS 私钥认证协议的分析后, 将指出该分析中的问题. NS 私钥认证协议[8,3,9, 10]的具体报文顺序如下：ababbsasbs K b K b K ab K K ab ab a aN B A N A B A K B A A K K B N A S N B A S A }1{ : 5}{ : 4} ,{ : 3}} ,{ , , ,{ : 2 , , : 1+→→→→→ 这里假设S 已经分别与A , B 享有共享密钥as K 和bs K . 下面就NS 私钥认证协议的报文交换过程作些说明. 首先, 主体A 将临时值a N 传送给服务器S , 以便向S 申请与主体B 建立会话密钥. S 在接到请求后, 为主体A 和B 生成会话密钥ab K , 然后将临时值a N 、主体B 的身份标识符、会话密钥ab K 和证书用A 和S 间共享的密钥as K 加密后发给A . 其中的证书就是用B 和S 间共享的密钥bs K 加密的会话密钥和主体A 的标识符. A 接收到报文2后, 对之解密, 并检验其中的临时值和主体标识符. 如果正确, A 将证书转发给B . B 将用会话密钥ab K 加密后的临时值b N 发给A . A 对b N 作相应变换后用会话密钥加密并发送给B .首先, 对NS 私钥认证协议进行理想化, 可得：A B A N B A BB A N A B B A B A B A B A B A N A S ab ab ab ab bsab asbs ab ab ab K K b K K b K K K K K K K a from } ,{ : 5 from } ,{ : 4}{ : 3}}{ ),(# , ,{ : 2 →←→ →←→ →←→ →← →← →←→这里, 报文1已被略去, 因为BAN 逻辑认为报文1仅含明文, 对于接收者信念的演变毫无贡献. 于是, 根据BAN 逻辑, 文献[3]对NS 协议作出如下的解释：X X X X4Journal of Software 软件学报 2002,13A B A N B BB A N A B A B B A B A B A N A ab ab ab ab bsab asbs ab ab ab K K b K K b K K K K K K K a from } ,{ 5 from } ,{ 4}{ 3}}{ ),(# , ,{ 2 →← →← →← →← →← →←<<<<NS 协议的初始化假设集为：P1 ;|S A A as K→←≡ P2 ;|S B B bs K →←≡ P3 ;|S A S as K →←≡ P4 ;||B A S A K →←⇒≡ P5 ;||B A S B K →←⇒≡ P6 ;|S B S bs K →←≡ P7 );(#||B A S A ab K→←⇒≡ P8 ),(# |b N B ≡ P9 ;|B A S ab K →←≡ P10 ),(# |a N A ≡ P11 );(# |B A B ab K→←≡ P12 ).(# |B A S ab K →←≡ 值得注意的是, 上面的假设P11实际上并不成立. 文献[3]中增加这条假设是为了得到理想的形式化分析结果. 下面先按照上述初始化假设, 对NS 私钥协议进行分析. 稍后我们再来讨论各初始化假设的合理性.形式化分析从报文2开始. A 接收到报文2, 就有：.}}{ ),(# , ,{ as bs ab ab ab K K K K K a B A B A B A N A →← →← →←<但,|S A A as K →←≡ 于是利用R1得：(1) .)}{ ),(# , ,(|~|bs ab ab ab K K K K a B A B A B A N S A →← →←→←≡ 又)(# |a N A ≡(即假设P10), 故由R11知).}{ ),(# , ,(# |bs ab ab ab K K K K a B A B A B A N A →← →← →←≡ 由此式和(1)式, 利用临时值验证规则R4得：(2) .)}{ ),(# , ,(||bs ab ab ab K K K K a B A B A B A N S A →← →← →←≡≡利用信念规则R14, 将, ,(B A N ab K a →←)}{ ),(#bs ab ab K K K B A B A →← →←拆开有：(3) .)(# || ,||B A S A B A S A ab ab K K →←≡≡ →←≡≡ 于是利用假设P4, P7及(3)式, 据管辖规则R5可得：(4) .)(# | ,|B A A B A A ab ab K K →←≡→←≡ B 收到报文3之后, 即有: .}{bs ab K K B A B →←< 由假设P2, 运用R1得: (5) ).(|~|B A S B ab K →←≡ 再加上假设P11, 运用R4得:(6) .||B A S B ab K→←≡≡ 由假设P5和(6)式, 运用R5得: (7) .|B A B ab K→←≡ 通过报文4和5, 主体A 和B 确信对方在线(因为他刚刚发送了报文). 由报文4有:. from } ,{ B B A N A ab ab K K b→←< 由(4)之第一式, 运用R1得: (8) .) ,( |~|B A N B A ab K b→←≡ 再运用R15得: (9) .)( |~|B A B A ab K→←≡ 于是由(4)之第二式, 运用R4得出: (10) . ||B A B A ab K→←≡≡ 同样, B 收到报文5后有: . from } ,{ A B A N B ab ab K K b →←< 由(7)式, 运用规则R1得出:(11) .) ,( |~|B A N A B ab K b →←≡ 而),(# |b N B ≡ 运用规则R11有:(12) ).,(#|B A N B ab K b→←≡ 由(11)、(12)式, 运用规则R4得出: (13) .),( ||B A N A B ab K b→←≡≡ 由(13)式, 运用规则R14得出： (14) . ||B A A B ab K→←≡≡ 这样, 上述(4)、(7)、(10)及(14)式就是文献[3]得出的分析结果：(15) ,|B A A ab K→←≡ ,|B A B ab K →←≡ , ||B A B A ab K →←≡≡ . ||B A A B ab K →←≡≡ 上述分析说明, 如果12条假设全都成立的话, A 和B 都相信密钥ab K 是A 和B 之间的共享密钥, 且相信对方也相信这一点. 但我们认为: 在上述对NS 协议的分析中, 文献[3]所作的假设P11是不正确的, 而假设P7和P12是过分的. 因为通过协议报文交换, 不存在任何信息促使B 相信ab K 的新鲜性, 报文3完全可能是一重发5报文. 所以假设P11是不成立的. 假设P12表示S 创建的会话密钥ab K 是新鲜的, 可作为临时值使用；而假设P7表明主体A 相信认证服务器S 对ab K 的新鲜性具有管辖权. 但管辖权假设是BAN 逻辑中最强的假设, 应尽量少使用[9]. 所以假设P7和P12是过分的, 不合理的.另外, 报文4中不包含任何A 可辩识的信息, 所以对报文4的如下理解也是不正确的：. from } ,{ B B A N A ab ab K K b→←< 在没有假设P11之时, 关于主体B 只能得到),(|~|B A S B ab K →←≡ 而不能得到B A B ab K →←≡|和 ||≡≡A B.B A ab K →← 也就是说, 没有假设P11时所得到的分析结果是：(16) ,|B A A ab K→←≡ ),(|~|B A S B ab K →←≡ . ||B A B A ab K →←≡≡ 而没有假设P7, P11和P12时, 对NS 私钥协议的形式化分析结果是：(17) ,|B A A ab K→←≡ ).(|~|B A S B ab K →←≡ 这说明, 对NS 私钥协议的正确分析结果应该是(17)式, 而不是文献[3]给出的(15)式. 事实上, 我们的分析结果(17)式与运用GNY 逻辑和SVO 逻辑分析得出的如下结果[4,6,2]是吻合的(其中的X A ∋表示主体A 拥有X )：,ab K A ∋ ,|B A A ab K→←≡ .ab K B ∋ 3 改进NS 私钥认证协议的形式化分析在本节中, 我们将使用BAN 逻辑形式化地分析改进的NS 私钥协议[10]. 结果表明, 改进的NS 私钥协议才能够真正达到密钥确认和对方主体身份认证的目的. 改进的NS 私钥协议如下(其中的s T 是由服务器S 产生的时间戳)：ababbsasbs K b K a b K s ab a K K s ab a ab a aN B A N N A B T K A N B A T K A N K B N A S N B A S A }{ : 5} ,{ : 4} , , ,{ : 3}} , , ,{ , , ,{ : 2 , , : 1→→→→→ 将上述协议进行理想化和解释可得：ab ab abab bsab asbs ab ab K K b K K a b K s K a K K s K a K a B A N B B A N N A T B A N B T B A N B A N A } ,{ 5} , ,{ 4} , ,{ 3}} , ,{ , ,{ 2 →← →← →← →← →←<<<<改进NS 私钥认证协议的初始化假设如下：P1 ;|S A A as K→←≡ P2 ;|S B B bs K →←≡ P3 ;|S A S as K →←≡ P4 ;||B A S A K →←⇒≡ P5 ;||B A S B K →←⇒≡ P6 ;|S B S bs K →←≡ P7 ),(# |a N A ≡ P8 ),(# |b N B ≡ P9 ;|B A S ab K→←≡ P10 ).(# |s T B ≡A 收到报文2后就有： .}} , ,{ , ,{ as bs ab ab K K s K a K a TB A N B A N A →←→←< 由P1及R1得: (18) .)} , ,{ , ,( |~|bs ab ab K s K a K a T B A N B A N S A →← →←≡ 而由假设P7及R11知：(19) .)} , ,{ , ,(# |bs ab ab K s K a K a T B A N B A N A →← →←≡ 由(18)式及(19)式, 利用临时值验证规则R4得：(20) .)} , ,{ , ,( ||bs ab ab K s K a K a T B A N B A N S A →← →←≡≡ 将R14运用于(20)式得：(21) .||B A S A ab K →←≡≡ 于是由假设P4及(21)式, 利用管辖规则R5得：(22) .|B A A ab K→←≡ 主体B 收到报文3后, 即有.} , ,{ bs ab K s K a T B A N B →←< 于是由假设P2及R1得). , ,( |~|s K a T B A N S B ab →←≡6 Journal of Software 软件学报 2002,13再由假设P10及R11知: .) , ,(# |s K a T B A N B ab →←≡ 根据这两个式子, 利用R4得:(23) .) , ,( ||s K a T B A N S B ab→←≡≡ 由(23)式, 利用R14得： (24) . ||B A S B ab K→←≡≡ 再由假设P5及(24)式, 据R5得： (25) . |B A B ab K→←≡ A 收到报文4后有.} , ,{ ab ab K K a b B A N N A→←< 由(22)式和本式, 根据R1得). , ,(|~|B A N N B A ab K a b →←≡ 而由假设P7及R11知.) , ,(# |B A N N A ab K a b →←≡ 由此二式, 利用R4得：(26) ). , ,(||B A N N B A ab K a b→←≡≡ 由(26)式, 利用R14得： (27) .||B A B A ab K→←≡≡ 主体B 收到报文5后, 有.} ,{ ab ab K K b B A N B →←< 由本式和(25)式, 利用R1得). ,(|~|B A N A B ab K b →←≡由假设P8及R11知.) ,(# |B A N B ab K b →←≡ 由此二式, 利用R4得：(28) ). ,(||B A N A B ab K b→←≡≡ 由(28)式, 利用R14得： (29) .||B A A B ab K→←≡≡ 这样, 我们就得到了对改进NS 私钥认证协议的形式化分析结果：(30) ,|B A A ab K→←≡ ,|B A B ab K →←≡ , ||B A B A ab K →←≡≡ . ||B A A B ab K →←≡≡ 这表明, 我们在文献[10]中对NS 私钥认证协议的改进是成功的、有效的.4 结 论本文运用BAN 逻辑, 对NS 私钥协议及其改进版本作了形式化分析. 结果表明, 文献[3]对NS 协议的分析是有缺点的, 而文献[10]中对NS 私钥协议的改进是成功的. 但值得注意的是, BAN 逻辑作为一种有效的形式化分析工具, 利用它确实发现了许多协议的缺点, 但其本身还存在许多局限性[11,12,2]：协议理想化过程的非形式化极易导致分析的失败；BAN 逻辑假设主体能够识别报文的来源, 从而不能考虑协议执行回合内的攻击；对交错攻击缺乏有效的识别机制；对未认证的密钥缺乏有效的分析机制；BAN 逻辑系统的各条假设是否合理等. 因此, 如何扩充和完善BAN 逻辑就成为一项很有价值的工作, 有待进一步的研究.References:[1] Meadows, C. Formal verification of cryptographic protocols: a survey. In: Advances in Cryptology - Asiacrypt'96 Proceedings,LNCS 1163. Berlin: Springer-Verlag, 1996. 135~150.[2] Wang, Gui-lin. Design and analysis of threshold signature schemes and authentication protocols [Ph.D Thesis]. Beijing:Instistute of Software, the Chinese Academy of Sciences. December, 2000 (in Chinese).[3] Burrows, M., Abadi, M., Needham, R. A logic of authentication. Research report 39, Digital Systems Research Center, February1989. Parts and versions of this material have been presented in many places, including: ACM Transactions on Computer Systems, 1989, 8(1): 18~36; Proceedings of the Royal Society of London A, 1989, 426: 233~271.[4] Gong, L., Needham, R. and Yahalom, R. Reasoning about belief in cryptographic protocols. In: Proceedings of the 1990 IEEEComputer Society Symposium on Research in Security and Privacy. Los Alamitos: IEEE Computer Society Press, 1990. 234~ 248.[5] Abadi, M., Tuttle, M.R. A semantics for a logic of authentication. In: Proceeding of the Tenth ACM Symposium on Principles ofDistributed Computing. ACM Press, 1991. 201~216.[6] Syverson, P.F., van Oorschot, P.C. On unifying some cryptographic protocol logics. In: Proceedings of the 1994 IEEE ComputerSociety Symposium on Research in Security and Privacy. Los Alamitos: IEEE Computer Society Press, 1994. 14~28.[7] Kindred, D. Theory generation for security protocols [Ph.D Thesis]. Pittsburgh, Computer Science Department, Carnegie MellonUniversity, 1999.[8] Needham, R., Schroeder, M. Using encryption for authentication in large networks of computers. Communications of the ACM,1978, 21(12): 993~999.7[9] Abadi, M., Needham, R. Prudent engineering practice for cryptographic protocols. IEEE Transactions on Software Engineering,1996, 22(1): 6~15.[10] Wang, Gui-lin, Qing, Si-han, Zhou, Zhan-fei. Some new attacks upon authentication protocols. Journal of Software, 2001, 12(6):907~913 (in Chinese).[11] Nessett, D.M. A critique of the Burrows, Abadi and Needham logic. ACM Operating Systems Review, 1990, 24(2): 35~38.[12] Qing, Si-han. Formal analysis of authentication protocols. Journal of Software, 1996, 7(supplement): 107~114 (in Chinese).附中文参考文献：[2] 王贵林. 门限签名方案和认证协议的设计与分析[博士学位论文]. 北京: 中国科学院软件研究所, 2000年12月.[10] 王贵林, 卿斯汉, 周展飞. 认证协议的一些新攻击方法. 软件学报, 2001, 12(6): 907~913.[12] 卿斯汉. 认证协议的形式化分析. 软件学报, 1996, 7(增刊): 107~114.Formal Analysis of Needham-Schroeder ProtocolWANG Gui-lin1,2, QING Si-han1,2, and ZHOU Zhan-fei31(State Key Laboratory of Information Security, Institute of Software, The Chinese Academy of Sciences, Beijing 100080, China);2(Engineering Research Center for Information Security Technology, The Chinese Academy of Sciences, Beijing 100080, China);3(Mathematics Department, Nihon University, Tokyo 101-8308, Japan)Abstract:Authentication protocol is one important kind protocol in network environment, and formal analysis is the key method to guarantee its security properties. In this paper, Needham-Schroeder shared-key protocol and an improvement of it are analyzed by using BAN logic. The research results reveal that the original protocol has only limited security, but the improvement achieves the expectative authentication goals.Key words: authentication protocol; Needham-Schroeder protocol; formal analysis; BAN logic; information security* Received March 15, 2001; accepted June 16, 2001Supported by the National Grand Fundamental Research 973 Program of China under Grant No.G1999035800。
