计算机研究与发展杂志 北大期刊 CSCD期刊 统计源期刊

计算机研究与发展 2017年第07期杂志 文档列表

计算机研究与发展杂志综述

SMT求解技术的发展及最新应用研究综述1405-1425

摘要：可满足性模理论（satisfiability modulo theories, SMT）是判定一阶逻辑公式在组合背景理论下的可满足性问题．SMT的背景理论使其能很好地描述实际领域中的各种问题，结合高效的可满足性判定算法，SMT在测试用例自动生成、程序缺陷检测、RTL（register transfer level）验证、程序分析与验证、线性逻辑约束公式优化问题求解等一些最新研究领域中有着突出的优势．首先阐述SMT问题的基础SAT（satisfiability）问题及判定算法；其次对SMT问题、判定算法进行了总结，分析了主流的SMT求解器，包括Z3，Yiees2，CVC4等；然后着重介绍了SMT求解技术在典型领域中的实际应用，对目前的研究热点进行了阐述；最后对SMT未来的发展前景进行了展望，目的是试图推动SMT的发展，为此领域的相关人员提供有益的参考．

计算机研究与发展杂志人工智能

基于图和改进K近邻模型的高效协同过滤推荐算法1426-1438

摘要：在互联网高速发展的今天，推荐系统已成为解决信息过载的有效手段，能够缓解用户在筛选感兴趣信息时的困扰，帮助用户发现有价值的信息．推荐系统中的协同过滤推荐算法，因其领域无关性及支持用户发现潜在兴趣的优点被广泛应用．由于数据的规模过大且稀疏的特点，当前协同过滤在算法实时性、推荐精确度等方面仍有较大提升空间．提出了GKCF方法，通过建立基于图的评分数据模型，将传统的协同过滤算法与图计算及改进的KNN算法结合．通过图的消息传播及改进的相似度计算模型对用户先进行筛选再做相似度计算；以用户一项目二部图的节点结构为基础，通过图的最短路径算法进行待评分项目的快速定位．在此基础上，进一步通过并行图框架对算法进行了并行化实现及优化．在物理集群环境下进行了实验，结果表明，与已有的协同过滤算法相比，提出的GK—CF算法能够很好地提高推荐的准确度和评分预测的准确性，并具有较好的算法可扩展性和实时性能．

一种基于差分隐私保护的协同过滤推荐方法1439-1451

摘要：由于推荐系统需要利用大量用户数据进行协同过滤，会给用户的个人隐私带来相当大的风险，如何保护隐私数据成为推荐系统当前面临的重大挑战．差分隐私作为一种新出现的隐私保护框架，能够防止攻击者拥有任意背景知识下的攻击并提供有力的保护．针对推荐系统中的隐私保护问题，提出一种满足差分隐私保护的协同过滤推荐算法．首先，构建用户和项目的潜在特征矩阵，有效降低数据稀疏性；然后，采用目标扰动方法对矩阵中添加满足差分隐私约束的噪声得到噪矩阵分解模型；通过随机梯度下降算法最小化相关联的正则化平方误差函数来获取模型中的参数；最后，应用差分隐私矩阵分解模型进行评分预测，并在MovieI。ens和Nefflix数据集上对算法的有效性进行评价．实验结果证明：所提出方法的有效性能够在有限的精度损失范围内进行推荐并保护用户隐私．

基于Spark的Top-k对比序列模式挖掘1452-1464

摘要：对比序列模式（distinguishing sequential pattern, DSP）指在目标类序列集合中频繁出现，而在非目标类序列集合中不频繁出现的序列．对比序列模式能够描述2个序列集合间的差异，有着广泛的应用，例如：构建序列分类器，识别DNA序列的生物特征，特定人群行为分析．与挖掘满足支持度阈值要求的对比序列模式相比，挖掘对比度top—k对比序列模式能避免用户设置不恰当的支持度阈值．因而，更易于用户使用．但是现有的top—k对比序列模式挖掘算法难以处理大规模序列数据．对此，设计了一种基于Spark的top—k对比序列模式并行挖掘算法，称为SP—kDSP—Miner．此外，为了提高SP—kDSP—Miner的效率，针对Spark结构的特点，设计了候选模式生成策略和若干剪枝策略，以及候选模式对比度的并行计算方法．通过在真实数据集与合成数据集上的实验，验证了SP—kDSP—Miner的有效性、执行效率和可扩展性．

