Computing abstract distances in logic programs

Casso, Ignacio de and Morales Caballero, José Francisco and López Garcia, Pedro and Giacobazzi, Roberto and Hermenegildo, Manuel V. (2019). Computing abstract distances in logic programs. In: "29th International Symposium on Logic-Based Program Synthesis and Transformation ( LOPSTR 2019)", 8-10 Oct 2019, Oporto, Portugal. ISBN 978-3-030-45259-9. pp. 57-72. https://doi.org/10.1007/978-3-030-45260-5_4.

Description

Title: Computing abstract distances in logic programs
Author/s:
  • Casso, Ignacio de
  • Morales Caballero, José Francisco
  • López Garcia, Pedro
  • Giacobazzi, Roberto
  • Hermenegildo, Manuel V.
Item Type: Presentation at Congress or Conference (Article)
Event Title: 29th International Symposium on Logic-Based Program Synthesis and Transformation ( LOPSTR 2019)
Event Dates: 8-10 Oct 2019
Event Location: Oporto, Portugal
Title of Book: Logic-Based Program Synthesis and Transformation
Date: 2019
ISBN: 978-3-030-45259-9
Volume: 12042
Subjects:
Freetext Keywords: Abstract interpretation; Static analysis; Logic programming; Metrics; Distances; Complete lattices; Program semantics
Faculty: E.T.S. de Ingenieros Informáticos (UPM)
Department: Inteligencia Artificial
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (929kB) | Preview

Abstract

Abstract interpretation is a well-established technique for performing static analyses of logic programs. However, choosing the abstract domain, widening, fixpoint, etc. that provides the best precisioncost trade-off remains an open problem. This is in a good part because of the challenges involved in measuring and comparing the precision of different analyses. We propose a new approach for measuring such precision, based on defining distances in abstract domains and extending them to distances between whole analyses of a given program, thus allowing comparing precision across different analyses. We survey and extend existing proposals for distances and metrics in lattices or abstract domains, and we propose metrics for some common domains used in logic program analysis, as well as extensions of those metrics to the space of whole program analyses. We implement those metrics within the CiaoPP framework and apply them to measure the precision of different analyses on both benchmarks and a realistic program.

Funding Projects

TypeCodeAcronymLeaderTitle
Government of SpainTIN2015-67522-C3-1-RTRACESFundación IMDEA SoftwareTecnologías y herramientas para el desarrollo de software consciente de los recursos, correcto y eficiente (IMDEA)
Madrid Regional GovernmentP2018/TCS-4339BLOQUES-CMUnspecifiedContratos inteligentes y blockchains escalables y seguros mediante verificación y análisis

More information

Item ID: 62525
DC Identifier: http://oa.upm.es/62525/
OAI Identifier: oai:oa.upm.es:62525
DOI: 10.1007/978-3-030-45260-5_4
Official URL: https://link.springer.com/content/pdf/10.1007%2F978-3-030-45260-5_4.pdf
Deposited by: Biblioteca Facultad de Informatica
Deposited on: 01 May 2020 07:52
Last Modified: 01 May 2020 07:52
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM