Random Hardware Faults

Computer hardware randomly generates incorrect answers once in a while, in some cases due to single event upsets from cosmic rays. Yes, really! Here's a summary of the problem and how often you can expect it to occur, with references for further reading.

---------------------------------------

(As will be the case with some of my posts over the next few months, this text is written more in an academic style, and emphasizes automotive safety applications since that is the area I perform much of my research in. But I hope it is still useful, if less entertaining in style than some of my other posts.)

Hardware corruption in the form of bit flips in memories has been known to occur on terrestrial computers for more than 30 years (e.g., May & Woods 1979; Karnik et al. 2004, Heijman 2011). Hardware data corruption includes changes during operation made to both RAM and other CPU hardware resources (for example bits held in CPU registers that are intermediate results in a computation).

"Soft errors" are those in which a transient fault causes a loss of data, but not damage to a circuit. (Mariani03, pg. 51) Terminology can be slightly confusing in that a “soft error” has nothing to do with software, but instead refers to a hardware data corruption that does not involve permanent chip damage. These “soft” errors can be caused by, among other things, neutrons created by cosmic rays that penetrate the earth’s atmosphere.

Soft errors can be caused by external events such as naturally occurring alpha radiation particle caused by impurities in the semiconductor materials, as well as neutrons from cosmic rays that penetrate the earth’s atmosphere (Mariani03, pp. 51-53). Additionally, random faults may be caused by internal events such as electrical noise and power supply disruptions that only occasionally cause problems. (Mariani03, pg. 51).

As computers evolve to become more capable, they also use smaller and smaller individual devices to perform computation. And, as devices get smaller, they become more vulnerable to data corruption from a variety of sources in which a subtle fleeting event causes a disruption in a data value. For example, a cosmic ray might create a particle that strikes a bit in memory, flipping that bit from a “1” to a “0,” resulting in the change of a data value or death of a task in a real time control system. (Wang 2008 is a brief tutorial.)

Chapter 1 of Ziegler & Puchner (2004) gives an historical perspective of the topic. Chapter 9 of Ziegler & Puchner (2004) lists accepted techniques for protecting against hardware induced errors, including use of error correcting codes (id., p. 9-7) and memory scrubbing (id., p. 9-8). It is noted that techniques that protect memory “are not effective for computational or logic operations” (id., p. 9-8), meaning that only values stored in RAM can be protected by these methods, although special exotic methods can be used to protect the rest of the CPU (id., p. 1-13).

Causes for such failures vary in source and severity depending upon a variety of conditions and the exact type of technology used, but they are always present. The general idea of the failure mode is as follows. SRAM memory uses pairs of inverter logic gates arranged in a feedback pattern to “remember” a “1” or a “0” value. A neutron produced by a cosmic ray can strike atoms in an SRAM cell, inducing a current spike that over-rides the remembered value, flipping a 0 to a 1, or a 1 to a 0. Newer technology uses smaller hardware cells to achieve increased density. But having smaller components makes it easier for a cosmic ray or other disturbance to disrupt the cell’s value. While a cosmic ray strike may seem like an exotic way for computers to fail, this is a well documented effect that has been known for decades (e.g., May & Woods 1979 discussed radiation-induced errors) and occurs on a regular basis with a predictable average frequency, even though it is fundamentally a randomly occurring event.

Radiation strike causing transistor disruption (Gorini 2012).

A paper from Dr. Cristian Constantinescu, a top Intel dependability expert at that time, summarized the situation about a decade ago (Constantinescu 2003). He differentiates random faults into two cases. Intermittent faults, which might be due to a subtle manufacturing or wearout defect,  can cause bursts of memory errors (id., pp. 15-16). Transient faults, on the other hand, can be caused by naturally occurring neutron and alpha particles, electromagnetic interference, and electrostatic discharge (id., pg. 16), which he refers to as “soft errors” in general. To simplify terminology, we’ll consider both transient and intermittent faults as “random” errors, even though intermittent errors strictly speaking may come in occasional bursts rather than having purely random independent statistical distributions. His paper goes on to discuss errors observed in real computers. In his study, 193 corporate server computers were studied, and 69% of them observed one or more random errors in a 16-month period. 2.6 percent of the servers reported more than 1000 random errors in that 16-month period due to a combination of random error sources (id., pg. 16):

