You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@systemds.apache.org by ba...@apache.org on 2020/09/29 12:29:39 UTC
[systemds] branch master updated: [SYSTEMDS-2668] Fine-Grained Priv
Constraint Prop
This is an automated email from the ASF dual-hosted git repository.
baunsgaard pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/systemds.git
The following commit(s) were added to refs/heads/master by this push:
new 7c9694a [SYSTEMDS-2668] Fine-Grained Priv Constraint Prop
7c9694a is described below
commit 7c9694a15dd174342a3ef6528cf0f9bda4455e60
Author: sebwrede <sw...@know-center.at>
AuthorDate: Wed Sep 16 17:36:00 2020 +0200
[SYSTEMDS-2668] Fine-Grained Priv Constraint Prop
This PR improves propagation of fine-grained privacy constraints for
matrix multiplications. The PR also provides a new structure for
fine-grained privacy propagations by introducing a "Propagator"
interface which are implemented by different propagator classes. This
interface will be used in the following implementations of privacy
propagation for other operators.
The new matrix multiplication propagation is more efficient than the
previous implementation since it makes an array with the summarized
privacy level of the rows of the first matrix and the columns of the
second matrix.
Furthermore, it takes the operator type into account. This means that
if a row or column contains only a single non-zero value, it cannot be
considered an aggregation, hence the output in case of the
PrivateAggregation privacy level in the input should still be
PrivateAggregation. The rules of propagation is implemented in the
method "PrivacyPropagator.corePropagation", where the comment also
details the privacy "truth table".
- Edit Fine-Grained Constraint Propagation in Matrix Multiplications
- The new version will take operator type into account when propagating
and will summarize the privacy level of rows and columns of the input
matrices to make a faster propagation. The new implementation needs
further test cases, which will be added in future commits.
- Add Tests of Matrix Multiplication Privacy Propagation
- Refactor Matrix Multiplication Propagation By Introducing
the Propagator Interface
- Add Optimized PrivateFirst Propagator
Closes #1060
---
.../sysds/runtime/privacy/PrivacyPropagator.html | 2 +-
.../privacy/class-use/PrivacyPropagator.html | 8 +-
.../org/apache/sysds/parser/BinaryExpression.java | 2 +-
.../federated/FederatedWorkerHandler.java | 2 +-
.../sysds/runtime/instructions/Instruction.java | 2 +-
.../runtime/instructions/cp/CPInstruction.java | 2 +-
.../runtime/instructions/fed/FEDInstruction.java | 2 +-
.../privacy/finegrained/FineGrainedPrivacy.java | 10 +
.../finegrained/FineGrainedPrivacyList.java | 50 ++
.../privacy/finegrained/FineGrainedPrivacyMap.java | 21 +
.../MatrixMultiplicationPropagator.java | 155 ++++++
.../MatrixMultiplicationPropagatorNaive.java | 60 +++
...MatrixMultiplicationPropagatorPrivateFirst.java | 103 ++++
...tiplicationPropagatorPrivateFirstOptimized.java | 85 ++++
.../runtime/privacy/propagation/OperatorType.java | 25 +
.../{ => propagation}/PrivacyPropagator.java | 124 ++---
.../runtime/privacy/propagation/Propagator.java | 33 ++
.../test/functions/privacy/CorePropagatorTest.java | 80 ++++
.../functions/privacy/PrivacyPropagatorTest.java | 533 ++++++++++++++++++++-
19 files changed, 1208 insertions(+), 91 deletions(-)
diff --git a/docs/api/java/org/apache/sysds/runtime/privacy/PrivacyPropagator.html b/docs/api/java/org/apache/sysds/runtime/privacy/PrivacyPropagator.html
index cb20d47..bd03008 100644
--- a/docs/api/java/org/apache/sysds/runtime/privacy/PrivacyPropagator.html
+++ b/docs/api/java/org/apache/sysds/runtime/privacy/PrivacyPropagator.html
@@ -100,7 +100,7 @@ var activeTableTab = "activeTableTab";
<li><a href="https://docs.oracle.com/javase/8/docs/api/java/lang/Object.html?is-external=true" title="class or interface in java.lang">java.lang.Object</a></li>
<li>
<ul class="inheritance">
-<li>org.apache.sysds.runtime.privacy.PrivacyPropagator</li>
+<li>org.apache.sysds.runtime.privacy.propagation.PrivacyPropagator</li>
</ul>
</li>
</ul>
diff --git a/docs/api/java/org/apache/sysds/runtime/privacy/class-use/PrivacyPropagator.html b/docs/api/java/org/apache/sysds/runtime/privacy/class-use/PrivacyPropagator.html
index ecbaee4..9e7a6d5 100644
--- a/docs/api/java/org/apache/sysds/runtime/privacy/class-use/PrivacyPropagator.html
+++ b/docs/api/java/org/apache/sysds/runtime/privacy/class-use/PrivacyPropagator.html
@@ -4,7 +4,7 @@
<head>
<!-- Generated by javadoc -->
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
-<title>Uses of Class org.apache.sysds.runtime.privacy.PrivacyPropagator (SystemDS 2.0.0-SNAPSHOT API)</title>
+<title>Uses of Class org.apache.sysds.runtime.privacy.propagation.PrivacyPropagator (SystemDS 2.0.0-SNAPSHOT API)</title>
<link rel="stylesheet" type="text/css" href="../../../../../../stylesheet.css" title="Style">
<script type="text/javascript" src="../../../../../../script.js"></script>
</head>
@@ -12,7 +12,7 @@
<script type="text/javascript"><!--
try {
if (location.href.indexOf('is-external=true') == -1) {
- parent.document.title="Uses of Class org.apache.sysds.runtime.privacy.PrivacyPropagator (SystemDS 2.0.0-SNAPSHOT API)";
+ parent.document.title="Uses of Class org.apache.sysds.runtime.privacy.propagation.PrivacyPropagator (SystemDS 2.0.0-SNAPSHOT API)";
}
}
catch(err) {
@@ -70,9 +70,9 @@
</a></div>
<!-- ========= END OF TOP NAVBAR ========= -->
<div class="header">
-<h2 title="Uses of Class org.apache.sysds.runtime.privacy.PrivacyPropagator" class="title">Uses of Class<br>org.apache.sysds.runtime.privacy.PrivacyPropagator</h2>
+<h2 title="Uses of Class org.apache.sysds.runtime.privacy.propagation.PrivacyPropagator" class="title">Uses of Class<br>org.apache.sysds.runtime.privacy.propagation.PrivacyPropagator</h2>
</div>
-<div class="classUseContainer">No usage of org.apache.sysds.runtime.privacy.PrivacyPropagator</div>
+<div class="classUseContainer">No usage of org.apache.sysds.runtime.privacy.propagation.PrivacyPropagator</div>
<!-- ======= START OF BOTTOM NAVBAR ====== -->
<div class="bottomNav"><a name="navbar.bottom">
<!-- -->
diff --git a/src/main/java/org/apache/sysds/parser/BinaryExpression.java b/src/main/java/org/apache/sysds/parser/BinaryExpression.java
index acccb66..42dde75 100644
--- a/src/main/java/org/apache/sysds/parser/BinaryExpression.java
+++ b/src/main/java/org/apache/sysds/parser/BinaryExpression.java
@@ -23,7 +23,7 @@ import java.util.HashMap;
import org.apache.sysds.common.Types.DataType;
import org.apache.sysds.common.Types.ValueType;
-import org.apache.sysds.runtime.privacy.PrivacyPropagator;
+import org.apache.sysds.runtime.privacy.propagation.PrivacyPropagator;
public class BinaryExpression extends Expression
diff --git a/src/main/java/org/apache/sysds/runtime/controlprogram/federated/FederatedWorkerHandler.java b/src/main/java/org/apache/sysds/runtime/controlprogram/federated/FederatedWorkerHandler.java
index 76166f2..323248e 100644
--- a/src/main/java/org/apache/sysds/runtime/controlprogram/federated/FederatedWorkerHandler.java
+++ b/src/main/java/org/apache/sysds/runtime/controlprogram/federated/FederatedWorkerHandler.java
@@ -52,7 +52,7 @@ import org.apache.sysds.runtime.meta.MatrixCharacteristics;
import org.apache.sysds.runtime.meta.MetaDataFormat;
import org.apache.sysds.runtime.privacy.DMLPrivacyException;
import org.apache.sysds.runtime.privacy.PrivacyMonitor;
-import org.apache.sysds.runtime.privacy.PrivacyPropagator;
+import org.apache.sysds.runtime.privacy.propagation.PrivacyPropagator;
import org.apache.sysds.utils.JSONHelper;
import org.apache.sysds.utils.Statistics;
import org.apache.wink.json4j.JSONObject;
diff --git a/src/main/java/org/apache/sysds/runtime/instructions/Instruction.java b/src/main/java/org/apache/sysds/runtime/instructions/Instruction.java
index 7a2e410..10645ab 100644
--- a/src/main/java/org/apache/sysds/runtime/instructions/Instruction.java
+++ b/src/main/java/org/apache/sysds/runtime/instructions/Instruction.java
@@ -27,7 +27,7 @@ import org.apache.sysds.parser.DataIdentifier;
import org.apache.sysds.runtime.controlprogram.context.ExecutionContext;
import org.apache.sysds.runtime.matrix.operators.Operator;
import org.apache.sysds.runtime.privacy.PrivacyConstraint;
-import org.apache.sysds.runtime.privacy.PrivacyPropagator;
+import org.apache.sysds.runtime.privacy.propagation.PrivacyPropagator;
public abstract class Instruction
{
diff --git a/src/main/java/org/apache/sysds/runtime/instructions/cp/CPInstruction.java b/src/main/java/org/apache/sysds/runtime/instructions/cp/CPInstruction.java
index 8ce3dec..53dd274 100644
--- a/src/main/java/org/apache/sysds/runtime/instructions/cp/CPInstruction.java
+++ b/src/main/java/org/apache/sysds/runtime/instructions/cp/CPInstruction.java
@@ -30,7 +30,7 @@ import org.apache.sysds.runtime.instructions.CPInstructionParser;
import org.apache.sysds.runtime.instructions.Instruction;
import org.apache.sysds.runtime.instructions.fed.FEDInstructionUtils;
import org.apache.sysds.runtime.matrix.operators.Operator;
-import org.apache.sysds.runtime.privacy.PrivacyPropagator;
+import org.apache.sysds.runtime.privacy.propagation.PrivacyPropagator;
public abstract class CPInstruction extends Instruction
{
diff --git a/src/main/java/org/apache/sysds/runtime/instructions/fed/FEDInstruction.java b/src/main/java/org/apache/sysds/runtime/instructions/fed/FEDInstruction.java
index 1550bc6..9301765 100644
--- a/src/main/java/org/apache/sysds/runtime/instructions/fed/FEDInstruction.java
+++ b/src/main/java/org/apache/sysds/runtime/instructions/fed/FEDInstruction.java
@@ -22,7 +22,7 @@ package org.apache.sysds.runtime.instructions.fed;
import org.apache.sysds.runtime.controlprogram.context.ExecutionContext;
import org.apache.sysds.runtime.instructions.Instruction;
import org.apache.sysds.runtime.matrix.operators.Operator;
-import org.apache.sysds.runtime.privacy.PrivacyPropagator;
+import org.apache.sysds.runtime.privacy.propagation.PrivacyPropagator;
public abstract class FEDInstruction extends Instruction {
diff --git a/src/main/java/org/apache/sysds/runtime/privacy/finegrained/FineGrainedPrivacy.java b/src/main/java/org/apache/sysds/runtime/privacy/finegrained/FineGrainedPrivacy.java
index 725b17c..2aa2f1d 100644
--- a/src/main/java/org/apache/sysds/runtime/privacy/finegrained/FineGrainedPrivacy.java
+++ b/src/main/java/org/apache/sysds/runtime/privacy/finegrained/FineGrainedPrivacy.java
@@ -33,6 +33,12 @@ public interface FineGrainedPrivacy {
*/
public void put(DataRange dataRange, PrivacyLevel privacyLevel);
+ public void putRow(int rowIndex, int rowLength, PrivacyLevel privacyLevel);
+
+ public void putCol(int colIndex, int colLength, PrivacyLevel privacyLevel);
+
+ public void putElement(int rowIndex, int colIndex, PrivacyLevel privacyLevel);
+
/**
* Get the data ranges and related privacy levels within given data search range.
* @param searchRange the range from which all privacy levels are retrieved
@@ -77,4 +83,8 @@ public interface FineGrainedPrivacy {
* @return all constraints
*/
public ArrayList<Map.Entry<DataRange, PrivacyLevel>> getAllConstraintsList();
+
+ public PrivacyLevel[] getRowPrivacy(int numRows, int numCols);
+
+ public PrivacyLevel[] getColPrivacy(int numRows, int numCols);
}
diff --git a/src/main/java/org/apache/sysds/runtime/privacy/finegrained/FineGrainedPrivacyList.java b/src/main/java/org/apache/sysds/runtime/privacy/finegrained/FineGrainedPrivacyList.java
index 1f266af..2992606 100644
--- a/src/main/java/org/apache/sysds/runtime/privacy/finegrained/FineGrainedPrivacyList.java
+++ b/src/main/java/org/apache/sysds/runtime/privacy/finegrained/FineGrainedPrivacyList.java
@@ -36,11 +36,61 @@ public class FineGrainedPrivacyList implements FineGrainedPrivacy {
private ArrayList<Map.Entry<DataRange, PrivacyLevel>> constraintCollection = new ArrayList<>();
@Override
+ public PrivacyLevel[] getRowPrivacy(int numRows, int numCols) {
+ PrivacyLevel[] privacyLevels = new PrivacyLevel[numRows];
+ for (int i = 0; i < numRows; i++) {
+ long[] beginRange1 = new long[] {i, 0};
+ long[] endRange1 = new long[] {i, numCols};
+ privacyLevels[i] = getStrictestPrivacyLevel(new DataRange(beginRange1, endRange1));
+ }
+ return privacyLevels;
+ }
+
+ @Override
+ public PrivacyLevel[] getColPrivacy(int numRows, int numCols) {
+ PrivacyLevel[] privacyLevels = new PrivacyLevel[numCols];
+ for (int i = 0; i < numCols; i++) {
+ long[] beginRange = new long[] {0, i};
+ long[] endRange = new long[] {numRows, i};
+ privacyLevels[i] = getStrictestPrivacyLevel(new DataRange(beginRange, endRange));
+ }
+ return privacyLevels;
+ }
+
+ private PrivacyLevel getStrictestPrivacyLevel(DataRange searchRange){
+ PrivacyLevel strictestLevel = PrivacyLevel.None;
+ for ( Map.Entry<DataRange, PrivacyLevel> constraint : constraintCollection ) {
+ if(constraint.getKey().overlaps(searchRange)) {
+ if(constraint.getValue() == PrivacyLevel.Private)
+ return PrivacyLevel.Private;
+ if(constraint.getValue() == PrivacyLevel.PrivateAggregation)
+ strictestLevel = PrivacyLevel.PrivateAggregation;
+ }
+ }
+ return strictestLevel;
+ }
+
+ @Override
public void put(DataRange dataRange, PrivacyLevel privacyLevel) {
constraintCollection.add(new AbstractMap.SimpleEntry<>(dataRange, privacyLevel));
}
@Override
+ public void putRow(int rowIndex, int rowLength, PrivacyLevel privacyLevel){
+ put(new DataRange(new long[] {rowIndex, 0}, new long[] {rowIndex, rowLength-1}), privacyLevel);
+ }
+
+ @Override
+ public void putCol(int colIndex, int colLength, PrivacyLevel privacyLevel){
+ put(new DataRange(new long[] {0, colIndex}, new long[] {colLength-1, colIndex}), privacyLevel);
+ }
+
+ @Override
+ public void putElement(int rowIndex, int colIndex, PrivacyLevel privacyLevel){
+ put(new DataRange(new long[]{rowIndex,colIndex},new long[]{rowIndex,colIndex}), privacyLevel);
+ }
+
+ @Override
public Map<DataRange,PrivacyLevel> getPrivacyLevel(DataRange searchRange) {
Map<DataRange, PrivacyLevel> matches = new LinkedHashMap<>();
for ( Map.Entry<DataRange, PrivacyLevel> constraint : constraintCollection ){
diff --git a/src/main/java/org/apache/sysds/runtime/privacy/finegrained/FineGrainedPrivacyMap.java b/src/main/java/org/apache/sysds/runtime/privacy/finegrained/FineGrainedPrivacyMap.java
index c6bd848..ffd6048 100644
--- a/src/main/java/org/apache/sysds/runtime/privacy/finegrained/FineGrainedPrivacyMap.java
+++ b/src/main/java/org/apache/sysds/runtime/privacy/finegrained/FineGrainedPrivacyMap.java
@@ -40,6 +40,18 @@ public class FineGrainedPrivacyMap implements FineGrainedPrivacy {
constraintCollection.put(dataRange, privacyLevel);
}
+ @Override public void putRow(int rowIndex, int rowLength, PrivacyLevel privacyLevel) {
+
+ }
+
+ @Override public void putCol(int colIndex, int colLength, PrivacyLevel privacyLevel) {
+
+ }
+
+ @Override public void putElement(int rowIndex, int colIndex, PrivacyLevel privacyLevel) {
+
+ }
+
@Override
public Map<DataRange, PrivacyLevel> getPrivacyLevel(DataRange searchRange) {
Map<DataRange, PrivacyLevel> matches = new LinkedHashMap<>();
@@ -102,4 +114,13 @@ public class FineGrainedPrivacyMap implements FineGrainedPrivacy {
constraintCollection.forEach((k,v)->outputList.add(new AbstractMap.SimpleEntry<>(k,v)));
return outputList;
}
+
+ @Override
+ public PrivacyLevel[] getRowPrivacy(int numRows, int numCols){
+ return new PrivacyLevel[0];
+ }
+
+ public PrivacyLevel[] getColPrivacy(int numRows, int numCols){
+ return new PrivacyLevel[0];
+ }
}
diff --git a/src/main/java/org/apache/sysds/runtime/privacy/propagation/MatrixMultiplicationPropagator.java b/src/main/java/org/apache/sysds/runtime/privacy/propagation/MatrixMultiplicationPropagator.java
new file mode 100644
index 0000000..b818928
--- /dev/null
+++ b/src/main/java/org/apache/sysds/runtime/privacy/propagation/MatrixMultiplicationPropagator.java
@@ -0,0 +1,155 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.sysds.runtime.privacy.propagation;
+
+import org.apache.sysds.runtime.matrix.data.MatrixBlock;
+import org.apache.sysds.runtime.privacy.PrivacyConstraint;
+import org.apache.sysds.runtime.privacy.finegrained.FineGrainedPrivacy;
+
+import java.util.stream.Stream;
+
+/**
+ * Used for propagating constraints in a matrix multiplication.
+ */
+public abstract class MatrixMultiplicationPropagator implements Propagator {
+
+ MatrixBlock input1, input2;
+ PrivacyConstraint privacyConstraint1, privacyConstraint2;
+
+ /**
+ * Constructor for empty instance.
+ * The fields can later be set with the setFields method.
+ */
+ public MatrixMultiplicationPropagator(){}
+
+ /**
+ * Constructs the propagator and initializes the fields used for propagation.
+ * @param input1 left-hand input in matrix multiplication.
+ * @param privacyConstraint1 privacy constraint of left-hand input in matrix multiplication
+ * @param input2 right-hand input in matrix multiplication
+ * @param privacyConstraint2 privacy constraint of right-hand input in matrix multiplication
+ */
+ public MatrixMultiplicationPropagator(
+ MatrixBlock input1, PrivacyConstraint privacyConstraint1,
+ MatrixBlock input2, PrivacyConstraint privacyConstraint2){
+ setFields(input1, privacyConstraint1, input2, privacyConstraint2);
+ }
+
+ /**
+ * Sets all fields of propagator.
+ * @param input1 left-hand input in matrix multiplication.
+ * @param privacyConstraint1 privacy constraint of left-hand input in matrix multiplication
+ * @param input2 right-hand input in matrix multiplication
+ * @param privacyConstraint2 privacy constraint of right-hand input in matrix multiplication
+ */
+ public void setFields(
+ MatrixBlock input1, PrivacyConstraint privacyConstraint1,
+ MatrixBlock input2, PrivacyConstraint privacyConstraint2){
+ this.input1 = input1;
+ this.privacyConstraint1 = privacyConstraint1;
+ this.input2 = input2;
+ this.privacyConstraint2 = privacyConstraint2;
+ }
+
+ @Override
+ public PrivacyConstraint propagate() {
+ // If the overall privacy level is private, then the fine-grained constraints do not have to be checked.
+ if ( (privacyConstraint1 != null && privacyConstraint1.getPrivacyLevel() == PrivacyConstraint.PrivacyLevel.Private)
+ || (privacyConstraint2 != null && privacyConstraint2.getPrivacyLevel() == PrivacyConstraint.PrivacyLevel.Private) )
+ return new PrivacyConstraint(PrivacyConstraint.PrivacyLevel.Private);
+
+ int r1 = input1.getNumRows();
+ int c1 = input1.getNumColumns();
+ int r2 = input2.getNumRows();
+ int c2 = input2.getNumColumns();
+ PrivacyConstraint mergedConstraint = new PrivacyConstraint();
+ FineGrainedPrivacy mergedFineGrainedConstraints = mergedConstraint.getFineGrainedPrivacy();
+
+ // Get row privacy levels for input1
+ PrivacyConstraint.PrivacyLevel[] rowPrivacy = (privacyConstraint1 != null && privacyConstraint1.getFineGrainedPrivacy() != null) ?
+ privacyConstraint1.getFineGrainedPrivacy().getRowPrivacy(r1,c1) :
+ Stream.generate(() -> PrivacyConstraint.PrivacyLevel.None).limit(r1).toArray(PrivacyConstraint.PrivacyLevel[]::new);
+ // Get col privacy levels for input2
+ PrivacyConstraint.PrivacyLevel[] colPrivacy = (privacyConstraint2 != null && privacyConstraint2.getFineGrainedPrivacy() != null) ?
+ privacyConstraint2.getFineGrainedPrivacy().getColPrivacy(r2,c2) :
+ Stream.generate(() -> PrivacyConstraint.PrivacyLevel.None).limit(c2).toArray(PrivacyConstraint.PrivacyLevel[]::new);
+ // Get operator type array based on values in rows of input1 and cols of input2
+ OperatorType[] operatorTypes1 = getOperatorTypesRow();
+ OperatorType[] operatorTypes2 = getOperatorTypesCol();
+ // Propagate privacy levels based on above arrays
+ generateFineGrainedConstraints(mergedFineGrainedConstraints, rowPrivacy, colPrivacy, operatorTypes1, operatorTypes2);
+ return mergedConstraint;
+ }
+
+ /**
+ * Gets the operator types of all rows of the left-hand input in the matrix multiplication.
+ * An operator type defines if the row will result in an aggregation or not.
+ * @return array of operator types representing the rows of the left-hand input in the matrix multiplication
+ */
+ public OperatorType[] getOperatorTypesRow(){
+ OperatorType[] operatorTypes = new OperatorType[input1.getNumRows()];
+ for (int i = 0; i < input1.getNumRows(); i++) {
+ MatrixBlock rowSlice = input1.slice(i,i);
+ operatorTypes[i] = getOperatorType(rowSlice);
+ }
+ return operatorTypes;
+ }
+
+ /**
+ * Gets the operator types of all columns of the right-hand input in the matrix multiplication.
+ * An operator type defines if the column will result in an aggregation or not.
+ * @return array of operator types representing the columns of the right-hand input in the matrix multiplication.
+ */
+ public OperatorType[] getOperatorTypesCol(){
+ OperatorType[] operatorTypes = new OperatorType[input2.getNumColumns()];
+ for (int j = 0; j < input2.getNumColumns(); j++) {
+ MatrixBlock colSlice = input2.slice(0, input2.getNumRows()-1, j, j, new MatrixBlock());
+ operatorTypes[j] = getOperatorType(colSlice);
+ }
+ return operatorTypes;
+ }
+
+ protected OperatorType mergeOperatorType(OperatorType input1, OperatorType input2){
+ if (input1 == OperatorType.NonAggregate || input2 == OperatorType.NonAggregate)
+ return OperatorType.NonAggregate;
+ else return OperatorType.Aggregate;
+ }
+
+ protected OperatorType getOperatorType(MatrixBlock inputSlice){
+ if(inputSlice.getNonZeros() == 1)
+ return OperatorType.NonAggregate;
+ else
+ return OperatorType.Aggregate;
+ }
+
+ /**
+ * An abstract method that generates the fine-grained privacy constraints based on the input
+ * and puts it in the mergedFineGrainedConstraints.
+ * @param mergedFineGrainedConstraints FineGrainedPrivacy instance in which the output privacy constraints are put
+ * @param rowPrivacy privacy constraints of the rows of the left-hand input in the matrix multiplication
+ * @param colPrivacy privacy constraints of the columns of the right-hand input in the matrix multiplication
+ * @param operatorTypes1 operator types of the left-hand input in the matrix multiplication
+ * @param operatorTypes2 operator types of the right-hand input in the matrix multiplication
+ */
+ protected abstract void generateFineGrainedConstraints(FineGrainedPrivacy mergedFineGrainedConstraints,
+ PrivacyConstraint.PrivacyLevel[] rowPrivacy, PrivacyConstraint.PrivacyLevel[] colPrivacy,
+ OperatorType[] operatorTypes1, OperatorType[] operatorTypes2);
+
+}
diff --git a/src/main/java/org/apache/sysds/runtime/privacy/propagation/MatrixMultiplicationPropagatorNaive.java b/src/main/java/org/apache/sysds/runtime/privacy/propagation/MatrixMultiplicationPropagatorNaive.java
new file mode 100644
index 0000000..1ac50e0
--- /dev/null
+++ b/src/main/java/org/apache/sysds/runtime/privacy/propagation/MatrixMultiplicationPropagatorNaive.java
@@ -0,0 +1,60 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.sysds.runtime.privacy.propagation;
+
+import org.apache.sysds.runtime.matrix.data.MatrixBlock;
+import org.apache.sysds.runtime.privacy.PrivacyConstraint;
+import org.apache.sysds.runtime.privacy.PrivacyConstraint.PrivacyLevel;
+import org.apache.sysds.runtime.privacy.finegrained.FineGrainedPrivacy;
+
+/**
+ * MatrixMultiplicationPropagator that overrides generateFineGrainedConstraints
+ * with a naive propagation of the fine-grained constraints.
+ * The output is correct, but is likely less efficient than other implementations.
+ */
+public class MatrixMultiplicationPropagatorNaive extends MatrixMultiplicationPropagator{
+
+ public MatrixMultiplicationPropagatorNaive(){
+ super();
+ }
+
+ public MatrixMultiplicationPropagatorNaive(MatrixBlock input1, PrivacyConstraint privacyConstraint1,
+ MatrixBlock input2, PrivacyConstraint privacyConstraint2) {
+ super(input1, privacyConstraint1, input2, privacyConstraint2);
+ }
+
+ /**
+ * Generates fine-grained constraints and puts them in the mergedFineGrainedConstraints instance.
+ * This implementation loops over every cell of the output matrix and sets the constraint based on the
+ * row/column privacy constraints and the row/column operator type.
+ */
+ @Override
+ protected void generateFineGrainedConstraints(FineGrainedPrivacy mergedFineGrainedConstraints,
+ PrivacyLevel[] rowPrivacy, PrivacyConstraint.PrivacyLevel[] colPrivacy,
+ OperatorType[] operatorTypes1, OperatorType[] operatorTypes2) {
+ for ( int i = 0; i < rowPrivacy.length; i++){
+ for ( int j = 0; j < colPrivacy.length; j++){
+ OperatorType operatorType = mergeOperatorType(operatorTypes1[i], operatorTypes2[j]);
+ PrivacyLevel outputLevel = PrivacyPropagator.corePropagation(new PrivacyLevel[]{rowPrivacy[i], colPrivacy[j]}, operatorType);
+ mergedFineGrainedConstraints.putElement(i,j,outputLevel);
+ }
+ }
+ }
+}
diff --git a/src/main/java/org/apache/sysds/runtime/privacy/propagation/MatrixMultiplicationPropagatorPrivateFirst.java b/src/main/java/org/apache/sysds/runtime/privacy/propagation/MatrixMultiplicationPropagatorPrivateFirst.java
new file mode 100644
index 0000000..b1e91c6
--- /dev/null
+++ b/src/main/java/org/apache/sysds/runtime/privacy/propagation/MatrixMultiplicationPropagatorPrivateFirst.java
@@ -0,0 +1,103 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.sysds.runtime.privacy.propagation;
+
+import org.apache.sysds.runtime.matrix.data.MatrixBlock;
+import org.apache.sysds.runtime.privacy.PrivacyConstraint;
+import org.apache.sysds.runtime.privacy.PrivacyConstraint.PrivacyLevel;
+import org.apache.sysds.runtime.privacy.finegrained.FineGrainedPrivacy;
+
+/**
+ * MatrixMultiplicationPropagator that overrides generateFineGrainedConstraints by finding the private elements first
+ * followed by propagating PrivateAggregation in case of non-aggregating operator types.
+ */
+public class MatrixMultiplicationPropagatorPrivateFirst extends MatrixMultiplicationPropagator {
+
+ public MatrixMultiplicationPropagatorPrivateFirst(){
+ super();
+ }
+
+ public MatrixMultiplicationPropagatorPrivateFirst(MatrixBlock input1, PrivacyConstraint privacyConstraint1,
+ MatrixBlock input2, PrivacyConstraint privacyConstraint2) {
+ super(input1, privacyConstraint1, input2, privacyConstraint2);
+ }
+
+ /**
+ * Generates fine-grained constraints and puts them in the mergedFineGrainedConstraints instance.
+ * This implementation first loops over the rowPrivacy array and sets the entire row to private if the rowPrivacy is private.
+ * Next, it loops over the colPrivacy array and sets the entire column to private if the colPrivacy is private.
+ * Then it loops over the operatorTypes for both input matrices.
+ * If the operator type is non-aggregate and the privacy level is PrivateAggregation,
+ * then it sets the entire row/column to PrivateAggregation.
+ * If the operator type is non-aggregate and the privacy level is not private, then it loops through all elements
+ * in the row/column and checks for PrivateAggregation in the privacy level array of the other input.
+ */
+ @Override
+ protected void generateFineGrainedConstraints(FineGrainedPrivacy mergedFineGrainedConstraints,
+ PrivacyLevel[] rowPrivacy, PrivacyLevel[] colPrivacy,
+ OperatorType[] operatorTypes1, OperatorType[] operatorTypes2) {
+ int r1 = rowPrivacy.length;
+ int c2 = colPrivacy.length;
+ for ( int i = 0; i < rowPrivacy.length; i++ ) {
+ if(rowPrivacy[i] == PrivacyConstraint.PrivacyLevel.Private) {
+ // mark entire row private
+ mergedFineGrainedConstraints.putRow(i,c2, PrivacyConstraint.PrivacyLevel.Private);
+ }
+ }
+
+ for ( int j = 0; j < colPrivacy.length; j++ ) {
+ if(colPrivacy[j] == PrivacyConstraint.PrivacyLevel.Private) {
+ // mark entire col private
+ mergedFineGrainedConstraints.putCol(j,r1, PrivacyConstraint.PrivacyLevel.Private);
+ }
+ }
+
+ for ( int k = 0; k < operatorTypes1.length; k++ ){
+ if ( operatorTypes1[k] == OperatorType.NonAggregate ){
+ if ( rowPrivacy[k] == PrivacyConstraint.PrivacyLevel.PrivateAggregation ){
+ // Mark entire row PrivateAggregation
+ mergedFineGrainedConstraints.putRow(k,c2, PrivacyConstraint.PrivacyLevel.PrivateAggregation);
+ } else if ( rowPrivacy[k] != PrivacyConstraint.PrivacyLevel.Private ){
+ // Go through each element of colPrivacy and if element is PrivateAggregation then mark cell as PrivateAggregation
+ for ( int l = 0; l < colPrivacy.length; l++ ){
+ if ( colPrivacy[l] == PrivacyConstraint.PrivacyLevel.PrivateAggregation )
+ mergedFineGrainedConstraints.putElement(k,l, PrivacyConstraint.PrivacyLevel.PrivateAggregation);
+ }
+ }
+ }
+ }
+
+ // Do the same for operatorTypes2
+ for ( int k = 0; k < operatorTypes2.length; k++ ){
+ if ( operatorTypes2[k] == OperatorType.NonAggregate ){
+ if ( colPrivacy[k] == PrivacyConstraint.PrivacyLevel.PrivateAggregation ){
+ // Mark entire col PrivateAggregation
+ mergedFineGrainedConstraints.putCol(k,r1, PrivacyConstraint.PrivacyLevel.PrivateAggregation);
+ } else if ( colPrivacy[k] != PrivacyConstraint.PrivacyLevel.Private ){
+ // Go through each element of rowPrivacy and if element is PrivateAggregation then mark cell as PrivateAggregation
+ for ( int l = 0; l < rowPrivacy.length; l++ ){
+ if ( rowPrivacy[l] == PrivacyConstraint.PrivacyLevel.PrivateAggregation )
+ mergedFineGrainedConstraints.putElement(k,l, PrivacyConstraint.PrivacyLevel.PrivateAggregation);
+ }
+ }
+ }
+ }
+ }
+}
diff --git a/src/main/java/org/apache/sysds/runtime/privacy/propagation/MatrixMultiplicationPropagatorPrivateFirstOptimized.java b/src/main/java/org/apache/sysds/runtime/privacy/propagation/MatrixMultiplicationPropagatorPrivateFirstOptimized.java
new file mode 100644
index 0000000..f2a8aa9
--- /dev/null
+++ b/src/main/java/org/apache/sysds/runtime/privacy/propagation/MatrixMultiplicationPropagatorPrivateFirstOptimized.java
@@ -0,0 +1,85 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.sysds.runtime.privacy.propagation;
+
+import org.apache.sysds.runtime.privacy.PrivacyConstraint;
+import org.apache.sysds.runtime.privacy.finegrained.FineGrainedPrivacy;
+
+/**
+ * MatrixMultiplicationPropagator that overrides generateFineGrainedConstraints by finding the private elements first
+ * while propagating PrivateAggregation in case of non-aggregating operator types. This is an optimized version of
+ * MatrixMultiplicationPropagatorPrivateFirst since it does both kinds of propagation in the same loop.
+ */
+public class MatrixMultiplicationPropagatorPrivateFirstOptimized extends MatrixMultiplicationPropagator {
+
+ /**
+ * Generates fine-grained constraints and puts them in the mergedFineGrainedConstraints instance.
+ * This implementation loops over the rowPrivacy array and sets the entire row to private if the rowPrivacy is private.
+ * During this loop, if the element is not private, it will check the operator type and check for private aggregation level.
+ * If the operator type is non-aggregate and the privacy level is PrivateAggregation,
+ * then it sets the entire row/column to PrivateAggregation.
+ * If the operator type is non-aggregate and the privacy level is not private, then it loops through all elements
+ * in the row/column and checks for PrivateAggregation in the privacy level array of the other input.
+ */
+ @Override
+ protected void generateFineGrainedConstraints(FineGrainedPrivacy mergedFineGrainedConstraints,
+ PrivacyConstraint.PrivacyLevel[] rowPrivacy, PrivacyConstraint.PrivacyLevel[] colPrivacy,
+ OperatorType[] operatorTypes1, OperatorType[] operatorTypes2) {
+ int r1 = rowPrivacy.length;
+ int c2 = colPrivacy.length;
+ for ( int i = 0; i < rowPrivacy.length; i++ ) {
+ if(rowPrivacy[i] == PrivacyConstraint.PrivacyLevel.Private) {
+ // mark entire row private
+ mergedFineGrainedConstraints.putRow(i,c2, PrivacyConstraint.PrivacyLevel.Private);
+ }
+ else if ( operatorTypes1[i] == OperatorType.NonAggregate ){
+ if ( rowPrivacy[i] == PrivacyConstraint.PrivacyLevel.PrivateAggregation ){
+ // Mark entire row PrivateAggregation
+ mergedFineGrainedConstraints.putRow(i,c2, PrivacyConstraint.PrivacyLevel.PrivateAggregation);
+ } else { // rowPrivacy[i] is None, but colPrivacy could be PrivateAggregation
+ // Go through each element of colPrivacy and if element is PrivateAggregation then mark cell as PrivateAggregation
+ for ( int l = 0; l < colPrivacy.length; l++ ){
+ if ( colPrivacy[l] == PrivacyConstraint.PrivacyLevel.PrivateAggregation )
+ mergedFineGrainedConstraints.putElement(i,l, PrivacyConstraint.PrivacyLevel.PrivateAggregation);
+ }
+ }
+ }
+ }
+
+ for ( int j = 0; j < colPrivacy.length; j++ ) {
+ if(colPrivacy[j] == PrivacyConstraint.PrivacyLevel.Private) {
+ // mark entire col private
+ mergedFineGrainedConstraints.putCol(j,r1, PrivacyConstraint.PrivacyLevel.Private);
+ }
+ else if ( operatorTypes2[j] == OperatorType.NonAggregate ){
+ if ( colPrivacy[j] == PrivacyConstraint.PrivacyLevel.PrivateAggregation ){
+ // Mark entire col PrivateAggregation
+ mergedFineGrainedConstraints.putCol(j,r1, PrivacyConstraint.PrivacyLevel.PrivateAggregation);
+ } else { // colPrivacy[j] is None, but rowPrivacy could be PrivateAggregation
+ // Go through each element of rowPrivacy and if element is PrivateAggregation then mark cell as PrivateAggregation
+ for ( int l = 0; l < rowPrivacy.length; l++ ){
+ if ( rowPrivacy[l] == PrivacyConstraint.PrivacyLevel.PrivateAggregation )
+ mergedFineGrainedConstraints.putElement(j,l, PrivacyConstraint.PrivacyLevel.PrivateAggregation);
+ }
+ }
+ }
+ }
+ }
+}
diff --git a/src/main/java/org/apache/sysds/runtime/privacy/propagation/OperatorType.java b/src/main/java/org/apache/sysds/runtime/privacy/propagation/OperatorType.java
new file mode 100644
index 0000000..18a94b1
--- /dev/null
+++ b/src/main/java/org/apache/sysds/runtime/privacy/propagation/OperatorType.java
@@ -0,0 +1,25 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.sysds.runtime.privacy.propagation;
+
+public enum OperatorType {
+ Aggregate,
+ NonAggregate;
+}
diff --git a/src/main/java/org/apache/sysds/runtime/privacy/PrivacyPropagator.java b/src/main/java/org/apache/sysds/runtime/privacy/propagation/PrivacyPropagator.java
similarity index 85%
rename from src/main/java/org/apache/sysds/runtime/privacy/PrivacyPropagator.java
rename to src/main/java/org/apache/sysds/runtime/privacy/propagation/PrivacyPropagator.java
index 734eb0c..7b66e87 100644
--- a/src/main/java/org/apache/sysds/runtime/privacy/PrivacyPropagator.java
+++ b/src/main/java/org/apache/sysds/runtime/privacy/propagation/PrivacyPropagator.java
@@ -17,7 +17,7 @@
* under the License.
*/
-package org.apache.sysds.runtime.privacy;
+package org.apache.sysds.runtime.privacy.propagation;
import java.util.*;
@@ -42,9 +42,9 @@ import org.apache.sysds.runtime.instructions.cp.SqlCPInstruction;
import org.apache.sysds.runtime.instructions.cp.UnaryCPInstruction;
import org.apache.sysds.runtime.instructions.cp.VariableCPInstruction;
import org.apache.sysds.runtime.matrix.data.MatrixBlock;
+import org.apache.sysds.runtime.privacy.DMLPrivacyException;
+import org.apache.sysds.runtime.privacy.PrivacyConstraint;
import org.apache.sysds.runtime.privacy.PrivacyConstraint.PrivacyLevel;
-import org.apache.sysds.runtime.privacy.finegrained.DataRange;
-import org.apache.sysds.runtime.privacy.finegrained.FineGrainedPrivacy;
import org.apache.wink.json4j.JSONException;
import org.apache.wink.json4j.JSONObject;
@@ -64,7 +64,61 @@ public class PrivacyPropagator
}
return cd;
}
-
+
+ private static boolean anyInputHasLevel(PrivacyLevel[] inputLevels, PrivacyLevel targetLevel){
+ return Arrays.stream(inputLevels).anyMatch(i -> i == targetLevel);
+ }
+
+ /**
+ * Returns the output privacy level based on the given input privacy levels and operator type.
+ * It represents the basic logic of privacy propagation:
+ *
+ * Unary input:
+ * Input | NonAggregate | Aggregate
+ * -----------------------------------
+ * priv | priv | priv
+ * privAgg | privAgg | none
+ * none | none | none
+ *
+ * Binary input:
+ * Input | NonAggregate | Aggregate
+ * --------------------------------------------
+ * priv-priv | priv | priv
+ * priv-privAgg | priv | priv
+ * priv-none | priv | priv
+ * privAgg-priv | priv | priv
+ * none-priv | priv | priv
+ * privAgg-privAgg | privAgg | none
+ * none-none | none | none
+ * privAgg-none | privAgg | none
+ * none-privAgg | privAgg | none
+ *
+ * @param inputLevels privacy levels of the input
+ * @param operatorType type of the operator which is either an aggregation (Aggregate) or not an aggregation (NonAggregate)
+ * @return output privacy level
+ */
+ public static PrivacyLevel corePropagation(PrivacyLevel[] inputLevels, OperatorType operatorType){
+ if (anyInputHasLevel(inputLevels, PrivacyLevel.Private))
+ return PrivacyLevel.Private;
+ if (operatorType == OperatorType.Aggregate)
+ return PrivacyLevel.None;
+ if (operatorType == OperatorType.NonAggregate && anyInputHasLevel(inputLevels,PrivacyLevel.PrivateAggregation))
+ return PrivacyLevel.PrivateAggregation;
+ return PrivacyLevel.None;
+ }
+
+ public static PrivacyConstraint mergeNary(PrivacyConstraint[] privacyConstraints, OperatorType operatorType){
+ PrivacyLevel[] privacyLevels = Arrays.stream(privacyConstraints)
+ .map(constraint -> {
+ if (constraint != null)
+ return constraint.getPrivacyLevel();
+ else return PrivacyLevel.None;
+ })
+ .toArray(PrivacyLevel[]::new);
+ PrivacyLevel outputPrivacyLevel = corePropagation(privacyLevels, operatorType);
+ return new PrivacyConstraint(outputPrivacyLevel);
+ }
+
public static PrivacyConstraint mergeBinary(PrivacyConstraint privacyConstraint1, PrivacyConstraint privacyConstraint2) {
if (privacyConstraint1 != null && privacyConstraint2 != null){
PrivacyLevel privacyLevel1 = privacyConstraint1.getPrivacyLevel();
@@ -228,10 +282,12 @@ public class PrivacyPropagator
if ( (privacyConstraint1 != null && privacyConstraint1.hasFineGrainedConstraints() ) || (privacyConstraint2 != null && privacyConstraint2.hasFineGrainedConstraints() )){
MatrixBlock input1 = ec.getMatrixInput(inst.input1.getName());
MatrixBlock input2 = ec.getMatrixInput(inst.input2.getName());
- mergedPrivacyConstraint = matrixMultiplicationPropagation(input1, privacyConstraint1, input2, privacyConstraint2);
+ Propagator propagator = new MatrixMultiplicationPropagatorPrivateFirst(input1, privacyConstraint1, input2, privacyConstraint2);
+ mergedPrivacyConstraint = propagator.propagate();
}
else {
- mergedPrivacyConstraint = mergeBinary(privacyConstraint1, privacyConstraint2);
+ mergedPrivacyConstraint = mergeNary(new PrivacyConstraint[]{privacyConstraint1,privacyConstraint2},
+ OperatorType.NonAggregate);
inst.setPrivacyConstraint(mergedPrivacyConstraint);
}
inst.output.setPrivacyConstraint(mergedPrivacyConstraint);
@@ -251,58 +307,6 @@ public class PrivacyPropagator
}
/**
- * Return the merged fine-grained privacy constraint of a matrix multiplication with the given privacy constraints.
- * The current implementation has a tendency to create small ranges of privacy level private. These ranges could be merged
- * to create fewer ranges spanning the same elements.
- * @param input1 first input matrix block
- * @param privacyConstraint1 privacy constraint of the first matrix
- * @param input2 second input matrix block
- * @param privacyConstraint2 privacy constraint of the second matrix
- * @return merged privacy constraint
- */
- public static PrivacyConstraint matrixMultiplicationPropagation(MatrixBlock input1, PrivacyConstraint privacyConstraint1, MatrixBlock input2, PrivacyConstraint privacyConstraint2){
- // If the overall privacy level is private, then the fine-grained constraints do not have to be checked.
- if ( (privacyConstraint1 != null && privacyConstraint1.getPrivacyLevel() == PrivacyLevel.Private) || (privacyConstraint2 != null && privacyConstraint2.getPrivacyLevel() == PrivacyLevel.Private) )
- return new PrivacyConstraint(PrivacyLevel.Private);
-
- boolean hasOverallConstraintAggregate = ( (privacyConstraint1 != null && privacyConstraint1.getPrivacyLevel() == PrivacyLevel.PrivateAggregation ) || ( privacyConstraint2 != null && privacyConstraint2.getPrivacyLevel() == PrivacyLevel.PrivateAggregation));
- PrivacyConstraint mergedConstraint = new PrivacyConstraint();
- if ( hasOverallConstraintAggregate )
- mergedConstraint.setPrivacyLevel(PrivacyLevel.PrivateAggregation);
-
- int r1 = input1.getNumRows();
- int c1 = input1.getNumColumns();
- int r2 = input2.getNumRows();
- int c2 = input2.getNumColumns();
- FineGrainedPrivacy mergedFineGrainedConstraints = mergedConstraint.getFineGrainedPrivacy();
-
- for (int i = 0; i < r1; i++){
-
- // Get privacy of first matrix row
- long[] beginRange1 = new long[]{i,0};
- long[] endRange1 = new long[]{i,c1};
- Map<DataRange, PrivacyLevel> privacyInRow = (privacyConstraint1 != null) ? privacyConstraint1.getFineGrainedPrivacy().getPrivacyLevel(new DataRange(beginRange1, endRange1)) : new HashMap<>();
-
- for (int j = 0; j < c2; j++){
- // Get Privacy of Second matrix col
- long[] beginRange2 = new long[]{0,j};
- long[] endRange2 = new long[]{r2,j};
- Map<DataRange, PrivacyLevel> privacyInCol = (privacyConstraint2 != null) ? privacyConstraint2.getFineGrainedPrivacy().getPrivacyLevel(new DataRange(beginRange2, endRange2)) : new HashMap<>();
-
- // if any elements in the row or col has privacy level private or privateaggregate,
- // then output element in the index should be same level.
- long[] beginRangeMerged = new long[]{i,j};
- long[] endRangeMerged = new long[]{i,j};
- if ( privacyInRow.containsValue(PrivacyLevel.Private) || privacyInCol.containsValue(PrivacyLevel.Private))
- mergedFineGrainedConstraints.put(new DataRange(beginRangeMerged, endRangeMerged), PrivacyLevel.Private);
- else if ( !hasOverallConstraintAggregate && (privacyInRow.containsValue(PrivacyLevel.PrivateAggregation) || privacyInCol.containsValue(PrivacyLevel.PrivateAggregation) ))
- mergedFineGrainedConstraints.put(new DataRange(beginRangeMerged, endRangeMerged), PrivacyLevel.PrivateAggregation);
- }
- }
- return mergedConstraint;
- }
-
- /**
* Propagate privacy constraint to output if any of the elements are private.
* Privacy constraint is always propagated to instruction.
* @param inst aggregate instruction
@@ -572,8 +576,8 @@ public class PrivacyPropagator
private static boolean privacyConstraintActivated(PrivacyConstraint instructionPrivacyConstraint){
return instructionPrivacyConstraint != null &&
- (instructionPrivacyConstraint.privacyLevel == PrivacyLevel.Private
- || instructionPrivacyConstraint.privacyLevel == PrivacyLevel.PrivateAggregation);
+ (instructionPrivacyConstraint.getPrivacyLevel() == PrivacyLevel.Private
+ || instructionPrivacyConstraint.getPrivacyLevel() == PrivacyLevel.PrivateAggregation);
}
@SuppressWarnings("unused")
diff --git a/src/main/java/org/apache/sysds/runtime/privacy/propagation/Propagator.java b/src/main/java/org/apache/sysds/runtime/privacy/propagation/Propagator.java
new file mode 100644
index 0000000..48a261a
--- /dev/null
+++ b/src/main/java/org/apache/sysds/runtime/privacy/propagation/Propagator.java
@@ -0,0 +1,33 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.sysds.runtime.privacy.propagation;
+
+import org.apache.sysds.runtime.privacy.PrivacyConstraint;
+
+/**
+ * Interface for all propagator instances.
+ */
+public interface Propagator {
+ /**
+ * Activates the propagation and returns the output privacy constraint.
+ * @return output privacy constraint.
+ */
+ PrivacyConstraint propagate();
+}
diff --git a/src/test/java/org/apache/sysds/test/functions/privacy/CorePropagatorTest.java b/src/test/java/org/apache/sysds/test/functions/privacy/CorePropagatorTest.java
new file mode 100644
index 0000000..a359a7d
--- /dev/null
+++ b/src/test/java/org/apache/sysds/test/functions/privacy/CorePropagatorTest.java
@@ -0,0 +1,80 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.sysds.test.functions.privacy;
+
+import org.apache.sysds.test.AutomatedTestBase;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+import java.util.Arrays;
+import java.util.Collection;
+import org.apache.sysds.runtime.privacy.propagation.PrivacyPropagator;
+import org.apache.sysds.runtime.privacy.propagation.OperatorType;
+import org.apache.sysds.runtime.privacy.PrivacyConstraint.PrivacyLevel;
+
+import static org.junit.Assert.assertEquals;
+
+@RunWith(value = Parameterized.class)
+public class CorePropagatorTest extends AutomatedTestBase {
+
+ protected PrivacyLevel[] input;
+ protected OperatorType operatorType;
+ protected PrivacyLevel expectedPrivacyLevel;
+
+ public CorePropagatorTest(PrivacyLevel[] input, OperatorType operatorType, PrivacyLevel expectedPrivacyLevel) {
+ this.input = input;
+ this.operatorType = operatorType;
+ this.expectedPrivacyLevel = expectedPrivacyLevel;
+ }
+
+ @Override public void setUp() {}
+
+ @Test
+ public void corePropagation(){
+ PrivacyLevel outputLevel = PrivacyPropagator.corePropagation(input, operatorType);
+ assertEquals(expectedPrivacyLevel, outputLevel);
+ }
+
+ @Parameterized.Parameters
+ public static Collection<Object[]> data() {
+ Object[][] data = new Object[][] {
+ {new PrivacyLevel[]{PrivacyLevel.Private, PrivacyLevel.Private}, OperatorType.NonAggregate, PrivacyLevel.Private},
+ {new PrivacyLevel[]{PrivacyLevel.Private, PrivacyLevel.Private}, OperatorType.Aggregate, PrivacyLevel.Private},
+ {new PrivacyLevel[]{PrivacyLevel.Private, PrivacyLevel.PrivateAggregation}, OperatorType.NonAggregate, PrivacyLevel.Private},
+ {new PrivacyLevel[]{PrivacyLevel.Private, PrivacyLevel.PrivateAggregation}, OperatorType.Aggregate, PrivacyLevel.Private},
+ {new PrivacyLevel[]{PrivacyLevel.Private, PrivacyLevel.None}, OperatorType.NonAggregate, PrivacyLevel.Private},
+ {new PrivacyLevel[]{PrivacyLevel.Private, PrivacyLevel.None}, OperatorType.Aggregate, PrivacyLevel.Private},
+ {new PrivacyLevel[]{PrivacyLevel.PrivateAggregation, PrivacyLevel.Private}, OperatorType.NonAggregate, PrivacyLevel.Private},
+ {new PrivacyLevel[]{PrivacyLevel.PrivateAggregation, PrivacyLevel.Private}, OperatorType.Aggregate, PrivacyLevel.Private},
+ {new PrivacyLevel[]{PrivacyLevel.None, PrivacyLevel.Private}, OperatorType.NonAggregate, PrivacyLevel.Private},
+ {new PrivacyLevel[]{PrivacyLevel.None, PrivacyLevel.Private}, OperatorType.Aggregate, PrivacyLevel.Private},
+ {new PrivacyLevel[]{PrivacyLevel.PrivateAggregation, PrivacyLevel.PrivateAggregation}, OperatorType.NonAggregate, PrivacyLevel.PrivateAggregation},
+ {new PrivacyLevel[]{PrivacyLevel.PrivateAggregation, PrivacyLevel.PrivateAggregation}, OperatorType.Aggregate, PrivacyLevel.None},
+ {new PrivacyLevel[]{PrivacyLevel.None, PrivacyLevel.None}, OperatorType.NonAggregate, PrivacyLevel.None},
+ {new PrivacyLevel[]{PrivacyLevel.None, PrivacyLevel.None}, OperatorType.Aggregate, PrivacyLevel.None},
+ {new PrivacyLevel[]{PrivacyLevel.PrivateAggregation, PrivacyLevel.None}, OperatorType.NonAggregate, PrivacyLevel.PrivateAggregation},
+ {new PrivacyLevel[]{PrivacyLevel.PrivateAggregation, PrivacyLevel.None}, OperatorType.Aggregate, PrivacyLevel.None},
+ {new PrivacyLevel[]{PrivacyLevel.None, PrivacyLevel.PrivateAggregation}, OperatorType.NonAggregate, PrivacyLevel.PrivateAggregation},
+ {new PrivacyLevel[]{PrivacyLevel.None, PrivacyLevel.PrivateAggregation}, OperatorType.Aggregate, PrivacyLevel.None}
+ };
+ return Arrays.asList(data);
+ }
+}
diff --git a/src/test/java/org/apache/sysds/test/functions/privacy/PrivacyPropagatorTest.java b/src/test/java/org/apache/sysds/test/functions/privacy/PrivacyPropagatorTest.java
index 1d9f833..9fbf54c 100644
--- a/src/test/java/org/apache/sysds/test/functions/privacy/PrivacyPropagatorTest.java
+++ b/src/test/java/org/apache/sysds/test/functions/privacy/PrivacyPropagatorTest.java
@@ -19,20 +19,22 @@
package org.apache.sysds.test.functions.privacy;
-import static org.junit.Assert.assertEquals;
-import static org.junit.Assert.assertFalse;
-import static org.junit.Assert.assertTrue;
-
+import java.util.List;
import java.util.Map;
+import java.util.stream.Stream;
+import org.apache.sysds.runtime.data.DenseBlock;
+import org.apache.sysds.runtime.data.DenseBlockLFP64;
import org.apache.sysds.runtime.matrix.data.MatrixBlock;
import org.apache.sysds.runtime.privacy.PrivacyConstraint;
-import org.apache.sysds.runtime.privacy.PrivacyPropagator;
+import org.apache.sysds.runtime.privacy.propagation.*;
import org.apache.sysds.runtime.privacy.PrivacyConstraint.PrivacyLevel;
import org.apache.sysds.runtime.privacy.finegrained.DataRange;
import org.apache.sysds.test.AutomatedTestBase;
import org.junit.Test;
+import static org.junit.Assert.*;
+
public class PrivacyPropagatorTest extends AutomatedTestBase {
@Override
@@ -42,37 +44,151 @@ public class PrivacyPropagatorTest extends AutomatedTestBase {
}
@Test
- public void matrixMultiplicationPropagationTestPrivateGeneral(){
- MatrixBlock inputMatrix1 = new MatrixBlock(10,20,15);
- MatrixBlock inputMatrix2 = new MatrixBlock(20,30,12);
+ public void matrixMultiplicationPropagationTestPrivateGeneralNoFineGrained(){
+ PrivacyConstraint constraint1 = new PrivacyConstraint(PrivacyLevel.Private);
+ PrivacyConstraint constraint2 = new PrivacyConstraint();
+ MatrixMultiplicationPropagator propagator = new MatrixMultiplicationPropagatorPrivateFirst();
+ mmGeneralNoFineGrainedGeneralized(constraint1,constraint2, propagator);
+ }
+
+ @Test
+ public void matrixMultiplicationPropagationTestPrivateGeneralNoFineGrained2(){
+ PrivacyConstraint constraint1 = new PrivacyConstraint();
+ PrivacyConstraint constraint2 = new PrivacyConstraint(PrivacyLevel.Private);
+ MatrixMultiplicationPropagator propagator = new MatrixMultiplicationPropagatorPrivateFirst();
+ mmGeneralNoFineGrainedGeneralized(constraint1, constraint2, propagator);
+ }
+
+ @Test
+ public void matrixMultiplicationPropagationTestPrivateGeneralNoFineGrainedNaive(){
PrivacyConstraint constraint1 = new PrivacyConstraint(PrivacyLevel.Private);
- constraint1.getFineGrainedPrivacy().put(new DataRange(new long[]{3,8},new long[]{2,5}), PrivacyLevel.Private);
PrivacyConstraint constraint2 = new PrivacyConstraint();
- PrivacyConstraint mergedConstraint = PrivacyPropagator.matrixMultiplicationPropagation(inputMatrix1, constraint1, inputMatrix2, constraint2);
+ MatrixMultiplicationPropagator propagator = new MatrixMultiplicationPropagatorNaive();
+ mmGeneralNoFineGrainedGeneralized(constraint1,constraint2, propagator);
+ }
+
+ @Test
+ public void matrixMultiplicationPropagationTestPrivateGeneralNoFineGrained2Naive(){
+ PrivacyConstraint constraint1 = new PrivacyConstraint();
+ PrivacyConstraint constraint2 = new PrivacyConstraint(PrivacyLevel.Private);
+ MatrixMultiplicationPropagator propagator = new MatrixMultiplicationPropagatorNaive();
+ mmGeneralNoFineGrainedGeneralized(constraint1, constraint2, propagator);
+ }
+
+ @Test
+ public void matrixMultiplicationPropagationTestPrivateGeneralNoFineGrained3(){
+ PrivacyConstraint constraint1 = new PrivacyConstraint(PrivacyLevel.Private);
+ PrivacyConstraint constraint2 = new PrivacyConstraint(PrivacyLevel.PrivateAggregation);
+ MatrixMultiplicationPropagator propagator = new MatrixMultiplicationPropagatorPrivateFirst();
+ mmGeneralNoFineGrainedGeneralized(constraint1, constraint2, propagator);
+ }
+
+ @Test
+ public void matrixMultiplicationPropagationTestPrivateGeneralNoFineGrained3Naive(){
+ PrivacyConstraint constraint1 = new PrivacyConstraint(PrivacyLevel.Private);
+ PrivacyConstraint constraint2 = new PrivacyConstraint(PrivacyLevel.PrivateAggregation);
+ MatrixMultiplicationPropagator propagator = new MatrixMultiplicationPropagatorNaive();
+ mmGeneralNoFineGrainedGeneralized(constraint1, constraint2, propagator);
+ }
+
+ @Test
+ public void matrixMultiplicationPropagationTestPrivateGeneralNoFineGrained4(){
+ PrivacyConstraint constraint1 = new PrivacyConstraint(PrivacyLevel.Private);
+ PrivacyConstraint constraint2 = new PrivacyConstraint(PrivacyLevel.Private);
+ MatrixMultiplicationPropagator propagator = new MatrixMultiplicationPropagatorPrivateFirst();
+ mmGeneralNoFineGrainedGeneralized(constraint1, constraint2, propagator);
+ }
+
+ @Test
+ public void matrixMultiplicationPropagationTestPrivateGeneralNoFineGrained4Naive(){
+ PrivacyConstraint constraint1 = new PrivacyConstraint(PrivacyLevel.Private);
+ PrivacyConstraint constraint2 = new PrivacyConstraint(PrivacyLevel.Private);
+ MatrixMultiplicationPropagator propagator = new MatrixMultiplicationPropagatorNaive();
+ mmGeneralNoFineGrainedGeneralized(constraint1, constraint2, propagator);
+ }
+
+ @Test
+ public void matrixMultiplicationPropagationTestPrivateGeneralNoFineGrained5(){
+ PrivacyConstraint constraint1 = new PrivacyConstraint(PrivacyLevel.PrivateAggregation);
+ PrivacyConstraint constraint2 = new PrivacyConstraint(PrivacyLevel.Private);
+ MatrixMultiplicationPropagator propagator = new MatrixMultiplicationPropagatorPrivateFirst();
+ mmGeneralNoFineGrainedGeneralized(constraint1, constraint2, propagator);
+ }
+
+ @Test
+ public void matrixMultiplicationPropagationTestPrivateGeneralNoFineGrained5Naive(){
+ PrivacyConstraint constraint1 = new PrivacyConstraint(PrivacyLevel.PrivateAggregation);
+ PrivacyConstraint constraint2 = new PrivacyConstraint(PrivacyLevel.Private);
+ MatrixMultiplicationPropagator propagator = new MatrixMultiplicationPropagatorNaive();
+ mmGeneralNoFineGrainedGeneralized(constraint1, constraint2, propagator);
+ }
+
+
+ private void mmGeneralNoFineGrainedGeneralized(PrivacyConstraint constraint1, PrivacyConstraint constraint2, MatrixMultiplicationPropagator propagator){
+ MatrixBlock inputMatrix1 = new MatrixBlock(10,20,15);
+ MatrixBlock inputMatrix2 = new MatrixBlock(20,30,12);
+ propagator.setFields(inputMatrix1, constraint1, inputMatrix2, constraint2);
+ PrivacyConstraint mergedConstraint = propagator.propagate();
assertTrue("Privacy should be set to Private", mergedConstraint.hasPrivateElements());
assertFalse("Fine grained constraint should not be propagated", mergedConstraint.hasFineGrainedConstraints());
}
- @Test
- public void matrixMultiplicationPropagationTestPrivateGeneral2(){
+ private void mmPropagationPrivateGeneralized(PrivacyLevel fineGrainedPrivacyLevel, MatrixMultiplicationPropagator propagator){
MatrixBlock inputMatrix1 = new MatrixBlock(10,20,15);
MatrixBlock inputMatrix2 = new MatrixBlock(20,30,12);
PrivacyConstraint constraint1 = new PrivacyConstraint(PrivacyLevel.Private);
- constraint1.getFineGrainedPrivacy().put(new DataRange(new long[]{3,8},new long[]{2,5}), PrivacyLevel.PrivateAggregation);
+ constraint1.getFineGrainedPrivacy().put(new DataRange(new long[]{3,8},new long[]{2,5}), fineGrainedPrivacyLevel);
PrivacyConstraint constraint2 = new PrivacyConstraint();
- PrivacyConstraint mergedConstraint = PrivacyPropagator.matrixMultiplicationPropagation(inputMatrix1, constraint1, inputMatrix2, constraint2);
+ propagator.setFields(inputMatrix1, constraint1, inputMatrix2, constraint2);
+ PrivacyConstraint mergedConstraint = propagator.propagate();
assertTrue("Privacy should be set to Private", mergedConstraint.hasPrivateElements());
assertFalse("Fine grained constraint should not be propagated", mergedConstraint.hasFineGrainedConstraints());
}
@Test
- public void matrixMultiplicationPropagationTestPrivateFineGrained(){
+ public void matrixMultiplicationPropagationTestPrivateGeneral(){
+ MatrixMultiplicationPropagator propagator = new MatrixMultiplicationPropagatorPrivateFirst();
+ mmPropagationPrivateGeneralized(PrivacyLevel.Private, propagator);
+ }
+
+ @Test
+ public void matrixMultiplicationPropagationTestPrivateGeneral2() {
+ MatrixMultiplicationPropagator propagator = new MatrixMultiplicationPropagatorPrivateFirst();
+ mmPropagationPrivateGeneralized(PrivacyLevel.PrivateAggregation, propagator);
+ }
+
+ @Test
+ public void matrixMultiplicationPropagationTestPrivateGeneralNaive(){
+ MatrixMultiplicationPropagator propagator = new MatrixMultiplicationPropagatorNaive();
+ mmPropagationPrivateGeneralized(PrivacyLevel.Private, propagator);
+ }
+
+ @Test
+ public void matrixMultiplicationPropagationTestPrivateGeneral2Naive() {
+ MatrixMultiplicationPropagator propagator = new MatrixMultiplicationPropagatorNaive();
+ mmPropagationPrivateGeneralized(PrivacyLevel.PrivateAggregation, propagator);
+ }
+
+ @Test
+ public void matrixMultiplicationPropagationTestPrivateGeneralPrivateFirstOptimized(){
+ MatrixMultiplicationPropagator propagator = new MatrixMultiplicationPropagatorPrivateFirstOptimized();
+ mmPropagationPrivateGeneralized(PrivacyLevel.Private, propagator);
+ }
+
+ @Test
+ public void matrixMultiplicationPropagationTestPrivateGeneral2PrivateFirstOptimized() {
+ MatrixMultiplicationPropagator propagator = new MatrixMultiplicationPropagatorPrivateFirstOptimized();
+ mmPropagationPrivateGeneralized(PrivacyLevel.PrivateAggregation, propagator);
+ }
+
+ private void mmPropagationTestPrivateFineGrainedGeneralized(MatrixMultiplicationPropagator propagator){
MatrixBlock inputMatrix1 = new MatrixBlock(4,3,2);
MatrixBlock inputMatrix2 = new MatrixBlock(3,3,4);
PrivacyConstraint constraint1 = new PrivacyConstraint();
constraint1.getFineGrainedPrivacy().put(new DataRange(new long[]{1,0},new long[]{1,1}), PrivacyLevel.Private);
PrivacyConstraint constraint2 = new PrivacyConstraint();
- PrivacyConstraint mergedConstraint = PrivacyPropagator.matrixMultiplicationPropagation(inputMatrix1, constraint1, inputMatrix2, constraint2);
+ propagator.setFields(inputMatrix1, constraint1, inputMatrix2, constraint2);
+ PrivacyConstraint mergedConstraint = propagator.propagate();
assertTrue("Privacy should be set to Private", mergedConstraint.hasPrivateElements());
assertTrue("Fine grained constraint should not be propagated", mergedConstraint.hasFineGrainedConstraints());
assertTrue("Merged constraint should not contain privacy level PrivateAggregation", mergedConstraint.getFineGrainedPrivacy().getDataRangesOfPrivacyLevel(PrivacyLevel.PrivateAggregation).length == 0);
@@ -85,23 +201,398 @@ public class PrivacyPropagatorTest extends AutomatedTestBase {
assertTrue("Privacy level of element 1 is Private", outputElement1.containsValue(PrivacyLevel.Private));
assertTrue("Privacy level of element 2 is Private", outputElement2.containsValue(PrivacyLevel.Private));
assertTrue("Privacy level of element 3 is Private", outputElement3.containsValue(PrivacyLevel.Private));
- assertTrue("Any other index has no privacy constraint", mergedConstraint.getFineGrainedPrivacy().getPrivacyLevel(new DataRange(new long[]{2,0}, new long[]{3,2})).isEmpty() );
+ Map<DataRange, PrivacyLevel> expectedEmpty = mergedConstraint.getFineGrainedPrivacy().getPrivacyLevel(new DataRange(new long[]{2,0}, new long[]{3,2}));
+ assertTrue("Any other index has no privacy constraint", expectedEmpty.isEmpty() ||
+ (!expectedEmpty.containsValue(PrivacyLevel.Private)
+ && !expectedEmpty.containsValue(PrivacyLevel.PrivateAggregation)));
}
@Test
- public void matrixMultiplicationPropagationTestPrivateFineGrained2(){
+ public void matrixMultiplicationPropagationTestPrivateFineGrained(){
+ MatrixMultiplicationPropagator propagator = new MatrixMultiplicationPropagatorPrivateFirst();
+ mmPropagationTestPrivateFineGrainedGeneralized(propagator);
+ }
+
+ @Test
+ public void matrixMultiplicationPropagationTestPrivateFineGrainedNaive(){
+ MatrixMultiplicationPropagator propagator = new MatrixMultiplicationPropagatorNaive();
+ mmPropagationTestPrivateFineGrainedGeneralized(propagator);
+ }
+
+ @Test
+ public void matrixMultiplicationPropagationTestPrivateFineGrainedPrivateFirstOptimized(){
+ MatrixMultiplicationPropagator propagator = new MatrixMultiplicationPropagatorPrivateFirstOptimized();
+ mmPropagationTestPrivateFineGrainedGeneralized(propagator);
+ }
+
+ private void mmPropagationTestPrivateFineGrained2Generalized(MatrixMultiplicationPropagator propagator){
MatrixBlock inputMatrix1 = new MatrixBlock(4,3,2);
MatrixBlock inputMatrix2 = new MatrixBlock(3,3,4);
PrivacyConstraint constraint1 = new PrivacyConstraint();
PrivacyConstraint constraint2 = new PrivacyConstraint();
constraint2.getFineGrainedPrivacy().put(new DataRange(new long[]{1,0},new long[]{1,1}), PrivacyLevel.Private);
- PrivacyConstraint mergedConstraint = PrivacyPropagator.matrixMultiplicationPropagation(inputMatrix1, constraint1, inputMatrix2, constraint2);
+ propagator.setFields(inputMatrix1, constraint1, inputMatrix2, constraint2);
+ PrivacyConstraint mergedConstraint = propagator.propagate();
assertTrue("Privacy should be set to Private", mergedConstraint.hasPrivateElements());
assertTrue("Fine grained constraint should not be propagated", mergedConstraint.hasFineGrainedConstraints());
assertTrue("Merged constraint should not contain privacy level PrivateAggregation", mergedConstraint.getFineGrainedPrivacy().getDataRangesOfPrivacyLevel(PrivacyLevel.PrivateAggregation).length == 0);
Map<DataRange, PrivacyLevel> outputRange = mergedConstraint.getFineGrainedPrivacy().getPrivacyLevel(new DataRange(new long[]{0,0},new long[]{3,1}));
- assertEquals(8, outputRange.size());
assertTrue("Privacy level is Private", outputRange.containsValue(PrivacyLevel.Private));
- assertTrue("Any other index has no privacy constraint", mergedConstraint.getFineGrainedPrivacy().getPrivacyLevel(new DataRange(new long[]{0,2}, new long[]{3,2})).isEmpty() );
+ Map<DataRange, PrivacyLevel> expectedEmpty = mergedConstraint.getFineGrainedPrivacy().getPrivacyLevel(new DataRange(new long[]{0,2}, new long[]{3,2}));
+ assertTrue("Any other index has no privacy constraint", expectedEmpty.isEmpty() ||
+ (!expectedEmpty.containsValue(PrivacyLevel.Private)
+ && !expectedEmpty.containsValue(PrivacyLevel.PrivateAggregation)));
+ }
+
+ @Test
+ public void matrixMultiplicationPropagationTestPrivateFineGrained2(){
+ MatrixMultiplicationPropagator propagator = new MatrixMultiplicationPropagatorPrivateFirst();
+ mmPropagationTestPrivateFineGrained2Generalized(propagator);
+ }
+
+ @Test
+ public void matrixMultiplicationPropagationTestPrivateFineGrained2Naive(){
+ MatrixMultiplicationPropagator propagator = new MatrixMultiplicationPropagatorNaive();
+ mmPropagationTestPrivateFineGrained2Generalized(propagator);
+ }
+
+ @Test
+ public void matrixMultiplicationPropagationTestPrivateFineGrained2PrivateFirstOptimized(){
+ MatrixMultiplicationPropagator propagator = new MatrixMultiplicationPropagatorPrivateFirstOptimized();
+ mmPropagationTestPrivateFineGrained2Generalized(propagator);
+ }
+
+ private void mmPropagationTestPrivatePrivateAggregationFineGrainedGeneralized(MatrixMultiplicationPropagator propagator){
+ //Build
+ MatrixBlock inputMatrix1 = new MatrixBlock(4,3,2);
+ MatrixBlock inputMatrix2 = new MatrixBlock(3,3,4);
+ PrivacyConstraint constraint1 = new PrivacyConstraint();
+ constraint1.getFineGrainedPrivacy().put(new DataRange(new long[]{1,0},new long[]{1,1}), PrivacyLevel.Private);
+ PrivacyConstraint constraint2 = new PrivacyConstraint();
+ constraint2.getFineGrainedPrivacy().put(new DataRange(new long[]{1,0},new long[]{1,1}), PrivacyLevel.PrivateAggregation);
+
+ //Execute
+ propagator.setFields(inputMatrix1, constraint1, inputMatrix2, constraint2);
+ PrivacyConstraint mergedConstraint = propagator.propagate();
+
+ //Assert
+ assertTrue("Privacy should be set to Private", mergedConstraint.hasPrivateElements());
+ assertTrue("Fine grained constraint should not be propagated", mergedConstraint.hasFineGrainedConstraints());
+ assertTrue("Merged constraint should not contain privacy level PrivateAggregation", mergedConstraint.getFineGrainedPrivacy().getDataRangesOfPrivacyLevel(PrivacyLevel.PrivateAggregation).length == 0);
+ Map<DataRange, PrivacyLevel> outputElement1 = mergedConstraint.getFineGrainedPrivacy().getPrivacyLevelOfElement(new long[]{1,0});
+ Map<DataRange, PrivacyLevel> outputElement2 = mergedConstraint.getFineGrainedPrivacy().getPrivacyLevelOfElement(new long[]{1,1});
+ Map<DataRange, PrivacyLevel> outputElement3 = mergedConstraint.getFineGrainedPrivacy().getPrivacyLevelOfElement(new long[]{1,2});
+ assertEquals(1, outputElement1.size());
+ assertEquals(1, outputElement2.size());
+ assertEquals(1, outputElement3.size());
+ assertTrue("Privacy level of element 1 is Private", outputElement1.containsValue(PrivacyLevel.Private));
+ assertTrue("Privacy level of element 2 is Private", outputElement2.containsValue(PrivacyLevel.Private));
+ assertTrue("Privacy level of element 3 is Private", outputElement3.containsValue(PrivacyLevel.Private));
+ Map<DataRange, PrivacyLevel> expectedEmpty = mergedConstraint.getFineGrainedPrivacy().getPrivacyLevel(new DataRange(new long[]{2,0}, new long[]{3,2}));
+ assertTrue("Any other index has no privacy constraint", expectedEmpty.isEmpty() ||
+ (!expectedEmpty.containsValue(PrivacyLevel.Private)
+ && !expectedEmpty.containsValue(PrivacyLevel.PrivateAggregation)));
+ }
+
+ @Test
+ public void matrixMultiplicationPropagationTestPrivatePrivateAggregationFineGrained(){
+ MatrixMultiplicationPropagator propagator = new MatrixMultiplicationPropagatorPrivateFirst();
+ mmPropagationTestPrivatePrivateAggregationFineGrainedGeneralized(propagator);
+ }
+
+ @Test
+ public void matrixMultiplicationPropagationTestPrivatePrivateAggregationFineGrainedNaive(){
+ MatrixMultiplicationPropagator propagator = new MatrixMultiplicationPropagatorNaive();
+ mmPropagationTestPrivatePrivateAggregationFineGrainedGeneralized(propagator);
+ }
+
+ @Test
+ public void matrixMultiplicationPropagationTestPrivatePrivateAggregationFineGrainedPrivateFirstOptimized(){
+ MatrixMultiplicationPropagator propagator = new MatrixMultiplicationPropagatorPrivateFirstOptimized();
+ mmPropagationTestPrivatePrivateAggregationFineGrainedGeneralized(propagator);
+ }
+
+ @Test
+ public void getOperatorTypesRowTest(){
+ int rows = 4;
+ int cols = 2;
+ MatrixBlock m1 = getMatrixBlock(rows, cols);
+ MatrixMultiplicationPropagator propagator = new MatrixMultiplicationPropagatorPrivateFirst(m1, null, null, null);
+ OperatorType[] actual = propagator.getOperatorTypesRow();
+ OperatorType[] expected = Stream.generate(() -> OperatorType.Aggregate).limit(rows).toArray(OperatorType[]::new);
+ assertArrayEquals("All values should be OperatorType.Aggregate", expected, actual);
+ }
+
+ @Test
+ public void getOperatorTypesRowNonAggTest(){
+ int rows = 4;
+ int cols = 2;
+ int nonAggRow = 2;
+ MatrixBlock m1 = getMatrixBlock(rows, cols);
+ // Make a single row NNZ=1
+ m1.getDenseBlock().set(nonAggRow,0,0);
+ MatrixMultiplicationPropagator propagator = new MatrixMultiplicationPropagatorPrivateFirst(m1, null, null, null);
+ OperatorType[] actualArray = propagator.getOperatorTypesRow();
+ OperatorType expected = OperatorType.NonAggregate;
+ assertEquals("All values except one should be OperatorType.Aggregate", expected, actualArray[nonAggRow]);
+ }
+
+ private void getOperatorTypesRowMultipleNonAggTestGeneralized(MatrixMultiplicationPropagator propagator){
+ int rows = 4;
+ int cols = 2;
+ int nonAggRow = 2;
+ MatrixBlock m1 = getMatrixBlock(rows, cols);
+ // Make two rows NNZ=1
+ m1.getDenseBlock().set(nonAggRow,0,0);
+ m1.getDenseBlock().set(nonAggRow+1,0,0);
+ propagator.setFields(m1, null, null, null);
+ OperatorType[] actualArray = propagator.getOperatorTypesRow();
+ OperatorType expected = OperatorType.NonAggregate;
+ assertEquals("All values except two should be OperatorType.Aggregate", expected, actualArray[nonAggRow]);
+ assertEquals("All values except two should be OperatorType.Aggregate", expected, actualArray[nonAggRow+1]);
+ }
+
+ @Test
+ public void getOperatorTypesRowMultipleNonAggTest(){
+ MatrixMultiplicationPropagator propagator = new MatrixMultiplicationPropagatorPrivateFirst();
+ getOperatorTypesRowMultipleNonAggTestGeneralized(propagator);
+ }
+
+ @Test
+ public void getOperatorTypesColTest(){
+ int rows = 2;
+ int cols = 3;
+ MatrixBlock m2 = getMatrixBlock(rows, cols);
+
+ MatrixMultiplicationPropagator propagator = new MatrixMultiplicationPropagatorPrivateFirst(null, null, m2, null);
+ OperatorType[] actual = propagator.getOperatorTypesCol();
+ OperatorType[] expected = Stream.generate(() -> OperatorType.Aggregate).limit(cols).toArray(OperatorType[]::new);
+ assertArrayEquals("All values should be OperatorType.Aggregate", expected, actual);
+ }
+
+ @Test
+ public void getOperatorTypesColNonAggTest(){
+ int rows = 2;
+ int cols = 3;
+ int nonAggCol = 1;
+ MatrixBlock m2 = getMatrixBlock(rows, cols);
+ // Make a single col NNZ=1
+ m2.getDenseBlock().set(0,nonAggCol,0);
+ MatrixMultiplicationPropagator propagator = new MatrixMultiplicationPropagatorPrivateFirst(null, null, m2, null);
+ OperatorType[] actualArray = propagator.getOperatorTypesCol();
+ OperatorType expected = OperatorType.NonAggregate;
+ assertEquals("All values except one should be OperatorType.Aggregate", expected, actualArray[nonAggCol]);
+ }
+
+ private void getOperatorTypesColMultipleNonAggTestGeneralized(MatrixMultiplicationPropagator propagator){
+ int rows = 2;
+ int cols = 3;
+ int nonAggCol = 1;
+ MatrixBlock m2 = getMatrixBlock(rows, cols);
+ // Make two cols NNZ=1
+ m2.getDenseBlock().set(0,nonAggCol,0);
+ m2.getDenseBlock().set(0,nonAggCol+1,0);
+ propagator.setFields(null, null, m2, null);
+ OperatorType[] actualArray = propagator.getOperatorTypesCol();
+ OperatorType expected = OperatorType.NonAggregate;
+ assertEquals("All values except two should be OperatorType.Aggregate", expected, actualArray[nonAggCol]);
+ assertEquals("All values except two should be OperatorType.Aggregate", expected, actualArray[nonAggCol+1]);
+ }
+
+ @Test
+ public void getOperatorTypesColMultipleNonAggTest(){
+ MatrixMultiplicationPropagator propagator = new MatrixMultiplicationPropagatorPrivateFirst();
+ getOperatorTypesColMultipleNonAggTestGeneralized(propagator);
+ }
+
+ private MatrixBlock getMatrixBlock(int rows, int cols){
+ DenseBlock denseM = new DenseBlockLFP64(new int[]{rows,cols});
+ for ( int r = 0; r < rows; r++ ){
+ for ( int c = 0; c < cols; c++ ){
+ denseM.set(r,c,r+c+1);
+ }
+ }
+ return new MatrixBlock(rows,cols,denseM);
+ }
+
+ @Test
+ public void matrixMultiplicationPropagationTestNonAgg(){
+ MatrixMultiplicationPropagator propagator = new MatrixMultiplicationPropagatorPrivateFirst();
+ NonAggGeneralizedTest(PrivacyLevel.PrivateAggregation, propagator);
+ }
+
+ @Test
+ public void matrixMultiplicationPropagationTestNonAggPrivate(){
+ MatrixMultiplicationPropagator propagator = new MatrixMultiplicationPropagatorPrivateFirst();
+ NonAggGeneralizedTest(PrivacyLevel.Private, propagator);
+ }
+
+ @Test
+ public void matrixMultiplicationPropagationTestNonAggNaive(){
+ MatrixMultiplicationPropagator propagator = new MatrixMultiplicationPropagatorNaive();
+ NonAggGeneralizedTest(PrivacyLevel.PrivateAggregation, propagator);
+ }
+
+ @Test
+ public void matrixMultiplicationPropagationTestNonAggPrivateNaive(){
+ MatrixMultiplicationPropagator propagator = new MatrixMultiplicationPropagatorNaive();
+ NonAggGeneralizedTest(PrivacyLevel.Private, propagator);
+ }
+
+ @Test
+ public void matrixMultiplicationPropagationTestNonAggPrivateOptimized(){
+ MatrixMultiplicationPropagator propagator = new MatrixMultiplicationPropagatorPrivateFirstOptimized();
+ NonAggGeneralizedTest(PrivacyLevel.PrivateAggregation, propagator);
+ }
+
+ @Test
+ public void matrixMultiplicationPropagationTestNonAggPrivatePrivateOptimized(){
+ MatrixMultiplicationPropagator propagator = new MatrixMultiplicationPropagatorPrivateFirstOptimized();
+ NonAggGeneralizedTest(PrivacyLevel.Private, propagator);
+ }
+
+ private void NonAggGeneralizedTest(PrivacyLevel privacyLevel, MatrixMultiplicationPropagator propagator){
+ int nonAggRow = 2;
+ MatrixBlock m1 = getMatrixBlock(4,2);
+ MatrixBlock m2 = getMatrixBlock(2, 3);
+ m1.getDenseBlock().set(nonAggRow,0,0);
+ PrivacyConstraint constraint1 = new PrivacyConstraint();
+ constraint1.getFineGrainedPrivacy().putRow(nonAggRow,2,privacyLevel);
+ PrivacyConstraint constraint2 = new PrivacyConstraint();
+ propagator.setFields(m1, constraint1, m2, constraint2);
+ PrivacyConstraint mergedPrivacyConstraint = propagator.propagate();
+ Map<DataRange, PrivacyLevel> constraints = mergedPrivacyConstraint.getFineGrainedPrivacy().getPrivacyLevel(new DataRange(new long[]{nonAggRow,0}, new long[]{nonAggRow,1}));
+ assertTrue("Output constraints should contain the privacy level " + privacyLevel.toString(),
+ constraints.containsValue(privacyLevel));
+ if ( privacyLevel == PrivacyLevel.Private)
+ assertFalse("Output constraints should not contain the privacy level PrivateAggregation",
+ constraints.containsValue(PrivacyLevel.PrivateAggregation));
+ else if ( privacyLevel == PrivacyLevel.PrivateAggregation )
+ assertFalse("Output constraints should not contain the privacy level Private",
+ constraints.containsValue(PrivacyLevel.Private));
+ }
+
+ @Test
+ public void matrixMultiplicationPropagationTestNonAgg2(){
+ MatrixMultiplicationPropagator propagator = new MatrixMultiplicationPropagatorPrivateFirst();
+ NonAggGeneralizedColTest(PrivacyLevel.PrivateAggregation, propagator);
+ }
+
+ @Test
+ public void matrixMultiplicationPropagationTestNonAggPrivate2(){
+ MatrixMultiplicationPropagator propagator = new MatrixMultiplicationPropagatorPrivateFirst();
+ NonAggGeneralizedColTest(PrivacyLevel.Private, propagator);
+ }
+
+ @Test
+ public void matrixMultiplicationPropagationTestNonAgg2Naive(){
+ MatrixMultiplicationPropagator propagator = new MatrixMultiplicationPropagatorNaive();
+ NonAggGeneralizedColTest(PrivacyLevel.PrivateAggregation, propagator);
+ }
+
+ @Test
+ public void matrixMultiplicationPropagationTestNonAggPrivate2Naive(){
+ MatrixMultiplicationPropagator propagator = new MatrixMultiplicationPropagatorNaive();
+ NonAggGeneralizedColTest(PrivacyLevel.Private, propagator);
+ }
+
+ @Test
+ public void matrixMultiplicationPropagationTestNonAgg2PrivateFirstOptimized(){
+ MatrixMultiplicationPropagator propagator = new MatrixMultiplicationPropagatorPrivateFirstOptimized();
+ NonAggGeneralizedColTest(PrivacyLevel.PrivateAggregation, propagator);
+ }
+
+ @Test
+ public void matrixMultiplicationPropagationTestNonAggPrivate2PrivateFirstOptimized(){
+ MatrixMultiplicationPropagator propagator = new MatrixMultiplicationPropagatorPrivateFirstOptimized();
+ NonAggGeneralizedColTest(PrivacyLevel.Private, propagator);
+ }
+
+ private void NonAggGeneralizedColTest(PrivacyLevel privacyLevel, MatrixMultiplicationPropagator propagator){
+ int nonAggCol = 2;
+ MatrixBlock m1 = getMatrixBlock(4,2);
+ MatrixBlock m2 = getMatrixBlock(2, 3);
+ m2.getDenseBlock().set(0,nonAggCol,0);
+ PrivacyConstraint constraint1 = new PrivacyConstraint();
+ PrivacyConstraint constraint2 = new PrivacyConstraint();
+ constraint2.getFineGrainedPrivacy().putCol(nonAggCol,4,privacyLevel);
+ propagator.setFields(m1, constraint1, m2, constraint2);
+ PrivacyConstraint mergedPrivacyConstraint = propagator.propagate();
+ Map<DataRange, PrivacyLevel> constraints = mergedPrivacyConstraint.getFineGrainedPrivacy().getPrivacyLevel(new DataRange(new long[]{0,nonAggCol}, new long[]{3,nonAggCol}));
+ assertTrue("Output constraints should contain the privacy level " + privacyLevel.toString(),
+ constraints.containsValue(privacyLevel));
+ if ( privacyLevel == PrivacyLevel.Private)
+ assertFalse("Output constraints should not contain the privacy level PrivateAggregation",
+ constraints.containsValue(PrivacyLevel.PrivateAggregation));
+ else if ( privacyLevel == PrivacyLevel.PrivateAggregation )
+ assertFalse("Output constraints should not contain the privacy level Private",
+ constraints.containsValue(PrivacyLevel.Private));
+ }
+
+ @Test
+ public void matrixMultiplicationPropagationTestNonAggRowColNA(){
+ MatrixMultiplicationPropagator propagator = new MatrixMultiplicationPropagatorPrivateFirst();
+ NonAggGeneralizedRowColTest(PrivacyLevel.PrivateAggregation, true, propagator);
+ }
+
+ @Test
+ public void matrixMultiplicationPropagationTestNonAggRowColNAA(){
+ MatrixMultiplicationPropagator propagator = new MatrixMultiplicationPropagatorPrivateFirst();
+ NonAggGeneralizedRowColTest(PrivacyLevel.PrivateAggregation, false, propagator);
+ }
+
+ @Test
+ public void matrixMultiplicationPropagationTestNonAggRowColNaiveNA(){
+ MatrixMultiplicationPropagator propagator = new MatrixMultiplicationPropagatorNaive();
+ NonAggGeneralizedRowColTest(PrivacyLevel.PrivateAggregation, true, propagator);
+ }
+
+ @Test
+ public void matrixMultiplicationPropagationTestNonAggRowColNaiveNAA(){
+ MatrixMultiplicationPropagator propagator = new MatrixMultiplicationPropagatorNaive();
+ NonAggGeneralizedRowColTest(PrivacyLevel.PrivateAggregation, false, propagator);
+ }
+
+ @Test
+ public void matrixMultiplicationPropagationTestNonAggRowColPrivateFirstOptimizedNA(){
+ MatrixMultiplicationPropagator propagator = new MatrixMultiplicationPropagatorPrivateFirstOptimized();
+ NonAggGeneralizedRowColTest(PrivacyLevel.PrivateAggregation, true, propagator);
+ }
+
+ @Test
+ public void matrixMultiplicationPropagationTestNonAggRowColPrivateFirstOptimizedNAA(){
+ MatrixMultiplicationPropagator propagator = new MatrixMultiplicationPropagatorPrivateFirstOptimized();
+ NonAggGeneralizedRowColTest(PrivacyLevel.PrivateAggregation, false, propagator);
+ }
+
+ private void NonAggGeneralizedRowColTest(PrivacyLevel privacyLevel, boolean putElement, MatrixMultiplicationPropagator propagator){
+ int nonAgg = 2;
+ MatrixBlock m1 = getMatrixBlock(4,2);
+ MatrixBlock m2 = getMatrixBlock(2, 3);
+ m1.getDenseBlock().set(nonAgg,0,0);
+ PrivacyConstraint constraint1 = new PrivacyConstraint();
+ PrivacyConstraint constraint2 = new PrivacyConstraint();
+ if (putElement)
+ constraint2.getFineGrainedPrivacy().putElement(0,1, privacyLevel);
+ else constraint2.getFineGrainedPrivacy().putCol(1,2,privacyLevel);
+ propagator.setFields(m1, constraint1, m2, constraint2);
+ PrivacyConstraint mergedPrivacyConstraint = propagator.propagate();
+
+ // Check output
+ List<Map.Entry<DataRange, PrivacyLevel>> constraints = mergedPrivacyConstraint.getFineGrainedPrivacy().getAllConstraintsList();
+ int privacyLevelSum = 0;
+ DataRange levelRange = null;
+ PrivacyLevel level = PrivacyLevel.None;
+ for ( Map.Entry constraint : constraints )
+ if ( constraint.getValue() == privacyLevel ){
+ privacyLevelSum++;
+ levelRange = (DataRange)constraint.getKey();
+ level = (PrivacyLevel) constraint.getValue();
+ }
+
+ assertEquals("Output constraint should only contain one privacy level which is not none", 1,privacyLevelSum);
+ assertEquals(new DataRange(new long[]{2,1},new long[]{2,1}), levelRange);
+ assertEquals("Output constraints should contain the privacy level " + privacyLevel.toString(), privacyLevel,
+ level);
}
}