FlexRay时钟同步拜占庭故障容错算法研究

刘让 张凤登

摘 要：为了解决FlexRay分布式实时系统中时钟同步可能出现拜占庭故障，从而导致系统时钟崩溃的问题，提出一种有效的解决算法FlexRayB FT（ FlexRay Byzantine-Fault-Tolerant）。该算法在传统拜占庭容错算法基础上引入消息认证码技术，对报文进行加密处理，相比指数型算法，其性能提高了3个数量级。FlexRayBFT执行分为准备阶段与回复执行阶段，分析不同阶段的消息具体通信过程，同时证明了算法的一致性与正确性。通过使用Truetime工具箱搭建FlexRay线控转向分布式实时系统，对系统使用FlexRayBFT算法前后分别进行仿真实验验证。结果表明，FlexRayBFT算法可以有效克服FlexRay分布式实时系统中时钟同步的拜占庭故障，保障时钟同步的稳定性。

关键词：FlexRay;分布式实时系统;时钟同步;拜占庭故障

DOI： 10. 11907/rjdk.192422

开放科学（资源服务）标识码（OSID）：

中图分类号：TP312

文献标识码：A

文章编号：1672-7800（2020）001-0068-07

0 引言

随着汽车电子控制系统的发展，一种基于FlexRay的分布式实时系统逐渐受到关注。作为新兴的汽车电子分布式系统，其对实时性与可靠性有着严格要求，而拜占庭恶性故障对分布式系统的时钟同步会造成严重威胁，故在系统设计中，容忍时钟同步中的拜占庭恶性故障，从而保证系统实时性与可靠性至关重要。

目前在时钟同步及拜占庭故障方面，国内外已进行了很多研究。针对时钟同步算法，Lamport在文献[1]中系统阐述了时钟同步技术原理、方法及其在分布式系统中的应用，以及逻辑时钟在带时序分布式事件处理中的作用，并在文献[2]、[3]中提出确定性收敛平均时钟同步方法;Yamashita等[4]对高斯分布的时钟同步信息传输延迟进行分析，给出高斯分布下时钟同步精度置信区间表达式以及时钟偏差均值计算方法，但对于具体工程应用中的时钟同步，单纯的软件时钟同步算法实现的同步精度相对较低;Ramanathan等[5-6]提出一种将软硬件结合的同步方式，软件算法借鉴Lamport的收敛平均算法[2-3]，而硬件部分主要实现同步信息的发送与接收，以及记录同步信息的本地时间戳。实验结果表明，采用软硬件结合的同步算法后，可以使系统同步误差精确到几十个微秒级，比纯软件同步算法提高了2个数量级以上。然而，以上研究仅针对时钟同步，无法解决该过程中出现的一系列故障问题，所以可容忍故障的时钟同步方案之后逐渐被提出。其中文献[7]提出共同投币技术，利用该技术构造概率型常数轮的同步拜占庭一致性协议。对于分布式系统中的每一个节点，共同投币技术的使用让其在每一轮运行中得到一个事先无法预测的随机比特值，那些正常节点通过该共同随机比特值达成一致意见。但该方法是一个概率性方法，比较容易受到破坏;文献[8]一[11]提出使用Ouorum和状态机复制技术实现的异步拜占庭故障容忍算法（BFT），该算法在状态机中的执行分为5个阶段，分别为：请求阶段、预备阶段、准备阶段、回复阶段、执行阶段，并结合前摄性恢复技术使拜占庭节点在更新服务状态后可以重用。算法确保了系统在某时间段内可容忍的拜占庭节点数小于系统节点总数的1/3，而在系统整个运行时间内则可以容忍任意数量的拜占庭节点。BFT（ Byzantine Fault Tolerant）算法的良好性能提升了拜占庭容错系统在实际工程领域的可行性，但该算法执行过程相对复杂，且仅可以实现固定组的拜占庭节点一致，一旦节点出现物理故障或受到恶意攻击，性能便会大大降低。因此，本文提出可容忍该故障的FlexRay-BFT算法，使用加密技术对消息进行验证。在对比公钥签名体系与消息认证码后，发现公钥签名体系应用的是指数型算法，会严重影响算法性能，而消息认证码使用对称加密方式，算法性能比前者提高了3个数量级。使用消息认证码技术，当出现时钟同步中的拜占庭故障时.可在整个系统网络中利用该算法找出系统中的故障节点，并将其屏蔽掉，在确保达到时钟同步稳定性的同时，消除拜占庭故障的不良影响，进而从根本上实现容忍时钟同步中的拜占庭故障。

