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 <[email protected]>
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);
}
}
