Acronym

21.1 Introduction to Partitioning

Partitioning is the Achilles heel of integrated modular avionics (IMA) systems and advanced avionics. Implementing a robustly partitioned system requires extreme care and caution. This chapter provides an overview of the basic concepts related to partitioning and key actions necessary to implement partitioning in a safety-critical system.

21.2 Shared Memory (Spatial Partitioning)

John Rushby writes: “Spatial partitioning must ensure that software in one partition cannot change the software or private data of another partition (either in memory or in transit) nor command the private devices or actuators of other partitions” [4]. Basically, spatial partitioning prevents a function in one partition from corrupting or overwriting the data space of a function in another partition [9]. Justin Littlefield-Lawwill and Larry Kinnan explain that spatial partitioning assures that shared system resources in one partition “are not consumed in a manner that would result in a denial of service for other partitions requiring access to the same resource” [10]. There are two common approaches to memory protection: (1) using a memory management unit (MMU) or (2) using software fault isolation (SFI).

Hardware-based spatial partitioning is the most prevalent form of spatial partitioning. A hardware MMU is usually provided with the CPU. The details of the MMU operation vary from processor to processor. The MMU ensures that policies expressed in MMU tables provide the desired controls over memory access. Since the MMU is a commercial off-the-shelf (COTS) device without supporting life cycle data, the operating system is used to set up the MMU tables that the processor subsequently uses. The proper functionality (accuracy) of the MMU needs to be confirmed during the certification effort. Chapter 20 explained that this is often confirmed during the RTOS testing. The Federal Aviation Administration (FAA) report entitled Commercial Off-The-Shelf Real-Time Operating System and Architectural Considerations [11] provides some additional details for how the MMU and RTOS are used to provide robust partitioning.

If the MMU isn’t used, SFI is an alternative [4]. With this approach logical checks are added in the code at each memory access point. The machine code in a partition is examined to determine the destinations of memory references and to check their accuracy.

Indirect memory references cannot be checked statically, so instructions are added to the program to check the contents of the address regis ter at runtime, immediately prior to its use. The SFI technique imposes some overhead cost by adding code to the program. It also requires an additional analysis and certification cost on every project. However, it is possible to automate much of the check procedure and to qualify a tool or toolset that can be used on multiple projects [9].

The CAST-2 position paper identifies several areas to consider when implementing memory partitioning, such as loss, corruption, or delay of input or output data, corruption of internal data, program overlays, buffer sequences, external device interaction, control flow defects which affect memory (e.g., incorrect branching into a partition or protected area), etc. [1].

21.3 Shared Central Processing Unit (Temporal Partitioning)

“Temporal partitioning must ensure that the service received from shared resources by the software in one partition cannot be affected by the software in another partition. This includes the performance of the resource concerned, as well as the rate, latency, jitter, and duration of scheduled access to it” [4]. Partitioning in the time domain is closely related to multitasking schedulability, which was discussed in Chapter 20. ARINC 653 enforces strict round-robin scheduling for partitions (durations and periods are specified in a configuration table). Within the partition, other schedulers are used.

The goal of temporal partitioning is to ensure that functions in one partition do not disturb the timing of events in other partitions. Concerns include one partition that monopolizes the CPU, crashes the system, or issues a HALT instruction—leading to denial of services for other partitions. “Other scenarios that can cause a partition to fail to relinquish the CPU on time include simple schedule overruns, where particular parameter values cause a computation to take longer than its allotted time, and runaway executions, where a program gets stuck in a loop” [4]. The approach to temporal partitioning should take these scenarios into account.

Processor interrupts are used in real-time systems to identify an event that needs processor access. Interrupts must be handled carefully to avoid undermining the temporal partitioning. Normally such disruptions are prevented by eliminating interrupts altogether, with the exception of the timer tick used to implement the schedule. However, some parties desire to expand ARINC 653 to provide a deterministic means of handling interrupts [7]. Interrupts are discussed more in Section 21.5.

The CAST-2 position paper identifies areas to consider when implementing temporal partitioning, such as interrupts and interrupt inhibits, loops, frame overrun, counter or timer corruption, pipelining and caching, control flow defects, memory or I/O contention, software traps (such as divide by zero), etc. [1].

21.4 Shared Input/Output

Most systems have multiple I/O ports, devices, and channels, for example, a serial bus, an ARINC 664 AFDX (avionics full-duplexed switched ethernet) end system, a field-programmable gate array device, or a CRC device. Some devices are dedicated to a specific partition and others are shared by multiple partitions. As noted in Chapter 20 on RTOSs, a device driver typically serves as the glue code between the device and the RTOS kernel.

As with other shared resources, I/O resources need to be partitioned. Partitioning concerns for shared I/O are closely related to space and time partitioning. For each I/O device, partitioning for both the time and space domains must be considered.

Addressing partitioning in I/O can be one of the most challenging aspects of design for a partitioned system. ARINC 653 provides sampling and queuing port interface and operation definitions for interpartition I/O; however, I/O to physical devices or intermodule I/O is implemented at the discretion of the RTOS developers or other stakeholders. The ARINC 653 port mechanism (which is based on pseudo ports and pseudo partitions) can be used as an interface standard for connectivity; however, it may lead to performance issues for the applications [10]. Steve VanderLeest explains that when partitioning I/O devices, not only the end device must be considered, but one must also consider the communication mechanisms connecting the device to the memory and CPU (such as communication busses, direct memory access engines, and intermediate buffers). “The partitioning environment must manage all the salient features of the I/O subsystem” (including latency, bandwidth, control registers, and buffer space) to prevent partitions from affecting one another by an unauthorized means [7].

The approach to address I/O partitioning varies depending on I/O hardware specifics and the low-level device driver. The FAA research report, entitled Real-Time Operating Systems and Component Integration Considerations in Integrated Modular Avionics Systems Report, notes:

Different approaches are possible, such as kernel-centralized I/O control or partition I/O control. Many implementations incorporate some type of RTOS-governed partition or task permission table that permits only certain partitions or tasks to access specific I/O. A health monitor is then employed to identify any undesignated accesses by other tasks or partitions. I/O considerations differ for different RTOSs [8].

Depending on the scenario, the RTOS may implement some constraints or make some assumptions that require special integration steps by the integrator [8]. As with any other assumptions or constraints, these should be documented by the RTOS vendor and/or platform supplier and communicated to the integrator; oftentimes, the platform data sheet includes this type of information.

The use of I/O interrupts should be carefully evaluated in the partitioning scheme. Most CPUs support interrupts from I/O-related events. However, as will be discussed shortly, interrupts can impact partitioning and may not be allowed. Therefore, another approach may need to be established to communicate events that require action.

21.5 Some Partitioning-Related Challenges

Some organizations are tempted to rely on the RTOS alone to implement partitioning. However, partitioning is a system-level characteristic. The processor, board support package (BSP), devices, device drivers, MMU, etc. play a role in the partitioning approach and can disrupt robust time and space partitioning. Some specific areas that pose challenges to partitioning are identified in this section, including direct memory access, cache memory, interrupts, and interpartition communication.

21.6 Recommendations for Partitioning

This section provides some practical recommendations to consider when implementing and verifying partitioning. Each project varies and the technical details must be addressed on a case-by-case basis; however, these recommendations are intended to provide a starting point.

Recommendation 1: Keep in mind that robust partitioning is a system-level concern. As explained in Section 21.5, robust partitioning is not implemented by software alone. It is a system-level concern that requires early and ongoing collaboration between systems, hardware, and software teams. Likewise, robust partitioning isn’t implemented by the RTOS alone. The RTOS can play a significant role in enforcing robust partitioning, but it is not the only component involved.

Recommendation 2: Proactively design for robust partitioning. Robust partitioning requires diligent design—it does not just happen. There are multiple dimensions to consider and numerous technical challenges. However, addressing these challenges proactively during the development phases significantly reduces surprises during the integration and verification phases. The following suggestions are offered:

1. Consider the common issues noted earlier (such as interrupts, cache memory, I/O challenges) and address them as part of the design solution.

