Code Monkey home page Code Monkey logo

apron's Introduction

The Apron Numerical Abstract Domain Library

Introduction

Apron is a library to represent properties of numeric variables, such as variable bounds or linear relations between variables, and to manipulate these properties through semantic operations, such as variable assignments, tests, conjunctions, entailment.

Apron is intended to be used in static program analyzers, in order to infer invariants of numeric variables, i.e., properties that hold for all executions of a program. It is based on the theory of Abstract Interpretation.

The API documentation is available on the GitHub page for Apron.

Overview

The Apron library includes several numeric abstract domains, corresponding to different classes of numeric properties with their own internal representation and algorithms, achieving various trade-offs between precision, expressiveness, and efficiency.

Apron includes the following numeric domains:

  • intervals (boxes)
  • polyhedra (newpolka)
  • octagons
  • zonotopes (taylor1plus)

Additional domains are made available through the optional PPL and PPLite third-party libraries:

  • alternate polyhedra implementation (PPL, PPLite)
  • grids (PPL)
  • reduced products of polyhedra and grids (PPL)

The domains are made available under a common interface, so that changing the abstract domain of interpretation in a static analysis should only take a one-line change.

The core API is in C, but optional API wrappers for additional languages are provided:

  • OCaml
  • Java
  • C++

Dependencies

Base

Compiling the built-in domains with the C interface requires:

Additional domains

Compiling the PPL-based domains requires the Parma Polyhedra Library (tested with version 1.2) and gcc (no clang).

Compiling the PPLite-based domains requires the PPLite library, which also depends on Flint. Note that building the PPLite library from sources requires using a C++ compiler (g++ or clang++) that supports the c++17 language standard; however, starting from PPLite version 0.11, the Apron wrapper for PPLite can be compiled using a C++ compiler supporting the c++11 language standard.

Additional language support

Additional language wrappers require additional components:

  • a C++ compiler for the C++ API
  • a JDK >= 1.6 for the Java API
  • for the OCaml API:
    • a recent OCaml compiler (tested with 4.07, but earlier 4.x should also work)
    • ocamlfind
    • camlidl
    • mlgmpidl

Installation instructions

Installation with Opam

If you are using OCaml and the Opam package manager, then you could install the latest version of Apron in Opam with just opam install apron. Only Opam 2.x is supported.

To compile from this source tree, you can install the dependencies with opam install --deps-only . and follow the instructions below.

Installation on Linux

On deb-based Linux distributions (Debian, Ubuntu) a sudo apt-get install libgmp-dev libmpfr-dev should suffice to get the dependencies for the basic C library.

On Opam-based OCaml distributions, a opam install ocamlfind camlidl mlgmpidl should suffice to get the dependencies for the OCaml API.

Compilation from source could be as simple as:

  • ./configure
  • make
  • sudo make install

./configure automatically generates a Makefile.config file. It is also possible to write a Makefile.config by hand by taking some inspiration from Makefile.config.model.

In case some components fail to compile, it is possible to disable them through ./configure options:

  • -no-cxx to disable the C++ API
  • -no-java to disable the Java API (there are known problems where the compilation fails to find jni.h )
  • -no-ocaml to disable the OCaml API
  • -no-ppl to disable the PPL domains
  • -no-pplite to disable the PPLite domains

See ./configure -help for more options.

Debug versions

By default, make install now only install non-debug versions of the C libraries. Moreover, these are striped of symbols.

Use the -debug ./configure option to also install debug (non-stripped) C versions, and -no-strip to avoid stripping the non-debug C versions. The C debug versions have a _debug suffix (such as libapron_debug.so).

When installing with opam, debug versions are always available. OCaml debug libraries use the .d suffix (such as apron.d.cmxa).

Installation on MacOS X

Help needed for this section.

The README.mac file is not up to date.

Installation on Windows

See the Windows README.

Documentation compilation

You can build the documentation with make doc. You will need the following tools:

  • pdflatex
  • texi2html for the C API
  • ocamldoc for the OCaml API
  • doxygen for the the C++ API
  • javadoc for the Java API

Note that some generated documentation may not be up-to-date.

A generated copy of the documentation is available on-line on the GitHub page for Apron.

apron's People

Contributors

antoinemine avatar bennostein avatar bjeannet avatar caterinaurban avatar cgcgbcbc avatar d4n avatar dwrchyngqxs avatar ezaffanella avatar ghilesz avatar jberdine avatar kghorbal avatar lqchen avatar lucaneg avatar monniaux avatar nberth avatar santiagobautista avatar seba-- avatar sim642 avatar skcho avatar thierry-martinez avatar yakobowski avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

apron's Issues

Different widening results across instantiations

I am working with a fairly large codebase and for some reason need to compare the outputs across the two different versions.

This code at some point computes the widening of 2 values in the Octagon domain. The input to the widening function is “sort of” the same in both versions of the code. However, I am getting a different output across the versions.
Here are the values, and the outputs across the 2 versions:

v1: [|cur_v>=0; -cur_v>=0; -cur_v-n>=0; cur_v-n>=0; -n>=0; -n+prefn>=0; -cur_v-prefn>=0; cur_v-prefn>=0; -n-prefn>=0; n-prefn>=0; -prefn>=0|]
v2: [|cur_v>=0; -cur_v+1.>=0; -cur_v-n+2.>=0; cur_v-n>=0; -n+1.>=0; -n+prefn>=0; -cur_v-prefn+2.>=0; cur_v-prefn>=0; -n-prefn+2.>=0; n-prefn>=0; -prefn+1.>=0|]

The new version returns [|cur_v>=0; cur_v-n>=0; -n+prefn>=0; cur_v-prefn>=0; n-prefn>=0|]
The old version returns [|cur_v>=0; -n+prefn>=0; n-prefn>=0|]

I think the old version’s output is correct. However, I am not sure why the new version produces that.
I tried to look at the fdump output of v1 across the 2 files and there is a difference which I do not know how to interpret.

This is the (verbatim) output of the old version:
abstract value of level 1:

environment: dim = (3,0), count = 21
 0: cur_v
 1: n
 2: prefn
octagon of dim (3,0)
matrix:
0 0
0 0
+oo +oo 0 +oo
+oo +oo 0 0
+oo +oo 0 +oo 0 +oo
+oo +oo 0 0 0 0
closed matrix:
0 0
0 0
+oo +oo 0 +oo
0 0 0 0
+oo +oo 0 +oo 0 +oo
0 0 0 0 0 0

This is the output of the new version:
abstract value of level 1:

environment: dim = (3,0), count = 1
 0: cur_v
 1: n
 2: prefn
octagon of dim (3,0)
matrix: NULL
closed matrix:
0 0
0 0
+oo +oo 0 +oo
0 0 0 0
+oo +oo 0 +oo 0 +oo
0 0 0 0 0 0

Soname not defined within generated posix shared libraries

