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.
소프트웨어 취약점은 많은 연구에도 불구하고 보안과 프라이버시를 저해하는 근본적인 원인으로 지속해서 보안 위협의 최전선에 있다. 동적 테스팅 기법은 이러한 소프트웨어 취약점을 찾는데 널리 쓰이고 있다. 이러한 동적 테스팅 기법은 두 가지 측면, 경로 탐색과 위반 감지에서 향상을 이룰 수 있다. 하지만 두 가지 측면 모두 확장성과 능력 면에서 상충된다. 이 학위 논문에서는 이러한 상충점을 분석하고 두 가지 새로운 근사 기법을 제시하여 확장성을 유지하면서 능력을 향상했다.
이 학위논문의 첫 번째 부분은 경로 탐색을 위한 자동화 기법에 초점을 두고 있다. 콘콜릭 실행은 실행 경로를 체계적인 방법으로 탐색하는 강력한 프로그램 분석 기법이다. 무작위성에 기반한 퍼징과 비교하여, 콘콜릭 실행은 복잡하고 엄격한 분기 조건으로 막힌 경로들을 탐색하는데 효율적이다. 하지만, 단점은 콘콜 릭 실행은 실제 실행보다 매우 느리다는 점이다. 성능 저하의 가장 큰 원인 중 하나는 콘콜릭 실행 엔진은 프로그램의 변수에 대한 심볼릭 표현을 유지하기 위해 명령어들을 해석해야 한다는 점이다. 이 문제를 해 결하기 위해, 우리는 명령어 해석을 동적 테인트 분석과 프로그램 합성 기법으로 치환하여 콘콜릭 실행을 근사하는 새로운 접근을 제안한다. 우리는 이 접근 방법이 기존의 기법에 비해 더 많은 경로를 탐색할 수 있음을 보였다.
학위논문의 두번 째 부분은 메모리 접근 위반을 감지하는 것에 초점을 맞추었다. 메모리 오류를 감지 하기 위한 다양한 접근 방법이 있지만, 감지능력과 확장성의 상충점이 있다. 감지 능력을 향상 시키기 위해, 우리는 무한한 주소 공간이라는 이상적인 특성을 근사하였다. 이 특성을 확장 가능한 영역에서 달성하기 위하여, 우리는 고유한 사용자 공간 메모리 할당 방법인 페이지 엘리어싱 기법을 제시한다. 페이지 엘리어싱 기법은 여러 가상 페이지들이 하나의 물리 페이지에 매핑하게 하여 가상 메모리는 최대한 활용하면서 물리 메모리 사용은 최소화 할 수 있게 한다. 우리는 이러한 접근방법이 같은 시간 동안 더 많은 버그를 찾을 수 있다는 것을 보였다.