2. Document partitioning goals, for example:

   1. The system will implement robust memory protection: An application will always receive its allocated memory resources, without interference from other applications.

   2. The system will implement robust time protection: An application will always receive its specified execution time without interference from other applications.

   3. The system will implement robust resource protection: An application will always receive its physical and logical allocated resources without interference from other applications.

3. Define robust partitioning requirements to meet the goals.

4. Identify all shared resources so they can be properly utilized to support robust partitioning.

5. Document partitioning details in the design. In particular, ensure that all components and their interactions are clearly identified.

6. Identify all requirements (at each hierarchical level) that support or impact partitioning. For example, a requirements attribute may be assigned to distinguish partitioning-related requirements. This also assists with the subsequent partitioning analysis.

7. Identify multiple means to prevent failure propagation.

8. Use containment boundaries to limit the effect of failures.

9. Reference the guidance of DO-297 section 3.5.1 (entitled Design for robust partitioning) [3], which provides guidelines to consider when designing a robustly partitioned IMA platform. The DO-297 concepts are applicable, even if the system is not classified as IMA.

Recommendation 3: During design and design reviews ensure that vulnerabilities are addressed. As the design is documented and reviewed, consider probing questions that would uncover partitioning violations. Table 21.1 pro vides example questions to help uncover data-related and control-related vulnerabilities.

Recommendation 4: Consider using an ARINC 653 compliant RTOS. As previously noted, the RTOS alone doesn’t address all of the partitioning issues; however, it is a good start. ARINC 653 provides guidelines to help RTOS and platform developers think through the partitioning challenges.

Recommendation 5: Utilize other development and verification activities to prevent redundant efforts. Partitioning should be considered throughout the system and software development. Other development or verification activities can be utilized to support the robust partitioning design and verification, including the following:

• Build upon the data and control coupling activities. The data and control coupling analyses provides a good starting point for robust partitioning. Data and control coupling and software partitioning are related, but are distinct concepts. Partitioning is a way to provide isolation between independent software components and thus provides protection of unintended coupling between independent partitioned components. Data and control coupling is an intentional interaction between components, including coupling between separately partitioned components. Software partitioning does not guarantee avoidance of data or control coupling problems; conversely, data and control coupling problems do not imply that the partitioning mechanism is flawed. For partitioned systems, data and control coupling analyses, as well as partitioning analysis, are required. There may be some synergy between the two objectives.

• Use robustness testing to confirm partitioning is not violated. When partitioning is clearly documented in the requirements and design, it drives the testing effort, which provides a good start toward proving the robust partitioning claims. The partitioning analysis may identify the need for additional testing; however, the requirementsbased tests provide a foundation to begin building confidence in the partitioning strategy.

• Utilize the RTOS software vulnerability analysis (SVA). If an RTOS is used, the RTOS vendor may have an SVA available to use as input to the partitioning analysis data. The SVA was discussed in Chapter 20.

Recommendation 6: Test the partitioning mechanism. The main purpose of verifying the partitioning mechanism is to ensure that no erroneous behavior in one partition can contribute to misbehavior or failure of any other partition and to ensure that partitioning of shared resources are not violated. DO-248C discussion paper #14 (entitled Partitioning aspects in DO-178C/DO-278A) provides some suggestions for verifying the partitioning mechanism:

Elements of partitioning integrity can be verified by exercising the partitioning mechanisms using special test scenarios, simulations, and/or analysis techniques. Test scenarios should be written to stimulate the partitioning mechanism by injecting errors or violation attempts to bypass time and space constraints. An example of additional analysis would be the calculation of worst-case execution times to assess temporal performance… A verification test suite (containing normal range test cases and abnormal or out of range test cases for all requirements of the partitioning mechanism) should be established. Robustness of the partitioning mechanism may be demonstrated by use of a requirementsbased test suite (satisfying requirements-based test coverage) [12].

Some projects also implement rogue partition testing, where a rogue partition is developed to try to deliberately violate the partitioning.