Shared object libraries can define an SONAME field. This is currently not done within apron. Some programs (such as Python's ctypes library) may assume this field is always defined. Due to a conjunction of bad situation, this may make the apronpy interface unable to easily find libapron.so on recent Debian-based distribution, see related issue on apronpy

I guess it should just be a matter of adding -Wl,-soname,libbar.so in addition to the -shared when calling the compiler to create libbar.so. I can do the PR, I just want to be sure I haven't missed a reason to avoid defining this field.

Build OCaml opam package without C++ and Java

I've noticed random GitHub CI failures on our OCaml project caused by the Apron opam package failing to fully build, for example: https://github.com/goblint/analyzer/runs/3479696196?check_suite_focus=true#step:5:1326.
However that obscure failure is just from building the Java API, which isn't really necessary for the opam package.

It seems to me that the build instructions in apron.opam should simply specify -no-cxx and -no-java because even if the configure script determines their requirements met, it's not really necessary to build them when trying to install the opam package. It would avoid build failures unrelated to the OCaml API and maybe save a fraction of a second as well.

If one wants to use the C++ or Java API, then one would build Apron manually for that instead of through OCaml's opam package manager and then using the libraries from some opam's internal build directory.

install --strip causing problems on Mac

The command option --strip doesn't seem to be recognized on Mac (my version is Ventura 13.2.1).
I think install on Mac does not like --.

I think the only place where it's used is here https://github.com/antoinemine/apron/blob/master/Makefile.config.model#L185

I replaced it with -s but then I get this error:

/Library/Developer/CommandLineTools/usr/bin/strip: error: symbols referenced by indirect symbol table entries that can't be stripped in: /Users/jorge/Repos/apron-mine/install-release/lib/libapron.so
___gmpfr_mpfr_get_sj
___gmpfr_out_str
___gmpn_perfect_square_p
___gmpq_add
___gmpq_canonicalize
___gmpq_clear
___gmpq_cmp
___gmpq_cmp_si
___gmpq_div
___gmpq_div_2exp
....

Note that install -s calls strip.

I've found this issue with a similar problem and it seems that we should call strip -u on dynamic libraries.

I believe the issue is that bare strip is too aggressive for a dylib. strip -u seems to work. I'm not sure if -r should also be added. I might suggest adding -u to any dylib crate.

Unfortunately, I don't know how to tell install command to pass the option -u to strip.

Using apron with ocaml dune build system

First of all thank you for this project.

I am working on a static analyser written in Ocaml. This project use apron ocaml bindings.
I am trying to upgrade the project to the more recent Dune build system (the project previously used ocamlbuild) but I am having difficulties to generate a valid executable.
I supposed the issue resides in an incorrect linking at compile time but I am not sure how to solve it.

Here is a simplified version of my dune config :

(library
 (name mylib)
 (libraries zarith camlidl bigarray gmp apron apron.boxD apron.boxMPFR apron.polkaMPQ apron.octMPQ apron.polkaRll apron.t1pD apron.t1pMPFR apron.t1pMPQ apron.octD apron.boxMPQ str unix)
)

(executable
 (public_name myexecutable)
 (name main)
 (libraries mylib zarith camlidl bigarray gmp apron apron.boxD apron.boxMPFR apron.polkaMPQ apron.octMPQ apron.polkaRll apron.t1pD apron.t1pMPFR apron.t1pMPQ apron.octD apron.boxMPQ str unix)
 (preprocess
  (pps ppx_inline_test)))

dune build main.exe works just fine but when I try to run the program it fails with this error message :
bin/main.exe: symbol lookup error: bin/main.exe: undefined symbol: ap_abstract0_policy_meet_tcons_array_improve

So my question will be : can I use apron ocaml bindings with dune? And if so, how to make it work?

Thank you
Sincerely

hasVar() for level 1

Hello,
I noticed a potential bug with the hasVar() method for level 1 nodes. Here is a code snipped where hasVar() on level 1 returns false but if I transform the same node to a level 0 node and check if it contains the same variable it returns true:

Texpr1VarNode x = new Texpr1VarNode("x");
Environment environment = new Environment(new String[]{"x"},new String[]{});
Preconditions.checkArgument(!x.hasVar("x")); \\ I would expect true for x.hasVar("x")
Texpr0Node xZero = x.toTexpr0Node(environment);
Preconditions.checkArgument(xZero.hasDim(environment.dimOfVar("x")));

Thanks!

Unexpected behavior for of_box() and to_box() for 0-dim domain elements

It seems that box and polka domains behave differently when importing/exporting a 0-dimensional abstract value as an array of intervals (using ap_abstract0_of/to_box). The following program seems to witness a mismatch:

#include <stdio.h>
#include <stdlib.h>

#include <ap_global0.h>
#include <box.h>
#include <pk.h>

ap_manager_t* box_man;
ap_manager_t* pk_man;

int main() {
  ap_manager_t* box_man = box_manager_alloc();
  ap_manager_t* pk_man = pk_manager_alloc(false);

  ap_interval_t** itvs0 = ap_interval_array_alloc(1);

  ap_abstract0_t* box0 = ap_abstract0_of_box(box_man, 0, 0, itvs0);
  bool box0_is_bottom = ap_abstract0_is_bottom(box_man, box0);
  bool box0_is_top = ap_abstract0_is_top(box_man, box0);
  printf("box0 is bottom = %i, box0 is top = %i\n\n", box0_is_bottom, box0_is_top);

  ap_abstract0_t* pk0 = ap_abstract0_of_box(pk_man, 0, 0, itvs0);
  bool pk0_is_bottom = ap_abstract0_is_bottom(pk_man, pk0);
  bool pk0_is_top = ap_abstract0_is_top(pk_man, pk0);
  printf("pk0 is bottom = %i, pk0 is top = %i\n\n", pk0_is_bottom, pk0_is_top);

  ap_interval_t** itvs1 = ap_abstract0_to_box(pk_man, pk0);
  ap_abstract0_t* box1 = ap_abstract0_of_box(box_man, 0, 0, itvs1);
  bool box1_is_bottom = ap_abstract0_is_bottom(box_man, box1);
  bool box1_is_top = ap_abstract0_is_top(box_man, box1);
  printf("box1 is bottom = %i, box1 is top = %i\n\n", box1_is_bottom, box1_is_top);
}

It prints:

$ ./bug
box0 is bottom = 1, box0 is top = 0

pk0 is bottom = 0, pk0 is top = 1

box1 is bottom = 1, box1 is top = 0

Am I missing anything obvious (e.g., violating a library precondition)?

Assign_texpr on box and taylor1+ are not strict in option type

Consider the following program:

open Apron

let manbox    = Box.manager_alloc ();;
let manoct    = Oct.manager_alloc ();;
let maneq     = Polka.manager_alloc_equalities ();;
let manpk     = Polka.manager_alloc_strict();;
let manpkl    = Polka.manager_alloc_loose();;
let manppl    = Ppl.manager_alloc_strict();;
let manppll   = Ppl.manager_alloc_loose();;
let mangrid   = Ppl.manager_alloc_grid ();;
let mant1p    = T1p.manager_alloc ();;

let test man =
  let name = Manager.get_library man in
  let varj = Var.of_string "j" in
  let env  = Environment.make [| varj |] [| |] in
  let top  = Abstract1.top man env in
  let bot  = Abstract1.bottom man env in
  let a    = Abstract1.assign_texpr man top varj
               (Texpr1.cst env (Coeff.Interval (Interval.of_int 1 1))) (Some bot) in
  let is_bot = Abstract1.is_leq man a bot in
    if is_bot
    then Format.printf "%s : %b@." name is_bot
    else Format.printf "%s : %b, a : %a@." name is_bot Abstract1.print a

;;
test manbox;;
test manoct;;    (* succeeds *)
test maneq;;     (* succeeds *)
test manpk;;     (* succeeds *)
test manpkl;;    (* succeeds *)
test manppl;;    (* succeeds *)
test manppll;;   (* succeeds *)
test mangrid;;   (* succeeds *)
test mant1p;;

I compile with

ocamlfind ocamlopt -o issuebox1.opt issuebox1.ml -package "qcheck,ppx_deriving.show,apron.boxMPQ,apron.octMPQ,apron.polkaMPQ,apron.ppl,apron.polkaGrid,apron.t1pMPQ" -linkpkg

for Apron downloaded from this repository May 6.

For a list of managers I get the following output:

box : false, a : top
oct : true
polka, equalities mode : true
polka, strict mode : true
polka, loose mode : true
PPL::Polyhedron, strict mode : true
PPL::Polyhedron, loose mode : true
PPL::Grid : true
Taylor1+ : false, a : [|j-1=0|]

Given Some bot as the last argument, a bottom result would be preferable precision-wise,
even if these are strictly speaking not unsound (pun not intended).
Note how Taylor1+ gives the natural j=1 result whereas box actually just yields top 😮

States with interval [0,-1] is not bottom in newer versions

The function ap_abstract1_is_bottom() is returning false for a program state with one variable having value [0,-1] under tags v0.9.12 and v0.9.13. The same function returns True in earlier tag import-svn1104.

I have created a small test program for the same:

#include "ap_abstract1.h"
#include "ap_manager.h"
#include "box.h"
#include "ap_global1.h"

#include<iostream>

using namespace std;

int main() {
    ap_manager_t *man;
    ap_environment_t *env;
    ap_abstract1_t state;

    // init box manager 
    man = box_manager_alloc();

    // init env with two integer variables x and y and no floats
    ap_var_t varX = (ap_var_t)"x";
    ap_var_t varY = (ap_var_t)"y";
    ap_var_t intVars[2] = {varX, varY};
    ap_var_t floatVars[0];
    env = ap_environment_alloc(intVars, 2, floatVars, 0);
    
    // init the program state with top
    state = ap_abstract1_top(man, env);

    // initialize all variables to zero
    ap_linexpr1_t expr = ap_linexpr1_make(env, AP_LINEXPR_SPARSE, 1);
    ap_linexpr1_set_list(&expr, AP_CST_S_INT, 0, AP_END);
    state = ap_abstract1_assign_linexpr(man, true, &state, varX, &expr, NULL);
    state = ap_abstract1_assign_linexpr(man, true, &state, varY, &expr, NULL);
    
    cout << "Program State:" << endl;
    ap_abstract1_fprint(stdout, man, &state);

    // add constraint -y > 0
    expr = ap_linexpr1_make(env, AP_LINEXPR_SPARSE, 2);
    ap_lincons1_t consExpr = ap_lincons1_make(AP_CONS_SUP, &expr, NULL);
    ap_lincons1_set_list(&consExpr, AP_COEFF_S_INT, -1, varY, AP_CST_S_INT, 0, AP_END);
    cout << "ConsExpr: " << endl;
    ap_lincons1_fprint(stderr, &consExpr);
    cout << endl;
    ap_lincons1_array_t consArray = ap_lincons1_array_make(env, 1);
    ap_lincons1_array_set(&consArray, 0, &consExpr);

    // take meet of the constraint -y > 0 and current state
    state = ap_abstract1_meet_lincons_array(man, true, &state, &consArray);

    cout << "Program State:" << endl;
    ap_abstract1_fprint(stdout, man, &state);
    cout << "is bottom: " << ap_abstract1_is_bottom(man, (ap_abstract1_t*)&state)<< endl;

    return 0;
}

The output of this program under v0.9.12 and v0.9.13 is shown here:

Program State:
interval of dim (2,0):
       x in [0,0]
       y in [0,0]
ConsExpr: 
-y > 0
Program State:
interval of dim (2,0):
       x in [1,-1]
       y in [0,-1]
is bottom: 0

While for tag import-svn1104, the output returned 1 for the function ap_abstract1_is_bottom() as shown below:

Program State:
interval of dim (2,0):
       x in [0,0]
       y in [0,0]
ConsExpr: 
-y > 0
Program State:
interval of dim (2,0): bottom
is bottom: 1

Apron uses deprecated fpsetround(3) on FreeBSD

apron uses the deprecated(3) function. See the manpage:

FPGETROUND(3)          FreeBSD Library Functions Manual          FPGETROUND(3)

NAME
     fpgetround, fpsetround, fpsetprec, fpgetprec, fpgetmask, fpsetmask,
     fpgetsticky, fpresetsticky – IEEE floating point interface

SYNOPSIS
     #include <ieeefp.h>

     typedef enum {
             FP_RN,          /* round to nearest */
             FP_RM,          /* round down to minus infinity */
             FP_RP,          /* round up to plus infinity */
             FP_RZ           /* truncate */
     } fp_rnd_t;
     fp_rnd_t
     fpgetround(void);

     fp_rnd_t
     fpsetround(fp_rnd_t direction);

     typedef enum {
             FP_PS,          /* 24 bit (single-precision) */
             FP_PRS,         /* reserved */
             FP_PD,          /* 53 bit (double-precision) */
             FP_PE           /* 64 bit (extended-precision) */
     } fp_prec_t;
     fp_prec_t
     fpgetprec(void);

     fp_prec_t
     fpsetprec(fp_prec_t precision);

     #define fp_except_t     int
     #define FP_X_INV        0x01    /* invalid operation */
     #define FP_X_DNML       0x02    /* denormal */
     #define FP_X_DZ         0x04    /* zero divide */
     #define FP_X_OFL        0x08    /* overflow */
     #define FP_X_UFL        0x10    /* underflow */
     #define FP_X_IMP        0x20    /* (im)precision */
     #define FP_X_STK        0x40    /* stack fault */
     fp_except_t
     fpgetmask(void);

     fp_except_t
     fpsetmask(fp_except_t mask);

     fp_except_t
     fpgetsticky(void);

     fp_except_t
     fpresetsticky(fp_except_t sticky);

DESCRIPTION
     The routines described herein are deprecated.  New code should use the
     functionality provided by fenv(3).

How I got here: builds were failing on armv6, armv7, riscv64 architectures:

ap_manager.c:310:3: error: implicit declaration of function 'fpsetround' is invalid in C99 [-Werror,-Wimplicit-function-declaration]
  fpsetround(FP_RP);
  ^
1 error generated.

As it turned out fpsetround(3) is deprecated, and additionally it isn't even defined on the above architectures that caused build failures.

Move headers in a subdirectory

Running sudo make install creates many files in /usr/include.
Some of them have the ap_ prefix which is perfectly fine.
However, some of them have very generic names (box.h, num.h) that could easily clash with other libraries.

I would suggest to create an apron directory in /usr/include and put all the headers there. You could then remove the ap_ prefix for some headers.

Users could then simply #include <apron/xxx.h>.

Thanks!

Polka widening does not overapproximate the join operator

Initially found by @seba--. Given the states s1 and s2:

s1 = 1·f + 1 == 0 ∧ -1·m + 1·n + 1 >= 0 ∧ 1·m - 1·n + 0 >= 0 ∧ 1·m - 1 >= 0
s2 =-1·m + 1·n + 0 == 0

The Polka domain returns that s1 ∇ s2 = s2. Thus we do not have s1 <= s1 ∇ s2, which contradicts the usual definition of widening. Is this to be expected?

Below is a MWE relying on apronpy, but I can also refactor it to OCaml if needed.

from apronpy.environment import PyEnvironment
from apronpy.var import PyVar
from apronpy.polka import PyPolkaMPQlooseManager, PyPolka
from apronpy.lincons0 import ConsTyp
from apronpy.lincons1 import PyLincons1, PyLincons1Array
from apronpy.linexpr1 import PyLinexpr1
from apronpy.coeff import PyDoubleScalarCoeff
from apronpy.oct import PyOctMPQManager, PyOct

def create_constraint_equality(env, constraints, cst, op=ConsTyp.AP_CONS_EQ):
    e = PyLinexpr1(env)
    for (var, coeff) in constraints:
        e.set_coeff(var, PyDoubleScalarCoeff(coeff))
    e.set_cst(PyDoubleScalarCoeff(cst))
    return PyLincons1(op, e)

if __name__ == "__main__":
    mode = "poly"
    if mode == "poly":
        man = PyPolkaMPQlooseManager()
        rel_cons = PyPolka
    else:
        man = PyOctMPQManager()
        rel_cons =  PyOct

    f = PyVar('f')
    m = PyVar('m')
    n = PyVar('n')
    e2 = PyEnvironment([f, m, n])

    c1_s1 = create_constraint_equality(e2, [(f, 1)], 1)
    c2_s1 = create_constraint_equality(e2, [(m, -1), (n, 1)], 1, ConsTyp.AP_CONS_SUPEQ)
    c3_s1 = create_constraint_equality(e2, [(m, 1), (n, -1)], 0, ConsTyp.AP_CONS_SUPEQ)
    c4_s1 = create_constraint_equality(e2, [(m, 1)], -1, ConsTyp.AP_CONS_SUPEQ)

    s1 = rel_cons(man, e2, array=PyLincons1Array([c1_s1, c2_s1, c3_s1, c4_s1]))
    print("s1: ", s1)

    c2_s1 = create_constraint_equality(e2, [(m, -1), (n, 1)], 0)

    s2 = rel_cons(man, e2, array=PyLincons1Array([c2_s1]))
    print("s2: ", s2)

    sw = s1.widening(s2)
    print("sw: ", sw)

    print("s1 <= sw? ", s1.is_leq(sw))
    print("s2 <= sw? ", s2.is_leq(sw))

Segfault after many operations in the taylor1plus domain.

When performing a loop with many t1p_of_lincons_array operations, after a while there is a segfault. The bug occurs in t1p_init_from_manager and seems to be because ((t1p_internal*)man->internal)->funid does not point to a valid location anymore. I've created an example that demonstrates the issue here. I haven't observed the same issue when using t1p_meet_lincons_array without calling it from t1p_of_lincons_array, so I think the bug specifically concerns meeting with top.

Make 4.4 build issue

The Fedora Linux project is preparing to update GNU Make to version 4.4. Apron 0.9.13 fails to build with this version of make, due to this change. The issue is that include directives for nonexistent files are no longer ignored, but are considered fatal errors. The file apron/Makefile has such a directive on line 4: include depend. On initially unpacking the archive, there is no file named apron/depend. Furthermore, it cannot be created with make -C apron depend, because that reads the Makefile which wants to include the file named depend, which doesn't exist yet.

A workaround, which I will use for the Fedora build, is to do this before invoking make:

touch apron/depend
make -C apron depend

It would be better if the Makefile could be restructured to work with make 4.4 out of the box.

Segfault when dividing by zero with Polka MPQ domain

Hello,

I am not sure if this is expected but, when explicitly dividing a constant by 0 in the Polka MPQ domain, the program crashes. This does not happen with the Octagon or Boxes domains. Also, this does not happen with a type other than Real.

Here is a simplified example that exhibits the problem:

#require "apron";;
#require "apron.octMPQ";;
#require "apron.polkaMPQ";;

open Apron
open Texpr1

let to_cst (x: int) : expr =
  Cst (x |> string_of_int |> Mpqf.of_string |> Coeff.s_of_mpqf)

let () =
  let man = Polka.manager_alloc_strict () in
  (* let man = Oct.manager_alloc () in *)
  let x = Var.of_string "x" in
  let env = Environment.make [|x|] [||] in
  let s = Abstract1.top man env in
  let e = Binop (Div, to_cst 1, to_cst 0, Real, Zero) in
  let s = Abstract1.assign_texpr man s x (of_expr env e) None in
  ()
;;

I wish you a good end of week!
Jérôme Boillot

jar packages do not contain .class files

The apron.jar and gmp.jar files produced (starting from version 0.9.13) contain no .class file; they only contain the .java files.
While not being a Java expert (I was only trying to build an Apron-based java wrapper for PPLite's polyhedra domains), I suppose this change wrt 0.9.12 was done unintentionally. The following patch for japron/Makefile works for me.

diff --git a/japron/Makefile b/japron/Makefile
index d31a57c..0eaa6e9 100644
--- a/japron/Makefile
+++ b/japron/Makefile
@@ -117,7 +117,7 @@ ifneq ($(JAVAC_HAS_H),)
 
 gmp.jar: $(GMPJ)
        $(JAVAC) -h gmp $+
-       $(JAR) cf $@ $+
+       $(JAR) cf $@ $(GMPCLASS)
        $(JAR) i $@
 
 else
@@ -125,7 +125,7 @@ else
 gmp.jar: $(GMPJ)
        $(JAVAC) $+
        $(JAVAH) -d gmp $(GMPCNAME)
diff --git a/japron/Makefile b/japron/Makefile
index d31a57c..0eaa6e9 100644
--- a/japron/Makefile
+++ b/japron/Makefile
@@ -117,7 +117,7 @@ ifneq ($(JAVAC_HAS_H),)
 
 gmp.jar: $(GMPJ)
        $(JAVAC) -h gmp $+
-       $(JAR) cf $@ $+
+       $(JAR) cf $@ $(GMPCLASS)
        $(JAR) i $@
 
 else
@@ -125,7 +125,7 @@ else
 gmp.jar: $(GMPJ)
        $(JAVAC) $+
        $(JAVAH) -d gmp $(GMPCNAME)
-       $(JAR) cf $@ $+
+       $(JAR) cf $@ $(GMPCLASS)
        $(JAR) i $@
 
 endif
@@ -141,7 +141,7 @@ ifneq ($(JAVAC_HAS_H),)

inconsistency between the origin expression and the result expression

When I want to reduce the expression [| x + y -2 >= 0; x + y > - 3=0|], the result of tab is [|-3 + 1 * x + 1 * y >= 0|], How can I get the origin expression x + y - 3 >= 0?

let _ =
  let vx = Var.of_string "x" in
  let vy = Var.of_string "y" in
  let env = Environment.make [||] [|vx;vy|] in
  let c = Texpr1.cst env (Coeff.s_of_int 2) in
  let c' = Texpr1.cst env (Coeff.s_of_int 3) in
  let vx' =  Texpr1.var env vx in
  let vy' = Texpr1.var env vy in
  let texpr = Texpr1.binop Add vx' vy' Real Near in
  let texpr1 = Texpr1.binop Sub texpr c Real Near in
  let texpr2 = Texpr1.binop Sub texpr c' Real Near in
  (* let sum' = Texpr1.(Binop(Sub,x2,Cst c,Int,Near)) in *)
  Format.printf "env = %a@." (fun x -> Environment.print x) env;
  Format.printf "expr = %a@." (fun x -> Texpr1.print x) texpr;
  let cons1 = Tcons1.make texpr1 Lincons0.SUPEQ in
  let cons2 = Tcons1.make texpr2 Lincons0.SUPEQ in

  let tab = Tcons1.array_make env 2 in
  Tcons1.array_set tab 0 cons1;
  Tcons1.array_set tab 1 cons2;
  let abs = Abstract1.of_tcons_array manpk env tab in
  let tab' = Abstract1.to_tcons_array manpk abs in
  Format.printf "tab = %a@." (fun x -> Tcons1.array_print x) tab;
  Format.printf "tab1 = %a@." (fun x -> Tcons1.array_print x) tab'

Publishing Apron

Hello,
we currently try to include Apron in JavaSMT (https://github.com/sosy-lab/java-smt) as a pseudo SMT solver. We would be interested whether you have published the library in an Ivy/Maven repository? And if not, would you be ok if we publish Apron in our Ivy and Maven repositories (in accordance with your license of course)?
Best, Winnie

'best' and 'exact' flags not set correctly for octagons?

Hello,
I am new to using Apron, and I have the impression that the flags 'best' and 'exact' are not accurately modified when using the octagon domain.

The example that makes me think so is the following:

open Apron

let manoct = Oct.manager_alloc ()

let var_x = Var.of_string "x"
let var_y = Var.of_string "y"

let env_xy = Environment.make [||] [|var_x; var_y|]

let ex() =
  (*** Creating an abstract value for the point [x=1; y=3] ***)
  let cons1 = Lincons1.array_make env_xy 2 in
  (* Constraint x - 1 = 0  *)
  let eq1_expr1 = Linexpr1.make env_xy in
  Linexpr1.set_array eq1_expr1
    [|
      (Coeff.Scalar (Scalar.of_frac   1  1), var_x);
    |]
    (Some (Coeff.Scalar (Scalar.of_frac (-1) 1)));
  Lincons1.array_set cons1 0 (Lincons1.make eq1_expr1 Lincons1.EQ);

  (* Constraint y - 3 = 0 *)
  let eq2_expr1 = Linexpr1.make env_xy in
  Linexpr1.set_array eq2_expr1
    [|
      (Coeff.Scalar (Scalar.of_frac   1  1), var_y);
    |]
    (Some (Coeff.Scalar (Scalar.of_frac (-3) 1)));
  Lincons1.array_set cons1 1 (Lincons1.make eq2_expr1 Lincons1.EQ);

  (*** Creating an abstract value for the point [x=1; y=4] ***)
  let cons2 = Lincons1.array_make env_xy 2 in
  (* Constraint x - 1 = 0 *)
  let eq1_expr2 = Linexpr1.make env_xy in
  Linexpr1.set_array eq1_expr2
    [|
      (Coeff.Scalar (Scalar.of_frac   1  1), var_x);
    |]
    (Some (Coeff.Scalar (Scalar.of_frac (-1) 1)));
  Lincons1.array_set cons2 0 (Lincons1.make eq1_expr2 Lincons1.EQ);
  (* Constraint y - 4 = 0 *)
  let eq2_expr2 = Linexpr1.make env_xy in
  Linexpr1.set_array eq2_expr2
    [|
      (Coeff.Scalar (Scalar.of_frac   1  1), var_y);
    |]
    (Some (Coeff.Scalar (Scalar.of_frac (-4) 1)));
  Lincons1.array_set cons2 1 (Lincons1.make eq2_expr2 Lincons1.EQ);

  (*** Set the 'flags wanted' flags ***)
  let opt = Manager.get_funopt manoct Funid_join in
  Manager.set_funopt manoct Funid_join {opt with flag_exact_wanted = true; flag_best_wanted = true};
  
  (* The corresponding abstract values *)
  let u = Abstract1.of_lincons_array manoct env_xy cons1 in
  let v = Abstract1.of_lincons_array manoct env_xy cons2 in
  (* The join of the two points *)
  let res = Abstract1.join manoct u v in
  
  (* Printing of the different values and the flags *)
  let best = Manager.get_flag_best manoct in
  let exact = Manager.get_flag_exact manoct in
  Format.printf "u=%a@." Abstract1.print u;
  Format.printf "v=%a@." Abstract1.print v;
  Format.printf "result=%a@." Abstract1.print res;

  print_endline ("exact flag is " ^ Bool.to_string exact);
  print_endline ("best flag is " ^ Bool.to_string best)  
;;

ex();;

In this example, the union of two points cannot be exactly represented as an octagon, and hence the result of the join is a segment. The result is a best abstraction but not an exact abstraction. Nevertheless executing the above code results in the exact flag being true.

Did I misunderstand or misuse something?

In advance, thank you very much for your answers.

Unlawful `compare` implementations

The compare functions which are exposed to OCaml, either directly or via custom_operations structs and Stdlib.compare, do not satisfy the usual order laws. In turn, this means that many Apron types cannot (at least easily) be used for Set.Make and Map.Make.
Since the operations are somehow defined, doing so doesn't immediately fail (e.g. by exception), but leads to some nasty Heisenbugs down the line.

Examples

Environment

Environment.compare is explicitly exposed to OCaml:

quote(MLI,"\n(** Compare two environment. [compare env1 env2] return [-2] if the environments are not compatible (a variable has different types in the 2 environments), [-1] if [env1] is a subset of env2, [0] if equality, [+1] if env1 is a superset of env2, and [+2] otherwise (the lce exists and is a strict superset of both) *)")
int ap_environment_compare(ap_environment_ptr env1,
ap_environment_ptr env2);

The documentation correctly describes its behavior, which, however, is not the compare suitable for Set.OrderedType.
For example (in pseudo-syntax), Environment.compare {var1} {var2} > 0 and Environment.compare {var2} {var1} > 0 both return true (because compare returns 2 both ways).

What's worse, the same implementation is specified for the Environment.t custom OCaml block via custom_operations struct, which is to be used by Stdlib.compare (and its standard operator-derivatives). The problem is that this doesn't fit the usually-understood properties of that function as documented:

compare x y returns 0 if x is equal to y, a negative integer if x is less than y, and a positive integer if x is greater than y.
[...]
The compare function can be used as the comparison function required by the Set.Make and Map.Make functors.

So, for example, {var1} > {var2} and {var2} > {var1} both return true as well.

Abstract0 (and Abstract1)

Abstract0 (and Abstract1, which is built on top of it) don't directly expose and document a compare. However, one is still defined for Abstract0.t's custom block:

int camlidl_apron_abstract0_ptr_compare(value v1, value v2)
{
ap_abstract0_ptr* p1 = (ap_abstract0_ptr *) Data_custom_val(v1);
ap_abstract0_ptr* p2 = (ap_abstract0_ptr *) Data_custom_val(v2);
ap_abstract0_t* a1 = *p1;
ap_abstract0_t* a2 = *p2;
ap_dimension_t dim1,dim2;
int res;
if (v1==v2 || p1==p2 || a1==a2)
res=0;
else {
dim1 = ap_abstract0_dimension(a1->man,a1);
dim2 = ap_abstract0_dimension(a2->man,a2);
res = dim1.intdim-dim2.intdim;
if (!res){
res = dim1.realdim-dim2.realdim;
if (!res){
if (ap_abstract0_is_eq(a1->man,a1,a2))
res=0;
else
res = a1 > a2 ? 1 : (-1);
if (a1->man->result.exn!=AP_EXC_NONE) camlidl_apron_manager_check_exception(a1->man,NULL);
}
}
}
return res;
}

At first glance, this appears somewhat sound: first dimensions are compared, then ap_abstract0_is_eq is used to check for semantic equality (which is also exposed as is_eq to OCaml). But the final fallback comparison is of pointers themselves (which are arbitrary memory addresses). On its own, that's a valid total order, but not when combined with the semantic equality check.

For example, suppose a1 = {x>=0}, a2 = {-x>=0} and a3 = {x>=0} are allocated in order and their addresses also happen to be in the same order. Then a1 < a2 and a2 < a3 per pointer comparison, but a1 = a3 per semantic equality check.

Other types

Other Apron types might have similar issues, I didn't check everything. Var.compare at least is sound because it's just strcmp.

Conclusion

Even though polymorphic comparison and Stdlib.compare aren't generally recommended, they have been defined for Apron's custom blocks and that's the only way to compare most of them. Even if there's no plan to fix it, this issue hopefully serves as a warning to anyone trying to use Set.Make/Map.Make on Apron data types, which appears to work at first glance but can surprisingly break down.

Cannot find ap_ppl.h after installation [MacOS]

Hi all,

After installing Apron, I cannot find ap_ppl.h in the target include directory. Here are the HAS Flags:

######################################################################
# HAS Flags
######################################################################

# If defined to non-empty value, generates dynamic libraries.
# Do not forget to add -fPIC to CFLAGS and CFLAGS_DEBUG
HAS_SHARED=1

# If defined to non-empty value, compiles the OCaml interface (bytecode)
# HAS_OCAML = 1
# If defined to non-empty value, compiles the OCaml interface (native code)
# HAS_OCAMLOPT = 1

# If defined to non-empty value, compiles the C++ interface (beta version)
# HAS_CPP = 1

# If defined to non-empty value, compiles the PPL domain
# (require included patch to PPL, see ppl/README and ppl/ppl.patch)

# HAS_PPL = 1

# If defined to non-empty value, compiles the fppol domain
# (The fppol domain requires GLPK)

# HAS_GLPK = 1

# If defined to non-empty value, support for "long double" is enabled

# HAS_LONG_DOUBLE = 1

# If defined to non-empty value, compiles the Java interface
# HAS_JAVA = 1

# If defined to non-empty value, assumed to be the right executable,
# use FINDLIB/ocamlfind package system
# (advised)
OCAMLFIND = ocamlfind

I additionally comment out HAS_OCAML and HAS_OCAMLOPT because I do not need ocaml API. In the https://github.com/antoinemine/apron/blob/master/README.mac, it says one should disable HAS_PPL, I suspect that we should keep this flag?

Actually, I find ap_ppl.h after setting HAS_PPL=1.

Installs shared libraries without .so suffix which are also unstripped

====> Running Q/A tests (stage-qa)
Warning: 'bin/octtestD' is not stripped consider trying INSTALL_TARGET=install-strip or using ${STRIP_CMD}
Warning: 'bin/octtestMPQ' is not stripped consider trying INSTALL_TARGET=install-strip or using ${STRIP_CMD}
Warning: 'bin/ap_ppl_test' is not stripped consider trying INSTALL_TARGET=install-strip or using ${STRIP_CMD}
Warning: 'lib/libapron.' is not stripped consider trying INSTALL_TARGET=install-strip or using ${STRIP_CMD}
Warning: 'lib/libapron_debug.' is not stripped consider trying INSTALL_TARGET=install-strip or using ${STRIP_CMD}
Warning: 'lib/libpolkaMPQ.' is not stripped consider trying INSTALL_TARGET=install-strip or using ${STRIP_CMD}
Warning: 'lib/libpolkaMPQ_debug.' is not stripped consider trying INSTALL_TARGET=install-strip or using ${STRIP_CMD}
Warning: 'lib/libpolkaRll.' is not stripped consider trying INSTALL_TARGET=install-strip or using ${STRIP_CMD}
Warning: 'lib/libpolkaRll_debug.' is not stripped consider trying INSTALL_TARGET=install-strip or using ${STRIP_CMD}
Warning: 'lib/libboxMPQ.' is not stripped consider trying INSTALL_TARGET=install-strip or using ${STRIP_CMD}
Warning: 'lib/libboxD.' is not stripped consider trying INSTALL_TARGET=install-strip or using ${STRIP_CMD}
Warning: 'lib/libboxMPFR.' is not stripped consider trying INSTALL_TARGET=install-strip or using ${STRIP_CMD}
Warning: 'lib/libboxMPQ_debug.' is not stripped consider trying INSTALL_TARGET=install-strip or using ${STRIP_CMD}
Warning: 'lib/libboxD_debug.' is not stripped consider trying INSTALL_TARGET=install-strip or using ${STRIP_CMD}
Warning: 'lib/libboxMPFR_debug.' is not stripped consider trying INSTALL_TARGET=install-strip or using ${STRIP_CMD}
Warning: 'lib/liboctD.' is not stripped consider trying INSTALL_TARGET=install-strip or using ${STRIP_CMD}
Warning: 'lib/liboctD_debug.' is not stripped consider trying INSTALL_TARGET=install-strip or using ${STRIP_CMD}
Warning: 'lib/liboctMPQ.' is not stripped consider trying INSTALL_TARGET=install-strip or using ${STRIP_CMD}
Warning: 'lib/liboctMPQ_debug.' is not stripped consider trying INSTALL_TARGET=install-strip or using ${STRIP_CMD}
Warning: 'lib/libt1pMPQ.' is not stripped consider trying INSTALL_TARGET=install-strip or using ${STRIP_CMD}
Warning: 'lib/libt1pD.' is not stripped consider trying INSTALL_TARGET=install-strip or using ${STRIP_CMD}
Warning: 'lib/libt1pMPFR.' is not stripped consider trying INSTALL_TARGET=install-strip or using ${STRIP_CMD}
Warning: 'lib/libt1pMPQ_debug.' is not stripped consider trying INSTALL_TARGET=install-strip or using ${STRIP_CMD}
Warning: 'lib/libt1pD_debug.' is not stripped consider trying INSTALL_TARGET=install-strip or using ${STRIP_CMD}
Warning: 'lib/libt1pMPFR_debug.' is not stripped consider trying INSTALL_TARGET=install-strip or using ${STRIP_CMD}
Warning: 'lib/libap_ppl.' is not stripped consider trying INSTALL_TARGET=install-strip or using ${STRIP_CMD}
Warning: 'lib/libap_ppl_debug.' is not stripped consider trying INSTALL_TARGET=install-strip or using ${STRIP_CMD}
Warning: 'lib/libap_pkgrid.' is not stripped consider trying INSTALL_TARGET=install-strip or using ${STRIP_CMD}
Warning: 'lib/libap_pkgrid_debug.' is not stripped consider trying INSTALL_TARGET=install-strip or using ${STRIP_CMD}

Please also don't install _debug versions. Package shouldn't contain debug libs by default. They should be built only for debugging.

Segfault on linearization

The following program causes a segfautl on some machines after a few iterations:

open Apron

let () =
  let man = Polka.manager_alloc_loose () in
  let env = Environment.make [||] [||] in
  let cond = Parser.tcons1_of_lstring env [
      "0 <= 0";
      "0 <= 100 - 1";
    ]
  in
  let top = Abstract1.top man env in
  for i = 0 to 100 do
    Format.printf "Iteration %d@." i;
    let _ = Abstract1.meet_tcons_array man top cond in
    ()
  done;
  ()

Valgrind says:

Iteration 0
==22150== Invalid read of size 4
==22150==    at 0x4A7776A: itv_canonicalize_MPQ (in /home/mine/.opam/4.08.1/share/apron/lib/libapron.so)
==22150==    by 0x4A8369C: itv_boxize_lincons_array_MPQ (in /home/mine/.opam/4.08.1/share/apron/lib/libapron.so)
==22150==    by 0x4A03C67: ap_intlinearize_tcons0_array_MPQ (in /home/mine/.opam/4.08.1/share/apron/lib/libapron.so)
==22150==    by 0x49F2FF0: ap_generic_meet_intlinearize_tcons_array (in /home/mine/.opam/4.08.1/share/apron/lib/libapron.so)
==22150==    by 0x49B6F5E: pk_meet_tcons_array (in /home/mine/.opam/4.08.1/share/apron/lib/libpolkaMPQ.so)
==22150==    by 0x49EFBF6: ap_abstract0_meet_tcons_array (in /home/mine/.opam/4.08.1/share/apron/lib/libapron.so)
==22150==    by 0x49F9EC6: ap_abstract1_meet_tcons_array (in /home/mine/.opam/4.08.1/share/apron/lib/libapron.so)
==22150==    by 0x21BC31: camlidl_abstract1_ap_abstract1_meet_tcons_array (in /home/mine/tmp/bug-apron/main.native)
==22150==    by 0x1BA78A: camlMain__entry (in /home/mine/tmp/bug-apron/main.native)
==22150==    by 0x1B81C8: caml_program (in /home/mine/tmp/bug-apron/main.native)
==22150==    by 0x25516F: ??? (in /home/mine/tmp/bug-apron/main.native)
==22150==    by 0x255554: caml_startup_common (startup_nat.c:160)
==22150==  Address 0x5102f04 is 20 bytes after a block of size 0 alloc'd
==22150==    at 0x483677F: malloc (vg_replace_malloc.c:299)
==22150==    by 0x4A7B8EA: itv_array_set_ap_interval_array_MPQ (in /home/mine/.opam/4.08.1/share/apron/lib/libapron.so)
==22150==    by 0x4A03A33: ap_intlinearize_tcons0_array_MPQ (in /home/mine/.opam/4.08.1/share/apron/lib/libapron.so)
==22150==    by 0x49F2FF0: ap_generic_meet_intlinearize_tcons_array (in /home/mine/.opam/4.08.1/share/apron/lib/libapron.so)
==22150==    by 0x49B6F5E: pk_meet_tcons_array (in /home/mine/.opam/4.08.1/share/apron/lib/libpolkaMPQ.so)
==22150==    by 0x49EFBF6: ap_abstract0_meet_tcons_array (in /home/mine/.opam/4.08.1/share/apron/lib/libapron.so)
==22150==    by 0x49F9EC6: ap_abstract1_meet_tcons_array (in /home/mine/.opam/4.08.1/share/apron/lib/libapron.so)
==22150==    by 0x21BC31: camlidl_abstract1_ap_abstract1_meet_tcons_array (in /home/mine/tmp/bug-apron/main.native)
==22150==    by 0x1BA78A: camlMain__entry (in /home/mine/tmp/bug-apron/main.native)
==22150==    by 0x1B81C8: caml_program (in /home/mine/tmp/bug-apron/main.native)
==22150==    by 0x25516F: ??? (in /home/mine/tmp/bug-apron/main.native)
==22150==    by 0x255554: caml_startup_common (startup_nat.c:160)

This seems due to a call to linearization with an empty environment.

Java version check broken in 0.9.12 if _JAVA_OPTIONS is set

The Java version check added in 720a18a does not work if _JAVA_OPTIONS is set.

To reproduce:

  1. Run export _JAVA_OPTIONS="-Duser.language=en" (or something similar)
  2. Run ./configure
  3. Note that java_version will be Picked up _JAVA_OPTIONS: -Duser.

The first line of java -version when the environment variable is set is:

Picked up _JAVA_OPTIONS: -Duser.language=en

and the following lines as normal.

Is there a way to have precise assignments on PPL Grid?

I'd like the assignment m = n % 12 to be handled precisely by assign_texpr in the PPL Grid domain. It currently does not work precisely, while a similar code meeting constraints work when we use the EQMOD operator. I was wondering if you had any hint as to why this is imprecise, or how to fix it?

open Apron

let man = Ppl.manager_alloc_grid () 
let env = Environment.make [|Var.of_string "n"; Var.of_string "m"|] [||]
let top = Abstract1.top man env
let t3 = Texpr1.binop Mod (Texpr1.var env (Var.of_string "n")) (Texpr1.cst env (Coeff.s_of_int 12)) Int Rnd  (* n % 12 *)
let a3 = Abstract1.assign_texpr_array man top [|(Var.of_string "m")|] [|t3|] None  (* m := n % 12 *)
let () = Format.printf "@.test3: " 
let () = Tcons1.array_print Format.std_formatter (Abstract1.to_tcons_array man a3)
let () = Format.printf "@."

Distinct Test fails

Hi, I wonder, why this small tests says that the abstract1-object is not bottom. Somehow the constraint x != y is not added to the abstract1-object. Is that a bug or is it intended?

  public static void distinctTest(Manager manager) throws ApronException {
    //x,y = 0 and x != y
    Texpr1VarNode x = new Texpr1VarNode("x");
    Texpr1VarNode y = new Texpr1VarNode("y");
    Texpr1BinNode leftArg = new Texpr1BinNode(Texpr1BinNode.OP_SUB, x,y);
    Environment environment = new Environment(new String[]{"x","y"},new String[]{});
    Tcons1 xIsZero = new Tcons1(environment, Tcons1.EQ,x);
    Tcons1 yIsZero = new Tcons1(environment, Tcons1.EQ,y);
    Tcons1 constraint = new Tcons1(environment,Tcons1.DISEQ,leftArg);
    Abstract1 abstract1 = new Abstract1(manager, new Tcons1[]{xIsZero,yIsZero,constraint});
    Preconditions.checkArgument(abstract1.isBottom(manager));
  }

  public static void main(String[] args) throws ApronException {
    Manager manager = new Polka(false);
    distinctTest(manager);
  }

`bound_texpr` could be more precise for non-linear expressions

Following a discussion with @jboillot in the Mopsa static analyzer, I believe bound_texpr could be more precise. Consider the case where x >= y and z >= 0. Currently, bound_texpr on (x-y)*z returns [-oo,+oo], while it could return [0, +oo].

I tried bound_texpr on x-y, the result is precise. I also tried bounding x*y when x >= 0, y >= 0, and got a precise result.

Code to reproduce the issue:

open Apron

let man = Polka.manager_alloc_loose ()
let env = Environment.make (Array.map Var.of_string [|"x"; "y"; "z"|]) [||]
let top = Abstract1.top man env
let tv s = Texpr1.var env (Var.of_string s)
let cons1 = Tcons1.make (tv "z") SUPEQ
let cons2 = Tcons1.make (Texpr1.binop Sub
                           (tv "x")
                           (tv "y")
                           Int Rnd) SUPEQ
let cons = Tcons1.array_make env 2
let () = Tcons1.array_set cons 0 cons1
let () = Tcons1.array_set cons 1 cons2
let a = Abstract1.meet_tcons_array man top cons
let () = Tcons1.array_print Format.std_formatter (Abstract1.to_tcons_array man a)
let xmy = Texpr1.binop Sub (tv "x") (tv "y") Int Rnd
let e = Texpr1.binop Mul xmy (tv "z") Int Rnd
let itv = Abstract1.bound_texpr man a e
let () = Format.printf "@.%a in %a@." Texpr1.print e Interval.print itv 

Tried with apron 0.9.13, 0.9.14, using either the Polka or Octagon domain.

sat_tcons wrong behaviour

If I understand the documentation correctly, when sat_tcons abs c returns true then all the values of the concretization of abs do satisfy the constraint c. However, I stumbled upon examples with polyhedra, and a non-linear constraint, where sat_tcons answers true while some values of \gamma(abs) do not satisfy the constraint. The following code illustrates this behaviour:

let _ =
  let vx = Var.of_string "x" in
  let env = Environment.make [||] [|vx|] in

  (* x^2 - 2 >= 0*)
  let c = Coeff.s_of_int 2 in
  let x2 = Texpr1.(Binop(Pow,Var vx,Cst c,Real,Near)) in
  let sum' = Texpr1.(Binop(Sub,x2,Cst c,Real,Near)) in
  let texpr = Texpr1.of_expr env sum' in
  let cons = Tcons1.make texpr Lincons0.SUPEQ in

  (* x \in [-3;3] *)
  let pman = Polka.manager_alloc_strict() in
  let poly = Abstract1.top pman env in
  let texpr = Texpr1.cst env (Coeff.i_of_int (-3) 3) in
  let poly = Abstract1.assign_texpr pman poly vx texpr None in

  (* for x=0  'cons' is not satisfied, we should have false? *)
  Format.printf "does %a satisfy the constraint '%a'?\n%b\n%!"
    Abstract1.print poly Tcons1.print cons
    (Abstract1.sat_tcons pman poly cons)

Uninterpreted Functions

Hi, I am currently working on my Bachelor thesis to include Apron in JavaSMT at LMU Munich and I am wonderig, if uninterpreted functions are directly implemented in apron?
Thanks :)

cosine benchmark

to use cosine in this tool, do you first manually convert it into a Taylor expansion or this tool automatically convert that?

Integer division of `n/d` where `n = [-1, 1], d = -1` yields bottom

Originally encountered by @svenkeidel, I'm providing an OCaml MWE.

We found that integer division of n/d yields bottom when -1 <= n <= 1 and d = -1. I have checked the documentation and I am not sure to understand this behavior?

MWE:

open Apron 

let run nv man = 
  let vars = Array.map Var.of_string [| "n"; "d1"; "d2"; "r" |] in 
  let nd = Array.sub vars 0 3 in
  let env = Environment.make vars [||] in
  let values = Array.map
      (fun (l, h) -> Texpr1.cst env (Coeff.i_of_int l h))
      [|nv; (-1, -1); (1, 1) |] in
  let abs = Abstract1.assign_texpr_array man (Abstract1.top man env) nd values None in
  let () = Format.printf "%a@." Abstract1.print abs  in
  let div1 = Texpr1.binop Div
      (Texpr1.var env vars.(0))
      (Texpr1.var env vars.(1)) Int Down in
  let abs1 = Abstract1.assign_texpr man abs vars.(3) div1 None in
  let () = Format.printf "assign(%a, %a) = %a\t=> r in %a@."
    Var.print vars.(3)
    Texpr1.print div1 
    Abstract1.print abs1
    Interval.print (Abstract1.bound_variable man abs vars.(3)) in
  ()

let () = run (-1, 1) (Polka.manager_alloc_loose ())

ppl.hh seems missing

$./configure ; make
(...)
In file included from ppl_user.cc:20:
In file included from ./ppl_user.hh:20:
./ppl_poly.hh:20:10: fatal error: 'ppl.hh' file not found
#include "ppl.hh"
(...)

Java compiliation incorrect

Greetings,
while trying to compile Apron with Java bindings i noticed that the apron.jar is not working.
The reason is that you package the .java files into the jar. You need to package the class files into the jar instead.

Best,
Daniel

Minimize for octagons

The original octagon library implements and documents a minimization algorithm. The Apron implementation of octagon minimization is missing:

/* NOT IMPLEMENTED: do nothing */
void oct_minimize(ap_manager_t* man, oct_t* a)
{
oct_internal_t* pr = oct_init_from_manager(man,AP_FUNID_MINIMIZE,0);
ap_manager_raise_exception(man,AP_EXC_NOT_IMPLEMENTED,pr->funid,
"not implemented");
}

Although the original implementation has a separate space-efficient storage format for minimized octagons, Apron clearly does not. Nevertheless, the algorithm could still be implemented to just act on and return the half-matrix representation (or really just modify it in-place).

It wouldn't offer actual space savings, but it would be useful for printing and to_lincons_array to have the octagon minimzed, such that they don't return an incomprehensibly large set of redundant constraints.

Floating point numbers using Polka manager

According to the documentation, the Polka manager doesn't handle floating point representation and instead convert floats to rationals :

All scalars of type double are converted to scalars of type mpq_t inside NewPolka, as NewPolka works internally with exact rational arithmetics. So when possible it is better for the user (in term of efficiency) to convert already double scalars to mpq_t scalars.
Source

Is there an efficient way to ensure that computations, such as the getBound method, yield only conservative approximations of concrete operations, both for 32bits and 64bits floating points numbers ?

Regression in 0.9.14: illegal option -- -

gmake[2]: Entering directory '/usr/ports/math/apron/work/apron-0.9.14/itv'
/usr/bin/install -d /usr/ports/math/apron/work/stage/usr/local/include /usr/ports/math/apron/work/stage/usr/local/lib
/usr/bin/install itv.h itv_fun.h itv_config.h itv_linexpr.h itv_linearize.h /usr/ports/math/apron/work/stage/usr/local/include
for i in libitvIl.a libitvIll.a libitvRl.a libitvRll.a libitvMPZ.a libitvMPQ.a libitvD.a libitvMPFR.a libitv.a libitvDl.a; do \
        if test -f $i; then /usr/bin/install --strip $i /usr/ports/math/apron/work/stage/usr/local/lib; fi; \
done
install: illegal option -- -
usage: install [-bCcpSsUv] [-f flags] [-g group] [-m mode] [-o owner]
               [-M log] [-D dest] [-h hash] [-T tags]
               [-B suffix] [-l linkflags] [-N dbdir]
               file1 file2
       install [-bCcpSsUv] [-f flags] [-g group] [-m mode] [-o owner]
               [-M log] [-D dest] [-h hash] [-T tags]
               [-B suffix] [-l linkflags] [-N dbdir]
               file1 ... fileN directory
       install -dU [-vU] [-g group] [-m mode] [-N dbdir] [-o owner]
               [-M log] [-D dest] [-h hash] [-T tags]
               directory ...

It looks like the build scripts became Linux-only since the release 0.9.14.
On BSDs install doesn't have such options.

FreeBSD 13.2

Improved use of minimization routines in PPL wrapper

The patch attached improves the use of minimization procedures in the PPL wrapper.

When using strict polyhedra, calling minimized_generators() just after a call to minimized_constraints() is probably NOT going to obtain the desired effect (i.e., minimize both descriptions); due to epsilon-representation implementation details, one can only minimize one description at a time. My guess is that in most cases (probably, all cases except add_generators_array) one is interested in obtaining a minimized constraint representation. As a side note, I also think this explains some old reports of users complaining that when using the PPL in Apron they were sometimes seeing redundant constraints even after a call to minimize().

Note: in contrast, on non-strict polyhedra, the second time you call a PPL minimization procedure it does nothing at all.

ppl-patch.txt

Building the java wrapper: "conflicting types for ‘Java_gmp_Mpfr_jn’"

Hi, I'm trying to build the java wrapper on windows:

$ make
(cd num; make all)
make[1]: Entering directory '/cygdrive/d/apron-0.9.13/apron-0.9.13/num'
make[1]: Nothing to be done for 'all'.
make[1]: Leaving directory '/cygdrive/d/apron-0.9.13/apron-0.9.13/num'
(cd itv; make all)
make[1]: Entering directory '/cygdrive/d/apron-0.9.13/apron-0.9.13/itv'
make[1]: Nothing to be done for 'all'.
make[1]: Leaving directory '/cygdrive/d/apron-0.9.13/apron-0.9.13/itv'
(cd apron; make all)
make[1]: Entering directory '/cygdrive/d/apron-0.9.13/apron-0.9.13/apron'
x86_64-w64-mingw32-gcc.exe  -I../num -I../itv -I/usr/include -E -MM ap_scalar.c ap_interval.c ap_coeff.c ap_dimension.c ap_linexpr0.c ap_lincons0.c ap_generator0.c ap_texpr0.c ap_tcons0.c ap_manager.c ap_abstract0.c ap_policy.c ap_generic.c ap_var.c ap_environment.c ap_linexpr1.c ap_lincons1.c ap_generator1.c ap_texpr1.c ap_tcons1.c ap_abstract1.c ap_linearize.c ap_reducedproduct.c ap_disjunction.c  > depend
make[1]: Nothing to be done for 'all'.
make[1]: Leaving directory '/cygdrive/d/apron-0.9.13/apron-0.9.13/apron'
(cd newpolka; make all)
make[1]: Entering directory '/cygdrive/d/apron-0.9.13/apron-0.9.13/newpolka'
make[1]: Nothing to be done for 'all'.
make[1]: Leaving directory '/cygdrive/d/apron-0.9.13/apron-0.9.13/newpolka'
(cd box; make all)
make[1]: Entering directory '/cygdrive/d/apron-0.9.13/apron-0.9.13/box'
make[1]: Nothing to be done for 'all'.
make[1]: Leaving directory '/cygdrive/d/apron-0.9.13/apron-0.9.13/box'
(cd octagons; make MPQ D)
make[1]: Entering directory '/cygdrive/d/apron-0.9.13/apron-0.9.13/octagons'
make[1]: Nothing to be done for 'MPQ'.
make[1]: Nothing to be done for 'D'.
make[1]: Leaving directory '/cygdrive/d/apron-0.9.13/apron-0.9.13/octagons'
(cd taylor1plus; make all)
make[1]: Entering directory '/cygdrive/d/apron-0.9.13/apron-0.9.13/taylor1plus'
make[1]: Nothing to be done for 'all'.
make[1]: Leaving directory '/cygdrive/d/apron-0.9.13/apron-0.9.13/taylor1plus'
(cd japron; make)
make[1]: Entering directory '/cygdrive/d/apron-0.9.13/apron-0.9.13/japron'
x86_64-w64-mingw32-gcc.exe -Wcast-qual -Wswitch -Werror-implicit-function-declaration -Wall -Wextra -Wundef -Wbad-function-cast -Wcast-align -Wstrict-prototypes -Wno-unused -Wno-unused-parameter -Wno-unused-function -std=c99 -U__STRICT_ANSI__ -fPIC -O3 -DNDEBUG -Wno-int-to-pointer-cast -Wno-pointer-to-int-cast -Wno-bad-function-cast -c  -I/usr/include -I/usr/include -I/usr/include -IC:\Program Files\Java\jdk-16.0.1/include -IC:\Program Files\Java\jdk-16.0.1/include/linux -I../apron -I../box -I../newpolka -I../octagons -I../ppl -I../products -I C:\Program\ Files\Java\jdk1.8.0_291\include -I C:\Program\ Files\Java\jdk1.8.0_291\include\win32  gmp/gmp_Mpfr.c -o gmp/gmp_Mpfr.o
gmp/gmp_Mpfr.c: In function ‘Java_gmp_Mpfr_root’:
gmp/gmp_Mpfr.c:830:3: warning: ‘mpfr_root’ is deprecated [-Wdeprecated-declarations]
  830 |   return mpfr_root(as_mpfr(o1), as_mpfr(o2), i, p);
      |   ^~~~~~
In file included from gmp/jgmp.h:16,
                 from gmp/gmp_Mpfr.c:11:
/usr/x86_64-w64-mingw32/sys-root/mingw/include/mpfr.h:727:21: note: declared here
  727 | __MPFR_DECLSPEC int mpfr_root (mpfr_ptr, mpfr_srcptr, unsigned long,
      |                     ^~~~~~~~~
gmp/gmp_Mpfr.c: At top level:
gmp/gmp_Mpfr.c:1729:24: error: conflicting types for ‘Java_gmp_Mpfr_jn’; have ‘jint(const struct JNINativeInterface_ **, struct _jobject *, int,  struct _jobject *, jint)’ {aka ‘long int(const struct JNINativeInterface_ **, struct _jobject *, int,  struct _jobject *, long int)’}
 1729 | JNIEXPORT jint JNICALL Java_gmp_Mpfr_jn
      |                        ^~~~~~~~~~~~~~~~
In file included from gmp/gmp_Mpfr.c:12:
gmp/gmp_Mpfr.h:1039:24: note: previous declaration of ‘Java_gmp_Mpfr_jn’ with type ‘jint(const struct JNINativeInterface_ **, struct _jobject *, jint,  struct _jobject *, jint)’ {aka ‘long int(const struct JNINativeInterface_ **, struct _jobject *, long int,  struct _jobject *, long int)’}
 1039 | JNIEXPORT jint JNICALL Java_gmp_Mpfr_jn
      |                        ^~~~~~~~~~~~~~~~
make[1]: *** [Makefile:133: gmp/gmp_Mpfr.o] Error 1
make[1]: Leaving directory '/cygdrive/d/apron-0.9.13/apron-0.9.13/japron'
make: *** [Makefile:35: java] Error 2

Since I' not really familiar with C I don't know how to fix it. Can somebody help me?

OCaml 5 support

As far as I understand v0.9.14 will support OCaml 5. I'm just opening this as a tracking issue for having a version supporting OCaml 5 published on Opam.

Installation via opam fails

On my laptop running Arch Linux, with MPFR 4.2.0, GMP 6.2.1, and OCaml 4.14.1 or 4.12.1, opam install apron fails (on a fresh opam switch) to compile apron. Building master from source works. opam pin add --dev-repo apron can be used as a workaround to install master through opam (thanks to octachron on #ocaml).

Crash on call to `of_lincons_array` with constraint `x+inf>=0`

Hello,

I've found a crash occurring when of_lincons_array is called with the constraint x+inf >= 0. Here's a simplified example exhibiting the problem:

open Apron

let main () =
  let x = Var.of_string "x" in
  let env = Environment.make [| x |] [||] in
  let man = Polka.manager_alloc_loose () in

  let le = Linexpr1.make env in
  Linexpr1.set_list le [(Coeff.s_of_int 1, x)] (Some (Scalar (Scalar.of_infty 1)));
  Format.printf "le: %a\n%!" Linexpr1.print le;

  let cons = Lincons1.make le Lincons1.SUPEQ in
  Format.printf "cons: %a\n%!" Lincons1.print cons;

  let arr = Lincons1.array_make env 1 in
  Lincons1.array_set arr 0 cons;

  let a = Abstract1.of_lincons_array man env arr in
  Format.printf "%a\n" Abstract1.print a;

  ()

let _ = main ()

Backtrace:

#0  0x00007fffee74d9d8 in __gmpn_rshift () from /lib/x86_64-linux-gnu/libgmp.so.10
#1  0x00007fffee77eb25 in __gmpn_divexact () from /lib/x86_64-linux-gnu/libgmp.so.10
#2  0x00007fffee73ac98 in __gmpz_divexact () from /lib/x86_64-linux-gnu/libgmp.so.10
#3  0x00007fffee1f6ec3 in vector_set_itv_linexpr () from /home/mm7/.opam/default/share/apron/lib/libpolkaMPQ.so
#4  0x00007fffee1f702e in vector_set_itv_lincons () from /home/mm7/.opam/default/share/apron/lib/libpolkaMPQ.so
#5  0x00007fffee1f7482 in matrix_set_itv_lincons_array () from /home/mm7/.opam/default/share/apron/lib/libpolkaMPQ.so
#6  0x00007fffee203593 in poly_meet_itv_lincons_array () from /home/mm7/.opam/default/share/apron/lib/libpolkaMPQ.so
#7  0x00007fffee203859 in pk_meet_lincons_array () from /home/mm7/.opam/default/share/apron/lib/libpolkaMPQ.so
#8  0x00007fffee630f29 in ap_abstract0_meet_lincons_array () from /home/mm7/.opam/default/share/apron/lib/libapron.so
#9  0x00007fffee63aea9 in ap_abstract1_meet_lincons_array () from /home/mm7/.opam/default/share/apron/lib/libapron.so
#10 0x000055555593e845 in camlidl_abstract1_ap_abstract1_meet_lincons_array_with ()
#11 0x000055555579d2ef in camlDune__exe__Newmain4__main_465 () at abstract1.ml:270
#12 0x000055555579d39f in camlDune__exe__Newmain4__entry () at driver/newmain4.ml:23
#13 0x00005555557988c9 in caml_program ()
#14 0x0000555555976781 in caml_start_program ()
#15 0x0000555555976aec in caml_startup_common (argv=0x7fffffffdd88, pooling=<optimized out>, pooling@entry=0) at startup_nat.c:160
#16 0x0000555555976b6b in caml_startup_exn (argv=<optimized out>) at startup_nat.c:167
#17 caml_startup (argv=<optimized out>) at startup_nat.c:172
#18 caml_main (argv=<optimized out>) at startup_nat.c:179
#19 0x0000555555797cdc in main (argc=<optimized out>, argv=<optimized out>) at main.c:37

Suggestion: integer division and linearization could be more precise

Let us consider this simple program:

int m = rand(2, 9);
int y = rand(0, 2020);
int y2 = y + ((m + 1) / 12);

The relational numerical domain is able to infer that 12y + m ≤ 12y2 + 11 /\ 12y2 ≤ 12y + m + 1. I would have expected y2 = y since m+1 < 12 => (m+1)/12 = 0 over integers.

I guess the linearization could be improved in that case.

Disequality constraint has no effect on abstract value representing equality

Hi,
I realized that applying a disequality constraint (say x <> 1) on an abstract value representing an equality (say x = 1) has no effect, and I was wondering if this is the intended behavior or if it is a precision bug.
Here is a working example:

open Apron

let manoct = Oct.manager_alloc ()
let round_typ = Texpr1.Near
let coeff_typ  = Texpr1.Int

let var_x = Var.of_string "x"
let env   = Environment.make [|var_x|] [||]

(*** Abstract value x = 1 ***)
(* x = 1 constraint *)
let x_minus_1 =
  let open Texpr1 in
  Binop(Sub, Var(var_x), Cst(Coeff.s_of_int 1), coeff_typ, round_typ)

let x_eq_1 =
  Tcons1.make
    (Texpr1.of_expr env x_minus_1)
    Tcons1.EQ

(* Abstract value *)
let eq          = Tcons1.array_make env 1
let ()           = Tcons1.array_set eq 0 x_eq_1
let abs_val = Abstract1.of_tcons_array manoct env eq

(*** Constraint x <> 1 ***)
let x_neq_1 =
  Tcons1.make
    (Texpr1.of_expr env x_minus_1)
    Tcons1.DISEQ

let neq = Tcons1.array_make env 1
let ()    = Tcons1.array_set neq 0 x_neq_1

(*** Test ***)
let res = Abstract1.meet_tcons_array manoct abs_val neq

let print_array ppf array = Tcons1.array_print ppf array
let () =
  Format.fprintf
    Format.std_formatter
    "@[<hv 0>@[Applying constraint@;<1 2>%a@]@ @[to abtract value@;<1 2>%a@]@ @[yields@;<1 2>%a@]@]@."
    print_array neq
    Abstract1.print abs_val
    Abstract1.print res

it produces the following output:

Applying constraint [|x -_i,n 1 <> 0|]
to abtract value [|x-1>=0; -x+1>=0|]
yields [|x-1>=0; -x+1>=0|]

Installs libraries without extension

plist looks like this:

...
lib/avo.idl
lib/libap_pkgrid.
lib/libap_pkgrid.a
lib/libap_pkgrid_debug.
lib/libap_pkgrid_debug.a
lib/libap_ppl.
lib/libap_ppl.a
lib/libap_ppl_debug.
lib/libap_ppl_debug.a
lib/libapron.
lib/libapron.a
lib/libapron_debug.
lib/libapron_debug.a
lib/libavoD.
...

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.