Comments (3)
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.
@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.
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)
- Support array invariants from traces HOT 1
- support float point numbers from traces
- Support purely random trace generation (no symbolic execution) HOT 1
- replace symbolic execution with fuzzing HOT 1
- replace CIL with pycparser HOT 2
- Support congruence domain (trace only) HOT 1
- Support Java analysis in Docker
- Emphasize Relational and Non-Relational Abstract Domains HOT 1
- user term is broken HOT 2
- Why can't I get the analysis results of this simple trace files? HOT 1
- How to analyze java in docker HOT 1
- add beartype HOT 1
- add ability to check user-supplied invariants in src code
- dealing with strong preconds
- Issue with setting up using Docker HOT 4
- docker issue (ModuleNotFoundError: No module named 'pycparser') HOT 4
- Using dynamically generated invariants to help static analyzers to prove properties that they cannot prove previously
- cannot generate inv from Timos & Ferhat HOT 2
- Docker Issue (SARL Configuration Error: Mismatched Z3 Version) HOT 2
- Some problems encountered while testing custom cases HOT 8
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
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.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from dig.