当期目录

• 2005年, 第4期　刊出日期：2005-04-01 上一期    下一期
  本期栏目： 论文

论文

一个NHPP类软件可靠性增长模型框架

刘宏伟[1] 杨孝宗[1] 岳晓光[2] 曲峰[1]

2005, 27(4): 1-2. doi:

摘要 ( 356 )   PDF (150KB) ( 445 )   　　

NHPP类软件可靠性增长模型已经成为软件可靠性工程实践中非常成功的工具，从某些模型的一些共同特征出发，研究了NHPP类软件可靠性增长模型的有限通用框架，提出了一  个既考虑软件测试的不完美性、故障检测率随时间的变化，又考虑了故障改正效率随时间变化的NHPP类软件可靠性增长模型框架。一些已经存在的NHPP类软件可靠性增长模型型是这个框架的特例。

基于UML Statechart语义的测试序列生成方法

缪力 张大方

2005, 27(4): 3-5. doi:

摘要 ( 324 )   PDF (137KB) ( 381 )   　　

UML Statechart是UML的一个主要组成部分，与其他类型的Statechart相比，由于采用事件队列的调度方式，UML Statechart有着更多的不确定性，使得针对UML Statechart  模型的测试非常困难。本文给出了一个形式化的语义模型，并将Stateehart转化为一个比较简单的标志变迁系统，利用路径选择算法得到一个基于标志变迁系统的测试集，然 后通过判断得到的测试集中每个测试用例是否满足UML Statechart执行步的语义，从而得到一个满足UML Statechart执行步的语义的、可执行的测试集。

基于硬件与虚拟用户的大型软件性能测试解决方案

李文武 刘予

2005, 27(4): 6-7. doi:

摘要 ( 376 )   PDF (143KB) ( 404 )   　　

关键的负载测试对于降低大型软件的风险至关重要。在实施负载测试的几种方法中，基于硬件与虚拟用户的测试方法的可行性、可实施性都很强。本文以Rational性能测试工 具为例，给出了一个基于硬件与虚拟用户的大型软件负载测试解决方案。

基于索引的准同步检查点的重新计时策略

罗元盛[1] 闵应骅[2] 张大方[1]

2005, 27(4): 8-10. doi:

摘要 ( 322 )   PDF (144KB) ( 371 )   　　

基于索引的分布式检查点算法利用了Lamport逻辑时钟的思想来保证形成全局一致性检查点(或者恢复线)。作为一种准同步方法，基于索引的检查点算法具有异步检查点算法 的灵活性，且能像同步算法一样避免多米诺效应。本文在著名的BCS算法的基础上提出了一种减少基本检查点数目的优化策略——重新计时法。最后，通过模拟实验证明了这种改进策略的有效性。

改进的快速N＋1奇偶校验检查点

周军海[1] 张大方[2] 杨金民[3]

2005, 27(4): 11-13. doi:

摘要 ( 347 )   PDF (138KB) ( 382 )   　　

本文运用缓冲区和增量有盘检查点相结合的技术提出了一个快速可靠的改进N+1奇偶校验检查点方案。在N个应用进程运行时，通过设置一个专用的检查点进程来实现N+1的奇 偶校验，并且利用检查点机在检查点间隔的空闲时间将增量的奇偶校验检查点信息保存到稳定的存储器中。改进的算法利用了无盘检查点方案的快速及磁盘检查点的高可靠性 ，减少了一台备份处理机，并且可容忍一个应用进程及一个检查点进程的两个并发错误。

一种回归测试后的错误定位方法

蒋曹清 张大方 缪力

2005, 27(4): 14-15. doi:

摘要 ( 371 )   PDF (147KB) ( 389 )   　　

测试和调试之间的关系是极端密切的。回归测试是软件测试和维护过程中的一个重要活动。在程序中找出错误是一个复杂的过程，它涉及到理解程序的用途、结构、语意和导 致错误的测试的相关特征。本文提出了一种基于Chopping技术进行错误定位的方法。这种方法反复利用调试信息和回归测试结果，通过从程序中抽取出与特定的语句有关的、   、相对原来的程序小得多的语句集，实现准确、快速的错误定位。

基于错误的表达式测试研究

曹文静 宫云战

2005, 27(4): 16-18. doi:

摘要 ( 344 )   PDF (154KB) ( 381 )   　　

由于表达式LRAUC错误对程序中各类错误的广泛覆盖性，本文以表达式LRAUC错误为检测对象，研究了表达式测试方法。本文首先阐述了当前表达式测试方法理论研究的局限性；然后，为了解决处于程序上下文中的一般表达式测试问题，研究了表达式错误／失效过程，并对影响该过程复杂性的因素进行了简化，提出了表达式LRAUC单路测试方法； 阐述了此方法的具体实现，给出了表达式LRAUC单路测试约束集构造算法。

软件健壮性的包裹测试

刘洪涛 江建慧 赵则章

2005, 27(4): 19-21. doi:

摘要 ( 363 )   PDF (185KB) ( 552 )   　　

软件的健壮性正变得越来越重要，目前还缺乏准确的、可重复利用的方法来衡量系统的健壮性。健壮性基准程序就是为了解决这一问题而提出的，它由一系列健壮性测试案例组成。本文以Linux为例，简要介绍了当今操作系统健壮性基准程序测试的主要方法，对用于分析测试结果的维度模型进行了分析，提出了软件健壮性的包裹测试方法，并用 实例说明了其有效性。

包含异常处理的Java程序切片

王鹏飞 张大方 缪力

2005, 27(4): 22-24. doi:

摘要 ( 384 )   PDF (134KB) ( 462 )   　　

Exception是一类特殊的对象，它在Java方法出错时被创建，并利用try／catch／finally机制抛出、处理异常。本文提出了一种合理的新方法，在系统依赖图中表示异常处理 模块，利用图可迭性算法实现了Java程序切片。

针对线间串扰现象的静态定时分析

沈培福[1] 李华伟[2]

2005, 27(4): 25-28. doi:

摘要 ( 359 )   PDF (219KB) ( 360 )   　　

超深亚微米工艺下，线间串扰是导致电路故障的主要原因之一。尽管可能导致故障的线间串扰的数量巨大，但真正会引起故障的线间串扰却相对较少。因此，如果能在对电路 验证或测试前进行静态定时分析，找出那些导致电路故障的线间串扰，则可以有效提高测试生成效率，并降低测试成本。基于此目的，文章在静态定时分析中引入对线间串扰   扰现象的分析，在线时延模型的基础上使用重叠跳变对故障模型，只需要求出与最长通路的重叠跳变对即可。在对ISCAS89基准电路的实验中，各电路需要测试的串扰数平均 减少至10％以下。相对于已发表的实验结果，本文的实验结果具有较高的CPU效率。

用于k测试的BIST测试向量生成器

汪昱 邝继顺

2005, 27(4): 29-30. doi:

摘要 ( 362 )   PDF (157KB) ( 434 )   　　

检测CMOS电路中的开路故障通常需要使用测试向量对。内建自测试(BIST)作为一种有效的测试技术可以大大降低测试开销。本文采用一种具有规则性、模块化和层叠结构的自动控制单元(CA)，来构造产生测试向量对的BIST模块。实验证明，该方法用于瞬态电流测试是有效的。

大规模数字集成电路标准矩阵功能测试新方法

徐拾义

2005, 27(4): 31-35. doi:

摘要 ( 340 )   PDF (266KB) ( 321 )   　　

本文提出了一种对VLSI电路功能测试的方法，可以同时检测和定位VLSI电路输入和输出端上的固定故障和桥接故障，而不需要知道它们的内部逻辑结构。因而，对于简化测试 过程、降低测试成本，具有十分重要的实际意义。

基于扫描森林的BIST策略

陈明静[1] 向东[2]

2005, 27(4): 36-39. doi:

摘要 ( 340 )   PDF (198KB) ( 328 )   　　

在本文中，我们提出了一种改进的扫描森林结构并将其运用到基于扫描的自测试中，目的是在保证故障覆盖率的同时，将电路的扫描测试代价降低到非扫描可测试性设计的水平。为了构造这种适合于自测试(以下简称BIST)的改进的扫描森林结构，我们使用了三项技术：一种扫描触发器平衡分组策略、一种新的扫描树结构和一种新的扫描输入信号号处理办法。大量的实验结果表明，该方法与传统的基于扫描自测试方法相比，能获得更高的故障覆盖率。同时，改进的扫描森林结构相比于原始的扫描森林结构，能大幅度  减少集成电路芯片的面积开销。

面向存储器核的内建自测试

檀彦卓 徐勇军 韩银和 李华伟 李晓维

2005, 27(4): 40-42. doi:

摘要 ( 340 )   PDF (204KB) ( 1058 )   　　