1 FlexRay时钟同步机制

时钟同步的目的在于使物理或逻辑时钟维持在一个全局一致的状态，从而令系统中的信息、事件以及节点中与时间有关的行为有一个全局一致的解释，保证系统中各节点的通信在时间逻辑上是完全正确的。FlexRav协议的静态段采用基于TDMA的工作方式，节点在发送报文前就已知道了报文的确切发送时间，而接收节点也知道报文接收时间。FlexRay协议之所以能够提前得知报文发送与到达时间，并能保证系统的准确性，关键在于整个通信簇有一个共同的时间标准。因此，每个节点都必须保证时间同步，并且每个节点之间的最大偏差必须在限定范围内，这是实现时钟同步的前提，最大偏差也称为精度。

FlexRay协议采用分布式时钟同步机制，在该机制中每个节点通过其它节点发送的同步帧观测它们的时钟计时，从而使各自与节点簇同步。FlexRay节点内的时间表示法是在周期cycle、最大时钟节拍MT（ Macrotick）和最小時钟节拍（ Microtick）基础上建立的。MT在节点簇范围的基础上进行同步。在容忍误差范围内，节点簇中所有同步节点的MT持续时间相同。每个节点MT包含Microtick的数量取决于每个节点的振荡器频率和预计数器，所以虽然各同步节点的MT时间相同，但各自MT包含的Microtick数量可能不同。

FlexRav时钟同步主要包含两个并发进程：时钟同步进程（Clock Synchronization Process，简称CSP）和宏节拍生成进程（Macrotick Generation Process，简称MTC）。CSP主要实现循环开始时的初始化，测量并存储偏差值，同时计算相位修正值和速率修正值;MTG控制循环计数器和宏节拍计数器，并运用相位修正值和速率修正值调整时间。具体时钟同步过程如图1所示。

时钟同步功能的主要作用是使簇中各节点之间的时间偏差保持在精密度范围之内。时间偏差分为两种：相位偏差（ Offset Difference）和速率偏差（Rate Difference）。相位偏差是指两个时钟在某个特定时间的绝对差别;速率偏差是指相位偏差随着时间推移的变化，其反映了相位偏差在特定时间的变化，分别运用相位修正（ Offset Correction）和速率修正（Rate Correction）使不同节点的本地时基保持同步[12-13]。

2 FlexRay时钟同步拜占庭容错算法

2.1 拜占庭时钟故障

在分布式实时系统中，若有3个节点A、B、C，如果A、B是正常节点，而C是“两面性”恶性故障节点，如：C节点告知A节点此刻时间为4：00，却告知B节点此刻是4：05。由于C节点的“叛徒”行为，从而影响了整个系统时钟的准确性。这种恶性的两面性行为称为恶性错误或拜占庭错误[14]，如图2所示。

对于基于FlexRay总线的分布式实时系统，导致拜占庭时钟故障的原因可能是由于系统中元器件出现故障，或节点在信息交换过程中发生故障，从而随机发送各种错误消息，使得其它正常节点收到错误信息后作出错误判断，进而影响整个系统的时钟同步。

2.2 拜占庭故障算法充分条件

对于拜占庭故障可概括为：所有正常节点都可以让其余节点接收到其真实消息，并且最终会一致采取正确措施，即拜占庭故障容错算法是一个关于一致性与正确性的算法问题。该算法针对的是正常节点，因为拜占庭节点可以采取任何无法预估的行动，所要做的就是在有拜占庭节点干扰的情况下，研究出抗干扰算法。

下面以拜占庭将军问题原型为例，为方便描述，给出如下定义：

变量Vi：为i个将军发给其他将军的命令值，并将其自身判断记为Vi。

向量（V1，V2，…，Vn）：表示大多数将军的意见，将军们会通过函数处理该向量后将处理结果作为最终采用的意见。

条件1：所有忠诚的将军们必须拥有相同向量（V1，V2，…，Vn）。

（2）正确性。

条件2：对于忠诚的将军i，其余所有忠诚将军们的Vi必须是将军i发送的值。

将问题简化为司令一副官模型，可得到以下充分条件：

IC1（一致性）：每个忠诚副官必须遵守同一条命令。

IC2（正确性）：对于忠诚的司令，所有忠诚的副官们都必须遵守司令发送的命令。

要简化成司令一副官模型，只需将司令遍历各个将军，便得到一个完整的关于分布式系统中的拜占庭问题，而其采用的算法可以是完全一致的。IC1和IC2构成解决拜占庭问题的充分条件。在接下来的工作中，解决拜占庭问题的算法只要能够满足上述充分条件，则表明该算法是有效、可行的拜占庭故障容错算法[14]。

2.3 FlexRayBFT算法

在对口头协议算法OM（m）、签署协议算法SM（m）、公钥签名体系等算法研究基础上，结合FlexRay总线通信协议，并引入消息验证码对消息进行认证，从而改进算法性能，提升系统的实时性与可靠性，改进算法被称为FlexRay-BFT算法。

通过对消息或与消息有关的信息进行加密或签名变换所进行的认证称为消息认证。消息认证的目的主要为了防止消息在传输或存储时被有意、无意地篡改，其认证主要包括消息内容认证（即消息完整性认证）、消息源和宿认证（身份认证），以及消息序号和操作时间认证等。将密钥与需要验证的信息经函数处理后得到消息认证码，当消息接收者拥有相应密钥时，则可判断出消息内容是否被篡改。消息认证码不同于公钥签名，消息认证码的生成与验证使用同一个密钥，而公钥签名采用私钥签名、公钥加密的方式。公钥签名使用非对称加密方式，且属于指数型算法，会严重影响算法性能，从而使拜占庭算法无法在实际工程领域得到应用。消息认证码使用对称加密方式，算法性能相比前者提升了3个数量级，因此相对而言使用消息认证码的算法更具有可行性。由于消息认证码需要相同密钥，所以消息发送方和接收方需要在通信开始前对密钥达成一致。消息认证过程如图3所示。

在使用消息认证码之前，需要保证所有节点计算能力是有限的，并且不存在两条消息经消息认证码算法运算得到的消息认证码是相同的，即保证消息认证码算法是安全的。在此前提下，发送节点将经消息认证码算法处理得到的消息认证码与消息发送给接收节点，接收节点在接收这些信息后，使用事先已达成一致的密钥和算法得到用于验证的消息认证码，并将其与接收到的认证码进行对比判断。若相同，则表明消息是完整的，即在传输过程中消息没有被改动，且发送节点认证通过，消息内容以及消息源和宿认证通过;若不同，则表明消息是不完整的，即消息在传输过程中被改动，或发送节点被冒充等，接收节点不接收，消息则不会进入下一过程进行处理。

2.4 FlexRayBFT算法分析及过程

FlexRay分布式拜占庭容错系统模型如图4所示。总线传输速率为2.5Mbit/s，报文可在A、B双通道同时传输，单个通信周期总长度为Sms。

2.4.1 FlexRayBFT准备阶段

当节点Ni准备发送消息m Ni时，其会将当前循环的编号k（0≤k≤63）加入该信息前作为编号，然后将m-Ni经消息认证码算法处理得到的消息摘要d与自己的节点标号i（即节点身份ID）加入上述消息m Ni中，形成准备发给其余n-l个节点的消息，称为准备消息Prepare_MshNi。鉴于在FlexRay分布式系统中往往有多个接收节点，故进一步引入消息认证码向量，表示为（k）ij，1 ≤j≤n，且j≠i。準备消息Prepare_MshNi格式如图5所示。

在该阶段，所有节点会获得来自其余节点的准备消息，当某节点收到2f条与m N、k以及i相匹配的准备消息，则该节点获得了一个关于准备消息的消息集，称为准备消息集。准备阶段如图6所示。

该算法由于加入了循环编号k，保证系统不会受到重放攻击，即有其它循环消息或之前执行过的消息冒充当前循环消息发送而扰乱系统。

2.4.2 回复执行阶段

在回复执行阶段，节点会向其余各节点发送回复消息，记为Reply_MsgNi，告知其余节点其已经有了准备消息集。回复消息格式与准备消息格式类似，包括当前循环编号k、消息摘要d、自身节点标号i以及准备消息集。回复消息Reply_MsgNi格式如图7所示。

每个节点都会接收这条消息，直至节点获得一个关于回复消息的消息集，称为回复消息集。回复消息集所具备的条件为：至少应包含2f+1条回复消息（包括节点本身在内），且每条回复消息的循环编号后和d皆需一一对应。当节点拥有回复消息集时，则回复完成，也为算法执行作好了准备。回复阶段如图8所示。

算法执行阶段利用网络空闲时间（NIT），即将对每个节点接收到回复决议证书的处理放于NIT。各节点会利用得到的回复消息集，通过校验之后得到一个消息向量表。假设n节点是拜占庭故障节点，对于节点1，其向量如表1所示。

综上可知，所有正常节点采用的命令都是A，即满足IC1（一致性），并且通过将主节点遍历各个节点，发现与正常主节点保持一致，即满足IC.（正确性）。对于节点为n时（对应主节点为故障节点）都一致采取R（撤退）命令，即满足IC，（一致性）。对应FlexRay分布式系统中的执行措施即为故障节点屏蔽措施，即将节点n屏蔽掉。所谓故障屏蔽技术，即假设该错误节点之后发送的所有消息皆为空，或不接受该错误节点的消息。

对于一个拥有n个节点的FlexRay分布式系统，可通过执行FlexRayBFT算法确保其各节点的时钟同步。假设一个FlexRay分布式系统拥有4个节点NodeA、NodeB、NodeC、NodeD，其中NodeB是拜占庭节点。对于执行时钟同步时，zPrimaryTRP（在时钟同步中表示的是同步帧的实际到达时刻）使用的是上一轮保存的值，此处时钟同步方法类似于相位修正时的时钟同步方法，则节点A观察到的时钟消息向量如表2所示。

其中，DevAf表示節点A与i之间的时间偏差，且Dev Value= zPrimary TRP - zActionPoint，zActionPoint表示时钟同步帧的理想到达时刻。

表2中各数字皆表示时刻，由表2可知节点A的时间偏差序列为：

zlist_A={DevAA，DevAC，DevAD}

（8）

根据FTM算法会得到一个最终的zCorrectValue，即修正值以调整节点A的时钟，确保A的时钟同步。回复执行阶段如图9所示。

整个FlexRayBFT算法执行过程如图10所示。

3 实验验证

基于所搭建的FlexRay线控转向系统模型与Truetime工具箱，将提出的FlexRayBFT算法移人系统中，并对系统进行仿真测试。首先，在不将FlexRayBFT算法加入系统，即不执行FlexRayBFT算法时，运行系统模型。系统受拜占庭节点干扰后，各节点FlexRay总线通信信号及时钟运行情况分别如图11、图12所示。

图11、图12中从下往上依次为传感器的FlexRay总线信号及时钟运行情况、控制器的FlexRav总线信号及时钟运行情况、执行器的FlexRav总线信号及时钟运行情况、拜占庭节点的FlexRay总线信号及时钟运行情况。从图中可以看出，受拜占庭节点影响，各节点通信都是杂乱无章的，无法进行正常的通信及时钟同步。

FlexRay线控转向系统在受拜占庭故障干扰的情况下，控制器、传感器节点及执行器节点输出信号如图13所示。

在将FlexRayBFT算法加入系统，即执行FlexRayBFT算法后，运行系统模型。系统克服拜占庭节点干扰后，各节点的FlexRay总线通信信号及时钟运行情况分别如图14、图15所示。

图14、图15中从下往上依次为传感器的FlexRav总线信号及时钟运行情况、控制器的FlexRay总线信号及时钟运行情况、执行器的FlexRay总线信号及时钟运行情况、拜占庭节点的FlexRay总线信号及时钟运行情况。

从两幅图中可以清楚看出，在执行FlexRayBFT算法后，图14中的拜占庭节点信号消失，成功被算法屏蔽，所以在图15中，也就不存在拜占庭节点时钟。当故障节点被屏蔽后，剩下的正常节点传感器、执行器、控制器各节点则可进行正常的通信及时钟同步。

