Challenges in Autonomous Vehicle Testing and Validation

It's a lot of work to demonstrate that self-driving cars will actually work properly.  Testing alone is probably not going to be enough, and probably there will need to be some clever architectural approaches as well.  Last week I gave a talk at the SAE World Congress in Detroit about this and related challenges.

Link to paper 
Link to slides  (also see slideshare version by scrolling down).

Challenges in Autonomous Vehicle Testing and Validation 
     Philip Koopman & Michael Wagner
     Carnegie Mellon University; Edge Case Research LLC
     SAE World Congress, April 14, 2016

Abstract:
Software testing is all too often simply a bug hunt rather than a well considered exercise in ensuring quality. A more methodical approach than a simple cycle of system-level test-fail-patch-test will be required to deploy safe autonomous vehicles at scale. The ISO 26262 development V process sets up a framework that ties each type of testing to a corresponding design or requirement document, but presents challenges when adapted to deal with the sorts of novel testing problems that face autonomous vehicles. This paper identifies five major challenge areas in testing according to the V model for autonomous vehicles: driver out of the loop, complex requirements, non-deterministic algorithms, inductive learning algorithms, and fail operational systems. General solution approaches that seem promising across these different challenge areas include: phased deployment using successively relaxed operational scenarios, use of a monitor/actuator pair architecture to separate the most complex autonomy functions from simpler safety functions, and fault injection as a way to perform more efficient edge case testing. While significant challenges remain in safety-certifying the type of algorithms that provide high-level autonomy themselves, it seems within reach to instead architect the system and its accompanying design process to be able to employ existing software safety approaches.

Challenges in Autonomous Vehicle Testing and Validation from Philip Koopman

Ensure Code Is Modular

Critical embedded software should be modular, and in particular should limit function size to no more than 1-2 pages of code including comments.

Consequences: Poor modularity can reasonably be expected to result in code that is more complex, more brittle, and in general has a higher defect rate than modular code. This is in part because code with poor modularity it is harder to understand (and therefore harder to get right), and in part because it is more difficult to test than code with good modularity.

Accepted Practices:

• A significant majority of functions, procedures, or subroutines must each be no more than a defined length in the range of 100-225 lines long, nominally 120 lines long, including comments. Longer functions should be rare, and their length should be specifically justified, taking into account whether they have low cyclomatic complexity or other mitigating factors. 
• Each module should have high cohesion, low coupling, and good information hiding. There are no generally accepted precise values for these metrics.

Discussion:

Code is considered modular if it is written in reasonably small chunks of code (modules) that work together in a way that maintains some key properties. Code that is merely in small chunks but that does not achieve these properties is not considered modular. A code “module” is classically defined as a piece of code that accomplishes a particular function. This may be either a single software subroutine (or equivalent) with associated variables, or may be a small set of collected subroutines that work together to accomplish a function or a set of closely related functions. Key properties of modular code include the following areas.

Small size: each function should be one or two pages of code when printed (up to say 120 lines of code including comments maximum, but with most functions being less than one page of 60-75 lines including comments). Having a function size larger than this makes it difficult for developers and reviewers to understand the entirety of the function at one time, decreasing the effectiveness of finding bugs. Large size also makes it harder to create effective unit tests due to the increased complexity of a large function. (This length limit is historically associated with a function, in terms of a single function fitting on one printed page of about 65 lines.)

High cohesion: each module performs a single job and contains a set of closely related functions rather than a collection of unrelated functions. Having low cohesion results in code that mixes up unrelated functions, making it difficult to test, and difficult to maintain as changes need to be made. Low cohesion also normally leads to bugs due to related functions being scattered around many modules instead of in a single module.

Low coupling: modules should have a low dependency upon other module data. High coupling causes data dependencies among modules that makes testing difficult and tends to lead to subtle data sharing bugs. Good practice is to minimize coupling via avoiding global variables. High coupling can be reasonably expected to increase defect rates.

Information hiding: modules should hide as much about the details of their implementation as possible to reduce implicit dependencies that can cause other parts of the software to fail. For example, the exact algorithm or data format used for calculations internal to a module should not be discernible to any other module. Accepted practice is to use the “static” keyword on identifiers within a .c file to accomplish information hiding, and declare variables within a procedure, instead of globally, if they are only needed within that procedure.

Selected Sources:

Fenton & Neil discuss the topic of software metrics (1999), and say that to really understand the problem you need to consider many factors at once rather than simple metrics. They give an example a combination of problem complexity, use of IEC1508 (draft version of IEC 61508), code complexity, and operational usage among others (Fenton Fig 3, pg. 684) as a way to ensure good code. In other words, it is clear that these types of factors matter, even if there is no single optimal answer.

McConnell presents a survey of function length practices. A length limit of one to two printed pages is common in industry. McConnell says: “If you want to write routines longer than about 200 lines, be careful. (A line is a non-comment nonblank line of source code.)” He also says: “you’re bound to run into an upper limit of understandability as you pass 200 lines of code” (McConnell 1993, pp. 93-94). These comments are primarily in the context of desktop applications rather than safety critical embedded control software. In my opinion a smaller limit than 200 lines of non-comment code is considered acceptable practice for safety critical embedded systems. McConnell, chapter 5, talks more generally about modular programming in terms of information hiding, coupling, cohesion, and function length.

Selby & Basili found that software modules with high coupling and low coherence had 7.0 times as many errors (per lines of non-comment code) as modules with low coupling and high coherence. (Selby et al. 1991, abstract, p. 146).

Withrow found that the optimum size for minimizing defects was 225 lines of code per module, which is a bit larger than some guidelines (Withrow 1990), but still in the same general range being discussed.

The NASA “Power of Ten” rules for writing safety critical code recommend functions of at most 60 lines of text (Holzman 06, rule 4).  They also recommend declaring data objects at the smallest possible level of scope (id., rule 6).

IEC 61508-3 highly recommends a module size limit (p. 93).

MISRA states that modularity requires high cohesion and low coupling (MISRA Report 5, pp. 9-10).

References:

• Fenton, A critique of software defect prediction models, IEEE Trans. Software Engineering, Sep/Oct 1999, pp. 675-689.
• IEC 61508, Functional Safety of Electrical/Electronic/Programmable Electronic Safety-related Systems (E/E/PE, or E/E/PES), International Electrotechnical Commission, 1998. Parts 2,3,7. 
• Holzman, ''The Power of Ten -- Rules for Developing Safety Critical Code,'' IEEE Computer, June 2006, pp. 93-95.
• McConnell, Code Complete, Microsoft Press, 1993.
• MISRA, Report 5: Software Metrics, February 1995.
• Selby & Basili, Analyzing error-prone system structure, IEEE Trans. Software Engineering, Feb 1991, pp. 141-152.
• Withrow, Error density and size in Ada software, IEEE Software, Jan. 1990, pp. 26-30.

Redundant Input Processing for Safety

Redundant analog and digital inputs to a safety critical system must be fed to independent chips to ensure no single point failure exists.  (This posting is a follow-on to a previous post about single points of failure.)

Consequences: If fully replicated input processing and validation is not implemented with complete avoidance of single points of failure, it is possible for a single fault to result in erroneous input values causing unsafe system operation.

Accepted Practices:

• A safety critical system must not have any single point of failure that results in a significant unsafe condition if that failure can reasonably be expected to occur during the operational life of the deployed fleet of systems. Redundant input processing is an accepted practice that can help avoid single point failures.

Discussion:

A specific instance of avoiding single points of failure involves the processing of data inputs. It is imperative that safety critical input signals be duplicated and processed independently to avoid a single point of failure in input processing.

Analog inputs must be converted to digital signals via an A/D converter, which is a relatively complex apparatus that takes up a significant amount of chip area. For this reason, it is common to use a single shared A/D converter with multiple shared (“muxed”) inputs to that single converter. If redundant external inputs are run through the same A/D, this creates a single point of failure in the form of the A/D converter itself and the associated control circuitry.

Mauser gives an example of this problem applied to automotive throttle control, showing that only a "true 2-channel system" (e.g., a 2oo2 system with redundant inputs) provides safety.

Figures from Mauser 1999, pp. 731, 738-739 showing an example throttle control system that causes runaway unless a truly redundant system (dual CPUs plus dual A/D conversion) is used.

