Int domain refinement causes fixpoint error

A second program, which we believe has the same problem but terminates with a fixpoint error (which maybe makes the debugging easier), is the following:

// PARAM:  --conf ./svcomp_bitfield.json --set ana.specification ./unreach-call.prp

reach_error() {}
a(b) {
  if (!b) {
    reach_error();
    abort();
  }
}

main() {
  int c = 0;
  unsigned d;
  unsigned e = 0;
  while (5) {
    c = c + 1;
    d = d + 2;
    e = e + 3;
    a(e == c + d);
  }
}

However, the fixpoint error of the second program only occured with activated refinements and the activated bitfield domain of our PR (see #1623 ). Without our bitfield domain but still with activated refinements, the second program terminates normally without any problems. Therefore, we need a slightly different config file to produce this error:
svcomp_bitfield.json

Minimal example where it misbehaves with not finding the fixpoint (decoupled from SV-COMP). Interestingly #1674 does not fix the issue, whereas #1675 does.

// PARAM: --set ana.activated[+] abortUnless --set exp.unrolling-factor 4  --enable ana.int.interval_threshold_widening --enable ana.int.bitfield --enable ana.int.enums --enable ana.int.congruence --enable ana.int.interval --set ana.int.refinement fixpoint

int a(int b) {
  if (!b) {
    abort();
  }
}

main() {
  int c = 0;
  unsigned d;
  unsigned e = 0;
  while (1) {
    c = c + 1;
    d = d + 2;
    e = e + 3;
    a(e == c + d);
  }
}

// PARAM: --set ana.activated[+] abortUnless  --enable ana.int.interval_threshold_widening --enable ana.int.bitfield --enable ana.int.enums --enable ana.int.congruence --enable ana.int.interval --set ana.int.refinement fixpoint

int a(int b) {
  if (!b) {
    abort();
  }
}

int main(void)
{
  int c = 1;
  unsigned int d = 2;
  unsigned int e = 3;

  a(e == (unsigned int )c + d);

  c ++;
  d += 2U;
  e += 3U;


  c ++;
  d += 2U;
  e += 3U;

  while (1) {
    c ++;
    d += 2U;
    e += 3U;
    a(e == (unsigned int )c + d);
  }


  return (0);

}

Without loop unrolling.

@jerhard

With @jerhard I traced the fixpoint error and it is in fact due to a mistake in Congruences (#1587)

%%% congruence: sub : 3ℤ ℤ -> 3ℤ

The minimized program if someone wants to take a look again:

// PARAM: --enable ana.int.bitfield --enable ana.int.enums --enable ana.int.congruence --enable ana.int.interval --set ana.int.refinement fixpoint

int main(void)
{
  unsigned int c = 3;
  unsigned int d = 6;
  unsigned int e = 9;
  int burgo;

  while (1) {
    c ++;

    d += 2U;

    e += 3U;

    assert(e == (unsigned int )c + d);

    burgo = 23;
  }

  return (0);

}

Add test case for unreached fixpoint due to bug in congruences showin…

Navigation Menu

Repository navigation

Int domain refinement causes fixpoint error #1671

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Int domain refinement causes fixpoint error #1671

Description

Activity

sim642 commented on Feb 6, 2025

michael-schwarz commented on Feb 6, 2025

sim642 commented on Feb 7, 2025

michael-schwarz commented on Feb 10, 2025

michael-schwarz commented on Feb 11, 2025

michael-schwarz commented on Feb 12, 2025

michael-schwarz commented on Feb 12, 2025

michael-schwarz commented on Feb 12, 2025

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions