Вопрос: Компиляция приложения для использования в сильно радиоактивных средах


Мы собираем встроенное приложение C / C ++, которое развертывается в экранированном устройстве в среде, обстрелянной с помощью ионизирующего излучения , Мы используем GCC и кросс-компиляцию для ARM. При развертывании наше приложение генерирует некоторые ошибочные данные и вылетает чаще, чем хотелось бы. Аппаратное обеспечение предназначено для этой среды, и наше приложение работает на этой платформе в течение нескольких лет.

Могут ли быть внесены изменения в наш код или улучшения времени компиляции, которые могут быть сделаны для идентификации / исправления мягкие ошибки и повреждение памяти, вызванное разовые события ? У других разработчиков был успех в снижении вредных последствий мягких ошибок в долгосрочном приложении?


1264


источник


Ответы:


Работает около 4-5 лет с разработкой программного обеспечения и прошивки и тестированием среды миниатюризированные спутники *, Я хотел бы поделиться своим опытом здесь.

* ( миниатюризированные спутники намного более склонны к разовым расстройствам событий, чем более крупные спутники из-за относительно небольших ограниченных размеров для своих электронных компонентов )

Быть предельно кратким и прямым: нет механизма для восстановления обнаруживаемый, ошибочный   ситуация самим программным обеспечением / прошивкой без , хотя бы один копия из минимальная рабочая версия программного обеспечения / прошивки где-то для восстановление цели - и с аппаратное обеспечение, поддерживающее восстановление (Функциональные).

Теперь эту ситуацию обычно обрабатывают как на аппаратном, так и на программном уровне. Здесь, по вашему запросу, я расскажу, что мы можем сделать на уровне программного обеспечения.

  1. ... цель восстановления ... , Предоставляйте возможность обновлять / перекомпилировать / перепрограммировать ваше программное обеспечение / прошивку в реальной среде. Это почти обязательно для любого программного обеспечения / прошивки в сильно ионизированной среде. Без этого вы мог имеют избыточное программное обеспечение / аппаратное обеспечение столько, сколько хотите, но в какой-то момент они все взорвутся. Итак, подготовьте эту функцию!

  2. ... минимальная рабочая версия ... Имейте отзывчивые, множественные копии, минимальную версию программного обеспечения / прошивки в вашем коде. Это похоже на безопасный режим в Windows. Вместо того, чтобы иметь только одну, полностью функциональную версию вашего программного обеспечения, есть несколько копий минимальной версии вашего программного обеспечения / прошивки. Минимальная копия обычно имеет гораздо меньший размер, чем полная копия, и почти всегда имеет только следующие две или три функции:

    1. способный слушать команду из внешней системы,
    2. способный обновлять текущее программное обеспечение / прошивку,
    3. способный контролировать данные по хозяйственной деятельности базовой операции.
  3. ... копировать ... где-то ... У вас есть избыточное программное обеспечение / прошивка.

    1. Вы могли бы или без избыточного оборудования, попробуйте иметь избыточное программное обеспечение / прошивку в вашем ARM uC. Обычно это делается при наличии двух или более идентичных программ / прошивок в отдельных адресах которые посылают сердцебиение друг другу, но только один будет активен одновременно. Если известно, что одно или несколько программных / прошивок не реагируют, переключитесь на другое программное обеспечение / прошивку. Преимущество использования этого подхода заключается в том, что мы можем иметь функциональную замену сразу после возникновения ошибки - без какого-либо контакта с какой-либо внешней системой / стороной, которая несет ответственность за обнаружение и исправление ошибки (в случае с сателлитом обычно используется Центр управления полетами ( MCC)).

      Строго говоря, без избыточного оборудования недостатком этого является то, что вы на самом деле не могу Устранить все единственная точка сбоев. По крайней мере, у вас все еще будет один единственная точка отказа, которая сам переключатель (или часто это начало кода). Тем не менее, для устройства, ограниченного размером в сильно ионизированной среде (например, спутники pico / femto), уменьшение единственной точки отказа до одной точки без дополнительное оборудование все равно стоит рассмотреть. Возможно, часть кода для переключения, безусловно, будет намного меньше, чем код для всей программы, что значительно снижает риск получения в нем Single Event.

    2. Но если вы этого не делаете, у вас должна быть хотя бы одна копия в вашей внешней системе, которая может соприкасаться с устройством и обновить программное обеспечение / прошивку (в случае с сателлитом, это снова центр управления полетами).

    3. Вы также можете иметь копию в своем постоянном хранилище на вашем устройстве, которое может быть запущено для восстановления программного обеспечения / прошивки операционной системы
  4. ... обнаружимая ошибочная ситуация .. Ошибка должна быть обнаруживаемый , обычно с помощью аппаратного обеспечения схема коррекции ошибок / обнаружения или небольшим фрагментом кода для исправления / обнаружения ошибок. Лучше всего поставить такой код как маленький, многократный и независимый от основного программного обеспечения / прошивки. Его главная задача - только для проверки / исправления. Если аппаратная схема / прошивка надежный (например, это больше радиации, более жесткой, чем остатки) или с несколькими схемами / логикой, то вы можете подумать об исправлении ошибок. Но если это не так, лучше сделать это как обнаружение ошибок. Поправкой может быть внешняя система / устройство. Для исправления ошибок вы можете рассмотреть возможность использования базового алгоритма коррекции ошибок, такого как Hamming / Golay23, потому что они могут быть проще реализованы как в схеме / программном обеспечении. Но это в конечном счете зависит от возможностей вашей команды. Для обнаружения ошибок обычно используется CRC.

  5. ... аппаратное обеспечение, поддерживающее восстановление Теперь дело доходит до самого сложного аспекта в этом вопросе. В конечном счете, для восстановления требуется оборудование, которое отвечает за восстановление как минимум функциональны. Если аппаратное обеспечение постоянно повреждено (обычно это происходит после Общая ионизирующая доза достигает определенного уровня), тогда (к сожалению) нет способа помочь программному обеспечению в восстановлении. Таким образом, аппаратное обеспечение по праву имеет первостепенное значение для устройства, подверженного воздействию высокого уровня излучения (такого как спутник).

