• 2009年第20卷第10期文章目次
    全 选
    显示方式: |
    • 一种基于类型传播分析的泛型实例重构方法

      2009, 20(10):2617-2627.

      摘要 (4625) HTML (0) PDF 642.10 K (4897) 评论 (0) 收藏

      摘要:重构泛型实例有利于提高软件的复用性和类型安全,但现有重构方法的时间复杂度较高,不适用于即时持续的重构.分析了变量类型传播分析方法在重构中的不足,提出了一种改进的泛型变量类型传播分析方法.该方法通过引入一种可以描述复杂参数化类型关系的泛型类型传播图,以复制节点的方式实现泛型变量属性敏感的类型分析,并通过解决别名问题来提高分析的精度.实例研究表明,可以在与程序规模呈近似线性增长的时间复杂度内实施重构,取得了较满意的效果.

    • >在线出版
    • 容错多处理机中一种高效的实时调度算法

      2009, 20(10):2628-2636.

      摘要 (4358) HTML (0) PDF 469.51 K (5431) 评论 (0) 收藏

      摘要:针对基于主副版本容错的多处理机中独立的、抢占性的硬实时任务,提出了一种高效的调度算法——TPFTRM(task partition based fault tolerant rate-monotonic)算法.该算法将单机实时RM 算法扩展到容错多处理机上,并且调度过程中从不使用主动执行的任务副版本,而仅使用被动执行和主副重叠方式执行的任务副版本,从而最大限度地利用副版本重叠和分离技术提高了算法调度性能.此外,TPFTRM 根据任务负载不同将任务集合划分成两个不相交的子集进行分配;还根据处理机调度的任务版本不同,将处理机集合划分成3 个不相交的子集进行调度,从而使TPFTRM 调度算法便于理解、实现以及减少了调度所需要的运行时间.模拟实验对各种具有不同周期和任务负载的任务集合进行了调度测试.实验结果表明,TPFTRM与目前所知同类算法相比,在调度相同参数的任务集合时不仅明显减少了调度所需要的处理机数目,还减少了调度所需要的运行时间,从而证实了TPFTRM 算法的高效性.

    • 蜕变测试和断言检查的比较与实验研究

      2009, 20(10):2637-2654.

      摘要 (5752) HTML (0) PDF 821.81 K (5672) 评论 (0) 收藏

      摘要:在软件测试中,测试预言是一种用于检查程序在测试中是否正常运行的机制.然而在某些实际情况下,还无法制定测试预言或者难以有效地应用测试预言.针对此类测试预言问题,蜕变测试于近年应运而生,但蜕变测试的效率问题还没有被充分地加以研究.作者用控制实验的方法研究了使用蜕变测试的成本及效率,进而将蜕变测试和常用的断言检查两种方法的错误检测率和时间成本进行了比较和分析.实验结果表明,相比于断言检查方法,蜕变测试具有检测到更多错误的潜力.通过分析蜕变测试的效率和性能,与断言测试相比,蜕变测试的错误检测率更高效而效率有待提高,可适用于较为粗粒度的测试需求.

    • 上下文感知系统中的规则生成与匹配算法

      2009, 20(10):2655-2666.

      摘要 (4989) HTML (0) PDF 782.68 K (5748) 评论 (0) 收藏

      摘要:针对现有上下文感知系统中的规则主要依靠开发者或用户手工定义的问题,提出了一种基于粗糙集理论的自动规则生成方法.该方法将上下文感知系统视为一种决策信息系统,并利用可辨识矩阵对上下文信息加以约简,进而自动生成规则.由于可供使用的数据有限,所生成的规则无法完全覆盖上下文的取值范围,因此可能出现找不到与上下文状态相匹配规则的问题.为了解决这一问题,提出了一种基于语义距离的规则匹配算法.最后验证了所提出方法的有效性和效率.

    • >在线出版
    • 基于函数依赖的结构匹配方法

      2009, 20(10):2667-2678.

      摘要 (5908) HTML (0) PDF 623.67 K (5363) 评论 (0) 收藏

      摘要:模式匹配是模式集成、数据仓库、电子商务以及语义查询等领域中的一个基础问题,近来已经成为研究的热点,并取得了丰硕的成果.这些成果主要利用元素(典型的为关系模式中的属性)自身的信息来挖掘元素语义,目前,这方面的研究已经相当成熟.结构信息作为模式中一种重要的信息,能够为提高模式匹配的精确性提供有用的支持,但是目前关于如何利用结构信息提高模式匹配的精确性的研究还很少.将模式元素之间的相似度分为语义相似度(根据元素自身信息得到的相似度)和结构相似度(根据元素之间的关联关系得到的相似度),并采用新的统计方法计算元素间的结构相似度,然后再综合考虑语义相似度得到元素间的相似概率;最后根据相似概率得到模式元素间的映射关系(模式元素之间的对应关系).实验结果表明,该算法在查准率、查全率及全面性等方面都优于已有的其他算法.

    • 基于动作图的视角无关动作识别

      2009, 20(10):2679-2691.

      摘要 (4974) HTML (0) PDF 745.46 K (6778) 评论 (0) 收藏

      摘要:针对视角无关的动作识别,提出加权字典向量描述方法和动作图识别模型.将视频中的局部兴趣点特征和全局形状描述有机结合,形成加权字典向量的描述方法,该方法既具有兴趣点抗噪声强的优点,又可克服兴趣点无法识别静态动作的缺点.根据运动捕获、点云等三维运动数据构建能量曲线,提取关键姿势,生成基本运动单元,并通过自连接、向前连接和向后连接3种连接方式构成有向图,称为本质图.本质图向各个方向投影,根据节点近邻规则建立的有向图称为动作图.通过Na?ve Bayes训练动作图模型,采用Viterbi算法计算视频与动作图的匹配度,根据最大匹配度标定视频序列.动作图具有多角度投影和投影平滑过渡等特点,因此可识别任意角度、任意运动方向的视频序列.实验结果表明,该算法具有较好的识别效果,可识别单目视频、多目视频和多动作视频.

    • 基于C4.5决策树的流量分类方法

      2009, 20(10):2692-2704.

      摘要 (5240) HTML (0) PDF 645.73 K (8625) 评论 (0) 收藏

      摘要:近年来,利用机器学习方法处理流量分类问题成为网络测量领域一个新兴的研究方向.在现有研究中,朴素贝叶斯方法及其改进算法以其实现简单、分类高效的特点而被广泛应用.但此类方法过分依赖于样本在样本空间的分布,具有潜在的不稳定性.为此,引入C4.5决策树方法来处理流量分类问题.该方法利用训练数据集中的信息熵来构建分类模型,并通过对分类模型的简单查找来完成未知网络流样本的分类.理论分析和实验结果都表明,利用C4.5决策树来处理流量分类问题在分类稳定性上均具有明显的优势.

    • >在线出版
    • 一种无线传感器网络分布式安全成簇协议

      2009, 20(10):2705-2720.

      摘要 (5973) HTML (0) PDF 785.34 K (7087) 评论 (0) 收藏

      摘要:分簇的层次型拓扑控制方式在无线传感器网络中得到广泛研究和应用.然而,由于传感器网络本身所具有的开放性和资源有限的特点,攻击者可以很容易对成簇协议实施有效的误用和破坏.因此,保证成簇协议安全性是其实际广泛应用的基本前提.针对成簇协议所面临的各种安全威胁,提出了一种分布式安全成簇协议,通过网络安全初始化、可信基站的随机数广播和单向密钥链技术来有效地抵御节点伪装和簇首占据攻击、簇成员恶意征募攻击和多重簇成员身份攻击.对协议的安全性和开销进行了广泛和深入的分析,证明了协议的安全性和有效性.

    • 移动Ad Hoc网络通信量相关干扰感知路由协议

      2009, 20(10):2721-2728.

      摘要 (5440) HTML (0) PDF 615.79 K (5307) 评论 (0) 收藏

      摘要:干扰严重影响移动Ad hoc网络的网络吞吐量、能量消耗、网络寿命等性能.在已有基于邻居数目和分布位置的干扰模型基础上,进一步考虑各邻居上的通信量情况,提出通信量干扰模型.并在该干扰模型的基础上,提出一个通信量相关干扰感知路由TIR(traffic load-based interference-aware routing)协议.TIR通过在源节点和目的节点之间选择干扰最小的路径来降低数据包在转发过程中可能受到的干扰.模拟实验结果表明,所提出的通信量干扰模型符合移动Ad hoc网络的特性,通信量相关干扰感知路由协议对网络寿命、通信延迟及吞吐量等网络性能有明显改善.

    • 基于蚁群优化解决传感器网络中的能量洞问题

      2009, 20(10):2729-2743.

      摘要 (13949) HTML (0) PDF 1.12 M (9467) 评论 (0) 收藏

      摘要:基于多跳的无线传感器网络,越靠近sink的传感器节点因需要转发更多的数据,其能量消耗就越快,从而在sink周围形成了一种称为“能量洞”的现象.“能量洞”问题会导致整个网络由于内部节点能量过早耗尽而结束寿命,同时,网络中离sink较远的节点仍有大量能量剩余.研究“能量洞”现象,基于改进的分级环模型,总结出调节各环内节点的数据传输距离是实现网络节能的有效方法.证明搜索各区域最优的传输距离是一个多目标优化问题,即是NP难问题.从而提出一种基于蚁群优化的分布式算法,各区域根据其节点分布情况自适应地探索近似最优的传输距离,延长网络寿命.模拟实验结果表明,该算法在较短的时间内能够收敛到合理的解,并且得到的网络寿命接近于理想情况下的最优时间,与现有的类似算法相比,该算法提供了更长的网络寿命,并能适用于非均匀节点分布情况.

    • 路标迭代提取和剔除的自适应空洞处理算法

      2009, 20(10):2744-2751.

      摘要 (4439) HTML (0) PDF 566.38 K (4475) 评论 (0) 收藏

      摘要:针对无线传感器网络贪婪地理路由协议中的路由空洞问题,提出一种高效的基于路标迭代提取和剔除的自适应空洞处理算法.该算法中,当探测包贪婪转发遇到空洞时,在网络拓扑局部平面化的基础上,以左(右)手法则提取空洞边界并沿其逆(顺)时针周边模式双向转发,同时,分布式地进行路标的迭代提取和剔除,直到获取的路标使得后续的数据包依次以它们为中间目标节点进行传输而不再遇到空洞为止.仿真结果表明,该协议能够以较小的控制开销代价获得次最优的传输路径,极大地提高了路由协议的性能,可以应用于无法消除路由空洞的大规模无线传感器网络贪婪地理路由协议.

    • 一种基于磁盘介质的网络存储系统缓存

      2009, 20(10):2752-2765.

      摘要 (4552) HTML (0) PDF 892.16 K (6125) 评论 (0) 收藏

      摘要:随着计算规模越来越大,网络存储系统应用领域越来越广泛,对网络存储系统I/O性能要求也越来越高.在存储系统高负载的情况下,采用低速介质在客户机和网络存储系统的I/O路径上作为数据缓存也变得具有实际的意义.设计并实现了一种基于磁盘介质的存储系统块一级的缓存原型D-Cache.采用两级结构对磁盘缓存进行管理,并提出了相应的基于块一级的两级缓存管理算法.该管理算法有效地解决了因磁盘介质响应速度慢而带来的磁盘缓存管理难题,并通过位图的使用消除了磁盘缓存写Miss时的Copy on Write开销.原型系统的测试结果表明,在存储服务器高负载的情况下,缓存系统能够有效地提高系统的整体性能.

    • >在线出版
    • 网格服务资源多维性能聚类任务调度

      2009, 20(10):2766-2775.

      摘要 (5507) HTML (0) PDF 554.10 K (5401) 评论 (0) 收藏

      摘要:网格计算是当前一个重要的研究领域,其中任务调度是一个基本组成部分,其性能直接影响到网格服务质量.为了缩短任务调度完成时间,提高任务调度性能,提出了一种网格资源多维性能聚类任务调度算法MPCGSR (task scheduling algorithm based on multidimensional performance clustering of grid service resources).该算法根据网格环境下服务资源数量庞大、异构、多样的特点,预先以构建的网格服务资源超图模型为基础,结合小世界理论对服务资源进行多维性能聚类,将任务与聚类资源相匹配并实施调度.模拟实验结果表明,算法较之同类算法具有优越性,是一种有效的网格任务调度算法.

    • 面向分布式证明的信任协商策略语言和方法

      2009, 20(10):2776-2786.

      摘要 (5464) HTML (0) PDF 583.96 K (4972) 评论 (0) 收藏

      摘要:现有信任协商语言对复杂的访问控制策略和协商策略以及信任分布式证明方法的支持都不够全面.在RT(role-based trust-management)语言基础上提出一种面向信任分布式证明和协商的策略语言RTP(role-based trust proving),其特点是能够支持信任分布式证明方法,可以定义复杂角色,保护信任证敏感信息并能避免信任证盲目搜索.给出了RTP语言及其推理规则的语法语义描述,介绍了一种基于RTP语言的信任分布式证明协商示例算法.实验结果表明,该算法支持RTP语言的功能,且比传统信任协商方法有很大的性能提升.

    • >综述文章
    • 无线传感器网络中的地址分配协议

      2009, 20(10):2787-2798.

      摘要 (7612) HTML (0) PDF 691.97 K (7767) 评论 (0) 收藏

      摘要:地址用来标识节点,使能网络通信协议,在无线传感器网络中扮演重要角色.由于无线传感器网络中节点众多,再考虑其网络动态性,手动地为每个节点分配地址是一件繁琐甚至无法完成的工作,于是,地址分配协议成为必需.由于无线传感器网络自身所具有的特点,传统的DHCP协议和ad hoc网络的地址分配协议对其不再适用.分析了无线传感器网络地址分配协议的必要性,总结了地址分配协议需要解决的问题和所面临的挑战,并对已有地址分配协议进行了分类.介绍和比较了当前有代表性的地址分配协议,并指出了它们的问题,分析了地址分配协议下一步研究的重点.

    • 突破认证测试方法的局限性

      2009, 20(10):2799-2809.

      摘要 (4640) HTML (0) PDF 581.28 K (4098) 评论 (0) 收藏

      摘要:认证测试是一种用于证明安全协议认证属性的新方法,该方法能够简化协议认证属性的证明过程,但其局限性是无法应用于认证测试元素被多重加密的情况.指出Perrig和Song提出的认证测试改进方案在多个方面所存在的问题.在此基础上提出新的改进方案,并进行了形式化证明.新的认证测试定理突破了认证测试元素在整个协议消息中不能被加密的限制,扩展了认证测试理论的应用范围.

    • 基于签密的密码工作流密钥封装机制

      2009, 20(10):2810-2821.

      摘要 (4479) HTML (0) PDF 614.13 K (5021) 评论 (0) 收藏

      摘要:密码工作流(cryptographic workflow)是多用户环境下一种特殊的密码系统工作模式,在这种工作模式下,加密消息需要依据某种策略进行,因此只有履行这一策略的实体才能进行消息解密.为保证在密码工作流模式下密钥封装能够同时实现密钥免托管性和密钥封装传递的不可伪造性,基于签密的思想定义了一个新的密码工作流模式下的密钥封装机制.首先定义了密码工作流模式下基于签密的密钥封装一般模型,并给出了相应的安全模型;其次,结合秘密共享方案、基于身份加密方案和签密方案,提出一个新的结构方案,并在标准模型(standard model)下利用序列游戏证明方法对该结构方案的安全性进行了详细证明.证明结果表明,该密钥封装结构方案能够达到密码工作流模式下要求的接收者安全和外部安全.

    • >在线出版
    • 利用类型推理验证Ad Hoc安全路由协议

      2009, 20(10):2822-2833.

      摘要 (4922) HTML (0) PDF 645.24 K (5513) 评论 (0) 收藏

      摘要:提出一种基于类型推理的移动Ad-Hoc网络安全路由协议的形式化验证方法.定义了一种邻域限制通信演算NCCC(neighborhood-constrained communication calculus),包括演算的语法和基于规约的操作语义,在类型系统中描述了移动Ad-Hoc网络路由协议的安全属性,定义了近似攻击消息集用以精简Dolev-Yao攻击模型.还给出了该方法的一个协议验证实例.基于类型推理,该方法不仅能够验证协议的安全性,也可以得出针对协议的攻击手段.因为攻击集的精简,有效地缩减了推理空间.

    • 语义网站点的发现与排序

      2009, 20(10):2834-3843.

      摘要 (5742) HTML (0) PDF 541.91 K (6189) 评论 (0) 收藏

      摘要:随着语义网中RDF数据的大量涌现,语义搜索引擎为用户搜索RDF数据带来了便利.但是,如何自动地发现包含语义网信息资源的站点,并高效地在语义网站点中收集语义网信息资源,一直是语义搜索引擎所面临的问题.首先介绍了语义网站点的链接模型.该模型刻画了语义网站点、语义网信息资源、RDF模型和语义网实体之间的关系.基于该模型讨论了语义网实体的归属问题,并进一步定义了语义网站点的发现规则;另外,从站点链接模型出发,定义了语义网站点依赖图,并给出了对语义网站点进行排序的算法.将相关算法在一个真实的语义搜索引擎中进行了初步测试.实验结果表明,所提出的方法可以有效地发现语义网站点并对站点进行排序.

    • 2008年中国计算机大会推荐优秀论文介绍

      2009, 20(10):2857-2858.

      摘要 (4874) HTML (0) PDF 191.09 K (5064) 评论 (0) 收藏

      摘要:

    • 软件可靠性评估的重要抽样方法

      2009, 20(10):2859-2866.

      摘要 (5239) HTML (0) PDF 500.93 K (6417) 评论 (0) 收藏

      摘要:基于统计测试的马尔可夫使用模型对软件可靠性评估提出了一种有效的估计方法.该方法利用重要抽样技术在保证可靠性估计无偏性的条件下,利用交叉熵度量操作剖面与零方差抽样分布之间的差异,通过启发式迭代过程调整各个状态之间的转移概率来修正测试剖面.从理论上证明了利用修正测试剖面测试估计的可靠性是方差为0的无偏估计.最后给出了软件可靠性估计的最优测试剖面生成的启发式迭代算法.仿真结果表明,该方法与模拟退火算法相比,能够明显降低估计的方差,在提高估计精度的同时加快统计测试速度.

    • 基于适应性分段估计的数据流相似性搜索

      2009, 20(10):2867-2884.

      摘要 (4686) HTML (0) PDF 1.43 M (5032) 评论 (0) 收藏

      摘要:相似性搜索在股票交易行情、网络安全、传感器网络等众多领域应用广泛.由于这些领域中产生的数据具有无限的、连续的、快速的、实时的特性,所以需要适合数据流上的在线相似性搜索算法.首先,在具有或不具有全局约束条件下,分别提出了没有索引结构的DTW(dynamic time warping)下限函数LB_seg_WFglobalLB_seg_WF,它们是一种分段DTW技术,能够处理数据流上的非等长序列间在线相似性匹配问题.然后,为了进一步提高LB_seg_WFglobalLB_seg_WF的近似程度,提出了一系列的改进方法.最后,针对流上使用LB_seg_WFglobalLB_seg_WF可能会出现连续失效的情况,分别提出了DTW的下限函数LB_WFglobal(具有全局约束条件)和上限函数UB_WF、下限函数LB_WF(不具有全局约束条件).通过增量方式快速估计DTW,极大地减少了估计DTW的冗余计算量.通过理论分析和统计实验,验证了该方法的有效性.

    • 一种基于反馈可信度的分布式P2P信任模型

      2009, 20(10):2885-2898.

      摘要 (5146) HTML (0) PDF 1.09 M (6138) 评论 (0) 收藏

      摘要:开放、共享与匿名的Peer-to-Peer(简称P2P)网络已经取得了越来越多的应用,无中心对等的特性也吸引了越来越多的用户.但由于其网络中的节点不受约束,资源的共享是用户自愿的行为,因此节点间的信任很难通过传统的信任机制建立.一种可行的解决方案是借鉴人际网络中的信任关系,建立一种基于信誉的全局信任模型.已有的工作基本建立在信任度高的节点其反馈也更可信这个假设的基础上,将节点的反馈质量简单地等同于服务质量.针对这一问题,提出了一种基于节点反馈可信度的分布式P2P全局信任模型(简称FCTrust),用于量化和评估节点的可信程度,并给出了模型的数学表述和分布式实现方法.分析及仿真实验结果表明,FCTrust较已有的全局信任模型在遏制更广泛类型的恶意节点攻击的有效性、迭代计算的收敛性及消息成本上有较大提高.

    • 基于概要数据结构可溯源的异常检测方法

      2009, 20(10):2899-2906.

      摘要 (4916) HTML (0) PDF 530.76 K (6032) 评论 (0) 收藏

      摘要:提出一种基于sketch概要数据结构的异常检测方法.该方法实时记录网络数据流信息到sketch数据结构,然后每隔一定周期进行异常检测.采用EWMA(exponentially weighted moving average)预测模型预测每一周期的预测值,计算观测值与预测值之间的差异sketch,然后基于差异sketch采用均值均方差模型建立网络流量变化参考.该方法能够检测DDoS、扫描等攻击行为,并能追溯异常的IP地址.通过模拟实验验证,该方法占用很少的计算和存储资源,能够检测骨干网络流量中的异常IP地址.

    • 可证明安全的多接收者公钥加密方案设计与分析

      2009, 20(10):2907-2914.

      摘要 (5267) HTML (0) PDF 497.68 K (6115) 评论 (0) 收藏

      摘要:针对现有安全广播协议密钥分发效率较低的问题,提出了一种通过多接收者公钥加密实现安全广播的方法.以Shamir的门限秘密共享方案为设计基础,首先提出了一个基于椭圆曲线上双线性变换的具有抗不可区分选择明文攻击(IND-CPA)安全性的多接收者公钥加密方案,然后对所提方案进行安全扩展,在此基础上最终提出了一个具有抗不可区分自适应选择密文攻击(IND-CCA2)安全性的多接收者公钥加密方案.基于双线性判定Diffie- Hellman假设和双线性间隙Diffie-Hellman假设,对上述所声称的IND-CPA安全性和IND-CCA2安全性进行了证明.同时,对方案的正确性及性能等进行了分析和证明.分析发现,该方案是一个安全、有效的公钥加密方案.由一个加密密钥所加密的密文可以被多个解密密钥解密而得到其所对应的明文,这使得该方案具有非常重要的应用,尤其是可以用来实现安全广播,以便在不安全的、开放的网络环境中安全地广播敏感信息.

    • 教育资源网格模型及副本创建策略

      2009, 20(10):3844-2856.

      摘要 (4106) HTML (0) PDF 642.62 K (4470) 评论 (0) 收藏

      摘要:教育资源网格是解决目前分布式教育资源共享问题的有效手段.针对中小学教育资源共享问题,提出了层次式的教育资源网格模型,定义了各层节点的功能.通过与欧洲数据网格对比,分析了教育资源网格的特点.基于层次式的教育资源网格,对影响副本创建策略性能的因素进行了分析,然后引入网络带宽和文件大小两个参数,提出了一种动态副本创建策略(dynamic replica creation strategy,简称EDRS).利用数据网格模拟工具OptorSim构建了教育资源网格虚拟环境,分析比较了EDRS策略与Caching-LRU策略、Caching-LFU策略和基于经济模型的副本创建策略的性能.最后,综合各项指标分析了不同策略对教育资源网格系统性能的影响.结果表明,EDRS策略在教育资源网格应用中有着更好的系统性能.

当期目录


文章目录

过刊浏览

年份

刊期

联系方式
  • 《软件学报 》
  • 主办单位:中国科学院软件研究所
                     中国计算机学会
  • 邮编:100190
  • 电话:010-62562563
  • 电子邮箱:jos@iscas.ac.cn
  • 网址:https://www.jos.org.cn
  • 刊号:ISSN 1000-9825
  •           CN 11-2560/TP
  • 国内定价:70元
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号