Nadjib Lazaar

JAIR Journal 2025 Journal Article

A Query-Based Constraint Acquisition Approach for Enhanced Precision in Program Precondition Inference

• Grégoire Menguy
• Sébastien Bardin
• Arnaud Gotlieb
• Nadjib Lazaar

Program annotations in the form of function pre/postconditions play a crucial role in various software engineering and program verification tasks. However, the frequent unavailability of these annotations necessitates manual retrofitting. This paper shows how constraint acquisition, a learning framework derived from constraint programming and version space learning, can be extended for automatically inferring program preconditions. Our approach performs this inference in a black-box manner through automatic query generation and input-output observations of program executions. We introduce PreCA, the first-ever precondition inference framework leveraging query-based constraint acquisition. Notably, we specialize PreCA to handle memory-related preconditions on binary code, which pose significant challenges in data and information management systems. In contrast to prior black-box techniques, PreCA provides well-defined guarantees. Specifically, it employs a sound and complete method to generate preconditions consistent with all the observed input-output relationships of the program. Furthermore, empirical evaluations on our benchmark demonstrate that PreCA outperforms the results of state-of-the-art approaches, delivering comparable or superior results in 5s, as opposed to the 1-hour runtime of existing approaches on identical machines. We also present two successful use cases from the standard libc and the mbedtls cryptographic library. PreCA notably infers for the former one a more precise precondition than specified in the documentation.

AIJ Journal 2024 Journal Article

Corrigendum to “Learning constraints through partial queries” [Artificial Intelligence 319 (2023) 103896]

• Christian Bessiere
• Clément Carbonnel
• Anton Dries
• Emmanuel Hebrard
• George Katsirelos
• Nadjib Lazaar
• Nina Narodytska
• Claude-Guy Quimper

JAIR Journal 2024 Journal Article

Query-driven Qualitative Constraint Acquisition

• Mohamed-Bachir Belaid
• Nassim Belmecheri
• Arnaud Gotlieb
• Nadjib Lazaar
• Helge Spieker

Many planning, scheduling or multi-dimensional packing problems involve the design of subtle logical combinations of temporal or spatial constraints. Recently, we introduced GEQCA-I, which stands for Generic Qualitative Constraint Acquisition, as a new active constraint acquisition method for learning qualitative constraints using qualitative queries. In this paper, we revise and extend GEQCA-I to GEQCA-II with a new type of query, universal query, for qualitative constraint acquisition, with a deeper query-driven acquisition algorithm. Our extended experimental evaluation shows the efficiency and usefulness of the concept of universal query in learning randomly-generated qualitative networks, including both temporal networks based on Allen’s algebra and spatial networks based on region connection calculus. We also show the effectiveness of GEQCA-II in learning the qualitative part of real scheduling problems.

KR Conference 2023 Conference Paper

Active Disjunctive Constraint Acquisition

• Grégoire Menguy
• Sébastien Bardin
• Nadjib Lazaar
• Arnaud Gotlieb

Constraint acquisition (CA) is a method for learning users' concepts by representing them as a conjunction of constraints. While this approach works well for many combinatorial problems over finite domains, some applications require the acquisition of disjunctive constraints, possibly coming from logical implications or negations. In this paper, we propose the first CA algorithm tailored to the automatic inference of disjunctive constraints, named DCA. A key ingredient there, is to build upon the computation of maximal satisfiable subsets. We demonstrate experimentally that DCA is faster and more effective than traditional CA with added disjunctive constraints, even for ultra-metric constraints with up to 5 variables. We also apply DCA to precondition acquisition in software verification, where it outperforms the previous CA-based approach PreCA, being 2. 5 times faster. Specifically, in our evaluation DCA infers more preconditions in just 5 minutes than PreCA does in an hour, without requiring prior knowledge about disjunction size. Our results demonstrate the potential of DCA for improving the efficiency and scalability of constraint acquisition in the disjunctive case, enabling a wide range of novel applications.

AIJ Journal 2023 Journal Article

Learning constraints through partial queries

• Christian Bessiere
• Clément Carbonnel
• Anton Dries
• Emmanuel Hebrard
• George Katsirelos
• Nadjib Lazaar
• Nina Narodytska
• Claude-Guy Quimper

Learning constraint networks is known to require a number of membership queries exponential in the number of variables. In this paper, we learn constraint networks by asking the user partial queries. That is, we ask the user to classify assignments to subsets of the variables as positive or negative. We provide an algorithm, called QuAcq2, that, given a negative example, elucidates a constraint of the target network in a number of queries logarithmic in the size of the example. The whole constraint network can then be learned with a polynomial number of partial queries. We give information theoretic lower bounds for learning some simple classes of constraint networks and show that our generic algorithm is optimal in some cases. We provide a version of QuAcq2 with a cutoff mechanism that controls the time to generate a query. Our experiments illustrate the good behavior of QuAcq2 in practice, especially in the case where QuAcq2 is executed to learn the missing constraints in a partially filled constraint model. Our experiments also show that QuAcq2 requires significantly fewer queries to learn a network than its predecessor QuAcq1.

IJCAI Conference 2022 Conference Paper

Automated Program Analysis: Revisiting Precondition Inference through Constraint Acquisition

• Grégoire Menguy
• Sébastien Bardin
• Nadjib Lazaar
• Arnaud Gotlieb

Program annotations under the form of function pre/postconditions are crucial for many software engineering and program verification applications. Unfortunately, such annotations are rarely available and must be retrofit by hand. In this paper, we explore how Constraint Acquisition (CA), a learning framework from Constraint Programming, can be leveraged to automatically infer program preconditions in a black-box manner, from input-output observations. We propose PreCA, the first ever framework based on active constraint acquisition dedicated to infer memory-related preconditions. PreCA overpasses prior techniques based on program analysis and formal methods, offering well-identified guarantees and returning more precise results in practice.

AAAI Conference 2022 Conference Paper

GEQCA: Generic Qualitative Constraint Acquisition

• Mohamed-Bachir Belaid
• Nassim Belmecheri
• Arnaud Gotlieb
• Nadjib Lazaar
• Helge Spieker

Many planning, scheduling or multi-dimensional packing problems involve the design of subtle logical combinations of temporal or spatial constraints. On the one hand, the precise modelling of these constraints, which are formulated in various relation algebras, entails a number of possible logical combinations and requires expertise in constraint-based modelling. On the other hand, active constraint acquisition (CA) has been used successfully to support non-experienced users in learning conjunctive constraint networks through the generation of a sequence of queries. In this paper, we propose GEQCA, which stands for Generic Qualitative Constraint Acquisition, an active CA method that learns qualitative constraints via the concept of qualitative queries. GEQCA combines qualitative queries with time-bounded path consistency (PC) and background knowledge propagation to acquire the qualitative constraints of any scheduling or packing problem. We prove soundness, completeness and termination of GEQCA by exploiting the jointly exhaustive and pairwise disjoint property of qualitative calculus and we give an experimental evaluation that shows (i) the efficiency of our approach in learning temporal constraints and, (ii) the use of GEQCA on real scheduling instances.

AAAI Conference 2021 Conference Paper

Parallel Constraint Acquisition

• Nadjib Lazaar

Constraint acquisition systems assist the non-expert user in modelling her problem as a constraint network. QUACQ is a sequential constraint acquisition algorithm that generates queries as (partial) examples to be classified as positive or negative. The drawbacks are that the user may need to answer a great number of such examples, within a significant waiting time between two examples, to learn all the constraints. In this paper, we propose PACQ, a portfolio-based parallel constraint acquisition system. The design of PACQ benefits from having several users sharing the same target problem. Moreover, each user is involved in a particular acquisition session, opened in parallel to improve the overall performance of the whole system. We prove the correctness of PACQ and we give an experimental evaluation that shows that our approach improves on QUACQ.

IJCAI Conference 2019 Conference Paper

Constraint Programming for Mining Borders of Frequent Itemsets

• Mohamed-Bachir Belaid
• Christian Bessiere
• Nadjib Lazaar

Frequent itemset mining is one of the most studied tasks in knowledge discovery. It is often reduced to mining the positive border of frequent itemsets, i. e. maximal frequent itemsets. Infrequent itemset mining, on the other hand, can be reduced to mining the negative border, i. e. minimal infrequent itemsets. We propose a generic framework based on constraint programming to mine both borders of frequent itemsets. One can easily decide which border to mine by setting a simple parameter. For this, we introduce two new global constraints, FREQUENTSUBS and INFREQUENTSUPERS, with complete polynomial propagators. We then consider the problem of mining borders with additional constraints. We prove that this problem is coNP-hard, ruling out the hope for the existence of a single CSP solving this problem (unless coNP ⊆ NP).

AAAI Conference 2018 Conference Paper

Discovering Program Topoi Through Clustering

• Carlo Ieva
• Arnaud Gotlieb
• Souhila Kaci
• Nadjib Lazaar

