• 2015年第26卷第12期文章目次
    全 选
    显示方式: |
    • 构件软件的回归测试复杂性度量

      2015, 26(12):3043-3061. DOI: 10.13328/j.cnki.jos.004876

      摘要 (2897) HTML (156) PDF 2.34 M (2826) 评论 (0) 收藏

      摘要:基于构件的软件构建方法目前被广泛使用在软件开发中,用于减少软件开发的工程成本和加快软件开发进度.在软件维护过程中,由于构件更新或者新版本的发布,基于构件的系统会受到影响,需要进行回归测试.对于指定的软件修改需求,维护者可以实施不同的修改手段.不同的修改手段会导致不同的回归测试复杂性,这种复杂性是软件维护成本和有效性的重要因素.目前的研究没有强调构件软件的回归测试复杂性问题.基于修改影响复杂性模型和度量,提出一种回归测试的复杂性度量框架.该度量框架包括两个部分:基于图的模型和形式化度量计算.该度量可以有效表示构件软件分别在构件和系统层面的回归测试复杂性因素,可视化地体现复杂性变化.然后根据模型,提出具体的度量计算方式.最后,通过实验研究,针对同一个构件软件的相同修改需求,利用若干个实验组进行独立修改实施,然后比较回归测试的复杂性.实验结果表明,所提出的度量方式是可行和有效的.

    • 基于代码库和特征匹配的函数名称推荐方法

      2015, 26(12):3062-3074. DOI: 10.13328/j.cnki.jos.004817

      摘要 (3149) HTML (217) PDF 1.42 M (3694) 评论 (0) 收藏

      摘要:函数名称质量的高低,对于理解和维护程序非常重要.然而对于软件开发人员,尤其是母语非英语的软件开发人员,为函数选取高质量的名称比较困难.为此,提出一种函数名称推荐方法.首先,基于开源软件创建函数库;然后,对于某个需要推荐名称的函数f,从函数库中检索与其相似的函数.对检索返回的相似函数用自然语言处理工具对函数名进行解析并获取标注词条,然后,从相应的函数体中提取特征代码并与相应的标注词条建立关联.基于此关联关系以及函数f的特征,自动推荐合适的函数名.该方法在开源项的1430个函数中进行了初步验证,结果表明:有22.7%的推荐结果与原函数名完全一致,有57.9%的推荐结果与原函数名关键词一致或基本一致.

    • 基于程序不变量计算软件可靠性

      2015, 26(12):3075-3087. DOI: 10.13328/j.cnki.jos.004803

      摘要 (3042) HTML (167) PDF 1.28 M (3494) 评论 (0) 收藏

      摘要:现有的计算软件可靠性的方法采用测试的输入/输出结果,但这些数据并不能真实地反映软件内部的真实行为,如测试中会出现假性正确的情况以及测试不能显示一个输入有多个错误的输出情况.试图通过程序不变量来计算软件的可靠性,程序不变量可以描述程序的性质.首先选取测试用例集,动态地获取程序不变量,再从这些不变量中提取失效数据,最后,基于Nelson模型计算软件的可靠性.作为实验,对西门子程序包计算软件的可靠性.采用随机、分支覆盖和分块覆盖这3种不同的测试方法得到程序不变量,据此计算程序的可靠性.为了检查结果的可行性,采用传统方法计算这些软件的可靠性.两种可靠性比较后显示:它们的差别很小,而且不依赖于对测试方法的选择.通过进一步的方差分析得知,用所提出的方法计算的可靠性比用现有的方法计算的可靠性具有更小的波动,即更平稳.因此,前者更接近系统的真实可靠性.结论说明,可用程序不变量来计算软件的可靠性.

    • 浮点数学函数异常处理方法

      2015, 26(12):3088-3103. DOI: 10.13328/j.cnki.jos.004814

      摘要 (2689) HTML (159) PDF 1.69 M (4190) 评论 (0) 收藏

      摘要:异常会造成程序错误,实现完全没有异常的浮点计算软件也很艰难,因此,实现有效的异常处理方法很重要.但现有的异常处理并不针对浮点运算,并且研究重点都集中在整数溢出错误上,而浮点类型运算降低了整数溢出存在的可能.针对上述现象,面向基于汇编实现的数学函数,提出了一种针对浮点运算的分段式异常处理方法.通过将异常类型映射为64位浮点数,以核心运算为中心,将异常处理过程分为3个阶段:输入参数检测(处理INV异常)、特定代码检测(处理DZE异常和INF异常)以及输出结果检测(处理FPF异常和DNO异常),并从数学运算的角度对该方法采用分段式处理的原因进行了证明.实验将该方法应用于Mlib浮点函数库,对库中600多个面向不同平台的浮点函数进行了测试.测试结果表明:该方法能够将出现浮点异常即中断的函数个数从90%降到0%.同时,实验结果验证了该方法的高效性.

    • 数组维度类型程序设计方法及高性能FFT实现

      2015, 26(12):3104-3116. DOI: 10.13328/j.cnki.jos.004801

      摘要 (2886) HTML (189) PDF 1.36 M (3046) 评论 (0) 收藏

      摘要:异构集群多层次异构存储的特点,决定了在其上进行计算时,数据需要进行更多维度的划分.现有集群程序设计语言缺乏对多维数组传输和转置的统一表示机制.介绍多维数组维度转置的表示方法和课题组实现的Parray语言,可以对异构集群复杂数据维度变换的数据操作进行清晰表示.同时介绍基于数组维度类型程序设计方法和Parray语言实现的天河1A系统上的大规模3维FFT,该算法代码实现简洁,同时得到了良好的性能和可延展性.

    • 结合扩展规则重构的#SAT问题增量求解方法

      2015, 26(12):3117-3129. DOI: 10.13328/j.cnki.jos.004827

      摘要 (2789) HTML (174) PDF 1.35 M (2780) 评论 (0) 收藏

      摘要:#SAT问题是人工智能中的重要问题,在人工智能领域被广泛应用.在对基于扩展规则的模型计数求解方法CER深入研究的基础上,重构CER中使用的计算公式,并对其正确性进行了证明;提出极大项相交集和扩展极大项相交集的概念,并给出根据两者关系重用极大项相交集计算结果的增量求解方法,且对广义互补子句集对应的所有扩展极大项相交集进行剪枝,有效避免了计算所有极大项相交集对应极大项个数时的冗余求解;提出构建记录子句间互补关系的互补表方法,给出重用极大项相交集基础子句集互补结果的增量互补判定方法,较好地避免了判断子句间和各极大项相交集的基础子句集互补关系时的重复计算.实验结果表明:RCER方法易于实现,扩展性强,比CER方法效率更高,尤其是在互补因子较低时,效率提升更为显著.

    • 基于查询子主题分类的多样性搜索评价方法

      2015, 26(12):3130-3139. DOI: 10.13328/j.cnki.jos.004744

      摘要 (2649) HTML (132) PDF 1.08 M (3489) 评论 (0) 收藏

      摘要:多样化检索结果的评测通常假设一个查询词包含多个权重各不相同的用户子意图,并在此假设的基础上对检索结果进行评测.虽然大多数已经存在的多样化检索评测方法利用了这些特性对检索结果进行评测,但在评测过程中,它们都忽略了查询子意图的类型信息;而不同类型的查询子意图对信息需求具有不同的特点.首先,通过引入衰减函数对这种特点进行描述,进而对用户子意图的分类方法进行抽象;在此基础上,提出了利用查询子意图类型信息进行多样化检索结果评测的框架,该框架定义了利用查询子意图类型信息进行多样化检索评测的方法应该具有的结构;然后,讨论了在用信息类和导航类作为子意图分类方法的前提下,其对应的衰减函数的形式;最后,在TREC与NTCIR测试集上的实验结果表明了所提出方法的有效性.

    • 概率最大受限路径相容算法

      2015, 26(12):3140-3150. DOI: 10.13328/j.cnki.jos.004815

      摘要 (2912) HTML (136) PDF 1.30 M (3904) 评论 (0) 收藏

      摘要:研究了可用于求解约束满足问题的最大受限路径相容算法(maxRPC).maxRPC算法执行过程中有大量无效的寻找路径相容证明(PC-witness)的操作,有效地识别和避免这些无效的寻找PC-witness的操作,可以提高maxRPC算法的求解效率.首先,提出了在一条约束上任意两个相容的值在任意路径上存在PC-witness的概率;然后,基于这一概率提出了一种概率最大受限路径相容算法(PmaxRPC),并将新算法成功应用于求解约束满足问题的回溯搜索.实验结果显示:PmaxRPC可以避免一部分无效的寻找PC-witness的操作,在求解约束满足问题时,PmaxRPC效率高于maxRPC.在某些测试用例上,PmaxRPC比maxRPC和最流行的弧相容算法效率更高.

    • 基于树形条件随机场的跨语言时态标注

      2015, 26(12):3151-3161. DOI: 10.13328/j.cnki.jos.004816

      摘要 (2669) HTML (156) PDF 1.10 M (3127) 评论 (0) 收藏

      摘要:提出时态树的概念和构造方法,从而将汉英时态转换问题转换为时态树标注的问题.而后,使用树形条件随机场为未标注时态树的结点标注英语时态.提出的特征函数的模板较好地满足了模型推断的需要.实验结果表明:与基于线性条件随机场模型的时态标注方法相比,基于时态树方法的准确率有大幅度的提高,说明使用时态树能够更好地表达子句间时态的依赖关系.

    • 概念格多属性渐减式构造

      2015, 26(12):3162-3173. DOI: 10.13328/j.cnki.jos.004818

      摘要 (2550) HTML (132) PDF 1.23 M (2763) 评论 (0) 收藏

      摘要:渐进式算法是概念格构造的重要方法之一,但以前的渐进式算法均为渐增式算法,即对象或属性都是增加的.实践表明,很多场合需要属性减少后的概念格.2013年,减少单个属性的渐减式算法已有研究,然而该算法只适用于单个属性,减少多个属性时,该算法需要反复执行多次.研究了减少多个属性的一次性渐减式算法,该算法与减少单个属性的渐减式算法有相同的时间复杂度,但当,减少多个属性时,单属性的渐减式算法需要反复执行多次,而该算法只需执行一次.

    • 使用ECC的身份混合签密方案

      2015, 26(12):3174-3182. DOI: 10.13328/j.cnki.jos.004819

      摘要 (2991) HTML (159) PDF 1.09 M (3344) 评论 (0) 收藏

      摘要:身份混合签密能够高效封装对称密钥和安全传输数据.针对现有身份混合签密方案计算复杂度高的问题,集成身份混合签密和椭圆曲线密码学(ECC)中的双线性映射,构造了一种使用ECC的身份混合签密方案.证明了所构造的方案在随机预言模型下满足co-BDH假设下的保密性和co-CDH假设下的不可伪造性.由于该方案通信成本低且计算效率高,因而能够更好地满足密码学应用需求.

    • ABeCK模型下安全的基于属性的认证密钥协商协议

      2015, 26(12):3183-3195. DOI: 10.13328/j.cnki.jos.004825

      摘要 (2549) HTML (177) PDF 1.31 M (2933) 评论 (0) 收藏

      摘要:基于属性的认证密钥协商(attribute-based authenticated key agreement,简称ABAKE)协议可在保护身份隐私的通信环境中为用户建立共享的会话密钥,ABeCK(attribute-based extended Canetti-Krawczyk)模型是适用于ABAKE协议安全性分析的一种安全强度较高的模型.首先在GCDH(gap computational Diffie-Hellman)假设的基础上提出了GCPBDHE(gap computational parallel bilinear Diffie-Hellman exponent)假设,然后,基于Waters属性基加密方案提出了一个基于属性的认证密钥协商协议,并在GCPBDHE假设和CDH假设成立的条件下,证明了该方案在ABeCK模型下是安全的.与现有的ABeCK模型下安全的ABAKE协议相比,降低了通信开销.

    • 抗签名密钥泄露的可撤销无证书签名

      2015, 26(12):3196-3203. DOI: 10.13328/j.cnki.jos.004826

      摘要 (2973) HTML (155) PDF 906.14 K (2966) 评论 (0) 收藏

      摘要:当用户的私钥泄露或使用权限到期时,系统如何撤销该用户是亟待解决的问题.这一问题在传统公钥系统TPKC和基于身份的公钥系统IBC下已有解决方案,然而在无证书公钥系统中,这一问题至今没有得到很好的解决.我们知道,无证书公钥系统没有庞杂的证书库和密钥托管问题,只是算法的计算量稍有增加,是TPKC和IBC之外的一种较理想的公钥系统,所以对它的撤销机制的研究十分必要.设计了一种可撤销的无证书签名方案,基本原理是:系统定期地给每个未被撤销的用户生成新的时间密钥,并通过公共信道传输给用户.相比现有的Al-Riyami和Paterson的撤销机制而言,该方案更加高效.同时,新方案达到了抗签名密钥泄露的安全性,且签名密钥的长度非常短.在CDH困难性假设下,该方案是UF-CMA可证明安全的.

    • 高效可证安全的无证书聚合签名方案

      2015, 26(12):3204-3214. DOI: 10.13328/j.cnki.jos.004830

      摘要 (2531) HTML (194) PDF 1.14 M (3230) 评论 (0) 收藏

      摘要:由于现有聚合签名方案多数是基于双线性映射构造,存在计算效率低的不足.针对不同的网络环境,提出了2种不使用双线性映射的无证书聚合签名方案CLAS-Ⅰ和CLAS-Ⅱ,并在随机预言机模型下,基于离散对数困难问题证明了方案的不可伪造性;同时,分析了该方案所具有的公开验证性等安全属性.与现有方案相比较,由于未使用双线性映射运算,该方案具有更高的计算效率.由于方案CLAS-Ⅰ的聚合签名长度较长,将用于带宽较高的网络环境;CLAS-Ⅱ具有较短的签名长度,且长度与用户数无关,将用于带宽较低的网络环境.

    • RFID快速隐私保护认证协议

      2015, 26(12):3215-3222. DOI: 10.13328/j.cnki.jos.004832

      摘要 (2870) HTML (154) PDF 858.26 K (3234) 评论 (0) 收藏

      摘要:基于对称密码体系的RFID隐私保护认证协议的构造是学术界和工业界研究的热点问题.具有完整性隐私保护协议的效率不够高效,需要对系统中所有的标签进行穷尽搜索,难以应用于物联网海量终端的环境.给出了一种高效的RFID隐私保护认证协议的构造方法.构造的协议采用了单比特输出的伪随机函数,将协议的认证过程分解为多个步骤,与传统的基于对称密码体系的RFID认证协议相比,构造的协议显著提高了读写器对标签的搜索效率.构造的协议具有隐私性,并且计算开销小,读写器端对标签的搜索效率高,能够很好地应用于海量终端的物联网环境.

    • 基于树状线性规划搜索的单调速率优化设计

      2015, 26(12):3223-3241. DOI: 10.13328/j.cnki.jos.004853

      摘要 (3435) HTML (138) PDF 1.95 M (3095) 评论 (0) 收藏

      摘要:改善单调速率(rate monotonic,简称RM)可调度性判定算法的效率,是过去40年计算机实时系统设计的重要问题.最近,研究人员把可调度性判定问题扩展到了更一般的优化设计问题,即,如何调节在区间可选择情况下的任务运行时间,使得:(1)系统RM可调度;(2)系统的某个性能(如CPU利用率)达到最优.在已有的求解实时系统RM优化设计问题的方法中,都是先把原问题建模成广义约束优化问题,然后再对广义约束优化问题进行求解.但现有方法的求解速度较慢,任务数较多时不再适用.提出一种求解优化问题的方法——基于树状的线性规划搜索(linearprogramming search,简称LPS)方法.该方法先将实时系统RM优化设计问题建模成广义约束优化问题,再将其分拆成若干线性规划子问题,然后构造线性规划搜索树,利用剪枝搜索算法求解部分线性规划子问题,最后得到优化解.实验结果表明:LPS方法相比于已有的方法能够节省20%~70%的求解时间,任务数越多,节省时间越多.该研究成果可以与计算机可满足性模定理(satisfiability modulo theories,简称SMT)领域的多个研究热点问题联系起来,并可望改善SMT问题的求解效率.

当期目录


文章目录

过刊浏览

年份

刊期

联系方式
  • 《软件学报 》
  • 主办单位:中国科学院软件研究所
                     中国计算机学会
  • 邮编: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号