sbv-8.7: SMT Based Verification: Symbolic Haskell theorem prover using SMT solving.

Copyright | (c) Levent Erkok
License | BSD3
Maintainer | erkokl@gmail.com
Stability | experimental
Safe Haskell | None
Language | Haskell2010

Documentation.SBV.Examples.ProofTools.BMC

Contents

- System state
- Encoding the problem
- Examples

Description

A BMC example, showing how traditional state-transition reachability problems can be coded using SBV, using bounded model checking.

We imagine a system with two integer variables, `x` and `y`. At each iteration, we can either increment `x` by `2`, or decrement `y` by `4`.

Can we reach a state where `x` and `y` are the same starting from `x=0` and `y=10`?

What if `y` starts at `11`?

Synopsis

- data S a = S {
  - x :: a
  - y :: a
  }
- problem :: Int -> (S SInteger -> SBool) -> IO (Either String (Int, [S Integer]))
- ex1 :: IO (Either String (Int, [S Integer]))
- ex2 :: IO (Either String (Int, [S Integer]))

# System state

data S a Source #

System state, containing the two integers.

Constructors

S |

Fields

- x :: a
- y :: a

#### Instances

Instances details

Functor S Source # |
Instance details Defined in Documentation.SBV.Examples.ProofTools.BMC Methods fmap :: (a -> b) -> S a -> S b (<$) :: a -> S b -> S a
Foldable S Source # |

Instance details

Defined in Documentation.SBV.Examples.ProofTools.BMC

Methods

fold :: Monoid m => S m -> m

foldMap :: Monoid m => (a -> m) -> S a -> m

foldMap' :: Monoid m => (a -> m) -> S a -> m

foldr :: (a -> b -> b) -> b -> S a -> b

foldr' :: (a -> b -> b) -> b -> S a -> b

foldl :: (b -> a -> b) -> b -> S a -> b

foldl' :: (b -> a -> b) -> b -> S a -> b

foldr1 :: (a -> a -> a) -> S a -> a

foldl1 :: (a -> a -> a) -> S a -> a

toList :: S a -> [a]

null :: S a -> Bool

length :: S a -> Int

elem :: Eq a => a -> S a -> Bool

maximum :: Ord a => S a -> a

minimum :: Ord a => S a -> a

sum :: Num a => S a -> a

product :: Num a => S a -> a

Traversable S Source # |
Instance details Defined in Documentation.SBV.Examples.ProofTools.BMC Methods traverse :: Applicative f => (a -> f b) -> S a -> f (S b) sequenceA :: Applicative f => S (f a) -> f (S a) mapM :: Monad m => (a -> m b) -> S a -> m (S b) sequence :: Monad m => S (m a) -> m (S a)
Fresh IO (S SInteger) Source # | `Fresh` instance for our state
Instance details Defined in Documentation.SBV.Examples.ProofTools.BMC Methods fresh :: QueryT IO (S SInteger) Source #
Show a => Show (S a) Source # | Show the state as a pair
Instance details Defined in Documentation.SBV.Examples.ProofTools.BMC Methods showsPrec :: Int -> S a -> ShowS show :: S a -> String showList :: [S a] -> ShowS
EqSymbolic a => EqSymbolic (S a) Source # | Symbolic equality for `S`.

Instance details

Defined in Documentation.SBV.Examples.ProofTools.BMC

Methods

(.==) :: S a -> S a -> SBool Source #

(./=) :: S a -> S a -> SBool Source #

(.===) :: S a -> S a -> SBool Source #

(./==) :: S a -> S a -> SBool Source #

distinct :: [S a] -> SBool Source #

distinctExcept :: [S a] -> [S a] -> SBool Source #

allEqual :: [S a] -> SBool Source #

sElem :: S a -> [S a] -> SBool Source #

sNotElem :: S a -> [S a] -> SBool Source #

# Encoding the problem

problem :: Int -> (S SInteger -> SBool) -> IO (Either String (Int, [S Integer])) Source #

We parameterize over the initial state for different variations.

# Examples

ex1 :: IO (Either String (Int, [S Integer])) Source #

Example 1: We start from `x=0`, `y=10`, and search up to depth `10`. We have:

    >>> ex1
    BMC: Iteration: 0
    BMC: Iteration: 1
    BMC: Iteration: 2
    BMC: Iteration: 3
    BMC: Solution found at iteration 3
    Right (3,[(0,10),(2,10),(2,6),(2,2)])

As expected, there's a solution in this case. Furthermore, since the BMC engine found a solution at depth `3`, we also know that there is no solution at depths `0`, `1`, or `2`; i.e., this is "a" shortest solution. (That is, it may not be unique, but there isn't a shorter sequence to get us to our goal.)

ex2 :: IO (Either String (Int, [S Integer])) Source #

Example 2: We start from `x=0`, `y=11`, and search up to depth `10`. We have:

    >>> ex2
    BMC: Iteration: 0
    BMC: Iteration: 1
    BMC: Iteration: 2
    BMC: Iteration: 3
    BMC: Iteration: 4
    BMC: Iteration: 5
    BMC: Iteration: 6
    BMC: Iteration: 7
    BMC: Iteration: 8
    BMC: Iteration: 9
    Left "BMC limit of 10 reached"

As expected, there's no solution in this case. While SBV (and BMC) cannot establish that there is no solution at a larger depth, you can see that this will never be the case: In each step we do not change the parity of either variable. That is, `x` will remain even, and `y` will remain odd. So, there will never be a solution at any depth. This isn't the only way to see this result of course, but the point remains that BMC is just not capable of establishing inductive facts.