计算机科学

第49卷第11期目录

计算机科学. 2022, 49 (11): 0-0.

摘要 ( 219 )

PDF(404KB) ( 515 )

相关文章 | 多维度评价

实例编程研究进展与挑战

严倩羽, 李弋, 彭鑫

计算机科学. 2022, 49 (11): 1-7. doi:10.11896/jsjkx.211000225

摘要 ( 547 )

PDF(1921KB) ( 9368 )

参考文献 | 相关文章 | 多维度评价

程序合成指计算机自动地构造符合指定语法和用户给定规约的代码。实例编程是程序合成中一类以输入输出实例为规约形式的范式,它易用性高、学习成本低。近年来,该技术已经在数据处理、字符串变换等领域得到成功应用,具有很大的发展潜力。实例编程主要待解决的问题有两点:一是庞大程序空间中高效搜索的问题,二是程序合成解的歧义性问题。为解决第一个问题,实例编程方法在指定搜索策略时,需选取适当的领域特定语言,制定搜索算法,所应用的算法可分类为基于规则的算法和基于统计模型的算法。为解决第二个问题,实例编程方法需制定排序策略,所应用的排序策略可分类为基于给定实例的排序方法和基于用户交互的排序方法。文中对近年来的实例编程相关文献进行了整理,针对解决以上两个问题的方法、关键技术点进行了总结归纳,最后对实例编程领域未来的研究方向给出了建议。

面向软件缺陷报告的缺陷定位方法研究与进展

倪珍, 李斌, 孙小兵, 李必信, 朱程

计算机科学. 2022, 49 (11): 8-23. doi:10.11896/jsjkx.220200117

摘要 ( 656 )

PDF(2280KB) ( 10379 )

参考文献 | 相关文章 | 多维度评价

软件缺陷定位是软件缺陷修复任务的一个重要步骤。面向软件缺陷报告的缺陷定位方法以描述缺陷产生现象的软件缺陷报告作为查询,以项目的源代码作为语料库,通过分析缺陷报告与源代码单元之间的相关关系,设计缺陷报告与源代码单元之间相关度的计算方法;随后,挖掘各类软件历史仓库来创建缺陷定位数据集,构建缺陷定位模型,以识别缺陷报告所描述的缺陷对应的源代码单元(即缺陷位置),实现缺陷定位。对近年来国内外学者在该研究领域取得的成果进行了系统总结。首先,介绍了软件缺陷定位的相关概念,归纳了面向软件缺陷报告的缺陷定位方法的主要流程;其次,围绕定位流程中的3个关键步骤梳理了已有研究工作;然后,总结了缺陷定位领域常用的实验数据集和实验评估指标;最后,对未来研究可能面临的挑战进行了展望。

面向SOA的集成测试序列生成算法研究

张冰清, 费琪, 王轶辰, 杨召

计算机科学. 2022, 49 (11): 24-29. doi:10.11896/jsjkx.210400210

摘要 ( 574 )

PDF(1866KB) ( 10092 )

参考文献 | 相关文章 | 多维度评价

集成测试序列生成是软件集成测试研究中的一个重要课题,合理的测试序列可以在提高集成测试效率的同时有效降低测试代价。面向服务的架构SOA(Service-Oriented Architecture)是近年来在企业中被广泛应用的一类分布式架构,目前针对SOA架构中集成测试序列生成的相关研究较少。由于SOA架构中服务间组合具有多态性,单纯使用传统的自顶向下和自底向上等集成测试策略,无法得到SOA架构中服务软件之间的集成测试序列,而目前以面向对象系统中类簇为对象的集成测试序列生成研究又很难适应SOA架构中服务之间复杂的耦合关系。基于此,提出了一种基于遗传算法的集成测试序列生成方法,用于解决SOA架构中服务软件之间的集成测试问题。该方法提出了利用服务特征组的概念表征集成测试影响因素和利用集成测试优先度的概念来表征服务软件的集成测试重要度的基本思想,同时构建了测试依赖图,用于描述SOA架构中服务软件之间的复杂耦合关系,在此基础上提出了面向测试依赖图的测试优先度算法,并以降低测试代价为最优化目标设计了遗传算法,用于生成集成测试序列。最后通过实例验证了所提方法的可行性和正确性,结果表明,所提方法能够生成测试优先度相对较高的节点优先集成和测试代价较低的服务软件集成测试序列。

基于决策树算法的API误用检测

李康乐, 任志磊, 周志德, 江贺

计算机科学. 2022, 49 (11): 30-38. doi:10.11896/jsjkx.211100177

摘要 ( 719 )

PDF(3144KB) ( 10725 )

参考文献 | 相关文章 | 多维度评价

通过应用程序编程接口(Application Programming Interface,API)复用已有的软件框架或类库,可有效地提高软件开发效率。然而,正确使用API须遵守很多规约,如调用顺序、异常处理等。若违反了这些规约就会造成API误用,进而可能导致软件崩溃、产生错误或漏洞。尽管很多API误用检测技术已经被提出,但是这些技术仍面临两个方面的挑战:1)难以获取API使用规约;2)难以同时检测多种不同类型的API误用。为了应对上述挑战,提出了一种基于决策树算法的API误用检测方法。首先,将API使用源代码转换为API使用图,从图中挖掘API使用规约,有效地应对了第一个挑战。其次,在获取的API规约信息的基础上构建API使用决策树,并通过融入剪枝策略来提高API使用决策树的泛化能力。最后,在检测阶段提出了粗粒度和细粒度相结合的检测方式,来提高API使用决策树的检测能力,有效地应对了第二个挑战。实验结果表明,该方法能够在一定程度上发现API误用缺陷。

AutoUnit:基于主动学习和预测引导的测试自动生成

张大林, 张哲玮, 王楠, 刘吉强

计算机科学. 2022, 49 (11): 39-48. doi:10.11896/jsjkx.220200086

摘要 ( 706 )

PDF(2609KB) ( 10644 )

参考文献 | 相关文章 | 多维度评价

测试用例自动生成技术旨在降低测试成本,与人工生成测试用例相比,它具有更高的测试效率。现有主流的测试工具对软件中的所有文件都平等对待,但是大多数情况下含有缺陷的文件只占整个软件项目的一小部分。因此,如果测试人员能针对更易存在缺陷的文件进行测试,就能极大地节省测试资源。针对以上问题,文中设计了一种基于主动学习的预测引导的自动化测试工具AutoUnit。首先对待测文件池中的所有文件进行缺陷预测,然后对最“可疑”的文件进行测试用例生成,之后将实际测试用例执行结果反馈给缺陷预测模型并更新该预测模型,最后根据召回率判断是否进入下一轮测试。此外,AutoUnit还能在含缺陷文件总数未知时,通过设置不同的目标召回率来及时停止预测引导。它能依据已测文件来预测含缺陷文件总数并计算当前召回率,判断是否停止预测引导,保证测试效率。实验分析表明,当测得相同数量的缺陷文件时,AutoUnit花费的最短时间为目前主流测试工具的70.9%,最长时间为目前主流测试工具的80.7%;当含缺陷文件总数未知且目标召回率设置为95%时,与最新版本的Evosuite相比,AutoUnit只需要检查29.7%的源代码文件就能达到相同的检测水平,且其测试时间仅为Evosuite的34.6%,极大地降低了测试成本。实验结果表明,该方法有效地提高了测试的效率。

ROP漏洞利用脚本的语义还原和自动化移植方法

施瑞恒, 朱云聪, 赵易如, 赵磊

计算机科学. 2022, 49 (11): 49-54. doi:10.11896/jsjkx.210900230

摘要 ( 332 )

PDF(2661KB) ( 10826 )

参考文献 | 相关文章 | 多维度评价

漏洞利用脚本在安全研究中有着极为重要的作用,安全研究人员需要研究漏洞利用脚本触发以及利用漏洞的方式,来对漏洞程序进行有效的防护。然而,从网络中获取的大量漏洞利用脚本的通用性和适配性都很差,局限于特定的操作系统及环境,会因运行环境的改变而失效。这个问题在基于ROP的漏洞利用脚本中尤为普遍,使得ROP漏洞利用脚本的移植利用分析变得非常困难,需要依赖于大量的人工辅助与专家经验。针对ROP漏洞利用脚本的移植利用难题,提出了ROPTrans系统,通过ROP漏洞利用脚本的语义识别,定位与运行环境相关的关键语义及其变量,随后自动化适配环境,生成目标环境下的ROP漏洞利用脚本,以实现ROP脚本的自动化移植。实验结果表明,ROPTrans的成功率可以到达80%,验证了该方法的有效性。

自动化软件重构质量目标与非质量目标有效性研究

郭亚琳, 李晓晨, 任志磊, 江贺

计算机科学. 2022, 49 (11): 55-64. doi:10.11896/jsjkx.220300058

摘要 ( 334 )

PDF(3409KB) ( 10776 )

参考文献 | 相关文章 | 多维度评价

随着软件不断迭代发展,软件维护成本也相应增加。自动化重构可以降低软件维护成本,基于搜索的重构方法是解决该问题最典型的方法之一。其中目标的选择对搜索过程起决定性作用,质量目标与非质量目标都是开发人员在重构时通常会考虑的目标。然而,尚未有研究系统地分析在相同的评价环境下,哪些目标更有利于代码重构,特别是得到符合开发者预期的代码重构结果;并且也未分析质量目标与常用的非质量目标进行组合是否会有更好的效果。文中提出了基于搜索的多目标软件重构方法,探索了7个不同目标的组合对软件重构质量的影响。在6个规模不同的开源软件项目上进行了验证,应用多种指标对重构前后软件质量进行评估,并分析了不同优化目标组合的表现。实验结果表明,质量目标与非质量目标组合比单独使用质量目标组合对重构效果的提升更明显,其中质量目标与之前重构记录的一致性的组合对重构有较好的提升效果。

基于机器视觉的Web应用页面元素识别及可视化脚本生成

李子东, 姚怡飞, 王微微, 赵瑞莲

计算机科学. 2022, 49 (11): 65-75. doi:10.11896/jsjkx.220200122

摘要 ( 484 )

PDF(2624KB) ( 11877 )

参考文献 | 相关文章 | 多维度评价

为了给用户提供丰富的交互响应,Web应用的可视化元素越发复杂多样,传统基于DOM的测试已不能满足Web应用的测试新需求。新一代基于机器视觉的测试方法为Web应用复杂元素的测试提供了一种有效途径。目前,此类方法主要依赖于模版匹配技术识别Web页面元素,以生成可视化测试脚本对Web应用进行测试。然而,页面元素外观的细微变化可导致模版匹配技术失效,从而无法识别Web页面元素,更无法生成可视化测试脚本。因此,如何提高基于机器视觉的Web页面元素识别的准确性,使其在复杂条件中仍然适用是一项具有挑战性的工作。基于深度学习的目标检测是当前计算机视觉和机器学习领域的研究热点,可通过大样本学习得到深层的数据特征表示,以准确识别目标,其泛化能力相比模板匹配更强。针对Web应用,从页面元素的视觉特征出发,提出了一种基于深度学习的Web页面元素识别方法,即利用基于深度学习的目标检测算法YOLOv3构建Web页面元素识别模型,自动定位元素的位置和边界,识别Web页面元素类型及功能描述;在此基础上,自动为Web应用生成可视化测试脚本,提升Web应用的测试效率。为了验证基于机器视觉的Web页面元素识别的准确性,针对同一Web应用的不同版本及不同Web应用分别进行实验,结果表明,基于机器视觉的Web页面元素识别模型的平均召回率为75.6%,可有效辅助Web应用可视化测试脚本生成。

基于GCC编译器的流式存储优化方法

高秀武, 黄亮明, 姜军

计算机科学. 2022, 49 (11): 76-82. doi:10.11896/jsjkx.211200252

摘要 ( 1074 )

PDF(2713KB) ( 11732 )

参考文献 | 相关文章 | 多维度评价

针对流式存储访问引起的缓存污染与强制性缺失问题,部分高性能通用处理器平台提供了不经过缓存而直接访问存储器的专用通路及配套指令支持。在常见的流式存储应用场景中,合理采用直访主存方式可以提高芯片存储器系统的整体性能。然而,判断何时使用直访主存能够获得收益对于程序员来说是一项十分繁琐且容易出错的任务,一种行之有效的方法是通过编译器自动实现。因此,文中在深入分析流式存储访问模式使用不同类型访存操作性能收益的基础上,提出了基于GCC编译器的流式存储优化方法。该方法由编译器自动实现对程序员透明,在GCC编译器SSA-GIMPLE阶段对程序循环中具有流式访问特征的连续写或者跨步写进行识别,并根据收益分析与依赖关系筛选优化对象,最后在编译器后端匹配指令模板生成直访主存指令。使用连续/跨步写用例与STREAM测试集及变体在申威国产处理器平台上进行实验评估,结果表明,文中提出的优化方法能够显著缩短流式存储应用程序的执行时间,优化后STREAM测试集的平均加速比为1.31。另外,文中实现的流式存储优化与循环展开优化一起使用效果更好,STREAM测试集的平均加速比能达到1.45。

结合Doc2Vec和BERT嵌入技术的补丁验证方法

黄颖, 姜淑娟, 蒋婷婷

计算机科学. 2022, 49 (11): 83-89. doi:10.11896/jsjkx.210900207

摘要 ( 350 )

PDF(2492KB) ( 11146 )

参考文献 | 相关文章 | 多维度评价

自动程序修复是近年来的研究热点并取得了一定的进展。现有的自动程序修复方法大多利用测试套件来验证补丁正确性。然而,使用测试套件验证自动程序修复方法生成的大量候选补丁不仅会造成巨大的开销,不完美的测试套件还会导致补丁的过拟合问题,因此如何提高补丁验证效率、有效验证补丁正确性成为亟待解决的问题。为了降低补丁验证开销并提高补丁正确率,提出了结合两种嵌入技术验证补丁正确性的方法。该方法首先利用Doc2Vec计算补丁与错误代码的相似性,然后使用一个基于BERT模型的分类器过滤通过相似性筛选出的补丁中的错误补丁。为了验证所提方法的有效性,基于5个开源的Java缺陷库进行实验,结果表明该方法能够有效地验证补丁的正确性并提高验证效率。

基于关系数据库的时态RDF建模

韩啸, 章哲庆, 严丽

计算机科学. 2022, 49 (11): 90-97. doi:10.11896/jsjkx.211100065

摘要 ( 514 )

PDF(2509KB) ( 373 )

参考文献 | 相关文章 | 多维度评价

