Simon Value-Range Analysis of C Programs

Towards Proving the Absence of Buffer Overflow Vulnerabilities
1. Auflage 2010
ISBN: 978-1-84800-017-9
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 302 Seiten

Abu?erover?owoccurswheninputiswrittenintoamemorybu?erthatisnot large enough to hold the input. Bu?er over?ows may allow a malicious person to gain control over a computer system in that a crafted input can trick the defectiveprogramintoexecutingcodethatisencodedintheinputitself.They are recognised as one of the most widespread forms of security vulnerability, and many workarounds, including new processor features, have been proposed to contain the threat. This book describes a static analysis that aims to prove the absence of bu?er over?ows in C programs. The analysis is conservative in the sense that it locates every possible over?ow. Furthermore, it is fully automatic in that it requires no user annotations in the input program. Thekeyideaoftheanalysisistoinferasymbolicstateforeachp- gram point that describes the possible variable valuations that can arise at that point. The program is correct if the inferred values for array indices and pointer o?sets lie within the bounds of the accessed bu?er. The symbolic state consists of a ?nite set of linear inequalities whose feasible points induce a convex polyhedron that represents an approximation to possible variable valuations. The book formally describes how program operations are mapped to operations on polyhedra and details how to limit the analysis to those p- tionsofstructuresandarraysthatarerelevantforveri?cation.Withrespectto operations on string bu?ers, we demonstrate how to analyse C strings whose length is determined by anul character within the string.

Autoren/Hrsg.

Simon, Axel

Inhaltsverzeichnis

1;Preface;6
1.1;Target Audience;7
1.2;Acknowledgments;8
2;Contents;9
3;Contributions;14
4;List of Figures;16
5;1 Introduction;20
5.1;1.1 Technical Background;21
5.2;1.2 Value-Range Analysis;23
5.3;1.3 Analysing C;25
5.4;1.4 Soundness;26
5.5;1.5 Efficiency;30
5.6;1.6 Completeness;34
5.7;1.7 Related Tools;37
6;2 A Semantics for C;41
6.1;2.1 Core C;41
6.2;2.2 Preliminaries;46
6.3;2.3 The Environment;46
6.4;2.4 Concrete Semantics;50
6.5;2.5 Collecting Semantics;55
6.6;2.6 Related Work;60
7;Abstracting Soundly;62
7.1;3 Abstract State Space;63
7.1.1;3.1 An Introductory Example;64
7.1.2;3.2 Points-to Analysis;67
7.1.3;3.3 Numeric Domains;72
7.2;4 Taming Casting and Wrapping;87
7.2.1;4.1 Modelling the Wrapping of Integers;88
7.2.2;4.2 A Language Featuring Finite Integer Arithmetic;90
7.2.3;4.3 Polyhedral Analysis of Finite Integers;92
7.2.4;4.4 Implicit Wrapping of Polyhedral Variables;93
7.2.5;4.5 Explicit Wrapping of Polyhedral Variables;94
7.2.6;4.6 An Abstract Semantics for Sub C;99
7.2.7;4.7 Discussion;102
7.3;5 Overlapping Memory Accesses and Pointers;104
7.3.1;5.1 Memory as a Set of Fields;104
7.3.2;5.2 Access Trees;108
7.3.3;5.3 Mixing Values and Pointers;115
7.3.4;5.4 Relating Concrete and Abstract Domains;121
7.4;6 Abstract Semantics;126
7.4.1;6.1 Expressions and Simple Assignments;131
7.4.2;6.2 Assigning Structures;133
7.4.3;6.3 Casting, &-Operations, and Dynamic Memory;136
7.4.4;6.4 Inferring Fields Automatically;138
8;Ensuring Efficiency;140
8.1;7 Planar Polyhedra;141
8.1.1;7.1 Operations on Inequalities;143
8.1.2;7.2 Operations on Sets of Inequalities;145
8.2;8 The TVPI Abstract Domain;161
8.2.1;8.1 Principles of the TVPI Domain;162
8.2.2;8.2 Reduced Product between Bounds and Inequalities;166
8.2.3;8.3 Related Work;177
8.3;9 The Integral TVPI Domain;178
8.3.1;9.1 The Merit of Z-Polyhedra;179
8.3.2;9.2 Harvey’s Integral Hull Algorithm;181
8.3.3;9.3 Planar Z-Polyhedra and Closure;190
8.3.4;9.4 Related Work;195
8.4;10 Interfacing Analysis and Numeric Domain;197
8.4.1;10.1 Separating Interval from Relational Information;197
8.4.2;10.2 Inferring Relevant Fields and Addresses;199
8.4.3;10.3 Applying Widening in Fixpoint Calculations;204
9;Improving Precision;207
9.1;11 Tracking String Lengths;208
9.1.1;11.1 Manipulating Implicitly Terminated Strings;209
9.1.2;11.2 Incorporating String Buffer Analysis;220
9.1.3;11.3 Related Work;224
9.2;12 Widening with Landmarks;227
9.2.1;12.1 An Introduction to Widening/Narrowing;227
9.2.2;12.2 Revisiting the Analysis of String Buffers;230
9.2.3;12.3 Acquiring Landmarks;236
9.2.4;12.4 Using Landmarks at a Widening Point;237
9.2.5;12.5 Extrapolation Operator for Polyhedra;239
9.2.6;12.6 Related Work;241
9.3;13 Combining Points-to and Numeric Analyses;244
9.3.1;13.1 Boolean Flags in the Numeric Domain;246
9.3.2;13.2 Incorporating Boolean Flags into Points-to Sets;250
9.3.3;13.3 Practical Implementation;259
9.4;14 Implementation;268
9.4.1;14.1 Technical Overview of the Analyser;269
9.4.2;14.2 Managing Abstract Domains;271
9.4.3;14.3 Calculating Fixpoints;273
9.4.4;14.4 Limitations of the String Buffer Analysis;280
9.4.5;14.5 Proposed Future Refinements;285
9.5;15 Conclusion and Outlook;286
9.5.1;Conclusion;286
9.5.2;Outlook;287
10;A Core C Example;289
11;References;292
12;Index;304