Conformance Testing and Error Explanation for Software Models

Error explanation addresses the question of how to correct faults. Many heuristics have been proposed, but there has been little effort to characterize the complexity of the problem. Because this is a vital part of any verification endeavor, we analyze the complexity of the most popular error explanation heuristics as a function of the program model. We establish the hardness of error explanation according to one heuristic via an interesting reduction from the well-known hard problem of determining the smallest deterministic finite automaton that is consistent with a given sample of positively and negatively labeled inputs. We also prove that error explanation based on the second heuristic is tractable for several models that capture program behavior.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2015

Author dc:creator

• Kumar, Viraj

Contributors dc:contributor

• Viswanathan, Mahesh

• Computer Science

Language dc:language

eng

Identifier

(MiAaPQ)AAI3290282

OAI identifier oai:identifier

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