1

This question is related to my previous question

Is it possible to get a legit range info when using a SMT constraint with Z3

So it seems that "efficiently" finding the maximum range info is not proper, given typical 32-bit vectors and so on. But on the other hand, I am thinking whether it is feasible to find certain "sub-maximum" range info, which hopefully becomes more efficient. Another thing is that we may want to have certain "safe" guarantee, say for all elements in the sub-maximum range, they must satisfy the constraint, but there could exist some other solutions that would satisfy the constraint as well.

I am currently exploring whether model counting technique could make sense in this setting. Any thoughts would be appreciated very much. Thanks.

lllllllllllll
  • 8,519
  • 9
  • 45
  • 80
  • If the bit vector is unsigned, it is trivial to extract the first k most-significant bits and apply the same range-slicing technique I proposed in the previous question. The granularity is fixed, so it can over-estimate the actual interval bounds, and even consider a two uncontiguous intervals as one bigger one. It seems that you're more interested in a safe under-approximation, in this case it might work by flipping the property around. Actually trying both ways in parallel might give the best information on the search interval. What is your model counting idea, can you elaborate on it more? – Patrick Trentin Dec 12 '18 at 18:23

1 Answers1

2

General case

This is not just a question of efficiency. Consider a problem where you have two variables a and b, and a single constraint:

a != b

What's the range of b? (maximum or otherwise?)

You can say all values are legitimate. But that would be wrong, as obviously the choice of a impacts the choice of b. The more variables you have around, the more complicated the problem will become. I don't think the problem is even well defined in this case, so searching for a solution (efficient or otherwise) doesn't make much sense.

Single variable assumption

Having said that, I think you can come up with a solution if you assume there's precisely one variable in the system. (Or, alternatively, if you fix all the other variables to some predefined constants.) If you're willing to go down this path, then you can implement a binary search algorithm to find a reasonably sized range by simply proving the quantified formula

Exists([b], And(b >= minBound, b <= maxBound, Not(constraints)))

Once you get unsat for this, you have your range. So long as you get sat, you can adjust your minBound/maxBound to search within smaller ranges. In the worst case, this can turn into a linear walk, but you can "cut-down" this search by making sure you go down a significant size in each step. That could be a parameter to the whole search, depending on how large you want your intervals to be. It'll have to be a choice between trying to find a maximal range, and how long you want to spend in this search. Of course, if you cut-down too much, you can miss a big interval, but that's the cost of efficiency.

Example1 (Good case) There's a single constraint that says b != 5. Then your search will be quick and depending on which branch you'll go, you'll either find [0, 4] or [6, 255] assuming 8-bit words.

Example2 (Bad case) There's a single constraint that says b is even. Then your search will exhibit worst-case behavior, and if your "cut-down" size is 1, you'll possibly iterate 255 times before you settle down on [0, 0]; assuming z3 gives you the maximum odd number in each call.

I hope that illustrates the point. In general, though, I'd assume you'd be closer to the "good case" for practical applications and even if your cut-down size is minimal you can most likely converge in a few iterations. Of course, this entirely depends on your problem domain, but I'd expect it to hold for software analysis in general.

alias
  • 28,120
  • 2
  • 23
  • 40