В дополнение к предложению выше, предсказывая ошибку прошивки из-за разоблачения одного события, я также хотел бы предложить вам:

  1. Алгоритм обнаружения ошибок и / или исправления ошибок в протоколе связи между подсистемой. Это еще один вопрос, который должен быть необходим, чтобы избежать неполных / неправильных сигналов, полученных от другой системы

  2. Фильтр в вашем считывании АЦП. Делать не используйте прямое считывание АЦП. Отфильтруйте его средним фильтром, средним фильтром или любыми другими фильтрами - никогда значение доверия доверия. Образец больше, не менее - разумно.


725



НАСА статья об радиационно-упрочненной программного обеспечения. Он описывает три основные задачи:

  1. Регулярный мониторинг памяти для ошибок, а затем очистка этих ошибок,
  2. надежные механизмы восстановления ошибок и
  3. возможность перенастроить, если что-то больше не работает.

Обратите внимание, что скорость сканирования памяти должна быть достаточно частым, чтобы ошибки с несколькими битами редко возникали, так как большинство ECC память может восстанавливаться из однобитовых ошибок, а не из нескольких битовых ошибок.

Надежное восстановление ошибок включает в себя передачу потока управления (как правило, перезапуск процесса в точке до ошибки), выпуск ресурсов и восстановление данных.

Их основная рекомендация по восстановлению данных состоит в том, чтобы избежать необходимости в нем, поскольку промежуточные данные обрабатываются как временные, так что перезапуск перед ошибкой также возвращает данные в надежное состояние. Это похоже на концепцию «транзакций» в базах данных.

Они обсуждают методы, особенно подходящие для объектно-ориентированных языков, таких как C ++. Например

  1. Программные ECC для смежных объектов памяти
  2. Программирование по контракту : проверка предварительных условий и постусловий, а затем проверка объекта, чтобы проверить, что он все еще находится в допустимом состоянии.

367



Вот некоторые мысли и идеи:

Используйте ПЗУ более творчески.

Храните все, что вы можете в ПЗУ. Вместо того, чтобы вычислять вещи, храните поисковые таблицы в ПЗУ. (Убедитесь, что ваш компилятор выводит ваши поисковые таблицы в раздел только для чтения! Распечатайте адреса памяти во время выполнения, чтобы проверить!) Сохраните таблицу векторов прерываний в ПЗУ. Разумеется, запустите несколько тестов, чтобы узнать, насколько надежный ваш ПЗУ сравнивается с вашей оперативной памятью.

Используйте свою лучшую RAM для стека.

