2 Search Results for "Botbol, Vincent"

Document
DOI: 10.4230/LIPIcs.CP.2025.40
An Efficient and Uniform CSP Solution Generator Generator

Authors: Ghiles Ziat and Martin Pépin

Published in: LIPIcs, Volume 340, 31st International Conference on Principles and Practice of Constraint Programming (CP 2025)

Abstract
Constraint-based random testing is a powerful technique which aims at generating random test cases to verify functional properties of a program. Its objective is to determine whether a function satisfies a given property for every possible input. This approach requires firstly defining the property to satisfy, then secondly to provide a "generator of inputs" able to feed the program with the inputs generated. Besides, function inputs often need to satisfy certain constraints to ensure the function operates correctly, which makes the crafting of such a generator a hard task. In this paper, we are interested in the problem of manufacturing a uniform and efficient generator for the solutions of a CSP. In order to do that, we propose a specialized solving method that produces a well-suited representation for random sampling. Our solving method employs a dedicated propagation scheme based on the hypergraph representation of a CSP, and a custom split heuristic called birdge-first that emphasizes the interests of our propagation scheme. The generators we build are general enough to handle a wide range of use-cases. They are moreover uniform by construction, iterative and self-improving. We present a prototype built upon the AbSolute constraint solving library and demonstrate its performances on several realistic examples.
Cite as

Ghiles Ziat and Martin Pépin. An Efficient and Uniform CSP Solution Generator Generator. In 31st International Conference on Principles and Practice of Constraint Programming (CP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 340, pp. 40:1-40:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ziat_et_al:LIPIcs.CP.2025.40,
  author =	{Ziat, Ghiles and P\'{e}pin, Martin},
  title =	{{An Efficient and Uniform CSP Solution Generator Generator}},
  booktitle =	{31st International Conference on Principles and Practice of Constraint Programming (CP 2025)},
  pages =	{40:1--40:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-380-5},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{340},
  editor =	{de la Banda, Maria Garcia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2025.40},
  URN =		{urn:nbn:de:0030-drops-239010},
  doi =		{10.4230/LIPIcs.CP.2025.40},
  annote =	{Keywords: Constraint Programming, Property-based Testing}
}
Document
DOI: 10.4230/LIPIcs.CP.2021.59
Automated Random Testing of Numerical Constrained Types

Authors: Ghiles Ziat, Matthieu Dien, and Vincent Botbol

Published in: LIPIcs, Volume 210, 27th International Conference on Principles and Practice of Constraint Programming (CP 2021)

Abstract
We propose an automated testing framework based on constraint programming techniques. Our framework allows the developer to attach a numerical constraint to a type that restricts its set of possible values. We use this constraint as a partial specification of the program, our goal being to derive property-based tests on such annotated programs. To achieve this, we rely on the user-provided constraints on the types of a program: for each function f present in the program, that returns a constrained type, we generate a test. The tests consists of generating uniformly pseudo-random inputs and checking whether f’s output satisfies the constraint. We are able to automate this process by providing a set of generators for primitive types and generator combinators for composite types. To derive generators for constrained types, we present in this paper a technique that characterizes their inhabitants as the solution set of a numerical CSP. This is done by combining abstract interpretation and constraint solving techniques that allow us to efficiently and uniformly generate solutions of numerical CSP. We validated our approach by implementing it as a syntax extension for the OCaml language.
Cite as

Ghiles Ziat, Matthieu Dien, and Vincent Botbol. Automated Random Testing of Numerical Constrained Types. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 59:1-59:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{ziat_et_al:LIPIcs.CP.2021.59,
  author =	{Ziat, Ghiles and Dien, Matthieu and Botbol, Vincent},
  title =	{{Automated Random Testing of Numerical Constrained Types}},
  booktitle =	{27th International Conference on Principles and Practice of Constraint Programming (CP 2021)},
  pages =	{59:1--59:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-211-2},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{210},
  editor =	{Michel, Laurent D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2021.59},
  URN =		{urn:nbn:de:0030-drops-153502},
  doi =		{10.4230/LIPIcs.CP.2021.59},
  annote =	{Keywords: Constraint Programming, Automated Random Testing, Abstract Domains, Constrained Types}
}
  • Refine by Type
  • 2 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2021

  • Refine by Author
  • 2 Ziat, Ghiles
  • 1 Botbol, Vincent
  • 1 Dien, Matthieu
  • 1 Pépin, Martin

  • Refine by Series/Journal
  • 2 LIPIcs

  • Refine by Classification
  • 1 Computing methodologies → Randomized search
  • 1 Software and its engineering → Dynamic analysis

  • Refine by Keyword
  • 2 Constraint Programming
  • 1 Abstract Domains
  • 1 Automated Random Testing
  • 1 Constrained Types
  • 1 Property-based Testing

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact