Struct cwe_checker_lib::abstract_domain::IntervalDomain

pub struct IntervalDomain { /* private fields */ }

An abstract domain representing values in an interval range with strides and widening hints.

The interval bounds are signed integers, i.e. the domain looses precision if tasked to represent large unsigned integers. The interval has a stride, i.e. all values represented by the interval are contained in the same residue class modulo the stride as the interval bounds.

The domain also contains widening hints to faciliate fast and exact widening for simple loop counter variables. See the IntervalDomain::signed_merge_and_widen method for details on the widening strategy. Note that the widening hints may not respect the stride, i.e. they may be contained in different residue classes than the interval bounds.

Implementations

impl IntervalDomain

pub fn add(&self, rhs: &Self) -> Self

Compute the interval of possible results if one adds a value from self to a value from rhs.

pub fn sub(&self, rhs: &Self) -> Self

Compute the interval of possible results if one subtracts a value in rhs from a value in self.

pub fn signed_mul(&self, rhs: &Self) -> Self

Compute the interval of possible results if one multiplies a value in self with a value in rhs.

pub fn shift_left(&self, rhs: &Self) -> Self

Compute the resulting interval after a left shift operation. The result is only exact if the rhs interval contains exactly one value.

impl IntervalDomain

pub fn new(start: Bitvector, end: Bitvector) -> Self

Create a new interval domain with the given bounds.

Both start and end are inclusive, i.e. contained in the interval. The widening hints are set to None and the stride is set to 1 if start != end.

pub fn equal_as_value_sets(&self, other: &IntervalDomain) -> bool

Returns true if the two intervals represent the same value sets. This function ignores differences in the widening hints of the two intervals.

pub fn update_widening_lower_bound(&mut self, bound: &Option<Bitvector>)

If bound is more exact/restrictive than the current lower bound of self, set the lower bound to bound. Otherwise keep the old lower bound.

pub fn update_widening_upper_bound(&mut self, bound: &Option<Bitvector>)

If bound is more exact/restrictive than the current upper bound of self, set the upper bound to bound. Otherwise keep the old upper bound.

pub fn signed_merge(&self, other: &IntervalDomain) -> IntervalDomain

Merge as signed intervals without performing widenings.

pub fn signed_merge_and_widen(&self, other: &IntervalDomain) -> IntervalDomain

Merge as signed intervals and perform widening if necessary.

Widening Strategy

The widening delay

Each interval has a widening_delay counter, which denotes the length of the interval after the last time that widening was performed. For operations with more than one input, the widening delay is set to the maximum of the input widening delays. The only exception to this is the IntervalDomain::intersect() method, which may lower the value of the widening delay.

When to widen

If the merged interval equals one of the input intervals as value sets, do not perform widening. Else widening is performed if and only if the length of the interval is greater than the widening delay plus the stride of the interval.

How to widen

If no suitable widening bounds for widening exist, widen to the Top value. If exactly one widening bound exists, widen up to the bound, but do not perform widening in the other direction of the interval. If widening bounds for both directions exist, widen up to the bounds in both directions.

After that the widening_delay is set to the length of the resulting interval.

pub fn zero_extend(self, width: ByteSize) -> IntervalDomain

Zero-extend the values in the interval to the given width.

pub fn sign_extend(self, width: ByteSize) -> Self

Sign-extend the values in the interval to the given width.

pub fn fits_into_size(&self, size: ByteSize) -> bool

Check whether all values in the interval are representable by bitvectors of the given size. Does not check whether this is also true for the widening hints.

Trait Implementations

impl AbstractDomain for IntervalDomain

fn merge(&self, other: &IntervalDomain) -> IntervalDomain

Merge two interval domains and perform widening if necessary. See IntervalDomain::signed_merge_and_widen for the widening strategy.

fn is_top(&self) -> bool

Return true if the interval spans all possible values.

fn merge_with(&mut self, other: &Self) -> &mut Self

Returns an upper bound (with respect to the partial order on the domain) for the two inputs self and other.

impl Add for IntervalDomain

type Output = IntervalDomain

The resulting type after applying the + operator.

fn add(self, rhs: Self) -> Self

Performs the + operation.

impl Clone for IntervalDomain

fn clone(&self) -> IntervalDomain

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for IntervalDomain

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<'de> Deserialize<'de> for IntervalDomain

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl Display for IntervalDomain

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl From<ApInt> for IntervalDomain

fn from(bitvec: Bitvector) -> Self

Create an interval containing only bitvec.

impl From<Interval> for IntervalDomain

fn from(interval: Interval) -> IntervalDomain

Generate an interval domain without widening hints.

impl HasTop for IntervalDomain

fn top(&self) -> Self

Return a new interval with the same byte size as self and representing the Top value of the domain.

impl Hash for IntervalDomain

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl Neg for IntervalDomain

type Output = IntervalDomain

The resulting type after applying the - operator.

fn neg(self) -> Self

Performs the unary - operation.

impl PartialEq for IntervalDomain

fn eq(&self, other: &IntervalDomain) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl RegisterDomain for IntervalDomain

fn bin_op(&self, op: BinOpType, rhs: &Self) -> Self

Compute the result of a binary operation between two interval domains.

For binary operations that are not explicitly implemented the result is only exact if both intervals contain exactly one value.

fn un_op(&self, op: UnOpType) -> Self

Compute the result of an unary operation on the interval domain.

fn subpiece(&self, low_byte: ByteSize, size: ByteSize) -> Self

Take a sub-bitvector of the values in the interval domain.

fn cast(&self, kind: CastOpType, width: ByteSize) -> Self

Compute the result of a cast operation on the interval domain.

fn bin_op_bytesize(&self, op: BinOpType, rhs: &Self) -> ByteSize

Return the bytesize of the result of the given binary operation. Has a generic implementation that should not be overwritten!

impl Serialize for IntervalDomain

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.

impl SizedDomain for IntervalDomain

fn bytesize(&self) -> ByteSize

Return the size in bytes of the represented values.

fn new_top(bytesize: ByteSize) -> Self

Return a new Top value with the given bytesize.

impl SpecializeByConditional for IntervalDomain

fn intersect(self, other: &Self) -> Result<Self, Error>

Compute the intersection of two intervals. Return an error if the intersection is empty.

fn add_signed_less_equal_bound(self, bound: &Bitvector) -> Result<Self, Error>

Return the restriction of self to values satisfying self <= bound with self and bound interpreted as signed integers. Returns an error if no value represented by self can satisfy the comparison.

fn add_signed_greater_equal_bound( self, bound: &Bitvector ) -> Result<Self, Error>

Return the restriction of self to values satisfying self >= bound with self and bound interpreted as signed integers. Returns an error if no value represented by self can satisfy the comparison.

fn add_unsigned_less_equal_bound(self, bound: &Bitvector) -> Result<Self, Error>

Return the restriction of self to values satisfying self <= bound with self and bound interpreted as unsigned integers. Returns an error if no value represented by self can satisfy the comparison.

fn add_unsigned_greater_equal_bound( self, bound: &Bitvector ) -> Result<Self, Error>

Return the restriction of self to values satisfying self >= bound with self and bound interpreted as unsigned integers. Returns an error if no value represented by self can satisfy the comparison.

fn add_not_equal_bound(self, bound: &Bitvector) -> Result<Self, Error>

Return the restriction of self to values satisfying self != bound Returns an error if self only represents one value for which self == bound holds.

fn without_widening_hints(self) -> Self

Remove all widening hints from self. Necessary for cases where several sources have widening hints, but only one source should contribute widening hints to the result.

impl Sub for IntervalDomain

type Output = IntervalDomain

The resulting type after applying the - operator.

fn sub(self, rhs: Self) -> Self

Performs the - operation.

impl TryToBitvec for IntervalDomain

fn try_to_bitvec(&self) -> Result<Bitvector, Error>

If the domain represents an interval of length one, return the contained value.

fn try_to_offset(&self) -> Result<i64, Error>

If self represents a single absolute value, try to convert it to a signed integer and return it. Else return an error. Note that the conversion loses information about the bytesize of the value.

impl TryToInterval for IntervalDomain

fn try_to_interval(&self) -> Result<Interval, Error>

If the domain represents a bounded (i.e. not Top) interval, return it.

fn try_to_offset_interval(&self) -> Result<(i64, i64), Error>

If self represents an interval of absolute values (or can be widened to represent such an interval) then return it as an interval of signed integers of the form (start, end) if the interval is bounded. Else return an error. Note that the conversion loses information about the bytesize of the values contained in the interval.

impl Eq for IntervalDomain

impl StructuralEq for IntervalDomain

impl StructuralPartialEq for IntervalDomain