An automatic verifier for concurrent algorithms.
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
Examples
grasshopper
hsf
syntax
.gitattributes
.gitignore
.travis.yml
AST.fs
AssemblyInfo.fs
Axiom.fs
Collator.fs
Collections.fs
CollectionsTests.fs
Command.fs
CommandTests.fs
Definer.fs
Expr.fs
ExprEquiv.fs
ExprTests.fs
Flattener.fs
FlattenerTests.fs
Frontend.fs
Graph.fs
GraphTests.fs
Grapher.fs
GrapherTests.fs
Grasshopper.fs
GuardedView.fs
GuardedViewTests.fs
Guarder.fs
GuarderTests.fs
Horn.fs
HornTests.fs
INSTALL
Instantiate.fs
InstantiateTests.fs
LICENSE
Main.fs
Model.fs
Modeller.fs
ModellerTests.fs
MuZ3Backend.fs
Optimiser.fs
OptimiserTests.fs
Parser.fs
ParserTests.fs
Pretty.fs
PrettyTests.fs
README.md
Reifier.fs
ReifierTests.fs
Semantics.fs
SemanticsTests.fs
Settings.FSharpLint
Starling.sublime-syntax
Symbolic.fs
SymbolicTests.fs
TermGen.fs
TermGenTests.fs
TestStudies.fs
Traversal.fs
TraversalTests.fs
TypeSystem.fs
Utils.fs
Var.fs
View.fs
ViewDesugar.fs
Z3.fs
Z3Backend.fs
bench.sh
benchmarks.in
benchone.sh
countFails.sh
graphMethod.sh
install-hsf.sh
install-z3.sh
packages.config
regress.py
setStarling.sh
starling-gh.sh
starling-hsf.sh
starling.fsproj
starling.sh
starling.sln
test.sh
testresults
trace.sh

README.md

Starling

Build Status

Starling is an automated verification tool for concurrent programs. It accepts programs written in a C-like language and annotated with Concurrent Views Framework-style assertions, as well as a series of constraints binding those assertions to concrete facts about the program's shared state, and tries to prove soundness.

For a quick example of the flavour of Starling scripts, see Examples/Pass/ticketLock.cvf.

Current work

Starling is a work in progress, but currently it can check correctness of fully-specified programs written in a limited command language (integer and Boolean variables; arrays; basic statements; atomic assignment and compare-and-swap; parameter-less methods with no calling).

Starling can be used on its own to check complete proofs of programs using the Z3 SMT solver, or combined with other tools:

  • With the HSF Horn clause solver, Starling can perform limited definition inference for proofs, helping to complete partial proofs;
  • (Experimental.) With the GRASShopper separation logic solver, Starling can prove properties of programs using linked heap-based data structures.

Future work

  • Methods with call/return syntax;
  • Structs;
  • Proof of soundness of the tool itself;
  • Clean-up and general user interface polish.

Requirements

A F# 4.0 development environment (tested with mono on Linux), NuGet, and the native Z3 library for your platform.

NuGet should be able to restore the rest of the prerequisites.

The helper scripts mentioned below require a POSIX environment: cygwin or MSYS should work on Windows.

To use HSF, you will need a copy of qarmc. An outdated but useable version of qarmc is available. Install it in your PATH to be able to use starling-hsf.sh.

To use GRASShopper, you will need a copy of grasshopper.native. This can be compiled from source available at this GitHub repository. Install it in your PATH to be able to use starling-gh.sh.

Usage

  • To check a Starling file using Z3, use ./starling.sh -ssmt-failures /path/to/file. Examples using Z3 can be found in Examples/Pass and Examples/Fail.
  • To check a Starling file using HSF/qarmc, use ./starling-hsf.sh /path/to/file. Examples using HSF can be found in Examples/PassHSF.
  • To check a Starling file using GRASShopper, use ./starling-gh.sh /path/to/file. Examples using GRASShopper can be found in Examples/PassGH.
  • To run the regression tests, use ./regress.sh.

Editor support

A very basic major mode (highlighting only) for GNU Emacs, based on cc-mode, is available in syntax/starling-mode.el. This is fairly outdated.

People

Licence

MIT; see LICENSE.