Memory leak in algebraic_immunity of BooleanFunction class

[sagetrac-okazymyrov]

On my Mac OS X 10.8.3 the code

from sage.crypto.boolean_function import BooleanFunction
s=[BooleanFunction(random_vector(GF(2),16).list()).algebraic_immunity() for g in xrange(100)]
s=[BooleanFunction(random_vector(GF(2),16).list()).algebraic_immunity() for g in xrange(100)]

takes around 5GB of RAM on each "s=..." part. You can repeat the procedure for new 5GB.

Without algebraic_immunity function, the problem disappears.

The actual leak happens in BooleanPolynomialRing, see the below discussion. For this instance, the leak can be somewhat prevented, by using the constructor factory for BooleanPolynomialRing.

Component: cryptography

Keywords: algebraic_immunity, BooleanFunction

Author: Friedrich Wiemer

Branch/Commit: b350237

Reviewer: Martin Albrecht

Issue created by migration from https://trac.sagemath.org/ticket/14549

[pfasante]

comment:5

I took a look at this issue, it is still present in sage-8.0. But it seems as this is not a problem in the algebraic_immunity function, but, inherited from the call to annihilator, a problem with pbori's BooleanPolynomialRing objects. The memory leak can be reproduced by

from sage.rings.polynomial.pbori import BooleanPolynomialRing
s=[BooleanPolynomialRing(8, 'x') for _ in xrange(100)]

and repeating the last line.

I skimmed over the PolyBoRi wrapper code, but I have no idea about cython and how this wrapping works in sage, so I'm a bit lost here :) Maybe someone else has a idea, what to do here.

Should this ticket be somehow changed? Closed as the problem is somewhere else, or how to proceed?

[nbruin]

comment:6

The leak actually already exists on python level:

import gc
from collections import Counter
gc.collect()
pre={id(c) for c in gc.get_objects()}
from sage.rings.polynomial.pbori import BooleanPolynomialRing
for i in range(100):
    P=BooleanPolynomialRing(8, 'x')
    del P
gc.collect()
post=Counter(type(o) for o in gc.get_objects() if id(o) not in pre)
sorted(post.iteritems(),key=lambda t: t[1])

shows that the sage python-level polynomial rings remain in memory.
Looking at the backreferences graph:

objgraph.show_backrefs((a for a in gc.get_objects() if type(a) is sage.rings.polynomial.pbori.BooleanPolynomialRing).next(),filename="g.png",max_depth=6)

You can see there is a circular reference between
sage.rings.polynomial.pbori.BooleanMonomialMonoid and
sage.rings.polynomial.pbori.BooleanPolynomialRing. Furthermore, the polynomial ring is a construction parameter for the monoid. This puts a strong reference to the polynomial ring in the CachedRepresentation cache, so the cycle is kept alive.

The simple solution is to not make BooleanMonomialMonoid to be UniqueRepresentation. It probably doesn't need to be. If that's not an option, then BooleanPolynomialRing isn't allowed to store any references to the BooleanMonomialMonoid (after all, it can look it up in the CachedRepresentation cache ...)

This is a classic memory leak that keeps happening over and over.

(it could still be that pbori leaks underneath as well, but the construction above can already explain exploding memory use)