Code Monkey home page Code Monkey logo

Comments (3)

nguyenthanhvuh avatar nguyenthanhvuh commented on June 9, 2024

Yes, unfortunately while pure dynamic invariant generation doesn't have problem with library function like sqrt, DIG relies on symbolic execution and such to check the results and they might have problem with these functions. A work around is using a nonsqrt version: https://github.com/unsat/dig/blob/dev/benchmark/c/nla_full/knuth_nosqrt.c

from dig.

TaihuLight avatar TaihuLight commented on June 9, 2024

@nguyenthanhvuh Thank you for your reply.
The newly updated DIG can remove redundancy from eqts. However, it does not support removing redundancy from ineqts. For the program, e.g,

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

void vassume(int b){}
void vtrace(int x, int y){} 

void mainQ( ) 
{
  int x,y;  
  x=0;
  y=0;
  vassume (x==0&&y==0);  
  while(x<=100)
    {// loop invariant:x==y
      vtrace(x,y);
      y=y+1;
      x=x+1;
    } 
    //assert(x==y);
}

void main(int argc, char **argv){
    mainQ();
}

the invariants generated with DIG is

sage -python -O dig.py bench16_potsumm1.c -log 3 -nominmax -nominmaxplus -nomp -maxdeg 5 -seed 2
settings:INFO:2021-07-02 15:25:23.002700: dig.py bench16_potsumm1.c -log 3 -nominmax -nominmaxplus -nomp -maxdeg 5 -seed 2
alg:INFO:analyze '/home/ly/Music/benchmark-tasep/bench16_potsumm1.c'
alg:INFO:compute symbolic states (4.63s)
alg:INFO:infer invs at 1 locs: vtrace
alg:INFO:found 1 eqts (1.41s)
alg:INFO:found 5 ieqs (0.12s)
alg:INFO:test 6 invs using 101 traces (0.02s)
alg:INFO:simplify 6 invs (0.04s)
* prog bench16_potsumm1 locs 1;  invs 4 (Eqt: 1, Oct: 3) V 2 T 2 D 1;  NL 0 (1) ;
-> time eqts 1.4s, ieqs 0.1s, simplify 0.1s, symbolic_states 4.6s, total 6.2s
-> checks  0 () change depths 0 () change vals 0 ()
-> max  0 () change depths 0 ()
runs 1
rand seed 2.0, test (11, 57)
vtrace (4 invs):
1. x - y == 0
2. -y <= 0
3. x - y <= 0
4. -x + y <= 0
tmpdir: /var/tmp/dig_2_lke27k9i

The 3th and 4th invariants are equal to the 1st one, then they are redundant and can be removed.
(1) Does DIG support removing redundancy from ineqts (e.g., Removing x-y<=0 and -x+y<=0 for the above result)?
(2) If not, will DIG support this operation in the coming days?

from dig.

nguyenthanhvuh avatar nguyenthanhvuh commented on June 9, 2024

This is by design. In many cases the redundant invariants are still useful and not easily seen from the stronger, independent ones. So if I just eliminate all redundant ones the developers sometimes don't see what they expect. Given that the total number of generated invariants is not too long, I've decided to keep the equalities and some shorter inequalities, even though they might be redundant.

from dig.

Related Issues (20)

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.