La lecture en ligne est gratuite
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres
Télécharger Lire

Static code analysis in multi-threaded environments [Elektronische Ressource] / vorgelegt von Christian Ehrhardt

155 pages
Universität UlmFakultät für Mathematik und WirtschaftswissenschaftenInstitut für Angewandte InformationsverarbeitungStatic Code Analysis inMulti-Threaded EnvironmentsDissertationzur Erlangung des Doktorgrades Dr. rer. nat. der Fakultät fürMathematik und Wirtschaftswissenschaften der Universität Ulmvorgelegt vonChristian Ehrhardtaus Mutlangen26. Oktober 2007AAmtierender Dekan: Prof. Dr. Frank StehlingGutachter: Prof. Dr. Franz SchweiggertProf. Dr. Helmut PartschProf. Dr.-Ing. Stefan JähnichenDr. Johannes MayerTag der Promotion: 26. Oktober 2007Who can understand his errors?Cleanse thou me from secret faults.Psalms 19.12, The BiblePrefaceThe notion that software might contain errors dates back to the famous annotationsof Lady Ada Lovelace to the description of the Analytical Engine designed by CharlesBabbage[36] where she states: “Granted that the actual mechanism [of the AnalyticEngine] is unerring in its processes, the cards may give it wrong orders. This isunquestionably the case; but there is much less chance of error, and likewise far lessexpenditure of time and labour, where operations only, and the distribution of theseoperations, have to be made out, than where explicit numerical results are to beattained.”Despite Lady Lovelace’s assessment, errors in software (i.e. today’s equivalent ofcards that give wrong orders) have become a predominant concern in software devel-opment and software engineering.
Voir plus Voir moins

