<?xml version="1.0" encoding="UTF-8"?><?xml-stylesheet type="text/xsl" href="static/style.xsl"?><OAI-PMH xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd"><responseDate>2026-11-22T23:29:33Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/14876" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/14876</identifier><datestamp>2026-04-28T16:46:38Z</datestamp><setSpec>com_10012_9900</setSpec><setSpec>com_10012_1</setSpec><setSpec>col_10012_9908</setSpec><setSpec>col_10012_6</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:doc="http://www.lyncode.com/xoai" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="advisor">Rayside, Derek</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="advisor">Ganesh, Vijay</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="author">Babaee Cheshmeahmadrezaee, Reza</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2019-08-13T18:43:37Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2019-08-13T18:43:37Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2019-08-13</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2019-08-09</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/14876</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">Runtime Verification (RV) is the formal analysis of the execution of a system against some properties at runtime. RV is particularly useful for stochastic systems that have a non-zero probability of failure at runtime. The standard RV assumes constructing a monitor that checks only the currently observed execution of the system against the given properties. This dissertation proposes a framework for predictive RV, where the monitor instead checks the current execution with its finite extensions against some property. The extensions are generated using a prediction model, that is built based on execution samples randomly generated from the system. The thesis statement is that predictive RV for stochastic systems is feasible, effective, and useful. The feasibility is demonstrated by providing a framework, called Prevent, that builds a predictive monitor by using trained prediction models to finitely extend an execution path, and computing the probabilities of the extensions that satisfy or violate the given property. The prediction model is trained using statistical learning techniques from independent and identically distributed samples of system executions. The prediction is the result of a quantitative bounded reachability analysis on the product of the prediction model and the automaton specifying the property. The analysis results are computed offline and stored in a lookup table. At runtime the monitor obtains the state of the system on the prediction model based on the observed execution, directly or by approximation, and uses the lookup table to retrieve the computed probability that the system at the current state will satisfy or violate the given property within some finite number of steps. The effectiveness of Prevent is shown by applying abstraction when constructing the prediction model. The abstraction is on the observation space based on extracting the symmetry relation between symbols that have similar probabilities to satisfy a property. The abstraction may introduce nondeterminism in the final model, which is handled by using a hidden state variable when building the prediction model. We also demonstrate that, under the convergence conditions of the learning algorithms, the prediction results from the abstract models are the same as the concrete models. Finally, the usefulness of Prevent is indicated in real-world applications by showing how it can be applied for predicting rare properties, properties with very low but non-zero probability of satisfaction. More specifically, we adjust the training algorithm that uses the samples generated by importance sampling to generate the prediction models for rare properties without increasing the number of samples and without having a negative impact
on the prediction accuracy.</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso" lang="en">en</dim:field>
   <dim:field mdschema="dc" element="publisher" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Runtime verification</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Predictive runtime verification</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Black box system</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Abstraction</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Importance sampling</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Stochastic system</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Prediction model</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">Predictive Runtime Verification of Stochastic Systems</dim:field>
   <dim:field mdschema="dc" element="type" lang="en">Doctoral Thesis</dim:field>
   <dim:field mdschema="dc" element="pending">false</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="department" lang="en">Electrical and Computer Engineering</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="discipline" lang="en">Electrical and Computer Engineering</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="grantor" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="uws-etd" element="degree" lang="en">Doctor of Philosophy</dim:field>
   <dim:field mdschema="uws" element="contributor" qualifier="advisor">Rayside, Derek</dim:field>
   <dim:field mdschema="uws" element="contributor" qualifier="advisor">Ganesh, Vijay</dim:field>
   <dim:field mdschema="uws" element="contributor" qualifier="affiliation1" lang="en">Faculty of Engineering</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="city" lang="en">Waterloo</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="country" lang="en">Canada</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="province" lang="en">Ontario</dim:field>
   <dim:field mdschema="uws" element="typeOfResource" lang="en">Text</dim:field>
   <dim:field mdschema="uws" element="peerReviewStatus" lang="en">Unreviewed</dim:field>
   <dim:field mdschema="uws" element="scholarLevel" lang="en">Graduate</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>