Back to search

University of British Columbia

Coho : a verification tool for circuit verification by reachability analysis

Abstract

dc:description

COHO is a verification tool for systems modeled by nonlinear ordinary differential equations (ODEs). Verification is performed using reachability analysis. The reachable space is represented by projectagons which are the polyhedron described by their projection onto two dimensional subspace. COHO approximates nonlinear ODEs with linear differential inclusions to compute the reachable state. We re-engineer the COHO system to provide a robust implementation with a clear interface and well-organized structure. We demonstrate the soundness and robustness of our approach by applying it to several examples, including a three dimensional, non-linear systems for which previous version of COHO failed due to numerical stability problems. The correctness of COHO strongly depends on the accuracy, efficiency and robustness of the linear program solver that is used throughout the analysis. Our COHO linear program solver is implemented by integrating the Simplex algorithm with interval arithmetic based on the framework set up by Laza [Laz01]. For highly ill-conditioned problems, an approximation that is very close to the optimal result is computed by our algorithm. This results in a very small error bound that allows COHO to successfully verify interesting examples. This thesis also presents an algorithm to solve the problem of projecting the feasible region of a linear program onto two dimensional subspaces. This algorithm uses the COHO linear program solver for efficiency and accuracy. We derive an analytical upper bound for the error and present experimental results to show that the errors are negligible in practice.

Degree

thesis:*
Name thesis:degree_name
Master of Science - MSc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
2006

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Yan, Chao

Rights

dc:rights
Statement dc:rights
  • For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/18181

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Yan, Chao. Coho : a verification tool for circuit verification by reachability analysis. master's thesis, University of British Columbia, 2006. http://hdl.handle.net/2429/18181