The smart table constraint represents a powerful modeling tool that has been recently introduced. This constraint allows the user to represent compactly a number of well-known (global) constraints and more generally any arbitrarily structured constraints, especially when disjunction is at stake. In many problems, some constraints are given under the basic and simple form of tables explicitly listing the allowed combinations of values. In this paper, we propose an algorithm to convert automatically any (ordinary) table into a compact smart table. Its theoretical time complexity is shown to be quadratic in the size of the input table. Experimental results demonstrate its compression efficiency on many constraint cases while showing its reasonable execution time. It is then shown that using filtering algorithms on the resulting smart table is more efficient than using state of the art filtering algorithms on the initial table.

We present and discuss a tool that checks the correctness of simple programs constructed according to the structured programming method. The tool is intended to provide interesting feedback to students learning the programming method: it detects programming and/or reasoning errors and it provides typical counter-examples. We argue that our system is better adapted to our pedagogical context than other verification tools and we report on preliminary experiments with the tool in a third year programming course.

Abstract interpretation is a general methodology for systematic development of program analyses. An abstract interpretation framework is centered around a parametrized non-standard semantics that can be instantiated by various domains to approximate different program properties. Many abstract interpretation frameworks and analyses for Prolog have been proposed, which seek to extract information useful for program optimization. Although motivated by practical considerations, notably making Prolog competitive with imperative languages, such frameworks fail to capture some of the control structures of existing implementations of the language. In this paper, we propose a novel framework for the abstract interpretation of Prolog which handles the depth-first search rule and the cut operator. It relies on the notion of substitution sequence to model the result of the execution of a goal. The framework consists of (i) a denotational concrete semantics, (ii) a safe abstraction of the concrete semantics defined in terms of a class of post-fixpoints, and (iii) a generic abstract interpretation algorithm. We show that traditional abstract domains of substitutions may easily be adapted to the new framework, and provide experimental evidence of the effectiveness of our approach. We also show that previous work on determinacy analysis, that was not expressible by existing abstract interpretation frameworks, can be seen as an instance of our framework. The ideas developed in this paper can be applied to other logic languages, notably to constraint logic languages, and the theoretical approach should be of general interest for the analysis of many non-deterministic programming languages.

Computer security is a topic of growing concern because, on the one hand, the power of computers continues to increase at exponential speed and all computers are virtually connected to each other and because, on the other hand, the lack of reliability of software systems may cause dramatic and unrecoverable damage to computer systems and hence to the newly emerging computerized society. Among the possible approaches to improve the current situation, expert systems have been advocated to be an important one. Typical tasks that such expert systems attempt to achieve include finding system vulnerabilities and detecting malicious behaviour of users. We extend our intrusion detection system ASAX with a deductive subsystem that allows us to assess the security level of a software configuration on a real time basis. By coupling the two subsystems-intrusion detection and configuration analysis-we moreover achieve a better tuning of the intrusion detection since the system has only to enable intrusion detection rules that are specifically required by the current state of the configuration. We also report some preliminary performance measurements, which suggest that our approach can be practical in real life contexts.

An implemented system for on-line analysis of multiple distributed data streams is presented. The system is conceptually universal since it does not rely on any particular platform feature and uses format adaptors to translate data streams into its own standard format. The system is as powerful as possible (from a theoretical standpoint) but still efficient enough for on-line analysis thanks to its novel rule-based language (RUSSEL) which is specifically designed for efficient processing of sequential unstructured data streams. The generic concepts are applied to security audit trail analysis. The resulting system provides powerful network security monitoring and sophisticated tools for intrusion/anomaly detection. The rule-based and command languages are described as well as the distributed architecture and the implementation. Performance measurements are reported, showing the effectiveness of the approach.>

Type analysis of Prolog is of primary importance for high-performance compilers, since type information may lead to better indexing and to sophisticated specializations of unification and built-in predicates to name a few. However, these optimizations often require a sophisticated type inference system capable of inferring disjunctive and recursive types and hence expensive in computation time.

Abstract interpretation [7] is a systematic methodology to design static program analysis which has been studied extensively in the logic programming community, because of the potential for optimizations in logic programming compilers and the sophistication of the analyses which require conceptual support. With the emergence of efficient generic abstract interpretation algorithms for logic programming, the main burden in building an analysis is the abstract domain which gives a safe approximation of the concrete domain of computation. However, accurate abstract domains for logic programming are often complex because of the variety of analyses to perform their interdependence, and the need to maintain structural information. The purpose of this paper is to propose conceptual and software support for the design of abstract domains. It contains two main contributions: the notion of open product and a generic pattern domain. The open product is a new way of combining abstract domains allowing each combined domain to benefit from information from the other components through the notions of queries and open operations. The open product is general-purpose and can be used for other programming paradigms as well. The generic pattern domain Pat (R)automatically upgrades a domain D with structural information yielding a more accurate domain Pat (D) without additional design or implementation cost. The two contributions are orthogonal and can be combined in various ways to obtain sophisticated domains while imposing minimal requirements on the designer. Both contributions are characterized theoretically and experimentally and were used to design very complex abstract domains such as PAT(OProp⊗OMode⊗OPS) which would be very difficult to design otherwise. On this last domain, designers need only contribute about 20% (about 3,400 lines) of the complete system (about 17,700 lines).

Abstract interpretation of PROLOG programs has attracted many researchers in recent years, partly because of the potential for optimization in PROLOG compilers and partly because of the declarative nature of logic programming languages that make them more amenable to optimization than procedural languages. Most of the work, however, has remained at the theoretical level, focusing on the developments of frameworks and the definition of abstract domains. This paper reports our effort to verify experimentally the practical value of this area of research. It describes the design and implementation of the generic abstract interpretation algorithm GAIA that we originally proposed in Le Charlier et al. [1991], its instantiation to a sophisticated abstract domain (derived from Bruynooghe and Janssens [1988]) containing modes, types, sharing, and aliasing, and its evaluation both in terms of performance and accuracy. The overall implementation (over 5000 lines of Pascal) has been systematically analyzed on a variety of programs and compared with the complexity analysis of Le Charlie et al. [1991] and the specific analysis systems of Hickey and Mudambi [1989], Taylor [1989; 1990], Van Roy and Despain [1990], and Warren et al. [1988].

The domain Prop [22,8] is a conceptually simple and elegant abstract domain to compute groundness information for Prolog programs. In particular, abstract substitutions are represented by Boolean functions built using the logical connectives ⇔, ∨, ∧. Prop has raised much theoretical interest recently but little is known about the practical accuracy and efficiency of this domain.In this paper, we describe an implementation of Prop and we use it to instantiate a generic abstract interpretation algorithm [14, 10, 17, 15]. A key feature of the implementation is the use of ordered binary decision graphs. The implementation has been compared systematically to two other abstract domains, Mode and Pattern, from the point of view of groundness analysis.The experimental results indicate that (1)Prop is very accurate to infergroundness information; (2) this domain is quite practical in terms of efficiency, although it is theoretically exponential (in the number of clause variables).

Abstract The efficient implementation of generic abstract interpretation algorithms for Prolog is reconsidered after References 1 and 2. Two new optimization techniques are proposed and applied to the original algorithm of Reference 1: dependency on clause prefixes and caching of operations. The first improvement avoids re‐evaluating a clause prefix when no abstract value which it depends on has been updated. The second improvement consists of caching all operations on substitutions and reusing the results whenever possible. The algorithm and the two optimization techniques have been implemented in C (about 8000 lines of code each), tested on a large number of Prolog programs, and compared with the original implementation on an abstract domain containing modes, types and sharing. In conjunction with refinements of the domain algorithms, they produce an average reduction of more than 58 per cent is computation time. Extensive experimental results on the programs are given, including computation times, memory consumption, hit ratios for the caches, the number of operations performed, and the time distribution. As a main result, the improved algorithms exhibit the same efficiency as the specific tools of References 3 and 4, despite the fact that our abstract domain is more sophisticated and accurate. The abstract operations also take 90 per cent of the computation time, indicating that the overhead of the control is very limited. Results on a simpler domain are also given and show that even extremely basic domains can benefit from the optimizations. The general‐purpose character of the optimizations is also discussed.