Detecting problematic execution patterns through automatic kernel trace analysis

As multi-core processors, distributed systems and virtualization are gaining a larger share in the market, debugging production systems has become a more challenging task, especially when the occurring problems are not easily reproducible. The new architectural complexity introduced a large number of potential problems that need to be detected on live systems with adequate, efficient and scalable methodologies. By tracing the kernel of an operating system, performance bottlnecks, malicious activities, programming bugs and other kinds of problematic behavior could be accurately detected. Tracing consists in monitoring and logging relevant events occurring on live systems with a minimal performance impact and interference with the flow of execution. The generated trace is typically inspected remotely with no overhead on the system whatsoever. This work presents an automata-based approach for modeling patterns of undesired behavior using executable Finite State Machines. They are fed into an offline analyzer which efficiently and simultaneously checks for their occurrences even in traces of several gigabytes. The analyzer provides an Application Programming Interface offering essential services to the Finite State Machines. To our knowledge, this is the first attempt that relies on describing problematic patterns for kernel trace analysis.;The analyzer achieves a linear performance with respect to the trace size. The remaining factors impacting its performance are also discussed. The performance of the automata-based approach is compared with that of a dedicated implementation suggesting that the overhead of using Finite State Machines for execution and not just for modeling is acceptable especially in post-mortem analysis.;The implemented solution is highly parallelizable and may be ported for online pattern matching. The thesis concludes by suggesting a list of possible optimizations that would further improve the analyzer's performance.;The implemented patterns touch on several fields including security, software testing and performance debugging. The analysis results provide enough information to precisely identify the source of the problem. This was helpful to identify a suspicious code sequence in the Linux kernel that could generate a deadlock.