Security Bloggers Network 
SBN

Constraint Solvers

by Jason on December 22, 2010

Lately, I’ve become interested in integer factorization and have been playing with constraint solvers. I started out with minion but quickly became frustrated. Minion does not support nesting of constraints or custom constraints from what I can tell. The set of equations I was working with were mostly comprised of terms that were either a*b mod 10 or (a*b – a*b mod 10) / 10. I would need to have all sorts of intermediate variables and constraints to express these terms. Which isn’t difficult, but would be tedious.

Enter python-constraint. This module is awesome and I thank the author for creating it. It allowed me to write constraints that were easy to read and understand. It supports constraints expressed as lambda functions (nameless functions in py). Unfortunately, the worst case performance of python-constraint is not great when compared to minion. I ended up writing a simple benchmark in py and minion to contrast the differences. Here is the python benchmark. It is nice and readable.
import sys
from constraint import *
p = Problem()
p.addVariables([“x”, “y”], range(0, 999))
p.addVariable(“z”, range(0, 999999))
p.addConstraint(lambda x, y: x > 1 and y > 1, [“x”, “y”])
p.addConstraint(lambda x, y, z: x * y == z, [“x”, “y”, “z”])
p.addConstraint(lambda z: z == 123456, [“z”])
print p.getSolution()
This little snippet took 17 minutes and 11 seconds to complete.
time ./bench.py
{‘y’: 192, ‘x’: 643, ‘z’: 123456}
real 17m16.996s
user 17m11.200s
sys 0m0.392s
And now, minion:
MINION 3
**VARIABLES**
DISCRETE x {0..999}
DISCRETE y {0..999}
DISCRETE z {0..999999}
**SEARCH**
VARORDER [x, y]
PRINT[[x, y, z]]
**TUPLELIST**
**CONSTRAINTS**
product(x, y, z)
eq(z, 123456)
sumgeq([x], 2)
sumgeq([y], 2)
**EOF**
Minion spits out a result in under 1 second. Yipes.
Sol: 192 643 123456
Solution Number: 1
Time:0.000000
Nodes: 2
Solve Time: 0.208013
Total Time: 0.276017
Total System Time: 0.288018
Total Wall Time: 0.651100
Maximum Memory (kB): 0
Total Nodes: 2
Problem solvable?: yes
Solutions Found: 1
real 0m0.680s
user 0m0.276s
sys 0m0.312s
That’s a huge reduction in processing time. Note that both problems are poorly structured. Looks like I may need to dive into that tedious process of translating equations to minion.

*** This is a Security Bloggers Network syndicated blog from Armchair Stratosphere authored by Jason. Read the original post at: http://maliciousattacker.blogspot.com/2010/12/constraint-solvers.html

Jason , ,