随着时态数据的不断增加,时态知识图谱的概念得到了普及,如何高效地表示时态知识图谱已成为一个重要的研究方向。RDF(Resource Description Framework)虽然在传统知识图谱建模中被广泛运用,但其只能表示静态语义,缺乏表示时态知识图谱的能力,因此已有几种针对时态知识图谱的时态RDF模型被提出。但这些模型都只是将时态信息简单地附加在谓语或整个三元组上,缺少对时态信息所属对象的准确定位。为了更好地表示时态知识图谱,文中提出了一个新的时态RDF表示模型-tRDF。该模型首先根据宾语的不同类型,选择性地将时态信息附加在宾语或谓语上;其次,结合时态数据库的概念,给出了一种基于关系数据库PostgreSQL的tRDF数据存储方法;最后,从数据存储的时间和空间两个方面对所提出的tRDF数据存储方法进行了验证。实验结果表明,所提方案能有效地表示时态知识图谱。

动态部分标记混合数据的增量式特征选择算法

闫振超, 舒文豪, 谢昕

计算机科学. 2022, 49 (11): 98-108. doi:10.11896/jsjkx.210900076

摘要 ( 593 )

PDF(3679KB) ( 354 )

参考文献 | 相关文章 | 多维度评价

许多实际应用中的数据集是由符号型、数值型和缺失型特征构成的混合数据。针对混合数据的决策标记,由于获取全部数据的决策标记需要耗费大量的人工和时间成本,只能为部分数据进行决策标记,因此产生了部分标记数据。同时,现实应用领域中数据是动态产生的,即数据维度随着不同的需求动态地增加或删减。针对混合数据的高维性、部分标记和动态性,文中提出了两种面向部分标记混合数据的增量式特征选择算法。首先,利用信息粒度对部分标记混合数据的特征进行重要度分析;其次,当特征集发生动态变化时,结合增量学习的思想,给出信息粒度的增量更新机制;然后,在此基础上提出了两种面向部分标记混合数据的增量式特征选择算法;最后,通过与其他算法在UCI数据集上的实验结果进行对比,进一步验证了所提算法的可行性和有效性。

语义增强的完全不平衡标签网络表示学习算法

富坤, 郭云朋, 禚佳明, 李佳宁, 刘琪

计算机科学. 2022, 49 (11): 109-116. doi:10.11896/jsjkx.210900101

摘要 ( 262 )

PDF(2604KB) ( 459 )

参考文献 | 相关文章 | 多维度评价

在网络表示学习的研究中,数据的不完整性问题是一个重要问题,该问题使现有的表示学习算法难以达到预期效果。近年来,不少学者针对此类问题提出了解决方法,这些方法大多仅考虑标签信息本身的缺失问题,对数据不平衡性涉及较少,尤其是某一类别标签完全缺失的完全不平衡问题。解决这类问题的学习算法并不完善,主要存在的问题是在聚合邻域特征时侧重于考虑网络结构信息,未利用属性特征与语义特征间的关系来增强表示结果。为了解决以上问题,提出了融合属性特征与结构特征的SECT(Semantic Information Enhanced Network Embedding with Completely Imbalanced Labels)方法。首先,在考虑属性空间和语义空间关系的基础上,引入注意力机制进行监督学习,得到语义信息向量;然后,应用变分自编码器无监督提取结构特征以增强算法的鲁棒性;最后,在嵌入空间中融合语义与结构两种信息。将使用SECT算法得到的网络向量表示在Cora,Citeseer等数据集上进行测试,应用于节点分类任务时与RECT和GCN等算法相比,取得了0.86%~1.97%的效果提升。网络向量表示的可视化结果显示,与其他算法相比,SECT算法的类间距离变大,类簇内部更加紧凑,能较清晰地区分类别边界。实验结果表明了SECT算法的有效性,SECT得益于更好地在低维嵌入空间中融合语义信息,有效提升了存在完全不平衡标签情况下的节点分类任务性能。

基于微观行为的自适应多注意力会话推荐

乔晶晶, 王莉

计算机科学. 2022, 49 (11): 117-125. doi:10.11896/jsjkx.210900061

摘要 ( 346 )

PDF(2161KB) ( 536 )

参考文献 | 相关文章 | 多维度评价

会话推荐(Session-based Recommendation,SR)旨在根据短期会话信息推荐用户偏好的下一个物品,它不需要用户的配置文件和长期历史信息,具有广阔的应用前景。现有的SR模型通常关注用户点击行为或仅利用某单一类型的行为数据,忽略了用户点击行为的具体语义,如商品浏览、商品收藏、添加到购物车、购买等。这些不同语义的行为被称为微观行为,能够从微观层面反映用户在购物过程中意图的转换以及决策过程,为改善推荐效果提供了有价值的信息。文中提出了一种基于微观行为的自适应多注意力会话推荐模型(Adaptive Multi-Attention Network,AMAN)。首先,将微观行为组成的会话序列建模为异构有向图,然后建立3个组件进行会话推荐:有向图注意力网络(Directed Graph ATtention network,DGAT)从物品级学习物品表征,自适应捕获具有相同微观操作的物品间的关联性;操作级异构图注意力网络(Operation-level Heterogeneous Graph ATtention network,OHGAT)从操作级学习物品表征,自适应捕获具有不同微观操作的物品间的关联性;微观行为协同注意力网络(Micro-Behavior Co-ATtention network,MBCAT)学习微观行为序列表征,自适应捕获不同微观行为序列间的依赖性。在Yoochoose,Taobao14和Taobao15这3个数据集上的实验结果表明,所提方法优于基线模型。

变分推断域适配驱动的城市街景语义分割

金玉杰, 初旭, 王亚沙, 赵俊峰

计算机科学. 2022, 49 (11): 126-133. doi:10.11896/jsjkx.220500193

摘要 ( 371 )

PDF(1978KB) ( 468 )

参考文献 | 相关文章 | 多维度评价

街景语义分割技术旨在从图像中识别分割出行人、障碍物、道路、标志物等要素,为车辆提供道路上自由空间的信息,是自动驾驶的关键技术之一。高性能的语义分割系统非常依赖于训练时所需的大量真实标注数据,然而为图像中的每个像素进行标注成本很高,往往难以实现。一种低成本获取标注数据的方法是利用视频游戏收集逼真且标注成本低的合成图片,来帮助机器学习模型对现实世界中的图片作语义分割,这对应域适配技术。与当前基于VC维理论或Rademacher复杂度理论的主流语义分割域适配方法不同,受基于PAC-Bayes理论的兼容伪标签函数的域适配目标域Gibbs风险上界启发,考虑假设空间的平均情况而非最差情况,以避免主流方法过度约束隐空间上的领域差异,从而导致目标域泛化误差上界未能被有效估计并优化的问题。在上述思想的指导下,提出了一种变分推断语义分割域适配方法(VISA),该方法在利用Dropout变分族进行变分推断求解假设空间上的理想后验分布的同时能快速得到一个近似Bayes分类器,并通过目标域熵最小化和筛选像素点使得对风险上界的估计更加准确。在街景语义分割数据集GTA5→Cityscapes上的适配的实验结果表明,VISA方法相比基线方法平均交并比提高了0.5%~6.6%,且在行人、车辆等关键街景要素上具有较高的识别准确率。

基于粒度感知和语义聚合的图像-文本检索网络

缪岚芯, 雷雨, 曾鹏鹏, 李晓瑜, 宋井宽

计算机科学. 2022, 49 (11): 134-140. doi:10.11896/jsjkx.220600010

摘要 ( 430 )

PDF(2980KB) ( 476 )

参考文献 | 相关文章 | 多维度评价

