Re: Efficient interval representation
- From: "Alf P. Steinbach" <alfps@xxxxxxxx>
- Date: Fri, 31 Aug 2007 10:45:08 +0200
* Tim Frink:
Hi,
I've a basic question. Let's assume I want to statically
analyze a program using abstract interpretation. I want
to represent an unsigned char variable in its abstract
form using intervals. Further, let's assume that the variable
is represented by the interval <10..255> at some point
of the program (program under analysis is a C source, so the
data type unsigned char has a bit length of 8).
When I now add a constant to that value, let's say <5..5>, I have a wrap-around. IMHO, there are not two ways how to
represent the result:
a) again <0..255>. However, here I have a loss of precision since the values <5..14> are actually not possible in the
sum
b) the result is represented by two intervals: <0..4> and <15..255>. This form fosters precision since just
feasible values are given
The first representation has the advantage that I keep the
number of intervals small (just one interval for each
variable) but loose precision so that I probably get high
overestimations the longer the analysis proceeds. On the
other hand, the second representation keeps the calculations
precise but the computation complexity increases and might
end up in a state explosion that becomes too complex to compute.
What is done in practice in such a case?
I don't understand why on Earth you'd want to do interval arithmetic analysis on integers.
But given that, and assuming arithmetic modulo 256, if you start with the interval <10..255>, and add 5, then you have the interval <15..260> which is congruent to <15..4>. You just have to keep in mind (and possibly also represent) that this is modulo 256. So on top of not understanding why you'd want to do this, I don't understand the technical problem either: I see no technical problem whatsoever, unless you have as a requirement to not be able to represent the intervals you want to represent, in which case the situation would be hopeless.
One idea to handle this trade-off between complexity and precision
that comes into my mind might be to define the number of maximal intervals for each variable (if further intervals are required they must be somehow merged with the present results to not exceed the
max. #intervals).
I don't see the /problem/.
Cheers, & hth.,
- Alf
--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?
.
- References:
- Efficient interval representation
- From: Tim Frink
- Efficient interval representation
- Prev by Date: Efficient interval representation
- Next by Date: Re: Any progress yet? (was Re: Fast pi program?)
- Previous by thread: Efficient interval representation
- Next by thread: Re: Efficient interval representation
- Index(es):
Relevant Pages
|
|