Random Error Data (Constantinescu 2003, pp. 15-16).

This data supports the well known notion that random errors can and do occur in all computer systems. It is to be expected due to minute variations in manufacturing, environments, and statistical distribution properties that some systems will have a very large number of such errors in a short period of time, while many of the same exact type of system will exhibit none even for extended periods of operation. The problem is only expected to get worse for newer generations of electronics (id., pg. 17).

Excerpt from Mariani 2003, pg. 50

Mariani (2003, pg. 50) makes it clear that soft errors “are officially considered one of the main causes of loss of reliability in modern digital components.” He even goes so far to say of “x-by-wire” automotive systems (which includes “throttle-by-wire” and other computer-controlled functions): “Of course such systems must be highly reliable, as failure will cause fatal accidents, and therefore soft errors must be taken into account.” Additionally, random faults may be caused by internal events such as electrical noise and power supply disruptions that only occasionally cause problems. (Mariani 2003, pg. 51). MISRA Report 2 makes it clear that “random hardware failures” must be controlled for safety critical automotive applications, with a required rigor to control those failures increasing as safety becomes more important. (MISRA Report 2 p. 18).

Semiconductor error rates are often given in terms of FIT (“Failures in Time”), where one FIT equals one failure per billion operating hours.  Mariani gives representative numbers as 4000 FIT for a CPU circa 2001 (Mariani03, pg. 54), with error rates increasing significantly for subsequent years. Based on a review of various data sources considered it seems reasonable to use an error rate of 1000 FIT/Mbit (1 errors per 1e13 bit-hr) for SRAM. (e.g., Heijman 2011 pg. 2, Wang 2008 pg. 430, Tezzaron 2004) Note that not all failures occur in memory. Any transistor on a chip can fail due to radiation, and not all storage is in RAM. As an example, registers such as a computer’s program counter are exposed to Single Event Upsets (SEUs), and the effect of an SEU there can result in the computer having arbitrarily bad behavior unless some form of mitigation is in place. Automotive-specific publications state that hardware induced data corruption must be considered (Seeger 1982).

SEU rates vary considerably based on a number of factors such as altitude, with data presented for Boulder Colorado showing a factor of 3.5 to 4.8 increase in cosmic-ray induced errors over data collected in Essex Junction Vermont (near sea level) (O’Gorman 1994, abstract).

Given the above, it is clear that random hardware errors are to be expected when deploying a large fleet of embedded systems. This means that if your system is safety critical, you need to take such errors into account. In a future post I'll explore how bad the effects of such a fault can be.

References:

Constantinescu, Trends and challenges in VLSI circuit reliability, IEEE Micro, July-Aug 2003, pp. 14-19

Heijmen, Soft errors from space to ground: historical overview, empirical evidence, and future trends (Chapter 1), in: Soft Errors in Modern Electronic Systems, Frontiers in Electronic Testing, 2011, Volume 41, pp. 1-41.

Karnik et al., Characterization of soft errors caused by single event upsets in CMOS processes, IEEE Trans. Dependable and Secure Computing, April-June 2004, pp. 128-143.

Los Alamos National Laboratory, The Invisible Neutron Threat, https://www.lanl.gov/science/NSS/issue1_2012/story4full.shtml 

Mariani, Soft errors on digital computers, Fault injection techniques and tools for embedded systems reliability evaluation, 2003, pp. 49-60.

May & Woods, Alpha-particle-induced soft errors in dynamic memories, IEEE Trans. On Electronic Devices, vol. 26, 1979

MISRA, Report 2: Integrity, February 1995. (www.misra.org.uk)

O’Gorman, The effect of cosmic rays on the soft error rate of a DRAM at ground level, IEEE Trans. Electron Devices, April 1994, pp. 553-557.

Seeger, M., Fault-Tolerant Software Techniques, SAE Report 820106, International Congress & Exposition, Society of Automotive Engineers, 1982, pp. 119-125.

Tezzaron Semiconductor, Soft Errors in Electronic Memory -- A White Paper, 2004, www.tezzaron.com

Wang & Agrawal, Single event upset: an embedded tutorial, 21st Intl. Conf. on VLSI Design, 2008, pp. 429-434.

