Skip to content

Latest commit

 

History

History
122 lines (100 loc) · 6.18 KB

CHANGES.md

File metadata and controls

122 lines (100 loc) · 6.18 KB
Raw

Kind 2 v1.1.0

This new version features many internal improvements as well as several new features over v1.0.1 (more than 300 commits):

  • Support for Scade 6 automata (see documentation)

  • Support for Scade 6 arrays

  • Arithmetic invariant generation: up to v1.0.1, the main invariant generation technique besides the IC3 engine was boolean template-based invariant generation. This technique can discover equalities and implications between predicates over the state variables of the system.

    The technique has been extended to arithmetic terms (int and real): Kind 2 can discover equalities and orderings (<=) between arithmetic terms mined from the input system.

    The boolean, integer and real template-based invariant generation techniques all come in two flavors: one-state which can only relate terms over the current state, and two-state which can relate terms mentioning the current and the previous state.

    Each of them runs as a differente process at runtime. By default, only the following are active:

    • INVGENOS (one-state boolean)
    • INVGEN (two-state boolean)
    • INVGENINTOS (one-state integer)
    • INVGENREALOS (one-state real)

  • Several features distinct from the actual verification process were introduced in Kind 2 v1.0.0: certification, contract generation, compilation to Rust, and test generation.

    These features are now aggregated under the term post-analyses. Most of them have been improved and v1.1.0 introduces a post-analysis: invariant logging. This feature attemps to log strengthening invariants discovered by Kind 2 as a contract.

  • Silent contract loading attempts to load contracts generated by Kind 2 during previous runs as candidate properties for the current run (see documentation)

Kind 2 v1.0.1

  • Read files on standard input in Lustre format

Kind 2 v1.0.0

This new version brings many new features and improvements over v0.8 (more than 800 commits).

NB:

  • Kind 2 now requires OCaml 4.03 or higher

New features:

  • 2-induction: makes Kind 2 react quicker to good strengthening invariants discovered by invariant generation
  • Assume/guarantee-based contract language with modes as Lustre annotations (see documentation)
    • specification-checking: before checking a node with a contract, check that the modes from the contract cover all situations allowed by the assumptions (implementation-agnostic mode exhaustiveness)
  • Compositional reasoning: --compositional (see contract semantics)
    • abstraction of subnodes by their contract
  • Modular analyses: --modular
    • Kind 2 traverses the node hierarchy bottom-up
    • applying the analysis specified by the other flags to each node
    • reusing results (invariants) from previous analyses when relevant
    • allows refinement when used with compositional reasoning
  • Compilation from Lustre to Rust: --compile
  • Mode-based test generation: --testgen
    • explores the DAG of activeable modes from the initial state up to a depth
    • generates witnesses as traces of inputs logged as XML files
    • compiles the contract as an executable oracle in Rust: reads a sequence of inputs/outputs values for the original node on stdin and prints on stdout the boolean values the different parts of the contract evaluate to
  • Generation of certificates and proofs: --proof and --certif
    • produces either SMTLIB-2 certificates or LFSC proofs
    • distributed with LFSC proof rules for k-induction
    • requires CVC4, JKind and the LFSC checker for proofs
    • generate proofs skeletons for potential holes
  • Support for forward references on nodes, types, constants and contracts
  • Output and parser for native (internal) transition system format
  • Contract generation: --contract_gen
    • Very experimental: the modes generated might not be exhaustive and the check exhaustiveness check might fail
    • This feature's main goal, for now, is to help users get started with contracts by generating a contract stub partially filled with invariants discovered by invariant generation

Improvements:

  • Flags are now organized into modules, see --help and --help_of <module>
  • Mode information (when available) to counterexample output
  • Optimized invariant generation
  • Named properties and guarantees
  • Colored output
  • No more dependencies on Camlp4
  • Strict mode to disallow unguarded pre and undefined local variables
  • Many bug fixes and performance improvements
  • Added mode information (when available) to counterexample output
  • Rewrote invariant generation from scratch: much faster now
  • Many bug and performance fixes
  • czmq fixes: there should be no process still running after Kind 2 exits

Refer to the user documentation online for more details.

Kind 2 v0.8.0

  • Optimize IC3/PDR engine, add experimental IC3 with implicit abstraction
  • Add two modular versions of the graph-based invariant generation from PKind.
  • Add path compression in k-induction
  • Support Yices 1 and 2 as SMT solvers
  • Optimize Lustre translation and internal term data structures
  • Optimize queries to SMT solvers with check-sat with assumption instead of push/pop
  • Return Lustre counterexamples faithful to input by undoing optimizations in translation
  • Improve output and logging
  • Many bug and performance fixes
  • Web service to accept jobs from remote clients

Refer to the user documentation for more details.