Peter Okech, School Of Computing, Nairobi, Kenya
Nicholas McGuire, OpenTech EDV Research GmbH, Bullendorf, Austria
Christof Fetzer, Systems Engineering Group, Technische Universität Dresden, Germany

In Linux, a program executes either in user or kernel context. The control flow of the program is determined by its input when executing in user space. There is only a limited set of valid inputs for any program and thus in the absence of faults, the path taken by the program is highly predictable. In contrast, the input space of the kernel is very large so it is expected that for any program executing in kernel context, there could be several possible code paths available to be taken during an execution instance. We set out to investigate the level of non-determinism in the execution path of an application in the Linux kernel. In our work, we define the path as the set of kernel functions that are called by a specific system call invoked from the user space by an application. The experiments involved running a simple program over a large number of iterations and tracing its execution in kernel space using the Ftrace tool. The trace output was then transferred to a PostgreSQL database for analysis. We report the early results of our work, focusing on tracing a single system call, the open() call. The distribution of the frequency of path occurrences has several peaks representing the common execution paths matching our expectations. Further analysis shows that preemption and interrupts have an effect both on the execution time and control flow through the kernel. The result of this preliminary work points to a strong possibility of divergence in state of program replicas due to temporal and path non-determinism in the application's kernel space. This inherent diversity of OS kernel state could be useful in the protection of replicated systems against residual faults in the execution platform.