2019, 30(11):3243-3258. DOI: 10.13328/j.cnki.jos.005567
摘要:秩函数法是循环程序终止性分析的主流方法.针对一类多分支多项式循环程序,这类程序的秩函数计算问题被证明可归结为单形上正定多项式的探测问题,从而便于利用线性规划工具Simplex去计算这类程序的秩函数.不同于现有基于柱形代数分解的量词消去算法,该方法能够在可接受的时间内计算更为复杂的多项式秩函数.
甘水滔 , 王林章 , 谢向辉 , 秦晓军 , 周林 , 陈左宁
2019, 30(11):3259-3280. DOI: 10.13328/j.cnki.jos.005562
摘要:提出了一种基于程序功能标签切片的制导符号执行分析方法OPT-SSE.该方法从程序功能文档提取功能标签,利用程序控制流分析,建立各功能标签和程序基本块的映射关系,并根据功能标签在程序执行中的顺序关系生成功能标签执行流.针对给定的代码目标点,提取与之相关的功能执行流切片,根据预定义好的功能标签流制导规则进行符号执行分析,在路径分析过程中,及时裁剪无关的功能分支路径以提升制导效率.通过对不同的功能标签流进行分离制导符号执行分析,可避免一直执行某复杂循环体的情形,从而提高对目标程序的整体分支覆盖率和指令覆盖率.实验结果表明,通过对binutils、gzip、coreutils等10个不同软件中的20个应用工具上的分析,OPT-SSE与KLEE提供的主流搜索策略相比,代码目标制导速度平均提升到4.238倍,代码目标制导成功率平均提升了31%,程序指令覆盖率平均提升了8.95%,程序分支覆盖率平均提升了8.28%.
2019, 30(11):3281-3296. DOI: 10.13328/j.cnki.jos.005582
摘要:安卓系统在移动端操作系统始终占据主导地位,在增强用户体验和提高程序性能的同时,其特有的事件驱动模型和多线程模型也造成了并发缺陷.并发程序中,线程调度的不确定性和难以再现性是并发缺陷检测困难的原因.现有技术主要在动态生成执行路径的基础上进行发生序(happens-before)分析,进而检测安卓应用的并发缺陷,但仍然存在低覆盖率、误报、漏报等问题.结合共享变量分析和约束求解方法实现了安卓应用数据竞争的检测,并实现了检测工具RaceDetector.该工具首先根据安卓系统的特性和数据竞争的定义,通过静态分析抽取相关信息,并进一步使用安卓共享变量分析来提高准确性和性能,继而进行可疑数据竞争分析,得出可疑的数据竞争集合;接着根据每一个可疑的数据竞争候选者,通过约束求解的方法在所有事件调度和线程调度解空间下识别发生序关系,并最终检测出真正的数据竞争.实验部分是从Google Play等来源收集了15个流行的应用APK文件作为数据集,RaceDetector平均报告了340个数据竞争,误报率为13%(44/340).与现有工具EventRacer(默认产生300随机事件触发应用执行,平均检测2个有害数据竞争)相比,RaceDetector能够解析全部源码,覆盖了所有线程调度和事件调度,平均检测出15个有害数据竞争.
陈星 , 黄志明 , 叶心舒 , 马郓 , 陈艺燕 , 郭文忠
2019, 30(11):3297-3312. DOI: 10.13328/j.cnki.jos.005802
摘要:随着智能家居基础设施的不断发展,智能家居逐渐进入以智能服务为特征的新时期.大量复杂、异构的智能设备相互协同,构成海量、智能、集成的智能家居应用.其中,情境感知服务根据服务对象所处情境的变化为其提供准确的服务,是智能家居应用的典型代表.目前,情境感知服务往往面向场景进行构建,其设备多样性和服务随需性给应用开发带来极大的挑战.开发者需要熟悉设备管理接口、进行接口调用和交互,同时,理解服务功能和质量需求,进行管理逻辑的编写.为了快速定制和开发情境感知服务,将知识图谱引入开发过程,提出一种智能家居情境感知服务的运行时建模与执行方法:首先,提出智能家居情境感知服务知识图谱概念模型,定义其情境中各种概念和关系;其次,提出智能家居情境感知服务知识图谱实例模型的构造与维护机制,通过运行时概念、关系实例表示情境知识;最后,提出基于知识推理的智能家居情境感知服务执行方法,通过知识推理自动执行设备功能.面向实际场景,构建智能家居原型系统.实验结果显示,该方法能够实现情境感知服务运行时建模与执行,其代码减少量超过90%.
2019, 30(11):3313-3325. DOI: 10.13328/j.cnki.jos.005862
摘要:随着人机对话的不断发展,让计算机能够准确地理解用户查询意图,对整个人机对话领域都有着重要意义.意图分类的主要目标是在人机对话的过程中判断用户的意图,提升人机对话系统的准确度与自然度.首先分析多个分类模型在意图分类任务上的优缺点.在此基础上,提出一种混合神经网络模型,综合利用多个深度网络模型的多样性输出.在输入特征预处理上,采用语言模型词向量,将语言模型拥有的语义挖掘能力应用到混合网络中,可以进一步提升模型的表达能力.所提出的混合神经网络模型相对于最好的基准模型在两份数据集上分别取得了2.95%和3.85%的性能提升.新模型在该数据上取得了最优的性能.
2019, 30(11):3326-3339. DOI: 10.13328/j.cnki.jos.005574
摘要:建立以受限玻尔兹曼机(restricted Boltzmann machine,简称RBM)为基石的深度网络模型,是深度学习研究的热点领域之一.Point-wise Gated受限玻尔兹曼机(point-wise gated RBM,简称pgRBM)是一种RBM的变种算法.该算法能够在含噪声的数据中自适应地找到数据中与分类有关的部分,从而实现较好的分类结果.假设一组数据中有噪声数据和干净数据,如何应用不含噪声的数据提升pgRBM的性能,是一个重要的研究问题.针对这一问题,首先,在传统的pgRBM基础上提出一种基于随机噪声数据与干净数据的Point-wise Gated受限玻尔兹曼机(pgRBM based on random noisy data and clean data,简称pgrncRBM)方法,其网络中与分类有关权值的初值是通过不含噪声的数据学习得到的,所以pgrncRBM在处理随机噪声数据时可以学习到更为"干净"的数据.在pgrncRBM中,与分类有关的数据与噪声都是使用RBM建模.如果噪声是图片,pgrncRBM就不能很好地去除噪声.Spike-and-Slab RBM(ssRBM)是一种处理实值数据的RBM变种模型,其定义两种不同类型的隐层用来学习实值数据的分布特性.因此,将ssRBM与pgRBM相结合,提出一种基于图像噪声数据与干净数据的Point-wise Gated受限玻尔兹曼机(pgRBM based on image noisy data and clean data,简称pgincRBM)方法.该方法使用ssRBM对噪声建模,其在处理图像噪声数据时可以学习到更为"干净"的数据.然后,通过堆叠pgrncRBM、pgincRBM和传统的RBM构建出深度网络模型,并探讨了权值不确定性方法在提出网络模型中的可行性.最后,在含噪声的手写数据集上进行MATLAB仿真实验.实验结果表明,pgrncRBM和pgincRBM都是有效的神经网络学习方法.
2019, 30(11):3340-3354. DOI: 10.13328/j.cnki.jos.005634
摘要:隐喻计算是自然语言处理领域中的重要问题.尝试以差异性计算为基础,结合语言、心理和认知的角度对英语隐喻识别进行深入分析和探索.对人类而言,隐喻识别是一个动态分类的过程,动态分类是从多个角度来度量事物之间的差异性.研究了如何模仿人类来获取概念的特征、选择分类角度、在特定分类角度下计算差异性,并进行了英语名词性隐喻识别的实验.该方法对隐喻/常规表达识别的准确率达到85.4%,实验结果表明,该方法是有效的.
2019, 30(11):3355-3363. DOI: 10.13328/j.cnki.jos.005559
摘要:表约束是一种外延的知识表示方法,每个约束在对应的变量集上列举出所有支持或禁止的元组.广义弧相容(generalized arc consistency,简称GAC)是求解约束满足问题应用最广泛的相容性.Simple Tabular Reduction(STR)是一类高效的维持GAC的算法.在回溯搜索中,STR动态地删除无效元组,降低了查找支持的开销,并拥有单位时间的回溯代价,在高元表约束上获得了广泛运用,并有大量基于STR的改进算法被提出,其中,元组集的压缩表示是目前研究较多的方法.同样基于动态维持元组集有效部分的思想,为STR提出一种检测并删除无效元组和为变量更新支持的算法,作用于原始表约束并拥有单位时间的回溯代价.实验结果表明,该算法在表约束上维持GAC的效率普遍高于现有的非基于压缩表示的STR算法,并且在一些实例上的效率高于最新的基于元组集压缩表示的STR算法.
2019, 30(11):3364-3381. DOI: 10.13328/j.cnki.jos.005579
摘要:排序合并连接是数据库系统一种重要的连接实现方式,比哈希连接有更广泛的应用.分布式环境下,数据分片、分布存储,面对昂贵的网络代价,进行高效排序合并连接的挑战巨大.传统策略首先针对连接数据进行排序,然后基于排好序的数据执行合并连接.这两部分操作均基于原始数据进行操作,通常情况下,原始连接数据存在无用数据块,这些数据块无需连接,但会增加额外开销,包括网络开销.随着数据量的增多,出现无用数据块的概率增大,额外开销随之增多.传统策略没有预先处理这些无用数据块.针对这个问题,提出一种分布式环境下基于剪枝的并行排序合并连接策略(parallel sort-merge join based on prune,简称Pr_PSMJ).其特点是,连接发生之前高效完成对连接对象无用数据块的剪枝处理,提高整体连接效率.基本思想是,根据连接对象对应的连接分区数据统计信息,构造一种双边邻接表(bilateral adjacency list,简称BAL),用来对连接数据中无用数据块进行剪枝,并保证最终连接结果的正确性;剪枝完成后,利用BAL计算出各个最佳本地连接执行点,并指导分区数据的迁移,使数据移动量最小;在连接阶段,由于BAL保证本地连接执行节点的独立性,因此能够轻松并行执行整个连接过程,并在每个连接点本地利用多核环境完成局部并行排序合并连接;最后,将局部结果合并成最终结果.由于Pr_PSMJ中的高效剪枝策略是在连接执行之前完成的,因此几乎适合任何合并连接操作,并且对于其他连接策略也有借鉴作用.给出了基于Pr_PSMJ的算法的正确性、效率性以及适应性分析,并且给出实验验证,证明了在分布式大数据量排序合并连接情况下,Pr_PSMJ相对于其他策略能够有效减少网络开销,并提高连接效率.
2019, 30(11):3382-3396. DOI: 10.13328/j.cnki.jos.005542
摘要:根据用户的历史评分数据为用户提供推荐的商品列表,是目前推荐系统研究的主流.研究者发现,随着用户参与度的不断提高,将反映用户偏好的评论文本与评分数据结合,可以进一步提高推荐的质量.提出了基于潜在特征同步学习和偏好引导的商品推荐方法,将评论文本的主题与用户的"打分偏好"进行关联,同步学习用户评论文本的潜在主题、评分矩阵的用户潜在因子和商品潜在因子,并将潜在主题作为用户个人偏好引导来约束推荐方法对商品的预测打分.该方法对推荐质量的优化主要体现在两个方面:一是在评论文本的潜在主题和评分数据的两种潜在因子之间建立映射关系,同步求解主题模型和矩阵分解模型;二是将从评论文本中学习得到的潜在主题作为用户对商品的个性偏好引入到矩阵分解中,进一步优化推荐方法.在来自Amazon网站的28组真实数据集上进行实验,以均方误差为评价指标,与已有的模型进行了对比分析.实验结果表明,该方法有效减少了推荐误差,与已有的TopicMF方法相比,均方误差在数据子集上最大减少了3.32%,平均减少了0.92%.
2019, 30(11):3397-3412. DOI: 10.13328/j.cnki.jos.005545
摘要:向微博用户推荐对其有价值和感兴趣的内容,是改善用户体验的重要途径.通过分析微博特点以及现有微博推荐算法的缺陷,利用标签信息表征用户兴趣,提出一种结合标签扩充与标签概率相关性的微博推荐方法.首先,考虑到大部分微博用户未给自己添加任何标签或添加标签过少,视用户发布微博为超边,微博中的词视为超点来构建超图,并以一定的加权策略对超边和超点进行加权,通过在超图上随机游走,得到一定数量的关键词,对微博用户标签进行扩充;然后,采用相关性标签权重加权方案构建用户-标签矩阵,利用标签之间的概率相关性,构造标签相似性矩阵,对用户-标签矩阵进行更新,使该矩阵既包含用户兴趣信息,又包含标签与标签之间的关系.以新浪微博公开API抓取的微博信息作为实验数据进行了一系列的实验和分析,结果表明,该推荐算法具有较好的效果.
2019, 30(11):3413-3426. DOI: 10.13328/j.cnki.jos.005571
摘要:残基相互作用网络比对,对于研究蛋白质结构与功能的关系具有重要意义.在基于网络拓扑信息进行网络比对的MAGNA算法基础上,将蛋白质的序列信息(即残基匹配度)引入到其优化函数中,确定拓扑信息和序列信息对比对的影响程度,提出适合于残基相互作用网络比对的SI-MAGNA算法.实验结果表明,SI-MAGNA算法比现有的基于网络拓扑信息的经典比对方法(GRAAL、MI-GRAAL、MAGNA和CytoGEDEVO)具有更高的边正确性(edge correctness,简称EC).最后,使用SI-MAGNA算法对来自不同耐热温度的生物的同源蛋白质进行网络比对和分析,探索蛋白质结构对其热稳定性的影响.
2019, 30(11):3427-3439. DOI: 10.13328/j.cnki.jos.005569
摘要:高精度室内定位有着广阔的市场前景.针对传统的WKNN室内定位方法所面临的在处理面积较大目标区域时,位置估计结果跳动跨度较大、精度不高等问题,提出了一种基于空间特征分区和前点约束的WKNN室内定位方法.该方法通过将面积较大的目标区域按其空间特征划分为多个分区,解决了指纹数据库无法实现全域覆盖的问题;又通过考虑行人在相邻时刻所处位置之间的空间约束关系,缩小了参考点的候选范围,很好地提升了位置估计的平顺性.大量真实环境下室内定位实验的结果表明,该方法可以有效地解决大面积目标区域内的室内定位问题;且与传统方法相比,定位精度大幅度提升.
2019, 30(11):3440-3456. DOI: 10.13328/j.cnki.jos.005655
摘要:由于数据流的动态性和流量负载转移,软件定义网络(software defined networking,简称SDN)需要频繁更新数据平面以优化网络性能.大多数已有路由更新策略首先根据网络当前流量状态确定目标路由配置,然后更新数据流的路由.然而,由于交换机基于TCAM(ternary content addressable memory)进行流表更新的速度较慢,导致路由更新的延迟通常较大.当网络规模大或网络拓扑结构经常变化时,路由更新的延迟可能更大.研究发现,大多数数据流的持续时间很短且整个网络的流量强度在一段时间后会发生变化.如果路由更新延迟过长,更新后的路由配置可能不再有效.为此,研究了SDN的实时路由更新问题,提出了延迟满足的路由选择和调度更新策略(delay satisfied route selection and updating scheme,简称DSRSU).与大多数现有研究不同,DSRSU同时从控制平面路径选择和数据平面的更新调度两方面来联合优化,降低路由更新的延迟.路径选择阶段只选择部分数据流进行路由更新;更新调度阶段通过建立更新关系图挖掘数据流的更新先后顺序,进一步加快路由更新速度.仿真分析结果表明,与现有几种路由更新策略相比,DSRSU能够在大幅度降低路由更新延迟的同时,达到与现有策略相似的网络性能.
2019, 30(11):3457-3468. DOI: 10.13328/j.cnki.jos.005577
摘要:近年来,基于室内定位的应用服务越来越普及,吸引了大量的研究工作.其中,基于WiFi信号指纹的室内定位技术发展尤为迅速.但无线信号传输易受环境影响,会导致WiFi信号指纹定位存在偏差.为了提高定位精度并减小环境因素带来的不利影响,提出了智能手机内置传感器辅助WiFi信号指纹定位的方法,即利用智能设备上内置的传感器如加速计、陀螺仪等采集数据,计算得到用户轨迹信息和轨迹可信度,将轨迹信息与信号指纹信息结合起来建立综合概率模型,进行位置匹配,确定最近参考点.实验结果表明,与经典WiFi信号指纹定位方法相比,利用传感器所估测的用户轨迹信息能够有效应对环境变化的影响,提高平均定位精度.
2019, 30(11):3469-3485. DOI: 10.13328/j.cnki.jos.005623
摘要:私人交通网络下的最短路径查询主要考虑路径长度、行驶时间等因素,而公共交通网络下的路径查询需要考虑路径上相邻的边的时间顺序约束以及路径的费用.研究了公共交通网络下3种查询:给定起点、终点、时间区间和费用上限,查找在时间区间内不超过费用上限的最早到达路径、最晚出发路径和最短耗时路径.首先给出一种Dijkstra变种算法Dijk-CCMTP,在此基础上给出3类查询的查询算法.然后提出一种高效的索引结构ACCTL(approximate cost constrained time labelling).ACCTL采用Dijk-CCMTP对图中的每个顶点预先计算部分从该顶点出发的和到达该顶点的基本路径.对于任意从起点s到终点d的查询,可以采用类似数据库表连接的方式从ACCTL中连接从a出发的和到达d的路径生成近似解,避免遍历原图搜索路径.ACCTL建立索引的时间复杂度是O(|V|·△max·|E|·(log|E|+△max)),其中,|V|表示顶点数,|E|表示边数,△max表示顶点的最大度数.实验验证ACCTL索引支持的查询速度比Dijkstra的变种算法的查询速度快2~3个数量级,并分析了影响建立索引时间和空间大小的因素.
2019, 30(11):3486-3502. DOI: 10.13328/j.cnki.jos.005575
摘要:Zhao等人提出了一个比特币投票协议,使得n个投票人能够通过投票决定两个候选人中的一个接受比特币资助.投票人首先通过秘密分享、承诺和零知识证明生成各自的投票,再通过比特币交易完成投票和比特币资助,保护了投票人的隐私.此文的工作支持n个投票人生成关于m个候选人的一般性投票,并通过智能合约完成了投票和以太币资助,同样不泄露投票人的隐私.同时,该智能合约不依赖门限签名等体制,更为高效,合约的主要业务逻辑也在检测模型工具中进行了检测.
2019, 30(11):3503-3517. DOI: 10.13328/j.cnki.jos.005573
摘要:k近邻(k-nearest neighbor,简称kNN)分类器在生物信息学、股票预测、网页分类以及鸢尾花分类预测等方面都有着广泛的应用.随着用户隐私保护意识的日益提高,kNN分类器也需要对密文数据提供分类支持,进而保证用户数据的隐私性,即设计一种支持隐私保护的k近邻分类器(privacy-preserving k-nearest neighbor classifier,简称PP-kNN).首先,对kNN分类器的操作进行分析,从中提取出一些基本操作,包括加法、乘法、比较、内积等.然后,选择两种同态加密方案和一种全同态加密方案对数据进行加密.在此基础上设计了针对基本操作的安全协议,其输出结果与在明文数据上执行同一方法的输出结果一致,且证明该协议在半诚实模型下是安全的.最后,通过将基本操作的安全协议进行模块化顺序组合的方式实现kNN分类器对密文数据处理的支持.通过实验,对所设计的PP-kNN分类器进行测试.结果表明,该分类器能够以较高效率实现对密文数据的分类,同时为用户数据提供隐私性保护.
2019, 30(11):3518-3534. DOI: 10.13328/j.cnki.jos.005539
摘要:针对代码复用的攻击与防御已成为网络安全领域研究的热点,但当前的防御方法普遍存在防御类型单一、易被绕过等问题.为此,提出一种基于运行特征监控的代码复用攻击防御方法RCMon.该方法在分析代码复用攻击实现原理的基础上定义了描述程序正常运行过程的运行特征模型RCMod,并提出了验证程序当前运行状态是否满足RCMod约束规则的安全验证自动机模型.实现中,通过直接向目标程序中植入监控代码,使程序运行到监控节点时自动陷入,并由Hypervisor实现运行特征库的构建和安全验证.实验结果表明,RCMon能够有效地防御已知的绝大部分代码复用攻击,平均性能开销约为22%.
2019, 30(11):3535-3548. DOI: 10.13328/j.cnki.jos.005556
摘要:研究保密意愿探测问题:Alice和Bob可以协同测试他们是否可以在某个理想区域共事,但不泄漏彼此的隐私信息.近年来,大部分的移动智能设备在出厂时都预装了位置感知设备,从而为开发者设计各种各样的提供位置识别与服务的应用软件提供了广阔的空间.然而很多情况下,用户间不愿意泄露自己的位置信息(或者活动范围),仅通过一比特的信息探知(或知晓)各参与方是否愿意在某个(便于彼此的)区域内共同做某件事情.保密意愿探测协议可以实现这样的功能,并且能够保证各参与方位置信息不会泄露.首先,设计了一个新的基于高阶剩余类判定性难解问题的云外包同态加密方案;然后,基于该方案构造了一个保密意愿探测协议,并在ideal/real模型下证明了协议的安全性.
2019, 30(11):3549-3566. DOI: 10.13328/j.cnki.jos.005835
摘要:妆容迁移是指把参考妆容迁移到素颜人脸上,并保持其上妆风格的一种任务.它提供了快速高效的候选妆容可视化的解决方案,得到了学术界和工业界的广泛关注.为了解决真实同人异妆数据的缺失,以及现有妆容迁移方法没有充分考虑人与人的五官差异而导致的迁移脸部结构丢失等问题,提出了一种多通路的分区域快速妆容迁移深度网络模型.具体而言,首先在人脸关键点检测的基础上,完成端到端的人脸校准;再利用通路差异的损失函数,根据眼影、唇膏、粉底的区域妆容特点优化网络;最后通过泊松融合、多通路的输出生成上妆结果.该模型具有存储空间小、生成速度快的优点,在保证人脸结构不变的同时,使得迁移后的眼影更均衡,唇膏色彩更保真,粉底迁移更精细.在国际通用VMU和DLMT美妆数据库上进行实验研究,结果表明,该方法取得了更协调的视觉效果、更快的上妆速度、更多样的同人异妆和异人同妆的迁移风格,优于对比方法.
2019, 30(11):3567-3577. DOI: 10.13328/j.cnki.jos.005570
摘要:在手绘草图检索(sketch-based image retrieval,简称SBIR)领域,引入一种手绘草图的新型检索模型.手绘草图与自然图片之间存在巨大的差异性,这是因为,与自然图片相比,手绘草图展现出高度抽象的视觉表达,用现有的方法对手绘草图进行特征提取,其产生的特征描述子对于手绘草图的内容无法进行有效地拟合;对于相同的物体,不同的人群用手绘草图描述方式和表达也存在巨大的差距,这就使得手绘草图-自然图片的匹配更加困难;同时,将手绘草图与自然图片映射到相同视觉域的工作,也是一项具有困难的任务.所以,手绘草图检索技术是公认的比较有挑战性的任务.提出一种将手绘草图与自然图片在多个层次上映射到同一视觉域的策略来解决跨域的问题.同时,引入多层深度融合卷积神经网络(multi-layer deep fusion convolutional neural network)的框架来训练并获得手绘草图和自然彩色图片的多层特征表达.在Flickr15k图像数据库进行检索实验,实验结果显示,多层深度融合卷积网络学习到的特征的检索精度超过了现有的手工特征以及由自然图片或者手绘草图训练出来的卷积神经网络(convolutional neural network,简称CNN)的特征.