Comments (3)
Usually we would limit the value range, but this task is ridiculously exponential in nature.
The property should still hold if we calculate modulo ULLONG_MAX
, so using unsigned integers would get rid of the undefined behavior. A task where this was done actually already exists as geo1-u.c
. So we could add a task geo1-ull.c
where we use unsigned long long
. This is somewhat unsatisfactory since we want to also have a task where the negative numbers are present. The best way to do this from a software engineers perspective would be to use the builtin overflow functions to check for overflows and terminate in those cases. These overflow checks are not supported by all tools, but coding them in manually is not the way to go if you ask me.
from sv-benchmarks.
Would be the following a general solution for overflows involving multiplication? If we have y * z
(I assume both variables are of type int
), add the following check before assume_abort_if_not(2147483647 / z >= y)
. I tried in a couple of examples where I was having problems (possible because of integer overflows due to multiplications) and it seems to work.
from sv-benchmarks.
This works if both integers are positive only. The general check is more complicated, cf. https://wiki.sei.cmu.edu/confluence/display/c/INT32-C.+Ensure+that+operations+on+signed+integers+do+not+result+in+overflow#INT32C.Ensurethatoperationsonsignedintegersdonotresultinoverflow-CompliantSolution.3 (you might need to reload this page once it is loaded to jump to the right anchor I linked, some weird browser bug at least in chrome)
A general solution in my opinion would be to write assume_abort_if_not(__builtin_smulll_overflow(y,z,*y));
instead of y = y * z;
One of the objectives with sv-benchmarks is to have benchmarks that are close to code that would be found in real software. For real software I would either use builtin overflow functions and report to the callee of such an algorithm whether the calculations worked without an overflow or I would limit the range of inputs to ones that guarantee that there is no overflow.
Bounded tasks are generated anyways in nla-digbench-scaling. So for this issue I would generate two additional tasks:
- geo1-ull.c where we solve the problem by using unsigned long long
- geo1-ll-ovfcheck.c where we use builtin overflow functions to ensure defined behavior
from sv-benchmarks.
Related Issues (20)
- Tasks in seq-mthreaded wrongly marked as non-terminating HOT 2
- Task ntdrivers/floppy2 is not memory safe
- Task ntdrivers/diskperf.i.cil-1.c is not memory safe HOT 2
- ntdrivers/parport.i.cil-2 is not memory safe
- LDV tasks with undefined behaviour and/or wrong verdicts HOT 3
- cut-2 and od-1 from busy-box are not memory safe HOT 1
- Undefined behavior in two AWS benchmarks
- MemSafety - unset subproperty for false verdict
- Incorrect Verification Task
- Implementation-defined behaviour HOT 3
- SV-COMP concurrency benchmarks with data races HOT 3
- "Repeated" benchmarks in pthread-wmm
- why can echo-2.i overflow? HOT 2
- __builtin_unreachable() in LDV benchmarks HOT 3
- Benchmarks for weak memory models HOT 3
- Reachable error in pthread-ext/41_FreeBSD_abd_kbd_sliced
- Use of `__VERIFIER_nondet_*` functions that aren't specified in SV-COMP rules HOT 1
- Info on SV-COMP 2022? HOT 2
- Repository moved to GitLab HOT 1
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 sv-benchmarks.