Analyzing Programs with Z3
Channel:Compose Conference · Length:43:30 · Published:2016-07-21 · Views:24298
Summary
Tikhon Jelvis's Compose Conference talk on using the Z3 SMT solver to analyze and verify programs, including checking invariants with bounded loops. He demonstrates verifying programs in a small language by compiling them to Z3.
Why HN recommends it
HN lists it among the practical entry points for learning Z3 and formal verification.
the best one I've found as an entry point was the approach they use in Cryptol — HN, 2017
Functional programming · Compilers, interpreters & program analysis · Logic & formal methods
Subtitles (excerpt)
all right everyone we have our last talk of the day it's T cons Elvis with some information thoughts about the z3 SMT solver all right Thank You T Khan right okay so as a few people have noticed that there's something of a SMD solver sub-theme at the conference this year and in some sense my talk is maybe one of the more introductory ones to how you could use an SMD solver and while I have some code in Haskell and it uses z3 none of the ideas are specific to either and you could use them in any language with any SMT solver but first let's again review what an SMT solver is so it all starts with the boolean satisfiability problem which is a classic np-complete problem which in practice we can solve surprisingly fast for real-world instances so there are two things that make it interesting one of which being that you know we have fast as Sat solvers and the other one is that it's actually relatively easy to encode problems in terms of sat as opposed to other np-complete problems and the way that is formulated is you have some number of boolean variables which are ANDed or and you know could be negated and the solver tells you whether there's any assignment of true and false for each variable so that the whole thing holds true so it either gives you
On Hacker News
### FV Resources These are few and far between. My paper on it is soup to nuts for how we do it in Pact which, while technical, should be somewhat approachable for most devs to grasp (I tried at least -- representing a program as equations is just an abstract concept). Until it comes out, the best one I've found as an entry point was the approach they use in Cryptol: [VIDEO] . Cryptol, generally … — buckie, 2017-07
If you want a fun example of using Z3, I gave a talk recently that walks you through verifying programs in a tiny little imperative language by compiling them to Z3 formulas. It's easier than it sounds! It was recorded [1] and I have example code and additional resources (papers, etc) on my site [2]. [1]: [VIDEO] [2]: [LINK] If you want to do more, you can extend the same process to synthesizing … — tikhonj, 2016-08
These are other good resources: - rise4fun [LINK] - [LINK] - Programming Z3 - [LINK] - Nikolaj Bjorner's tutorial [LINK] - Hakank's examples [LINK] - Yurichev's book "SMT by Example" [LINK] - [LINK] - [VIDEO] Tikhon Jelvis - Analyzing Programs with Z3 - [LINK] - Nadia Polykarpova on Z3 - SAT SMT school [LINK] - Emina Torlak's course [LINK] - Lindsey Kuper - SMT Solving and Solver-Aided Systems [L… — philzook, 2021-01
Related videos
- Emacs Rocks! Episode 14: Paredit · emacsrocks · 3:25
- Growing a Language, by Guy Steele · Bill Pugh · 53:31
- Ruby Conf 12 - Y Not- Adventures in Functional Programming by Jim Weirich · Confreaks · 53:21
- The Soul of Erlang and Elixir • Sasa Juric • GOTO 2019 · GOTO Conferences · 42:02
- "Simple Made Easy" - Rich Hickey (2011) · Strange Loop Conference · 1:01:38
- Rich Harris - Rethinking reactivity · You Gotta Love Frontend · 36:45
- "Making Impossible States Impossible" by Richard Feldman · elm-conf · 25:06
- Lexical Scanning in Go - Rob Pike · GoogleFOSSSydney · 51:17
- William Byrd on "The Most Beautiful Program Ever Written" [PWL NYC] · PapersWeLove · 1:31:05
- The Value of Values with Rich Hickey · InfoQ · 31:43
- Why Isn't Functional Programming the Norm? – Richard Feldman · Metosin · 46:09
- Maybe Not - Rich Hickey · ClojureTV · 1:03:28
- Solving Problems the Clojure Way - Rafal Dittwald · Clojure/north · 1:02:26
- Lecture 1A: Overview and Introduction to Lisp · MIT OpenCourseWare · 1:12:55
- Conway's Game Of Life in APL · Dyalog · 7:47
- Lecture 1A | MIT 6.001 Structure and Interpretation, 1986 · MIT OpenCourseWare · 1:12:55