Universität Ulm
Fakultät für Mathematik und Wirtschaftswissenschaften
Institut für Angewandte Informationsverarbeitung
Static Code Analysis in
Multi-Threaded Environments
Dissertation
zur Erlangung des Doktorgrades Dr. rer. nat. der Fakultät für
Mathematik und Wirtschaftswissenschaften der Universität Ulm
vorgelegt von
Christian Ehrhardt
aus Mutlangen
26. Oktober 2007
AAmtierender Dekan: Prof. Dr. Frank Stehling
Gutachter: Prof. Dr. Franz Schweiggert
Prof. Dr. Helmut Partsch
Prof. Dr.-Ing. Stefan Jähnichen
Dr. Johannes Mayer
Tag der Promotion: 26. Oktober 2007Who can understand his errors?
Cleanse thou me from secret faults.
Psalms 19.12, The BiblePreface
The notion that software might contain errors dates back to the famous annotations
of Lady Ada Lovelace to the description of the Analytical Engine designed by Charles
Babbage[36] where she states: “Granted that the actual mechanism [of the Analytic
Engine] is unerring in its processes, the cards may give it wrong orders. This is
unquestionably the case; but there is much less chance of error, and likewise far less
expenditure of time and labour, where operations only, and the distribution of these
operations, have to be made out, than where explicit numerical results are to be
attained.”
Despite Lady Lovelace’s assessment, errors in software (i.e. today’s equivalent of
cards that give wrong orders) have become a predominant concern in software devel-
opment and software engineering. Nowadays, the vast majority of software engineers
and hackers alike believes that all sufficiently complex software has bugs. Solutions
that have been proposed to uncover bugs reach from testing on the one hand to
rigorous formal proofs of correctness on the other hand.
In this work we follow an intermediate approach that tries to use sound and
conservative static code analysis techniques to avoid certain classes of bugs without
having to conduct a full blown formal proof of correctness. The methods developed
in this work are tailored to concurrent systems where global data is shared between
all threads. While this requirement is not strictly necessary for the soundness of the
analysis we shall see that it greatly increases the accuracy. In this context accuracy
refers to the likelihood that a problem reported by the analysis is caused by an actual
bug in the software and not by an inadequacy of the analysis methods. The usefulness
of the methods presented will be supported by several case studies conducted on real
life software systems of significant size.
Nevertheless, I am convinced that in software engineering there is no Holy Grail
that software can gain eternal bug free life from. As a corollary this Holy Grail
cannot be expected to be found in this work. Thus, readers are encouraged to use
the methods described in this work to supplement but not to replace existing bug
prevention and software quality techniques.
12
Acknowledgments
This work has been developed at the Institute of Applied Information Processing at
the University of Ulm. I would like to express my gratitude to all my present and
formercolleaguesfortheworkingatmospherewhichhasalwaysbeenveryconstructive,
open, and friendly. This would not have been possible without the extraordinary
commitment of Prof. Dr. Franz Schweiggert, the director of the Institute, to his
employees. Likewise, this work would not have been possible without his guidance
and support. Thank you very much for always being there when needed.
Prof. Dr. Helmut Partsch has kindly agreed to report on this thesis which I am
very grateful for.
Regarding this work, many people have given helpful suggestions and constructive
criticism that has been very much appreciated. Especially, I am much obliged to Dipl.
Inf. Walter Guttmann and Dr. Johannes Mayer for valuable discussions. I would also
like to thank the latter for agreeing to reporting on this thesis.
Special thanks go to Dr. Andreas Borchert. He has always been open for indepth
discussions and I have learned a lot from him.
Apart from those already mentioned, I would like to thank Dr. Ingo Melzer for
proof reading and Dipl. Math. oec. Uta Phillip for proof reading and her love, faith,
and patience.
Last but not least, I would like to thank my parents for continued and insisting
encouragement and support.Contents
Preface 1
Contents 3
1 Introduction 7
1.1 Software Bugs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.1.1 Possible Consequences of Bugs . . . . . . . . . . . . . . . . . . 8
1.1.2 Reproducibility . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.1.3 Latency of Symptoms . . . . . . . . . . . . . . . . . . . . . . . 9
1.1.4 Probability of Discovery . . . . . . . . . . . . . . . . . . . . . . 10
1.1.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.1.6 Approach Used in this Work . . . . . . . . . . . . . . . . . . . 11
1.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.2.1 Targeted Generation of Test Cases . . . . . . . . . . . . . . . . 12
1.2.2 Proof of Correctness . . . . . . . . . . . . . . . . . . . . . . . . 12
1.2.3 Static Code Analysis . . . . . . . . . . . . . . . . . . . . . . . . 13
1.2.4 Partial Program Verification . . . . . . . . . . . . . . . . . . . 15
1.2.5 Model Checking . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.3 Outline of this Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2 Program Representation 19
2.1 Abstract Syntax Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2 Normalized Syntax Trees . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2.1 Declarations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2.2 Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.2.3 Simple Statements . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.2.4 Return Statement . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.2.5 Function Calls . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.2.6 Aggregate Statements . . . . . . . . . . . . . . . . . . . . . . . 26
2.3 Single Static Assignment Form . . . . . . . . . . . . . . . . . . . . . . 26
34 CONTENTS
2.4 Linking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.4.1 External Variables and Functions . . . . . . . . . . . . . . . . . 28
2.4.2 Type Declarations . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.4.3 Structure Field Declarations . . . . . . . . . . . . . . . . . . . . 30
2.5 Semantic Restrictions . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.5.1 Complete Normalized ASTs . . . . . . . . . . . . . . . . . . . . 30
2.5.2 Addresses of Objects . . . . . . . . . . . . . . . . . . . . . . . . 31
2.5.3 Effective Type and Aliasing . . . . . . . . . . . . . . . . . . . . 31
2.5.4 Field Declarations and Unions . . . . . . . . . . . . . . . . . . 33
2.5.5 Integer Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.5.6 Multi-Threading . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.5.7 Volatility of Global Data . . . . . . . . . . . . . . . . . . . . . 35
2.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3 Basic Analysis 39
3.1 AST Generation and Object Names . . . . . . . . . . . . . . . . . . . 39
3.2 Addressed Variables and Fields . . . . . . . . . . . . . . . . . . . . . . 40
3.3 Additional Return Values . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.4 Basic Blocks and the Control Flow Graph . . . . . . . . . . . . . . . . 42
3.5 Live Ranges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.6 Function Pointers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.6.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.6.2 Inclusion Graph . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.6.3 Generic Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.6.4 Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.6.5 Extension . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.7 Static Structure Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.7.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.7.2 Unaliased Memory . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4 Function Body Analysis 55
4.1 Predicates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.1.1 Specification of Predicates . . . . . . . . . . . . . . . . . . . . . 56
4.1.2 Multi-Threaded Programs . . . . . . . . . . . . . . . . . . . . . 58
4.2 Representing and Modifying Predicates . . . . . . . . . . . . . . . . . 59
4.2.1 Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.2.2 Copy on Write and Hashing . . . . . . . . . . . . . . . . . . . . 59
4.2.3 Modifying Predicates . . . . . . . . . . . . . . . . . . . . . . . . 60CONTENTS 5
4.3 Inspecting a Predicate . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
4.3.1 Range of a Variable . . . . . . . . . . . . . . . . . . . . . . . . 63
4.3.2 Bits of a Variable . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.3.3 Equality of Two Variables . . . . . . . . . . . . . . . . . . . . . 63
4.4 Binary Operations on Predicates . . . . . . . . . . . . . . . . . . . . . 63
4.4.1 Special Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.4.2 Equality of Two Predicates . . . . . . . . . . . . . . . . . . . . 64
4.4.3 Merging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4.4.4 Intersection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4.5 Predicates and Statements . . . . . . . . . . . . . . . . . . . . . . . . . 66
4.5.1 Pre- and Post-Predicates . . . . . . . . . . . . . . . . . . . . . 67
4.5.2 Per Function Predicate List . . . . . . . . . . . . . . . . . . . . 67
4.6 Predicate Transitions at Statements . . . . . . . . . . . . . . . . . . . 68
4.6.1 Assignments . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.6.2 Goto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.6.3 Conditional Expression . . . . . . . . . . . . . . . . . . . . . . 73
4.6.4 Switch Expression . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.6.5 Addresses of Global Variables . . . . . . . . . . . . . . . . . . . 74
4.7 Analysis Algorithm for a Block . . . . . . . . . . . . . . . . . . . . . . 75
4.7.1 Notational Conventions . . . . . . . . . . . . . . . . . . . . . . 77
4.7.2 Example: If Statement . . . . . . . . . . . . . . . . . . . . . . . 78
4.7.3 Example: While Loop . . . . . . . . . . . . . . . . . . . . . . . 78
4.8 Optimizations and Performance . . . . . . . . . . . . . . . . . . . . . . 78
4.8.1 Compacting of Pre-Sets . . . . . . . . . . . . . . . . . . . . . . 79
4.8.2 Simplifying Predicates . . . . . . . . . . . . . . . . . . . . . . . 79
4.8.3 Multi-Thread Ready Predicates . . . . . . . . . . . . . . . . . . 80
4.8.4 Caching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
4.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
5 Global Analysis 83
5.1 Function Call Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . 83
5.2 F Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
5.2.1 Initial States . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
5.2.2 Pre-Conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
5.3 Function Calls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
5.3.1 Checking of Function Call Pre-Conditions . . . . . . . . . . . . 90
5.3.2 Calculated Calls . . . . . . . . . . . . . . . . . . . . . . . . . . 90
5.4 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
5.5 Recursive Calls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 926 CONTENTS
5.5.1 Preprocessing of the Call Graph . . . . . . . . . . . . . . . . . 93
5.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
6 Analyzing Synchronization 99
6.1 Synchronization Primitives . . . . . . . . . . . . . . . . . . . . . . . . 99
6.1.1 Mutex Locks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
6.1.2 A Generic Lock Model . . . . . . . . . . . . . . . . . . . . . . . 100
6.1.3 Semaphores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
6.1.4 Read/Write Locks . . . . . . . . . . . . . . . . . . . . . . . . . 101
6.1.5 Lock-Free Synchronization . . . . . . . . . . . . . . . . . . . . . 102
6.2 Identifying Equal Locks . . . . . . . . . . . . . . . . . . . . . . . . . . 103
6.3 Locks and Predicates . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
6.3.1 Extended Predicates . . . . . . . . . . . . . . . . . . . . . . . . 105
6.3.2 Lock Specific Predicate Operations . . . . . . . . . . . . . . . . 108
6.3.3 Normal Predicate Operations and Locks . . . . . . . . . . . . . 110
6.4 Pointers to Locks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
6.4.1 Local Pointers to Locks . . . . . . . . . . . . . . . . . . . . . . 119
6.4.2 Additional Locking Functions . . . . . . . . . . . . . . . . . . . 121
6.4.3 Container Locks . . . . . . . . . . . . . . . . . . . . . . . . . . 121
6.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
7 Case Studies 123
7.1 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
7.2 Case Studies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
7.2.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
7.2.2 Time and Performance Measurements . . . . . . . . . . . . . . 125
7.3 Examples of Actual Bugs . . . . . . . . . . . . . . . . . . . . . . . . . 132
7.3.1 Random Number Pool . . . . . . . . . . . . . . . . . . . . . . . 132
7.3.2 Out of Memory Badness Function . . . . . . . . . . . . . . . . 132
7.3.3 NetBSD Bugs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
7.4 Problematic Program Constructs . . . . . . . . . . . . . . . . . . . . . 134
7.4.1 Function Pointers . . . . . . . . . . . . . . . . . . . . . . . . . . 135
7.4.2 Flags . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
7.4.3 Non-Static Fields . . . . . . . . . . . . . . . . . . . . . . . . . . 136
7.4.4 Complex Synchronization Semantics . . . . . . . . . . . . . . . 137
7.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
8 Summary and Perspective 139
Bibliography 143

Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin