基于循环变量的死循环检测.pdf

《自动化技术与应用》2015年第34卷第4期
计算机应用
Computer Applications
基于循环变量的死循环检测
常娟
(黑龙江司法警官职业学院,黑龙江哈尔滨150060)
摘要:本文提出了一种检测C语言程序的循环结构中是否存在死循环的方法,该方法基于循环结构中的循环变量,采用了程序的静
态分析技术,以及程序切片的思想来分析和理解程序,通过上述方法来判断给定的程序中是否存在死循环模式,也即在程序运
行中是否会出现死循环问题,从而提高程序的运行效率
关键词:循环变量;死循环;程序的静态分析;程序切片
中图分类号:TP311.1文献标识码:A文章编号:1003-7241(2015)04-0044-03
Infinite Loop Detection Based on Cycle Variable
CHANG Hui-iuan
( The Professional Judical Police College of Heilongjiang, Harbin 150060 China)
Abstract: This article mentions a method of detection that if there has dead cycle in the C programs, and it bases on the cycle
variable in the cycle structure, using the program's static analysis and the theory of program slicing to analysis and
understand the program. Based on those judgement to judge if there is dead cycle pattern, also if there is dead cycle in
the running of program, so the run effiency of the program can be proved
Key words: cyclic variable; dead cycle, program 's static analysis; program slicing
1引言
以改变的量,与之相对的,常量是其值恒定不变的量。
程序的静态分析是程序编译的一个重要研究内容,
(2)循环:在程序的执行过程中,当满足某特定
死循环是程序分析技术中一个不可忽视的方向,当程序的条件时,一条或一条以上的语句反复执行的过程,
中出现死循环时,往往会造成很多无法估计的后果和损称为循环。
失;死循环的检测可归结为停机问题,是一个不可计算的
在C语言中,循环结构共有三种:简单循环、串接循
问题,没有一种通用的算法能够精确地判定任意一个程环和循环嵌套;在程序中被反复执行的一条或一条以上
序是否含有死循环1,但是可以通过分析程序的代码,在的语句块称为循环体。事实上,几乎所有的程序中都存
定程度上检测出程序中的死循环;本文研究的是基于在着循环,有些方法使用有向环来描述程序中的循环?。
循环变量的死循环的检测技术。
(3)循环变量:在循环执行中,其值被不断改变,
并随着其值的改变最终使循环走向终止的变量称为循
2循环检测中的基本概念
环变量。
在介绍基于变量分析的检测技术之前,先来介绍分
在程序的循环过程中,当循环变量的值满足循环的
析过程中需要用到的一些基本概念。
条件时,循环体被不断地执行;反之,当循环变量改变
(1)变量:在程序的运行过程中,其值可以发生改不满足循环条件时,则不能继续执行循环体,循环终止。
变的量。
(4)死循环:在程序的运行中,由于不断满足循环
在程序中,通常有常量和变量两种。变量是其值可条件或是不能满足循环结東的条件,而使循环体反复i)
执行不停止的情况称为死循环。
收稿日期:2014-05-19
(5)程序的静态分析:通过直接对程序的代码进行
44 Techniques d Automation&Applications
计算机应用
《自动化技术与应用》2015年第34卷第4期
Computer Applications
所条件A
条件A
循环体A
语句组A
断条件
循环体A
判终件B
假
判断条件B
活句
环体B
语句短
循环体B
语句B
图1循环的三种形式
分析,从而发现其中错误的分析方法称为程序的静态分
析;静态分析方法的特点是不运行软件。
while(ml=n)(
if(m>n)(
(6)程序的切片:它有两种定义方式,一是通过从
m=m-ni
源程序中移去零条或多条语句构造的一个可执行程序;
二是由程序中语句和控制谓词组成的一个子集,这些语
else
men-mi
句和控制谓词直接或间接影响在切片准则计算的变量
Jif
的值,这类切片不必构成可执行的程序“4
/while
本文中基于循环变量的程序切片采用的是第二种
图2简单循环的实例代码
定义方式,将循环变量直接从运行程序中提取出来,使
用静态分析方法研究其变化规律及对程序的影响,是否
根据上面内容可以看出,m、n是该段代码的循环
存在错误导致死循环等问题。
变量,因此我们所关注的语句共有四句,其中使用②符
号表示循环条件,用#表示选择条件:
3基于循环变量的分析和抽象
程序的静态分析技术已经被研究了很多年,经历了
@ml=ni
若干种验证方法;其中比较知名的是路径敏感、路径不
#hm>n
m-m-ng
敏感,以及流不敏感、跨过程等分析方法。本文主要
#msn:
研究的是基于循环变量的程序静态分析,查找程序中可
n=n-ms
能存在的、导致死循环的一些错误。
图3简单循环的切片代码
下面分析一下循环结构的几种形式。循环结构是
程序语言的三种基本结构之一,它又包含三种形式:即
那么我们可以假定m总是两个数中较大值,n为较
简单循环、串接循环和嵌套循环;具体如下图所示。
小值,若求差后其值比n小,则两者互换,则可以将代码
接着我们就三种循环形式中循环变量对于循环的简化为如下形式:
影响进行分析。
om=np
a)简单循环中的循环变量分析
mem-nt
下面以一段代码为例,来分析在简单循环中的循环
变量以及是否存在死循环问题。
图4简单循环的代码简化
也就是说,当m和n不相等的时候,不断地求它们
techniques of Automation &Applications 45