CSB

CSB (Count and Sample on Bitvectors) is an approximate model counting and almost-uniform sampling tool aimed at solving constraints of bitvectors.

CSB uses STP as its frontend and is built on top of that. For counting it uses ApproxMC (with Arjun). For sampling, it uses UniSamp.

Build and install

For a quick install:

sudo apt-get install git cmake bison flex libboost-all-dev python2 perl build-essential
sudo apt-get install zlib1g-dev libboost-program-options-dev libboost-serialization-dev libgmp-dev
git clone https://github.com/meelgroup/csb
cd csb
git submodule init && git submodule update
./scripts/deps/setup-gtest.sh
./scripts/deps/setup-outputcheck.sh
./scripts/deps/setup-cms.sh
./scripts/deps/setup-minisat.sh
./scripts/deps/setup-unisamp.sh
mkdir build
cd build
cmake ..
cmake --build .
sudo cmake --install .

Input format

The SMT-LIB2 format is the recommended file format, because it is parsed by all modern bitvector solvers. Only quantifier-free bitvectors and arrays are implemented from the SMT-LIB2 format.

Usage as Uniform-like Sampler:

The samples should be uniform in practice. Run with an SMT-LIB2 file:

./stp -s --seed 6 myproblem.smt2

Usage as Almost-uniform Sampler:

The samples are generated with theoretical guarantees on uniformity. But this procedure might be slower than uniform-like sampler.

./stp -u --seed 6 myproblem.smt2

Change seed value to get different samples. Refer to this post to know more about uniform, almost-uniform and uniform like samplers.

Usage as Approximate Counter:

Run with an SMT-LIB2 file:

./stp -c myproblem.smt2

Python Interface for Almost-uniform Sampler:

In [1]: import stp
In [2]: a = stp.Solver()
In [3]: x = a.bitvec('x')
In [4]: y = a.bitvec('y')
In [5]: a.add(x + y < 20)
In [6]: a.add(x  > 10)
In [7]: a.add(y  > 10)
In [8]: a.useUnigen()
Out[8]: True
In [9]: a.check()
Out[9]: True
In [10]: a.model()
Out[10]: {'x': 2371135469, 'y': 1923831833}

Python Interface for Approximate Counter:

In [8]: a.useApproxMC()
Out[8]: True
In [9]: a.count()
Out[9]: 180388626432

Architecture

CSB converts bitvector constraints into SAT using STP, integrating with ApproxMC or UniSamp based on specific needs of counting or sampling. This tool is developed from a study on model counters and bitblasting tools, as detailed in this study.

Authors

• Arijit Shaw
• Kuldeep S. Meel

Please refer to STP/UniSamp/ApproxMC for the respective authors.