基于抽象解释的线性混成系统不变式的生成方法

摘要

本发明提供一种线性混成系统不变式的生成系统，输入为线性混成系统模型——线性混成自动机，输出该线性混成系统的节点不变式；线性混成系统不变式生成系统包括转换模块和不变式生成部分两个组成部分如下：1）转换模块基于面向线性混成系统的等价迁移系统构造的模块，其输入侧为线性混成系统模型——线性混成自动机，输出侧为迁移系统模型；2）不变式生成部分，连接上述转换模块，针对上述迁移系统进行分析并根据其分析结果反馈得到线性混成系统模型的不变式；根据转换模块转换生成的迁移系统，输出为原线性混成系统的节点不变式；然后利用新工具进行不变式生成工作。

主权项

一种线性混成系统不变式的生成系统，其特征在于，输入为线性混成系统模型——线性混成自动机，输出该线性混成系统的节点不变式；线性混成系统不变式生成系统包括转换模块和不变式生成部分两个组成部分如下：1)转换模块基于面向线性混成系统的等价迁移系统构造的模块，其输入侧为线性混成系统模型——线性混成自动机，输出侧为迁移系统模型，其中：以线性混成自动机作为线性混成系统模型，表示为H＝(X,Σ,V,E,V⁰,α,β,γ)，其中：X为实数值系统变量的有限集合且X中变量的个数为混成自动机的维度，Σ为事件名的有限集合，V是位置节点的有限集合，E为位置节点之间跳转关系集合且E中的元素e代表一次跳转关系、e的形式为其中，v,v'∈V，σ∈Σ，是形为的转换卫式集合，ψ是形为x:＝c的重置动作集合；以上x,x_i(0≤i≤l)∈X，a,b,c_i(0≤i≤l)∈R，a取值‑∞，b取值∞)，V⁰为初始位置节点集合，α为第一标注函数，其将V中的每个位置映射到一个节点不变式，β为第二标注函数，其将V中的每个位置映射到一个变化率的集合，γ为第三标注函数，其将初始节点集合V⁰中的每个位置映射到一组初始条件；迁移系统模型表示为P＝(X_T,L,T,L₀,θ)，其中：X_T为系统变量，L为节点名集合，L⁰为初始节点集合，θ为初始条件集合，T为迁移关系集合；所述转换规则如下，将输入的线性混成系统模型转换为输出的迁移系统模型：系统变量X_T，其包含线性混成系统模型中所有的系统变量X并引入时间变量t，有X_T＝X∪{t}；节点名集合L，其直接决定于线性混成系统模型的位置节点集合，有L＝V；初始节点集合L⁰，其直接决定于线性混成系统模型的初始位置集合，有L⁰＝V⁰；初始条件集合θ，其初始位置到初始条件的映射函数θ满足θ(l)＝γ(v)，l为初始位置，v为位置节点；迁移关系集合T，包括由线性混成系统模型的连续变化所构造的迁移关系τ和由线性混成系统模型的离散变化e:所构造的迁移关系δ，其中：迁移关系τ表示为(l,l′,ρ)，l,l′分别代表迁移关系τ的源节点和目标节点v，ρ为迁移关系τ上的约束集合，约束集合ρ来源于位置节点v对应的节点不变式α(v)和节点变化率β(v)，有ρ＝α(v)|_X∪α(v)|_X′∪β(v)|_X,X′,t∪{t＞0,t′＞0}v∈V,X表示当前变量值，X′表示迁移后新状态的变量值，α(v)|_X表示变量当前值要满足节点不变式，α(v)|_X′表示状态迁移后的变量值要满足当前节点不变式，β(v)|_X,X′,t表示变量当前值和迁移后的变量值要满足时间变量t内的变量变化率关系；迁移关系δ表示为(v,v',ρ)，v和v′分别为迁移关系δ的源节点和目标节点，此处ρ为迁移关系δ上的约束集合，有v∈V,X表示当前变量值，X′表示迁移后新状态的变量值，表示变量当前值要满足混成自动机上离散跳转e的转换卫式，ψ|_X′表示状态迁移后的变量值要满足混成自动机上离散跳转e的重置动作，α(v)|_X表示变量当前值要满足节点不变式，α(v′)|_X′表示状态迁移后的变量值要满足当前节点不变式；2)不变式生成部分，连接上述转换模块，针对上述迁移系统进行分析并根据其分析结果反馈得到线性混成系统模型的不变式；根据转换模块转换生成的迁移系统，输出为原线性混成系统的节点不变式；其中，该不变式生成部分对已有的成熟开源工具Interproc进行修改，然后利用新工具进行不变式生成工作；不变式生成部分包括不变式生成工具修改模块和与之连接的不变式生成模块，如下述：2‑1)不变式生成工具修改模块，对已有的成熟开源工具Interproc进行修改，使之能够分析迁移系统，得到原对应混成系统的不变式；Interproc是基于抽象解释不变式生成技术和工具，它针对命令式语言Imperative language进行过程间分析；针对Interproc，主要有以下三方面修改：·数据结构：新定义的迁移数据结构type transition＝{tname:string；source:string；target:string；tinput:declaration list；toutput:declaration list；consts:block；}·迁移系统构造equation system过程：由于新增了源节点和目标节点两个数据项，迁移的流向将由下一个迁移关系的源节点是当前迁移关系的目标节点这一特征决定；首先，所有迁移关系的源节点和目标节点之间的进行匹配；如果迁移e1的目标节点和迁移e2的源节点相同，就在e1的exit point和e2的begin point之间创建一个关系恒为true的transfer，这说明e1和e2之间恒存在一个控制流向关系；如果存在多个迁移的源节点和e1的目标节点相同，则迁移流每次将从e1随机流向下一个迁移；·分析结果的提取：Interproc将program中的每一条语句结束之处都看作一个point，计算结果将输出每一个point的不变式；工作关心的是混成系统位置节点满足的不变式；混成系统到迁移系统的转换，构造了位置节点到自身的自循环迁移，也就是说所构造的迁移源节点和目标节点相同；2‑2)不变式生成模块的主体技术，是Interproc中所用基于抽象解释的分析技术。