FlexRay线控转向系统在克服拜占庭故障后，控制器、传感器节点及执行器节点输出信号如图16所示。在克服了故障节点影响后，各信号波形趋于稳定。

从以上执行FlexRayBFT算法的前后仿真图对比可知，通过执行FlexRayBFT算法可以有效克服FlexRav线控转向系统中时钟同步的拜占庭故障。

4 结语

本文针对FlexRav时钟同步中的拜占庭故障，提出一种有效的解决算法FlexRayBFT。基于所搭建的FlexRav线控转向系统模型与Truetime工具箱，将提出的FlexRay-BFT算法移人系统中并对系统进行仿真测试。通过对仿真结果的分析可知，经过FlexRavBFT算法处理后，可以有效克服FlexRay线控转向系统中时钟同步的拜占庭故障，并确保FlexRay分布式系统中各节点的时钟同步以及正常运行。通过该研究，对于拜占庭容错算法以及FlexRav协议的时钟同步过程有了更深入的理解。本文在应用消息认证码方法的基础上，成功实现了对拜占庭故障的容忍，从而提高了系统性能。在今后的研究中，可以尝试继续提高消息认证码的性能，从而对时钟拜占庭故障容错算法性能作进一步优化。

参考文献

[1]LAMPORT L. Time， clock and the ordering of events in a distributed system[J]. Communication of the ACM. 1987（ 21 ） ： 558-565.

[2]LAMPORT L， MELLIAR-SMITH P M. Synchronizing clocks in thepresence of faults[J]. Journal of the ACM. 1985 ， 32 （ I ） ： 52-78.

[3]LAMPORT L. The Byzantine general prohlem [J] . ACM Transactionon Programming Languages and Systems， 1982， 4 （ 3 ） ： 382-401.

[4]YAMASHITA T， ONO S. A statistical time synchronization method forfrequency-synchronized net，vork clocks in distributed systems [ J] . IE -ICE Transactions on information and Systems .2004 （ 7） ： 1878-1886.

[5]RAMANATHAN P， KANDLUR D D， SHIN K C. Hardware-assistedsoftware clock synchronization for homogeneous distributed systems[J]. IEEE Transactions on Computers ， 1990， 39（4） ： 514-524.

[6]SHIN K G， RAMANATHAN P. Transmission delays in hardware clocksynchronization [J] . IEEE Transactions on Computers ， 1988 . 37 （ 1 I ） ：1465-1467.

[7]FELDMAN P. MICALI S. An optimal probabilistic protocol for syn-chronous byzantine Agreement [J].SIAM Journal on Computing，1997，26（4） ： 873-933.

[8]MALKHI D. REITER M. Byzantine quorum system [J]. Journal of Dis-tributed Computing， 1998 ， 11（ 4） ： 203-213.

[9]CASTRO M ， LISKOV B. Proactive recovery in a Byzantine tolerant sys-tem [C]. In Proceedings of the Fourth Symposium on Operating Sys-tems Design and Implementation（ OSDI） . 2000.

[10]CASTRO M . LISKOV B. Practical Byzantine fault tolerance [ C]. InThird Symposium on Operating systems Design and Implementation（ OSDI） . 1999.

[11]CASTRO M. LISKOV B. Practical Byzantine fault tolerance and pro-active recovery [J] . ACM Transactions on Computer Systems ， 2002 ， 20（ 4） ： 398-461.

[12]張凤登.现场总线技术用 [ M].北京 ：科学出版社 ， 2008.

[13] 张凤登.实时传输网络 FlexRay原理与规范 [ M].北京 ：电 子-工业出版社 ， 2017.

[14] 张凤登，分布式实时系统[M].北京：科学出版社，2014.

基金项目：上海市自然科学基金项目（ 15ZR1429300）

作者简介：刘让（1994-），男，上海理工大学光电信息与计算机工程学院硕士研究生，研究方向为汽车电子、现场总线、嵌入式系统;张凤登（1963-），男，博士，上海理工大学光电信息与计算机工程学院教授、博士生导师，研究方向为分布式系统、过程控制、现场总线。