基于Word2Vec和决策树的故障定位技术

王露露 陈军华

摘  要： 利用Word2Vec方法对Java源代码进行深层语义编码，生成文件级和行级的语义向量，并将其用作输入数据来训练决策树模型，以实现精确的文件级别和行级别故障定位，优化故障检测过程，构建一个综合文件级别与行级别分析的高效故障定位框架. 实验结果表明：该模型在各项目中的故障定位准确率均高于83%.

关键词： 故障定位； 语义表示； Word2Vec； 决策树

中图分类号： TP 18； TP 391.1  文献标志码： A  文章编号： 1000-5137（2024）02-0223-05

Fault location technology based on Word2Vec and decision tree

WANG Lulu， CHEN Junhua^*

（College of Information，Mechanical and Electrical Engineering，Shanghai Normal University，Shanghai 201418，China）

Abstract： Word2Vec technology was utilized to perform deep semantic encoding on Java source code， generating file-level and line-level semantic vectors. These vectors were used as input data to train the decision tree model， aiming to achieve precise file-level and line-level fault location and to optimize the fault detection process. An efficient fault localization framework was constructed by this method which integrated file-level and line-level analysis. The experimental results showed that the fault localization accuracy of the model in all projects was higher than 83%.

Key words： fault location； semantic representation； Word2Vec； decision tree

譜分析故障定位（SBFL）^［1］根据程序的执行信息（覆盖率信息）和程序的执行结果（是否发生错误）来计算每一行代码可能导致错误的概率，该方法虽然注重检测代码语法，却常常忽视了对程序的语义与功能层面的检测.程序切片故障定位^［2］是一种静态分析技术，用于识别可能影响特定变量或计算结果的代码行，但计算复杂、内存需求高，并不适用于大型软件系统，且缺乏灵活性. 基于机器学习的软件故障定位^［3］，是一个使用机器学习技术来识别软件中错误或缺陷位置的方法，其中构建有效的预测模型至关重要，不仅可以识别出与软件缺陷紧密相关的属性，还能准确地捕捉到这些属性在源程序中的表现.

本文作者提出了一种利用Word2Vec方法对程序源代码的语义进行编码的方法，旨在提炼程序的深层语义信息，以优化故障定位流程.通过结合文件级和行级故障定位技术，将程序文件的语义表示引入文件级故障定位框架，以筛查潜在缺陷. 一旦发现问题，进一步将代码每一行的语义表示纳入行级故障定位，以精确定位错误. 相较于传统方法，该方法不仅深入挖掘程序的语义层面，准确提取了源程序的语义特征，还展现了更强的适应性和更高的定位效率，进而实现了高效的自动化行级故障诊断.

1  相关技术基础

1.1 程序频谱

故障定位是一项软件维护任务，利用程序故障的相关信息来定位必须纠正的错误源代码^［4］. 程序频谱是一种每个程序元素（语句、基本块、分支等）执行与否或执行次数的信息，使用测试套件获得这些信息，程序频谱常见的类型为计数频谱和命中频谱^［5］.

1.2 程序表示

程序表示是一种对程序或代码进行结构化和抽象化表示的方法，其传统形式有：抽象语法树（AST）、控制流图（CFG）、数据流图（DFG）以及中间表示（IR）. 程序表示学习已经渗透在命名推荐，代码补全，缺陷检测、缺陷定位、缺陷修复等软件开发的多个环节^［6］. 由于程序员在编写代码时遵循某种规律，使得代码具有自然性^［7］，可以对大规模代码库进行程序语义表示.

1.3 数据集选择

采用Defects4J作为本研究的数据集. Defects4J是一个公开可用、内容丰富、覆盖多版本、囊括真实缺陷的Java程序缺陷数据库，广泛应用于软件工程的各个研究领域，包括自动程序修复、缺陷预测、故障定位和软件测试等^［8］. Defects4J包含多个不同版本的软件项目以及相应的缺陷修复记录. 对于每个特定缺陷，Defects4J提供了存在缺陷的版本、修复后的版本，以及一组可以复现该缺陷的测试用例.在本研究中，将重点分析Defects4J中的以下5个项目：JFreeChart，Apache Commons Math，Apache Commons Lang，Mockito以及Joda-Time，如表1所示.

通过Defects4J中的测试框架获取软件的代码覆盖率和测试信息，方便后续提取命中频谱所涉及的程序代码文件级和行级语义信息. 同时，结合分布式版本控制系统Git的历史提交信息，对故障文件和故障代码行进行标记，以便更好地理解和分析软件的缺陷.

2  基于Word2Vec提取程序语义向量

Word2Vec是一种先进的神经网络语言模型，它构建了一个词嵌入空间，能够将词汇表中的每个单词转换成向量形式. 在这个多维空间中，那些在语义上互有关联的词语被赋予了彼此接近的向量表示.本研究中，借助Word2Vec这一自然语言处理技术，有效地提炼出程序代码中蕴含的语义特征.

尽管Word2Vec的能力局限于提取代码中单个单词的语义向量，但是根据文献［9］的论述，由Word2Vec生成的向量具有一些独特的属性，这些属性允许通过向量之间的数学运算来揭示语言结构的内在规律. 鉴于此，本文作者将一行代码中所有单词的向量进行累加，来表示该行代码的向量. 类似地，可以通过累加其多行代码的向量得到整个源程序代码的向量. 虽然源程序本质上是文本文件，理论上可以直接用于训练Word2Vec模型，但其中的特殊符号和专有词汇需要作适当处理. 因此，在使用数据集中的源程序进行训练之前，必须对其进行预处理，以优化模型的训练效果. 同时，Word2Vec能够将单词转化为固定维度的向量，这一维度是一个关键的超参数，需在模型训练阶段确定. 维度的大小直接关联到模型的表现和效率. 基于Word2Vec的程序语义向量提取模型的训练流程可概述为以下几个精细化步骤：

Step1：删除特殊字符，将特殊符号（ 例如 “+” “-” “*” “＼” “［］” ）替换为一个空格字符.

Step2：拆分Camel命名法的标识符，将该标识符拆分成独立的单词. 将拆分后的每个单词转换为小写.

Step3：对于Joda-Time项目，将每一个测试用例的源代码通过训练好的Word2Vec模型转换成向量. Word2Vec利用上下文的分布信息来捕捉词语的语义含义，采用Word2Vec中预训练好的Continuous Bag of Words（CBOW） 模型，根据上下文词预测中心词. 计算上下文窗口内周围词的词嵌入平均值，作为模型的输入：

， （1）

其中，是上下文窗口内第c个词的词嵌入向量；C是上下文窗口的大小.預测目标词的条件概率^［10］

， （2）

其中，为激活函数；w是权重向量；b是偏置值.

Step4：使用转换得到的代码向量作为特征，将测试用例的测试结果作为标签，训练一个线性支持向量机（SVM）分类器. SVM 的目标是找到一个决策边界，使得样本点到这个边界的间隔最大. 这可以通过最小化权重向量的范数来实现：

， （3）

， （4）

其中，y_i是样本点x_i的类别标签.

Step5：模型评估，使用线性SVM分类器对测试用例进行分类，预测的分类结果

， （5）

其中，为决策函数；为获取决策函数符号的函数. 记录分类的准确性，判断Word2Vec模型的效果.

3  文件级和行级相结合的故障定位模型

在进行源代码故障定位时，如果仅采用行级定位技术，那么对于平均含有n行代码的m个文件，将执行m×n次的逐行检查，效率较低. 如果先通过文件级检测来筛选出包含故障的文件，再对这些特定文件执行行级故障定位，那么检测的效率就会显著提高. 具体来说，首先进行m次的文件级检测，识别出包含故障的文件数量k（k<m），接着针对这k个文件的每一行代码进行故障检测，即进行k×n次检测，总体检测次数缩减为m+k×n次.

在进行故障定位时，选择合适的模型对于提高定位的准确性至关重要. 本研究引入的文件级和行级故障定位模型均依赖于语义向量分类的方法. 两者的主要区别在于输入模型的语义向量所承载的信息层级不同：文件级模型处理的语义向量映射了整个源文件的语义内容，而行级模型关注的则是单行代码的语义信息.

为了评估文件级故障定位模型的有效性，比较SVM、反向传播（BP）神经网络及决策树算法在Defects4J上的执行性能，特别是识别含有故障的源程序文件的准确率. 结果表明：决策树算法在分类Word2Vec生成的程序向量时展现出了较为良好的性能.

考虑到所有选用的模型都是基于语义向量进行分类的，将那些在文件级分类中表现出色的模型也作为候选模型，用于行级语义向量的分类，以期在细粒度层面上实现高效准确的故障定位.

基于决策树的文件级和行级相结合的故障定位模型流程可概述为以下几个步骤：

Step 1：数据准备.首先运用Word2Vec方法来提取程序中单词的语义向量. 捕捉单词层面的深层语义，通过将这些单词向量进行累加，构建代表各个代码行的语义向量. 通过汇总一个文件中所有代码行的语义向量，能够得到反映整个文件语义的综合向量.

Step 2：文件级故障定位.使用决策树算法对文件级特征进行学习. 首先构建一棵树，其中每个内部节点代表一个特征的决策，选择一个最佳特征创建子节点，使该子节点在目标变量上比原始节点具备更高的纯度. 熵是衡量数据集不确定性的指标，在决策树算法中被用于衡量数据集的纯度.

， （6）

其中，S是数据集；是S的熵；n是类别数；p_i是第i个类别在数据集中的比例. 信息增益是选择分割属性时的主要标准，基于熵的减少量来衡量分割的有效性.

（7）

其中，是某個特征；为在上的信息增益；（）是所有可能的值；是值为时的数据集子集. 对文件级的语义向量进行二分类，预测和识别可能存在故障的文件.

Step 3：行级故障定位. 基于数据准备阶段所生成的文件代码行语义向量，应用决策树算法对可能包含故障的文件代码行语义向量进行二分類.

Step 4：输出结果. 综合文件级和行级故障定位的结果，输出最终的故障定位报告.

4  仿真实验

4.1 实验环境

硬件环境. 计算机型号：DESKTOP-FMMKAKR；处理器：Intel（R） Core（TM） i5-7300HQ CPU@2.50  GHz；内存：16 GB DDR4；存储：16 GB SSD；显卡：NVIDIA GeForce GTX 1050 Ti.

软件环境. 操作系统：Ubuntu 18.04 LTS；编程语言及版本：Python 3.7.4；数据集：Defects4J.

4.2 实验结果分析

训练了5个不同维度（50，75，100，200及300）的模型. 实验结果显示：随着维度的增加，向量包含的信息逐渐丰富，线性SVM的分类准确度也相应提高. 因此，将Word2Vec的维度超参数设置为300.

在文件级故障定位的性能比较中，决策树算法性能显著，如表2所示.

此外，根据文献［11］，利用西门子数据集对基于频谱的故障定位进行分析时，Ochiai相似系数的方法平均可以排除80%的无故障代码块. 相比之下，本研究的决策树算法文件级故障定位时，这一比例提升至90%.

表3为单纯的行级故障定位模型与结合文件级和行级的故障定位模型在Defects4J中的准确率. 可以看出，虽然单纯的行级故障定位模型与结合文件级和行级的故障定位模型在准确率上稍显不足，这可能是因为本研究所采用的数据预处理策略会在一定程度上牺牲了故障定位的准确性，但在定位速度方面，结合文件级和行级的故障定位模型表现更为优异，可以作为更加高效的故障定位策略.

5  结语

本文作者构建了文件级和行级相结合的故障定位模型，在标准测试中展现了良好的性能，相比传统基于频谱的故障定位技术，显著缩减了调试时需要审查的代码范围，进一步压缩了自动化故障定位所需的时间. 此外，采用决策树算法作为核心的故障定位模型，在实验评估中，该模型的故障定位准确率较高.

参考文献：

［1］ JONES J A， HARROLD M J， STASKO J. Visualization of test information to assist fault localization ［C］// Proceedings of the 24th International Conference on Software Engineering. Windsor： IEEE， 2002：467-477.

［2］ 白骏. 分布式Java程序切片及其在故障定位中的应用 ［D］. 南京： 东南大学， 2018.

BAI J. Distributed Java program slice and its application in fault localization ［D］. Nanjing： Southeast University， 2018.

［3］ LI X， LI W， ZHANG Y， et al. Deepfl： integrating multiple fault diagnosis dimensions for deep fault localization ［C］// Proceedings of the 28th ACM SIGSOFT International Symposium on Software Testing and Analysis. New York： ACM， 2019：169-180.

［4］ LUKINS S K， KRAFT N A， ETZKORN L H. Source code retrieval for bug localization using latent dirichlet allocation ［C］// 2008 15th Working Conference on Reverse Engineering. Antwerp： IEEE， 2008：155-164.

［5］ JIA Y， HARMAN M. An analysis and survey of the development of mutation testing ［J］. IEEE Transactions on Software Engineering， 2010，37（5）：649-678.

［6］ 马骏驰， 迪骁鑫， 段宗涛， 等. 程序表示学习综述 ［J］. 浙江大学学报（工学版）， 2023，57（1）：155-169.

MA J C， DI X X， DUAN Z T， et al. Survey on program representation learning ［J］. Journal of Zhejiang University （Engineering Science） ，2023，57（1）：155-169.

［7］ ALLAMANIS M，BARR E T，DEVANBU P， et al. A survey of machine learning for big code and naturalness ［J］. ACM Computing Surveys （CSUR）， 2018，51（4）：1-37.

［8］ JUST R， JALALI D， ERNST M D. Defects4J： a database of existing faults to enable controlled testing studies for Java programs ［C］// International Symposium on Software Testing and Analysis. San Jose： ACM， 2014：437-440.

［9］ MIKOLOV T， SUTSKEVER I， CHEN K， et al. Distributed representations of words and phrases and their compositionality ［C］// Proceedings of the 26th International Conference on Neural Information Processing Systems. New York： ACM， 2013： 3111-3119.

［10］ MIKOLOV T， CHEN K， CORRADO G， et al. Efficient estimation of word representations in vector space ［J/OL］. arXiv：1301. 3781， 2013 ［2023-10-10］. https：// arxiv.org/abs/1301.3781v1.

［11］ ABREU R， ZOETEWEIJ P， VAN GEMUND A J C. On the accuracy of spectrum-based fault localization ［C］// Testing： Academic and Industrial Conference Practice and Research Techniques-MUTATION （TAICPART-MUTATION 2007）. Windsor： IEEE， 2007：89-98.

（责任编辑：包震宇，郁慧）

DOI： 10.3969/J.ISSN.1000-5137.2024.02.012

收稿日期： 2023-12-25

作者简介： 王露露（1999—），男，硕士研究生，主要从事软件工程、代码异味方面的研究.E-mail： 1000513412@smail.shnu.edu.cn

*通信作者： 陈军华（1968—），男，副教授，主要从事数据信息处理技术及数据库信息系统方面的研究.E-mail： chenjh@shnu.edu.cn

引用格式： 王露露， 陈军华. 基于Word2Vec和决策树的故障定位技术 ［J］. 上海师范大学学报 （自然科学版中英文）， 2024，53（2）：223?227.

Citation format： WANG L L， CHEN J H. Fault location technology based on Word2Vec and decision tree ［J］. Journal of Shanghai Normal University （Natural Sciences）， 2024，53（2）：223?227.