第卷第期秦振华牟永敏面向程序的环形复杂度自动化计算方法其入度为和一个唯一的出口节点其出度为控制流图中的节点代表程序的语句或表达式有向边表示语句间的执行关系令表示控制流图中的边称是的前驱是的后继控制流图中的节点可分为种类型一种是块结构即把程序划分为块块

Size: px

Start display at page:

Download "第卷第期秦振华牟永敏面向程序的环形复杂度自动化计算方法其入度为和一个唯一的出口节点其出度为控制流图中的节点代表程序的语句或表达式有向边表示语句间的执行关系令表示控制流图中的边称是的前驱是的后继控制流图中的节点可分为种类型一种是块结构即把程序划分为块块"

焙贺
5 years ago
Views:

1 第卷第期计算机工程年月体系结构与软件技术文章编号文献标志码中图分类号面向 9 程序的环形复杂度自动化计算方法秦振华牟永敏北京信息科技大学计算机学院北京摘要为准确度量软件复杂程度提出一种环形复杂度计算方法借助于 " $ 度量法针对语言程序通过对源程序进行预处理提取其中含有控制流信息的关键语句后对其进行分情况处理从而无须借助控制流图即可实现程序环形复杂度的自动化计算实验结果表明该方法可以准确高效地计算出程序的环形复杂度关键词 " $ 度量法控制流图环形复杂度复合条件自动化计算中文引用格式秦振华牟永敏面向程序的环形复杂度自动化计算方法计算机工程 # 英文引用格式 8 0 0$ " 7 $ $$ 0, $ # (% (-9 - (% "(3% %)24 9%,"6(0 )% 9 % $" $ $, % 0 1 * 1-0 $ $( -(, $ $ 1 $* *. 2$ 0*$ * *$ $$ 0,. 3 1: " $ 0, $ $ $ $ $ 1 ** 0 * $ 0 1 * $ *200 $ 0.2. $ * 3 $,%0 1 * *$ **, * $ $ 1 * $* $+ 0 $ $ $$. $ 3 1$,,, * 0 '2 ( $0 '( 3 $ * **02 0$ 0 0, *. $* $, $ $$ $ $ $ 1 $,. 1 /"0 1% $ " $ 0, '2( $0'( 3 1,, $ $ $$ # 4 ** # 概述软件复杂性主要表现在程序的复杂性即模块内程序的复杂性常见的定量度量软件复杂性的方法有代码行度量法 " $ 度量法和 $* $, 度量法 " $ 度量法根据程序控制流的复杂程度定量度量程序复杂程度这样度量出的结果称为程序的环形复杂度在软件测试中环形复杂度用于衡量一个模块判定结构的复杂程度数量上表现为独立路径条数即合理的预防错误所需测试的最少路径条数这是为确保所有语句至少执行一次而必须进行测试的数量的上界也可以理解为覆盖所有的可能情况最少使用的测试用例数 # 在通常情况下程序环形复杂度值越大说明程序判断逻辑越复杂越容易出错且软件难以测试与维护大量研究和经验表明环形复杂度与软件模块中的错误紧密相关假如一个模块比较复杂那么它就容易出错当超过了度量的阈值通常是模块中的错误数量也会随之急剧增长 # 目前计算程序环形复杂度的方法有种一种是根据控制流图人工计算出环形复杂度当程序比较复杂时容易产生错误另一种是采用工具自动计算如 " 计算速度快但在某些复杂条件下得出的环形复杂度不够准确针对上述问题本文通过对源程序进行预处理提取程序中含有控制流信息的关键语句实现程序环形复杂度的自动化计算相关技术控制流图控制流图 '2 ( $0'( 是一个有向图 0 其中是控制流节点的集合是有向边的集合一个控制流图有一个唯一的入口节点基金项目国家自然科学基金北京市自然科学基金网络文化与数字传播北京市重点实验室开放课题北京信息科技大学研究生教育基金作者简介秦振华男硕士主研方向为软件自动化测试牟永敏教授博士收稿日期 ## 修回日期 ## / +0 0$

2 第卷第期秦振华牟永敏面向程序的环形复杂度自动化计算方法其入度为和一个唯一的出口节点其出度为控制流图中的节点代表程序的语句或表达式有向边表示语句间的执行关系令表示控制流图中的边称是的前驱是的后继控制流图中的节点可分为种类型一种是块结构即把程序划分为块块中的语句是连续的且只包含简单语句不包含分支和循环等引起程序执行顺序改变的语句另一种是程序的每一条语句都单独地看成一个控制流节点 # 本文绘制的控制流图节点采用第一种类型并且以程序的行号来表示程序的控制流节点 -9 " 度量法计算程序的环形复杂度有种方法以图所示控制流图为例图控制流图种方法的具体描述如下给定控制流图 0 的环形复杂度 0 控制流图中区域的数量仅考虑区域个数不考虑边的方向图中区域数量为则 0 给定控制流图 0 的环形复杂度 0 定义为 0 是控制流图中边的数量是控制流图中节点的数量图中边的数量为节点的数量为则 0 给定控制流图 0 的环形复杂度 0 定义为 0 是控制流图中判定节点的数量判定节点是只包含一个条件的节点从每一个判定节点发出条或多条边图中判定节点的数量为个判定节点为则 0 问题分解本文针对语言程序研究环形复杂度的自动化计算首先分析其结构特点语言程序中的语句分为控制语句函数调用语句表达式语句空语句和复合语句共种其中控制语句分为种分别是.# * 条件语句. 循环语句 20 循环语句,#20 循环语句语句 $ 语句 *2 0 多分支选择语句语句和语句 # 在这里将.# * 语句.# *. 语句 *2 0#$* 语句和包含三目运算符的语句称为分支语句. 语句 20 语句和,#20 语句称为循环语句分支语句和循环语句将对应于控制流图中的判定节点因此可以借助程序中的分支和循环语句来实现环形复杂度的计算当程序中分支语句或者循环语句的判别条件为复合条件时将复合条件分解成单个条件后再进行环形复杂度的计算下面将分情况讨论语言程序中分支语句和循环语句对程序环形复杂度的影响.# * 语句当. 语句中只有个判别条件时当前语句对应的判定节点的数量等于当. 语句中有多个判别条件时当前语句对应的判定节点的数量等于. 语句中判别条件的个数.# *. 语句对于.# *. 语句除了考虑. 语句的情况外还需要考虑 *. 语句的情况处理方法和.# * 语句的处理方法相同当前语句对应的判定节点的数量等于判别条件的个数包含三目运算符的语句由于包含三目运算符的语句也是一种特殊的条件语句因此其处理方法和.# * 语句的处理方法一样其对应的判定节点的数量等于语句中判别条件的个数 *2 0#$* 语句对于 *2 0#$* 而言有没有,.$ 语句对于程序环形复杂度的计算没有影响在一般情况下判定节点的数量等于 $* 的个数由于 *2 0#$* 不用像.# *. 那样遍历条件分支直到命中条件而只需访问对应索引号的表项从而达到定位分支的目的具体地说 *2 0#$* 会生成一份大小表项数为最大 $* 常量的跳表程序首先判断 *2 0 变量是否大于最大 $* 常量若大于则跳到,.$ 分支处理否则取得索引号为 *2 0 变量大小的跳表项的地址即跳表的起始地址表项大小 " 索引号程序接着跳到此地址执行到此完成了分支的跳转所以即使 $* 中没有 $ 语句也不会影响产生的分支数对程序环形复杂度的计算也不会产生影响但是存在一种特殊情况即多个 $* 相连此时需要把多个相连的 $* 当成一个判定节点进行计算以文献中的例子加以说明如图所示图多个 -$" 相连的情况

