Scalable path exploration and memory error detection for efficient vulnerability discovery

Abstract

Despite decades of research, software vulnerabilities continue to be at the forefront of security threats and root causes that harm security and privacy. Dynamic testing has been widely used for finding vulnerabilities in software. There are two main aspects that can be enhanced for dynamic testing: (a) exploring paths and (b) detecting violation. However, both aspects have a trade-off between scalability and capability. This dissertation explores the trade-off and opts for capability through two new approximation techniques. The first part of this thesis focuses on automated testing techniques for exploring paths. Concolic execution is a powerful program analysis technique for exploring execution paths in a systematic manner. Compared to random mutational-based fuzzing, concolic execution is efficient for exploring paths that are guarded by complex and tight branch conditions (e.g., $a*b = = 0xdeadbeef$). However, the drawback is that concolic execution is much slower than native execution. One major source of the slowness is that concolic execution engines have to interpret instructions to maintain the symbolic expression of program variables. To address this problem, we propose a new approach for approximated concolic execution which replaces the interpretations with dynamic taint analysis and program synthesis techniques. We show that our approach can achieve more coverage than state-of-the-art techniques. The second part of the thesis focuses on detecting memory access violations. There have been several approaches to detect memory bugs. However, There is a trade-off between capability and scalability. To enhance detection capability, we approximated an ideal property, called an infinite address space. To achieve the property with scalable resource usage, we propose a novel user-space memory allocation mechanism, called page aliasing which maps multiple virtual pages to a single physical page. Page aliasing allows full utilization of virtual memory, but minimized physical memory use. We show that our approach can detect significantly more bugs with the same amount of time.