DTA

Digital Theses Archive

 

Tesi etd-09092019-225750

Type of thesis
Dottorato
Author
BRISTOT DE OLIVEIRA, DANIEL
URN
etd-09092019-225750
Title
Automata-based Formal Analysis and Verification of the Real-Time Linux Kernel
Scientific disciplinary sector
ING-INF/05
Course
INGEGNERIA - Ph.D. Programme in Emerging Digital Technologies (EDT)
Committee
relatore Prof. CUCINOTTA, TOMMASO
Membro Prof. RIVALINO, MATIAS
Presidente Prof. LIPARI, GIUSEPPE
Membro DI NATALE, MARCO
Relatore CASTRO, MARCIO BASTOS
Keywords
  • Automata
  • Formal methods
  • Linux kernel
  • Real-time Systems
  • Runtime Verification
Exam session start date
;
Availability
completa
Abstract
Real-time systems are computing systems where the correct behavior does not depend only on the functional behavior, but also on the timing behavior. In the real-time scheduling theory, a system is an abstraction, modeled using a set of variables that describe the sole timing behavior of its components. Linux is an implementation of an OS, that nowadays supports some of the fundamental abstractions from the real-time scheduling theory. Despite all improvements of the last decade, classifying Linux as a RTOS is still a source of conflict between real-time Linux and scheduling communities. The central reasons for this conflict lie in the empirical analysis of the timing properties of Linux made by practitioners, as it is expected that the properties of a real-time system derive from a mathematical description of the behavior of the system. Generally, a rigorous set of proofs is required for any conclusion about the predictability of the runtime behavior of a real-time system. The gap between the real-time Linux and real-time theory roots in the Linux kernel complexity. The amount of effort required to understand all the constraints imposed on real-time tasks on Linux is not negligible. The challenge is then to describe such operations, using a level of abstraction that removes the complexity due to the in-kernel code. The description must use a formal format that facilitates the understanding of Linux dynamics for real-time researchers, without being too far from the way developers observe and improve Linux. Hence, to improve the real-time Linux runtime analysis and verification, this thesis presents a formal thread synchronization model for the PREEMPT_RT Linux kernel. This model is built upon the automata formalism, using a modular approach that enables the creation of a model based on a set of independent sub-systems and the specifications that define their synchronized behavior. The thesis also presents a viable modeling methodology, including the validation strategy and tooling that compares the model against the real execution of the system. This model is then used as the base for the creation of a runtime verification of the method for the Linux kernel. The runtime verification method uses automatic code generation from the model to facilitate the development of the monitoring system. Moreover, it uses the dynamic tracing features of Linux to enable on-the-fly verification of the system, at a low overhead. Finally, the formal modeling of the kernel behavior is used as an intermediary step, facilitating the understanding of the rules and properties that rule the timing behavior of Linux tasks. These properties are then used in the formal definition of the components and composition of the main metric used by the real-time Linux developers, the scheduling latency, in the same level of abstraction used by real-time researchers. The values for these variables are then measured and analyzed by a tool proposed in this thesis.
Files