并发程序验证（精选6篇）
并发程序验证 篇1
0概述
软件事务内存(STM)[1,2,3]是基于软件的事务内存实现,近些年的研究[4,5,6]表明,STM不仅能有效利用现已大量投入使用的多核多处理器,而且有希望像垃圾收集器一样被广泛应用在现代编译器的开发中,为自动实现对共享资源的互斥安全访问提供运行时的支持,从而大大减轻程序员开发并发程序的负担。但STM算法通常采用乐观投机和细粒度并发的实现方式,算法思想十分精妙,可靠性难以保证。因此,研究STM并发机制的验证方法对提高并发软件的可靠性和安全性有重要意义。
Transactional Locking II(TL2)[7]是经典的基于锁的STM算法,它通过细粒度并发代码来实现事务的原子性。验证底层细粒度并发代码的正确性等价于证明它与高层抽象事务原子块间的上下文精化关系[8],即在任意的调用环境下底层代码产生的行为不会比原子事务的行为多。但该算法思想巧妙,验证难度很大。据作者所知,目前还没有在代码级上对TL2事务底层实现的验证工作。
本文基于TL2算法给出了一个典型的读写事务T(3行)对应的底层细粒度并发代码P(28行),使用基于依赖保证的程序模拟技术证明代码P是对事务T的一个精化实现,即在代码级上验证读写事务底层实现的正确性。
本文的主要贡献如下:应用程序精化技术完成了TL2事务的底层实现在代码级的验证,总结出了TL2算法中具体状态和抽象状态对应关系满足的不变式和基于时间戳的读集检验策略满足的不变式,为完成整个TL2算法在代码级的验证奠定了基础。
1 软件事务内存和TL2算法
STM是模拟数据库事务的并发控制机制来控制并行计算时的共享内存访问的一种技术,它是锁的一种替代机制。在STM中,一个事务指的是一段读、写共享内存的代码。这些读写操作在逻辑上是一个独立的单元,其中间状态对于其它的事务而言,是不可见的。与现在许多并发应用程序广泛使用的锁机制不同,STM通常采用一种乐观投机的并发控制方式:一个线程独立完成对共享内存的修改,完全忽略可能存在的其它线程,线程在日志中记录对共享内存的每一个投机的读写动作,然后根据日志中的记录进行共享内存的一致性检查,如果没有冲突就提交事务并更新共享内存,否则根据日志中的记录进行回滚,并重新开始一个新的事务。这种乐观投机的策略往往可以增加系统的并发度:任何线程无需等待一个资源,多个线程可以并发而且安全地修改同一共享数据结构的多个部分,从而实现共享数据结构的细粒度同步访问控制。
STM机制提供一些接口,主要包括以下几个重要接口:STM_begin()表示开始一个事务并完成对事务的初始化操作;STM_read(x)用于读共享变量x并更新读集;STM_write(x, buffer)将新的值写入写集buffer; STM_validate()用于冲突检测; STM_c o m m i t ( ) 用于提交 事务并更 新共享内 存 ;STM_abort()用于事务失败时进行回滚。图1左边表示“STM_atom{y=x+3}”,表示一个被原子执行的事务,而右边则是调用STM机制提供的接口进行程序变换后得到的运行时程序。
TL2和多数STM算法思想类似,采用“投机→检查→提交或回滚”的方式实现对共享数据的同步访问控制,它通过维护一个全局时间戳来完成对共享数据的一致性检查,并为每个事务存储单元额外添加锁和版本号两个域,事务在提交时会根据最新的全局时间戳来更新存储单元的版本号。因而事务可通过比较存储单元的版本号与全局时间戳之间的关系来判断共享存储是否已过时,是否需要回滚重新读取。事务对共享存储单元进行写入操作时,不是直接写入,而是写在一个缓冲区中,最后提交前才获取该单元的锁,最后提交时写入并释放锁。
图2是一个支持共享存储读写访问的原子事务。该事务中x和y是整型共享变量(事务共享存储),它们会被多个并发执行的事务同时访问。tmp是事务内部的局部整型变量,只能被当前线程访问。该事务提供给 程序员的 抽象行为 是原子地 执行STM_atom{}内的三行代码。
图4给出上述事务基于TL2算法的底层实现,可认为它是TL2算法对上述事务编译的目标代码。其中每个共享变量会被翻译成为一个结构体(如图3所示)。该结构体中,data保存与高层对应的值;ver是版本号;lk是底层共享结构体的保护锁,锁空闲时为0,被线程id获取后为id。代码中gt是全局时间戳,是一个可被多个并发执行的事务同时访问的整型共享变量。代码中的NAN类似C语言中的NAN,意思是“非数(Not a Number)”,在验证时表示某个变量的值是未定义的。
图4中,函数increment_and_fetch(>)原子地把全局时间戳gt加1并返回gt的新值。函数trylock(&x)非阻塞地获取结构体x的锁:如果锁空闲,便获取锁并返回0;如果锁已被占用,直接返回1。函数unlock(&x)释放结构体x的锁。
程序用fail作为指示标志,用来表示事务是否成功提交。当fail为1时,表示失败;当fail为0时,表示成功。程序主干部分由while循环构成。如果事务未成功提交,则fail为1,就继续执行循环体直至事务成功提交。
底层细粒度代码执行过程如下:首先将fail置为0(第3行)并进行STM_begin操作(第4~5行),读取全局时间戳并初始化各变量。之后对变量x进行投机读操作(STM_read):首先检查x的锁是否空闲(第6行),之后读取x的值保存在tmp中(第8行),再检查锁是否空闲、版本号是否小于等于rv(第9行)。读前和读后的这两次检查就保证了从开始执行事务至今,x未被其他线程更改。随后进行STM_write操作,将值存在缓冲区中(第10~11行)。之后尝试获取x与y的锁(第12~15行)。之后改变全局时间戳并且把这个新的全局时间戳记录在一个线程局部变量wv中(第17行)。在这以后执行STM_validate操作(第18行),再次检查x的版本号是否小于等于rv。如果有不符,则将fail置为1。这就保证了从开始执行事务至今,x的值未被修改。最后进行提交(STM_commit,第21~22行):把缓冲区内的值写入x和y,用wv更新版本号,并释放锁。整个过程存在很多检查,任意一次检查失败就把fail置为1并进行回滚。
验证TL2实现时,通常把实现事务的底层代码的每一步对应到高层事务代码的某一步上,即找到底层代码每执行一步时高层代码执行到的对应位置(高层代码可以不执行,也可以执行若干步),本文把这个对应位置称作“线性化点”。找到这些线性化点后,证明两层程序状态满足某个对应关系,而这个关系体现了两层程序状态的一致性,进而体现了实现的正确性。但验证难度很大。
首先,验证时很难确定底层代码每执行一步时高层代码执行到的对应位置。比如底层代码改变全局时间戳之后,就要进行STM_validate和STM_commit操作。大多数人直观地认为再次检查x版本号是否小于等于rv后的那个程序点或者提交过程中的某个子步是线性化点,和高层事务执行后的那个程序点对应。但是因为检查x版本号后,x就可被其他线程修改,这样高层执行事务代码后,高层x和底层x的值就不一致。这样就不能建立一个清晰的对应关系。另外线性化点也不能“简单地”放在再次检查x版本号这步之前,因为在检查完成后才知道是否可以提交,才能确定这个到底是不是线性化点。
另外验证时要指定在线性化点上高层程序状态和底层程序状态的对应关系。但是TL2算法实现的代码的粒度很细,因此这个对应关系非常微妙。大多数人很容易直观地以为这个对应关系可以表述为“如果一个共享变量的锁空闲,那么该共享变量在高层程序状态上的值和在底层程序状态上的值相等”。但这个对应关系无法描述如下情况:如果最后一次检查x的版本号后要进行回滚,那么即使已经获取了一个共享变量的锁,它在高层程序状态上的值和在底层程序状态上的值依然相等。
2 TL2事务的精化验证
如果要对STM的实现进行验证,那么就必须对其正确性有一个定义。目前有许多对STM正确性的定义,比如可线性化(linearizability)[9]、可串行化(serializability)[10]、不透明度(opacity)[11]以及其他几种变形。这些都是针对事务执行历史定义的,很难直接应用在STM代码级的验证上。最近Attiya等人使用上下文精化关系来刻画STM实现的正确性[8]。基于这个定义,如果一个原子事务的实现是正确的,那么该原子事务和实现这个事务的底层代码之间具有精化关系,即底层实现事务的代码在执行过程中表现出来的可观测行为不比原有事务在执行过程中表现出的可观测行为多。这个定义很直观,通俗易懂,可以在代码层面对事务内存的实现进行验证,所以本文采用这个定义来描述TL2实现的正确性。
图4实现事务的底层代码 (参见下页)
验证两个程序之间是否满足上下文精化关系可采用Liang等人提出的基于依赖保证的模拟技术(RGSim)[12]。这个技术可用于模块化验证两个并发程序之间的精化关系。验证时需要指定两个程序在执行时的依赖保证条件以及两个程序在执行时程序状态要满足的不变式。两个程序状态始终要满足这个不变式,这个不变式反映了两个程序状态之间的对应关系,也就体现了两个程序状态之间的一致性,进而体现了实现的正确性。验证精化关系时,要确定高层和底层代码的对应点(即线性化点),验证不变式在这些对应点上始终成立;同时要验证在程序执行过程中,每个指令的前后条件都在环境(由依赖条件指定)中始终成立。Liang等人提出的基于依赖
保证的向前向后模拟技术[13]扩展了RGSim,通过证明并发数据结构提供的并发操作满足上下文精化关系,来证明并发数据结构的可线性化性。采用这项技术验证程序A是程序B的精化实现时,需要模拟地执行A和B。A每执行一步,就要找B的对应点(即线性化点)。如果对应点确定,那么B执行到对应点,即B执行线性化操作到达线性化点。如果对应点不确定,此时就遇到了“疑似的”对应点,那么在此做一个尝试性的线性化操作,将线性化后的程序结果与未线性化的程序结果均记录在验证时使用的程序状态中。以后检查中,如果发现某个条件不满足,此前的线性化结果要被舍弃,那么就在程序状态中舍弃线性化后的结果。如果发现条件都满足,此前的线性化结果应该被保留,那么就在程序状态中舍弃没有线性化的结果。本文验证时就采用RGSim和基于依赖保证的向前向后模拟技术。
对于线性化点确定的代码,RGSim验证精化关系非常有效。为了降低验证的复杂性,本文在高层和底层中加入一个中间层,将高层代码转换为中间层代码,然后验证高层代码和中间层代码的精化关系,之后再验证中间层代码和底层代码的精化关系。在验证高层和中间层代码的精化关系时,因为高层和中间层的线性化点确定,所以采用RGSim。
首先将高层代码转换为中间层代码,如图5所示。表示中间层共享变量的结构体和表示底层共享变量的结构体类似,但只有data和lk两个域。函数lock(&x)获取结构体x的锁,如果这个锁被其他线程占用,函数便阻塞直至锁被本线程获取。函数unlock(&x)释放结构体x的锁。图5中的尖括号“< >”将若干语句包含在一起组成一条原子指令。中间层先原子地执行如下操作:获取x和y的锁并执行原始事务。之后逐一释放x和y的锁。
验证高层和中间层之间的精化关系时,依赖保证条件可根据操作语义得出,此处省略。用到的不变式是
此不变式中,对高层和中间层都存在的变量,用下标进行区别,H表示高层,M表示中间层。此不变式体现了高层变量和中间层变量应始终保持的一致性,即x与y两个共享变量在高层和中间层中的值始终相等,且高层和中间层对应的局部变量tmp的值始终相等。高层和中间层的对应点是:当中间层线程执行第一个原子操作时,高层线程执行事务;当中间层线程执行余下操作时,高层线程不执行任何操作。经过推导,高层和中间层的精化关系便可得到验证。
验证中间层和底层的精化关系时,因为线性化点不确定,采用基于依赖保证的向前向后模拟技术。首先考虑中间层代码和底层代码在执行时的线性化点:底层代码在用increment_and_fetch函数改变全局时间戳之后,中间层代码尝试性地进行线性化。在提交之前,底层代码要对读取的共享变量x进行再次检查。如果发现没有问题,就进行提交,同时保留中间层线性化后的结果,舍弃中间层没有线性化的结果;如果发现有问题,那么就需回滚,同时保留中间层没有线性化的结果,舍弃中间层线性化后的结果。
在验证中间层和底层的精化关系时,依赖保证条件可以根据操作语义得出,此处不再赘述。用到的不变式反映了算法的本质,是验证的关键,所以下文主要对不变式进行阐述。表示不变式时,对中间层和底层都存在的变量,用下标进行区别,M表示中间层,L表示底层。
首先阐述的是中间层和底层程序状态的对应关系满足的不变式,即TL2算法中具体状态与抽象状态对应关系满足的不变式。该不变式为
该不变式是说,如果一个共享变量在中间层或底层的锁空闲,那么它在中间层和底层的值对应相等。该不变式保证了中间层和底层共享变量的一致性。同时它也体现了引入中间层的必要性。为了看清这个问题,假设没有中间层,那么就需要讨论高层和底层状态的对应关系满足的不变式,这个不变式可以写作
假设底层代码投机执行时已获取了x和y的锁,但是在最后STM_validate检查中失败,必须回滚。回滚前,x和y的锁没有被释放,不变式的前提为假,因此不变式为真。回滚后,不变式的前提为真,要保证不变式依然成立,不变式的结论必须为真,但这个是无法推导出的。在加上中间层后,就可以解决这个问题。在中间层尝试进行线性化操作后,程序状态中有两种结果,一种是线性化后的结果,一种是没有线性化的结果。如果在STM_validate检查中失败,那么就要保留没有线性化的结果。在这个结果中,回滚前,由于不变式成立,并且中间层的锁空闲(即不变式的前提为真),所以不变式的结论为真;回滚后,不变式的前提依然为真,回滚操作不改变共享变量的data域,这就使得不变式的结论依然为真,所以不变式依然为真。因此加入中间层后,这个不变式就能恒成立。
另外一个重要的不变式是基于时间戳的读集检验策略满足的不变式,这个不变式为
它的意思是如果1)共享变量x已经通过了初次检查并读取了x的值,并且2)x的锁在中间层或底层空闲,并且3)x的版本号不大于rv,那么读取x时保存值的局部变量tmp和对应的底层共享变量x的值相等。在读取x前的那次检查可使得条件1)成立,读取x后的那次检查可使得条件2)和3)成立。因为共享变量的版本号单调增加,所以只要在任意程序点条件3)成立,那么在这个程序点之前它始终成立。因此如果读取x之后的那次检查没问题,那么在读取x前检查锁的时刻以及读取x的时刻,条件3)都成立。这个就可以保证读取的x的值正确。类似地,也可以推导出在STM_validate时,如果通过了检查,读取的x的值正确。
最后还有一个不变式比较重要,这个不变式是
它是说线程局部变量rv和共享变量的版本号都始终小于或等于全局时间戳,这反映了全局时间戳单调增加的性质。在验证时这个不变式是一个重要的辅助。
采用基于依赖保证的向前向后模拟技术进行验证时,根据操作语义推导出每个语句在执行过程中的前后条件,同时验证这些前后条件在环境(由依赖条件指定(中始终保持。推导后便验证了中间层和底层的精化关系。
在验证高层和中间层的精化关系以及中间层和底层的精化关系之后,根据精化关系的定义,便可知高层和底层之间也有精化关系。这样便在代码级上完成了对这个TL2读写事务底层实现的精化验证。
3 相关工作
已有的许多工作[14,15,16,17]使用模型检查(modelchecking)验证STM算法,但为了减少状态数量并简化验证,他们的抽象模型通常将STM算法的若干步合为一个原子指令,这样就忽略了真实的STM算法在线程交叉执行时的微妙状态。而本文在代码级上对TL2事务的底层实现进行验证,并关注了这些微妙状态,同时还给出了这些状态对应关系满足的不变式。
Tasiran[18]对STM算法在代码级上进行了精化验证,但所验证的STM算法的策略与TL2的策略不同,所以所用方法不适用于TL2的验证。Mohsen等人[19]基于模拟技术提出了验证STM的框架,但只支持向前模拟,不支持向前向后模拟,也无法验证TL2事务的实现。而本文采用向前向后模拟技术验证了TL2事务的底层实现。
4 结束语
本文用TL2算法实现的代码具有代表性,体现了TL2算法的本质,帮助人们对TL2算法有更深入的理解。
引入中间层后,本文使用基于依赖保证的向前模拟技术(RGSim)验证了高层和中间层的精化关系,再使用基于依赖保证的向前向后模拟技术验证了中间层和底层的精化关系。这样便验证了高层和底层的精化关系,完成了对一个典型读写事务基于TL2算法的底层实现在代码级的验证工作。
本文总结了TL2算法中具体状态和抽象状态对应关系满足的不变式和基于时间戳的读集检验策略满足的不变式,为完成整个TL2算法在代码级的验证奠定了基础。
基于偏序简化的并发系统验证 篇2
在基于构件的软件开发CBSD(Component Based Software Development)中,需要对构件交互协议进行形式化描述和验证。而构件交互协议是一种典型的分布式并发系统模式。上世纪七十年代末,R.Milner和C.A.R.Hoare分别提出了CCS(Calculus of Communicating Systems)和CSP(Communication Sequential Processes),共同开创了用进程代数研究通信并发系统的先河。之后基于进程代数模型检测技术就成为分布并发系统模型检测的热点。目前对协议模型的验证和检查主要采用进程代数方法。
在并发系统中,子系统间互补的迁移同步,其余的迁移是交错进行。这是引起模型状态空间爆炸的主要原因。提出组合可达性分析(Compositional reachability analysis)算法,通过弱等价关系缩小模型规模,但该算法首先需要遍历组合模型的所有状态,所以并未彻底解决问题。
状态爆炸问题往往出现在进程并发合成环节上,若能限制与子系统交互的环境就能控制其状态规模。普度大学的Wei Jen Yeh[2]提出通过改造并发模型进程代数的定义来控制进程组合中间过程的状态爆炸技术。
上述多种并发模型检测技术都有各自的优势,然而它们仅仅是去除模型组合中间过程出现的冗余状态,还不能够有效解决状态爆炸问题。Bell实验室的Patrice Godefroid[3]仔细研究了并发模型中迁移的依赖关系,提出针对状态爆炸的偏序简化技术,在Petri网描述的并发模型上得到了很好的应用,但至今还未在进程代数描述的模型上得以应用。
而以通信系统演算CCS为代表的进程代数,因其概念简洁,可用的数学工具丰富,在并发分布式系统的规范、分析、设计和验证方面获得了广泛应用。所以,本文提出基于进程代数的偏序简化算法,通过引入迁移交织执行顺序的表示,即迹(trace)的概念[3,4]达到对状态空间简化的目的,从而缩小了组合模型的规模,减少了验证算法所需遍历的状态数,提高了验证效率。
1迹与偏序
偏序技术(partial order technique)是一种基于迹的状态化简技术[6],可实施迁移之间的偏序关系准确地表示了系统迁移之间的相互独立或依赖关系。这种技术能有效地减少模型检测过程中需要被搜索的状态空间数量。偏序简化技术(partial order reduction)通过消除迹中的冗余迁移序列来对状态迁移图进行化简,主要有稳固集技术和睡眠集技术[3]。与偏序简化技术密切相关的两个基本概念是迁移的独立性和迹。
偏序与迹的对应关系是:迹中的迁移序列就是其迁移偏序经线性化的所有全序集合。如图1中T={t1,t2,t3,t4}。迁移t1分别与t2和t3相依赖(用从t1指向t2和t3的弧表示),迁移t4分别与t2和t3相依赖,t2和t3相互独立。所以:
D={(t1,t1),(t2,t2),(t3,t3),(t4,t4),(t1,t2),(t2,t1),(t1,t3),(t3,t1),(t2,t4),(t4,t2),(t3,t4),(t4,t3)}
那么迁移序列ω=t1t2t3t1就代表了迹[ω]={t1t2t3t1,t1t3t2t1}。因为t1t3t2t1中迁移t2和t3相毗邻且相互独立,交换位置后就可得到新的迁移序列t1t2t3t1。
稳固集是定义在每个状态上的可实施迁移集合。在每个状态中,应该能够选择与其他可实施迁移子集相互独立的迁移子集予以实施。
稳固集的选择—搜索算法如下所示。该算法遍历到某一状态时,只沿着该状态稳固集中的迁移继续遍历。算法中用到栈与哈希表这两个数据结构。栈用来暂存需要遍历的状态,哈希表保存遍历过的状态。初始情况下把起始状态入栈,进入循环从起始状态沿其稳固集遍历其余的状态,直到栈空为止。
1 Initialize: Stack is empty:H is empty;
2 pash (s0) onto Stack;
3 Loop:while Stack≠ϕ do{
4 pop (s) from Stack;
5 if s is NOT already in H then {
6 enter s in H;
7 T=Persistent_Set(s);
8 for all t in T do {
9 s′=succ(s) after t:/* t is executed */
10 push (s′) outo Stack;
11 }
12 }
13 }
2偏序简化及其算法
在进程代数模型中,本文认为在动作前缀前后的迁移有相互依赖关系,如P=a.b.c.d中a与b相依赖,b与c相依赖。试想若a迁移不能执行,那么后续迁移都无法执行,所以依赖关系可以是传递的,即a与c也相依赖。有了依赖关系不难得出独立关系的定义,独立关系也可应用稳固集定义得到。顽固集定义是计算稳固集的有效算法,为了定义顽固集节,首先提出迁移冲突定义:
定义1 在状态s的迁移集合中,迁移t1和t2冲突,当且仅当,参与在s状态下并发合成的进程中,存在P=t1.P1+t1.P2,即t1和t2分别是进程P非确定选择项的首动作。
定义2Ts是状态s的顽固集,若Ts包含至少一个状态s的可实施迁移,并且∀t∈Ts,下面两条成立:
若迁移t在状态s不可实施,即参与在状态s并发合成的进程中,存在进程P拥有与t互补的迁移t′,但在状态s下还不可实施。那么从进程P当前状态出发到迁移t′可实施的所有前缀中的迁移也在Ts中。
若迁移t在状态s可实施,那么所有与t相冲突的迁移也在Ts中。
根据定义2可以得出顽固集算法,至此在进程代数模型上,已经定义了有效计算稳固集的算法。用稳固集简化模型状态迁移图后,再配合睡眠集去除稳固集中冗余迁移,之前定义的利用稳固集和睡眠集的选择—搜索算法在进程代数模型上完全适用,而且该算法也是有效的。所以我们就得出了如下的基于CCS的偏序简化算法。
1 Initialize: Stack is empty:H is empty;
2 pash (s0) onto Stack;
3 Loop:while Stack≠ϕ do{
4 pop (s) from Stack;
5 if s is NOT already in H then {
6 enter s in H;
7 T=Persistent_Set(s);
8 for all t in T do {
9 s′=succ(s) after t:/* t is execnted */
10 push (s′) outo Stack;
11 }
12 } else {
13 Iad=Adjust_per Set(s);
14 for all t∈Tad do {
15 s′=succ(s) after t:/*t is executed*/
16 push(s) onto stack
17 }
18 }
19 }
3基于偏序简化的并发系统安全性验证
传统的偏序简化算法仅针对于死锁的检查,并没有涉及安全性验证。下面给出利用偏序简化验证模型安全性的方法。
进程代数中进程是参与并发合成的实体,仔细分析参与并发合成的进程,首先分为递归形式和非递归形式两种,其下层又可分为确定形式与非确定形式。这两层分类直接影响进程并发合成的结果。如设参与并发合成的进程为P和Q,那么若P和Q都是递归形式就如图2所示。
根据基于进程代数的偏序简化算法对图4进行化简:首先选择c.d进行迁移,沿迁移序列c.d从(0,2)状态出发又返回到它,此时可以考虑再往状态(0,2)的稳固集中增加迁移集合Tad,然后再沿Tad中的迁移继续遍历。对于遍历过的状态再继续遍历的条件是该状态还有未遍历过的迁移。图2中在第二次遍历状态(0,2)时,函数Adjust_PerSet(s)向状态(0,2)稳固集增加迁移集合Tad={a},此时算法沿a遍历到状态(1,2),再沿b回到状态(0,2),此时(0,2)状态的所有迁移都已遍历过,且它的稳固集就是它的所有迁移集合,算法终止。
图2中的右侧子图就是经过偏序简化后的状态迁移图,虚线弧和虚线圆表示被删减的迁移和状态。由迹的定义,被删减掉的迁移都可以由相独立相毗邻的迁移互换位置而扩展出来。所以在验证模型的安全性质时,首先判断该性质定义的状态迁移图是否指定了模型中相互独立迁移的顺序,如性质P = a.c,即a与c相依赖。但在模型中a与c相独立,所以模型肯定不满足性质P。此时不能仅给出简化后的图的违反性质的路径,要考虑所有可能违反性质的路径,因为这样才能为开发者提供全面的信息。所以当模型不满足性质时,按照组合可达性分析安全性验证算法给出结论。如果模型满足性质,就给出偏序简化后的结果。
4结束语
本文将偏序规约应用于进程代数模型,给出了进程代数模型的偏序简化算法,并且提出验证安全性的方法。算法基于在并发模型验证中没有必要计算所有的迁移交织,而是由任一迁移交织来代替与其在同一迹中的其余迁移交织的思想提出的,从而达到对状态空间简化的目的,有助于提高验证效率,便于对并发系统进行安全性验证。
摘要：构件交互风格和交互协议的描述与验证是基于构件的分布式系统开发的基础和关键,而构件交互协议是一种典型的分布式并发系统。传统的方法难以解决系统建模和验证中的所谓的状态爆炸问题。偏序简化是应用迹的概念,对模型进行化简并且对模型进行死锁验证。但这样的验证重点放在了Petri网模型上,而没有涉及进程代数模型,所验证的只是模型是否有死锁状态。而以通信系统演算CCS为代表的进程代数,因其概念简洁,可用的数学工具丰富,在分布式并发系统的规范、分析、设计和验证方面获得了广泛应用。对此,提出将偏序规约应用于进程代数模型,给出基于进程代数模型的偏序简化算法,并提出利用进程代数模型偏序简化算法来验证安全性的方法。
关键词：分布式系统,并发系统,偏序简化,进程代数,安全性
参考文献
[1] Cheung S C,Kramer J.Checking Safety Properties Using Compositional Reachability Analysis. ACM Transactions on Software Engineering and Methodology (TOSEM), New York, NY: ACM Press,1999,8(1):49-78.
[2]Yeh W J.Controlling State Explosion In Reachability Analysis.SERC Technical Reports.SERC-TR-147-P,Purdue University West Lafa-yette,IN,USA:1993.
[3] Godefroid P.Partial-order Methods for the Verification of Concurrent Systems——An Approach to the State-Explosion Problem. Lecture Notes in Computer Science, Secaucus, NJ, USA: Springer-Verlag New York,1996,1032:142.
[4]Godefroid P,Wolper P.A Partial Approach to Model Checking.Papers presented at the IEEE symposium on Logic in computer science,Orlan-do,FL,USA:Academic Press,1994:305-326.
[5]Wolper P,Godefroid P.Partial-Order Methods for Temporal Verifica-tion.Lecture Notes In Computer Science,London,UK:Springer-Ver-lag,1993,715:233-246.
并发程序验证 篇3
基于演绎推理的形式验证是程序验证的一种重要方法。其核心是由程序员书写断言描述程序的性质, 然后根据某种方式对断言进行演算产生验证条件, 最后使用某个自动定理证明器来证明验证条件。该方法的程序验证原型系统非常多,但是到目前为止还没有可供工业界使用的产品问世。其主要原因是验证原型系统的能力受限于自动定理证明器的能力。 在研究程序验证的过程中,必须考虑如何提高自动定理证明技术,同时也应该研究如何减少对自动定理证明器的依赖。
本实验室设计并且实现了一个源码级验证工具 ——面向Pointer C的程序验证器原型(简称原型系统)[1,2,3,4]。原型系统对Pointer C语言程序进行自动验证,先对程序进行形状分析生成形状图,然后根据程序员书写的前后条件以及循环不变式通过最强后条件演算方式生成验证条件,最后交给自动定理证明Z3[5]证明。本文研究的主要内容是,在引入自定义谓词增强断言语言的表达能力的同时,怎样减轻因此产生的自动定理证明器的负担。
原有的原型系统中由于断言语言能力的局限, 很多易变数据结构的性质无法简明准确的表达。为此,原型系统引入自定义递归谓词来描述这些比较复杂的程序性质。程序员在写代码的过程中有时会用到递归谓词的归纳性质。但是这样做带来的问题是,Z3在证明验证条件的过程中无法发现这些归纳性质,从而造成验证条件证明失败。
为了自动定理证明器能顺利完成验证条件的证明,原型系统由程序员提供自定义谓词之间的归纳性质定理来帮助自动定理证明器证明。同时由于性质定理是由程序员提供的,其正确性无法保证。本文给出一种先对性质定理本身进行具体分析然后再结合结构归纳的方法,实现了性质定理的自动证明。
本文接下来的内容安排如下,在第1节里介绍Pointer C程序验证器原型系统中断言语言的设计以及为什么需要引入自定义谓词;第2节给出程序员需要提供性质定理的原因;第3节详细阐述如何具体实现性质定理的自动证明;第4节简单介绍当前原型系统的组成以及可以通过的验证实例;第5节的主要内容则是全文总结以及相关工作的比较。
1程序断言语言设计
验证系统原型的核心是程序断言语言的设计, 其主要验证对象是操作易变数据结构的指针程序, 而易变数据结构的特点是递归性。为了准确用断言表达易变数据的性质,直观的方法就是引入谓词。 引入谓词有两种机制,一种是系统内部建立固定谓词让程序员使用,但是这种不满足多变的程序性质和复杂的数据结构;另一种是由程序员自己定义谓词来满足程序性质多变的情况,这也符合自动定理器的功能在不断扩展的事实。本文中采用的就是自定义谓词的机制。
1.1自定义谓词
自定义谓词是程序员自己提供的用以描述程序的性质的谓词,最常见是递归定义的谓词,也称归纳谓词。其详细文法可以参考Pointer C的程序验证器原型相关的文献[1,2,3,4]。
例如有结构体定义为:
typedef struct node{int data; Node* l; Node*r;}Node;
现在定义一棵二叉排序树(Binary Sort Tree),它提供性质定理的原因;第3节详细阐述如何具体实现性质定理的自动证明;第4节简单介绍当前原型系统的组成以及可以通过的验证实例;第5节的主要内容则是全文总结以及相关工作的比较。需要三个归纳谓词一起定义,其形式为:
符号:=的左边是谓词的名字以及谓词的参数, :=的右边是谓词的定义。谓词gt表示对于指针p来说, p指向空或者p指向一棵二叉树,且x的数值大于这棵树上所有节点的data域的数值。此时我们发现归纳谓词中的指针p不再是指向一个单独的存储单元,而是抽象成为了一棵二叉树。p可以为空树,也可以有左子树和右子树。这是由归纳谓词的定义决定的, 谓词体右边出现的同名谓词可以继续按照谓词的定义展开。所以BST的含义是:p可以为空树;当p不为NULL时,该树的上所有父节点的数据域data值小于右子树根节点的data值大于左子树根节点的data值。
1.2自定义谓词在程序验证中的作用
自定义谓词除了能够定义复杂的数据结构性质之外,还可以根据程序的实际特点定义指针之间的关系,只有灵活应用自定义谓词,才能正确书写正确的函数前后条件和循环不变式。现在用二叉排序树删除根节点的函数(图1)来具体阐述这个问题。函数的谓词定义为:
谓词(1),(2),(3)一起定义了一棵二叉排序树, 而谓词(4)则表示p指向的二叉树上所有的节点的data值都小于q指向的树 上所有节 点的数据 。 而BST_seg(p,q)则表示从p指针到q指针之间的树段上所有数据的性质。
这些谓词的定义都是原型系统验证二叉排序树 (非空树)根节点函数需要的。二叉排序树删除了根节点之后,还需要保持该数据结构是一棵二叉排序树,所以函数在while循环语句中寻找中序前驱,然后将它的值替换根点,最后删除这个中序节点。所以这个函数的性质的前条件是p!=NULL BST(p), 它的后条件是BST(p)。同时在循环语句中,指针s在该树的左子树上向右前进直至找到中序前驱,所以它的循环不变式是BST(p->r) lt_all(s,p->r) lt(q->data,s) BST_seg(p->l,q) BST(s) ,表明了它在循环语句执行的过程中程序代码一定会满足的性质。
2程序员提供的性质定理
由上文可以看出,自定义谓词为程序验证提供了便利,基于原有的谓词文法我们已经可以方便写出函数的前后条件以及循环不变式。但是新的问题诞生了,前后条件以及循环不变式演算完毕生成的验证条件交给Z3时,自动定理证明器无法证明结果。 而发生这个情况的原因是自动定理证明器Z3没有推导谓词之间的归纳性质的能力。
虽然Z3无法发现归纳谓词之间的归纳性质,但是程序员自己可以给出归纳性质的定理辅助Z3证明。 对于图1的二叉树根节点删除函数来说,提供几个性质定理,自动定理证明器就可以顺利进行验证条件的证明。这些性质定理如下:
二叉排序树删除根节点函数的循环不变形状图为:
图2中形状不变图表示循环语句中程序维持的形状。现在以性质定理(c)来说一下,为什么验证条件的证明需要它们。当BST_seg(p,q)的展开情况不为不动 点的时候 , 是基于p - > r上的谓词 性质B S T _ s e g ( p - > r , q ) , 将其他谓 词的性质 按照p - > r指向节点定义序列段的左边加入该谓词,得到BST_seg(p,q)。
根据图2的循环不变图,我们可以看图1函数循环体里的赋值语句{q= s; s = s->r; }中看出s从根节点到右子树前进方向,已经遍历过的节点序列的性质和当前指针指向的节点性质,再加上尚未遍历的节点性质综合起来才能证明循环出口的验证条件。也许就是说B S T _ s e g ( p - > l , q ) 可以扩大 到BST_seg(p->l,q->r),正是性质定理(c)表达的意思。
这个分析过程,实际上就给程序员提供了一种如何书写性质定理的思路。程序员在写代码的过程中,清楚谓词在形状图上的含义,也清楚自己利用了谓词上哪些归纳性质。比如在该例子中,程序员知道二叉树删除根节点后的中序节点就是该树左子树上最底层最右边的点,所以并没有直接将这个节点替换根节点,而是利用它的值是左子树上所有节点的最大值这个归纳性质。程序员将这个性质交给Z3作为推导的条件,就可以证明循环出口的验证条件。同时,程序员也可以对形状上各个节点附带的谓词性质进行分析,就能很容易地发现验证条件的证明缺少哪些性质定理。
3性质定理的自动证明
一般情况下,定理证明不存在自动发现归纳证明步骤的通用算法。但是对于原型系统的性质定理来说,出现的参数变量个数少,指针参数的递归结构明确而且形状固定,可以通过对定理各个组成部分的分析得到归纳证明的方法。本文提供一种自动证明性质定理的分析方法,并且按照这种方法在原型系统中实现了性质定理的自动归纳证明。
另外,本文采用的归纳方法不是自然数归纳法, 而是结构归纳法。它的基本思路是假设在某一个集合上某个命题成立,证明某个包含这个集合的集合上这个命题成立。接下来详细介绍这种方法的思路和具体实现过程中的步骤。
3.1证明思路
该方法的基本思路分为三个步骤,最后一步是归纳证明,前两步是分析性质定理的结构。本节会根据第2节二叉排序删除根节点函数的谓词和性质定理具体分析证明过程。
第一步,分析谓词间的依赖关系与谓词的归纳方式。谓词的依赖关系就是指谓词是基于哪些谓词定义,谓词lt的定义谓词不依赖其它谓词,谓词 ( 4 ) l t _ a l l依赖谓词 ( 2 ) l t 。同时也很容易得到谓词 (5)BST_seg依赖谓词谓词(3)BST、谓词(2)lt和谓词 (1)gt。而谓词的归纳方式在静态检查谓词时就已经完成。它从谓词参数的定义出发,比如谓词lt和gt都只有一个指针变量,所以按照二叉树的结构归纳。 而谓词lt_all有两个指针变量,但是它的谓词体中, 只有第一个指针的路径有变化,说明此谓词按照第一个指针变元归纳,并且归纳的方式是按照二叉树的结构。同理,我们可以得到谓词BST_seg的归纳变元也是第一个指针,但是他的归纳方式不再是按二叉树的结构,而是只按照节点的右子树路径r指针进行归纳。
第二步,利用性质定理(引理)间的依赖关系。 原则上来说,定理应该是按照各个谓词的定义就可以独立证明,比如定理(a)、(b)。实际上,证明某一个相对复杂的定理可以将其他的引理作为前提条件, 这样可以减少复杂定理的证明步骤。比如引理(e) 依赖于引理(a),没有引理(a),它要进行两次归纳证明。确定引理之间的依赖关系没有像谓词之间依赖关系那样直观,几乎没有明确的办法。一种简单的方法是,证明任意一条定理时,都将其他的定理作为前提条件。
第三步,按照第一步的分析出来的归纳变元跟归纳方式对性质定理进行证明。其具体的操作分为3小步:
1)按照第一步分析得到的归纳变元和归纳方式进行归纳基始证明。证明失败原型系统报错,退出程序验证;
2)按照第一步分析得到的归纳变元和归纳方式形成归纳假设;
3)将该引理外的其他引理和上一小步的归纳假设都作为前提条件跟引理一起交给自动定理证明器证明。证明失败原型系统报错。
3.2性质定理的自动证明过程
性质定理的抽象语法定义为其中P的形式为Q的格。下面我们以定理(d)
为例介绍如何在原型系统中实现性质定理的自动证明。
第一步,检查P和Q的归纳变元,决定是否需要归纳证明。系统原型在进行性质定理证明之前,会对每个谓词进行检查得到它们的归纳变元。如何寻找归纳变元第2节中有介绍。这样我们得到P的归纳变元集合A与Q的归纳变元集合B,A={a1,a2..ah}, B = { b1, b2. . b1} ,其中ai和bj都是指针路径(格式为ptr->next或者ptr->l),不包括指针数据域路径(格式为ptr->next->data)。同时我们还需要P、Q的指针路径集合X和Y。显然指针路径也包含了归纳变元集合的元素,因为单个谓词的指针路径中不会都是归纳变元。对于定理(d)来说,A={m,n->r},B={m}, X={m,n,n->r},Y={m}。
此外,我们定义函数NUM(x)求解集合的元素个数。根据NUM(A)和NUM(B)的值,我们得到三种情况。P与Q都没有归纳变元,直接交给Z3证明;P与Q只有一边有归纳变元,直接证明交给Z3证明;P与Q都有归纳变元,到第二步。的左边和右边都有归纳变元,所以到第二步证明。
第二步,得到归纳变元与归纳方式。归纳变元应该是P和Q中归纳变元的交集R中的元素,但是R≠ A∩B,而是A和B的等价交集。这里等价交集的元素分两种情况,第一种是它们是同一个变量,另一种是指如果不为同一个变量时它们互为别名。别名的含义为两个指针指向同一个节点。
得到等价元素的算法如下:先定义P中的指针路径等式集合 {1,2..n},根据 ,我们可以得到若干个指针路径的等价群组{E1,E2..Em},每一个群组都应该包括一组相等的指针路径。现在我们需要知道{a1,a2,a3..ah}和{b1,b2..b1}是否有等价的元素。当它们等价时,它们的减去同样的后缀后,留下的指针前缀至少有一组同时出现在某一个Ei中。具体来说,有路径p->next->next->next和q->next->next,那么它有三组需要验证的指针前缀,是(p->next->next, q - > n e x t ) ,( p - > n e x t , q ) 和( p - > n e x t - > n e x t - > n e x t ,q->next->next)。指针路径p->next和q->l不可能等价, 因为p和q不是一种结构体指针。
得到归纳变元之后,我们要寻找归纳方式。按照之前的内容介绍,每个谓词的归纳方式都不同。 我们按照归纳方式最有限制的谓词来,归纳方式最有限制就是二叉树的不动点限制最多,或者归纳路径的数目最少。当然我们可能有多种不同的最有限制的归纳方式,我们就一一尝试,如果每一个证明结果都是错误,我们就对性质定理报错。根据以上方法,很容易得定理(d)的归纳变元是m,归纳方式是m->r。
第三步,证明归纳基始。这个过程就是按照谓词的不动点的定义化简性质定理,然后交给Z3证明。 化简得方式就是将不动点的定义直接合取P。定理(d)的归纳基始:容易得证。
第四步,归纳假设的生成。我们按照第二步得到的归纳方式,将性质定理里的归纳变元替换为归纳路径就是归纳假设。有几种归纳路径,就生成几个归纳假设公式。定理(d)只有一个归纳路径,所以归纳假设为:
第五步,将归纳假设,归纳基始,所有谓词定义和其他性质定理作为条件,将性质定理本身交给自动定理器证明。如果证明结果如果为false,原型系统退出。
4原型系统简介
研究小组设计并且实现了面向Pointer C语言的的程序验证原型系统(简称原型系统)。它的基本流程为以下三个步骤:
1)预处理阶段(编译器前端)。这个阶段处理Pointer C语言,包括词法分析,语法分析和类型检查。具体的过程是,对程序员的源程序(包括编程语言跟断言语言)进行词法分析和语法分析,生成符号表和抽象语法树AST。同时还要进行类型检查,类型检查类似于C语言。
2)程序分析阶段(形状系统):遍历(1)生成的程序的语法树AST,根据形状图逻辑的演算规则生成各个程序点的形状图,还要进行形状检查和得到循环不变图。
3)程序验证阶段(验证条件生成器):以函数为单位,根据程序员提供的函数的循环不变式和前后条件,按照最强后条件演算方法和专有逻辑形状图逻辑演算得到验证条件,最后将验证条件交给自动定理证明器证明。
现阶段原型系统已经可以通过以下程序的验证, 一种是不涉及易变数据结构的非指针程序,快速排序,二分查找,二叉堆(数组实现)等;另一种是涉及易变数据结构的指针程序(全部包含性质定理跟自定义归纳谓词),有序单(双)链表的插入删除,有序单(双)向链表逆置,有序单链表合并, AA树插入,平衡二叉树、二叉排序树、treap树和splay树的插入和删除。
对原有的原型系统来说中,通过验证的大多数实例都包含性质定理。系统在假设其正确的情况下对所有的实例进行程序验证,实际上这种验证结果并不可靠。而在本文的工作实现之后,现有的实例中所有的性质定理都通过了验证,之前原型系统通过的实例的正确性得到了保证。
5总结与相关工作比较
本文的内容主要是实现了当前所有包含谓词的测试用例里中性质定理的自动归纳证明。性质定理描述了自定义谓词之间的关系,它和自定义谓词一样由程序员自己提供,其目的是辅助自动定理证明器证明验证条件。自动定理证明器的局限性,使其在不提供性质定理的情况下,需要推导出归纳性质的验证条件证明失败。此外,自动定理证明器也不具备归纳证明的方法。本文通过对性质定理本身以及谓词的分析给出了一种自动证明归纳定理的方法。
近年来,还有很多其他的国内外实验室也在开发源码级的验证工具。比如,Veri Fast是一个可以验证C和Java程序的工具原型[6]。它为了提高表达程序性质的能力,允许程序员定义归纳数据类型(类似于结构体定义)及其上的递归函数,还有允许定义基于分离逻辑的谓词。递归函数跟本文归纳谓词的最大区别是,递归函数需要提供更多参数,实际表达含义可以一样。
Veri Fast和本文的验证工具还有一个区别就是, 程序中的定理证明由程序自己提供。因为这个证明过程在Veri Fast中就是一个函数。但是本文是原型系统的工作,程序员只需要根据形状图分析书写性质定理就可以了,难度相对会小不少。此外,Dafny[7]工具的最新实现[8]和本文方法的自动证明定理的方法很接近似。它和我们原型系统一样,提供性质定理,在Dafny中叫做lemma。同样对lemma进行归纳证明,不过它和我们原型系统不同的是,它作的是自然数归纳证明,并且允许多个变量归纳的情况。
还有其他一些类似于本实验原型系统的工具, 大多数验证工具都和原型系统一样,引入自定义谓词提高程序断言语言的表达能力,比如有[9,10]。但是这些工具都没有提供像本文中实现的自动证明性质定理的功能。而且这里面的某些工具,为了验证谓词归纳性质的方便性,在编程语言中限制了循环语句的使用,极大的降低了编程的灵活性。
参考文献
[1]ZHANG Zhi-tian,LI Zhao-peng,CHEN Yi-yun,et al.An Automatic Program Verifier for Pointer C:Design and Implementation[J].Journal of Computer Research and Development,2013,Vol.50(No.5):1044-1054.
[2]Zhaopeng Li,Yu Zhang,Yiyun Chen.A shape graph logic and a shape system.Journal of Computer Science and Technology.28(6):1063-1084,Nov.2013.
[3]XU Wen-yi,CHEN Yi-yun,LI Zhao-peng.Verifier Prototype for Programs with User-defined Predicates in the Assertion Language[J].Journal of Chinese Computer Systems,2013,Vol.34(No.7):1482-1486.
[4]SONG Yan-hui,LI Zhao-peng,CHEN Yi-yun.Automatic Inference of Pre and Post Shape Graphs for Pointer-type Recursive Functions[J].Journal of Chinese Computer Systems,to be published.
[5]Leonardo de Moura and Nikolaj Bjørner.Z3:An Efficient SMT Solver,Conference on Tools and Algorithms for the Construction and Analysis of Systems(TACAS),Budapest,Hungary.Vol 4963 of LNCS,pages 337–340,2008.
[6]Bart Jacobs,Jan Smans,Pieter Philippaerts,Frédéric Vogels,Willem Penninckx,and Frank Piessens.Veri Fast:A Powerful,Sound,Predictable,Fast Verifier for C and Java.In NASA Formal Methods,pages 41-55,2011.
[7]K.Rustan and M.Leino.Dafny:An Automatic Program Verifier for Functional Correctness.In LPAR-16,LNCS 6355,pages 348-370,2010.
[8]K.Rustan and M.Leino.Automating Induction with an SMT Solver.In VMCAI 2012,LNCS 7148,pages 315-331,2012.
[9]W.-N.Chin,C.David,H.H.Nguyen,and S.Qin.Automated verification of shape,size and bag properties via user-defined predicates in separation logic.Science of Computer Programming,doi:10.1016/j.scico.2010.07.004,2010.
并发程序验证 篇4
1 主要功能
表单验证对于任何一个编程者都不陌生, 此类程序主要应用在用户注册、信息采集、网络报名等程序流程中, 对于表单严整不严格的程序会给后期数据加工、数据处理工作带来很大的麻烦, 所以在做表单验证程序的时候, 需要尽量详细地考虑存在的相关问题。
常用的表单验证主要包括是否填写信息、填写信息是否规范、密码强度判断、两次密码输入是否一致、中英文数字的处理判断、出生日期格式判断、电子邮箱的验证、留言信息长度限定等功能, 最后在提交表单时出现是否确认提交的提示, 提交成功后出现提示框。
密码已经是人们生活工作中必不可少的工具, 但一个不安全的密码有又有可能会给人们造成不必要的损失。作为设计者, 如果在网页中能对用户输入的密码进行安全评估, 并显示出相应的提示信息, 那么对用户设置一个安全的密码将有很大帮助。评估方式:
(1) 如果密码少于5位, 那么就认为这是一个弱密码。
(2) 如果密码只由数字、小写字母、大写字母或其他特殊符号当中的一种组成, 则认为这是一个弱密码。
(3) 如果密码由数字、小写字母、大写字母或其他特殊符号当中的两种组成, 则认为这是一个中度安全的密码。
(4) 如果密码由数字、小写字母、大写字母或其他特殊符号当中的3种以上组成, 则认为这是一个比较安全的密码。
出生日期在数据库中存储是有一定格式要求的, 如果不是规范存储则填写的日期将无法进行处理、分析。所以出生日期需要用标准的“xxxx—xx—xx (年-月-日) 这种方式进行填写。
电子邮箱的填写能否收集用户联系方式, 这就需要用户按照规范填写, 填写时要按照电子邮箱的填写标准进行填写, 一般电子邮箱的格式为username@***.net、username@***.com.cn等, 这样就可以按照规范进行判断。
下面对验证的主要功能进行详细分析:
(1) 验证用户名是否填写, 并且填写是否规范, 用户名需要是A-Za-z0-9_。
(2) 密码和确认密码是否一致。
(3) 密码强度的评估。
(4) 检测是否为中文。
(5) 检测姓名拼音是否都为字母。
(6) 日期的格式检测。
(7) 电子邮件的格式检测。
(8) 手机号码应该全部为数字。
(9) 填写留言信息字数限制以及现有字符数显示。
(10) 提交表单后出现的确认对话框提示。
此程序在开发过程中存在的难点问题:
(1) 密码强度的评估, 弱、中、强的判断与检测。
(2) 利用正则表达式来对用户输入信息进行验证。
2 代码详解
程序主要由若干部分组成, 可以把每一部分功能都定义为一个函数模块, 下面分别介绍详细程序代码, 如图1, 图2所示。
2.1 用户标识判断
主要利用form1.name.value获取所填写的内容, 判断内容是否为空, 如果为空则出现相应提示, 并且利用form1.name.focus () ;获取当前焦点。
利用正则表达式的知识来对条件进行限制, 用户标识需要是字母或者是数字。JavaScript中的RegExp对象用于正则表达式相关的操作, 这个对象提供了一个方法test来判定某个字符串是否满足某个表达式, 返回值是true/false。
2.2 用户密码、确认密码
判断两次密码输入是否一致, 如果不一致则出现错误提示。并且利用form1.pwdok.focus () ;获取当前焦点, form1.pwdok.select () ;选中当前不相同密码。
2.3 中文姓名
判断输入的字符是否为中文, 在正则表达式中u4E00-u9FA5 (unicode码) 中表示汉字, reg0.test对输入的字符串进行检测, 如果输入的不是中文, 则出现相应提示信息。
2.4 姓名拼音
此部分对拼音进行判断, 利用for循环字符串的遍历出所有输入字符, 然后利用form1.ename.value.charAt (i) 获取每一个字符, 进行字母的判断, 如果不是大写或小写字母, 则会出现错误提示。此部分判断也可以利用正则表达式来校验, 读者可以根据相关知识认真思考一下。
2.5 出生日期
利用正则表达式来列出日期的条件, 2009-12-30为标准格式, 不符合此格式就会出现错误提示。Str.match (reg) 表示规定要匹配的模式的RegExp对象, 若没有找到任何匹配的子串, 则返回null。
2.6 电子邮件
利用正则表达式来列出电子邮件的条件, 在上一部分内容中详细分析了电子邮件的基本格式, username@***.com和username@***.com.cn两种标准格式, 不符合此格式就会出现错误提示。Str.search (reg) 方法用于检索字符串中指定的子字符串, 或检索与正则表达式相匹配的子字符串。如果没有找到任何匹配的子串, 则返回-1, 在此实例中-1表示输入的电子邮件格式有误, 不符合正则表达式的规范。
2.7 手机号码
手机号码的验证主要是判断它是否为数字, 如果输入汉字或者字符则输入错误, 此部分利用isNaN来判断当前输入的是否为数字, isNaN表示返回一个Boolean值, 指明提供的值是否是保留值NaN (不是数字) 。
2.8 留言信息
留言信息主要判断输入字符的长度, 如果超过40个字符出现错误提示。程序利用form1.liuyan.value.length来获取当前长度来判断是否超出范围, 如果超出范围则出现alert错误提示, 并且利用form1.liuyan.focus () ;获取焦点, 同时利用form1.liuyan.select () ;选中当前字符, 如图3所示。
2.9 信息提交判断
此部分代码主要使用confirm方法, confirm是Windows中的一个方法。它可以弹出一个包含“确定”与“取消”的对话框, 如果用户按下了确定, 返回true;如果按下了取消, 返回false。form1.reset () ;表示重置表单中的所有信息, 程序中/n的含义表示在JavaScript中的回车, 如图4所示。
2.1 0 计算字符
在留言信息中可以计算当前字符的数量, onkeydown和onkeyup是键盘的两个事件, 通过onkeydown="showlen (this) "和onkeyup="showlen (this) "这两个事件调用showlen () 函数, 表示每输入一个字符都会有当前的数值变化, 利用form1.contentlen.value=obj.value.length;把当前的字符显示到contentlen文本框中。
style="border-width:0;background:transparent;"表示隐藏文本框的边框。
2.1 1 密码强度
密码强度判断主要是通过以下4个函数构成, 分别是CharMode () , bitTotal () , checkStrong () , pwStrength () , 如图5所示。
2.1 1. 1 CharMode函数
CharMode () 主要是测试输入的每一个字符都是哪一类, 主要分为4类, 数字、大写、小写和特殊字符。
2.1 1. 2 modetotal函数
Modetotal函数计算出当前密码一共有多少种模式, 此部分使用了不太常用的移位操作符>>>, 它是一种“无符号”右移位操作符 (>>>) , 它使用了“零扩展”:无论正负, 都在高位插入0。移位可与等号 (>>>=) 组合使用时, 操作符左边的值会移动由右边的值指定的位数, 再将得到的结果赋回左边的变量。
2.1 1. 3 checkpwd函数
Checkpwd函数是返回密码的强度级别, 主要分为4个级别0, 1, 2和3以上, 主要利用循环方式把当前输入的密码进行按位或的运算, 分别会得出0, 1, 2和3以上。
2.1 1. 4 pwdstrong函数
pwdstrong函数是当用户放开键盘或密码输入框失去焦点时, 根据不同的级别显示不同的颜色。
通过以上JavaScript版表单验证程序的学习, 基本可以使用学习过的知识进行实例的操作, 此表单验证基本囊括了目前收集客户信息时需要验证的内容, 在以上程序讲解中, 读者可能会注意到正则表达式这个概念经常出现, 在JavaScript的表单验证中起了很重要的作用, 目前关于正则表达式出版了很多相关的书籍提供参考, 书中对验证的介绍更加详细 (包括一些复杂验证) , 此程序的介绍意在抛砖引玉, 使更多的初学者入门, 并深入学习。
3 结语
以上代码是在Internet Explore6.0、Internet Explore7.0中测试通过, 实例截图为Internet Explore6.0中运行效果。此表单验证比较简单, 此程序的学习对于初学者来说有很大的帮助, 该实例长期作为JavaScript这门课程的一个典型实例为学生进行讲授, 在一些报名系统中表单验证程序均使用此代码, 所以此实例的学习对于今后想深入学习JavaScript这门语言的读者有一定促进作用。
摘要：通过实例对表单验证程序进行详细讲解, 实例中基本包括了用户在填写表单时需要验证的信息, 每部分功能使用函数来完成, 这让初学者能够很容易接受并且理解语句段的含义, 快速地掌握JavaScript这门语言。
并发程序验证 篇5
当今，工作流技术的应用越来越广泛，它也逐渐成为计算机领域的研究热点。而工作流设计的正确与否直接影响工作流执行期间的正确性，基于此人们也越来越认识到在过程定义阶段保证工作流模型正确的重要性。目前，工作流的模型验证已经成为工作流技术的研究领域之一，但大多数研究都只是针对单个工作流实例的研究，其中有一部分研究涉及单个工作流实例中多个任务的并发。文献[1,2]基于数据资源语义及其约束的分析为基础，扩展Aalst的工作流网为资源语义约束工作流网，给出了基于并发矩阵的并发冲突检测算法，并给出了基于锁的并发保证机制。文献[3]提出了基于集合的冲突分析方法，该方法分为两个阶段，在第一阶段从工作流定义中产生集合约束，在第二阶段解决第一阶段获得的集合约束。
但当工作流的多个实例并发执行时，这种情况的并发冲突分析比分析单个工作流实例中任务之间的并发要复杂的多，而且分析方法也有所不同。当存在几个工作流实例中的任务同时对环境中的共享数据进行访问时，我们需要考虑如下并发冲突问题：即读写冲突和写写冲突。
本文对UML状态图进行了扩展;然后把扩展的UML建立的工作流模型转化为Büchi自动机[4]，用Büchi自动机之间的积表示多个工作流实例的并发模型;接着给出了根据并发模型中标记的命题公式判断并发冲突的定理，并进行了证明;最后，给出了一个并发冲突检测算法。
2 扩展的UML状态图到Büchi自动机的转化
2.1 扩展UML状态图
我们可以通过UML状态图[5,6]对工作流建模，并通过几个UML状态图之间的同步表示多个工作流实例的并发，但由于UML状态图自身就存在并发的特性，所以会使得证明很复杂。为了消除UML状态图自身的并发性，降低证明的难度，本文把UML状态图转化为Büchi自动机，在实现这一转化之前，我们需要扩展UML状态图。
定义2.1(扩展的UML状态图)扩展的UML状态图是ES=(S,init,Labs,￡,T,ρ)，其中：
1)S是有穷状态集合;
2)init是初始状态;
3)Labs是迁移标记集合，它是元组(source,event,guard,action,target)，其中source是迁移的源状态，event是触发迁移的事件，guard是迁移的监视条件，action是迁移触发时发生的动作，target是迁移的目标状态;
4)￡是状态标记集合，它是命题集合{TR(Di),TW(Dj),True}，其中Di,Dj表示工作流环境中的共享数据，没有读写操作时状态标记为True;
5)T哿2S×Labs×2S是迁移集合;
6)ρ：S→2S是状态精化函数，刻画状态间的层次(父/子)关系.
下面用扩展的UML状态图表示一个实例，图1表示的是某人用银行卡的母卡在账户里存入一定数额的人民币，图2表示的是与此同时另一个人正在用该银行卡的子卡刷卡消费。
这里不再详述UML状态图的操作语义，请参考文献[6,7,8,9,10]。扩展后的UML状态图的操作语义与UML状态图的操作语义只是稍有不同，但在状态标记为True时，语义与原来的相同，而当状态标记为TR()或TW()时，首先要完成对环境中数据的读写操作，然后再执行与原来语义中相同的一系列动作。
2.2 扩展的UML状态图到Büchi自动机的转化
在进行扩展的UML状态图到Büchi自动机前，下面先介绍一下Büchi自动机的定义。
定义2.2(Büchi自动机)Büchi自动机A=(AP,S,Δ,I,L,F)，其中：
1)AP是有穷命题集合;
2)S是有穷状态集合;
3)Δ哿S×S是状态间的迁移关系;
4)I哿S是初始状态集合;
5)L:S→2AP是用命题集合中的命题标记状态的标记函数;
6)F哿S是接受状态集合.
我们假设每个单独的工作流实例都是正确的，下面给出转化过程：
1)Conf0=(init)，把init的所有活跃子状态的初始状态加入Conf0中
2)从事件队列中删除当前触发事件，得到可以被当前事件使能的所有迁移集合
3)检查迁移集合中是否存在冲突的迁移，如果存在则根据迁移间的优先关系进行触发
4)在触发之前，检查迁移所在源状态的状态标记集合，如果标记为True，则直接触发;如果存在读、写标记，则从环境中完成读写操作后才能触发，如果要进行操作的资源暂时不可用，而其它使能迁移的标记为true或其操作的资源可用时，则先进行触发，如果没有这样的使能迁移，则待触发的迁移等待资源可用时进行触发
5)根据迁移关系到达所有可达状态，如果当前触发状态没有其它迁移则从当前格局中删除，否则保留;把所有可达状态中与当前格局中不同的状态加入当前格局，生成新的格局;如果生成的新格局中没有新状态，则算法终止，生成错误信息
6)新格局的状态标记为前继格局中未触发状态的与触发后可达状态的状态标记两者状态标记的合取
7)如果格局中的状态都为终止状态，则算法结束，否则跳到2)。
我们没有在图1和图2中的模型引入层次结构，所以它们通过上述转化过程，得到的Büchi自动机模型与原来的模型相同。
3 建立并发工作流的模型
3.1 Büchi自动机的积
为了建立多个工作流实例并发执行的模型，前面我们已经给出了扩展的UML状态图到Büchi自动机的转化过程，下面我们应用Büchi自动机的积[11]建立并发工作流的模型。
定义3.1(Büchi自动机的积)给定两个Büchi自动机A=(AP1,S1,Δ1,I1,L1,F1)和B=(AP2,S2,Δ2,I2,L2,F2)，它们做积生成的Büch自动机为C=(AP,S,Δ,I,L,F)，其中：
1)AP=AP1∪AP2;
2)S=S1∩S2;
3)(
4)(s0,t0)∈I当且仅当s0∈I1且t0∈I2;
5)L(s1,t1)=L1(s1)∧L2(t1)s1∈S1,t1∈S2;
6)(s,t)∈F当且仅当s∈F1且t∈F2.
3.2 实例的并发模型
根据Büchi自动机的积的定义，我们建立图1和图2的并发模型。
4 并发工作流的验证
4.1 并发冲突的判定
通常，判定模型时候正确都是通过判定模型是否满足某些性质，这里，并发工作流模型是正确的当且仅当模型中不存在并发冲突即存在读写或写写冲突。下面给出判定工作流模型中是否存在并发冲突的定理。
定理4.1(工作流并发冲突)并发工作流实例间存在并发冲突当且仅当存在TR(Di)∧TW(Di)或TW(Di)∧TW(Di)是Büchi自动机建立的并发模型中某个状态的状态标记的子公式，其中Di是工作流环境中的共享数据。
证明：先证必要性，在扩展的UML状态图模型转化为Büchi自动机模型和Büchi自动机间作积的过程中状态标记都是合取形式，而我们前面又假设每个单独实例都是正确的，所以它们的状态标记不可能存在有TR(Di)∧TW(Di)或TW(Di)∧TW(Di)的形式或是某个状态标记的子公式，现在我们已知并发工作流实例间存在并发冲突，即存在读写或写写冲突，由前面分析知并发冲突只可能发生在用Büchi自动机建立并发模型的过程中，并且存在并发工作实例中的任务同时读写或写写工作流环境中的共享数据，即TR(Di)∧TW(Di)或TW(Di)∧TW(Di)某个状态标记的子公式;
再证明充分性，由于存在TR(Di)∧TW(Di)或TW(Di)∧TW(Di)是Büchi自动机建立的并发模型中某个状态标记的子公式，即并发模型中存在并发冲突，前面我们已经假设每个单独实例都是正确的，所以每个单个实例中的任务间都不存在并发冲突，并发冲突只可能在多个工作流实例的并发过程中产生的。
4.2 验证算法
由于多个工作流实例并发会使得生成的状态空间会很庞大，我们这里使用on-the-fly技术[12]，它是一种根据需要生成状态空间而不用生成整个状态空间的技术。假设sub(F)表示状态标记F的所有子公式，下面给出根据上述定理验证Büchi自动机建立的并发模型正确性的算法：
算法的复杂度为O(m×n)，其中m为工作流环境中共享数据的数目，n为并发模型中的状态数。最好情况只检测1次，即在初始状态检测出对于第一个共享数据就存在并发冲突，最坏情况是检测m×n次，即生成最后一个状态并检测出它对于最后一个共享数据存在并发冲突。
根据验证算法，检测到图3中(s4,t3)存在读写冲突，检测到冲突后算法终止。
6 结束语
本文扩展了UML状态图，在其中加入了状态标记;给出了扩展的UML状态图到Büchi自动机的转化过程，通过Büchi自动机间的积建立并发工作流模型;提出了判定是否存在并发冲突的判定定理，并给予了证明;给出了验证并发模型正确性的算法。本文的侧重点是并发工作流模型的验证，但还存在着许多工作要进一步研究：本文只给出了检测是否存在并发冲突，而没有给出检测到并发冲突后使用何种策略解决冲突，这是我们下一步研究的方向;如何直接通过UML状态图之间的同步表示并发工作流模型，并使用相关的方法降低验证的复杂性，这也是我们下一步研究的方向。
参考文献
[1]胡乃静,顾宁,施伯乐.基于语义约束的资源工作流并发正确性验证[J].计算机研究与发展,2003,40(5):712-719.
[2]胡乃静,赵亮,罗永强.基于资源限制流图的工作流并发结构的正确性验证[J].小型微型计算机系统,2003,24(7):1289-1292.
[3]LEE M,HAN D,SHIM J.Set-based access conflict analysis of concurrent of workflow definition[J].Information Processing Letters,2001,80:189-194.
[4]Giannakpoulou D,Lerda F.From States to Translation:Improving Translation LTL Formulae to Büchi Automata[C].Formal Techniques for Networked and Distributed Sytems-FORTE2002:22nd IFIP WG6.1.International Conference,Houston,Texas,USA,Berlin:Springer-Ver-lag,2002,2529:308-326.
[5]HAREL D.STATECHARTS:A VISUAL FORMALISM FOR COMPLEX SYSTEMS[J].Science of Computer Programming,1987,8:231-274.
[6]董威,王戟,齐治昌.UML Statecharts的模型检验方法[J].软件学报,2003,14(4):750-756.
[7]李留英,王戟,齐治昌.UML Statechart图的操作语义[J].软件学报,2001,12(12):1864-1873.
[8]周颖,郑国梁,李宣东.面向模型检验的UML状态机语义[J].电子学报,2003,31(12A):2091-2095.
[9]蒋慧,林东,谢希仁.UML状态机的形式语义[J].软件学报,2002,13(12):2241-2250.
[10]Harel D,Naamad A.The STATEMENT Semantics of Statecharts[J].ACM Transactions on Software Engineering and Methodology,1996,5(4):293-333.
[11]Berard B,Bidoit M,Finkel A,et al.Systems and Software Verification-Model checking Techniques and Tools[M].Berlin:Springer-Verlag,2001.
并发程序验证 篇6
形式化方法是保证微内核操作系统正确性的重要方法。形式化验证[1]就是从数学上完备地证明系统是否实现了设计者的意图,是指用形式化方法描述程序的规范,然后通过一定的验证规则对这些形式化规范以及相关代码进行验证,判断这个程序是否依照程序规范所指示的方式执行主要包括模型检测和定理证明。定理证明[2]是将软件按照需求、设计描述为形式化系统,将需要满足的性质描述为系统中的定理,并建立推理规则,将待检测软件的各个要素与形式化系统中的变量对应起来,证明这些要素满足系统中的定理和规则。模型检测[3]是将测试对象建立状态机模型,将待检测属性用逻辑语言描述,然后用有限状态穷举的方法判定状态机模型是否满足用逻辑语言描述的待检测性质。本文主要是在UPPAAL中使用模型检测方法,对微内核操作系统程序验证方法进行探索和研究。
1 模型检测工具 UPPAAL
UPPAAL[4]是由瑞典的Uppsala大学与丹麦的Aalborg大学于1995年联合研发的一种以R.Alur和Dill提出的时间自动机作为行为模型的自动验证工具,可以用于实时系统模拟、仿真、验证,主要采用一组带有整形变量的时间自动机对实时系统的行为进行模拟,可以有效地对实时系统建模,模拟和验证,它可以验证实时系统中的可达性以及由可达性所衍生的一些性质,特别适合对实时系统的安全性和有界活性进行自动验证,从而确保了系统在实际运行中的高度正确性。
UPPAAL对系统性质的描述采用形式化描述语言CTL(timed computation tree logic)逻辑,UPPAAL中的模型检测采用的方法是状态空间的穷搜索,其自动验证器主要用于检查简单不变式,系统的安全性,可达性以及受限活性等。CTL查询语言由路径公式和状态公式组成,状态公式描述单独的状态;路径公式量化模型的路径或轨迹,可以分为可达性、安全性、活性。UPPAAL使用的规范验证语言形式如下:
Prop::=A []Expression|E<> Expression|E []Expression|A<>Expression|Expression Expression
UPPAAL使用的规范验证语言归纳见表1:
具体查询语句的含义如下,其中p、q表示某个状态性质:
(1)E<>p:表示Possibly,存在一条路径,p最终成立,E<>p为真当且仅当在时间自动机中存在一个序列S0→S1→…→Sn,使得S0是起始状态,Sn是p。
(2)A[]p: 表示Invariantly,对于所有的路径,p总是成立,A[]p等价于notE<>notp。
(3)E[]p: 表示Potentially always,存在一条路径,p总是成立。在时间自动机中,E[]p为真当且仅当存在一个序列S0→S1→…→Si→…使得p在所有状态si中得以满足。
(4)A<>p: 表示Eventually,对于所有的路径,p最终成立,A<>p等价于notE[]notp。
(5)p→q: 表示Lead to,无论何时p成立,q最终成立,p→q等价于A[](p implyA<>q)。
2 基于 UPPAAL的程序验证
2.1 验证的研究方案
模型检测[5]使用状态空间搜索的办法来全自动地检验一个有穷状态系统是否满足其设计规范。这类方法的优点在于它有全自动化的检测过程且验证速度快、效率高,并且如果一个性质不满足,它能给出这个性质不满足的理由,据此可对系统描述进行改进。
在模型检测中涉及两种形式说明语言:性质说明语言,例如CTL,用于描述系统的性质;模型描述语言,例如时间状态自动机,用于描述系统的模型。模型检测技术用于检验由模型描述语言描述的系统模型是否满足性质说明语言描述的系统性质。
因此,采用模型检测方法对程序进行验证时主要分为建模、规约、验证三步。其中,建模是采用时间状态自动机对程序进行建模分析;规约是对抽取的程序性质进行描述;验证是通过模型检测工具UPPAAL来检验在所建立的模型上,给出的系统性质是否能够得到满足。基于模型检测的验证研究方案如图1所示。
2.2 ucosII 任务管理在 UPPAAL中的模型表示
本节以微内核操作系统ucos-II[6]任务管理部分中的taskinitusers .c文件中初始化用户任务源函数代码作为实例进行分析。μcosII的任务看起来与任何C函数一样,具有一个返回类型和一个参数,只是它从不返回,任务的返回类型必须被定义成void型,任务必须是图2、图3两种结构之一:
根据所需验证代码实现的功能,通过函数调用、同步信号等形式,判断返回值情况以及函数调用是否成功,建立代码到UPPAAL模型的对应关系,对应的模型如图4、图5所示。
2.3 属性表示及验证
利用UPPAAL验证器进行属性的验证,可对如下的性质进行验证:
(1)E<>Initialize_user_tasks.Internal_error_Occurred验证Internal_error_Occurred状态是否可达。若可达则说明存在一条路径从函数的入口到达该状态,反之亦然。能够有效自动的判定,程序中的重要状态是否可达,从而验证程序编写的正确性。
(2)A []not deadlock可以验证该函数是否出现死锁。若出现死锁,则说明函数的编写有问题,不能正常的传递参数,得到正确的返回值等信息,可以根据模型,动态跟踪错误发生的位置。
验证结果如图6所示。
由验证结果可以清晰的看出,所建立的模型不会产生死锁,Internal_error_Occurred状态是可达的。根据这些属性的验证结果,当发现代码的不安全和不完善后,可以及时的进行修改,以满足代码正确性的要求。
3 结束语
在形式化验证程序正确性的领域中,模型检测以其自动化程度高、强大的时态逻辑描述能力而得到了广泛的研究与应用。模型检测基于时态逻辑,为验证对象建立状态机模型,将待检测属性用逻辑语言描述,然后用有限状态穷举的方法判定状态机模型是否满足用逻辑语言描述的待检测性质,是形式化验证的主流方法之一。本文采用模型检测方法对微内核操作系统的程序进行分析和验证,采用这种方法对程序进行验证的自动化程度高,用时间自动机对程序分析结构进行建模,形象且直观易懂,通过实验的验证结果可知,模型检测方法可以应用于微内核操作系统软件的验证,能够得到正确的验证结果,具有一定的研究和验证实用价值。
摘要：随着航天、航空工业的发展,机载嵌入式软件的可信属性验证是新一代飞机研制最关注的软件质量保障问题。形式化方法具有严密的数学基础,能够准确的对系统进行建模、描述和验证,能够在软件系统的设计初期发现潜在的错误,是保证机载软件可信性和安全性的软件正确性验证技术。形式化验证以形式化描述为基础,对所描述系统的特性进行分析和验证,以评判系统是否满足期望的性质,分为定理证明和模型检测两类。文章研究模型检测方法应用于程序形式化描述和验证的技术,提出基于模型检测的验证程序正确性的方案,并进行微内核操作系统程序分析,最后在UPPAAL中进行程序属性的验证。