Compositional analysis of the effects of uncertainty on computations

Joshi, Keyur Parag

Permalink

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

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 at 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

Thesis

Copyright and License Information

Copyright 2024 Keyur Parag Joshi

Owning Collections