SEU в стеке, вероятно, являются наиболее вероятным источником сбоев, потому что там обычно живут такие вещи, как индексные переменные, статусные переменные, обратные адреса и указатели разного рода.

Реализовать таймер-таймер и контрольные таймеры.

Вы можете запустить подпрограмму «проверка работоспособности» каждый таймер, а также процедуру сторожевого таймера для блокировки системы. Ваш основной код также может периодически увеличивать счетчик, указывая на прогресс, и процедура проверки работоспособности может гарантировать, что это произошло.

Воплощать в жизнь исправляющих ошибки-коды в программном обеспечении.

Вы можете добавить избыточность в свои данные, чтобы иметь возможность обнаруживать и / или исправлять ошибки. Это добавит время обработки, что потенциально приведет к тому, что процессор будет подвергаться воздействию излучения в течение более длительного времени, что увеличит вероятность ошибок, поэтому вы должны учитывать компромисс.

Помните тайники.

Проверьте размеры кэшей процессора. Данные, которые вы недавно получили или изменили, вероятно, находятся в кеше. Я считаю, что вы можете отключить хотя бы некоторые из кэшей (при большой производительности); вы должны попробовать это, чтобы понять, насколько уязвимы кэши для SEU. Если кеши более жесткие, чем оперативная память, вы можете регулярно читать и переписывать критические данные, чтобы убедиться, что он остается в кеше и возвращает RAM обратно в линию.

Используйте обработчики ошибок страниц.

Если вы помечаете страницу памяти как не существующую, то при попытке доступа к ней CPU выдает ошибку страницы. Вы можете создать обработчик ошибок страницы, который выполняет некоторую проверку перед обслуживанием запроса на чтение. (Операционные системы для ПК используют это для прозрачной загрузки страниц, которые были заменены на диск.)

Используйте язык ассемблера для критических вещей (это может быть все).

С ассемблером вы знать что находится в регистрах и что находится в ОЗУ; вы знать какие специальные таблицы оперативной памяти использует процессор, и вы можете проектировать вещи окольными способами, чтобы снизить риск.

использование objdumpна самом деле посмотреть на сгенерированный язык ассемблера и определить, какой код выполняет каждый из ваших подпрограмм.

Если вы используете большую ОС, такую ​​как Linux, то вы просите о неприятностях; есть так много сложности и так много вещей, чтобы пойти не так.

Помните, что это игра вероятностей.

Один комментатор сказал

Каждая рутина, которую вы пишете, чтобы ловить ошибки, будет подвержена самому отказу от одной и той же причины.

Хотя это верно, вероятность ошибок в (скажем) 100 байт кода и данных, необходимых для правильной работы проверки, намного меньше, чем вероятность ошибок в других местах. Если ваш ПЗУ достаточно надежный, и почти весь код / ​​данные на самом деле находятся в ПЗУ, ваши шансы еще лучше.

Используйте избыточное оборудование.

Используйте 2 или более идентичные аппаратные настройки с идентичным кодом. Если результаты отличаются друг от друга, необходимо выполнить сброс. С 3 или более устройствами вы можете использовать систему «голосования», чтобы попытаться определить, какой из них был взломан.


106



You may also be interested in the rich literature on the subject of algorithmic fault tolerance. This includes the old assignment: Write a sort that correctly sorts its input when a constant number of comparisons will fail (or, the slightly more evil version, when the asymptotic number of failed comparisons scales as log(n) for n comparisons).

A place to start reading is Huang and Abraham's 1984 paper "Algorithm-Based Fault Tolerance for Matrix Operations". Their idea is vaguely similar to homomorphic encrypted computation (but it is not really the same, since they are attempting error detection/correction at the operation level).

A more recent descendant of that paper is Bosilca, Delmas, Dongarra, and Langou's "Algorithm-based fault tolerance applied to high performance computing".


93



Writing code for radioactive environments is not really any different than writing code for any mission-critical application.