图像-文本检索是视觉-语言领域中的基本任务,其目的在于挖掘不同模态样本之间的关系,即通过一种模态样本来检索具有近似语义的另一种模态样本。然而,现有方法大多高度依赖于将图像特定区域和句中单词进行相似语义关联,低估了视觉多粒度信息的重要性,导致了错误匹配以及语义模糊嵌入等问题。通常,图片包含了目标级、动作级、关系级以及场景级的粗、细粒度信息,而这些信息无显式多粒度标签,难以与模糊的文本表达直接一一对应。为了解决此问题,提出了一个粒度感知和语义聚合(Granularity-Aware and Semantic Aggregation,GASA)网络,用于获得多粒度视觉特征并缩小文本和视觉之间的语义鸿沟。具体来说,粒度感知的特征选择模块挖掘视觉多粒度信息,并在自适应门控融合机制和金字塔空洞卷积结构的引导下进行了多尺度融合。语义聚合模块在一个共享空间中对来自视觉和文本的多粒度信息进行聚类,以获得局部表征。模型在两个基准数据集上进行了实验,在MSCOCO 1k上R@1优于最先进的技术2%以上,在Flickr30K上R@Sum优于之前最先进的技术4.1%。

基于边缘引导的自校正皮肤检测

郑顺源, 胡良校, 吕晓倩, 孙鑫, 张盛平

计算机科学. 2022, 49 (11): 141-147. doi:10.11896/jsjkx.220600012

摘要 ( 501 )

PDF(4107KB) ( 486 )

参考文献 | 相关文章 | 多维度评价

皮肤检测作为计算机视觉领域中的研究热点多年来被广泛研究,且仍然是一项具有挑战性的任务。尽管目前的方法在许多常规场景下取得了成功,但仍然存在预测不完整和泛化能力差等问题。针对该问题,提出了一种基于边缘引导的神经网络,并且由大量经过自校正的皮肤检测数据驱动网络训练,实现鲁棒的皮肤检测。首先,提出一种基于多任务学习的网络,对皮肤检测和边缘检测两个任务进行联合优化。进一步,提出边缘注意力模块,将预测所得的边缘检测结果通过该模块重新融合到皮肤检测支路中。最后,提出一种自校正算法,通过借助人体解析任务中的大量低质量数据以增强皮肤检测模型的泛化能力。通过自校正算法对带噪声标签的优化,逐步消除使用带噪声标签进行监督训练的副作用。实验结果表明,所提皮肤检测方法优于现有的其他方法。

基于分解极限学习机的手写字符识别方法

何玉林, 李旭, 金一, 黄哲学

计算机科学. 2022, 49 (11): 148-155. doi:10.11896/jsjkx.211200265

摘要 ( 527 )

PDF(3522KB) ( 390 )

参考文献 | 相关文章 | 多维度评价

手写字符识别是图像识别的一个重要分支,是基于数据挖掘和机器学习技术对数字、字母和文字等的手写体进行识别。当前手写字符识别方法主要集中在对不同深度学习模型的完善和改进上,其中多层极限学习机由于其快于深度信念网络和深度玻尔兹曼机的训练速度以及更高的识别精度引起了学术界和工业界的广泛关注。但是,多层极限学习机的预测表现极易受随机权重的影响,层数越多影响就越明显。文中在深入分析浅层极限学习机训练模式的基础上,提出了一种基于隐含层输出矩阵分解的浅层极限学习机模型,并将其应用于对手写字符的识别。分解极限学习机不需要对手写字符图像进行特征提取,而是通过对大规模隐含层输出矩阵的分解来获得极限学习机的输出层权重。相比深层极限学习机,分解极限学习机降低了基于极限学习机的手写字符识别模型训练的随机性。同时,在MNIST类数据集(即MNIST,EMNIST,KMNIST和K49-MNIST)上的比较结果表明,在相同的训练时间下,分解极限学习机能够获得优于多层极限学习机的识别精度;在相同的识别精度下,分解极限学习机的训练时间明显短于多层极限学习机。实验结果证实了分解极限学习的可行性以及在处理手写字符识别问题上的有效性。

基于时序信息对齐的连续手语跨模态知识蒸馏

肖正业, 林世铨, 万修安, 方昱春, 倪兰

计算机科学. 2022, 49 (11): 156-162. doi:10.11896/jsjkx.220600036

摘要 ( 360 )

PDF(2645KB) ( 354 )

参考文献 | 相关文章 | 多维度评价

近年来,连续手语识别的研究工作主要围绕RGB模态的数据展开,并且在现实场景数据集和实验室采集数据集上都取得了显著进展。然而,RGB模态的处理对设备计算能力具有很高的要求,而骨骼关键点模态则由于输入数据复杂度相对低,因此处理速度更快,只是在识别性能上弱于RGB模态。为了综合两种方法的优点,文中提出了一种基于时序关联信息对齐的跨模态知识蒸馏方法(Temporally Related Knowledge Distillation,TRKD)。该方法使用RGB模态的神经网络作为教师网络来指导使用骨骼关键点模态的学生网络,以快速准确地实现连续手语识别。由于教师网络对手语语境的理解能力十分值得学生网络学习,因此提出了具有先验信息以及自适应学习方法的图卷积网络来提取两类模态中的时序关联特征,并通过特征对齐来实现教学。在特征对齐过程中,在教师网络中引入可学习参数会导致教师提供的监督信息丢失。为了解决这个问题,所提出的TRKD方法引入了自监督学习中的对比学习来提供监督信息,从而实现了教师网络与学生网络在时序关联特征上的对齐。文中在Phoenix-2014手语数据集上组织了多项蒸馏任务,以验证所提方法的有效性。

背景估计和局部自适应集成的手写图像二值化

何皇兴, 陈爱国, 王蛟龙

计算机科学. 2022, 49 (11): 163-169. doi:10.11896/jsjkx.210900225

摘要 ( 293 )

PDF(4157KB) ( 420 )

参考文献 | 相关文章 | 多维度评价

手写文档图像中存在光照不均、笔墨浸染、纸张退化、阴影等复杂情况,针对文档图像在复杂背景下二值化后OCR效果不理想的问题,提出了一种对改进的背景估计和局部自适应集成的二值化方法。首先利用局部自适应方法得到具有高召回率的二值化图像,然后对背景估计的方法进行改进得到具有高精确率的二值化图像,最后基于连通域的方法将两种类型的图像集成得到结果。使用4种评价指标在DIBCO2013和DIBCO2016手写数据集上进行了对比实验,结果表明该方法整体性能优于Otsu,Wolf,Niblack,Sauvola,Singh和Howe等经典算法。

基于多尺度特征融合的驾驶员注意力分散检测方法

张宇欣, 陈益强

计算机科学. 2022, 49 (11): 170-178. doi:10.11896/jsjkx.211000040

摘要 ( 389 )

PDF(2813KB) ( 541 )

参考文献 | 相关文章 | 多维度评价

