ARG lifter non-termination with growing exclusion sets

[michael-schwarz]

For the program

extern void abort(void);
extern void __assert_fail(const char *, const char *, unsigned int, const char *) __attribute__ ((__nothrow__ , __leaf__)) __attribute__ ((__noreturn__));
void reach_error() { __assert_fail("0", "nr2.c", 3, "reach_error"); }
extern void abort(void);
void assume_abort_if_not(int cond) {
  if(!cond) {abort();}
}
void __VERIFIER_assert(int cond) { if(!(cond)) { ERROR: {reach_error();abort();} } }
extern int __VERIFIER_nondet_int(void);

int CELLCOUNT;

int main()
{
	CELLCOUNT = __VERIFIER_nondet_int();
	if(CELLCOUNT > 1)
	{
		int DEFAULTVALUE=1;
		int MINVAL=2;
		int i;
		int j;
		int volArray[CELLCOUNT];

		if(CELLCOUNT % 2 != 0) { return 1; }

		assume_abort_if_not(CELLCOUNT % 2 == 0);

		for(i = 1; i <= CELLCOUNT/2; i++)
		{
			for(j = 2; j >= 1; j--)
			{
				if(j >= MINVAL)
				{
					volArray[i*2 - j] = j;
				}
				else
				{
					volArray[i*2 - j] = 0;
				}
			}
		}

		for(i = 0; i < CELLCOUNT; i++)
		{
			__VERIFIER_assert(volArray[i] >= MINVAL || volArray[i] == 0 );
		}
	}
	return 1;
}

with config

{
  "ana": {
    "sv-comp": {
      "enabled": true,
      "functions": true
    },
    "int": {
      "def_exc": true,
      "enums": false,
      "interval": true
    },
    "float": {
      "interval": true
    },
    "activated": [
      "base",
      "threadid",
      "threadflag",
      "threadreturn",
      "mallocWrapper",
      "mutexEvents",
      "mutex",
      "access",
      "race",
      "escape",
      "expRelation",
      "mhp",
      "assert",
      "var_eq",
      "symb_locks",
      "region",
      "thread",
      "threadJoins",
      "affeq"
    ],
    "path_sens": [
      "mutex",
      "malloc_null",
      "uninit",
      "expsplit",
      "activeSetjmp",
      "memLeak",
      "threadflag"
    ],
    "context": {
      "widen": false
    },
    "malloc": {
      "wrappers": [
        "kmalloc",
        "__kmalloc",
        "usb_alloc_urb",
        "__builtin_alloca",
        "kzalloc",

        "ldv_malloc",

        "kzalloc_node",
        "ldv_zalloc",
        "kmalloc_array",
        "kcalloc",

        "ldv_xmalloc",
        "ldv_xzalloc",
        "ldv_calloc",
        "ldv_kzalloc"
      ]
    },
    "base": {
      "arrays": {
        "domain": "partitioned"
      }
    }
  },
  "sem": {
    "unknown_function": {
      "spawn": false
    },
    "int": {
      "signed_overflow": "assume_none"
    },
    "null-pointer": {
      "dereference": "assume_none"
    }
  },
  "witness": {
    "graphml": {
      "enabled": true,
      "id": "enumerate",
      "unknown": false
    }
  },
  "pre": {
    "enabled": false
  }
}

and property unreach-call, Goblint does not seem to terminate and consumes dubious amounts of memory. If I disable the generation of graphml witnesses, it terminates without any issue.

[sim642]

When minimized, this has nothing to do with affine equalities:

int main()
{
	int CELLCOUNT;
    int i;
    int j;
    for(i = 1; i <= CELLCOUNT/2; i++)
    {
        for(j = 2; j >= 1; j--)
        {
        }
    }
	return 1;
}

{
  "ana": {
    "sv-comp": {
      "enabled": true,
      "functions": true
    }
  },
  "sem": {
    "int": {
      "signed_overflow": "assume_none"
    }
  },
  "witness": {
    "graphml": {
      "enabled": true
    }
  }
}

Tracing shows exclusion sets growing without bound, e.g.

j ->   (Not {-12, -11, -10, -9, -8, -7, -6, -5, -4, -3, -2, -1}([-31,31]))

[michael-schwarz]

As we have dropped this from the SV-COMP config, it now is only relevant for abstract debugging (or other things using ARGs).