存储器内建自测试是当前针对嵌入式随机存储器测试的一种经济有效的途径。它实质是BIST测试算法在芯片内部的硬件实现，形成“片上BIST测试结构999作为E-RAM核与芯片系统其他逻辑电路的接口，负责控制功能，实现片上E-RAM的自动测试。根据一个实际项目，本文介绍了MBIST的整体设计过程，并针对测试开销等给出了定量和定性的讨论。

基于CTL的SOCIP核的测试技术

吴明行 韩银和 李晓维

2005, 27(4): 43-45. doi:

摘要 ( 350 )   PDF (150KB) ( 481 )   　　

本文介绍了一种针对SOC测试设计中嵌入式芯核的核测试语言(CTL)。该语言描述了如何将可测试性设计置入具有知识产权(Intellectual Property，简称IP)芯核和SOC中，从 而加速测试生成和复用。CTL语言标准虽然还未被IEEE正式通过，但已经在EDA厂商、ATE厂商和IP芯核提供者之间悄然兴起并被积极采用，一系列基于CTL的产品也相继被研制  制出来。本文通过对CTL的分析与研究，较为详细地说明了CTL引入的重要性及其特性，并为SOCIP芯核提供CTL语言测试设计实例。

面向SOC系统设计的层次化CDFG的扩展

刘志鹏 边计年 王云峰 薛宏熙

2005, 27(4): 46-48. doi:

摘要 ( 73 )   PDF (177KB) ( 173 )   　　

本文主要介绍了层次化CDFG中标准控制结构和并行结构的扩充及转换方法，从而为在高层次SOC设计中真正使用HCDFG提供了基础。同时，文中还给出了HCDFG在系统验证中的作用，它为不同方法的混合验证提供了统一而有效的内部结构。

VLSI电路短路和开路故障模型研究进展

陈火军 江建慧

2005, 27(4): 49-53. doi:

摘要 ( 77 )   PDF (213KB) ( 264 )   　　

本文概述了近十年来VLSI电路的短路和开路缺陷及其故障建模的研究进展。本文将VLSI电路短路缺陷分为逻辑门内部的短路和逻辑门之间的互连短路两大类，重点介绍了栅氧短路和桥接故障模型。相应地，文中将VLSI电路的开路缺陷分为逻辑门内部的开路和逻辑门之间的互连 开路两大类，重点介绍了逻辑门内部的网络断开、浮栅和互连开路的故障模型。文中还讨论了故障模型与测试的关系。分析结果表明，目前已有的短路和开路故障模型还不够完善，特别需要研究故障机制对电路中其它节点动态行为的依赖性和对噪声的敏感性。

关于事件注入用于网络可信性测评的几个关键指标

王慧强[1] 庞永刚[1] 贺劼[2]

2005, 27(4): 54-56. doi:

摘要 ( 79 )   PDF (123KB) ( 167 )   　　

事件注入是源于故障注入原理，可以用于对计算机网络可信性进行测评研究。本文分析了事件注入技术在可信性测评中的应用问题，对事件注入的几个关键指标进行了相应的分析，并探讨了事件注入技术不足之处和改进方向。

基于代理的Byzantine一致性协议的研究

王天锷 张大方 杨金民

2005, 27(4): 57-59. doi:

摘要 ( 62 )   PDF (118KB) ( 201 )   　　

本文在研究了国内外Byzantine协议的基础上提出了一种新的Byzantine一致性协议，即基于代理的Byzantine一致性协议。该协议按照Byzantine容错机制将所有参与运算的进程分成很多小块，每个块设有一个代理。通过代理，块内的进程向其他块的进程发送运算结果。这样，在进程发生Byzantine错误时可以先在块的内部处理，从而可以有效地减少容错的开销和时延，提高系统的安全性。

网络应用软件健壮性测试方法研究

孙志岗 李扎 王宇颖

2005, 27(4): 60-62. doi:

摘要 ( 89 )   PDF (137KB) ( 485 )   　　

软件测试是提高软件可靠性的有效手段，健壮性是网络应用软件重要的质量因素。本文针对网络软件的特点，提出了一种测试网络软件健壮性的方法——通过对交互数据接口进行负载测试和接口容错测试，检验软件对异常数据的处理能力，从而确保各种异常输入的正确处理， 提高系统的安全性以及可靠性。

分布式入侵检测系统中告警相关的研究与实现

秦拯 龚发根 张大方

2005, 27(4): 63-65. doi:

摘要 ( 60 )   PDF (123KB) ( 199 )   　　

现有的告警相关方法处理开销比较大，特别是在告警风暴的情况下有可能无法处理。该文针对这种情况，提出一种改进的、适用于分布式入侵检测系统的告警相关方法，并给出了一个采用这种方法的实现框架及其实验结果。结果表明，改进后的告警相关方法能在告警相关识别率和告警相关准确率保持基本不降低的条件下，告警相关数据处理率降低40％以上，从而可保证告警相关部件在告警风暴的情况下仍有效地工作。

一个扩展的以QoS为指向的网格任务调度算法

吴俊 张大方 张伟鹏 祝勇刚

2005, 27(4): 66-67. doi:

摘要 ( 61 )   PDF (131KB) ( 186 )   　　

在对网格计算的研究中，有人考虑了计算资源中服务质量(QoS)因素，在对传统的Min-Min算法加以改进的基础上，提出了QoS Guided Min-Min算法。在此基础上，本文提出一种新的扩展型算法，以进一步提高网格资源的利用率。最后，本文对以上三种算法的实验结果进行了比较分析。

一个容错的网格资源选择算法

段智勇 张大方 张伟鹏

2005, 27(4): 68-70. doi:

摘要 ( 75 )   PDF (134KB) ( 184 )   　　

芝加哥大学提出了一个网格资源选择算法，能够同时满足单一资源选择和多个资源选择的要求。但是，由于算法一开始就选择了资源集合中单机最强的节点，所以很容易陷入局部最优，且算法不具备容错能力。针对这种情况，本文对该算法进行改进，提出了基于基版本／副版本技术的容错资源选择算法。模拟实验表明，算法是有效的。

一种改进的基于包对模型的有效带宽测量方法

李明杰 张大方 张伟鹏

2005, 27(4): 71-72. doi:

摘要 ( 85 )   PDF (125KB) ( 174 )   　　

本文通过分析数据包对的分离时间与背景流量之间的关系，提出了一种改进的基于包对模型测量端到端路径有效带宽的方法(ABwPP)，可以直接测量路径的有效带宽而不需已知瓶颈带宽。NS-2上的模拟实验结果表明，该方法是准确有效的。

一种遵循Rich—Club现象的网络拓扑模型

李莹 张大方

2005, 27(4): 73-75. doi:

摘要 ( 70 )   PDF (125KB) ( 305 )   　　

基于现有的AS网络拓扑生成模型，本文提出了一个遵循Rich-Club现象的新网络拓扑模型。该模型不仅保正反映AS网络的基本性质，还能满足AS网络所有的特性Rich-Club现象。仿真结果表明，本文的模型和算法是有效的。

一种基于概率密度函数的IP网包乱序行为评价指标

曾彬 张大方 黎文伟

2005, 27(4): 76-77. doi:

摘要 ( 116 )   PDF (151KB) ( 327 )   　　

目前。因特网端到端行为的研究多集中在包延迟、包丢失等测量指标的研究上，对包乱序行为却没有深入的研究。也缺乏能精确、全面反映包乱序程度的评价指标。本文针对包乱序行为，提出了一种基于概率密度函数的评价指标——包乱序密度函数。该指标能精确、直观地量 化包乱序的程度。最后。本文通过在中国教育和科研网选取的链路进行实际测量分析，使用该指标对所测链路的包乱序行为进行了评价。并初步总结了包乱序的行为特征。

一种站场图逻辑语义解析算法

胥幸燕 徐中伟

2005, 27(4): 78-79. doi:

摘要 ( 82 )   PDF (134KB) ( 153 )   　　

本文介绍了铁路车站站场图的结构，阐述了站场图逻辑语义的含义及站场图构成规则库的构建，提出了一种基于图搜索技术的站场图逻辑语义解析算法，并将该算法在铁路计算机联锁软件测试评估平台子系统的站场CAD拼贴及数据校验中实现。

C语言系统描述的HCDFG-Ⅱ实现

赵康 边计年 吴强 薛宏熙

2005, 27(4): 80-83. doi:

摘要 ( 78 )   PDF (195KB) ( 214 )   　　