近年来,道路交通事故的发生逐年增加。驾驶员注意力不集中是造成交通事故的主要原因之一。该项工作利用多源数据来检测驾驶员是否注意力分散。由于每个数据源能为其余数据源提供一定的信息,即多源数据之间的关联性较强,因此对不同来源的数据进行同等处理或对多源特征进行简单的连接整合会导致特征耦合度高,不能保证挖掘任务的有效性。另外,注意力分散驾驶可能受到许多因素的影响,当已知类别的集合中不存在驾驶员注意力分散的类型时,常见的有监督方法可能会导致分类错误。对此,提出了一种基于多尺度特征融合的驾驶员注意力分散检测方法(Multi-Scale Feature Fusion Network,MSFFN)。首先,通过多个嵌入式子网络从多源数据中学习低维表示。然后,提出一种多尺度特征融合方法,从时空关联性的角度聚合这些特征表示,降低多源特征之间的耦合度。最后,设计基于卷积长短期记忆的编解码模型进行无监督检测。在训练阶段,模型仅对正常驾驶实例进行训练,确定正常数据的一类分类边界。在检测阶段,计算模型重构误差并将其作为每一个测试数据的评分,从而做出细粒度的检测决策。该方法在公开的驾驶员行为数据集上取得了很好的实验结果,优于现有方法。

基于优化YOLO-V4的交通标志检测识别方法

潘惠苹, 王敏琴, 张福泉

计算机科学. 2022, 49 (11): 179-184. doi:10.11896/jsjkx.220300251

摘要 ( 684 )

PDF(3021KB) ( 668 )

参考文献 | 相关文章 | 多维度评价

交通标志检测识别是自动驾驶系统的核心功能,为了实时准确地识别交通标志,在YOLO-V4的基础上进行改进,并结合了空间金字塔池化(Spatial Pyramid Pooling,SPP)模块。首先,为了提高分辨率和增大感受野,将原特征图3个尺度的分辨率更改为26×26和52×52;然后,在连接层中添加SPP模块,消除网络对固定尺度的约束,在最大池化层中得到最优特征,改善网络性能。实验中,利用行车记录仪采集各种交通标志图像,与其他优秀方法相比,所提方法取得了更优的性能,其平均检测识别准确度达99.0%,平均检测时间为0.449 s,达到了实时检测的要求。

一种专利知识图谱的构建方法

邓亮, 曹存根

计算机科学. 2022, 49 (11): 185-196. doi:10.11896/jsjkx.211100063

摘要 ( 724 )

PDF(3779KB) ( 830 )

参考文献 | 相关文章 | 多维度评价

专利知识图谱对专利精准检索、专利深度分析和专利知识培训等应用起到了重要作用。文中提出了一种实用的基于种子知识图谱、文本挖掘以及关系补全的专利知识图谱构建方法。在该方法中,为确保质量,首先人工建立一个种子专利知识图谱,然后采用专利文本模式的概念和关系抽取方法扩展种子专利知识图谱,最后对扩展的专利知识图谱进行定量评估。文中针对中医药领域专利进行了种子知识的人工提取和词法句法模式的人工总结,并使用机器学习的方法在学习到新的词法句法模式后对种子专利知识图谱进行扩展和图谱补全。实验结果表明,中医药领域专利种子知识图谱中的节点数和关系数分别为19 453个和194 775条,经过扩展后,它们分别达到了558 461个和7 275 958条,即分别增加了27.7倍和36.3倍。

基于双向长短时记忆网络的企业弹性能力预测模型

宋美琦, 傅湘玲, 闫晨巍, 仵伟强, 任芸

计算机科学. 2022, 49 (11): 197-205. doi:10.11896/jsjkx.210900195

摘要 ( 287 )

PDF(2809KB) ( 406 )

参考文献 | 相关文章 | 多维度评价

传统的风险管理方法专注于识别、预测和评估可能发生的潜在风险,但当企业面临突发的、不可预期的风险时,往往束手无策。因此,学术界逐渐将风险管理的视角由预测并规避风险转变为提升企业自身对风险的承受能力和从风险中恢复的能力,也就是企业的弹性能力。文中提出了基于时序特征数据的企业弹性能力预测方法,使用Bi-LSTM对时序特征数据进行双向编码,获得企业的特征表示,并通过softmax分类器得到弹性能力分类结果。模型在中国上市公司的真实数据集中进行实验,macro-F1值达到89.0%,与RF,XGBoost和LightGBM等未使用时序特征数据的模型相比有一定提升。此外,进一步探讨了企业弹性能力的多种影响因素及其重要程度,并首次将机器学习方法应用到企业弹性能力的评估预测中,为企业应对突发风险提供了理论方法指导。

基于多维语义映射的关系抽取方法研究

程华龄, 陈艳平, 杨卫哲, 秦永彬, 黄瑞章

计算机科学. 2022, 49 (11): 206-211. doi:10.11896/jsjkx.210900120

摘要 ( 456 )

PDF(2053KB) ( 421 )

参考文献 | 相关文章 | 多维度评价

关系抽取旨在从句子中识别出实体对之间的关系类型。在关系抽取领域,目前主流的方法都使用了深度学习方法,但大部分方法在输入层没有对词向量进行深层次的讨论。针对这一不足,提出了一种基于多维语义映射的关系抽取方法,该方法的核心思想是将矩阵降维方法应用于神经网络模型输入层。通过将表示文本的词向量进行多维度的降维分解,使分解后的词向量能映射表示同一语句在不同维度上的语义信息。实验结果表明,在Chinese Literature Text和SemEval-2010 Task8数据集上F1值分别达到了75.3%和88.9%,验证了所提方法的有效性。

一种自适应权重的多分类通用集成方法

魏军胜, 刘琰, 陈静, 段顺然

计算机科学. 2022, 49 (11): 212-220. doi:10.11896/jsjkx.210900054

摘要 ( 425 )

PDF(2968KB) ( 530 )

参考文献 | 相关文章 | 多维度评价

集成学习一直是构建强大和稳定的预测模型的策略之一,它能通过融合多个模型来提升结果的准确性和稳定性。但是,现有的集成方法在权重计算上还存在一定的缺陷,面对多种分类问题时无法自适应地选择集成权重,不具有通用性。针对以上问题,提出了一种自适应权重的多分类通用集成方法(UMEAW)。与通常的集成分类方法只针对一种分类任务不同,UMEAW面对不同的分类问题,首先根据分类个数计算权重调配系数,然后利用指数函数分布特性,根据模型评价指标与权重调配系数自动计算一次模型融合的权重,最后通过不断迭代的方法自适应地调整融合权重,实现不同分类任务下的模型融合。实验结果表明,UMEAW在9个不同分类个数、不同领域、不同规模的数据集上都能实现模型融合,其融合效果在大部分任务上都优于基线方法。与单个模型相比,用UMEAW融合后的结果F₁值稳定增加了3%~25%;与其他集成方法相比,F₁值稳定提升了1%~2%,证明了UMEAW的通用性和有效性。

融合词性与声调特征的越南语语法错误检测

张洲, 朱俊国, 余正涛

计算机科学. 2022, 49 (11): 221-227. doi:10.11896/jsjkx.210900247

摘要 ( 426 )

PDF(2783KB) ( 569 )

参考文献 | 相关文章 | 多维度评价

BERT(Bidirectional Encoder Representation from Transformers)预训练语言模型在对越南语分词时会去掉越南语音节的声调,导致语法错误检测模型在训练过程中会丢失部分语义信息。针对该问题,提出了一种融合越南语词性和声调特征的方法来补全输入音节的语义信息。由于越南语的标注语料稀缺,语法错误检测任务面临训练数据规模不足的问题。针对该问题,设计了一种由正确语料生成大量错误文本的数据增强算法。在越南语维基百科和新闻语料上的实验结果表明,所提方法在测试集上取得了最高的F_0.5和F₁分数,证明该方法可提高检测效果,并且随着生成数据规模的扩大,该方法与基线模型方法的效果都得到了逐步提升,从而证明了所提数据增强算法的有效性。

