Abstract
Computer intrusions can occur in various ways. Many of them occur by exploiting program flaws and
system configuration errors. Existing solutions that detects specific kinds of flaws are substantially
different from each other, so aggregate use of them may be incompatible and require substantial
changes in the current system and computing practice. Intrusion detection systems may not be the
answer either, because they are inherently inaccurate and susceptible to false positives/negatives.
This dissertation presents a taxonomy of security flaws that classifies program vulnerabilities
into finite number of error categories, and presents a security mechanism that can produce accurate
solutions for many of these error categories in a modular fashion. To be accurate, a solution should
closely match the characteristic of the target error category. To ensure this, we focus only on error
categories whose characteristics can be defined in terms of a violation of process integrity.
The thesis of this work is that the proposed approach produces accurate solutions for many error
categories. To prove the accuracy of produced solutions, we define the process integrity checking
approach and analyze its properties. To prove that this approach can cover many error categories,
we develop a classification of program security flaws and find error characteristics (in terms of a
process integrity) from many of these categories.
We implement proof-of-concept solutions for two most prevalent error categories, the buffer
overflow and the race condition, and analyze their accuracy and performance.
Contents
Contents
Abstract i
1 Introduction 1
1.1 Problem statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Process integrity checking approach . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4 Thesis statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.5 Dissertation outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2 Related work 7
2.1 Intrusion detection systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.1.1 Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2 Solutions for specific program flaws . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.1 Buffer overflow vulnerability . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.2 Race condition in the file name space . . . . . . . . . . . . . . . . . . . . . . 14
2.2.3 Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.3 Taxonomies of security flaws . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3.1 Research in Secured Operating Systems . . . . . . . . . . . . . . . . . . . . . 18
2.3.2 Protection analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
v
2.3.3 Classification by Neumann . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.3.4 Orthogonal Defect Classification . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.3.5 Classification by Landwehr et al. . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.3.6 Classification by Bishop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.3.7 Classification by Aslam, Krsul and Spafford . . . . . . . . . . . . . . . . . . . 23
2.3.8 Classification by Du and Mathur . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3.9 Classification by SecurityFocus . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.3.10 Classification of race condition . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.3.11 Limitation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3 Process integrity checking 27
3.1 The policy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.1.1 Identifying correctness relations . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.1.2 Deriving verification algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.1.3 Proving the thesis statement . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2 The mechanism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2.1 Obtaining process state information . . . . . . . . . . . . . . . . . . . . . . . 30
3.2.2 Compatibility of solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2.3 System library functions as checkpoints . . . . . . . . . . . . . . . . . . . . . 33
3.3 Contributions and novelty . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.4 Advantages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.5 Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4 Classification of program flaws 36
4.1 Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.2 The classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.2.1 Internal categories . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4.2.2 Leaf categories . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.3 Distribution of program flaws . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5 Buffer overflow vulnerability 57
5.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5.2.1 Stack smashing attack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5.2.2 Return-into-libc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
5.2.3 C++ virtual function pointer . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5.3 Property . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
5.4 The verification algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
5.4.1 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.5 Extending the correctness relation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
5.5.1 Protecting an arbitrary grouping of variables . . . . . . . . . . . . . . . . . . 71
5.5.2 Protecting a stack frame as a whole . . . . . . . . . . . . . . . . . . . . . . . 71
5.5.3 Implementation of the extension . . . . . . . . . . . . . . . . . . . . . . . . . 71
5.6 Experiments and measurements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
5.6.1 Time overhead . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
5.6.2 Space overhead . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
5.7 Accuracy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
6 Race condition in the file name space 76
6.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
6.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
6.2.1 Typical binding flaw . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
6.2.2 Binding flaw with multiple use operations . . . . . . . . . . . . . . . . . . . . 78
6.2.3 Temporary file race . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
vii
6.2.4 Binding flaw spanning multiple processes . . . . . . . . . . . . . . . . . . . . 79
6.3 Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
6.3.1 Stateless file operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
6.3.2 Vulnerable intervals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
6.4 The verification algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
6.4.1 Program contextual information . . . . . . . . . . . . . . . . . . . . . . . . . 83
6.4.2 Correctness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
6.4.3 Efficiency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
6.5 A reduced algorithm by relaxing the correctness relation . . . . . . . . . . . . . . . . 84
6.5.1 Relaxing the vulnerable interval . . . . . . . . . . . . . . . . . . . . . . . . . 84
6.5.2 Approximating the group of cooperating processes . . . . . . . . . . . . . . . 85
6.5.3 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
6.6 Experiments and measurements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
6.6.1 Space overhead . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
6.6.2 Time overhead . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
6.7 Discussions on the relaxation of the correctness relation . . . . . . . . . . . . . . . . 98
6.8 Accuracy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
7 Testing 101
7.1 Buffer overflow detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
7.1.1 A vulnerable program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
7.1.2 Exploit scenario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
7.1.3 Detection scenario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
7.2 Detection of race condition on the file name space . . . . . . . . . . . . . . . . . . . 103
7.2.1 A vulnerable program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
7.2.2 Exploit scenario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
7.2.3 Detection scenario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
8 Conclusions and future work 106
8.1 Summary of contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
A Generated buffer range-checking functions 109
B Program that exploits buffer overflow 111
C Experiment results of the race condition detection 113
Bibliography 116
Vita 127
