Hacker News Reader

Comment by waterlesscloud | Hacker News Reader

I was reading up on the Primary Flight Computer (PFC) of the 777, just out of curiosity.

It's a triple redundant system, that is there's 3 separate PFC systems. That's not too surprising.

What did surprise me was that each of the 3 PFCs has 3 channels, and each channel is a CPU from a different manufacturer (AMD, Motorola, Intel). The reasoning is that any flaw in any particular cpu design would be outvoted by the other two.

They appear to use 3 different compilers for this reason (Ada), one for each processor. Seems like the I/O and endianness of the various chips would add complexity too.

I wonder if the added complexity makes it a net win or loss for safety? I guess a win, since that's what they do.

View on HN

This reminds me of an article I read about the Space Shuttle's flight control system. Five computers on board, with 4 running redundantly and the fifth on backup.

> Q. How are actuators controlled?

> A. For the aerosurface actuators, each of the four computers sends out an independent command on an independent bus. With no failures, the commands should be identical. The voting is done at the actuator using a hydraulic voting mechanism, called a force-fight voter. In it, there are four hydraulic ports called secondary ports, each commanded by one of the four GPCs. The secondary ports go into the primary ports, which are heavy-duty actuators that connect to what's called a "summing bar," which is no more than a massive steel rod. If there are three good computers and one bad one, the three good commands physically out-muscle the fourth. This limits the control authority a little bit--we don't get the total force we'd like to get, but there's still enough power to control the vehicle. If you have a large enough pressure differential for a large enough time, the port is hydraulically bypassed, which relieves the pressure in that one port. The remaining three ports then regain their full authority.

The whole article is worth a read: http://klabs.org/DEI/Processor/shuttle/shuttle_primary_compu...

  Homer: Well, today's the day for Homer J. I know I'm 
         gonna win this time.

  Lenny: Yeah? How come? 

  Homer: Union Rule 26: "Every employee must win Worker of 
         the Week at least once regardless of gross 
         incompetence, obesity or rank odor."

  Mr. Burns: Compadres, it is imperative that we crush the 
             freedom fighters before the start of the rainy 
             season. And remember, a shiny new donkey for 
             whoever brings me the head of Colonel 
             Montoya... Hmm? What? Oh! ...and by that I 
             mean, of course, it's time for the Worker of 
             the Week Award. I can't believe we've 
             overlooked this week's winner for so very, 
             very long. We simply could not function 
             without his tireless efforts. So, a round of 
             applause for this inanimate [steel] rod.

It was a carbon rod. That was the episode where Homer went into space, where another carbon rod became a hero.

http://simpsons.wikia.com/wiki/Inanimate_carbon_rod

Yes, I am aware of that. Hence the brackets.

That "force-fight voter" concept is pretty cool.

This has been normal practice on airline computers for decades. The 757 used dual systems (the third being the pilot). Each channel:

1. used a different CPU architecture and brand 2. used different circuits 3. used different algorithms 4. used different languages 5. were developed by independent teams 6. with a third independent team to verify there were no inadvertent similarities

If the two channels disagreed, they were automatically electrically isolated, and the pilot was notified and was expected to take over.

And this is why the 757 systems failed far too often, because taking N-Modular Redundancy to this level causes a great deal of false positives.

For this reason it was rejected for use on the 777 by the FAA Chief Scientific and Technical Advisor for Flight Controls.

With regard to the 777 Flight Control System Design, "Bob Yeh" released a number of documents on the system.

http://www.citemaster.net/get/1472830e-8785-11e3-9b63-00163e...

I didn't know this. It makes sense, and the reference indicates they did some solid statistical work on the experiences with those methods.

Interesting bit here: There were 20 Freescale Semiconductor engineers on that MH 370 plane. Story is getting interesting by the day.

http://www.reuters.com/article/2014/03/09/us-malaysia-airlin...

>They appear to use 3 different compilers for this reason (Ada)

I understand why Ada is used for safety-critical applications, but I have to wonder: Does the fact that Ada is a relatively old and unfriendly language lead to more bugs than it prevents? My mind would probably go blank if I had to stare at Ada code for 8 hours a day.

What if we used Haskell for all non-realtime safety-critical functionality in aircraft? With a few extra rules to prevent stack overflows, I think I'd trust a million-line Haskell program over a million-line Ada program (although it would probably be more like ten-thousand-line Haskell program vs million-line Ada program).

Ada is proven in this area and generates fast, efficient code that is suitable for embedded systems. Ada's last revision is 2012. What do you find unfriendly?

I would most certainly not trust Haskell over Ada in embedded system work.

>Ada is proven in this area and generates fast, efficient code that is suitable for embedded systems.

So does coding in assembly. The idea is to create fast, efficient code that is also simple and easy to understand.

>I would most certainly not trust Haskell over Ada in embedded system work.

If the system does not have hard realtime requirements and has a decent resources, why wouldn't you trust Haskell?

>> If the system does not have hard realtime requirements and has a decent resources, why wouldn't you trust Haskell?

Because that doesn't describe cars, a jet, space shuttles, or ... well anything I'd trust my life to. Hell, Haas CNCs still run DOS 8.0

Yeah, I would avoid trusting something hard-realtime to a language with lazy evaluation and garbage collection, even if it's quite trustworthy for other purposes.

(IIRC, these programs don't even use malloc, let alone garbage collection :)

MISRA discourages use of malloc (because you can deviate with clear documentation as to why) but it's not at all unheard of. That said, many embedded systems don't come with a usable implementation of malloc so the safe default is to write your own memory manager (safer but not always possible: use a well tested one) that uses static memory pools to allocate dynamic memory.

Any time you're using malloc() you run the risk of running out of memory, which is a very very bad thing for a safety-critical embedded system. Statically allocated, fixed-size things are good, as are algorithms that are designed not to require O(n) space to perform their processing.

There are many safety-critical systems that aren't hard realtime. Radio transponders, human interface systems, life support systems.

In fact, I'd say a great way to do it would be to implement all the hard realtime bits in some low-level, pain-in-the-ass language like Ada and then wrap all that unpleasant stuff in a high-level language that is very unfriendly to implementation bugs (like Haskell).

"There are many safety-critical systems that aren't hard realtime."

I'm not convinced you can make such a clean separation.

>> Radio transponders, human interface systems, life support systems.

Don't think you know what a hard real time system is. Both radio transponders and life support systems have to be hard real time. Motors and antennas don't magically communicate with your userland "apps," they're controlled by precisely timed code. The "human interface systems" (could you have brought to the conversation a more generic term?) to all of these are often, too, hard real time because that's the easiest way to prove something is safe and test the edge cases. For all intents and purposes, anything "soft real time" has a kernel and kernels are monolithic disasters waiting to happen for anyone who needs timing guarantees (hint: if your life depends on it, it needs timing guarantees).

On top of that is the unfriendliness of Haskell to the real world of hiring (and this is Boeing for godzilla's sake) and it's lack of proper testing in such an environment, although I'm sure there are those who use it in embedded.

>Motors and antennas don't magically communicate with your userland "apps," they're controlled by precisely timed code.

Motors and antennas are usually managed by hardware or dedicated uCs, not PFC software. Aircraft aren't running their telemetry off GnuRadio, and aircraft PFCs sure as hell aren't worrying about servo timing.

"Human interface systems" I thought would be self explanatory; pilots don't care if their plane UIs take 5us or 5ms to update. They can't react on those time scales anyway. Hell, you could probably code all the user-facing avionics stuff in Javascript and be fine.

> pilots don't care if their plan UIs take 5us or 5ms to update

Hard real-time doesn't mean "fast", it means having guaranteed upper bounds on response time. In order to get those guarantees, uninteruptable code paths need to be short and critical parts of the systems need to be simple, which often also leads to fast response. However, the difference between soft and hard realtime systems is the guarantees.

A soft real-time system that has a 5ms mean update time but has a 1e-6 chance of taking 10 seconds is much less useful than a hard real-time system that has a 15ms mean update time with a hard upper-bound of 50ms.

Which is why Rust is so interesting. It has deterministic upper bounds on performance. Not many new languages have this feature. Should eventually be useful for real-time systems and game developers.

But based on my meager experience in the language, I disagree that Ada is a massive pain in the ass to program in. It's probably less verbose and friendlier than Java, for example. Certainly easier than programming in C, and much less prone to fatal mistakes.

Do you have any links about the upper bounds of performance in Rust? I have a passive interest in embedded and Rust and that sounds pretty interesting.

> user-facing avionics stuff in Javascript

Please don't give anyone any stupid ideas.

I'm sure someone once made the same comment about Ada when compared to competing languages (C? Assembly?) too ;)

The history of Ada is about these type of systems. Haskell's history and runtime characteristics aren't.

As an aside, I've been playing with learning Ada for a while (and all of the books I have from the last time poked at it are very out of date). Do you happen to know of any good references, online (Better!) or off?

this seems to be a good starting point these days - http://www.adacore.com/adaanswers/resources

I learned with "ADA as a Second Language", but its way out of date and I do believe out of print.

They wouldn't be running Ada 2012 on a 777.

I was just answering that the language is not old. I'm really not sure what they would be running (83 probably, since its first flight was before 95).

I am a big Haskell fan but no, just, no. That would be a terrible idea because of how inherently unpredictable lazy evaluation is. Replace "Haskell" with OCaml or SML though, and I definitely agree.

Also as others have commented there are usually special requirements for embedded systems that may even occasionally require one to drop down to assembly (e.g. to get the code in the right place to execute if you're on bare metal).

What's so great about Haskell? It has no particular safety features compared to other languages, I think.

It won't help with with static analysis of any numeric types (though you can turn bad conversions into type errors, it can't tell if an explicit conversion is right or not) and the timing of anything is really hard to reason out.

>What's so great about Haskell?

The type system.

When I write Haskell programs, I create orders of magnitude fewer bugs than I do when writing programs in other PLs.

The language makes it very hard to screw up implementing an idea.

Haskell forces me to implement things in ways that are both elegant and easy to comprehend. Haskell does not easily admit spaghetti code.

Have you programmed any Ada?

The things that matter in critical embedded systems are typically not captured by type systems: memory boundedness, running time upper bounds, overflows,... For these things even (controlled) C is a better option than Haskell today.

There is enormous tooling and a very good semantics for Ada. Haskell is only somewhat comparable: I've not seen anything like SPARK for Haskell.

You know, there are other languages than Haskell doing interesting things. Ada2012 for example, introduced design by contract with support for formal verification in conforming subprograms. This may be a near term more practical path than dependent types. Highly interesting.

-> http://www.open-do.org/projects/hi-lite/gnatprove/

http://www.open-do.org/wp-content/uploads/2011/12/hi-lite-er...

Golden hammer, meet screw.

This sounds like a gross misunderstanding of the kinds of guarantees made by Haskell's static systems.

The closest you're going to get it something like Atom [0] which is used to program a few different hard realtime systems. If you look at the Atom docs, however, you'll quickly find that programming in Atom is nothing like programming in Haskell---it's merely embedded there. The type system helps to ensure that your embedding does falter, but most of the errors still live in the sublanguage and I'm not sure how far Haskell's type system goes toward reducing those.

[0] http://hackage.haskell.org/package/atom

Avionics software is written in an environment where, _if_ such a problem as a programming language being "old and unfriendly" introduced bugs, that would have been noticed and mitigated.

http://www.fastcompany.com/28121/they-write-right-stuff

> I wonder if the added complexity makes it a net win or loss for safety? I guess a win, since that's what they do.

The chance of one or more of the systems failing actually triples (OR), but the chance of all three failing (AND) decreases, which is what redundancy provides. Basic probability.

Hard to say.

It means that there's an increased chance of bugs overall, yes, but a decreased chance of bugs that affect the overall flight, as it means that many more bugs will be caught and dealt with before they start affecting things majorly.

It doesn't save you from flaws in the design specs, though, or if everyone made the same faulty assumption.

As I've found myself: the best way to test an implementation of a data structure is to compare it against another implementation (preferably the simplest implementation possible - singly linked list, anyone?) and assert that they exhibit identical behavior.

Probably an overall win for safety, redundancy, and (maybe more importantly) security. That said, considering the number of different exploits that have been assembled for large attacks in the past (how many zero-days were in Stuxtnet?), I wouldn't completely rule out the possibility that the flight systems were hacked. This flight may not even have been the primary target, but rather a test of the attack vector, with the attacker finally directing the aircraft out over a big, deep body of water where it would eventually run out of fuel and eliminate most of the evidence.

More components obviously reduce the reliability, but if the likelihood of failure of each of those redundant systems are independent (and to some degree even if they are dependent), at a high-level I believe it's just P(failure of system 1)P(2)P(3), so the likelihood of failure could pretty easily be made infinitesimal. On the other hand, there are lots of plane flights. :-)

Where was you reading this?, I love that type of stuff.

Sounds interesting. Link?

http://www.scribd.com/doc/212547313/Primary-Flight-Computer-...

Reply on news.ycombinator.com