[klee-dev] 回复: symbolic variable appears in the offset of a pointer or an array

im 1527733628 at qq.com
Wed Jul 3 16:05:24 BST 2024


Thanks for your reply!
I may not have described it clearly,I use klee to generate test cases for a source code.
On the basis of not changing the source code,I want to generate cases to cover all the path.
If the code test.c is written like this:
int my_test(int *p,int index){
	if (p[index] > 5){
		/*....*/
	}
	for (int i = 0;i < index;i++){
		if (p[index] &gt; 3){/*....*/}
	}
}
then I want to generate test cases for the function my_test.
Although this code has bug that it does not limit the value of index,on the basis of not changing the source code, I want to automatically generate a driver template (main.c) like that:
#include "test.c"
int main(){
	int b[2];
	int index,b1,b0;
	klee_make_symbolic(&amp;index,sizeof(index),"index");
	klee_make_symbolic(&amp;b1,sizeof(b1),"b1");
	klee_make_symbolic(&amp;b0,sizeof(b0),"b0");
	b[0] = b0;
	b[1] = b1;
	int *p = b;
	my_test(p,index);
}
then I will compile main.c and test.c into xxx.bc, and use klee to do symbolic execution.
If I can change the origin source code,I may do that as you suggested:
if (index &gt;= 0 &amp;&amp; index < 2){
	if (p[index] &gt; 5){
		/*....*/
	}
	for (int i = 0;i < index;i++){
		if (p[index] &gt; 3){/*....*/}
	}
}
or I can also change the driver template (main.c) that:
add code : klee_assume(index &gt;= 0 &amp;&amp; index < 2);
insert this code after klee_make_symbolic also limit the index.
But in reality, I cannot do that because the source code test.c cannot be changed and the conditions in klee_assume that "index < 2" cannot be known before symbolic execution. The number "2" can be anything if the source code changed.
So I want to change some code in klee where it handles the getelementptr instruction and memory allocation,which can help me automatically avoid the "out of bound pointer" error when processing getelementptr instruction. Let the symbolic variable "index" be smaller than a constant if it appears in the offset of a pointer or array.
I have solved the issue with array because I can get the size of array when handling the gep instruction(in Executor.cpp):
for (gep_type_iterator ii = ib;ii != ie;++ii){
	if (isa<ArrayType&gt;(*ii)){
		const auto *sq = cast<ArrayType&gt;(*ii);
		unsigned int array_len = sq-&gt;getNumElements();
	}
}
After getting the array_len, I add constraint that : ref<Expr&gt; res = SleExpr::create(index_expr, ConstantExpr::alloc(array_len, Context::get().getPointerWidth()));
then the symbolic variable index will not be larger than the array_len. Is this right?
but when I handle the pointerType,I cannot get the length of the pointer (not the size of the int*) if it has been allocated by an array. The pointerType class does not store the information
Take the above as an example, pointer *p is assigned b,the length of the pointer is "2",then automatically add constraint : create a SleExpr (index, 2).
If I do not get the pointer size ,use a constant "2" that when symbolic variable appears in the offset of pointer,add constraint to let it smaller than "2".Does this work?
I hope you can understand what I mean. thanks for your help!!


Best
tao.zhang





im
1527733628 at qq.com



&nbsp;




------------------ 原始邮件 ------------------
发件人:                                                                                                                        "Daniel Schemmel"                                                                                    <d.schemmel at imperial.ac.uk&gt;;
发送时间:&nbsp;2024年7月3日(星期三) 晚上6:54
收件人:&nbsp;"klee-dev"<klee-dev at imperial.ac.uk&gt;;

主题:&nbsp;Re: [klee-dev] symbolic variable appears in the offset of a pointer or an array



Hello,

if you wish to only execute a piece of code (such as `if (p[x] &gt; 3) { /* 
... */ }`) when a condition (such as `x &gt;= 0 &amp;&amp; x < sizeof(b) / 
sizeof(*b)`) holds, you can use an if statement like this:
```
if (x &gt;= 0 &amp;&amp; x < sizeof(b) / sizeof(*b)) {
&nbsp;&nbsp; if (p[x] &gt; 3){ /*...*/ }
&nbsp;&nbsp; if (b[x] &gt; 3){ /*...*/ }
&nbsp;&nbsp; for (int i = 0;i < x;i++){ /* p[i] ... */ }
}
```

Best,
Daniel

On 2024-07-02 03:35, im wrote:
&gt; I hope to use Klee to help me in generating test cases, and I have met 
&gt; some problems.
&gt; When the symbolic variable appears in the offset of a pointer or an 
&gt; array, such as:
&gt; int *p;
&gt; int b[3];
&gt; int x;
&gt; klee_make_symbolic(&amp;x,sizeof(x),"x");
&gt; if (p[x] &gt; 3){...}
&gt; if (b[x] &gt; 3){...}
&gt; for (int i = 0;i < x;i++){ p[i] ... }
&gt; during the symbolic execution,it always occurs error like "out of 
&gt; bound pointer",
&gt; And the value of x that solved by klee also is greater than the size 
&gt; of the pointer or array.
&gt; If the pointer is allocated memory by a sized array, such as:
&gt; p = b;
&gt; How can I make sure that the symbolic variable x is restricted from 0-2 ?
&gt;
&gt; I have an idea that when I fix with the gep instruction in 
&gt; executeInstruction(), if the offset is not a constantexpr and the 
&gt; geptype has <ArrayType&gt;, I append two constraints that x &gt;=0 and x < 
&gt; sizeof(b).So that the symbolic value x will not be out of bound.This 
&gt; can solve the problem of array,but I do not know how to fix pointer.
&gt; If the pointer is allocates memory by a sized array(int *p = b),I hope 
&gt; that the offset should be restricted from 0 to the size of the array, 
&gt; but when I fix with the gep instruction(p[x]),I cannot get the size of 
&gt; the array.I only know the pointer type and the size of the type from 
&gt; the gep instruction.How can I do it?
&gt; My English is not so good, sorry
&gt;
&gt; _______________________________________________
&gt; klee-dev mailing list
&gt; klee-dev at imperial.ac.uk
&gt; https://mailman.ic.ac.uk/mailman/listinfo/klee-dev

_______________________________________________
klee-dev mailing list
klee-dev at imperial.ac.uk
https://mailman.ic.ac.uk/mailman/listinfo/klee-dev
-------------- next part --------------
HTML attachment scrubbed and removed


More information about the klee-dev mailing list