TY - GEN
T1 - Inferring min and max invariants using max-plus polyhedra
AU - Allamigeon, Xavier
AU - Gaubert, Stéphane
AU - Goubault, Éric
PY - 2008/8/13
Y1 - 2008/8/13
N2 - We introduce a new numerical abstract domain able to infer min and max invariants over the program variables, based on max-plus polyhedra. Our abstraction is more precise than octagons, and allows to express non-convex properties without any disjunctive representations. We have defined sound abstract operators, evaluated their complexity, and implemented them in a static analyzer. It is able to automatically compute precise properties on numerical and memory manipulating programs such as algorithms on strings and arrays.
AB - We introduce a new numerical abstract domain able to infer min and max invariants over the program variables, based on max-plus polyhedra. Our abstraction is more precise than octagons, and allows to express non-convex properties without any disjunctive representations. We have defined sound abstract operators, evaluated their complexity, and implemented them in a static analyzer. It is able to automatically compute precise properties on numerical and memory manipulating programs such as algorithms on strings and arrays.
U2 - 10.1007/978-3-540-69166-2_13
DO - 10.1007/978-3-540-69166-2_13
M3 - Conference contribution
AN - SCOPUS:48949100159
SN - 3540691634
SN - 9783540691631
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 189
EP - 204
BT - Static Analysis - 15th International Symposium, SAS 2008, Proceedings
T2 - 15th International Static Analysis Symposium, SAS 2008
Y2 - 16 July 2008 through 18 July 2008
ER -