首页期刊导航|计算机学报
期刊信息/Journal information
计算机学报
计算机学报

高文

月刊

0254-4164

cjc@ict.ac.cn

010-62620695

100190

中国科学院计算技术研究所（北京2704信箱）

计算机学报/Journal Chinese Journal of ComputersCSCD北大核心CSTPCDEI
查看更多>>本刊是中国计算机领域的有代表性学术刊物，作为一种科学研究档案，代表了计算机领域各个研究阶段的水平。本刊被《工程索引》（美国）、《科学文摘》（英国）、《数学文摘》（美国）、《科技文献速报》（日本）、《文摘杂志》（俄罗斯）等多种权威系统收录。是科技部科技信息研究所科技论文统计源期刊、中国科学引文数据库来源期刊。
正式出版
收录年代

    异常信息敏感的框架API生命周期模型构造

    燕季薇黄进豪杨恒钦严俊...
    1989-2008页
    查看更多>>摘要：大型软件系统的实现依赖于底层框架或第三方库,但这些复杂的框架/库代码在演化升级时往往独立于其调用者,为上层软件的质量保障带来挑战.例如,框架/库代码演化时新增和删除API、更改API的代码语义等行为会导致框架/库代码的不同版本之间不兼容,进而在上层应用开发者更新版本时,影响应用代码的正确性.为应对这一问题,需精准提取框架/库代码API的演化过程,形成演化报告,协助上层应用开发者选择兼容的版本或快速进行代码适配.其中,框架/库代码API的演化过程分析对应着框架API生命周期模型构造.现有工作中的API生命周期模型主要关注API的存在性变动,而未考虑特定代码语义变更对开发者的影响,特别是异常相关代码带来的语义变更,给上层软件系统带来隐患.为此,本文采用面向Java字节码的静态分析方法,识别框架API中的异常抛出行为并为其生成异常摘要报告,通过多轮流式匹配策略获取异常信息的变更情况,最终为框架/库代码构造异常信息敏感的API生命周期模型.该方法:(1)通过控制依赖语句切片提取异常抛出语句的关键触发条件,采用参数推断策略将局部变量的约束条件转换为仅与外部输入参数相关的异常前断言,并基于自底向上的摘要传递实现跨过程异常摘要提取;(2)通过关键信息精准匹配和自适应模糊匹配策略,分析异常摘要信息的新增、删除和修改情况,最终得到异常敏感的API生命周期模型(共涉及七种API变更形式).基于该方法,实现了基于Java字节码分析的API生命周期提取工具JavaExP.与现有最新方法相比,JavaExP的异常摘要信息提取准确性(F1值)提高了 67％,分析用时减少了 87％.对真实项目的API生命周期演化分析表明,与异常不敏感的API生命周期模型相比,采用异常敏感的模型时,API发生变动的比例提高了 18％.在75,433个被分析的API中,约有20％API的异常抛出行为至少发生过一次改变,这些API共涉及超过七千多处独立的异常变更.在多个项目上的分析结果表明,异常敏感的模型构造能够更加精准地描述API的演化过程.

    静态分析代码演化Java异常摘要API生命周期

      原文链接:
    • 万方数据
    • 维普

    面向内存数据库的类字典树索引综述与性能比较

    储召乐罗永平金培权
    2009-2034页
    查看更多>>摘要：如何快速存取海量数据是大数据时代数据库系统面临的重大挑战.利用大内存构建内存数据库系统是实现大数据实时存取的可行途径.在此背景下,用于加速内存数据存取的内存数据库索引成为近几年国内外的研究热点.但是,内存数据库索引也面临着诸多挑战.以常见的内存B+树索引为例,第一个问题是索引的空间效率较低,这是因为内存B+树索引的节点内部存在较大的空间浪费;第二个问题是索引的查询复杂度较高,B+树的查询复杂度受限于数据规模,随着数据规模的扩张,索引的搜索效率也会下降;第三个问题是变长数据支持弱,B+树对于变长键的支持比较差,往往难以适应实际应用的需要.近年来,由于字典树具有空间代价低、查询效率与数据规模无关、支持变长键等优点,逐步成为了内存数据库索引研究中的一个主要方向.本论文围绕面向内存数据库的类字典树索引,首先介绍了字典树的概念、特点和历史,然后系统梳理和总结了类字典树索引的现状和最新进展,之后提出了一种全新的分类方法对类字典树索引进行了分类.在此基础上,论文对主流的六种类字典树索引进行了实验,在多个数据集和负载上进行了性能对比,并基于实验结果讨论了类字典树索引的设计和使用建议,最后展望了未来类字典树索引的发展方向.

    内存数据库字典树索引性能对比

      原文链接:
    • 万方数据
    • 维普

    资源失配时低代价的数据与计算密集型服务重配

    周长兵李小翠王煜炜王亚沙...
    2035-2058页
    查看更多>>摘要：随着边缘计算的广泛应用,近年来在网络边缘侧激增了一些延迟敏感的用户请求,这些应用对边缘网络中物联网设备提供的资源提出了较高的服务质量(Quality of Service,QoS)需求,例如严格的地理空间约束、时延/能量及其他资源约束.物联网设备提供的功能通常被封装为运行在边缘节点上的服务,用户请求可以通过组合数据和/或计算密集型的物联网服务来实现.考虑到物联网设备的资源稀缺性以及用户请求的在线持续部署和潜在长期执行特征,边缘服务运行期间对物联网设备资源的占用和释放导致边缘网络中资源动态变化.由于物联网设备的资源通常难以得到有效补充,且消耗差异可能较大,有些设备可能会过载,导致在当前时间点适配的物联网服务,在随后时间点可能难以适配用户请求,并导致QoS降级.针对边缘网络高负载时新请求持续部署导致特定强约束难以满足的挑战,本文开展资源失配时低代价的服务重配研究,提出了一种资源高效的服务重配方法,旨在通过服务迁移技术重调度物联网设备所提供的服务,以满足更多具有一定QoS约束的用户请求.基于上海电信基站数据集进行了大量实验,实例验证本文方法的有效性.实验结果表明,本文所提方法在满足用户服务请求时延约束、降低物联网设备能量消耗、提高边缘网络资源利用效益等方面表现均优于对比技术.

    数据与计算密集型服务资源利用效益服务重配服务迁移边缘网络

      原文链接:
    • 万方数据
    • 维普

    智能模糊测试综述:问题探索和方法分类

    王琴应许嘉诚李宇薇潘祖烈...
    2059-2083页
    查看更多>>摘要：随着近年来软件系统规模以及复杂性的增加,安全漏洞数量持续增长、影响面逐步扩大,全球安全形势依然严峻.针对该问题,学术界和工业界致力于研究高效的漏洞挖掘技术,提前发现和修复潜在的漏洞.其中模糊测试作为先进的漏洞挖掘技术之一,吸引了学术界和工业界的广泛关注.为了进一步提高漏洞挖掘的能力,研究人员提出了智能模糊测试,即利用人工智能和程序分析等技术作为辅助,从而实现对复杂软件系统更高效的测试和分析并智能引导漏洞挖掘方向.本文回顾了近八年来智能模糊测试研究进展,提出了一个通用模糊测试流程模型和问题导向的智能模糊技术分类方法,从优化测试输入生成、提高测试效率以及增强测试预言机三个方面总结了当前智能模糊测试的优势和不足之处,最后对智能模糊测试面临的挑战和未来研究方向进行展望和总结.

    模糊测试软件与系统安全漏洞挖掘人工智能程序分析

      原文链接:
    • 万方数据
    • 维普

    面向Select和Sort的数据库算子缓存的设计与实现

    蔡万里王新硕胡卉芪蔡鹏...
    2084-2103页
    查看更多>>摘要：缓存是数据库中提高查询性能的一种常用技术.目前,现有数据库缓存主要有两个方向:查询结果缓存和存储层块缓存.查询结果缓存是利用数据库查询执行的最终结果或中间结果(如子查询),而存储层块缓存则缓存查询涉及的底层数据块.本文从另外一个角度"缓存中含有的计算量"来重新审视缓存在查询优化中的应用,并以此为基础进一步划分数据库缓存方式.在查询执行过程中,数据库查询被转换成一系列操作(例如选择、排序等)的集合,而算子对应操作.查询处理中算子输出的数据为中间结果,含有部分计算量,我们将这部分数据进行缓存并加以利用.我们将这种缓存部分计算量的缓存方式称为算子缓存,即缓存每个操作执行后的结果.由于不同查询之间可能会存在相同算子,对相近数据执行相同计算,因此利用算子缓存加速查询执行性能具有相当大的潜力.本文的新颖之处在于从缓存含有的计算量角度出发,提出并研究算子缓存如何在查询优化中应用.本文以Filter、Sort算子为例,针对缓存复用提出了一种基于语义树的匹配算法,用于快速匹配缓存中的结果集.同时,针对复用缓存可能劣化查询性能的情况,提出使用基于成本的代价优化器防止使用缓存劣化查询性能.最后,本文基于开源分析型数据库ClickHouse实现了 Filter、Sort算子缓存的原型,并对提出的算子缓存方案进行了大量的实验测试.结果表明,相比块缓存、物化视图方式,本文提出的算子缓存方案在本地SSD部署下最大能够分别提升9倍以及1.5倍的查询响应速度,在云环境下部署能够分别提升30倍以及2倍的查询响应速度.

    数据库查询执行查询优化算子缓存联机分析处理

      原文链接:
    • 万方数据
    • 维普

    MBO:基于多目标平衡优化的监控视频浓缩

    张云佐朱鹏飞
    2104-2115页
    查看更多>>摘要：视频浓缩可在极大压缩视频长度的同时完整保留目标运动信息,在学术界和工业界受到广泛关注.然而现有浓缩方法无法精准保留目标之间的交互行为,且难以平衡压缩和碰撞,严重阻碍了视频浓缩的性能提升和实际应用.为此,本文提出了一种基于多目标平衡优化的监控视频浓缩方法(Multi-Objective Balance Optimization,MBO).首先,提出了一种基于目标交互帧数量和动态阈值对比的交互行为判断方法,用以组建多目标单元,结合目标在每帧的移动方向并采用动态阈值提升交互行为判断的准确性;其次,定义了碰撞矩阵和插入位置占比率,分别记录目标碰撞和插入位置深浅;然后,提出了一种压缩与碰撞的动态平衡方法,以优化重排目标,能在极大程度缩短视频长度的同时减少产生的目标碰撞;最后,融合视频背景和重排后的目标生成浓缩视频.VISOR、CAVIAR和KTH等多个数据集上的实验结果表明,相较于当前主流方法,本文所提方法保留交互行为的F-score提升高达0.472,并且能够有效平衡压缩和目标碰撞.

    视频浓缩多目标平衡优化交互行为

      原文链接:
    • 万方数据
    • 维普

    自适应双坐标系的差分进化算法求解混合变量优化问题

    周新宇黄君洪彭虎王晖...
    2116-2140页
    查看更多>>摘要：如何设计求解混合变量优化问题(Mixed-variable Optimization Problems,MVOPs)的相关算法,是计算机算法设计与分析领域中的一个重要研究方向.该问题的求解难点在于需同时优化连续型和离散型决策变量,目前进化算法(Evolutionary Algorithms,EAs)是求解该问题的一种有效手段.然而,现有的相关EAs忽略了问题变量之间的相关性,导致算法性能还存在一定不足.为此,本文从变量相关性角度出发,提出了一种自适应双坐标系的差分进化算法来求解MVOPs.首先,利用种群的协方差矩阵信息来构建特征坐标系,实现在特征坐标系下执行算法的相关操作,以松弛连续变量与离散变量之间的相关性;其次,为避免种群多样性丢失,仍保留了原坐标系,并设计了一种自适应策略来应用特征坐标系和原坐标系,以发挥双坐标系的优势;最后,为提高离散变量的优化效果,专门设计了一种基于离散变量相关性的局部搜索策略,以增强算法的整体性能.为验证本文方法性能,在一套包含28个测试函数的通用测试集上进行了大量实验,与5种求解MVOPs的知名EAs进行了对比,结果表明本文方法有更好性能.此外,在一个实际MVOP上,即焊接梁设计问题,本文方法能取得目前已知最好解.本文方法为计算机算法设计和分析领域的相关工作提供了新的思路.

    混合变量差分进化变量相关性特征坐标系双坐标系

      原文链接:
    • 万方数据
    • 维普

    一种多粒度空间的快速构建方法

    赵凡张清华吴成英谢秦...
    2141-2162页
    查看更多>>摘要：粒计算是模拟人脑多粒度认知模式处理复杂问题的一种方法.模糊商空间理论作为粒计算的一种典型模型,将复杂问题渐进式粒化成为分层递阶的多粒度空间,从而实现层次化的求解.然而,面对海量高维数据,现有模糊商空间模型通过模糊相似关系构建多粒度空间的效率将大幅降低.一方面,模糊相似关系需要计算数据空间中任意两个对象之间的相似性,不利于处理体量大的数据集;另一方面,模糊相似关系包含大量冗余信息,导致后续步骤中存在大量的冗余计算.因此,本文基于2近邻模糊关系,提出了多粒度空间的快速构建方法,在保证面向下游分类任务时性能不下降的前提下,极大地提升了多粒度空间构建效率.首先,基于k近邻算法提出k近邻模糊关系,并分析证明其关键性质;然后,面向多粒度空间构建任务,对k近邻模糊关系进行参数分析,从理论上证明k取2时即可包含数据空间中全部有效信息;随后,定义了最近邻和次近邻两阶段的有效位置数,提出了模糊相似关系有效值和有效位置提取算法,多粒度空间构建效率提升了 75％左右.最后,通过在9个UCI数据集、3个UKB数据集、3个图像数据集和3个文本数据集上的相关实验,验证了该算法构建多粒度空间的高效性、正确性以及面向下游分类任务的有效性、稳定性和显著性.

    粒计算多粒度空间k近邻模糊关系模糊商空间

      原文链接:
    • 万方数据
    • 维普

    NTRU格基密钥封装方案GPU高性能实现

    李文倩沈诗羽赵运磊
    2163-2178页
    查看更多>>摘要：随着量子计算技术的发展,传统加密算法受到的威胁日益严重.为应对量子计算时代的挑战,各国正积极加强后量子密码算法的实现和迁移部署工作.由于NTRU密码方案具有结构简洁、计算效率高、尺寸较小、无专利风险等优点,因此NTRU格基密钥封装算法对于后量子时代的密码技术储备和应用具有重要意义.同时,图形处理器(Graphics Processing Unit,GPU)以其强大的并行计算能力、高吞吐量、低能耗等特性,已成为当前高并发密码工程实现的重要平台.本文给出后量子密码算法CTRU/CNTR的首个GPU高性能实现方案.对GPU主要资源占用进行分析,我们综合考虑并行计算、内存访问、数据布局和算法优化等多个方面,采用一系列计算和内存优化技术,旨在并行加速计算、优化访存、合理占用GPU资源以及减少I/O时延,从而提高本方案的计算能力和性能.本文的主要贡献在于以下几个方面:首先,针对模约减操作,使用NVIDIA并行指令集实现,有效减少所需指令条数;其次,针对耗时的多项式乘法模块,采用混合基NTT,并采用层融合、循环展开和延迟约减等方法,加快计算速度;此外,针对内存重复访问和冲突访问等问题,通过合并访存、核函数融合等优化技术,实现内存的高效访问;最后,为实现高并行的算法,设计恰当的线程块大小和数量,采用内存池机制,实现多任务的快速访存和高效处理.基于NVIDIA RTX409 0平台,本方案CTRU768实现中密钥生成、封装和解封装的吞吐量分别为每秒1170.9万次、926.7万次和315.4万次.与参考实现相比,密钥生成、封装和解封装的吞吐量分别提高了 336倍、174倍和128倍.本方案CNTR768实现中密钥生成、封装和解封装的吞吐量分别为每秒1117.3万次、971.8万次和322.2万次.与参考实现相比,密钥生成、封装和解封装的吞吐量分别提高了 329倍、175倍和134倍;与开源Kyber实现相比,密钥生成、密钥封装和密钥解封装的吞吐量分别提升10.84～11.36倍、9.49～9.95倍和5.11～5.22倍.高性能的密钥封装实现在大规模任务处理场景下具有较大的应用潜力,对保障后量子时代的信息和数据安全具有重要意义.

    后量子密码格基密码密钥封装方案并行处理图形处理器

      原文链接:
    • 万方数据
    • 维普

    基于HRF-Net的指纹细节点及汗孔统一提取方法

    刘凤王秋恒肖延峰文嘉俊...
    2179-2194页
    查看更多>>摘要：基于多级特征(例如细节点、汗孔等)融合的指纹识别技术,大大提高了指纹识别系统的安全性和鲁棒性.然而,目前基于高精度指纹的识别技术,几乎都是基于第三级特征中的汗孔特征,而忽略了指纹图像中的其他重要特征.针对这一问题,本文首次提出一种指纹特征提取方法,能够实现在高精度指纹图像上同时提取不同层级特征,包括二级的细节点特征和三级的汗孔特征.本文设计了 High-Resolution Fingerprint Net(HRF-Net)作为特征提取模型,利用指纹图像生成细节点与汗孔的热力图,再通过滑动窗口算法处理得到特征点坐标.在HRF-Net模型中,通过引入中继输出结构以实现汗孔和细节点特征的解耦,利用由粗到细的阶段式监督以兼顾网络对不同层级特征的学习,在网络中加入shuffle unit模块减少模型计算复杂度,实现了对指纹不同层级特征高效准确的提取.实验结果表明,本文提出的特征统一提取方法在汗孔的提取上真阳率(RT)达到了 96.59％,比目前取得最好性能的Judge CNN提高了 3.45％;在细节点的提取上真阳率(RT)达到了 81.93％.同时,我们在对汗孔和细节点单独提取上也达到了最好的结果,以衡量提取综合性能的Fl-score作为评价指标,模型提取汗孔的Fl-score达到了 95.83％,比Judge CNN提高1.48％.我们利用所提取的特征在指纹匹配数据集上的指纹图像进行匹配实验,在等错误率(Equal Error Rate,EER)上达到了 5.39％,相比传统方法下降7.02％.结果表明,本文的方法在汗孔和细节点的提取性能以及匹配结果上都达到了目前最佳水平.

    指纹识别高精度指纹细节点提取汗孔提取

      原文链接:
    • 万方数据
    • 维普