2021年第32卷第9期文章目次
2021, 32(9):2629-2641.
DOI: 10.13328/j.cnki.jos.006049
摘要:
3-CNF公式的随机难解实例生成对于揭示3-SAT问题的难解实质和设计满足性测试的有效算法有着重要意义.对于整数k>2和s>0，如果在一个k-CNF公式中每个变量正负出现次数均为s，则称该公式是严格正则（k，2s）-CNF公式.受严格正则（k，2s）-CNF公式的结构特征启发，提出每个变量正负出现次数之差的绝对值均为d的严格d-正则（k，2s）-CNF公式，并使用新提出的SDRRK2S模型生成严格d-正则随机（k，2s）-CNF公式.取定整数5<s<11，模拟实验显示，严格d-正则随机（3，2s）-SAT问题存在SAT-UNSAT相变现象和HARD-EASY相变现象.因此，立足于3-CNF公式的随机难解实例生成，研究了严格d-正则随机（3，2s）-SAT问题在s取定时的可满足临界.通过构造一个特殊随机实验和使用一阶矩方法，得到了严格d-正则随机（3，2s）-SAT问题在s取定时可满足临界值的一个下界.模拟实验结果验证了理论证明所得下界的正确性.
3-CNF公式的随机难解实例生成对于揭示3-SAT问题的难解实质和设计满足性测试的有效算法有着重要意义.对于整数k>2和s>0，如果在一个k-CNF公式中每个变量正负出现次数均为s，则称该公式是严格正则（k，2s）-CNF公式.受严格正则（k，2s）-CNF公式的结构特征启发，提出每个变量正负出现次数之差的绝对值均为d的严格d-正则（k，2s）-CNF公式，并使用新提出的SDRRK2S模型生成严格d-正则随机（k，2s）-CNF公式.取定整数5<s<11，模拟实验显示，严格d-正则随机（3，2s）-SAT问题存在SAT-UNSAT相变现象和HARD-EASY相变现象.因此，立足于3-CNF公式的随机难解实例生成，研究了严格d-正则随机（3，2s）-SAT问题在s取定时的可满足临界.通过构造一个特殊随机实验和使用一阶矩方法，得到了严格d-正则随机（3，2s）-SAT问题在s取定时可满足临界值的一个下界.模拟实验结果验证了理论证明所得下界的正确性.
2021, 32(9):2642-2664.
DOI: 10.13328/j.cnki.jos.006275
摘要:
背景：近年来，领域驱动设计（domain driven design，简称DDD）作为一种软件设计方法在业界中逐渐流行起来，并形成了若干应用的固有范式，即领域驱动设计模式（domain driven design pattern，简称DDDP）.然而，目前软件开发社区却仍然对DDDP在软件项目中的作用缺少较为全面的了解.目的：旨在揭示DDDP的应用情况，即哪些DDDP被应用到了软件开发中，以及其所带来的收益、挑战及相应的缓解挑战方法.方法：应用系统化文献综述方法，对2003年~2019年7月之间发表的相关文献进行了识别、筛选、汇总和分析.结果：通过结合手动检索、自动检索和滚雪球等过程，覆盖了1 884篇相关文献，经过筛选，最终得到26篇高质量文献，对应26个独立的研究.总结了基础研究中DDDP的应用概况，即已经被应用到软件开发中的DDDP以及应用DDDP所获得的11项收益、17个挑战以及相应的缓解挑战方法.结论：因为对领域知识非常重视，领域驱动设计能够帮助实践者更好地进行软件设计，但在具体应用领域驱动设计模式时却存在着诸多挑战.虽然目前存在一些缓解方法能够在一定程度上应对挑战，但是仍然存在很多不足.通过系统文献综述，填补了学术界在这一领域的空白.考虑到DDDP的实践价值与当前理论成熟度的不匹配，未来工业界和学术界应该给予该领域更多关注.
背景：近年来，领域驱动设计（domain driven design，简称DDD）作为一种软件设计方法在业界中逐渐流行起来，并形成了若干应用的固有范式，即领域驱动设计模式（domain driven design pattern，简称DDDP）.然而，目前软件开发社区却仍然对DDDP在软件项目中的作用缺少较为全面的了解.目的：旨在揭示DDDP的应用情况，即哪些DDDP被应用到了软件开发中，以及其所带来的收益、挑战及相应的缓解挑战方法.方法：应用系统化文献综述方法，对2003年~2019年7月之间发表的相关文献进行了识别、筛选、汇总和分析.结果：通过结合手动检索、自动检索和滚雪球等过程，覆盖了1 884篇相关文献，经过筛选，最终得到26篇高质量文献，对应26个独立的研究.总结了基础研究中DDDP的应用概况，即已经被应用到软件开发中的DDDP以及应用DDDP所获得的11项收益、17个挑战以及相应的缓解挑战方法.结论：因为对领域知识非常重视，领域驱动设计能够帮助实践者更好地进行软件设计，但在具体应用领域驱动设计模式时却存在着诸多挑战.虽然目前存在一些缓解方法能够在一定程度上应对挑战，但是仍然存在很多不足.通过系统文献综述，填补了学术界在这一领域的空白.考虑到DDDP的实践价值与当前理论成熟度的不匹配，未来工业界和学术界应该给予该领域更多关注.
2021, 32(9):2665-2690.
DOI: 10.13328/j.cnki.jos.006274
摘要:
软件缺陷是软件开发和维护过程中不可避免的.随着现代软件规模的不断变大，软件缺陷的数量以及修复难度随之增加，为企业带来了巨大的经济损失.修复软件缺陷，成为了开发人员维护软件质量的重大负担.软件缺陷自动修复技术有希望将开发者从繁重的调试中解脱出来，近年来成为热门的研究领域之一.搜集了94篇该领域最新的高水平论文，进行了详细的分析和总结.基于缺陷修复技术在补丁生成阶段所使用的技术手段不同，系统性地将软件自动修复技术分为4大类，分别是基于启发式搜索、基于人工模板、基于语义约束和基于统计分析的修复技术.特殊地，根据对近几年最新研究的总结，首次提出了基于统计分析的技术分类，对已有分类进行了补充和完善.随后，基于对已有研究的分析，总结了该领域研究所面临的关键挑战及对未来研究的启示.最后，对缺陷修复领域常用的基准数据集和开源工具进行了总结.
软件缺陷是软件开发和维护过程中不可避免的.随着现代软件规模的不断变大，软件缺陷的数量以及修复难度随之增加，为企业带来了巨大的经济损失.修复软件缺陷，成为了开发人员维护软件质量的重大负担.软件缺陷自动修复技术有希望将开发者从繁重的调试中解脱出来，近年来成为热门的研究领域之一.搜集了94篇该领域最新的高水平论文，进行了详细的分析和总结.基于缺陷修复技术在补丁生成阶段所使用的技术手段不同，系统性地将软件自动修复技术分为4大类，分别是基于启发式搜索、基于人工模板、基于语义约束和基于统计分析的修复技术.特殊地，根据对近几年最新研究的总结，首次提出了基于统计分析的技术分类，对已有分类进行了补充和完善.随后，基于对已有研究的分析，总结了该领域研究所面临的关键挑战及对未来研究的启示.最后，对缺陷修复领域常用的基准数据集和开源工具进行了总结.
2021, 32(9):2691-2712.
DOI: 10.13328/j.cnki.jos.005984
摘要:
软件测试是软件开发中重要的一环，能有效地提高软件的可靠性和质量.而测试用例的重用可减少软件测试的工作量，提升测试的效率.提出一种面向关键字流图的相似程序间测试用例的重用方法，该方法将程序已经生成的测试数据重用到与之相似的程序中.可见，探究测试用例重用的前期工作是判定程序的相似性.对于程序相似性的判定，给出根据关键字流图相似性比较的方法：首先，将程序代码中的关键字存储在流图所对应的节点中，构建关键字流图；接下来，利用动态规划算法查找待测程序关键字流图的最大公共子图；最后，根据最大公共子图距离算法计算程序的相似度.较高相似程度的程序可用到测试用例重用的方法中.在利用遗传算法生成测试用例时，引用相似程序中适应度较高的测试用例，使种群在进行进化操作过程中不断与这些用例进行交叉，加快用例的生成效率.实验表明：将测试用例重用在相似程序的测试生成中，与传统方法相比，在覆盖率和平均进化代数等方面均有明显优势.
软件测试是软件开发中重要的一环，能有效地提高软件的可靠性和质量.而测试用例的重用可减少软件测试的工作量，提升测试的效率.提出一种面向关键字流图的相似程序间测试用例的重用方法，该方法将程序已经生成的测试数据重用到与之相似的程序中.可见，探究测试用例重用的前期工作是判定程序的相似性.对于程序相似性的判定，给出根据关键字流图相似性比较的方法：首先，将程序代码中的关键字存储在流图所对应的节点中，构建关键字流图；接下来，利用动态规划算法查找待测程序关键字流图的最大公共子图；最后，根据最大公共子图距离算法计算程序的相似度.较高相似程度的程序可用到测试用例重用的方法中.在利用遗传算法生成测试用例时，引用相似程序中适应度较高的测试用例，使种群在进行进化操作过程中不断与这些用例进行交叉，加快用例的生成效率.实验表明：将测试用例重用在相似程序的测试生成中，与传统方法相比，在覆盖率和平均进化代数等方面均有明显优势.
2021, 32(9):2713-2728.
DOI: 10.13328/j.cnki.jos.005990
摘要:
基于日志分析的故障诊断是智能运维的关键技术之一，然而该技术存在关键瓶颈——日志的质量.当今，由于程序开发人员缺乏日志打印规范和指导等问题，日志质量欠佳，因此实现日志的自动化打印决策以提升日志质量的需求日益迫切.关注自动化日志打印决策问题，与现有研究工作不同，提出一种基于程序层次树和逆序组合的特征向量生成方法，能够适用于不同编程语言编写的软件系统.此外，还利用迁移学习算法实现跨组件和跨软件系统的日志打印位置决策.在3个典型的应用场景——版本升级、组件开发和系统开发及5个流行的开源软件系统——OpenStack，Tensorflow，SaltCloud，Hadoop和Angel上的实验表明：所述方法在Java系统中的日志打印决策准确率约为95%，在Python系统中的日志打印决策准确率约为70%.
基于日志分析的故障诊断是智能运维的关键技术之一，然而该技术存在关键瓶颈——日志的质量.当今，由于程序开发人员缺乏日志打印规范和指导等问题，日志质量欠佳，因此实现日志的自动化打印决策以提升日志质量的需求日益迫切.关注自动化日志打印决策问题，与现有研究工作不同，提出一种基于程序层次树和逆序组合的特征向量生成方法，能够适用于不同编程语言编写的软件系统.此外，还利用迁移学习算法实现跨组件和跨软件系统的日志打印位置决策.在3个典型的应用场景——版本升级、组件开发和系统开发及5个流行的开源软件系统——OpenStack，Tensorflow，SaltCloud，Hadoop和Angel上的实验表明：所述方法在Java系统中的日志打印决策准确率约为95%，在Python系统中的日志打印决策准确率约为70%.
2021, 32(9):2729-2743.
DOI: 10.13328/j.cnki.jos.006075
摘要:
微服务系统每轮迭代过程中都需要进行回归测试，大量重复测试会造成资源浪费，可通过减少测试用例集的规模来降低成本，以提高测试效率.现有测试用例集缩减技术主要依赖系统规约和架构描述作为输入，对于具有服务自治、调用关系不确定等特点的微服务系统实用性受限.并且，现有测试用例集缩减技术很少考虑使用场景，测试用例集很难反映用户关切.提出了一种基于API网关层日志挖掘的测试用例集缩减技术，从API网关层日志中挖掘出能够反映服务使用场景的频繁调用路径，建立频繁路径与测试用例的关联关系，进而构建搜索图，并基于启发式搜索生成测试用例缩减集.描述了该技术的完整过程，并基于一个集成办公微服务系统进行了实验.实验结果表明：该技术能够缩减测试用例规模40%以上，且缺陷发现能力降幅不超过10%.
微服务系统每轮迭代过程中都需要进行回归测试，大量重复测试会造成资源浪费，可通过减少测试用例集的规模来降低成本，以提高测试效率.现有测试用例集缩减技术主要依赖系统规约和架构描述作为输入，对于具有服务自治、调用关系不确定等特点的微服务系统实用性受限.并且，现有测试用例集缩减技术很少考虑使用场景，测试用例集很难反映用户关切.提出了一种基于API网关层日志挖掘的测试用例集缩减技术，从API网关层日志中挖掘出能够反映服务使用场景的频繁调用路径，建立频繁路径与测试用例的关联关系，进而构建搜索图，并基于启发式搜索生成测试用例缩减集.描述了该技术的完整过程，并基于一个集成办公微服务系统进行了实验.实验结果表明：该技术能够缩减测试用例规模40%以上，且缺陷发现能力降幅不超过10%.
2021, 32(9):2744-2754.
DOI: 10.13328/j.cnki.jos.005974
摘要:
扩展规则推理方法在经典的可满足性问题求解中已得到广泛应用，若干个基于扩展规则的推理方法已被提出，皆得到国内外的认可，例如完备的NER，IMOMH_IER，PPSER算法以及基于局部搜索的不完备算法ERACC等，都具有良好的求解效果.其中，ERACC算法是当前扩展规则求解器中求解效率最高、能力最强的算法.但是，串行的ERACC算法在启发式和预处理上仍然具有可提升的空间.基于此，设计了相应的并行框架，提出了PERACC算法.该算法基于格局检测的局部搜索方法，从变量赋初始值、化简解空间和启发式这3个阶段出发，将原极大项空间分解成为若干极大项子空间，并对原子句集进行化简后，并行处理各个子空间.通过实验显示：该算法与原算法相比，不仅在求解效率方面有较大提高，而且可以求解规模更大的测试用例，使扩展规则方法再次突破公式规模的限制.
扩展规则推理方法在经典的可满足性问题求解中已得到广泛应用，若干个基于扩展规则的推理方法已被提出，皆得到国内外的认可，例如完备的NER，IMOMH_IER，PPSER算法以及基于局部搜索的不完备算法ERACC等，都具有良好的求解效果.其中，ERACC算法是当前扩展规则求解器中求解效率最高、能力最强的算法.但是，串行的ERACC算法在启发式和预处理上仍然具有可提升的空间.基于此，设计了相应的并行框架，提出了PERACC算法.该算法基于格局检测的局部搜索方法，从变量赋初始值、化简解空间和启发式这3个阶段出发，将原极大项空间分解成为若干极大项子空间，并对原子句集进行化简后，并行处理各个子空间.通过实验显示：该算法与原算法相比，不仅在求解效率方面有较大提高，而且可以求解规模更大的测试用例，使扩展规则方法再次突破公式规模的限制.
2021, 32(9):2755-2768.
DOI: 10.13328/j.cnki.jos.005986
摘要:
设计了新的生成器网络、判决器网络以及新的损失函数，用于图像场景转换.首先，生成器网络采用了带跨层连接结构的深度卷积神经网络，其中，多个跨层连接以实现图像结构信息的共享；而判决器网络采用了多尺度全域卷积网络，多尺度判决器可以区分不同尺寸下的真实和生成图像.同时，对于损失函数，该算法借鉴其他算法提出了4种损失函数的组合，并通过实验对比证明了新损失函数的有效性，包括GAN损失、L1损失、VGG损失、FM损失.从实验结果显示，该算法能够实现多种转换，且转换后图像的细节保留较为完整，生成图像较为真实，明显消除了块效应.
设计了新的生成器网络、判决器网络以及新的损失函数，用于图像场景转换.首先，生成器网络采用了带跨层连接结构的深度卷积神经网络，其中，多个跨层连接以实现图像结构信息的共享；而判决器网络采用了多尺度全域卷积网络，多尺度判决器可以区分不同尺寸下的真实和生成图像.同时，对于损失函数，该算法借鉴其他算法提出了4种损失函数的组合，并通过实验对比证明了新损失函数的有效性，包括GAN损失、L1损失、VGG损失、FM损失.从实验结果显示，该算法能够实现多种转换，且转换后图像的细节保留较为完整，生成图像较为真实，明显消除了块效应.
2021, 32(9):2769-2782.
DOI: 10.13328/j.cnki.jos.005989
摘要:
并行传播是并行约束程序领域中的一个研究方向，其研究内容是如何并行执行在约束上的过滤算法.根据维持表约束网络广义弧相容（generalized arc consistency，简称GAC）的串行传播模式，提出了维持表约束网络临时广义弧相容（temporary generalized arc consistency，简称TGAC）的并行传播模式，该模式基于多核CPU，由并行传播算法和并行过滤算法两部分组成；之后，给出了并行传播模式的可靠性证明，而且通过对并行传播模式的最坏时间复杂度分析，可以认为并行传播模式在平均过滤时间较长的实例上要快于串行传播模式；最终的实验结果也验证了上述结论，并行传播模式在多数实例集上取得了从1.4~3.4不等的加速比.
并行传播是并行约束程序领域中的一个研究方向，其研究内容是如何并行执行在约束上的过滤算法.根据维持表约束网络广义弧相容（generalized arc consistency，简称GAC）的串行传播模式，提出了维持表约束网络临时广义弧相容（temporary generalized arc consistency，简称TGAC）的并行传播模式，该模式基于多核CPU，由并行传播算法和并行过滤算法两部分组成；之后，给出了并行传播模式的可靠性证明，而且通过对并行传播模式的最坏时间复杂度分析，可以认为并行传播模式在平均过滤时间较长的实例上要快于串行传播模式；最终的实验结果也验证了上述结论，并行传播模式在多数实例集上取得了从1.4~3.4不等的加速比.
2021, 32(9):2783-2800.
DOI: 10.13328/j.cnki.jos.005992
摘要:
针对情感分析任务中没有充分利用现有的语言知识和情感资源，以及在序列模型中存在的问题：模型会将输入文本序列解码为某一个特定的长度向量，如果向量的长度设定过短，会造成输入文本信息丢失.提出了一种基于多通道特征和自注意力的双向LSTM情感分类方法（MFSA-BiLSTM），该模型对情感分析任务中现有的语言知识和情感资源进行建模，形成不同的特征通道，并使用自注意力重点关注加强这些情感信息.MFSA-BiLSTM可以充分挖掘句子中的情感目标词和情感极性词之间的关系，且不依赖人工整理的情感词典.另外，在MFSA-BiLSTM模型的基础上，针对文档级文本分类任务提出了MFSA-BiLSTM-D模型.该模型先训练得到文档的所有的句子表达，再得到整个文档表示.最后，对5个基线数据集进行了实验验证.结果表明：在大多数情况下，MFSA-BiLSTM和MFSA-BiLSTM-D这两个模型在分类精度上优于其他先进的文本分类方法.
针对情感分析任务中没有充分利用现有的语言知识和情感资源，以及在序列模型中存在的问题：模型会将输入文本序列解码为某一个特定的长度向量，如果向量的长度设定过短，会造成输入文本信息丢失.提出了一种基于多通道特征和自注意力的双向LSTM情感分类方法（MFSA-BiLSTM），该模型对情感分析任务中现有的语言知识和情感资源进行建模，形成不同的特征通道，并使用自注意力重点关注加强这些情感信息.MFSA-BiLSTM可以充分挖掘句子中的情感目标词和情感极性词之间的关系，且不依赖人工整理的情感词典.另外，在MFSA-BiLSTM模型的基础上，针对文档级文本分类任务提出了MFSA-BiLSTM-D模型.该模型先训练得到文档的所有的句子表达，再得到整个文档表示.最后，对5个基线数据集进行了实验验证.结果表明：在大多数情况下，MFSA-BiLSTM和MFSA-BiLSTM-D这两个模型在分类精度上优于其他先进的文本分类方法.
2021, 32(9):2801-2815.
DOI: 10.13328/j.cnki.jos.006418
摘要:
深度学习算法在很多有监督学习任务上达到了令人满意的结果，但其依赖于大量标注样本，并且使用特定类别训练的分类器，只能对这些类别进行分类.零次学习希望计算机像人类一样，能够结合历史经验与知识进行推理，无需使用大量新类别样本训练，便可达到识别新类别的效果.发现了零次学习任务存在“冷启动”以及矩阵稀疏两个特点，这些特点在推荐任务中同样存在.受推荐任务启发，将零次图像分类任务建模为矩阵填充问题，借鉴推荐领域中协同过滤算法，将稀疏的样本标签矩阵视为非稀疏的视觉特征矩阵和类别特征矩阵的内积结果，进而实现对新类别样本的分类预测.此外，构建了基于类间语义关联的语义图结构，使用图神经网络进行已知类别和新类别之间的知识迁移，以较小代价为类别学得准确的语义特征.在3个经典零次学习数据集上分别进行传统零次学习和广义零次学习实验，实验结果表明：提出的协同过滤式零次学习方法能够有效提升分类精度，且训练代价较小.
深度学习算法在很多有监督学习任务上达到了令人满意的结果，但其依赖于大量标注样本，并且使用特定类别训练的分类器，只能对这些类别进行分类.零次学习希望计算机像人类一样，能够结合历史经验与知识进行推理，无需使用大量新类别样本训练，便可达到识别新类别的效果.发现了零次学习任务存在“冷启动”以及矩阵稀疏两个特点，这些特点在推荐任务中同样存在.受推荐任务启发，将零次图像分类任务建模为矩阵填充问题，借鉴推荐领域中协同过滤算法，将稀疏的样本标签矩阵视为非稀疏的视觉特征矩阵和类别特征矩阵的内积结果，进而实现对新类别样本的分类预测.此外，构建了基于类间语义关联的语义图结构，使用图神经网络进行已知类别和新类别之间的知识迁移，以较小代价为类别学得准确的语义特征.在3个经典零次学习数据集上分别进行传统零次学习和广义零次学习实验，实验结果表明：提出的协同过滤式零次学习方法能够有效提升分类精度，且训练代价较小.
12 碎片化家谱数据的融合技术
2021, 32(9):2816-2836.
DOI: 10.13328/j.cnki.jos.006010
摘要:
家谱数据是典型的碎片化数据，具有海量、多源、异构、自治的特点.通过数据融合技术将互联网中零散分布的家谱数据融合成一个全面、准确的家谱数据库，有利于针对家谱数据进行知识挖掘和推理，从而为用户提供姓氏起源、姓氏变迁和姓氏间关联等隐含信息.在大数据知识工程BigKE模型的基础上，提出了一个结合HAO智能模型的碎片化数据融合框架FDF-HAO （fragmented data fusion with human intelligence，artificial intelligence and organizational intelligence），阐述了架构中每层的作用、关键技术和需要解决的问题，并以家谱数据为例，验证了该数据融合框架的有效性.最后，对碎片化数据融合的前景进行展望.
家谱数据是典型的碎片化数据，具有海量、多源、异构、自治的特点.通过数据融合技术将互联网中零散分布的家谱数据融合成一个全面、准确的家谱数据库，有利于针对家谱数据进行知识挖掘和推理，从而为用户提供姓氏起源、姓氏变迁和姓氏间关联等隐含信息.在大数据知识工程BigKE模型的基础上，提出了一个结合HAO智能模型的碎片化数据融合框架FDF-HAO （fragmented data fusion with human intelligence，artificial intelligence and organizational intelligence），阐述了架构中每层的作用、关键技术和需要解决的问题，并以家谱数据为例，验证了该数据融合框架的有效性.最后，对碎片化数据融合的前景进行展望.
2021, 32(9):2837-2848.
DOI: 10.13328/j.cnki.jos.005972
摘要:
积分分析是一种针对分组密码十分有效的分析方法，其通常利用密文某些位置的零和性质构造积分区分器.基于高阶差分理论，可通过研究密文与明文之间多项式的代数次数来确定密文某些位置是否平衡.从传统的积分分析出发，首次考虑常数对多项式首项系数的影响，提出了概率积分分析方法，并将其应用于PUFFIN算法的安全性分析.针对PUFFIN算法，构造了7轮概率积分区分器，比已有最好的积分区分器轮数长1轮.进一步，利用构造的概率积分区分器，对9轮PUFFIN算法进行密钥恢复攻击.该攻击可恢复92比特轮密钥，攻击的数据复杂度为224.8个选择明文，时间复杂度为235.48次9轮算法加密，存储复杂度为220个存储单元.
积分分析是一种针对分组密码十分有效的分析方法，其通常利用密文某些位置的零和性质构造积分区分器.基于高阶差分理论，可通过研究密文与明文之间多项式的代数次数来确定密文某些位置是否平衡.从传统的积分分析出发，首次考虑常数对多项式首项系数的影响，提出了概率积分分析方法，并将其应用于PUFFIN算法的安全性分析.针对PUFFIN算法，构造了7轮概率积分区分器，比已有最好的积分区分器轮数长1轮.进一步，利用构造的概率积分区分器，对9轮PUFFIN算法进行密钥恢复攻击.该攻击可恢复92比特轮密钥，攻击的数据复杂度为224.8个选择明文，时间复杂度为235.48次9轮算法加密，存储复杂度为220个存储单元.
2021, 32(9):2849-2866.
DOI: 10.13328/j.cnki.jos.005973
摘要:
TLS协议在TCP/IP体系中的传输层和应用层之间工作，通过提供机密性、完整性、必选的服务器认证以及可选的客户端认证等一系列安全服务，有效保护了传输层的安全.TLS1.3协议为了降低网络延迟，增加了对0-RTT数据的支持，通过客户端缓存服务器的长期公钥，在第1条消息中，直接利用该长期公钥生成一个会话密钥发送部分应用层数据.针对3种0-RTT模式，使用Scyther工具对其进行了形式化分析，得出了在CK安全模型下，0-RTT数据的两种攻击，并基于其中的1-RTT semi-static模式提出了一种优化协议.通过安全性证明和形式化分析，证明了该优化协议在CK安全模型下能够抵抗针对0-RTT数据的KCI攻击和重放攻击.
TLS协议在TCP/IP体系中的传输层和应用层之间工作，通过提供机密性、完整性、必选的服务器认证以及可选的客户端认证等一系列安全服务，有效保护了传输层的安全.TLS1.3协议为了降低网络延迟，增加了对0-RTT数据的支持，通过客户端缓存服务器的长期公钥，在第1条消息中，直接利用该长期公钥生成一个会话密钥发送部分应用层数据.针对3种0-RTT模式，使用Scyther工具对其进行了形式化分析，得出了在CK安全模型下，0-RTT数据的两种攻击，并基于其中的1-RTT semi-static模式提出了一种优化协议.通过安全性证明和形式化分析，证明了该优化协议在CK安全模型下能够抵抗针对0-RTT数据的KCI攻击和重放攻击.
2021, 32(9):2867-2886.
DOI: 10.13328/j.cnki.jos.005975
摘要:
在无线可充电传感器网络（wireless rechargeable sensor network，简称WRSN）中，所面临的一项重要挑战是如何在高效收集传感器节点数据的同时，降低网络整体能量消耗.大多数现有数据收集策略或是不能适应大规模的充电传感器网络，或是没有充分考虑到传感器节点能量补充的问题，这将严重降低网络的通信量和生命周期.为此，针对WRSN中数据收集和网络能耗的问题，提出使用数据收集小车（data collection vehicle，简称DCV）和无线充电小车（wireless charging vehicle，简称WCV）分别负责数据收集和节点充电，从而在优化数据收集的同时，保证网络的持续性.首先，为了提高数据收集和充电效率，根据传感器节点的邻域相似度以及节点之间的距离，将网络自适应划分为多个子区域；随后，根据传感器节点k跳路由之内的电池能量和节点社交性，选择各个区域内数据收集锚点；接着，通过分析传感器节点自身能量消耗与网络系统能耗之间的关系，设计了网络能耗优化函数，通过对偶分解和次梯度的方法求得优化函数的最佳节点感知率和物理链路传输率；最后，实验验证了该网络不仅能有效降低网络整体能耗，而且具有较低的节点死亡数目.
在无线可充电传感器网络（wireless rechargeable sensor network，简称WRSN）中，所面临的一项重要挑战是如何在高效收集传感器节点数据的同时，降低网络整体能量消耗.大多数现有数据收集策略或是不能适应大规模的充电传感器网络，或是没有充分考虑到传感器节点能量补充的问题，这将严重降低网络的通信量和生命周期.为此，针对WRSN中数据收集和网络能耗的问题，提出使用数据收集小车（data collection vehicle，简称DCV）和无线充电小车（wireless charging vehicle，简称WCV）分别负责数据收集和节点充电，从而在优化数据收集的同时，保证网络的持续性.首先，为了提高数据收集和充电效率，根据传感器节点的邻域相似度以及节点之间的距离，将网络自适应划分为多个子区域；随后，根据传感器节点k跳路由之内的电池能量和节点社交性，选择各个区域内数据收集锚点；接着，通过分析传感器节点自身能量消耗与网络系统能耗之间的关系，设计了网络能耗优化函数，通过对偶分解和次梯度的方法求得优化函数的最佳节点感知率和物理链路传输率；最后，实验验证了该网络不仅能有效降低网络整体能耗，而且具有较低的节点死亡数目.
2021, 32(9):2887-2900.
DOI: 10.13328/j.cnki.jos.005976
摘要:
迄今为止，大多数密码原语的安全性都依赖于高质量的不可预测的随机数.密码学中，通常用伪随机数生成器（pseudorandom number generator，简称PRNG）生成随机数.因此，密码算法中所用的PRNG的安全性将直接影响着密码算法的安全性.然而，近年来，越来越多的研究结果表明：在实际应用中，很多人为因素会导致PRNG生成的随机数是不随机或可预测的，称这种不安全的PRNG为有后门的PRNG （backdoored pseudorandom number generator，简称BPRNG）.BPRNG最典型的例子是双椭圆曲线伪随机数生成器（dual elliptic curves pseudorandom number generator，简称Dual EC PRNG），其算法于2014年被曝出存在后门.BPRNG的出现，使密码算法的研究面临着新的挑战.因此，研究抗随机数后门攻击的密码算法显得尤为重要.首先概述了抗随机数后门攻击密码算法的研究背景，然后着重对已有抗随机数后门攻击密码算法进行了总结和梳理.
迄今为止，大多数密码原语的安全性都依赖于高质量的不可预测的随机数.密码学中，通常用伪随机数生成器（pseudorandom number generator，简称PRNG）生成随机数.因此，密码算法中所用的PRNG的安全性将直接影响着密码算法的安全性.然而，近年来，越来越多的研究结果表明：在实际应用中，很多人为因素会导致PRNG生成的随机数是不随机或可预测的，称这种不安全的PRNG为有后门的PRNG （backdoored pseudorandom number generator，简称BPRNG）.BPRNG最典型的例子是双椭圆曲线伪随机数生成器（dual elliptic curves pseudorandom number generator，简称Dual EC PRNG），其算法于2014年被曝出存在后门.BPRNG的出现，使密码算法的研究面临着新的挑战.因此，研究抗随机数后门攻击的密码算法显得尤为重要.首先概述了抗随机数后门攻击密码算法的研究背景，然后着重对已有抗随机数后门攻击密码算法进行了总结和梳理.
2021, 32(9):2901-2915.
DOI: 10.13328/j.cnki.jos.005980
摘要:
近年来，基于深度学习的空域隐写分析研究在高嵌入率下已经取得了较好的成果，但是对低嵌入率的检测效果还不太理想.因此设计了一种卷积神经网络结构，使用SRM滤波器进行预处理来获取隐写噪声残差，采用3个卷积层并对卷积核大小进行合理设计，通过适当选择批量归一化操作和激活函数来提升网络的性能.实验结果表明：与现有方法相比，所提出的网络结构对WOW，S-UNIWARD和HILL这3种常见的空域内容自适应隐写算法取得了更好的检测效果，且在低嵌入率0.2bpp，0.1bpp和0.05bpp下的检测效果有非常明显的提升.还提出了逐步迁移（step by step）的迁移学习方法，进一步提升低嵌入率条件下的隐写分析效果.
近年来，基于深度学习的空域隐写分析研究在高嵌入率下已经取得了较好的成果，但是对低嵌入率的检测效果还不太理想.因此设计了一种卷积神经网络结构，使用SRM滤波器进行预处理来获取隐写噪声残差，采用3个卷积层并对卷积核大小进行合理设计，通过适当选择批量归一化操作和激活函数来提升网络的性能.实验结果表明：与现有方法相比，所提出的网络结构对WOW，S-UNIWARD和HILL这3种常见的空域内容自适应隐写算法取得了更好的检测效果，且在低嵌入率0.2bpp，0.1bpp和0.05bpp下的检测效果有非常明显的提升.还提出了逐步迁移（step by step）的迁移学习方法，进一步提升低嵌入率条件下的隐写分析效果.
2021, 32(9):2916-2934.
DOI: 10.13328/j.cnki.jos.005983
摘要:
随着Web应用的日益广泛，Web浏览过程中，恶意网页对用户造成的危害日趋严重.恶意URL是指其所对应的网页中含有对用户造成危害的恶意代码，会利用浏览器或插件存在的漏洞攻击用户，导致浏览器自动下载恶意软件.基于对大量存活恶意URL特征的统计分析，并重点结合了恶意URL的重定向跳转、客户端环境探测等逃避检测特征，从页面内容、JavaScript函数参数和Web会话流程这3个方面设计了25个特征，提出了基于多特征融合和机器学习的恶意URL检测方法——HADMW.测试结果表明：该方法取得了96.2%的精确率和94.6%的召回率，能够有效地检测恶意URL.与开源项目以及安全软件的检测结果相比，HADMW取得了更好的效果.
随着Web应用的日益广泛，Web浏览过程中，恶意网页对用户造成的危害日趋严重.恶意URL是指其所对应的网页中含有对用户造成危害的恶意代码，会利用浏览器或插件存在的漏洞攻击用户，导致浏览器自动下载恶意软件.基于对大量存活恶意URL特征的统计分析，并重点结合了恶意URL的重定向跳转、客户端环境探测等逃避检测特征，从页面内容、JavaScript函数参数和Web会话流程这3个方面设计了25个特征，提出了基于多特征融合和机器学习的恶意URL检测方法——HADMW.测试结果表明：该方法取得了96.2%的精确率和94.6%的召回率，能够有效地检测恶意URL.与开源项目以及安全软件的检测结果相比，HADMW取得了更好的效果.
2021, 32(9):2935-2944.
DOI: 10.13328/j.cnki.jos.006019
摘要:
盲签名是一种特殊的数字签名，可广泛应用于各种匿名场合.目前，大多数盲签名的安全性主要基于大整数分解问题或离散对数问题的难解性.然而，实用量子计算机的即将诞生会使得传统的盲签名不再安全，而且量子算法的出现对传统的盲签名亦提出了挑战.因此，构造能够防御量子计算攻击的盲签名方案具有重要的意义.多变量公钥密码是后量子密码的主要候选者之一.在多变量公钥密码和盲签名的理论基础上，设计了一种新颖的多变量公钥密码体制下的盲签名方案.该密码方案借助另一非线性可逆变换L：Fr→Fr将签名的公私钥分离，减少了公私钥之间的线性关系，提高了盲签名的安全性.分析表明：该密码方案不仅具有盲性、不可伪造性和不可追踪性，而且还具有计算复杂度低及抗量子计算攻击的优点.
盲签名是一种特殊的数字签名，可广泛应用于各种匿名场合.目前，大多数盲签名的安全性主要基于大整数分解问题或离散对数问题的难解性.然而，实用量子计算机的即将诞生会使得传统的盲签名不再安全，而且量子算法的出现对传统的盲签名亦提出了挑战.因此，构造能够防御量子计算攻击的盲签名方案具有重要的意义.多变量公钥密码是后量子密码的主要候选者之一.在多变量公钥密码和盲签名的理论基础上，设计了一种新颖的多变量公钥密码体制下的盲签名方案.该密码方案借助另一非线性可逆变换L：Fr→Fr将签名的公私钥分离，减少了公私钥之间的线性关系，提高了盲签名的安全性.分析表明：该密码方案不仅具有盲性、不可伪造性和不可追踪性，而且还具有计算复杂度低及抗量子计算攻击的优点.
2021, 32(9):2945-2962.
DOI: 10.13328/j.cnki.jos.005978
摘要:
“神威·太湖之光”国产超级计算机的特点是适用于高通量计算系统，此类系统往往存储器访问延迟，网络延迟较长.在实际应用中，有一大类问题是时间演化的模拟问题，往往需要高频状态迭代，每次迭代需要通信.此类应用问题的典型代表是分子动力学模拟，分子的性质依赖于时间演化，导致状态相关的时间尺度上难以并行化.实际应用中，全原子模型需要模拟超过ms时间尺度，每一步的物理时间为1fs~2.5fs，这意味着所需时间步个数超过1012个.众核处理器中，不同核心访存时需较长的“排队”等待，造成访存延迟.另外，网卡通信延迟以及较长的数据通路会带来网络延迟，由此导致在长延迟的众核处理器上进行一次有效的模拟几乎是不可能的.解决此类问题的主要挑战是提高迭代频率，即每秒执行尽可能多的迭代步.针对神威高性能芯片处理器的体系结构特点，以分子动力学模拟为例，研究了一系列优化策略以提高迭代频率：（1）单核通信与片上核间同步相结合，降低通信成本；（2）共享内存等待与从核同步相结合，优化异构体系结构中的核间同步；（3）改变计算模式，减少核间数据关联和依赖关系；（4）数据传输与计算重叠，掩盖访存延迟；（5）规则化问题，以提高访存凝聚性.
“神威·太湖之光”国产超级计算机的特点是适用于高通量计算系统，此类系统往往存储器访问延迟，网络延迟较长.在实际应用中，有一大类问题是时间演化的模拟问题，往往需要高频状态迭代，每次迭代需要通信.此类应用问题的典型代表是分子动力学模拟，分子的性质依赖于时间演化，导致状态相关的时间尺度上难以并行化.实际应用中，全原子模型需要模拟超过ms时间尺度，每一步的物理时间为1fs~2.5fs，这意味着所需时间步个数超过1012个.众核处理器中，不同核心访存时需较长的“排队”等待，造成访存延迟.另外，网卡通信延迟以及较长的数据通路会带来网络延迟，由此导致在长延迟的众核处理器上进行一次有效的模拟几乎是不可能的.解决此类问题的主要挑战是提高迭代频率，即每秒执行尽可能多的迭代步.针对神威高性能芯片处理器的体系结构特点，以分子动力学模拟为例，研究了一系列优化策略以提高迭代频率：（1）单核通信与片上核间同步相结合，降低通信成本；（2）共享内存等待与从核同步相结合，优化异构体系结构中的核间同步；（3）改变计算模式，减少核间数据关联和依赖关系；（4）数据传输与计算重叠，掩盖访存延迟；（5）规则化问题，以提高访存凝聚性.
2021, 32(9):2963-2976.
DOI: 10.13328/j.cnki.jos.005981
摘要:
信息中心网络（information-centric networking，简称ICN）将网络通信模式从当前的以地址为中心转变为以信息为中心.泛在化缓存是ICN重要特性之一，它通过赋予网络任意节点缓存的能力来缓和服务器的压力，降低用户访问延迟.然而，由于缺少内容热度的分布感知，现有ICN缓存策略仍存在缓存利用率较低、缓存位置缺乏合理规划等问题.为了解决这些问题，提出一种基于两级缓存的协同缓存机制（a cache coordination scheme based on two-level cache，简称CSTC）.将每个节点的缓存空间分为热度感知和协作分配两部分，为不同热度的内容提供不同的缓存策略.同时，结合提出的热度筛选机制和路由策略，降低了缓存冗余，实现了缓存位置优化.最后，基于真实网络拓扑的仿真实验表明，CSTC在次热门内容缓存数量上提升了2倍，缓存命中率提升了将近50%，且平均往返跳数在多数情况下优于现有On-path缓存方式.
信息中心网络（information-centric networking，简称ICN）将网络通信模式从当前的以地址为中心转变为以信息为中心.泛在化缓存是ICN重要特性之一，它通过赋予网络任意节点缓存的能力来缓和服务器的压力，降低用户访问延迟.然而，由于缺少内容热度的分布感知，现有ICN缓存策略仍存在缓存利用率较低、缓存位置缺乏合理规划等问题.为了解决这些问题，提出一种基于两级缓存的协同缓存机制（a cache coordination scheme based on two-level cache，简称CSTC）.将每个节点的缓存空间分为热度感知和协作分配两部分，为不同热度的内容提供不同的缓存策略.同时，结合提出的热度筛选机制和路由策略，降低了缓存冗余，实现了缓存位置优化.最后，基于真实网络拓扑的仿真实验表明，CSTC在次热门内容缓存数量上提升了2倍，缓存命中率提升了将近50%，且平均往返跳数在多数情况下优于现有On-path缓存方式.
联系方式
- 《软件学报 》
- 主办单位：中国科学院软件研究所
中国计算机学会 - 邮编：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
技术支持：北京勤云科技发展有限公司
