没有合适的资源?快使用搜索试试~ 我知道了~
理论计算机科学电子笔记157(2006)77-94www.elsevier.com/locate/entcs软件模型检测Murray Stokely1谷歌Sagar Chaki2美国匹兹堡卡内基梅隆大学软件工程学院JoéelOuaknine3英国牛津大学计算实验室摘要在本文中,我们研究如何形式化的软件验证系统可以通过利用并行分配在最弱的前提条件计算得到改善。我们首先介绍现代软件验证系统。具体来说,我们回顾了使用反例引导的抽象细化(CEGAR)构建软件抽象的方法。首先提出了一个经典的NP完全并行指派问题,然后通过增加一个额外的限制条件,得到了一个特殊的情形,使得该问题可以用O(n2)的算法来处理.并行分配问题,然后讨论的背景下,最弱的前提条件计算。在这种特殊的情况下,语句可以被假定为真正并发执行,我们表明,任何序列的简单的分配语句没有函数调用可以转化为一个等效的并行分配块。结果压缩成一个并行的形式与此算法的赋值语句的各种软件应用程序。所提出的算法在ComFoRT推理框架中实现[12],并用于衡量真实软件系统验证的改进。事实证明,这种时间上的改进对许多类软件都是非常重要的。保留字:静态分析,软件模型检测,谓词抽象,并行赋值。1电子邮件:mstokely@google.com2电子邮件:chaki@sei.cmu.edu3电子邮件:joel@comlab.ox.ac.uk1571-0661 © 2006 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2006.01.02478M. Stokely等人理论计算机科学电子笔记157(2006)771介绍在本文中,我们研究如何通过利用并行赋值语句来改进正式的软件验证系统具体来说,我们对在用通用编程语言(如C或Java)编写的程序上执行这种静态转换感兴趣。修改后的程序然后用扩展的模型检查工具进行验证,该工具与定理证明器和决策程序相互作用,以推理软件抽象。验证工具,如MAGIC(C中程序的模块分析)[14,4]采用了一个称为C计数器示例-G引导抽象R(CEGAR)[8,5]的框架,以迭代方式创建程序的更精确的抽象,直到可以证明所需的属性或真正的反例。Ple生成。MAGIC提供了一个组合框架,可用于根据一系列安全性和活性规范验证并发C程序[5,6,7]。在此上下文中,每个原子分配被表示为软件模型中的状态,然后使用特定的Buu-hi自动机来获取该模型的carrierproduct。我们的方法是分析控制流图(CFG),并结合成并行分配块顺序分配。由于迭代的CE-GAR框架可以导致在CFG的相同部分上的大量通过,因此通过该压缩过程获得的累积节省可以导致显著的加速。从数学上讲,最弱前提条件计算(通常涉及与定理证明器的交互)变得更加有效。此外,在并发C程序的上下文中,单个组件中状态数的减少对整个系统的状态数具有倍增效应1.1纲要在第2节中,介绍了并行赋值语句。首先考虑了经典的NP完全并行指派问题,然后在此基础上增加了一个并行分配问题,然后讨论的背景下,最弱的前提条件计算。在这种特殊的情况下,可以假设状态真正并发执行,我们发现一个更好的算法压缩多个顺序的赋值语句到一个单一的并行赋值。在第3节中,给出了实验,这些实验显示了可以从广泛的软件类别中实现的分配压缩算法-M. Stokely等人理论计算机科学电子笔记157(2006)7779第2节中的算法也已在ComFoRT推理框架中实现,结果显示了模型检查的时间和存储空间的改进。最后,我们在第4节讨论了未来的研究方向。2平行分配赋值指令的序列被称为直线程序或线性块。 并行赋值是一种允许将多个变量更新为单个原子操作的构造。为了验证的目的,我们感兴趣的是识别直线代码中的顺序赋值语句此操作将顺序赋值语句的多个控制点新的并行赋值控制点由赋值语句列表组成。在本节中,我们考虑一些可能的方法来找到适合并行分配的分配序列。• 在2.1节中,我们要求并行赋值块中的每个赋值语句可以以任何顺序执行,而不需要中断该并行块中的其他赋值语句在这种情况下,示例x,y:=y,x不是有效的并行赋值,因为x:=y;y:=x是不同的当verx/=y时,从y:=x;x:=y。• 在2.2节中,我们通过不允许赋值语句的重新排序,给经典的并行赋值问题增加了一个额外的限制。这就产生了一个易于处理的问题,可以得到有效的算法。• 在2.3节中,我们看到在最弱前提条件计算的上下文中,我们有额外的可扩展性。我们可以假设并行赋值块中的赋值必须全部并发执行。2.1经典并行赋值经典的并行分配问题由Garey和Johnson [11]描述如下。实例:设置V ={v1,v2,.,vn},设置A ={A1,A2,.,An}的赋值,每个Ai的形式为“v i ← op(B i)”,对于某个子集B i <$V,以及正整数K。80M. Stokely等人理论计算机科学电子笔记157(2006)77A1:v1:=op(B1)A2:v2:=op(B2)A3:v3:=op(B3).An:vn:=op(Bn)问题:是否有一个排序vπ(1),vπ(2),.,vπ(n)使得i的值至多有K个,1≤i≤n,其中vπ(i)∈Bπ(j),对某些j>i?作业#1任务#2任务#3作业#4任务#5. . .分配编号NFig. 1. 顺序存储转换为并行存储因此,我们将顺序赋值语句压缩成尽可能少的并行赋值语句的问题将等价于找到满足K的最小值的优化问题。不幸的是,Sethi [16]通过从反馈节点集问题中在下一节中,我们将考虑一个贪婪算法,该算法识别并行赋值,并附加了一个限制,即顺序赋值必须相邻。也就是说,不允许重新排序分配,即使这不会破坏数据依赖性。在第2.3节中,我们考虑了最弱前提计算中语句的特殊情况,以便更好地压缩单个赋值语句。2.2可处理的通用并行赋值现在考虑经典并行赋值问题的修改版本,其中赋值语句的重新排序是不允许的。上一节介绍的实例仍然使用,但问题变成了:问题:i,1≤i≤n,vi∈Bj,是否至多有K个值对于一些j> i?图1说明了从顺序到并行赋值语句的转换,包括在经典的并行赋值问题中允许的重新排序图2显示了一个类似的转换,其中附加了防止重新排序的条件。并行分配块#1并行分配块#2并行分配块#3M. Stokely等人理论计算机科学电子笔记157(2006)7781作业#1任务#2任务#3作业#4任务#5. . .分配编号N图二. 顺序存储转换为并行存储,无需重新排序。2.2.1分析对于n个赋值Ai中的每一个,并且对于每个j,ij≤n,我们必须测试是否v∈B。 因此,我们需要d(n−1)+(n−2)+(n−3)+。 . . +3+2+1=(n−1)2i j2设置包含操作。 如果<对于某个常数C,每个{\displaystyle\mathbb} j{\displaystyle\mathbb} C,则设时间复杂度为O(n2)。回想一下,n将不是整个程序中控制位置的数量。相反,n是控制流程图的一个节点中的赋值语句的顺序列表中的赋值数量。因此,n永远不是一个很大的数。2.2.2执行为了推理赋值语句右侧的变量,我们需要比控制流程图提供的信息更多的信息解析树[1]提供了表达式级的语法信息,我们需要对各个赋值进行推理然而,我们对整个程序源代码的解析树不感兴趣相反,我们希望控制流程图为每个单独的赋值语句维护一个指向解析树的指针给定这样一个解析树,可以很容易地在赋值语句的左侧(LHS)和右侧(RHS)建立变量以这两个列表作为输入,在算法1中描述了创建利用并行赋值语句的新CFG的过程。这个算法访问控制流图中的每个节点,然后遵循贪婪策略来建立并行赋值语句列表将CFG节点中的每个赋值语句与并行赋值块中的赋值运行列表进行比较如果赋值状态不适合与当前并行赋值块中的所有其他赋值进行并行赋值,则完成该赋值块并开始新的赋值块。该算法依赖于另一种算法来确定作为-并行分配块#3并行分配块#1并行分配块#4并行分配块#282M. Stokely等人理论计算机科学电子笔记157(2006)77赋值语句S1可以被包括在并行赋值块P1中。算法2,canadelise,说明了在简单的情况下,只有两个赋值语句的决策过程算法1 Atomise接受一个CFG,并在可能的情况下循环分配状态,将相邻的分配组合成并行的分配块输入:A CFG输出:一个已并行化赋值语句的CFG对于所有N∈CFG,如果N包含语句列表S,则设平行表=第一个s∈S。对于所有语句s ∈ S,后继语句sJ。doifcanadelise(parallel list,sJ)then将sJ附加到并行列表。其他将并行列表追加到新列表用sJ初始化并行列表。如果结束,则结束将并行列表追加到新列表用新列表替换CFG节点N中的语句列表S。如果结束,则结束2.3并发并行分配前两节中描述的算法基于两个假设。第一个假设是我们不能改变各个赋值语句的形式。第二个假设是,我们必须保证并行块中的赋值可以以任何顺序执行,而不需要检查结果。事实上,在为最弱前提条件计算构建并行赋值的上下文中,这些假设请考虑以下示例:x:=yz:=x算法1将不能组合这两个赋值语句,因为一个的左手边存在于另一个的右手边然而,可以在不改变第二赋值的情况下改变第二赋值。M. Stokely等人理论计算机科学电子笔记157(2006)7783算法2Canaderelise接受一个适合于解析的赋值列表检查分配和附加分配,并确定新分配是否可以安全地添加到现有并行分配块。输入:赋值列表l和赋值语句s1.输出:关于语句是否可以并行执行的布尔答案。设LHS(s)是一个函数,返回单个赋值s左侧的变量。让LHS List(l)是一个函数,返回赋值列表l中赋值左侧的变量。让RHS(s)是一个函数,返回赋值s右侧的变量列表。让RHS List(l)是一个函数,返回赋值列表l中赋值右侧的变量。ifLHS(s1)∈RHSList(l)orrRHS(s1)LHSList(l)/=thenreturnfalse其他返回trueend if块的结果x:=yz:=y通过这种修改,我们现有的算法将能够将这两个分配组合成一个并行分配块。同样清楚的是,结果与原始赋值序列完全相同一般来说,我们可以定义一个函数,它接受一系列简单的赋值语句S,没有指针和函数调用,并返回一个等效的并行赋值语句。归纳证明单一赋值的基本情况S={s1}是空真的。f(S)=S是函数。现在,让S是一个序列的n个顺序赋值语句,让S+表示序列S和S中最后一个赋值语句的后继,SJ。假设存在一个函数g,可以将赋值序列S转换为一个等价的并行赋值g(S)。(归纳假设)我们构造一个新的函数h(S+)如下:对于所有v∈RHS(sJ),如果v=LHS(s∈g(S)),则ReplacevinsJwiththRHS(s)84M. Stokely等人理论计算机科学电子笔记157(2006)77如果结束,则结束输出(g(S),sJ)通过SJ上的置换构造,保证了它可以与g(S)在一个平行块中组合,从而归纳地证明了我们的结果Q使用并发并行赋值时,所有赋值语句的左侧会同时更新这意味着并行赋值块中所有变量的实例都引用了进入并行块之前的赋值如果一个赋值语句需要在另一个赋值语句之后利用变量的赋值,那么这个赋值语句必须用前面证明中概述的过程重写作为一个最终的说明,考虑以下分配列表:int x =1;y =x;u =2;int v =u;经典的并行赋值问题试图找到赋值语句的最佳顺序,以便找到并行赋值语句的最小集合,例如:x = 1 |||u = 2;y = x |||int v= u;然而,在最弱前提条件计算的上下文中,我们可以根据需要修改赋值语句,以确保所有语句都可以合并到一个并行赋值块中:x= 1 |||intsum = 1; |||u = 2 |||intv = 2;2.3.1执行上一节中描述的ConcurrentAtomise算法在算法3中呈现。2.4并行赋值与最弱前提对于一个赋值语句s和谓词φ,最弱的前提条件WP(s,φ)是通过用赋值语句的右侧替换所有出现在s左侧的条件而得到的。这可以用替换符号φ[LHS/RHS]表示。当s是一个并行赋值时,这个替换操作自然会扩展M. Stokely等人理论计算机科学电子笔记157(2006)7785算法3 ConcurrentAtomise接受一个CFG并在as上循环赋值语句根据需要修改相邻的赋值,以允许它们组合成单个并行赋值块。输入:A CFG输出:一个已并行化赋值语句的CFG对于所有N∈CFG,如果N包含语句列表S,则设平行表=第一个s∈S。对于所有语句s∈S,后继语句sJ。对于所有v∈RHS(sJ)do如果v=LHS(s∈Paral lel列表,则ReplacevinsJwiththRHS(s)如果结束,则结束将sJ附加到并行列表。端将CFG节点N中的语句列表S替换为并行列表。如果结束,则结束分段块。φ中出现在s中赋值左侧的每个变量都被替换为相应的右侧。例如,并行赋值a,c:=b,a和相同谓词φ的最弱前提将被表示为φ[a/b,c/a]。3实验评价我们在卡内基梅隆大学的ComFoRT推理框架和伯克利CIL [15]工具中实现了原子化算法。这个实验的目的如下。第一个目标是确定在几个不同的应用领域中,对于真实的程序,赋值语句可以压缩多少第二个目标是确定这种压缩实际上是否会加速模型检查过程。最终的目标是验证模型检查可以从并行赋值语句的使用中获益最多的软件类别3.1分配压缩结果在本节中,我们描述了我们在上述第一个目标的背景下的结果,即, 检查Atomiser和ConcurrentAtomiser算法在实际软件中压缩分配控制位置的有效性86M. Stokely等人理论计算机科学电子笔记157(2006)77(b)第(1)款(一)图三. (a)一个由四个简单赋值语句组成的序列,以及在CEGAR循环中计算的相关最弱前提条件计算。(b)一个较短的并行赋值语句序列,具有较少的相关最弱前提条件计算。源代码.本节中的结果是使用Berkeley CIL解析器和我们的并行赋值压缩器获得的。简单赋值语句序列的相对长度和频率随不同的软件应用程序域而变化选择下面的实验是因为它们代表了广泛的相关软件应用程序。3.1.1Unix系统软件第一个基准测试集包括来自FreeBSD的Unix系统软件6.0 操 作 系 统 。 选 择 的 实 用 程 序 包 括 文 件 系 统 一 致 性 检 查 实 用 程 序(fsck)、ifconf ig、mount、ping、bdes、gzip和grep。表1说明了结果。第一列Utility提供了实用程序的名称第二列,源文件,提供源文件的名称第三列“行数”列出源代码WP(x:=y,Φ)WP(a:=b,Φ)WP(y:=z,Φ)WP(c:=b,Φ)WP(x,a:=y,b, Φ)WP(y,c:=z,b, Φ)y,c:=z,bx,a:=y,bx:= ya:= by:= zc:= bM. Stokely等人理论计算机科学电子笔记157(2006)7787实用源文件LOCLoc1Loc2Loc3fsckfsck.c12081027262ifcon文件ifcon fig.c2335174140122ifcon文件af inet6.c1436766156山芒特ufs. c2271065平ping.c3242312200181化二苯醚bdes.c2357284253220gziptrees.c1221299192147gzipdeadenate.c 4771036559gzip在埃塞俄比亚。c1491377254169grepsearch.c2033239191181总数16027 197614341202平均压缩百分之七十二点六百分之六十点八表1Unix系统软件文件。具体来说,这意味着在C预处理器运行并执行CIL转换之后的代码行,但不计算预处理器插入的任何#line指令。第四列Loc1列出了源文件中简单赋值语句的数量。数字列Loc2列出了使用Atomiser算法生成的新源文件中赋值语句的数量。第六列Loc3列出了使用ConcurrentAtomiser算法生成的新源文件中的赋值数量。3.1.2图形库第二个基准集包括流行的PNG和JPEG库,大多数商业和开源软件都使用这些库来读取和写入这些流行的图形文件格式。表2展示了libpng v1.2.8和libjpeg v6b的最大源文件的赋值压缩结果3.1.3结果总结在本节测试的软件主体上,Atomiser算法将赋值语句控制点的数量减少到原始总数的63%ConcurrentAtomiser算法提供了另外10%的控制点减少。88M. Stokely等人理论计算机科学电子笔记157(2006)77图书馆源文件LOCLoc1Loc2Loc3pngpng.c1108876057pngpnggccrd.c2835511262229pngpngrtan.c62211859930629JPEGjmemmgr.c 1232252174160JPEGjquant1.c136125712596JPEGjquant2.c1803466264176JPEGtransupp.c3826637414345总数18386 406922291692平均压缩百分之五十四点八41.6%表2图形库的赋值压缩3.2模型检查结果ComFoRT推理框架[12]使用模型检查来预测软件是否满足特定的安全性和可靠性要求。模型检查引擎源自MAGIC [5],MAGIC是卡内基梅隆大学模型检查小组我们将atom-iser算法集成到ComFoRT中,并在Windows设备驱动程序、OpenSSL和Micro-C OS基准测试的集合上运行它。这些基准测试显示了赋值压缩在时间和内存空间方面的改进3.2.1OpenSSL第一组基准测试在OpenSSL源代码上运行。OpenSSL库实现了安全套接字层(SSL v2/v3)和传输层安全(TLS v1)协议。它被许多不同计算平台上的Web浏览器、SSH客户端和其他安全网络应用程序广泛使用表3提供了OpenSSL基准测试的模型检查结果。服务器测试是具有相同源代码但规格不同的四个基准的几何平均值。客户端测试是具有相同源代码但规格不同的两个基准的几何平均值。Srvr-Clnt测试是具有相同源代码但不同规格的十六个基准的几何平均值。每个测试在三种不同的模型检查条件下运行(i) 没有分配并行化;M. Stokely等人理论计算机科学电子笔记157(2006)7789名称LOCLoc1Loc2Loc3Time1Time2时间3Mem1Mem2Mem3服务器24832071721719.88.88.4135.3136.2133.8客户端248417514514417.511.712.4128.9128.1127.7Srvr-Clnt位置如上165.8136.7128.4201.1194.7192.3表3使用ComFoRT模型检查器+Atomise的OpenSSL基准测试名称LOCLoc1Loc2Loc3Time1Time2时间3Mem1Mem2Mem3cdaudio1017126131447129852.652.753.0272.6264.0269.6diskperf4824118771961715.915.815.7176.3176.3175.0奥皮9579347819571845130.4130.5129.3468.8468.8470.4kb filtr39055603312861.91.91.8129.1128.7126.3parclass2662328401649145074.573.772.3335.5335.5340.0parport12431463429352409384.5381.1375.61102.31102.31127.2表4Windows设备驱动程序基准测试ComFoRT模型检查器+Atomise(ii) 与Atomiser算法并行(单个分配不变)(iii) 与ConcurrentAtomiser算法并行化(根据需要单独更改)对于上面的每个条件,列出了分配的数量(Loc)以及以秒为单位的时间(Time)和模型检查所需的内存MB数3.2.2Windows设备驱动程序第二组ComFoRT基准测试在一组Windows设备驱动程序上运行结果见表4,格式与上一节相同。请注意,虽然实现了显著的分配压缩,但模型检查时间没有实质性改善。3.2.3Micro-C操作系统最终的ComFoRT基准测试在Micro-C OS上运行。结果见表5。相同的源代码用于两个不同的规范。一个描述安全属性,另一个描述活动属性。该表中最引人注目的结果可能是这样一个事实,即安全性属性的模型检查并没有通过赋值压缩得到改进,但Liveness属性验证的速度得到了显着提高。3.2.4结果总结使用两种雾化器算法中的任一种,在控制位置的数量方面肯定存在压缩一般来说,90M. Stokely等人理论计算机科学电子笔记157(2006)77名称LOCLoc1Loc2Loc3Time1Time2时间3Mem1Mem2Mem3安全627926991789158935.535.736.0229.2229.2223.5活跃度位置如上182.2144.4134.4272.3260.6260.4表5Micro-C OS基准测试ComFoRT模型检查器+Atomise没有压缩,并且Atomiser算法比Atomiser和ConcurrentAtomiser算法之间的压缩更重要。模型检查器的实际性能在许多情况下确实有所提高,特别是对于SSL和Micro-C OS。这种改进在时间上是显著的,但在空间上有点微不足道设备驱动程序缺乏改进可能是因为完成验证所需的谓词数量相对较少这意味着状态的数量不会像其他基准那样随着控制位置数量的减少而急剧减少用其他例子进行更多的实验可能会为这些观察提供额外的支持。3.3意见在检查数据之后,可以看到两种情况有助于观察到的使用Atomiser算法的模型检查时间的加速• 组合性与偏序约简• 物业面积3.3.1组合性与偏序约简异步系统(如OpenSSL Srvr-Clnt基准测试)通常使用交错计算模型来描述[10]。并发事件是通过允许它们以相对于彼此的所有可能的顺序执行来建模的。图4显示了两个独立组件中的每个组件上的3个转换(赋值语句)。这里我们假设每个线程中的变量不是共享的。第一个分量的跃迁标记在1和3之间,第二个分量的跃迁标记在4和6之间每个组件的控制顺序是固定的,但不能保证两个组件之间的转换的相对顺序或交错模型检查器并不知道交错无关紧要,因此它将尝试所有可能的两个交错进行模型检查。表示所有可能的过渡交错的晶格如图5所示。使用并行赋值语句,图4中的6个转换将减少为图6中的两个转换。图7显示了具有并行分配的更简单的关联格。ConcurrentAtomiser算法允许特殊情况下的部分降阶,以消除M. Stokely等人理论计算机科学电子笔记157(2006)77911424153425164352615362631x:=32y:=43 z:=5456图四、组合模型的两个组件中的赋值状态图五、没有平行赋值的两个分支中的转换的可能路径的格不同的等价交织排序[9]。这具有戏剧性地减少对定理证明器的所需调用的数量的效果,以推理作为最弱前提条件计算的一部分的谓词。3.3.2物业面积表5中的Micro-C OS基准测试提供了另一个重要的例子,说明本文中提出的算法特别有用。92M. Stokely等人理论计算机科学电子笔记157(2006)77212211 x,y,z:= 3,4,5见图6。 组合模型见图7。 平行赋值的两个分支的转移的可能路径的格。安全性和活跃度属性都是顺序的单分量系统,因此减少前一节中描述的交织路径没有好处在该过程中,构造了一个用于财产登记的Bu?c?i?a?然后,该自动机与软件的抽象模型同步,以获得新的产品自动机,在该产品自动机上执行空性分析。考虑安全属性M| =&“locks unlocks alternate”和事件字母表= { a,b,c,lock,unlock }:a、b、c假设我们的系统也有一个抽象模型a、锁S1S2解锁解锁锁S3a,b,c,锁M. Stokely等人理论计算机科学电子笔记157(2006)7793S1、U1一S1、U2锁U1 U2一解锁锁BU4 U3然后我们可以用卡氏积来定义一个新的修改的Kripke结构:...通过这种方式,我们的LTL属性被转化为Carbohydrate产品的空度测试。有了这种乘积构造,人们发现这个性质的布希自动机的大小充当乘积自动机大小的缩放因子对于Micro-COS安全方案,布希自动机相对简单,只有4个状态。然而,对于活性属性,自动机有51个状态。因此,抽象软件模型大小的任何小的减少都将通过该因子进一步改进这解释了为什么相同级别的赋值压缩对活性基准有显著影响,但对安全基准没有影响。看看通过将这些算法实现到其他模型检查工具(如BLAST [3]和SLAM[2])中,可以在时间和内存方面获得哪些改进,这将是很有趣的。4今后工作这项工作的重点是在抽象和建模步骤发生之前,对软件然而,这是对软件进行更广泛的可能改进的一部分94M. Stokely等人理论计算机科学电子笔记157(2006)77模型检查过程。其他静态变换可以使得能够进一步减少必要状态的数量。例如,最近关于路径切片的工作[13]说明了控制流程图的静态分析如何从抽象模型中删除大量不必要的状态。在现代软件验证工具中,偏序约简也可能有更富有成效的应用引用[1] A.阿霍河Sethi和J. Ullman。出版商:原则,技术和工具。艾迪生-韦斯利,1986年.[2] T. Ball和S.拉贾马尼SLAM项目:通过静态分析测试系统软件。在POPL。ACM Press,2002.[3] 爆炸网站 http://www-cad.eecs.berkeley.edu/rupak/blast网站。[4] S. Chaki,E. Clarke,A. Groce,S. Jha和H.维斯C中软件组件的模块化验证在ICSE。IEEE计算机学会,2003年。[5] S. Chaki,E. Clarke,A. Groce,J. Ouaknine,O. Strichman和K.约拉夫有效验证顺序和并发C程序。系统设计中的形式化方法,25(2-3):129-166,2004年。[6] S. Chaki,E. M. Clarke,O. Grumberg,J. Ouaknine,N. Sharygina,T. Touili和H.维斯分支时间规范的状态/事件软件验证。在IFM。Springer LNCS,2005年。[7] S. Chaki,E. M. Clarke,J. Ouaknine,N. Sharygina和N.辛哈使用状态、事件和死锁的并发软件验证。Formal Aspects of Computing(to appear),2005.[8] E. Clarke,O. Grumberg,S. Jha,Y. Lu和H.维斯用于符号模型检验的反例引导抽象细化。J.ACM,50(5):752[9] E. Clarke,O. Grumberg,M. Mackay,和D.佩尔德。使用偏序技术减少状态空间。J.软。技术工具转移,2:279 -287,1999年。[10] E. Clarke,O. Grumberg和D.佩尔德。模型检查。MIT Press,1999.[11] M. Garey和D.约翰逊 计算机和顽固性。 贝尔电话实验室,1979年。[12] J. Ivers和N.沙瑞金娜ComFoRT:一个模型检测推理框架。技术报告CMU/SEI-2004-TN-018,卡内基梅隆软件工程研究所,2004年。[13] R. Jhala和R.马宗达 路径切片。 在PLDI。ACM Press,2005.[14] 魔术网站 http://www.cs.cmu.edu/chaki/magic.[15] G. Necula,S.McPeak,S. Rahul和W.威默CIL:用于分析和转换C程序的中间语言和工具。在CC,2304卷。Springer LNCS,2002年。[16] R.塞西关于实现并行赋值指令的注记。Information Processing Letters,2:91
下载后可阅读完整内容,剩余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直接复制
信息提交成功