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

当期目录

2017年 第54卷 第7期    出版日期:2017-07-01
综述
SMT求解技术的发展及最新应用研究综述
王翀,吕荫润,陈力,王秀利,王永吉,
2017, 54(7):  1405-1425.  doi:10.7544/issn1000-1239.2017.20160303
摘要 ( 1262 )   HTML ( 18)   PDF (5478KB) ( 766 )  
相关文章 | 计量指标
可满足性模理论(satisfiability modulo theories, SMT)是判定一阶逻辑公式在组合背景理论下的可满足性问题.SMT的背景理论使其能很好地描述实际领域中的各种问题,结合高效的可满足性判定算法,SMT在测试用例自动生成、程序缺陷检测、RTL(register transfer level)验证、程序分析与验证、线性逻辑约束公式优化问题求解等一些最新研究领域中有着突出的优势.首先阐述SMT问题的基础SAT(satisfiability)问题及判定算法;其次对SMT问题、判定算法进行了总结,分析了主流的SMT求解器,包括Z3,Yices2,CVC4等;然后着重介绍了SMT求解技术在典型领域中的实际应用,对目前的研究热点进行了阐述;最后对SMT未来的发展前景进行了展望,目的是试图推动SMT的发展,为此领域的相关人员提供有益的参考.
人工智能
基于图和改进K近邻模型的高效协同过滤推荐算法
孟桓羽,刘真,王芳,徐家栋,张国强
2017, 54(7):  1426-1438.  doi:10.7544/issn1000-1239.2017.20160302
摘要 ( 753 )   HTML ( 1)   PDF (4831KB) ( 707 )  
相关文章 | 计量指标
在互联网高速发展的今天,推荐系统已成为解决信息过载的有效手段,能够缓解用户在筛选感兴趣信息时的困扰,帮助用户发现有价值的信息.推荐系统中的协同过滤推荐算法,因其领域无关性及支持用户发现潜在兴趣的优点被广泛应用.由于数据的规模过大且稀疏的特点,当前协同过滤在算法实时性、推荐精确度等方面仍有较大提升空间.提出了GK-CF方法,通过建立基于图的评分数据模型,将传统的协同过滤算法与图计算及改进的KNN算法结合.通过图的消息传播及改进的相似度计算模型对用户先进行筛选再做相似度计算;以用户-项目二部图的节点结构为基础,通过图的最短路径算法进行待评分项目的快速定位.在此基础上,进一步通过并行图框架对算法进行了并行化实现及优化.在物理集群环境下进行了实验,结果表明,与已有的协同过滤算法相比,提出的GK-CF算法能够很好地提高推荐的准确度和评分预测的准确性,并具有较好的算法可扩展性和实时性能.
一种基于差分隐私保护的协同过滤推荐方法
何明,常盟盟,吴小飞
2017, 54(7):  1439-1451.  doi:10.7544/issn1000-1239.2017.20160207
摘要 ( 893 )   HTML ( 5)   PDF (5394KB) ( 628 )  
相关文章 | 计量指标
由于推荐系统需要利用大量用户数据进行协同过滤,会给用户的个人隐私带来相当大的风险,如何保护隐私数据成为推荐系统当前面临的重大挑战.差分隐私作为一种新出现的隐私保护框架,能够防止攻击者拥有任意背景知识下的攻击并提供有力的保护.针对推荐系统中的隐私保护问题,提出一种满足差分隐私保护的协同过滤推荐算法.首先,构建用户和项目的潜在特征矩阵,有效降低数据稀疏性;然后,采用目标扰动方法对矩阵中添加满足差分隐私约束的噪声得到噪矩阵分解模型;通过随机梯度下降算法最小化相关联的正则化平方误差函数来获取模型中的参数;最后,应用差分隐私矩阵分解模型进行评分预测,并在MovieLens和Netflix数据集上对算法的有效性进行评价.实验结果证明:所提出方法的有效性能够在有限的精度损失范围内进行推荐并保护用户隐私.
基于Spark的Top-k对比序列模式挖掘
张鹏,段磊,秦攀,左劼,唐常杰,元昌安,彭舰
2017, 54(7):  1452-1464.  doi:10.7544/issn1000-1239.2017.20160553
摘要 ( 1200 )   HTML ( 4)   PDF (5657KB) ( 504 )  
相关文章 | 计量指标
对比序列模式(distinguishing sequential pattern, DSP)指在目标类序列集合中频繁出现,而在非目标类序列集合中不频繁出现的序列.对比序列模式能够描述2个序列集合间的差异,有着广泛的应用,例如:构建序列分类器,识别DNA序列的生物特征,特定人群行为分析.与挖掘满足支持度阈值要求的对比序列模式相比,挖掘对比度top-k对比序列模式能避免用户设置不恰当的支持度阈值.因而,更易于用户使用.但是现有的top-k对比序列模式挖掘算法难以处理大规模序列数据.对此,设计了一种基于Spark的top-k对比序列模式并行挖掘算法,称为SP-kDSP-Miner.此外,为了提高SP-kDSP-Miner的效率,针对Spark结构的特点,设计了候选模式生成策略和若干剪枝策略,以及候选模式对比度的并行计算方法.通过在真实数据集与合成数据集上的实验,验证了SP-kDSP-Miner的有效性、执行效率和可扩展性.
基于邻居选取策略的人群定向算法
周孟,朱福喜
2017, 54(7):  1465-1476.  doi:10.7544/issn1000-1239.2017.20160360
摘要 ( 673 )   HTML ( 1)   PDF (4655KB) ( 401 )  
相关文章 | 计量指标
人群定向是广告推荐系统中的一种重要技术,它是通过分析种子人群的行为数据,找出潜在的目标人群,而现有人群定向算法大多依赖于传统的协同过滤推荐算法.由于传统的协同过滤算法具有推荐精度低和抗攻击能力较弱的问题,为了解决这些问题,提出了一种基于邻居选取策略的人群定向算法.1)通过用户行为相似,动态选择出与种子人群具有相似行为的用户;2)以用户特征和用户行为作为邻居选取的依据,通过用户相似度从行为相似人群中选择出每个种子用户的邻居,并将所有的相似邻居作为候选人群;3)通过基于邻居选取策略的人群定向算法,从候选人群中择出潜在的目标用户,以完成人群定向.实验结果表明:与现有方法相比,该方法不仅提高了人群定向的精度,而且也增强了系统的抗攻击能力.
一种基于决策森林的单调分类方法
许行,王文剑,任丽芳
2017, 54(7):  1477-1487.  doi:10.7544/issn1000-1239.2017.20160154
摘要 ( 636 )   HTML ( 0)   PDF (5890KB) ( 489 )  
相关文章 | 计量指标
单调分类问题是特征与类别之间带有单调性约束的有序分类问题.对于符号数据的单调分类问题已有较好的方法,但对于数值数据,现有的方法分类精度和运行效率有限.提出一种基于决策森林的单调分类方法(monotonic classification method based on decision forest, MCDF),设计采样策略来构造决策树,可以保持数据子集与原数据集分布一致,并通过样本权重避免非单调数据的影响,在保持较高分类精度的同时有效提高了运行效率,同时这种策略可以自动确定决策森林中决策树的个数.在决策森林进行分类时,给出了决策冲突时的解决方法.提出的方法既可以处理符号数据,也可以处理数值数据.在人造数据集、UCI及真实数据集上的实验数据表明:该方法可以提高单调分类性能和运行效率,缩短分类规则的长度,解决数据集规模较大的单调分类问题.
基于贝叶斯网的评价数据分析和动态行为建模
王飞,岳昆,孙正宝,武浩,冯辉
2017, 54(7):  1488-1499.  doi:10.7544/issn1000-1239.2017.20160556
摘要 ( 892 )   HTML ( 3)   PDF (7278KB) ( 557 )  
相关文章 | 计量指标
随着Web2.0的不断普及和电子商务应用的迅速发展,大规模的在线评价数据不断产生,使用户行为数据分析和用户行为建模成为可能,具有重要意义.考虑到用户评价数据和评价行为的动态性,提出以带有隐变量的贝叶斯网作为各属性间依赖关系及其不确定性表示的基本框架,构建既能刻画用户评价数据中各属性间相互依赖的不确定性、也能描述用户行为动态性的评价行为模型.首先,以贝叶斯信息标准(BIC)分值作为模型与数据拟合度的度量标准,提出基于打分搜索方法来构建各时间片的隐变量模型,并给出基于期望最大(EM)算法的隐变量取值填充方法;其次,基于条件互信息和时序的不可逆性,提出了相邻时间片间隐变量模型的构建方法.建立在MovieLens数据集上的实验结果验证了提出的动态用户行为建模方法的高效性及有效性.
不完备多粒度决策系统的局部最优粒度选择
顾沈明,顾金燕,吴伟志,李同军,陈超君
2017, 54(7):  1500-1509.  doi:10.7544/issn1000-1239.2017.20160349
摘要 ( 660 )   HTML ( 0)   PDF (2089KB) ( 296 )  
相关文章 | 计量指标
粒计算是知识表示和数据挖掘的一个重要方法.从粒计算来看,一个粒是由多个比较小的颗粒组成的更大的一个单元.在许多实际应用中,由于不同标记尺度对数据集进行分割会得到不同层次的粒度,许多人在用粒计算解决问题时自然而然地考虑不同层次的粒度问题.这就促使思考如何选择一个合适的粒度层次来解决问题.围绕不完备多粒度决策系统,研究了基于局部最优粒度的规则提取方法.1)介绍了不完备多粒度决策系统的概念;2)在协调的不完备多粒度决策系统中定义了最优粒度和局部最优粒度、介绍了基于局部最优粒度的属性约简和规则提取方法,在不协调的不完备多粒度决策系统中引入了广义决策、定义了广义最优粒度和广义局部最优粒度,并给出了基于广义局部最优粒度的属性约简和规则提取方法;3)给出了在公开的数据集上的实验结果.
信息安全
基于格的前向安全无证书数字签名方案
徐潜,谭成翔,冯俊,樊志杰,朱文烨
2017, 54(7):  1510-1524.  doi:10.7544/issn1000-1239.2017.20160427
摘要 ( 748 )   HTML ( 2)   PDF (3131KB) ( 439 )  
相关文章 | 计量指标
无证书签名方案利用密钥生成中心与用户共同生成签名密钥的方式,解决了传统的基于身份的数字签名方案中存在的密钥托管问题.目前,针对无证书签名方案的研究还存在3点可以改进的地方:1)已有的基于随机格构建的无证书签名方案,虽然具有后量子安全性,但都是建立在随机预言模型下,尚无针对标准模型的相关研究;2)已有的格基无证书签名方案大多只考虑外部敌手,缺乏抵御不诚实用户攻击的能力;3)已有的无证书签名方案均需要保证用户密钥是绝对安全的,无法解决密钥泄露问题.针对这3点不足,在随机预言模型下的前向安全的无证书格基签名方案的基础上,首次提出了标准模型下可证明安全的基于随机格的前向安全无证书数字签名方案,并在不引入第三方代理的前提下同时解决了密钥泄露和密钥托管问题.在面对不诚实的用户和恶意密钥生成中心2类强敌手的情况下,利用小整数解SIS假设证明了所提出的方案具有适应性选择消息、选择身份攻击下的前向安全强不可伪造性.
Crypton算法的不可能差分分析
崔竞一,郭建胜,刘翼鹏
2017, 54(7):  1525-1536.  doi:10.7544/issn1000-1239.2017.20160415
摘要 ( 561 )   HTML ( 1)   PDF (4586KB) ( 265 )  
相关文章 | 计量指标
Crypton算法是基于Square算法设计的SPN结构类密码算法,由于其具备良好的软硬件性能而引起了广泛的关注.对Crypton分组密码算法在不可能差分分析下的安全性进行了研究.通过分析Crypton算法扩散层的性质,指出了现有7轮Crypton算法不可能差分分析中存在的问题,结合快速排序、分割攻击与早夭技术对7轮Crypton算法的不可能差分分析进行了改进,降低了其数据复杂度与时间复杂度;同时,通过并行使用4条不可能差分区分器,结合密钥扩展算法的性质给出了7轮Crypton算法的多重不可能差分分析结果,恢复了算法的主密钥;最后,在7轮Crypton算法的不可能差分分析的基础上向后拓展1轮,给出了8轮Crypton-256算法的不可能差分分析,恢复了其主密钥,其数据复杂度为2\+{103}个选择明文,时间复杂度为2\+{214}次8轮Crypton加密,存储复杂度为2\+{154.4} B.研究结果表明:结合算法的性质及多种技术给出了Crypton算法目前最优的不可能差分分析结果.
针对数据泄漏行为的恶意软件检测
王丽娜,谈诚,余荣威,尹正光
2017, 54(7):  1537-1548.  doi:10.7544/issn1000-1239.2017.20160436
摘要 ( 610 )   HTML ( 6)   PDF (7670KB) ( 579 )  
相关文章 | 计量指标
高级可持续威胁(advanced persistent threat, APT)级网络攻击对企业和政府的数据保护带来了极大的挑战.用0day漏洞制作恶意软件来进行攻击是APT级网络攻击的常用途径,传统基于特征的安全系统很难检测这类攻击.为了检测泄漏敏感信息的恶意软件,首先分析已出现的APT恶意软件,描绘出窃取信息的攻击步骤,以此为基础提出1个针对数据泄漏行为的恶意软件检测方案用于检测同种攻击类型的恶意软件.该方案结合异常检测和误用检测,对被保护的主机和网络进行低开销的持续监控,同时提出一系列推断规则来描述攻击步骤中可以观察到的高级恶意事件.一旦监控到可疑事件,进一步收集主机和网络的低级行为,根据推断规则关联低级行为和高级恶意事件,据此重构窃取信息的攻击步骤,从而检测出攻击的存在.通过仿真实验验证了该方案的有效性.
非加密方法安全计算集合包含关系
陈振华,李顺东,王道顺,黄琼,董立红
2017, 54(7):  1549-1556.  doi:10.7544/issn1000-1239.2017.20160034
摘要 ( 476 )   HTML ( 0)   PDF (1940KB) ( 260 )  
相关文章 | 计量指标
针对已存在的安全计算集合包含关系的协议大多基于多次公钥加密算法,计算复杂性较高,并且不能公开计算,应用受限的问题.提出了2种非加密安全计算集合包含关系的协议.协议1首先将集合包含问题转化为向量内积问题;然后利用数学难解问题解决了此问题;最后针对不可信第三方存在的应用场景,利用双线性对和数学难解问题给出了可公开判断集合包含关系的实用性协议2.协议1和协议2都没有使用任何公钥加密方法,避免了前人方案中繁琐的公私钥产生和加解密过程以及多次匹配查找,因此更加高效而简洁.此外,协议2开拓了保密判断集合关系的新应用场景.
软件技术
使用锁分配图动态检测混合死锁
禹振,苏小红,邱景
2017, 54(7):  1557-1568.  doi:10.7544/issn1000-1239.2017.20160369
摘要 ( 424 )   HTML ( 1)   PDF (4342KB) ( 436 )  
相关文章 | 计量指标
死锁难以暴露、重演和调试.一旦发生,将导致多线程程序响应时间增长、吞吐量下降甚至宕机崩溃.现有死锁检测技术每次只能检测一个互斥锁死锁.为一次性检测由多个线程和多个互斥锁或读写锁造成的所有类型死锁,首先提出混合锁分配图的概念和构建方法,然后提出一种利用混合锁分配图动态检测混合死锁的方法.通过劫持所有互斥锁和读写锁的加锁解锁操作,以动态构建和实时更新一个反映目标程序同步状态的混合锁分配图.通过在锁分配图上检测环并判定该环是否为死锁环来检测死锁.当检测到死锁时,输出死锁信息来辅助调试.死锁检测实验、性能影响实验和可扩展性实验结果表明:该方法成功检测出所有13个共5种类型的死锁缺陷,检测能力强;给openldap-2.2.20带来至多10.15%的性能下降幅度,对目标程序造成的性能影响较小;性能开销随线程数目指数级增大而平缓增长,扩展性良好.
基于QEMU的动态函数调用跟踪
向勇,曹睿东,毛英明
2017, 54(7):  1569-1576.  doi:10.7544/issn1000-1239.2017.20160094
摘要 ( 879 )   HTML ( 3)   PDF (3069KB) ( 381 )  
相关文章 | 计量指标
函数调用一直是Linux内核分析研究领域的重点.获得函数调用信息主要有2种方法:静态分析和动态分析.动态跟踪方法可实时和准确地获取函数调用关系信息,在分析和调试软件程序时有极大的帮助作用.针对现有工具存在跟踪信息不全面、需要编译选项支持等不足,基于开源的QEMU模拟器,设计并实现了支持多种CPU平台的通用动态函数调用跟踪工具,可在x86_32,x86_64,ARM共3种体系架构上动态跟踪包括Linux内核启动过程在内的函数调用和返回信息.该工具在程序运行时截获调用和返回的指令,并记录相关信息,利用此种指令只会在QEMU翻译块的最后一条出现的性质,减少检查指令的数量,提高运行效率;可不依赖源代码,只依据函数符号表进行函数调用关系分析.实验结果表明:跟踪和分析结果与源代码行为一致,相比于S2E提升了分析性能和支持的CPU平台种类,且能更好地扩展至其他平台.
Web数据库top-k多样性关键字查询推荐方法
孟祥福,毕崇春,张霄雁,唐晓亮,唐延欢
2017, 54(7):  1577-1591.  doi:10.7544/issn1000-1239.2017.20160005
摘要 ( 589 )   HTML ( 0)   PDF (6668KB) ( 506 )  
相关文章 | 计量指标
Web数据库用户通常使用他们熟知的关键字表达查询意图,这可能导致获取的结果不能很好满足其查询需求,因此为他们提供top-k个与初始查询语义相关且多样化的候选查询有助于用户扩展知识范围,从而更准确完善地表达其查询意图.提出一种top-k多样性关键字查询推荐方法.1)利用不同关键字在查询历史中的同现频率和关联关系评估关键字之间的内耦合和间耦合关系;2)根据关键字之间的耦合关系构建语义矩阵,进而利用语义矩阵和核函数方法评估不同关键字查询之间的语义相关度.为了快速返回top-k个与初始查询相关且多样性的候选查询,根据查询之间的语义相关度,利用概率密度函数分析查询的典型程度,并利用近似算法从查询历史中找出典型查询.对于所有的典型查询,从中选出少数代表性查询,根据其他典型查询与代表性查询之间的语义相关度,为每个代表性查询构建相应的查询序列;当一个新的查询到来时,评估其与代表性查询之间的语义相关度,然后利用阈值算法(threshold algorithm, TA)在预先创建的查询序列上快速选出top-k个与给定查询语义相关的多样性候选查询.实验结果和分析表明:提出的关键字之间耦合关系计算和查询之间的语义相关度评估方法具有较高准确性,top-k多样性选取方法具有较好效果和较高执行效率.
一种基于Spark的多路空间连接查询处理算法
乔百友,朱俊海,郑宇杰,申木川,王国仁
2017, 54(7):  1592-1602.  doi:10.7544/issn1000-1239.2017.20160558
摘要 ( 620 )   HTML ( 0)   PDF (6150KB) ( 235 )  
相关文章 | 计量指标
针对云环境下空间数据连接查询处理问题,提出了一种基于Spark的多路空间连接查询处理算法BSMWSJ.该算法采用网格划分方法将整个数据空间划分成大小相同的网格单元,并将各类数据集中的空间对象,根据其空间位置划分到相应的网格单元中,不同网格单元中的空间数据对象进行并行连接查询处理.在多路空间连接查询处理过程中,采用边界过滤的方法来过滤无用数据,即通过计算前面连接操作候选结果的MBR来过滤后续连接数据集,从而过滤掉无用的连接对象,减少连接对象的多余投影与复制,并采用重复避免策略来减少重复结果的输出,从而进一步减少后续连接计算的代价.合成数据集和真实数据集上的大量实验结果表明:提出的多路空间连接查询处理算法在性能上明显优于现有的多路连接查询处理算法.
支持多用户协同编辑的云存储访问控制方法
史姣丽,黄传河,何凯,沈燮阳,华超
2017, 54(7):  1603-1616.  doi:10.7544/issn1000-1239.2017.20151135
摘要 ( 489 )   HTML ( 0)   PDF (7723KB) ( 471 )  
相关文章 | 计量指标
以往的云存储属性基访问控制研究大多数是对外包数据的读权限进行控制,很少考虑多个用户协同编辑云端同一个外包数据时的写权限控制.多用户协同编辑控制存在挑战:1)资源有限的数据拥有者希望云辅助自己对外包数据的写权限进行控制,但不希望云获得数据内容,也不希望云感知匹配内容,甚至不希望云能够预测用户的写权限;2)布尔公式的访问结构无法表达写权限控制策略;3)双线性映射运算计算代价大,不适合多用户协同编辑控制.提出一个支持多用户协同编辑的云存储访问控制方法:数据拥有者采用表达能力更丰富的circuit定义写权限访问控制策略,委托半可信云采用矩阵运算快速判断用户提交的修改数据是否应该接受,并且云不可预测每个用户是否具有写权限.分析与实验表明:该方法具有多用户协同编辑的访问控制能力,并且在读权限控制时,利用云辅助解密方法使得用户端存储量和加解密计算量是较小的.
网络技术
一种减少长尾延迟的分布式实时约束传播方法
任睿,马久跃,隋秀峰,包云岗
2017, 54(7):  1617-1628.  doi:10.7544/issn1000-1239.2017.20160247
摘要 ( 1122 )   HTML ( 2)   PDF (6790KB) ( 296 )  
相关文章 | 计量指标
提出了一种在数据中心环境下用于减少长尾延迟的分布式实时约束传播方法,该方法能够使当前节点感知请求的全局响应时间约束信息,并能够将请求的实时约束信息传播到整个处理路径;节点可以利用请求的实时约束信息进行请求调度或加速请求执行时间,以此来减少长尾延迟现象.同时,针对划分/聚合模式和串行/依赖模式2种数据中心应用,提出了阶段服务模型和并行单元模型,并基于这2种模型实现了分布式实时约束传播框架.最后,在分布式实时约束传播框架上实现了实时约束感知调度算法,通过实验进行了简单的验证,初步的实验结果显示了分布式实时约束传播方法能够在一定程度上减少长尾延迟.