3 计算机工程年月日 20 语句在一个循环结构中循环条件表达式和循环结束条件共同决定程序的最终走向结合这一特点对于 20 循环语句可以分种情况进行讨论条件表达式永真这里只考虑 20 这种形式的永真但是有循环结束条件此时 20 语句不是判定节点如图所示分析工具可以维护测量和分析源代码该工具能够分析种语言包括 4 $ $'&5%5 和一些 : 编程语言例如并且适用于大部分操作系统包括 $ * 该工具可以对整个项目的结构度量值进行分析并输出报表能够对代码生成多种图包括控制流图依赖关系图 " 类图等 " 是一款免费的软件运行在 :,2* 平台下它可对多种语言写的代码进行度量包括 ' $ $- 0 和 %" 并且针对不同的语言输出不同的代码度量值对于程序提供了总行数语句数目分支语句比例注释比例函数数目平均每个函数包含的语句数目函数环形复杂度和函数深度等度量值系统分析与设计图 13" 语句的特殊形式在图中第行和第行语句合并为一个节点此时控制流图中只有一个判定节点这与平时遇见的情况有所不同需要特殊处理条件表达式永真但是无循环结束条件即所谓的死循环此时 20 语句是判定节点条件表达式永假这里只考虑 20 这种形式的永假此时循环体内的所有判定节点都不需要计算包括 20 自己条件表达式非永真永假并且是单个条件此时 20 语句相当于一个判定节点条件表达式非永真永假并且是复合条件此时 20 语句对应判定节点的数量等于 20 语句中判别条件的个数. 语句. 语句的处理方法和 20 语句的处理方法一样,#20 语句,#20 语句的处理方法和 20 语句的处理方法基本一致唯一的区别是当条件表达式永假时 20 语句的循环体内的所有判定节点都不需要计算而,#20 语句的循环体内的判定节点需要计算代码度量工具环形复杂度是代码复杂度的一个指示器可以利用一些著名的开放源码工具计算环形复杂度比如 "0 1 和 $ $ 但是这些工具只是针对 $ $ 程序的 & % * 2 "%, * $, " 等工具可以度量程序的环形复杂度在实验部分借助于后种工具和本文提出的方法进行比较, * $, 是一个 %* 发行的商用的静态本文提出的研究方法可分为个阶段源代码的预处理控制流信息的提取环形复杂度的自动化计算其中采用了状态机编程思想删掉源程序中的注释来实现源代码的预处理利用模式匹配的规则来提取含控制流信息的关键语句通过分情况处理关键语句来实现程序环形复杂度的自动化计算源代码预处理技术源代码的预处理主要是扫描程序中出现的注释并将其删掉由于注释信息对最后环形复杂度的计算没有影响并且注释中的某些信息会干扰接下来关键语句的提取因此找出源代码中的注释信息将其从源代码中删掉这里只考虑单行注释多行注释和折行注释这种情况其中折行注释是以双斜杠开头反斜杠结尾很多编辑器高亮都没有考虑到这种情况此处采用了状态机编程思想将源代码中的注释删掉控制流信息的提取在程序中分支语句和循环语句最终对应于控制流图中的判定节点因此如何提取程序中的分支和循环语句显得尤为重要此处通过模式匹配的方式提取程序中的关键语句其中模式匹配规则如表所示表模式匹配规则模式序号模式规则 # *.#.#. #20 * *2 0 * #$* #,.$ * * * $ #, # # 表中的模式匹配规则共有种模式左侧为模式序号右侧为模式匹配的规则由于计算的是

4 第卷第期秦振华牟永敏面向程序的环形复杂度自动化计算方法单个函数的环形复杂度因此用模式匹配程序中的函数定义从而开启一个处理单元分支语句和循环语句用模式和进行匹配其中模式匹配.. 和 20 语句模式匹配 *2 0#$* 语句模式匹配包含三目运算符的语句模式匹配,#20 语句和 $ 语句匹配 $ 语句是为了后续判断当循环结构中无循环条件表达式时有无循环结束条件如果循环体中有循环结束条件 $ 语句那么循环可以正常结束此时的循环语句不是判定节点否则是死循环结构此时的循环语句是判定节点模式用来进行花括号匹配左花括号对应语句块的开始右花括号对应语句块的结束根据花括号可以对源程序进行分块处理在表规则的基础上再结合正则表达式中的 * $ 0 方法就可以将程序中的关键语句信息都提取出来环形复杂度的自动化计算经过源程序的预处理和提取关键语句这步此时程序中只剩下分支语句循环语句等关键信息接下来需要根据这些关键信息进行程序环形复杂度的计算在当前步的处理中需要注意的是当语句中判别条件是复合条件时需要把复合条件分解成单个条件进行计算对于循环语句中条件表达式永真永假的情况尤其是当条件表达式永真但是有 $ 语句可以跳出循环此时当前循环语句并不能当成判定节点这种情况都需要进行特殊处理鉴于此在当前步骤的算法设计中采用自顶向下的分析策略对各种情况分别编写相应的处理函数定义一个栈 * $ 用来进行花括号匹配定义一个变量用来记录最终环形复杂度的值初始值为并用.$ 标志来标记循环语句块中是否有 $ 语句.$ 表示没有.$ 表示有用标志标记. 语句块中是否包含 $ 语句当循环语句块中嵌套. 语句块. 语句块中包含 $ 语句此时 $ 语句也可以跳出循环.$ 然后从上往下扫描源程序如果当前语句中包含则进行入栈操作 * $ *0 若包含则进行出栈操作 * $ 若包含. 关键字 *2 0 关键字, 关键字. 关键字 20 关键字三目运算符则相应地调用 %. % $* %, %. % 20 % 0 方法通过对应的方法计算代码块中相应代码的环形复杂度并把计算得到的结果加到变量中去接着进行下面语句的处理直到程序结束这样最终程序环形复杂度的值便等于变量的值其中计算 20 语句块中相应代码的环形复杂度的算法如下算法 %20 输入程序的行号值输出环形复杂度值 * 0 * $ *.$, 3 0 * $ " * $ * $ $ * $., $ 3 ** * /$ 0 20 * $ * /$, $, 0 3 * $, 20 * 20 * $ * /$, * 0 3 * $.* $ *. 0 * %., 3. * 0.$*.$,. *.* $ **2 0 0 * % $*, 3 *.* $ *, 0 * %,, 3 *.* $ *20 0 * %20, 3 *.* $ *. 0 * %., 3 *.* $ * $ 1 $ 0 * % 0, 3 *.* $ * $ 0.$,., 20., $ 3 ** * /$ 0..$ * /$ 0 *,. * * 0., *,.,. * 在算法中对于 20 语句块的处理需要考虑条件表达式永真永假和非永真永假这种情况语句块的开始和结束对应栈的入栈和出栈操作当栈中元素个数为时标志着当前语句块中内容处理完毕对于条件表达式永假的情况直接顺序读取语句块中的内容即可对于永真的情况需要根据.$ 的值来判断 * 的值需不需要加对于非永真永假的情况 * 需要加的值等于 20 语句中条件的个数