基于邻居选取策略的人群定向算法1465-1476

摘要：人群定向是广告推荐系统中的一种重要技术，它是通过分析种子人群的行为数据，找出潜在的目标人群，而现有人群定向算法大多依赖于传统的协同过滤推荐算法．由于传统的协同过滤算法具有推荐精度低和抗攻击能力较弱的问题，为了解决这些问题，提出了一种基于邻居选取策略的人群定向算法．1）通过用户行为相似，动态选择出与种子人群具有相似行为的用户；2）以用户特征和用户行为作为邻居选取的依据，通过用户相似度从行为相似人群中选择出每个种子用户的邻居，并将所有的相似邻居作为候选人群；3）通过基于邻居选取策略的人群定向算法，从候选人群中择出潜在的目标用户，以完成人群定向．实验结果表明：与现有方法相比，该方法不仅提高了人群定向的精度，而且也增强了系统的抗攻击能力．

一种基于决策森林的单调分类方法1477-1487

摘要：单调分类问题是特征与类别之间带有单调性约束的有序分类问题．对于符号数据的单调分类问题已有较好的方法，但对于数值数据，现有的方法分类精度和运行效率有限．提出一种基于决策森林的单调分类方法（monotonic classification method based on decision forest，MCDF），设计采样策略来构造决策树，可以保持数据子集与原数据集分布一致，并通过样本权重避免非单调数据的影响，在保持较高分类精度的同时有效提高了运行效率，同时这种策略可以自动确定决策森林中决策树的个数．在决策森林进行分类时，给出了决策冲突时的解决方法．提出的方法既可以处理符号数据，也可以处理数值数据．在人造数据集、UCI及真实数据集上的实验数据表明：该方法可以提高单调分类性能和运行效率，缩短分类规则的长度，解决数据集规模较大的单调分类问题．

基于贝叶斯网的评价数据分析和动态行为建模1488-1499

摘要：随着web2．0的不断普及和电子商务应用的迅速发展，大规模的在线评价数据不断产生，使用户行为数据分析和用户行为建模成为可能，具有重要意义．考虑到用户评价数据和评价行为的动态性，提出以带有隐变量的贝叶斯网作为各属性间依赖关系及其不确定性表示的基本框架，构建既能刻画用户评价数据中各属性间相互依赖的不确定性、也能描述用户行为动态性的评价行为模型．首先，以贝叶斯信息标准（BIC）分值作为模型与数据拟合度的度量标准，提出基于打分搜索方法来构建各时间片的隐变量模型，并给出基于期望最大（EM）算法的隐变量取值填充方法；其次，基于条件互信息和时序的不可逆性，提出了相邻时间片间隐变量模型的构建方法．建立在MovieLens数据集上的实验结果验证了提出的动态用户行为建模方法的高效性及有效性．

2017年《计算机研究与发展》专题（正刊）征文通知——边缘计算1499-1499

摘要：伴随着计算机硬件和网络技术的发展，计算模式从大型主机计算演进到C／S模式的网络计算，再到云计算．然而，基于云计算的电子商务平台、评级服务、搜索引擎、在线社交网络等集中式服务采集个人在线行为和社交数据而易导致隐私泄露；从用户到云的完全授权的应用程序和系统控制，

不完备多粒度决策系统的局部最优粒度选择1500-1509

摘要：粒计算是知识表示和数据挖掘的一个重要方法．从粒计算来看，一个粒是由多个比较小的颗粒组成的更大的一个单元．在许多实际应用中，由于不同标记尺度对数据集进行分割会得到不同层次的粒度，许多人在用粒计算解决问题时自然而然地考虑不同层次的粒度问题．这就促使思考如何选择一个合适的粒度层次来解决问题．围绕不完备多粒度决策系统，研究了基于局部最优粒度的规则提取方法．1）介绍了不完备多粒度决策系统的概念；2）在协调的不完备多粒度决策系统中定义了最优粒度和局部最优粒度、介绍了基于局部最优粒度的属性约简和规则提取方法，在不协调的不完备多粒度决策系统中引入了广义决策、定义了广义最优粒度和广义局部最优粒度，并给出了基于广义局部最优粒度的属性约简和规则提取方法；3）给出了在公开的数据集上的实验结果．

2015年《计算机研究与发展》高被引论文TOP101509-1509

计算机研究与发展杂志计算机网络与信息安全

基于格的前向安全无证书数字签名方案1510-1524

摘要：无证书签名方案利用密钥生成中心与用户共同生成签名密钥的方式，解决了传统的基于身份的数字签名方案中存在的密钥托管问题．目前，针对无证书签名方案的研究还存在3点可以改进的地方：1）已有的基于随机格构建的无证书签名方案，虽然具有后量子安全性，但都是建立在随机预言模型下，尚无针对标准模型的相关研究；2）已有的格基无证书签名方案大多只考虑外部敌手，缺乏抵御不诚实用户攻击的能力；3）已有的无证书签名方案均需要保证用户密钥是绝对安全的，无法解决密钥泄露问题．针对这3点不足，在随机预言模型下的前向安全的无证书格基签名方案的基础上，首次提出了标准模型下可证明安全的基于随机格的前向安全无证书数字签名方案，并在不引入第三方的前提下同时解决了密钥泄露和密钥托管问题．在面对不诚实的用户和恶意密钥生成中心2类强敌手的情况下，利用小整数解SIS假设证明了所提出的方案具有适应性选择消息、选择身份攻击下的前向安全强不可伪造性．

Crypton算法的不可能差分分析1525-1536

摘要：Crypton算法是基于Square算法设计的SPN结构类密码算法，由于其具备良好的软硬件性能而引起了广泛的关注．对Crypton分组密码算法在不可能差分分析下的安全性进行了研究．通过分析Crypton算法扩散层的性质，指出了现有7轮Crypton算法不可能差分分析中存在的问题，结合快速排序、分割攻击与早夭技术对7轮Crypton算法的不可能差分分析进行了改进，降低了其数据复杂度与时间复杂度；同时，通过并行使用4条不可能差分区分器，结合密钥扩展算法的性质给出了7轮Crypton算法的多重不可能差分分析结果，恢复了算法的主密钥；最后，在7轮Crypton算法的不可能差分分析的基础上向后拓展1轮，给出了8轮Crypton-256算法的不可能差分分析，恢复了其主密钥，其数据复杂度为2如。个选择明文，时间复杂度为2^214次8轮Crypton加密，存储复杂度为2^154.4 B．研究结果表明：结合算法的性质及多种技术给出了Crypton算法目前最优的不可能差分分析结果．

针对数据泄漏行为的恶意软件检测1537-1548

摘要：高级可持续威胁（advanced persistent threat, APT）级网络攻击对企业和政府的数据保护带来了极大的挑战．用Oday漏洞制作恶意软件来进行攻击是APT级网络攻击的常用途径，传统基于特征的安全系统很难检测这类攻击．为了检测泄漏敏感信息的恶意软件，首先分析已出现的APT恶意软件，描绘出窃取信息的攻击步骤，以此为基础提出1个针对数据泄漏行为的恶意软件检测方案用于检测同种攻击类型的恶意软件．该方案结合异常检测和误用检测，对被保护的主机和网络进行低开销的持续监控，同时提出一系列推断规则来描述攻击步骤中可以观察到的高级恶意事件．一旦监控到可疑事件，进一步收集主机和网络的低级行为，根据推断规则关联低级行为和高级恶意事件，据此重构窃取信息的攻击步骤，从而检测出攻击的存在．通过仿真实验验证了该方案的有效性．

非加密方法安全计算集合包含关系1549-1556

摘要：针对已存在的安全计算集合包含关系的协议大多基于多次公钥加密算法，计算复杂性较高，并且不能公开计算，应用受限的问题．提出了2种非加密安全计算集合包含关系的协议．协议1首先将集合包含问题转化为向量内积问题；然后利用数学难解问题解决了此问题；最后针对不可信第三方存在的应用场景，利用双线性对和数学难解问题给出了可公开判断集合包含关系的实用性协议2．协议1和协议2都没有使用任何公钥加密方法，避免了前人方案中繁琐的公私钥产生和加解密过程以及多次匹配查找，因此更加高效而简洁．此外，协议2开拓了保密判断集合关系的新应用场景．

计算机研究与发展杂志软件技术

使用锁分配图动态检测混合死锁1557-1568

