Compositional analysis of the effects of uncertainty on computations

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.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois Urbana-Champaign

Year dc:date

2024

Author dc:creator

• Joshi, Keyur Parag

Contributors dc:contributor

• Misailovic, Sasa
• Adve, Sarita
• Mitra, Sayan
• Filieri, Antonio

• Program Analysis
• Uncertainty
• Compositional Analysis

Statement dc:rights

• Copyright 2024 Keyur Parag Joshi

Language dc:language

eng

Handle dc:identifier

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

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/124160