基于改进灰狼算法优化SVR的混凝土中钢筋直径检测方法

卢纯义, 于津, 余忠东, 丁双松, 张占龙, 裘科成

计算机科学. 2022, 49 (11): 228-233. doi:10.11896/jsjkx.210800039

摘要 ( 391 )

PDF(3079KB) ( 378 )

参考文献 | 相关文章 | 多维度评价

传统钢筋混凝土检测方法通过线性拟合或标准值查表法只能对钢筋直径做大致估算,无法精确测量。针对钢筋直径检测中样本数据较少、检测结果受到钢筋埋深及相邻钢筋间距的影响而非表现出非线性回归变化的情况,提出了基于改进灰狼算法(Improved Grey Wolf Optimizer,IGWO)优化的支持向量回归机(Support Vector Regression,SVR)检测方法(IGWO-SVR)。首先,通过反向学习策略优化初始化种群分布,改善了灰狼优化算法(Grey Wolf Optimizer,GWO)的全局搜索能力,通过随机差分变异策略扩大狼群动态搜索范围,避免了灰狼优化算法陷入局部最优;然后,将改进后的灰狼优化算法应用于支持向量回归机的核心参数寻优,以改良算法模型的检测性能;最后,与另外3种算法模型的实验结果进行对比分析,结果表明了所提方法在钢筋直径检测中的精度以及优化模型与实际值的拟合度都得到了有效提升。

无人机边缘计算中的资源管理优化研究综述

袁昕旺, 谢智东, 谭信

计算机科学. 2022, 49 (11): 234-241. doi:10.11896/jsjkx.211100015

摘要 ( 482 )

PDF(2724KB) ( 762 )

参考文献 | 相关文章 | 多维度评价

移动边缘计算将云计算的服务资源移向更靠近终端的边缘,满足了密集计算和低时延需求。地面网络在复杂地形、设备故障等场景中面临挑战,通过无人机辅助,可提升移动边缘计算网络部署的灵活性和鲁棒性。无人机具有成本低廉、操控便捷、机动灵活等优点,但也由于受体积、重量等限制,其功率、通信、计算等资源往往很有限,并且当多无人机协同工作时,其资源的异构性和动态性特征逐步显现,因此,如何高效利用其资源成为研究的热点。从综述的角度,梳理了无人机边缘计算网络中推广应用时面临的问题与挑战,分析总结在功率控制、信道分配、计算服务资源管理以及资源联合优化等方面的研究现状,并分类总结对比了资源管理可行的优化解决方法,最后对资源管理优化的未来发展趋势进行分析和展望。

空地协同移动群智感知研究综述

程文辉, 张乾元, 程梁华, 向朝参, 杨振东, 沈鑫, 张乃凡

计算机科学. 2022, 49 (11): 242-249. doi:10.11896/jsjkx.220400264

摘要 ( 415 )

PDF(2333KB) ( 727 )

参考文献 | 相关文章 | 多维度评价

移动群智感知是一种新兴的感知模式,通过复用现有大量空地移动感知资源,从而实现低成本、大规模的城市感知。因此,联合利用空地移动感知资源实现空地协同移动群智感知,对提高移动感知资源的利用率,促进智慧城市发展具有重要意义。为此,对近年来空地协同移动群智感知研究工作进行综述。首先介绍空地协同移动群智感知兴起的背景和发展现状;然后分别从基于地面移动设备和基于空中移动设备两个维度对现有的移动群智感知研究工作进行分析,总结当前存在的问题;最后提出空地协同移动群智感知在跨平台的用户信息学习、跨空地的移动设备调度、跨任务的感知资源分配3个未来重要的研究方向,为相关研究人员提供有价值的参考。

多云工作流调度综述

于浩雯, 刘波, 周娜琴, 林伟伟, 柳鹏

计算机科学. 2022, 49 (11): 250-258. doi:10.11896/jsjkx.211200234

摘要 ( 439 )

PDF(3419KB) ( 411 )

参考文献 | 相关文章 | 多维度评价

传统的云供应商单独为用户提供服务,这导致了本地云资源不足和扩展费用较高等问题。而新兴的多云组合地理位置不同的云供应商的服务,为用户提供了更多的选择,逐渐成为了研究的热点。同时,工作流调度又是多云研究的关键问题之一。为此,文中首先对多云环境下的工作流调度技术做了深入的调查和分析,然后将多云下的工作流调度方法进行分类和比较,重点阐述了面向成本、面向完工时间的单目标优化工作流调度,面向成本和完工时间,面向响应时间和成本,面向可靠性、成本和完工时间的多目标优化工作流调度,以及面向其他多目标优化的多云工作流调度。最后,在此基础上讨论了多云环境下工作流调度的未来研究方向:不确定性工作流调度、能耗与其他目标的联合调度优化、与边缘服务器协同的调度优化、虚拟机和Serverless平台混合调度。

WiPasLoc:基于WiFi的被动式室内人员定位新方法

王冬子, 郭政鑫, 桂林卿, 黄海平, 肖甫

计算机科学. 2022, 49 (11): 259-265. doi:10.11896/jsjkx.220500098

摘要 ( 524 )

PDF(2735KB) ( 744 )

参考文献 | 相关文章 | 多维度评价

被动式室内人员定位是实现普适无线感知系统的基础。然而在实际生活中,商用WiFi信号易受到周围环境的影响,导致现有基于WiFi的被动式室内定位工作难以从复杂的接收信号中准确分离出目标人员动态分量。针对上述问题,提出了一种精确的被动式室内人员定位系统WiPasLoc,其通过利用商用WiFi设备中提取到的信道状态信息(Channel State Information,CSI),实现了高精度的室内定位。首先,结合CSI子载波的信号质量完成动态多普勒频移(Doppler Frequency Shift,DFS) 估计;然后,通过基于双窗口的信号到达角(Angle of Arrive,AoA)的估计方法,从信道状态信息中精准分离出目标人员的信号分量;最后,结合人员的初始位置信息提出轨迹拟合算法,实现了精确的被动式室内人员定位。实验结果表明:WiPasLoc对室内人员运动轨迹定位的中值误差为80cm,相比现有典型的Widar2.0定位精度提升了25.9%。

基于负载特征的边缘智能系统性能优化

胡朝霞, 胡海周, 蒋从锋, 万健

计算机科学. 2022, 49 (11): 266-276. doi:10.11896/jsjkx.211000067

摘要 ( 399 )

PDF(4741KB) ( 475 )

参考文献 | 相关文章 | 多维度评价

边缘智能指利用人工智能算法为网络边缘设备提供数据分析能力的一种服务形式。然而,边缘计算环境比云计算更加复杂和多变。在构建边缘智能的过程中存在很多问题,例如缺乏量化的评价标准、异构计算平台、复杂的网络拓扑、不断变化的用户需求等,其中比较突出的是算法模型的高资源需求与边缘设备资源储备低之间的矛盾。机器学习是边缘智能的主要工作负载,它需要大量的计算资源,然而边缘设备的计算资源有限,两者的供求关系并不匹配,边缘智能负载的部署和优化成为了一个难题。因此,针对边缘智能负载性能优化问题,文中提出了基于负载特征的边缘智能性能优化CECI(Cloud -Edge Collaborative Inference)策略,从模型选择、批量自适应调整和云边协同方面对不同机器学习负载进行了优化。在模型选择方面,使用基于目标权重的模型自适应选择策略,实现在多个条件约束下,综合权衡多个性能优化目标的效果。在批量自适应调整方面,提出了基于开销反馈的批量自适应调整算法,使得模型在运行时能够达到更好的性能。在云边协同方面,通过结合网络状态和用户时延要求设计出了云边协同策略,进而达到了动态利用云端计算资源的效果。实验结果表明,与云智能相比,所提出的基于负载特征的边缘智能能够缩短50.79%的程序运行时间,降低了42.46%的系统能耗,并提升了4.52%的模型准确率。