Ziegler & Puchner, SER – History, Trends, and Challenges: a guide for designing with memory ICs, Cypress Semiconductor, 2004.

Additional material:

• Article on cosmic ray memory corruption as a limiting factor in supercomputer size: https://spectrum.ieee.org/computing/hardware/how-to-kill-a-supercomputer-dirty-power-cosmic-rays-and-bad-solder
• Cosmic rays and Japanese network malfunctions: "Cosmic rays causing 30,000 network malfunctions in Japan each year, April 5, 2021: https://mainichi.jp/english/articles/20210405/p2g/00m/0bu/028000c
• https://www.bbc.com/future/article/20221011-how-space-weather-causes-computer-errors

The Therac 25: A Case Study in Unsafe Software

Many of you are writing software that has safety aspects creeping into it. There's nothing like a real-world case study to bring home both the consequences of unsafe software. The Therac 25 story is must-read material. The short version is several radiation therapy patients were killed by massive radiation overdoses that trace back to bad software. See below for more details...

--------------------------------------------------------------------

(This article is written in an academic style rather than as an informal blog post. But hopefully it's informative.)

The Therac 25 accidents form the basis for what is often considered the best-documented software safety case-study available. The experience illustrates a number of principles that are vital to understanding how and why the design and analysis of safety-critical systems must be done in a methodical way according to established principles. The Therac 25 accidents came at a time before many current practices were widespread, and serve as a cautionary tale for why such practices exist and are essential to creating safe systems.

Briefly, the Therac 25 was a medical radiation therapy machine that was supposed to deliver controlled doses of radiation to cancer patients. Basically, this was a “radiation-by-wire” system in which software was used to replace some hardware safety mechanisms. Due to software defects, among other factors, it was involved in six known massive overdose accidents resulting in deaths and serious injuries. (Leveson 1993, p. 18). A simple explanation of the likely mechanism for the accidents was using a beam strength for x-ray exposure, but without the electron beam to X-ray metallic beam-attenuating conversion target target in place, resulting in 100x over-doses. Due to limitations of the dose measurement system, the way patients knew they were over-exposed was radiation burns (and, in at least one case, a reported sizzling sound of the radiation dose measurement devices frying).


(Source: ComputingCases.Org)

Some of the characteristics of the Therac 25 development process are summarized as: almost all testing was done at the system level rather than as lower level unit tests, shared memory variables are unprotected from concurrency defects, and “race conditions due to multitasking without protecting shared variables played an important part in the accidents.” (id., text box pp 20-21)  Operators were taught that there were “so many safety mechanisms” that it was “virtually impossible to overdose a patient.” (id., p. 24)

The manufacturer could not reproduce an initially reported problem involving the Ontario Cancer Foundation mishap in 1985. After analysis, they blamed a patient turntable position measurement sensor. A sensor modification and a software failsafe were added to mitigate the problem, (id. pg. 23-26) and the manufacturer claimed a five order of magnitude safety improvement. But this was not an accurate assessment.

Later, after the 1986 East Texas Cancer Center accidents, two manufacturer engineers could not reproduce a malfunction indication reported by the local staff. The manufacturer’s “home office engineer reportedly explained that it was not possible for the Therac-25 to overdose a patient.” But this was found to be untrue after an investigation into a second overdose a month later at the same facility revealed the problem to be a software defect. (id., pp. 27-28) Reproducing the effects of the software defect was difficult, because it was timing-dependent and involved the speed of radiation prescription data entry. (id., p. 28) A number of hardware and software mitigations were added (id., pp. 31-32). But even then, an entirely different timing-dependent software problem emerged to cause the Yakima Valley 1987 overdose mishap (id., pp. 33-34), and potentially another mishap.

At a technical level, some of the factors that contributed to the Therac 25 accidents included: cryptic error messages, using a home-brew real time operating system, mutex operations that were not atomic (and therefore, defective), race conditions between user inputs and machine actions, a problem that only manifested when a counter value rolled over to zero, and generally inadequate testing and reviews.

When used for treatment, the machines were known to throw lots of error codes. But instead of this being seen as a sign that the machines were exercising the safety mechanisms often (which is a really bad idea), this was interpreted as being safe due to all the shutdowns. In reality, a system that exercises its failsafes all the time is prone to eventually seeing a fault that gets past the failsafes. It's well known in operating safety-critical systems that exercising failsafes is undesirable. They are your last line of defense, and should be a last resort backup that is almost never activated. Regularly exercising failsafes is a hallmark of an unsafe system.

The lessons from the Therac 25 form bedrock principles for the safety critical software community. They include: “Accidents are seldom simple – they usually involve a complex web of interacting events with multiple contributing technical, human, and organizational factors.” (id., p. 38). Do not assume that fixing a particular error will prevent future accidents (“There is always another software bug”) (id.). Higher level system engineering failures are often relevant, such as: lack of follow-through on all reported incidents, overconfidence in the software, less-than-acceptable software engineering practices, and unrealistic risk assessments (which for the Therac 25 included an assessment that the software was defect-free). (id.).

“Designing any dangerous system in such a way that one failure can lead to an accident violates basic system-engineering principles. In this respect, software needs to be treated as a single component.” (id. pp. 38-39). (In context, this refers to the software resident on a single CPU, meaning that if any software defect on one CPU can cause an accident, that is a single point failure that renders the system unsafe.)

Leveson lists “basic software-engineering practices that apparently were violated with the Therac-25” as: documentation should not be an afterthought; software quality assurance practices and standards should be established; designs should be kept simple; ways to get error information should be designed in; and that “the software should be subjected to extensive testing and formal analysis at the module and software level: system testing alone is not adequate.” (id., p. 39) Leveson finishes by saying that although this was a medical system, “the lessons apply to all types of systems where computers control dangerous devices.” (id., p. 41)

Reference:

Leveson, An investigation of the Therac-25 Accidents, IEEE Computer, July 1993, pp. 18-41. (updated version here: http://sunnyday.mit.edu/papers/therac.pdf)

Other reading:

Therac-25 Case materials for teaching: http://www.computingcases.org/case_materials/therac/therac_case_intro.html 

CMU 18-649 Software safety lecture (second half covers Therac 25)

Better Embedded System Software. Chapter 28 is on software safety.

Automated Vehicle Research Challenges

This is an academic paper for a National Science Foundation workshop on "Transportation Cyber-Physical Systems."  Since automated vehicle deployment is a hot topic now, some of my readers might be interested in what I see as key challenges.  By way of background, much of my current research work centers on stress-testing automated vehicle software and creating run-time safety monitors for them, so that gives you an idea of where I'm coming from.

The short version is -- it's not going to be easy to go from a handful of demonstrator autonomous vehicles to a large-scale deployed fleet. In large part this is because there isn't an established way to ensure the safety of "AI" type techniques (e.g., machine learning algorithms). I'm not saying it's impossible, and some smart people are working on this. But it is definitely a research challenge and not just grinding through an engineering problem.

Paper Abstract:
Creating safe Transportation Cyber-Physical Systems (CPSs) presents new challenges as autonomous operation is attempted in unconstrained operational environments. The extremely high safety level required of such systems (perhaps one critical failure per billion operating hours) means that validation approaches will need to consider not only normal operation, but also operation with system faults and in exceptional environments. Additional challenges will need to be overcome in the areas of rigorously defining safety requirements, trusting the safety of multi-vendor distributed system components, tolerating environmental uncertainty, providing a realistic role for human oversight, and ensuring sufficiently rigorous validation of autonomy technology.

Link to paper:
http://www.ece.cmu.edu/~koopman/pubs/koopman14_cps_transportation.pdf

Link to workshop position paper submissions:
http://cps-vo.org/group/CPSTransportationWksp2014/CFP-submissions

(For the curious, "Cyber-Physical Systems" is an extension of the idea of "embedded systems," generally including more scope such as control and mechanical system aspects. The distinctions between "embedded" and "CPS" depend upon whom you ask, and there is not a bright line to be drawn between the two concepts.)

Do Not Re-Enable Interrupts In An ISR

Summary: It might sound intuitive to re-enable interrupts within an ISR so higher priority interrupts can run without delay. But, in fact, this is probably the worst thing you can do for delay, and might even make the code unsafe due to stack overflow.

---

A previous post on rules for using interrupts included the rule:

• "Don't re-enable interrupts within an Interrupt Service Routine (ISR).  That's just asking for subtle race condition and stack overflow problems."

Some developers take a different point of view, and feel that it is best to re-enable interrupts to let higher priority ISRs run without delay. The idea is that high priority interrupts should run as soon as possible, without having to wait for low priority interrupts to complete. Re-enabling interrupts within an ISR seems to let that happen. BUT, while there might be some intuitive appeal to this notion, this is a dangerous practice that makes things worse instead of better.

First, to recap, when an interrupt triggers an ISR one of the first things that happens is that further interrupts get masked by the interrupt handling hardware mechanisms. Once the ISR starts running, at some point (best is at the beginning) it acknowledges the interrupt source, clearing the interrupt request that triggered the ISR. At that point the ISR can re-enable interrupts if it wants to, or leave them masked until the ISR completes execution. (The "return from interrupt" instruction will typically restore interrupt flags, re-enabling interrupts as appropriate when the ISR completes.) If interrupts are re-enabled within the ISR, then another interrupt can suspend the ISR and run some other, second ISR. This means that if a higher priority interrupt comes along, it can run its ISR right away.

The problem is that other, bad, things can also happen once interrupts are re-enabled:

•  If a lower priority interrupt comes along, it also gets to run, suspending the currently running, higher priority ISR. Interrupt priority hardware does not keep track of interrupt history after an ISR starts and acknowledges its interrupt source, and so loses track of how high the priority is for the running ISR. Worse, if a high and low priority interrupt happen at the same time, this approach guarantees that the high priority ISR waits for the low priority ISR. This happens because the high priority ISR runs first, then gets preempted by the lower priority ISR as soon as interrupts are re-enabled. In the case where no other interrupts are pending, the low priority ISR runs to completion before the high priority ISR gets to finish.

• The ISRs nest as above rather than running one at a time, filling up the stack. You might be able to account for this by allocating enough stack for all ISRs to be active at the same time.  But if you leave interrupts masked in ISRs. the worst case is only the single biggest ISR stack use. (Some hardware has multiple tiers/levels/classes ... pick your favorite term ... of interrupts, but in that case it is still only one ISR of stack use per tier rather than one per ISR source.)

• The same ISR might run more than once at a time, especially if it got unlucky and was preempted by other ISRs, delaying its completion time. For example, if you get a burst of noise on an ISR hardware line you might kick of a half dozen or so copies of the same ISR. Or once in a while hardware events happen close together and re-trigger the ISR. This will lead to trouble if your ISR code is not re-entrant. It also could overflow the stack, ending up in memory corruption, etc. unless you can accurately predict or limit how many times ISRs can be re-triggered in absolute worst-case conditions.

You could say "the highest priority ISR doesn't re-enable interrupts"  -- but what about the second-highest priority ISR? Once you get more than a couple ISRs involved this gets hopeless to untangle. You could try to write some sort of ISR handler to mitigate some of these risks, but it's going to be difficult to get right, and add overhead to every ISR. In all, the situation sounds pretty messy and prone to problems .. and it is. You might get away with this on some systems some of the time if you are really good (and never make mistakes). But, getting concurrency-related tricky code right is notoriously difficult.  Re-enabling interrupts is just asking for problems.

So let's look at the alternative. What is the true cost you might be trying to avoid in terms of delaying that oh-so-urgent high priority ISR because you're not re-enabling interrupts in an ISR? 

The worst case is that the longest-running low priority ISR runs to completion, making all the higher priority ISRs wait for it to complete before they can start. But after that all the remaining ISRs that are pending will complete in priority order -- highest to lowest priority. That's exactly what you want except for the low priority ISR clogging up the works. So if you have an obnoxiously long low priority ISR that's a problem. But if none of your ISRs run for very long (which is how you're supposed to write ISRs), you're fine. Put into scheduling terms, you want to make sure none of your ISRs runs long, because a long-running ISR gives you a high blocking time, and blocking time delays high priority tasks from completing. 

Let's compare outcomes for the two alternative strategies. If you re-enable interrupts, the worst case latency for the highest priority ISR in the system is that it arrives, and then gets preempted by every other ISR in the system (including the longest-running ISR if it comes in later, but before the high priority ISR has a chance to complete).  If you leave interrupts masked, the worst case is that the longest-running ISR has to complete, but then the high priority ISR goes immediately afterward. So, leaving interrupts disabled (masked) during every ISR is clearly a win for the worst case, in that you only have to wait for the longest-running ISR to complete before running the highest priority ISR, instead of waiting for all ISRs to complete. The worst case is typically what you care about in a real time embedded system, so you should leave interrupts disabled in ISRs to ensure the fastest worst-case completion time of high priority ISRs. And, leaving interrupts disabled in ISRs also gets rid of the risks of stack overflow and re-triggered ISRs we mentioned.

UPDATE: To avoid confusion, it's important to note that the above is talking about what happens at ONE level of interrupts, such that when one ISR is running no other interrupts run until the ISR completes or ISRs at that level complete. Many architectures have multiple levels, in which one ISR can interrupt another ISR at a lower level even if that lower level has interrupts masked. This corresponds to the comment about one ISR per level being active in the worst case. Also, note that if an architecture can change the priorities of interrupts within a single level that's irrelevant -- it is the existence of levels that are each individually maskable and that are prioritized as groups of interrupts per level that gives a way around some of these problems. So, going back to the title says, do not RE-enable the same level of interrupts within an ISR.

Why You Need A Software-Specific Test Plan

Summary: Pretty much every embedded system goes through some sort of system test. But, you need to do software-specific testing in addition to that.  For example, what if you ship a system with the watchdog timer accidentally turned off?

---

In essentially every embedded system there is some sort of product testing. Typically there is a list of product-level requirements (what the product does), and a set of tests designed to make sure the product works correctly. For many products there is also a set of tests dealing with fault conditions (e.g., making sure that an overloaded power supply will correctly shed load). And many companies think this is enough .. but I've found that such tests usually fall short in many cases.

The problem is that there are features built into your software that are difficult or near-impossible to test in traditional product-level testing.  Take the watchdog timer for example. I have heard more than one developer say that there was a case where a product shipped (at least one version of a product) with the watchdog timer accidentally turned off. How could this happen?  Easy: a field problem is reported; developer turns off watchdog to do single-step debugging; bug found and fixed; forgot to turn the watchdog back on; product test doesn't have a way to intentionally crash the software to see if the watchdog is working; new software version ships with watchdog timer still turned off.

Continuing with the watchdog example, how do you solve this? One way is to include user-accessible functions that exercise the watchdog timer by intentionally crashing the software. Sounds a bit dangerous, especially if you are worried about security. More likely you'll need to have some separate, special way of testing functions that you don't want visible to the end user. And you'll need a plan for executing those tests.

And ... well, here we are, needing a Software Test Plan in addition to a Product Test Plan. Maybe the software tests are done by the same testers who do product test, but that's not the point. The point is you are likely to need some strategy for testing things that are there not because the end product user manual lists them as functions, but rather because the software requirements say they are needed to provide reliability, security, or other properties that aren't typically thought of as product functions. ("Recovers from software crashes quickly" is typically not something you boast about in the user manual.) For similar reasons, the normal product testers might not even think to test such things, because they are product experts and not software experts.

So to get this right the software folks are going to have to work with the product testers to create a software-specific test plan that tests what the software requirements need to have tested, even if they have little directly to do with normal product functions. You can put it in product test or not, but I'd suggest making it a separate test plan, because some tests probably need to be done by testers who have particular skill and knowledge in software internals beyond ordinary product testers. Some products have a "diagnostic mode" that, for example, sends test messages on a network interface. Putting the software tests here makes a lot of sense.

But for products that don't have such a diagnostic mode, you might have to do some ad hoc testing before you build the final system by, for example, manually putting infinite loops into each task to make sure the watchdog picks them up. (Probably I'd use conditional compilation to do that -- but have a final product test make sure the conditional compilation flags are off for the final product!)

Here are some examples of areas you might want to put in your software test plan:

• Watchdog timer is turned on and stays turned on; product reboots as desired when it trips
• Watchdog timer detects timing faults with each and every task, with appropriate recovery (need a way to kill or delay individual tasks to test this)
• Tasks and interrupts are meeting deadlines (watchdog might not be sensitive enough to detect minor deadline misses, but deadline misses usually are a symptom of a deeper problem)
• CPU load is as expected (even if it is not 100%, if you predicted an incorrect number it means you have a problem with your scheduling estimates)
• Maximum stack depth is as expected
• Correct versions of all code have been included in the build
• Code included in the build compiles "clean" (no warnings)
• Run-time error logs are clean at the end of normal product testing
• Fault injection has been done for systems that are safety critical to test whether single points of failure turn up (of course it can't be exhaustive, but if you find a problem you know something is wrong)
• Exception handlers have all been exercised to make sure they work properly. (For example, if your code hits the "this can never happen" default in a switch statement, does the system do something reasonable, even if that means a system reset?)

Note that some of these are, strictly speaking, not really "tests." For example, making sure the code compiles free of static analysis warnings isn't done by running the code. But, it is properly part of a software test plan if you think of the plan as ensuring that the software you're shipping out meets quality and functionality expectations beyond those that are explicit product functions.

And, while we're at it, if any of the above areas aren't in your software requirements, they should be. Typically you're going to miss tests if there is nothing in the requirements saying that your product should have these capabilities.

If you have any areas like the above that I missed, please leave a comment.  I welcome your feedback!

CRC and Checksum Tutorial Webinar

I've completed my FAA-sponsored look at CRC and Checksum performance for aviation systems. While some of the material is aircraft-specific, it is all relevant to safety critical systems and contains quite a bit of information about CRC vs. checksum performance.

I'm pleased to be able to share a two-hour Webinar recording describing all the work, as well as the slides and draft report. There is a guide to the material below that you may find useful if you are looking for a specific topic.

• Video: Vimeo (streaming and download)
• Video:  Youtube (streaming)
• Slides (Acrobat)
• Final report (Acrobat)
• My other blog posts on CRCs and checksums

The general flow of the presentation is as follows, by slide number:

• 6 - CRC and checksum background and terminology

• 10 - Why picking the right CRC isn't as easy as you might think

• 20 - Summary of project technical approach

• 21 - Project results overview

• 24 - Checksum results (Checksum, Fletcher Checksum, ATN-32)

• 30 - CRC-32 compared to checksums

• 31 - It's all about the Hamming Distance

• 33 - Table of checksum compared to CRC-32

• 35 - Good CRC choices (8 & 16 bits)

• 36 - Good CRC choices (24 & 32 bits)

• 37 - Aviation industry results (might be enlightening for everyone)

• 43 - Multiple CRC & memory-specific CRC results

• 46 - System level effects and cross-layer interactions (e.g., unprotected length field, bit encoding)

• 48 - ARINC-825 / CAN issues

• 52 - 8b10b encoding Gbit Ethernet issue

• 53 - Mapping to criticality levels (how do you know your CRC/checksum is good enough?)

• 64 - Determining Bit Error Ratio (BER)

• 71 - Error detection mechanism failure and scrubbing

• 74 - A simple recipe for how to determine how big and capable a CRC/checksum you need

• 76 - CRC/Checksum seven deadline sins (bad ideas)

• 79 - Review of the study project subtasks (most readers can skip this part)

I owe significant thanks to my Co-Investigators Kevin Driscoll and Brendan Hall at Honeywell labs, without whom this work could not have been done. And also a warm and sincere thanks to our FAA contacts, and especially to Chuck Kilgore for his good spirits, kind words, and unfailing support.

NOTES:

"The provided links will give you the option of downloading the video file or view it through your web browser.   Some people have reported problems viewing the video with their web browser due to the 2 hour length.  Others have been able to view the video in a browser without any problems.   If you encounter problems, we recommend that you download the file for offline viewing if possible to avoid any streaming issues."

"This work was supported by the Federal Aviation Administration, Aircraft Certification Service, and Assistant Administration for NextGen, William J. Hughes Technical Center, Aviation Research Division, Atlantic City International Airport, New Jersey 08405. The findings and conclusions in this presentation are those of the author(s) and do not necessarily represent the views of the funding agency.  This presentation does not constitute FAA policy."

The Webinar was scheduled Oct 1, 2013, but was delayed due to the government shutdown. The webinar was actually held on Oct 29, 2013.

Secrecy vs. Integrity and Why Encryption Might Be the Wrong Choice

Summary: Encryption doesn't solve all security problems.  In many cases you need authentication and integrity, not secrecy, and encryption can be the wrong tool for the job.  In those cases you need a Message Authentication Code, not encryption.

---

It's pretty typical to see embedded system designers use encryption to solve security problems. And it's also common for that to be the wrong answer to the real problem.

To understand why, consider a simplistic security need. (This example is naive in many ways, but serves to illustrate a point.) Let's say you want to set a light bulb intensity to one of 256 levels, and you want to make sure that only an authorized person can set that level.  To do this with no security, you'd send a message on an embedded network to that light bulb:

Message =  BulbLevel               (where BulbLevel is an 8 bit unsigned integer)

OK, so now you want to encrypt things.  You compute  X = Encrypt(BulbLevel) with a shared secret key that only you and the light bulb know and send that in the message:

Encrypted Message = X              (still 8 bits)

Now there is no way for anyone to know what level you've sent -- you've accomplished secrecy.  (Ignore all those attacks that just came into your head, such as recording past messages and playing them back .. or peeking to see what the light bulb did when it received the message ... this is just an illustrative example.) But is secrecy what you really wanted?   Remember our goal in this example wasn't to keep it a secret what the level was, but rather to prevent someone unauthorized from setting the light bulb level.

What if an adversary just sent random garbage:

Encrypted Message = RANDOM_8_bits         (still 8 bits)

That would set the light bulb output to some value. Maybe not a desired value, but the attacker would be able to change the light value to something other than what you commanded without knowing the secret key, (with probability 255/256 that it wasn't a repeat of the value already there) which is what you're trying to prevent.

The issue is that encryption is the wrong tool for the job.  What you really want is some combination of authentication (I know the right person sent it) and integrity (I know the contents have not been altered). Encryption isn't the best tool for this -- what you want is a Message Authentication Code (MAC). One way to get this is to compute an appropriately chosen secure hash function and append its results to the message:

Authenticated Message = BulbLevel  |  SecureHash         (8 bits concatenated with a hash value)

Both you and the light bulb still have a shared secret key with this approach. The light bulb receiving the message computes its own hash of the BulbLevel value and compares it to the received SecureHash value in the message. If they match, the message is authentic and it takes action. If they don't match, then it is a forgery and the message is ignored. Note that the BulbLevel isn't a secret -- it's transmitted "in the clear." That's because the point of this isn't secrecy; it's authentication (the sender knows the secret key to the cryptographic hash function) and integrity (the hash matches the value expected from the BulbLevel value, so the message hasn't been tampered with). If the hash value is sufficiently large, the chance of someone guessing the right hash value for a maliciously sent bulb level is low enough to be tolerated or even virtually impossible given the lifetime of the lightbulb, providing an arbitrarily good probabilistic level of security.

There's another important benefit to using a MAC. Encryption for the purpose of keeping data secret tends to be export controlled. Message Authentication Codes tend not to be export controlled. So ditching encryption in favor of a MAC usually helps with export issues. (Read the rules and talk to your lawyer -- this is just a sweeping generalization.)

The overall message is: if you want to ensure authenticity and integrity and secrecy isn't a big deal, using encryption is barking up the wrong tree.

The fine print: OK, now for those who have begun composing comments about how naive the above schemes are ... yes, I know .. it was only an example. You don't actually do it that way for either approach. For example, you need a time stamp or something to prevent playback attacks. And that tends to help encryption do better because of the reduced chance of accidentally coming up with a plausible decrypted timestamp value (if the receiver is checking for plausible timestamps). And certainly encryption can be made to work if you are careful. But, when I've looked into this for real systems what I've found is that a MAC is often a better tradeoff for a number of reasons and tends to provide better authentication and integrity for a given computational cost and bandwidth cost in practical scenarios. And, I've found designs in the real world based on encryption that weren't going to work as well as the designers thought because they didn't get the details of authentication right. Also, just to make sure it's said ... a CRC is not cryptographically secure, so don't use it as a secure hash function.

Even after the fine print, the message remains: use a MAC if it does the job. Don't jump to a default strategy of encryption if secrecy isn't what you really need. And if you do decide to use encryption, make sure it is really providing authentication and integrity checking in addition to secrecy.