芯片(integrated circuits,ICs)如今已经应用在人类生活的方方面面。随着万物互联时代的到来,芯片的应用规模将达到新的高度。芯片的安全与我们每个人以及整个国家的安全息息相关。一旦芯片的存在漏洞,攻击者可以利用芯片漏洞窃取个人的隐私信息、关键信息,威胁个人经济财产以及人身安全。利用芯片漏洞,他国攻击者甚至可以轻易对国家关键武器、军事设施、财务系统以及科研仪器等安全敏感系统实施攻击,严重威胁国家安全。因此确保芯片安全是当下最重要的议题之一。在大数据时代下,数据分析技术飞速发展,同时数据分析在金融、电子商务、物流配送、广告点击等众多领域取得了显著的成功。数据分析技术是对混杂且低价值密度的海量数据分析的技术,能发掘数据中潜在的有价值信息。利用数据分析,黑客可以改良攻击方式、节约时间成本、挖掘芯片潜在的信息,进而极大提升自身攻击能力。强大的数据分析技术会对芯片安全造成了巨大的威胁。这使得以往的安全性设计以及防御手段在新型的基于数据分析的攻击下变得不再可靠。有限状态机(finite state machine,FSM)在芯片中常常作为控制模块出现。在集成电路的整个设计流程中,FSM属于上层设计。一直以来,人们认为从底层的门级网表逆向提取FSM设计是不可能的,因此FSM始终被认为是芯片中的安全结构。由此,基于FSM实现的硬件安全设计不断被提出。如在FSM中嵌入水印信息实现对芯片知识产权的保护,基于扩展原FSM设计以实现硬件计量技术,抵御芯片制造商的过量生产行为。然而,大数据与数据挖掘技术以及芯片内的数据泄露为从芯片底层信息逆向分析FSM信息提供了可能。一旦FSM结构被破解,那么所有基于FSM的安全设计都不再安全。因此证明基于大数据破解芯片FSM设计的可行性并提出相应的安全芯片设计策略刻不容缓。基于此,本文提出基于大数据分析的有限状态机结构反演技术研究。数据分析的前提是数据获取,本文首先提出了基于全扫描链的数据获取方案。随着数字集成电路的发展,电路对可测试性要求越来越高,扫描链作为最好的可测试性结构之一广泛应用于数字集成电路之中。但扫描链在提升电路的可测试性的同时,也成为了电路信息泄露的旁路。全扫描连将电路中的所有寄存器串联起来,通过测试控制(TC)信号可以控制全扫描链的工作模式。在测试模式下,通过芯片扫描输入(SI)、扫描输出(SO)引脚,使用者可以输入状态向量以及获取芯片响应。基于此,本文提出利用TC信号不断切换芯片的工作模式来获取电路连续工作状态的方法。假设全扫描连长为n,首先将扫描输出引脚SO接至扫描输入引脚SI,扫描链形成循环移位寄存器,循环周期为n。在t(n+1)时刻全扫描链状态序列为st。控制TC信号让电路工作在正常工作状态下1个时钟,电路状态更新,全扫描链状态更新为st+1。再控制TC信号让电路工作在测试状态下n个时钟,则通过SO引脚可以获得当前全扫描链状态st+1。因为周期为n,则经过n个时钟,扫描链状态恢复为st+1。重复上述步骤即可获得电路的连续工作状态,进而将这些连续工作状态作为分析用的数据。FSM由状态寄存器和状态跳转图(state transition graph,STG)组成,因此对FSM结构反演技术也可以分为两步:确定FSM寄存器和STG提取。其中FSM状态寄存器确认的难点在于从其它寄存器中区分出FSM寄存器,因此本文提出利用FSM属性构建寄存器特征的方式区分FSM寄存器。考虑到在电路中常常作为控制模块出现,因此FSM的状态将会影响整个电路的工作模式,而电路的其它结构则不会。从寄存器的角度看,扫描链中大部分寄存器的状态受到FSM寄存器的状态的控制。基于此,本文定义了寄存器的影响力特征(Impact)用于描述寄存器对电路状态的影响成度。显然FSM寄存器相比于大多数普通寄存器有更大的Impact。考虑到从攻击者角度来看,已知的只有从全扫链获取的状态跳转数据。本文提出了基于决策树的Impact分析方案。该方案利用决策树算法以及收集的寄存器状态跳转数据对每一个寄存器的状态跳转作回归分析,逼近真实的寄存器状态跳转的依赖关系,进而得到N×N大小的寄存器状态跳转依赖关系表。各个寄存器的近似Impact可以通过依赖关系表计算得到。为了逼近真实的寄存器Impact以及使FSM寄存器与普通寄存器区分度最大,决策树采用限制决策树深度、叶节点数等预剪枝策略以及leaf-wise策略避免过拟合。基于寄存器的Impact属性,本文提出了一个粗略的FSM寄存器确认算法,将Impact最大的Q个寄存器确认为FSM寄存器。显然Q越大,确认的FSM集合越可能包含所有FSM寄存器。考虑到FSM是上层设计,FSM状态及状态跳转具有语义级信息。因此FSM状态跳转序列(state transition sequence,STS)具有规律性。从寄存器角度看,FSM寄存器之间的STS具有强相关性。为了定量分析STS的相关性,本文引入了划分的概念,研究某特定划分d下的STS相关性。在d下,STS会被分成许多子序列,其中不重复的子序列集合被称之为该寄存器器在d下的模式集。因此STS之间相关性转化为模式集相关性,显然两寄存器对应模式分布接近,二者相关性越强。基于此,本文定义了寄存器相关度(register Relevancy)特征定量地描述寄存器在STS上的相关性。本文同时证明了register Relevancy在一个合适划分下能有效地体现FSM寄存器之间的相关性。考虑到两个强相关的STS必定对其它STS有接近的相关性,一个寄存器对其它所有寄存器的Relevancy构成的寄存器相关度向量(Relev)可以用来表征该寄存器的STS特性。若两寄存器强相关,二者Relev在欧式距离上必然接近。基于此本文提出使用k-means算法(KMA)对Relev进行聚类进而将寄存器划分至不同集合。因为KMA算法对由高维度引入的噪声敏感,本文提出了采用Impact及主成分分析(principle component analysis,PCA)降维策略的Relev提取方案。在该方案中,本文首先提出了一个贪心划分生成算法用于生成合适的划分d和一个基于二叉树的在特定划分下高效Relevancy计算算法。利用上述算法以及降维策略从收集的STSs中提取出Relev。对获取的Relev应用KMA算法即可获得寄存器集精准的划分,各个寄存器集都是候补的FSM寄存器集合。本文同时考虑了特殊情况下的FSM寄存器确认。当FSM采用独热码(one-hot)编码时,一个寄存器集合若想成为FSM寄存器寄存器集合,其必要条件为该寄存器集合中所有寄存器的STSs在任意时刻有且只有一个状态为1。本文将该必要条件拆分为二个独立条件,其中第一个条件为任意两寄存器STSs不能同时为1,第二个条件为集合STSs状态为1的次数和为序列长。利用上述两个条件,本文提出了高效的one-hot编码下FSM寄存器的确认算法。该算法首先判断任意两寄存器是否满足条件一并构建无向图,满足条件一则两寄存器在无向图中相邻。然后算法利用深度优先算法分别从无向图中每一个顶点出发,判断搜索的寄存器集合是否满足条件二。不同于之前的两个FSM确认算法,该算法能够保证得到FSM寄存器的准确解。在确定FSM集合后,本文提出了STG提取算法。考虑到STG由状态跳转与状态跳转条件两部分组成,STG提取算法分为状态跳转提取与状态跳转条件逼近。在状态提取时,本文提出对寄存器集合STS进行遍历,直接提取所有出现过的状态跳转。提取完状态跳转后,对于每一个寄存器集合状态,其状态跳转条件逼近问题可以转化为一个回归问题。因此本文提出利用决策树算法针对每一个寄存器集合状态分别逼近其状态条件。本文采用Open Core上基于FSM的复杂设计作为实验对象,并提出了正确检测率(correct detection rate,CDR),命中率(hit rate,HR)两个指标衡量方案效果。对于基于Relevancy的FSM寄存器确认算法中,FSM寄存器可能被分入不同的集合,我们以带有FSM寄存器数最多的集合来评价算法。在理想情况下,CDR与HR同时趋于100%。对于实际情况我们偏向于在优先保证高的CDR。实验结果显示,基于Impact的FSM粗略确认算法在选择合适划分阈值时能够在保证CDR为100%的同时保证一定的HR。基于Relevancy寄存器确认算法则可以避免人工选择划分阈值,同时在保证CDR为100%的同时有更高的HR。对于一个待定的集合,STG提取算法可以提取出绝大多数的实际状态跳转。