Show simple item record

dc.contributor.advisorHuang, Jeff
dc.creatorRajagopalan, Arun Krishnakumar
dc.date.accessioned2016-07-08T15:17:37Z
dc.date.available2018-05-01T05:49:18Z
dc.date.created2016-05
dc.date.issued2016-05-03
dc.date.submittedMay 2016
dc.identifier.urihttp://hdl.handle.net/1969.1/157131
dc.description.abstractWhile concurrent programming is quickly gaining popularity lately, developing bug-free programs is still challenging. Although developers have a wide choice of race detection tools available, we have found that the majority of these techniques do not scale well and developers are often forced to balance precision with speed. Additionally, various practical issues force even precise race detectors to produce spurious warnings, defeating their purpose and burdening their users. We design and implement a novel race detection technique that is both fast and precise, even in the face of missing program source information. Towards this goal, we have developed two separate tools, TREE and RDIT, that respectively improve performance and precision over existing techniques. TREE, implemented in the RoadRunner framework, acts as a filter and sends through only those events that might add value to race detection while eliminating those events which are deemed redundant for this purpose. All the while, removing these redundant events does not affect its race detection capability. We have evaluated TREE against a whole set of standard benchmarks, including two large real-world applications. We have found that there exists a significant number of redundant events in all these applications and on an average, TREE saves somewhere between 15-25% of analysis time as compared to the state-of-the-art techniques. Meanwhile, our next tool, RDIT, is able to precisely detect races in programs with incomplete source information, generating no false positives. RDIT is also maximal in the sense that it detects a maximal set of true races from the observed incomplete trace. It is underpinned by a sound BarrierPair model that abstracts away the missing events by capturing the invocation data of their enclosing methods. By making the least conservative assumption that a missing method introduces synchronization only when its invocation data overlaps with other missing methods, and by formulating maximal thread causality as a set of logical constraints, RDIT guarantees to precisely detect races with maximal capability. We tested RDIT against seven real-world large concurrent systems and have detected dozens of true races with zero false alarm. Comparatively, existing algorithms such as Happens-Before, Causal-Precede, and Maximal-Causality, which are all known to be precise, were observed reporting hundreds of false alarms due to trace incompleteness.en
dc.format.mimetypeapplication/pdf
dc.language.isoen
dc.subjectbug detectionen
dc.subjectconcurrencyen
dc.subjectdebuggingen
dc.subjectdynamic analysisen
dc.subjectparallelismen
dc.subjectperformance analysisen
dc.subjectruntime monitoringen
dc.subjectsoftware engineeringen
dc.subjectredundancyen
dc.subjectdata raceen
dc.subjectmissing eventsen
dc.subjectprecise detectionen
dc.subjecthappens-beforeen
dc.subjectmaximal thread causalityen
dc.titleFast and Precise On-The-Fly Data Race Detectionen
dc.typeThesisen
thesis.degree.departmentComputer Science and Engineeringen
thesis.degree.disciplineComputer Scienceen
thesis.degree.grantorTexas A & M Universityen
thesis.degree.nameMaster of Scienceen
thesis.degree.levelMastersen
dc.contributor.committeeMemberWelch, Jennifer L
dc.contributor.committeeMemberJi, Jim
dc.type.materialtexten
dc.date.updated2016-07-08T15:17:37Z
local.embargo.terms2018-05-01
local.etdauthor.orcid0000-0001-9619-5970


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record