没有合适的资源?快使用搜索试试~ 我知道了~
理论计算机科学电子笔记144(2006)125-145www.elsevier.com/locate/entcs自优化系统的基于模型的验证框架1Y. 赵S. O berthuérM. 卡多斯足球俱乐部拉米希Heinz Nixdorf研究所,帕德博恩大学,帕德博恩,德国摘要本文描述了一种新的在线模型检测方法,并将其作为实时操作系统(RTOS)的服务。验证系统特别适用于基于组件的自优化实时系统,其中通过动态交换组件来执行自优化。验证是在(RT-UML)模型的级别上进行的。 要检查的属性由RT-OCL术语表示,其中底层的时态逻辑被限制为时间注释的ACTL或LTL公式。在线模型检查以流水线方式与待检查组件的执行交错运行。 所应用的技术是基于对的,非线性模型检查。更具体地说,对于ACTL公式,这意味着NHORNSAT问题的即时解决方案,而在LTL的情况下,应用了空性检查方法关键词:基于模型的验证,在线ACTL/LTL模型检测,自优化系统。1动机机电一体化系统是一类特殊的复杂的跨领域嵌入式系统。这种系统的设计涉及机械和电气工程以及计算机科学中日益增加的复杂性,甚至由系统异质性所强调的复杂性汽车工业)。 为了处理这种复杂性,1这项工作是在合作研究中心614 -机械工程中的自优化概念和结构-帕德博恩大学的课程中开发的,并以其名义出版,由德国研究共同体(DFG)资助。1571-0661 © 2006 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2006.02.008126Y. Zhao等人理论计算机科学电子笔记144(2006)125是以一种自反射、自适应和自优化的方式建立机电一体化系统。在合作研究中心614“机械工程中的自优化概念和结构”中,我们正在研究这种方法。主要的重点放在自我优化的应用程序与高度动态的软件组件,优化,甚至在运行时更换。此外,所考虑的应用程序在实时约束下运行(见图1)。由于这些技术系统的故障通常会造成严重后果,因此安全性和可预测性至关重要。这对验证这种复杂且高度可靠的系统提出了新的要求。对于具有动态任务集的实时系统,验收测试与兼容性是最先进的。在可重构和可依赖系统中,还必须检查组件更换后的安全性和一致性。这扩展了在线验收测试的经典领域。传统上,在实时系统中,人们试图执行尽可能多的检查活动。在动态结构的系统中,这将意味着必须检查可能在替换中使用的所有组件(例如,使用传统的模型检查)在任意上下文中是正确的,即,在最普遍的背景下。当然,这种非常一般的正确性要求将导致高度超尺寸的,从而效率低下的组件。这将与自我优化的总体目标相矛盾。因此,我们决定开发一种新的技术,用于在运行时对组件的上下文特定部分进行在线模型检查。我们将此验证作为底层RTOS的一项服务。实时限制使得有必要在(UML)模型级别执行在线模型检查,假设模型被正确实现,并假设组件的任何非上下文特定内部都已被在线验证。Fig. 1. 为例Y. Zhao等人理论计算机科学电子笔记144(2006)125127针对这一问题,本文提出了一种基于模型的运行时验证机制,该机制可以在更大程度上保证系统在线重构的安全性和一致性。让假设一个实时应用程序包含四个并行运行的组件A、B、C和D。现在,由于某些原因,比如环境的变化或其他原因,RTOS在组件 C将在tr之后的第td'个时间步长处被分量E在时间点tr+td真正完成替换之前,RTOS将请求基于模型的运行时验证服务检查系统在替换之后是否仍然保持安全性和一致性。根据来自验证服务的响应,是、否或未知,RTOS将接受或拒绝用组件E替换组件C的要求。显然,组件E替换组件C将导致系统中每个组件的环境在运行时直接改变(即,B、D和E)或间接地(即,A)。回想一下这种基于组件的系统的组合推理[15],即每个组件都在组件所依赖的环境的给定假设下被检查正确。在我们的案例研究中,由于运行时重新配置,系统中每个组件的环境可能会动态更改。这就产生了以下问题:“改变后的环境是否仍然满足所需的假设?"。为了回答这个问题,传统的模型检验方法已经不再适用:一方面,很难预测重构将如何以及何时发生;另一方面,很难在给定的时间约束内检验重构的安全性和一致性。在实践中,由于巨大的时间和空间复杂性,检查所有可能的重构情况是不现实的。据我们所知,最先进的运行时验证(第4节)也不适合我们的需要:一方面,只有线性时态逻辑公式以及断言和不变量可以通过跟踪程序执行来检查;另一方面,潜在的错误只有当它们真正发生时才能被检测到。基于上述原因,本文提出了一种基于模型的运行时验证机制作为实时操作系统的系统服务,通过该机制,我们能够在模型级对自优化系统的安全性和一致性进行在线检查,从而在错误发生之前就能预测并及时避免本文的结构如下:第2节介绍了基本概念;第3节详细介绍了我们基于模型的运行时验证框架;第4节讨论了相关工作;最后,第5节结束了结论。128Y. Zhao等人理论计算机科学电子笔记144(2006)1252预赛2.1实时UML状态图根据协同研究中心614提出的设计技术[14],自优化系统是基于UML 2.0的建模概念,使用CASE工具Fujaba2也就是说,系统的体系结构由组件图以及端口和连接器的定义来指定;系统的整体行为由具有实时扩展的UML状态机来指定,称为实时UML状态图,与每个组件相关联。事实上,组件C的整个行为就是实时UML状态图的并行组合r(1≤i≤m),它们是相应协议与C的端口Pi(1≤i≤m)相关联的状态机,以及内部C的同步状态图Ms,即,MC=MrMr···MrMs。它1 2m很容易推断出系统模型的整体行为是并行的一组实时UML状态图的组成就实时UML状态图而言,在文献中有许多在这里,我们介绍了[13]中提出的实时UML状态图。简单地说,实时UML状态图是通过向通常的UML状态图添加实时注释(经过一些简化)来获得的。的除了时间约束,实时UML状态图中的初始状态、历史状态、简单状态、复合状态(顺序状态和并发状态)和最终状态以及转换与通常UML状态图中的对应物具有类似的含义。另外像在时间自动机中,实时UML状态图中的转换可能是紧急的(非紧急的),并具有优先级(整数)。 请注意,非紧急转换与优先级为0的转换相同。在某种意义上,实时UML状态图可以看作是分层时间自动机的一个变体不失一般性,图2说明了实时UML状态图的一个典型部分。状态S1具有时间不变量t0≤5(时间单位),S2具有时间不变量t0≤20和t1≤13,其中t0和 t1是全局时钟。 S1的进入动作entryS1 ()具有最坏情况执行时间(wcet)w=1(时间单位),并且当进入S1时时钟t0被重置,doS1的活动doS1()有w= 2,周期p∈[2,3],S1的退出活动exitS1()有w= 1。类似地,时钟t0和t1在退出S2时被复位。每当事件e发生时,从S1到S2的转换被触发。可用,并且保持保护x≤2和时间保护1≤t0。在2http://wwwcs.upb.de/cs/fujaba/M我Y. Zhao等人理论计算机科学电子笔记144(2006)125129平均时间,时钟t2被复位,并且执行w在时间间隔[1,10]内,并且每当时钟t1∈[3,6]时,必须完成转换的触发。默认情况下,转换是紧急的,优先级为1。图二. 部分实时UML状态图2.2实时OCLReal-time OCL(RT-OCL)[12]是一种面向状态的时态扩展,通过在实时UML状态图的活动状态配置序列上引入额外的有界时态逻辑运算符来扩展通常的对象约束语言。例如,在一个示例中,下面的不变量要求对于类C的每个实例,在接下来的20个时间单元的每个时间点,在所有可能的执行路径上,必须随后进入状态S1和S2上下文C投资者:self@ post [1 , 20] →forall ( p : OclPath|p→includes(Sequence{S1,S2}))引入的符号符合OCL 2.0的语法建议和映射到实时CTL(RTCTL)[11],一个离散时间变量,蚂蚁的计算树逻辑,为进一步应用到模型检查。在未来,我们2.3抽象状态机语言抽象状态机语言(AsmL)[17,18]是一种建立在抽象状态机(ASM)[4,16]理论基础上的可执行规范语言,这是一种用于高级建模和规范的形式化方法,已在各种应用领域证明了其强大的建模和规范能力。AsmL的主要优势在于其丰富而富有表现力的语法,正式由ASM理论支持,它使用户能够3http://www.eecs.umich.edu/gasm/130Y. Zhao等人理论计算机科学电子笔记144(2006)125在任何所需的抽象水平上创建精确和可理解的规范。除此之外,AsmL提供了一个强大的类型系统,可以促进从算法的纯数学规范到复杂的面向对象软件规范的广泛设计。类型系统包含基本的原始类型,面向对象的结构,如类,结构,接口和数学结构,如元组,集合,包,序列和映射。此外,它还支持类型一般化和所谓的约束类型。除了这些语言功能外,AsmL还提供了工具支持,允许通过规范执行进行常规验证以及增强的基于模型的测试。此外,AsmL工具套件提供了一个驱动模型状态空间探索的功能。这个特征可以用于从给定的规范中构造相应的Kripke结构,该结构可以进一步作为模型检查算法应用的基础[21]。3基于模型的验证框架3.1概述请注意,我们的运行时验证服务(图3)工作在模型级别。也就是说,要检查的模型和属性都必须提前知道。为此,首先,建模系统的实时UML状态图和相关的实时OCL约束以XML文档的形式从Fujaba工具套件中导出,并在翻译阶段分别翻译为相应的AsmL模型和实时ACTL/LTL公式。然 后 ,通过对AsmL模型和A C T L/ L T L模型应用探索功能,导出了每个AsmL模型的Kripke结构,并将其转化为Buuchi自动机.最后,将所得的Kripke结构和Bu?chi自动机归结为提前做好储备。每当收到来自RTOS的验证请求时(图1),验证服务将从存储器中获取相关的Kripke结构和Bu?chi自动机,然后快速触发实时模型检查。自优化操作可以使系统在运行时以多种方式重新配置。本文主要讨论一个元件被另一个元件替代的情况。显然,更换可能会直接或间接地改变系统中每个活动组件的环境另一方面,对可相互替换的组件的唯一约束是它们必须遵循兼容的协议,这意味着新组件的协议必须与旧组件的协议相同或有所改进。因此,调用运行时验证服务Y. Zhao等人理论计算机科学电子笔记144(2006)125131图三. 基于模型的运行时验证框架以确保这样的重新配置是真正安全和一致的。对于基于组件的系统,组合推理[15]是模型检查[6]固有的状态空间爆炸问题的有效解决方案。也就是说,每个组成部分在对组成部分环境的给定假设下被验证为正确根据我们的设计技术[14],每个组件所需的属性在设计阶段由开发人员在实时OCL中指定。我们在验证框架的翻译阶段将它们转换为断言、不变量、ACTL或LTL公式,并带有实时注释。注意,这里的断言(不变量)表示这些命题应该在某个时间和地点(在任何时间和地点)被持有的平凡属性。带时间注释的ACTL 公式只是RTCTL(实时计算树逻辑)[11],只允许使用通用量化器。 带时间注释的LTL以类似的方式定义。的是,形式为[a,b]的时间间隔,其中a和b是s,且a≤b,是附加到通常的时间运营商,因此,命名为有界时间运营商。例如,在一个示例中, 公式AG(p→AF[0,t]q)说明p总是在t个时间步长内导致q。然而,为了避免由可能性算子引起的公平性条件,我们要求可能性算子必须是有界的。通过这种方式,可能性运算符的界限防止了无限延迟。 实时ACTL(LTL)公式只是要检查的属性的中间表示。最后,将这些形式转化为Buchi自动机,132Y. Zhao等人理论计算机科学电子笔记144(2006)125单位延迟状态转移图实际上,从AsmL模型导出的Kripke结构也被表示为单位延迟状态转移图。当然,系统中每个组件的实现都必须符合组件的相应模型。这是通过使用Fujaba直接从设计模型生成代码自动实现的。因此,组件的实现是组件模型的细化,或者换句话说,模型是相应实现的抽象。这意味着ACTL(LTL)公式在模型级别为真意味着它在实现中也为真在模型级别为假并不意味着它也是假的在执行层面。也就是说,我们的运行时验证是保守的,因为它应用于模型级别。然而,预测和避免错误的好处是由于它被应用到模型级。3.2流水线工作原理很容易看出,时间约束是我们基于模型的运行时验证的主要障碍。为了跨越这一障碍,我们采用了流水线技术,以获得更多的执行时间进行验证。图4的序列图说明了验证服务和实时应用程序之间的协作。更准确地说,流水线工作模式是在RTOS和验证服务之间完成的,因此对应用程序是透明的。每当RTOS收到应用程序的组件替换请求时,它将调用验证服务来检查替换是否合法。在我们的例子中,答案必须在所需的时间约束内给出,比如td。如果幸运的话,验证可能会在时间限制结束之前完成检查任务。不幸的是,对于更复杂的系统,情况可能并非如此。因此,很可能在td个时间单位内,仅检查从初始状态开始的接下来的t1个是,这意味着替换在接下来的t1个时间步之前是安全的。在这种情况下,RTOS确实允许应用程序进行替换并向前执行t1个时间步长。 在此期间,核查工作继续进行。为了检查,假设接下来的t2-t1时间步长。因此,应用程序可以继续下一个t2-t1时间步长。注意,在每个时间点td+ti(i1)(相对于tr),应用程序可以报告其当前状态,我说:“那就去验证吧。基于该运行时信息,验证可以在系统模型中定位关于si的对应状态,从而避免通过仅检查从si映射的该特定状态可到达的足够的子空间来检查系统模型的整个状态空间。通过这种方式,可以在更大程度上减少验证的计算量。Y. Zhao等人理论计算机科学电子笔记144(2006)125133见图4。 流水线工作原理重复上述过程如果在某个时间点检测到错误,则可以通过对RTOS的回答“否”否则,我们将继续这一进程。在某个时间点,比如td+tj(相对于tr),虽然检查结果是肯定的,但是,如果时间间隔tj+1−tj不大于预定义的时间常数tc,它表示验证必须提前的最小时间步长应用程序,那么我们必须放弃验证过程并向RTOS报告未知。请注意,这两种情况只意味着错误可能在未来发生,因为我们不知道错误是否是虚假的。为了避免错误真的发生,我们不得不保守地选择拒绝替换请求。也就是说,RTOS将在必要时引发异常以及反例。至于应用程序将如何响应异常,这超出了本文的范围。最后,如果成功地检查了覆盖实时应用程序的实际运行的足够的子空间,那么我们可以向RTOS报告明确的是,并终止验证过程。从现在开始,应用程序可以保证在替换后安全一致地执行。当然,为了使我们基于模型的运行时验证技术适用,需要一些先决条件:1) 在设计阶段,应检查组件在其所依赖的环境的给定假设下的正确性;2) 每个组件的实现都符合相应134Y. Zhao等人理论计算机科学电子笔记144(2006)125KK设计模型;3) 要检查的属性以及断言和不变量仅限于带时间注释的ACTL和LTL公式;4) 验证的处理速度快于申请的处理速度请注意,我们隐含地假设所考虑的组件拥有有限状态机。事实上,图4只是说明了应用程序和验证之间通过RTOS作为中介的理想流水线合作,而不考虑任何实现细节。3.3模型检测方法很容易看出,验证服务和实时应用程序之间的流水线工作原理要求模型检查必须以自顶向下的图5直观地演示了如何在我们的基于模型的运行时版本中进行在线ACTL/LTL模型检查。定义框架,其中“≤”代表ACTL模型检查的“≤"(模拟关系),“|=”(满意度关系)用于LTL模型检查。如第3.2节所述,从初始状态开始,只有接下来的t1个时间步可以在给定的td时间单位内检查是类似地,在接下来的t1个时间单元内,接下来的t2-t1个时间步长可以被检查为是。 重复此过程,直到得出明确的答案是“是”、“否”或“未知”注意,当实时模型检查运行到第(td+ti相对于TR),将通知应用的当前状态是SI。因此,模型检查可以在系统模型中定位关于si为了简单起见,我们还使用si来表示系统模型中的对应物。从现在开始,模型检查可以从系统模型中的这个si以这种方式,仅需要遍历系统模型的状态空间的一部分。不失一般性,假设实时系统模型M包含n个并行工作的组件 C1,C2,···, Cn(n2),并且在时间点 tr被请求用另一组件替换组件 Ck(1≤k≤ nJ,记为MJ= M(CJ/Ck)@(trd td)。由于并发和反应式系统中固有的非确定性,为了得到一个确定的状态,我们只能推导出一个分量Ci(i/=k)在时间点tr+td可能达到的所有可能状态。也就是说,Ci在时间点tr+td的状态不是唯一的,即,MJ可能不止一个初始状态,当运行时验证被触发时。为了方便起见,我们引入一个虚拟状态p0作为MJ的唯一初始状态.设MJ=(APM J,SM J,RM J,p0,LM J),其中AP表示一组拓扑拓扑关系S,S表示一组状态,R<$S×S表示跃迁关系,L:S→2AP表示标号CY. Zhao等人理论计算机科学电子笔记144(2006)125135KKKKKK图五. 在线ACTL/LTL模型检验方法在国家上发挥作用。在实践中,新的系统模型是在现场构建的,即,C1,C2,···,CJ,···,Cn在时间点tr+ td的并行合成由待检查的属性自动机引导。这样,在找到反例(如果有的话)之前,可能只会构造Mj的整个状态空间的一小部分。由于运行时检查断言和不变量(仅由命题组成)是微不足道的,因此在下文中,我们主要关注运行时检查带有时间注释的ACTL和LTL公式,其中可能性运算符是有界运算符(如果有的话)。3.3.1在线ACTL模型检测B是从ACTL中导出的Buüchi自动机,用于与分量Ci(1≤i≤n)和BJ计算中Buüchi自动机CJ。显然,原系统M满足B=B1<$B2<$··<$Bn。在替换之后,新的ysmMJ应保持BJ=B1<$B2<$··<$Bj<$··<$Bn。因此,我们的在线ACTL模型检查的目标是检查重构系统模型M(CJ/Ck)@(trdtd)≤B1<$B2<$··<$Bj<$··<$Bn。K K注意,属性自动机B1、B2、···、BJ、···、Bn都被预先构造并存储在存储库中。因此,我们可以通过将B1,B2,···,BJ,···,Bn在-上组合来构建Bj。类似于MJ,BJ也可以具有多于一个初始状态。为了方便起见,我们引入一个虚态q0作为Bj的唯一初始状态,并证明了BJ=(APBj,SBj,RBj,q0,LBj).为了使在线ACTL模型检查可用,我们去检查136Y. Zhao等人理论计算机科学电子笔记144(2006)125MJ和BJ之间的模拟预排序递增[23]。通过这种方法,将检验仿真预序的决策问题转化为满意决策问题。弱负Horn公式的可解性问题[22],称为NHORNSAT问题。其基本思想是对模拟关系的属性进行将MJ和BJ之间的关系转化为一类CNF(Conjunctive Normal Form)公式Γ,即,弱负的Horn公式,然后直接证明了公式Γ在多项式时间内是满足的。设Xp,q是Γ中的一个变量,其中p和q分别是MJ和BJ中的状态.那么,公式Γ中的子句具有以下三种类型:1) 正文字Xp,q,当(p,q)为模拟关系时;2) 负文字Xp,q,当(p,q)不能在任何模拟关系中时3) 形式Xp,q→p,JQJXp,JQJ的蕴涵定理,其中(p,q)为模拟关系,(pJ,qJ)中的一个也必须在模拟关系中。这里(pJ,qJ)属于(p,q)的后继。从MJ和BJ的初态出发,按BFS(广度优先搜索)顺序,逐层地把由MJ×BJ幸运的是,在[2]中提出了一个有效的On-the-Money算法,该算法每次接收一个Horn子句,并允许对迄今为止收到的整个公式的满足性进行快速查询。设l为插入子句的大小,n为到目前为止接收到的整个公式的大小。然后,算法在O(1)的摊销时间内插入一个大小为l的子句,在O(n)的时间内将插入操作的结果传播到前一个结果上,并在O(1)的时间内判定此前构造的公式的满足性。这比[8]和[20]中相同问题的最佳已知算法的性能高出一个数量级。类似地,[2]中的算法的对偶化也给出了NHORNSAT问题的有效线性时间在线解[23]。然而,为了使这种基于实时操作系统的算法能够以流水线的方式与实时应用程序无缝地协作,我们需要做一些扩展。Gi ve表示p,PJ和q,其中p,PJ∈SMj,(p,PJ)∈RMj,q∈SBj. 根据模拟关系的定义,若(p,q)在模拟关系中,则对任意一个变迁(p,PJ)∈RMj,都不存在变迁(q,QJ)∈RBJ 如果(p,q,J)是模拟关系,则(p,q)不可能是模拟关系.下面的函数getClauses(p,pJ,q)返回一组从p,pJ和q派生的子句(文字)。getClauses(p,pJ,q)=def如果存在qJ∈nextStates(q),其中isConsistent(pJ,qJ),则JJreturn{Xp,qqJ∈nex tSta tes(q)Xp,JqJ|是一致的(p, q)}Y. Zhao等人理论计算机科学电子笔记144(2006)125137其他返回{Xp,q}endif为了跟踪getClauses(p,pJ,q)新创建的子句中的正文字,下面的函数getLiterals(p,pJ,q)返回一组这样的文字。在这里,我们引入LiteralT,它能够存储派生的文字以元组((p,pJ,q),文字)的形式从p,pJ和q中提取,以避免在p,pJ和q上的重复计算(如果有的话)。getLiterals(p,pJ,q)=def如果存在qJ∈nextStates(q),其中isConsistent(pJ,qJ),则letliterals={Xp,JqJ|qJ∈下一个States(q)∈Cconsistent(pJ,qJ)}add((p,pJ,q),literals)toLiteralT able返回文字其他add((p,pJ,q),n)toLiteralT able回线endif算法1演示了运行时ACTL模型检查的工作原理。该算法的输入参数是重建系统的模型MJ、属性自动机BJ、重建系统的时间约束td和当前状态si该算法的输出是一个表示实时系统可以安全地前进多少时间步。特别地,我们定义Yes,No和U nknown为常数s,比如Yes = 1,No = 0和U nknown= −1。该算法中的主要数据结构被列出并解释如下:• 计时器测量到目前为止经过的时间;• oldT imes保持由上一个检查周期获得的时间步长;• newT times保持由当前检查周期获得的时间步长;• currentLiterals保存一组待处理的文字;• oldLiterals保存一组已处理的文字• newLiterals保存一组新创建的文字• oldClauses保留一组已检查的子句• newClauses保存一组新创建的子句;• ComputedTable保存元组列表(si,timeSteps,currentLiterals);• LiteralT able保存元组((p,pJ,q),literals)的列表注意,ComputedTable和LiteralT able被用来改进138Y. Zhao等人理论计算机科学电子笔记144(2006)12500算 法 的 效 率 。 ComputedTable 中 的 元 组 ( si , timeSteps ,currentLiterals)意味着从si开始,下一个timeSteps已经被检查为安全,因此,每当si再次变为当前状态时,程序可以直接从currentLiterals开 始 检 查 , currentLiterals 是 远 离 si 的 timeSteps 。 最 初 ,ComputedTable只包含tu-ple((p0,q0),0,{Xp,q}).LiteralT able中的元组((p,pJ,q),literals)表示已经生成了从p、pJ和q导出的文字,因此,每当再次遍历p、pJ和q时,程序可以直接引用先前计算的结果。最初,LiteralT able是空的。一旦接收到来自RTOS的验证请求,算法就从初始状态(p0,q0)开始工作,即,第一个当前状态s0=(p0,q0)。设在第i个时间步从(p,q)可达的所有状态(pJ,qJ关于(p,q)的第i从这个意义上说,currentLiterals保留了所有从 timeSteps 'th 导 出 的 文 字 当 前 ) 层 状 态 ( 第 6-11 行 ) 。 因 此 ,newLiterals保留了所有从下一层状态派生的文字,newClauses保留了所有新创建的子句(第15-24行)。 如果oldClauses和newClauses仍然可以满足,我们增加newT times,然后更新oldLiterals和oldClauses;否则,向RTOS返回No(第30-40行)。这个过程在while循环中重复,直到达到时序约束(第12行)或检查了从si在前一种情况下,td被分配给下一轮检查中可用的新定时约束(行42)。然而,如果这个新的td不大于预 定义 的 时间 常 数tc , 则 算法 必 须放 弃 检查 任 务并 向 RTOS 报 告 Unknown(第43-44行);否则,算法更新ComputedTable,通知RTOS应用程序可以在下一个td时间步长内安全地前进,然后继续下一轮检查(第46-49行)。在后一种情况下,算法只告诉RTOS是,因为从当前状态可到达的所有状态(即,从当前状态开始的足够的子图)已经被检查(第25-26行)。也就是说,从现在开始,实时应用程序可以永远安全地运行。算法1在线ACTL模型检测算法输入:MJ,BJ,td,si输出:开始1initialization()2N extRound:3计时器:= 04oldT imes:=newT imes5newT times:= 0Y. Zhao等人理论计算机科学电子笔记144(2006)1251396如果inComputedT able(si),则7currentLiterals:=getCurrentLiterals(ComputedT able(si))8其他9currentLiterals:={Xp,q|Xp,q∈oldLiterals<$p= si}10add(si,0,currentLiterals)到ComputedTable11endif12whiletimer≤td do13newLiterals:=014newClauses:= 015对于所有的Xp,q∈currentLiterals,16对于所有pJ∈nextStates(p),17如果inLiteralT able(p,pJ,q),则18newLiterals:=newLiteralsliterals(LiteralT able(p,pJ,q))19其他20newLiterals:=newLiteralsgetLiterals(p,pJ,q)21newClauses:=newClausesgetClauses(p,pJ,q)22endif23结束24结束25如果所有的Xp,q∈newLiterals成立Xp,q用si标记,则26return是27其他28用si标记所有Xp,q∈29endif30如果newClauses=0,则31新闻动态++32currentLiterals:=newLiterals33elseifisSatisfiable(oldClauses,newClauses) then34新闻动态++35currentLiterals:=newLiterals36oldLiterals:=oldLiterals37oldClauses:=oldClauses新子句38其他39不返回40endif41endwhile42td:=newT imes+getT imeSteps(ComputedT able(si))−oldT imes43如果td≤tc,则44return未知45其他140Y. Zhao等人理论计算机科学电子笔记144(2006)12546lettimeSteps=newT imes+getT imeSteps(ComputedT able(si))47add(si,timeSteps,currentLiterals)到ComputedTable48输出td49转到下一轮50恩迪夫恩德显然,如果检查结果不符合是负的(即,否或未知)。根据下面的定理和推论,我们还可以得出结论,如果检查结果是肯定的,则该算法保证终止。因此,该算法将在所有情况下终止。定理3.1给定系统模型M=(APM,SM,RM,s0,LM)和系统模型的无穷大解π=(s0,s1,s2,·· ·,si,· ··)。下面的命题成立:M(s0)<$M(s1)<$M(s2)<$··<$M(si)<$··其中M(si)表示M从s i开始的子图。这个证明很简单,因此这里省略了。从这个定理,我们可以很容易地得出如下推论:推论3.2如果M中存在从si到sj的循环,则M(si)= M(sj)。回想一下,ComputedTable存储了一系列当前状态以及与这些状态相关的相应检查结果。给定当前状态si,如果检查从si可到达的状态导出的文字,则此文字将标记为si(第28行)。显然,如果所有从M(si)的状态导出的文字都用si标记,则意味着整个子图M(si)都被检查过。由于M的从后续当前状态开始的子图都被M(si)覆盖,因此,该算法可以用检查结果Y es(第25-26行)来完成。在该算法中,一个子句只被添加到oldClauses一次(第17-22行)。因此,函数isSatisfiable(oldClauses,newClauses)仅在有非空的newClauses将被添加到oldClauses(第33行)时被调用。从检查完所有子句的时候起,算法将不再需要检查满足性问题,而只需遍历图从MJ和BJ逐层生成,直到保持某个终止条件。每次将newClauses添加到oldClauses时,如 前 所 述 , isSatisfiable ( oldClauses , newClauses ) 取 决 于 将newClauses插入oldClauses的时间以及将此插入操作的结果传播到先前结果的时间。 请注意,无论何时一个文字Xp,q被评估为false,这意味着(p,q)不能处于任何模拟关系中,文字是从(p,q)Y. Zhao等人理论计算机科学电子笔记144(2006)125141KK将不再由isSatisfiable(oldClauses,newClauses)处理 虽然,在我们的例子中,算法的复杂度是O(|SM J| ·|SBJ|)和clausesgene erates disO的数量(|RM J| ·|RBJ|),通过引入当前状态si,在每个检查周期中,算法只检查从si开始的子图因此,在局部视图中,每一轮的时间复杂度相对于时序约束是可接受的。因此,这种运行时ACTL模型检测在实践中是可行的3.3.2在线LTL模型检测对于非线性LTL模型检查,我们遵循空性检查技术[7]。在这样做时,对于每个分量Ci(CJ),属性自动机Bi(BJ)从要检查的LTL公式的否定导出在那里-因此,我们的在线LTL模型检查的目标是检查重组是否正确固定系统模型M(CJ/Ck)@(trDtd)$B1<$B2<$··<$BJ<$··<$Bn.的K K只要存在使M(CJ/Ck)@(trd td)|= Bi(BJ),k k k我们可以得出这样的结论:部件更换是不安全的。 通过引入伪初始状态q0,然后将q0链接到Bi(i=k)的初始状态和BJ,很容易将B1,B2,···,BJ,···,Bn组合在一起成为一个统一的K K自动机BJ表示dasBJ=(APBJ,SBJ,RBJ,q0,LBJ).因此,可以在- the-y上检查MJ和BJ也就是说,按需从初始状态(p0,q0)开始,以BFS顺序逐层计算MJ和BJ当然,我们仍然需要做一些事情,使这种空检查适合管道化的工作方式。算法2展示了运行时LTL模型检查的工作原理。该算法的输入和输出与算法1相同。该算法的大部分数据结构也与算法1相同,只是我们引入了 currentState , oldState 和 newState , 其 功 能 与 算 法 1 中 的currentLiterals,oldLiterals和newLiterals相似。一旦从RTOS接收到验证请求,算法就从当前状态s0=(p0,q0)开始工作。这里ComputedT able最初包含唯一的元组((p0,q0),0,{ ( p0 , q0 ) } ) 。 currentStates 保 留 当 前 要 处 理 的 状 态 如 果 从currentStates导出的下一层状态之前被创建,这意味着找到了循环,那么算法可以完成检查任务并向RTOS返回No(第17-18行);否则,下一层状态被添加到newStates(第20行)。 如果没有新的下一层state可以从currentStates导出,即,newStates=0,这意味着MJ和BJ的交集为空,然后,算法可以完成检查任务并将Y es通知给RTOS(第24-25行)。 否则算法递增newT倍并更新currentState和oldState142Y. Zhao等人理论计算机科学电子笔记144(2006)125(line 27-29)。这个过程在while循环中重复,直到达到时间约束(第12行). 算法的其余部分与算法1相同。算法2在线LTL模型检测算法输入:MJ,BJ,td,si输出:开始1initialization()2N extRound:3计时器:= 04oldT imes:=newT imes5newT times:= 06如果inComputedT able(si),则7currentStates:=getCurrentStates(ComputedTable(si))8其他9currentStates:={(p,q)|(p,q)∈ oldStates <$p = si}10add(si,0,currentStates)到ComputedTable11endif12whiletimer≤td do13newStates:=014对于所有(p,q)∈当前状态,15对于所有的(pJ,qJ),pJ∈nextStates(p)成立16isConsistent(pJ,qJ)do17如果(pJ,qJ)∈oldStates则18不返回19其他20newStates:=newStates<${(pJ,qJ)}21endif22结束23结束24如果newStates=0,则25return是26其他27新闻动态++28currentStates:=newStates29oldStates:=oldStates新状态30endif31endwhile32td:=newT imes+getT imeSteps(ComputedT able(si))−oldT imes33如果td≤tc,则Y. Zhao等人理论计算机科学电子笔记144(2006)12514334return未知35其他36lettimeSteps=newT imes+getT imeSteps(ComputedT able(si))37add(si,timeSteps,currentStates)到ComputedTable38输出td39转到下一轮40恩迪夫恩德显然,该算法保证终止。特别地,出租的时间复杂度,即, O(|SM J| ·|SBJ|),并不增加对静态空检查的计算量。相反,通过引入应用程序的当前状态,在每个检查周期中只处理MJ的一个子图因此,在局部视图中,每轮的时间复杂度为在时间限制方面是可以接受的。因此,这种运行时LTL模型检测在
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 5
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- OptiX传输试题与SDH基础知识
- C++Builder函数详解与应用
- Linux shell (bash) 文件与字符串比较运算符详解
- Adam Gawne-Cain解读英文版WKT格式与常见投影标准
- dos命令详解:基础操作与网络测试必备
- Windows 蓝屏代码解析与处理指南
- PSoC CY8C24533在电动自行车控制器设计中的应用
- PHP整合FCKeditor网页编辑器教程
- Java Swing计算器源码示例:初学者入门教程
- Eclipse平台上的可视化开发:使用VEP与SWT
- 软件工程CASE工具实践指南
- AIX LVM详解:网络存储架构与管理
- 递归算法解析:文件系统、XML与树图
- 使用Struts2与MySQL构建Web登录验证教程
- PHP5 CLI模式:用PHP编写Shell脚本教程
- MyBatis与Spring完美整合:1.0.0-RC3详解
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功