没有合适的资源?快使用搜索试试~ 我知道了~
参数化数据结构在有界模型检查中的应用
理论计算机科学电子笔记174(2007)3-16www.elsevier.com/locate/entcs使用参数化数据结构进行有界模型检查1ErikaA'brah'amMarcHerbstrittBerndBecker2Albert-Ludwigs-University,Freiburg im Breisgau,德国马丁·斯特鲁恩3Christian-Albrechts-University,Kiel,Germany摘要有界模型检测(BMC)是一种成功的反驳方法,不仅可以检测电路和其他二进制系统中的错误,还可以检测具有更复杂域的系统,如时间自动机或线性混合自动机。固定长度的反例由可判定逻辑中的公式描述,并由合适的求解器检查其满足性在早期的论文中,我们分析了如何通过适当的编码作为公式的反例和选择性的冲突学习来加速线性混合自动机的BMC。在本文中,我们介绍了参数数据库的内部求解器结构,利用BMC问题的对称性,显着降低了内存需求的求解器。保留字:混合自动机,参数数据结构,SAT。1介绍有界模型检验(BMC)[10]是一种成功的,相对年轻的反驳方法,在过去几年中得到了非常广泛的研究和应用,例如[12,13]的一些工业应用。 从系统的初始状态开始,BMC算法考虑具有增加的长度k = 0,1,.对于每个k,算法检查是否存在反例对于给定的长度,即,是否有一个从初始状态开始的计算这导致一个状态在k步中违反系统规范1这项工作得到了德国研究委员会(DFG)的部分支持,作为跨区域合作研究中心“复杂系统的自动验证和分析”(SFB/TR 14 AVACS)的一部分如需详细信息,请参阅www.avacs.org2{eab|赫伯斯特里|becker}@ informatik.uni-freiburg.de3ms@informatik.uni-kiel.de1571-0661 © 2007 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2006.12.0194E. Abraham等人/理论计算机科学电子笔记174(2007)3基本上,BMC可以应用于所有类型的系统,其中在有限数目的步骤内的可达性可以用可判定逻辑来表示。例如,对于离散系统,使用一阶谓词逻辑,而线性混合自动机的分析[4,24]需要一阶逻辑公式,(R,+,,0, 1)[18].时间自动机被处理,例如,在[29,32,6,35]中。此外,所考虑的规范类型可以具有不同的逻辑域。我们处理安全属性:违反安全属性是通过声明计算的最后一个状态不满足指定来表示的。附加的循环确定技术扩展了该方法,以验证某些问题类的属性(参见例如[11、17])。一旦一个固定长度的反例的存在性由某个公式表示,我们需要检查该公式是否满足:该公式是满足的,当且仅当该长度的计算可以违反该规范。在离散情况下,检查由SAT求解器执行,即,布尔满足性检查器,而在混合离散-连续的混合自动机和时间自动机的情况下,检查通常通过组合SAT和LP求解器来完成(线性规划,见5.2节)。一些流行的求解器是,例如,[28],Berk- Min [23],MiniSAT [20],HySat[21],MathSAT [5],CVC Lite [8],and ICS [16]. 我们如以下部分所介绍的,该方法不限于任何固定的应用领域。我们通过检查一些离散系统(电路)和一些线性混合自动机的安全性来说明它的优点。我们在AVACS项目[7]中的研究目标之一是提高BMC对大型混合自动机的适用性。在早期的论文[3]中,我们集中讨论了如何通过将反例适当编码为公式以及通过选择性冲突学习来加速线性混合自动机的BMC。采用这些技术是为了改善CPU运行时间。然而,我们观察到,对于某些示例,所需的实际时间比CPU时间长得多对于长的反例,相应的公式变得非常大,例如在[22]中所述。此外,Shtrichman [30]认为学习会增加记忆消耗。当内存需求达到计算机的内存大小时在本文中,我们将讨论如何解决BMC问题所需的内存大小可以减少,而不增加求解器的运行时间。其主要思想是利用BMC问题的对称性,并以参数形式存储公式的对称部分我们引入参数数据类型的内部求解器结构,并表明这些参数结构的使用显着降低了求解器的内存需求实验结果表明,CPU时间没有增加,而且,由于对内存的需求较低,交换发生得更晚,从而缩短了系统时间。本文的组织如下:在第2节中,我们回顾BMC方法,然后在第3节中介绍参数数据库。电路的实验结果在第4节中给出。第五节将结果推广到线性混合自动机 最后,在第6节中,我们讨论了相关的工作,并得出结论。E. Abraham等人/理论计算机科学电子笔记174(2007)352有界模型检验在介绍我们的工作之前,我们首先简要回顾一下离散转移系统及其有限游程作为一阶谓词逻辑公式的编码,如BMC [10]中所介绍的那样。此外,我们描述了最先进的求解器的相关细节,用于检查这些公式的满足性。2.1离散转移系统下面,我们形式化离散转换系统。这种定义允许处理由标准时序电路指定的转换系统。另一方面,它可以扩展到线性混合系统的建模。定义2.1[离散转换系统]离散转换系统(D)是一个元组(V,L,I,T),其中V是布尔变量的有限集合,L是节点的有限集合我们用V来表示赋值集合ν:V→ {0, 1},用V =(L× V)来表示状态集合。集合I定义初始状态,T(L×2V×V×L)将跃迁关系指定为具有典型元素的有限跃迁集合t.我们写((l,ν),(lJ,νJ))∈ti <$t=(l,μ,lJ),其中(ν,νJ)∈μ。游程是一个有限序列σ0,σ1,.,σn使得σ0∈I且(σi,σi+1)∈ti ,其中对某些ti∈T,i =0,... .,n−1。一个状态是可达的,如果有一个运行导致它。由于我们处理的是有限系统,所以对于所有的t∈T,初始条件和转移可以用一阶逻辑公式Init(s)和Transt(s,sJ)来描述,其中s和sJ明确表示给定系统公式:s =(v0,. ,v,m)是所 有 变 量 的序列,并且SJ=(v,J,. ,vJ)0m的它们的副本,以描述过渡后的目标估值。让此外,Safe(s)是描述系统的安全属性的一阶逻辑公式。固定长度k的反例,即,违反安全属性的长度为k的游程,可以通过以下公式描述:.Σk(s0,.,sk)= Init(s0)i=0,.,k−1t∈TTranst(si,si+1) 安全(sk)。从k= 0开始,迭代地增加k∈N,BMC检查k是否满足要求。算法终止,如果dk是满意的,即,不安全状态可以从初始状态分k步到达。2.2安全性检查通过最先进的DPLL(Davis-Putnam-Logemann-Loveland [15,14])SAT求解器检查描述长度为k的反例的公式Rk在满足性检查开始之前,布尔公式被转换为合取范式(CNF)。为了使公式尽可能小,使用辅助布尔变量来构建CNF [34]。CNF形式的公式是子句的合取,而每个子句是文字的析取。我们区分正和负文字,是布尔变量或其否定。6E. Abraham等人/理论计算机科学电子笔记174(2007)3为了满足公式,必须满足每个条款,即,至少有一个字面值必须为真。 SAT求解器为变量赋值 以迭代的方式。在每一个决定之后,即,自由选择赋值,求解器通过搜索unit-clause来传播赋值,因为除了一个之外的所有文字都已经是假的,因此最后一个未赋值的文字被暗示为真。如果两个unit-clauses对同一个变量有不同的值,则发生冲突。在这种情况下,发生冲突分析,导致非时序回溯和冲突学习[9,27]。直观地,求解器使用蕴涵树对一些单位子句应用归结,并插入一个新的子句加强该问题约束和限制了进一步搜索的状态空间。本文的一个重要观点是使用监视文字来检测单位子句[28]。基本思想如下:如果在一个子句中有两个未赋值(或已经为真)的变量,那么这个子句就不能是一个unit-clause。因此,在每个子句中只观察两个未赋值或真变量就足够了,我们称之为观察字面量。如果其中一个监视字面值变为假,则我们在子句中搜索另一个字面值,该字面值未赋值或已经为真,并且与另一个监视字面值不同。只有当我们找不到任何新的表文字时,这个子句才确实是一个单位子句。使用这种方法,我们必须在决策后确定单位子句的子句数量可以显着减少。3对称与参数化数据结构在本节中,我们将介绍如何通过参数化求解器内部数据结构来利用BMC问题的固有对称性。3.1BMC问题BMC问题的公式具有特殊的结构:它们描述了从初始状态开始,执行k个过渡步骤,并导致违反规范的状态的计算。 因此,由SAT求解器生成的子句集合可以被分组为描述(1)初始条件的子句(I-子句),(2)一个转换(T-子句),(3)违反规范(S-子句)。 T子句可以被进一步分组为描述T子句的k个k计算步骤。这k个T子句集描述了相同的转换关系,但在不同的时间点。这意味着,它们实际上是相同的,直到重命名变量。例如,在一个示例中,BMC问题的第三次迭代可以由如图1所示的子句集表示。表示第二个过渡步骤的T子句与第一个步骤的T子句相同,但对于所有变量v和索引i,vi被vi+1替换;我们将该替换写为[vi+1/vi]3.2参数化数据结构由于不同步骤的T子句在变量重命名之前是相同的,因此存储转换步骤的参数化版本(实际上是转换)就足够了。E. Abraham等人/理论计算机科学电子笔记174(2007)37I子句T子句S子句(x0 y0),. (x0y1z0),.,(x1y1z0)(x1y2z1),. ,(x2y2 z1)(x2y3z2),.,(x3y3 z2)(y3z3),.Fig. 1. 子句集关系,并且记住重命名以便计算关于k个不同计算步骤的信息。如果我们需要某个转换步骤的子句,例如确定单位子句或用于归结,我们只需相应地重命名参数T子句中的对于上面的例子,我们可以存储参数T子句集(x0y1z0),. ,(x1y1 z0). 计算的第一步由该子句集描述。应用替换[vi+1/vi]([vi+2/vi])给出描述第二(第三)计算步骤的子句集合。为了保持求解器结构简单,使用快速且不复杂的重命名机制非常重要查找表将是一个可能的解决方案,但是,我们预计,他们将导致增加计算时间。相反,我们采用了一种更自然、更简单的命名约定,包括三个阶段:• 变量在求解器内部不是由整数表示,而是由一对整数(a,i)表示:抽象ida标识变量,实例idi标识变量的实例,即,变量的值被考虑的时间实例例如,在一个示例中,如果x具有抽象ID 5,则x处于初始状态,即, 在第一个过渡步骤之后,由(5,0)表示x1,由(5, 1),并在第k个步骤后,对于xk,我们有(5,k)。 变量的否定由抽象id表示,阴性例如,在一个示例中,x3被存储为(-5,3)。常量独立于它们被求值的状态,其实例id为-1。下面我们把常量当作变量;如果我们说我们增加了变量的实例id,那么我们的意思是,它的实例ID只在它是非负数的情况下才增加。• 条款的内容,即,它的字面量现在由整数对的列表表示。例如,文字(x0,x1)存储为((5, 0),(−5,1))。• 最后,每个子句由一对非负整数(a,i)引用,其中抽象ida标识参数子句,通常通过子句列表中的索引,实例idi标识其实例。参数子句的第i个实例包含该子句的字面量,每个(非负)实例ID都增加i。例如,在一个示例中,如果第7个参数子句有文字((5, 0),(-5,1)),则(7, 0)指的是具有文字((5, 0),(-5,1))的子句,而(7, 1)代表子句的文字((5, 1),(−5,2))和(7,k)表示((5,k),(−5,k+1))。通过这种方式,处理参数子句变得非常简单:我们将描述第一个计算步骤的T子句的文字存储为参数子句。为了计算描述第i个计算步骤的T子句的具体文字,我们只需将所有T子句文字的实例id增加i−1。上面我们描述了在for中发生的布尔变量的编码-8E. Abraham等人/理论计算机科学电子笔记174(2007)3参数条款:手表:1:第二章:. . .. . .k:T2T1非参数子句:手表:手表:. . .. . .手表:T2(1)T1(2)第二层(2)T1(k)T2(k)T1(1)图二. 非参数和参数数据结构mula。用于构建CNF的辅助布尔变量的表示需要更多的解释:辅助布尔变量将其编码的公式中出现的最小实例id作为实例id。不同时间点的相同配方的提取使用相同的摘要ID。请注意,参数存储仅适用于子句的文字。我们仍然需要单独存储每个变量实例的赋值。 此外,参数子句的不同实例的监视文字必须单独存储。因此,每个参数子句由其(参数)文字的列表以及另外的监视对的列表组成,监视对的列表确定子句的每个可能实例的当前监视文字,如图2所示。参数子句的实例数由观察对列表的长度隐式给出,因此不需要显式存储。例如,在一个示例中,图2的参数子句具有k个实例1,. ,k,因为它们具有k个附接的手表对。对于冲突分析,求解器以蕴涵树的形式存储哪个单元子句隐含哪个赋值的信息在参数方法中,隐含的单位子句由整数对标识,如上所述现在,让我们看看BMC如何使用参数化结构。首先,我们检查是否存在长度为0或1的计算。在这一点上,求解器包含所有I子句,说明第一个状态是初始的,所有T子句描述第一个计算步骤,所有S子句说明运行中的最后一个状态违反规范。对于每个后续BMC迭代,我们必须如下增加计算长度• 我们通过用新的对扩展监视文字列表来向每个参数T子句添加新的实例,并且• 我们将S子句中的文字的实例id增加I条款仍然未受影响。请注意,我们不需要插入任何新的子句或文字来增加计算长度!这是通过以新的监视对的形式向已经存在的转换子句添加新的实例来完成的。子句的数量和文字的数量保持不变。E. Abraham等人/理论计算机科学电子笔记174(2007)393.3持续学习除了描述反例的从句,我们还必须注意第二种从句类型:冲突从句。在SAT检查期间学习的冲突子句确保搜索不会再次进入相同的搜索路径(或类似的搜索通常,在检查下一个BMC实例之前,在BMC实例的SAT检查期间学习的冲突子句会被删除。然而,它们也可以以Shtrichman [31]的风格部分地重用,从而在搜索开始之前就从SAT搜索中排除搜索路径此外,如果用于解析以生成冲突子句的所有子句都存在于具有增加的实例的下一SAT迭代中,则可以使用增加的实例进行相同的解析。因此,每个这样的冲突条款可以在下一次BMC迭代中添加增加的实例。因此,我们区分以下冲突条款类型:• I-连接子句由I-和可能的T-(连接-)子句的解析产生;它们可以在下一次迭代中重用,因为这些子句也存在于所有后续迭代中,即,可以做出同样的决议• S-连接子句由S-和可能的T-(连接-)子句的解析产生;它们只能与增加的实例一起重用,因为S-子句的实例在下一次迭代中会增加。• T-连接子句仅由T-(连接子句-)子句的分解产生;它们可以像I-连接子句一样被重用,并且像S-连接子句一样额外插入增加的实例,因为所有T-子句都存在于下一次迭代中,具有相同的实例和增加的实例。请注意,源自I-子句和S-子句的冲突子句(IS-冲突子句)不能重用。进一步注意,如果我们在解决过程中不仅记录涉及哪种子句(I、T或S),而且还记录T子句的实例,那么甚至可以学习2个以上的T-连接子句然而,我们的实验表明,学习所有可能的冲突子句实例会导致大量的新子句(或参数情况下的子句实例),在传播新决策时必须考虑其中的每一个。这就是为什么学习太多反而会减慢SAT检查而不是加速它的原因。我们遵循尽可能重复使用连接子句的策略,并在增加一个实例的情况下额外插入T-con连接子句。这个策略在我们的实验BMC框架中是成功的。我们也以参数方式存储冲突子句,类似于I子句、T子句和S子句。在每次迭代之后,除了I-、T-和S-子句的更新之外,还发生以下更新:• 为每个T-constricts子句插入一个新的监视对,• 增加每个S-连接子句中所有文字的实例ID(如果非负)10E. Abraham等人/理论计算机科学电子笔记174(2007)31,和• 删除所有IS-一致性条款。同样,I-合同条款未被触及。3.4变量排序我们的求解器原型使用静态变量顺序来选择决策变量。正如[31]中所建议的,顺序由变量的实例id确定,因此遵循计算的自然时间顺序。尽管如此,我们的参数化数据结构使更多的变量集中的scor- ing算法,如VSIDS[28],它不像纯CNF-SAT求解器那样独立地处理变量,而是在展开的时间框架上对属于一个变量的几个实例的信息进行分组,允许面向问题的动态分配。4实验结果我们实现了一个SAT求解器,主要按照第2.2节中描述的方式工作,但是使用了参数化的内部数据结构。为了查看与没有参数结构的情况的区别,我们还创建了一个修改的求解器,以完全相同的方式工作,但没有参数子句。当创建新的BMC问题实例时,对于T子句和T连接子句,参数求解器通过将新的监视对附加到子句的监视列表来添加新的子句实例在实验中,我们使用了一台配备Intel Pentium 2、 8 GHz CPU和1 GB内存的计算机。请注意,所需的内存与计算机的速度和内存大小无关。但是,如果内存大小低于要求,则会发生交换,这会减慢计算速度我们应用BMC检查VIS基准测试套件中的三个基准测试的不变量[33],涵盖不同的应用领域:Am2910(微控制器),Tcp(通信协议)和UsbPhy(通用串行总线)。图3显示了内存需求:描述了非参数数据结构和参数数据结构通常,在第k次BMC迭代中使用参数子句,T子句的数量可以减少因子k。在迭代i中学习的T-连续子句在每次迭代中通过学习从i+1移动到k;而不是k−i+1子句,我们只需要存储1个参数实例。在这两种方法中,I-子句和S-子句的数量保持不变;I-子句和S-子句也是是值得一提的是,习得的冲突构成了从句的很大一部分存储器需求不能以与子句数量相同的因子来减少必须为所有子句实例存储监视文字。然而,存储器需求仍然显著降低。减少的程度也取决于条款的大小。满足性检查所需的CPU时间大致相同E. Abraham等人/理论计算机科学电子笔记174(2007)3111010参数非参数参数非参数9008007006005004003002001000基准Am2910参数非参数0 50100 150 200 250 300深度k8007006005004003002001000基准TCP0 50 100 150 200 250深度k2000180016001400120010008006004002000基准UsbPhy020 40 60 80 100120140160180深度k图三. 离散VIS基准测试对于非参数和参数求解器(见图7的一些实验数据)。这是由于用于表示变量、文字和子句的自然数据结构。计算参数子句的某个具体实例是通过一些算术加法来完成的5线性混合自动机前面提出的方法可以自然地扩展到线性混合自动机的BMC,这是我们的主要目标,已经在介绍中提到5.1线性混合自动机混合自动机[4,24]是描述具有离散和连续行为的系统的一种形式化模型.它们通常以图形方式进行说明,如图4所示。这个自动机模拟了一个恒温器,它可以感知房间的温度,然后打开和关闭加热器。当控制停留在一个位置和时间流逝时,微分方程形式的流动条件决定了实值变量的连续变化。例如,在位置O中,温度根据对流条件下降-3≤x分 ≤-1。控制可以进入一个位置或停留在一个位置,只要位置的不变量是满意的。 位置o的不变量x≥18确保加热器在最迟在温度达到18度时。如果满足转换条件,控制可以沿着离散跳跃从一个位置移动堆峰值[MB]堆峰值[MB]堆峰值[MB]12E. Abraham等人/理论计算机科学电子笔记174(2007)3乔·奥·萨沃X=2031J在`\11-10≤xstec≤−10,x≥18,,10≤x分≤5,x≤22,,见图4。恒温器从理论上讲,跳变可能导致系统状态的离散变化,这称为跳变效应。例如,在一个示例中,当温度低于19度时,从位置0到ON的转换被启用;温度X在跳变期间不改变。最后,初始条件描述了系统计算的起始点。对于我们的例子,最初加热器是0度,温度是20度。我们考虑一类线性混合自动机[4,24]。应用BMC,一个线性混合自动机的cun-terexamples可以类似于一个随机数的编码在混合情况下,底层逻辑是(R,+,,0, 1)上的一阶逻辑,即,公式是使用实值变量的线性项上的(内)方程的布尔组合转换关系捕获了两种情况:离散跳跃和连续流,这两种情况都必须在BMC编码中表示。有关编码和优化的详细描述,请参见[3]。5.2LP-SAT-检查上述描述固定长度的反例的公式与离散情况一样,由合适的求解器进行检查。由于现在我们处理的是实值变量上线性(非)方程的布尔组合,因此可满足性检查由组合的SAT-LP求解器完成,如图5所示。首先,通过替换每个实约束,即,每个线性(入)方程,通过辅助布尔抽象变量。这个布尔抽象由SAT求解器检查是否满足。如果抽象不能令人满意,那么具体的混合公式也不能令人满意。否则,如果抽象具有解,则LP求解器检查在真实域中是否存在对应的解。也就是说,LP求解器收集所有抽象变量为真的那些真实约束以及所有抽象变量为假的那些真实约束的否定,并使用类似于[21]的基于单纯形的方法来检查它们是否一起满足如果是的话,那么我们就找到了解决具体问题的办法。如果不是,则LP求解器以不满足(不满足)方程组的形式提供解释,该方程组解释了实域中的矛盾分配。SAT求解器现在可以通过在进一步的搜索中排除抽象的解释来细化抽象上述机制被称为惰性满意度检查。 不那么懒惰的变体更频繁地检查实域中的一致性,不仅是完整的布尔解,而且是部分布尔解。这允许更早地检测真正的冲突,并且X<19,x>21E. Abraham等人/理论计算机科学电子笔记174(2007)313布尔抽象SAT-求解器联合UNSAT坐(In)方程组联合坐坐LP−求解器解释图五. 组合SAT-LP-Solver因此也可以更早地回溯这种冲突。虽然LP检查在运行时间上相对昂贵,但早期回溯的优势通常是值得的。然而,懒惰的程度对运行时间至关重要。如果抽象只有很少的解决方案,那么完整的惰性变体可能会更快,而对于有许多解决方案的抽象,惰性较少的变体预计会更有效。在我们的求解器中,LP检查的频率是动态确定的,取决于已经为抽象找到的解决方案的数量在SAT检查期间,我们的求解器还学习LP求解器提供的解释,以细化抽象。这些解释在实值域中是矛盾的,因此我们可以使用所涉及的实值变量的所有可能的重命名来排除它们在我们的求解器中,这些冲突条款,源于实值域,被视为T-冲突条款。5.3结果我们还实现了一个组合的SAT-LP求解器,作为上一节的SAT求解器,但扩展了LP求解器用于检查的实部类似于离散的情况下,我们比较了参数和非参数版本的求解器,使用相同的SAT-LP算法。实验在与离散情况相同的计算机上进行。我们使用Fischer的互斥协议[ 26 ]作为第一个例子,该规范规定了互斥属性,即,在每个时间点,在其临界区中最多有一个过程。第二个例子是铁路道口[24],由3个并行自动机组成:一个模拟火车,一个模拟铁路道口门,一个模拟控制器。该规范要求当列车接近铁路道口时,闸门始终完全关闭。图7显示了Fischer协议的3个进程的运行时间运行时间表明,计算速度不会因参数结构而减慢。图8显示了其余示例的内存消耗,同样是非参数版本和参数14E. Abraham等人/理论计算机科学电子笔记174(2007)3参数非参数参数非参数xi≥Bk/=iJidlei`\,cJtesti`\等一下Jcriti`\Hi:k=0→xi:=04≤xsteci≤15k,xi:=i,04≤xsteci≤1xi≥Bk=i,xi≤A,,、、k:=0、、见图6。Fischer400350300250200150100500参数非参数0 10 20 30 40 50 60迭代200150100500参数非参数0 10 20 30 40 50 60迭代见图7。 Fischer方案3个工艺9008007006005004003002001000Fischer0 5 10 15 20 25 30迭代250200150100500铁路道口0 10 20 30 40 50 60迭代见图8。 4个进程的Fischer协议和铁路示例6结论和相关工作本文介绍了参数数据结构,以减少满足性检验的内存需求,特别是有界模型检验。BMC的应用程序,一些离散和混合的例子,指出我们的方法的实际意义。k=0CPU时间[秒]堆峰值[MB]堆峰值[MB]堆峰值[MB]5E. Abraham等人/理论计算机科学电子笔记174(2007)315大多数关于SAT求解的研究都是在提高运行时效率的重要领域进行的。相关的工作,如处理基本求解器算法,有界模型检查和BMC上下文中的学习等,在引言中已经提到了。我们知道只有两篇论文明确涉及减少BMC内存需求。在[19]中,与我们的方法类似,作者利用了过渡步骤的对称性。然而,他们没有像我们一样引入新的内部数据结构,而是应用量化来将反例描述的k个转换压缩为单个量化项。通过专用QBF求解器检查量化公式的满足性。[22]的方法通过分布式计算解决BMC期间的内存问题在那里,子句集的展开被划分,并且每个划分被分配给网络中的一个组件。重点在于布尔约束传播到本地组件的分布,使得由于分散的组织而实现内存减少。因此,[22]在某种意义上与我们的方法正交,我们通过参数数据结构利用BMC公式的固有对称性。至于未来的工作,我们也正在研究一个并行化方案,结合这两个想法。另一个有趣的点是优化技术的集成,如锥内干扰减少[12]和虽然前者并不限制我们的参数化概念,但后者需要进行可行性研究,作为今后的工作。确认我们感谢Ralf Wimmer和Jochen Schlinger对本文件提出的宝贵意见。引用[1] “CADE’02,” LNAI[2] “CAV’04,” LNCS[3] A'brah'am,E., B. 别担心,F。 Klae dk e andM. Steen,O pt i mizingbondedmod elc hecki ngf orlinearhybrid systems,in:Proc. of VMCAI'05,LNCS 3385,pp. 396-412[4] 巴尔河,C. Courcoubetis,T. Henzinger,P. Ho,X. Nicollin,A. Olivero,J. Sifakis和S. Yovine,混合系统的算法分析,理论计算机科学138(1995),pp. 3-34[5] Audemard,G.,P. Bertoli,A. Cimatti,A. Korni-lowicz和R.李世石,一种基于SAT的求解布尔和线性数学命题公式的方法,在:Proc. of CADE[6] Audemard,G.,A. Cimatti,A. Korni-lowicz和R.李世石,时控系统的有界模型检测,载于:Forte243-259[7] 跨区域合作研究中心14 AVACS:复杂系统的自动验证和分析,http://www.avacs.org。[8] 巴雷特角和S.Berezin,CVC Lite:协作有效性检查器的新实现,在:CAV'04的程序515-518[9] 小巴亚多R. 和p.Schrag,使用CSP回看技术解决现实世界的SAT实例,在:国家人工智能会议(AAAI),1997年。16E. Abraham等人/理论计算机科学电子笔记174(2007)3[10] Biere,A.,A. Cimatti,E. Clarke和Y. Zhu,Symbolic model checking without BDD,in:Proc. ofTACAS193-207.[11]Biere,A.,A. Cimatti,E. M. Clarke,O. Strichman和Y. Zhu,Bounded Model Checking,Advancesin Computers58(2003).[12] Biere,A.,E. 克拉克河Raimi和Y.Zhu,“使用无BDD的符号模型检查的PowerPCTM微处理器的安全特性”,Proc.of CAV[13] Copty,F.,L.菲克斯河Fraer,E. Guinchiglia,G. Kamhi和M. Y. Vardi,Benefits of bounded modelchecking in an industrial setting,in:Proc. of CAV436-453.[14] 戴维斯,M.,G. Logemann和D.Loveland,A Machine Program for Theorem-Proving,Communications of the ACM5(1962),pp.394-397.[15] 戴维斯,M。和H.Putnam,A computing procedure for quantification theory,Journal of the ACM7(1960),pp. 201-215[16] 德韦拉湖和H.陆文辉,地面决策程序的实验评估,载:CAV162-174。[17] 德韦拉湖,H. Ruewald和M. Sorea,Bounded model checking and induction:From refutation toverification,in:Proc. of CAV14比26[18] 德韦拉湖,H. Ruewald和M. Sorea,有限域上有界模型检验的Lazy定理证明,在:Proc. of CADE438-455[19] Dershowitz,N.,Z.李文,基于QBF的有界模型检验,2005年学术会议论文集,北京:清华大学出版第3569页408-414[20] 恩,N。 和N. S?ren ss o n,Anextensib leSAT-sover. ,i n:Proc. ^SAT' 0 3,L N C S 2919,pp. 502-518[21] 我是弗伦茨先生。 和DC。 因此,Eschercietproooofe ngensfororbondd elc hek i ngofhybridss t e m s s e ms s e m s s e m s s e m s s e m s s e m s s e m s s e m s s e m s s e m s s e m s se m ss ,ENTCS 133(2005),pp. 119比137[22] Ganai,M. K.,A.古普塔角,巴西-地Yang和P. Ashar,有效的分布式SAT和基于SAT的分布式有界模型检测,在:Proc. of CHARME334-347.[23] Goldberg,E.和Y. Novikov,BerkMin:A fast and robust SAT-solver,in:Proc. of Date142-149.[24] Henzinger,T.一、 混合自动机的理论,在:Proc。 LICS'96,pp. 278-292.[25] Kuehlmann,A.,有界性质检查的动态转换关系简化。,in:Proc. of ICCAD50比57[26] 林奇,N.,“Distributed Algorithms,” Kaufmann Publishers,[27] Marques-Silva,J.和K. Sakallah,GRASP:A search algorithm for propositional satisfiability,IEEETrans. on Comp.48(1999),pp. 506-521[28] Moskewicz,M. W.,C. F. Madigan,Y.赵湖,加-地Yang和S. Malik,Cha Cha:Engineering anefficient SAT solver,in:Proc. of DAC530-535[29] Niebert,P.,M. Mahfoudh,E. Asarin,M. Bozga,N. Jain和O. Maler,通过满意度检查验证时间自动机,在:Proc. FTRTFT'02,LNCS 2469。[30] Shtrichman,O.,基于SAT的有界模型检验问题的剪枝技术,见:Proc. of CHARME58比70[31] Shtrichman,O.,加速安全公式的有界模型检查,系统设计中的形式方法24(2004),pp。5-24[32] Sorea,M.,Bounded Model Checking for Timed Automata,ENTCS68(2002).[33] VIS Group,VIS:验证和综合系统,收录于:Proc. of CAV428http://vlsi.colorado.edu/-432,也参见www.example.com。[34] Tseitin,G.,关于命题演算中推导的复杂性,见:《构造数学与数学逻辑研究》,1968年。[35] Wo'zna,B., A. ZbrzeznyandW. Pennczek,CheckingeachabilitypropertiesforortimedautomataviaSAT,Fundamenta Informaticae 55(2003),pp. 223-241
下载后可阅读完整内容,剩余1页未读,立即下载
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
我的内容管理 收起
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
会员权益专享
最新资源
- BSC关键绩效财务与客户指标详解
- 绘制企业战略地图:从财务到客户价值的六步法
- BSC关键绩效指标详解:财务与运营效率评估
- 手持移动数据终端:常见问题与WIFI设置指南
- 平衡计分卡(BSC):绩效管理与战略实施工具
- ESP8266智能家居控制系统设计与实现
- ESP8266在智能家居中的应用——网络家电控制系统
- BSC:平衡计分卡在绩效管理与信息技术中的应用
- 手持移动数据终端:常见问题与解决办法
- BSC模板:四大领域关键绩效指标详解(财务、客户、运营与成长)
- BSC:从绩效考核到计算机网络的关键概念
- BSC模板:四大维度关键绩效指标详解与预算达成分析
- 平衡计分卡(BSC):绩效考核与战略实施工具
- K-means聚类算法详解及其优缺点
- 平衡计分卡(BSC):从绩效考核到战略实施
- BSC:平衡计分卡与计算机网络中的应用
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)