top
<返回首页 <退出
欢迎您来到51-ARM学习论坛,您还没有[注册]或[登陆]
用户名:  
密  码:  
验证码:  
共有1299位会员 新进来宾:xle
今日发帖:27篇 在线人数:965人
最高发帖:140篇 主题总数:589篇
消息:热烈祝贺侯工单片机工作室官方网站正式开通!论坛版块诚征精英斑竹...凡51-ARM论坛斑竹,均有机参加侯工单片机工作室组织的各种技术交流,培训!!!
 论坛帮助  
51-ARM论坛>>单片机杂谈-破天荒
 
  标题:(经典)汇编程序覆盖测试中不可达指令检测算法
日本豆腐 
排长
等级: 普通会员
文章:3
积分:138
     楼主

汇编程序覆盖测试中不可达指令检测算法

1、引言

        一般而言,汇编语言程序的执行表现为一系列逻辑路径的动态组合,测试时尽量覆盖所有可能的路径是软件测试的目标之一,有关的工作叫做覆盖测试。目前大多数测试工具是针对C/C++等高级语言的,针对汇编语言的测试工具相当少见。由于汇编语言非结构化的特点,其实现程序往往采用很多条件和无条件跳转指令,使得程序结构复杂化,按照汇编语言程序执行的一般方法,可以得到语句的执行序列。如果当一段程序中包含有一些无论在任何情况下都不需要执行或者根本执行不到的指令时,一般的测试方法就很难将这些指令甄别出来并给出适当的提示或进行必要的排除。这些指令称为不可达指令。为此,在研究汇编程序软件测试的过程中,本文提出了一种判定汇编源程序不可达指令的算法。

2、不可达指令的判定

2.1 算法提出的前提条件

程序块

定义1 程序块是指程序中一个含有少量的语句序列,其中只有一个入口语句和一个或多个出口语句,执行时只能从入口语句进入,从出口语句退出。对于一个给定的程序,可以把它划分为一系列的程序块。

定义2 入口语句是指:1) 程序的第一个语句;2) 或者能够由条件转移语句或无条件转移语句转移到的语句;3) 或者紧跟在条件转移语句后面的语句。

定义3 出口语句是指:1) 下一条入口语句之前的那条语句;2) 或者程序的终止语句。

2.2 不可达指令的判定算法基本思想

1)首先将已经划分好的某个源程序块的所有语句序列号存入一个预先定义好的数组A中;

2)取程序段执行中可以认可的初始值的上限运行程序,将指令执行的语句序列进行记录,并存入一个预先定义好的数组A1中;

3)取程序段执行中可以认可的初始值的下限运行程序,同样将指令执行的语句序列进行记录,并存入一个预先定义好的数组A2中;

4)取程序段执行中可以认可的初始值的中间值运行程序,同样将指令执行的语句序列进行记录,并存入一个预先定义好的数组A3中;

5)将A1,A2,A3三个数组分别与源程序段的语句序列数组A进行逐项比较,并分别把不同项列出并存入数组B1,B2,B3中;

6)最后将分别存有不同项的三个数组B1,B2,B3进行比较,找出其交集,其交集中的元素即为不可达指令语句号。

2.3 不可达指令的判定算法实现

        算法实现如下:

Void pleonasm( )
{
Int A[n],A1[n],A2[n],A3[n],B1[n],B2[n],B3[n],B[n];
Int I,j,k=0,p=0;
For(i=0;iFor(j=0;jIf(A[i]!=A1[j])
{ B1[k]=A1[j];
k++;}//找出执行上限值时没有执行到的指令序列号
l=len(B1);
k=0;
For(i=0;iFor(j=0;jIf(A[i]!=A2[j])
{ B2[k]=A2[j];
k++;}//找出执行下限值时没有执行到的指令序列号
k=0;
m=len(B2);
For(i=0;iFor(j=0;jIf(A[i]!=A3[j])
{ B3[k]=A3[j];
k++;}//找出执行中间值时没有执行到的指令序列号
n=len(B3);
for(i=0;ifor(j=0;jfor(k=0;kif(B1[i]==B2[j]&&B2[j]==B3[k])
{B[p]=B1[i];
P++;
Printf(“不可达指令语句号=%d,”,B[p]); }
Pringf(“\n”);
}

3、算法验证

        下面以一个简单的汇编源程序来验证算法。

1)根据判定算法,首先把源程度块的所有语句序列号存入数组A
A={1,2,3,4,5,6,7,8,9,10,11,12}

2)把X=12(大于0的数)时所执行的语句序列号存入数组A1
A1={1,2,3,4,5,6,7,10,11,12}

3)把X=-3(小于0的数)时所执行的语句序列号存入数组A2
A2={1,2,3,4,9,10,11,12}

4)把X=0(等于0的数)时所执行的语句序列号存入数组A3
A3={1,2,3,4,5,10,11,12}

5)分别求出A1、A2、A3的补集B1,B2,B3
B1= ={8,9},
B2= ={5,6,7,8},
B3= ={6,7,8,9}

6)求出B1,B2,B3的交集B
B=B1ΛB2ΛB3={8}

        因此可以断定语句8为不可达指令,从源程序块中删除后并不影响程序的正确性。

4、算法复杂度分析

        此种算法源于程序块内,程序结构全部为顺序结构和简单分支结构,因此遍历过程算法复杂度均为O(n),判定交集算法复杂度为O(n2)。因为此算法只是进行两种运算,因此算法综合复杂度为O(n2)。

5、结论

        本文讨论了一种判定汇编语言程序不可达指令的算法,并通过一个示例程序说明了算法的实现并验证了其正确性。本文的工作为覆盖测试更全面、更有效的进行做了必要的补充,下一步需要做的是研究高效的覆盖测试算法,以提高测试的覆盖率。

[此帖已经被作者于2009-4-9 20:38:07编辑过]  
 
 2009-4-9 20:37:48  
日本豆腐 
排长
等级: 普通会员
文章:3
积分:138
     第1楼
 
 
 2009-4-9 20:38:12  
pplive 
士兵
等级: 普通会员
文章:0
积分:94
     第2楼
 
 
 2009-4-10 16:51:49  
没有激情 
排长
等级: 普通会员
文章:0
积分:112
     第3楼
学习下
 
 
 2009-04-12 20:21:07  
阿涛 
排长
等级: 普通会员
文章:5
积分:181
     第4楼
 
 
 2009-04-17 01:57:24  
kks 
排长
等级: 普通会员
文章:0
积分:100
     第5楼
学习
 
 
 2009-04-17 01:58:02  
首页 上一页 下一页 末页 页次1/1页 共 5 条回复 第
快速回复:
 
bottom
 
联系电话:0755-26766021 邮箱:51-ARM@163.com QQ群:43996737
项目定制承接手机:13798532857(侯工)
部分内容转载于网络,如有涉及版权问题,请通知本站删除。
粤ICP备09217420号 版权所有  @  2008-2012  侯工单片机工作室