Towards Integration of Adaptability and Non-Intrusive Runtime Verification in Avionic Systems

Abstract

Unmanned autonomous systems (UAS) avionics call for advanced computing system architectures ful lling strict size, weight and power consumption (SWaP) requisites, decreasing the vehicle cost and ensuring the safety and timeliness of the system. The AIR (ARINC 653 in Space Real-Time Operating System) architecture de nes a partitioned environment for the development and execution of aerospace applications, following the notion of time and space partitioning (TSP), preserving application timing and safety requisites. The plan for a UAS mission may vary with the passage of time, according to its mode/phase of operation, and the vehicle may be exposed to unpredictable (environmental) events and failures, calling for the advanced adaptability and recon gurability features included in the AIR architecture. This paper explores the potential of non-intrusive runtime veri cation (RV) mechanisms, currently being included in AIR, to improve system safety and to decrease the computational cost of timeliness adaptability and of the corresponding overhead on the system.

Keywords

• eol>dependability
• timeliness
• adaptability
• runtime veri cation
• time and space partitioning
• integrated modular avionics

Categories and Subject Descriptors

C.4 [Computer System Organisation]: [Fault tolerance]; C.3 [Special-Purpose and Application Based Systems]: Real-time and embedded systems; D.4.7 [Operating systems]: Organization and Design|Real-time systems and embedded systems This work was partially supported by FCT, through project PTDC/EEI-SCR/3200/2012 (READAPT) and through LaSIGE Strategic Project PEst-OE/EEI/UI0408/2014. This work integrates the activities of COST Action IC1402 - Runtime Veri cation beyond Monitoring (ARVI).

2. AIR TECHNOLOGY FOR TSP SYSTEMS

The AIR Technology evolved from a proof of feasibility for adding ARINC 653 functional support to the Real-Time Executive for Multiprocessor Systems (RTEMS) to a multi-OS (operating system) TSP architecture [ 20 ]. The AIR modular design aims at high levels of exibility, hardware- and OSindependence, easy integration and independent component veri cation, validation and certi cation.

2.1 System architecture

The AIR modular architecture is pictured in Figure 1. The AIR Partition Management Kernel (PMK) is the basis of a core software layer, enforcing robust TSP properties and hosting crucial functionality such as partition scheduling and dispatching, low-level interrupt management, and interpartition communication support. Temporal partitioning ensures that the real-time requisites of the di erent functions executing in each partition are guaranteed. Spatial partitioning relies on having dedicated addressing spaces for the functions executing on di erent partitions.

Each partition can host a di erent OS (the partition operating system, POS), which in turn can be either a real-time operating system (RTOS) or a generic non-real-time one. The AIR POS Adaptation Layer (PAL) encapsulates the POS of each partition, providing an adequate POS-independent interface to the surrounding components.

The Portable Application Executive (APEX) interface [ 22 ] provides a standard programming interface derived from the ARINC 653 speci cation [ 1 ], with the possibility of being subsetted and/or adding speci c functional extensions for certain partitions [ 19 ].

The organization of vehicle functions in di erent partitions requires interpartition communication facilities, since a function hosted in a partition may need to exchange information with other partitions. Interpartition communication consists of the authorized transfer of information between partitions without violating neither spatial separation constrains nor information security properties [ 21, 20, 5 ].

2.2 Two-level scheduling

The AIR technology employs a two-level scheduling scheme, as illustrated in Figure 2. The rst level corresponds to partition scheduling and the second level to process scheduling. Partitions are scheduled on a cyclic basis, through the partition scheduling and dispatching components (Figure 2), ac

Native POS Process Scheduler

Native POS Process Scheduler

Native POS Process Scheduler . . . cording to a partition scheduling table (PST) repeating over a major time frame (MTF). The PST assigns execution time windows to partitions. Inside each partition's time windows, its processes compete for processing resources according to the POS's native process scheduler.

2.3 Health monitoring and error handling

The AIR architecture incorporates Health Monitor (HM) functions that aim to contain faults within their domains of occurrence and to provide the corresponding error handling capabilities. Support to these functions is spread throughout virtually all of the AIR architectural components. The HM plays an important role in achieving system safety given it prevents/mitigates ill-e ects of process and/or partition level errors in the remaining partitions. The action to be performed in the event of an error is de ned by the application programmer through an appropriate error handler. This may comprise adaptability features such as the rede nition of timing and control parameters or the issue of a di erent schedule request. If no handler is provided, a response action de ned by the partition's HM ARINC 653 con guration table is executed, as shown in Figure 3.

Application

EH: event handler

POS Process Exception!

Interrupt traps others AIR PMK/POS interrupt handling Activate (event-driven)

no

System level? no EH defined? yes EH running?

yes no yes

Action defined? yes

no AIR Health Monitor Default Action

Ignore Restart Shutdown The design of AIR allows HM handlers to simply replace existing exception handlers or to be added to existing ones, in pre- and/or post-processing modes.

3. ADAPTABILITY

The adaptation to changing environmental or operating conditions is crucial for unmanned space and aerial missions survivability, which can be signi cantly improved through software recon gurability, as studied in [ 23 ].

The design of AIR integrates special-purpose mechanisms to address speci c adaptation requirements, thoroughly described in [ 7 ] and summarised next.

3.1 Mode-based schedules

Timing requirements may change according to a mission's phase since certain functions should only execute during certain phases. The original ARINC 653 notion of a single xed PST [ 1 ], de ned o ine, is limited in terms of timeliness adaptability, as well as safety and fault-tolerance control, and surely contributes to some degree of resource utilization waste. To address this primary limitation, the AIR design incorporates the notion of mode-based partition schedules, inspired by the optional service de ned within the scope of ARINC 653 Part 2 speci cation [ 2 ].

Instead of one xed PST, the system can be con gured with multiple PSTs, which may di er in terms of the MTF duration, of which partitions are scheduled, and of how much processor time is assigned to them, as shown in Figure 2. The system can then switch between these PSTs; selection of the active PST is performed through a service call issued by an authorized and/or dedicated partition. To avoid violating temporal requirements, a PST switch request is only e ectively granted at the end of the ongoing MTF. Hosting multiple PSTs aboard autonomous vehicles opens room for the (self-)adaptability of unmanned missions, in function of passage of time and of changing environmental and operational conditions. Pre-generation of di erent partition schedules can be aided by a tool that applies rules and formulas to the temporal requirements of processes/partitions, taking into account the functions' needs in di erent anticipated conditions [ 20, 8 ]. Unforeseeable conditions can be handled thorough the mechanisms for remote update of PSTs and onboard software described in [ 19 ].

3.2 Process deadline violation monitoring

During runtime execution, it may be the case that a process exceeds its deadline. In the AIR architecture, the PAL component monitors, at each POS clock tick, if some process in the active partition has violated its deadline (Figure 2). In addition, it is also possible that a process exceeds its deadline while the partition in which it executes is inactive. This violation will only be detected when the partition is being dispatched, just before the PAL component invokes the POS process scheduler, as shown in the diagram of Figure 2. The use of o ine tools that verify the ful lment of timing requirements [ 20, 8 ], should rule out deadline violations due to faulty system planning (e.g., time windows not satisfying the partitions' timing requirements). However, such tools cannot cope with process deadline violations caused by a runtime malfunction, by transient overload (e. g., due to abnormally high event occurrence rates), or by the underestimation of a process's worst case execution time (WCET) at system con guration and integration time.

4. MECHANISMS FOR NON-INTRUSIVE

RUNTIME VERIFICATION

Runtime veri cation (RV) obtains and analyses data from the execution of a system to detect and possibly react to behaviours, either satisfying or violating the system specication. RV implies that small components, which are not part of the functional system, acting as observers, are added to monitor and assess the state of the system in runtime. The usage of recon gurable logic supporting versatile platform designs (e.g., soft-processors) enables innovative approaches to RV [ 17 ], herein explored in the context of TSP systems. An enhanced AIR architecture makes use of an AIR Observer (AO) featuring: non-intrusiveness, meaning system operation is not adversely a ected and code instrumentation with RV probes is not required; con gurable, being able to accommodate di erent event observations. s e s u B

Bus

Interfaces

Mgmt.

Interface

Time Base

currentTicks

Observer

Configuration

System Clock

The AO is plugged to the platform where the AIR software components execute, and comprises the modules depicted in Figure 4: Bus Interfaces, capturing all physical bus activity, such as bus transfers or interrupts; Management Interface, enabling AO con guration; Con guration, storing the patterns of the events to be detected; Observer, detecting events of interest based on the registered con gurations. Though RV concepts can be applied to both time and space partitioning, this paper is restricted to temporal issues. Thus, it is assumed that a robust time base1 accounts for, in the AO hardware (Figure 4), the number of POS-level clock ticks elapsed so far, to which AIR components have access, through the read only currentT icks variable/register.

5. INTEGRATING ADAPTABILITY AND

NON-INTRUSIVE RUNTIME VERIFI

CATION

The integration of RV features in the AIR architecture uses a dual approach, as follows: operation enforced in hardware, either totally or with some degree of assistance from software components, being the runtime veri cation actions performed in software; operation achieved through the execution of software components, with runtime veri cation actions enforced in hardware.

5.1 Mode-based schedules

In the generic and highly exible AIR architecture design presented in [ 20 ], the handling of mode-based schedules is entirely integrated within a software-based AIR Partition Scheduler, as illustrated in the diagram of Figure 2. In a hardware-assisted approach, partition scheduling switch decisions from the AO hardware are complemented with software RV and partition switch actions: when a partition 1The design and engineering AIR robust timers is out of the scope of this paper. It will be addressed in a future work. Algorithm 1 AIR Partition Scheduler with Runtime Verication featuring adaptation through mode-based schedules 1: Entered upon exception: partition preemption point detected 2: Runtime veri cation actions 3: if schedulescurrentSchedule :tabletableIterator :tick 6= (currentTicks lastScheduleSwitch) mod schedulescurrentSchedule :mtf then 4: HealthMonitor(activePartition) 5: else Partition switch actions 6: if currentSchedule 6= nextSchedule ^ (currentTicks lastScheduleSwitch) mod schedulescurrentSchedule :mtf = 0 then 7: currentSchedule nextSchedule 8: lastScheduleSwitch currentTicks 9: tableIterator 0 10: end if 11: heirP artition

schedulescurrentSchedule :tabletableIterator :partition 12: tableIterator (tableIterator + 1) mod

schedulescurrentSchedule :numberPartitionPreemptionPoints 13: end if is dispatched, the absolute value (in POS-level clock ticks) of its partition preemption point is inserted in the AO conguration; when this instant is reached, an AO's hardware exception triggers the execution of Algorithm 1. The RV actions of Algorithm 1 check, from the active PST, if the current instant is a partition preemption point (line 3). If that is not the case, a severe system level error has occurred and the HM is noti ed (line 4) to handle the situation. The remaining lines (6-12) implement the partition switch actions of [ 20 ], checking (line 6) if there is a pending scheduling switch to be applied and the current instant is the end of the MTF. If these conditions apply, a di erent PST will be used henceforth (line 7). The processing resources are assigned to the heir partition, obtained (line 11) from the PST in use, until the next partition preemption point. The AIR Partition Scheduler is set (line 12) to access the heir partition parameters.

This hardware/software co-design allows to maintain some degree of AIR architectural exibility with advantages in terms of improved safety and timeliness. This is particularly useful for running AIR in platforms integrating processor cores (e.g., dual-core ARM) and FPGA logic [ 10 ]. The partition switch actions are followed by the execution of the AIR Partition Dispatcher speci ed in Algorithm 2. Two signi cant di erences from [ 20 ] do exist: suppression of speci c elapsed clock ticks setting, which are no longer required because the partition dispatcher is always invoked after a partition switch; insertion of the next partition preemption point in the AO con guration (line 6). The remaining actions in Algorithm 2 are related to saving and restoring the execution context (lines 2 and 7) and evaluation of the elapsed clock ticks (line 4). Line 8 enforces the execution of pending actions the rst time after a PST change the partition is executed [ 20 ].

Compared with the equivalent speci cation in [ 20 ], the design of Algorithm 3 was greatly simpli ed since all the actions concerning process deadline violation monitoring were removed. The needed actions are now restricted to the signalling of the elapsed clock ticks (line 2) and to the instantiation of the POS native process scheduler (line 4). Algorithm 2 AIR Partition Dispatcher 1:

Entered from the AIR Partition Scheduler after partition switch actions 2: SaveContext(activePartition:context) 3: activePartition:lastTick currentTicks 1 4: elapsedTicks currentTicks heirPartition:lastTick 5: activePartition heirPartition 6: ReplacePreemptionPoint(heirPartition:tick) 7: RestoreContext(heirPartition:context) 8: PendingScheduleChangeAction(heirPartition) Algorithm 3 AIR PAL { pre POS process scheduler 1:

Executed immediately after AIR Partition Dispatcher and at every POS-level clock tick

2: PAL ClockTickAnnounce(elapsedTicks) 3: elapsedTicks = 1 4: POS ProcessScheduler()

5.2 Process deadline violation monitoring

Process deadline violation monitoring, a RV action, was made non-intrusive in the AIR hardware-assisted design. Each process issues, when required, system calls through the APEX interface. For those listed in Table 1, AIR PAL encapsulation provides the registering of the process' deadline in the AO (updating the process' entry, or creating a new one, if not con gured yet) or its unregistering (removing the process' entry from the AO con guration). If a process' deadline instant is reached, the AO detects the timeliness violation and issues a hardware exception that once caught activates the process level event handler de ned by the application programmer, as illustrated in Figure 3. The APEX primitive RAISE APPLICATION ERROR is used for that purpose, with PAL encapsulating a software-based RV action con rming the process deadline violation. The occurrence of process-/partition-level errors may be signalled through interpartition communication to a (system partition) process performing a Fault Detection, Isolation and Recovery (FDIR) function. A system-wide recon gurability logic should be included in FDIR [ 7, 20 ].

5.3 Analysis and discussion

Critical software, namely that developed to go aboard an aerial or space vehicle, goes through a strict process of veri cation, validation and certi cation.

Code complexity a ects the e ort required for that process, being one relevant metric for code complexity its size, in lines of source code. Towards the usage of standardized accounting methods one employ the logical source lines of code (logical SLOC) metric of the Uni ed CodeCount tool [ 15 ]. The C implementation of fundamental AIR software components is assessed in Table 2, which shows its logical SLOC count along with the entity instantiating the component, and implicitly, the instantiation frequency.

Most AIR software components have linear complexity, O(1): accesses to multielement structures are made by index, being independent of the number and position of the elements. The exception concern process deadline veri cation in the software-based approach, which in the worst case wields O(n), being n the number of processes in the partition. Similar considerations apply to timing issues. The AIR observer and the non-intrusive hardware-assisted approach has reduced the number and code complexity of software components in the path of POS-level clock tick processing. This is specially true for Algorithm 3 and its software-based counterpart code complexity and worst case timing, though in the normal and most frequent case where no process deadlines occur, both components exhibit similar execution times. Comparing the normalised processing time overheads of AIR Partition Scheduler and Dispatcher (TSD), in the softwarebased and hardware-assisted approaches, along a full normalised MTF period (TMT F ): =

TSD Soft

TSD Hard

TMT F TSD Soft

Ttick

TSD Hard : nppp

TMT F (1) (2) where, nppp is the number of partition preemption points in the MTF and Ttick is the normalised POS-level clock tick. The normalisation of timing parameters in Figure 5 take the experimental values TSD Soft = 150 ns and Ttick = 1 ms as references, making TSD Hard TSD Soft for hardwareassisted and TSD Hard = 0 for a full hardware implementation of the AIR Partition Scheduler/Dispatcher. The di erence to software-based processing overheads ( ) in function of MTF duration is represented in Figure 5. For the full hardware implementation, that di erence is independent from the MTF value being, in any case, upper bounded by the TSD Soft=Ttick ratio, which typically have quite small values due to the e cient coding of AIR Partition Scheduler and Dispatcher components. For the hardware-assisted approach the processing overhead di erence is smaller, dependent on the number/frequency of partition preemption points and only asymptotically approaches the TSD Soft=Ttick limit.

Though POS-level hardware-assisted mechanisms are also deemed to bene t partition/process scheduling timeliness and jitter, those issues have not been addressed so far.

6. RELATED WORK

To the best of our knowledge, contemporary approaches to exible scheduling in TSP systems are restricted to the mode-based scheduling feature of the commercial Wind River VxWorks 653 product [ 27 ]. Previous research on other TSP solutions [ 9 ] and works on scheduling analysis for avionic systems [ 14, 11 ] do not foresee mechanisms for timeliness adaptation. Alternatives to TSP/IMA are compared in [ 12 ],

Full hardware AIR Partition Scheduler/Dispatcher

Hardware-assisted AIR Partition Scheduler/Dispatcher 10 30 50 70 90 110 130 150 170 190

TMTF (time units) which includes recommendations for adaptation of IMA-like architectures. Some results on recon gurable IMA [ 4 ] and UAS adaptive and recon gurable control [ 25 ] do exist. A hardware/software co-design approach and the concept of system observer is present in the Simplex Architecture [ 3 ]. Emergence of non-intrusive runtime veri cation techniques for embedded systems in general is addressed in [ 26, 18 ], while its applicability to complex safety-critical systems is presented in [ 13 ]. However, no previous work have applied such techniques to the realm of TSP systems.

7. CONCLUSION

This paper addressed fundamental mechanisms providing support for adaptive and self-adaptive behaviour to applications based on the AIR architecture for time- and spacepartitioned systems. The usage of hybrid platforms combining processor cores and programmable logic makes advantageous the use of a hardware-assisted design complemented with some simple software-based components. The computational cost of such components decreases and the non-intrusive runtime veri cation of the system enables improvements in both safety and timeliness properties. Non-intrusive runtime veri cation is a relevant contribution with respect to veri cation, validation and certi cation efforts of TSP systems that will be extended in future research. Additional works aim to taking advantage of multicore platforms in AIR [ 6 ], which include adaptation/recon guration features and, in the near future, RV capabilities.

POS-level clock tick

APEX call

APEX call

POS-level clock tick

POS-level clock tick 12 8 4 6 4 >190 partition preemption point partition preemption point

APEX call

APEX call

POS-level clock tick

POS-level clock tick aSpeci ed and analysed in [ 20, 7 ] bSpeci ed in Algorithm 1 cSpeci ed in Algorithm 2 dSpeci ed in Algorithm 3; software-based approach speci ed and analysed in [ 20, 7 ] eRTEMS 4.9 [ 16 ] C code only; plus >182 assembly instructions in the POS-level clock interrupt service routine (ISR)

References

[1] AEEC (Airlines Electronic Engineering Committee ) . Avionics Application Software Standard Interface, Part 1 - Required Services , Mar. 2006 .

[2] AEEC (Airlines Electronic Engineering Committee ) . Avionics Application Software Standard Interface, Part 2 - Extended Services , Dec. 2008 .

[3] S. Bak , D. Chivukula , O. Adekunle , M. Sun , M. Caccamo , and L. Sha . The System-level Simplex Architecture for improved real-time embedded system safety . In 15th IEEE Real-Time and Embedded Tech. and Applications Symposium , pages 99 { 107 , Apr . 2009 .

[4] P. Bieber , E. Noulard , C. Pagetti , T. Planche , and F. Vialard . Preliminary design of future recon gurable IMA platforms . In Second Int. Workshop on Adaptive and Recon gurable Embedded Systems , pages 21 { 24 , Grenoble, France, Oct. 2009 .

[5] J. Carraca , R. C. Pinto , J. P. Craveiro , and J. Ru no. Information security in time- and space-partitioned architectures for aerospace systems . In Proc. 6th Simposio de Informatica (INForum 2014 ), pages 457 { 472 , Porto , Portugal, Sept. 2014 .

[6] J. P. Craveiro . Real-Time Scheduling in Multicore Time- and Space-Partitioned Architectures . PhD thesis , Universidade de Lisboa, Portugal, Aug. 2013 .

[7] J. P. Craveiro and J. Ru no. Adaptability support in time- and space-partitioned aerospace systems . In Proc. 2nd Int. Conf. on Adaptive and Self-adaptive Systems and Applic ., Lisbon, Portugal, Nov. 2010 .

[8] J. P. Craveiro and J. Ru no. Schedulability analysis in partitioned systems for aerospace avionics . In Proc. 15th IEEE Int. Conf. on Emerging Technologies and Factory Automation , Bilbao, Spain, Sept. 2010 .

[9] A. Crespo , I. Ripoll , and M. Masmano . Partitioned embedded architecture based on hypervisor: the XtratuM approach . In Proc. 8th European Dependable Computing Conf., Valencia , Spain, Apr. 2010 .

[10] DILIGENT. ZYBO Reference Manual , Feb. 2014 .

[11] A. Easwaran , I. Lee , O. Sokolsky , and S. Vestal . A compositional scheduling framework for digital avionics systems . In Proc. 15th IEEE Int. Conf. Embedded Real-Time Computing Systems and Applications , Beijing, China, Aug. 2009 .

[12] B. Ford , P. Bull , A. Grigg , L. Guan , and I. Phillips . Adaptive architectures for future highly dependable, real-time systems . In Proc. 7th Ann. Conf. on Systems Engineering Research , Loughborough, UK , Apr. 2009 .

[13] A. Kane . Runtime Monitoring for Safety-Critical Embedded Systems . PhD thesis , Carnegie Mellon University, USA, Feb. 2015 .

[14] Y. Lee , D. Kim , M. Younis , and J. Zhou . Partition scheduling in APEX runtime environment for embedded avionics software . In Proc. 5th Int. Conf. on Real-Time Computing Systems and Applications , pages 103 { 109 , Hiroshima , Japan, 1998 .

[15] V. Nguyen , S. Deeds-Rubin , T. Tan , and B. Boehm . A SLOC counting standard . In The 22nd Int. Ann. Forum on COCOMO and Systems/Software Cost Modelling , Los Angeles, USA, 2007 .

[16] On-Line Applications Research Corporation. RTEMS C User ' s Guide, 4.9.4 edition , 2010 .

[17] R. C. Pinto and J. Ru no. Towards non-invasive run-time veri cation of real-time systems . In 26th Euromicro Conf. on Real-Time Systems - WIP Session , pages 25 { 28 , Madrid, Spain, July 2014 .

[18] T. Reinbacher , M. Fugger , and J. Brauer . Runtime veri cation of embedded real-time systems . Formal Methods in System Design , 24 ( 3 ): 203 { 239 , 2014 .

[19] J. Rosa , J. P. Craveiro , and J. Ru no. Safe online recon guration of time- and space-partitioned systems . In Proc. 9th IEEE Int. Conf. on Industrial Informatics (INDIN 2011 ), Caparica, Lisbon, Portugal, July 2011 .

[20] J. Ru no, J . Craveiro, and P. Verissimo . Architecting robustness and timeliness in a new generation of aerospace systems . In A. Casimiro, R. de Lemos, and C. Gacek, editors, Architecting Dependable Systems VII , volume 6420 of LNCS . Springer, 2010 .

[21] J. Rushby . Partitioning in avionics architectures: Requirements, mechanisms and assurance . Technical Report NASA CR-1999-209347 , SRI International, California, USA, June 1999 .

[22] S. Santos , J. Ru no, T . Schoofs, C. Tatibana , and J. Windsor . A portable ARINC 653 standard interface . In Proc. 27th Digital Avionics Systems Conf., St . Paul, MN, USA, Oct. 2008 .

[23] M. Tafazoli . A study of on-orbit spacecraft failures . Acta Astronautica , 64 ( 2-3 ): 195 { 205 , 2009 .

[24] TSP Working Group. Avionics time and space partitioning user needs . Technical Note TEC-SW/ 09 -247/JW, ESA, Aug. 2009 .

[25] B. Vanek . Future trends in UAS avionics . In Proc. 10th Int. Symp. of Hungarian Researchers on Computational Intelligence and Informatics , Budapest, Hungary, Nov. 2009 .

[26] C. Watterson and D. He ernan. Runtime veri cation and monitoring of embedded systems . Software, IET , 1 ( 5 ): 172 { 179 , October 2007 .

[27] Wind River . Wind River VxWorks 653 Platform 2.4 and 2.5 , 2015 . Retrieved Jun 29, 2015 .