Fast Automatic Software Survivability
Promotor: Prof. Dr. H. Bos
Co-Promotor: D r. C. Giuffrida
”Always on” mode is the norm rather than ex ception for modern software services. Financial services, telecommuni cations, transportation and logistics, business management, industry operations, medical and healthcare services – everything that defin es our modern day life, highly depends on these always-on online serv ices. The recent pandemic that the world unfortunately has had to fac e and overcome has only emphasized their importance and demonstrated their potential to keep the world running during its recovery, by ena bling virtual connectivity [150, 70]. Evolution of both hardware and software systems through the past several decades has made this a rea lity. 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 re search on eliminating bugs from software, the dream of bug-free softw are remains elusive [122, 28]. Often, performance-oriented design obj ectives conflict with high resource requirements of heavy-weight bug elimination strategies. Faster software development cycles also impos e practical restrictions on the time and other resources spent on tho rough testing to eliminate bugs. So, eliminating software bugs is not an option. Can we mitigate the devastating effects that bugs can cau se? In this thesis, we address this question and aim to make software survive their faults and keep running albeit perhaps with some servi ce degradation. Memory errors form the Achilles’ heel of foundation al software like operating systems, networking components, web server s, databases and runtime libraries that are written in unmanaged lang uages like C and C++ for performance reasons. Even today, buffer over flows, uninitialized memory accesses, use-after-free faults and their variants still rank very high in causing software crashes or, even w orse, security vulnerabilities [162]. Attack 1 2 CHAPTER 1. INTRODUCT ION ers subject a software service to malicious inputs, probing to lo ok for existing vulnerabilities. Probes often take the form of mutati ng inputs to target software, repeatedly observing its crashes and fa ulty execution behaviors to identify its vulnerabilities. Then, they exploit them to leak sensitive information, corrupt its process memor y and even remotely take control of its execution to introduce attack er-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 st rategies 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 de tails of the issues found. They help developers to analyze and make c hanges to the software to fix the reported issues. While they have pr oved themselves to be effective in finding many varieties of importan t bugs in software, each has its own inherent limitations. Static ana lysis techniques scan a software’s code base and help in uncovering many bugs, in addition to inserting useful assertions that prevent f aulty or vulnerable executions of the software. However, complete lac k of insight into the runtime nature of the software (for example, in puts, configurations, host environment, etc.) that can influence impo rtant characteristics viz., allocation and deallocation of memory, po inter-based code and data accesses and interactions with other proces ses, the operating system and hardware peripherals significantly dimi nishes their effectiveness in bug elimination. Symbolic execution met hods devise ways to also include runtime influenced paths in analyzin g a software. Besides being computation and memory intensive, they of ten 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, dependin g on how they choose what is important. Instead of limiting to only a nalyze the code base, dynamic analysis and fuzzing techniques actuall y execute and monitor the runtime behavior of the target software for a variety of input combinations to find unacceptable behaviors. Howe ver, code coverage of the test suite that drives the executions limit s which paths get tested, leaving out an unknown portion of its runti me behaviors still untested. For a much better degree of dependabilit y, 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 specifi cation [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 languag e like Coq [13], Isabelle [127], TLA+ [96] or PlusCal [97]. In additi on, having to execute or compute all the execution behaviors simply d oes not 1.1. DEALING WITH FAULTS IN DEPLOYED SOFTWARE 3 Chapter 1 sca le 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 softwa re services.
DESCRIPTION: Promotor: Prof. Dr. H. Bos Co-Promotor: Dr. C. Giuffrida ”Always on” mode is the norm rather than exception for modern sof tware services. Financial services, telecommunications, transportatio n and logistics, business management, industry operations, medical an d healthcare services – everything that defines our modern day life , highly depends on these always-on online services. The recent pande mic that the world unfortunately has had to face and overcome has onl y emphasized their importance and demonstrated their potential to kee p the world running during its recovery, by enabling virtual connecti vity [150, 70]. Evolution of both hardware and software systems throu gh the past several decades has made this a reality. Our dependence o n high availability online services is so high that their unplanned d owntimes are known to cost millions [45, 7, 174, 48, 48] if not billi ons [181] of US dollars. In this fast-changing realm however, one tre nd has remained constant: despite decades of research on eliminating bugs from software, the dream of bug-free software remains elusive [1 22, 28]. Often, performance-oriented design objectives conflict with high resource requirements of heavy-weight bug elimination strategies . Faster software development cycles also impose practical restrictio ns on the time and other resources spent on thorough testing to elimi nate bugs. So, eliminating software bugs is not an option. Can we mit igate 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 opera ting systems, networking components, web servers, databases and runti me libraries that are written in unmanaged languages like C and C++ f or performance reasons. Even today, buffer overflows, uninitialized m emory accesses, use-after-free faults and their variants still rank v ery high in causing software crashes or, even worse, security vulnera bilities [162]. Attack 1 2 CHAPTER 1. INTRODUCTION ers subject a soft ware service to malicious inputs, probing to look for existing vulner abilities. Probes often take the form of mutating inputs to target so ftware, repeatedly observing its crashes and faulty execution behavio rs to identify its vulnerabilities. Then, they exploit them to leak s ensitive information, corrupt its process memory and even remotely ta ke control of its execution to introduce attacker-controlled maliciou s behaviors, or even worse, take control of its host environment [16, 129, 144, 72] and inflict catastrophy. Besides developer-driven test ing efforts, over the years, bug elimination strategies have taken th e form of static analysis, symbolic execution, dynamic analysis, fuzz ing and formal verification. They apply checks that detect bad patter ns of code in the target software and report details of the issues fo und. 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, ea ch has its own inherent limitations. Static analysis techniques scan a software’s code base and help in uncovering many bugs, in additio n to inserting useful assertions that prevent faulty or vulnerable ex ecutions 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 d ata accesses and interactions with other processes, the operating sys tem and hardware peripherals significantly diminishes their effective ness in bug elimination. Symbolic execution methods devise ways to al so include runtime influenced paths in analyzing a software. Besides being computation and memory intensive, they often quickly run into w hat is known as the path explosion problem [22, 32]. Consequently, th ey attempt to maximize gains in finding bugs by prioritizing and limi ting the exploration to certain parts, depending on how they choose w hat 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 co mbinations to find unacceptable behaviors. However, code coverage of the test suite that drives the executions limits which paths get test ed, leaving out an unknown portion of its runtime behaviors still unt ested. For a much better degree of dependability, one can formally ve rify a software [124, 27, 128]. There are model checkers that compute all possible execution combinations and apply formal reasoning to re port observed deviations from the input specification [96, 84]. Unfor tunately, formal verification does not scale to large code bases. Fir st, it requires formal verification experts to translate the target a pplication implementation into a formal language like Coq [13], Isabe lle [127], TLA+ [96] or PlusCal [97]. In addition, having to execute or compute all the execution behaviors simply does not 1.1. DEALING W ITH FAULTS IN DEPLOYED SOFTWARE 3 Chapter 1 scale for large software with code bases easily spanning upwards of 100,000 lines of code. Fur ther, fast software update cycles leave little opportunities for thes e techniques to be applied, which often require very long hours of ex pert attention or automated exploration [128]. In the end, despite ou r best efforts in software testing and analyses for eliminating bugs, a degree of uncertainty always lingers when it comes to dependabilit y, security and availability of deployed software services. Fast Auto matic Software Survivability END:VEVENT END:VCALENDAR