# FO²-Solver

Published in ICDT 2017 and available on the Dagstuhl repository:

On the automated verification of web applications with embedded SQL.
Shachar Itzhaky, Tomer Kotek, Noam Rinetzky, Mooly Sagiv, Orr Tamir, Helmut Veith, Florian Zuleger.
International Conference on Database Theory

FO²-solver is a new finite satisfiability solver for FO², the two-variable fragment of first-order logic. FO²-solver receives as input a sentence in FO² and answers whether the sentence is satisfiable by a structure with a finite universe.

The basic principle of FO²-solver uses the bounded model property of FO². The solver computes an upper bound on the universe size of the smallest structure satisfying the input sentence, if any structure which satisfies the sentence exists. Then, the solver uses a SAT solver to search for a model up to the upper bound size. If such a model is found, the sentence is satisfiable. If no such model is found, the sentence is unsatisfiable. The algorithm that the solver uses is sound and complete. Practically, of course, the solver may timeout or run out of space. The solver employs some strategies to lower the upper bound on the universe size and improve performance. For more details, see Section 4 of arXiv:1610.02101. FO²-solver was implemented by Tomer Kotek, based on some basic infrastructure from Shachar Itzhaky‘s EPR-based Verification tool.

# The logic FO²

FO² contains all the first-order logic sentences which use only two-variables: x and y. Examples of FO² sentences are:

Φ0 = (∀ x U(x)) ∧ (∃ x ¬ U(x))
Φ1 = (∀ x ∃ y B1(x,y)) → (∃ y ∀ x B2(x,y))

Note that quantification over the same variable can be nested:

Φ2 = ∀ x ∃ y (U(x) → ∃ x B(x,y))

The sentences may use unary relation symbols (such U above) and binary relation symbols (such as B, B1, and B2 above). The sentences may not use function symbols. The equality symbol = is in the language. No other special symbols are allowed (e.g., one cannot assume to have the smaller than < relation on the universe elements). Relation symbols with arity larger than 2 cannot be used.

Additionally, constant symbols may be used. For example:

Φ3 = ∀ x ∀ y (¬(x=c) → B(c,y))
Φ4 = (c1=c2) ∧ B(c1,c2)

Here, c, c1, and c2 are constant symbols.

# Input format: SMT-LIBv2

The input format of FO²-solver is SMT-LIBv2. Here is how an smt2 file given as input to FO²-solver should be constructed.

## Declarations

`(declare-sort V 0)`

Then, the symbols in the sentence are declared.
A binary relation symbol is declared as follows:

`(declare-fun B (V V) Bool)`

A unary relation symbol is declared as follows:

`(declare-fun U (V) Bool)`

A constant symbol is declared as follows:

`(declare-const c V)`

The equality symbol does not need to be declared.

## The assert command

After the declarations are done comes the most important part of the smt2 file. Inside the assert command you may use exists, forall, and, or, =>, not, and atomic formulas.

For instance:

`(assert (exists ((x V)) (or (B x x) (exists ((y V)) (=> (B x y) (not (= x y)))))))`

## The check-sat command

Every smt2 should end with:

`(check-sat)`

The command (get-model) is ignored, but it is allowed to occur here for compatibility.

## Examples

The smt2 file of Φ0 = (∀ x U(x)) ∧ (∃ x ¬ U(x)):

```(declare-sort V 0)
(declare-fun U (V) Bool)
(assert (and (forall ((x V)) (U x)) (exists ((x V)) (not (U x)))))
(check-sat)```

The smt2 file of Φ1 = (∀ x ∃ y B1(x,y)) → (∃ y ∀ x B2(x,y)):

```(declare-sort V 0)
(declare-fun B1 (V V) Bool)
(declare-fun B2 (V V) Bool)
(assert
(=>
(forall ((x V)) (exists ((y V)) (B1 x y)))
(exists ((y V)) (forall ((x V)) (B2 x y)))))
(check-sat)```

The smt2 file of Φ2 = ∀ x ∃ y (U(x) → ∃ x B(x,y)):

```(declare-sort V 0)
(declare-fun U (V) Bool)
(declare-fun B (V V) Bool)
(assert (forall ((x V)) (exists ((y V))
(=> (U x) (exists ((x V)) (B x y))))))
(check-sat)```

The smt2 file of Φ3 = ∀ x ∀ y (¬(x=c) → B(c,y)):

