没有合适的资源?快使用搜索试试~ 我知道了~
⃝⃝可在www.sciencedirect.com上在线ScienceDirectICT Express 4(2018)51www.elsevier.com/locate/icte自动验证车辆协调米凯尔·阿斯普朗瑞典林雪平大学计算机与信息科学系接收日期:2017年9月1日;接受日期:2018年在线发布2018年摘要在下一代基于道路的交通系统中,车辆交换信息并协调其行动,一个主要挑战将是确保交互规则是安全的并导致进步。在本文中,我们解决的问题,自动验证这种分布式车辆协调协议的正确性。我们提出了一种新的建模方法,通信移动实体的可满足性模理论(SMT)的概念的基础上我们将此方法应用于交叉路口碰撞避免协议,并展示了如何使用该方法来调查这样的协议实现安全和进步的设置。c2018 韩 国 通 信 信 息 科 学 研 究 所 。 出 版 社 : Elsevier B.V. 这 是 一 篇 基 于 CC BY-NC-ND 许 可 证 的 开 放 获 取 文 章(http://creativecommons.org/licenses/by-nc-nd/4.0/)。关键词:形式化验证;车辆协调; SMT;交叉口避1. 介绍高级驾驶员辅助系统(ADAS)正变得越来越复杂和连接。新兴的应用包括车队,碰撞避免和紧急车辆意识。尽管车辆之间的交互越来越多,但该行业目前缺乏确保协作车辆系统的安全性和正确性的方法。例如,目前的ISO26262功能安全标准只涉及车载功能。在本文中,我们提出了一种新的方法来正式建模和自动验证车辆协调,包括模型的环境和不可靠的无线通信。我们建议使用可满足性模理论(SMT)的概念,它允许表达复杂的特定领域的模型,同时也支持正确性属性的我们讨论了不同的建模选择的表达性/易处理性的权衡,并提出了一个系统模型,我们证明,以实现一个有用的平衡。在以前的工作[1]中,我们形式化了一个旨在实现交叉口避碰的协调协议[2电子邮件地址:mikael. liu.se。同行评审由韩国通信信息科学研究所负责https://doi.org/10.1016/j.icte.2018.01.013(ICA)使用车辆间通信。在这项工作中,我们创建了一个非常基本的环境模型,它只包含一个十字路口。我们用它来证明算法的安全性(即,保证它不会以糟糕的状态结束)。现在,我们提出了一个通用的建模框架,用于描述道路,交叉口,车辆和共享资源的集合。我们从我们以前的工作中扩展了案例研究,以解释这个新的更一般的环境模型。此外,我们还展示了案例研究实现逻辑安全和进展的参数条件(而不是我们以前的工作中的逻辑安全)。本文的其余部分组织如下。第2节介绍了我们的系统模型和我们的方法,正式车辆协调。第3节包含了我们的方法的验证。最后,第4节介绍了相关工作,第5节总结了本文。2. 系统模型我们的方法来形式化的车辆协调问题是建模系统作为一组时间依赖性的约束,结合传统的混合自动机描述一个特定的主题车辆。在本节中,我们将描述我们的基本建模框架,包括如何表示物理环境和通信功能。2405-9595/c2018韩国通信信息科学研究所。Elsevier B. V.的出版服务。这是CC BY-NC-ND许可证下的开放获取文章(http://creativecommons.org/licenses/by-nc-nd/4.0/)。=:→⊂:×→∈:≤52米Asplund / ICT Express 4(2018)51C.这使我们能够提供单个实体的更详细的内部模型,并使用关于其可观察行为(包括通信)的假设对其他实体进行建模。最后,考虑转移函数T(i, j),其中i和j是状态,其用于表征主体实体的行为。我们将混合自动机编码为在定时和非定时转换之间交替的转换函数,这是建模混合自动机时的常见过程表1Fig. 1. 系统模型概述。系统.由于篇幅限制,完整的模型无法在此描述,但可以与研究界分享。3. 验证系统模型的组件。构件描述E一组实体(车辆)R一组路由X一组交集一组资源M一组消息S一组状态一组初始状态TSS布尔A转换函数F谓词的有限集合C有限约束我们的建模阶段的目标是提供一组基本的构建块,可以构建一个足够详细的表示系统与合作车辆。因为我们将使用该模型来正式证明协调方法的正确性,所以重要的是平衡表达性(其允许真实的表示)与易处理性(即,以保持模型足够抽象以用于自动化证明)。图1显示了我们的系统模型是如何构建的概述。它由一个“核心”自动机和一组时间相关的约束组成我们将系统建模为元组M(E,R,X,R,M,S,I,T,F,C),其由若干无限集和有限集以及映射组成,如表1所示。注意,集合E、R、X、M、S和I都可以是无限的,从而允许我们对无限数量的汽车、路线、交叉口和通信消息进行建模。谓词(或未解释的函数)的集合F为核心自动机的状态提供语义。函数的允许域和范围是实数(时间)、整数和我们模型中的任何集合。我们在模型中使用的一个未解释函数的例子是tsndMR,表示给定消息的发送时间。C中的约束为我们提供了一种描述环境属性和其他我们需要采用的假设的方法。约束应用于与未解释函数F相同的域,并且还可以包含量词。约束的一个例子(我们不使用)可以是MMtsnd(m)10,这意味着在时间点10之后不发送消息。我们让S中的状态和转移函数T表示特定主体实体的状态和行为系统中其他实体的行为使用我们使用Z3Py实现了我们的模型,它为Z3 v4.3.1定理证明器提供了Python API。本质上,我们有许多一阶谓词逻辑公式,我们将其表示为python函数。这些可以组合成模型M。验证的目的是表明模型M在逻辑上为所有可达状态SrS带来安全状态:M |= i ∈S r:安全i其中safei是安全谓词。最基本的定义安全谓词的一个重要特征是要求实体之间没有冲突。我们称之为noCollision谓词,它表示如果主体实体处于交叉路口,则没有其他汽车可以在同一物理资源中。我们使用有限k-归纳法[3]和安全不变量来确保模型可以由Z3定理证明器[1]处理。在本节的剩余部分中,我们将使用三个重要方面来验证我们的方法:一致性、无崩溃性和进度。我们使用术语一致性来表示模型在逻辑上是合理的,因此模型至少支持一些基本行为。无碰撞意味着我们可以证明,如果车辆遵守协调协议,则不会因协议中的错误而发生碰撞请注意,我们不能保证在一般情况下无碰撞,因为这取决于现实交通场景中的许多其他因素。我们只是证明了协调协议按预期工作。最后,我们证明了该协议也保证了在这个意义上,车辆不能永远等待通过十字路口的进展。3.1. 场景我们已经将我们的正式建模方法应用于一个跨部门的避碰案例研究。该场景是基于一个四路交叉口,车辆可以从所有四个方向到达。研究中的车辆接近交叉口,并执行协调协议(CwoRIS),以同意与其他车辆时,它是安全的通过交叉口。核心自动机和协议形式化的细节在其他地方发表[1],尽管环境和通信模型比我们在这项工作中使用的更简单。CwoRIS协议通过使用与道路的物理区域相对应的资源来确保车辆协调。每个实体都有责任在没有确保它对该资源具有独占访问权的情况下不进入该资源。该协议使用一系列交换的消息和本地数据结构来推断是否存在潜在的冲突:→M. Asplund / ICT Express 4(2018)51-5453图二. 显示参数组合的矩阵(从交叉口中心开始准备交叉口的距离,以及车辆的制动能力),可以证明系统可以避免碰撞。一种资源。该协议还使用优先级来避免循环死锁。3.2. 一致性验证的第一步是确保模型是合理的,因为我们没有使它受到过度的限制。特别是,在系统的自动机中,应该总是可以转换到新的如果模型被卡住,这意味着在现实世界的表示中存在错误。我们引入一个后继函数succSS,在哪里 对于每个状态,它返回一个新的状态,有效过渡。后继函数可以从过渡函数的定义中推导出来,而不需要付出很大的努力。因为succ总是保证为每个输入状态提供输出,所以我们可以通过证明以下公式来证明没有死锁:M|= i,j:T(i,j)T(j,succ(j)).3.3. 无碰撞这里研究的协议可以证明,在某些参数的假设下,保证自由的崩溃图2示出了参数组合的矩阵,对于该矩阵,系统可以被证明避免碰撞。矩阵中的行(y轴)表示到交叉口中心的距离,车辆必须在该距离处制动,除非它已经协商进入交叉口。柱(x轴)表示车辆的最大制动(减速)能力。结果是直观的和预期的。如果汽车具有更高的制动能力,那么它可以在不得不刹车之前更接近十字然而,在这些结果中有趣的是,浅绿色区域代表我们已经在数学上自动证明系统是正确的值,在这个意义上,碰撞不会发生(在正式模型的假设下)。3.4. 进展设计一个可证明安全的交叉口碰撞避免协议是很容易的,它迫使一些或所有的汽车不确定地停止。然而,这样的计划显然是错误的,因为它图三. 显示参数组合(最大可接受等待时间和从接收消息到发送确认的最长时间)的矩阵,可以证明系统在这些参数组合下保持进展。并不能保证车辆到达各自的目的地。因此,重要的是不仅要能够证明没有碰撞,而且要能够证明存在一个边界车辆必须在“不确定状态”中等待的时间。为了实现这一点,我们添加了所有消息都被传递的假设(不需要证明安全性的假设)。该协议只能保证在不丢弃消息的期间内的进度。图3显示了一个矩阵,其中有可能证明系统的进展。我们所说的进步是指实体将不会停留在其访问请求被无限延迟的状态中。矩阵中的行(y轴)表示车辆在决定其进入交叉口的请求是否被准许之前可以被迫等待的最大时间。列(x轴)表示确认消息在发送之前可以延迟多长时间.绿色区域的解释是,如果确认延迟低于给定值,则可以证明系统实现了进展,等待时间不长于x轴上显示的值。本研究的底线是,对于图中导致绿色单元格的所有参数组合,我们已经证明了协调协议是可证明安全的并且没有死锁。考虑到参与者数量无限、通信的明确模型以及连续的时间和空间所涉及的复杂性,这显然是文献中先前描述的一个进步。4. 相关工作一些研究,如Huang等人的研究。[4],使用SMT求解器来验证实时通信协议,但不考虑移动性和空间安全约束。自主交通代理应如何避免碰撞的问题也被正式处理与手动证明策略。例如,Damm等人[5]提出了两辆车碰撞自由度的证明规则。其他研究也采用SMT来验证车辆应用(例如,[6、7])。然而,据我们所知,我们是第一个展示如何使用约束求解器自动验证一个具有无限数量的参与者、明确的通信建模以及连续时间和空间的系统。自动交叉口管理在智能交通领域得到了广泛的探索[8],54米Asplund / ICT Express 4(2018)51尽管通常不关注证明正确性。的参考文献这里提出的协调方法所基于的Comhordu'协调方案是由Bhandal等人形式化的。[9]使用过程代数方法。在若干车辆核查工作中研究了车辆排,包括最近的Kamali等人。[10],他们使用Uppaal模型检查器和逻辑编程的组合我们的工作不同于现有的研究,处理协调车辆的安全性,明确建模的通信协议和消息传递,以及使用的方法,允许大多是自动的,而不是手动验证。5. 讨论和结论在本文中,我们提出了一种车辆协调算法的建模方法。我们表明,在SMT的帮助下,仔细选择适当的模型抽象,可以自动证明系统的属性,否则将无法实现。我们已经能够验证一个完全分布式的交叉碰撞避免协议的正确性,在逻辑安全性和进展。该模型并非没有限制。例如,我们没有包括横向运动和控制,纵向模型是非常基本的。然而,我们已经取得了显着的进展,目前的最先进的建模和验证的智能交通系统与无限数量的车辆,明确建模的通信消息,连续的时间和空间。确认本工作得到了Centrumfoürindustriellinfor-mationsteknologi(CENIIT)项目14.04的支持利益冲突作者声明,本文中不存在利益冲突[1] M. Asplund,A. Manzoor,M. Bouroche,S. Clarke,V. Cahill,Aformalapproachtoautonomousvehiclecoordination , in :D.Giannakopoulou,D.Mry(Eds.),FM 2012:Formal Methods,in:Lecture Notes in Computer Science,vol.7436,Springer BerlinHeidelberg,2012,pp.52比67 网址://dx.doi.org/10.1007/978-3-642-32759-98. casino[2] M.L. Sin,M. Bouroche,V. Cahill,实时分布式系统中动态参与者的调度,第30届IEEE可靠分布式系统研讨会,SRDS,2011年。http://dx. 多岛或g/10。1109/SRDS. 2011。 37.[3] M. Shepherd,S. Singh,G. St.t.a.lmarck,使用归纳和求解器检查安全属性,在:W。Hunt,S.Johnson(Eds.),计算机辅助设计中的形式化127-144. http://dx.doi.org/10.1007/3-540-40922-X 8.[4] J. Huang,J. Blech,A.拉贝角Buckl,A. Knoll,静态调度基于SMT解决方案的时间触发的片上网络,在:Design,AutomationTest in Europe Conference Exhibition(DATE),2012,pp. 509-514[5] W. Damm,H. Hungar,E. R. Olderog,Verification of cooperatingtraf- fic agents , Internat. J. Control 79 ( 5 ) ( 2006 ) .http://dx.doi.org/10.1080/00207170600587531.[6] C. Herde,A. Eggers,M. Franzle,T. Teige,基于hysat的混合动力系统分析,第三届国际系统会议(ICONS),2008年,http://dx。多岛或g/10。1109/ICONS. 2008年。十七岁[7] S. Gulwani,A.基于约束的混杂系统分析方法,载于:A。古普塔河Malik(Eds.),Computer Aided Verification,in:Lecture Notes inComputer Science,vol.5123,Springer Berlin /Hei-delberg,2008,pp. 190-203. http://dx.doi.org/10.1007/978-3-540-70545-118.[8] L. Chen C.,马缨丹属Englund,协同交叉口管理:一项调查,IEEETrans. 内 特 尔 运 输 单 系 统 17 ( 2 ) ( 2016 ) 。http://dx.doi.org/10.1109/TITS.2015.2471812.[9] C.班达尔湾Bouroche,A. Hughes,A process algebraic description ofa temporal wireless network protocol,in:Proceedings of the FourthInternational Workshop on Formal Methods for Interactive Systems,2011.[10] M. 洛杉矶卡马里Dennis,O.McAree,M.Fisher,S.M.Veres,自动车 辆 队 列 的 正 式 Comput. 《 编 程 》 ( 2017 年 ) 。http://dx.doi.org/10.1016/j.scico.2017.05.006网站。
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 5
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- WebLogic集群配置与管理实战指南
- AIX5.3上安装Weblogic 9.2详细步骤
- 面向对象编程模拟试题详解与解析
- Flex+FMS2.0中文教程:开发流媒体应用的实践指南
- PID调节深入解析:从入门到精通
- 数字水印技术:保护版权的新防线
- 8位数码管显示24小时制数字电子钟程序设计
- Mhdd免费版详细使用教程:硬盘检测与坏道屏蔽
- 操作系统期末复习指南:进程、线程与系统调用详解
- Cognos8性能优化指南:软件参数与报表设计调优
- Cognos8开发入门:从Transformer到ReportStudio
- Cisco 6509交换机配置全面指南
- C#入门:XML基础教程与实例解析
- Matlab振动分析详解:从单自由度到6自由度模型
- Eclipse JDT中的ASTParser详解与核心类介绍
- Java程序员必备资源网站大全
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功