4 ms·

Hardcoded loop bounds are a requirement for running on hardware that will not be 100% reliable due to operating in the space radiation environment. Paranoid lev

Hardcoded loop bounds are a requirement for running on hardware that will not be 100% reliable due to operating in the space radiation environment. Paranoid levels of defensive programming are a requirement for this regime. I would trust NASA's experience here rather than an armchair expert.

cjbgkagh 2y ago
Don’t they have voting CPUs? If one goes out of sync discard that result and restart it. And wouldn’t the value end up on the CPU the same if it was hardcoded or not? Perhaps there could be some verification done with hardcoded loop bounds for making sure things work in real time. I’ll read the article before commenting further. Edit: Yeah, the hardcoded bounds is to give some sort of guarantee as to how long a function will take.
- mr_toad 2y ago
  I’ve only heard of voting CPUs being used on launchers. I think the level of redundancy on other craft varies.
  - fuzztester 2y ago
    iirc, I read about voting CPUs (like 4 of them) being used on space shuttles or earlier spacecraft. I could be wrong though.
- pauldino 2y ago
  That's not the case for JPL missions (the paper originally is from JPL) which generally have 2 separate independent computers where 1 is active at a time. Since they're independent, the 2 computers don't actually have to run the same software, I believe during Mars entry descent and landing the standby compute element runs a different less sophisticated but easier to validate version of the EDL code to take over if any fault is detected while the primary software is running. (I was going to do a quick check on dataverse.jpl.nasa.gov to confirm that but it seems to be down) Also I think a few years ago on the Mars Curiosity rover (2012) there was some corruption in the flash storage on one of the computers that prevents the full flight software from being loaded on to it, so instead it runs a stripped-down version of the code with very limited functionality to function as a lifeboat in case the fully-working computer ever fails. https://ieeexplore.ieee.org/document/9843266 https://ieeexplore.ieee.org/document/9843266
AnimalMuppet 2y ago
I think radiation unreliability is orthogonal to fixed upper bounds. Radiation is as likely to flip a bit in the check of the upper bound as anywhere else. Having that upper bound hardcoded won't protect against that at all, as far as I can see.
- kevin_thibedeau 2y ago
  It will ensure a more rapid recovery to a safe state. This is why in principle you don't check for loop termination with "==" when ">=" or <=" will better protect against a corrupted loop counter.
  - AnimalMuppet 2y ago
    On such a system, would the code execute out of ROM? Or would the ROM image be loaded into RAM? If the latter, then radiation could flip a bit in the code that represents the upper limit of the loop. Still, if you're going to use words like "better protect" instead of "protect", I'm not sure I can say you're wrong...
    - kevin_thibedeau 2y ago
      RAM and ROM can be nominally protected with ECC, which many rad hard processors provide. It's the internal state of the processor (registers and control logic) which is not fully protected. The inherent hardening of the process makes faults less likely, but they are still guaranteed to happen. There are design approaches to improve reliability with triplicate flip-flops but you pay a power and area penalty. Higher level redundancies aren't always practical also due to mass and volume constraints. At the end of the day software has to account for running on an unreliable system and minimizing bad stuff happening as much as possible.
dooglius 2y ago
Can you elaborate on the failure mode described here? If we take a model where registers (including PC) or memory can get bit-flipped, it seems like all bets are off.
- kevin_thibedeau 2y ago
  High energy radiation causes single event upsets in digital logic when you get an unlucky hit in the right part of a circuit. When that part is a flip-flop holding state or a bus transmitting data, you get persistent corruption. That can cause any and everything to go awry or it may resolve itself depending on what was hit. Various design approaches are used to address these faults through redundancy mechanisms but it isn't always practical to employ them. For basic software protection you may want to depend on a watchdog timer and filling unused memory with NOP slides to trap the processor until the timer reboots. If you have hardware controlling something more risky like explosive bolts, you may want stronger assurances that the hardware won't fail by adding lower level redundancies.
- AlotOfReading 2y ago
  This is actually a pretty common part of the threat model for high integrity computing (e.g. the ECU in your car and airplane avionics). Part of the standard solution is to run processors in lockstep and throw errors if any part of the cpu state diverges between the cores.
olalonde 2y ago
Space radiation and hardware reliability are not the given reason for the upper-bound. From the NASA document: > Rule: All loops must have a fixed upper-bound. It must be trivially possible for a checking tool to prove statically that a preset upper-bound on the number of iterations of a loop cannot be exceeded. If the loop-bound cannot be proven statically, the rule is considered violated. > Rationale: The absence of recursion and the presence of loop bounds prevents runaway code. This rule does not, of course, apply to iterations that are meant to be non-terminating (e.g., in a process scheduler). In those special cases, the reverse rule is applied: it should be statically provable that the iteration cannot terminate. One way to support the rule is to add an explicit upper-bound to all loops that have a variable number of iterations (e.g., code that traverses a linked list). When the upper-bound is exceeded an assertion failure is triggered, and the function containing the failing iteration returns an error. (See Rule 5 about the use of assertions.)

cjbgkagh 2y ago

Don’t they have voting CPUs? If one goes out of sync discard that result and restart it. And wouldn’t the value end up on the CPU the same if it was hardcoded or not? Perhaps there could be some verification done with hardcoded loop bounds for making sure things work in real time. I’ll read the article before commenting further. Edit: Yeah, the hardcoded bounds is to give some sort of guarantee as to how long a function will take.

mr_toad 2y ago
I’ve only heard of voting CPUs being used on launchers. I think the level of redundancy on other craft varies.
- fuzztester 2y ago
  iirc, I read about voting CPUs (like 4 of them) being used on space shuttles or earlier spacecraft. I could be wrong though.
pauldino 2y ago
That's not the case for JPL missions (the paper originally is from JPL) which generally have 2 separate independent computers where 1 is active at a time. Since they're independent, the 2 computers don't actually have to run the same software, I believe during Mars entry descent and landing the standby compute element runs a different less sophisticated but easier to validate version of the EDL code to take over if any fault is detected while the primary software is running. (I was going to do a quick check on dataverse.jpl.nasa.gov to confirm that but it seems to be down) Also I think a few years ago on the Mars Curiosity rover (2012) there was some corruption in the flash storage on one of the computers that prevents the full flight software from being loaded on to it, so instead it runs a stripped-down version of the code with very limited functionality to function as a lifeboat in case the fully-working computer ever fails. https://ieeexplore.ieee.org/document/9843266 https://ieeexplore.ieee.org/document/9843266

AnimalMuppet 2y ago

I think radiation unreliability is orthogonal to fixed upper bounds. Radiation is as likely to flip a bit in the check of the upper bound as anywhere else. Having that upper bound hardcoded won't protect against that at all, as far as I can see.

kevin_thibedeau 2y ago
It will ensure a more rapid recovery to a safe state. This is why in principle you don't check for loop termination with "==" when ">=" or <=" will better protect against a corrupted loop counter.
- AnimalMuppet 2y ago
  On such a system, would the code execute out of ROM? Or would the ROM image be loaded into RAM? If the latter, then radiation could flip a bit in the code that represents the upper limit of the loop. Still, if you're going to use words like "better protect" instead of "protect", I'm not sure I can say you're wrong...
  - kevin_thibedeau 2y ago
    RAM and ROM can be nominally protected with ECC, which many rad hard processors provide. It's the internal state of the processor (registers and control logic) which is not fully protected. The inherent hardening of the process makes faults less likely, but they are still guaranteed to happen. There are design approaches to improve reliability with triplicate flip-flops but you pay a power and area penalty. Higher level redundancies aren't always practical also due to mass and volume constraints. At the end of the day software has to account for running on an unreliable system and minimizing bad stuff happening as much as possible.

dooglius 2y ago

Can you elaborate on the failure mode described here? If we take a model where registers (including PC) or memory can get bit-flipped, it seems like all bets are off.

kevin_thibedeau 2y ago
High energy radiation causes single event upsets in digital logic when you get an unlucky hit in the right part of a circuit. When that part is a flip-flop holding state or a bus transmitting data, you get persistent corruption. That can cause any and everything to go awry or it may resolve itself depending on what was hit. Various design approaches are used to address these faults through redundancy mechanisms but it isn't always practical to employ them. For basic software protection you may want to depend on a watchdog timer and filling unused memory with NOP slides to trap the processor until the timer reboots. If you have hardware controlling something more risky like explosive bolts, you may want stronger assurances that the hardware won't fail by adding lower level redundancies.
AlotOfReading 2y ago
This is actually a pretty common part of the threat model for high integrity computing (e.g. the ECU in your car and airplane avionics). Part of the standard solution is to run processors in lockstep and throw errors if any part of the cpu state diverges between the cores.

olalonde 2y ago

Space radiation and hardware reliability are not the given reason for the upper-bound. From the NASA document: > Rule: All loops must have a fixed upper-bound. It must be trivially possible for a checking tool to prove statically that a preset upper-bound on the number of iterations of a loop cannot be exceeded. If the loop-bound cannot be proven statically, the rule is considered violated. > Rationale: The absence of recursion and the presence of loop bounds prevents runaway code. This rule does not, of course, apply to iterations that are meant to be non-terminating (e.g., in a process scheduler). In those special cases, the reverse rule is applied: it should be statically provable that the iteration cannot terminate. One way to support the rule is to add an explicit upper-bound to all loops that have a variable number of iterations (e.g., code that traverses a linked list). When the upper-bound is exceeded an assertion failure is triggered, and the function containing the failing iteration returns an error. (See Rule 5 about the use of assertions.)