Opened 7 years ago

Closed 3 years ago

#14549 closed defect (fixed)

Memory leak in algebraic_immunity of BooleanFunction class

Reported by: okazymyrov Owned by: asante
Priority: minor Milestone: sage-8.0
Component: cryptography Keywords: algebraic_immunity, BooleanFunction, memory leak
Cc: Merged in:
Authors: Friedrich Wiemer Reviewers: Martin Albrecht
Report Upstream: N/A Work issues:
Branch: b350237 (Commits) Commit: b350237676f95b1cc666dd0347982b7c588beaa7
Dependencies: Stopgaps:

Description (last modified by asante)

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?.

Change History (15)

comment:1 Changed 7 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:2 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:3 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:4 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:5 Changed 3 years ago by asante

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?

comment:6 Changed 3 years ago by nbruin

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)

comment:7 Changed 3 years ago by asante

I tried to simple remove the inheritance of UniqueRepresentation?:

diff --git a/src/sage/rings/polynomial/pbori.pyx b/src/sage/rings/polynomial/pbori.pyx
index 812f3b9..b6b761a 100644
--- a/src/sage/rings/polynomial/pbori.pyx
+++ b/src/sage/rings/polynomial/pbori.pyx
@@ -1835,7 +1835,7 @@ def get_var_mapping(ring, other):
     return var_mapping
 
 
-class BooleanMonomialMonoid(UniqueRepresentation,Monoid_class):
+class BooleanMonomialMonoid(Monoid_class):
     """
     Construct a boolean monomial monoid given a boolean polynomial
     ring.

but this does not seem to solve the problem for me (ie. it still leaks).

Interestingly, there seems to be no leak, when not importing BooleanPolynomialRing? from pbori before. I guess it then calls the constructor from sage/rings/polynomial/polynomial_ring_constructor.py

Calling this constructor in annihilator also seems to solve the memory leak in the boolean_functions module.

comment:8 Changed 3 years ago by nbruin

That sounds like a reasonable hack for the immediate problem. It looks like pbori.BooleanPolynomialRing isn't UniqueRepresentation? by itself, so calling the factory function is definitely the way to go.

Your tests suggest there needs to be more work if we actually want to solve the underlying leak (there are more polynomial rings that leak: anything that has to do with libsingular has eternal life too). With using the appropriate factory function, you will see that

for i in range(10000):
    R=BooleanPolynomialRing(8,"x%s"%i)

still leaks.

comment:9 Changed 3 years ago by asante

  • Branch set to u/asante/Memory_leak_in_algebraic_immunity_of_BooleanFunction_class
  • Milestone changed from sage-6.4 to sage-8.0
  • Owner changed from mvngu to asante

comment:10 Changed 3 years ago by git

  • Commit set to b350237676f95b1cc666dd0347982b7c588beaa7

Branch pushed to git repo; I updated commit sha1. New commits:

b350237hack: solving the immediate memory leak here

comment:11 Changed 3 years ago by asante

  • Status changed from new to needs_review

comment:12 Changed 3 years ago by asante

  • Authors set to Friedrich Wiemer
  • Description modified (diff)
  • Keywords memory leak added

comment:13 Changed 3 years ago by nbruin

There is some related discussion on #21892. Apparently UniqueRepresentation is there because of a pickling problem and possibly we can do away with BooleanPolynomialRing?.

One solution is to close this ticket by merging the branch here and leave #21892 open for resolving the underlying problem.

comment:14 Changed 3 years ago by malb

  • Reviewers set to Martin Albrecht
  • Status changed from needs_review to positive_review

Looks good to me.

comment:15 Changed 3 years ago by vbraun

  • Branch changed from u/asante/Memory_leak_in_algebraic_immunity_of_BooleanFunction_class to b350237676f95b1cc666dd0347982b7c588beaa7
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.