计算机科学与探索杂志

计算机科学与探索杂志2019年第10期

• 静态软件缺陷预测研究进展

  吴方君

  软件缺陷预测在提高软件质量和用户满意度、降低开发成本和风险等方面起着非常重要的作用，在学术界如火如荼地展开了众多理论和实证研究，但在产业界却发现其存在着实用性差、效率低、未考虑缺陷严重等级等不足。为了查找具体原因，首先依据预测目标的不同，将静态软件缺陷预测细分为缺陷倾向性预测、缺陷的数量/分布密度预测和缺陷模块排序预测；然后从软件度量指标的筛选、测评数据资源库、缺陷预测模型的构建和缺陷预测模型的评价等四方面综述了上述三类静态软件缺陷预测现有的研究工作，详细地指出了各自存在的问题，重点综述了缺陷倾向性预测模型的构建和缺陷模块排序模型的构建方面的工作；最后结合在产业界的应用情况，指出了静态软件缺陷预测面临的挑战和瓶颈，展望了进一步的研究方向。

• 系统架构描述语言AADL的功能行为建模扩展

  许金淼，杨志斌，黄志球，谢 健，周勇

  架构分析与设计语言（AADL）是一种用于描述复杂嵌入式系统体系架构的建模语言，被广泛用于安全关键系统建模与验证。AADL通过行为附件以状态机的形式对组件的内部行为建模。工业界中的复杂系统常使用层次自动机描述组件的功能行为，而行为附件中没有表达层次自动机的机制。针对这一问题，提出了AADL行为附件的层次化扩展——HBA。首先给出了HBA的形式语法，然后定义了HBA的操作语义。提出了HBA的元模型，并在OSATE环境中实现其文本和图形化编辑器。为了便于形式化验证，给出了HBA到时间自动机（TA）的转换规则，并基于模型检测工具UPPAAL进行形式化验证。最后，给出一个案例研究来验证所提方法的有效性。

• 申威众核处理器上的三对角并行求解器

  刘侃，王欣亮，许平，薛巍

  三对角方程求解器是一种在很多科学与工程领域广泛应用的数值计算核心。目前，CPU、GPU等主流硬件平台上都提出了高度优化的并行算法，但是对于中国自主研发的申威26010众核处理器，还没有一种算法能有效地利用其独特的硬件特性来达到最大化的性能。提出了一种分布式CR算法swDCR，来求解大量的、规模不大的三对角方程。该算法对每个三对角方程使用多个从核并行求解，通过联合多个从核的缓存使得运算过程中所有中间变量都能存储在缓存中，同时利用寄存器通信完成核间数据的高速传输。通过设计线程级数据划分机制，使得向量化的优化效果最大化。swDCR的吞吐率相比主核上的追赶法达到了单精度43.9倍和双精度36.7倍的加速，相比从核上的追赶法达到了单精度和双精度均2.07倍的加速。该算法在申威26010处理器单个核组上可以获得24 GB/s的有效带宽。

• LQCD Dslash在神威·太湖之光上的研究分析与MPI实现

  张淼，周宇，陈建海，何钦铭，徐顺，宫明

  “神威·太湖之光”是我国全自主研发的千万核超级计算机，目前已有很多大型应用程序在此先进架构上进行了移植优化。然而，高能物理领域的格点量子色动力学（LQCD）数值模拟软件在神威平台上尚未进行过移植优化，这引起了科学工作者们的关注。针对LQCD在神威平台上的移植优化问题展开研究。首先，论述了国内外对LQCD在不同硬件架构上进行并行优化的发展历程。其次，通过对其热点模块Dslash的重构，实现了在神威平台上的成功移植。再次，针对申威26010芯片异构众核的架构和并行模式，实现了从核阵列异构并行、从核本地设备存储器（LDM）与主存之间的直接存储访问（DMA）通讯、主核之间的消息传递接口（MPI）通讯及全局归约等操作。最后，经过实验测试，单核组优化程序与16核组优化程序相比单主核程序分别获得了165倍和25倍的加速比，并发现了一些重要的性能瓶颈问题，为进一步优化提升整体效率奠定重要基础。同时，对国产超算平台的推广使用具有积极意义。

• 基于Zynq7000 FPGA异构平台的YOLOv2加速器设计与实现

  陈辰，柴志雷，夏珺

  当前，卷积神经网络已在图像分类、目标检测等计算机视觉领域被广泛应用。然而，在前向推断阶段，许多实际应用往往具有低延时和严格的功耗限制。针对该问题，采用参数重排序、多通道数据传输等优化策略，设计并实现了一种基于FPGA的SIMD卷积神经网络加速器架构。以YOLOv2目标检测算法为例，介绍了将卷积神经网络模型映射到FPGA上的完整流程；对加速器的性能和资源耗费进行深入分析和建模，将实际传输延时考虑在内，缩小了加速器理论时延与实际时延的误差；改进了加速器架构中的输入和输出模块，有效提高了总线带宽的实际利用率。实验结果表明，在Zedboard上获得了30.15 GOP/s的性能，与Xeon E5-2620 v4 CPU相比，能效是其120.4倍，性能是其7.3倍；与双核ARM-A9 CPU相比，能效是其86倍，性能是其112.9倍。

