Skip to content
/ theta Public

Generic, modular and configurable formal verification framework supporting various formalisms and algorithms

License

Notifications You must be signed in to change notification settings

ftsrg/theta

Repository files navigation

Theta

Build Status Build Theta with Gradle Build dockerfiles Codacy Badge Apache 2.0 License

Theta logo

About

Theta is a generic, modular and configurable model checking framework developed at the Fault Tolerant Systems Research Group of Budapest University of Technology and Economics, aiming to support the design and evaluation of abstraction refinement-based algorithms for the reachability analysis of various formalisms. The main distinguishing characteristic of Theta is its architecture that allows the definition of input formalisms with higher level language front-ends, and the combination of various abstract domains, interpreters, and strategies for abstraction and refinement. Theta can both serve as a model checking backend, and also includes ready-to-use, stand-alone tools.

Use Theta

Tools are concrete instantiations of the framework to solve a certain problem using the built-in algorithms. Currently, the following 3 tools are available. Follow the links for more information about each tool.

  • theta-cfa-cli: Reachability checking of error locations in Control Flow Automata (CFA) using CEGAR-based algorithms.
    • Gazer is an LLVM-based frontend to verify C programs using theta-cfa.
  • theta-sts-cli: Verification of safety properties in Symbolic Transition Systems (STS) using CEGAR-based algorithms.
  • theta-xta-cli: Verification of Uppaal timed automata (XTA).

Extend Theta

If you want to extend Theta and build your own algorithms and tools, then take look at doc/Development.md.

Overview of the architecture

Theta can be divided into the following four layers.

  • Formalisms: The core elements of Theta are the formalisms, which represent models of real life systems (e.g., software, hardware, protocols). Formalisms are usually low level, mathematical representations based on first order logic expressions and graph like structures. Formalisms can also support higher level languages that can be mapped to that particular formalism by a language front-end (consisting of a specific parser and possibly reductions for simplification of the model). The common features of the different formalisms reside in the core project (e.g., expressions and statements) and each formalism has its own project. Currently, there are three formalisms: symbolic transition systems (sts), control-flow automata (cfa) and timed automata (xta).
  • Analysis back-end: The analysis back-end provides the verification algorithms that can formally prove whether a model meets certain requirements. There is an interpreter for each formalism, providing a common interface towards the algorithms (e.g., calculating initial states and successors). This ensures that most components of the algorithms work for all formalisms (as long as they provide the interpreter). The verification algorithms are mostly based on abstraction. The analysis back-end defines various abstract domains (e.g., predicates, explicit values, zones), strategies for performing abstraction and refinement (e.g., interpolation), and algorithms built from these components. The common components reside in the analysis project (e.g., CEGAR loop) and the formalism-specific modules (e.g., the interpreters) are implemented in separate analysis projects (with suffix -analysis) for each formalism.
  • SMT solver interface and SMT solvers: Many components of the algorithms rely on satisfiability modulo theories (SMT) solvers. The framework provides a general SMT solver interface in the project solver that supports incremental solving, unsat cores, and the generation of binary and sequence interpolants. Currently, the interface is implemented by the Z3 SMT solver in the project solver-z3, but it can easily be extended with new solvers.
  • Tools: Tools are command line or GUI applications that can be compiled into a runnable jar file. Tools usually read some input and then instantiate and run the algorithms. Tools are implemented in separate projects.

The table below shows the architecture and the projects. Each project contains a README.md in its root directory describing its purpose in more detail.

Common CFA STS XTA
Tools cfa-cli sts-cli xta-cli
Analyses analysis cfa-analysis sts-analysis xta-analysis
Formalisms core, common cfa sts xta
SMT solvers solver, solver-z3

Read more

If you want to read more, take a look at our list of publications. A good starting point is our tool paper and slides/talk presented at FMCAD 2017.

To cite Theta, please use the following paper.

@inproceedings{theta-fmcad2017,
    author     = {T\'oth, Tam\'as and Hajdu, \'{A}kos and V\"or\"os, Andr\'as and Micskei, Zolt\'an and Majzik, Istv\'an},
    year       = {2017},
    title      = {Theta: a Framework for Abstraction Refinement-Based Model Checking},
    booktitle  = {Proceedings of the 17th Conference on Formal Methods in Computer-Aided Design},
    isbn       = {978-0-9835678-7-5},
    editor     = {Stewart, Daryl and Weissenbacher, Georg},
    pages      = {176--179},
    doi        = {10.23919/FMCAD.2017.8102257},
}

Acknowledgements

Supporters of the Theta project are listed below.