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 wrap: on
line diff
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/apps/gc-test.py	Thu May 22 21:49:53 2008 +0200
@@ -0,0 +1,82 @@
+#!/usr/bin/python
+
+# Copyright 2008 VIFF Development Team.
+#
+# This file is part of VIFF, the Virtual Ideal Functionality Framework.
+#
+# VIFF is free software: you can redistribute it and/or modify it
+# under the terms of the GNU Lesser General Public License (LGPL) as
+# published by the Free Software Foundation, either version 3 of the
+# License, or (at your option) any later version.
+#
+# VIFF is distributed in the hope that it will be useful, but WITHOUT
+# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+# or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
+# Public License for more details.
+#
+# You should have received a copy of the GNU Lesser General Public
+# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
+
+# This application will is meant for 3 players. They will run forever,
+# sharing and summing integers. After 100 iterations the time per
+# iteration and the current memory allocation is printed. The
+# allocation should stay *constant* since shares are released at the
+# same speed as they are allocated.
+
+import sys
+import gc
+from time import time
+from pprint import pprint
+
+from twisted.internet import reactor
+
+from viff.field import GF
+from viff.runtime import create_runtime
+from viff.config import load_config
+from viff.util import find_prime
+
+id, players = load_config(sys.argv[1])
+
+
+def memory_usage():
+    """Read memory usage of the current process."""
+    status = None
+    try:
+        # This will only work on systems with a /proc file system
+        # (like Linux).
+        status = open('/proc/self/status', 'r')
+        for line in status:
+            if line.startswith('VmRSS'):
+                parts = line.split()
+                return parts[1]
+        return 'unknown'
+    finally:
+        if status is not None:
+            status.close()
+
+class Protocol:
+
+    def __init__(self, runtime):
+        self.Zp = GF(find_prime(2**64))
+        self.runtime = runtime
+        self.last_time = time()
+        self.share_next(0)
+
+    def share_next(self, n):
+        if isinstance(n, self.Zp):
+            n = n.value
+        
+        if n % 100 == 0:
+            now = time()
+            memory = memory_usage()
+            print "Iteration %d: %.1f ms/iteration, allocated %s KiB" \
+                  % (n, 10*(now - self.last_time), memory)
+            self.last_time = now
+
+        x, y, z = self.runtime.shamir_share([1, 2, 3], self.Zp, n + 1)
+        n = self.runtime.open(x + y - z)
+        n.addCallback(self.share_next)
+
+pre_runtime = create_runtime(id, players, 1)
+pre_runtime.addCallback(Protocol)
+reactor.run()
--- a/viff/runtime.py	Thu May 22 21:45:57 2008 +0200
+++ b/viff/runtime.py	Thu May 22 21:49:53 2008 +0200
@@ -288,6 +288,8 @@
             deq = self.incoming_data.setdefault(key, deque())
             if deq and isinstance(deq[0], Deferred):
                 deferred = deq.popleft()
+                if not deq:
+                    del self.incoming_data[key]
                 deferred.callback(data)
             else:
                 deq.append(data)
@@ -556,6 +558,8 @@
         if deq and not isinstance(deq[0], Deferred):
             # We have already received some data from the other side.
             data = deq.popleft()
+            if not deq:
+                del self.protocols[peer_id].incoming_data[key]
             deferred.callback(data)
         else:
             # We have not yet received anything from the other side.
@@ -915,7 +919,31 @@
 
         # Use r_lsb to flip b as needed.
         return (b_p, b ^ r_lsb)
-        
+
+    @increment_pc
+    def prss_shamir_share_bit_double(self, field):
+        """Shamir share a random bit over *field* and GF256."""
+        n = self.num_players
+        k = self.options.security_parameter
+        prfs = self.players[self.id].prfs(2**k)
+        prss_key = tuple(self.program_counter)
+        inputters = range(1, self.num_players + 1)
+
+        ri = rand.randint(0, 2**k - 1)
+        ri_p = self.shamir_share(inputters, field, ri)
+        ri_lsb = self.shamir_share(inputters, GF256, ri & 1)
+
+        r_p = reduce(self.add, ri_p)
+        r_lsb = reduce(self.add, ri_lsb)
+
+        b_p = self.prss_share_random(field, binary=True)
+        b = self.open(b_p + r_p)
+        # Extract least significant bit and change field to GF256.
+        b.addCallback(lambda i: GF256(i.value & 1))
+        b.field = GF256
+
+        # Use r_lsb to flip b as needed.
+        return (b_p, b ^ r_lsb)
 
     @increment_pc
     def _shamir_share(self, number):
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/viff/test/test_memory.py	Thu May 22 21:49:53 2008 +0200
@@ -0,0 +1,52 @@
+# Copyright 2008 VIFF Development Team.
+#
+# This file is part of VIFF, the Virtual Ideal Functionality Framework.
+#
+# VIFF is free software: you can redistribute it and/or modify it
+# under the terms of the GNU Lesser General Public License (LGPL) as
+# published by the Free Software Foundation, either version 3 of the
+# License, or (at your option) any later version.
+#
+# VIFF is distributed in the hope that it will be useful, but WITHOUT
+# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+# or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
+# Public License for more details.
+#
+# You should have received a copy of the GNU Lesser General Public
+# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
+
+from viff.field import GF256
+from viff.runtime import Share
+from viff.test.util import RuntimeTestCase, protocol
+
+class MemoryTest(RuntimeTestCase):
+    """Tests that memory is freed when the expected data has
+    arrived."""
+
+    def check_empty(self, _, runtime):
+        """Check that all protocols are empty."""
+        for p in runtime.protocols.itervalues():
+            self.assertEquals(p.incoming_data, {})
+
+    @protocol
+    def test_empty_incoming_data(self, runtime):
+        """Check that a single sharing does not leak memory."""
+        if runtime.id == 1:
+            x = runtime.shamir_share([1], self.Zp, 10)
+        else:
+            x = runtime.shamir_share([1], self.Zp)
+
+        def check(_):
+            for p in runtime.protocols.itervalues():
+                self.assertEquals(p.incoming_data, {})
+
+        x.addCallback(self.check_empty, runtime)
+        return x
+
+    @protocol
+    def test_intermediate_released(self, runtime):
+        """Check that a complex calculation does not leak memory."""
+        x, y, z = runtime.shamir_share([1, 2, 3], self.Zp, runtime.id)
+        w = x * y + z
+        w.addCallback(self.check_empty, runtime)
+        return w
--- a/viff/test/test_runtime_prss.py	Thu May 22 21:45:57 2008 +0200
+++ b/viff/test/test_runtime_prss.py	Thu May 22 21:49:53 2008 +0200
@@ -128,3 +128,17 @@
         result = gather_shares([runtime.open(bit_p), runtime.open(bit_b)])
         result.addCallback(lambda (a, b): self.assertEquals(a.value, b.value))
         return result
+
+    @protocol
+    def test_prss_shamir_share_bit_double(self, runtime):
+        """Tests Shamir sharing a bit over Zp and GF256."""
+        bit_p, bit_b = runtime.prss_shamir_share_bit_double(self.Zp)
+
+        self.assert_type(bit_p, Share)
+        self.assertEquals(bit_p.field, self.Zp)
+        self.assert_type(bit_b, Share)
+        self.assertEquals(bit_b.field, GF256)
+
+        result = gather_shares([runtime.open(bit_p), runtime.open(bit_b)])
+        result.addCallback(lambda (a, b): self.assertEquals(a.value, b.value))
+        return result