Value analysis for high loop bounds

Question

I am analysing a control program with the following structure:

unsigned int cnt=0;
unsigned int inc=3;
...

void main(){
int i;
int lim;

for(i=0;i<100000;i++)
{
  f1();
 ....
  lim = f2();
  if(cnt < lim)
    cnt += inc;
 ....
}
}

My aim is to analyse enough loop iterations to show that the cnt variable cannot overflow. Increasing the slevel alone will not help since the state space will get too high. I saw that the slevel can be adjusted for individual functions. Is this also possible for e.g. a single if/else construct? Increasing the slevel for a whole function can be already too much for such loop structures. Is there a way to prove the absence of an overflow without writing complex loop invariants and assertions?

BR, Harald

Answer 1

I've taken the liberty of specifying that f2 returns something positive. Otherwise, the test if(cnt < lim) performs a negative -> unsigned conversion, which Value does not handle precisely at the moment. And in fact, your property does not hold if f2 returns always -1!

Under this hypothesis, cnt does not overflow.

unsigned int cnt=0;
unsigned int inc=3;

//@ assigns \result \from \nothing; ensures 0 <= \result;
int f2();

void main(){
  int i;
  int lim;

  for(i=0;i<100000;i++)
    {
      f1();
      lim = f2();      
      if(cnt < lim)
        cnt += inc;
    }
}

This is the result of the analysis. cnt has not overflown, since its maximal value is 4294967295.

[value] Values at end of function main:
  cnt ∈ [0..2147483649],0%3
  i ∈ {100000}
  lim ∈ [0..2147483647]

If f2 can return negative values <= -4, I'm not sure the result can be proven without using e.g. the WP plugin.

Regarding the rest of your question, there are various alternatives to better use the amount of slevel required for an analysis, but probably nothing that would help you here.