公开/公告号CN112559359A
专利类型发明专利
公开/公告日2021-03-26
原文格式PDF
申请/专利权人 华东师范大学;
申请/专利号CN202011524084.0
申请日2020-12-22
分类号G06F11/36(20060101);G06F40/151(20200101);G06F40/253(20200101);G06F40/30(20200101);
代理机构31215 上海蓝迪专利商标事务所(普通合伙);
代理人徐筱梅;张翔
地址 200241 上海市闵行区东川路500号
入库时间 2023-06-19 10:24:22
技术领域
本发明涉及计算机软件验证技术领域,尤其是一种基于S
背景技术
安全攸关系统是指系统失效将会导致人员伤亡或严重财产损失的系统软件,例如列车控制软件、核反应堆管理软件、飞行器控制软件、辐射剂量管理软件、军事目标识别软件等。对这种系统的设计不仅需要满足特定的功能性需求,还必须满足与安全相关的非功能性需求。这些需求和系统的质量息息相关,主要包括:安全性、可靠性,以及运行时间,其中系统的安全性是安全关键系统最重要的需求。
现有的验证方法中,使用“测试”来找bug,这种方法只能找到bug,不能证明程序没有bug。仿真是一种基于经验的模拟验证方法,通过反复试验试图查明缺陷,这要花相当多的时间尝试所有可能的组合,因此永远不会完整。另外,由于工程师必须定义和产生大量输进条件,他们的工作重点将是如何在非设计目标基础上分解设计。形式化验证是穷尽式数学技术,使工程师仅关注设计意图。纯形式验证技术与仿真验证相反,专注于证实模块的端到端、直接对应微架构规范的高层要求,帮助用户极大进步项目的设计和验证产能,同时确保正确性。形式化验证技术具有以下优点:
1)由于形式验证技术是借用数学上的方法将待验证系统和性质直接进行比较,因此测试者不必考虑如何获得测试向量。
2)形式验证是对指定描述的所有可能的情况进行验证,而不是仅仅对其中的一个子集进行多次试验,因此有效地克服了模拟验证的不足。
3)形式验证可以进行从系统级到入门级的验证,而且验证时间短,有利于尽早、尽快地发现和改正系统的错误,有可能缩短开发周期。
形式验证补充了模拟验证的不足,二者各有优势,互为补充,缺一不可。通过验证,可以极大的提高系统的可靠性与安全性。
Z3是由微软公司开发的一个优秀的SMT求解器(也就定理证明器),它能够检查逻辑表达式的可满足性。Z3是一个底层的工具,它最好是作为一个组件应用到其它需要求解逻辑公式的工具中。为了方便使用,Z3提供了很多的API,这些API支持的语言有C,.NET,andOCaml。当然,Z3也可以通过命令行的方式来执行。Z3是基于SMT理论构建,用于判定一阶逻辑的可满足性。由于SMT引入了语义解释,因而缩减了必须的计算空间,将可满足性问题转变为可判定性问题,因而,Z3具备较高的求解效率。
目前,有关借助Z3约束求解器来对安全自动机进行验证,判断约束是否可满足,给出需求是否满足期望系统属性的结论,尚未见有相关技术和文献的公开报道。
发明内容
本发明的目的是针对现有技术的不足而设计的一种基于S
本发明的目的是这样实现的:一种基于S
A1,读取由创建的安全自动机生成的格式文件;
A2,以字符串的形式抽取出每个状态之间的迁移条件;
A3,对每个字符串进行词法分析,分别存入词素列表中;
A4,对词素列表进行分析,将词素列表转换成为Z3约束求解器中可进行约束求解的EXPR式;
A5,将每一个EXPR存储于与迁移条件类似的数据结构中;
A6,进行状态迁移冲突和全局满足条件冲突的性质验证。
所述S
(1)S
元素(Elements)
S
其中:Z={z
(2)S
执行规则
Safety_SysML模型要求模型的执行被视为与其环境同步,在同步计算模式中,主要体现为tick事件被派发,活动状态的所有迁出迁移的触发器都被满足,其系统执行规则如下:
当Safety_SysML状态图被触发时,检查系统是否处于活动状态,输入变量是否在当前设置下,tick事件是否触发,如果tick事件不触发,那么迁移不执行。如果tick事件触发,迁移条件不满足则迁移不执行,迁移条件满足迁移执行。
如果Safety_SysML模型中只存在一个状态转换,则会触发此转换;如果有多个转换,则会触发具有最高优先级的状态转换。在同步计算模式下,状态的常规转换要在tick的一个事件周期内完成,强迁移、弱迁移和即刻迁移要符合定义的语法。
如果Safety_SysML模型中没有可以触发的转换,则Safety_SysML模型仍处于当前活动状态。
在同步计算模式下,Safety_SysML状态模型在tick被派发时,活动状态的所有迁出迁移的触发器都被满足,都处于可发生状态,但是只有优先级最高且满足卫士条件的迁移才可以发生。
所述步骤A4包括以下步骤:
B1,利用中序表达式转后序表达式算法对中序的词素列表进行分析;
B2,利用符号的出栈操作进行判断,将每一个词素列表转换成Z3约束求解器可识别的EXPR格式;
所述步骤A6包括以下两种验证方式:
C1,状态迁移冲突:对于每个状态,取出它的所有向外迁移条件,存入EXPR列表中,对该列表每次抽出两个不同的EXPR式,放入Z3的Model中进行Model Check,若满足且优先级相同,则代表有解,说明该状态产生状态迁移冲突,反之,无状态迁移冲突。
C2,全局满足条件冲突(自设定全局应满足性质):对于所有状态,取出所有迁移条件,存入EXPR列表中。对该列表每次抽出一个EXPR式,并将它与全局应满足的性质所生成的EXPR式一起放入Z3的Model中进行Model Check,若不满足,则代表无解,说明该迁移与全局应满足性质产生冲突,反之,无全局满足条件冲突。
本发明与现有技术相比具有较高的求解效率,极大的提高系统的可靠性与安全性,借助Z3约束求解器进行性质验证,为安全攸关系统的验证奠定了基础,较好的解决了SysML的状态机图不支持自动检测系统的安全性的问题,方法简便,成本低廉且安全可靠。
附图说明
图1为本发明流程示意图;
图2为实施例1生成的格式文件示意图;
图3为实施例1验证模块读取的文件的格式示意图;
图4为实施例1性质验证的界面示意图。
具体实施方式
以下结合附图和具体实施方式对本发明作进一步的详细说明。
实施例1
参阅附图1,按下述步骤对生成的数据文件进行基于S
步骤S101,读取由创建好的安全自动机生成的格式文件;
步骤S102,以字符串的形式抽取出每个状态之间的迁移条件;
步骤S103,对每个字符串进行词法分析,分别存入词素列表中;
步骤S104,对词素列表进行分析,将词素列表转换成为Z3约束求解器中可进行约束求解的EXPR式;
步骤S105,将每一个EXPR存储于与迁移条件类似的数据结构中;
步骤S106,进行性质分析。
其中,步骤S101和步骤S102所创建的安全自动机模型中的状态和迁移信息需要符合定义的Safety_SysML的语法和语义:
(1)S
元素(Elements)
S
其中:Z={z
(2)S
执行规则
Safety_SysML模型要求模型的执行被视为与其环境同步。在同步计算模式中,主要体现为tick事件被派发,活动状态的所有迁出迁移的触发器都被满足,其系统执行规则如下:
当Safety_SysML状态图被触发时,检查系统是否处于活动状态,输入变量是否在当前设置下,tick事件是否触发,如果tick事件不触发,那么迁移不执行。如果tick事件触发,迁移条件不满足则迁移不执行,迁移条件满足迁移执行。
如果Safety_SysML模型中只存在一个状态转换,则会触发此转换;如果有多个转换,则会触发具有最高优先级的状态转换。在同步计算模式下,状态的常规转换要在tick的一个事件周期内完成。强迁移、弱迁移和即刻迁移要符合定义的语法。
如果Safety_SysML模型中没有可以触发的转换,则Safety_SysML模型仍处于当前活动状态。
在同步计算模式下,Safety_SysML状态模型在tick被派发时,活动状态的所有迁出迁移的触发器都被满足,都处于可发生状态,但是只有优先级最高且满足卫士条件的迁移才可以发生。
参阅附图2~图3,步骤S101对其模型进行分析,生成数据格式文件的实现过程如下:
步骤S101-1,建好安全自动机之后,在左边工具栏选择安全自动机文件,右击选择相应的插件,单击generate按钮,生成图2所示的格式文件。
步骤S101-2,将格式文件转化成以.cvs或.txt为后缀的文件。
其中,步骤S102中以字符串的形式抽取出每个状态之间的迁移条件的实现过程如下:
步骤S102-1,读取由前面的步骤生成图3所示的安全自动机的.cvs或.txt文件。
步骤S102-2,逐行读取文件的内容,以字符串的形式存储。
其中,步骤S103中对每个字符串进行词法分析,分别存入词素列表中的实现方式如下:
步骤S103-1,根据数字、字母和操作符的分类对上一步取出的字符串进行词法分析。
步骤S103-2,将词法分析的结果存入词素列表。
其中,步骤S104中对词素列表进行分析,将词素列表转换成为Z3约束求解器中可进行约束求解的EXPR式的实现过程如下:
步骤S104-1,表达式转后序表达式算法对中序的词素列表进行分析,该算法通过入栈出栈的操作,将转换后的表达式存入栈中。
步骤S104-2,符号的出栈操作进行判断,将每一个词素列表转换成Z3约束求解器可识别的EXPR格式。
参阅附图4,步骤S106中对建好的安全自动机进行部分性质的验证,所述验证主要包括了以下两种形式:
步骤S106-1,状态迁移冲突:对于每个状态,取出它的所有向外迁移条件,存入EXPR列表中。对该列表每次抽出两个不同的EXPR式,放入Z3的Model中进行Model Check,若满足且优先级相同,则代表有解,说明该状态产生状态迁移冲突,反之,无状态迁移冲突。
步骤S106-2,全局满足条件冲突(自设定全局应满足性质):对于所有状态,取出所有迁移条件,存入EXPR列表中。对该列表每次抽出一个EXPR式,并将它与全局应满足的性质所生成的EXPR式一起放入Z3的Model中进行Model Check,若不满足,则代表无解,说明该迁移与全局应满足性质产生冲突,反之,无全局满足条件冲突。
本发明借助Z3约束求解器对安全自动机的迁移冲突进行验证,为安全攸关系统的建模和验证奠定了一定的基础。以上只是对本发明作进一步的说明,并非用以限制本专利,凡为本发明等效实施,均应包含于本专利的权利要求范围之内。
机译: 一种基于属性的安全的云计算身份验证方法
机译: 一种用于在线银行的PIN-TAN身份验证方法,其中交易号的生成是通过用户与其银行之间的安全连接在应用程序中基于自我的授权步骤中发生的
机译: 一种基于生物数据识别的电子文档验证方法和一种基于生物数据完整性的电子签名方法,该方法将电子文档的原始文本与标记,验证码和标记一起使用,并以此为目的进行验证,验证,确认服务器和计算机