一种基于马尔可夫链模型的代码克隆检测方法

专利主权项内容

1.一种基于马尔可夫链模型的代码克隆检测方法，其特征在于，包括以下步骤：S1 将待匹配的两代码段生成抽象语法树AST；S2 对于每个AST，将AST中的节点按照每连续的三个节点为一组进行拆分；基于马尔可夫链，构建每个AST的状态转移矩阵，并将其转化为转移概率矩阵；本步骤包括以下分步骤：S21 将AST中的节点按照连续的三个节点为一组进行拆分；前两个连续的节点作为马尔可夫链状态转换的初始状态，另外一个节点作为马尔可夫链状态转换中的另一状态；S22 基于马尔可夫链状态转换中的两个状态构建状态转移矩阵；S23 将状态转移矩阵转化为转移概率矩阵；S3 计算得到的两个AST对应的转移概率矩阵之间的距离向量，并以得到的距离向量作为提取的特征向量；S4 对提取的特征向量进行选择；通过训练集确定若干特征，具体为：首先采用至少一种特征过滤算法对训练集中样本经步骤S1-S3提取的特征向量进行过滤；所述特征过滤算法包括T-test、归一化互信息、距离相关性；之后采用机器学习算法对过滤后的特征进行筛选；所述机器学习算法为随机森林算法、KNN-1、KNN-3、决策树、极端梯度提升分类算法、迭代算法中的一种；S5 依据选择的特征，通过分类模型判断两代码段是否存在克隆关系。