边缘环境下轨迹预测性感知的在线边缘服务分配

李晓波, 陈鹏, 帅彬, 夏云霓, 李建岐

计算机科学. 2022, 49 (11): 277-283. doi:10.11896/jsjkx.211100029

摘要 ( 351 )

PDF(3542KB) ( 383 )

参考文献 | 相关文章 | 多维度评价

移动通信技术的快速发展促使了移动边缘计算(Mobile Edge Computing,MEC)的出现。作为第五代(5G)无线网络的关键技术,MEC可利用无线接入网络就近提供电信用户所需服务和云端计算功能,从而创造出一个具备高性能、低延迟与高带宽的服务环境,加速网络中的各项内容、服务及应用。然而,如何实现MEC环境下有效且性能有保障的服务卸载和迁移仍然是一个巨大的挑战。针对这一问题,大多数现有的解决方案都倾向于将任务卸载视为一个离线决策过程,使用用户的瞬时位置作为模型输入。而文中考虑了一种预测轨迹感知的在线MEC任务卸载策略,即PreMig。该策略首先通过多项式滑动窗口模型对服务所属边缘用户的未来轨迹进行预测,然后计算用户在边缘服务器信号覆盖范围内的停留时间,最后以一种贪心策略进行边缘服务的分配。为了验证所设计的方法的有效性,基于真实MEC部署数据集和校园移动轨迹数据集开展了模拟实验,实验结果显示,所提策略在平均服务率和用户服务迁移次数两个关键性能指标上均优于传统策略。

蜻蜓网络上完全独立生成树的构造算法

卞庆荣, 程宝雷, 樊建席, 潘志勇

计算机科学. 2022, 49 (11): 284-292. doi:10.11896/jsjkx.211000037

摘要 ( 288 )

PDF(4213KB) ( 369 )

参考文献 | 相关文章 | 多维度评价

蜻蜓网络(Dragonfly network)是由Kim等提出的一种适用于高性能计算系统的拓扑结构。在蜻蜓网络中,网络被组织成两级架构,计算节点与交换机连接,交换机被分为成多个组。在每一组内部的每个交换机之间互相有一条边相连,任意两组之间有一条边相连接。完全独立生成树在信息的可靠传输、信息的并行传输和安全分发以及并行故障服务器诊断算法中具有非常重要的应用。在实际应用中,随着网络规模的不断增大,信息传输的效率以及安全性等要求越来越高。因此,研究网络的完全独立生成树具有重要意义。目前,有许多关于网络中完全独立生成树的研究,但是缺乏蜻蜓网络上的完全独立生成树的研究成果。文中提出了蜻蜓网络全局链路分别以相对链接、绝对链接以及循环链接下的完全独立生成树划分的构造算法,并在此划分的基础上给出了完全独立生成树边集合的构造算法,并对以上算法的正确性进行了证明。最后分析了算法的时间复杂度。

基于残差网络和循环神经网络混合模型的应用层协议识别方法

吴吉胜, 洪征, 马甜甜, 林培鸿

计算机科学. 2022, 49 (11): 293-301. doi:10.11896/jsjkx.210800252

摘要 ( 340 )

PDF(3062KB) ( 332 )

参考文献 | 相关文章 | 多维度评价

针对现有协议识别方法无法有效提取协议数据的时间和空间特征导致协议识别准确率不高的问题,提出了一种基于一维残差网络和循环神经网络的应用层协议识别方法。所构造的协议识别模型由一维预激活残差网络(PreResNet)和双向门控循环神经网络(BiGRU)组成,利用一维PreResNet提取协议数据的空间特征,利用 BiGRU提取协议数据的时间特征,在此基础上通过注意力机制提取与协议识别有关的关键特征来提高协议识别的准确率。所提方法首先从网络流量中提取应用层协议数据,对数据进行预处理,从而将其转化为一维向量;然后利用训练数据对分类模型进行训练,得到成熟的协议识别模型;最后用训练好的分类模型识别应用层协议。在公开数据集ISCX2012上进行测试实验,结果表明,所提协议识别模型的总体准确率为96.87%,平均F值为96.81%,高于对比的协议识别模型。

利用状态归约的分片负载均衡方法

陈静, 李志淮, 高冬雪, 李敏

计算机科学. 2022, 49 (11): 302-308. doi:10.11896/jsjkx.210800109

摘要 ( 497 )

PDF(2372KB) ( 339 )

参考文献 | 相关文章 | 多维度评价

分片技术是解决区块链可扩展性问题的核心技术之一。当将P2P网络中的交易按规则汇集到既定分片,且验证节点随机均衡分配到各分片后,由于个别分片的交易验证负载可能远远超过平均负载,因此该分片内的交易可能会拥堵。为了解决分片间的负载不均衡,提出了利用状态归约的分片负载均衡方法。首先,给出了状态归约模型,允许性能高的节点存储更多的相邻状态,并据此将节点性能做出粗略分类;然后,根据每一时隙的交易验证情况将未经验证的交易作为剩余负载,并将其作为调整下一时隙分片内验证能力的依据;最后,对节点进行评分、等级划分,根据剩余负载、共识验证节点集合的平均评分,给出节点选取策略,合理且随机分配节点,并对高负载分片的剩余负载向上归约。实验结果表明,利用状态归约的分片负载均衡方法在不降低单个分片的交易验证率的基础上,有效处理了个别分片的异常过载。

面向通用一致性优化的通信高效的异步ADMM算法

王冬霞, 雷咏梅, 张泽宇

计算机科学. 2022, 49 (11): 309-315. doi:10.11896/jsjkx.211200006

摘要 ( 444 )

PDF(2610KB) ( 582 )

参考文献 | 相关文章 | 多维度评价

分布式交替方向乘子法(Alternating Direction Method of Multipliers,ADMM)是求解大规模机器学习问题使用最广泛的方法之一。现有大多数分布式ADMM算法都基于完整的模型更新。随着系统规模及数据量的不断增长,节点间的通信开销逐渐成为限制分布式ADMM算法发展的瓶颈。为了减少节点间通信开销,提出了一种通信高效的通用一致性异步分布式ADMM算法(General Form Consensus Asynchronous Distributed ADMM,GFC-ADADMM ),该算法通过分析高维稀疏数据集的特性,节点间利用关联模型参数代替完整模型参数进行通信,并对模型参数进行过滤以进一步减少节点间传输负载。同时结合过时同步并行(Stale Synchronous Parallel,SSP)计算模型、allreude通信模型及混合编程模型的优势,利用异步allreduce框架并基于MPI/OpenMP混合编程模型实现GFC-ADADMM算法,提高算法计算与通信效率。文中利用GFC-ADADMM算法求解稀疏logistic回归问题,实验测试表明,与现有分布式ADMM算法相比,GFC-ADADMM算法可减少15%~63%的总运行时间,且算法收敛时可达到更高的准确率。

社交网络中的虚假信息经加边修正最大化问题