In addition to what has already been mentioned, here are some miscellaneous tips:

  • Use everyday "bread & butter" safety measures that should be present on any semi-professional embedded system: internal watchdog, internal low-voltage detect, internal clock monitor. These things shouldn't even need to be mentioned in the year 2016 and they are standard on pretty much every modern microcontroller.
  • If you have a safety and/or automotive-oriented MCU, it will have certain watchdog features, such as a given time window, inside which you need to refresh the watchdog. This is preferred if you have a mission-critical real-time system.
  • In general, use a MCU suitable for these kind of systems, and not some generic mainstream fluff you received in a packet of corn flakes. Almost every MCU manufacturer nowadays have specialized MCUs designed for safety applications (TI, Freescale, Renesas, ST, Infineon etc etc). These have lots of built-in safety features, including lock-step cores: meaning that there are 2 CPU cores executing the same code, and they must agree with each other.
  • IMPORTANT: You must ensure the integrity of internal MCU registers. All control & status registers of hardware peripherals that are writeable may be located in RAM memory, and are therefore vulnerable.

    To protect yourself against register corruptions, preferably pick a microcontroller with built-in "write-once" features of registers. In addition, you need to store default values of all hardware registers in NVM and copy-down those values to your registers at regular intervals. You can ensure the integrity of important variables in the same manner.

    Note: always use defensive programming. Meaning that you have to setup all registers in the MCU and not just the ones used by the application. You don't want some random hardware peripheral to suddenly wake up.

  • There are all kinds of methods to check for errors in RAM or NVM: checksums, "walking patterns", software ECC etc etc. The best solution nowadays is to not use any of these, but to use a MCU with built-in ECC and similar checks. Because doing this in software is complex, and the error check in itself could therefore introduce bugs and unexpected problems.

  • Use redundancy. You could store both volatile and non-volatile memory in two identical "mirror" segments, that must always be equivalent. Each segment could have a CRC checksum attached.
  • Avoid using external memories outside the MCU.
  • Implement a default interrupt service routine / default exception handler for all possible interrupts/exceptions. Even the ones you are not using. The default routine should do nothing except shutting off its own interrupt source.
  • Understand and embrace the concept of defensive programming. This means that your program needs to handle all possible cases, even those that cannot occur in theory. Examples.

    High quality mission-critical firmware detects as many errors as possible, and then ignores them in a safe manner.

  • Never write programs that rely on poorly-specified behavior. It is likely that such behavior might change drastically with unexpected hardware changes caused by radiation or EMI. The best way to ensure that your program is free from such crap is to use a coding standard like MISRA, together with a static analyser tool. This will also help with defensive programming and with weeding out bugs (why would you not want to detect bugs in any kind of application?).
  • IMPORTANT: Don't implement any reliance of the default values of static storage duration variables. That is, don't trust the default contents of the .data or .bss. There could be any amount of time between the point of initialization to the point where the variable is actually used, there could have been plenty of time for the RAM to get corrupted. Instead, write the program so that all such variables are set from NVM in run-time, just before the time when such a variable is used for the first time.

    In practice this means that if a variable is declared at file scope or as static, you should never use = to initialize it (or you could, but it is pointless, because you cannot rely on the value anyhow). Always set it in run-time, just before use. If it is possible to repeatedly update such variables from NVM, then do so.

    Similarly in C++, don't rely on constructors for static storage duration variables. Have the constructor(s) call a public "set-up" routine, which you can also call later on in run-time, straight from the caller application.

    If possible, remove the "copy-down" start-up code that initializes .data and .bss (and calls C++ constructors) entirely, so that you get linker errors if you write code relying on such. Many compilers have the option to skip this, usually called "minimal/fast start-up" or similar.

    This means that any external libraries have to be checked so that they don't contain any such reliance.

  • Implement and define a safe state for the program, to where you will revert in case of critical errors.

  • Implementing an error report/error log system is always helpful.

36



It may be possible to use C to write programs that behave robustly in such environments, but only if most forms of compiler optimization are disabled. Optimizing compilers are designed to replace many seemingly-redundant coding patterns with "more efficient" ones, and may have no clue that the reason the programmer is testing x==42 when the compiler knows there's no way x could possibly hold anything else is because the programmer wants to prevent the execution of certain code with x holding some other value--even in cases where the only way it could hold that value would be if the system received some kind of electrical glitch.

Declaring variables as volatile is often helpful, but may not be a panacea. Of particular importance, note that safe coding often requires that dangerous operations have hardware interlocks that require multiple steps to activate, and that code be written using the pattern:

... code that checks system state
if (system_state_favors_activation)
{
  prepare_for_activation();
  ... code that checks system state again
  if (system_state_is_valid)
  {
    if (system_state_favors_activation)
      trigger_activation();
  }
  else
    perform_safety_shutdown_and_restart();
}
cancel_preparations();

If a compiler translates the code in relatively literal fashion, and if all the checks for system state are repeated after the prepare_for_activation(), the system may be robust against almost any plausible single glitch event, even those which would arbitrarily corrupt the program counter and stack. If a glitch occurs just after a call to prepare_for_activation(), that would imply that activation would have been appropriate (since there's no other reason prepare_for_activation() would have been called before the glitch). If the glitch causes code to reach prepare_for_activation() inappropriately, but there are no subsequent glitch events, there would be no way for code to subsequently reach trigger_activation() without having passed through the validation check or calling cancel_preparations first [if the stack glitches, execution might proceed to a spot just before trigger_activation() after the context that called prepare_for_activation() returns, but the call to cancel_preparations() would have occurred between the calls to prepare_for_activation() and trigger_activation(), thus rendering the latter call harmless.

Such code may be safe in traditional C, but not with modern C compilers. Such compilers can be very dangerous in that sort of environment because aggressive they strive to only include code which will be relevant in situations that could come about via some well-defined mechanism and whose resulting consequences would also be well defined. Code whose purpose would be to detect and clean up after failures may, in some cases, end up making things worse. If the compiler determines that the attempted recovery would in some cases invoke undefined behavior, it may infer that the conditions that would necessitate such recovery in such cases cannot possibly occur, thus eliminating the code that would have checked for them.


30



This is an extremely broad subject. Basically, you can't really recover from memory corruption, but you can at least try to fail promptly. Here are a few techniques you could use:

  • checksum constant data. If you have any configuration data which stays constant for a long time (including hardware registers you have configured), compute its checksum on initialization and verify it periodically. When you see a mismatch, it's time to re-initialize or reset.

  • store variables with redundancy. If you have an important variable x, write its value in x1, x2 and x3 and read it as (x1 == x2) ? x2 : x3.

  • implement program flow monitoring. XOR a global flag with a unique value in important functions/branches called from the main loop. Running the program in a radiation-free environment with near-100% test coverage should give you the list of acceptable values of the flag at the end of the cycle. Reset if you see deviations.

  • monitor the stack pointer. In the beginning of the main loop, compare the stack pointer with its expected value. Reset on deviation.


27



What could help you is a watchdog. Watchdogs were used extensively in industrial computing in the 1980s. Hardware failures were much more common then - another answer also refers to that period.

A watchdog is a combined hardware/software feature. The hardware is a simple counter that counts down from a number (say 1023) to zero. TTL or other logic could be used.

The software has been designed as such that one routine monitors the correct operation of all essential systems. If this routine completes correctly = finds the computer running fine, it sets the counter back to 1023.

The overall design is so that under normal circumstances, the software prevents that the hardware counter will reach zero. In case the counter reaches zero, the hardware of the counter performs its one-and-only task and resets the entire system. From a counter perspective, zero equals 1024 and the counter continues counting down again.

This watchdog ensures that the attached computer is restarted in a many, many cases of failure. I must admit that I'm not familiar with hardware that is able to perform such a function on today's computers. Interfaces to external hardware are now a lot more complex than they used to be.

An inherent disadvantage of the watchdog is that the system is not available from the time it fails until the watchdog counter reaches zero + reboot time. While that time is generally much shorter than any external or human intervention, the supported equipment will need to be able to proceed without computer control for that timeframe.


26



This answer assumes you are concerned with having a system that works correctly, over and above having a system that is minimum cost or fast; most people playing with radioactive things value correctness / safety over speed / cost

Several people have suggested hardware changes you can make (fine - there's lots of good stuff here in answers already and I don't intend repeating all of it), and others have suggested redundancy (great in principle), but I don't think anyone has suggested how that redundancy might work in practice. How do you fail over? How do you know when something has 'gone wrong'? Many technologies work on the basis everything will work, and failure is thus a tricky thing to deal with. However, some distributed computing technologies designed for scale expect failure (after all with enough scale, failure of one node of many is inevitable with any MTBF for a single node); you can harness this for your environment.

Here are some ideas:

  • Ensure that your entire hardware is replicated n times (where n is greater than 2, and preferably odd), and that each hardware element can communicate with each other hardware element. Ethernet is one obvious way to do that, but there are many other far simpler routes that would give better protection (e.g. CAN). Minimise common components (even power supplies). This may mean sampling ADC inputs in multiple places for instance.

  • Ensure your application state is in a single place, e.g. in a finite state machine. This can be entirely RAM based, though does not preclude stable storage. It will thus be stored in several place.

  • Adopt a quorum protocol for changes of state. See RAFT for example. As you are working in C++, there are well known libraries for this. Changes to the FSM would only get made when a majority of nodes agree. Use a known good library for the protocol stack and the quorum protocol rather than rolling one yourself, or all your good work on redundancy will be wasted when the quorum protocol hangs up.

  • Ensure you checksum (e.g. CRC/SHA) your FSM, and store the CRC/SHA in the FSM itself (as well as transmitting in the message, and checksumming the messages themselves). Get the nodes to check their FSM regularly against these checksum, checksum incoming messages, and check their checksum matches the checksum of the quorum.

  • Build as many other internal checks into your system as possible, making nodes that detect their own failure reboot (this is better than carrying on half working provided you have enough nodes). Attempt to let them cleanly remove themselves from the quorum during rebooting in case they don't come up again. On reboot have them checksum the software image (and anything else they load) and do a full RAM test before reintroducing themselves to the quorum.

  • Use hardware to support you, but do so carefully. You can get ECC RAM, for instance, and regularly read/write through it to correct ECC errors (and panic if the error is uncorrectable). However (from memory) static RAM is far more tolerant of ionizing radiation than DRAM is in the first place, so it may be better to use static DRAM instead. See the first point under 'things I would not do' as well.

Let's say you have an 1% chance of failure of any given node within one day, and let's pretend you can make failures entirely independent. With 5 nodes, you'll need three to fail within one day, which is a .00001% chance. With more, well, you get the idea.

Things I would not do:

  • Underestimate the value of not having the problem to start off with. Unless weight is a concern, a large block of metal around your device is going to be a far cheaper and more reliable solution than a team of programmers can come up with. Ditto optical coupling of inputs of EMI is an issue, etc. Whatever, attempt when sourcing your components to source those rated best against ionizing radiation.

  • Roll your own algorithms. People have done this stuff before. Use their work. Fault tolerance and distributed algorithms are hard. Use other people's work where possible.

  • Use complicated compiler settings in the naive hope you detect more failures. If you are lucky, you may detect more failures. More likely, you will use a code-path within the compiler which has been less tested, particularly if you rolled it yourself.

  • Use techniques which are untested in your environment. Most people writing high availability software have to simulate failure modes to check their HA works correctly, and miss many failure modes as a result. You are in the 'fortunate' position of having frequent failures on demand. So test each technique, and ensure its application actual improves MTBF by an amount that exceeds the complexity to introduce it (with complexity comes bugs). Especially apply this to my advice re quorum algorithms etc.


22



Since you specifically ask for software solutions, and you are using C++, why not use operator overloading to make your own, safe datatypes? For example:

Instead of using uint32_t (and double, int64_t etc), make your own SAFE_uint32_t which contains a multiple (minimum of 3) of uint32_t. Overload all of the operations you want (* + - / << >> = == != etc) to perform, and make the overloaded operations perform independently on each internal value, ie don't do it once and copy the result. Both before and after, check that all of the internal values match. If values don't match, you can update the wrong one to the value with the most common one. If there is no most-common value, you can safely notify that there is an error.

This way it doesn't matter if corruption occurs in the ALU, registers, RAM, or on a bus, you will still have multiple attempts and a very good chance of catching errors. Note however though that this only works for the variables you can replace - your stack pointer for example will still be susceptible.

A side story: I ran into a similar issue, also on an old ARM chip. It turned out to be a toolchain which used an old version of GCC that, together with the specific chip we used, triggered a bug in certain edge cases that would (sometimes) corrupt values being passed into functions. Make sure your device doesn't have any problems before blaming it on radio-activity, and yes, sometimes it is a compiler bug =)


21



Disclaimer: I'm not a radioactivity professional nor worked for this kind of application. But I worked on soft errors and redundancy for long term archival of critical data, which is somewhat linked (same problem, different goals).

The main problem with radioactivity in my opinion is that radioactivity can switch bits, thus radioactivity can/will tamper any digital memory. These errors are usually called soft errors, bit rot, etc.

The question is then: how to compute reliably when your memory is unreliable?

To significantly reduce the rate of soft errors (at the expense of computational overhead since it will mostly be software-based solutions), you can either:

  • rely on the good old redundancy scheme, and more specifically the more efficient error correcting codes (same purpose, but cleverer algorithms so that you can recover more bits with less redundancy). This is sometimes (wrongly) also called checksumming. With this kind of solution, you will have to store the full state of your program at any moment in a master variable/class (or a struct?), compute an ECC, and check that the ECC is correct before doing anything, and if not, repair the fields. This solution however does not guarantee that your software can work (simply that it will work correctly when it can, or stops working if not, because ECC can tell you if something is wrong, and in this case you can stop your software so that you don't get fake results).

  • or you can use resilient algorithmic data structures, which guarantee, up to a some bound, that your program will still give correct results even in the presence of soft errors. These algorithms can be seen as a mix of common algorithmic structures with ECC schemes natively mixed in, but this is much more resilient than that, because the resiliency scheme is tightly bounded to the structure, so that you don't need to encode additional procedures to check the ECC, and usually they are a lot faster. These structures provide a way to ensure that your program will work under any condition, up to the theoretical bound of soft errors. You can also mix these resilient structures with the redundancy/ECC scheme for additional security (or encode your most important data structures as resilient, and the rest, the expendable data that you can recompute from the main data structures, as normal data structures with a bit of ECC or a parity check which is very fast to compute).

If you are interested in resilient data structures (which is a recent, but exciting, new field in algorithmics and redundancy engineering), I advise you to read the following documents:

  • Resilient algorithms data structures intro by Giuseppe F.Italiano, Universita di Roma "Tor Vergata"

  • Christiano, P., Demaine, E. D., & Kishore, S. (2011). Lossless fault-tolerant data structures with additive overhead. In Algorithms and Data Structures (pp. 243-254). Springer Berlin Heidelberg.

  • Ferraro-Petrillo, U., Grandoni, F., & Italiano, G. F. (2013). Data structures resilient to memory faults: an experimental study of dictionaries. Journal of Experimental Algorithmics (JEA), 18, 1-6.

  • Italiano, G. F. (2010). Resilient algorithms and data structures. In Algorithms and Complexity (pp. 13-24). Springer Berlin Heidelberg.

If you are interested in knowing more about the field of resilient data structures, you can checkout the works of Giuseppe F. Italiano (and work your way through the refs) and the Faulty-RAM model (introduced in Finocchi et al. 2005; Finocchi and Italiano 2008).

/EDIT: I illustrated the prevention/recovery from soft-errors mainly for RAM memory and data storage, but I didn't talk about computation (CPU) errors. Other answers already pointed at using atomic transactions like in databases, so I will propose another, simpler scheme: redundancy and majority vote.

The idea is that you simply do x times the same computation for each computation you need to do, and store the result in x different variables (with x >= 3). You can then compare your x variables:

  • if they all agree, then there's no computation error at all.
  • if they disagree, then you can use a majority vote to get the correct value, and since this means the computation was partially corrupted, you can also trigger a system/program state scan to check that the rest is ok.
  • if the majority vote cannot determine a winner (all x values are different), then it's a perfect signal for you to trigger the failsafe procedure (reboot, raise an alert to user, etc.).

This redundancy scheme is very fast compared to ECC (practically O(1)) and it provides you with a clear signal when you need to failsafe. The majority vote is also (almost) guaranteed to never produce corrupted output and also to recover from minor computation errors, because the probability that x computations give the same output is infinitesimal (because there is a huge amount of possible outputs, it's almost impossible to randomly get 3 times the same, even less chances if x > 3).

So with majority vote you are safe from corrupted output, and with redundancy x == 3, you can recover 1 error (with x == 4 it will be 2 errors recoverable, etc. -- the exact equation is nb_error_recoverable == (x-2) where x is the number of calculation repetitions because you need at least 2 agreeing calculations to recover using the majority vote).

The drawback is that you need to compute x times instead of once, so you have an additional computation cost, but's linear complexity so asymptotically you don't lose much for the benefits you gain. A fast way to do a majority vote is to compute the mode on an array, but you can also use a median filter.

Also, if you want to make extra sure the calculations are conducted correctly, if you can make your own hardware you can construct your device with x CPUs, and wire the system so that calculations are automatically duplicated across the x CPUs with a majority vote done mechanically at the end (using AND/OR gates for example). This is often implemented in airplanes and mission-critical devices (see triple modular redundancy). This way, you would not have any computational overhead (since the additional calculations will be done in parallel), and you have another layer of protection from soft errors (since the calculation duplication and majority vote will be managed directly by the hardware and not by software -- which can more easily get corrupted since a program is simply bits stored in memory...).


16