• 三维片上网络高维超立方裂变拓扑结构研究

  梁华林，张大坤

  三维片上网络是解决片上网络通讯瓶颈的重要途径，拓扑结构是三维片上网络研究中的关键问题之一。针对高维超立方拓扑结构节点度迅速增加，出现通讯瓶颈的问题，提出一种高维超立方裂变拓扑结构，该拓扑在同等网络规模下具有网络直径短、可扩展性强等优点。以五维超立方裂变拓扑结构为例进行了仿真实验，并与3D Mesh拓扑结构进行了对比分析：当两种拓扑结构在均匀负载状态下达到饱和时，五维超立方裂变拓扑结构的吞吐量比3D Mesh拓扑结构高300%，平均延时比3D Mesh拓扑结构低85.1%，平均跳数比3D Mesh拓扑结构少21.5%；在局部负载下，五维超立方裂变拓扑结构的平均延时比3D Mesh拓扑结构低79.1%，平均跳数比3D Mesh拓扑结构少13.3%。仿真实验表明提出的网络拓扑结构既保留了原有超立方体拓扑结构的优点，又解决了高维超立方体拓扑结构的通讯瓶颈问题。

• 社交网络谣言传播的破窗效应和责任分散效应

  马宇红，赵媛媛，强亚蓉

  在社交网络中，谣言的传播总是受到个体认知心理和社会环境的影响，从而呈现出一定的社会效应。建立了SHIR谣言传播模型，并从个体角度刻画了谣言传播的破窗效应和责任分散效应；研究了两种社会效应发挥最大作用的传播者阈值；基于BA无标度网络，仿真分析了社交网络中破窗效应和责任分散效应对谣言扩散的影响。结果表明：在小规模低密度社交网络中，随着传播者阈值的增加，破窗效应的传播峰值总体单调递减并趋于无社会效应时的传播峰值，责任分散效应的传播峰值总体单调递增并趋于无社会效应时的传播峰值；破窗效应的最佳传播者阈值为0.08，责任分散效应的最佳传播者阈值为0.07；破窗效应下谣言传播峰值提高了58.2%，责任分散效应下谣言传播峰值下降了69.9%，说明破窗效应能够促进谣言传播，而责任分散效应则会抑制谣言传播。

• 可问责的多关键字可搜索加密方案

  裴树军，易鑫，陈彦橦，苗辉

  为了解决现有的可搜索加密方案无法对私钥泄露者的身份进行追踪问责等问题，提出了一种可问责的多关键字密文搜索方案。引入一个追踪算法，根据被泄露、出售的私钥追踪到私钥所有者的身份，并对该用户进行问责。如果确定该用户为泄密者，可直接将其从系统中撤销，从而保障系统的安全。经证明，该方案是可问责的并且基于[q' - SDH]假设是具有安全性的。同时，该方案将加密阶段分为离线加密和在线加密，有效地减少了在线加密的计算量，提升了系统整体运行效率。此外，该方案还支持多关键字查询，为用户缩小了查询范围，搜索效率得到了提升。最后，给出了安全性证明和实验分析，证明了该方案是安全的、可行的。

• 使用动态增减枝算法优化网络结构的DBN模型

  张士昱，宋威，王晨妮，郑珊珊

  近年来深度信念网络（DBN）得到了广泛的应用，但在现有文献中很少有关于如何动态确定其结构的详细研究。提出了一种使用动态增减枝算法的DBN模型（DDBN），可以有效地优化DBN的网络结构。DDBN可以使用动态增减枝算法而不是人工实验来自动确定其结构。首先，在训练过程中通过改变隐藏层层数和隐藏层神经元的数量，自动构建DDBN的结构，这是通过动态增减枝算法实现的。该算法依赖于隐藏层神经元的权重距离（WD）和激活概率的标准差以及整个网络的能量函数。其次，DDBN能够在动态过程中调整权重，有助于提高网络性能。最后，为了验证DDBN的有效性，将DDBN在MNIST、USPS和CIFAR-10三个基准图像数据集上进行了测试。实验结果表明，DDBN比现有的一些DBN结构调整方法具有更好的性能。

• 利用变分自编码器进行网络表示学习

  张蕾，钱峰，赵姝，陈洁，张燕平

  网络表示学习的目标是将网络节点映射到一个低维的向量空间中，然后利用已有的机器学习方法解决诸如节点分类、链接预测、社团挖掘和推荐等下游应用任务。通常网络中的节点携有属性信息，与结构信息具有一定的相关性，将这些信息融入到网络表示学习过程中，有助于提升下游任务的性能。但是针对不同的应用场景，结构和属性信息并不总是线性相关，而且它们都是高度非线性的数据。提出一种基于变分自编码器的网络表示学习方法VANRL。变分自编码器是一种深度神经网络，它不仅可以捕获结构和属性非线性相似性，还可以学习到数据的分布。针对不同的应用任务，灵活地组合结构信息和属性信息，使学习到的网络节点表示达到令人满意的性能。在四个网络（包括两个社交网络，两个引用网络）上的实验结果表明，VANRL可以在节点分类和链路预测任务中获得相对显著的效果。

• 去除光流中冗余信息的动作预测方法

  石祥滨，代海龙，张德园，刘翠微

  近年来使用光流作为输入特征的基于深度学习的动作预测方法逐渐成为主流，但是光流由于环境因素等影响，极易引入无关的冗余信息，从而降低动作预测的精度，而现有方法并没有考虑到光流中的冗余信息。可以从三方面去除光流图中的冗余信息：消除视频中静止部分光流所带来的冗余信息；选取合理的运动区域以消除无关背景因素引入的光流冗余信息；评估相机的运动去除相机运动产生的光流冗余信息。针对去除冗余信息的光流图，提出了一种基于深度学习的动作预测框架，通过使用空间卷积和时间卷积来减少模型的参数，使用基于时间权重的投票机制实现了对动作的预测。在UT-Interaction set1和set2数据集上的实验表明了该方法的有效性。

• 协同过滤策略的异构双种群蚁群算法

  朱宏伟，游晓明，刘升

  针对蚁群算法收敛速度较慢，易陷入局部最优等问题，提出一种基于协同过滤策略的异构双种群蚁群算法。针对两个异构种群，引入协同过滤策略，奖励两个种群中蚂蚁更加偏好的路径，使算法更具导向性，加快算法的收敛速度；根据种群之间信息的动态反馈，自适应调整两个种群的交流频率，增加算法多样性；算法停滞时，两个种群协同交互，均化每个种群信息素，跳出局部最优。最后，引入神经网络失活思想，采用城市范围失活的方法，使程序运行时间更短。在对中大规模商旅问题（TSP）测试集仿真实验上，该算法提高了解的质量，保证了算法的多样性，加快了算法的收敛速度。

• 多标记不完备数据的特征选择算法

  钱文彬，黄琴，王映龙，杨珺

  多标记数据的特征选择是机器学习和数据挖掘领域的重要研究内容，当前对于多标记数据的特征选择研究大多是针对完备性数据，但在许多应用领域中，连续型数值数据较多，且由于诊测成本和隐私保护等因素导致数据往往呈现出不完备性。为解决上述问题，提出了一种面向多标记不完备数据的特征选择算法。该算法将邻域粗糙集模型应用于多标记不完备数据的特征选择，根据邻域阈值求解多标记不完备数据的邻域粒度，并基于邻域粒度给出了度量多标记不完备数据的特征重要性准则，以此设计了面向多标记不完备数据的特征选择算法。最后，通过在Mulan数据集上的实验结果验证了算法的有效性和可行性。

• 具有DP的广义可能性模糊时态CTL模型检测

  魏杰林，袁申，李永明，梁常建

  为了增强计算树逻辑在时序上的表达能力，以广义可能性测度、决策过程和计算树逻辑为基础，研究了具有决策过程的广义可能性模糊时态计算树逻辑的模型检测。首先采用广义可能性决策过程作为系统模型；然后引入模糊时态算子，构造了模糊时态计算树逻辑并给出其在广义可能性测度下的语义，得到新的广义可能性模糊时态计算树逻辑用来描述系统属性；最后在广义可能性调度下通过模糊矩阵运算讨论了“soon、within、last、nearly”等几类模糊时态连接词的具体计算方法，给出相应的模型检测算法。经验证明，广义可能性模糊时态计算树逻辑是广义可能性计算树逻辑在模糊时序上的扩充，具有更强的表达能力。

• 程度多粒度软粗糙集模型

  孙文鑫，刘玉锋，卓春英

  多粒度粗糙集的研究是近几年来研究的热门课题之一。提出了一种介于乐观和悲观多粒度软粗糙集的新模型——程度多粒度软粗糙集。首先，通过计数函数建立了程度多粒度软粗糙集模型；其次，讨论了程度多粒度软粗糙近似算子的性质；再次，定义并研究了程度多粒度软粗糙集的不确定性度量及性质；最后，通过医院对病人诊断的案例验证了模型的实用性。