论文部分内容阅读
随着当前软件规模的不断上升,软件维护的复杂度和效率日益受到关注。为了减少软件后期维护的复杂度、增加维护的效率,研究者提出了一系列程序理解的方法。这些方法降低了学习现有软件系统的成本,以辅助人工进行软件维护。在程序理解中,算法作为预先定义好的程序抽象化概念,直接诠释了程序的本质。基于这一点,算法识别是程序理解中的重要研究方向。本文在研究和分析现有算法识别技术的基础上,提出了基于抽象字符串的方法进行程序算法识别。 将程序源代码抽象为字符串表现形式的方法称为抽象字符串方法。在算法识别中,由于算法定义了具体的程序计算过程,所以实现同一类算法的程序具有同样的计算序列,体现在源代码上意味着具有近似的代码结构。然而不同的编程风格会带来在具体代码上的差异。通过将源代码抽象为字符串的方法,可以在消除具体代码差异的同时不影响计算序列的信息,从而可以提高算法识别的准确率。由抽象字符串方法生成的字符串作为程序源代码特征在数据体积上远小于原始的源代码,使得算法识别的效率得以提升。 在基于抽象字符串方法构建的源代码特征基础上,应用字符串相似度方法以及隐马尔科夫方法进行算法识别。字符串相似度方法利用实现同类算法的源代码会生成近似的抽象字符串的特性来实现算法识别。其通过对同类算法的源代码抽象字符串进行提取公共子串的方式获得算法特征字符串,并将算法特征字符串与待测程序抽象字符串进行相似度计算来判定待测程序实现了何种算法;隐马尔科夫方法是在抽象字符串的基础上,统计待测程序抽象字符串属于某一种算法的概率,从而判断待测程序实现了何种算法。隐马尔科夫方法对每一种算法建立对应的隐马尔科夫模型作为知识库。根据隐马尔科夫中的概率计算公式,计算待测程序在各种算法的隐马尔科夫模型下的概率,从而推断出它最可能是哪一种算法的具体实现。 实验结果显示字符串相似度方法相对于隐马尔科夫方法,在识别的准确性和查全率方面具有更优良的表现。同时,隐马尔科夫方法还有多种其它的建模方式可供改进,使得该方法在算法识别上拥有进一步优化的潜力。