Search Results

Documents authored by Bueno, Francisco


Document
A Framework for Verification and Debugging of Resource Usage Properties: Resource Usage Verification

Authors: Pedro Lopez-Garcia, Luthfi Darmawan, and Francisco Bueno

Published in: LIPIcs, Volume 7, Technical Communications of the 26th International Conference on Logic Programming (2010)


Abstract
We present a framework for (static) verification of general resource usage program properties. The framework extends the criteria of correctness as the conformance of a program to a specification expressing non-functional global properties, such as upper and lower bounds on execution time, memory, energy, or user defined resources, given as functions on input data sizes. A given specification can include both lower and upper bound resource usage functions, i.e., it can express intervals where the resource usage is supposed to be included in. We have defined an abstract semantics for resource usage properties and operations to compare the (approximated) intended semantics of a program (i.e., the specification) with approximated semantics inferred by static analysis. These operations include the comparison of arithmetic functions (e.g., polynomial, exponential or logarithmic functions). A novel aspect of our framework is that the static checking of assertions generates answers that include conditions under which a given specification can be proved or disproved. For example, these conditions can express intervals of input data sizes such that a given specification can be proved for some intervals but disproved for others. We have implemented our techniques within the Ciao/CiaoPP system in a natural way, so that the novel resource usage verification blends in with the CiaoPP framework that unifies static verification and static debugging (as well as run-time verification and unit testing).

Cite as

Pedro Lopez-Garcia, Luthfi Darmawan, and Francisco Bueno. A Framework for Verification and Debugging of Resource Usage Properties: Resource Usage Verification. In Technical Communications of the 26th International Conference on Logic Programming. Leibniz International Proceedings in Informatics (LIPIcs), Volume 7, pp. 104-113, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)


Copy BibTex To Clipboard

@InProceedings{lopezgarcia_et_al:LIPIcs.ICLP.2010.104,
  author =	{Lopez-Garcia, Pedro and Darmawan, Luthfi and Bueno, Francisco},
  title =	{{A Framework for Verification and Debugging of Resource Usage Properties: Resource Usage Verification}},
  booktitle =	{Technical Communications of the 26th International Conference on Logic Programming},
  pages =	{104--113},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-17-0},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{7},
  editor =	{Hermenegildo, Manuel and Schaub, Torsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICLP.2010.104},
  URN =		{urn:nbn:de:0030-drops-25889},
  doi =		{10.4230/LIPIcs.ICLP.2010.104},
  annote =	{Keywords: Program Verification and Debugging, Cost Analysis, Resource Usage Analysis, Complexity Analysis}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail