Promotor: Prof. Dr. H. Bos
Co-Promotor: Dr. C. Giuffrida
”Always on” mode is the norm rather than exception for modern software services. Financial services, telecommunications, transportation and logistics, business management, industry operations, medical and healthcare services – everything that defines our modern day life, highly depends on these always-on online services. The recent pandemic that the world unfortunately has had to face and overcome has only emphasized their importance and demonstrated their potential to keep the world running during its recovery, by enabling virtual connectivity [150, 70]. Evolution of both hardware and software systems through the past several decades has made this a reality. Our dependence on high availability online services is so high that their unplanned downtimes are known to cost millions [45, 7, 174, 48, 48] if not billions [181] of US dollars. In this fast-changing realm however, one trend has remained constant: despite decades of research on eliminating bugs from software, the dream of bug-free software remains elusive [122, 28]. Often, performance-oriented design objectives conflict with high resource requirements of heavy-weight bug elimination strategies. Faster software development cycles also impose practical restrictions on the time and other resources spent on thorough testing to eliminate bugs. So, eliminating software bugs is not an option. Can we mitigate the devastating effects that bugs can cause? In this thesis, we address this question and aim to make software survive their faults and keep running albeit perhaps with some service degradation. Memory errors form the Achilles’ heel of foundational software like operating systems, networking components, web servers, databases and runtime libraries that are written in unmanaged languages like C and C++ for performance reasons. Even today, buffer overflows, uninitialized memory accesses, use-after-free faults and their variants still rank very high in causing software crashes or, even worse, security vulnerabilities [162]. Attack 1 2 CHAPTER 1. INTRODUCTION ers subject a software service to malicious inputs, probing to look for existing vulnerabilities. Probes often take the form of mutating inputs to target software, repeatedly observing its crashes and faulty execution behaviors to identify its vulnerabilities. Then, they exploit them to leak sensitive information, corrupt its process memory and even remotely take control of its execution to introduce attacker-controlled malicious behaviors, or even worse, take control of its host environment [16, 129, 144, 72] and inflict catastrophy. Besides developer-driven testing efforts, over the years, bug elimination strategies have taken the form of static analysis, symbolic execution, dynamic analysis, fuzzing and formal verification. They apply checks that detect bad patterns of code in the target software and report details of the issues found. They help developers to analyze and make changes to the software to fix the reported issues. While they have proved themselves to be effective in finding many varieties of important bugs in software, each has its own inherent limitations. Static analysis techniques scan a software’s code base and help in uncovering many bugs, in addition to inserting useful assertions that prevent faulty or vulnerable executions of the software. However, complete lack of insight into the runtime nature of the software (for example, inputs, configurations, host environment, etc.) that can influence important characteristics viz., allocation and deallocation of memory, pointer-based code and data accesses and interactions with other processes, the operating system and hardware peripherals significantly diminishes their effectiveness in bug elimination. Symbolic execution methods devise ways to also include runtime influenced paths in analyzing a software. Besides being computation and memory intensive, they often quickly run into what is known as the path explosion problem [22, 32]. Consequently, they attempt to maximize gains in finding bugs by prioritizing and limiting the exploration to certain parts, depending on how they choose what is important. Instead of limiting to only analyze the code base, dynamic analysis and fuzzing techniques actually execute and monitor the runtime behavior of the target software for a variety of input combinations to find unacceptable behaviors. However, code coverage of the test suite that drives the executions limits which paths get tested, leaving out an unknown portion of its runtime behaviors still untested. For a much better degree of dependability, one can formally verify a software [124, 27, 128]. There are model checkers that compute all possible execution combinations and apply formal reasoning to report observed deviations from the input specification [96, 84]. Unfortunately, formal verification does not scale to large code bases. First, it requires formal verification experts to translate the target application implementation into a formal language like Coq [13], Isabelle [127], TLA+ [96] or PlusCal [97]. In addition, having to execute or compute all the execution behaviors simply does not 1.1. DEALING WITH FAULTS IN DEPLOYED SOFTWARE 3 Chapter 1 scale for large software with code bases easily spanning upwards of 100,000 lines of code. Further, fast software update cycles leave little opportunities for these techniques to be applied, which often require very long hours of expert attention or automated exploration [128]. In the end, despite our best efforts in software testing and analyses for eliminating bugs, a degree of uncertainty always lingers when it comes to dependability, security and availability of deployed software services.