基于惰性抽象与插值优化的嵌入式汇编程序实时可达性验证新方法
《IEEE Access》:Verifying Reachability With Real-Time Properties of Embedded Assembly Programs Based on Lazy Abstraction and Refinement
【字体:
大
中
小
】
时间:2025年12月17日
来源:IEEE Access 3.6
编辑推荐:
本研究针对嵌入式系统日益复杂化背景下,如何高效验证汇编程序实时可达性并避免状态爆炸的难题,提出了一种融合惰性抽象(Lazy Abstraction)与插值细化(Refinement by Interpolants)的模型检测方法。通过构建时序控制流自动机(Timed CFA)模型,结合实时计算树逻辑(RTCTL)公式描述实时属性,利用iZ3求解器实现抽象模型的自动优化。实验表明该方法能有效缩减状态空间,显著提升对H8/3687微控制器汇编程序的验证效率,为安全关键系统(如自动驾驶、机器人控制)的可靠性保障提供了创新解决方案。
随着人工智能技术在自动驾驶、智能机器人等嵌入式系统中的深度融合,系统复杂性呈指数级增长。传统基于C语言的模型检测方法难以捕捉硬件相关错误(如中断处理异常、栈溢出等),而汇编级验证虽能解决此痛点,却面临状态空间爆炸的挑战。特别是在需要严格满足实时约束的安全关键场景中,如何平衡验证效率与精度成为学界攻坚的重点。
发表于《IEEE Access》的这项研究开创性地将惰性抽象与插值优化技术引入嵌入式汇编程序的实时验证领域。研究团队通过构建时序控制流自动机(Timed Control Flow Automaton, Timed CFA)对H8/3687微控制器汇编指令进行建模,赋予每个状态节点时间戳属性;采用实时计算树逻辑(Real-Time Computational Tree Logic, RTCTL)描述如“错误状态在k时间内不可达”的时序属性;利用反例引导抽象细化(CounterExample Guided Abstraction Refinement, CEGAR)框架,结合iZ3求解器的插值生成能力,实现抽象模型的动态优化。该方法通过仅对必要路径进行精细化建模,显著降低计算复杂度。
关键技术方法包括:1) 基于Lex/Yacc的汇编指令解析与时序CFA构建;2) 融合时间约束的抽象可达树(Timed ART)生成算法;3) 基于Craig插值的反例路径虚假性判定与谓词优化;4) 采用固定长度位向量(Fixed-Sized Bit-Vectors, FLSBV)理论对微控制器寄存器进行精确建模。
研究采用Kripke结构对系统状态进行数学建模,通过CTL逻辑运算符(如AX、EU等)描述分支时序属性,并扩展RTCTL支持时间上界约束(如EF≤k)。相较于线性时序逻辑(RTLTL),RTCTL在表达能力和计算效率间取得更好平衡。
针对H8/3687架构特点,将寄存器(如ER7栈指针)、地址空间映射为位向量函数,使用SSA(Static Single Assignment)形式对MOV、ADD等指令的副作用进行逻辑编码。通过连接(concat)、提取(extract)等操作精确模拟不同位宽数据的运算行为。
在传统谓词抽象基础上,引入惰性抽象策略:仅当反例路径出现时才局部细化模型,避免全局重构的开销。通过iZ3求解器对反例路径进行可满足性判定,自动生成插值作为新谓词,有效剔除虚假反例。实验显示该方法较非惰性抽象减少约60%状态数。
以绝对值计算程序为例(Listing 7),验证AG≤20?error属性。初始抽象模型生成217个状态时出现虚假反例,经插值优化后仅需132个状态即完成验证,验证时间从229ms降至146ms。在LED控制程序(1700行代码)和定时器中断程序(2822行代码)的对比实验中,该方法均表现出最优的时空效率。
研究结论表明,基于惰性抽象与插值优化的CEGAR框架能够有效解决嵌入式汇编程序实时验证的状态爆炸问题。通过时序建模与动态细化相结合,在保证精度的同时将验证时间控制在毫秒级。该成果为自动驾驶、工业机器人等安全关键系统的形式化验证提供了新范式,未来可扩展至多核架构和混合关键性系统的验证场景。
生物通微信公众号
生物通新浪微博
今日动态 |
人才市场 |
新技术专栏 |
中国科学人 |
云展台 |
BioHot |
云讲堂直播 |
会展中心 |
特价专栏 |
技术快讯 |
免费试用
版权所有 生物通
Copyright© eBiotrade.com, All Rights Reserved
联系信箱:
粤ICP备09063491号