没有合适的资源?快使用搜索试试~ 我知道了~
执行统计数据的收集方法及其应用
36理论计算机科学电子笔记70第4期(2002)网址:http://www.elsevier.nl/locate/entcs/volume70.html19页收集关于执行的统计数据Bernd Finkbeiner、Sriram Sankaranarayanan和Henny Sipma斯坦福大学计算机科学系。94305摘要通过收集程序运行时执行的统计数据,我们可以回答复杂的查询,例如通信协议中的“平均数据包重传次数是多少”,或者互斥算法中的“进程P1进入临界区而进程P2等待的频率是我们提出了一个扩展的线性时间时序逻辑,结合了统计数据的收集的时间规格通过将该语言的公式转化为交替自动机,我们得到了一个简单而有效的查询求值算法。我们用例子和实验结果说明了我们的方法1介绍验证[13]是一种轻量级的程序安全方法。给定程序执行的跟踪,如果跟踪满足程序规范,则报告成功,如果检测到错误,则报告失败。这种方法有一定的局限性。例如,活性属性永远不会在有限的轨迹上被证伪。在监控应用程序时,警告即将发生故障的指示器(如网络中的数据包重传次数)通常比警告实际违规更有帮助。在本文中,我们提出了一个扩展的线性时间时序逻辑,结合了时间规格与统计数据的收集。而不是检查属性我们的查询是从实验中构建的,这些实验在各个跟踪位置形成基本观察,并将1本研究部分由NSF(ITR)资助CCR-01-21403, 通过 NSF授权CCR-99-00984-001,ARO授权DAAD 19 -01-1-0723,以及ARPA/AF合同F33615-00-C-1693和F33615-99-C-3014。2002年由ElsevierScienceB出版。 诉 操作访问根据C CB Y-NC-N D许可证进行。FINKBEINER、SANKARANARAYANAN和 SIPMA37∀多项实验的结果。这种查询语言在第2节中定义。我们讨论的例子,从通信协议和互斥算法。接下来,我们开发了一个自动机理论的解决方案,评估查询。 我们在第四节中介绍代数交替自动机,并讨论它们在迹上的求值。 查询到自动机的转换在第5节中描述。第6节最后给出了我们的原型实现的实验结果。相关工作程序剖析有着悠久的历史,例如流行的工具gprof。然而,这项研究主要集中在某些特定类型的数据上,如运行时间和内存泄漏。我们的方法可用于开发评估用户定义的时态查询的灵活的分析工具线性时间时态逻辑的验证最近受到越来越多的关注。例子包括商业系统Temporal Rover [7],这是一种允许将规范嵌入C,C++,Java,Verilog和VHDL程序的工具。验证算法也被应用于指导NASA开发的Java模型检查器Java Path。线性时间时态逻辑是一种广泛使用的形式主义,用于反应和并发系统的规范和验证[15]。对于静态分析,定量查询的其他扩展首先在实时系统的背景下进行了研究[8,9]。最近的工作沿着同样的路线包括[1,5]。我们的查询语言可以看作是MAX CTL[5]中的逻辑M的推广。交替自动机[6]是不确定自动机和非确定自动机[14]的推广.由于它们的简洁性,它们是一种有效的数据结构,用于规范和验证中的许多问题[19,18]。我们在第4节中定义的代数交替自动机受到[4]的扩展交替自动机的启发。在那里,扩展的交替自动机用于静态查询检查,它确定了一组命题公式,满足时间查询的程序。我们使用交替自动机进行运行时验证的一般框架在[10]中报告。在本文中,我们具体化的一般方法,提供了一个查询语言以及从查询到交替自动机的转换。2统计数据2.1程序、状态和跟踪在我们的框架中,运行时验证包括对程序跟踪的查询这些查询通常包含对程序变量的表达式,但它们并不进一步依赖于程序或其结构,也不依赖于它们的求值。因此,只形式化状态和迹的概念就足够了。FINKBEINER、SANKARANARAYANAN和 SIPMA38T ›→ V∈VV V›→ V不∨¬≥设λ是一个多排序代数签名,P是一个变量X有限集的程序。假设每个变量x∈X都有一个固定的排序τx。查询表达式e是术语代数(algebra,X)中的一个术语。给定一个λ-代数得双曲余切值.- 程序P的状态是映射s:X这样每个变量x X都被赋予一个在中正确排序的值。 我们故意将状态s与唯一同态s混淆:(x,X),它扩展了s。因此,如果e是一个表达式,则s(e)由这个同态定义带有排序布尔值的表达式称为断言。我们假设存在一个蕴涵关系q这样,一个国家满足了一个断言,,写为sq函数可能返回一个值,也可能失败。因此,我们假设所有的排序都包含一个特殊的元素来表示查询的失败在程序跟踪上解释数据形式上,长度为n的(P-)迹σ是状态s0,s1,...,sn−1。我们写σ(i)来表示状态si。2.2实验覆盖程序跟踪是从统计实验中构造的:例如,在跟踪中的特定位置处指定关于跟踪的查询。给定前面介绍过的一元代数,设p是断言,c是一个常数,δ是一个一元项,f和g分别是一个一元函数和二元函数。那么,如果101和102是统计实验,那么以下也是• 状态表达式。 p:δ,表示给定位置的δ值,如果p否则实验失败。• 连接。如果实验结果是101和102都成功的话,那么g的值就是101和102,否则实验失败。• 分离。 ψ1g2,同上,除了1和2中只有一个必须成功才能使实验成功• 否定。c1,如果1失败,则表示值c,否则视为失败。• 下一个 2 f1,表示应用于在跟踪的下一个位置执行的1的结果的f值,前提是1成功。• 直到... 1Ug更正式地说,统计实验的结果值在迹σ:s0,s1, . 上 的 结 果 值 。 在位置j处,0是written[σ](σ,j),归纳定义如下:FINKBEINER、SANKARANARAYANAN和 SIPMA39联系我们≤≤12(σ,j)(σ,k)⊥对于状态表达式:sj(δ)ifsjqp[p:δ](σ,j)=100其中sj(δ)是δ在s中的值。对于bobeconnecancerves:否则如果[σ1](σ,j)=σ[<$c<$1](σ,j)=g([[1g2](σ,j)=g([[1g2](σ,j)=σr[σ2](σ,j)对于时态运算符:否则f([[二f<$1](σ,j)=否则,其中k是最小的k,jk n,证明了[σ2](σ,k) ∈C,且[1Ug2](σ,j)=[1](σ,i)对于每个i,j,≤i k,或如果不存在这样的k,则为在析取和Until运算符的情况下,g的参数之一可能是。我们假设g被扩展为在这种情况下被定义。例1. 想想痕迹σ:σ 1,1,σ 1,2,σ 1,3,σ 2,3,σ 5,3,σ 4,3其中,每个状态x,y表示两个整数变量x和y的值。以下是统计实验的简单例子:• 如果xy成立,则σ的第一状态x的值,表示为[xy:x](σ,0)结果值为n,因为第一个状态不满足x y。• 如果x≤y,则在σ的第一状态中的元组x,y由下式表示:[x≤y:](σ,0)否则否则FINKBEINER、SANKARANARAYANAN和 SIPMA40关于我们⊥∧⊥结果值为1,1。• 实验[(x≤y:x)U+(y=x+ 2:y)](σ,0)返回4,第一个状态中x的值和第三个状态中y的值之和,因为1, 3是第一个状态,使得y=x+2为真。注:线性时间时间公式及其通常的迹线解释是统计实验的一种特殊情况,其中δ对所有状态表达式都有排序T,并且运算符具有以下相关函数:但是,但是,呃,2 ,Uπ2ID其中id是恒等函数,π2是在第二个元素上的投影。因此,线性时间时态公式可以被认为是一个统计表达式,如果它成立,则值为T,如果它失败,则值为T,因此也可以在更复杂的查询中用作子公式。在本文的其余部分,我们将使用时间公式的常用符号,并省略项δ和与运营商相关的功能。2.3汇总统计数据统计实验提供了轨迹中特定位置的值。这些实验的结果可以组合到聚合统计中,以获得部分跟踪或全部跟踪的值。这种聚合统计的示例是计算轨迹上所有成功实验的最小值或最大值,或者所有结果的总和,或者只是所有成功实验的计数。我们假设这些汇总统计量可以以增量方式计算,并且评估顺序,向前或向后,不会影响最终值。此外,我们假设所有当且仅当所有实验都失败时,聚合统计返回0聚合表达式定义如下。 设是一个统计实验,是一个带有排序布尔值的统计实验,g是一个二元函数,α是一个增量可计算的聚合函数。如果R1和R2是聚合表达式,则以下表达式也是聚合表达式:• 实验:集合表达式的值等于在特定位置处的实验• 合取:101g2.2. 聚合表达式的值为101和102如前所述进行统计实验。• 分离:0.1×0.2×0.2。这些值如上所述进行组合• 无条件收集:Cα1。汇总统计量α应用于所有不符合条件的1991年的从当前位置到结束追踪• 间隔Co ll e:101Iα。总统计量α适用于所有输出-FINKBEINER、SANKARANARAYANAN和 SIPMA41⊥⊥⟨⟩从当前位置开始到停止保持时结束的未超过最大间隔的时间间隔在给出最后两个算子的形式语义之前,我们先给出一些增量可计算统计量的例子,即迹σ上的函数α:s0,s1,.,sn,使得存在二元函数fα,使得α(σ)= fα(. (fα(fα(n,sn),sn−1),. . ),s0)以下是计算聚合统计最小值、最大值、总和和计数的二进制函数。在两个参数都是非线性的情况下:fmin ( x , y ) =ifxythenxelsey;fmax(x,y)=ifxythenyelsex;fmax ( x , y )=x+yfcont(x,y)=x+ 1对于其中一个参数为“t”的情况,上述函数返回非“t”,除了“f”之外,如果第一个参数为“t”,则"h“返回1。如果第二个参数为“”,则为非“”参数。给定一个增量可计算统计量α,迹σ中位置j≥0处的聚合表达式的结果定义如下[Cα<$1](σ,j)=fα([Cα<$1](σ,j+1),[<$1](σ,j))<$fα([<$1Iαφ](σ,j+1),[<$1](σ,j))if(σ,j)q φ[1Iαφ](σ,j)=否则有时子表达式的非参数的值并不重要,例如在计数聚合的范围内。下面我们将简单地省略这种情况下的项和函数符号,并假设默认标签为常数T。实施例2. 为了说明聚合统计信息,请考虑跟踪σ:1,1,2,1, 2,2,1, 3,1,2, 3,1,5, 3,1,4, 3,2其中每个三元组x,y,z标识三个整数变量x,y和z的值。下面我们将展示如何将有关此跟踪的各种问题表示为聚合表达式以及它们的结果值是什么• 有多少个位置使得x的值与y的值相同?[Ccount(x=y)](σ,0)=count(T,)=1注意这里的表达式类型是默认的T。FINKBEINER、SANKARANARAYANAN和 SIPMA42• 在轨迹中x+y的最小值是多少[Cmin(真:x+y)](σ,0)=min(2,3, 4, 5, 8, 7)=2• 在x为y的某个位置上的x值与在x≥y的最近位置上的x值之间的最小差值是多少?[Cmin((x< y:x)U| −|(x≥y:x))](σ,0)= min(σ,4,4,3,5,σ)= 3,其中|−|是两个参数之间的绝对差;如果其中一个参数是零(就像这里序列中的第五个元素的情况一样),它被定义为等于非零参数。• x+y的平均值是多少?虽然这在这里不能直接定义,但我们可以将一个量的平均值定义为它的和与它的计数的对,也就是说,我们定义C avg= C·,·C count.那么x+y的平均值可以写为:[Cavg(true:x+y)](σ,0)=129,6• 在一个区间内z= 1的最大次数是多少,x≤y?[Cmax((z=1)Icount(x≤y))](σ,0)=max(2,2,2,1,σ,σ)=2在下一节中,我们用两个例子来说明我们的规范语言PLE:互斥算法和通信协议。3示例为了说明运行程序的统计数据的收集,我们提出了两个著名的程序和这些程序的相关统计数据的一些例子。这些程序是用[15]的简单编程语言(SPL)编写的,这是一种类似Pascal的语言,具有并发性结构状态被标记为允许显式引用控制位置。3.1互斥图1显示了一个简单的SPL程序,它通过一个信号量[15]确保对两个进程的临界区的互斥访问。request语句仅在r为正时启用,并且在执行时,它将r减1。release语句将r递增1。下面是一些在程序执行期间可以监视的统计信息的示例。• 信号量值:在正确的实现中,r的最大值不应该超过1。 表达Cmax(true:r)可以用来监测是否确实如此。FINKBEINER、SANKARANARAYANAN和 SIPMA43当地x:整数,其中r= 1l0:loop foreverdom0:loop foreverdol1:m1:第二章:非关键请求r关键版本r–||程序2:非关键请求r关键版本r第三章:l4:步骤3:m4:–Fig. 1.程序多路复用-SEM(信号量互斥)• 互斥:表达式Cmax(l3:1时+m3:1时)记录在任何一个时刻临界区中存在的进程的最大数量。 当进程P1位于位置l3时,l3处的谓词为真;类似地,当进程P2位于位置m3时,m3处的谓词为真。如果此表达式的值超过1,则违反互斥。• 偏见:表达C计数(在l32处 在l3处的<$C计数(在m3处的<$2 (m3)返回P1访问临界区的次数与P2访问临界区的次数• 超车:程序多路扫描电镜并不意味着一个进程可以进入临界区,而另一个进程正在等待进入。在实践中,人们可能希望监视进程被超越的次数。表达Cmax((m3时) (在m3))Icont(在l2))记录在P1在l2空闲的任何时间段内,P2访问临界区的最大次数。3.2通信协议图2显示了交替位协议的SPL实现(改编自[16]),交替位协议是一种通信协议,它保证数据通过有损信道传输到接收器,首先在[2]中提出。两个进程,发送者和接收者并行执行。发送方通过异步数据通道dchan发送数据项;每个数据项都伴随有一个布尔值seq(交替位)。然后,它等待接收方在异步确认通道achan上发送一个由一位组成的确认,或者它超时(我们假设语句l4在它被启用后执行一段固定的时间如果接收到ACK并且其值FINKBEINER、SANKARANARAYANAN和 SIPMA44⊥∧¬等于seq位,则发送方假定数据已被接收,并且它继续移动到下一个数据项,同时将seq的值重新封装。如果没有接收到ack,或者其值不等于seq,则再次发送相同的数据项。接收器从dchan中检索数据项。如果伴随的seq位等于它的本地ack位,它通过移动它的指针来接受数据转移到下一个数据项,并对其ACK位进行重传。我们假设achan和dchan都可能丢失项目,但不会损坏或重新排序项目。以下是对该协议的跟踪的一些示例查询。• 成功发送的数据项的总数,可以表示为C计数(在l6处)• 发送与接收:发送者发送的项目数与接收者接收的项目数通过C计数(在l1时为2,在l1时为1)计数(m1时)• 最大重传次数:任何一个数据包的最大重传次数表示为:Cmax((在l1时) (<$at11))Icount(<$at16))该表达式计算在任何时间间隔内执行语句l1的次数,在该时间间隔内,控制不驻留在控制位置l6,在该位置更新当前数据项然后它取所有区间上的最大值• 平均重传:每个数据包的平均重传次数可以用类似的表达式表示平均值(atl62<$atl6)∧π2trueUπ2((at112 (<$at11))Icount(<$at16))在每个位置,Until表达式的计算结果为在最近的间隔中执行的传输数,其中控制不在l6。与atl62atl6的结合确保了我们在计算平均值时只对每个间隔计数一次,因为序列将仅在发送者移动到新数据项的位置处具有非值。4评估统计数据现在我们把注意力转向对给定迹计算类似于[10]的迹检查方法,我们使用交替自动机作为中间表示。我们定义了代数自动机,它在迹上求值时产生一个值然后,我们的构造由两个步骤组成这种方法的动机是将评估策略与CFINKBEINER、SANKARANARAYANAN和 SIPMA45localdchan:channel [1.. []of(integer,boolean)localachan:channel [1.. [布尔值]当地本地的数据我:array [1.. [整数]:integer其中i= 1本地的seq,ack:boolean其中seq=TRUE本地的timeout:booleanwhere<$timeout你好,0中文(简体)循环永远做l:1dchan [i](data[i],seq)L3:阿昌·阿贾克你好,2埃克塞特l4: timeout:=TRUE第五章:if<$timeout超时确认=seq超时第十七章:l6:(i,seq):=(i+1,<$seq)timeout:=FALSE||本地的本地的recvdJ:array [1.. [整数]:integer其中j= 1本地的seq,ack:boolean其中ack=TRUE收件人:0循环永远做m1:程序2:dchan(recvd[j],seq)如果seq=ack,则m3:(j,ack):=(j+1,<$ack)m4: 阿昌塞图二. 程序ABP:交替位协议FINKBEINER、SANKARANARAYANAN和 SIPMA46A一A0,π2(x1,x2)D的1p:A2,fmin(x1,x2)D一个3q:A4ID(x1)图三. 代数交替自动机时间操作符的定义。我们从一些基本的定义开始。4.1代数交替自动机定义1. (Algebras Alternating Automaton)。设X是一个多排序代数签名,X是一组程序变量。设g(x1:τ1,x2:τ2):τ是在两个变量x1:τ1,x2:τ2/∈X上的任何一类τ项,f(x1)是在一类τ1的一个变量x1上的一类τ项.一个代数交替自动机(algebraic alternating automaton,简写为AL)定义如下:A:τ::= p,e终端节点断言p和e:τ∈ T(τ,X)|A:τ1,f瞬态节点|A:τ1μgA:τ2结合|A:τ1μgA:τ2析取|f(A:τ1)功能应用请注意,两个自动机的任何合取或析取运算的排序是注释该运算的项g(x1,x2)的排序实施例3. 图3显示了一个在签名上的函数的例子,其中包含单个排序nat,一个用于未定义值的单个常量nat,以及函数π1,π2,fmin和id。没有出边的节点表示终端节点;有出边的节点是瞬时节点,f,边导致。带弧的菱形表示两个分支的结合,没有弧的菱形表示分离。定义2. (价值)。给定迹σ:s0,.,sn−1,长度为n,位置为in,则A的值由函数eval(A,σ,i)定义FINKBEINER、SANKARANARAYANAN和 SIPMA47√一A.A.如下给出如果(σ,i)qp,则[σ(i)](e)eval(p,e,σ,i)=否则f(eval(A1,σ,i+1))ifeval(A1,σ,i+ 1)/=eval(A1,f,σ,i)=g(eval(A1,σ,i),eval(A2,σ,i))eval(A1<$gA2,σ,i)=如果eval(A1,σ,i)n和eval(A2,σ,i)/= n我的智慧g(eval(A1,σ,i),eval(A2,σ,i))eval(A1<$gA2,σ,i)=如果eval(A1,σ,i)/=或eval(A2,σ,i)/=我的智慧eval(f(A1),σ,i)=f(eval(A1,σ,i))任何自动机的值被定义为在迹线之外的任何位置处的值为n,也就是说,对于长度为n的迹线,任何位置i≥n的值为n。还要注意的是,对于函数应用,f可以具有将非k值转换为k值的能力,反之亦然。实 施例 4. 再 次 考虑图3中的自动机A0,设V是具有载体集A = N<${\displaystyle\mathbb {A}}的代数,其中N是自然数的集合,函数π1(x1,x2)= x1,π2(x1,x2)= x2,fmin是整数上的最小函数,如果两个参数都是\displaystyle\mathbb {A},则给出\displaystyle\mathbb{A} , 如 果 一 个 参 数 都 是 \displaystyle\mathbb {A} , 则 给 出 非\displaystyle\mathbb{A}的值。的参数是,和id的身份功能。我们在图4所示的跟踪tr上计算0。跟踪显示了每个位置上两个变量x和y的值,以及两个断言p和q对程序变量的满足程度(由表示)。0除以tr的求值计算如下否则FINKBEINER、SANKARANARAYANAN和 SIPMA48一位置0123456断言p√√√√断言q√√√√√程序状态103,1分100,200美元2012年2月1日2012年2月3日100,3002016年6月2日1,000日元图四、示例程序跟踪和断言p和q的满足位置01234567a0级12⊥⊥⊥⊥0⊥的1312⊥⊥⊥1⊥一个212⊥3⊥00⊥一个312⊥3⊥20⊥一个42⊥⊥⊥⊥0⊥⊥图五. eval的结果如果eval(A1,tr,i)/=,则取eval(A2eval(A0,tr,i)=(i)(x)如果 tr(i)qpeval(A1,tr,i)=0f(eval(A3,tr,i),eval(A4,tr,i))eval(2,tr,i)=min如果eval(A3,tr,i)/=0或eval(A4,tr,i)/=0我的智慧tr(i)(y)iftr(i)qqeval(A3,tr,i)=0eval(A4,tr,i)=id(eval(A0,tr,i+1))=eval(A0,tr,i+1)eval的结果值如图5所示。请注意,自动机A0对应于公式A0:q:yIminp。正如预期的那样,在p或q为假的位置的否则否则否则FINKBEINER、SANKARANARAYANAN和 SIPMA49⊥ ⟨A⟩A一位置0、1和6处的值是y在p为真的区间上的最小值。4.2痕迹评价评价可以向前或向后进行。前一种策略是从开始到结束遍历轨迹。自动机递归地进行评估,如定义2中的方程所示。不幸的是,前向求值的复杂性在跟踪长度上是指数级的。正如Rosu和Havelund [17]指出的那样,通过向后遍历迹线可以避免这种情况。我们首先赋值所有节点的形式,f。 一个自动机在一个位置in仅取决于其子自动机的值,<位置,或者在形式为f的节点的情况下,在迹线的下一位置中的值(如果有的话)上。因此,可以执行向后评估,同时仅存储当前和下一位置处的所有自动机的值。5将规范转换为自动机在本节中,我们将描述如何将查询语言的公式转换为上一节中描述的代数交替自动机。我们假设代数签名包含一个二元函数fα,用于每个聚合统计量α的增量计算。此外,为了对否定运算符建模,我们假设对于其中的每个常数c,存在一个函数对c取反,定义为求反c(v)=⊥ifv⊥c否则我们还假设每个排序都有恒等函数id。给定一个统计实验,其相应的统计实验A(A)构造如下。对于状态表达式和布尔连接词:AA(:ej)= ⟨ψ,ej ⟩AA(101克)(2)=AA(1)gAA(2)AA(101克)(2)=AA(1)gAA(2)AA(<$c1)=求反c(AA(1))对于时态运算符:AA(2f())=AA(),f<$AAA(1U<$2)=f(A1).FINKBEINER、SANKARANARAYANAN和 SIPMA50⟨⟩⊥一一⊥A0:f( A1)A1:收集(x1,x2)DA2:πx1,π2(x2)πDAA(1)id(x1)AA(102)见图6。自动机的构造与A1=(AA( 1)x1,π2(x2)A1,id)collectAAA( 2)其中函数collect定义为nπ1(x1),x2ifx2center(x1,x2)=否则为10x1第一个参数x1是一个元组,包含当前状态下的值x1和最接近跟踪中下一个位置的x2状态下的值x2第二个参数x2表示当前状态下的值x2如果在当前状态中存在一个非-num2值,则丢弃旧的num2值,并选择当前值。U自动机的构造如图6所示自动机A2计算一个元组,该元组由轨迹中最接近下一个位置的值和当前值组成。节点A0计算与1相同的元组,除了它将函数f应用于元组,如图所示。给定一个集合表达式,相应的合取和析取的表达式是这样构造的。无条件和区间收集的构造如下:AA(Cα())=AA()<$f α<$AA(Cα()),id<$AA(<$Iα<$) =(<$AAA(<$Iα<$),id<$$>fαAA(<$))<$π1AA<$这些自动机的构造如图7所示。在Cα运算符的构造中,用恒等函数id(x1)标记的节点收集迹的下一状态中的统计值(其FINKBEINER、SANKARANARAYANAN和 SIPMA51在跟踪结束时被初始化为“0”)实施例5. 图8显示了公式的表达式C平均值(在l6ππ2处2 ((在l1点02分在11)Icount(在16),在3.2节的交替位协议示例中计算重传次数的公式6实验结果第4.2节中的求值算法已在Java中实现,利用STeP(Stanford TemporalProver)系统[3]中现有的表达式解析和命题简化软件模块。第3.1节的互斥和交替位协议示例中描述的公式以及这些示例中的一些其他公式通过模拟SPL程序产生不同长度的轨迹。在每一个位置,执行随机选择的过程的单个步骤。然后,我们测量了所花费的时间进行评估的手段向后评估的痕迹长度不同。结果如图9所示。这些时间是在运行Redhat Linuxv7.0和Sun JDK 1.4的1.7GHz PC确认我们要感谢匿名的评审人,他们仔细阅读了我们的意见书,并提出了许多建设性的意见和建议。A0:π1(x1,x2)DdA1:fα(x1,x2)A2:fα(x1,x2)dAA(102)id(x1)AA()id(x1)AA(1)图7.第一次会议。 操作员1Iα2(左)和Cα(右)的自动机构造。FINKBEINER、SANKARANARAYANAN和 SIPMA52fcount(x1,x2)1x1,x2x2dDdf(x1,x2)id(x1)id(x1)π1(x1,x2)did(x1)在16:Tπ1(x1,x2)df计数D否定T(在16:T)id(x1)d在11:Tid(x1)否定T(在l1:T)见图8。 C平均值[在l6ππ2处]的平移 2 ((在l1点02分 <$at11)Icount(<$at16))]引用[1] 巴尔河,S. L. Torre,K. Ettessami和D. Peled,用于模型测量的参数时序逻辑,在:J.Wiedermann,P. van Emde Boas和M. Nielsen,editors,ICALP159-168.[2] Bartlett,K.,R. Scantlebury和P. Wilkinson,关于半双工链路上的可靠全双工传输的说明,ACM通信12(1969),pp. 260-261。[3] 比约纳,N. 美国,A. 布朗,M. 科洛恩,B。 Fink beiner,Z. Manna,H. B.Sipma和T. E. Uribe,反应系统的时态属性:STeP教程,系统设计中的形式化方法16(2000),pp.227-270[4] Bruns, G. 和 P.Godefroid , Temporal logic query checking , in : Proc.16thIEEE Symp. 在Comp.Sci. (2001),pp. 409-417[5] Chakrabarti,P.,P. Dasgupta,J.Deka和S. Sankaranarayanan,Min-max computation tree logic , Arti Ficial Intelligence127 ( 2001 ) ,pp.137-162.[6] Chandra,A. K.,D. C. Kozen和L. J.Stockmeyer,Alternation,J.ACM28(1981),pp. 114-133FINKBEINER、SANKARANARAYANAN和 SIPMA53超车最大时间临界最小最大r临界数∀1000 1000800 800600 600400 400200 200010000 20000 30000 4000050000010000 20000 30000 40000 50000迹线长度[状态]见图9。互斥程序(左)和交替位协议(右)上查询的运行时间。[7] Drusinsky,D., 时间漫游者和ATG漫游者,在:K。 哈夫隆,J. Penix和W. Visser,editors,SPIN Model Checking and SoftwareVerification,7th Int'l SPIN Workshop,LNCS 1885(2000),pp.323-330[8] Emerson,A.,A. Mok,A. P. Sistla和J.Srinivasan,定量时间推理,实时系统4(1993),pp. 334-351.[9] Emerson,A.和R.Trer,Generalized quantitative temporal reasoning:Anautomata-theoreticapproach , TAPSOFT : 7thInternationalJointConference on Theory and Practice of Software Development,1997。[10] 芬克拜纳湾和H. Sipma,Checking finite traces using alternating automata,in : K. Havelund 和 G. Rosu , editors , Electronic Notes in TheoreticalComputer Science , Electronic Notes in Theoretical Computer Science55(2001),pp.1比17[11] 格雷厄姆,S。 L.,P. B. Kessler和M. K. McKusick,gprof:a call graphexecution profiler,in:SIGPLAN Symposium on Functional Construction,1982,pp. 120比126[12] Havelund,K.,使用运行时分析指导java程序的模型检查,在:K.Havelund , J.Penix 和 W. Visser , editors , SPIN Model Checking andSoftware Verification,7th245- 264。[13] Havelund,K.和G. Rosu,editors,[14] 曼纳角,巴西-地和A. Pnueli,Specification and Verification of ConcurrentPrograms by -automata,in:B. Banieqbal,H. Barringer和A. Pnueli,编辑,规范中的时序逻辑,LNCS中的第398号,Springer-Verlag,柏林,1987年重传延迟最大包吞吐量运行时间[ms]FINKBEINER、SANKARANARAYANAN和 SIPMA54pp. 124-164,也在Proc.14th ACM Symp.的Prog。浪,Munich,Germany,pp.1987年1月1日[15] 曼纳角,巴西-地和A. Pnueli,[16] 曼纳角,巴西-地和A. Pnueli,[17] 罗苏湾和K. Havelund,Synthesizing dynamic programming algorithms fromlinear temporal logic formulas,2001,已提交出版。[18] Vardi,M.是的,Alternating automata and program veri fication,in:J.van Leeuwen,editor,Computer Science Today. 最近的趋势和发展,LNCS 1000,Springer-Verlag,1995页。471-485.[19] Vardi,M.是的,一个自动机理论的方法,以线性时序逻辑,在:F. Moller和G. Birtwistle,编辑,并发逻辑。结构与自动机,LNCS 1043(1996),pp。238-266。
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功