FreeRTOS CBMC 证明套件深度解析xQueueReceive 的内存安全证明、Harness 限界与 CBMC 配置【免费下载链接】FreeRTOSClassic FreeRTOS distribution. Started as Git clone of FreeRTOS SourceForge SVN repo. Submodules the kernel.项目地址: https://gitcode.com/GitHub_Trending/fr/FreeRTOS本篇技术文章基于 FreeRTOS 仓库中FreeRTOS/Test/CBMC自动证明体系下的 QueueReceive 证明文档讲解如何用 C Bounded Model CheckerCBMC对 FreeRTOS 队列接收函数xQueueReceive建立内存安全证明。读完本文你将理解该证明的假设边界哪些并发/临界区函数被抽象、harness 如何通过LOCK_BOUND、QUEUE_RECEIVE_BOUND、MAX_ITEM_SIZE三个宏约束状态空间、Makefile.json中 CBMC 标志与待证对象文件的具体含义以及如何在本机复现运行该证明并解读报告。1. 证明定位一个进行中的 xQueueReceive 内存安全证明QueueReceive证明目录下的 README 用简短的几句话界定了这条证明的性质与边界这些内容必须完整理解证明目标在 harness 所描述的边界bound之内证明xQueueReceive函数的内存安全memory safety抽象策略证明过程中将“任务池task pool”和“并发相关函数concurrency functions”抽象掉即不对多任务并发行为做真实建模而是以非确定性nondeterministic值代替完成度声明文档明确标注该证明是 work-in-progress进行中工作证明的假设条件记录在 harness 文件内外部假设清单证明还假定以下 8 个函数自身是内存安全的、且没有影响本函数内存安全结论的副作用vPortEnterCriticalvPortExitCriticalvPortGenerateSimulatedInterruptvTaskMissedYieldvTaskPlaceOnEventListvTaskSuspendAllxTaskRemoveFromEventListxTaskResumeAll这份人工假设清单在工程上有一个机器可读的对应物同目录的 cbmc-viewer.json 中expected-missing-functions数组列出了 CBMC 在符号化过程中允许缺失实现的全部符号其中完整包含上述 8 个函数并额外覆盖了vPortCloseRunningThread、xPortStartScheduler、xTaskPriorityInherit、xTaskPriorityDisinherit等平台/任务类符号。README 中的自然语言假设与该 JSON 配置相互印证凡是证明中未纳入符号化模型的函数都被视为黑盒其内存安全性由读者或上游其他证明负责。该证明属于更上层的 CBMC Proof Infrastructure 的一部分顶层 README 说明proofs目录下的每个叶子目录都是“FreeRTOS 单个入口点entry point的内存安全证明”且持续集成系统会用这些证明校验每一个 pull request开发者也可以在本机运行。2. 证明目录结构与文件角色FreeRTOS/Test/CBMC/proofs/Queue/QueueReceive/目录内只有四个文件各自承担明确职责文件角色README.md人类可读的证明目标、抽象策略与外部假设说明QueueReceive_harness.c证明入口harness()构造被证函数的前置状态并调用xQueueReceiveMakefile.json证明配置入口函数名、限界宏、CBMC 标志、参与符号化的对象文件、编译宏cbmc-viewer.json报告工具配置证明名称、根目录、允许缺失的函数白名单顶层 CBMC/README.md 还交代了三个配套目录proofs各证明、patches证明前对源码打的补丁用于剥离static、volatile限定符见 patches 目录、include与windows证明使用的头文件。3. Harness 设计状态空间是如何被约束的harness 源文件 是理解这条证明的核心。CBMC 对 C 程序做的是路径探索若输入完全无约束则状态空间爆炸、证明无法收敛harness 的工作就是把xQueueReceive可能遇到的输入约束到一个“足够宽且可证完”的范围内。3.1 三个限界宏LOCK_BOUND / QUEUE_RECEIVE_BOUND / MAX_ITEM_SIZEharness 文件头部定义了三个带默认值的宏每个都配有注释说明其约束对象与性能动机/* prvUnlockQueue is going to decrement this value to 0 in the loop. * We need a bound for the loop. Using 4 has a reasonable performance resulting * in 3 unwinding iterations of the loop. The loop is mostly modifying a * data structure in task.c that is not in the scope of the proof. */ #ifndef LOCK_BOUND #define LOCK_BOUND 4 #endif /* This code checks for time outs. This value is used to bound the time out * wait period. The stub function xTaskCheckForTimeOut used to model * this wait time will be bounded to this define. */ #ifndef QUEUE_RECEIVE_BOUND #define QUEUE_RECEIVE_BOUND 4 #endif /* If the item size is not bounded, the proof does not finish in a reasonable * time due to the involved memcpy commands. */ #ifndef MAX_ITEM_SIZE #define MAX_ITEM_SIZE 20 #endifLOCK_BOUND默认 4prvUnlockQueue内部存在把cTxLock/cRxLock递减到 0 的循环LOCK_BOUND就是该循环的展开上限源码注释指出该循环主要修改的是task.c中不属于本证明范围的数据结构因此只需有限展开。QUEUE_RECEIVE_BOUND默认 4约束超时等待循环。xQueueReceive在等不到数据时会循环调用xTaskCheckForTimeOut检查超时该函数的 stub 以这个宏为上限建模等待次数。MAX_ITEM_SIZE默认 20约束队列元素大小。注释直白地说明若不约束元素大小xQueueReceive成功路径上的memcpy会使证明无法在合理时间内结束。需要注意的是harness 中的默认值会被Makefile.json覆盖配置文件中显式写入了LOCK_BOUND: 2和QUEUE_RECEIVE_BOUND: 3见 Makefile.json#L31-L32即实际生效的限界比 harness 默认值更小以换取更快的证明时间——这正是该目录将这两个宏同时放入DEF列表QUEUE_RECEIVE_BOUND{QUEUE_RECEIVE_BOUND}、LOCK_BOUND{LOCK_BOUND}的原因。3.2 harness() 主流程前置状态构造harness 主体QueueReceive_harness.c#L65-L93按以下顺序构造被测函数的前置状态void harness() { vInitTaskCheckForTimeOut( 0, QUEUE_RECEIVE_BOUND - 1 ); xQueue xUnconstrainedQueueBoundedItemSize( MAX_ITEM_SIZE ); TickType_t xTicksToWait; if( xState taskSCHEDULER_SUSPENDED ) { xTicksToWait 0; } if( xQueue ) { xQueue-cTxLock LOCK_BOUND - 1; xQueue-cRxLock LOCK_BOUND - 1; void * pvBuffer pvPortMalloc( xQueue-uxItemSize ); if( !pvBuffer ) { xQueue-uxItemSize 0; } xQueueReceive( xQueue, pvBuffer, xTicksToWait ); } }逐步拆解初始化超时计数器vInitTaskCheckForTimeOut( 0, QUEUE_RECEIVE_BOUND - 1 )将 stub 内部的迭代计数器归零、上限设为QUEUE_RECEIVE_BOUND - 1见第 5.1 节使等待循环最多展开有限次。构造“近乎无约束”的队列xUnconstrainedQueueBoundedItemSize( MAX_ITEM_SIZE )返回一个除元素大小被上限约束外字段大多为非确定性的队列句柄见第 5.2 节覆盖了队列的各种合法内部状态而非手工构造某一特例。调度器状态分支xState是描述调度器状态的非确定变量当调度器处于挂起taskSCHEDULER_SUSPENDED状态时xTicksToWait被强制为 0。从源码结构看未挂起分支下xTicksToWait保持未初始化即非确定性取值等价于对“任意等待时长”的超时路径都进行验证——两种调度器状态都被证明所覆盖。锁计数器初始化为限界值减一cTxLock/cRxLock被设为LOCK_BOUND - 1与 3.1 节中prvUnlockQueue循环的展开上限严格配套保证解锁循环不会超过已展开的迭代数。接收缓冲区模拟分配失败pvPortMalloc( xQueue-uxItemSize )的结果可能被建模为NULL此时把uxItemSize置 0使函数进入“零长度数据”的处理路径从而对缓冲区为空/为 0 的边界也进行内存安全验证。调用被证函数最终以任意合法前置状态调用xQueueReceive( xQueue, pvBuffer, xTicksToWait )CBMC 检查其所有执行路径上的读写是否越界、是否解引用非法指针。3.3 本地 stubvTaskInternalSetTimeOutStateharness 还内联定义了一个 stubQueueReceive_harness.c#L58-L63void vTaskInternalSetTimeOutState( TimeOut_t * const pxTimeOut ) { __CPROVER_assert( __CPROVER_w_ok( ( pxTimeOut-xOverflowCount ), sizeof( BaseType_t ) ), pxTimeOut should be a valid pointer and xOverflowCount writable ); __CPROVER_assert( __CPROVER_w_ok( ( pxTimeOut-xTimeOnEntering ), sizeof( TickType_t ) ), pxTimeOut should be a valid pointer and xTimeOnEntering writable ); xQueue-uxMessagesWaiting nondet_BaseType_t(); }它对真实实现做了两点抽象一是把“设置超时状态”的副作用替换为对全局队列uxMessagesWaiting赋非确定值建模“等待期间其他任务可能改动队列中消息数”这一并发效果二是用两个__CPROVER_w_ok断言保留了原始调用点对pxTimeOut指针的内存安全义务——即被调用方指针必须有效且两个成员必须可写避免抽象掉真实函数后丢失该检查。文件头注释也说明了“pxTimeOut 的初始化与本 harness 无关”。4. Makefile.json证明义务、CBMC 标志与待证对象Makefile.json 是准备脚本生成 Makefile 的配置源其关键字段与证明语义一一对应{ ENTRY: QueueReceive, LOCK_BOUND: 2, QUEUE_RECEIVE_BOUND: 3, CBMCFLAGS: [ --unwind 1, --signed-overflow-check, --unsigned-overflow-check, --unwindset xQueueReceive.0:{QUEUE_RECEIVE_BOUND},prvUnlockQueue.0:{LOCK_BOUND},prvUnlockQueue.1:{LOCK_BOUND}, --nondet-static ], OBJS: [ $(ENTRY)_harness.goto, $(FREERTOS)/Source/queue.goto, $(FREERTOS)/Source/list.goto, $(FREERTOS)/Test/CBMC/proofs/CBMCStubLibrary/tasksStubs.goto ], DEF: [ configUSE_TRACE_FACILITY0, configGENERATE_RUN_TIME_STATS0, INCLUDE_xTaskGetSchedulerState1, QUEUE_RECEIVE_BOUND{QUEUE_RECEIVE_BOUND}, LOCK_BOUND{LOCK_BOUND} ], GENERATE_HEADER: [ queue_datastructure.h ] }ENTRYQueueReceive既是配置键也是 harness 文件名前缀$(ENTRY)_harness.goto即 harness 符号化后的 goto 字节码与harness()入口对应。CBMCFLAGS逐项含义--unwind 1默认循环只展开 1 次作为兜底限界防止未显式指名的循环失控--signed-overflow-check/--unsigned-overflow-check把有/无符号整型溢出也作为检查项内存安全之外额外覆盖整数安全--unwindset xQueueReceive.0:{QUEUE_RECEIVE_BOUND},prvUnlockQueue.0:{LOCK_BOUND},prvUnlockQueue.1:{LOCK_BOUND}对三个已知循环显式给出展开次数——xQueueReceive内的第 0 个循环展开QUEUE_RECEIVE_BOUND3次对应超时等待循环prvUnlockQueue内两个循环各展开LOCK_BOUND2次对应发送/接收锁计数递减循环。这与 3.1 节中“harness 默认值、Makefile 实际值”的配套关系完全吻合--nondet-static将静态存储变量初始化为非确定值避免证明仅覆盖“全零初值”这一特例。OBJS参与符号化的编译单元。被证代码是$(FREERTOS)/Source/queue.goto来自内核queue.c内核位于 git submoduleFreeRTOS/Source与$(FREERTOS)/Source/list.gotolist.c队列底层链表结构再加上tasksStubs.goto任务函数桩。也就是说这条证明的“被测代码”恰是队列模块与其依赖的链表模块其余 FreeRTOS 代码全部不进入证明。DEF关闭追踪设施与运行时统计减少无关代码分支并强制包含xTaskGetSchedulerStateharness 依赖xState判断调度器状态。GENERATE_HEADER: queue_datastructure.hCBMC 工作流会生成该类型头文件把Queue_t等结构体成员暴露给 harness 以便直接赋值如uxMessagesWaiting、cTxLock——这正是 harness 能写入私有结构体字段的原因。5. 支撑组件Stub 库与队列构造助手5.1 任务桩tasksStubs.c 中的超时建模OBJS中链接的 tasksStubs.c 提供被抽象的并发函数实现xTaskGetSchedulerState()直接返回全局非确定变量xState使 harness 的xState taskSCHEDULER_SUSPENDED分支成为真正的双分支证明vInitTaskCheckForTimeOut( maxCounter, maxCounter_limit )允许 harness 在运行时设定等待循环上限harness 中传入0, QUEUE_RECEIVE_BOUND - 1xTaskCheckForTimeOut()用一个静态计数器建模“等待若干次后超时”每次调用自增计数器达到上限返回pdTRUE已超时否则返回非确定性布尔值本次是否超时。源码注释说明这是为了让依赖它的循环拥有确定的迭代上界且该上界“应该由 Makefile.json 按 harness 的性能需求覆盖”——本证明中正是以QUEUE_RECEIVE_BOUND完成的。5.2 队列构造助手xUnconstrainedQueueBoundedItemSizeharness 使用的队列构造器定义在 include/queue_init.h#L96-L124。其注释直言目的“构造一个几乎无约束的队列但把最大元素大小设上界这是 CBMC 当前性能所必需的”。其实现要点用__CPROVER_assume约束uxQueueLength 0、uxItemSize uxItemSizeBound本证明即MAX_ITEM_SIZE额外假设总存储空间小于CBMC_OBJECT_MAX_SIZE由CBMC_OBJECT_BITS默认 7 位推导并保证uxItemSize * uxQueueLength不越界——注释指出xQueueGenericCreate本身不检查乘法溢出故由 harness 侧补上该假设调用真实实现xQueueGenericCreate创建队列后把cTxLock、cRxLock、uxMessagesWaiting等字段覆写为非确定值并假设锁计数不为 127避免与锁计数饱和哨兵值混淆、uxMessagesWaiting uxLength源码注释称这是代码库中以断言检查的不变量若不从初始即成立证明无法成功。同一头文件中还有一个与队列集queue sets相关的prvCopyDataToQueuestub当configUSE_QUEUE_SETS 1时用断言替代真实的内存拷贝注释说明“prvCopyDataToQueue与prvNotifyQueueSetContainer联用会导致问题空间爆炸因此用该 stub 并为prvCopyDataToQueue单开一条独立证明”——这也解释了为什么 proofs/Queue 下存在prvCopyDataToQueue、prvNotifyQueueSetContainer等独立证明目录体现的是按函数切分、逐条收敛的证明工程策略。5.3 报告白名单cbmc-viewer.jsoncbmc-viewer.json 声明proof-name为QueueReceive、proof-root为Test/CBMC/proofs其expected-missing-functions是报告工具的“已知缺失函数”白名单证明运行后报告中只出现白名单之外的缺失函数才视为异常。它实际上是 README 中 8 项外部假设的超集另含pxPortInitialiseStack、pvTaskIncrementMutexHeldCount等平台相关符号保证 CI 判定时不会因为“预期的黑盒”而误报失败。6. 本机复现准备、运行与结果判读运行方式继承自顶层 CBMC/README.md要点如下适用前提Linux 或 macOSWindows 需经 WSL仅支持基于 Python 的构建流程环境Python 版本 ≥ 3.7、系统make64 位机器需安装 32 位 gcc 库如sudo apt-get install gcc-multilib。安装 CBMC 工具链cbmc、goto-ccWindows 下为goto-cl、goto-instrument均能在命令行执行安装cbmc-viewer用于生成 HTML/JSON 报告。初始化子模块在内核所在的 git submodule 就绪的前提下于仓库根目录执行git submodule update --init --recursive --checkoutOBJS引用的$(FREERTOS)/Source/queue.c、list.c即来自内核 submodule。生成 Makefile进入proofs目录执行python3 prepare.py需要跨平台生成如在 Windows 上生成 Linux Makefile时给准备脚本传--system linux/--system windows。准备阶段会为每个叶子证明目录生成 Makefile并对源码施加 patches 目录 中的补丁剥离static、volatile限定符使prvUnlockQueue等 static 函数可被--unwindset按名点名。运行本证明进入FreeRTOS/Test/CBMC/proofs/Queue/QueueReceive/执行make。顶层 README 提示“证明可能需要较长时间”。判读结果make生成 HTML 与 JSON 报告目录结构参照顶层 README 以 TaskCreate 为例的说明证明目录/html/html/index.html为 HTML 报告入口证明目录/html/json为 JSON 报告。用浏览器打开 HTML 报告Errors小节显示None即为通过。7. 结论与边界声明回到 README 的原始表述可以准确概括这条证明的语义边界它证明的是内存安全读写不越界、无非法指针解引用不是功能正确性也不断言并发场景下的行为等价证明在harness 限界内成立等待循环展开 3 次、解锁循环展开 2 次Makefile 实际值、元素大小不超过 20 字节、超时检查由有界计数器 stub 建模任务池与并发机制被抽象README 列出的 8 个函数以及 cbmc-viewer.json 白名单中的其余符号均按“内存安全且无相关副作用”的假设处理文档自述为 work-in-progress上述限界值与假设集合可能随证明工程演进而调整——阅读源码时以 QueueReceive_harness.c 与 Makefile.json 的当前内容为准。对内核开发者而言这套证明的工程价值在于xQueueReceive每次改动后CI 会自动重跑本证明用上述限界与假设集合对其做回归式内存安全校验对阅读者而言harness Makefile.json stub 三件套完整展示了“如何用 CBMC 对带循环、带并发抽象的嵌入式 C 函数做可判定的形式验证”这一可复制的方法论。【免费下载链接】FreeRTOSClassic FreeRTOS distribution. Started as Git clone of FreeRTOS SourceForge SVN repo. Submodules the kernel.项目地址: https://gitcode.com/GitHub_Trending/fr/FreeRTOS创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考