C程序代码结构自动审查方法研究

2013-10-27张晓欣孙伟杰

通信技术 2013年4期

张晓欣，孙伟杰

（中国人民解放军61081部队，北京 100094）

0 引言

自从1976年Michael Fagan首次提出代码审查（Code Inspection）以来，代码审查一直被认为是一种重要而且有效的改进软件质量的方法。经验表明，代码审查能发现软件中 30%～70%的设计和编码缺陷[1]。但随着软件规模的不断增大，人工代码审查耗时、成本巨大且需要知识和经验积累的问题也越来越引起人们的关注。因此，人们开始研究自动代码审查技术，开发相应的工具支持代码审查，以提高审查效率和准确性。

自动化代码审查技术主要通过利用计算机实现对源代码的静态分析，找出代码中潜在的代码缺陷，为代码审查中讨论和确定这个缺陷提供依据。因此，自动化代码审查技术为显著提高软件质量和可维护性提供了有力的支持。

1 目前的研究现状

目前的代码审查工具对程序结构的审查，其审查对象主要为函数调用图、数据流图等，其审查目的主要是对程序结构的度量，如计算程序的圈复杂度量[2]值是否过大、结构复杂性度量和 halstead方法[3]度量值等是否显著偏离合理范围。

上述方法一定程度上忽视了程序是否符合设计的功能模块划分，程序结构是否合理的检验。特别是一些遗留系统，要么缺少设计文档，要么由于代码的持续演化导致其已经明显偏离原设计等，因此很难准确有效的帮助测试人员进行软件结构的审查。

因此，代码结构自动审查技术主要是对文件的组织形式进行审查，目的是通过对源码的静态分析，分析程序的逻辑联接关系和语义相似度关系，提取程序的合理模块划分，通过与设计文档的比较，判断程序的结构是否合理。

2 C语言程序结构基本规则的研究

对于所有程序（除了最小的程序）来说，将整个程序都置于单个文件中既不明智也不实用。首先，每次修改了程序的任何一部分，都必须重新编译整个程序。其次，不能在另一个程序中重用这个程序的任何一部分，除非把源代码拷贝[4]给另一个文件。第三，这种结构不利于程序的维护。

根据编程实践中提出的合理组织方式的基础上，总结出一些程序结构应该遵循的基本原则：

1）主程序文件：通常为主函数单独建立一个文件，其中也可以包含少数与之关系密切的公共变量的定义和被主函数调用的函数。

2）对于全局变量和用户定义类型，应根据谁用谁管的归属原则，分别在不同的源文件里定义。

3）考虑把程序所需的功能划分为若干部分，每部分中定义的程序实体互相之间应有较密切的逻辑联系，这样形成一种整体性，可以考虑放在一起建立一个程序文件。

4）一个设计适当的功能划分可以作为一个单一的单位从系统中提出来，不必重写任何代码就可以在另一个系统中有效地重用。

5）公共程序实体，即在程序中可被广泛使用的程序实体（数据结构、公共函数等），这些实体的特点是程序中被众多的其它实体使用，因此与程序中不同模块的实体之间都有着比较密切的关联。这些公共实体应当被单独划分为公共模块。

6）程序中变量、函数的命名应符合命名规范，且使用能够清楚说明其功能的词汇（单词或词组）或适当的缩写。

3 C程序代码结构自动审查方法研究

自动化代码结构审查技术主要通过静态分析的方法对被审查程序的源代码进行结构分析[5]，提取程序实体间逻辑联接关系和语义相似度关系，通过聚类的方法根据程序高内聚、低耦合的原则提取出程序组织，与被审查程序文件组织结构的比对，为被审查程序的重组提供依据，从而提高代码的维护性和可读性，并且方便代码的复用。

3.1 程序实体间逻辑联接关系的研究

在程序中，函数、用户自定义结构类型及全局变量这3种程序实体之间的逻辑连接关系可归纳为如图1所示关系。

图1 程序实体间逻辑关系

（1）函数间关系

calls：一个函数调用另外一个函数。

（2）用户自定义结构类型间关系

is-part-of-utype：一个typedef struct用于另外一个typedef struct的定义中，如：

（3）函数与全局变量间关系

actual-parameter：全局变量作为函数的实际参数使用。

var-access：函数访问全局变量：函数赋予全局变量一个新值，或函数读取全局变量数值，或函数使用全局变量地址。

（4）用户自定义结构类型与全局变量间关系

var-of-utype：全局变量被声明为用户自定义结构类型。

（5）函数与用户自定义结构类型间关系

return-utype：函数的返回值类型为用户自定义结构类型。

access-fields：函数访问由用户自定义结构类型声明的变量，以“.”或“->”的方式进行访问。

local-var-of-utype：函数中的局部变量由用户自定义结构类型声明。

parameter-of-utype：函数声明列表中的形参由用户自定义结构类型声明。

上述5类9种连接关系基本上反映了函数、用户自定义结构类型及全局变量3种程序实体之间的逻辑连接关系，通过静态分析得到这3种程序实体的各体及其相互间逻辑关系，为逻辑连接关系度量提供了基础。

3.2 程序实体间语义相似度度量算法

程序中变量、函数的命名应符合命名规则，并在在一定程度上说明该变量或函数所能完成的功能。因此，规范的变量、函数命名包含丰富的语义信息，针对语义信息的相似度度量有助于对程序划分的提取工作。

但是，要获取程序实体名字之间的语义相似性，并据此来发现元素之间的聚类关系，必须采用适当的方法来完成程序实体名称之间的语义相似度度量。

目前较为常用的字符串间相似度度量算法包括：

（1）编辑距离

俄国科学家 Vladimir Levenshtein提出的编辑距离方法可以用来判断字符串的相似度。编辑距离，又称Levenshtein距离，是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。编辑距离法允许的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。试验证明，两个字符串间的编辑距离越小，则其相似度越高。

（2）最长公共子串

最长公共子串(LCS，Longest Common Subsequence)方法可以用来计算字符串之间的相似度。LCS的解法是用一个矩阵来记录两个字符串中所有位置上的两个字符之间的匹配情况，若是匹配则为1，否则为0。然后求出对角线最长的“1序列”，其对应的位置就是最长匹配子串的位置。试验证明，两个字符串间的最长公共子串越长，则其相似度越高。究其原因，主要是由于变量、函数的命名通常是由有意义的英文单词或独立或联合构成，其相似性更加适合使用最长公共子串法来进行计算。