CBMC detected an assert error in my Pthreads program, is it correct?

user_9688676 0
Viewed 93

I use CBMC to verify my Pthreads program, it detected some assert errors which I don't think would exist. The error only occur when I run the two threads at the same time. That is to say, when I put one of the statement which calls the thread function(func or func1) into comment, CBMC can then verify it successful. Is there any conflict in the assignment of array a and b? 

int a[4], b[4];

static void * func(void * me)
{
  int i;
  for(i=0; i<2; i++){
    a[i] = b[i] = i;
    assert( a[i] == i ); //failed
  }
  return ((void *) 0);
}

static void * func1(void * me)
{
  int i;
  for(i=2; i<4; i++){
    a[i] = b[i] = i;
    assert( a[i] == i ); //failed
  } 
  return ((void *) 0);
}

int main(){
  pthread_t thr1;
  pthread_create(&thr1, NULL, func1, (void *)0);
  (*func)(0);
  pthread_join(thr1,NULL);

  return 0;
}

The output of CBMC is as following:

Violated property:
  file pthreads4.c line 25 function func1
  assertion a[i] == i
  a[(signed long int)i] == i

VERIFICATION FAILED
cbmc pthreads c
1 Answers

This looks to be a false positive on CBMC's part.

We can see that the main thread will modify a[0], a[1], b[0], and b[1].

Thread thr1 modifies a[2], a[3], b[2], and b[3].

There is actually no overlapping accesses between the the threads and so this program should behave as if it is being run sequentially.

The error trace produced by CBMC does not make much sense either:

Counterexample:

State 19 file test.c line 27 function main thread 0
----------------------------------------------------
  thr1=1ul (00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000001)

State 22 file test.c line 28 function main thread 0
----------------------------------------------------
  thread=&thr1!0@1 (00000010 00000000 00000000 00000000 00000000 00000000 00000000 00000000)

State 23 file test.c line 28 function main thread 0
----------------------------------------------------
  attr=((union pthread_attr_t { char __size[56l]; signed long int __align; } *)NULL) (00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000)

State 24 file test.c line 28 function main thread 0
----------------------------------------------------
  start_routine=func1 (00000011 00000000 00000000 00000000 00000000 00000000 00000000 00000000)

State 25 file test.c line 28 function main thread 0
----------------------------------------------------
  arg=NULL (00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000)

State 47 file test.c line 29 function main thread 0
----------------------------------------------------
  me=NULL (00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000)

State 48 file test.c line 8 function func thread 0
----------------------------------------------------
  i=0 (00000000 00000000 00000000 00000000)

State 49 file test.c line 9 function func thread 0
----------------------------------------------------
  i=0 (00000000 00000000 00000000 00000000)

State 51 file test.c line 10 function func thread 0
----------------------------------------------------
  b[0l]=0 (00000000 00000000 00000000 00000000)

State 52 file test.c line 10 function func thread 0
----------------------------------------------------
  a[0l]=0 (00000000 00000000 00000000 00000000)

State 54 file test.c line 9 function func thread 0
----------------------------------------------------
  i=1 (00000000 00000000 00000000 00000001)

State 57 file test.c line 10 function func thread 0
----------------------------------------------------
  b[1l]=1 (00000000 00000000 00000000 00000001)

State 58 file test.c line 20 function func1 thread 1
----------------------------------------------------
  b[2l]=2 (00000000 00000000 00000000 00000010)

State 59 file test.c line 20 function func1 thread 1
----------------------------------------------------
  a[2l]=2 (00000000 00000000 00000000 00000010)

State 61 file test.c line 19 function func1 thread 1
----------------------------------------------------
  i=3 (00000000 00000000 00000000 00000011)

State 64 file test.c line 10 function func thread 0
----------------------------------------------------
  a[1l]=0 (00000000 00000000 00000000 00000000)

Violated property:
  file test.c line 11 function func
  assertion a[i] == i
  a[(signed long int)i] == i


VERIFICATION FAILED

This counter example claims that a[1] == 0. However, state 64 shows 0 being assigned to a[1] even though the last written value to b[1] is 1 in state 57.

user_96142490
Related