摘要：死锁难以暴露、重演和调试．一旦发生，将导致多线程程序响应时间增长、吞吐量下降甚至宕机崩溃．现有死锁检测技术每次只能检测一个互斥锁死锁．为一次性检测由多个线程和多个互斥锁或读写锁造成的所有类型死锁，首先提出混合锁分配图的概念和构建方法，然后提出一种利用混合锁分配图动态检测混合死锁的方法．通过劫持所有互斥锁和读写锁的加锁解锁操作，以动态构建和实时更新一个反映目标程序同步状态的混合锁分配图．通过在锁分配图上检测环并判定该环是否为死锁环来检测死锁．当检测到死锁时，输出死锁信息来辅助调试．死锁检测实验、性能影响实验和可扩展性实验结果表明：该方法成功检测出所有13个共5种类型的死锁缺陷，检测能力强；给openldap-2．2．20带来至多10．15％的性能下降幅度，对目标程序造成的性能影响较小；性能开销随线程数目指数级增大而平缓增长，扩展性良好．

基于QEMU的动态函数调用跟踪1569-1576

摘要：函数调用一直是Linux内核分析研究领域的重点．获得函数调用信息主要有2种方法：静态分析和动态分析．动态跟踪方法可实时和准确地获取函数调用关系信息，在分析和调试软件程序时有极大的帮助作用．针对现有工具存在跟踪信息不全面、需要编译选项支持等不足，基于开源的OEMU模拟器，设计并实现了支持多种CPU平台的通用动态函数调用跟踪工具，可在x86_32，x86_64，ARM共3种体系架构上动态跟踪包括Linux内核启动过程在内的函数调用和返回信息．该工具在程序运行时截获调用和返回的指令，并记录相关信息，利用此种指令只会在QEMU翻译块的最后一条出现的性质，减少检查指令的数量，提高运行效率；可不依赖源代码，只依据函数符号表进行函数调用关系分析．实验结果表明：跟踪和分析结果与源代码行为一致，相比于S2E提升了分析性能和支持的CPU平台种类，且能更好地扩展至其他平台．

Web数据库top-k多样性关键字查询推荐方法1577-1591

摘要：Web数据库用户通常使用他们熟知的关键字表达查询意图，这可能导致获取的结果不能很好满足其查询需求，因此为他们提供top—k个与初始查询语义相关且多样化的候选查询有助于用户扩展知识范围，从而更准确完善地表达其查询意图．提出一种top—k多样性关键字查询推荐方法．1）利用不同关键字在查询历史中的同现频率和关联关系评估关键字之间的内耦合和间耦合关系；2）根据关键字之间的耦合关系构建语义矩阵，进而利用语义矩阵和核函数方法评估不同关键字查询之间的语义相关度．为了快速返回top—k个与初始查询相关且多样性的候选查询，根据查询之间的语义相关度，利用概率密度函数分析查询的典型程度，并利用近似算法从查询历史中找出典型查询．对于所有的典型查询，从中选出少数代表性查询，根据其他典型查询与代表性查询之间的语义相关度，为每个代表性查询构建相应的查询序列；当一个新的查询到来时，评估其与代表性查询之间的语义相关度，然后利用阈值算法（threshold algorithm，TA）在预先创建的查询序列上快速选出top—k个与给定查询语义相关的多样性候选查询．实验结果和分析表明：提出的关键字之间耦合关系计算和查询之间的语义相关度评估方法具有较高准确性，top—k多样性选取方法具有较好效果和较高执行效率．

一种基于Spark的多路空间连接查询处理算法1592-1602

摘要：针对云环境下空间数据连接查询处理问题，提出了一种基于Spark的多路空间连接查询处理算法BSMWSJ．该算法采用网格划分方法将整个数据空间划分成大小相同的网格单元，并将各类数据集中的空间对象，根据其空间位置划分到相应的网格单元中，不同网格单元中的空间数据对象进行并行连接查询处理．在多路空间连接查询处理过程中，采用边界过滤的方法来过滤无用数据，即通过计算前面连接操作候选结果的MBR来过滤后续连接数据集，从而过滤掉无用的连接对象，减少连接对象的多余投影与复制，并采用重复避免策略来减少重复结果的输出，从而进一步减少后续连接计算的代价．合成数据集和真实数据集上的大量实验结果表明：提出的多路空间连接查询处理算法在性能上明显优于现有的多路连接查询处理算法．