• 2017年第28卷第10期文章目次
    全 选
    显示方式: |
    • 基于混合搜索的含逻辑“与”“或”的RM优化算法

      2017, 28(10):2525-2538. DOI: 10.13328/j.cnki.jos.005133

      摘要 (2917) HTML (149) PDF 1.11 M (2245) 评论 (0) 收藏

      摘要:相对于标准约束优化问题,广义约束优化问题(或称析取优化问题)的等式或不等式约束条件中不仅包含逻辑“与”关系,还含有逻辑“或”关系.单调速率(RM)优化问题是广义约束优化问题的一个重要应用.目前RM优化问题已有的解法包括函数变换、混合整数规划、线性规划搜索等算法.随着任务数的增多,这些算法的求解时间较长.提出一种基于线性规划的深度广度混合搜索算法(LPHS),将广义约束优化问题拆分成若干子问题,建立线性规划搜索树,合理选择搜索顺序,利用动态剪枝算法减小子问题的规模,最终求得最优解.实验结果表明,LPHS算法比其他方法有明显的效率提升.研究成果与计算机基础理论中的可满足性模理论的研究相结合,有助于提高可满足性模理论问题的求解效率,促进该理论在程序验证、符号执行等领域的进一步应用.

    • NMG-代数中同态核的结构刻画

      2017, 28(10):2539-2547. DOI: 10.13328/j.cnki.jos.005175

      摘要 (1962) HTML (153) PDF 567.31 K (1963) 评论 (0) 收藏

      摘要:逻辑代数上的Bosbach态与Riečan态是经典概率论中Kolmogorov公理的两种不同方式的多值化推广,也是概率计量逻辑中语义计量化方法的代数公理化,是非经典数理逻辑领域中的重要研究分支.现已证明具有Glivenko性质的逻辑代数上的Bosbach态与Riečan态等价,并且逻辑代数的Glivenko性质是研究态算子的构造和存在性的重要工具,因而是态理论中的研究热点之一.研究了NMG-代数基于核算子的Glivenko性质,证明NMG-代数具有核基Glivenko性质的充要条件是该核算子是从此NMG-代数到其像集代数的同态,并给出NMG-代数中同态核的结构刻画.这里,NMG-代数是刻画序和三角模<([0,1/2,TNM]),([1/2,1,TM])>的逻辑系统NMG的语义逻辑代数.

    • 面向软件产品线中特征选择的多目标优化算法

      2017, 28(10):2548-2563. DOI: 10.13328/j.cnki.jos.005130

      摘要 (2711) HTML (170) PDF 762.04 K (2402) 评论 (0) 收藏

      摘要:软件产品线中,产品定制的核心是选择合适的特征集.由于多个非功能需求间往往相互制约甚至发生冲突,特征选择的本质是多目标优化过程.优化过程的搜索空间被特征间错综复杂的依赖和约束关系以及明确的功能需求大大限制.另外,有些非功能需求有明确的数值约束,而有些则仅要求尽可能地得到优化.多样的非功能需求约束类型也给优化选择过程带来极大的挑战.提出一种含修正算子的多目标优化算法MOOFs.首先,设计特征间依赖和约束关系描述语言DL-DCF来统一规范特征选择过程中必须遵守的规则,所有的非功能需求都转化为优化目标,相关的数值约束则作为优化过程中特征选择方案的过滤器.另外,设计了修正算子用于保证选择出的特征配置方案必满足产品线的特征规则约束.通过与4种常用的多目标优化算法在4个不同规模的特征模型上的运行结果进行对比,表明该方法能够更快地产生满足约束的优化解,且优化解具备更好的收敛性与多样性.

    • CPN建模与on-the-fly方法相结合的测试用例生成

      2017, 28(10):2564-2582. DOI: 10.13328/j.cnki.jos.005145

      摘要 (1930) HTML (157) PDF 1.78 M (2455) 评论 (0) 收藏

      摘要:在对复杂的软件系统进行测试时,生成的系统状态空间可能会非常庞大.为了避免对整个状态空间进行遍历,提出将on-the-fly方法与CPN形式化建模方法结合起来,用于生成测试例.在这种方法中,无需对整个状态空间进行遍历,只是仅对测试人员感兴趣的部分状态空间进行针对性的测试.首先,给出CPN和扩展可达图的定义,介绍了on-the-fly测试方法中涉及的相关概念,包括系统规约、测试目的、同步乘积和测试例等.然后,实现了同步乘积算法,并设计相关测试例对其进行了测试.最后,选定一个被测系统示例CPN建模与on-the-fly结合的方法,并通过适配器实现与被测系统的交互,生成和执行测试例,由此验证了方法的可行性和有效性.

    • ROP图灵完备的普遍可实现性

      2017, 28(10):2583-2598. DOI: 10.13328/j.cnki.jos.005317

      摘要 (2046) HTML (195) PDF 676.74 K (2455) 评论 (0) 收藏

      摘要:返回导向编程(return-oriented programming,简称ROP)被广泛用于软件漏洞利用攻击中,用来构造攻击代码.通过更新ROP构造技术,证实了图灵完备的纯ROP攻击代码在软件模块中是普遍可实现的.ROP构造功能代码的难点是实现条件转移逻辑.通过深入分析条件转移机器指令的执行上下文发现,对这些指令的传统认知存在一定的局限性.事实上,在已有代码中存在少量的条件转移指令,它们的两个分支的开始部分都是可复用的代码片段(称为gadgets),而且这两个gadgets会从不同的内存单元中取得下一个gadget的地址,因此,以这些条件转移指令开始的代码片段可以帮助ROP实现条件转移逻辑.把这种代码片段称为if-gadget.在Linux和Windows系统上的实验结果表明,if-gadget普遍存在,即使在代码量很小的日常可执行程序中也存在.在Binutils程序集上的实验结果表明,引入if-gadget后,构造图灵完备的ROP代码要比用传统方法容易得多.在Ubuntu这样的主流操作系统上,由于可执行程序上默认没有实施防御ROP攻击的保护机制,因此,攻击者可以在这些软件模块中构造纯ROP攻击代码来发动攻击.由此可见,ROP对系统安全的威胁比原来认为的严重得多.

    • 拉普拉斯多层极速学习机

      2017, 28(10):2599-2610. DOI: 10.13328/j.cnki.jos.005128

      摘要 (3109) HTML (140) PDF 1.15 M (2737) 评论 (0) 收藏

      摘要:极速学习机不仅仅是有效的分类器,还能应用到半监督学习中.但是,半监督极速学习机和拉普拉斯光滑孪生支持向量机一样,是一种浅层学习算法.深度学习实现了复杂函数的逼近并缓解了以前多层神经网络算法的局部最小性问题,目前在机器学习领域中引起了广泛的关注.多层极速学习机(ML-ELM)是根据深度学习和极速学习机的思想提出的算法,通过堆叠极速学习机-自动编码器算法(ELM-AE)构建多层神经网络模型,不仅实现了复杂函数的逼近,并且训练过程中无需迭代,学习效率高.把流形正则化框架引入ML-ELM中,提出拉普拉斯多层极速学习机算法(Lap-ML-ELM).然而,ELM-AE不能很好地解决过拟合问题.针对这一问题,把权值不确定引入ELM-AE中,提出权值不确定极速学习机-自动编码器算法(WU-ELM-AE),可学习到更为鲁棒的特征.最后,在前面两种算法的基础上提出权值不确定拉普拉斯多层极速学习机算法(WUL-ML-ELM),它堆叠WU-ELM-AE构建深度模型,并用流形正则化框架求取输出权值.该算法在分类精度上有明显提高并且不需花费太多的时间.实验结果表明,Lap-ML-ELM与WUL-ML-ELM都是有效的半监督学习算法.

    • 基于异构网络面向多标签系统的推荐模型研究

      2017, 28(10):2611-2624. DOI: 10.13328/j.cnki.jos.005132

      摘要 (2052) HTML (235) PDF 774.81 K (2233) 评论 (0) 收藏

      摘要:标签成为信息组织的重要方式之一,随着推荐系统的蓬勃发展,标签推荐成为学者们研究的重要问题之一.目前存在各种各样的标签系统,其功能千差万别,标签数据信息越来越复杂.目前研究往往针对特定类型标签数据,缺乏既综合考虑标签数据中不同类型对象的复杂信息又能适用于多种标签系统数据的标签推荐模型.构建了标签推荐模型HnMTR,该模型首先针对标签数据中不同类型对象构建异构网络模型,其次对异构网络模型中不同类型顶点进行同空间映射,使不同类型的顶点和边可在同一空间进行量化比较;最后基于同空间映射后网络,引入多参数马尔可夫模型进行标签评分和推荐.通过基于豆瓣、Delicious和Meetup这3个标签系统数据实验,其结果表明,HnMTR模型平均准确率比目前主流算法提高10%以上,取得了较好的推荐结果.

    • 基于密度偏倚抽样的局部距离异常检测方法

      2017, 28(10):2625-2639. DOI: 10.13328/j.cnki.jos.005134

      摘要 (2773) HTML (265) PDF 1.20 M (2454) 评论 (0) 收藏

      摘要:异常检测是数据挖掘的重要研究领域,当前基于距离或者最近邻概念的异常数据检测方法,在进行海量高维数据异常检测时,存在运算时间过长的问题.许多改进的异常检测方法虽然提高了算法运算效率,然而检测效果欠佳.基于此,提出一种基于密度偏倚抽样的局部距离异常检测算法,首先利用基于密度偏倚的概率抽样方法对所需检测的数据集合进行概率抽样,之后对抽样数据利用基于局部距离的局部异常检测方法,对抽样集合进行局部异常系数计算,得到的异常系数既是抽样数据的局部异常系数,又是数据集的近似全局异常系数.然后对得到的每个数据点的局部异常系数进行排序,异常系数值越大的数据点越可能是异常点.实验结果表明,与已有的算法相比,该算法具有更高的检测精确度和更少的运算时间,并且该算法对各种维度和数据规模的数据都具有很好的检测效果,可扩展性强.

    • 基于读分割最优匹配的indels识别算法

      2017, 28(10):2640-2653. DOI: 10.13328/j.cnki.jos.005137

      摘要 (2528) HTML (153) PDF 850.35 K (2582) 评论 (0) 收藏

      摘要:高通量测序技术的发展,极大地推动了基因组结构变异识别的研究.当前,该领域主要使用覆盖度、读分割或片段组装方法来识别变异,但目前的方法识别结果不够准确,敏感度高,对基因组结构变异的信息(如变异序列、变异坐标等)挖掘不充分.插入和删除类型的结构变异统称为indels,在基因组结构变异中最为常见.为此,针对indels的精确识别,提出了基于读分割和动态规划的最优序列匹配算法(optimal split-read matching algorithm,简称OSRM).OSRM算法能将异常读片段以最少的空位打断比对到参考序列上.首先,建立异常读片段与特定参考序列的匹配得分矩阵;然后,建立回溯路径矩阵;最后,用以变异特点设计的得分公式对每条路径进行最优匹配筛选,输出精确识别的indels坐标及序列.实验结果显示,该方法对小中型的indels有很高的识别性能.此外,与读分割法的经典算法Pindel进行了比较,证实OSRM算法在小中型的indels识别方面有更好的效果,可识别更复杂的情况.

    • 融合语境分析的时序推特摘要方法

      2017, 28(10):2654-2673. DOI: 10.13328/j.cnki.jos.005146

      摘要 (2007) HTML (287) PDF 1.48 M (2281) 评论 (0) 收藏

      摘要:时序推特摘要是文本摘要任务中的一个重要分支,旨在从热点事件相关的海量推特流中总结出随时间演化的简要推特集,以帮助用户快速获取信息.推特作为当今最流行的社交媒体平台,其信息量爆发式的增长以及文本碎片的非结构性,使得单纯依赖文本内容的传统摘要方法不再适用.与此同时,社交媒体的新特性也为推特摘要带来了新的机遇.将推特流视作信号,剖析了其中的复杂噪声,提出融合推特流随时序变化的宏微观信号以及用户社交上下文语境信息的时序推特摘要新方法.首先,通过小波分析对推特流全局时序信息建模,实现某一关键词相关的热点子事件时间点检测;接着,融入推特流局部时序信息和用户社交信息建立推特的随机步图模型摘要框架,为每个热点子事件生成推特摘要.在算法评估过程中,对真实推特数据集进行了专家时间点和专家摘要的人工标注,实验结果表明了小波分析和融合了时序-社交上下文语境的图模型在时序推特摘要中的有效性.

    • 中文短文本聚合模型研究

      2017, 28(10):2674-2692. DOI: 10.13328/j.cnki.jos.005147

      摘要 (2147) HTML (186) PDF 2.96 M (2538) 评论 (0) 收藏

      摘要:中文短文本聚合的目的是将两个数据集中属于同一对象的短文本信息进行匹配关联,同时要避免匹配不属于同一对象的短文本信息,这项研究对于多源异构的短文本数据资源整合具有重要的理论和现实意义.提出了一种有效的中文短文本聚合模型,通过快速匹配和精细匹配两个关键步骤可以大幅度降低匹配的候选对数量,并保证匹配的精度.针对传统短文本相似度算法的不足,提出了一种新颖的广义Jaro-Winkler相似度算法,并从理论上分析了该算法的参数特性.通过对不同数据集上的商户信息数据进行聚合实验,结果表明,新算法与传统算法相比,在匹配准确率和稳定性上具有最优的性能.

    • 面向节点演化波动的社会网络事件检测方法

      2017, 28(10):2693-2703. DOI: 10.13328/j.cnki.jos.005153

      摘要 (2059) HTML (143) PDF 872.77 K (2148) 评论 (0) 收藏

      摘要:社会网络特征千差万别,演化规律错综复杂.合理地分析网络演化规律,及时地检测网络事件具有重大意义.基于链路预测的社会网络事件检测方法利用有限的网络拓扑信息,能够有效地发现网络演化的异常波动,准确地检测网络事件.然而,现有方法大多受到链路预测的宏观评价指标的限制,忽略了不同节点演化波动的差异,用相同的相似性计算指标去描述所有节点的演化波动,不利于提升事件检测的表现.为了进一步提升事件检测的精确性和敏感性,提出一种面向节点演化波动的社会网络事件检测方法NodeED,由节点相似性计算指标判定算法SimJudge和网络微观演化波动检测算法MicroFluc组成.主要工作如下:(1)结合粒子群优化算法,提出SimJudge定量地比较不同的相似性计算指标对节点演化波动的描述程度,确定每个节点在不同时段的最佳相似性计算指标;(2)为了量化事件对网络演化的影响,提出了MicroFluc,充分考虑节点演化波动的差异,从节点演化波动的角度对不同时段的网络整体演化波动进行定量评估;(3)在真实社会网络VAST和ENRON中进行对比实验,其结果表明,NodeED在VAST中的事件敏感性提升了100%,在ENRON中的事件敏感性提升了50%,更有利于精确地检测社会网络中发生的事件.

    • 自适应偏好半径划分区域的多目标进化方法

      2017, 28(10):2704-2721. DOI: 10.13328/j.cnki.jos.005307

      摘要 (2400) HTML (172) PDF 2.52 M (2149) 评论 (0) 收藏

      摘要:偏好多目标进化算法是一类帮助决策者找到感兴趣的Pareto最优解的算法.目前,在以参考点位置作为偏好信息载体的偏好多目标进化算法中,不合适的参考点位置往往会严重影响算法的收敛性能,偏好区域的大小难以控制,在高维问题上效果较差.针对以上问题,通过计算基于种群的自适应偏好半径,利用自适应偏好半径构造一种新的偏好关系模型,通过对偏好区域进行划分,提出基于偏好区域划分的偏好多目标进化算法.将所提算法与4种常用的以参考点为偏好信息载体的多目标进化算法g-NSGA-II、r-NSGA-II、角度偏好算法、MOEA/D-PRE进行对比实验,结果表明,所提算法具有较好的收敛性能和分布性能,决策者可以控制偏好区域大小,在高维问题上也具有较好的收敛效果.

    • 一种新的密码学原语研究——流程加密

      2017, 28(10):2722-2736. DOI: 10.13328/j.cnki.jos.005138

      摘要 (1946) HTML (144) PDF 840.08 K (2214) 评论 (0) 收藏

      摘要:在许多实际的应用场景中,当用户需要获取敏感数据时,需要判断该用户是否满足某些“流程”的要求.现存的加密方案不能有效应用到以上场景中.为了解决这一新问题,提出了一种新的加密原语:基于流程的加密(process based encryption,简称PBE),并把PBE分成两种类型:密钥策略的PBE(KP-PBE)与密文策略的PBE(CP-PBE).运用双线性映射与线性秘密共享协议的工具,给出了一种KP-PBE的构造方法.随后,把KP-PBE方案与传统属性加密进行对比,指出在描述流程数量方面,KP-PBE与传统属性加密方案存在数量级的差异,从而体现了KP-PBE方案在描述流程方面的优越性.最后,在选择性安全的模型下,证明了该方案的安全性.

    • 一种高精度、低开销的单包溯源方法

      2017, 28(10):2737-2756. DOI: 10.13328/j.cnki.jos.005149

      摘要 (1921) HTML (135) PDF 2.42 M (1981) 评论 (0) 收藏

      摘要:混合拒绝服务攻击是当前互联网面临的主要威胁之一,针对它的单包溯源技术已成为网络安全领域研究的重点和热点.鉴于已有的单包溯源研究存在处理开销大、溯源精度低等问题,提出一种高精度、低开销的基于标签交换的单包溯源方法,简称S3T.该方法的基本思想是借鉴MPLS网络的交换路径生成原理,在溯源路由器上建立面向反向路由的追踪痕迹,降低溯源存储开销.然后,通过并行化建立追踪痕迹、灵活配置溯源路由器存储容量和自适应调整追踪痕迹存储时间等手段加快溯源路由器处理IP包速率,同时提高溯源精度.通过理论分析和基于大规模真实互联网拓扑的仿真实验,其结果表明,相比以往方案,S3T在溯源开销和溯源精度方面确实有了很大的改善.

    • 安全的无双线性映射的无证书签密机制

      2017, 28(10):2757-2768. DOI: 10.13328/j.cnki.jos.005150

      摘要 (1874) HTML (152) PDF 658.04 K (1952) 评论 (0) 收藏

      摘要:无证书签密是能够同时提供无证书加密和无证书签名的一种非常重要的密码学原语.近年来,多个无证书签密方案相继被提出,并声称他们的方案是可证明安全的.但是,通过给出具体的攻击方法,指出现有的一些无证书签密机制并不具备其所声称的安全性.针对上述问题,提出一种无双线性映射的高效无证书签密方案,并在随机谕言机模型下,基于计算性Diffie-Hellman问题和离散对数问题对所提方案的安全性进行了证明.同时,该方案还具有不可否认性和公开验证性等安全属性.与其他传统无证书签密方案相比,由于未使用双线性映射运算,在具有更高计算效率的同时,该方案的安全性更优.

    • 加权无标度网络的级联失效模型

      2017, 28(10):2769-2781. DOI: 10.13328/j.cnki.jos.005173

      摘要 (1839) HTML (178) PDF 1.17 M (2024) 评论 (0) 收藏

      摘要:在加权的无标度网络中,为了抵抗网络的级联失效,增强网络的鲁棒性,提出了一种参数可调的级联失效模型.该模型从全局和局域的角度,将节点介数、节点度、节点权重和邻居节点权重相结合构建节点的初始负载,并建立节点容量与初始负载的比例关系,当节点失效后,通过结合失效节点邻居的容量来制定负载重分配规则,进而通过对网络级联失效的分析,推导负载参数的演化过程,得出模型中的参数对网络鲁棒性的影响.最后,通过实验验证了所提方法的有效性.

    • 虚拟可信平台模块动态信任扩展方法

      2017, 28(10):2782-2796. DOI: 10.13328/j.cnki.jos.005174

      摘要 (2114) HTML (201) PDF 1.08 M (2459) 评论 (0) 收藏

      摘要:将可信计算技术应用到虚拟计算系统中,可以在云计算、网络功能虚拟化(network function virtualization,简称NFV)等场景下,提供基于硬件的可信保护功能.软件实现的虚拟可信平台模块(virtual trused platform module,简称vTPM)基于一个物理TPM(physical TPM,简称pTPM),可让每个虚拟机拥有自己专属的TPM,但需要将对pTPM的信任扩展到vTPM上.现有方法主要采用证书链来进行扩展,但在虚拟机及其vTPM被迁移后,需要重新申请vTPM的身份密钥证书,可能会存在大量的短命证书,成本较高,且不能及时撤销旧pTPM对vTPM的信任扩展,也不能提供前向安全保证.提出了一种vTPM动态信任扩展(dynamic trust extension,简称DTE)方法,以满足虚拟机频繁迁移的需求.DTE将vTPM看作是pTPM的一个代理,vTPM每次进行远程证明时,需从一个认证服务器(authenticaiton server,简称AS)处获得一个有效的时间令牌.DTE在vTPM和pTPM之间建立了紧密的安全绑定关系,同时又能明显区分两种不同安全强度的TPM.在DTE里,vTPM被迁移后,无需重新获取身份秘钥证书,旧pTPM可及时撤销对vTPM的信任扩展,而且DTE可提供前向安全性.从原型系统及其性能测试与分析来看,DTE是可行的.

    • 自适应轮廓的变分水平集复杂背景多目标检测

      2017, 28(10):2797-2810. DOI: 10.13328/j.cnki.jos.005172

      摘要 (2396) HTML (175) PDF 2.10 M (2426) 评论 (0) 收藏

      摘要:无需重新初始化的变分水平集模型能够避免经典水平集模型的重复初始化步骤,进而简化计算,缩短检测所需时间,同时能够有效利用图像的边缘梯度信息,从而准确定位图像的局部结构.但该模型不能自适应地获得初始化曲线,水平集的拓扑结构也无法改变,不能解决多个目标的检测问题.针对以上问题,提出了一种基于自适应轮廓的变分水平集复杂背景多目标检测方法,该方法采用帧间差分算法与K-means聚类算法相结合,以获得多个运动目标的初始化曲线,通过形态学方法来降低图像噪声的干扰,从而快速自适应地估计复杂背景下运动目标的位置和轮廓大小.该算法进一步对无需初始化的变分水平集进行改进,将其由单目标检测模型扩展为多目标检测模型,并修正原模型难以处理图像灰度不均匀的问题,最终实现对复杂背景下多个目标的检测.在标准数据库和实际数据集上的测试结果表明,所提方法能够准确地定位不同尺度和灰度目标的轮廓,从而提高算法的演化迭代效率及准确性.

当期目录


文章目录

过刊浏览

年份

刊期

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