1. 从一个逆向难题说起为什么要从硬件动态分析里“抠”出状态机做硬件安全或者固件逆向的朋友大概率都遇到过这样一种情况手里拿到一个黑盒芯片或者一段加密IP核的网表没有源码、没有文档甚至连寄存器手册都残缺不全。你给它喂激励它给你吐响应中间的逻辑像一团黑雾。这时候如果能把这团黑雾还原成一张清晰的状态转移图也就是有限状态机FSM那后续的分析、漏洞挖掘、甚至功能复现都会变得有章可循。这个项目标题里的“TIFS 21”指向的是一篇发表在信息安全领域顶级期刊上的研究工作核心思路就是不依赖任何内部信号的名字和语义仅通过观察硬件在动态运行时的输入输出行为逆向重建出它的有限状态机模型。听起来有点像给一个陌生人做性格侧写——你不认识他但通过不断给他不同的刺激观察他的反应慢慢就能画出他在什么情况下会进入什么情绪状态。这件事的价值在于现实中的硬件逆向往往卡在“语义鸿沟”上。你从网表里能看到成千上万个门电路但你看不到“这个信号代表空闲状态”或者“那个信号代表认证失败”。传统的逆向方法要么依赖人工读网表效率极低要么依赖形式化验证状态空间爆炸而动态分析逆向FSM走的是一条“行为主义”的路子不管内部多复杂我只关心外部可观测的输入输出序列从中推断出最小可解释的状态机。适合读这篇内容的人包括做硬件安全评估的工程师、搞固件逆向的研究生、对协议状态机推断感兴趣的开发者以及任何需要从黑盒系统中提取行为模型的技术人员。哪怕你之前没接触过FSM推断只要理解“状态”和“转移”这两个概念后面的内容都能跟得上。2. 核心思路拆解动态分析逆向FSM到底在做什么2.1 把硬件当成一个带记忆的黑盒先建立一个最朴素的认知模型。一个有限状态机由三样东西定义状态集合、输入字母表、转移函数。硬件在运行时当前状态决定了它对当前输入的响应同时可能跳转到下一个状态。问题在于状态是内部的你直接看不到。动态分析的做法是把硬件看成一个带记忆的黑盒。你施加一个输入序列它产生一个输出序列。如果硬件没有记忆那么相同的输入永远产生相同的输出但如果有记忆那么相同的输入在不同历史背景下可能产生不同的输出。正是这种“历史依赖性”暴露了状态的存在。举个生活化的例子。你按一个老式收音机的按钮如果当前是FM模式按“”会调到下一个FM电台如果当前是AM模式按“”会调到下一个AM电台。同样的输入“”输出行为不同说明收音机内部至少有FM和AM两个状态。动态分析逆向FSM要做的就是通过系统地尝试各种输入序列找出所有能区分开的状态以及状态之间的转移条件。2.2 为什么选择动态分析而不是静态分析静态分析硬件网表当然也能提取FSM但有几个硬伤。第一网表经过综合优化后状态编码可能被重新映射原始的状态含义完全丢失。第二加密IP核或者混淆过的设计里状态寄存器可能被拆分成多个信号甚至插入虚假状态。第三静态分析面对大规模设计时状态空间爆炸问题非常严重。动态分析的优势在于只关注可观测行为。你不需要理解内部每一个门电路的作用只需要设计一套高效的激励序列让硬件把它的状态“表演”出来。这就像测试一个API你不需要读它的源码只需要发请求看响应就能推断出它有哪些资源状态。当然动态分析也有代价。它要求你能控制输入并观察输出对于已经封装好的芯片可能需要借助调试接口或者侧信道。另外动态分析只能覆盖实际执行到的状态如果某些状态需要极长的序列才能到达可能会被遗漏。所以实际工作中动态分析和静态分析往往是互补的。2.3 状态推断的核心区分序列与等价类整个逆向过程的核心操作是状态区分。两个状态如果对所有可能的输入序列都产生相同的输出序列那它们就是等价的在最小化FSM里可以合并。反之如果存在某个输入序列能让两个状态产生不同输出这个序列就叫区分序列。动态分析逆向FSM的典型流程是先假设一个初始状态然后不断施加输入观察输出根据输出是否与已有状态的行为一致来决定是创建新状态还是复用已有状态。这个过程类似于构建一棵前缀树树的每个节点代表一个输入序列叶子节点的输出模式决定了它属于哪个状态等价类。这里有个关键难点状态数量未知。你不知道目标FSM到底有多少个状态所以需要一个停止准则。常见做法是设定一个最大状态数上限或者当新发现的区分序列不再增加状态数时停止。更严谨的方法是用L*算法或者观察表来系统化地推断最小DFA但这些算法原本是为软件协议设计的搬到硬件上需要处理时序和信号采样的问题。3. 实操要点从激励设计到状态图生成3.1 激励序列的设计原则激励序列的设计直接决定了逆向的效率和覆盖率。最笨的办法是穷举所有输入组合但输入字母表稍微大一点就会爆炸。实际工作中我会遵循几个原则。第一优先使用短序列。短序列能快速区分出浅层状态而且执行速度快。比如先尝试长度为1的输入再尝试长度为2的逐步增加。第二利用已知的协议知识。如果目标硬件实现的是某种标准协议比如SPI、I2C或者自定义的认证流程那么输入字母表通常可以缩减到几个关键命令。第三引入随机化。在系统化探索之后用随机序列做补充有时候能意外触发一些隐藏状态。注意激励序列的长度不是越长越好。过长的序列会增加状态推断的复杂度而且硬件可能有时序约束太长的连续操作可能触发超时复位反而干扰状态观察。3.2 输出观察与状态编码输出观察的粒度很关键。如果硬件输出是并行的多位信号你需要决定是观察完整输出向量还是只观察某些关键位。观察太粗可能区分不开状态观察太细可能把同一状态的不同输出误判为不同状态。我的经验是先观察完整输出向量然后在状态推断过程中逐步合并等价输出。具体来说如果两个状态在所有已尝试的输入下产生的输出向量完全相同就暂时认为它们等价。随着更多输入序列的加入如果发现某个序列让它们产生不同输出再拆分。状态编码方面动态分析不需要知道状态的二进制编码只需要给每个等价类分配一个抽象标识符。最终生成的FSM是一个抽象状态机状态名可以是S0、S1、S2这样的编号转移边标注输入和输出。3.3 状态合并与最小化状态合并是逆向FSM中最容易出错的地方。两个状态在当前观察下等价不代表它们真的等价。可能只是你还没找到那个能区分它们的序列。所以状态合并必须谨慎通常采用增量式合并先假设所有观察到的行为模式都是独立状态然后尝试用更长的序列去区分它们能区分的保持独立不能区分的才合并。这里可以借助观察表的方法。观察表的上半部分是已施加的输入序列下半部分是已发现的区分序列。每次发现新的区分序列就把它加入下半部分然后重新检查所有状态对是否仍然等价。这个过程会一直持续到观察表稳定为止。实操心得在硬件上做状态合并时一定要考虑复位行为。很多硬件在上电或复位后会进入一个确定的初始状态这个状态可以作为锚点帮助校准其他状态的相对关系。如果忽略复位可能会把初始状态和某个普通状态混淆。4. 完整实操流程从零搭建一个FSM逆向环境4.1 环境准备与工具选型要复现这套方法你需要一个能控制输入、观察输出、并且能自动化执行序列的平台。对于FPGA原型可以用Python脚本通过JTAG或者UART接口发送激励并采集响应。对于仿真环境可以用Verilog/VHDL的testbench配合PLI接口或者用cocotb这样的Python验证框架。工具选型上我推荐几个方向。激励生成可以用Python的itertools和random模块自己写也可以用专门的序列生成库。状态推断可以自己实现观察表算法也可以参考开源的DFA学习库比如LearnLib的思路但需要适配硬件时序。可视化用Graphviz把生成的FSM画成状态转移图直观检查。注意如果目标硬件有严格的时序要求比如输入信号必须在时钟上升沿稳定那么激励生成脚本必须包含时序控制逻辑。我通常会在Python脚本里用时间戳或者硬件触发信号来同步。4.2 自动化激励与响应采集自动化流程的核心是一个循环生成输入序列 - 施加到硬件 - 采集输出序列 - 更新状态模型 - 判断是否需要继续探索。这个循环可以用状态机自己来驱动听起来有点递归但逻辑是清晰的。具体实现时我会把输入字母表定义成一个列表比如[cmd_a, cmd_b, cmd_c, reset]。然后从长度为1的序列开始穷举所有组合。对于每个序列先复位硬件然后依次施加输入记录每个输入后的输出。如果发现某个序列的输出模式与已有状态都不匹配就创建一个新状态。采集响应时要注意采样时机。硬件输出可能在输入后几个时钟周期才有效所以需要等待稳定后再采样。我通常会在输入后插入固定的等待周期或者用握手信号来判断输出有效。4.3 状态模型构建与验证状态模型构建完成后必须做验证。验证的方法是用模型预测一个未见过的输入序列的输出然后实际施加到硬件上比较预测和实际是否一致。如果一致说明模型在当前覆盖范围内是可靠的如果不一致说明还有未发现的状态或转移需要继续探索。这个验证过程可以自动化而且应该反复进行。我一般会预留20%的随机序列作为验证集不参与模型构建专门用来测试模型的泛化能力。如果验证通过率低于某个阈值比如95%就说明模型还不够完整。4.4 从抽象FSM到语义标注生成的抽象FSM只是一堆编号状态和转移边要让它真正有用还需要语义标注。比如通过观察哪些输入会导致状态跳转可以推测出“这个转移代表认证成功”或者“那个状态是错误锁定状态”。语义标注需要结合领域知识但抽象FSM已经大大缩小了需要人工分析的范围。实操心得语义标注时可以故意施加一些边界输入比如超长数据、非法命令、时序违规观察FSM是否进入特殊状态。这些特殊状态往往是安全分析的重点。5. 常见问题与排查技巧实录5.1 状态爆炸怎么办状态爆炸是动态逆向FSM最常见的坑。表现是随着输入序列变长发现的新状态数量急剧增加模型越来越大但很多状态看起来行为相似。这时候首先要检查输出观察粒度是不是太细了把噪声当成了状态差异。其次要检查复位是否彻底如果复位不干净残留状态会导致虚假的新状态。如果确认不是观察问题那可能是目标FSM确实状态很多。这时候可以采用分而治之的策略先固定一部分输入不变只探索另一部分输入对应的子状态机最后再合并。或者用等价类抽象把行为相似的状态先合并再逐步细化。5.2 时序违例导致误判硬件对时序很敏感。如果激励施加太快硬件可能还没处理完上一个输入你就施加了下一个导致输出混乱。排查方法是在关键输入后增加等待周期或者用示波器/逻辑分析仪观察实际时序。我遇到过因为时钟域交叉导致输出延迟不确定的情况最后是通过在输出端加同步器解决的。5.3 复位状态不确定有些硬件没有明确的复位信号或者复位后状态依赖于上电顺序。这种情况下动态逆向会非常困难因为每次实验的起点可能不同。解决办法是找一个可重复的锚点序列比如连续施加某个特定输入直到输出稳定把这个稳定点作为事实上的初始状态。5.4 常见问题速查表问题现象可能原因排查方法解决思路状态数量异常多输出噪声或复位不彻底检查输出采样时机和复位序列增加滤波强化复位相同序列输出不一致时序违例或状态残留用逻辑分析仪抓时序增加等待周期重新复位模型预测准确率低状态覆盖不足增加随机验证序列扩展激励字母表或序列长度无法区分两个状态区分序列不够长尝试更长的输入序列用观察表系统化搜索硬件无响应激励电平或协议不匹配检查电气特性和协议格式调整电平标准或命令格式6. 影响范围与延展思考这套动态分析逆向FSM的方法影响范围远不止硬件安全。在协议逆向中它可以用来推断未知协议的会话状态机在嵌入式系统测试中它可以自动生成覆盖所有状态的测试用例在硬件木马检测中异常的状态转移可能是木马触发的线索。从更宏观的视角看动态行为建模是理解复杂系统的通用手段。无论是软件、硬件还是生物系统只要你能控制输入并观察输出就能用类似的方法提取行为模型。区别只在于状态的定义、观察的粒度和探索的效率。我个人在实际操作中的体会是不要追求一步到位生成完美的FSM。先快速生成一个粗糙的、可能包含冗余状态的模型然后用它来指导更有针对性的实验逐步精化。这个过程比一开始就试图设计最优激励序列要务实得多。另外自动化脚本一定要写好日志记录每个输入序列和对应的输出因为后期排查问题时原始数据比模型本身更有价值。最后分享一个小技巧如果目标硬件支持边界扫描或者内建自测试可以尝试利用这些机制来辅助状态观察。有时候一个原本不可观测的内部状态会通过测试引脚暴露出来这能大幅降低逆向难度。