宋新月, 帅天平, 陈彬

计算机科学. 2022, 49 (11): 316-325. doi:10.11896/jsjkx.211000043

摘要 ( 325 )

PDF(2388KB) ( 317 )

参考文献 | 相关文章 | 多维度评价

在线社交网络如微信等的普及,使人们更加关注信息传播的问题。虚假信息在社交网络中进行传播可能会造成很严重的后果,比如经济损失或者公众恐慌等。因此,需要采取相关的措施来控制虚假信息的传播。传统的虚假信息控制方法主要通过向网络中的部分节点传播真实信息,让真实信息和虚假信息进行竞争来减小虚假信息的影响。文中将传播真实信息和加边的方式相结合,提出了一个虚假信息修正最大化问题。该问题是NP-难的,其目标函数值的计算是#P-难的。由于目标函数既不是次模的也不是超模的,因此采用三明治近似策略来求解该问题。为此,构造目标函数的次模的上界和下界函数,利用反向影响采样技术在基数约束下求解上界和下界函数,最终得到原问题的一个数据相关的近似解。通过在3个真实网络的数据集上进行仿真实验,验证了所提算法的有效性。

基于有限状态机的内核漏洞攻击自动化分析技术

刘培文, 舒辉, 吕小少, 赵耘田

计算机科学. 2022, 49 (11): 326-334. doi:10.11896/jsjkx.211200039

摘要 ( 490 )

PDF(3471KB) ( 393 )

参考文献 | 相关文章 | 多维度评价

内核漏洞攻击是针对操作系统常用的攻击手段,对各攻击阶段进行分析是抵御该类攻击的关键。由于内核漏洞类型、触发路径、利用模式的复杂多样,内核漏洞攻击过程的分析难度较大,而且现有的分析工作主要以污点分析等正向程序分析方法为主,效率较低。为了提高分析效率,文中实现了一种基于有限状态机的内核漏洞攻击自动化分析技术。首先,构建了内核漏洞攻击状态转移图,作为分析的关键基础;其次,引入反向分析的思路,建立了基于有限状态机的内核漏洞攻击过程反向分析模型,能够减小不必要的分析开销;最后,基于模型实现了一种内核漏洞攻击反向分析方法,能够自动、快速地解析内核漏洞攻击流程。通过对10个攻击实例进行测试,结果表明,反向分析方法能够准确得到关键代码执行信息,且相比传统正向分析方法,分析效率有较大提高。

基于联盟链的能源交易数据隐私保护方案

时坤, 周勇, 张启亮, 姜顺荣

计算机科学. 2022, 49 (11): 335-344. doi:10.11896/jsjkx.220300138

摘要 ( 321 )

PDF(4770KB) ( 476 )

参考文献 | 相关文章 | 多维度评价

区块链技术可以有效地解决分布式能源交易系统中的信任缺失、恶意篡改和虚假交易等问题,但区块链开放、透明的特性使得基于区块链的能源交易系统极易受到攻击,导致用户隐私泄露。为此,提出了一种基于差分隐私算法和账户映射技术的隐私保护方案BLDP-AM(Blockchain Local Differential Privacy-Account Mapping),用于保护交易数据的隐私。该方案重新设计了本地差分隐私算法的数据扰动机制使之适用于区块链技术,并基于该扰动机制构造了BLDP(Blockchain Local Differential Privacy)算法来保护交易数据的隐私。同时,为了保证交易正确性以及隐藏交易曲线特征,该方案首先通过账户映射(Account Mapping,AM)技术实现用户与多个账户关联,然后采用指数平滑预测(Exponential Smoothing Prediction,ESP)算法计算各账户的交易预测值,最后使用BLDP算法扰动交易预测值来获得真实交易值并进行交易。通过隐私分析证明了该方案在保护数据隐私方面的可行性,且实验分析表明该方案具有较好的性能。

基于高效全同态加密的安全多方计算协议

朱宗武, 黄汝维

计算机科学. 2022, 49 (11): 345-350. doi:10.11896/jsjkx.210900047

摘要 ( 344 )

PDF(1715KB) ( 574 )

参考文献 | 相关文章 | 多维度评价

针对目前基于全同态加密的安全多方计算协议存在的密文尺寸大、效率较低的问题,文中证明了Chen等提出的支持多比特加密的全同态加密方案满足密钥同态性,基于该方案和门限解密设计了一个在公共随机串模型下的3轮交互的高效安全多方计算协议。该协议由非交互的零知识证明可以得出协议在恶意模型下是安全的,其安全性可归结为容错学习问题的变种问题Some-are-errorless LWE。与现有的在CRS模型下的协议相比,该协议支持多比特加密,能有效降低与非门复杂度;同时密文尺寸较小,减少了运算量,从而提高了时间与空间效率。

面向网络侦察欺骗的差分隐私指纹混淆机制

何源, 邢长友, 张国敏, 宋丽华, 余航

计算机科学. 2022, 49 (11): 351-359. doi:10.11896/jsjkx.220400285

摘要 ( 323 )

PDF(3013KB) ( 337 )

参考文献 | 相关文章 | 多维度评价

网络指纹探测作为一种重要的网络侦察手段,可以被攻击者用于获取目标网络的指纹特征,进而为后续开展有针对性的攻击行动提供支持。指纹混淆技术通过主动修改响应分组中的指纹特征,能够让攻击者形成虚假的指纹视图,但现有的混淆方法在应对攻击者策略性探测分析方面仍存在不足。为此,提出了一种面向网络侦察欺骗的差分隐私指纹混淆机制(Differential Privacy based Obfuscation of Fingerprinting,DPOF)。DPOF参考数据隐私保护的思想,首先建立了效用驱动的差分隐私指纹混淆模型,通过差分隐私指数机制计算不同效用虚假指纹的混淆概率,在此基础上进一步设计了资源约束下的指纹混淆决策方法,并实现了基于粒子群优化的混淆策略求解算法。仿真实验结果表明,相比现有的典型指纹混淆方法,DPOF在不同问题规模和预算情况下均具有更优的指纹混淆效果,且能够以更快的速度获得更好的近似最优策略。

基于联盟链的实用拜占庭容错算法的改进

谢卓, 张志鸿, 李磊, 冯英杰, 陈静

计算机科学. 2022, 49 (11): 360-367. doi:10.11896/jsjkx.210900178

摘要 ( 568 )

PDF(2620KB) ( 482 )

参考文献 | 相关文章 | 多维度评价

作为一种新兴技术,区块链从诞生之初就引起了广泛的关注。共识算法是区块链技术的核心技术之一,共识算法的研究也是区块链发展的重中之重。针对广泛应用于联盟链的实用拜占庭容错算法(PBFT)存在的主节点选取随意以及节点无法动态加入、退出的问题,提出了一种动态的PBFT算法——DPBFT。首先,对PBFT的主节点选取方法进行改进,为每个节点设置信任度积分,根据节点在每轮共识中的行为动态更新信任度积分,依据积分值来选取主节点,提高了诚实节点当选主节点的概率。其次,为PBFT算法设置4个子协议(JOIN,EXIT,PCLEAR,RCLEAR),分别解决节点加入、退出的问题以及对作恶节点做出惩罚,使得系统拥有动态的网络结构。结果证明新加入的4个子协议本身具有良好的安全性和活性,且不影响原始PBFT算法的安全性和活性。最后,实验结果表明,DPBFT算法相比传统PBFT算法具有更好的共识效率。