```(declare-sort V 0)
(declare-const c V)
(declare-fun B (V V) Bool)
(assert (forall ((x V) (y V)) (=> (not (= x c)) (B c y))))
(check-sat)```

The smt2 file of Φ4 = (c1=c2) ∧ B(c1,c2):

```(declare-sort V 0)
(declare-const c1 V)
(declare-const c2 V)
(assert (and (not (= c1 c2)) (B c1 c2)))
(check-sat)```

## System requirements

FO²-solver is designed to work on Linux systems with equipped with Java SE 7.

## Setup

Edit the script sat_solver_caller.sh to point to a SAT solver installed on your system. Any SAT solver which follows DIMACS input/output requirements is compatible (see SAT Competition 2009 for details). FO²-solver has been tested with Glucose and Lingeling.

# Running the tool

## Commands

The basic command to run the solver is:

`\$ java -jar FO2solver-wrapper.jar filename.smt2`

If the –print-model option is used, then FO²-solver prints a satisfying model to stdout if it exists.

`\$ java -jar FO2solver-wrapper.jar filename.smt2 --print-model`

The –sat-solver-path option overrides the setting of the SAT solver path in sat_solver_caller.sh.

## Output

FO²-solver begins by testing that the SAT solver is configured properly. If the SAT solver is configured correctly, the following will be printed:

```------ Testing SAT solver ------
--------------------------------```

If there is any error message between these two lines, then the SAT solver is not configured correctly.

Next, FO²-solver will print an output of the form:

```Reading smt2 file
------------------------
Computing formula in normal form
------------------------
Max model size 200
------------------------
Searching for a model of size at most 1:
Preparing input to SAT solver
Running SAT solver
Searching for a model of size at most 2:
Preparing input to SAT solver
Running SAT solver
Searching for a model of size at most 3:
Preparing input to SAT solver
Running SAT solver
Searching for a model of size at most 12:
Preparing input to SAT solver
Running SAT solver
------------------------
SATISFIABLE by a model of size at most 12```

If the input sentence is unsatisfiable, then the last line will be

` UNSATISFIABLE`

If the –print-model option is used and the input sentence is satisfiable, a model will be printed. For example:

```--- Satisfying model ---
The universe is 0,...,11
The true atoms are as follows: (atoms which do not occur are false)
U0(5)
U1(2)
U1(1)
U1(4)
U2(6)
U2(3)
U3(0)
B(0,5)
B(1,6)
B(5,1)
B(6,0)
B(7,1)
B(8,0)
B(9,1)
A(3)
A(4)
A(2)
A(5)
A(6)
A(7)
A(10)
A(11)
A(9)```

The order of the atoms is arbitrary.
In this case, the satisfying model has universe {0,…,11}. The relations in the model are:

U0 = {5}
U1 = {1, 2, 4}
U2 = {3, 6}
U3 = {0}
A = {2, 3, 4, 5, 6, 7, 9, 10, 11}
B = {(0,5), (1,6), (5,1), (6,0), (7,1), (8,0), (9,1)}

## Benchmark

The benchmarks from Section 5 of arXiv:1610.02101 are available.

## ERC Consolidator Grant 2020 for Laura Kovacs

Laura Kovács has been awarded with an ERC Consolidator Grant 2020, for her project “ARTIST: Automated Reasoning with Theories and Induction for Software Technology”.

## Marcel Moosbrugger wins the EPILOG Distinguished Young Alumnus award

Our PhD student Marcel Moosbrugger won the EPILOG Distinguished Young Alumnus award of the TU Wien, awarding the best master thesis of master students of the Faculty of Informatics at the TU Wien in the 2020 winter semester. Congratulations!

## Pavol Cerny joins FORSYTE as full professor

We welcome Pavol Černý, who joins the FORSYTE group as a full professor of computer science in September 2019.

## 3 Forsyte papers accepted at CAV 2019

Papers co-authored by Jure Kukovec, Marijana Lazić, and Josef Widder were accepted to be presented at the 31st International Conference on Computer-Aided Verification. […]

## Deadline for Applications: Helmut Veith Stipend for Female Master´s Students in CS

Motivated female students in the field of computer science (CS) who plan to pursue (or pursue) one of the master‘s programs in Computer Science at the Vienna University of Technology – TU Wien taught in English are invited to apply for the annually awarded Helmut Veith Stipend. The Helmut Veith Stipend is dedicated to the […]