Mercurial > pysmcl
changeset 263:7b9a5eaf2e88
Merge
author | Sigurd Meldgaard <stm@daimi.au.dk> |
---|---|
date | Wed, 24 Feb 2010 13:06:52 +0100 |
parents | f2610aa01a3d (current diff) c837fa9ff823 (diff) |
children | 74b8ba12cc18 |
files | examples/poker.py |
diffstat | 12 files changed, 99 insertions(+), 442 deletions(-) [+] |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/INSTALL Wed Feb 24 13:06:52 2010 +0100 @@ -0,0 +1,17 @@ +Requirements: + +To run a pysmcl application you will need a working install of +Viff (http://viff.dk), and that again requires a working Twisted, GMP, + +This project uses the Python module ast, and therefore requires at +least Python 2.6 + +To run: + +To use the pysmcl runner, put your pysmcl base directory into your +PYTHONPATH environment variable. And run: + +python -m pysmcl.runpysmcl app.py player.ini + +Where app.py is a file containing the pysmcl script, and player.ini +contains the viff configuration of you want to use.
--- a/README Tue Feb 23 14:30:56 2010 +0100 +++ b/README Wed Feb 24 13:06:52 2010 +0100 @@ -1,46 +1,38 @@ -Requirements: - -To run a pysmcl application you will need a working install of -Viff (http://viff.dk), and that again requires a working Twisted, GMP, - -This project uses the Python module ast, and therefore requires at -least Python 2.6 +A prototype implementation of PySMCL -To run: -To use the pysmcl runner, put your pysmcl base directory into your -PYTHONPATH environment variable. And run: - -python -m pysmcl.runpysmcl app.py player.ini - -Where app.py is a file containing the pysmcl script, and player.ini -contains the viff configuration of you want to use. +See installation instructions in INSTALL -A quick overview of the structure and files +A quick overview of the directory structure, and files: pysmcl: Contains the source code of the implementation of the PySmcl - language. compatibility_check.py: Checks if @secret functions use - features outside their scope flow.py: Builds a flow graph, and does - fixpoint analysis on it graph.py: Abstract datatype for a flowgraph, - contains a todot method util.py: Error-handling pretty_print.py: - Functions for pretty-printing the python AST-nodes + language. + + flow.py: Builds a flow graph, and does fixpoint analysis on it + graph.py: Abstract datatype for a flowgraph, contains a todot method + util.py: Error-handling + pretty_print.py: Functions for pretty-printing the python AST-nodes secret_annotator.py: Analyses secret variables/expressions - proof_burden.py: Still only Proof of concept, prints out a - proof-burden for openings secret_ifs.py: Rewrites secret annotations + proof_burden.py: Still only Proof of concept, prints out a proof-burden for openings + secret_ifs.py: Rewrites secret annotations + compatibility_check.py: Checks if @ideal_functionalities use unsupported features + functions.py: the fundamental functions of pysmcl programs + runtime_sugar.py: changes calls so they fit with the Viff framework + editor_info.py: Analyses a program, and outputs info, suitable for the eclipse plugin ideal_functionality.py: The decorator is declared here pysmcl/test: Various kinds of tests. -pysmcl/tes/unit: Unit tests. +pysmcl/test/unit: Unit tests. doctests.py: Use this to run all doctests (must be modified when new files get doctests) run as python pysmcl/test/unit/doctests.py +eclipse/: An eclipse plugin + Examples: Contains example applications - while-loop.py: a basic example + millionaires.py: The millionaires problem + while-loop.py: A binary search on secret values, for an auction + proofexample.thy: experiments with formal proofs in Isabelle - -Semantics: Files related to the description of the language. - semantics.tex: A description of the language and analysis. -
--- a/examples/millionaires.py Tue Feb 23 14:30:56 2010 +0100 +++ b/examples/millionaires.py Wed Feb 24 13:06:52 2010 +0100 @@ -1,213 +1,12 @@ - +from pysmcl.functions import result, input, output from pysmcl.ideal_functionality import ideal_functionality -import sys -from optparse import OptionParser - -import viff.reactor -viff.reactor.install() -from twisted.internet import reactor -from twisted.internet.defer import Deferred, DeferredList, gatherResults - -from viff.field import GF -from viff.runtime import Share, create_runtime, gather_shares -from viff.config import load_config -from viff.util import dprint, find_prime -from viff.comparison import Toft07Runtime - -# Load the configuration from the player configuration files. -id, players = load_config(sys.argv[1]) - -# Initialize the field we do arithmetic over. -Zp = GF(30916444023318367583) - -# Read input from the commandline. -input = int(sys.argv[2]) - -print "I am player %d and will input %s" % (id, input) - -# =========================================================================== - -# The not so nice millionaires program -def runNotNiceMills(runtime): - # Input player identity. - ids = runtime.input(runtime.players.keys(), Zp, runtime.id) - # Input player networths. - networths = runtime.input(runtime.players.keys(), Zp, input) - - # Create a list of tuples of identity and corresponding networths. - ls = zip(ids, networths) - - richest, max = millionaries(runtime, ls) - - output_to_all(runtime, richest, max) - -def not_nice_millionaries(runtime, ls): - """Computes the richest millionaire given a list of - pairs of identity and networth. - - Returns a pair of identity and networth of the richest millionaire. - """ - - # Declare temporary variables. - # *richest* contains the identity of the currently richest player. - # *max* contains the networth of the currently richest player. - richest = Share(runtime, Zp, Zp(0)) - max = Share(runtime, Zp, Zp(0)) - - # Loop over all the pairs of identity and networth and compute the maximum. - for id, networth in ls: - b = networth >= current_max - max = b * networth + (1 - b) * max - richest = b * id + (1 - b) * richest - - return richest, max - -# =========================================================================== - -# The nice millionaires program - -@ideal_functionality -def maximum(current_id, current_max, id, networth): - """Computes the maximum of current_max and networth. - - Returns the pair corresponding to the maximum value of - current_max and networth. - """ - identity = current_id - money = current_max - if networth >= current_max: - money = networth - identity = id - return identity, money - -def millionaries(runtime, ls): - """Computes the richest millionaire given a list of - pairs of identity and networth. - - Returns a pair of identity and networth of the richest millionaire. - """ - - # Declare temporary variables. - # *richest* contains the identity of the currently richest player. - # *max* contains the networth of the currently richest player. - richest = Share(runtime, Zp, Zp(0)) - max = Share(runtime, Zp, Zp(0)) - - # Loop over all the pairs of identity and networth and compute the maximum. - for id, networth in ls: - richest, max = maximum(richest, max, id, networth) - - return richest, max - -def output_to_all(runtime, richest, max): - # Everyone learns the identity and the networth of the richest. - deferred_identity = runtime.output(richest) - deferred_max = runtime.output(max) - - result = gather_shares([deferred_identity, deferred_max]) - - def result_reporter((id, max)): - print "The richest is player %s he has USD %s" % (id.value, max.value) - result.addCallback(result_reporter) - - runtime.schedule_callback(result, lambda _: runtime.synchronize()) - runtime.schedule_callback(result, lambda _: runtime.shutdown()) - -def output_to_richest(runtime, richest, max): - """Everyone learns the identity of the richest, but not his networth. - - This corresponds to figure 4(A) in the paper - "A Domain-Specific Programming Language for Secure Multiparty Computation" - by Janus Dam Nielsen and Michael I. Schwartzbach. - - """ - - deferred_identity = runtime.output(richest) - - def result_reporter(id): - print "The richest is player %s" % id.value - deferred_identity.addCallback(result_reporter) - - runtime.schedule_callback(deferred_identity, lambda _: runtime.synchronize()) - runtime.schedule_callback(deferred_identity, lambda _: runtime.shutdown()) - -def output_status(runtime, richest, max): - """Everyone learns their own status, but not the others. - - This corresponds to figure 4(B) in the paper - "A Domain-Specific Programming Language for Secure Multiparty Computation" - by Janus Dam Nielsen and Michael I. Schwartzbach. - - """ - - deferred_identity1 = None - deferred_identity2 = None - - secret_ids = runtime.input(runtime.players.keys(), Zp, runtime.id) - ids = runtime.players.keys() - - ls = zip(ids, secret_ids) - - for id, secret_id in ls: - # This is a bit ugly because the runtime does not provide a equals method. - r1 = secret_id >= richest - r2 = richest >= secret_id - d1 = runtime.output(r1, [id]) - d2 = runtime.output(r2, [id]) - if d1 is not None: - deferred_identity1 = d1 - deferred_identity2 = d2 - - def result_reporter((status1, status2)): - if status1.value and status2.value: - print "> You are the richest." - else: - print "> You are not so rich." - - deferred_identity = gather_shares([deferred_identity1, deferred_identity2]) - - deferred_identity.addCallback(result_reporter) - - runtime.schedule_callback(deferred_identity, lambda _: runtime.synchronize()) - runtime.schedule_callback(deferred_identity, lambda _: runtime.shutdown()) - - -def runMills(runtime): - # Input player identity. - ids = runtime.input(runtime.players.keys(), Zp, runtime.id) - # Input player networths. - networths = runtime.input(runtime.players.keys(), Zp, input) - - # Create a list of tuples of identity and corresponding networths. - ls = zip(ids, networths) - - richest, max = millionaries(runtime, ls) - -# output_to_all(runtime, richest, max) - -# output_to_richest(runtime, richest, max) - - output_status(runtime, richest, max) - -def errorHandler(failure): - print "Error: %s" % failure - - -# Parse command line arguments. -parser = OptionParser() -Toft07Runtime.add_options(parser) -options, args = parser.parse_args() - -if len(args) == 0: - parser.error("you must specify a config file") -else: - id, players = load_config(args[0]) - -# Create a deferred Runtime and ask it to run our protocol when ready. -pre_runtime = create_runtime(id, players, 1, options, Toft07Runtime) -#pre_runtime.addCallback(runNotNiceMills) -pre_runtime.addCallback(runMills) -pre_runtime.addErrback(errorHandler) -# Start the Twisted event loop. -reactor.run() +@ideal_functionality() +def main(): + a = input("How rich are you?", 1, 0, 100) + b = input("How rich are you?", 2, 0, 100) + c = output(a > b) + if(c): + print "Player 1 is the richest!" + else: + print "Player 2 is the richest!"
--- a/examples/poker.py Tue Feb 23 14:30:56 2010 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,144 +0,0 @@ - -import sys -from optparse import OptionParser - - -import viff.reactor -viff.reactor.install() -from twisted.internet import reactor -from twisted.internet.defer import Deferred, DeferredList, gatherResults - -from viff.field import GF -from viff.runtime import Share, create_runtime, gather_shares -from viff.config import load_config -from viff.util import dprint, find_prime, rand -from viff.comparison import Toft07Runtime - -from secretset import SecretSet - -# Load the configuration from the player configuration files. -id, players = load_config(sys.argv[1]) - -# Initialize the field we do arithmetic over. -Zp = GF(53) - -print "I am player %d" % id - - -class Dealer(object): - - def __init__(self, runtime, random, one): - self.runtime = runtime - self.random = random - self.one = one - self.dealt_cards = SecretSet(random, one) - - def next_card(self): -# print "n1" - def choose_random_card(x, r): -# print "n3" - if x: -# print "n4" - self.dealt_cards.add(r) - return r, - else: -# print "n5", self.random - r = self.random() -# print "n6" - contains = self.dealt_cards.contains(r) -# print "n7" - v = self.runtime.output(contains) -# print "n8" - v.addCallback(choose_random_card, r) -# print "n9" - v.addErrback(errorHandler) -# print "n10" - return v -# print "n2" - return choose_random_card(Zp(0), None) - - def get_list_of_cards(self, n): -# print "ls", n - if 0 >= n: -# print "foobar" - return [] -# print "ls2" - def f(card, n, acc): -# print "f:", card, acc, n - acc.append(card[0]) - if 0 == n: -# print "f: done" - return acc - else: -# print "f: cont." - card = self.next_card() - card.addCallback(f, n - 1, acc) - return card -# print "ls3" - card = self.next_card() -# print "ls4" - self.runtime.schedule_callback(card, f, n - 1, []) -# print "ls5" - return card - - -def get_one(runtime): - if 1 == runtime.id: - one = runtime.input([1], Zp, 1) - else: - one = runtime.input([1], Zp, None) - return one - - -def playPoker(runtime): - num_cards = 4 - - def random(): - r = runtime.prss_share_random(Zp) - return r - - one = get_one(runtime) - dealer = Dealer(runtime, random, one) - - cards = dealer.get_list_of_cards(num_cards*runtime.num_players) - - def deal_cards(cards): - my_cards = [] - for player in runtime.players.keys(): - for card in cards[(player-1)*num_cards:(player*num_cards)]: - c = runtime.output(card, [player]) - if c is not None: - my_cards.append(c) - - def print_cards(cards): - print "You have been dealt the following cards:" - for card in cards: - print "Card nr.", card.value - return None - dls = gatherResults(my_cards) - dls.addCallbacks(print_cards, errorHandler) - return dls - - runtime.schedule_callback(cards, deal_cards) - runtime.schedule_callback(cards, lambda _: runtime.synchronize()) - runtime.schedule_callback(cards, lambda _: runtime.shutdown()) - -def errorHandler(failure): - print "Error: %s" % failure - - -# Parse command line arguments. -parser = OptionParser() -Toft07Runtime.add_options(parser) -options, args = parser.parse_args() - -if len(args) == 0: - parser.error("you must specify a config file") -else: - id, players = load_config(args[0]) - -# Create a deferred Runtime and ask it to run our protocol when ready. -pre_runtime = create_runtime(id, players, 1, options, Toft07Runtime) -pre_runtime.addCallbacks(playPoker, errorHandler) -# Start the Twisted event loop. -reactor.run()
--- a/examples/while-loop.py Tue Feb 23 14:30:56 2010 +0100 +++ b/examples/while-loop.py Wed Feb 24 13:06:52 2010 +0100 @@ -1,8 +1,9 @@ -from pysmcl.functions import get +from pysmcl.functions import result, input, output from pysmcl.ideal_functionality import ideal_functionality from pysmcl.functions import precondition -@ideal_functionality(range={'bids': (-4,4)}) +@ideal_functionality(secrets=['bids'], + range={'bids': (-100, 100)}) def search(bids): precondition("a >= b <=> bids[a] >= bids[b]") precondition("0 >= bids[0]") @@ -10,8 +11,10 @@ low = 0 high = len(bids) while(low < high): + print low, high mid = (low + high) // 2 r = output(bids[mid] >= 0) + print mid if r: high = mid else: @@ -21,10 +24,10 @@ @ideal_functionality() def main(): - bids = [0] * 100 - for i in range(100): - bids1 = get("Buy at price: " + str(i), 1, (0,2)) - bids2 = get("Sell at price: " + str(i), 2, (0,2)) - bids[i] = bids1[i] - bids2[i] + bids = [0] * 3 + for i in range(3): + bids1 = input("Buy at price: " + str(i), 1, 0, 100) + bids2 = input("Sell at price: " + str(i), 2, 0, 100) + bids[i] = bids1 - bids2 a = search(bids) print "Market clearing price: " + str(a)
--- a/pysmcl/bad_calls.py Tue Feb 23 14:30:56 2010 +0100 +++ b/pysmcl/bad_calls.py Wed Feb 24 13:06:52 2010 +0100 @@ -6,9 +6,8 @@ def bad_calls(function_def): for node in ast.walk(function_def): - if isinstance(node, ast.stmt): - e = node.out_values["secret"] if(isinstance(node, ast.Call)): + e = ast.get_ancestor(node, ast.stmt).out_values["secret"] if(not isinstance(node.func, ast.Name)): if(any([expr_secret(i, e) for i in node.args])): util.error("Call of non-fixed function " @@ -25,7 +24,8 @@ " where a non-secret was expected", node) elif(any([expr_secret(i, e) for i in node.args])): util.error("Call of non-secret " - "function with secret argument", node) + "function %s with secret argument" % node.func.id, + node) if(isinstance(node, ast.Subscript) and expr_secret(node.slice,e)): util.error("Secret array indexing is not allowed", node)
--- a/pysmcl/editor_info.py Tue Feb 23 14:30:56 2010 +0100 +++ b/pysmcl/editor_info.py Wed Feb 24 13:06:52 2010 +0100 @@ -8,7 +8,7 @@ import pysmcl.secret_ifs as secret_ifs from pysmcl.util import error from pysmcl.bad_calls import bad_calls - +from pysmcl.ideal_functionality import transform_ifs_fixpoint def main(): try: @@ -21,13 +21,7 @@ decorator = ast.get_ideal_functionality(i) if decorator is None: continue - while True: - secret_analysis(i) - RangeAnalysis().apply(i, {}) - transform_ifs = secret_ifs.TransformIfs() - i = transform_ifs.visit(i) - if not transform_ifs.changed: - break + i = transform_ifs_fixpoint(i) secret_analysis(i) bad_calls(i) func_string = pp.pprint_string(i)
--- a/pysmcl/functions.py Tue Feb 23 14:30:56 2010 +0100 +++ b/pysmcl/functions.py Wed Feb 24 13:06:52 2010 +0100 @@ -1,9 +1,9 @@ from twisted.internet.defer import inlineCallbacks import pysmcl.setup -import random +from random import randint #from viff. import -def get(runtime, prompt, player, lower, upper): +def input(runtime, prompt, player, lower, upper): """ Queries player for an integer in the interval between lower and upper, and returns a sharing of the value.""" if runtime.id == player: @@ -11,7 +11,7 @@ print("Please enter a number in the interval from %d to %d" % (lower, upper)) # a = int(raw_input()) - a = random.randint(lower, upper);print "chose %d for you!" % a + a = randint(lower, upper);print "chose %d for you!" % a if(a < lower or a >= upper): raise RuntimeError("Invalid value shared") return runtime.shamir_share([player], pysmcl.setup.Zp, a)
--- a/pysmcl/ideal_functionality.py Tue Feb 23 14:30:56 2010 +0100 +++ b/pysmcl/ideal_functionality.py Wed Feb 24 13:06:52 2010 +0100 @@ -6,15 +6,17 @@ import pysmcl.ast_wrapper as ast import pysmcl.compatibility_check import pysmcl.pretty_print -import pysmcl.secret_annotator -import pysmcl.secret_ifs +from pysmcl.range_analysis import RangeAnalysis +from pysmcl.secret_annotator import secret_analysis +import pysmcl.secret_ifs as secret_ifs from pysmcl.runtime_sugar import runtime_sugar from pysmcl.bad_calls import bad_calls -debug = True +debug = False def catcher(f): + def c(*args, **kwargs): try: return f(*args, **kwargs) @@ -22,40 +24,40 @@ return e.value return c +def transform_ifs_fixpoint(function_ast): + while True: + secret_analysis(function_ast) + RangeAnalysis().apply(function_ast, {}) + transform_ifs = secret_ifs.TransformIfs() + function_ast = transform_ifs.visit(function_ast) + if not transform_ifs.changed: + break + return function_ast + + def ideal_functionality(range={}, secrets=[]): + def ideal_functionality_helper(f): source_str = inspect.getsource(f) source_ast = ast.parse(source_str) # Returns a module function_ast = source_ast.body[0] # We want only the function - # for i in ast.walk(function_ast): - # print i, getattr(i, "lineno", None) if(debug): pysmcl.pretty_print.pprint(source_ast) print "-"*80 pysmcl.compatibility_check.CompatibilityChecker().visit(function_ast) - transform_ifs = pysmcl.secret_ifs.TransformIfs() - pysmcl.secret_annotator.secret_analysis(function_ast) - t = transform_ifs.visit(function_ast) - while transform_ifs.changed: - pysmcl.secret_annotator.secret_analysis(function_ast) - t = transform_ifs.visit(function_ast) + function_ast = transform_ifs_fixpoint(function_ast) pysmcl.secret_annotator.secret_analysis(function_ast) bad_calls(function_ast) runtime_sugar(function_ast) - t.decorator_list.pop() -# pysmcl.proof_burden.proof_burden(t) + function_ast.decorator_list.pop() if(debug): pysmcl.pretty_print.pprint(source_ast) g = f.__globals__ g["returnValue"] = returnValue env = {} - ast.increment_lineno(t, 10) - # for i in ast.walk(function_ast): - # print i, getattr(i, "lineno", None) - # i.lineno = 3 - # print ast.dump(function_ast) - exec compile(ast.Module([t]), f.__code__.co_filename, "exec") in g, env + exec compile(ast.Module([function_ast]), + f.__code__.co_filename, "exec") in g, env f = env[function_ast.name] return inlineCallbacks(f)
--- a/pysmcl/range_analysis.py Tue Feb 23 14:30:56 2010 +0100 +++ b/pysmcl/range_analysis.py Wed Feb 24 13:06:52 2010 +0100 @@ -367,7 +367,7 @@ return Bottom() if node.func.id == "output": return self.visit(node.args[0]) - if node.func.id == "get": + if node.func.id == "input": return self.visit(node.args[2]).combine(self.visit(node.args[3])) if node.func.id == "range": if(len(node.args) > 1):
--- a/pysmcl/runtime_sugar.py Tue Feb 23 14:30:56 2010 +0100 +++ b/pysmcl/runtime_sugar.py Wed Feb 24 13:06:52 2010 +0100 @@ -9,6 +9,7 @@ return => returnValue """ + def runtime_sugar(f): """ *f* is the AST of a function written in pysmcl (after desuaring if's) and makes an implicit parameter out of the @@ -48,33 +49,24 @@ yield_exp = ast.Yield(value=node) ast.copy_location(yield_exp, node) return yield_exp - if(self.is_function(node, "input")): - r = ast.Attribute(value=runtime, - attr="input", - ctx=ast.Load()) - ast.copy_location(r, node.func) - node.func = r - return node + if(node.func.id == "input"): + node.args.insert(0, runtime) if(node.func.id in pysmcl.secret_annotator.annotated_functions): node.args.insert(0, runtime) - num = ast.copy_location(ast.Num(0), node) - slice = ast.copy_location(ast.Index(num), node) -# return ast.copy_location(ast.Subscript(value=node, -# slice=slice, -# ctx=ast.Load()),node) + yield_exp = ast.Yield(value=node) + ast.copy_location(yield_exp, node) + return yield_exp return node def visit_Return(self, node): returnValue = ast.copy_location( ast.Name(id="returnValue", ctx=ast.Load()), node) -# lst = ast.copy_location(ast.List(elts=[node.value], -# ctx=ast.Load()), node) call = ast.copy_location(ast.Call(func=returnValue, args=[node.value], keywords=[], starargs=None, kwargs=None), node) - + r = ast.copy_location(ast.Expr(value=call), node) return r @@ -84,6 +76,8 @@ Rewriter().visit(f) y = ast.copy_location(ast.Yield(value=ast.copy_location(ast.Num(0), f)), f) e = ast.copy_location(ast.Expr(value=y), f) - if_stm = ast.copy_location(ast.If(test=ast.copy_location(ast.Num(1), f), body=f.body,orelse=[e]), f) + if_stm = ast.copy_location( + ast.If(test=ast.copy_location( + ast.Num(1), f), body=f.body, orelse=[e]), f) f.body = [if_stm] ast.fix_ast_parents(f)
--- a/pysmcl/secret_annotator.py Tue Feb 23 14:30:56 2010 +0100 +++ b/pysmcl/secret_annotator.py Wed Feb 24 13:06:52 2010 +0100 @@ -4,7 +4,7 @@ non_compromising_functions = set(["len", "output", "result", "invariant", "precondition"]) -secret_functions = set(["get"]) +secret_functions = set(["input"]) annotated_functions = {}