Understanding source code of large open-source software projects is very challenging when there is only little documentation. New developers face the task of classifying a huge number of files and functions without any help. This paper documents a novel approach to this problem, called FEAT, that automatically extracts topoi from source code by using hierarchical agglomerative clustering. Program topoi summarize the main capabilities of a software system by presenting to developers clustered lists of functions together with an index of their relevant words. The clustering method used in FEAT exploits a new hybrid distance which combines both textual and structural elements automatically extracted from source code and comments. The experimental evaluation of FEAT shows that this approach is suitable to understand open-source software projects of size approaching 2, 000 functions and 150 files, which opens the door for its deployment in the open-source community.

AIJ Journal 2017 Journal Article

Constraint acquisition

• Christian Bessiere
• Frédéric Koriche
• Nadjib Lazaar
• Barry O'Sullivan

Constraint programming is used to model and solve complex combinatorial problems. The modeling task requires some expertise in constraint programming. This requirement is a bottleneck to the broader uptake of constraint technology. Several approaches have been proposed to assist the non-expert user in the modeling task. This paper presents the basic architecture for acquiring constraint networks from examples classified by the user. The theoretical questions raised by constraint acquisition are stated and their complexity is given. We then propose Conacq, a system that uses a concise representation of the learner's version space into a clausal formula. Based on this logical representation, our architecture uses strategies for eliciting constraint networks in both the passive acquisition context, where the learner is only provided a pool of examples, and the active acquisition context, where the learner is allowed to ask membership queries to the user. The computational properties of our strategies are analyzed and their practical effectiveness is experimentally evaluated.

IJCAI Conference 2016 Conference Paper

Constraint Acquisition with Recommendation Queries

• Abderrazak Daoudi
• Younes Mechqrane
• Christian Bessiere
• Nadjib Lazaar
• El Houssine Bouyakhf

Constraint acquisition systems assist the non-expert user in modeling her problem as a constraint network. Most existing constraint acquisition systems interact with the user by asking her to classify an example as positive or negative. Such queries do not use the structure of the problem and can thus lead the user to answer a large number of queries. In this paper, we propose Predict&Ask, an algorithm based on the prediction of missing constraints in the partial network learned so far. Such missing constraints are directly asked to the user through recommendation queries, a new, more informative kind of queries. Predict&Ask can be plugged in any constraint acquisition system. We experimentally compare the QuAcq system to an extended version boosted by the use of our recommendation queries. The results show that the extended version improves the basic QuAcq.

IJCAI Conference 2016 Conference Paper

Multiple Constraint Acquisition

• Robin Arcangioli
• Christian Bessiere
• Nadjib Lazaar

QUACQ is a constraint acquisition system that assists a non-expert user to model her problem as a constraint network by classifying (partial) examples as positive or negative. For each negative example, QUACQ focuses onto a constraint of the target network. The drawback is that the user may need to answer a great number of such examples to learn all the constraints. In this paper, we provide a new approach that is able to learn a maximum number of constraints violated by a given negative example. Finally we give an experimental evaluation that shows that our approach improves on QUACQ.

ECAI Conference 2014 Conference Paper

Boosting Constraint Acquisition via Generalization Queries

• Christian Bessière
• Remi Coletta
• Abderrazak Daoudi
• Nadjib Lazaar
• Younes Mechqrane
• El-Houssine Bouyakhf

Constraint acquisition assists a non-expert user in modeling her problem as a constraint network. In existing constraint acquisition systems the user is only asked to answer very basic questions. The drawback is that when no background knowledge is provided, the user may need to answer a great number of such questions to learn all the constraints. In this paper, we introduce the concept of generalization query based on an aggregation of variables into types. We present a constraint generalization algorithm that can be plugged into any constraint acquisition system. We propose several strategies to make our approach more efficient in terms of number of queries. Finally we experimentally compare the recent QUACQ system to an extended version boosted by the use of our generalization functionality. The results show that the extended version dramatically improves the basic QUACQ.

IJCAI Conference 2013 Conference Paper

Constraint Acquisition via Partial Queries

• Christian Bessiere
• Remi Coletta
• Emmanuel Hebrard
• George Katsirelos
• Nadjib Lazaar
• Nina Narodytska
• Claude-Guy Quimper
• Toby Walsh

We learn constraint networks by asking the user partial queries. That is, we ask the user to classify assignments to subsets of the variables as positive or negative. We provide an algorithm that, given a negative example, focuses onto a constraint of the target network in a number of queries logarithmic in the size of the example. We give information theoretic lower bounds for learning some simple classes of constraint networks and show that our generic algorithm is optimal in some cases. Finally we evaluate our algorithm on some benchmarks.