Recommendation 7: Perform a partitioning analysis. DO-297 promotes an activity called partitioning analysis. The purpose of the analysis is to demonstrate that no application in a partition can affect the behavior of applications in any other partition in an adverse manner. The partitioning analysis is similar to the system safety assessment, where all potential sources of failure are considered and mitigated. All vulnerabilities should be identified, classified, and mitigated [11]. The engineer(s) performing the analysis must have detailed understanding of the system, hardware, and software architecture. The chief architect is often the ideal person to do this analysis. Following are some common tasks performed as part of the partitioning analysis:

1. Gather data to support the analysis, including the preliminary sys tem safety assessment, system requirements and design, software requirements and design, hardware architecture, BSP and device driver design data, processor data sheet and/or user manual, device user manuals, interface specifications, configuration tool requirements and design (if applicable), etc.

2. Identify the robust partitioning claims that will be analyzed, for example,^*

   1. The system will implement robust memory protection: An application will always receive its allocated memory resources, without interference from other applications.

   2. The system will implement robust time protection: An application will always receive its specified execution time without interference from other applications.

   3. The system will implement robust resource protection: An application will always receive its physical and logical allocated resources without interference from other applications.

3. Identify potential vulnerabilities which could violate each claim. All potential sources of error should be systematically identified and considered, including resource limitations, scheduling tasks, I/O, interrupt error sources, etc. A traceability analysis that traces all shared resources to the modules, components, and applications that use those shared resources helps confirm that all potential vulnerabilities have been considered [13]. The potential partitioning violations of shared memory devices (such as read only memory [ROM], random access memory [RAM], cache, queues, and onboard chip registers) should be analyzed. Likewise, the effects of hardware failures on shared and nonshared hardware components should also be analyzed. DO-297 section 3.5.2.5 identifies some common potential sources of design errors that could impact the partitioning [3]:

   1. Interrupts and interrupt inhibits (software and hardware).

   2. Loops (for example, infinite loops or` indirect non-terminating call loops).

   3. Real-time correspondence (for example, frame overrun, interference with real-time clock, counter/timer corruption, pipeline and caching, deterministic scheduling).

   4. Control flow (for example, incorrect branching into a partitioned or protected area, corruption of a jump table, corruption of the processor sequence control, corruption of return addresses, unrecoverable hardware state corruption (for example, mask and halt)).

   5. Memory, input, and/or output contention.

   6. Sharing of data flags.

   7. Software traps (for example, divide by zero, unimplemented instruction, specific software interrupt instructions, unrecognized instruction, and recursion termination).

   8. Hold-up commands (i.e., performance hedges).

   9. Loss of input or output data.

   10. Corruption of input or output data.

   11. Corruption of internal data (for example, direct or indirect memory writes, table overrun, incorrect linking, calculations involving time, corrupted cache memory).

   12. Delayed data.

   13. Program overlays.

   14. Buffer sequence.

   15. External device interaction (for example, loss of data, delayed data, incorrect data, protocol halts).

4. Identify potential vulnerabilities that are mitigated by design. The majority of the vulnerabilities are mitigated by the design—especially when robust partitioning is proactively considered during the development phases. Each vulnerability mitigated by design should trace to the requirement(s) that demonstrate the mitigation (i.e., there should be a mapping between vulnerabilities and requirements that provide the mitigations). Additionally, each mitigation should be verified during testing.

5. Identify potential vulnerabilities that are mitigated by process. Some potential vulnerabilities may be mitigated by process (e.g., the use of a qualified tool to verify accuracy of configuration data or a design standard that confirms certain memory assignments).

6. Identify potential vulnerabilities that cannot be mitigated by design or process. These will need to be communicated to the integrator and possibly the application developer. Such communication is normally documented in the data sheet and appropriate user information, so the integrator or application developer can take the appropriate action.

7. Coordinate with safety and systems personnel throughout the partitioning analysis. The partitioning analysis is essentially an extension of the safety assessment and should be closely coordinated with the system safety personnel.

8. Ensure that all potential vulnerabilities have been mitigated, particularly those that were not addressed by design or process. The goal is to minimize mitigation activities to be taken by the integrator or applications; however, in some cases there may be special actions required. For example, the integrator may have to perform some special verification steps or impose special restrictions through the configuration files.