6

Given a requirement like

if A and B and not C then D must happen within 10ms

That can clearly be tested albeit at the cost of some pain proving the 10ms bit, but what happens if the requirement was instead

if and only if A and B and not C then D..... 

It seems to me that the only if likely requires an exhaustive exploration of the programs state space, and that is clearly infeasible given a reasonably large amount of state (And may be the sort of thing that Turing had things to say about). This is very much the kind of condition that applies to such things as firing airbags and other such things concerned with harm mitigation.

Is my suspicion about the difficulty of testing such things correct, and what are the strategies to reduce the size of the state space that must be explored to achieve coverage of such a requirement?

  • Looks good to me! – user1118321 Jun 3 '18 at 19:48
  • 1
    "requires an exhaustive exploration of the programs state space" - why not just the space of states of the few boolean values which are part of the conditional expression? In your example, 3 booleans, so just 8 states. Please clarify. – Doc Brown Jun 3 '18 at 20:02
  • 3
    So 'D' is setting a couple of IO register bits to some state, fairly mundane, but now I need to prove that no other code sets those register bits (Say because I screwed up somewhere and wrote PORTD when I meant PORTC in some completely unrelated code, or because I ran off the end of an array or because I blew the stack space limit). – Dan Mills Jun 3 '18 at 20:19
  • @DanMills: Action D should be designed such that it is nearly impossible to do those steps by accident. Or, if that makes the risk that the result of action D doesn't happen when needed too big, someone needs to accept the risk that action D can happen by accident. There is a trade-off there and will involve both hardware and software in the case of safety-critical embedded systems. – Bart van Ingen Schenau Jun 4 '18 at 10:45
5

Testing that something doesn't happen is generally very difficult. However, testing is not the only available QA technique. Here, combining a convenient architecture with static analysis and some testing may be optimal:

  • abstract over the IO registers so that they are only manipulated through macros, functions, or variables with a few easily distinguishable names.

  • find all places that use the airbag-related registers. If possible, move them into a single source file.

  • Implement a kind of static analysis to ensure that:

    (1) no code accesses the registers without going through the abstraction layer

    (2) no code except for specific files uses the airbag-related registers

    This might be as simple as a shell script that greps all source files for specific pattern, and compares the matching file list:

    #!/bin/sh
    for file in `find src/ include/ \
        -type f \( -name '*.c' -o -name '*.h' \) \
        -exec grep -l 'REG_TRIGGER_AIRBAG' {} +`
    do
      case "$file" in
        include/registers.h) ;;  # ok
        src/airbags.c) ;;  # ok
        *)
          echo "unexpected file is accessing airbag registers: $file"
          exit 1
          ;;
      esac
    done
    
  • Those source files that do use the airbag-related registers, test thoroughly. Consider using white-box techniques to construct a test suite with high coverage. This can be simplified by organizing the code linearly, and expressing the preconditions through guard clauses:

    /* called every 5ms */
    void trigger_airbag_if_necessary(bool A, bool B, bool C) {
      if (!A) return;
      if (!B) return;
      if (C) return;
      SET_REGISTER(REG_TRIGGER_AIRBAG, 1);
    }
    

    If the conditions are linear, it is easier to build a mental model of the conditions leading up to the event being triggered. Also, we only need 4 test cases for complete coverage of that function. More complex conditions do not fit into this schema, and the tests could be based on a flowchart or a truth table.

This strategy of isolating the relevant code is not perfect. It is possible to subvert these checks. But this should protect against accidental mistakes. E.g. if I set the airbag-related registers in a different part of the code, the static analysis will alert you quickly to the problem.

Your first hunch that we would have to verify the complete program state is not entirely wrong. But fortunately, we can shape that state space so that airbag-triggering events must go through a specific area, and we can pay extra attention to that area.

1

It seems to me that the only if likely requires an exhaustive exploration of the programs state space,

Or you could log and test that whenever D happens the right stuff was happening 10ms ago.

Testing is about reading code. Sure this thing is safety critical but if you let that motivate you to write crazy exhaustive tests no one can read then you're not saving anyone.

It might also help to use a language that lets you easily control what can change D and that blows up whenever you run off the end of an array.

  • The problem with log and test is that to get acceptable coverage you need to do a HUGE amount of it, even if running on a tiny core with only say 64 bytes of ram that is still more state space then you can reasonably test even a small fraction of. I am not sure that classical testing is actually useful here, as you really want verification. And yea, ADA with spark looks nice for this stuff, or just bite the bullet and write the damn logic in VHDL! – Dan Mills Jun 4 '18 at 12:21
  • In a language that prevents you from mucking about with memory that isn't yours the state space is A, B, C, and D. – candied_orange Jun 4 '18 at 12:29
  • @DanMills many folks run their unit test suite on host and then either only run a subset of integration tests on target, or chunk the tests out when running on target. – RubberDuck Jun 7 '18 at 21:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.