All-Paths test generation for C programs with aliases
Description of the program:
This program is a toy implementation of the Nikolai Kosmatov's late-aliases algorithm for generation of all-paths tests for C programs with internal aliases. A complete test generation tool called PathCrawler was developed at CEA LIST. It generates test cases for all feasible paths of the given program in a depth-first search.
This toy implementation requires that the program under test be first translated into intermediate format (IF) manually, like it is done in the examples. The main object of this study being C-like programs with aliases, it focuses on aliases and treats only the most basic data types and operations: integers, arrays, conditionals and loops. It uses symbolic execution to obtain executed path. The addition is supported, other arithmetic operations may be added in a similar way. Function calls are not supported and may be added (in PathCrawler, they are easily modeled using assignments of arguments and return value).
To run the program on one of the given examples (say, max3.pl), copy the example file to input.pl and run the generation. On Linux you may type the following command:
cp max8.pl input.pl; eclipse -e "[toypcr],toypcr:strTest."
To redirect the output into the file output.txt, you may type:
cp max8.pl input.pl; eclipse -e "[toypcr],toypcr:strTest." > output.txt
To increase the print depth for long lists and to see the statistics, you may type:
cp max8.pl input.pl; eclipse -e "[toypcr],set_flag(print_depth,1000),toypcr:strTest,statistics."
If the path to the ECLiPSe executable eclipse is not added to the PATH environment variable, or another program called eclipse is installed, you may need to provide the path explicitly, e.g.
cp max8.pl input.pl; ~/ECLiPSe/bin/i386_linux/eclipse -e "[toypcr],set_flag(print_depth,1000),toypcr:strTest,statistics."
Downloads: Toy implementation of the late-aliases algorithm (for ECLiPSe Prolog) and some examples.
The main prolog file (toypcr.pl).
Installation of the program:
This program is written in Prolog language for ECLiPSe Prolog, but can be adapted for any other version of Prolog language containing an FD constraint solver. To install the program, just download the main file (toypcr.pl) and example files to the same directory.
To install the ECLiPSe Constraint Programming System, visit the ECLiPSe homepage. We will describe in more detail the installation of ECLiPSe for Ubuntu linux. (Superuser's password or rights may be necessary.)
To install ECLiPSe for Ubuntu linux, you will need to visit the ECLiPSe Distribution website and to download a recent distribution (choose the subdirectory of the recent version, then the subdirectory corresponding to your system platform, e.g. 5.10_118/i386_linux/). The fastest way is to install ECLiPSe from a binary package. An installation from source code may be necessary if the binary one does not work. We describe a binary installation on a i386_linux platform (for a different platform or a source code installation see the readme file):
Examples:
For each example, we also give the number of test cases and execution time of complete all-paths test generation by our toy implementation on a laptop Intel Core 2 Duo with 1Gb RAM.
#define TAB_SIZE 8
int max8(int x[TAB_SIZE])
{
int result,i;
result=x[0];
i=1;
while(1){
if(i<TAB_SIZE)
{
if(result<x[i])
result=x[i];
}
else
goto label_break;
i=i+1;
}
label_break: return result;
}
#define TAB_SIZE 3
int max3ExceptOne(int x[TAB_SIZE], int except)
{
int result,i;
result=-1000;
i=0;
while(1){
if(i < TAB_SIZE)
{
if(i != except)
if(result < x[i])
result=x[i];
}
else
goto label_break;
i=i+1;
}
label_break: return result;
}
#define TAB_SIZE 4
int SumAlias4(int x, int y, int z,int t) {
int i, result, a[TAB_SIZE];
for (i = 0; i < TAB_SIZE; i++)
a[i] = 0;
a[x] = 1;
a[y] = 2;
a[z] = 3;
a[t] = 4;
result = a[0]+a[1]+a[2]+a[3];
if( result == 10 )
return 1;
else
return 0;
}
#define TAB_SIZE 3
int SumAlias3(int x, int y, int z) {
int i, result, a[TAB_SIZE];
for (i = 0; i < TAB_SIZE; i++)
a[i] = i+1;
result = a[x]+a[y]+a[z];
if( result == 6 )
return 1;
else
return 0;
}
//order of a permutation of size 5
#define N 5 // number of elements
typedef int perm[N];
int getOrder(perm p){
// p is a permutation of 0,...,N-1
int i, order=1, isId;
perm power, tmp;
for( i=0; i<N; i++ )
power[i]=p[i];
while(1){
for(i=0,isId=1; i<N && isId; i++)
if( power[i] != i ) isId=0;
if( isId ) return order;
for( i=0; i<N; i++ )
tmp[i]=power[i];
for( i=0; i<N; i++ )
power[i] = tmp[p[i]];
order++;
}
}
int Merge (int t1[], int t2[], int t3[], int l1, int l2){
int i = 0, j = 0, k = 0;
while(i < l1 && j < l2){
if(t1[i] < t2[j]){
t3[k] = t1[i];
i++;
}
else{
t3[k] = t2[j];
j++;
}
k++;
}
while(i < l1){
t3[k] = t1[i];
i++;
k++;
}
while(j < l2){
t3[k] = t2[j];
j++;
k++;
}
return 0;
}
Some Links: