- PPL-devel - BUGSENG Mailman

[Fwd: Re: Announcing the Parma Polyhedra Library (version 0.2)]
by Roberto Bagnara 20 Nov '01

20 Nov '01

-------- Original Message -------- Subject: Re: Announcing the Parma Polyhedra Library (version 0.2) Date: Mon, 19 Nov 2001 13:12:33 -0800 (PST) From: David Wagner <daw(a)cs.berkeley.edu> To: bagnara(a)cs.unipr.it (Roberto Bagnara) Thanks much for the information! This is the answer I sort of expected, given what I've seen from other polyhedra libraries, but thank you for taking the time to describe your experience. The application that interested me is detection of buffer overrun vulnerabilities in large C applications. Typically one must do a whole-program analysis, and interesting C applications tend to have thousands of relevant integer variables and tens of thousands of statements affecting these variables. Several colleagues and I looked at this problem, and we used a much less precise form of analysis to cope with the scalability issues. Still, this comes with significant costs: you get many false alarms (warnings that don't correspond to real bugs), and our experience suggests that polyhedra-style analysis could make a big improvement in this respect. If you're interested to read more about our work, our paper is online at <http://www.cs.berkeley.edu/~daw/papers/overruns-ndss00.ps>. Nurit Dor, Michael Rodeh, and Mooly Sagiv have done some work on applying polyhedra to the same problem, and they found that they could get a much more accurate analysis, but with the disadvantage that the result could only handle small programs. Thanks again for your note. I found your comments interesting, and I'll continue to follow your progress on this project! Regards, -- David

1 0

ibiblio action notice from the `keeper' program
by Linux Keeper 19 Nov '01

19 Nov '01

At about 2001-11-19 15:49:26 UCT, `keeper' moved the following files from Incoming to libs (special (non-libc) linking libraries): ppl-0.2.tar.gz c++ library for the manipulation of polyhedra ppl.lsm These replaced the following files: ppl-0.1.tar.gz c++ library for the manipulation of polyhedra ppl.lsm Thank you for your contribution of time, effort, and creativity. This message was a form letter generated by keeper 1.54, but replying to it will reach the human who told keeper what to do. You got this note because you're listed as a maintainer or author in the archive part involved. If your package was actually uploaded by someone else, and you know who that person is, please try to get that person to list him or herself in the LSM. -- Serena Fenton (ibiblio co-maintainer) fents(a)ibiblio.org

1 0

Re: Announcing the Parma Polyhedra Library (version 0.2)
by Roberto Bagnara 19 Nov '01

19 Nov '01

David Wagner wrote: > Thanks for the announcement! Do you have any data on what size problems > this scales to? Dear David, we are currently using the library for the analysis of logic and constraint logic programs. Our data-flow analyzer, when applied to the 400+ programs of our benchmark suite, never gives rise to space dimensions of more than a couple of hundreds. That is because the global inter-procedural analysis problem is partitioned in such a way that typical programs do not exceed these numbers (of course, exceptions are always possible and here is where the library being exception-safe plays an important role). > Do you have any sense for whether the library might > be able to handle polyhedra with thousands of variables and tens of > thousands of linear inequalities? My feeling is that the library and the algorithms it uses do not scale that much. Of course, things may be different for problems with a particular structure, but in general the numbers you mentions seem to be out of reach. We keep improving the library though. > (I'm thinking of applications to > inter-procedural program analysis for detecting security vulnerabilities.) We also target that kind of applications. Can you give me some intuition on why scaling to thousands of variables and tens of thousands of linear constraints is necessary and/or desirable? > Regards, > -- David Wagner All the best, Roberto Bagnara -- Roberto Bagnara Computer Science Group Department of Mathematics, University of Parma, Italy http://www.cs.unipr.it/~bagnara/ mailto:bagnara@cs.unipr.it

1 0

Parma Polyhedra Library 0.2
by Roberto Bagnara 14 Nov '01

14 Nov '01

We are glad to announce the release 0.2 of the Parma Polyhedra Library. The Parma Polyhedra Library (PPL) is a C++ library for the manipulation of convex polyhedra. For more information, visit the PPL web site at http://www.cs.unipr.it/ppl/ The PPL development team: Roberto Bagnara <bagnara(a)cs.unipr.it> Patricia M. Hill <hill(a)comp.leeds.ac.uk> Elisa Ricci <ericci(a)cs.unipr.it> Enea Zaffanella <zaffanella(a)cs.unipr.it> New Features ============ o Massive API changes. This would not normally be called "a feature", but the old API was very wrong in a number of ways. More API changes are to be expected for the next few releases. o All user-accessible library methods are now guarded by suitable sanity checks. Exception are thrown whenever the library is not called in the intended way. o A SICStus Prolog interface is now available. It comes with a somewhat interesting demo: a toy CLP(Q) interpreter. o Greatly improved documentation. Bugfixes ======== o Many, many more than we would like to admit. -- Roberto Bagnara Computer Science Group Department of Mathematics, University of Parma, Italy http://www.cs.unipr.it/~bagnara/ mailto:bagnara@cs.unipr.it

1 0

w3ppl/htdocs/templates macros.tmpl
by Roberto Bagnara 14 Nov '01

14 Nov '01

CVSROOT: /cvs/ppl Module name: w3ppl Changes by: roberto(a)cs.unipr.it 2001-11-14 06:40:22 Modified files: htdocs/templates: macros.tmpl Log message: Bump version number. Patches: http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/w3ppl/htdocs/templates/macros.tmp…

1 0

The PPL 0.2 release process begins
by Roberto Bagnara 13 Nov '01

13 Nov '01

Dear all, the sources have tentatively been tagged for the release (the tag is `ppl_0_2release'). If all the tests are passed, tomorrow we will release PPL 0.2. Ciao, Roberto -- Roberto Bagnara Computer Science Group Department of Mathematics, University of Parma, Italy http://www.cs.unipr.it/~bagnara/ mailto:bagnara@cs.unipr.it

1 0

ppl ChangeLog
by Roberto Bagnara 13 Nov '01

13 Nov '01

CVSROOT: /cvs/ppl Module name: ppl Changes by: roberto(a)cs.unipr.it 2001-11-13 21:57:53 Modified files: . : ChangeLog Log message: Updated. Patches: http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/ppl/ChangeLog.diff?cvsroot=ppl&r1…

1 0

w3ppl ./NEWS htdocs/ppl.raw
by Roberto Bagnara 13 Nov '01

13 Nov '01

CVSROOT: /cvs/ppl Module name: w3ppl Changes by: roberto(a)cs.unipr.it 2001-11-13 21:55:32 Modified files: . : NEWS htdocs : ppl.raw Log message: Mention that we have greatly improved the documentation. Patches: http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/ppl/NEWS.diff?cvsroot=ppl&r1=1.4&… http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/w3ppl/htdocs/ppl.raw.diff?cvsroot…

1 0

ppl ChangeLog
by Roberto Bagnara 13 Nov '01

13 Nov '01

CVSROOT: /cvs/ppl Module name: ppl Changes by: roberto(a)cs.unipr.it 2001-11-13 21:48:47 Modified files: . : ChangeLog Log message: Updated. Patches: http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/ppl/ChangeLog.diff?cvsroot=ppl&r1…

1 0

ppl/interfaces/Prolog Prolog_interface.dox
by Roberto Bagnara 13 Nov '01

13 Nov '01

CVSROOT: /cvs/ppl Module name: ppl Changes by: roberto(a)cs.unipr.it 2001-11-13 21:27:09 Modified files: interfaces/Prolog: Prolog_interface.dox Log message: Use `| ?-' everywhere a goal is introduced. Patches: http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/ppl/interfaces/Prolog/Prolog_inte…

1 0