viff

changeset 771:9be4b49842ad

Merged.
author Martin Geisler <mg@daimi.au.dk>
date Thu, 22 May 2008 21:49:53 +0200
parents 963d04c31c7d f993269c2660
children 69486719ad7a
files
diffstat 4 files changed, 177 insertions(+), 1 deletions(-) [+]
line diff
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/apps/gc-test.py	Thu May 22 21:49:53 2008 +0200
     1.3 @@ -0,0 +1,82 @@
     1.4 +#!/usr/bin/python
     1.5 +
     1.6 +# Copyright 2008 VIFF Development Team.
     1.7 +#
     1.8 +# This file is part of VIFF, the Virtual Ideal Functionality Framework.
     1.9 +#
    1.10 +# VIFF is free software: you can redistribute it and/or modify it
    1.11 +# under the terms of the GNU Lesser General Public License (LGPL) as
    1.12 +# published by the Free Software Foundation, either version 3 of the
    1.13 +# License, or (at your option) any later version.
    1.14 +#
    1.15 +# VIFF is distributed in the hope that it will be useful, but WITHOUT
    1.16 +# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
    1.17 +# or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
    1.18 +# Public License for more details.
    1.19 +#
    1.20 +# You should have received a copy of the GNU Lesser General Public
    1.21 +# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
    1.22 +
    1.23 +# This application will is meant for 3 players. They will run forever,
    1.24 +# sharing and summing integers. After 100 iterations the time per
    1.25 +# iteration and the current memory allocation is printed. The
    1.26 +# allocation should stay *constant* since shares are released at the
    1.27 +# same speed as they are allocated.
    1.28 +
    1.29 +import sys
    1.30 +import gc
    1.31 +from time import time
    1.32 +from pprint import pprint
    1.33 +
    1.34 +from twisted.internet import reactor
    1.35 +
    1.36 +from viff.field import GF
    1.37 +from viff.runtime import create_runtime
    1.38 +from viff.config import load_config
    1.39 +from viff.util import find_prime
    1.40 +
    1.41 +id, players = load_config(sys.argv[1])
    1.42 +
    1.43 +
    1.44 +def memory_usage():
    1.45 +    """Read memory usage of the current process."""
    1.46 +    status = None
    1.47 +    try:
    1.48 +        # This will only work on systems with a /proc file system
    1.49 +        # (like Linux).
    1.50 +        status = open('/proc/self/status', 'r')
    1.51 +        for line in status:
    1.52 +            if line.startswith('VmRSS'):
    1.53 +                parts = line.split()
    1.54 +                return parts[1]
    1.55 +        return 'unknown'
    1.56 +    finally:
    1.57 +        if status is not None:
    1.58 +            status.close()
    1.59 +
    1.60 +class Protocol:
    1.61 +
    1.62 +    def __init__(self, runtime):
    1.63 +        self.Zp = GF(find_prime(2**64))
    1.64 +        self.runtime = runtime
    1.65 +        self.last_time = time()
    1.66 +        self.share_next(0)
    1.67 +
    1.68 +    def share_next(self, n):
    1.69 +        if isinstance(n, self.Zp):
    1.70 +            n = n.value
    1.71 +        
    1.72 +        if n % 100 == 0:
    1.73 +            now = time()
    1.74 +            memory = memory_usage()
    1.75 +            print "Iteration %d: %.1f ms/iteration, allocated %s KiB" \
    1.76 +                  % (n, 10*(now - self.last_time), memory)
    1.77 +            self.last_time = now
    1.78 +
    1.79 +        x, y, z = self.runtime.shamir_share([1, 2, 3], self.Zp, n + 1)
    1.80 +        n = self.runtime.open(x + y - z)
    1.81 +        n.addCallback(self.share_next)
    1.82 +
    1.83 +pre_runtime = create_runtime(id, players, 1)
    1.84 +pre_runtime.addCallback(Protocol)
    1.85 +reactor.run()
     2.1 --- a/viff/runtime.py	Thu May 22 21:45:57 2008 +0200
     2.2 +++ b/viff/runtime.py	Thu May 22 21:49:53 2008 +0200
     2.3 @@ -288,6 +288,8 @@
     2.4              deq = self.incoming_data.setdefault(key, deque())
     2.5              if deq and isinstance(deq[0], Deferred):
     2.6                  deferred = deq.popleft()
     2.7 +                if not deq:
     2.8 +                    del self.incoming_data[key]
     2.9                  deferred.callback(data)
    2.10              else:
    2.11                  deq.append(data)
    2.12 @@ -556,6 +558,8 @@
    2.13          if deq and not isinstance(deq[0], Deferred):
    2.14              # We have already received some data from the other side.
    2.15              data = deq.popleft()
    2.16 +            if not deq:
    2.17 +                del self.protocols[peer_id].incoming_data[key]
    2.18              deferred.callback(data)
    2.19          else:
    2.20              # We have not yet received anything from the other side.
    2.21 @@ -915,7 +919,31 @@
    2.22  
    2.23          # Use r_lsb to flip b as needed.
    2.24          return (b_p, b ^ r_lsb)
    2.25 -        
    2.26 +
    2.27 +    @increment_pc
    2.28 +    def prss_shamir_share_bit_double(self, field):
    2.29 +        """Shamir share a random bit over *field* and GF256."""
    2.30 +        n = self.num_players
    2.31 +        k = self.options.security_parameter
    2.32 +        prfs = self.players[self.id].prfs(2**k)
    2.33 +        prss_key = tuple(self.program_counter)
    2.34 +        inputters = range(1, self.num_players + 1)
    2.35 +
    2.36 +        ri = rand.randint(0, 2**k - 1)
    2.37 +        ri_p = self.shamir_share(inputters, field, ri)
    2.38 +        ri_lsb = self.shamir_share(inputters, GF256, ri & 1)
    2.39 +
    2.40 +        r_p = reduce(self.add, ri_p)
    2.41 +        r_lsb = reduce(self.add, ri_lsb)
    2.42 +
    2.43 +        b_p = self.prss_share_random(field, binary=True)
    2.44 +        b = self.open(b_p + r_p)
    2.45 +        # Extract least significant bit and change field to GF256.
    2.46 +        b.addCallback(lambda i: GF256(i.value & 1))
    2.47 +        b.field = GF256
    2.48 +
    2.49 +        # Use r_lsb to flip b as needed.
    2.50 +        return (b_p, b ^ r_lsb)
    2.51  
    2.52      @increment_pc
    2.53      def _shamir_share(self, number):
     3.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     3.2 +++ b/viff/test/test_memory.py	Thu May 22 21:49:53 2008 +0200
     3.3 @@ -0,0 +1,52 @@
     3.4 +# Copyright 2008 VIFF Development Team.
     3.5 +#
     3.6 +# This file is part of VIFF, the Virtual Ideal Functionality Framework.
     3.7 +#
     3.8 +# VIFF is free software: you can redistribute it and/or modify it
     3.9 +# under the terms of the GNU Lesser General Public License (LGPL) as
    3.10 +# published by the Free Software Foundation, either version 3 of the
    3.11 +# License, or (at your option) any later version.
    3.12 +#
    3.13 +# VIFF is distributed in the hope that it will be useful, but WITHOUT
    3.14 +# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
    3.15 +# or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
    3.16 +# Public License for more details.
    3.17 +#
    3.18 +# You should have received a copy of the GNU Lesser General Public
    3.19 +# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
    3.20 +
    3.21 +from viff.field import GF256
    3.22 +from viff.runtime import Share
    3.23 +from viff.test.util import RuntimeTestCase, protocol
    3.24 +
    3.25 +class MemoryTest(RuntimeTestCase):
    3.26 +    """Tests that memory is freed when the expected data has
    3.27 +    arrived."""
    3.28 +
    3.29 +    def check_empty(self, _, runtime):
    3.30 +        """Check that all protocols are empty."""
    3.31 +        for p in runtime.protocols.itervalues():
    3.32 +            self.assertEquals(p.incoming_data, {})
    3.33 +
    3.34 +    @protocol
    3.35 +    def test_empty_incoming_data(self, runtime):
    3.36 +        """Check that a single sharing does not leak memory."""
    3.37 +        if runtime.id == 1:
    3.38 +            x = runtime.shamir_share([1], self.Zp, 10)
    3.39 +        else:
    3.40 +            x = runtime.shamir_share([1], self.Zp)
    3.41 +
    3.42 +        def check(_):
    3.43 +            for p in runtime.protocols.itervalues():
    3.44 +                self.assertEquals(p.incoming_data, {})
    3.45 +
    3.46 +        x.addCallback(self.check_empty, runtime)
    3.47 +        return x
    3.48 +
    3.49 +    @protocol
    3.50 +    def test_intermediate_released(self, runtime):
    3.51 +        """Check that a complex calculation does not leak memory."""
    3.52 +        x, y, z = runtime.shamir_share([1, 2, 3], self.Zp, runtime.id)
    3.53 +        w = x * y + z
    3.54 +        w.addCallback(self.check_empty, runtime)
    3.55 +        return w
     4.1 --- a/viff/test/test_runtime_prss.py	Thu May 22 21:45:57 2008 +0200
     4.2 +++ b/viff/test/test_runtime_prss.py	Thu May 22 21:49:53 2008 +0200
     4.3 @@ -128,3 +128,17 @@
     4.4          result = gather_shares([runtime.open(bit_p), runtime.open(bit_b)])
     4.5          result.addCallback(lambda (a, b): self.assertEquals(a.value, b.value))
     4.6          return result
     4.7 +
     4.8 +    @protocol
     4.9 +    def test_prss_shamir_share_bit_double(self, runtime):
    4.10 +        """Tests Shamir sharing a bit over Zp and GF256."""
    4.11 +        bit_p, bit_b = runtime.prss_shamir_share_bit_double(self.Zp)
    4.12 +
    4.13 +        self.assert_type(bit_p, Share)
    4.14 +        self.assertEquals(bit_p.field, self.Zp)
    4.15 +        self.assert_type(bit_b, Share)
    4.16 +        self.assertEquals(bit_b.field, GF256)
    4.17 +
    4.18 +        result = gather_shares([runtime.open(bit_p), runtime.open(bit_b)])
    4.19 +        result.addCallback(lambda (a, b): self.assertEquals(a.value, b.value))
    4.20 +        return result