首页 > 其他分享 >【模型检测学习笔记】1、系统分析相关基本概念

【模型检测学习笔记】1、系统分析相关基本概念

时间:2023-01-26 12:22:29浏览次数:45  
标签:形式化 笔记 验证 定理 系统 等价 系统分析 检验 基本概念

验证方法
模拟:动态验证,常用,如今最主流的验证方法。
仿真:类似模拟,但依赖于硬件。
形式化验证:静态验证,用数学方法对模型的功能、功能、规范做检验。验证的完备性高,但实施困难。
半形式化验证:形式化验证和前面结合。
形式化验证分类
按验证内容分类
性质检验(property checking):是否满足某些规范和功能需求。
等价性验证(equivalence verification):两个设计是否是等价的。
按验证方法分类
定理证明(Theory Proving)
模型检验(model checking)
等价性验证(equivalence proving)
接下来对这三种方法详细说明。

三类形式化验证方法
1. 定理证明
使用定理证明系统(内置了各种推理规则、推理对策、元对策等),从原始设计中抽象成形式逻辑(一阶逻辑、高阶逻辑、时态逻辑)模型,在验证者引导下对公理和已证定理施加推理,最终证明出所需的目标定理。没有完全自动的定理证明。

一些定理证明系统:PVS,LCF,ACL2,HOL,isabelle,coq 。其中HOL和PVS系统是高阶逻辑证明系统。

2. 等价性检验
如给定两个电路,等价性检验就是考察在有影响的输入下其输出是否一致。如此,输入可以分为:

使输出为1的输入。
使输出为0的输入。
不管项:与输出无关的输入。
等价条件:使它们输出不同的每个输入向量,至少是其中一个电路的不管项。

一些等价性检验工具:

Candence的Affirma
Verplex的Logic Equivalence Checker
Synopsys的 Formality
Mentor Graphics的FormalPro
等价性检验途径:

符号方法:将问题形式化成为符号表示,然后用特定的问题求解方法,如BDD,SAT。适用于系统缺乏结构相似性,不能得到 系统设计的内部情况时。
增量方法:利用被检验的系统在结构上存在的相似性,逐步检验内部局部子系统的等价性,进而最终得到系统在整体上的等价性。适用于相似性比较大的系统。
3. 模型检验
针对并发系统的一种自动验证技术,系统用有限状态结构表示,被验证的性质使用时态逻辑公式表示,对状态空间进行搜索以确定被验证的性质是否是可达的。

模型检验速度比较快,且对于不满足的性质能给出反例,但缺点是存在状态爆炸问题。

模型检验分为离散系统和混成系统,对于离散系统,有:

基于Kripke结构:SMV,nuSMV,SPIN,VIS
基于时间自动机:UPPAAL
基于概率(统计):UPPAAL,Prism

标签:形式化,笔记,验证,定理,系统,等价,系统分析,检验,基本概念
From: https://www.cnblogs.com/oceaning/p/17067690.html

相关文章

  • 【个人笔记】2023年搭建基于webpack5与typescript的react项目
    写在前面由于我在另外的一些文章所讨论或分析的内容可能基于一个已经初始化好的项目,为了避免每一个文章都重复的描述如何搭建项目,我在本文会统一记录下来,今后相关的文章直......
  • 读Java8函数式编程笔记01_Lambda表达式
    1. Java8函数式编程1.1. 没有单子1.2. 没有语言层面的惰性求值1.3. 没有为不可变性提供额外支持1.4. 集合类可以拥有一些额外的方法:default方法2. 现实世界中......
  • 《RPC实战与核心原理》学习笔记Day8
    09|健康检测:这个节点挂了,为啥还要疯狂发请求?服务调用方在每次调用服务提供方的服务时,RPC框架会根据路由和负载均衡算法选择一个具体的IP地址,为了保证请求成功,我们需要确......
  • 【笔记】gitlab+openldap使用memberof筛选登录用户
    这几天在搞kerberos+nfs4没搞成之前搞了个openldap实现了分散控制集中管理(不是DCS...)gitlab和nexus也支持ldap虽然都不咋好用但是在搞gitlab的时候发现memberOf这个玩......
  • JavaScript学习笔记—Map
    Map用来存储键值对结构的数据(key-value)Map中任何类型的值都可以成为数据的key1.创建:newMap()2.属性和方法:(1)map.size()获取map中键值对的数量(2)map.set(key,val......
  • JavaScript学习笔记—使用JSON进行深复制
    constobj={name:"孙悟空",friend:{name:"猪八戒"}};//对obj进行浅复制constobj2=Object.assign({},obj);//对obj进行深复制constobj3=s......
  • JavaScript学习笔记—对象的序列化
    JS中的对象使用时都是存在于计算机的内存中序列化指将对象转换为一个可以存储的格式,在JS中对象的序列化通常是将一个对象转换为字符串(JSON字符串)序列化的用途,对象转换为......
  • 9--Websoket学习 | 青训营笔记
    这是我参与「第五届青训营」伴学笔记创作活动的第9天简介WebSocket是基于TCP/IP协议,独立于HTTP协议的通信协议。双向通讯,有状态,客户端一(多)个与服务端一(多)双向实时响......
  • JavaScript学习笔记—对象的解构
    constobj={name:"孙悟空",age:18,gender:"男"};let{name,age,gender}=obj;//声明变量同时解构变量console.log(name,age,gender);//孙悟空18男let......
  • JavaScript学习笔记—数组的解构赋值
    constarr=["孙悟空","猪八戒","沙和尚"];let[a,b,c]=arr;//解构赋值console.log(a,b,c);//孙悟空猪八戒沙和尚let[d,e,f,g]=["唐僧","白骨精",......