摘要:
提出了一种基于程序功能标签切片的制导符号执行分析方法OPT-SSE.该方法从程序功能文档提取功能标签,利用程序控制流分析,建立各功能标签和程序基本块的映射关系,并根据功能标签在程序执行中的顺序关系生成功能标签执行流.针对给定的代码目标点,提取与之相关的功能执行流切片,根据预定义好的功能标签流制导规则进行符号执行分析,在路径分析过程中,及时裁剪无关的功能分支路径以提升制导效率.通过对不同的功能标签流进行分离制导符号执行分析,可避免一直执行某复杂循环体的情形,从而提高对目标程序的整体分支覆盖率和指令覆盖率.实验结果表明,通过对binutils、gzip、coreutils等10个不同软件中的20个应用工具上的分析,OPT-SSE与KLEE提供的主流搜索策略相比,代码目标制导速度平均提升到4.238倍,代码目标制导成功率平均提升了31%,程序指令覆盖率平均提升了8.95%,程序分支覆盖率平均提升了8.28%.
摘要:
安卓系统在移动端操作系统始终占据主导地位,在增强用户体验和提高程序性能的同时,其特有的事件驱动模型和多线程模型也造成了并发缺陷.并发程序中,线程调度的不确定性和难以再现性是并发缺陷检测困难的原因.现有技术主要在动态生成执行路径的基础上进行发生序(happens-before)分析,进而检测安卓应用的并发缺陷,但仍然存在低覆盖率、误报、漏报等问题.结合共享变量分析和约束求解方法实现了安卓应用数据竞争的检测,并实现了检测工具RaceDetector.该工具首先根据安卓系统的特性和数据竞争的定义,通过静态分析抽取相关信息,并进一步使用安卓共享变量分析来提高准确性和性能,继而进行可疑数据竞争分析,得出可疑的数据竞争集合;接着根据每一个可疑的数据竞争候选者,通过约束求解的方法在所有事件调度和线程调度解空间下识别发生序关系,并最终检测出真正的数据竞争.实验部分是从Google Play等来源收集了15个流行的应用APK文件作为数据集,RaceDetector平均报告了340个数据竞争,误报率为13%(44/340).与现有工具EventRacer(默认产生300随机事件触发应用执行,平均检测2个有害数据竞争)相比,RaceDetector能够解析全部源码,覆盖了所有线程调度和事件调度,平均检测出15个有害数据竞争.
摘要:
随着智能家居基础设施的不断发展,智能家居逐渐进入以智能服务为特征的新时期.大量复杂、异构的智能设备相互协同,构成海量、智能、集成的智能家居应用.其中,情境感知服务根据服务对象所处情境的变化为其提供准确的服务,是智能家居应用的典型代表.目前,情境感知服务往往面向场景进行构建,其设备多样性和服务随需性给应用开发带来极大的挑战.开发者需要熟悉设备管理接口、进行接口调用和交互,同时,理解服务功能和质量需求,进行管理逻辑的编写.为了快速定制和开发情境感知服务,将知识图谱引入开发过程,提出一种智能家居情境感知服务的运行时建模与执行方法:首先,提出智能家居情境感知服务知识图谱概念模型,定义其情境中各种概念和关系;其次,提出智能家居情境感知服务知识图谱实例模型的构造与维护机制,通过运行时概念、关系实例表示情境知识;最后,提出基于知识推理的智能家居情境感知服务执行方法,通过知识推理自动执行设备功能.面向实际场景,构建智能家居原型系统.实验结果显示,该方法能够实现情境感知服务运行时建模与执行,其代码减少量超过90%.
摘要:
建立以受限玻尔兹曼机(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都是有效的神经网络学习方法.
摘要:
表约束是一种外延的知识表示方法,每个约束在对应的变量集上列举出所有支持或禁止的元组.广义弧相容(generalized arc consistency,简称GAC)是求解约束满足问题应用最广泛的相容性.Simple Tabular Reduction(STR)是一类高效的维持GAC的算法.在回溯搜索中,STR动态地删除无效元组,降低了查找支持的开销,并拥有单位时间的回溯代价,在高元表约束上获得了广泛运用,并有大量基于STR的改进算法被提出,其中,元组集的压缩表示是目前研究较多的方法.同样基于动态维持元组集有效部分的思想,为STR提出一种检测并删除无效元组和为变量更新支持的算法,作用于原始表约束并拥有单位时间的回溯代价.实验结果表明,该算法在表约束上维持GAC的效率普遍高于现有的非基于压缩表示的STR算法,并且在一些实例上的效率高于最新的基于元组集压缩表示的STR算法.
摘要:
排序合并连接是数据库系统一种重要的连接实现方式,比哈希连接有更广泛的应用.分布式环境下,数据分片、分布存储,面对昂贵的网络代价,进行高效排序合并连接的挑战巨大.传统策略首先针对连接数据进行排序,然后基于排好序的数据执行合并连接.这两部分操作均基于原始数据进行操作,通常情况下,原始连接数据存在无用数据块,这些数据块无需连接,但会增加额外开销,包括网络开销.随着数据量的增多,出现无用数据块的概率增大,额外开销随之增多.传统策略没有预先处理这些无用数据块.针对这个问题,提出一种分布式环境下基于剪枝的并行排序合并连接策略(parallel sort-merge join based on prune,简称Pr_PSMJ).其特点是,连接发生之前高效完成对连接对象无用数据块的剪枝处理,提高整体连接效率.基本思想是,根据连接对象对应的连接分区数据统计信息,构造一种双边邻接表(bilateral adjacency list,简称BAL),用来对连接数据中无用数据块进行剪枝,并保证最终连接结果的正确性;剪枝完成后,利用BAL计算出各个最佳本地连接执行点,并指导分区数据的迁移,使数据移动量最小;在连接阶段,由于BAL保证本地连接执行节点的独立性,因此能够轻松并行执行整个连接过程,并在每个连接点本地利用多核环境完成局部并行排序合并连接;最后,将局部结果合并成最终结果.由于Pr_PSMJ中的高效剪枝策略是在连接执行之前完成的,因此几乎适合任何合并连接操作,并且对于其他连接策略也有借鉴作用.给出了基于Pr_PSMJ的算法的正确性、效率性以及适应性分析,并且给出实验验证,证明了在分布式大数据量排序合并连接情况下,Pr_PSMJ相对于其他策略能够有效减少网络开销,并提高连接效率.
摘要:
根据用户的历史评分数据为用户提供推荐的商品列表,是目前推荐系统研究的主流.研究者发现,随着用户参与度的不断提高,将反映用户偏好的评论文本与评分数据结合,可以进一步提高推荐的质量.提出了基于潜在特征同步学习和偏好引导的商品推荐方法,将评论文本的主题与用户的"打分偏好"进行关联,同步学习用户评论文本的潜在主题、评分矩阵的用户潜在因子和商品潜在因子,并将潜在主题作为用户个人偏好引导来约束推荐方法对商品的预测打分.该方法对推荐质量的优化主要体现在两个方面:一是在评论文本的潜在主题和评分数据的两种潜在因子之间建立映射关系,同步求解主题模型和矩阵分解模型;二是将从评论文本中学习得到的潜在主题作为用户对商品的个性偏好引入到矩阵分解中,进一步优化推荐方法.在来自Amazon网站的28组真实数据集上进行实验,以均方误差为评价指标,与已有的模型进行了对比分析.实验结果表明,该方法有效减少了推荐误差,与已有的TopicMF方法相比,均方误差在数据子集上最大减少了3.32%,平均减少了0.92%.
摘要:
向微博用户推荐对其有价值和感兴趣的内容,是改善用户体验的重要途径.通过分析微博特点以及现有微博推荐算法的缺陷,利用标签信息表征用户兴趣,提出一种结合标签扩充与标签概率相关性的微博推荐方法.首先,考虑到大部分微博用户未给自己添加任何标签或添加标签过少,视用户发布微博为超边,微博中的词视为超点来构建超图,并以一定的加权策略对超边和超点进行加权,通过在超图上随机游走,得到一定数量的关键词,对微博用户标签进行扩充;然后,采用相关性标签权重加权方案构建用户-标签矩阵,利用标签之间的概率相关性,构造标签相似性矩阵,对用户-标签矩阵进行更新,使该矩阵既包含用户兴趣信息,又包含标签与标签之间的关系.以新浪微博公开API抓取的微博信息作为实验数据进行了一系列的实验和分析,结果表明,该推荐算法具有较好的效果.
摘要:
由于数据流的动态性和流量负载转移,软件定义网络(software defined networking,简称SDN)需要频繁更新数据平面以优化网络性能.大多数已有路由更新策略首先根据网络当前流量状态确定目标路由配置,然后更新数据流的路由.然而,由于交换机基于TCAM(ternary content addressable memory)进行流表更新的速度较慢,导致路由更新的延迟通常较大.当网络规模大或网络拓扑结构经常变化时,路由更新的延迟可能更大.研究发现,大多数数据流的持续时间很短且整个网络的流量强度在一段时间后会发生变化.如果路由更新延迟过长,更新后的路由配置可能不再有效.为此,研究了SDN的实时路由更新问题,提出了延迟满足的路由选择和调度更新策略(delay satisfied route selection and updating scheme,简称DSRSU).与大多数现有研究不同,DSRSU同时从控制平面路径选择和数据平面的更新调度两方面来联合优化,降低路由更新的延迟.路径选择阶段只选择部分数据流进行路由更新;更新调度阶段通过建立更新关系图挖掘数据流的更新先后顺序,进一步加快路由更新速度.仿真分析结果表明,与现有几种路由更新策略相比,DSRSU能够在大幅度降低路由更新延迟的同时,达到与现有策略相似的网络性能.
摘要:
私人交通网络下的最短路径查询主要考虑路径长度、行驶时间等因素,而公共交通网络下的路径查询需要考虑路径上相邻的边的时间顺序约束以及路径的费用.研究了公共交通网络下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个数量级,并分析了影响建立索引时间和空间大小的因素.
摘要:
k
近邻(
k
-nearest neighbor,简称kNN)分类器在生物信息学、股票预测、网页分类以及鸢尾花分类预测等方面都有着广泛的应用.随着用户隐私保护意识的日益提高,kNN分类器也需要对密文数据提供分类支持,进而保证用户数据的隐私性,即设计一种支持隐私保护的
k
近邻分类器(privacy-preserving
k
-nearest neighbor classifier,简称PP-kNN).首先,对kNN分类器的操作进行分析,从中提取出一些基本操作,包括加法、乘法、比较、内积等.然后,选择两种同态加密方案和一种全同态加密方案对数据进行加密.在此基础上设计了针对基本操作的安全协议,其输出结果与在明文数据上执行同一方法的输出结果一致,且证明该协议在半诚实模型下是安全的.最后,通过将基本操作的安全协议进行模块化顺序组合的方式实现kNN分类器对密文数据处理的支持.通过实验,对所设计的PP-kNN分类器进行测试.结果表明,该分类器能够以较高效率实现对密文数据的分类,同时为用户数据提供隐私性保护.
摘要:
研究保密意愿探测问题:Alice和Bob可以协同测试他们是否可以在某个理想区域共事,但不泄漏彼此的隐私信息.近年来,大部分的移动智能设备在出厂时都预装了位置感知设备,从而为开发者设计各种各样的提供位置识别与服务的应用软件提供了广阔的空间.然而很多情况下,用户间不愿意泄露自己的位置信息(或者活动范围),仅通过一比特的信息探知(或知晓)各参与方是否愿意在某个(便于彼此的)区域内共同做某件事情.保密意愿探测协议可以实现这样的功能,并且能够保证各参与方位置信息不会泄露.首先,设计了一个新的基于高阶剩余类判定性难解问题的云外包同态加密方案;然后,基于该方案构造了一个保密意愿探测协议,并在ideal/real模型下证明了协议的安全性.
摘要:
妆容迁移是指把参考妆容迁移到素颜人脸上,并保持其上妆风格的一种任务.它提供了快速高效的候选妆容可视化的解决方案,得到了学术界和工业界的广泛关注.为了解决真实同人异妆数据的缺失,以及现有妆容迁移方法没有充分考虑人与人的五官差异而导致的迁移脸部结构丢失等问题,提出了一种多通路的分区域快速妆容迁移深度网络模型.具体而言,首先在人脸关键点检测的基础上,完成端到端的人脸校准;再利用通路差异的损失函数,根据眼影、唇膏、粉底的区域妆容特点优化网络;最后通过泊松融合、多通路的输出生成上妆结果.该模型具有存储空间小、生成速度快的优点,在保证人脸结构不变的同时,使得迁移后的眼影更均衡,唇膏色彩更保真,粉底迁移更精细.在国际通用VMU和DLMT美妆数据库上进行实验研究,结果表明,该方法取得了更协调的视觉效果、更快的上妆速度、更多样的同人异妆和异人同妆的迁移风格,优于对比方法.
摘要:
在手绘草图检索(sketch-based image retrieval,简称SBIR)领域,引入一种手绘草图的新型检索模型.手绘草图与自然图片之间存在巨大的差异性,这是因为,与自然图片相比,手绘草图展现出高度抽象的视觉表达,用现有的方法对手绘草图进行特征提取,其产生的特征描述子对于手绘草图的内容无法进行有效地拟合;对于相同的物体,不同的人群用手绘草图描述方式和表达也存在巨大的差距,这就使得手绘草图-自然图片的匹配更加困难;同时,将手绘草图与自然图片映射到相同视觉域的工作,也是一项具有困难的任务.所以,手绘草图检索技术是公认的比较有挑战性的任务.提出一种将手绘草图与自然图片在多个层次上映射到同一视觉域的策略来解决跨域的问题.同时,引入多层深度融合卷积神经网络(multi-layer deep fusion convolutional neural network)的框架来训练并获得手绘草图和自然彩色图片的多层特征表达.在Flickr15k图像数据库进行检索实验,实验结果显示,多层深度融合卷积网络学习到的特征的检索精度超过了现有的手工特征以及由自然图片或者手绘草图训练出来的卷积神经网络(convolutional neural network,简称CNN)的特征.
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:
北京勤云科技发展有限公司
京公网安备 11040202500063号