C语言是系统设计中一种主要的系统描述语言，在系统级软硬件协同验证及随后的软硬件划分、接口综合和行为综合等中都需要把C语言的系统描述转化为控制数据流图。本文介绍了一种层次化控制数据流图HCDFG-Ⅱ模型，以及从C语言生成该模型的方法。HCDFG-Ⅱ的层次化模型 分为函数／进程级、语句级和操作级，根据需要可以生成不同级别的模型。本文讨论了C语言中各种控制结构及数组、指针、联合和结构等复杂数据类型生成HCDFG-Ⅱ的方法。

遗传算法在管网校合中的应用研究

袁国斌[1] 王晖[2] 陶俊[2]

2005, 27(4): 84-86. doi:

摘要 ( 64 )   PDF (127KB) ( 243 )   　　

本文对管网校合数学模型进行改进，提出了用遗传算法进行管网校合的方法，并对广义简约梯度法和遗传算法进行了比较和分析，最后指出了算法的不足和以后研究的主要方向。

EDSMT微体系结构研究

蒋江 邢座程 张民选

2005, 27(4): 87-91. doi:

摘要 ( 76 )   PDF (216KB) ( 212 )   　　

本文提出了一种多线程微处理器微体系结构EDSMT。EDSMT有效结合显示并行指令计算EPIC和动态同时多线程DSMT技术，通过软、硬件协同的方式充分开发和有效支持多个层次的并行性。EDSMT能够降低硬件设计的复杂性，提高微处理器性能。

SOAST-1：一种综合优化的AS级拓扑推理算法

卓莹 李楠 王宏 龚正虎 陈琳

2005, 27(4): 92-95. doi:

摘要 ( 65 )   PDF (192KB) ( 165 )   　　

网络拓扑推理是网络管理系统的基本功能之一，AS级拓扑推理是其重点和难点。本文概括了目前已提出的，基于路径和基于Traceroute的两类AS级拓扑推理算法；针对它们的优缺点，提出了一种综合优化的AS级拓扑推理算法：SOAST-1。SOAST-1以BGP路由表作为路由信息的主要 来源，以Traceroute探测作为辅助手段，综合了上述两类AS级拓扑推理算法的优点。算法分析和实际运行结果表明SOAST-1算法能够取得良好效果。

集群视频服务平台流媒体监控系统的设计与实现

董志 金海 吴敏娜

2005, 27(4): 96-98. doi:

摘要 ( 59 )   PDF (133KB) ( 159 )   　　

本文设计了集群视频服务平台流媒体监控系统的分布式体系结构，提出了一种单线程多任务的带宽信息统计策略，以及保证接收信息包顺序的组包算法。测试结果表明，本系统能够快速、稳定地反映集群视频服务平台的性能和提供的服务状况。

计算机射频通信的实例与关键技术

周进[1] 侯方勇[2] 刘云生[3]

2005, 27(4): 99-101. doi:

摘要 ( 83 )   PDF (193KB) ( 209 )   　　

射频通信技术极大地扩展了计算机的应用领域与灵活性，也对相关工程技术人员提出了新的要求。本文针对计算机射频通信的设计与实现，首先通过系统构成的实例，描述了此类系统基本的软硬件组成；然后，针对某些典型的关键技术问题，进行了深入分析，并给出了解决方 法和建议。

深亚微米集成电路设计中串扰分析与解决方法

马剑武 陈书明 孙永节

2005, 27(4): 102-104. doi:

摘要 ( 86 )   PDF (144KB) ( 174 )   　　

本文介绍了深亚微米集成电路设计中串扰的成因及其对信号完整性的影响，论述了串扰分析和设计解决的一般方法，对于实际设计具有一定的理论指导意义和应用参考价值。本文最后指出了我们工作的进一步研究方向。

基于标准单元ASIC设计的综合优化综述

胡春媚 江东 马剑武 陈书明 郭阳

2005, 27(4): 105-107. doi:

摘要 ( 91 )   PDF (187KB) ( 180 )   　　

本文讨论了基于标准单元ASIC设计的逻辑综合优化问题，总结提出了逻辑综合优化的四种方法：系统和算法级优化、代码级优化、电路级优化和部分全定制的方法，并给出了这些方法的应用场合和应用实效。

小空间电子元器件的抗振设计

左华 陈祖豪 张帷

2005, 27(4): 108-110. doi:

摘要 ( 70 )   PDF (149KB) ( 146 )   　　

本文对自由振动系统及阻尼受迫振动系统进行了分析，指出提高系统抗振强度所需改进的各项因素，并对上述因素进行综合考虑，提出了专门针对小空间电子元器件减振的可行方式。最后，通过实验验证了减振模型的可行性和优越性。