Pasar al contenido principal

Resultados relacionados

Resultados totales (Incluyendo duplicados): 3
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
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

Hiord# : An Approach to the Specification and Verification of Higher-Order (C)LP Programs

  • Ciccalè, Marco
  • Jurjo-Rivas, Daniel
  • Morales, José F.
  • López-García, Pedro
  • Hermenegildo, Manuel
Higher-order constructs enable more expressive and concise code by allowing procedures to be parameterized by other procedures. Assertions allow expressing partial program specifications, which can be verified either at compile time (statically) or run time (dynamically). In higher- order programs, assertions can also describe higher-order arguments. While in the context of (constraint) logic programming ((C)LP), run-time verification of higher-order assertions has received some attention, compile-time verification remains relatively unexplored. We propose a novel approach for statically verifying higher-order (C)LP programs with higher-order assertions. Although we use the Ciao assertion language for illustration, our approach is quite general, and we believe is applicable to similar contexts. Higher-order arguments are described using predicate properties – a special kind of property which exploits the (Ciao) assertion language. We refine the syntax and semantics of these properties and introduce an abstract criterion to determine conformance to a predicate property at compile time, based on a semantic order relation comparing the predicate property with the predicate assertions. We then show how to handle these properties using an abstract interpretation-based static analyzer for programs with first-order assertions by reducing predicate properties to first-order properties. Finally, we report on a prototype implementation and evaluate it through various examples within the Ciao system., Partially funded by MICIU projects CEX2024-001471-M María de Maeztu and TED2021-132464B-I00 PRODIGY , as well as by the Tezos foundation. We would also like to thank the anonymous reviewers for their very useful and constructive feedback., Peer reviewed
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

Checkification: A Practical Approach for Testing Static Analysis Truths

  • Ferreiro, Daniela
  • Casso, Ignacio
  • Morales, José F.
  • López-García, Pedro
  • Hermenegildo, Manuel V.
38 páginas, 1 figura, 7 tablas, Static analysis is an essential component of many modern software development tools. Unfortunately, the ever-increasing complexity of static analyzers makes their coding error-prone. Even analysis tools based on rigorous mathematical techniques, such as abstract interpretation, are not immune to bugs. Ensuring the correctness and reliability of software analyzers is crit- ical if they are to be inserted in production compilers and development environments. While compiler validation has seen notable success, formal validation of static analysis tools remains relatively unexplored. In this paper we present checkification, a simple, automatic method for testing static analyzers. Broadly, it consists in checking, over a suite of benchmarks, that the properties inferred statically are satisfied dynamically. The main advantage of our approach lies in its simplicity, which stems directly from framing it within the Ciao assertion-based validation framework, and its blended static/dynamic assertion checking approach. We demonstrate that in this setting, the analysis can be tested with little effort by combining the following compo- nents already present in the framework: 1) the static analyzer , which outputs its results as the original program source with assertions interspersed; 2) the assertion run-time checking mech- anism, which instruments a program to ensure that no assertion is violated at run time; 3) the random test case generator , which generates random test cases satisfying the properties present in assertion preconditions; and 4) the unit-test framework , which executes those test cases. We have applied our approach to the CiaoPP static analyzer, resulting in the identification of many bugs with reasonable overhead. Most of these bugs have been either fixed or confirmed, helping us detect a range of errors not only related to analysis soundness but also within other aspects of the framework., Partially funded by MICINN projects PID2019-108528RB-C21 ProCode, TED2021- 132464B-I00 PRODIGY , and FJC2021-047102-I, and by the Tezos foundation. We would also like to thank the anonymous reviewers for their very useful feedback. This paper is an extended version of our previous work published in LOPSTR’20, Peer reviewed