Re: [tlaplus] Inductive Invariants and Counterexamples in TLAPS

[Igor Konnov <igor.konnov@xxxxxxxxx>]

>  In general, if we work over only finite domains, can't all SMT problems, in theory, be reduced to plain (i.e. boolean) SAT? Not suggesting this is necessarily more efficient than using some finite encoding with an SMT solver, but I just want to clarify the theoretical hardness of the problem.

If we assume that we have no integers or use integers of fixed bit width, yes, everything could be reduced to SAT. Actually, we first tried uninterpreted functions to encode sets (basically having the membership relation as an uninterpreted function). That worked, but it was relatively slow, so we switched to the propositional encoding of set membership. However, that was in the early stages of the project. One needs a large set of experiments to draw conclusions about what is more efficient in practice.

The interesting thing about Apalache is that it supports unbounded integers as individual constants. So you are not allowed to reason about infinite subsets of Int or Nat, but you can have a bounded number of integers. This is useful when you have to reason about clocks, smart contracts, etc. In theory, we could encode fix-width integers in SAT with bit-blasting, but as far as I know, tuning these SAT encodings is quite hard in practice.


Regards,
Igor

> On 15.09.2021, at 17:08, Willy Schultz <will62794@xxxxxxxxx> wrote:
> 
> Thank you to both Stephan and Igor for the helpful replies. A few thoughts in response.
> 
> Apalache assumes that all constants have been fixed (or that they belong to a finite set that is captured with ConstInit [1]). So for fixed parameters, we can prove inductive invariants. For instance, we have checked safety of the Tendermint consensus by proving an inductive invariant [2]. It is true that invariant violations are often easier to find with Apalache. It basically expands all quantifiers in disjunctions and conjunctions, which is probably what model-based quantifier instantiation has to do anyways. For the same reason, proving inductive invariants with Apalache takes longer, as the solver cannot use the structure of the quantified formulas to easily show unsatisfiability.
>  
>  In general, if we work over only finite domains, can't all SMT problems, in theory, be reduced to plain (i.e. boolean) SAT? Not suggesting this is necessarily more efficient than using some finite encoding with an SMT solver, but I just want to clarify the theoretical hardness of the problem.
> 
> Yes, that is interesting. It would be also interesting to compare inductiveness checking when using predefined bounds on the data structures. We have recently introduced the operator `Apalache!Gen` that tells the model checker to produce data structures of bounded sizes [3], similar to generators in property-based testing. Intuitively, this is another instance of the small model hypothesis.
> 
> Yes, the "small model hypothesis" indeed seems to come into play here. It also seems to be exploited more concretely by recent tools like ic3po [1], which use Ivy as an input language but search for inductive invariants over finite domains, and then generalize them to the unbounded domain.
> 
> [1] https://link.springer.com/chapter/10.1007/978-3-030-76384-8_9
>  
> 
> -- 
> You received this message because you are subscribed to the Google Groups "tlaplus" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to tlaplus+unsubscribe@xxxxxxxxxxxxxxxx.
> To view this discussion on the web visit https://groups.google.com/d/msgid/tlaplus/b70abf32-886d-4e45-b215-2b7cf74278a8n%40googlegroups.com.

-- 
You received this message because you are subscribed to the Google Groups "tlaplus" group.
To unsubscribe from this group and stop receiving emails from it, send an email to tlaplus+unsubscribe@xxxxxxxxxxxxxxxx.
To view this discussion on the web visit https://groups.google.com/d/msgid/tlaplus/235071F9-F68F-40DF-965B-A1275B375926%40gmail.com.