CCF形式化方法专业委员会 > 形式化方法教育 > 形式化方法公开课
组织形式化方法相关的公开课对于国内形式化方法相关方向的人才培养和生态建设具有重要意义。2022和2023年组织了约束求解公开课,2024年的公开课聚焦定理证明及其应用。
此次公开课邀请了国内外定理证明及其应用方面的知名学者,包括法国格勒诺布尔-阿尔卑斯大学计算机科学教授Jean-François Monin、中国科学院软件研究所的施晓牧副研究员、华为编程语言实验室的詹博华博士、上海交通大学的曹钦翔副教授来进行授课。
此次公开课具体内容包括定理证明相关的基础理论、工具使用、以及在程序验证中的应用等,公开课全部使用定理证明辅助工具Coq进行教学。相比于知名的Software Foundations课程,此次公开课既对Coq理论基础进行充分的介绍,也关注互动式的演示,并注重定理证明技术在程序验证中的应用。
公开课共有60学时,分为两个阶段,每个阶段均为30学时。第一阶段聚焦定理证明背后的基础理论,时间为4月1日-4月23日,由Jean-François Monin老师进行授课。第二阶段聚焦定理证明在程序验证中的应用,时间为9月7日-11月23日,由施晓牧、詹博华、曹钦翔老师进行授课。
序号 | 时间 | 内容 | 主讲人 | 直播回放链接 |
---|---|---|---|---|
1 | 4月1日(星期一)上午9:00-12:00 |
- 课程简介 - 带类型带函数式编程:Coq和Ocaml中的函数、符号使用规范及类型 - 归纳类型:树、抽象语法树及证明树 - Coq的初步使用 |
Jean-François Monin | 观看回放 |
2 | 4月2日(星期二)上午9:00-12:00 |
- 与归纳类型相关的归纳原理 - 逻辑连接符的函数式解释 - 相等性 - 列表相关的程序 - 递归程序的正确性证明(1) |
Jean-François Monin | 观看回放 |
3 | 4月3日(星期三)上午9:00-12:00 |
- 由带变量的算数表达式构造的语法树 - 表达式的函数语义(1) - 类型上的计算(1) - 证明策略"refine" - 递归程序的正确性证明(2) |
Jean-François Monin | 观看回放 |
4 | 4月8日(星期一)上午9:00-12:00 |
- 类型上的计算(2): 依赖类型 - 强归纳 - 归纳谓词和关系以及依赖归纳类型(1) - 表达式的函数语义(2) - 名为WHILE的语言 |
Jean-François Monin | 观看回放 |
5 | 4月9日(星期二)上午9:00-12:00 |
- 相等性的传播 - 初试定义WHILE语言的函数式语义 - 归纳谓词和关系以及依赖归纳类型(2) - WHILE语言的应用:WHILE的大步操作语义(1) |
Jean-François Monin | 观看回放 |
6 | 4月10日(星期三)上午9:00-12:00 |
- 转换/约简的作用,与转换相关的证明策略 - 在归纳关系上的归纳 - 大步操作语义(2) |
Jean-François Monin | 观看回放 |
7 | 4月17日(星期三)上午9:00-12:00 |
- 多态性,高级结构化机制(e.g. classes) - 相等性的传播(2)处理"absurd"情况 - 进阶主题(1):small inversions(上) - 小步语义(或称结构操作语义) |
Jean-François Monin | 观看回放 |
8 | 4月19日(星期五)上午9:00-12:00 |
- 进阶主题(2):small inversions(下) - 一个小型的经验证的表达式的编译器 |
Jean-François Monin | 观看回放 |
9 | 4月22日(星期一)上午9:00-12:00 |
- correct-by-constructions函数式程序的提取 - 进阶主题(3):终止问题,通过Braga方法提取一般递归函数 |
Jean-François Monin | 观看回放 |
10 | 4月23日(星期二)上午9:00-12:00 |
- 进阶主题(4): 更多关于Braga方法的介绍 - 进阶主题(5):GADT简介,用于带类型/不带类型的表达式的求值 |
Jean-François Monin | 观看回放 |
Jean-François Monin,法国Verimag和格勒诺布尔-阿尔卑斯大学计算机科学教授。Monin教授曾在法国电信研究与发展部门领导一个专注于形式方法的研究小组,并成功地将其应用于工业环境中软件设备正确性属性的证明。他的研究工作致力于类型理论、交互式定理证明工具,以及在分布式算法、信息安全问题和嵌入式软件等领域的应用。除了在这些领域发表多篇研究论文外,他还出版了一本名为《Understanding Formal Methods》的书籍,涵盖了这一热门领域中各种最新方法。他曾在多个地方教授Coq、函数式编程和形式方法,包括5届亚太夏季形式方法学校(APSSFM)。
序号 | 时间 | 内容 | 主讲人 | 直播回放链接 |
---|---|---|---|---|
1 | 9月7日(星期六)上午9:00-12:00 |
- Curry-Howard同构的基础理论 - 函数与证明的关系 |
施晓牧 | 观看回放 |
2 | 9月14日(星期六)上午9:00-12:00 |
- 介绍启发式证明方法reflection - 如何编写决策过程 - 如何用reflexivity |
施晓牧 | 观看回放 |
3 | 9月21日(星期六)上午9:00-12:00 | CoqQFBV: A Scalable Certified SMT Quantifier-free Bit-Vector Solver | 施晓牧 | 观看回放 |
4 | 9月28日(星期六)上午9:00-12:00 | 函数式程序的验证(1):数组与搜索 | 詹博华 | 观看回放 |
5 | 10月19日(星期六)上午9:00-12:00 | 函数式程序的验证(2):搜索树结构 | 詹博华 |
观看回放1 观看回放2 |
6 | 10月26日(星期六)上午9:00-12:00 | 使用Coq来进行程序验证 | 曹钦翔 | 观看回放 |
7 | 11月2日(星期六)上午9:00-12:00 | Verification of Imperative Programs I: Big-step and Small-step Operational Semantics | 詹博华 | 观看回放 |
8 | 11月9日(星期六)上午9:00-12:00 | Verification of Imperative Programs II: Hoare Logic | 詹博华 | 观看回放 |
9 | 11月23日(星期六)上午9:00-12:00 | 使用Coq来进行不动点和单子相关的证明 | 曹钦翔 | 观看回放 |
施晓牧,中国科学院软件研究所计算机科学国家重点实验室可信智能系统组副研究员。法国格勒诺布尔大学博士,曾在清华大学做博士后研究工作、在深圳大学计算机与软件学院任副研究员。研究专注于定理证明器相关的形式化验证,包括密码程序验证、硬件描述语言编译过程验证、硬件模拟器的正确性等研究,其中密码验证的工具CryptoLine已成功应用于多种后量子密码程序验证上。相关研究成果发表在CAV、CCS、CHES等国际会议与期刊上。
詹博华,华为编程语言实验室技术专家。2014年博士毕业于普林斯顿大学数学系,之后在麻省理工学院和慕尼黑工业大学任博士后。2018-2024年在中科院软件所任副研究员。2024年加入华为编程语言实验室。研究工作包括证明自动化方法和交互式定理证明器的设计与实现,嵌入式系统的建模与验证,以及在程序验证、操作系统、分布式系统、量子程序验证的应用。在CAV, IJCAR/CADE, TACAS, ITP, J. Automated Reasoning等形式化方法领域的主要会议和期刊发表文章30余篇。
曹钦翔,上海交通大学长聘教轨副教授、博士生导师。2013年本科毕业于北京大学,2018年在普林斯顿大学获得博士学位,曾获上海浦江人才计划资助。曹钦翔长期从事基于定理证明的程序验证与程序逻辑研究,论文主要发表在POPL、OOPSLA、JAR等国际著名会议或期刊,其代表性工作VST、VST-A程序验证工具是目前世界范围内最知名的几个程序验证工具之一。