5 计算机工程年月日实验评测实验环境实验所用操作系统为位 :,2* 旗舰版 $ 内存为 (- 处理器为 5 %" #8" ( + 测试用例实验中用的测试用例采用了文献中的程序该程序涉及到了注释.# * 语句 *2 0#$* 语句 20 语句三目运算符单个判别条件和复合条件具有一定的代表性具体测试用例如下所示 $ $$3 0$ $.$ 20 下方法利用 ( 编译源代码生成中间文件提取并分析中间文件的语句块信息找出语句块之间的关系用替换的方法把语句块之间的关系转换成行号之间的关系并把结果输出到一个, 文件中去最后使用 : ( $0 + 这个 &" 组件把最终结果以控制流图的形式展示出来 # 本文系统在自动生成控制流图时对于程序中判别条件是复合条件的情况将复合条件拆成单个条件并用行号 % 条件标号这种形式进行表示例如 % 表示第行第个判别条件对于三目运算符来说执行的语句用行号 % 语句块标号这种形式来表示例如 % 表示执行第行第个语句块中的语句上述测试用例所对应的控制流图如图所示.$ 0. 第, 次运算 44 输入的字符不是小写字母退出程序..$ $.$ + 44 输入运算数和运算符 *$.,, $ $ $3 $ $ 44$3 记录最大值 *2 0 $ $* $ $ $* 4. * $4 $,.$. 结果为,, $3 * $ 为了能更好地验证本文提出的环形复杂度自动化计算方法同时实现控制流图的自动生成采用如图测试用例对应的控制流图测试用例中..$ $".$ +" 语句的判别条件是复合条件拆成个判定节点 $3 $ $ 语句包含三目运算符判别条件是单个条件相当于一个判定节点 *2 0#$* 中有个 $* 产生个判定节点再加上嵌套的. 语句共产生个判定节点而对于 20 这种条件表达式永真的循环语句由于循环体中存在循环结束条件因此 20 语句不是判定节点综上所述测试用例中共有个判定节点程序的环形复杂度为实验结果根据图可知测试用例的环形复杂度为这与图得出的实验结果一致所以本文提出的方法可以准确地计算出程序的环形复杂度将系统命名

6 第卷第期秦振华牟永敏面向程序的环形复杂度自动化计算方法为 5 % * 工具与, * $, 和 " 工具针对上述测试用例计算得到的结果进行比较最终结果如表所示没有考虑循环语句中永真和永假的特殊形式对于 *2 0#$* 语句在一般情况下不管有没有,.$ 语句判定节点数等于 $* 的个数但是当 $* 语句块中没有 $ 语句时当前 $* 语句不当成判定节点对于多个 $* 相连的情况会把多个相连的 $* 当成一个判定节点进行计算通过比较可知系统在计算环形复杂度时相对于, * $, 和 " 工具更加准确下面分析种工具在计算时间开销上单位是秒的差别分别以行代码为例进行比较最终结果如表所示表种工具的计算时间开销 * 工具行代码行代码行代码 5 % *, * $, " 图程序运行结果表种测试工具的比较结果工具环形复杂度分析 5 % * 20 语句不是判定节点, * $, " 把复合条件 20 语句都当成一个判定节点 20 *,.$ 语句都当成一个判定节点经过大量实验得出, * $, 和 " 工具在计算环形复杂度时与 5% * 有如下不同, * $, 工具在生成控制流图和计算时把复合条件当成一个条件进行分析像循环语句中 20 和 20 这种特殊的永真和永假形式并没有被考虑在控制流图中会画出 20 节点并把 20 节点当成判定节点加入到环形复杂度中去对于包含三目运算符的语句在控制流图中当成顺序语句节点来处理在计算时会当成一个判定节点进行计算但是没有考虑复合条件的情况对于 *2 0#$* 语句在一般情况下当 $* 语句块中没有 $ 语句时对环形复杂度的计算无影响但是一旦出现多个 $* 相连这种特殊情况在生成控制流图时会把多个相连的 $* 当成一个节点在计算时统计的是 $* 的个数 " 工具将复合条件拆成多个单条件进行计算但是在处理包含三目运算符的语句时没有考虑复合条件只当成一个判定节点对于.# * 结构的语句会把 * 当成一个判定节点由表可知 5 % * 工具在计算效率上比 " 略高由于, * $, 工具会生成控制流图等额外信息因此时间开销较大但是产生的信息比较齐全结束语环形复杂度是软件难度度量的一个重要指标本文通过提取源程序中含有控制流信息的关键语句对其进行分析处理用于实现环形复杂度的自动化计算在这种方法下无需知道源程序的控制流图而且通过去掉源程序中一些无关紧要的信息只留下影响环形复杂度的关键信息进而可以高效准确地计算出程序的环形复杂度可操作性更强更简单节约了测试时间降低了测试成本下一步将完善该工具的扩展性使其可以计算其他语言编写的程序的环形复杂度参考文献 " - % 3 1 $* % $ *$ *. 2$ # : % & " - %, * $ * 0, 1 * 0 1 $ 3 1-4& ## $ 4/% * $ 0% * 0-5% 1 $ $ # " & & 0. 1 $ 3 1 $ $ $.. 2$ $, * $ * # & & 6 :&& (+" $ $ $ *$+$. *, * 44, *. $ $. $,. $ % 0 1:$*0 ** # 下转第页

7 计算机工程年月日结束语违约是互联网金融平台中常见的不良行为不仅会使交易中的一方蒙受损失对平台中用户的交易倾向也会产生不利影响本文基于典型相关分析模型及用户复杂网络特征提取方法对用户建立合理的违约风险量化及预测模型并对用户的个人特征及网络特征对违约风险的影响进行分析与评价分析结果表明用户的一些网络特征对于违约的影响要大于其个人特征在实际互联网平台运营过程中对于预测风险较高的用户进行更多的关注与审核可以有助于对平台违约率的控制但本文模型的数据集仍存在一定局限性下一步将对此进行改进并扩大特征的提取与选择范围以取得更好的预测效果参考文献刘新海丁伟大数据征信应用与启示以美国互联网金融公司 * ' $ 为例清华金融评论 # 张权罗嗣汉机器学习在金融大数据风险建模中的应用 -4& # # ,* 4$ 0 *4 ( " : (, * 2 0 $,$ $ $ $0 $*, * $0 * 3 1* *2 0 $ * # : ( (" ( $%2, *, *$*,,$* $ 1 * * 6 2, #$*, 1* * # 石澄贤陈雪交网贷个人信用评价指标体系的构建常州大学学报社会科学版 # 林国强赵毅鸣况青作等基于复杂网络和机器学习的用户违约预测北京师范大学学报自然科学版 # ; 5 ) $ $, *,.# $ 3 2 * 01**5 * # - ; 7 ( " $,.1 < $, * 3 2 * 01*$ $ * $" 0$ *$, * $ * # '5 " $ 1 * $ 2 * $ $.$ $ 2 * # '5 " *. $* *. $ 1 $*, 2 ** 1 # -& '$ $, 2 0 $ $0 * * $ ** *$, /,.$ $. "$ 0 $ $ 1 # -5 %0 $ $ 1.$ #*$ 01 3 $: * $ 0 2 * # 6-5( " 0 $ * * $01, $. 0 " # 5 : " 5 应用多元统计分析 " 陈诗一译北京北京大学出版社李航统计学习方法 " 北京清华大学出版社编辑吴云芳上接第页 5&( 02. 2$ * 0, * $ 0. 1 $ $,* 1 $, # (&'5 7 " ::0$, *.2 $1 1 $ 0 1 $ , *. $ $:., $1**$, "$ $ :$*0 ** # " $* #, $* $ $ $0 " - ( $ 1 % 7 % 5& " - 5( $$, 3 1 * *. 3 1 $* * $, 0.., 3 1 $ $ $. 2$ # 5 ' (. $. 1 $ 3 1.$ $ 44, *.$ $. 0. 2$ 1* *$, ( - ( $ 1 - %% 5 $ $*.*, 3 1 $ 2, $ * 1. % 0 1 陈梦云高建华基于圈复杂度的静态测试用例排序方法计算机应用与软件 # 陈梦云基于圈复杂度和调用次数的测试用例排序方法上海上海师范大学谭浩强程序设计 " 版北京清华大学出版社张海藩软件工程导论 " 北京清华大学出版社牟永敏杨志嘉基于函数调用路径的软件实现与设计一致性验证中国科学信息科学 # 牟永敏李慧丽基于函数调用路径的测试用例优先级排序计算机工程 # 周希基于静态分析的程序控制流图生成工具的设计与实现广州中山大学编辑顾逸斐

自然科学版预处理视盘粗定位视盘垂直坐标的粗定位视盘水平坐标的粗定位

自然科学版预处理视盘粗定位视盘垂直坐标的粗定位视盘水平坐标的粗定位自然科学版文章编号视网膜图像中视盘的快速自动定位方法赵晓芳林土胜李碧摘要基于眼底视网膜血管的分布结构及视盘本身的特点提出一种快速自动定位视盘的方法首先根据视网膜血管的网络分布结构大致定位视盘的垂直坐标然后根据视盘的亮度信息及视盘与血管的关系来定位视盘的水平坐标最后把视盘限定在以粗定位的视盘为中心的一个小窗口内用变换精确定位视盘中心该方法不需要事先分割视网膜血管也不需要对算法进行训练