丰田

【第一部分】背景简介 前几年闹得沸沸扬扬的丰田刹不住事件最近又有新进展。十月底俄克拉荷马的一次庭审，2007年一辆2005年凯美瑞暴冲（Unintended Acceleration，UA）致一死一伤事件中丰田被判有责。引起广泛关注的是庭审中主要证人Michael Barr的证词让陪审团同意丰田的动力系统软件存在巨大漏洞可能导致此类事件。这是丰田在同类事件中第一次被判有责。庭审过后丰田马上同意支付300万美元进入调解程序。 出于好奇，我漫不经心地下载了Barr的286页证词，却一下子被吸引住了。几天内读完，算是对这次事件进行了一次深入了解。下面就从外行角度总结一下这份证词并尝试以更简单的语言解释里面提到的暴冲原因以及丰田犯下的错误。 Barr的证词下载自他的个人博客Barr Code，但现在该文已经被删除。见2楼。 Michael Barr是谁？他是一位拥有20年以上行业经验的嵌入式系统工程师。在十八个月中，有12位嵌入式系统专家，包Barr，受原告诉讼团所托，被关在马里兰州一间高度保安的房间内对丰田动力控制系统软件（主要是2005年的凯美瑞）源代码进行深度审查。这房间没有英特网，没有手机信号，他们进出不能携带任何纸张、记录甚至皮带。最后的调查结果被写入一份800页，13章的详细报告。而鉴于保密协议，调查内容一直没有公布，直至俄克拉荷马这次庭审才首度部分公开（报告本身似乎还没公开）。 回到正题。丰田的软件有没有缺陷？根据Barr的调查，答案是有。这其实是废话，任何软件都会有缺陷，关键在于是什么样的缺陷。丰田的软件缺陷分为三类： 非常业余的结构设计 软件设计的基本要求是模块尽量简单化，因为这样可以一来更易于阅读二来更易于维护。但丰田的工程师显然没有遵循这原则。Barr使用一种工具自动根据代码的可能分支数量评估函数的复杂度，结果是丰田的软件中至少有67条函数复杂度超过50，意味着运行这个函数可能出现超过50种不同的执行结果，属于“非可测”级别。因为为了测试这50个不同的结果，必须准备至少50条不同的测试用例以及相应的文档，在生产环境中一般是不现实的。作为比较，Barr表示他自己的公司严格执行的其中一条规定就是任何代码复杂度不能超过30，否则不合格。而在这67条函数中还有12条复杂度超过100，达到“非可维护”级别，意味着一旦发现缺陷（Bug）也无法修复，因为实在太复杂，修复缺陷的过程中会产生新的缺陷。其中最复杂的一条函数有超过1300行代码，146个可能执行路径——正好用于根据各传感器数值计算节气门开关角度。 如果你不知道什么是节气门，那么这里我稍微解释一下。为了让内燃机运行，有三大要素：燃油、空气和点火时机。空气和燃油的混合物进入气缸，被火花塞在正确的时间点燃推动活塞并最终推动曲轴和车轮前进。在电喷技术发明以后直到2002年以前，三大要素的燃油和点火时间是由电子设备控制，节气门机械连接加速踏板，由司机直接控制。节气门大致是一个连接加速踏板的“空气龙头”——踩下去越多，“龙头”打开得越大，允许越多的空气进入发动机输出更大的动力。2002年以后，丰田引入的“电子油门”让电子系统掌管了最后一个要素：空气。加速踏板不再机械连接节气门，而是连接一些传感器，由行车电脑将这些传感器数值计算成节气门开启角度再由马达控制节气门。我们稍后会再讨论节气门开合。 极复杂的代码带来的是极复杂的功能。下面说一下被称为“厨房洗涤盆”的Task X。这里先解释一下，丰田的软件系统和很多别的软件系统一样，都是由一个统领程序（称之为“操作系统”）和若干小程序（称之为Task）组成。就好比电脑上跑的Windows是统领全局的操作系统，网络浏览器和记事本是跑在操作系统上的小程序。丰田的系统里每个Task都有自己的名字，但这些名字非常敏感，敏感到每次被提及的时候律师都要求法庭内的没有阅读代码权限的人全部清场。为了减少清场次数，Barr将这个最重要的小程序称为Task X。这个Task X有多重要呢？跟厨房里的洗涤盆一样重要。它负责非常多的事情，包括计算节气门开启角度、速度监测和保持、定速巡航监测等等。Task X的不正常运行被认为是暴冲事件的元凶。稍后会再继续讨论Task X。 还有一些别的匪夷所思的发现。比如丰田的软件包含了超过一万一千个全局变量。如果你不知道什么是全局变量，那么只需要知道软件设计的一般原则是要尽量少使用全局变量，因为有可能带来无法预测的结果。这里的“少”的意思是“尽量接近零”，绝对不会是一万一千个。 不符合软件开发规范 如同很多行业一样，汽车行业也有自己的规范。更具体一点，由于汽车的危险性质，汽车控制系统被划分为“安全关键性系统（Safety Critical System）”——说白了就是安全性非常重要，弄不好会死人的。为了达到这一特殊要求，汽车相关软件开发人员定期举行会议讨论并发布编程规范，称为MISRA C。该规范的2004年版的感谢列表里还能看到丰田员工的名字，至少让外界认为丰田确实也在遵循这些规范。 真的吗？根据源代码来看，答案是否定的。对此之前的NASA报告也有所提及，丰田辩称他们遵循的不是行业规范，而是丰田内部编程规范。这一规范与行业规范的吻合程度达到50%。但是Barr认为根据他的调查，两个规范之间吻合度小于10%，甚至有若干规范条目相互冲突。后来发现丰田的代码甚至没有遵循丰田内部规范，当然比起别的问题这个已经无关紧要了。 MISRA C拥有超过100条规范，NASA的调查只使用了到其中35条进行校对，发现超过7000处违规代码。Barr使用全部条目，对照结果是丰田的程序拥有超过80000处违规代码。 这些数字说明了什么？根据统计，违规数量可以用于预测代码中暗藏的缺陷（Bug）数量。在之前提到的汽车相关软件开发人员会议中，有人就这一主题发表过专题演讲，提出每30处违规代码可能包含一个重大缺陷和十个轻微缺陷。讽刺的是这人是丰田员工。 特别需要指出MISRA C其中一个规则的内容是不得使用递归。 如果你不知道什么是递归，那么这里我稍微解释一下。递归是一种计算方法。但一般计算方法要么是自己算，要么询问别的计算模块索要结果。而递归则是通过问一层层问自己的方法完成计算。好处是代码简单，坏处是计算层数不固定。可能会2层就出结果了，也可能会是10000层，在设计程序的时候无从得知。 软件计算需要消耗存储器。越繁琐、越长的计算自然需要占用越多的存储器。递归的问题在于其嵌套层数无法预测，从而导致可能消耗的存储器容量无法控制。稍后会再讨论存储器。 对关键变量缺乏保护。 什么是变量？变量就是存在一段存储器的0和1的集合。这些变量既可以是一些函数的处理结果，也可以是另一些函数的处理原材料。比方说前面提到有一条程序专门计算节气门开合角度，比如说是20度，这个20就是一个变量，存在存储器的一个指定位置。 另一个程序专门负责开合节气门，它知道去那个指定位置读取这个20，然后把节气门开启20度。 什么是保护？嵌入式系统，或者任何系统，都会在一定条件下发生硬件或者软件错误。客观上这是无法避免的。而且汽车作为一个时常在震动、发热、位移的系统，它的内部环境不能说不恶劣，发生硬件错误的可能性甚至更高。什么样的硬件错误呢？别忘了变量都是0和1的组合，这些0和1由存储器上的高低电平代表。由于某些不可抗原因，一个电平从高变成低，或者反过来，那么这个变量就被更改了。这被称为“位反转（Bit Flip）”。为了对抗这样的事情发生，需要对变量进行保护。保护的方法一般是镜像法。简单来说就是在两个不同的地方写入同一个变量，读取的时候两边都读，比较是不是一致。如果不一致，那么可以得知这个变量已经不可靠，需要进行容错处理。 丰田的程序总体上对其上万个变量进行了有效保护，但问题出在操作系统上。前面提到丰田的软件本质上分为操作系统和Task。Task是由丰田自己开发，但是操作系统则是由芯片供应商提供，固化在芯片里的。丰田在这里的过失是没有对供应商提供的代码进行深度审核，拿到什么用什么。 另一个保护措施是错误校验码（Error Detective and Correction Codes，EDAC）。这是一个硬件层面的数据保护措施。简而言之就是给内存中每一个字节（8比特）后面物理地增加几比特校验码。这样万一变量出错了，可以通过校验码得知，甚至可以通过校验码修复一些轻微错误。这个措施十分简单有效，但是在2005年款凯美瑞的系统中完全没有使用，丰田却告诉NASA他们用了。而在2008年款凯美瑞中使用了3比特长的EDAC。Barr认为是为了节省成本，否则应该使用5比特长。 还有值得一提的是，汽车相关的软件行业有那么几家操作系统供应商，早已形成了一套成熟标准称为OSEK。各供应商开发的符合OSEK认证的操作系统至少都能达到一定的质量。但丰田选用的操作系统却没有通过认证，让人不解。 现在我们知道丰田在编写软件的时候至少有三种缺陷。那么重点问题：丰田的这些软件缺陷是否会导致车辆暴冲？根据Barr的调查，答案是有可能。暴冲的起因需要结合上述三种缺陷来说明。 汽车正常运行需要倚靠若干程序（这里叫Task）的同时运作。Task有很多，CPU只有一块，在任何时刻只能处理一个Task，怎么办呢？这需要操作系统的统筹规划，合理分配CPU的任务，让每个Task都能按时执行。如果出现某种意外，让某个Task突然不执行了，那么就称为这个Task“死亡”。Task死了，自然不能执行它的任务。根据Barr的测试，在某些特定情况下，Task X的死亡可以导致节气门敞开——因为Task X的其中一个任务就是根据司机的操作计算节气门开合角度，它死了也就没法重新计算这个角度，即使司机把脚挪开加速踏板，节气门也无法关闭。此为暴冲的直接原因。更糟糕的是，节气门的开合角度这个数值，被Task X算出来以后保存在一个变量中。这个特定的变量正好没有被保护（缺陷3）。意味着万一Task X死亡并且停止计算，这个数值有可能因为不可抗原因被改变，而程序无从得知。 那么Task X为何会死亡呢？一般是因为内存出错。这个出错可能是一个小小的位反转，也可能是内存里的数值被别的程序错误覆盖。同一系统内同时运行了若干程序，这些程序需要共享一块内存，内存内部必然要被划分成若干块。比如第一块给程序1，第二块给程序2，等等。如果程序1因为某些原因（比如Bug）写到第二块内存上去，就会导致程序2读取了错误的信息。这就是所谓的内存出错。丰田的系统里，正好有这么两块相邻的内存块。第一块被称为“堆栈（Stack）”，这是所有Task存储它们运行状态的地方，大小为4KB。与之相邻的地方储存了操作系统进行任务分配的记录。那么可以想象，如果很多Task给堆栈里写入太多东西，超过4KB，那么就会错误地写入与之相邻的任务分配表。这种错误被称为“堆栈溢出”。操作系统拿到了错误的任务分配表，就会错误地分配任务，造成某些Task多执行几次，某些Task少执行几次，某些Task甚至就再也不执行——死了！必须指出的是，程序死亡并不罕见，甚至可以认为是正常现象。稍后解释处理方法。 那么堆栈为什么会溢出呢？显然是因为要写入的数据超过了堆栈的容量。在设计程序的时候要计算最坏的情况并且允许冗余。即使作出了正确的设计，这种错误也相对常见，所以NASA在他们的调查中重点排查堆栈溢出的可能性。于是NASA问丰田，丰田的回复是最坏的情况下4KB堆栈只写入了41%的数据，换句话说发生溢出的可能性非常低。NASA直接取信了这个数字并没有再深入调查。但Barr他们发现丰田的回答有严重低估，实际上最坏的情况会达到94%，而且还不算递归。丰田在代码中使用了递归（缺陷2）。因而实际数字有可能超过94%而且无法预计上限，因为递归计算的嵌套层数是无法预测的。所以实际情况下堆栈溢出的可能性相当可观。一旦溢出，相邻的任务分配表不可避免就会遭到破坏。此为暴冲的根本原因其中之一。之所以说“其中之一”，是因为堆栈溢出仅仅是损坏任务分配表的其中一个原因，别的还有许多可能性并没有被Barr在法庭上深入解释。而且任务分配表的损坏也仅仅是导致Task死亡的原因之一。 顺便提一句，2005年的凯美瑞的这部分供应商是电装，没有搭载堆栈实时监测功能——溢出了也不知道。同年的卡罗拉却搭载了，因为供应商是通用。 到这里我小结一下，串链子。左边是原因，右边是后果。 堆栈溢出→（可能导致）→任务分配表被改写→（可能导致）→Task X死亡→（可能导致）→节气门敞开→（导致）→汽车暴冲 必须指出的是，这条链子从最左边一直到Task X死亡，都还算是嵌入式系统的常见故障。虽然程序代码写得不好也许导致更容易出错，客观上丰田并没有特别大的过错。只要处理得当，这些故障都不会导致暴冲。 到此为止还只是前奏而已，接下来我们来看看丰田到底做错了什么。 【第二部分】丰田之罪 上面反复提到，嵌入式系统中内存出错或者程序死亡其实是一种正常现象——至少从Barr的证词可以得出这个结论——现在连我们都知道了，嵌入式工程师肯定比我们更清楚才对。确实，为了使系统正常运行不被错误干扰，一般的做法是设置若干层防护措施（Failsafe），让运行中出现的错误无法轻易突破，得到妥善处理。丰田的工程师自然也懂得这一点。很可惜，他们搞砸了。 上面那条链子应该修改成这样： （防护措施0）→堆栈溢出→（防护措施1）→（可能导致）→任务分配表被改写→（防护措施2）→（可能导致）→Task X死亡→（防护措施3）→（可能导致）→节气门敞开→（防护措施4）→（导致）→汽车暴冲 可以看到，防护措施不可谓不多。只要处理得当，这链条应该是走不通的。现在让我们从左到右看一个小小的内存错误是如何一层层突破防护最终导致汽车暴冲的。 首先防护措施0： 这个其实上面提到了，因为设计缺陷低估了最大占用的存储容量，并且不符合规范地使用了递归，最终可能导致堆栈溢出。 然后到防护措施1： 上面也提到了，任务分配表紧邻堆栈。作为外行我都觉得这是个十分危险的设计——既然堆栈这么容易溢出，好歹应该将任务分配表放远一点啊。当然我是外行，可能实际上比想象中复杂很多。这段Barr的证词中并未特别提到，属于我的个人理解。...