理论计算机科学电子笔记113（2005）145-162www.elsevier.com/locate/entcs度量时态逻辑规范PrasannaThatiandGrigoreRoRangsu美国伊利诺伊大学香槟分校计算机科学系{thati，grosu}@ cs.uiuc.edu二○ ○四年九月十一日摘要在实际的测试和监控应用中，程序执行跟踪可能非常大，以至于存储它们以进行详细分析是非常昂贵的，如果不是不可能的话。监视执行轨迹而不存储它们，对于许多规范形式主义来说可能是一件不平凡的事情，因为复杂的公式可能需要大量关于过去的信息度量时态逻辑（MTL）是命题线性时态逻辑的一种扩展，它具有离散时间有界时态算子。在MTL中，可以指定时间限制，在此时间限制内必须保持某些时间属性，从而使其非常适合表达实时监控要求。本文提出了针对MTL中的公式或其某些重要子逻辑检查带时间戳的执行轨迹的监控算法，并给出了监控问题的下界，证明了所提出的算法是渐近最优的。关键词：验证，执行跟踪，规格化，度量时态逻辑。1介绍验证和监控已经被提出作为轻量级的形式验证方法[13]，其明确的目标是在执行时根据其形式需求在大多数监视应用程序中，执行跟踪只能以增量方式提供，并且它们比检查它们所针对的公式大得多存储整个执行跟踪，然后通过随机访问跟踪来执行形式化分析是非常昂贵的，有时甚至是不可能的。例如，监视器可能缺少资源，例如，如果它在嵌入式系统中运行，或者监视器1571-0661 © 2004由Elsevier B. V.出版，CC BY-NC-ND许可下开放获取。doi：10.1016/j.entcs.2004.01.029146P. Thati，G.《理论计算机科学电子笔记》113（2005）145∞| |当违反其要求时，可以期望迅速作出反应，以便系统安全地采取恢复或关闭动作。在本文中，我们采取的立场，监测算法不存储执行痕迹，而是消费的事件，因为它们是从被监视的程序接收。针对时间规范检查执行跟踪的问题已知对于几个时间逻辑具有非常简单和有效的算法，例如[19]中所示，但这些算法中的大多数假设整个执行跟踪都是预先可用的，因此它们违反了监视算法的假设。本文研究了度量时态逻辑（MTL）[1，15]及其子逻辑的监控算法.MTL是命题线性时序逻辑（LTL）的扩展除了命题操作符，MTL允许未来和过去时间线性时态由离散时间区间约束的算子。例如，φU[3，7]说明从现在开始，φ应该保持在3到7个时间单位之间，并且在此之前φ应该保持不变。区间的一端或两端可以是0或∞。 LTL可以被看作是MTL的特殊情况，其中每个间隔是[0，）. 如[1]中所介绍的，MTL还提供了允许人们声明公式应该相对于绝对时间周期性地保持的同余我们称之为绝对-鲁特同余，并在我们的MTL规范中也支持它们，但除此之外，我们引入了一个新的变体，我们称之为相对同余。相对同余允许一个引用的时刻，周期性地发生从当前时间开始。首先，我们提出了一个通用的MTL监控算法的思想的基础上转换的MTL公式，每个时间戳的观察（或事件，简称）是从被监控的程序。该算法的基本原理是“解析过去，推导未来”。 所谓“分解过去”，是指将MTL公式转化为一个等价公式，该等价公式具有这样的性质：它不存在以过去时间算子为根的子公式，而这些子公式又不受其他时间算子的保护。通过“导出未来”，我们的意思是MTL公式被转换成新的MTL公式，该MTL公式具有当且仅当导出的公式在处理新接收的事件之后保持时当前公式在处理新接收的事件之前保持的属性。我们证明了该MTL监控算法在空间O（m2m）内运行，处理每个事件所需时间O（m323m），其中m等于φ加上φ中出现的所有数值常数之和，φ是φ，所有的时间下标都掉了。读者可能会注意到，尽管这些界限是显式的，但它们与执行跟踪的大小无关，P. Thati，G.《理论计算机科学电子笔记》113（2005）145147我们还表明，该算法具有更好的界限MTL的某些子逻辑，包括LTL。事实上，过去和未来时间LTL的界限与这些逻辑的先前最佳已知监控算法相匹配[11，12]。最后，我们推导出下限监测MTL及其子逻辑，这表明我们的算法是接近最优的。所有主张的证明都被省略了，但它们都可以在[21]中找到相关工作。文[1]中提出了MTL，并研究了它的表达复杂性. MTL只是用于指定实时系统的线性时态逻辑的各种扩展之一（参见[2]的调查）。我们用观测事件推导MTL公式的想法是对时态逻辑经典表格构造的适应[22，9]，其中当前状态下的公式表示输入迹剩余部分的约束，并从当前状态系统地传播到下一个状态。Drusinski [6]在他的商业Temporal Rover系统中实现了MTL公式的监视器，但该实现的实现和算法细节不可用。Java PathExplorer（JPaX）[10]是NASA运行时验证系统，提供过去和未来时间LTL的监控算法MTL对LTL进行了非平凡的推广，将LTL监控算法推广到MTL的动机是明确的--人们通常不仅希望监控可以用LTL表示的定性规范，而且还希望监控涉及时间约束的定量我们提出的算法，当用于LTL规范时，与JPaX中相应的专用算法一样有效或更有效Eagle [4]是一个基于定点的逻辑形式主义，围绕JPaX设计 它表明，鹰是能够定义和实现几个有限的跟踪监控逻辑，包括度量时序逻辑[4]。在最近的一项独立研究中，空间复杂度为O（m22m logm），时间复杂度为O（m422m log2m）。这些是可比的界限，我们建立我们的MTL监测算法时，专门为LTL。在[ 19 ]中的“模型检查路径”的上下文中已经讨论了根据时态公式检查路径的复杂性我们以[19]的风格描述了一个基于动态编程的一个基于简单的场景148P. Thati，G.《理论计算机科学电子笔记》113（2005）145►在[ 8 ]中提出了一种指数方法来检测我们证明了我们的一般算法在用于LTL公式时，不仅比[8]中的算法具有更好的复杂度，而且适用于任何LTL公式，包括未来和过去算子。 在监控中使用交替自动机也是一种有吸引力的方法，从[7]开始用于LTL，但目前尚不清楚它在时间序列事件的上下文中是否容易使用。2度量时态逻辑在本节中，我们简要回顾了MTL;读者可以参考[1]了解更多细节。给定一个有限命题集P，MTL公式集归纳定义如下。φ：=真实|虚假|p|φ1∧φ2|φ1⊕φ2|Iφ|φ1UIφ2|·Iφ|φ1SIφ2其中p∈P，且I是以下之一：(1) 非负实直线的一个区间，其左右端点为自然数或∞。对于数n，表达式±I±n表示区间{±y±n|y∈I}<$[0，∞）.(2) 相对全等 对于整数d≥2和c≥0，表达式dc。y∈φ dc表示y=cmodd，且±I±n表示集合{y|y=±c±nmod d}。(3) 对整数d≥2和c≥0，一个绝对同余式=dc表达式y∈ = dc表示y=cmodd和±I±n表示集合{y|y=cmod d}。在第三节中，我们用互斥选言代替否定来简化某些技术性问题。我们假设公式中出现的整数常量以二进制格式编码。我们解释MTL公式在有限时间状态序列。时间状态序列ρ=（π，τ）是由有限序列π的状态π iP，以及实数的有限序列τ，|π|为|τ |并且对于每个i，τ i≤τ i+1。德费恩|ρ|为|π|.直观地说，序列ρ表示系统的定时执行，并理解如下：在时间τi，系统被观察到处于πi状态。设π [i，j]表示π i π i+1.π j，对于τ [i，j]也是如此，令ρ [i， j]= （ π [i，j] ，τ [i ，j]） 。 给定时间状态序列ρ 和位置1≤i≤|ρ|，我们定义了（ρ，i）满足公式φ（记为（ρ，i）φ）的意义如下：（ρ，i）true总是true（ρ，i）false总是false（ρ，i）<$pi <$p∈πi（ρ，i）<$φ1<$φ2i <$（ρ，i）<$φ1和（ρ，i）<$φ2P. Thati，G.《理论计算机科学电子笔记》113（2005）145149◦| | |× |×（ρ，i）（ρ，i）Iφi i<|ρ|，（ρ，i +1）<$φ，τi+1∈ τ i+ I（ρ，i）<$φ1UIφ2i <$$>（ρ，j）<$φ2，其中j≥i，τj∈τi+I，（ρ，k）<$φ1，对所有i≤kj（ρ，i）<$·Iφi <$ i >1，（ρ，i−1）<$φ，andndτi−1∈τi−I（ρ，i）<$φ1SIφ2i <$$>（ρ，j）<$φ2对于某些j≤i，其中τj∈τi−I，（ρ，k）<$φ1，对于所有jk≤i我们把（ρ，1）<$φ简写为ρ<$φ。注意，间隔和相对同余表示相对于例如，在位置i处，◦ [m，n]真成立，如果τ i+1− τ i∈ [m，n]，并且如果τ i+1− τ i= c mod d，则ε=d c真成立，而如果τi+1=cmodd，则ε = d c真成立。MTLasoriginallydefinein[1]只包含作为原语的绝对同余，但我们引入相对同余，因为它们在许多规范中自然出现。以下是一些有用的缩写：<$φ=true<$φ φ1<$φ2=φ1<$φ2 <$$>（φ1<$φ2）QIφ=trueUIφQIφ=<$QI<$φQ·Iφ=trueSIφIφ=<$Q·I<$φ我们写U为U[0，∞），U≤m为U[0，m]，U>m为U（m，∞），Um为U[m，m]，对于其他时间算子也是如此。请注意，标准LTL属于MTL的退化子逻辑，其中仅允许间隔[0，∞），这相当于满意度的递归定义通常导致基于高效动态编程的算法，用于检查由公式[19]定义的轨迹集中的轨迹的成员资格。可以很容易地设计出上述语义的等效递归定义：（ρ，i）<$φ1UIφ2i <$0 ∈ I且（ρ，i）<$φ2，或i<|ρ|和（ρ，i）φ1和（ρ，i+1）<$φ1UIJφ2其中IJ=I−τi+1+τi（ρ，i）<$φ1SIφ2i <$0∈I且（ρ，i）<$φ2，或i>1且（ρ，i）<$φ1且（ρ，i−1）<$φ1SIJφ2其中IJ=I−τi+τi−1测试（ρ，i）φ的一个有效的动态规划算法自然遵循：分配一个大小为d的ρφc位，其中c是最大的出现在φ中的整数常数。这个想法是d（i，j，c）是1当且仅当（ρ，i）满足从φ的第j个子公式通过从子公式的根处的区间（如果有的话）减去c而获得的公式φ。通过仔细地遍历表d，可以在时间上线性地填充它的大小。参见[19]其他时态逻辑的相关算法。然而，这样的算法在监视的上下文中是非常不期望的，因为它不仅需要150P. Thati，G.《理论计算机科学电子笔记》113（2005）145--{−}要存储的整个跟踪，这在监视非常长的执行时是不可容忍的，但它本质上也不是在线的3有限迹在本节中，我们将介绍MTL的主要监控算法。3.1解析过去，衍生未来我们定义了两个相互递归的公式变换，一个用于过去，一个用于未来。变换[ρ，i]φ根据ρ中的第i个事件，即根据迄今为止观察到的事件，解析φ中的所有顶层过去时间算子。得到的公式是一个等价的公式，它不包含任何无保护的过去时间操作符，即每个顶层时态操作符都是未来时间操作符（见引理3.2）。变换φ ρ，i导出了关于ρ中第i个事件的公式φ，使得所得公式在事件之后成立，当且仅当φ在事件之前成立（见引理3.2）。定义3.1设ρ是时间状态序列，且1 ≤i≤|ρ|.我们定义[ρ，i]true=true[ρ，i]false=false[ρ，i]p=p∈πi[ρ，i]（φ1<$φ2）=（[ρ，i]φ1）<$（[ρ，i]φ2）[ρ，i]（φ1<$φ2）=（[ρ，i]φ1）<$（[ρ，i]φ2）[ρ，i]<$I φ=<$Iφ[ρ，i]（φ1UIφ2）=φ1UIφ2[ρ，i]·Iφ=ifi=1orrτi−1∈/τi−Ithenfalse else [ρ，i]（φ ρ，i1）[ρ，i]（φSφ） =if0∈Ithen[ρ，i]φ2ifi=1thenfalse1I2否则为falseelse[ρ，i]（φ1<$（φ1SIJφ2）{ρ，i−1}）其中IJ=I−τi+τi−1true{p，i}=truefalse{p，i}=falsep{ρ，i}=p∈πi（φ1<$φ2）{ρ，i}=（φ1{ρ，i}）<$（φ2{ρ，i }）（φ1<$φ2）{ρ，i}=（φ1{ρ，i}）<$（φ2{ρ，i}）（<$·Iφ）{ρ，i}=（[ρ，i]<$·Iφ）{ρ，i}（φ1SIφ2）{ρ，i}=（[ρ，i]（φ1SIφ2））{ρ，i}（Iφ）{ρ，i}=ifi=|ρ|或τi+1∈/τi+I，n个假元素eφP. Thati，G.《理论计算机科学电子笔记》113（2005）145151F（φUφ）{ρ，i}=if 0∈Ithenφ2{ρ，i}if i=|ρ|n个错误的字母1I2否则为falseelse（φ1{ρ，i}<$（φ1UIJφ2））其中IJ=I−τi+1+τi从现在起，我们采用了运算符[ρ，i]·和·{ρ，i}比所有逻辑连接词更弱的约束。例如，在一个示例中， [ρ，i] φ1SIφ2表示[ρ，i]（φ1SIφ2），并且φ1SIφ2{ρ，i}表示（φ1SIφ2）{ρ，i}。设F（φ）是φ的所有子公式的集合，这些子公式要么是时间算子，要么是拓扑算子. LetF（φ）是F（φ）中出现在φ中的不受时间算子保护的多个事件的集合，即（φ）中处于“顶层”的公式。令φ表示通过丢弃φ中的所有区间而获得的公式（即，用[0，∞））隐式地替换每个区间）。 例如，对于φ =p1UI（p2<$p3），我们有F（φ）={p1，p2，p3，φ}，Fφ（φ）={φ}，且ndφ=p1U（p2<$p3）. 让F+（φ）= F（φ）<${φ1UIJφ2|φ1UIφ2∈ F（φ），IJ= I − n对于某些n} F−（φ）= F（φ）<${φ1SIJφ2|φ1SIφ2∈ F（φ），IJ= I − n对于某个n} F±（φ）= F+（φ）<$F−（φ）下面的引理陈述了定义3.1中公式变换的某些性质，我们在本节前面非正式地声明了这些性质引理3.2对于时间状态序列ρ和1 ≤i≤ |ρ|、(i) F（[ρ，i]φ）<$F+（φ）.此外，如果φ以过去时间时间算子为根，则F（[ρ，i]φ）<$F+（φ）\φ。(ii) F_∞（[ρ，i]φ）中的每个公式都是一个可拓的理想算子。(iii) （ρ，i）<$φ当且仅当（ρ，i）<$[ρ，i] φ。(iv) F（φ {ρ，i}）<$F+（φ）.此外，如果φ以过去时间时间算子为根，则F（φ {p，i}）<$F+（φ）\φ。(v) F（φ {p，|ρ|}）为空，即φ {p，|ρ|}等价于true或false。(vi) 因为我<|ρ|，（ρ，i）<$φ当且仅当（ρ，i +1）<$φ{ρ，i}，且（ρ，i）|ρ|）φ φ当且仅当φ{ρ，|ρ|}。Q3.2标准形在每次事件后转换MTL公式时，保持转换后公式的大小较小至关重要。我们的监控算法的一个重要组成部分是一个程序，它保持公式在一个规范的形式，保证不增长大于指数的大小，原来的152P. Thati，G.《理论计算机科学电子笔记》113（2005）145⊕∧P∪{}⊕∧}Pi=1i=1联系我们|∈}||公式此外，公式表示也可以在简单的指数时间内以原始公式的大小更新。如下所述，这个过程的正确性是基于Hsiang [14]的结果，将命题演算视为布尔环，通过将命题简化为由合取的排他析取组成的规范形式。下面的命题编码BDD [5]或其他更标准的编码（如CNF或DNF）是否也可以在我们的监测框架中成为可行的可能性，反之亦然，即我们的编码是否然而，就目前而言，我们更喜欢下面介绍的布尔环编码，因为它使我们从处理否定中解脱出来，更重要的是，它允许非常简单和有效地实现几个命题运算，包括一个非平凡的替换。设P ={p1，p2，...，p m是一组“参数”，并让Prop_n（）是一组-规范命题的符号在真，假。通过-正则，它意味着正则模的结合性和交换性方程，使用下面的其他方程作为重写规则：结合，我们可以明确地写出表达式，如φ1. φ n和φ1转... φ n或φ i和φnφ i，分别。 由于教堂-罗瑟和AC重写系统的终止[14]，不难看出，- 标准型有唯一的形式<$i∈I<$j∈JiCij，其中• Cij∈P<$ {true，false}对所有i∈I和j∈Ji;• 对于每个i∈I，元素Cij形成一个集合，即Cij/=Cik对于jk;• 集合{C ij|j ∈ J i}也构成一个集合;• 真Cij j Ji，除非当Ji=1时，如果是这种情况，则i是I中具有此性质的唯一索引;• false/∈ {C ij|j ∈ J i}，除非|J I| = 1和|我|= 1。注意到|我|≤ 2 m且|J I| ≤m。 由于上述原因，人们可以将任何（一） （φ1<$φ2）<$φ3=φ1<$（φ2<$φ3）（二）φ1<$φ2=φ2<$φ1（三） φtrue=φ（四）φφ=φ（五） （φ1<$φ2）<$φ3=φ1<$（φ2<$φ3）（六）φ1<$φ2=φ2<$φ1（七） φfalse=φ（八）φφ=falseP. Thati，G.《理论计算机科学电子笔记》113（2005）145153∈--⊕M⊕∧⊕∧⊕∧P-规范形式，作为P中元素的集合的集合。为了使其工作，我们需要采用标准的概念，即j∈是真的，而i∈是假的。接下来，我们描述如何在P= p1，p2，.中的参数上的正则命题，Pm可以被编码在2比特上，并且还可以有效地执行对以这种方式编码的命题的几个常见操作。以来正则命题可以被看作是至多m个元素的集合的集合，我们首先通过用m位序列b对P的每个子集P进行编码，其中具有b[j]=1ifanddonlyifpj的命题P.Nechb对应于0到2m−1的正则命题φ;其思想是第i位为1当且仅当对应于i的二进制m比特表示的集合对应于φ的合取之一。一个2m个零的序列对公式进行了编码;如果φ的形式为真φφJ，则在φ的2m位表示中对应于i= 0的位为1。特别地，命题真被编码为1，被认为是一个2m比特的数.接下来，让我们定义相应的按位变换，用于对正则命题的各种运算。从现在起，由于一一对应，我们不再区分一 个 非正则命题和它的二元表示。因此，特别地，我们说φ[i] = 1当且仅当φ包含与i的二元表示中的相应命题形成的合取。互斥析取。对于双正则命题φ和φ的正则形式的二进制表示，只不过是按位异或操作应用于φ和φ的二进制表示。实际上，二进制表示中的每个比特对应于形成相应合取的命题集合，并且通过等式（8）和（7），同一集合不能在范式中出现两次这个简单的过程需要时间O（m2m），因为还需要递增遍历两个2m位序列的m连接。对于-正则命题φ和φ，我们声称下面的O（m22m）过程计算了它们在φ中合取的-正则形式的二进制表示：= 0对于i，j= 0至 2m− 1k=binary（i）或binary（j）n[k] =n[k]xor（φ[i]andn[j]）运算符or、xor和以上是按位的，binary（i）是i的二进制表示。如果i和j已经是二进制表示，那么for循环的增量，以及k和k[k]的计算，需要O（m）的时间。154P. Thati，G.《理论计算机科学电子笔记》113（2005）145∧∧−⊕∧⊕⊕∧⊕∧n ∈P联系我们为了保持符号简单，我们模糊地让φ也表示2m位通过上述程序计算的Δ其他布尔运算符。也可以定义其他布尔运算。例如，通过对φ的第一位进行异或运算，可以在恒定时间内计算出<$φ（对应于true的那个），1。同样，φp k，对于一些p k，可以像在一般合取中一样计算，但是具有优化因为j=2 k是唯一的位在n中是1，所以合取可以在时间O（m 2 m）内计算。最后，由于标准析取式φ到φ（φ），它可以在时间O（m22m）内计算。换人。我们将使用的对命题的一个非常频繁的操作是应用替换。更准确地说，假设T：[1，m] → [0，2 m− 1]是一个映射，赋给参数p j∈ P，由它们的指数抽象，一个二元表示中的正则命题。现在给出另一个- 二元表示中的规范命题，比如φ，问题是将T代入公式φ，使之成为标准形式，并求出其有效值。下面的代码运行时间为O（m223m），计算这个命题的二进制表示：= 0对于i= 1到 2m 1如果φ[i]，则γ= 1（作为2m位数）对于j= 1到m如果binary（i）[j]，则γ=γ<$T[j]=外循环和条件遍历φ的所有合取;然后内循环和条件遍历合取中出现的所有命题，并将它们递增地应用替换，由于分布性规则（9）而自底向上传播。最后，新得到的命题γ是-标准形式的，需要与已经存在的对不同的i得到的类似命题合并。设subst（φ，T）为上面计算的φ所有上述情况使我们能够说明以下重要结果：定理3.3-关于参数in= p1，p2，.的典型命题p m可以存储在空间2 m中，使得异或运算、合取运算和替换运算的时间分别为O（m 2 m）、O（m 22m）和O（m2 23m）。Q3.3监测MTL公式MTL监控算法现在可以相对容易地定义，遵循定义3.1中的相互递归公式转换关系，P. Thati，G.《理论计算机科学电子笔记》113（2005）145155⊕∧--FF F--1个监视器（φ，ρ）2分配R [1. m]、D [1. m]3对于i = 1，|ρ|做4对于j= 1至m，doR[j] = resolve（公式（j），R，D，ρ，i）5对于j= 1至m，D[j]= derive（公式（j），R，D，ρ，i）6φ=subst（φ，D）7如果φ=false或φ=true，则break8返回φ9端部监视器Fig. 1.有限时间状态序列上的MTL监控算法。利用命题的2m位标准形式表示和基本命题运算的高效实现。我们的算法本质上是一个动态规划算法，实现了定义3.1中的递归关系。给定一个φ的正则形式的公式，用象Hsiang [ 14 ]那样的方法，使m =| F±（φ）|. 注意m ≤ |φ| + φ，其中φ是与UI和SI在φ中的每次出现相关联的所有数字常数的总和，如下所示：如果I = [m，n]，则n;如果I = [m，∞]，则m;如果I=dc，则d;否则为0。 对于每一个f∈ F±（φ），指定一个唯一的整数1≤index（f）≤ms. t。当f∈ F±（f2）时，则指数（f1）≤指数（f2）.对于1≤i≤m，让公式（i）返回n，使得index（n）=i。图1显示了主要监控算法的伪代码。这个过程总是保持它所处理的公式为2m位规范形式.这些标准型将在参数F ±（φ）={φ1，.，其中index（i）=i，并且如子节3.2中所述进行编码。注意到φ的初始2m位表示可以在时间O（m2m）内计算。监视过程维护两个数组R和D，每个数组的长度为m，每当观察到的定时序列ρ中的下一个元素可用时，第3行中的循环就会更新这两个数组。如果公式（j）=π，则在第i迭代之后，R[j]将是[ρ，i]π，D[j]将是πρ，i。此外，R[j]和D[j]保持标准形式。我们注意到，可以使用相同的参数集1，. ..（D [j]），（R[j]）±（φ）。使用两个相互递归的过程来计算阵列R和D- 解析和导出-如图2所示。这些都遵循定义3.1，因此是不言自明的。注意，当前迭代中R的计算使用前一次迭代中的D，而当前迭代中D的计算使用当前迭代中的R。因此，在每次迭代中，R在D之前更新。156P. Thati，G.《理论计算机科学电子笔记》113（2005）145公司简介resolve（φ，R，D，ρ，i）caseφ ofp：π=p∈πiIφ1：ifi=1orτi−1∈/τi−Ithen=falseelseφ=subst（subst（φ1，D），R）φ1SIφ2：如果0∈I，则φ2 =subst（φ2，R）elseφ2=false如果i= 1，则1=false否则IJ=I−τi+τi−11=subst（φ1，R）◦Iφ1，φ1UIφ2：φ=φ回线结束解析导出（φ，R，D，ρ，i）情况φp：π=p∈πi◦Iφ1：ifi=|ρ|或τi+1∈/τi+I，则n∈=fal seelse∈=φ1φ1UIφ2：如果0 ∈ I，则φ1= subst（φ2，D），否则φ1=假如果i = |ρ|则f2= false否则IJ=I−τi+1+τi2=subst（φ1，D）Iφ1，φ1Iφ2：φ=subst（R[index（φ）]，D）回线端导出图二.解析过去，推演未来。定理3.4过程监控器（φ，ρ）返回真i <$ρ <$φ。时间复杂度为O（m2），时间复杂度为O（|ρ|m323m），其中m =|F ±（φ）| ≤|φ|+φ。Q我们以几点观察来结束这一节首先，请注意，在第i次迭代中，监控过程只访问ρ i−1，ρ i和ρ i+1，因此我们不需要存储观察到的整个时间序列。第二，空间重构--通过仅对那些根在过去时间算子的f∈ F±（φ）在R中具有条目，可以进一步优化该过程的查询。这是因为R中原子命题的条目与D中相应的条目一致，而根在未来时间的运算符的条目包含了它本身。P. Thati，G.《理论计算机科学电子笔记》113（2005）145157∞4MTL子逻辑的更强性能结果对MTL的某些子逻辑的监控算法的更精细的性能分析表明，与整个MTL相比，该算法在这些子逻辑上具有更好的性能我们考虑两个这样的子逻辑- MTL和LTL。4.1只有过去时间算子一大类安全属性，通常称为规范安全属性[18]，可以被简洁而自然地表示为过去时间公式φ，该公式必须在执行跟踪的每个时刻保持。在MTL中，这与针对Qφ（Q[0，∞）φ）的check相同。因此，适当地，可以快速地进行以下操作：定理4.1设φ是一个MTL公式，其中只有过去时间算子。（1）时间为0，时间为0，时间为0。|ρ|时间复杂度为O（m），其中m = |F±（φ）|. Q读者可以检查仅用未来时间操作符监视MTL与用未来和过去时间操作符监视MTL具有相同的复杂性4.2线性时态逻辑MTL的监控算法可以被专门化以获得LTL的算法回想一下，LTL公式可以被看作是MTL公式，只有形式[0，）的区间;尽管LTL公式是在（无时间的）状态序列上解释监视算法可以通过简单地在解析和导出过程中删除所有对时间的引用来专门化作为定理3.4和4.1的推论，我们得到了具有过去和未来时间算子的LTL可以在时间O（|ρ||φ|323|φ|）ndpaceO（|φ| 2 |φ|）（注意φ= φ），而仅具有过去时间算子的LTL可以在时间O（|ρ||φ|空间O（|φ|）. 事实上，具有相同复杂度界限的监控算法对于只有未来时间的LTL是已知的操作符[11]和仅具有过去时间操作符的LTL [12]。但同时具有过去和未来时间算子的LTL算法似乎是新颖的。5空间的指数下界我们现在得到一些空间下界的结果表明，我们的监测算法MTL及其子逻辑接近最优。158P. Thati，G.《理论计算机科学电子笔记》113（2005）145L00−−k，n23k，nk，n005.1MTL的下限考虑一个监控场景，只有一个命题，因此只有两个状态，比如0和1。对于自然数k，n，定义以下有限时间序列语言ρ=（π，τ）：Lk，n={p|τ1=. . . . =τk，τi+k=τi+1，τls. t. |π|=lkn，并且 1 ，C |ψ|≥（c+1）|ψ|≥|ψ|公司简介使用以下事实：|ψ|.最后，请注意，由于φk，n只包含未来时间算子，上面建立的下限也适用于只包含未来时间算子的MTL。5.2仅含区间的MTL的下界我们证明了MTL的子逻辑没有同余（绝对或相对）的下界。我们首先证明了MTL的一个下界，它只具有形式[0，∞）的区间。请注意，这也将为我们提供LTL的下限。考虑一个只有两个原子谓词的监控框架，因此只有四种可能的状态，比如0、1、#和$。 对于自然数k，定义Lk为所有时间序列（π，τ）的集合，使得π∈{σ#w#σJ$wσJJ|w∈{0，1}k且σ，σJ，σJJ∈{0，1，#}}类似的语言以前在几个作品中使用[16，17，20]来证明模型检查和监视扩展正则表达式的下界。引理5.3L k的任何监控算法都需要空间k（2 k）。Qψ√160P. Thati，G.《理论计算机科学电子笔记》113（2005）145一| |- ¬∨定理5.4设A是MTL的任何监控算法，其区间为m[0，∞）。这是一个公式φ，用于监视器，它要求α（2 α|φ|），则为常数α。Q对于MTL的子逻辑，这个下界可以被改进为具有任意间隔。使用类似于引理5.1证明中的论证，我们可以很容易地证明任何监控算法都需要空间n（n）来监控公式p（（Qntrue）（Qnq））。因此，一般来说，任何监控算法都需要空间φ（2αφ）来监控公式φ。发生上述情况是因为φ包含一个指数大于φ的常数。下图显示，即使公式中出现的最大常数远小于公式的大小，任何监视器仍然需要指数空间。定理5.5设是任意时间间隔MTL的监控算法.有一个公式φ，其中出现的最大常数小于|φ|且A需要空间<$（2 α|φ|/log|φ|），对于一个 固定常数α。 Q6结论和今后的工作给出了度量时态逻辑（MTL）需求的一种通用监控算法，并给出了MTL各子逻辑的实例。结果表明，该算法在原MTL公式中的时态算子和原子谓词的数目以及数值常数的和上是指数的，并且即使对于MTL的简单子逻辑也不能避免指数界.比例算子的数量，通常占指定的大部分大小，并不影响我们算法的复杂性。由于MTL是一种用于监控需求的表达性和强大的逻辑，因此所提出的新颖且接近最佳的算法可以用于实际的运行时验证和测试工具，如JPaX [10]。确认我们感谢Koushik Sen激励我们对所提出的技术进行更好的空间分析，从而将我们的监控算法的空间需求从原始的粗糙2O（m）提高到当前的O（m2m）。P. Thati，G.《理论计算机科学电子笔记》113（2005）145161引用[1] R. Alzheimer和T.亨辛格实时逻辑：复杂性与表现力。第五届计算机科学逻辑，第390IEEEComputer Society Press，1990.[2] R. Alzheimer和T.亨辛格逻辑和模型的实时：一个调查。InReal Time：Theory in Practice，卷600计算机科学讲义。Springer Verlag，1992年。[3] H. Barringer，A.戈德堡K.Havelund和K.参议员在Eagle中使用LTL进行程序监控并行和分布式系统研讨会：测试和调试，2004年。地出现。[4] H. Barringer，A.戈德堡K. Havelund和K.基于规则的运行时验证。第五届验证、模型检查和抽象解释国际会议论文集（VMCAI[5] R.E.布莱恩特基于图的布尔函数操作算法。IEEE Transactions on Computers，35（8）：677[6] 多伦·德鲁辛斯基时空漫游者和ATG漫游者SPIN Model Checking and Software Verification，1885卷，Lecture Notes in Computer Science，第323-330页。斯普林格，2000年。[7] B. Finkbeiner和H.西普玛使用交替自动机检查有限轨迹。电子笔记理论计算机科学，55（2），2001年。[8] M.盖伦论时态逻辑性质的监控器的构造。电子笔记理论计算机科学，55（2），2001年。[9] M.C.W.盖伦一种改进的实时时序逻辑的on-the-scheduled tableau构造。计算机辅助验证国际会议，2003年7月。[10] K. HavelundandG. Rosu.Mon itorigJavaprogramswithithJavaPathExplorer. 理论计算机科学中的电子计算机笔记，55（2），2001年。[11] K. HavelundandG. Rosu. 使用重写的原始程序。我想学土木工程。电气和电子工程师协会计算机学会，2001年。[12] K. HavelundandG. Rosu. 为安全起见，请对移动电话进行调整。系统构造与分析逻辑与逻辑，计算机科学讲义2280，第342- 356页，2002年[13] 我和格里戈尔和罗林斯都在这里。2001年出版，第55卷，理论计算机科学中的Electronnot es。Elsevier Science，2001年。计算机辅助验证（CAV'01）卫星研讨会论文集[14] 姐香使用项重写系统的反驳定理证明。《人工智能》，25：255[15] R.科伊曼斯用度量时态逻辑描述实时特性。实时系统，2（4）：255[16] O. Kupferman和M. Y.瓦迪自由、弱点与决定论：从线性时间到分支时间。IEEESymposium onLogic in Computer Science，第81-92页[17] O. Kupferman和M. Y.瓦迪安全属性的模型检验。计算机辅助验证会议论文集，计算机科学讲义，1999年。[18] 佐哈尔·曼纳和阿米尔·普努埃利反应系统的时间验证：安全性。Springer，纽约，1995年。[19] N. Markey和Ph. Schnoebelen。模型检查路径（初步报告）。在第14届国际会议上， 并发理论，计算机科学讲义2761，第251-265页。Springer，2003年。162P. Thati，G.《理论计算机科学电子笔记》113（2005）145[20] G. RonsundM. Viswan ath an. 通过重写来测试扩展的重定向结构。重写技术和应用，计算机科学讲义2706，2003。[21] P. Thati和G.罗苏度量时态逻辑规范的监控算法。技术报告UIUC DCS-R-2003-2395，计算机
我的内容管理
展开
