2023年第34卷第11期文章目次
2023, 34(11):4941-4951.
DOI: 10.13328/j.cnki.jos.006720
摘要:
稀疏三角线性方程组求解(SpTRSV)是预条件子部分的重要操作, 其中结构化SpTRSV问题, 在以迭代方法求解偏微分方程组的科学计算程序中, 是一种较为常见的问题类型, 而且通常是科学计算程序的需要解决的一个性能瓶颈. 针对GPU平台, 目前以CUSPARSE为代表的商用GPU数学库, 采用分层调度(level-scheduling)方法并行化SpTRSV操作. 该方法不仅预处理耗时较长, 而且在处理结构化SpTRSV问题时会出现较为严重GPU线程闲置问题. 针对结构化SpTRSV问题, 提出一种面向结构化SpTRSV问题的并行算法. 该算法利用结构化SpTRSV问题的特殊非零元分布规律进行任务划分, 避免对输入问题的非零元结构进行预处理分析. 并对现有分层调度方法的逐元素处理策略进行改进, 在有效缓解GPU线程闲置问题的基础上, 还隐藏了部分矩阵非零元素的访存延迟. 还根据算法的任务划分特点, 采用状态变量压缩技术, 显著提高算法状态变量操作的缓存命中率. 在此基础上, 还结合谓词执行等GPU硬件特性, 对算法实现进行全面的优化. 所提算法在NVIDIA V100 GPU上的实测性能, 相比CUSPARSE平均有2.71倍的加速效果, 有效访存带宽最高可达225.2 GB/s. 改进后的逐元素处理策略, 配合针对GPU硬件的一系列调优手段, 优化效果显著, 将算法的有效访存带宽提高了约1.15倍.
稀疏三角线性方程组求解(SpTRSV)是预条件子部分的重要操作, 其中结构化SpTRSV问题, 在以迭代方法求解偏微分方程组的科学计算程序中, 是一种较为常见的问题类型, 而且通常是科学计算程序的需要解决的一个性能瓶颈. 针对GPU平台, 目前以CUSPARSE为代表的商用GPU数学库, 采用分层调度(level-scheduling)方法并行化SpTRSV操作. 该方法不仅预处理耗时较长, 而且在处理结构化SpTRSV问题时会出现较为严重GPU线程闲置问题. 针对结构化SpTRSV问题, 提出一种面向结构化SpTRSV问题的并行算法. 该算法利用结构化SpTRSV问题的特殊非零元分布规律进行任务划分, 避免对输入问题的非零元结构进行预处理分析. 并对现有分层调度方法的逐元素处理策略进行改进, 在有效缓解GPU线程闲置问题的基础上, 还隐藏了部分矩阵非零元素的访存延迟. 还根据算法的任务划分特点, 采用状态变量压缩技术, 显著提高算法状态变量操作的缓存命中率. 在此基础上, 还结合谓词执行等GPU硬件特性, 对算法实现进行全面的优化. 所提算法在NVIDIA V100 GPU上的实测性能, 相比CUSPARSE平均有2.71倍的加速效果, 有效访存带宽最高可达225.2 GB/s. 改进后的逐元素处理策略, 配合针对GPU硬件的一系列调优手段, 优化效果显著, 将算法的有效访存带宽提高了约1.15倍.
2023, 34(11):4952-4972.
DOI: 10.13328/j.cnki.jos.006727
摘要:
给出批量矩阵的LU分解和批量求逆算法在GPU上实现及优化方法. 针对批量LU分解问题, 分析Left-looking和Right-looking等常用LU分解块算法在GPU上实现时对全局内存的数据读写次数, 针对GPU架构特点, 选择具有较少访存数据量的Left-looking块算法. 在LU分解的选主元过程, 采用适合GPU架构的并行二叉树搜索算法. 此外, 为了降低选主元引起的行交换过程对算法性能的影响, 提出Warp分组行交换和行交换延迟2个优化技术. 针对LU分解后的批量求逆问题, 分析矩阵求逆过程中修正方法, 为了减少修正过程对全局内存的访问, 在批量求逆的GPU实现中采用延迟修正的矩阵求逆块算法. 同时, 为了加快数据读写速度, 采用更多利用寄存器和共享内存的优化方法和减少访存数据量的列交换优化方法. 另外, 为了避免线程的闲置和共享内存等GPU资源浪费, 提出运行时动态GPU资源分配方法, 相较于一次性分配的静资源分配方法性能得到明显提升. 最终, 在TITAN V GPU上, 对10000个规模在33–190之间的随机矩阵进行测试, 测试的数据类型为单精度复数、双精度复数、单精度实数和双精度实数. 所实现的批量LU分解算法的浮点计算性能分别可达到约2 TFLOPS、1.2 TFLOPS、1 TFLOPS、0.67 TFLOPS, 与CUBLAS中的实现相比加速比最高分别达到了约9×、8×、12×、13×, 与MAGMA中的实现相比加速比分别达到了约1.2×–2.5×、1.2×–3.2×、1.1×–3×、1.1×–2.7×. 批量求逆算法的浮点计算性能分别可达到约4 TFLOPS、2 TFLOPS、2.2 TFLOPS、1.2 TFLOPS, 与CUBLAS中的实现相比加速比最高分别达到了约5×、4×、7×、7×, 与MAGMA中的实现相比加速比分别达到了约2×–3×、2×–3×、2.8×–3.4×、1.6×–2×.
给出批量矩阵的LU分解和批量求逆算法在GPU上实现及优化方法. 针对批量LU分解问题, 分析Left-looking和Right-looking等常用LU分解块算法在GPU上实现时对全局内存的数据读写次数, 针对GPU架构特点, 选择具有较少访存数据量的Left-looking块算法. 在LU分解的选主元过程, 采用适合GPU架构的并行二叉树搜索算法. 此外, 为了降低选主元引起的行交换过程对算法性能的影响, 提出Warp分组行交换和行交换延迟2个优化技术. 针对LU分解后的批量求逆问题, 分析矩阵求逆过程中修正方法, 为了减少修正过程对全局内存的访问, 在批量求逆的GPU实现中采用延迟修正的矩阵求逆块算法. 同时, 为了加快数据读写速度, 采用更多利用寄存器和共享内存的优化方法和减少访存数据量的列交换优化方法. 另外, 为了避免线程的闲置和共享内存等GPU资源浪费, 提出运行时动态GPU资源分配方法, 相较于一次性分配的静资源分配方法性能得到明显提升. 最终, 在TITAN V GPU上, 对10000个规模在33–190之间的随机矩阵进行测试, 测试的数据类型为单精度复数、双精度复数、单精度实数和双精度实数. 所实现的批量LU分解算法的浮点计算性能分别可达到约2 TFLOPS、1.2 TFLOPS、1 TFLOPS、0.67 TFLOPS, 与CUBLAS中的实现相比加速比最高分别达到了约9×、8×、12×、13×, 与MAGMA中的实现相比加速比分别达到了约1.2×–2.5×、1.2×–3.2×、1.1×–3×、1.1×–2.7×. 批量求逆算法的浮点计算性能分别可达到约4 TFLOPS、2 TFLOPS、2.2 TFLOPS、1.2 TFLOPS, 与CUBLAS中的实现相比加速比最高分别达到了约5×、4×、7×、7×, 与MAGMA中的实现相比加速比分别达到了约2×–3×、2×–3×、2.8×–3.4×、1.6×–2×.
2023, 34(11):4973-4988.
DOI: 10.13328/j.cnki.jos.006742
摘要:
大多数跨模态哈希检索方法仅使用余弦相似度进行特征匹配, 计算方式过于单一, 没有考虑到实例的关系对于性能的影响. 为此, 提出一种基于多重实例关系图推理的方法, 通过构造相似度矩阵, 建立全局和局部的实例关系图, 充分挖掘实例之间的细粒度关系. 在多重实例关系图的基础上进行相似度推理, 首先分别进行图像模态和文本模态关系图内部的推理, 然后将模态内的关系映射到实例图中进行推理, 最后执行实例图内部的推理. 此外, 为了适应图像和文本两种模态的特点, 使用分步训练策略训练神经网络. 在MIRFlickr和NUS-WIDE数据集上实验表明, 提出的方法在mAP指标上具有很明显的优势, 在Top-k-Precision曲线上也获得良好的效果. 这也说明所提方法对实例关系进行深入挖掘, 从而显著地提升检索性能.
大多数跨模态哈希检索方法仅使用余弦相似度进行特征匹配, 计算方式过于单一, 没有考虑到实例的关系对于性能的影响. 为此, 提出一种基于多重实例关系图推理的方法, 通过构造相似度矩阵, 建立全局和局部的实例关系图, 充分挖掘实例之间的细粒度关系. 在多重实例关系图的基础上进行相似度推理, 首先分别进行图像模态和文本模态关系图内部的推理, 然后将模态内的关系映射到实例图中进行推理, 最后执行实例图内部的推理. 此外, 为了适应图像和文本两种模态的特点, 使用分步训练策略训练神经网络. 在MIRFlickr和NUS-WIDE数据集上实验表明, 提出的方法在mAP指标上具有很明显的优势, 在Top-k-Precision曲线上也获得良好的效果. 这也说明所提方法对实例关系进行深入挖掘, 从而显著地提升检索性能.
2023, 34(11):4989-5007.
DOI: 10.13328/j.cnki.jos.006684
摘要:
分布式系统在计算环境中发挥重要的作用, 其中的共识协议算法用于保证节点间行为的一致性. 共识协议的设计错误可能导致系统运行故障, 严重时可能对人员和环境造成灾难性的后果, 因此保证共识协议设计的正确性非常重要. 形式化验证能够严格证明设计模型中目标性质的正确性, 适合用于验证共识协议. 然而, 随着分布式系统的规模增大, 问题复杂度提升, 使得分布式共识协议的形式化验证更为困难. 采用什么方法对共识协议的设计进行形式化验证、如何提升验证规模, 是共识协议形式化验证的重要研究问题. 对目前采用形式化方法验证共识协议的研究工作进行调研, 总结其中提出的重要建模方法和关键验证技术, 并展望该领域未来有潜力的研究方向.
分布式系统在计算环境中发挥重要的作用, 其中的共识协议算法用于保证节点间行为的一致性. 共识协议的设计错误可能导致系统运行故障, 严重时可能对人员和环境造成灾难性的后果, 因此保证共识协议设计的正确性非常重要. 形式化验证能够严格证明设计模型中目标性质的正确性, 适合用于验证共识协议. 然而, 随着分布式系统的规模增大, 问题复杂度提升, 使得分布式共识协议的形式化验证更为困难. 采用什么方法对共识协议的设计进行形式化验证、如何提升验证规模, 是共识协议形式化验证的重要研究问题. 对目前采用形式化方法验证共识协议的研究工作进行调研, 总结其中提出的重要建模方法和关键验证技术, 并展望该领域未来有潜力的研究方向.
2023, 34(11):5008-5028.
DOI: 10.13328/j.cnki.jos.006679
摘要:
深度学习系统具有强大的学习与推理能力, 在无人驾驶、语音识别和机器人等领域应用广泛. 由于数据集的限制以及依赖人工标签数据, 深度学习系统易于出现非预期的行为. 近年来, 深度学习系统的质量问题受到广泛的关注, 特别是在安全攸关的领域. 由于模糊测试具有较强的故障揭示能力, 运用模糊测试技术对深度学习系统进行测试成为研究热点. 从测试用例生成(包括种子队列构建、种子选择和种子变异)、测试结果判定、覆盖分析3个方面对已有的深度学习系统的模糊测试技术进行总结, 并介绍常用的数据集以及度量指标, 最后对其发展方向进行展望.
深度学习系统具有强大的学习与推理能力, 在无人驾驶、语音识别和机器人等领域应用广泛. 由于数据集的限制以及依赖人工标签数据, 深度学习系统易于出现非预期的行为. 近年来, 深度学习系统的质量问题受到广泛的关注, 特别是在安全攸关的领域. 由于模糊测试具有较强的故障揭示能力, 运用模糊测试技术对深度学习系统进行测试成为研究热点. 从测试用例生成(包括种子队列构建、种子选择和种子变异)、测试结果判定、覆盖分析3个方面对已有的深度学习系统的模糊测试技术进行总结, 并介绍常用的数据集以及度量指标, 最后对其发展方向进行展望.
2023, 34(11):5029-5041.
DOI: 10.13328/j.cnki.jos.006678
摘要:
软件系统是一个复杂的人工制品, 类之间的交互关系对软件质量有着潜在影响, 如软件缺陷的级联传播效应就是一个典型. 如何准确预测软件系统中类之间合理关系, 优化设计结构是软件质量保障的一个开放问题. 从软件网络观的视角, 综合考虑软件系统中类与类之间关系(外部图), 以及每个类内部方法之间关系(内部图), 将软件系统抽象成一个图中图结构的软件网络, 并在此基础上提出一种基于图中图卷积神经网络的类交互关系预测方法. 首先对每个类内部图进行卷积得到类节点的初始特征, 再通过外部图的卷积更新类节点的表征向量, 最后通过计算类节点对的评估值进行交互预测. 根据在6个Java开源项目上的实验结果显示, 图中图结构有助于提高软件系统结构的表征能力, 且所提方法与常规网络嵌入方法相比, AUC值和AP值的平均增长率超过5.5%. 与此同时, 和两种同行方法相比, AUC值和AP值的平均增长率分别在9.36%和5.22%以上.
软件系统是一个复杂的人工制品, 类之间的交互关系对软件质量有着潜在影响, 如软件缺陷的级联传播效应就是一个典型. 如何准确预测软件系统中类之间合理关系, 优化设计结构是软件质量保障的一个开放问题. 从软件网络观的视角, 综合考虑软件系统中类与类之间关系(外部图), 以及每个类内部方法之间关系(内部图), 将软件系统抽象成一个图中图结构的软件网络, 并在此基础上提出一种基于图中图卷积神经网络的类交互关系预测方法. 首先对每个类内部图进行卷积得到类节点的初始特征, 再通过外部图的卷积更新类节点的表征向量, 最后通过计算类节点对的评估值进行交互预测. 根据在6个Java开源项目上的实验结果显示, 图中图结构有助于提高软件系统结构的表征能力, 且所提方法与常规网络嵌入方法相比, AUC值和AP值的平均增长率超过5.5%. 与此同时, 和两种同行方法相比, AUC值和AP值的平均增长率分别在9.36%和5.22%以上.
2023, 34(11):5042-5057.
DOI: 10.13328/j.cnki.jos.006741
摘要:
基于区块链的去中心化应用已在加密数字货币、云存储、物联网等多个领域提供健壮、可信且持久的服务, 然而区块链的吞吐能力难以满足去中心化应用日益增长的性能需求. 分片是当前主流的区块链性能优化技术, 但现有的区块链分片主要面向用户和用户之间的转账交易, 并不完全适用于以智能合约调用交易为主的去中心化应用. 针对此问题, 设计并实现面向智能合约分片的联盟区块链系统BETASCO. BETASCO为每个智能合约提供一个分片作为独立执行环境, 通过基于分布式散列表的合约定位服务将交易路由至目标智能合约所在的分片, 并通过智能合约间的异步调用机制满足跨智能合约的通信和协作需求. BETASCO通过节点虚拟化允许一个节点加入多个分片, 支持同一组节点上多个智能合约的并行执行. 实验结果表明, BETASCO整体吞吐能力可随智能合约数量的增加而线性增长, 且执行单个智能合约的吞吐能力与HyperLedger Fabric相当.
基于区块链的去中心化应用已在加密数字货币、云存储、物联网等多个领域提供健壮、可信且持久的服务, 然而区块链的吞吐能力难以满足去中心化应用日益增长的性能需求. 分片是当前主流的区块链性能优化技术, 但现有的区块链分片主要面向用户和用户之间的转账交易, 并不完全适用于以智能合约调用交易为主的去中心化应用. 针对此问题, 设计并实现面向智能合约分片的联盟区块链系统BETASCO. BETASCO为每个智能合约提供一个分片作为独立执行环境, 通过基于分布式散列表的合约定位服务将交易路由至目标智能合约所在的分片, 并通过智能合约间的异步调用机制满足跨智能合约的通信和协作需求. BETASCO通过节点虚拟化允许一个节点加入多个分片, 支持同一组节点上多个智能合约的并行执行. 实验结果表明, BETASCO整体吞吐能力可随智能合约数量的增加而线性增长, 且执行单个智能合约的吞吐能力与HyperLedger Fabric相当.
2023, 34(11):5058-5083.
DOI: 10.13328/j.cnki.jos.006735
摘要:
随着信息技术与教育的深度融合, 蓬勃发展的在线教育已成为教育信息化进程的新常态, 并产生了海量的教育数据, 但也面临辍学率高、课程完成率低、监管不足等问题, 因此如何对海量教育数据进行挖掘和分析是解决这些问题的关键. 学习共同体是以学习者为核心要素的学习组织, 强调学习过程中学习者之间互动交流、资源共享以及协作学习等行为, 从而完成共同的学习任务或目标. 对在线教育环境中学习共同体的研究进行回顾、分析和展望. 首先, 介绍在线教育环境中学习共同体的背景与重要性. 其次, 介绍不同学科中学习共同体的定义. 然后, 总结同质、异质和混合3种类型学习共同体的构建方法. 接着, 从共享、协作和激励3个方面讨论学习共同体的管理机制. 最后, 探讨和展望学习共同体未来的研究方向.
随着信息技术与教育的深度融合, 蓬勃发展的在线教育已成为教育信息化进程的新常态, 并产生了海量的教育数据, 但也面临辍学率高、课程完成率低、监管不足等问题, 因此如何对海量教育数据进行挖掘和分析是解决这些问题的关键. 学习共同体是以学习者为核心要素的学习组织, 强调学习过程中学习者之间互动交流、资源共享以及协作学习等行为, 从而完成共同的学习任务或目标. 对在线教育环境中学习共同体的研究进行回顾、分析和展望. 首先, 介绍在线教育环境中学习共同体的背景与重要性. 其次, 介绍不同学科中学习共同体的定义. 然后, 总结同质、异质和混合3种类型学习共同体的构建方法. 接着, 从共享、协作和激励3个方面讨论学习共同体的管理机制. 最后, 探讨和展望学习共同体未来的研究方向.
2023, 34(11):5084-5112.
DOI: 10.13328/j.cnki.jos.006728
摘要:
近年来, 随着互联网信息传播以及新型冠状病毒COVID-19传播链阻断等重大应用问题的出现, 社会网络影响最大化问题的研究受到了科学界广泛关注. 影响最大化问题旨在根据特定应用问题的传播模型, 识别出最优影响种子节点集, 最大化其信息传播影响. 现有影响最大化算法主要针对单连接影响传播模型, 将影响最大化问题模拟为离散的影响力种子节点组合选取优化问题. 然而, 这些算法具有较高的计算时间复杂度, 且无法解决具有大规模冲突关系的符号网络影响最大化问题. 针对上述问题, 首先, 构建适用于符号网络的正负影响传播模型以及影响最大化优化模型. 其次, 通过引入由神经网络构成的deep Q network来选取种子节点集, 将离散的种子节点组合选取问题转化为更易优化的网络权重连续优化问题. 最后, 提出基于演化深度强化学习的符号网络影响最大化算法SEDRL-IM. 该算法将演化算法的个体视作策略, 结合演化算法的无梯度全局搜索以及强化学习的局部搜索特性, 实现对deep Q network权重优化问题解的有效搜索, 从而找到最优影响种子节点集. 在基准符号网络以及真实社交网络数据集上的大量实验结果表明, 所提算法在影响传播范围与求解效率上都优于经典的基准算法.
近年来, 随着互联网信息传播以及新型冠状病毒COVID-19传播链阻断等重大应用问题的出现, 社会网络影响最大化问题的研究受到了科学界广泛关注. 影响最大化问题旨在根据特定应用问题的传播模型, 识别出最优影响种子节点集, 最大化其信息传播影响. 现有影响最大化算法主要针对单连接影响传播模型, 将影响最大化问题模拟为离散的影响力种子节点组合选取优化问题. 然而, 这些算法具有较高的计算时间复杂度, 且无法解决具有大规模冲突关系的符号网络影响最大化问题. 针对上述问题, 首先, 构建适用于符号网络的正负影响传播模型以及影响最大化优化模型. 其次, 通过引入由神经网络构成的deep Q network来选取种子节点集, 将离散的种子节点组合选取问题转化为更易优化的网络权重连续优化问题. 最后, 提出基于演化深度强化学习的符号网络影响最大化算法SEDRL-IM. 该算法将演化算法的个体视作策略, 结合演化算法的无梯度全局搜索以及强化学习的局部搜索特性, 实现对deep Q network权重优化问题解的有效搜索, 从而找到最优影响种子节点集. 在基准符号网络以及真实社交网络数据集上的大量实验结果表明, 所提算法在影响传播范围与求解效率上都优于经典的基准算法.
2023, 34(11):5113-5125.
DOI: 10.13328/j.cnki.jos.006689
摘要:
资源丰富场景下, 利用相似性翻译作为目标端原型序列, 能够有效提升神经机器翻译的性能. 然而在低资源场景下, 由于平行语料资源匮乏, 导致不能匹配得到原型序列或序列质量不佳. 针对此问题, 提出一种基于多种策略进行原型生成的方法. 首先结合利用关键词匹配和分布式表示匹配检索原型序列, 如未能获得匹配, 则利用伪原型生成方法产生可用的伪原型序列. 其次, 为有效地利用原型序列, 对传统的编码器-解码器框架进行改进. 编码端使用额外的编码器接收原型序列输入; 解码端在利用门控机制控制信息流动的同时, 使用改进的损失函数减少低质量原型序列对模型的影响. 多个数据集上的实验结果表明, 相比基线模型, 所提出的方法能够有效提升低资源场景下的机器翻译性能.
资源丰富场景下, 利用相似性翻译作为目标端原型序列, 能够有效提升神经机器翻译的性能. 然而在低资源场景下, 由于平行语料资源匮乏, 导致不能匹配得到原型序列或序列质量不佳. 针对此问题, 提出一种基于多种策略进行原型生成的方法. 首先结合利用关键词匹配和分布式表示匹配检索原型序列, 如未能获得匹配, 则利用伪原型生成方法产生可用的伪原型序列. 其次, 为有效地利用原型序列, 对传统的编码器-解码器框架进行改进. 编码端使用额外的编码器接收原型序列输入; 解码端在利用门控机制控制信息流动的同时, 使用改进的损失函数减少低质量原型序列对模型的影响. 多个数据集上的实验结果表明, 相比基线模型, 所提出的方法能够有效提升低资源场景下的机器翻译性能.
2023, 34(11):5126-5142.
DOI: 10.13328/j.cnki.jos.006724
摘要:
知识追踪任务是根据学生历史答题记录追踪学生知识状态的变化, 预测学生未来的答题情况. 近年来, 基于注意力机制的知识追踪模型在灵活性和预测性能上都明显优于传统知识追踪模型. 但是现有深度模型大多只考虑了单一知识点题目的情况, 无法直接处理多知识点题目, 而智能教育系统中存在着大量的多知识点题目. 此外, 如何提高可解释性是深度知识追踪模型的关键挑战之一. 为了解决这些问题, 提出一种多知识点融合嵌入的深度知识追踪模型. 所提模型考虑涉及多知识点的题目中知识点之间的关系, 提出两种新颖的多知识点嵌入方式, 并且结合教育心理学模型和遗忘因素提升预测性能和可解释性. 实验表明所提模型在大规模真实数据集上预测性能上优于现有模型, 并验证各个模块的有效性.
知识追踪任务是根据学生历史答题记录追踪学生知识状态的变化, 预测学生未来的答题情况. 近年来, 基于注意力机制的知识追踪模型在灵活性和预测性能上都明显优于传统知识追踪模型. 但是现有深度模型大多只考虑了单一知识点题目的情况, 无法直接处理多知识点题目, 而智能教育系统中存在着大量的多知识点题目. 此外, 如何提高可解释性是深度知识追踪模型的关键挑战之一. 为了解决这些问题, 提出一种多知识点融合嵌入的深度知识追踪模型. 所提模型考虑涉及多知识点的题目中知识点之间的关系, 提出两种新颖的多知识点嵌入方式, 并且结合教育心理学模型和遗忘因素提升预测性能和可解释性. 实验表明所提模型在大规模真实数据集上预测性能上优于现有模型, 并验证各个模块的有效性.
2023, 34(11):5143-5161.
DOI: 10.13328/j.cnki.jos.006744
摘要:
深度神经网络容易受到来自对抗样本的攻击, 例如在文本分类任务中修改原始文本中的少量字、词、标点符号即可改变模型分类结果. 目前NLP领域对中文对抗样本的研究较少且未充分结合汉语的语言特征. 从中文情感分类场景入手, 结合了汉语象形、表音等语言特征, 提出一种字词级别的高质量的对抗样本生成方法CWordCheater, 涵盖字音、字形、标点符号等多个角度. 针对形近字的替换方式, 引入ConvAE网络完成汉字视觉向量的嵌入, 进而生成形近字替换候选池. 同时提出一种基于USE编码距离的语义约束方法避免对抗样本的语义偏移问题. 构建一套多维度的对抗样本评估方法, 从攻击效果和攻击代价两方面评估对抗样本的质量. 实验结果表明, CWordAttacker在多个分类模型和多个数据集上能使分类准确率至少下降27.9%, 同时拥有更小的基于视觉和语义的扰动代价.
深度神经网络容易受到来自对抗样本的攻击, 例如在文本分类任务中修改原始文本中的少量字、词、标点符号即可改变模型分类结果. 目前NLP领域对中文对抗样本的研究较少且未充分结合汉语的语言特征. 从中文情感分类场景入手, 结合了汉语象形、表音等语言特征, 提出一种字词级别的高质量的对抗样本生成方法CWordCheater, 涵盖字音、字形、标点符号等多个角度. 针对形近字的替换方式, 引入ConvAE网络完成汉字视觉向量的嵌入, 进而生成形近字替换候选池. 同时提出一种基于USE编码距离的语义约束方法避免对抗样本的语义偏移问题. 构建一套多维度的对抗样本评估方法, 从攻击效果和攻击代价两方面评估对抗样本的质量. 实验结果表明, CWordAttacker在多个分类模型和多个数据集上能使分类准确率至少下降27.9%, 同时拥有更小的基于视觉和语义的扰动代价.
2023, 34(11):5162-5178.
DOI: 10.13328/j.cnki.jos.006729
摘要:
社交媒体主题检测旨在从大规模短帖子中挖掘潜在的主题信息. 由于帖子形式简短、表达非正规化, 且社交媒体中用户交互复杂多样, 使得该任务具有一定的挑战性. 前人工作仅考虑了帖子的文本内容, 或者同时对同构情境下的社交上下文进行建模, 忽略了社交网络的异构性. 然而, 不同的用户交互方式, 如转发, 评论等, 可能意味着不同的行为模式和兴趣偏好, 其反映了对主题的不同的关注与理解; 此外, 不同用户对同一主题的发展和演化具有不同影响, 社区中处于引领地位的权威用户相对于普通用户对主题推断会产生更重要的作用. 因此, 提出一种新的多视图主题模型(multi-view topic model, MVTM), 通过编码微博会话网络中的异构社交上下文来推断更加完整、连贯的主题. 首先根据用户之间的交互关系构建一个属性多元异构会话网络, 并将其分解为具有不同交互语义的多个视图; 接着, 考虑不同交互方式与不同用户的重要性, 借助邻居级注意力和交互级注意力机制, 得到特定视图的嵌入表示; 最后, 设计一个多视图驱动的神经变分推理方法, 以捕捉不同视图之间的深层关联, 并自适应地平衡它们的一致性和独立性, 从而产生更连贯的主题. 在3个月新浪微博数据集上的实验结果证明所提方法的有效性.
社交媒体主题检测旨在从大规模短帖子中挖掘潜在的主题信息. 由于帖子形式简短、表达非正规化, 且社交媒体中用户交互复杂多样, 使得该任务具有一定的挑战性. 前人工作仅考虑了帖子的文本内容, 或者同时对同构情境下的社交上下文进行建模, 忽略了社交网络的异构性. 然而, 不同的用户交互方式, 如转发, 评论等, 可能意味着不同的行为模式和兴趣偏好, 其反映了对主题的不同的关注与理解; 此外, 不同用户对同一主题的发展和演化具有不同影响, 社区中处于引领地位的权威用户相对于普通用户对主题推断会产生更重要的作用. 因此, 提出一种新的多视图主题模型(multi-view topic model, MVTM), 通过编码微博会话网络中的异构社交上下文来推断更加完整、连贯的主题. 首先根据用户之间的交互关系构建一个属性多元异构会话网络, 并将其分解为具有不同交互语义的多个视图; 接着, 考虑不同交互方式与不同用户的重要性, 借助邻居级注意力和交互级注意力机制, 得到特定视图的嵌入表示; 最后, 设计一个多视图驱动的神经变分推理方法, 以捕捉不同视图之间的深层关联, 并自适应地平衡它们的一致性和独立性, 从而产生更连贯的主题. 在3个月新浪微博数据集上的实验结果证明所提方法的有效性.
2023, 34(11):5179-5190.
DOI: 10.13328/j.cnki.jos.006730
摘要:
选择式阅读理解通常采用证据抽取和答案预测的两阶段流水线框架, 答案预测的效果非常依赖于证据句抽取的效果. 传统的证据抽取多依赖词段匹配或利用噪声标签监督证据抽取的方法, 准确率不理想, 这极大地影响了答案预测的性能. 针对该问题, 提出一种联合学习框架下基于多视角图编码的选择式阅读理解方法, 从多视角充分挖掘文档句子之间以及文档句子和问句之间的关联关系, 实现证据句及其关系的有效建模; 同时通过联合训练证据抽取和答案预测任务, 利用证据和答案之间强关联关系提升证据抽取与答案预测的性能. 具体来说, 所提方法首先基于多视角图编码模块对文档、问题和候选答案联合编码, 从统计特性、相对距离和深度语义3个视角捕捉文档、问题和候选答案之间的关系, 获得问答对感知的文档编码特征; 然后, 构建证据抽取和答案预测的联合学习模块, 通过协同训练强化证据与答案之间的关系, 证据抽取子模块实现证据句的选择, 并将其结果和文档编码特征进行选择性融合, 并用于答案预测子模块完成答案预测. 在选择式阅读理解数据集ReCO和RACE上的实验结果表明, 所提方法提升了从文档中选择证据句子的能力, 进而提高答案预测的准确率. 同时, 证据抽取与答案预测联合学习很大程度减缓了传统流水线所导致的误差累积问题.
选择式阅读理解通常采用证据抽取和答案预测的两阶段流水线框架, 答案预测的效果非常依赖于证据句抽取的效果. 传统的证据抽取多依赖词段匹配或利用噪声标签监督证据抽取的方法, 准确率不理想, 这极大地影响了答案预测的性能. 针对该问题, 提出一种联合学习框架下基于多视角图编码的选择式阅读理解方法, 从多视角充分挖掘文档句子之间以及文档句子和问句之间的关联关系, 实现证据句及其关系的有效建模; 同时通过联合训练证据抽取和答案预测任务, 利用证据和答案之间强关联关系提升证据抽取与答案预测的性能. 具体来说, 所提方法首先基于多视角图编码模块对文档、问题和候选答案联合编码, 从统计特性、相对距离和深度语义3个视角捕捉文档、问题和候选答案之间的关系, 获得问答对感知的文档编码特征; 然后, 构建证据抽取和答案预测的联合学习模块, 通过协同训练强化证据与答案之间的关系, 证据抽取子模块实现证据句的选择, 并将其结果和文档编码特征进行选择性融合, 并用于答案预测子模块完成答案预测. 在选择式阅读理解数据集ReCO和RACE上的实验结果表明, 所提方法提升了从文档中选择证据句子的能力, 进而提高答案预测的准确率. 同时, 证据抽取与答案预测联合学习很大程度减缓了传统流水线所导致的误差累积问题.
2023, 34(11):5191-5204.
DOI: 10.13328/j.cnki.jos.006740
摘要:
近年来, 深度强化学习在复杂控制任务中取得了令人瞩目的效果, 然而由于超参数的高敏感性和收敛性难以保证等原因, 严重影响了其对现实问题的适用性. 元启发式算法作为一类模拟自然界客观规律的黑盒优化方法, 虽然能够有效避免超参数的敏感性, 但仍存在无法适应待优化参数量规模巨大和样本使用效率低等问题. 针对以上问题, 提出融合引力搜索的双延迟深度确定策略梯度方法(twin delayed deep deterministic policy gradient based on gravitational search algorithm, GSA-TD3). 该方法融合两类算法的优势: 一是凭借梯度优化的方式更新策略, 获得更高的样本效率和更快的学习速度; 二是将基于万有引力定律的种群更新方法引入到策略搜索过程中, 使其具有更强的探索性和更好的稳定性. 将GSA-TD3应用于一系列复杂控制任务中, 实验表明, 与前沿的同类深度强化学习方法相比, GSA-TD3在性能上具有显著的优势.
近年来, 深度强化学习在复杂控制任务中取得了令人瞩目的效果, 然而由于超参数的高敏感性和收敛性难以保证等原因, 严重影响了其对现实问题的适用性. 元启发式算法作为一类模拟自然界客观规律的黑盒优化方法, 虽然能够有效避免超参数的敏感性, 但仍存在无法适应待优化参数量规模巨大和样本使用效率低等问题. 针对以上问题, 提出融合引力搜索的双延迟深度确定策略梯度方法(twin delayed deep deterministic policy gradient based on gravitational search algorithm, GSA-TD3). 该方法融合两类算法的优势: 一是凭借梯度优化的方式更新策略, 获得更高的样本效率和更快的学习速度; 二是将基于万有引力定律的种群更新方法引入到策略搜索过程中, 使其具有更强的探索性和更好的稳定性. 将GSA-TD3应用于一系列复杂控制任务中, 实验表明, 与前沿的同类深度强化学习方法相比, GSA-TD3在性能上具有显著的优势.
2023, 34(11):5205-5229.
DOI: 10.13328/j.cnki.jos.006739
摘要:
GPU数据库近年来在学术界和工业界吸引了大量的关注. 尽管一些原型系统和商业系统(包括开源系统)开发了作为下一代的数据库系统, 但基于GPU的OLAP引擎性能是否真的超过CPU系统仍然存有疑问, 如果能够超越, 那什么样的负载/数据/查询处理模型更加适合, 则需要更深入的研究. 基于GPU的OLAP引擎有两个主要的技术路线: GPU内存处理模式和GPU加速模式. 前者将所有的数据集存储在GPU显存来充分利用GPU的计算性能和高带宽内存性能, 不足之处在于GPU容量有限的显存制约了数据集大小以及稀疏访问模式的数据存储降低GPU显存的存储效率. 后者只在GPU显存中存储部分数据集并通过GPU加速计算密集型负载来支持大数据集, 主要的挑战在于如何为GPU显存选择优化的数据分布和负载分布模型来最小化PCIe传输代价和最大化GPU计算效率. 致力于将两种技术路线集成到OLAP加速引擎中, 研究一个定制化的混合CPU-GPU平台上的OLAP框架OLAP Accelerator, 设计CPU内存计算、GPU内存计算和GPU加速3种OLAP计算模型, 实现GPU平台向量化查询处理技术, 优化显存利用率和查询性能, 探索GPU数据库的不同的技术路线和性能特征. 实验结果显示GPU内存向量化查询处理模型在性能和内存利用率两方面获得最佳性能, 与OmniSciDB和Hyper数据库相比性能达到3.1和4.2倍加速. 基于分区的GPU加速模式仅加速了连接负载来平衡CPU和GPU端的负载, 能够比GPU内存模式支持更大的数据集.
GPU数据库近年来在学术界和工业界吸引了大量的关注. 尽管一些原型系统和商业系统(包括开源系统)开发了作为下一代的数据库系统, 但基于GPU的OLAP引擎性能是否真的超过CPU系统仍然存有疑问, 如果能够超越, 那什么样的负载/数据/查询处理模型更加适合, 则需要更深入的研究. 基于GPU的OLAP引擎有两个主要的技术路线: GPU内存处理模式和GPU加速模式. 前者将所有的数据集存储在GPU显存来充分利用GPU的计算性能和高带宽内存性能, 不足之处在于GPU容量有限的显存制约了数据集大小以及稀疏访问模式的数据存储降低GPU显存的存储效率. 后者只在GPU显存中存储部分数据集并通过GPU加速计算密集型负载来支持大数据集, 主要的挑战在于如何为GPU显存选择优化的数据分布和负载分布模型来最小化PCIe传输代价和最大化GPU计算效率. 致力于将两种技术路线集成到OLAP加速引擎中, 研究一个定制化的混合CPU-GPU平台上的OLAP框架OLAP Accelerator, 设计CPU内存计算、GPU内存计算和GPU加速3种OLAP计算模型, 实现GPU平台向量化查询处理技术, 优化显存利用率和查询性能, 探索GPU数据库的不同的技术路线和性能特征. 实验结果显示GPU内存向量化查询处理模型在性能和内存利用率两方面获得最佳性能, 与OmniSciDB和Hyper数据库相比性能达到3.1和4.2倍加速. 基于分区的GPU加速模式仅加速了连接负载来平衡CPU和GPU端的负载, 能够比GPU内存模式支持更大的数据集.
2023, 34(11):5230-5248.
DOI: 10.13328/j.cnki.jos.006681
摘要:
异质信息网络是一种异质数据表示形式, 如何融合异质数据复杂语义信息, 是推荐系统面临的挑战之一. 利用弱关系具有的丰富语义和信息传递能力, 构建一种面向推荐系统的异质信息网络高阶嵌入学习框架, 主要包括: 初始化信息嵌入、高阶信息嵌入聚合与推荐预测3个模块. 初始化信息嵌入模块首先采用基于弱关系的异质信息网络最佳信任路径筛选算法, 有效地避免在全关系异质信息网络中, 采样固定数量邻居造成的信息损失, 其次利用新定义的基于多头图注意力的多任务共享特征重要性度量因子, 筛选出节点的语义信息, 并结合交互结构, 有效地表征网络节点; 高阶信息嵌入聚合模块通过融入弱关系及网络嵌入对知识良好的表征能力, 实现高阶信息表达, 并利用异质信息网络的层级传播机制, 将被采样节点的特征聚合到待预测节点; 推荐预测模块利用高阶信息的影响力推荐方法, 实现了推荐任务. 该框架具有嵌入节点类型丰富、融合共享属性和隐式交互信息等特点. 最后, 实验验证UI-HEHo学习框架可有效地改善评级预测的准确性, 以及推荐生成的针对性、新颖性和多样性, 尤其是在数据稀疏的应用场景中, 具有良好的推荐效果.
异质信息网络是一种异质数据表示形式, 如何融合异质数据复杂语义信息, 是推荐系统面临的挑战之一. 利用弱关系具有的丰富语义和信息传递能力, 构建一种面向推荐系统的异质信息网络高阶嵌入学习框架, 主要包括: 初始化信息嵌入、高阶信息嵌入聚合与推荐预测3个模块. 初始化信息嵌入模块首先采用基于弱关系的异质信息网络最佳信任路径筛选算法, 有效地避免在全关系异质信息网络中, 采样固定数量邻居造成的信息损失, 其次利用新定义的基于多头图注意力的多任务共享特征重要性度量因子, 筛选出节点的语义信息, 并结合交互结构, 有效地表征网络节点; 高阶信息嵌入聚合模块通过融入弱关系及网络嵌入对知识良好的表征能力, 实现高阶信息表达, 并利用异质信息网络的层级传播机制, 将被采样节点的特征聚合到待预测节点; 推荐预测模块利用高阶信息的影响力推荐方法, 实现了推荐任务. 该框架具有嵌入节点类型丰富、融合共享属性和隐式交互信息等特点. 最后, 实验验证UI-HEHo学习框架可有效地改善评级预测的准确性, 以及推荐生成的针对性、新颖性和多样性, 尤其是在数据稀疏的应用场景中, 具有良好的推荐效果.
2023, 34(11):5249-5266.
DOI: 10.13328/j.cnki.jos.006731
摘要:
在基于事件的社交网络(EBSNs)上, 事件规划一直是一个热点研究问题. 事件规划问题的核心是基于事件和用户的约束条件, 对于一组事件, 为每个事件选择一组用户, 以最大化预先定义的目标函数. 在实际应用中, 事件冲突、事件容量、用户容量、社交偏好、事件偏好, 简称为CCP, 即冲突conflict、容量capacity、偏好preference, 是规划方案需要考虑的重要因素. 然而, 现有的所有工作均未在研究事件规划问题时考虑CCP. 为了获得更加合理有效的规划方案, 首次提出一种CCP事件规划问题. 相比只考虑部分因素的规划, CCP事件规划面临着问题更复杂、约束条件更多的困难. 为了有效求解该问题, 提出事件导向的贪心用户选择算法、事件导向的动态规划算法及基于收益预测的快速版本和事件导向的近似最优用户选择算法. 大量的实验结果验证所提算法的有效性和高效性.
在基于事件的社交网络(EBSNs)上, 事件规划一直是一个热点研究问题. 事件规划问题的核心是基于事件和用户的约束条件, 对于一组事件, 为每个事件选择一组用户, 以最大化预先定义的目标函数. 在实际应用中, 事件冲突、事件容量、用户容量、社交偏好、事件偏好, 简称为CCP, 即冲突conflict、容量capacity、偏好preference, 是规划方案需要考虑的重要因素. 然而, 现有的所有工作均未在研究事件规划问题时考虑CCP. 为了获得更加合理有效的规划方案, 首次提出一种CCP事件规划问题. 相比只考虑部分因素的规划, CCP事件规划面临着问题更复杂、约束条件更多的困难. 为了有效求解该问题, 提出事件导向的贪心用户选择算法、事件导向的动态规划算法及基于收益预测的快速版本和事件导向的近似最优用户选择算法. 大量的实验结果验证所提算法的有效性和高效性.
2023, 34(11):5267-5281.
DOI: 10.13328/j.cnki.jos.006734
摘要:
时间序列分割是数据挖掘领域中的一个重要研究方向. 目前基于矩阵轮廓(matrix profile, MP)的时间序列分割技术得到了越来越多研究人员的关注, 并且取得了不错的研究成果. 不过该技术及其衍生算法仍然存在不足: 首先, 基于矩阵轮廓的快速低代价语义分割算法中对给定活动状态的时间序列分割时, 最近邻之间通过弧进行连接, 会出现弧跨越非目标活动状态匹配相似子序列问题; 其次, 现有提取分割点算法在提取分割点时采用给定长度窗口, 容易得到与真实值偏差较大的分割点, 降低准确性. 针对以上问题, 提出一种限制弧跨越的时间序列分割算法(limit arc curve cross-FLOSS, LAC-FLOSS), 该算法给弧添加权重, 形成一种带权弧, 并通过设置匹配距离阈值解决弧的跨状态子序列误匹配问题. 此外, 提出一种改进的提取分割点算法(improved extract regimes, IER), 它通过纠正弧跨越(corrected arc crossings, CAC)序列的形状特性, 从波谷中提取极值, 避免直接使用窗口在非拐点处取到分割点的问题. 在公开数据集datasets_seg和MobiAct上面进行对比实验, 验证以上两种解决方案的可行性和有效性.
时间序列分割是数据挖掘领域中的一个重要研究方向. 目前基于矩阵轮廓(matrix profile, MP)的时间序列分割技术得到了越来越多研究人员的关注, 并且取得了不错的研究成果. 不过该技术及其衍生算法仍然存在不足: 首先, 基于矩阵轮廓的快速低代价语义分割算法中对给定活动状态的时间序列分割时, 最近邻之间通过弧进行连接, 会出现弧跨越非目标活动状态匹配相似子序列问题; 其次, 现有提取分割点算法在提取分割点时采用给定长度窗口, 容易得到与真实值偏差较大的分割点, 降低准确性. 针对以上问题, 提出一种限制弧跨越的时间序列分割算法(limit arc curve cross-FLOSS, LAC-FLOSS), 该算法给弧添加权重, 形成一种带权弧, 并通过设置匹配距离阈值解决弧的跨状态子序列误匹配问题. 此外, 提出一种改进的提取分割点算法(improved extract regimes, IER), 它通过纠正弧跨越(corrected arc crossings, CAC)序列的形状特性, 从波谷中提取极值, 避免直接使用窗口在非拐点处取到分割点的问题. 在公开数据集datasets_seg和MobiAct上面进行对比实验, 验证以上两种解决方案的可行性和有效性.
2023, 34(11):5282-5311.
DOI: 10.13328/j.cnki.jos.006746
摘要:
在软件开发过程中, 软件库可以减少开发时间和节约成本而被广泛使用, 因此现代软件项目包含多种不同来源的代码而使得系统具有更高的复杂性和多样性. 软件库在使用的过程中常常伴随着各种风险, 如低质量或安全漏洞, 从而严重影响软件项目的质量. 通过分析与软件库的耦合强度, 来量化由软件库的依赖关系而引入客户代码的复杂性和多样性. 首先, 根据客户代码与软件库之间方法的调用关系建立软件边界图模型, 区分开客户代码和软件库的代码边界; 进而基于此提出一套软件库依赖图谱的复杂性度量指标RMS, 用以量化不同来源软件之间的耦合强度. 在实验过程中, 挖掘Apache开源社区中10个流行软件所有历史版本数据, 最终收集到7857个真实项目间依赖缺陷问题. 在上述真实数据基础上, 结合所提出的复杂性度量指标RMS, 利用假设验证方法开展实证调查研究来探讨: H1: 风险因子更高的边界节点是否更容易引入更多数量的项目间依赖缺陷; H2: 风险因子更高的边界节点会是否更容易引入严重等级高的项目间依赖缺陷; H3: RMS度量指标数值多大程度地影响了引入项目间依赖缺陷数量和严重等级. 实验结果表明, 根据RMS度量指标评估, 与软件库耦合度更高的边界节点容易引入更多数量且严重等级高的项目间依赖缺陷. 与传统复杂性度量指标对比, RMS度量指标较大程度地影响了引入项目间依赖缺陷的数量和严重等级.
在软件开发过程中, 软件库可以减少开发时间和节约成本而被广泛使用, 因此现代软件项目包含多种不同来源的代码而使得系统具有更高的复杂性和多样性. 软件库在使用的过程中常常伴随着各种风险, 如低质量或安全漏洞, 从而严重影响软件项目的质量. 通过分析与软件库的耦合强度, 来量化由软件库的依赖关系而引入客户代码的复杂性和多样性. 首先, 根据客户代码与软件库之间方法的调用关系建立软件边界图模型, 区分开客户代码和软件库的代码边界; 进而基于此提出一套软件库依赖图谱的复杂性度量指标RMS, 用以量化不同来源软件之间的耦合强度. 在实验过程中, 挖掘Apache开源社区中10个流行软件所有历史版本数据, 最终收集到7857个真实项目间依赖缺陷问题. 在上述真实数据基础上, 结合所提出的复杂性度量指标RMS, 利用假设验证方法开展实证调查研究来探讨: H1: 风险因子更高的边界节点是否更容易引入更多数量的项目间依赖缺陷; H2: 风险因子更高的边界节点会是否更容易引入严重等级高的项目间依赖缺陷; H3: RMS度量指标数值多大程度地影响了引入项目间依赖缺陷数量和严重等级. 实验结果表明, 根据RMS度量指标评估, 与软件库耦合度更高的边界节点容易引入更多数量且严重等级高的项目间依赖缺陷. 与传统复杂性度量指标对比, RMS度量指标较大程度地影响了引入项目间依赖缺陷的数量和严重等级.
2023, 34(11):5312-5329.
DOI: 10.13328/j.cnki.jos.006748
摘要:
认证数据结构(authenticated data structure, ADS) 解决了数据外包存储场景下服务器的不可信问题, 用户通过ADS可以验证不可信服务器返回查询结果的正确性与完整性, 但数据拥有者的安全性难以保证, 攻击者可以篡改数据拥有者存储的ADS, 破坏对查询结果的完整性、正确性验证. 数据拥有者将ADS存储在区块链上, 借助区块链的不可篡改性, 可以解决上述问题. 但现有ADS实现方案在区块链上维护成本较高并且大部分只支持静态数据的可验证查询, 目前缺少一种针对区块链设计的高效ADS. 通过分析智能合约的gas消耗机制与基于传统MHT的ADS的gas开销, 提出一种新型ADS认证结构SMT, 实现对流数据的高效可验证查询, 并且在区块链上具备更低的gas消耗. 从理论及实验出发, 验证了SMT的高效性, 通过安全性分析, 证明了SMT的安全性.
认证数据结构(authenticated data structure, ADS) 解决了数据外包存储场景下服务器的不可信问题, 用户通过ADS可以验证不可信服务器返回查询结果的正确性与完整性, 但数据拥有者的安全性难以保证, 攻击者可以篡改数据拥有者存储的ADS, 破坏对查询结果的完整性、正确性验证. 数据拥有者将ADS存储在区块链上, 借助区块链的不可篡改性, 可以解决上述问题. 但现有ADS实现方案在区块链上维护成本较高并且大部分只支持静态数据的可验证查询, 目前缺少一种针对区块链设计的高效ADS. 通过分析智能合约的gas消耗机制与基于传统MHT的ADS的gas开销, 提出一种新型ADS认证结构SMT, 实现对流数据的高效可验证查询, 并且在区块链上具备更低的gas消耗. 从理论及实验出发, 验证了SMT的高效性, 通过安全性分析, 证明了SMT的安全性.
2023, 34(11):5330-5354.
DOI: 10.13328/j.cnki.jos.006669
摘要:
可编程数据平面(PDP)一方面支持网络应用的卸载与加速, 给网络应用带来了革命性的发展机遇; 另一方面支持新协议、新服务的快速实现和部署, 促进了网络创新和演进, 是近年来网络领域的研究热点. FPGA因其通用的计算架构、丰富的片内资源和扩展接口提供了多种可编程数据平面的具体实现, 支持更广范围的应用场景. 同时, FPGA还为探索更通用的可编程数据平面抽象提供了可能. 因此, 基于FPGA的可编程数据平面受到了学术界与产业界的广泛关注. 首先分类别阐述基于FPGA的可编程数据平面(F-PDP)抽象. 接着, 介绍基于F-PDP快速构建网络应用的关键技术的研究进展. 之后, 介绍基于F-PDP的新型可编程网络设备. 此外, 从提升网络性能、构建网络测量框架以及部署网络安全应用这3个方面, 详细梳理近年来基于F-PDP的应用研究成果. 最后, 探讨F-PDP未来可能的研究趋势.
可编程数据平面(PDP)一方面支持网络应用的卸载与加速, 给网络应用带来了革命性的发展机遇; 另一方面支持新协议、新服务的快速实现和部署, 促进了网络创新和演进, 是近年来网络领域的研究热点. FPGA因其通用的计算架构、丰富的片内资源和扩展接口提供了多种可编程数据平面的具体实现, 支持更广范围的应用场景. 同时, FPGA还为探索更通用的可编程数据平面抽象提供了可能. 因此, 基于FPGA的可编程数据平面受到了学术界与产业界的广泛关注. 首先分类别阐述基于FPGA的可编程数据平面(F-PDP)抽象. 接着, 介绍基于F-PDP快速构建网络应用的关键技术的研究进展. 之后, 介绍基于F-PDP的新型可编程网络设备. 此外, 从提升网络性能、构建网络测量框架以及部署网络安全应用这3个方面, 详细梳理近年来基于F-PDP的应用研究成果. 最后, 探讨F-PDP未来可能的研究趋势.
2023, 34(11):5355-5375.
DOI: 10.13328/j.cnki.jos.006733
摘要:
WiFi作为当前最重要的通信方式之一, 基于WiFi信号的室内定位系统最有望在日常生活中得到广泛地部署应用. 最新研究表明, 当采用WiFi通信过程中获取的信道状态信息(CSI)对目标进行定位时, 系统可实现亚米级的定位精度. 然而, 实验场景下的定位精度受到测试样点位置、WiFi设备布局、天线布局等诸多因素的影响. 因为目前仍缺少WiFi CSI定位性能预测方法, WiFi定位系统部署后往往难以获得预期的精度. 为此, 面向多样化场景提出WiFi CSI定位性能的预测模型. 首先, 从CSI定位的基本物理模型出发, 定义天线对的误差微元函数, 并通过对定位空间的分析生成误差微元矩阵以及定位性能热度图; 其次, 对天线对进行拓展, 通过引入多天线融合方法、多设备融合方法构建通用的CSI定位性能预测模型; 最后, 为了将真实场景地图考虑在内, 提出将上述热度图与场景地图相融合的方法, 从而实现场景定制化的性能预测. 在理论分析的基础上, 结合2个不同场景下的实验数据验证了定位性能预测模型有效性. 实验结果表明, 实际定位精度的变化趋势与理论模型相吻合, 通过理论模型分析可将定位精度优化32%–37%.
WiFi作为当前最重要的通信方式之一, 基于WiFi信号的室内定位系统最有望在日常生活中得到广泛地部署应用. 最新研究表明, 当采用WiFi通信过程中获取的信道状态信息(CSI)对目标进行定位时, 系统可实现亚米级的定位精度. 然而, 实验场景下的定位精度受到测试样点位置、WiFi设备布局、天线布局等诸多因素的影响. 因为目前仍缺少WiFi CSI定位性能预测方法, WiFi定位系统部署后往往难以获得预期的精度. 为此, 面向多样化场景提出WiFi CSI定位性能的预测模型. 首先, 从CSI定位的基本物理模型出发, 定义天线对的误差微元函数, 并通过对定位空间的分析生成误差微元矩阵以及定位性能热度图; 其次, 对天线对进行拓展, 通过引入多天线融合方法、多设备融合方法构建通用的CSI定位性能预测模型; 最后, 为了将真实场景地图考虑在内, 提出将上述热度图与场景地图相融合的方法, 从而实现场景定制化的性能预测. 在理论分析的基础上, 结合2个不同场景下的实验数据验证了定位性能预测模型有效性. 实验结果表明, 实际定位精度的变化趋势与理论模型相吻合, 通过理论模型分析可将定位精度优化32%–37%.
2023, 34(11):5376-5391.
DOI: 10.13328/j.cnki.jos.006738
摘要:
为解决量子通信过程中的身份认证及协议的可实现性问题, 提出一种基于测量设备无关的带身份认证服务器的量子安全直接通信协议, 并依据该协议提出一种量子投票方案. 所提方案利用测量设备无关的量子密钥分配, 完备的量子加密, 以及经典的一次一密等技术, 不仅理论上确保方案的无条件安全性, 而在实际上也避免外部攻击者对测量设备漏洞的攻击. 此外, 所提方案使用BB84态的弱相干脉冲作为量子资源, 仅实施单粒子操作, 以及识别Bell态的测量. 因此, 基于现有技术, 所提方案具有良好的可实现性. 同时所提方案扩展了身份认证功能, 引入比特承诺, 使得监票人可以验证投票信息的完整性和正确性. 仿真结果和分析表明, 所提方案是正确的并具有理论上无条件的安全性, 即信息理论安全. 相较于现有的量子投票方案, 所提方案具有更好的可行性.
为解决量子通信过程中的身份认证及协议的可实现性问题, 提出一种基于测量设备无关的带身份认证服务器的量子安全直接通信协议, 并依据该协议提出一种量子投票方案. 所提方案利用测量设备无关的量子密钥分配, 完备的量子加密, 以及经典的一次一密等技术, 不仅理论上确保方案的无条件安全性, 而在实际上也避免外部攻击者对测量设备漏洞的攻击. 此外, 所提方案使用BB84态的弱相干脉冲作为量子资源, 仅实施单粒子操作, 以及识别Bell态的测量. 因此, 基于现有技术, 所提方案具有良好的可实现性. 同时所提方案扩展了身份认证功能, 引入比特承诺, 使得监票人可以验证投票信息的完整性和正确性. 仿真结果和分析表明, 所提方案是正确的并具有理论上无条件的安全性, 即信息理论安全. 相较于现有的量子投票方案, 所提方案具有更好的可行性.
2023, 34(11):5392-5407.
DOI: 10.13328/j.cnki.jos.006685
摘要:
对称可搜索加密(symmetric searchable encryption, SSE)能实现密文数据的检索而不泄露用户隐私, 在云存储领域得到了广泛的研究与应用. 然而, 在SSE方案中, 半诚实或者不诚实的服务器可能篡改文件中的数据, 返回给用户不可信的文件, 因此对这些文件进行验证是十分必要的. 现有的可验证SSE方案大多是用户本地进行验证, 恶意用户可能会伪造验证结果, 无法保证验证的公平性. 基于以上考虑, 提出一种基于区块链的动态可验证对称可搜索加密方案(verifiable dynamic symmetric searchable encryption, VDSSE); VDSSE采用对称加密实现动态更新过程中的前向安全; 在此基础上, 利用区块链实现搜索结果的验证, 验证过程中, 提出一种新的验证标签——Vtag, 利用Vtag的累积性实现验证信息的压缩存储, 降低验证信息在区块链上的存储开销, 并能够有效支持SSE方案的动态验证. 由于区块链具有不可篡改的性质, 验证的公平性得以保证. 最后, 对VDSSE进行实验评估和安全性分析, 验证方案的可行性和安全性.
对称可搜索加密(symmetric searchable encryption, SSE)能实现密文数据的检索而不泄露用户隐私, 在云存储领域得到了广泛的研究与应用. 然而, 在SSE方案中, 半诚实或者不诚实的服务器可能篡改文件中的数据, 返回给用户不可信的文件, 因此对这些文件进行验证是十分必要的. 现有的可验证SSE方案大多是用户本地进行验证, 恶意用户可能会伪造验证结果, 无法保证验证的公平性. 基于以上考虑, 提出一种基于区块链的动态可验证对称可搜索加密方案(verifiable dynamic symmetric searchable encryption, VDSSE); VDSSE采用对称加密实现动态更新过程中的前向安全; 在此基础上, 利用区块链实现搜索结果的验证, 验证过程中, 提出一种新的验证标签——Vtag, 利用Vtag的累积性实现验证信息的压缩存储, 降低验证信息在区块链上的存储开销, 并能够有效支持SSE方案的动态验证. 由于区块链具有不可篡改的性质, 验证的公平性得以保证. 最后, 对VDSSE进行实验评估和安全性分析, 验证方案的可行性和安全性.
2023, 34(11):5408-5423.
DOI: 10.13328/j.cnki.jos.006737
摘要:
随着信息通信技术的不断突破与发展, 信息获取变得非常便利. 与此同时, 隐私信息也更容易泄露. 将智能领域与安全多方计算技术相结合, 有望解决隐私保护问题. 目前, 安全多方计算已经解决了许多不同隐私保护问题, 但还有更多的问题等待人们去解决. 对于极差、极值和的安全多方计算问题目前研究的结果很少, 极差、极值和作为统计学的常用工具在实际中有广泛的应用, 研究极差、极值和的保密计算具有重要意义. 提出新编码方法, 用新编码方法解决了两种不同的安全多方计算问题, 一是极差的保密计算问题, 二是极值和的保密计算问题. 新编码方法结合Lifted ElGamal门限密码系统, 设计多方参与、每方拥有一个数据场景下分布式隐私数据集极差的保密计算协议; 将新编码方法稍作改动解决相同场景下保密计算极值和的问题. 以此为基础, 对新编码方法进一步修改, 结合Paillier密码系统设计了两方参与、每方拥有多个数据情况下分布式隐私数据集极差、极值和的保密计算协议. 用模拟范例方法证明协议在半诚实模型下的安全性. 最后, 用模拟实验测试协议的复杂性. 效率分析和实验结果表明所提协议简单高效, 可广泛用于实际应用中, 是解决其他很多安全多方计算问题的重要工具.
随着信息通信技术的不断突破与发展, 信息获取变得非常便利. 与此同时, 隐私信息也更容易泄露. 将智能领域与安全多方计算技术相结合, 有望解决隐私保护问题. 目前, 安全多方计算已经解决了许多不同隐私保护问题, 但还有更多的问题等待人们去解决. 对于极差、极值和的安全多方计算问题目前研究的结果很少, 极差、极值和作为统计学的常用工具在实际中有广泛的应用, 研究极差、极值和的保密计算具有重要意义. 提出新编码方法, 用新编码方法解决了两种不同的安全多方计算问题, 一是极差的保密计算问题, 二是极值和的保密计算问题. 新编码方法结合Lifted ElGamal门限密码系统, 设计多方参与、每方拥有一个数据场景下分布式隐私数据集极差的保密计算协议; 将新编码方法稍作改动解决相同场景下保密计算极值和的问题. 以此为基础, 对新编码方法进一步修改, 结合Paillier密码系统设计了两方参与、每方拥有多个数据情况下分布式隐私数据集极差、极值和的保密计算协议. 用模拟范例方法证明协议在半诚实模型下的安全性. 最后, 用模拟实验测试协议的复杂性. 效率分析和实验结果表明所提协议简单高效, 可广泛用于实际应用中, 是解决其他很多安全多方计算问题的重要工具.
2023, 34(11):5424-5441.
DOI: 10.13328/j.cnki.jos.006743
摘要:
$ (t, n) $门限隐私集合交集协议, 指$ N $个参与者各自拥有大小为$ n $的隐私集合, 在不泄露自身隐私信息的前提下, 如果各参与者交集数量大于门限值$ t $, 则参与各方能够获得交集信息, 其有广泛的应用, 如指纹识别、在线拼车、相亲网站等. 然而现有门限隐私集合交集协议大多针对两方参与者进行研究, 对多方门限隐私集合交集协议的研究仍存在许多挑战, 现有的多方门限隐私集合交集协议使用全同态加密等开销较大的公钥算法, 尚没有有效实现. 针对上述问题, 结合弹性秘密共享、布隆过滤器提出两种有效的多方门限隐私集合交集协议, 并首次仿真实现了协议. 首先, 设计一种新的布隆过滤器构造方法, 将弹性秘密共享生成的份额与参与方的集合元素相对应, 通过查询布隆过滤器获取的秘密子份额能否重构出正确秘密来判断各方交集是否达到门限值, 有效防止交集基数的泄露. 设计的第1个协议避免使用开销较大的公钥算法, 当设置安全参数$ \lambda $为128, 集合大小为$ {2^{14}} $, 门限值为$ 0.8n $时, 在三方场景下协议在线阶段的时间成本为191 s. 此外, 为了能在半诚实模型下抵抗至多$ N - 1 $个敌手合谋, 在第1个协议基础上结合不经意传输设计一种该协议的变体, 相同条件下, 在线阶段时间成本为194 s. 最后通过安全证明, 证明上述协议在半诚实模型下是安全的.
$ (t, n) $门限隐私集合交集协议, 指$ N $个参与者各自拥有大小为$ n $的隐私集合, 在不泄露自身隐私信息的前提下, 如果各参与者交集数量大于门限值$ t $, 则参与各方能够获得交集信息, 其有广泛的应用, 如指纹识别、在线拼车、相亲网站等. 然而现有门限隐私集合交集协议大多针对两方参与者进行研究, 对多方门限隐私集合交集协议的研究仍存在许多挑战, 现有的多方门限隐私集合交集协议使用全同态加密等开销较大的公钥算法, 尚没有有效实现. 针对上述问题, 结合弹性秘密共享、布隆过滤器提出两种有效的多方门限隐私集合交集协议, 并首次仿真实现了协议. 首先, 设计一种新的布隆过滤器构造方法, 将弹性秘密共享生成的份额与参与方的集合元素相对应, 通过查询布隆过滤器获取的秘密子份额能否重构出正确秘密来判断各方交集是否达到门限值, 有效防止交集基数的泄露. 设计的第1个协议避免使用开销较大的公钥算法, 当设置安全参数$ \lambda $为128, 集合大小为$ {2^{14}} $, 门限值为$ 0.8n $时, 在三方场景下协议在线阶段的时间成本为191 s. 此外, 为了能在半诚实模型下抵抗至多$ N - 1 $个敌手合谋, 在第1个协议基础上结合不经意传输设计一种该协议的变体, 相同条件下, 在线阶段时间成本为194 s. 最后通过安全证明, 证明上述协议在半诚实模型下是安全的.
2023, 34(11):5442-5456.
DOI: 10.13328/j.cnki.jos.006747
摘要:
超阈值多方隐私集合求交协议(OT-MP-PSI)是PSI协议的变体, 允许m个参与方共同计算至少t (t≤m)个参与方中拥有相同元素的超阈值交集, 且保证仅拥有超阈值元素的参与方才能知晓该元素是否属于超阈值交集, 对于其他信息一无所知. OT-MP-PSI推广了PSI的实际应用场景. 现有方案均基于昂贵的公钥密码来构建, 其较大的计算量导致运行时间缓慢. 首先设计一个基于对称密码的不经意可编程伪随机秘密共享(OPPR-SS)密码组件, 并基于 OPPR-SS组件设计双云辅助的OT-MP-PSI协议, 将秘密分发和重构的任务分别交给不可信云服务器来辅助完成, 实现弱计算能力的参与方也能完成 OT-MP-PSI协议. 在半诚实模型下证明协议安全性. 相比现有的OT-MP-PSI协议, 所提协议在秘密分发和重构阶段均具有最优运行时间和通信负载, 参与方、共享方和重构方的通信复杂度不再与阈值t有关, 实现参与方常数轮的通信, 通信复杂度仅为O(n), 秘密分发方和重构方的计算复杂度仅与对称密码次数有关.
超阈值多方隐私集合求交协议(OT-MP-PSI)是PSI协议的变体, 允许m个参与方共同计算至少t (t≤m)个参与方中拥有相同元素的超阈值交集, 且保证仅拥有超阈值元素的参与方才能知晓该元素是否属于超阈值交集, 对于其他信息一无所知. OT-MP-PSI推广了PSI的实际应用场景. 现有方案均基于昂贵的公钥密码来构建, 其较大的计算量导致运行时间缓慢. 首先设计一个基于对称密码的不经意可编程伪随机秘密共享(OPPR-SS)密码组件, 并基于 OPPR-SS组件设计双云辅助的OT-MP-PSI协议, 将秘密分发和重构的任务分别交给不可信云服务器来辅助完成, 实现弱计算能力的参与方也能完成 OT-MP-PSI协议. 在半诚实模型下证明协议安全性. 相比现有的OT-MP-PSI协议, 所提协议在秘密分发和重构阶段均具有最优运行时间和通信负载, 参与方、共享方和重构方的通信复杂度不再与阈值t有关, 实现参与方常数轮的通信, 通信复杂度仅为O(n), 秘密分发方和重构方的计算复杂度仅与对称密码次数有关.
联系方式
- 《软件学报 》
- 主办单位：中国科学院软件研究所
中国计算机学会 - 邮编：100190
- 电话：010-62562563
- 电子邮箱：jos@iscas.ac.cn
- 网址：https://www.jos.org.cn
- 刊号：ISSN 1000-9825
- CN 11-2560/TP
- 国内定价：70元
您是第位访问者
版权所有：中国科学院软件研究所 京ICP备05046678号-3
地址：北京市海淀区中关村南四街4号,邮政编码：100190
电话：010-62562563 传真：010-62562533 Email：jos@iscas.ac.cn
技术支持：北京勤云科技发展有限公司
版权所有：中国科学院软件研究所 京ICP备05046678号-3
地址：北京市海淀区中关村南四街4号,邮政编码：100190
电话：010-62562563 传真：010-62562533 Email：jos@iscas.ac.cn
技术支持：北京勤云科技发展有限公司
