用 Z3 分析程序
Analyzing Programs with Z3
频道:Compose Conference · 时长:43:30 · 发布:2016-07-21 · 播放:24298
简介
Tikhon Jelvis 在 Compose 大会上的演讲,关于使用 Z3 SMT 求解器分析和验证程序,包括用有界循环检查不变量。他演示了通过将小语言编译为 Z3 来验证程序。
HN 为什么推荐
HN 将其列为学习 Z3 和形式化验证的实用入门点之一。
我找到的最好的入门点是他们在 Cryptol 中使用的方法 — HN, 2017
函数式编程 · 编译器、解释器与程序分析 · 逻辑与形式化方法
中文字幕节选
好了各位,我们今天的最后一场演讲,来自Tikhon Jelvis 带来关于Z3 SMT求解器的一些信息和思考 好的,谢谢你Tikhon 好,可能有些人已经注意到,这次会议有一个SMT求解器的副主题 在今年的会议上,某种意义上我的演讲可能是比较 入门的一个,关于如何使用SMT求解器,虽然我有一些代码是用 Haskell写的,并且使用了Z3,但这些想法都不特定于它们,你可以 在任何语言中使用任何SMT求解器,但首先让我们再回顾一下 什么是SMT求解器,一切都从布尔可满足性 问题开始,这是一个经典的NP完全问题,在实践中我们 可以出奇地快速解决现实世界的实例,所以有两件事 让它变得有趣,其中之一是我们有快速的SAT求解器, 另一个是实际上用SAT来编码问题相对容易 相比于其他NP完全问题,它的表述方式是 你有一些布尔变量,它们被AND连接,或者你知道 可以被否定,求解器告诉你是否存在任何真和假的赋值 对于每个变量,使得整个表达式为真,所以它要么给你 正确的赋值,要么告诉你它是不可满足的,或者未设置,而SMT 求解器所做的是用其他类型的变量扩展这个想法,所以我们不再 局限于布尔值,而是可以有关于数字、数组和 其他事物的约束,这里的优势是它甚至更容易 用SMT来编码有趣的东西,比用SAT更容易,在 某种意义上,你可以把SAT看作是一个更低级的版本,你必须 逐位地做所有事情,而SMT让你在更高 层次上做事,而且求解器在它们提供的变量类型上有更多领域特定的见解, 让它们更快地解决某些问题,所以不同的 理论大致对应于不同类型的变量和不同 种类的约束,你可以表达,有很多,我的意思是,我列出了 那些看起来最容易理解的,但Z3有,我不知道,30 也许更多,有很多能力,其中一个值得 特别一看的是固定大小的字,所以基本上就是机器字, 它只是一串位,Z3也知道如何做常见的 位运算,包括将它们视为数字,所以加法、乘法、 除法,对于有符号和无符号,以及你在语言中看到的 普通位运算,还有一个相当近期的 进展是,建立在位向量求解器之上,现在支持 浮点数的理论,所以你可以实际上将浮点数表示为 它实际的那组位,而不是试图用实数来近似浮点数, 现在这听起来可能有点奇怪,因为通常我们 做的是用浮点数来近似实数,但一旦我们 开始关心程序的正确性,通常实际上更容易 反方向进行,但有了这些新的浮点理论,我们 可以完全正确地建模使用浮点数的程序,我 意思是,在这个例子中我不会回到浮点数,但应该 清楚的是,如果你只是把我每次使用整数的地方替换为浮点数,并且我们 使用浮点数理论,我们可以分析依赖于 浮点数的程序,我们做那些依赖于你知道固定大小整数的,好的,所以 Z3是我正在谈论的特定SMT求解器,它往往是默认的SMT 求解器,每个人首先会去用的,通常除非他们有充分的理由,他们 可能会依赖Z3,因为它有某种卓越的声誉和
HN 上的讨论
### FV 资源 这些资源非常稀少。我关于它的论文从基础到高级详细介绍了我们在 Pact 中如何实现形式化验证,虽然技术性较强,但大多数开发者应该能大致理解(至少我尝试了——将程序表示为方程只是一个抽象概念)。在论文发表之前,我发现最好的入门点是 Cryptol 中使用的方法:[VIDEO]。总的来说,Cryptol 是一个很好的参考项目。我们不采用交互式方法。我们的方法是在文档字符串中使用 EDSL,这样你可以从链上提取合约(pact 是解释型的,所以链上的代码就是执行的代码……当然是在内联和验证之后),并自行进行验证。Pact 在模块创建/更新时进行内联,作为一种安全特性——这样,如果依赖升级,你的合约运行的代码不会改变,但依赖可以撤销你的代码访问其表/数据的权利,直到你更新合约。这就是依赖的“no leftpad”方法。然而,所有导入的纯代码仍然有效。这样,在构建模块时,你知道你… — buckie, 2017-07
如果你想看一个使用 Z3 的有趣例子,我最近做了一个演讲,通过将程序编译成 Z3 公式来验证一种小型命令式语言中的程序。这比听起来容易!演讲被录制了[1],我的网站上有示例代码和其他资源(论文等)[2]。[1]: [VIDEO] [2]: [LINK] 如果你想做更多,你可以将同样的过程扩展到合成程序,而不仅仅是验证它们。它的扩展性不太强,但否则就像魔法一样。 — tikhonj, 2016-08
这些是其他好的资源: - rise4fun [LINK] - [LINK] - Programming Z3 - [LINK] - Nikolaj Bjorner 的教程 [LINK] - Hakank 的示例 [LINK] - Yurichev 的书《SMT by Example》[LINK] - [LINK] - [VIDEO] Tikhon Jelvis - 用 Z3 分析程序 - [LINK] - Nadia Polykarpova 关于 Z3 - SAT SMT 学校 [LINK] - Emina Torlak 的课程 [LINK] - Lindsey Kuper - SMT 求解和求解器辅助系统 [LINK] - [LINK] — philzook, 2021-01
相关视频
- Emacs Rocks! 第14集:Paredit · emacsrocks · 3:25
- 培育语言,作者:Guy Steele · Bill Pugh · 53:31
- Ruby Conf 12 - Y Not- 函数式编程历险记 by Jim Weirich · Confreaks · 53:21
- Erlang和Elixir的灵魂 • Sasa Juric • GOTO 2019 · GOTO Conferences · 42:02
- “简单造就易用” - Rich Hickey (2011) · Strange Loop Conference · 1:01:38
- Rich Harris - 重新思考响应式 · You Gotta Love Frontend · 36:45
- Richard Feldman 谈“让不可能的状态不可能” · elm-conf · 25:06
- Go 中的词法扫描 - Rob Pike · GoogleFOSSSydney · 51:17
- William Byrd 谈“有史以来最美丽的程序” [PWL NYC] · PapersWeLove · 1:31:05
- Rich Hickey 谈价值的价值 · InfoQ · 31:43
- 为什么函数式编程没有成为主流?—— Richard Feldman · Metosin · 46:09
- 也许不 - Rich Hickey · ClojureTV · 1:03:28
- 用 Clojure 的方式解决问题 - Rafal Dittwald · Clojure/north · 1:02:26
- 第一讲A:Lisp概述与简介 · MIT OpenCourseWare · 1:12:55
- APL中的康威生命游戏 · Dyalog · 7:47
- 讲座 1A | MIT 6.001 计算机程序的构造和解释,1986 · MIT OpenCourseWare · 1:12:55