Skip to content

Change verdict on 36-apron_22-traces-write-centered-vs-meet-mutex_true

I believe the current verdict (true) for this task is incorrect.

The following program can overflow:

int g = 0;
int h = 0;
int i = 0;
pthread_mutex_t A = PTHREAD_MUTEX_INITIALIZER; // h <= g
pthread_mutex_t B = PTHREAD_MUTEX_INITIALIZER; // h == g
pthread_mutex_t C = PTHREAD_MUTEX_INITIALIZER;

void *t_fun(void *arg) {
  int x = __VERIFIER_nondet_int(); //rand
  int y = __VERIFIER_nondet_int(); //rand
  int z = __VERIFIER_nondet_int(); //rand
  if (x < 1000) { // avoid overflow
    pthread_mutex_lock(&C);
    pthread_mutex_lock(&A);
    x = g;
    y = h;
    __VERIFIER_assert(y <= x);
    pthread_mutex_lock(&B);
    __VERIFIER_assert(x == y);
    pthread_mutex_unlock(&B);
    i = x + 31;
    z = i;
    __VERIFIER_assert(z >= x);
    pthread_mutex_unlock(&A);
    pthread_mutex_unlock(&C);
  }
  return NULL;
}

int main(void) {
  int x = __VERIFIER_nondet_int(); //rand
  if (x > -1000) { // avoid underflow
    pthread_t id;
    pthread_create(&id, NULL, t_fun, NULL);

    pthread_mutex_lock(&B);
    pthread_mutex_lock(&A);
    i = 11;
    g = x;
    h = x - 17;
    pthread_mutex_unlock(&A);
    pthread_mutex_lock(&A);
    h = x;
    pthread_mutex_unlock(&A);
    pthread_mutex_unlock(&B);
    pthread_mutex_lock(&C);
    i = 3;
    pthread_mutex_unlock(&C);
  }
  return 0;
}

Consider a scheduling where the function main makes all the operations but the return and then is followed by function t_fun. Let x = 2147483620 (from main). The global variables g and h will be set to the same value. Once the function t_fun is scheduled, the other local x (from t_fun) will be set first to a nondet number, and then it will receive the value of g (2147483620). The operation on i (i = x + 31) now has an overflow, and the next assertion will be violated (z >= x).

Please find attached a counterexample generated by cseq.counterexample.xml

Merge request reports

Loading