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

当期目录

2013年 第50卷 第4期    出版日期:2013-04-15
论文
调试中基于文法编码的日志异常检测算法
王 楠, 韩冀中, 方金云,
2013, 50(4):  677-685. 
摘要 ( 663 )   HTML ( 0)   PDF (2255KB) ( 660 )  
相关文章 | 计量指标
调试软件中的非确定错误对软件开发有重要意义.近年来,随着云计算系统的快速发展和对录制重放调试方法研究的深入,使用异常检测方法从大量文本日志或控制流日志等数据中找出异常的信息对调试愈发重要.传统的异常检测算法大多是为检测和防范攻击而设计的,它们很多基于马尔可夫假设,对事件流上的剧烈变化很敏感.但是新的问题要求异常检测能够检出语义级别的异常行为.实验表明现有的基于马尔可夫假设的异常检测算法在这方面表现不佳.提出了一种新的基于文法编码的异常检测算法.该算法不依赖于统计模型、概率模型、机器学习及马尔可夫假设,设计和实现都极为简单.实验表明在检测高层次的语义异常方面,该算法比传统方法有优势.
一种基于Kolmogorov-Smirnov检验的缺陷定位方法
叶 钢 余 丹 李重文 李先军 尹 杰 吕江花 马世龙
2013, 50(4):  686-699. 
摘要 ( 669 )   HTML ( 1)   PDF (4658KB) ( 460 )  
相关文章 | 计量指标
现有的基于中心极限定理和参数假设检验的方法被认为是一种高效的缺陷定位技术.然而,实验结果表明,在某些实验数据集上,测试用例的总数过小而不宜运用中心极限定理.实验结果同时表明,谓词的实际分布背离了基于参数假设检验的方法所假设的正态分布.基于以上发现,提出了一种基于Kolmogorov-Smirnov检验的缺陷定位方法.在西门子测试集和大型程序上的实验结果表明:该方法在小样本和非正态分布的样本集上具有较好的适用性.若谓词在某个测试用例执行时未被执行,已有的方法将该执行中此谓词的评估偏差值设为0.5.在西门子程序集上调查了该设置的有效性,实验结果表明:对于基于Kolmogorov-Smirnov检验的缺陷定位方法,该设置可以提高缺陷定位的效率.
一种基于微分代数动态逻辑的CPS建模与验证方法
陈乔乔 李必信 吉顺慧
2013, 50(4):  700-710. 
摘要 ( 515 )   HTML ( 0)   PDF (1769KB) ( 810 )  
相关文章 | 计量指标
随着CPS在工业控制、智能交通、智能医疗等领域的广泛应用,安全性已成为目前CPS理论和应用研究的核心问题.提出了一种基于微分代数动态逻辑的CPS安全性验证方法,该方法首先把HybridUML模型转换成微分代数程序, 然后使用微分代数动态逻辑对系统安全性进行规约,最后依据微分代数动态逻辑推理规则对CPS进行安全性验证.通过对飞机空中避撞系统的实例研究,表明该方法能够有效地验证避撞策略的正确性,从而保证避撞系统的安全性.
Frame精化:基于Frame的软件开发与逐步精化的融合
周进刚, 赵大哲, 许 力, 刘积仁,
2013, 50(4):  711-721. 
摘要 ( 422 )   HTML ( 0)   PDF (2029KB) ( 421 )  
相关文章 | 计量指标
基于Frame的软件开发和逐步精化是用于实现系统化软件开发(例如软件产品线)的两种范型.然而这两种方法基于不同的假设而独立发展,它们之间的联系还未得到完全认识.为了弥补这一缺失,使得能够在一个统一的软件开发过程中发挥这两者的优势,探讨了它们之间的联系、融合的必要性以及在融和过程中出现的有趣的问题,像可换合成策略和不同范型指令的融合等.为了支持这一观点,在frames的设计中集成了逐步精化技术,并设计开发了Frame++.它构建在XVCL之上,利用AHEAD(XAK)来支持frames精化.在frames中融入逐步精化的概念,使得可以按特征对frames进行组织(同时兼顾消除克隆),易于frames的演化和面向特征的复用与组装;同时精化的参数化特性使得处理细粒度的可变性特征变得容易.一个人员维护模块的产品线被用来展示这种方法.此方法可以提升frames设计中的关注点分离,并促进系统化的软件开发.
一种高效的网络流记录表示方法
张广兴, 邱 峰, 谢高岗, 童红霞,
2013, 50(4):  722-730. 
摘要 ( 791 )   HTML ( 1)   PDF (1924KB) ( 541 )  
相关文章 | 计量指标
带宽和应用不断发展,迫切需要对应用业务的精细化网络流量进行持续监测.NetFlow的表示方法存在数据组织效率低等问题,导致传输开销过大、历史数据存储空间爆炸增长;聚合NetFlow表示方法又带来大量信息丢失.寻找一种高效的网络流记录表示方法对满足网络测量有着非常重要的意义.提出了一种新的方法——基于对象和应用的流量特征统计描述(TABSI),该方法以单位时间周期内各个监测对象在不同应用下的流量统计、流数目统计及分布为流量信息的基本描述单位,周期性地导出该信息来描述链路流量特征.理论分析表明TABSI比聚合NetFlow记录包含更多的信息量,能够很好地描述网络行为;且TABSI历史数据有效性更强.现网运行测试表明该方法可使传输数据量减少、存储组织高效查询分析更快、存储空间大大减少.
一种高效率的大流提取方法
王风宇, 郭山清, 李亮雄, 云晓春,
2013, 50(4):  731-740. 
摘要 ( 442 )   HTML ( 0)   PDF (2078KB) ( 556 )  
相关文章 | 计量指标
随着网络带宽的不断提高,在线识别大流对于拥塞控制、异常检测等网络应用具有重要意义.提出了一种提取大流的算法FEFS(flow extracting with frequency & size),能够通过在线识别和淘汰小流,把大流信息保存在有限的高速存储空间中,从而快速提取大流.该算法利用LRU(least recently used)定位更新频率低的流,并进一步用流尺寸因子s和自适应调节因子M标记其中相对较小的流,最后用新到达的流将其替换.FEFS把LRU策略和尺寸因子s相结合,同时考虑了流的近期更新频率和累积报文数量,因此能够准确在线识别大流.LRU策略和尺寸因子都利用了流大小的重尾分布特征,因此FEFS能以很低的存储代价保存和更新大流信息.模拟实验表明,在限定存储条件下,FEFS的平均相对误差率明显低于经典的multi-stage filter 算法,而平均报文处理时间也短于multi-stage filter 算法.
网络度相关及其传播特征研究
葛 新, 赵 海, 张 君,
2013, 50(4):  741-749. 
摘要 ( 538 )   HTML ( 1)   PDF (3876KB) ( 533 )  
相关文章 | 计量指标
现实世界网络的连接具有多种相关性,其对网络拓扑结构、动态行为特征等都有重要影响.针对网络中节点之间的度值相关性,提出一种基于给定网络或度序列构造具有极大和极小连续匹配系数网络的方法——最大加权覆盖,并利用匹配系数分析了网络结构与度相关性之间的关系.在此基础上,基于连续匹配系数网络,通过仿真及理论推导研究了度相关特征对病毒传播速度、传播阈值和稳态感染率的影响.发现异配网络会加速病毒的传播,而传播速度对同配网络具有更高的敏感性.此外,从免疫策略角度的研究表明,以大度值为目标的免疫策略对异配网络具有更好的免疫效果,而在实际病毒防御中,应该根据有效传播率、匹配系数、免疫目标等综合考虑.
多接口车载自组织网络频谱分配算法研究
彭 鑫, 王 东, 李仁发, 曾凡仔, 付 彬,
2013, 50(4):  750-757. 
摘要 ( 445 )   HTML ( 0)   PDF (2281KB) ( 399 )  
相关文章 | 计量指标
如何提升链路的并行传输能力是车载自组网面临的重要问题.如果在车辆上装配多个无线接口,并且分别调制到不同的正交信道可以有效增强链路的并行传输能力,从而提升网络吞吐率.针对拓扑变化对多接口车载自组网动态频谱分配带来的影响,提出了一种多接口车载自组网动态频谱分配算法.算法根据车辆的运动速度进行分簇,然后在簇头间通信中采用离线频谱分配策略,从而避免了网络的拓扑变化对频谱分配造成的影响.而簇内车辆具有相同的运动速度,所以具有稳定的簇内拓扑结构,有利于频谱分配算法的应用.仿真分析表明,提出的算法适用于多接口车载自组网,在动态拓扑环境下表现出了良好的性能.
一种空间延迟容忍网络中的周期性链路数据转发算法
杜学绘 王亚弟 陈性元 王 振
2013, 50(4):  758-766. 
摘要 ( 544 )   HTML ( 1)   PDF (2149KB) ( 554 )  
相关文章 | 计量指标
空间延迟容忍网络的链路具有间歇连通的特点,难以形成一条端到端的路径,使得基于TCP/IP的端端数据传输机制无法适应空间延迟容忍网络.空间延迟网络中存在着大量连通时间短暂、具有周期性连通规律的卫星节点,它们处于高速周期性运动中,在空对地、空空之间构建了空间网络的核心链路.针对空间延迟容忍网络中的周期性连通链路,通过对卫星运行规律的分析,计算单颗卫星对地周期性连通时间和星间链路的连通时间,定义空间链路的连通矢量,设计基于节点间连通矢量的数据转发算法,有效解决了空间网络周期性链路的数据有效转发问题,为空间网络面向延迟容忍的数据转发提供支持.仿真结果表明,该算法在周期性链路的情况下具有较好的传递成功率和传输延迟性能,更适合于具有周期性链路的空间延迟容忍网络环境.
一种利用人脸对称性的光照归一化方法
韩 琥, 山世光, 陈熙霖, 高 文,
2013, 50(4):  767-775. 
摘要 ( 753 )   HTML ( 2)   PDF (1999KB) ( 656 )  
相关文章 | 计量指标
光照归一化在光照鲁棒的人脸识别中被广泛使用.许多现有光照归一化方法将人脸图像视为自然图像,而忽略了人脸这一类特定物体的先验属性,因此很难从一幅具有侧光的人脸图像中恢复阴影区域中的人脸信息.提出了利用人脸对称性先验的光照归一化方法,在能量最小化框架下,对人脸图像的阴影区域进行光照归一化时参考其对称非阴影区域中的人脸结构信息,同时提出了无阴影信度图将二元最优化问题简化为一元最优化问题,以降低光照归一化方法的计算代价.在合成阴影和真实阴影人脸图像上的实验表明,利用人脸对称性的光照归一化方法能有效恢复图像阴影区域中的人脸特征,并对人脸误配准和非对称几何归一化具有一定的鲁棒性.
结合低位深像素预测起点的小波域运动估计
宋传鸣, 谭 茹, 王相海, 刘 丹,
2013, 50(4):  776-786. 
摘要 ( 369 )   HTML ( 0)   PDF (2467KB) ( 380 )  
相关文章 | 计量指标
提出一种用2 b深度的像素预测搜索起点的快速小波域运动估计算法.首先,将像素深度的转换形式化为区间分划和区间映射,采用非均匀量化求解区间分划的初始阈值,再用隶属函数计算量化阈值并完成区间映射,从而获得位深度为2 b的视频表示;其次,设计了非均匀的搜索起点分布模板,并以此为基础提出一种基于2 b深度像素的搜索起点预测算法;最后,以搜索起点为中心,进一步采用改进的低频子带平移运动估计算法MLBSSME在较小的窗口内完成搜索.实验结果表明,对于具有不同场景特点的视频序列,算法始终能保持较高的估计精度,运动补偿的平均峰值信噪比较之低频子带平移运动估计和直接子带运动估计算法高0.41 dB和1.43 dB,比空间域全搜索降低0.07 dB.但是,算法的计算量仅相当于空间域全搜索的4.66%、低频子带平移运动估计的4.62%、子带直接运动估计的22.70%.
实际且快速的图像对比度增强方法
谢文达 邱竣鸿 王 垒
2013, 50(4):  787-799. 
摘要 ( 1428 )   HTML ( 5)   PDF (3821KB) ( 709 )  
相关文章 | 计量指标
根据以前有关图像对比度增强技术的研发成果加以修正改进,提出一种实际且快速的图像对比度增强方法(practical and efficient contrast enhancement method, PECE),此方法不仅可使增强后的清晰图像更趋近于原始图像的亮度,更能简化实际电路让用户易于操作调整.通过现场可编程逻辑门阵列(fieldprogrammable gate array, FPGA)的硬件实现验证,可发现此硬件电路可达到43.6 MSps(million sample per second),其处理速度为常规清晰度电视(standard definition television, SDTV)NTSC 720×480i规格的3.23倍及增强清晰度电视(enhanced digital television, EDTV) NTSC 720×480p规格的1.61倍.为了能更客观公正地观察PECE及各种图像对比度增强技术的效果及优缺点,综合了各种主客观评量标准,藉由对多种不同技术的全面化评估分析,各种技术的许多效能特色及优劣也在此一评估程序中显现.
抗裁剪和平移攻击的图像拷贝检测算法
张志杰 沈 田 邹建华
2013, 50(4):  800-807. 
摘要 ( 484 )   HTML ( 0)   PDF (2744KB) ( 398 )  
相关文章 | 计量指标
有效判定经拷贝攻击之后图像的版权归属是当今图像拷贝检测研究的热点和难点之一. 现有的检测算法对于噪声、拉伸、旋转、等比缩放等常见攻击具有较好的鲁棒性, 而对于裁剪、平移攻击则比较脆弱. 针对上述问题, 提出一种基于SIFT局部特征和整体DCT系数顺序测度的图像拷贝检测算法. 该算法首先通过匹配的SIFT特征划定内容保持不变的区域, 然后对内容不变区域的亮度分量作整体DCT变换, 并将DCT系数低频交流成分的顺序测度作为图像特征, 最后通过该特征判定拷贝是否存在. 由于匹配的SIFT特征可以精确定位拷贝发生区域, 因而对裁剪、平移攻击具有较好的抵抗能力, 又由于引入整体DCT系数顺序测度作为特征, 因而可以很好地抵抗其他常见攻击. 同时提出翻转补偿策略, 使本算法能抵抗水平翻转和垂直翻转攻击. 实验结果证明, 在抵抗裁剪和平移攻击方面, 给出的算法相对于已有算法具有较高的查准率和查全率.
基于正弦高斯调制和样条插值的CTF校正模型
王功明, 张 法, 樊莉亚, 孙 飞, 刘志勇,
2013, 50(4):  808-814. 
摘要 ( 723 )   HTML ( 1)   PDF (2275KB) ( 470 )  
相关文章 | 计量指标
在基于冷冻电镜的单颗粒三维重构过程中,衬度传递函数(contrast transfer function,CTF)校正是获取高分辨分子结构的关键操作.但传统CTF校正模型存在低频、高频阶段校正值过小、插值方法过于简单等问题,从而降低了重构精度.针对这两个问题,提出了一种新的CTF校正模型.首先,在CTF曲线的低频、高频阶段分别进行正弦和高斯调制,改善了CTF曲线的形态;然后,采用3次样条插值计算非整数傅里叶半径处的CTF值,提高了数据获取的精度,进而提高了重构结果的分辨率.对HBV分子图像进行重构实验,结果表明,使用本模型可以得到更清晰的结构特征,其重构结果分辨率为7.8,高于传统CTF校正重构结果的分辨率8.06.
基于局部特征的自适应快速图像分割模型
葛 琦, 韦志辉, 肖 亮, 张 军,
2013, 50(4):  815-822. 
摘要 ( 421 )   HTML ( 1)   PDF (2367KB) ( 414 )  
相关文章 | 计量指标
基于区域的活动轮廓模型如Chan-Vese(CV)模型等以其能较好的处理图像的模糊边界和复杂拓扑结构而广泛运用于图像分割中.然而基于灰度分布均匀假设,该模型对于含灰度不一致性的目标分割结果较差.此外,纹理是周期性重复出现的细节,依靠灰度信息无法正确检测.针对这些问题,提出一种基于局部特征的自适应快速图像分割模型.一方面,利用两种区域项检测卡通部分和纹理部分的特征信息,在自适应的局部块中提取局部统计信息以克服卡通部分的灰度不一致性;另一方面,利用自适应的局部块中的纹理特征来计算背景和目标区域的Kullback-Leibler(KL)距离以检测图像的纹理部分.进一步,基于分裂Bregman方法对该模型进行快速求解.分别对医学和纹理图像进行了实验,准确性和时效性都有显著提高.
一种中心反射折射直线像的拟合方法
段慧仙 李光耀
2013, 50(4):  823-833. 
摘要 ( 354 )   HTML ( 0)   PDF (4887KB) ( 340 )  
相关文章 | 计量指标
直线在中心反射折射摄像机下的像是一条二次曲线.由于存在遮挡,准确地拟合直线像是非常困难的,从而影响了摄像机的标定精度.目前,这一问题仍然没有得到有效的解决.此外,根据中心反射折射摄像机成像模型发现,如果可见弧上图像点的对极点已知,可以大大提高直线像的拟合精度.为此,提出了一种新的拟合直线像的方法,该方法适用于包括抛物反射折射摄像机在内的所有中心反射折射摄像机.首先,推导出一种新的关于对极图像点与摄像机主点之间的关系;然后,通过这种关系建立目标函数,用来优化得到直线像的方程;最后,利用拟合的直线像估计摄像机的内参数,以此评价拟合算法的性能.大量模拟实验和真实实验均验证了拟合算法的有效性,即提出的拟合算法不仅鲁棒,且提高了直线像的拟合精度,进而提高了摄像机的标定精度.
面向中文自然语言文档的自动知识抽取方法
车海燕 冯 铁 张家晨 陈 伟 李大利
2013, 50(4):  834-842. 
摘要 ( 963 )   HTML ( 3)   PDF (1213KB) ( 946 )  
相关文章 | 计量指标
自动知识抽取方法可以自动识别并抽取Web文档中与本体匹配的事实知识。利用这些事实知识既可以构建基于知识的服务,也能够为语义Web的实现提供必要的语义数据。但面向自然语言特别是中文自然语言的自动知识抽取非常困难.提出了基于语义Web理论和中文自然语言处理(natural language processing, NLP)技术的自动知识抽取新方法AKE,用聚集体知识概念刻画N元关系知识,能够在不使用大规模语言知识库和同义词表的情况下自动识别中文自然语言文档内容中显式和隐含的简单事实知识和N元关系复杂事实知识.实验结果表明该方法优于目前已知的其他方法.
一种基于智能调度的可扩展并行强化学习方法
刘 全, 傅启明, 杨旭东, 荆 玲, 李 瑾, 李 娇,
2013, 50(4):  843-851. 
摘要 ( 768 )   HTML ( 1)   PDF (2083KB) ( 571 )  
相关文章 | 计量指标
针对强化学习在大状态空间或连续状态空间中存在的“维数灾”问题,提出一种基于智能调度的可扩展并行强化学习方法——IS-SRL,并从理论上进行分析,证明其收敛性.该方法采用分而治之策略对大状态空间进行分块,使得每个分块能够调入内存独立学习.在每个分块学习了一个周期之后交换到外存上,调入下一个分块继续学习.分块之间在换入换出的过程中交换信息,以使整个学习任务收敛到最优解.同时针对各分块之间的学习顺序会显著影响学习效率的问题,提出了一种新颖的智能调度算法,该算法利用强化学习值函数更新顺序的分布特点,基于多种调度策略加权优先级的思想,把学习集中在能产生最大效益的子问题空间,保障了IS-SRL方法的学习效率.在上述调度算法中融入并行调度框架,利用多Agent同时学习,得到了IS-SRL方法的并行版本——IS-SPRL方法.实验结果表明,IS-SPRL方法具有较快的收敛速度和较好的扩展性能.
基于最小且非重叠发生的频繁闭情节挖掘
朱辉生, 汪 卫, 施伯乐,
2013, 50(4):  852-860. 
摘要 ( 621 )   HTML ( 3)   PDF (3277KB) ( 434 )  
相关文章 | 计量指标
事件序列上的频繁闭情节挖掘是一个重要课题,现有的研究基于最小发生的支持度定义和广度优先的搜索策略,不可避免地导致了情节发生的“过计数”和大量候选情节的产生问题,因此,基于最小且非重叠发生的支持度定义和深度优先的搜索策略,提出了一个事件序列上的频繁闭情节挖掘算法FCEMiner,在此基础上,利用特殊前向扩展的非闭一致性避免了冗余的闭合性检查,缩小了频繁闭情节的搜索空间.理论分析和实验评估证明FCEMiner能够有效地发现事件序列上的频繁闭情节.
通用集成学习算法的构造
付忠良
2013, 50(4):  861-872. 
摘要 ( 668 )   HTML ( 1)   PDF (1198KB) ( 497 )  
相关文章 | 计量指标
集成学习算法的构造属于机器学习领域的重要研究内容,尽管弱学习定理指出了弱学习算法与强学习算法是等价的,但如何构造好的集成学习算法仍然是一个未得到很好解决的问题.Freund和Schapire提出的AdaBoost算法和Schapire和Singer提出的连续AdaBoost算法部分解决了该问题.提出了一种学习错误定义,以这种学习错误最小化为目标,提出了一种通用的集成学习算法,算法可以解决目前绝大多数分类需求的学习问题,如多分类、代价敏感分类、不平衡分类、多标签分类、模糊分类等问题,算法还对AdaBoost系列算法进行了统一和推广.从保证组合预测函数的泛化能力出发,提出了算法中的简单预测函数可统一基于样本的单个特征来构造.理论分析和实验结论均表明,提出的系列算法的学习错误可以任意小,同时又不用担心出现过学习现象.
多文档文摘语义单元自动去噪器的监督学习方法
龚 书 瞿有利 田盛丰
2013, 50(4):  873-882. 
摘要 ( 509 )   HTML ( 5)   PDF (3373KB) ( 410 )  
相关文章 | 计量指标
多文档文摘的处理对象是存在噪音的文档集.现有文摘系统一般使用由人工设定阈值的固定阈值去噪器.但通过实验可见,不同文摘算法本身的抗噪能力各有高低,最优阈值随文档集、文摘算法、文本表示方法而改变,人工设定的固定阈值无法达到较好的通用性和去噪效果.为此,提出一种用于生成自动去噪器的监督学习方法,通过从人工文摘中自动获得标注信息,为语义单元提取多个特征,训练语义单元分类器而构成自动去噪器.可通用于不同文本表示所生成的语义单元,在不同多文档文摘系统的预处理阶段为任意文档集自动去除噪音语义单元.实验表明,该监督学习方法所生成的自动去噪器在不同文档集、文摘算法和文本表示方法下具有通用性,较好的去噪性能使各文摘算法的速度及所提取文摘的质量得到不同程度的提升.
连接位Minwise Hash算法的研究
袁鑫攀 龙 军 张祖平 罗跃逸 张 昊 桂卫华
2013, 50(4):  883-890. 
摘要 ( 1217 )   HTML ( 0)   PDF (2656KB) ( 448 )  
相关文章 | 计量指标
在信息检索中,Minwise Hash算法用于估计集合的相似度.b位Minwise Hash则通过存储Hash值的b位来估计相似度,从而节省了存储空间和计算时间.基于b位Minwise Hash的理论框架提出了连接位Minwise Hash算法,给出了连接位的相似度无偏估计和存储因子.通过理论证明了连接位Minwise Hash算法不需要损失很大的精度却可以成倍地减少比对的次数,提升了算法的性能.理论分析和实验验证了此方法的有效性.
手机三维菜单绩效预测模型
徐荣龙, 刘正捷,
2013, 50(4):  891-899. 
摘要 ( 468 )   HTML ( 0)   PDF (1186KB) ( 471 )  
相关文章 | 计量指标
菜单是手机界面的重要交互部件,手机功能增加所带来的菜单规模增大与手机小屏幕形成日益突出的矛盾.三维界面技术可以提高界面信息容量,因此,在手机上引入三维菜单概念是一个值得研究的课题.相应地,需要解决手机三维菜单用户操作绩效的评估问题.模型预测评估法能使研究人员和设计人员快速和以较低成本对用户界面进行评估.因此,基于Fitts定律和Hick-Hyman定律,建立了预测评估手机三维菜单操作绩效的定量模型.通过实验检验了模型的有效性,并将其与相关模型进行了对比分析.实验结果表明,实验得到的数据与该模型预测数据吻合较好,并且与相关模型相比该模型预测数据与实验数据的相关度最高.