Modelling and predicting extreme behavior in critical real-time systems with advanced statistics

Abstract

(English) Critical Real-Time Embedded Systems (CRTES) are used in domains like transportation (e.g. avionics, automotive, space, and railway), healthcare, and industrial machinery. This subset of embedded systems requires undergoing a stringent Validation & Verification (V&V) process before they are allowed to enter in operation since any misbehavior can result in harm of humans or even fatalities. Software timing behavior is a key element to cover in the V&V process, providing with evidence that software runs timely. Software timing analysis, in turn, requires deriving bounds to each application task’s execution time. These bounds are referred to as Worst-Case Execution Time (WCET) estimates. As CRTES implement more complex safety-related functionalities in every new product, more complex software and consequently more performant computing hardware is used to satisfy the high-performance requirements. The side effect, however, of using more complex hardware and software is challenging state-of-the-art software timing analysis techniques. Measurement-Based Probabilistic Timing Analysis (MBPTA) techniques have been proposed to handle such hardware and software complexity providing tight and trustworthy WCET bounds (estimates). Specifically, Extreme Value Theory (EVT) has been used to provide with models for the most extreme occurrences in form of a probabilistic distribution. The output of the timing model is referred as a probabilistic WCET (pWCET). However trustworthy, EVT models can be cumbersome to apply and they sometimes can be exceedingly pessimistic which adds extra cost into timing budgets. This thesis investigates MBPTA techniques and develops novel methodologies within this framework in three distinct fronts. Firstly, by improving the tightness of pWCET models on sky-high quantiles with two models. A first one that combines risk analysis with EVT for a safe and accurate pWCET. And a second one that introduces Markov’s Inequality to the pWCET estimation problem, which provides with trustworthy guarantees with less requirements for its correct application. Secondly, in order to boost the use of data coming from performance monitoring counters - increasingly used by MBPTA techniques to tighten estimates-, this thesis shows two mathematically-based ways of merging multiple disjointed readings based on order statistics and copula models. Finally, this thesis proposes a model for the contention of competing tasks, when the timing profile obtained is limited, that allows to provide with more extreme WCET scenarios based on the dependencies between tasks. Summarizing, this thesis pushes the state-of-the-art forward in the V&V methodologies for CRTES in the framework of MBPTA in terms of WCET estimation and data gathering.

(Español) Los Sistemas Críticos Embebidos en Tiempo Real (SCETR) se usan en ámbitos como el transporte (aviónica, automoción, ferrocarril, etc.), la sanidad y la industria. Este subconjunto de sistemas embebidos requiere un proceso de Validación y Verificación (VyV) antes de que se les permita entrar en funcionamiento,dado que un comportamiento erróneo puede provocar daños a los seres humanos o incluso víctimas mortales. El comportamiento temporal del software es un elemento clave que hay que cubrir en el proceso de VyV, ya que proporciona pruebas de que el software se ejecuta a tiempo. El análisis temporal del software, a su vez, requiere derivar límites al tiempo de ejecución de cada tarea de la aplicación. Estos límites se denominan estimaciones del Tiempo de Ejecución del Peor Caso (TEPC).

A medida que los SCETR implementan funcionalidades más complejas relacionadas con la seguridad en cada nuevo producto, se utiliza un software más complejo y un hardware ide computación de mayor rendimiento para satisfacer los requisitos de alto rendimiento. Sin embargo, el efecto secundario del uso de hardware y software más complejos es un reto para las técnicas de análisis temporal de software más avanzadas.

Se han propuesto técnicas de Análisis Temporal Probabilístico Basado en Mediciones (ATPBM) para manejar dicha complejidad de hardware y software, proporcionando límites (estimaciones) del TEPC ajustados y fiables. En concreto, se ha utilizado la Teoría de Valores Extremos (TVE) para proporcionar modelos para las ocurrencias más extremas en forma de distribución probabilística. El resultado del modelo de tiempo se denomina TEPC probabilístico (TEPCp). Sin embargo, aunque seguros, los modelos TVE pueden ser a veces excesivamente pesimistas, lo que añade un coste adicional a los presupuestos de temporización.

Esta tesis investiga las técnicas ATPBM y desarrolla metodologías novedosas dentro de este marco en tres frentes distintos. En primer lugar, mejorando el ajuste de los modelos TEPCp en los cuantiles altísimos con dos modelos. El primero combinará el análisis de riesgos con la TVE para obtener un TEPCp más seguro y preciso. El segundo introducirá la desigualdad de Markov en el problema de estimación del TEPCp, que proporciona garantías más seguras. En segundo lugar, para potenciar el uso de los datos procedentes de los contadores de monitorización del rendimiento, esta tesis muestra dos formas, basadas en las matemáticas, de fusionar múltiples lecturas disjuntas a partir de estadísticos de orden y modelos de cópula. Por último, esta tesis propone un modelo para la contención de tareas en competencia cuando el perfil de tiempos obtenido es limitado. Este método permite prever escenarios TEPC más extremos basados en las dependencias entre tareas.

Resumiendo, esta tesis impulsa el estado del arte en las metodologías de VyV para SCETR en el marco de ATPBM en términos de estimación de TEPC y recopilación de datos.