Pasar al contenido principal

METODOS RIGUROSOS PARA EL DESARROLLO DE SISTEMAS SOFTWARE DE CALIDAD Y FIABILIDAD CERTIFICADAS (SUBPROYECTO IMDEA)

PID2019-108528RB-C21

•
Nombre agencia financiadora Agencia Estatal de Investigación
Acrónimo agencia financiadora AEI
Programa Programa Estatal de I+D+i Orientado a los Retos de la Sociedad
Convocatoria Proyectos de I+D+i (Generación de Conocimiento y Retos Investigación)
Año convocatoria 2019
Plan Estatal 2017-2020 Plan Estatal de Investigación Científica y Técnica y de Innovación
Centro beneficiario FUNDACION IMDEA SOFTWARE

Resultados relacionados

Resultados totales (Incluyendo duplicados): 1
Encontrada(s) 1 página(s)

DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Contribución de congreso (ConferenceOutput)

An Order Theory Framework of Recurrence Equations for Static Cost Analysis – Dynamic Inference of Non-Linear Inequality Invariants

  • Rustenholz, Louis
  • López-García, Pedro
  • Morales, J.F.
  • Hermenegildo, Manuel V.
Static Analysis, 31st International Symposium, SAS 2024, Pasadena, CA, USA, October 20–22, 2024, Recurrence equations have played a central role in static cost analysis, where they can be viewed as abstractions of programs and used to infer resource usage information without actually running the programs with concrete data. Such information is typically represented as functions of input data sizes. More generally, recurrence equations have been increasingly used to automatically obtain non-linear numerical invariants. However, state-of-the-art recurrence solvers and cost analysers suffer from serious limitations when dealing with the (complex) features of recurrences arising from cost analyses. We address this challenge by developing a novel order-theoretical framework where recurrences are viewed as operators and their solutions as fixpoints, which allows leveraging powerful pre/postfixpoint search techniques. We prove useful properties and provide principles and insights that enable us to develop techniques and combine them to design new solvers. We have also implemented and experimentally evaluated an optimisation-based instantiation of the proposed approach. The results are quite promising: our prototype outperforms state-of-the-art cost analysers and recurrence solvers, and can infer tight non-linear lower/upper bounds, in a reasonable time, for complex recurrences representing diverse program behaviours., This work has been partially supported by MICINN projects PID2019-108528RB-C21 ProCode, TED2021-132464B-I00 PRODIGY, and FJC2021- 047102-I, and the Tezos foundation, Peer reviewed