Similarly, digital inputs that are processed in the same chip have common circuitry affecting their operation, which in typical chips includes a direction register that determines whether a digital pin is an input or output.

For both analog and digital inputs, an additional way of looking at single point failures is that if both redundant input signals are processed on the same chip, that one chip is subject to arbitrary faults, with arbitrary fault behavior including the possibility of corrupting both inputs in a way that is both faulty and undetectable by other components in the system. Unless some independent means of ensuring system safety is present, such a single point of failure impairs system safety. An arbitrary fault on a single chip that processes both copies of an analog input sensor might declare the sensor to be fully activated, but within normal operational limits, resulting in that value being processed by the rest of the system whether the input is really active or not. For example, an embedded CPU in a car might think that the brake pedal is depressed, accelerator pedal is depressed, or parking brake is engaged despite the potential presence of redundant sensors on those controls if both sensors pass through the same A/D converter or digital input port and there is a common-mode hardware fault in those input processing circuits.

Beyond the need to independently computer results on two different chips, there is an additional requirement for safety that each of the two chips independently and fully compare the inputs to detect any faults. For example, if chips A and B both process inputs, but only chip B compares them for correctness, then there is a single point of failure if chip B has a bad input and incorrectly reports the comparison as passing (this only counts as one failure because chip B can fail in an arbitrary way in which it both mis-interprets input B and "lies" about the comparison with input A being OK). A safe way to do such a comparison is that chip A compares both inputs, chip B compares both inputs, and the system only continues operation if both chip A and chip B agree that each of their comparisons validated the inputs as being consistent. Moreover, cross-checks on the outputs based on those inputs must also be performed to detect faults that occur after input processing. That generally leads to a 2oo2 architecture like the one shown below, with each FCR usually being a CPU chip.

Sometimes both inputs go to both FCRs, but then it must be ensured that there is hardware isolation in place so that a hardware fault on one FCR can't propagate to the inputs of the other FCR via the shared input lines. Another complication is that redundant sensors often do not produce identical output values, and the problem of determining distributed agreement turns out to be very difficult even if all you need is an approximate agreement result. In general, once you have replication, getting agreement across the replicated copies of inputs and computations requires some effort (Poledna 1995). But, these are the sorts of issues that engineers routinely work through when creating safety-critical systems.

In the end, having a single shared A/D converter or other input circuit for a safety critical system is inadequate. You must have two separate input processing circuits on two separate chips to have two independent Fault Containment Regions (e.g., using a 2oo2 architectural approach with redundant inputs). This is required to achieve safety for a high-integrity application, and any high-integrity embedded system that uses a shared A/D converter on a single chip to process redundant inputs is unsafe.

References:

• Mauser, Electronic throttle control – a dependability case study, J. Univ. Computer Science, 5(10), 1999, pp. 730-741.
• Poledna, S., "Fault tolerance in safety critical automotive applications: cost of agreement as a limiting factor ", Fault-Tolerant Computing, 1995. FTCS-25. Digest of Papers., Twenty-Fifth International Symposium on , 27-30 Jun 1995 Page(s): 73 -8

Embedded Software Risk Areas -- Architecture

Series Intro: this is one of a series of posts summarizing the different red flag areas I've encountered in more than a decade of doing design reviews of industry embedded system software projects. You can read more about the study here. If one of these bullets applies to your project, you should consider whether that presents undue risk to project success (whether it does or not depends upon your specific project and goals). The results of this study inspired the chapters in my book.

Here are the Architecture red flags:

• No defined software architecture

There is no picture showing the system’s software architecture. (Many such pictures might be useful depending upon the context – but often there is no picture at all.) Ill defined architectures often lead to poor designs and poor quality code.

• No message dictionary for embedded network

There is no list of the messages, payloads, timing, and other aspects of messages being sent on an embedded real time network such as CAN. As a result, there is no basis for analysis of real time network performance and optimization of message traffic.

• Poor modularity of code

The design has poorly chosen interfaces and poorly decomposed functionality, resulting in high coupling, poor cohesion, and overly long modules. In particular, interrupt service routines are often too big and mask interrupts for too long. The result is often increased risk of software defects due to increased complexity.