Skip to content

About

Implementation of HornStr, taken from the source. Adding extensions for the Formal Verification course

Resources

Stars

0 stars

Watchers

0 watching

Forks

Repository files navigation

String-Constrained Horn Clauses Solver

This tool addresses the regular language synthesis problem, for a target language (ie set of finite words) satisfying some constrained horn clauses.

The tool takes as an input an SMT2 file containing:

  • A declaration of an uninterpreted language, actually an interpreted function from words to booleans
  • A series of constrained horn clauses: each of these formula starts with a series of string variables universally quantified, followed by an implication: the premise may contain some string constrains on the variables, alongside one (or more) occurrence(s) of the uninterpreted predicate. The conclusion of the implication is either false or another occurrence of the uninterpreted predicate.

The goal is then to synthesize a suitable set of words for the uninterpreted predicate. The tool aims at the synthesis of a regular set, that is to say a language recognized by a deterministic finite automaton (DFA). Two methods are currently implemented:

  • SAT-based learning: a DFA is extracted from the model of a SAT-problem. this DFA is then checked against each clause, looking for falsifying example. If none is found, the DFA is returned. Otherwise, the counterexample is embedded back in the SAT specification.
  • L*-based learning: the check above qualifies as an equivalence query in the active learning terminology. Additionally, the L* algorithms produces membership queries. These are answered by instantiating clauses with specific values.

Example usage

  • For SAT based: python3 src/main.py models/smt2/linear/monadic/one_token_pass.smt2

  • For L*: python3 src/main.py models/smt2/linear/monadic/one_token_pass.smt2 --solver z3-noodler --method lstar

  • For SFA based: python3 src/main.py models/smt2/linear/monadic/one_token_pass.smt2 --solver ostrich --method sfa-learning

  • For local search based: python3 src/main.py models/smt2/linear/monadic/one_token_pass.smt2 --solver ostrich --method ls

  • For pcp benchmark generation where pcp_name includes 23hard, hard, instance, and pcp43: python3 src/pcp_parser.py {pcp_name}

  • More options: ./src/chc.py --help

Run Experiments

example: python experiments/run_experiments.py --problem-set models/smt2/linear/ --exp-cfg experiments/experiments_config.json --method sfa-learning --chc-solver ostrich --linear

Main dependencies

We make use of python's match/case which is not available for python versions before 3.10.

The following dependencies can be installed by pip3 install -r requirements.txt

Config

The path to different binaries and other configurations is read from the file ./config.json that is NOT in the repository as it is system dependent. However, a default example configuration is located at ./config.sample.

Tip: Create a file ./config.json with the contents of ./config.sample and adjust the values (paths) accordingly.

TEST

Tests are in the tests directory. Run them with:

pytest

or

python -m unittest discover tests

from the root directory

How to install SMT2 solver

In addition to the previous dependencies, some SMT2 solver should be installed. This solver must be available from the command line, to perform SMT2 interactive and incremental queries.

The paths to the binaries should be in ./config.json.

Z3

On Ubuntu/Debian, one can simply install the z3 package with sudo apt install z3

Ostrich

Download and install it from the github repository

CVC4

On Ubuntu/Debian, one can simply install the cvc4 package with sudo apt install cvc4

CVC5

https://github.com/cvc5/cvc5/releases/

About

Implementation of HornStr, taken from the source. Adding extensions for the Formal Verification course

Resources

Stars

0 stars

Watchers

0 watching

Forks

Releases

Packages

Contributors

Languages