Please wait a minute...
ISSN 1000-1239 CN 11-1777/TP

当期目录

2016年 第53卷 第3期    出版日期:2016-03-01
软件技术
一种软件演化活动波及效应混合分析方法
王炜,李彤,何云,李浩
2016, 53(3):  503-516.  doi:10.7544/issn1000-1239.2016.20140727
摘要 ( 612 )   HTML ( 0)   PDF (4136KB) ( 616 )  
相关文章 | 计量指标
确定演化活动潜在影响的过程称之为波及效应分析.波及效应分析已经被公认为影响软件演化项目成败的一个关键因素.针对当前波及效应分析准确率不高、各方法存在固有缺陷的问题,提出了一种混合波及效应分析方法,该方法将动态分析方法与文本分析方法相结合,在保持高召回率的基础上,基于演化软件领域知识降低了噪声对分析结果的不利影响,约简了分析范围,提高了查准率.为验证方法的有效性,对开源软件jEdit分别使用动态、静态、基于文本、基于历史演化知识和混合分析方法进行波及效应分析.通过比对实验结果,表明混合波及效应分析方法具有较好的综合性能.
基于软件节点重要性的集成测试序列生成方法
王莹,于海,朱志良
2016, 53(3):  517-530.  doi:10.7544/issn1000-1239.2016.20148318
摘要 ( 821 )   HTML ( 1)   PDF (3571KB) ( 680 )  
相关文章 | 计量指标
集成测试序列是软件集成测试的重要问题之一.不同的集成测试顺序对测试成本以及测试效率的影响很大.为降低测试成本,传统的类级集成测试顺序研究策略大多围绕如何减少构建测试桩数量和降低测试桩总体复杂度2个方面.若能将复杂程度高、出错概率大的类和发生错误后传播范围较大的类优先进行测试,不仅可以使得错误被尽早发现,还可以有效减小错误对系统的破坏性.为此,将上述思想应用到生成集成测试序列的算法当中,提出一种软件节点重要度的评估方法(Class-HITS).该方法利用复杂网络理论,将软件抽象为网络的形式,并结合所提出的重要度评估方法,打破软件网络中的环路,然后针对网络的无环链路逆向拓扑排序,最终得到类的集成测试序列.通过实验分析证明,利用该方法得出的集成测试序列既能够保证重要节点优先被测试,又确保了构造的测试桩的总复杂度较小.
一种基于图数据库的代码结构解析与搜索方法
林泽琦,赵俊峰,谢冰
2016, 53(3):  531-540.  doi:10.7544/issn1000-1239.2016.20148325
摘要 ( 714 )   HTML ( 5)   PDF (2121KB) ( 614 )  
相关文章 | 计量指标
软件复用是在软件开发中避免重复劳动的解决方案.在复用一个已有的软件项目时,软件开发人员通常需要理解某些代码元素以及其间的关联关系,称之为代码结构.软件开发人员一般通过浏览软件源代码的方式理解代码结构.由于源代码往往规模较大且结构复杂,理解代码结构通常会耗费大量的时间与精力.因此,将软件开发人员想要理解的代码结构自动、清晰地展示出来是很有帮助的.提出一种基于图数据库的代码结构解析与搜索方法以实现这一目的.这一方法可对软件的代码结构进行解析,并在图数据库中对其进行有效的组织和管理.搜索时,软件开发人员输入自然语言查询语句,该方法中的搜索机制会分析查询语句,并从图数据库中截取出与其相对应的代码结构进行展示.该方法具有高度的可扩展性:不同粒度的结点与多样化的关联关系可以容易地存储进图数据库中,且面向不同搜索目的的代码结构搜索算法亦可以容易地集成进搜索机制中.这一方法已在相应的工具中得到了实现,其有效性在一个商业案例研究中得到了验证.
基于输出域的测试用例自动生成方法研究
尤枫,赵瑞莲,吕珊珊
2016, 53(3):  541-549.  doi:10.7544/issn1000-1239.2016.20148045
摘要 ( 668 )   HTML ( 2)   PDF (2053KB) ( 429 )  
相关文章 | 计量指标
对大多数软件,很难根据规格说明自动产生期望的输出.而对于某些软件,输出域存在许多值得关注的检测点,适合于从输出域出发开发测试用例.但对于给定的输出,自动生成相应的输入也较为困难.提出了一种基于输出域的测试用例自动生成方法,首先利用BP神经网络构建被测软件的功能模型,然后在被测软件的功能模型上,对于给定的输出,利用遗传算法搜索相应的输入,实现基于输出域的测试用例自动生成.同时,对遗传算法进行了改进,提出了一种新的交叉算子和变异算子,以提高遗传算法生成测试用例效率,并在容错软件RSDIMU子模块和3个常用软件上进行了模型构建及测试生成实验.实验结果表明,利用遗传算法实现基于输出域的测试用例自动生成方法是行之有效的,改进的遗传算法能够提高测试生成的效率和成功率.
基于错误传播网络的回归测试用例排序方法
潘伟丰,李兵,周晓燕,何鹏
2016, 53(3):  550-558.  doi:10.7544/issn1000-1239.2016.20148329
摘要 ( 805 )   HTML ( 2)   PDF (1815KB) ( 625 )  
相关文章 | 计量指标
测试用例排序技术通过对测试用例进行排序以提高回归测试的效率.针对现有方法未能充分利用软件结构信息的不足,提出了基于错误传播网络的测试用例排序方法.该方法在类粒度将软件抽象成加权类依赖网络(weighted class dependency network,WCDN)模型,并基于WCDN分析错误在网络上的传播行为,构造错误传播网络(bug propagation network,BPN).测试用例排序时,首先在BPN中定位变更类和可能受变更类波及的类,从而计算类的测试重要性,最后以测试用例覆盖类的测试重要性总和作为最终的排序依据.实例研究表明,基于错误传播网络的测试用例排序方法在错误检出率上相比于其他经典方法有一定的提高,并且具有较好的稳定性.
大数据环境下高维数据的快速重复检测方法
朱蔚恒,印鉴,邓玉辉,龙舜,邱诗定
2016, 53(3):  559-570.  doi:10.7544/issn1000-1239.2016.20148218
摘要 ( 870 )   HTML ( 3)   PDF (3819KB) ( 765 )  
相关文章 | 计量指标
大数据时代多源、异构、海量的数据正逐渐成为各种应用的主流.多源异构不可避免地会使数据出现重复,同时庞大的数据量对重复检测的效率提出了极高的要求,传统技术在大数据环境下并不能很好地对高维数据进行重复检测,就此问题展开研究,分析了传统SNM类方法的不足,将重复问题概化为一类特殊的聚类问题,利用R-树建立了高效的索引,利用聚类簇的特性减少了在R-树叶子中比较的次数,利用重复检测的Apriori性质实现了对高维数据集并行处理.实验结果表明,提出的算法能有效地提高高维数据的重复检测效率.
基于压缩的海量不完整数据近似查询方法
王妍,刘赓浩,王俊陆,宋宝燕
2016, 53(3):  571-581.  doi:10.7544/issn1000-1239.2016.20150620
摘要 ( 634 )   HTML ( 2)   PDF (2253KB) ( 404 )  
相关文章 | 计量指标
随着数据的爆炸式增加,不完整数据普遍存在,传统的数据修复方法对于海量数据处理代价过高,且不能彻底修复,在这些不完整的海量数据上进行满足给定需求的近似查询引起了学术界的关注.因此,提出一种基于压缩的海量不完整数据近似查询方法,该方法对属性值缺失字段进行标记,根据频繁查询条件对标记后的数据进行压缩,并建立对应索引;根据属性划分对索引文件再次压缩以节省存储空间,采用编码字典对索引压缩文件进行选择和投影操作,最终获得不完整数据的近似查询结果.实验表明,该方法能够快速定位不完整数据的压缩位置,提高了查询效率,节省了存储空间,并且保证了查询结果的完整性.
人工智能
知识图谱构建技术综述
刘峤,李杨,段宏,刘瑶,秦志光
2016, 53(3):  582-600.  doi:10.7544/issn1000-1239.2016.20148228
摘要 ( 9502 )   HTML ( 208)   PDF (2414KB) ( 15844 )  
相关文章 | 计量指标
谷歌知识图谱技术近年来引起了广泛关注,由于公开披露的技术资料较少,使人一时难以看清该技术的内涵和价值.从知识图谱的定义和技术架构出发,对构建知识图谱涉及的关键技术进行了自底向上的全面解析.1)对知识图谱的定义和内涵进行了说明,并给出了构建知识图谱的技术框架,按照输入的知识素材的抽象程度将其划分为3个层次:信息抽取层、知识融合层和知识加工层;2)分别对每个层次涉及的关键技术的研究现状进行分类说明,逐步揭示知识图谱技术的奥秘,及其与相关学科领域的关系;3)对知识图谱构建技术当前面临的重大挑战和关键问题进行了总结.
社会网络中影响力传播的鲁棒抑制方法
李劲,岳昆,张德海,刘惟一
2016, 53(3):  601-610.  doi:10.7544/issn1000-1239.2016.20148341
摘要 ( 1027 )   HTML ( 2)   PDF (2408KB) ( 693 )  
相关文章 | 计量指标
社会网络中影响力传播的有效抑制是当前社会网络影响力传播机制研究关注的问题之一.针对不确定性、策略性负影响源的影响力传播抑制,讨论社会网络中影响力传播的鲁棒抑制问题.首先,作为提高算法运行效率的有效途径,讨论在竞争性线性阈值传播模型下,负种子集传播能力的近似估计方法,以此为基础,提出不确定性负影响源情况下,期望抑制效果最大化的抑制种子集挖掘算法.然后,对于策略性传播源,以最小化最坏情况下的影响力传播范围为目标,基于极小极大优化作为抑制决策准则,提出了一个随机抑制策略的多项式时间近似求解算法.最后,在真实的社会网络数据集上,通过实验验证了所提出方法的有效性.
面向网络舆情数据的异常行为识别
郝亚洲,郑庆华,陈艳平,闫彩霞
2016, 53(3):  611-620.  doi:10.7544/issn1000-1239.2016.20150746
摘要 ( 1043 )   HTML ( 6)   PDF (2681KB) ( 1152 )  
相关文章 | 计量指标
社交网络的日益普及和移动设备快捷的网络接入,使得网络舆情的传播十分迅捷,民众对热点话题的关注度和参与度得到很大的提升.网络舆情具有自由性、交互性、多元性、偏差性、突发性等特点,能够左右民众的情感和判断,能推动和改变事件的发展和走向,容易被反对分子利用,已经成为影响社会稳定的重要因素.因此,及时检测、控制并引导舆情的发展具有十分重要的意义.研究关注网络中传播的蕴含有“破坏”、“危险”、“损失”等涉及公共安全或涉及司法公正的行为.根据课题的需要,定义4种关注的异常行为类型:攻击行为、受伤行为、死亡行为、拘捕行为.从数据挖掘和信息抽取的角度研究识别异常行为的方法,首先通过分类器和触发词从海量的数据中过滤出包含异常行为的句子,然后抽取异常行为句中包含的命名实体,最后利用抽取的实体构建异常行为共现网络,为分析人员提供可视化的网络舆情分析方法.
基于三轴加速度传感器的人体运动识别
李锋,潘敬奎
2016, 53(3):  621-631.  doi:10.7544/issn1000-1239.2016.20148159
摘要 ( 1136 )   HTML ( 0)   PDF (3896KB) ( 2013 )  
相关文章 | 计量指标
提出并实现一种基于移动设备的用户运动行为的检测算法.在用户随身携带移动设备的情况下,算法就可以根据移动设备中的三轴加速度数据,判别出来用户的行为状态.算法综合分析了加速度传感器数据的时域和频域特性,并通过方向无关性和步幅处理,进一步提高算法的适应性.算法对所抽取21个运动特征值进行了主成分分析,找出了11个主要特征成分,然后使用这些主成分对运行数据进行识别分类.提高了算法准确度,并降低了算法的时间和空间复杂度.在对分类算法综合分析和比较后,J48判决树算法被采纳.算法还根据人类运动的习惯和特性,对特性分类并计算分类的结果,再采用隐式Markov模型进行处理,进一步提高识别的准确度.对多人、多状态数据的实验表明,这种综合方法具有较高的识别准确度和适应性,在对多人多次实际运动数据的处理中,正确识别率可以达到96.13%.
基于迁移共享空间的分类新算法
董爱美,毕安琪,王士同
2016, 53(3):  632-643.  doi:10.7544/issn1000-1239.2016.20148263
摘要 ( 761 )   HTML ( 2)   PDF (3119KB) ( 428 )  
相关文章 | 计量指标
为解决来自不同但相关领域的大量无标签数据和少量带标签数据的分类问题,首先构造一个联系源域到目标域的共享特征空间,并将该空间引入经典的支持向量机算法使其获得迁移能力,最终得到一种新的基于支持向量机的迁移共享空间的分类新算法,即迁移共享空间支持向量机.具体地,该方法以迁移学习理论为基础,结合分类器最大间隔原理,通过最大化无标签数据和带标签数据的联合概率分布来构建无标签数据和带标签数据的共享空间;为充分考虑少量带标签数据之数据分布,在其原始特征空间和共享空间组成的扩展空间中训练分类模型.相关实验结果验证了该迁移学习分类器的有效性.
PQ-树断点距离中心问题的复杂性和精确算法
刘培霞,姜海涛,朱大铭
2016, 53(3):  644-650.  doi:10.7544/issn1000-1239.2016.20148258
摘要 ( 995 )   HTML ( 0)   PDF (1137KB) ( 422 )  
相关文章 | 计量指标
PQ-树是一种树状数据结构,用来表示元素排列集合.虽然消逝物种完整基因组序列具有不确定性,但是根据同源物种可以确定部分基因的相对位置,所以可以利用PQ-树来存储消逝物种的基因组.在生物学中,进化树用来表示物种之间的进化关系.当构建生物进化树时,叶子结点表示现存物种,其基因组用排列表示;内部结点为祖先物种,其基因组用PQ-树表示.为了确定物种间的进化关系,需要确定PQ-树可以产生的排列与已知排列之间的距离.以断点距离为标准,研究了p-PQ-树断点中心问题,即从给定PQ-树中产生一个排列,使之与给定的p个排列的断点距离之和最小.证明当p≥2时,p-PQ-树断点中心问题是NP-完全的.当p=1时,p-PQ-树断点中心问题是参数化可计算的,针对1-PQ-树断点中心问题,提出了时间复杂度为O(3\+Kn)的参数化算法,其中K为最优解的断点距离.
信息安全
基于四元数指数矩的鲁棒彩色图像水印算法
王向阳,杨红颖,牛盼盼,王春鹏
2016, 53(3):  651-665.  doi:10.7544/issn1000-1239.2016.20148177
摘要 ( 761 )   HTML ( 1)   PDF (6227KB) ( 696 )  
相关文章 | 计量指标
近年来,抗几何攻击数字图像水印方法研究取得了很大进展,但现有绝大多数图像水印嵌入算法都是针对灰度图像的,直接用于彩色载体图像的数字水印算法较少.即使原始载体是彩色图像,大部分方法也只是通过提取其亮度信息或使用单色通道信息嵌入数字水印.也就说,现有算法未能很好体现和保留不同色彩分量在整个颜色空间内的特定联系,因而必然影响数字水印的鲁棒性和不可感知性.以四元数与指数矩理论为基础,提出了一种基于四元数指数矩的抗几何攻击彩色图像水印算法.1)把传统灰度图像的指数矩理论推广到四元数层面,并定义出彩色图像的四元数指数矩;2)对四元数指数矩的不变特性进行推导与分析;3)构造出基于四元数指数矩的抗几何攻击彩色图像水印方案.仿真实验表明,该算法不仅具有较好的不可感知性,而且对常规信号处理和几何攻击均具有较好的鲁棒性.
对8轮mCrypton-96的中间相遇攻击
王高丽,甘楠
2016, 53(3):  666-673.  doi:10.7544/issn1000-1239.2016.20148270
摘要 ( 595 )   HTML ( 1)   PDF (2009KB) ( 539 )  
相关文章 | 计量指标
在分析分组密码算法的安全性时,利用密钥关系来降低时间、存储和数据复杂度是一个常用的手段.在4轮mCrypton-96性质的基础上,利用密钥生成算法的弱点和S盒的性质,降低了攻击过程中需要猜测的密钥比特数,提出了对8轮mCrypton-96算法的中间相遇攻击,攻击的时间复杂度约为2\+{93.5}次8轮mCrypton-96加密运算,存储复杂度为2\+{47}B,数据复杂度为2\+{57}个选择明文.
一种基于变参级联混沌的Hash函数算法
吴涛,金建国,魏明军
2016, 53(3):  674-681.  doi:10.7544/issn1000-1239.2016.20148155
摘要 ( 614 )   HTML ( 1)   PDF (1369KB) ( 588 )  
相关文章 | 计量指标
针对级联混沌可能存在的密钥泄漏风险以及当前Hash函数的不足,提出了一种基于变参级联混沌的Hash函数算法,即在构成Hash函数的级联驱动系统中,引入了另一混沌系统的状态变量作为参数扰动,并在扰动强度的控制下实现安全的变参级联系统.由此构成的Hash函数不仅具有符合混沌规律的变参特性,同时还具有级联子系统间逐级串扰的性质,能有效降低由计算机有限精度和数字量化可能造成的短周期行为风险,对提高压缩函数内部结构的复杂度和抗碰撞性有着显著意义.实验结果表明:与其他混沌Hash算法和SHA-3算法相比,该算法具有高度的初值敏感性和良好的混乱与扩散性能,抗碰撞能力强,算法实现简单灵活,变参系统可控性强,在混沌保密通信、数字签名等领域具有良好的推广前景.
系统结构
冗余及监控混合策略的优化配置算法研究
何盼,谭春,袁月,吴开贵
2016, 53(3):  682-696.  doi:10.7544/issn1000-1239.2016.20148204
摘要 ( 622 )   HTML ( 0)   PDF (5223KB) ( 503 )  
相关文章 | 计量指标
大数据环境中监控和冗余混合策略的采用引起资源优化配置模型的状态空间膨胀,进化搜索算法在整型与非整型变量结合的解空间中的搜索效率有待提高,为此提出了基于搜索邻域分析的三元组模因算法.在分析了监控频率等参数变化对组件及系统可靠性增长影响的基础上,针对监控频率提出了基于变长邻域的近邻生成方法,针对策略选项提出了与组件关联的近邻生成方法.采用模因算法框架并改进了局部搜索算子,通过组件间的迭代搜索在保持个体优势的同时增大搜索范围.该算法能够用于求解混合策略下的组件保障措施选项及相应优化配置参数;与现有多策略搜索算法相比,在相同可靠性约束下,该算法能够得到消耗更低的资源配置结果;局部搜索策略对算法稳定性未造成明显影响.
一种通用云计算资源调度问题的快速近似算法
魏蔚,刘扬,杨卫东
2016, 53(3):  697-703.  doi:10.7544/issn1000-1239.2016.20148323
摘要 ( 730 )   HTML ( 2)   PDF (1471KB) ( 570 )  
相关文章 | 计量指标
在分布式云计算平台中,面向大规模用户的在线应用需处理针对海量资源的用户需求,在给定的资源预算下,服务提供商需确定最优资源放置位置,以最大程度地满足用户需求,通常需求用给定时间段内均值表示.然而真实场景中用户需求是高度动态和随机的,采用随机需求模型以考虑更多需求细节,资源利用率可得到进一步优化.但相比均值调度方法,随机需求模型会导致很高的计算复杂度.已有的最优解求解算法的时间复杂度和资源总量成正比,无法满足海量资源在线调度的效率要求.基于非线性规划理论,提出了一个快速资源分配算法,该算法可将计算复杂度降低至最优解算法的1‰,并逼近最优解效果的99%,因此可用于在线应用场景中海量资源的高效调度.
其他应用技术
基于可穿戴设备感知的智能家居能源优化
陈思运,刘烃,沈超,苏曼,高峰,徐占伯,师嘉悦,贾战培
2016, 53(3):  704-715.  doi:10.7544/issn1000-1239.2016.20150762
摘要 ( 994 )   HTML ( 7)   PDF (3500KB) ( 572 )  
相关文章 | 计量指标
智能家居能源优化作为智能电网在居民侧的延伸是智能家居领域的重要分支.智能家居能源优化的目标是通过优化调度家居用电设备,满足用户的舒适需求和降低用电费用.其中,用户舒适度与人的行为密切相关,具有很强的主观性和不确定性,对用户行为及舒适度需求的分析是智能家居能源管理系统中的难点.因此提出了一种基于可穿戴设备传感数据分析的智能家居能源优化方法,主要包括:基于可穿戴设备传感器数据实时分析用户行为;利用神经网络建立用户行为到舒适度需求的映射,更新用户的舒适度需求;建立家居系统动态模型,并基于智能家居环境传感器数据对模型参数进行动态估计;提出基于模型预测控制(model predictive control, MPC)的智能家居能源优化求解方法.同时开发了智能家居能源优化的原型系统,通过搭建的智能家居实验平台,设计了4种典型用户行为情景,验证了所提方法对智能家居经济性和舒适性的提升.
5种基本情绪的心肺系统生理反应模式
刘烨,王思睿,傅小兰
2016, 53(3):  716-725.  doi:10.7544/issn1000-1239.2016.20140743
摘要 ( 1046 )   HTML ( 9)   PDF (1060KB) ( 839 )  
相关文章 | 计量指标
情感交互是自然人机交互发展的必然趋势.生理计算为感知和识别用户的生理和情感状态提供了新的途径. 通过阅读文字情境,14名被试分别体验悲伤、喜悦、惊奇、恐惧、愤怒5种基本情绪和中性情绪,并以相应的情绪语调说出与情境有关的特定话语,考察了人们在上述5种基本情绪下的自主神经系统生理反应.使用BIOPAC MP150生理仪和可穿戴式感受器终端记录被试在言语过程中的心电和呼吸数据,并据此分析12项心肺活动指标.结果表明:除悲伤外,其他4种基本情绪下的生理反应与中性情绪存在显著或边缘显著差异;5种情绪所引发的生理反应模式在一定程度上存在差异.该研究表明,基本情绪所引发的心肺系统反应模式存在差异,为基于用户的生理反应模式对用户的情感状态进行识别提供了实验支持证据,通过捕捉心电和呼吸信号可以有效地监测用户的情感状态.