Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-17T00:51:07.214Z Has data issue: false hasContentIssue false

Interval-based resource usage verification by translation into Horn clauses and an application to energy consumption

Published online by Cambridge University Press:  11 May 2018

P. LOPEZ-GARCIA
Affiliation:
IMDEA Software Institute, Madrid, SpainSpanish Council for Scientific Research (CSIC), Madrid, Spain (e-mail: pedro.lopez@imdea.org)
L. DARMAWAN
Affiliation:
IMDEA Software Institute, Madrid, Spain (e-mail: luthfi.darmawan@imdea.org)
M. KLEMEN
Affiliation:
IMDEA Software Institute, Madrid, SpainUniversidad Politécnica de Madrid (UPM), Madrid, Spain (e-mails: maximiliano.klemen@imdea.org, umer.liqat@imdea.org)
U. LIQAT
Affiliation:
IMDEA Software Institute, Madrid, SpainUniversidad Politécnica de Madrid (UPM), Madrid, Spain (e-mails: maximiliano.klemen@imdea.org, umer.liqat@imdea.org)
F. BUENO
Affiliation:
Universidad Politécnica de Madrid (UPM), Madrid, Spain (e-mail: bueno@fi.upm.es)
M. V. HERMENEGILDO
Affiliation:
IMDEA Software Institute, Madrid, SpainUniversidad Politécnica de Madrid (UPM), Madrid, Spain (e-mail: manuel.hermenegildo@imdea.org)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Many applications require conformance with specifications that constrain the use of resources, such as execution time, energy, bandwidth, etc. We present a configurable framework for static resource usage verification where specifications can include data size-dependent resource usage functions, expressing both lower and upper bounds. Ensuring conformance with respect to such specifications is an undecidable problem. Therefore, to statically check such specifications, our framework infers the same type of resource usage functions, which safely approximate the actual resource usage of the program, and compares them against the specification. We review how this framework supports several languages and compilation output formats by translating them to an intermediate representation based on Horn clauses and using the configurability of the framework to describe the resource semantics of the input language. We provide a detailed formalization and extend the framework so that both resource usage specification and analysis/verification output can include preconditions expressing intervals for the input data sizes for which assertions are intended to hold, proved, or disproved. Most importantly, we also extend the classes of functions that can be checked. We also report on and provide results from an implementation within the Ciao/CiaoPP framework, as well as on a practical tool built by instantiating this framework for the verification of energy consumption specifications for imperative/embedded programs. Finally, we show as an example how embedded software developers can use this tool, in particular, for determining values for program parameters that ensure meeting a given energy budget while minimizing the loss in quality of service.

Information

Type
Original Article
Copyright
Copyright © Cambridge University Press 2018