University of Illinois Urbana-Champaign

Compositional analysis of the effects of uncertainty on computations

Joshi, Keyur Parag

Content Files
JOSHI-DISSERTATION-2024.pdf

Permalink

https://hdl.handle.net/2142/124217

Description

Title
Compositional analysis of the effects of uncertainty on computations
Author(s)
Joshi, Keyur Parag
Issue Date
2024-03-29
Director of Research (if dissertation) or Advisor (if thesis)
Misailovic, Sasa
Doctoral Committee Chair(s)
Misailovic, Sasa
Committee Member(s)
  • Adve, Sarita
  • Mitra, Sayan
  • Filieri, Antonio
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
  • Program analysis
  • Uncertainty
  • Compositional analysis
Abstract
Modern computations must regularly interact with imprecise sensors, deal with hardware failures, and operate on incomplete or inaccurate input data. Developers may also resort to intentionally adding approximate algorithms and machine learning models to such computations in order to make them tractable. Uncertainty analyses provide developers with the means to ensure that uncertainty introduced into a computation in this manner does not lead to unwanted or dangerous consequences. However, developers regularly modify modern computations throughout their lifetime to fix bugs and add features. An uncertainty analysis can become prohibitively expensive if it must be run from scratch every time a developer modifies the computation. Compositional analyses of uncertainty, which analyze different components of a computation in isolation and then analyze the overall computation, would have a clear advantage in this scenario; when a computation is modified, it would not be necessary to re-analyze the unmodified components. While researchers have developed compositional analyses for testing a variety of other properties, there is less work on developing compositional and precise analyses of uncertainty. In this dissertation, I present my work which shows that composable uncertainty analyses can have precision close to that of monolithic, non-composable uncertainty analyses. First, I describe a statistical analysis of the accuracy of approximate randomized algorithm implementations and computations running on unreliable hardware. Second, I describe a composable analysis of uncertainty in autonomous vehicle systems. Third, I describe an analysis that calculates how recovery mechanisms can increase the reliability of critical sub-computations running in an unreliable environment. Lastly, I describe a composable analysis that determines how soft errors affect computations and selects sets of vulnerable instructions to protect. The availability of composable analyses of uncertainty will encourage developers to regularly test the effects of proposed changes on the uncertainty characteristics of modern computations, possibly as part of regression testing suites.
Graduation Semester
2024-05
Type of Resource
text
Handle URL
https://hdl.handle.net/2142/124217
Copyright and License Information
Copyright 2024 Keyur Parag Joshi
Identical To
https://hdl.handle.net/2142/124160

Owning Collections

Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois